privacy_core/commitment_tree/
mod.rs

1//! BN254 Poseidon note-commitment tree (halo2-free).
2//!
3//! Extracted from `orchard-commitment-tree`, with the Poseidon hashing re-sourced to
4//! `privacy-core::commitment_tree::poseidon` (via `halo2_poseidon` + `halo2curves`).
5//! The Pallas-typed legacy stubs (`to_orchard_path`, `root`) were dropped — clients use
6//! the `siblings` (LE hex) directly.
7
8mod poseidon_primitives;
9pub mod frozen;
10pub mod poseidon;
11
12use ff::PrimeField;
13use halo2curves::bn256::Fr;
14use poseidon::Bn254IncrementalMerkleTree;
15use serde::{Deserialize, Serialize};
16
17/// A Merkle authentication path for a BN254 note commitment.
18///
19/// `siblings` are 32-byte LE hex strings (0x-prefixed) — pass directly to the prover's
20/// `parse_fr_le()` witness builder.
21#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Eq)]
22pub struct OrchardMerklePath {
23    /// 0-based leaf index in the commitment tree.
24    pub position: u32,
25    /// 32 sibling hashes from leaf to root (each a 0x-prefixed LE 32-byte hex string).
26    pub siblings: Vec<String>,
27}
28
29/// BN254 Poseidon note commitment tree.
30///
31/// Leaf values are BN254 `Fr` elements encoded big-endian (as emitted by the EVM
32/// `NoteAdded` event); internally the tree works in little-endian field representation.
33pub struct OrchardCommitmentTree {
34    inner: Bn254IncrementalMerkleTree,
35    size: u64,
36    latest_checkpoint: Option<u64>,
37}
38
39impl OrchardCommitmentTree {
40    pub fn new() -> Self {
41        Self { inner: Bn254IncrementalMerkleTree::new(), size: 0, latest_checkpoint: None }
42    }
43
44    /// Append a big-endian `cmx` (as from an EVM log) as the next leaf. Always `Some(pos)`.
45    pub fn append(&mut self, cmx_be: [u8; 32]) -> Option<u64> {
46        self.inner.append(be_bytes_to_fr(cmx_be));
47        let pos = self.size;
48        self.size += 1;
49        Some(pos)
50    }
51
52    /// Register a checkpoint label (Ethereum block number). The tree is append-only.
53    pub fn checkpoint(&mut self, checkpoint_id: u64) -> bool {
54        self.latest_checkpoint = Some(checkpoint_id);
55        true
56    }
57
58    /// Merkle root (LE 32 bytes). `None` when the tree is empty.
59    pub fn latest_root(&self) -> Option<[u8; 32]> {
60        if self.size == 0 {
61            return None;
62        }
63        Some(fr_to_le_bytes(self.inner.root()))
64    }
65
66    /// Authentication path for the leaf at `position` (current tree state). `None` if OOB.
67    pub fn merkle_path(&self, position: u64, _checkpoint_id: u64) -> Option<OrchardMerklePath> {
68        if position >= self.size {
69            return None;
70        }
71        let siblings = self
72            .inner
73            .witness(position as u32)
74            .iter()
75            .map(|fr| format!("0x{}", hex::encode(fr_to_le_bytes(*fr))))
76            .collect();
77        Some(OrchardMerklePath { position: position as u32, siblings })
78    }
79
80    pub fn size(&self) -> u64 {
81        self.size
82    }
83
84    pub fn latest_checkpoint_id(&self) -> Option<u64> {
85        self.latest_checkpoint
86    }
87}
88
89impl Default for OrchardCommitmentTree {
90    fn default() -> Self {
91        Self::new()
92    }
93}
94
95// ─── Field element conversion helpers ────────────────────────────────────────
96
97/// Big-endian 32-byte array (EVM representation) → BN254 `Fr` (via `from_raw`).
98fn be_bytes_to_fr(be: [u8; 32]) -> Fr {
99    let mut le = be;
100    le.reverse();
101    let mut limbs = [0u64; 4];
102    for (i, chunk) in le.chunks(8).enumerate() {
103        limbs[i] = u64::from_le_bytes(chunk.try_into().unwrap());
104    }
105    Fr::from_raw(limbs)
106}
107
108/// BN254 `Fr` → little-endian 32-byte array.
109fn fr_to_le_bytes(fr: Fr) -> [u8; 32] {
110    fr.to_repr().into()
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    fn be(h: &str) -> [u8; 32] {
118        hex::decode(h).unwrap().try_into().unwrap()
119    }
120
121    /// Byte-identity guard: the halo2-free Poseidon tree must reproduce the live on-chain
122    /// root for the real Sepolia leaves. If this fails, the Poseidon constants drifted.
123    #[test]
124    fn root_matches_onchain() {
125        let leaves = [
126            "16c1a78d9bf2a808a1f71e93b9caff5c86a28c79ea5cc5f1bebc52cbd5a936ff",
127            "2c421b91ff2f9ef6a4f024e56c29491eb2d26a6ae65ec34a420d6a70432a1fc0",
128            "1369c5ef5db9200ba955725e65855b1a4f77321a01a336a37e5807c6190e0fa0",
129            "11fe8d42f8ae822ccf7261f40e87c5695dff7853d942d308a8e4b7e5155cd781",
130        ];
131        let mut tree = OrchardCommitmentTree::new();
132        for l in leaves {
133            tree.append(be(l));
134        }
135        // Live Sepolia treeSize=4 root: indexer /root (LE) = 70c14793…; on-chain
136        // activeRoot()/indexer_meta (BE) = 22e4ff3d… latest_root() returns LE.
137        let expected_le = "70c14793de62ea1c6b3f134efc7900bdd5d81c71ee041e5b6481c17d3dffe422";
138        assert_eq!(hex::encode(tree.latest_root().unwrap()), expected_le);
139    }
140}
privacy_core/commitment_tree/mod.rs

privacy_core/commitment_tree/
mod.rs
