ic_auth/
chain_key_batch.rs

1//! Pure Merkle construction for the existing chain-key batch proof format.
2//!
3//! Hosts own leaf authorization, canonical certificate hashing, issuer ordering
4//! and uniqueness, batch identity, signing and persistence. A tree authenticates
5//! none of those inputs by itself. No runtime, clock or signing effect is used.
6
7use ic_auth_protocol_types::{ChainKeyBatchWitnessStepV1, ChainKeyBatchWitnessV1};
8use sha2::{Digest, Sha256};
9use std::ops::Range;
10use thiserror::Error;
11
12/// Rejection before allocating tree or witness material.
13#[derive(Debug, Error, Eq, PartialEq)]
14pub enum ChainKeyBatchError {
15    /// A batch cannot commit an empty set of leaves.
16    #[error("chain-key batch requires at least one leaf")]
17    EmptyBatch,
18    /// The supplied hashes exceed the host's explicit construction budget.
19    #[error("chain-key batch has {found} leaves, exceeding the limit {max}")]
20    TooManyLeaves { found: usize, max: usize },
21}
22
23/// Build a root and one witness per leaf, preserving the supplied order.
24///
25/// Supply canonical certificate hashes from
26/// [`crate::canonical::chain_key_delegation_cert_hash`] in the host's authorized
27/// issuer order. The host selects `max_leaves` from protected configuration;
28/// empty and over-budget inputs reject before tree allocation. Total witness
29/// material is bounded by `n * ceil(log2(n))` steps for `n <= max_leaves`.
30///
31/// Internal nodes hash `0x01 || left || right` with SHA-256. An unpaired node
32/// advances unchanged, without duplicating itself or adding a witness step.
33/// A singleton's root is its supplied leaf hash and its witness is empty.
34/// Duplicate hashes are preserved; issuer uniqueness is a host policy.
35pub fn merkle_root_and_witnesses(
36    leaf_hashes: &[[u8; 32]],
37    max_leaves: usize,
38) -> Result<([u8; 32], Vec<ChainKeyBatchWitnessV1>), ChainKeyBatchError> {
39    if leaf_hashes.is_empty() {
40        return Err(ChainKeyBatchError::EmptyBatch);
41    }
42    if leaf_hashes.len() > max_leaves {
43        return Err(ChainKeyBatchError::TooManyLeaves {
44            found: leaf_hashes.len(),
45            max: max_leaves,
46        });
47    }
48
49    let mut witnesses = vec![ChainKeyBatchWitnessV1 { steps: Vec::new() }; leaf_hashes.len()];
50    let mut level: Vec<_> = leaf_hashes
51        .iter()
52        .enumerate()
53        .map(|(index, hash)| Node {
54            hash: *hash,
55            leaves: index..index + 1,
56        })
57        .collect();
58    let mut next = Vec::with_capacity(level.len().div_ceil(2));
59    while level.len() > 1 {
60        next.clear();
61        for pair in level.chunks(2) {
62            let left = &pair[0];
63            if pair.len() == 1 {
64                next.push(left.clone());
65                continue;
66            }
67            let right = &pair[1];
68            for index in left.leaves.clone() {
69                witnesses[index]
70                    .steps
71                    .push(ChainKeyBatchWitnessStepV1::RightSibling(right.hash));
72            }
73            for index in right.leaves.clone() {
74                witnesses[index]
75                    .steps
76                    .push(ChainKeyBatchWitnessStepV1::LeftSibling(left.hash));
77            }
78            next.push(Node {
79                hash: node_hash(left.hash, right.hash),
80                leaves: left.leaves.start..right.leaves.end,
81            });
82        }
83        std::mem::swap(&mut level, &mut next);
84    }
85    Ok((level[0].hash, witnesses))
86}
87
88#[derive(Clone)]
89struct Node {
90    hash: [u8; 32],
91    leaves: Range<usize>,
92}
93
94// Callers admit proof-size budgets before reconstruction. This helper is also
95// the verification side of the constructor's existing node-byte contract.
96#[cfg(feature = "chain-key-verification")]
97pub(crate) fn witness_root(leaf: [u8; 32], witness: &ChainKeyBatchWitnessV1) -> [u8; 32] {
98    witness.steps.iter().fold(leaf, |current, step| match step {
99        ChainKeyBatchWitnessStepV1::LeftSibling(hash) => node_hash(*hash, current),
100        ChainKeyBatchWitnessStepV1::RightSibling(hash) => node_hash(current, *hash),
101    })
102}
103
104fn node_hash(left: [u8; 32], right: [u8; 32]) -> [u8; 32] {
105    let mut hasher = Sha256::new();
106    hasher.update([1]);
107    hasher.update(left);
108    hasher.update(right);
109    hasher.finalize().into()
110}
ic_auth/chain_key_batch.rs

ic_auth/
chain_key_batch.rs
