privacy_core/commitment_tree/
poseidon.rs

1//! Poseidon-based Merkle hashing on the BN254 scalar field (`Fr`).
2//!
3//! Lifted verbatim from `orchard-bn254`'s `poseidon_merkle_bn254` (the merkle-tree parts
4//! only), re-sourced to the **standalone** crates `halo2_poseidon` (Poseidon primitives)
5//! and `halo2curves` (BN254 `Fr`) so it carries **no `halo2_proofs` / `halo2_gadgets`
6//! dependency**. The Poseidon spec/constants are byte-identical to the prover + on-chain
7//! `PoseidonT3` (verified against the live commitment-tree root).
8
9use super::poseidon_primitives::{generate_constants, ConstantLength, Hash, Mds, Spec};
10use ff::Field;
11use halo2curves::bn256::Fr;
12
13/// Orchard-compatible depth for the incremental note commitment tree.
14pub const MERKLE_DEPTH_EVM: usize = 32;
15
16/// Poseidon-128, width 3, rate 2, x^5 S-box; Grain-generated constants for BN254 `Fr`.
17#[derive(Clone, Copy, Debug)]
18pub struct Bn254PoseidonMerkleSpec;
19
20impl Spec<Fr, 3, 2> for Bn254PoseidonMerkleSpec {
21    fn full_rounds() -> usize {
22        8
23    }
24    fn partial_rounds() -> usize {
25        56
26    }
27    fn sbox(val: Fr) -> Fr {
28        val.pow_vartime([5])
29    }
30    fn secure_mds() -> usize {
31        0
32    }
33    fn constants() -> (Vec<[Fr; 3]>, Mds<Fr, 3>, Mds<Fr, 3>) {
34        generate_constants::<Fr, Self, 3, 2>()
35    }
36}
37
38/// One Merkle layer: `H(level || left || right)` with domain separation on `level`.
39#[inline]
40pub fn merkle_compress(level: u8, left: Fr, right: Fr) -> Fr {
41    Hash::<Fr, Bn254PoseidonMerkleSpec, ConstantLength<3>, 3, 2>::init().hash([
42        Fr::from(level as u64),
43        left,
44        right,
45    ])
46}
47
48/// Full Merkle root (depth [`MERKLE_DEPTH_EVM`]) over `Fr` leaves from a sibling path.
49pub fn merkle_root(position: u32, leaf: Fr, siblings: &[Fr; MERKLE_DEPTH_EVM]) -> Fr {
50    let mut node = leaf;
51    for (level, sibling) in siblings.iter().enumerate() {
52        let l = level as u8;
53        if (position >> level) & 1 == 0 {
54            node = merkle_compress(l, node, *sibling);
55        } else {
56            node = merkle_compress(l, *sibling, node);
57        }
58    }
59    node
60}
61
62/// Append-only incremental Merkle tree of fixed depth [`MERKLE_DEPTH_EVM`] (32) over BN254
63/// scalar leaves. Empty leaves default to [`Fr::ZERO`].
64#[derive(Debug)]
65pub struct Bn254IncrementalMerkleTree {
66    leaves: Vec<Fr>,
67    /// `empty[l]` is the root of a depth-`l` all-zero subtree (`empty[0]` = `Fr::ZERO`).
68    empty: [Fr; MERKLE_DEPTH_EVM + 1],
69}
70
71impl Bn254IncrementalMerkleTree {
72    pub fn new() -> Self {
73        let mut empty = [Fr::ZERO; MERKLE_DEPTH_EVM + 1];
74        for i in 1..=MERKLE_DEPTH_EVM {
75            empty[i] = merkle_compress((i - 1) as u8, empty[i - 1], empty[i - 1]);
76        }
77        Self { leaves: Vec::new(), empty }
78    }
79
80    pub fn append(&mut self, leaf: Fr) {
81        self.leaves.push(leaf);
82    }
83
84    pub fn len(&self) -> usize {
85        self.leaves.len()
86    }
87
88    pub fn is_empty(&self) -> bool {
89        self.leaves.is_empty()
90    }
91
92    pub fn root(&self) -> Fr {
93        self.subtree_hash(MERKLE_DEPTH_EVM, 0)
94    }
95
96    /// Authentication path (siblings) for the leaf at `pos`. Panics if `pos >= len()`.
97    pub fn witness(&self, pos: u32) -> [Fr; MERKLE_DEPTH_EVM] {
98        assert!((pos as usize) < self.leaves.len(), "position out of tree");
99        let mut siblings = [Fr::ZERO; MERKLE_DEPTH_EVM];
100        for level in 0..MERKLE_DEPTH_EVM {
101            let sibling_node_idx = ((pos >> level) ^ 1) as usize;
102            siblings[level] = self.subtree_hash(level, sibling_node_idx);
103        }
104        siblings
105    }
106
107    fn subtree_hash(&self, level: usize, idx: usize) -> Fr {
108        let start = idx << level; // idx * 2^level
109        if start >= self.leaves.len() {
110            return self.empty[level];
111        }
112        if level == 0 {
113            return self.leaves[start];
114        }
115        let left = self.subtree_hash(level - 1, idx * 2);
116        let right = self.subtree_hash(level - 1, idx * 2 + 1);
117        merkle_compress((level - 1) as u8, left, right)
118    }
119}
120
121impl Default for Bn254IncrementalMerkleTree {
122    fn default() -> Self {
123        Self::new()
124    }
125}
privacy_core/commitment_tree/poseidon.rs

privacy_core/commitment_tree/
poseidon.rs
