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    if leaf_hashes.len() == 1 {
50        return Ok((
51            leaf_hashes[0],
52            vec![ChainKeyBatchWitnessV1 { steps: Vec::new() }],
53        ));
54    }
55    let depth = leaf_hashes.len().next_power_of_two().ilog2() as usize;
56    let mut witnesses: Vec<_> = (0..leaf_hashes.len())
57        .map(|_| ChainKeyBatchWitnessV1 {
58            steps: Vec::with_capacity(depth),
59        })
60        .collect();
61    let mut level: Vec<_> = leaf_hashes
62        .iter()
63        .enumerate()
64        .map(|(index, hash)| Node {
65            hash: *hash,
66            leaves: index..index + 1,
67        })
68        .collect();
69    let mut next = Vec::with_capacity(level.len().div_ceil(2));
70    while level.len() > 1 {
71        next.clear();
72        for pair in level.chunks(2) {
73            let left = &pair[0];
74            if pair.len() == 1 {
75                next.push(left.clone());
76                continue;
77            }
78            let right = &pair[1];
79            for index in left.leaves.clone() {
80                witnesses[index]
81                    .steps
82                    .push(ChainKeyBatchWitnessStepV1::RightSibling(right.hash));
83            }
84            for index in right.leaves.clone() {
85                witnesses[index]
86                    .steps
87                    .push(ChainKeyBatchWitnessStepV1::LeftSibling(left.hash));
88            }
89            next.push(Node {
90                hash: node_hash(left.hash, right.hash),
91                leaves: left.leaves.start..right.leaves.end,
92            });
93        }
94        std::mem::swap(&mut level, &mut next);
95    }
96    Ok((level[0].hash, witnesses))
97}
98
99#[derive(Clone)]
100struct Node {
101    hash: [u8; 32],
102    leaves: Range<usize>,
103}
104
105// Callers admit proof-size budgets before reconstruction. This helper is also
106// the verification side of the constructor's existing node-byte contract.
107#[cfg(feature = "chain-key-verification")]
108pub(crate) fn witness_root(leaf: [u8; 32], witness: &ChainKeyBatchWitnessV1) -> [u8; 32] {
109    witness.steps.iter().fold(leaf, |current, step| match step {
110        ChainKeyBatchWitnessStepV1::LeftSibling(hash) => node_hash(*hash, current),
111        ChainKeyBatchWitnessStepV1::RightSibling(hash) => node_hash(current, *hash),
112    })
113}
114
115fn node_hash(left: [u8; 32], right: [u8; 32]) -> [u8; 32] {
116    let mut hasher = Sha256::new();
117    hasher.update([1]);
118    hasher.update(left);
119    hasher.update(right);
120    hasher.finalize().into()
121}
ic_auth/chain_key_batch.rs

ic_auth/
chain_key_batch.rs
