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    while level.len() > 1 {
59        let mut next = Vec::with_capacity(level.len().div_ceil(2));
60        for pair in level.chunks(2) {
61            let left = &pair[0];
62            if pair.len() == 1 {
63                next.push(left.clone());
64                continue;
65            }
66            let right = &pair[1];
67            for index in left.leaves.clone() {
68                witnesses[index]
69                    .steps
70                    .push(ChainKeyBatchWitnessStepV1::RightSibling(right.hash));
71            }
72            for index in right.leaves.clone() {
73                witnesses[index]
74                    .steps
75                    .push(ChainKeyBatchWitnessStepV1::LeftSibling(left.hash));
76            }
77            next.push(Node {
78                hash: node_hash(left.hash, right.hash),
79                leaves: left.leaves.start..right.leaves.end,
80            });
81        }
82        level = next;
83    }
84    Ok((level[0].hash, witnesses))
85}
86
87#[derive(Clone)]
88struct Node {
89    hash: [u8; 32],
90    leaves: Range<usize>,
91}
92
93// Callers admit proof-size budgets before reconstruction. This helper is also
94// the verification side of the constructor's existing node-byte contract.
95#[cfg(feature = "token-verification")]
96pub(crate) fn witness_root(leaf: [u8; 32], witness: &ChainKeyBatchWitnessV1) -> [u8; 32] {
97    witness.steps.iter().fold(leaf, |current, step| match step {
98        ChainKeyBatchWitnessStepV1::LeftSibling(hash) => node_hash(*hash, current),
99        ChainKeyBatchWitnessStepV1::RightSibling(hash) => node_hash(current, *hash),
100    })
101}
102
103fn node_hash(left: [u8; 32], right: [u8; 32]) -> [u8; 32] {
104    let mut hasher = Sha256::new();
105    hasher.update([1]);
106    hasher.update(left);
107    hasher.update(right);
108    hasher.finalize().into()
109}
ic_auth/chain_key_batch.rs

ic_auth/
chain_key_batch.rs
