libzeropool_zkbob/circuit/
tree.rs

1use fawkes_crypto::{circuit::{
2    bitify::c_from_bits_le,
3    bool::CBool,
4    num::CNum,
5    poseidon::{c_poseidon_merkle_proof_root, CMerkleProof},
6    cs::{RCS, CS}
7}, native::poseidon::poseidon};
8use fawkes_crypto::core::signal::Signal;
9use fawkes_crypto::ff_uint::Num;
10use crate::native::tree::{TreePub, TreeSec};
11use crate::native::params::PoolParams;
12use crate::constants::{HEIGHT, OUTPLUSONELOG};
13
14
15
16
17#[derive(Clone, Signal)]
18#[Value = "TreePub<C::Fr>"]
19pub struct CTreePub<C:CS> {
20    pub root_before: CNum<C>,
21    pub root_after: CNum<C>,
22    pub leaf: CNum<C>
23}
24
25#[derive(Clone, Signal)]
26#[Value = "TreeSec<C::Fr>"]
27pub struct CTreeSec<C:CS> {
28    pub proof_filled:CMerkleProof<C, {HEIGHT - OUTPLUSONELOG}>,
29    pub proof_free:CMerkleProof<C, {HEIGHT - OUTPLUSONELOG}>,
30    pub prev_leaf:CNum<C>
31}
32
33pub fn tree_update<C:CS, P:PoolParams<Fr=C::Fr>>(
34    p: &CTreePub<C>,
35    s: &CTreeSec<C>,
36    params: &P,
37) {
38    let index_filled = c_from_bits_le(s.proof_filled.path.as_slice());
39    let index_free = c_from_bits_le(s.proof_free.path.as_slice());
40
41    let mut zero_leaf_value = Num::ZERO;
42    for _ in 0..OUTPLUSONELOG {
43        zero_leaf_value = poseidon(&[zero_leaf_value, zero_leaf_value], params.compress());
44    }
45
46    let mut zero_root_value = Num::ZERO;
47    for _ in 0..HEIGHT {
48        zero_root_value = poseidon(&[zero_root_value, zero_root_value], params.compress());
49    }
50
51
52    let zero_leaf:CNum<C> = p.derive_const(&zero_leaf_value);
53
54    (c_poseidon_merkle_proof_root(&zero_leaf, &s.proof_free, params.compress()) - &p.root_before).assert_zero();
55    (c_poseidon_merkle_proof_root(&p.leaf, &s.proof_free, params.compress()) - &p.root_after).assert_zero();
56
57    let empty_tree = (&p.root_before-zero_root_value).is_zero();
58
59    let prev_proof_expr = (c_poseidon_merkle_proof_root(&s.prev_leaf, &s.proof_filled, params.compress()) - &p.root_before).is_zero();
60    let prev_index_expr = (index_filled+Num::ONE-&index_free).is_zero();
61    let prev_leaf_expr = !(&s.prev_leaf-zero_leaf_value).is_zero();
62    
63    //for non-empty tree previous proof should be valid for nonzero leaf
64    ((prev_proof_expr & prev_index_expr & prev_leaf_expr) | &empty_tree).assert_const(&true);
65
66    //for empty tree index_free should be zero
67    (index_free.is_zero() | (!&empty_tree)).assert_const(&true);
68}
libzeropool_zkbob/circuit/tree.rs

libzeropool_zkbob/circuit/
tree.rs
