r1cs/
merkle_trees.rs

1#[cfg(not(feature = "std"))]
2use alloc::vec::Vec;
3
4use crate::expression::{BinaryExpression, BooleanExpression, Expression};
5use crate::field::Field;
6use crate::gadget_builder::GadgetBuilder;
7use crate::gadget_traits::CompressionFunction;
8
9/// The path from a leaf to the root of a binary Merkle tree.
10#[derive(Debug)]
11pub struct MerklePath<F: Field> {
12    /// The sequence of "turns" when traversing up the tree. The value of each bit indicates the
13    /// index of the target node relative to its parent. For example, a zero bit indicates that the
14    /// target node is the left child, and its sibling is the right child.
15    prefix: BinaryExpression<F>,
16    /// The sequence of (hashes of) sibling nodes which are encountered along the path up the tree.
17    siblings: Vec<Expression<F>>,
18}
19
20impl<F: Field> MerklePath<F> {
21    pub fn new(prefix: BinaryExpression<F>, siblings: Vec<Expression<F>>) -> Self {
22        assert_eq!(prefix.len(), siblings.len());
23        MerklePath { prefix, siblings }
24    }
25}
26
27impl<F: Field> Clone for MerklePath<F> {
28    fn clone(&self) -> Self {
29        MerklePath {
30            prefix: self.prefix.clone(),
31            siblings: self.siblings.clone(),
32        }
33    }
34}
35
36impl<F: Field> GadgetBuilder<F> {
37    /// Update an intermediate hash value in a Merkle tree, given the sibling at the current layer.
38    fn merkle_tree_step<CF>(
39        &mut self,
40        node: &Expression<F>,
41        sibling: &Expression<F>,
42        prefix_bit: &BooleanExpression<F>,
43        compress: &CF,
44    ) -> Expression<F> where CF: CompressionFunction<F> {
45        let left = self.selection(prefix_bit, sibling, node);
46        let right = sibling + node - &left;
47        compress.compress(self, &left, &right)
48    }
49
50    /// Compute a Merkle root given a leaf value and its Merkle path.
51    pub fn merkle_tree_root<CF>(
52        &mut self,
53        leaf: &Expression<F>,
54        path: &MerklePath<F>,
55        compress: &CF,
56    ) -> Expression<F> where CF: CompressionFunction<F> {
57        let mut current = leaf.clone();
58        for (prefix_bit, sibling) in path.prefix.bits.iter().zip(path.siblings.iter()) {
59            current = self.merkle_tree_step(
60                &current, sibling, prefix_bit, compress);
61        }
62        current
63    }
64
65    pub fn assert_merkle_tree_membership<E1, E2, MP, CF>(
66        &mut self,
67        leaf: &Expression<F>,
68        purported_root: &Expression<F>,
69        path: &MerklePath<F>,
70        compress: &CF,
71    ) where CF: CompressionFunction<F> {
72        let computed_root = self.merkle_tree_root(leaf, path, compress);
73        self.assert_equal(purported_root, &computed_root)
74    }
75}
76
77#[cfg(test)]
78mod tests {
79    use num::BigUint;
80
81    use crate::expression::{BinaryExpression, BooleanExpression, Expression};
82    use crate::field::{Element, Field};
83    use crate::gadget_builder::GadgetBuilder;
84    use crate::gadget_traits::CompressionFunction;
85    use crate::merkle_trees::MerklePath;
86    use crate::test_util::{F257, F7};
87
88    #[test]
89    fn merkle_step() {
90        let mut builder = GadgetBuilder::<F257>::new();
91        let node = builder.wire();
92        let sibling = builder.wire();
93        let is_right = builder.boolean_wire();
94        let parent_hash = builder.merkle_tree_step(
95            &Expression::from(node), &Expression::from(sibling),
96            &BooleanExpression::from(is_right), &TestCompress);
97        let gadget = builder.build();
98
99        let mut values_3_4 = values!(node => 3u8.into(), sibling => 4u8.into());
100        values_3_4.set_boolean(is_right, false);
101        assert!(gadget.execute(&mut values_3_4));
102        assert_eq!(Element::from(10u8), parent_hash.evaluate(&values_3_4));
103
104        let mut values_4_3 = values!(node => 3u8.into(), sibling => 4u8.into());
105        values_4_3.set_boolean(is_right, true);
106        assert!(gadget.execute(&mut values_4_3));
107        assert_eq!(Element::from(11u8), parent_hash.evaluate(&values_4_3));
108    }
109
110    #[test]
111    fn merkle_root() {
112        let mut builder = GadgetBuilder::<F257>::new();
113        let prefix_wire = builder.binary_wire(3);
114        let (sibling_1, sibling_2, sibling_3) = (builder.wire(), builder.wire(), builder.wire());
115        let path = MerklePath::new(
116            BinaryExpression::from(&prefix_wire),
117            vec![sibling_1.into(), sibling_2.into(), sibling_3.into()]);
118        let root_hash = builder.merkle_tree_root(&Expression::one(), &path, &TestCompress);
119        let gadget = builder.build();
120
121        let mut values = values!(
122            sibling_1 => 3u8.into(),
123            sibling_2 => 3u8.into(),
124            sibling_3 => 9u8.into());
125        values.set_binary_unsigned(&prefix_wire, &BigUint::from(0b010u8));
126        assert!(gadget.execute(&mut values));
127        // The leaf is 1; the first parent hash is 2*1 + 3 = 5; the next parent hash is
128        // 2*3 + 5 = 11; the root is 2*11 + 9 = 31.
129        assert_eq!(Element::from(31u8), root_hash.evaluate(&values));
130    }
131
132    // Tests whether large path Sparse Merkle Trees are possible
133    #[test]
134    fn large_merkle_root() {
135        let mut builder = GadgetBuilder::<F7>::new();
136        let prefix_wire = builder.binary_wire(8);
137        let (sibling_1, sibling_2, sibling_3, sibling_4, sibling_5, sibling_6, sibling_7, sibling_8)
138            = (builder.wire(), builder.wire(), builder.wire(), builder.wire(), builder.wire(), builder.wire(), builder.wire(), builder.wire());
139        let path = MerklePath::new(
140            BinaryExpression::from(&prefix_wire),
141            vec![sibling_1.into(), sibling_2.into(), sibling_3.into(), sibling_4.into(), sibling_5.into(), sibling_6.into(), sibling_7.into(), sibling_8.into()]);
142        let root_hash = builder.merkle_tree_root(&Expression::one(), &path, &TestCompress);
143        let gadget = builder.build();
144
145        let mut values = values!(
146            sibling_1 => 1u8.into(),
147            sibling_2 => 1u8.into(),
148            sibling_3 => 1u8.into(),
149            sibling_4 => 1u8.into(),
150            sibling_5 => 1u8.into(),
151            sibling_6 => 1u8.into(),
152            sibling_7 => 1u8.into(),
153            sibling_8 => 1u8.into()
154            );
155        values.set_binary_unsigned(&prefix_wire, &BigUint::from(0b00000000u8));
156        assert!(gadget.execute(&mut values));
157        // The leaf is 1; the first parent hash is 2*1 + 1 = 3; 2*3 + 1 == 0; 2*0 + 1 = 1; 2*1 + 1 = 3; 2*3 + 1 == 0; 2*0 + 1 = 1; 2*1 + 1 = 3;
158        // the root is 2*3 + 1 == 0.
159        assert_eq!(
160            Element::from(0u8),
161            root_hash.evaluate(&values));
162    }
163
164    // A dummy compression function which returns 2x + y.
165    struct TestCompress;
166
167    impl<F: Field> CompressionFunction<F> for TestCompress {
168        fn compress(&self, _builder: &mut GadgetBuilder<F>, x: &Expression<F>, y: &Expression<F>)
169                    -> Expression<F> {
170            x * 2 + y
171        }
172    }
173}
r1cs/merkle_trees.rs

r1cs/
merkle_trees.rs
