1use algebra::Field;
  2use r1cs_core::{ConstraintSystem, SynthesisError};
  3use r1cs_std::prelude::*;
  4use r1cs_std::boolean::AllocatedBit;
  5
  6use crate::{mht::HashMembershipProof, CommitmentScheme, FixedLengthCRH};
  7
  8use crate::{commitment::CommitmentGadget, crh::FixedLengthCRHGadget};
  9
 10use crate::ledger::{CommPath, Digest, LedgerDigest, LedgerWitness};
 11
 12use std::{borrow::Borrow, marker::PhantomData};
 13
 14pub trait LCWGadget<C: CommitmentScheme, D: LedgerDigest, CW: LedgerWitness<D>, ConstraintF: Field> {
 15    type ParametersGadget: AllocGadget<D::Parameters, ConstraintF>;
 16    type CommitmentGadget: AllocGadget<C::Output, ConstraintF>;
 17    type DigestGadget: AllocGadget<D, ConstraintF>;
 18    type WitnessGadget: AllocGadget<CW, ConstraintF>;
 19
 20    fn check_witness_gadget<CS: ConstraintSystem<ConstraintF>>(
 21        cs: CS,
 22        parameters: &Self::ParametersGadget,
 23        ledger_state_digest: &Self::DigestGadget,
 24        commitment: &Self::CommitmentGadget,
 25        witness: &Self::WitnessGadget,
 26    ) -> Result<(), SynthesisError> {
 27        Self::conditionally_check_witness_gadget(
 28            cs,
 29            parameters,
 30            ledger_state_digest,
 31            commitment,
 32            witness,
 33            &Boolean::Constant(true),
 34        )
 35    }
 36
 37    fn conditionally_check_witness_gadget<CS: ConstraintSystem<ConstraintF>>(
 38        cs: CS,
 39        parameters: &Self::ParametersGadget,
 40        ledger_state_digest: &Self::DigestGadget,
 41        commitment: &Self::CommitmentGadget,
 42        witness: &Self::WitnessGadget,
 43        should_enforce: &Boolean,
 44    ) -> Result<(), SynthesisError>;
 45}
 46
 47pub struct IdealLedgerGadget<C, H, HGadget, CGadget> {
 48    #[doc(hidden)]
 49    _comm_scheme: PhantomData<C>,
 50    #[doc(hidden)]
 51    _hash:        PhantomData<H>,
 52    #[doc(hidden)]
 53    _comm_gadget: PhantomData<CGadget>,
 54    #[doc(hidden)]
 55    _hash_gadget: PhantomData<HGadget>,
 56}
 57
 58pub struct CommitmentWitness<
 59    H: FixedLengthCRH,
 60    C: CommitmentScheme,
 61    HGadget: FixedLengthCRHGadget<H, ConstraintF>,
 62    ConstraintF: Field,
 63> {
 64    path:    Vec<(HGadget::OutputGadget, HGadget::OutputGadget)>,
 65    _crh:    PhantomData<H>,
 66    _comm:   PhantomData<C>,
 67    _engine: PhantomData<ConstraintF>,
 68}
 69
 70pub struct DigestGadget<H: FixedLengthCRH, HGadget: FixedLengthCRHGadget<H, ConstraintF>, ConstraintF: Field> {
 71    digest:  HGadget::OutputGadget,
 72    #[doc(hidden)]
 73    _crh:    PhantomData<H>,
 74    #[doc(hidden)]
 75    _engine: PhantomData<ConstraintF>,
 76}
 77
 78impl<C, ConstraintF, H, CGadget, HGadget> LCWGadget<C, Digest<H>, CommPath<H, C::Output>, ConstraintF>
 79    for IdealLedgerGadget<C, H, HGadget, CGadget>
 80where
 81    C: CommitmentScheme,
 82    C::Output: Eq,
 83    ConstraintF: Field,
 84    H: FixedLengthCRH,
 85    CGadget: CommitmentGadget<C, ConstraintF>,
 86    HGadget: FixedLengthCRHGadget<H, ConstraintF>,
 87{
 88    type ParametersGadget = <HGadget as FixedLengthCRHGadget<H, ConstraintF>>::ParametersGadget;
 89    type DigestGadget = DigestGadget<H, HGadget, ConstraintF>;
 90
 91    type CommitmentGadget = <CGadget as CommitmentGadget<C, ConstraintF>>::OutputGadget;
 92    type WitnessGadget = CommitmentWitness<H, C, HGadget, ConstraintF>;
 93
 94    /// Given a `leaf` and `path`, check that the `path` is a valid
 95    /// authentication path for the `leaf` in a Merkle tree.
 96    /// Note: It is assumed that the root is contained in the `path`.
 97    fn conditionally_check_witness_gadget<CS: ConstraintSystem<ConstraintF>>(
 98        mut cs: CS,
 99        parameters: &Self::ParametersGadget,
100        root_hash: &Self::DigestGadget,
101        commitment: &Self::CommitmentGadget,
102        witness: &Self::WitnessGadget,
103        should_enforce: &Boolean,
104    ) -> Result<(), SynthesisError> {
105        assert_eq!(
106            witness.path.len(),
107            (HashMembershipProof::<H, C::Output>::MAX_HEIGHT - 1) as usize
108        );
109        // Check that the hash of the given leaf matches the leaf hash in the membership
110        // proof.
111        let commitment_bits = commitment.to_bytes(&mut cs.ns(|| "commitment_to_bytes"))?;
112        let commitment_hash = HGadget::check_evaluation_gadget(
113            cs.ns(|| "check_evaluation_gadget"),
114            parameters,
115            &commitment_bits,
116        )?;
117
118        // Check if leaf is one of the bottom-most siblings.
119        let leaf_is_left = AllocatedBit::alloc(&mut cs.ns(|| "leaf_is_left"), || {
120            Ok(commitment_hash == witness.path[0].0)
121        })?
122        .into();
123        <HGadget::OutputGadget>::conditional_enforce_equal_or(
124            &mut cs.ns(|| "check_leaf_is_left"),
125            &leaf_is_left,
126            &commitment_hash,
127            &witness.path[0].0,
128            &witness.path[0].1,
129            should_enforce,
130        )?;
131
132        // Check levels between leaf level and root.
133        let mut previous_hash = commitment_hash;
134        for (i, &(ref left_hash, ref right_hash)) in witness.path.iter().enumerate() {
135            // Check if the previous_hash matches the correct current hash.
136            let previous_is_left =
137                AllocatedBit::alloc(&mut cs.ns(|| format!("previous_is_left_{}", i)), || {
138                    Ok(&previous_hash == left_hash)
139                })?
140                .into();
141
142            <HGadget::OutputGadget>::conditional_enforce_equal_or(
143                &mut cs.ns(|| format!("check_equals_which_{}", i)),
144                &previous_is_left,
145                &previous_hash,
146                left_hash,
147                right_hash,
148                should_enforce,
149            )?;
150
151            previous_hash = hash_inner_node_gadget::<H, HGadget, ConstraintF, _>(
152                &mut cs.ns(|| format!("hash_inner_node_{}", i)),
153                parameters,
154                left_hash,
155                right_hash,
156            )?;
157        }
158
159        root_hash.digest.conditional_enforce_equal(
160            &mut cs.ns(|| "root_is_last"),
161            &previous_hash,
162            should_enforce,
163        )
164    }
165}
166
167pub(crate) fn hash_inner_node_gadget<H, HG, ConstraintF, CS>(
168    mut cs: CS,
169    parameters: &HG::ParametersGadget,
170    left_child: &HG::OutputGadget,
171    right_child: &HG::OutputGadget,
172) -> Result<HG::OutputGadget, SynthesisError>
173where
174    ConstraintF: Field,
175    CS: ConstraintSystem<ConstraintF>,
176    H: FixedLengthCRH,
177    HG: FixedLengthCRHGadget<H, ConstraintF>,
178{
179    let left_bytes = left_child.to_bytes(&mut cs.ns(|| "left_to_bytes"))?;
180    let right_bytes = right_child.to_bytes(&mut cs.ns(|| "right_to_bytes"))?;
181    let mut bytes = left_bytes;
182    bytes.extend_from_slice(&right_bytes);
183
184    HG::check_evaluation_gadget(cs, parameters, &bytes)
185}
186
187impl<H, HGadget, ConstraintF> AllocGadget<Digest<H>, ConstraintF> for DigestGadget<H, HGadget, ConstraintF>
188where
189    H: FixedLengthCRH,
190    HGadget: FixedLengthCRHGadget<H, ConstraintF>,
191    ConstraintF: Field,
192{
193    fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
194        mut cs: CS,
195        value_gen: F,
196    ) -> Result<Self, SynthesisError>
197    where
198        F: FnOnce() -> Result<T, SynthesisError>,
199        T: Borrow<Digest<H>>,
200    {
201        let digest = HGadget::OutputGadget::alloc(&mut cs.ns(|| "digest"), || {
202            Ok(value_gen()?.borrow().0.clone())
203        })?;
204
205        Ok(DigestGadget {
206            digest,
207            _crh: PhantomData,
208            _engine: PhantomData,
209        })
210    }
211
212    fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
213        mut cs: CS,
214        value_gen: F,
215    ) -> Result<Self, SynthesisError>
216    where
217        F: FnOnce() -> Result<T, SynthesisError>,
218        T: Borrow<Digest<H>>,
219    {
220        let digest = HGadget::OutputGadget::alloc_input(&mut cs.ns(|| "input_digest"), || {
221            Ok(value_gen()?.borrow().0.clone())
222        })?;
223        Ok(DigestGadget {
224            digest,
225            _crh: PhantomData,
226            _engine: PhantomData,
227        })
228    }
229}
230
231impl<H, C, HGadget, ConstraintF> AllocGadget<CommPath<H, C::Output>, ConstraintF>
232    for CommitmentWitness<H, C, HGadget, ConstraintF>
233where
234    H: FixedLengthCRH,
235    C: CommitmentScheme,
236    HGadget: FixedLengthCRHGadget<H, ConstraintF>,
237    ConstraintF: Field,
238{
239    fn alloc<F, T, CS: ConstraintSystem<ConstraintF>>(
240        mut cs: CS,
241        value_gen: F,
242    ) -> Result<Self, SynthesisError>
243    where
244        F: FnOnce() -> Result<T, SynthesisError>,
245        T: Borrow<CommPath<H, C::Output>>,
246    {
247        let mut path = Vec::new();
248        for (i, &(ref l, ref r)) in value_gen()?.borrow().0.path.iter().enumerate() {
249            let l_hash =
250                HGadget::OutputGadget::alloc(&mut cs.ns(|| format!("l_child_{}", i)), || {
251                    Ok(l.clone())
252                })?;
253            let r_hash =
254                HGadget::OutputGadget::alloc(&mut cs.ns(|| format!("r_child_{}", i)), || {
255                    Ok(r.clone())
256                })?;
257            path.push((l_hash, r_hash));
258        }
259        Ok(CommitmentWitness {
260            path,
261            _crh: PhantomData,
262            _comm: PhantomData,
263            _engine: PhantomData,
264        })
265    }
266
267    fn alloc_input<F, T, CS: ConstraintSystem<ConstraintF>>(
268        mut cs: CS,
269        value_gen: F,
270    ) -> Result<Self, SynthesisError>
271    where
272        F: FnOnce() -> Result<T, SynthesisError>,
273        T: Borrow<CommPath<H, C::Output>>,
274    {
275        let mut path = Vec::new();
276        for (i, &(ref l, ref r)) in value_gen()?.borrow().0.path.iter().enumerate() {
277            let l_hash = HGadget::OutputGadget::alloc_input(
278                &mut cs.ns(|| format!("l_child_{}", i)),
279                || Ok(l.clone()),
280            )?;
281            let r_hash = HGadget::OutputGadget::alloc_input(
282                &mut cs.ns(|| format!("r_child_{}", i)),
283                || Ok(r.clone()),
284            )?;
285            path.push((l_hash, r_hash));
286        }
287
288        Ok(CommitmentWitness {
289            path,
290            _crh: PhantomData,
291            _comm: PhantomData,
292            _engine: PhantomData,
293        })
294    }
295}
296
297#[cfg(test)]
298mod test {
299    use std::rc::Rc;
300
301    use crate::crypto_primitives::{
302        commitment::{
303            pedersen::{PedersenCommitment, PedersenRandomness},
304            CommitmentScheme,
305        },
306        crh::{
307            pedersen::{PedersenCRH, PedersenWindow},
308            FixedLengthCRH,
309        },
310        mht::*,
311    };
312    use algebra::{
313        curves::jubjub::JubJubAffine as JubJub,
314        fields::jubjub::fr::Fr,
315        fields::jubjub::fq::Fq,
316        Group
317    };
318    use rand::SeedableRng;
319    use algebra::UniformRand;
320    use rand_xorshift::XorShiftRng;
321    use r1cs_core::ConstraintSystem;
322
323    use super::*;
324    use crate::gadgets::{
325        commitment::pedersen::PedersenCommitmentGadget,
326        crh::{pedersen::PedersenCRHGadget, FixedLengthCRHGadget},
327    };
328    use r1cs_std::{
329        groups::curves::twisted_edwards::jubjub::JubJubGadget,
330        test_constraint_system::TestConstraintSystem,
331    };
332
333    use crate::ledger::{CommPath, Digest};
334
335    #[derive(Clone)]
336    pub(super) struct Window4x256;
337    impl PedersenWindow for Window4x256 {
338        const WINDOW_SIZE: usize = 4;
339        const NUM_WINDOWS: usize = 256;
340    }
341
342    type H = PedersenCRH<JubJub, Window4x256>;
343    type HG = PedersenCRHGadget<JubJub, Fq, JubJubGadget>;
344    type C = PedersenCommitment<JubJub, Window4x256>;
345    type CG = PedersenCommitmentGadget<JubJub, Fq, JubJubGadget>;
346    type JubJubMHT = MerkleHashTree<H, <C as CommitmentScheme>::Output>;
347    type LG = IdealLedgerGadget<C, H, HG, CG>;
348    type DG = DigestGadget<H, HG, Fq>;
349    type LCWG = CommitmentWitness<H, C, HG, Fq>;
350
351    fn generate_merkle_tree(leaves: &[<C as CommitmentScheme>::Output]) -> () {
352        let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
353
354        let crh_parameters = Rc::new(H::setup(&mut rng).unwrap());
355        let tree = JubJubMHT::new(crh_parameters.clone(), &leaves).unwrap();
356        let root = tree.root();
357        let mut satisfied = true;
358        for (i, leaf) in leaves.iter().enumerate() {
359            let mut cs = TestConstraintSystem::<Fq>::new();
360            let proof = tree.generate_proof(i, &leaf).unwrap();
361            assert!(proof.verify(&crh_parameters, &root, &leaf).unwrap());
362
363            let digest = DG::alloc(&mut cs.ns(|| format!("new_digest_{}", i)), || {
364                Ok(Digest(root))
365            })
366            .unwrap();
367            let constraints_from_digest = cs.num_constraints();
368            println!("constraints from digest: {}", constraints_from_digest);
369
370            let crh_parameters =
371                <HG as FixedLengthCRHGadget<H, Fq>>::ParametersGadget::alloc(
372                    &mut cs.ns(|| format!("new_parameters_{}", i)),
373                    || Ok(crh_parameters.clone()),
374                )
375                .unwrap();
376            let constraints_from_parameters = cs.num_constraints() - constraints_from_digest;
377            println!(
378                "constraints from parameters: {}",
379                constraints_from_parameters
380            );
381
382            let comm = <CG as CommitmentGadget<C, Fq>>::OutputGadget::alloc(
383                &mut cs.ns(|| format!("new_comm_{}", i)),
384                || {
385                    let leaf: JubJub = *leaf;
386                    Ok(leaf)
387                },
388            )
389            .unwrap();
390            let constraints_from_comm =
391                cs.num_constraints() - constraints_from_parameters - constraints_from_digest;
392            println!("constraints from comm: {}", constraints_from_comm);
393
394            let cw = LCWG::alloc(&mut cs.ns(|| format!("new_witness_{}", i)), || {
395                Ok(CommPath(proof))
396            })
397            .unwrap();
398            let constraints_from_path = cs.num_constraints()
399                - constraints_from_parameters
400                - constraints_from_digest
401                - constraints_from_comm;
402            println!("constraints from path: {}", constraints_from_path);
403            LG::check_witness_gadget(
404                &mut cs.ns(|| format!("new_witness_check_{}", i)),
405                &crh_parameters,
406                &digest,
407                &comm,
408                &cw,
409            )
410            .unwrap();
411            if !cs.is_satisfied() {
412                satisfied = false;
413                println!(
414                    "Unsatisfied constraint: {}",
415                    cs.which_is_unsatisfied().unwrap()
416                );
417            }
418            let setup_constraints = constraints_from_comm
419                + constraints_from_digest
420                + constraints_from_parameters
421                + constraints_from_path;
422            println!(
423                "number of constraints: {}",
424                cs.num_constraints() - setup_constraints
425            );
426        }
427        assert!(satisfied);
428    }
429
430    #[test]
431    fn mht_gadget_test() {
432        let mut leaves = Vec::new();
433        let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
434        let comm_parameters = C::setup(&mut rng).unwrap();
435        for i in 0..4u8 {
436            let r = PedersenRandomness(Fr::rand(&mut rng));
437            let input = [i, i, i, i, i, i, i, i];
438            leaves.push(C::commit(&comm_parameters, &input, &r).unwrap());
439        }
440        generate_merkle_tree(&leaves);
441        // let mut leaves = Vec::new();
442        // for i in 0..100u8 {
443        //     leaves.push([i, i, i, i, i, i, i, i]);
444        // }
445        // generate_merkle_tree(&leaves);
446    }
447
448    fn bad_merkle_tree_verify(leaves: &[<C as CommitmentScheme>::Output]) -> () {
449        let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
450
451        let crh_parameters = Rc::new(H::setup(&mut rng).unwrap());
452        let tree = JubJubMHT::new(crh_parameters.clone(), &leaves).unwrap();
453        let root = tree.root();
454        for (i, leaf) in leaves.iter().enumerate() {
455            let mut cs = TestConstraintSystem::<Fq>::new();
456            let proof = tree.generate_proof(i, &leaf).unwrap();
457            assert!(proof.verify(&crh_parameters, &root, &leaf).unwrap());
458
459            let digest = DG::alloc(&mut cs.ns(|| format!("new_digest_{}", i)), || {
460                Ok(Digest(JubJub::zero()))
461            })
462            .unwrap();
463            let crh_parameters =
464                <HG as FixedLengthCRHGadget<H, Fq>>::ParametersGadget::alloc(
465                    &mut cs.ns(|| format!("new_parameters_{}", i)),
466                    || Ok(crh_parameters.clone()),
467                )
468                .unwrap();
469            let comm = <CG as CommitmentGadget<C, Fq>>::OutputGadget::alloc(
470                &mut cs.ns(|| format!("new_comm_{}", i)),
471                || {
472                    let leaf = *leaf;
473                    Ok(leaf)
474                },
475            )
476            .unwrap();
477            let cw = LCWG::alloc(&mut cs.ns(|| format!("new_witness_{}", i)), || {
478                Ok(CommPath(proof))
479            })
480            .unwrap();
481            LG::check_witness_gadget(
482                &mut cs.ns(|| format!("new_witness_check_{}", i)),
483                &crh_parameters,
484                &digest,
485                &comm,
486                &cw,
487            )
488            .unwrap();
489            if !cs.is_satisfied() {
490                println!(
491                    "Unsatisfied constraints: {}",
492                    cs.which_is_unsatisfied().unwrap()
493                );
494            }
495            assert!(cs.is_satisfied());
496        }
497    }
498
499    #[should_panic]
500    #[test]
501    fn bad_root_test() {
502        let mut leaves = Vec::new();
503        let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
504        let comm_parameters = C::setup(&mut rng).unwrap();
505        for i in 0..4u8 {
506            let r = PedersenRandomness(Fr::rand(&mut rng));
507            let input = [i, i, i, i, i, i, i, i];
508            leaves.push(C::commit(&comm_parameters, &input, &r).unwrap());
509        }
510        bad_merkle_tree_verify(&leaves);
511    }
512}