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

privacy_core/commitment_tree/
mod.rs
