tasm_lib/verifier/challenges/
new_empty_input_and_output.rs

1use num::One;
2use triton_vm::air::challenge_id::ChallengeId;
3use triton_vm::air::cross_table_argument::CrossTableArg;
4use triton_vm::air::cross_table_argument::EvalArg;
5use triton_vm::prelude::*;
6use twenty_first::math::x_field_element::EXTENSION_DEGREE;
7
8use crate::hashing::algebraic_hasher::sample_scalars_static_length_static_pointer::SampleScalarsStaticLengthStaticPointer;
9use crate::prelude::*;
10use crate::verifier::challenges::shared::challenges_data_type;
11use crate::verifier::eval_arg::compute_terminal_const_sized_static_symbols::ComputeTerminalConstSizedStaticSymbols;
12use crate::verifier::eval_arg::compute_terminal_from_digest::ComputeTerminalFromDigestInitialIsOne;
13
14#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
15pub struct NewEmptyInputAndOutput {
16    // claim_input: Vec<BFieldElement>,
17    // claim_output: Vec<BFieldElement>,
18    num_of_fiat_shamir_challenges: usize,
19    num_of_claim_derived_challenges: usize,
20
21    /// Memory address to store the challenges
22    pub challenges_pointer: BFieldElement,
23}
24
25impl NewEmptyInputAndOutput {
26    pub fn new(
27        num_challenges_to_sample: usize,
28        num_challenges_to_compute: usize,
29        challenges_pointer: BFieldElement,
30    ) -> Self {
31        Self {
32            num_of_fiat_shamir_challenges: num_challenges_to_sample,
33            num_of_claim_derived_challenges: num_challenges_to_compute,
34            challenges_pointer,
35        }
36    }
37
38    fn total_number_of_challenges_returned(&self) -> usize {
39        self.num_of_fiat_shamir_challenges + self.num_of_claim_derived_challenges
40    }
41
42    fn sample_scalars_snippet(&self) -> SampleScalarsStaticLengthStaticPointer {
43        SampleScalarsStaticLengthStaticPointer {
44            num_elements_to_sample: self.num_of_fiat_shamir_challenges,
45            extra_capacity: self.num_of_claim_derived_challenges,
46            scalars_pointer: self.challenges_pointer,
47        }
48    }
49}
50
51impl BasicSnippet for NewEmptyInputAndOutput {
52    fn inputs(&self) -> Vec<(DataType, String)> {
53        vec![(DataType::Digest, "program_digest".to_owned())]
54    }
55
56    fn outputs(&self) -> Vec<(DataType, String)> {
57        vec![(
58            challenges_data_type(self.total_number_of_challenges_returned()),
59            "challenges".to_owned(),
60        )]
61    }
62
63    fn entrypoint(&self) -> String {
64        format!(
65            "tasmlib_verifier_challenges_new_empty_input_and_output_{}_{}",
66            self.num_of_fiat_shamir_challenges, self.num_of_claim_derived_challenges,
67        )
68    }
69
70    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
71        let entrypoint = self.entrypoint();
72        let sample_scalars_snippet = self.sample_scalars_snippet();
73        let sample_scalars = library.import(Box::new(sample_scalars_snippet));
74        let compute_compressed_digest =
75            library.import(Box::new(ComputeTerminalFromDigestInitialIsOne));
76        let calculate_lookup_terminal =
77            library.import(Box::new(ComputeTerminalConstSizedStaticSymbols {
78                symbols: tip5::LOOKUP_TABLE.map(|i| BFieldElement::new(i as u64)),
79                initial: XFieldElement::one(),
80            }));
81
82        let scalars_pointer = self.challenges_pointer;
83        let scalar_write_index = |i: ChallengeId| {
84            scalars_pointer.value() + u64::try_from(i.index() * EXTENSION_DEGREE).unwrap()
85        };
86        let scalar_read_index =
87            |i: ChallengeId| scalar_write_index(i) + u64::try_from(EXTENSION_DEGREE - 1).unwrap();
88
89        triton_asm!(
90            {entrypoint}:
91                // _ [program_digest]
92                call {sample_scalars}
93                // _ [program_digest]
94
95                push {scalar_read_index(ChallengeId::CompressProgramDigestIndeterminate)}
96                read_mem {EXTENSION_DEGREE}
97                pop 1
98                // _ [program_digest; 5] [compress_program_digest_indeterminate; 3]
99                dup 7
100                dup 7
101                dup 7
102                dup 7
103                dup 7
104                // _ [program_digest; 5] [compress_program_digest_indeterminate; 3] [program_digest; 5]
105
106                call {compute_compressed_digest}
107                // _ [program_digest; 5] [compressed_digest; 3]
108
109                // **** Write compressed_digest to challenges array ****
110                push {scalar_write_index(ChallengeId::CompressedProgramDigest)}
111                write_mem {EXTENSION_DEGREE}
112                pop 1
113                // _ [program_digest; 5]
114                pop 5
115                // _
116
117                // **** Calculate lookup_terminal ****
118                push {scalar_read_index(ChallengeId::LookupTablePublicIndeterminate)}
119                read_mem {EXTENSION_DEGREE}
120                pop 1
121                // _ [lookup_table_public_indeterminate]
122
123                call {calculate_lookup_terminal}
124                // _ [lookup_terminal]
125
126                // **** Write lookup_terminal to challenges array ****
127                push {scalar_write_index(ChallengeId::LookupTablePublicTerminal)}
128                write_mem {EXTENSION_DEGREE}
129                pop 1
130
131                // Store `input_terminal`
132                push {EvalArg::default_initial().coefficients[2]}
133                push {EvalArg::default_initial().coefficients[1]}
134                push {EvalArg::default_initial().coefficients[0]}
135                push {scalar_write_index(ChallengeId::StandardInputTerminal)}
136                write_mem {EXTENSION_DEGREE}
137                pop 1
138
139                // Store `output_terminal`
140                push {EvalArg::default_initial().coefficients[2]}
141                push {EvalArg::default_initial().coefficients[1]}
142                push {EvalArg::default_initial().coefficients[0]}
143                push {scalar_write_index(ChallengeId::StandardOutputTerminal)}
144                write_mem {EXTENSION_DEGREE}
145                pop 1
146                // _
147
148                push {scalars_pointer}
149                // _ *scalars
150
151                return
152        )
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use triton_vm::challenges::Challenges;
159
160    use super::*;
161    use crate::rust_shadowing_helper_functions::array::insert_as_array;
162    use crate::test_prelude::*;
163    use crate::verifier::challenges::shared;
164
165    impl Procedure for NewEmptyInputAndOutput {
166        fn rust_shadow(
167            &self,
168            stack: &mut Vec<BFieldElement>,
169            memory: &mut std::collections::HashMap<BFieldElement, BFieldElement>,
170            _: &NonDeterminism,
171            _: &[BFieldElement],
172            sponge: &mut Option<Tip5>,
173        ) -> Vec<BFieldElement> {
174            let sponge = sponge.as_mut().expect("sponge must be initialized");
175            let program_digest = pop_encodable(stack);
176
177            let claim = Claim::new(program_digest);
178            let challenges = sponge.sample_scalars(self.num_of_fiat_shamir_challenges);
179            let challenges = Challenges::new(challenges, &claim);
180            dbg!(
181                "Rust-shadowing challenges: {}",
182                challenges.challenges.iter().join("\n")
183            );
184
185            stack.push(self.challenges_pointer);
186
187            insert_as_array(
188                self.challenges_pointer,
189                memory,
190                challenges.challenges.to_vec(),
191            );
192
193            vec![]
194        }
195
196        fn pseudorandom_initial_state(
197            &self,
198            seed: [u8; 32],
199            _: Option<BenchmarkCase>,
200        ) -> ProcedureInitialState {
201            let mut rng = StdRng::from_seed(seed);
202            let program_digest: Digest = rng.random();
203            let challenge = program_digest.0.into_iter().rev().collect_vec();
204            let stack = [self.init_stack_for_isolated_run(), challenge].concat();
205            let sponge = Tip5 {
206                state: rng.random(),
207            };
208
209            ProcedureInitialState {
210                stack,
211                sponge: Some(sponge),
212                ..Default::default()
213            }
214        }
215    }
216
217    #[test]
218    fn new_challenge_empty_input_output_pbt() {
219        const NUM_OF_CLAIM_DERIVED_CHALLENGES: usize = 4;
220        ShadowedProcedure::new(NewEmptyInputAndOutput {
221            num_of_claim_derived_challenges: NUM_OF_CLAIM_DERIVED_CHALLENGES,
222            num_of_fiat_shamir_challenges: Challenges::COUNT - NUM_OF_CLAIM_DERIVED_CHALLENGES,
223            challenges_pointer: shared::conventional_challenges_pointer(),
224        })
225        .test();
226    }
227}
228
229#[cfg(test)]
230mod benches {
231    use triton_vm::challenges::Challenges;
232
233    use super::*;
234    use crate::test_prelude::*;
235    use crate::verifier::challenges::shared;
236
237    #[test]
238    fn benchmark() {
239        const NUM_OF_CLAIM_DERIVED_CHALLENGES: usize = 4;
240        ShadowedProcedure::new(NewEmptyInputAndOutput {
241            num_of_claim_derived_challenges: 4,
242            num_of_fiat_shamir_challenges: Challenges::COUNT - NUM_OF_CLAIM_DERIVED_CHALLENGES,
243            challenges_pointer: shared::conventional_challenges_pointer(),
244        })
245        .bench();
246    }
247}
tasm_lib/verifier/challenges/new_empty_input_and_output.rs

tasm_lib/verifier/challenges/
new_empty_input_and_output.rs
