liminal_ark_relations/shielder/
deposit_and_merge.rs

1use liminal_ark_relation_macro::snark_relation;
2
3/// It expresses the facts that:
4///  - `old_note` is a prefix of the result of hashing together `token_id`, `old_token_amount`,
5///    `old_trapdoor` and `old_nullifier`,
6///  - `new_note` is a prefix of the result of hashing together `token_id`, `new_token_amount`,
7///    `new_trapdoor` and `new_nullifier`,
8///  - `new_token_amount = token_amount + old_token_amount`
9///  - `merkle_path` is a valid Merkle proof for `old_note` being present at `leaf_index` in some
10///    Merkle tree with `merkle_root` hash in the root
11/// Additionally, the relation has one constant input, `max_path_len` which specifies upper bound
12/// for the length of the merkle path (which is ~the height of the tree, ±1).
13#[snark_relation]
14mod relation {
15    #[cfg(feature = "circuit")]
16    use {
17        crate::shielder::{
18            check_merkle_proof, note_var::NoteVarBuilder, path_shape_var::PathShapeVar,
19            token_amount_var::TokenAmountVar,
20        },
21        ark_r1cs_std::{
22            alloc::{
23                AllocVar,
24                AllocationMode::{Input, Witness},
25            },
26            eq::EqGadget,
27            fields::fp::FpVar,
28        },
29        ark_relations::ns,
30        core::ops::Add,
31    };
32
33    use crate::shielder::{
34        convert_hash, convert_vec,
35        types::{
36            BackendLeafIndex, BackendMerklePath, BackendMerkleRoot, BackendNote, BackendNullifier,
37            BackendTokenAmount, BackendTokenId, BackendTrapdoor, FrontendLeafIndex,
38            FrontendMerklePath, FrontendMerkleRoot, FrontendNote, FrontendNullifier,
39            FrontendTokenAmount, FrontendTokenId, FrontendTrapdoor,
40        },
41    };
42
43    #[relation_object_definition]
44    #[derive(Clone, Debug)]
45    struct DepositAndMergeRelation {
46        #[constant]
47        pub max_path_len: u8,
48
49        // Public inputs
50        #[public_input(frontend_type = "FrontendTokenId")]
51        pub token_id: BackendTokenId,
52        #[public_input(frontend_type = "FrontendNullifier", parse_with = "convert_hash")]
53        pub old_nullifier: BackendNullifier,
54        #[public_input(frontend_type = "FrontendNote", parse_with = "convert_hash")]
55        pub new_note: BackendNote,
56        #[public_input(frontend_type = "FrontendTokenAmount")]
57        pub token_amount: BackendTokenAmount,
58        #[public_input(frontend_type = "FrontendMerkleRoot", parse_with = "convert_hash")]
59        pub merkle_root: BackendMerkleRoot,
60
61        // Private inputs.
62        #[private_input(frontend_type = "FrontendTrapdoor", parse_with = "convert_hash")]
63        pub old_trapdoor: BackendTrapdoor,
64        #[private_input(frontend_type = "FrontendTrapdoor", parse_with = "convert_hash")]
65        pub new_trapdoor: BackendTrapdoor,
66        #[private_input(frontend_type = "FrontendNullifier", parse_with = "convert_hash")]
67        pub new_nullifier: BackendNullifier,
68        #[private_input(frontend_type = "FrontendMerklePath", parse_with = "convert_vec")]
69        pub merkle_path: BackendMerklePath,
70        #[private_input(frontend_type = "FrontendLeafIndex")]
71        pub leaf_index: BackendLeafIndex,
72        #[private_input(frontend_type = "FrontendNote", parse_with = "convert_hash")]
73        pub old_note: BackendNote,
74        #[private_input(frontend_type = "FrontendTokenAmount")]
75        pub old_token_amount: BackendTokenAmount,
76        #[private_input(frontend_type = "FrontendTokenAmount")]
77        pub new_token_amount: BackendTokenAmount,
78    }
79
80    #[cfg(feature = "circuit")]
81    #[circuit_definition]
82    fn generate_constraints() {
83        //------------------------------
84        // Check the old note arguments.
85        //------------------------------
86        let old_note = NoteVarBuilder::new(cs.clone())
87            .with_token_id(self.token_id(), Input)?
88            .with_token_amount(self.old_token_amount(), Witness)?
89            .with_trapdoor(self.old_trapdoor(), Witness)?
90            .with_nullifier(self.old_nullifier(), Input)?
91            .with_note(self.old_note(), Witness)?
92            .build()?;
93
94        //------------------------------
95        // Check the new note arguments.
96        //------------------------------
97        let new_note = NoteVarBuilder::new(cs.clone())
98            .with_token_id_var(old_note.token_id.clone())
99            .with_token_amount(self.new_token_amount(), Witness)?
100            .with_trapdoor(self.new_trapdoor(), Witness)?
101            .with_nullifier(self.new_nullifier(), Witness)?
102            .with_note(self.new_note(), Input)?
103            .build()?;
104
105        //----------------------------------
106        // Check the token values soundness.
107        //----------------------------------
108        let token_amount =
109            TokenAmountVar::new_input(ns!(cs, "token amount"), || self.token_amount())?;
110        let token_sum = token_amount.add(old_note.token_amount)?;
111        token_sum.enforce_equal(&new_note.token_amount)?;
112
113        //------------------------
114        // Check the merkle proof.
115        //------------------------
116        let merkle_root = FpVar::new_input(ns!(cs, "merkle root"), || self.merkle_root())?;
117        let path_shape = PathShapeVar::new_witness(ns!(cs, "path shape"), || {
118            Ok((*self.max_path_len(), self.leaf_index().cloned()))
119        })?;
120
121        check_merkle_proof(
122            merkle_root,
123            path_shape,
124            old_note.note,
125            self.merkle_path().cloned().unwrap_or_default(),
126            *self.max_path_len(),
127            cs,
128        )
129    }
130}
131
132#[cfg(all(test, feature = "circuit"))]
133mod tests {
134    use ark_bls12_381::Bls12_381;
135    use ark_groth16::Groth16;
136    use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystem};
137    use ark_snark::SNARK;
138
139    use super::*;
140    use crate::shielder::{
141        note::{compute_note, compute_parent_hash},
142        types::FrontendNote,
143    };
144
145    const MAX_PATH_LEN: u8 = 4;
146
147    fn get_circuit_with_full_input() -> DepositAndMergeRelationWithFullInput {
148        let token_id: FrontendTokenId = 1;
149
150        let old_trapdoor: FrontendTrapdoor = [17; 4];
151        let old_nullifier: FrontendNullifier = [19; 4];
152        let old_token_amount: FrontendTokenAmount = 7;
153
154        let new_trapdoor: FrontendTrapdoor = [27; 4];
155        let new_nullifier: FrontendNullifier = [87; 4];
156        let new_token_amount: FrontendTokenAmount = 10;
157
158        let token_amount: FrontendTokenAmount = 3;
159
160        let old_note = compute_note(token_id, old_token_amount, old_trapdoor, old_nullifier);
161        let new_note = compute_note(token_id, new_token_amount, new_trapdoor, new_nullifier);
162
163        //                                          merkle root
164        //                placeholder                                        x
165        //        1                          x                     x                         x
166        //   2        3                x          x            x       x                 x       x
167        // 4  *5*   6   7            x   x      x   x        x   x   x   x             x   x   x   x
168        let leaf_index = 5;
169
170        let zero_note = FrontendNote::default(); // x
171
172        let sibling_note = compute_note(0, 1, [2; 4], [3; 4]); // 4
173        let parent_note = compute_parent_hash(sibling_note, old_note); // 2
174        let uncle_note = compute_note(4, 5, [6; 4], [7; 4]); // 3
175        let grandpa_root = compute_parent_hash(parent_note, uncle_note); // 1
176
177        let placeholder = compute_parent_hash(grandpa_root, zero_note);
178        let merkle_root = compute_parent_hash(placeholder, zero_note);
179
180        let merkle_path = vec![sibling_note, uncle_note];
181
182        DepositAndMergeRelationWithFullInput::new(
183            MAX_PATH_LEN,
184            token_id,
185            old_nullifier,
186            new_note,
187            token_amount,
188            merkle_root,
189            old_trapdoor,
190            new_trapdoor,
191            new_nullifier,
192            merkle_path,
193            leaf_index,
194            old_note,
195            old_token_amount,
196            new_token_amount,
197        )
198    }
199
200    #[test]
201    fn deposit_and_merge_constraints_correctness() {
202        let circuit = get_circuit_with_full_input();
203
204        let cs = ConstraintSystem::new_ref();
205        circuit.generate_constraints(cs.clone()).unwrap();
206
207        let is_satisfied = cs.is_satisfied().unwrap();
208        if !is_satisfied {
209            println!("{:?}", cs.which_is_unsatisfied());
210        }
211
212        assert!(is_satisfied);
213    }
214
215    #[test]
216    fn deposit_and_merge_proving_procedure() {
217        let circuit_withouth_input = DepositAndMergeRelationWithoutInput::new(MAX_PATH_LEN);
218
219        let mut rng = ark_std::test_rng();
220        let (pk, vk) =
221            Groth16::<Bls12_381>::circuit_specific_setup(circuit_withouth_input, &mut rng).unwrap();
222
223        let circuit = get_circuit_with_full_input();
224        let proof = Groth16::prove(&pk, circuit, &mut rng).unwrap();
225
226        let circuit: DepositAndMergeRelationWithPublicInput = get_circuit_with_full_input().into();
227        let input = circuit.serialize_public_input();
228        let valid_proof = Groth16::verify(&vk, &input, &proof).unwrap();
229        assert!(valid_proof);
230    }
231}
liminal_ark_relations/shielder/deposit_and_merge.rs

liminal_ark_relations/shielder/
deposit_and_merge.rs
