tasm_lib/verifier/vm_proof_iter/
new.rs

1use triton_vm::prelude::*;
2
3use crate::prelude::*;
4use crate::verifier::stark_verify::NUM_PROOF_ITEMS_EXCLUDING_FRI;
5use crate::verifier::stark_verify::NUM_PROOF_ITEMS_PER_FRI_ROUND;
6use crate::verifier::vm_proof_iter::shared::vm_proof_iter_type;
7
8/// Create a new `VmProofIter` instance.
9///
10/// A `VmProofIter` points to the next proof item in memory to be read in
11/// verifying a proof. It also counts how many proof items have been read and
12/// records the starting point and indicated length of the proof.
13#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
14pub struct New;
15
16impl New {
17    pub const FIRST_PROOF_ITEM_OFFSET: u64 = 4;
18    pub const MAX_PROOF_SIZE: usize = 1 << 26;
19
20    const MAX_NUMBER_OF_FRI_ROUNDS: usize = 24;
21    const SAFETY_MARGIN_PER_FRI_ROUND: usize = 1;
22    pub const MAX_NUM_PROOF_ITEMS: usize = Self::MAX_NUMBER_OF_FRI_ROUNDS
23        * (NUM_PROOF_ITEMS_PER_FRI_ROUND + Self::SAFETY_MARGIN_PER_FRI_ROUND)
24        + NUM_PROOF_ITEMS_EXCLUDING_FRI;
25}
26
27impl BasicSnippet for New {
28    fn inputs(&self) -> Vec<(DataType, String)> {
29        vec![(DataType::VoidPointer, "*proof".to_string())]
30    }
31
32    fn outputs(&self) -> Vec<(DataType, String)> {
33        vec![(
34            DataType::StructRef(vm_proof_iter_type()),
35            "vm_proof_iter".to_owned(),
36        )]
37    }
38
39    fn entrypoint(&self) -> String {
40        "tasmlib_verifier_vm_proof_iter_new".to_owned()
41    }
42
43    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
44        let entrypoint = self.entrypoint();
45        let dyn_malloc = library.import(Box::new(DynMalloc));
46
47        triton_asm!(
48            {entrypoint}:
49                // _ *proof
50
51                addi {Self::FIRST_PROOF_ITEM_OFFSET}
52                dup 0
53                addi -1
54                read_mem {Self::FIRST_PROOF_ITEM_OFFSET}
55                addi 1
56                push 0
57                place 5
58                hint first_proof_item: u32 = stack[6]
59                hint current_proof_item: u32 = stack[5]
60                hint num_proof_items: u32 = stack[4]
61                hint proof_len: u32 = stack[1]
62                // _ *first_proof_item current_proof_item num_proof_items (proof_len - 2) (proof_len - 1) proof_len *proof
63
64
65                /* Verify consistent size-indicators */
66                place 3
67                place 2
68                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len (proof_len - 2) (proof_len - 1)
69
70                addi 1
71                dup 2
72                eq
73                assert error_id 300
74                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len (proof_len - 2)
75
76                addi 2
77                dup 1
78                eq
79                assert error_id 301
80                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len
81
82
83                /* Verify sane sizes */
84                push {Self::MAX_PROOF_SIZE}
85                dup 1
86                lt
87                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len (proof_len < MAX_SIZE)
88
89                assert error_id 302
90
91                push {Self::MAX_NUM_PROOF_ITEMS}
92                dup 3
93                lt
94                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len (num_proof_items < MAX_NUM_ITEMS)
95
96                assert error_id 303
97                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len
98
99
100                /* Verify that entire proof lives in first memory page */
101                dup 1
102                pop_count
103                pop 1
104                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len
105
106                dup 0
107                pop_count
108                pop 1
109                // _ *first_proof_item current_proof_item num_proof_items *proof proof_len
110
111                dup 1
112                dup 1
113                add
114                pop_count
115                pop 1
116
117
118                /* Write proof information to memory */
119                pick 4
120                // _ current_proof_item num_proof_items *proof proof_len *first_proof_item
121
122                call {dyn_malloc}
123                // _ current_proof_item num_proof_items *proof proof_len *first_proof_item *vm_proof_iter
124
125                write_mem 5
126                // _ (*vm_proof_iter + 5)
127
128                addi -5
129                // _ *vm_proof_iter
130
131                return
132        )
133    }
134}
135
136#[cfg(test)]
137mod tests {
138    use arbitrary::Arbitrary;
139    use arbitrary::Unstructured;
140    use triton_vm::proof_item::ProofItem;
141    use triton_vm::proof_stream::ProofStream;
142
143    use super::*;
144    use crate::rust_shadowing_helper_functions;
145    use crate::test_prelude::*;
146    use crate::verifier::vm_proof_iter::shared::vm_proof_iter_struct::VmProofIter;
147
148    #[test]
149    fn vm_proof_iter_new_pbt() {
150        ShadowedFunction::new(New).test()
151    }
152
153    impl New {
154        fn init_state(
155            &self,
156            proof_items: Vec<ProofItem>,
157            proof_pointer: BFieldElement,
158        ) -> FunctionInitialState {
159            let mut proof_stream = ProofStream::default();
160            for proof_item in proof_items {
161                proof_stream.enqueue(proof_item);
162            }
163
164            let proof: Proof = proof_stream.into();
165            let mut memory = HashMap::default();
166            encode_to_memory(&mut memory, proof_pointer, &proof);
167
168            FunctionInitialState {
169                stack: [self.init_stack_for_isolated_run(), vec![proof_pointer]].concat(),
170                memory,
171            }
172        }
173    }
174
175    impl Function for New {
176        fn rust_shadow(
177            &self,
178            stack: &mut Vec<BFieldElement>,
179            memory: &mut HashMap<BFieldElement, BFieldElement>,
180        ) {
181            let pointer_to_proof = stack.pop().unwrap();
182            let proof = *Proof::decode_from_memory(memory, pointer_to_proof).unwrap();
183            let pointer_to_vm_proof_iter =
184                rust_shadowing_helper_functions::dyn_malloc::dynamic_allocator(memory);
185            let vm_proof_iter = VmProofIter::new(pointer_to_proof, &proof);
186            encode_to_memory(memory, pointer_to_vm_proof_iter, &vm_proof_iter);
187            stack.push(pointer_to_vm_proof_iter);
188        }
189
190        fn pseudorandom_initial_state(
191            &self,
192            seed: [u8; 32],
193            _bench_case: Option<BenchmarkCase>,
194        ) -> FunctionInitialState {
195            let mut rng = StdRng::from_seed(seed);
196            let proof_pointer = bfe!(rng.random_range(0..(1 << 20)));
197
198            // put randomness on heap because stack might be too small
199            let mut randomness = vec![0; 1_000_000];
200            rng.fill_bytes(&mut randomness);
201            let mut unstructured = Unstructured::new(&randomness);
202            let proof_items = (0..rng.random_range(10..25))
203                .map(|_| ProofItem::arbitrary(&mut unstructured).unwrap())
204                .collect();
205
206            self.init_state(proof_items, proof_pointer)
207        }
208    }
209}
tasm_lib/verifier/vm_proof_iter/new.rs

tasm_lib/verifier/vm_proof_iter/
new.rs
