sapling_crypto/
tree.rs

1use bitvec::{order::Lsb0, view::AsBits};
2use group::{ff::PrimeField, Curve};
3use incrementalmerkletree::{Hashable, Level};
4use lazy_static::lazy_static;
5use subtle::CtOption;
6
7use alloc::vec::Vec;
8use core::fmt;
9
10use super::{
11    note::ExtractedNoteCommitment,
12    pedersen_hash::{pedersen_hash, Personalization},
13};
14
15pub const NOTE_COMMITMENT_TREE_DEPTH: u8 = 32;
16pub type CommitmentTree =
17    incrementalmerkletree::frontier::CommitmentTree<Node, NOTE_COMMITMENT_TREE_DEPTH>;
18pub type IncrementalWitness =
19    incrementalmerkletree::witness::IncrementalWitness<Node, NOTE_COMMITMENT_TREE_DEPTH>;
20pub type MerklePath = incrementalmerkletree::MerklePath<Node, NOTE_COMMITMENT_TREE_DEPTH>;
21
22lazy_static! {
23    static ref UNCOMMITTED_SAPLING: bls12_381::Scalar = bls12_381::Scalar::one();
24    static ref EMPTY_ROOTS: Vec<Node> = empty_roots();
25}
26
27fn empty_roots() -> Vec<Node> {
28    let mut v = vec![Node::empty_leaf()];
29    for d in 0..NOTE_COMMITMENT_TREE_DEPTH {
30        let next = Node::combine(d.into(), &v[usize::from(d)], &v[usize::from(d)]);
31        v.push(next);
32    }
33    v
34}
35
36/// Compute a parent node in the Sapling commitment tree given its two children.
37pub fn merkle_hash(depth: usize, lhs: &[u8; 32], rhs: &[u8; 32]) -> [u8; 32] {
38    merkle_hash_field(depth, lhs, rhs).to_repr()
39}
40
41fn merkle_hash_field(depth: usize, lhs: &[u8; 32], rhs: &[u8; 32]) -> jubjub::Base {
42    let lhs = {
43        let mut tmp = [false; 256];
44        for (a, b) in tmp.iter_mut().zip(lhs.as_bits::<Lsb0>()) {
45            *a = *b;
46        }
47        tmp
48    };
49
50    let rhs = {
51        let mut tmp = [false; 256];
52        for (a, b) in tmp.iter_mut().zip(rhs.as_bits::<Lsb0>()) {
53            *a = *b;
54        }
55        tmp
56    };
57
58    jubjub::ExtendedPoint::from(pedersen_hash(
59        Personalization::MerkleTree(depth),
60        lhs.iter()
61            .copied()
62            .take(bls12_381::Scalar::NUM_BITS as usize)
63            .chain(
64                rhs.iter()
65                    .copied()
66                    .take(bls12_381::Scalar::NUM_BITS as usize),
67            ),
68    ))
69    .to_affine()
70    .get_u()
71}
72
73/// The root of a Sapling commitment tree.
74#[derive(Eq, PartialEq, Clone, Copy, Debug)]
75pub struct Anchor(jubjub::Base);
76
77impl From<jubjub::Base> for Anchor {
78    fn from(anchor_field: jubjub::Base) -> Anchor {
79        Anchor(anchor_field)
80    }
81}
82
83impl From<Node> for Anchor {
84    fn from(anchor: Node) -> Anchor {
85        Anchor(anchor.0)
86    }
87}
88
89impl Anchor {
90    /// The anchor of the empty Sapling note commitment tree.
91    ///
92    /// This anchor does not correspond to any valid anchor for a spend, so it
93    /// may only be used for coinbase bundles or in circumstances where Sapling
94    /// functionality is not active.
95    pub fn empty_tree() -> Anchor {
96        Anchor(Node::empty_root(NOTE_COMMITMENT_TREE_DEPTH.into()).0)
97    }
98
99    pub(crate) fn inner(&self) -> jubjub::Base {
100        self.0
101    }
102
103    /// Parses a Sapling anchor from a byte encoding.
104    pub fn from_bytes(bytes: [u8; 32]) -> CtOption<Anchor> {
105        jubjub::Base::from_repr(bytes).map(Self)
106    }
107
108    /// Returns the byte encoding of this anchor.
109    pub fn to_bytes(self) -> [u8; 32] {
110        self.0.to_repr()
111    }
112}
113
114/// A node within the Sapling commitment tree.
115#[derive(Clone, Copy, PartialEq, Eq)]
116pub struct Node(jubjub::Base);
117
118impl fmt::Debug for Node {
119    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
120        f.debug_struct("Node")
121            .field("repr", &hex::encode(self.0.to_bytes()))
122            .finish()
123    }
124}
125
126impl Node {
127    /// Creates a tree leaf from the given Sapling note commitment.
128    pub fn from_cmu(value: &ExtractedNoteCommitment) -> Self {
129        Node(value.inner())
130    }
131
132    /// Constructs a new note commitment tree node from a [`bls12_381::Scalar`]
133    pub fn from_scalar(cmu: bls12_381::Scalar) -> Self {
134        Self(cmu)
135    }
136
137    /// Parses a tree leaf from the bytes of a Sapling note commitment.
138    ///
139    /// Returns `None` if the provided bytes represent a non-canonical encoding.
140    pub fn from_bytes(bytes: [u8; 32]) -> CtOption<Self> {
141        jubjub::Base::from_repr(bytes).map(Self)
142    }
143
144    /// Returns the canonical byte representation of this node.
145    pub fn to_bytes(&self) -> [u8; 32] {
146        self.0.to_repr()
147    }
148
149    /// Returns the wrapped value
150    #[cfg(feature = "circuit")]
151    pub(crate) fn inner(&self) -> &jubjub::Base {
152        &self.0
153    }
154}
155
156impl Hashable for Node {
157    fn empty_leaf() -> Self {
158        Node(*UNCOMMITTED_SAPLING)
159    }
160
161    fn combine(level: Level, lhs: &Self, rhs: &Self) -> Self {
162        Node(merkle_hash_field(
163            level.into(),
164            &lhs.0.to_bytes(),
165            &rhs.0.to_bytes(),
166        ))
167    }
168
169    fn empty_root(level: Level) -> Self {
170        EMPTY_ROOTS[<usize>::from(level)]
171    }
172}
173
174impl From<Node> for bls12_381::Scalar {
175    fn from(node: Node) -> Self {
176        node.0
177    }
178}
179
180#[cfg(any(test, feature = "test-dependencies"))]
181pub(super) mod testing {
182    use ff::Field;
183    use proptest::prelude::*;
184    use rand::distributions::{Distribution, Standard};
185
186    use super::Node;
187    use crate::note::testing::arb_cmu;
188
189    prop_compose! {
190        pub fn arb_node()(cmu in arb_cmu()) -> Node {
191            Node::from_cmu(&cmu)
192        }
193    }
194
195    impl Node {
196        /// Return a random fake `MerkleHashOrchard`.
197        pub fn random(rng: &mut impl RngCore) -> Self {
198            Standard.sample(rng)
199        }
200    }
201
202    impl Distribution<Node> for Standard {
203        fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Node {
204            Node::from_scalar(bls12_381::Scalar::random(rng))
205        }
206    }
207}
sapling_crypto/tree.rs

sapling_crypto/
tree.rs
