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 parameters(&self) -> Vec<(DataType, String)> {
53        vec![(DataType::Digest, "program_digest".to_owned())]
54    }
55
56    fn return_values(&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 HashMap<BFieldElement, BFieldElement>,
170            _: &NonDeterminism,
171            _: &[BFieldElement],
172            sponge: &mut Option<Tip5>,
173        ) -> Result<Vec<BFieldElement>, RustShadowError> {
174            let Some(sponge) = sponge.as_mut() else {
175                return Err(RustShadowError::SpongeUninitialized);
176            };
177            let program_digest = pop_encodable(stack)?;
178
179            let claim = Claim::new(program_digest);
180            let challenges = sponge.sample_scalars(self.num_of_fiat_shamir_challenges);
181            let challenges = Challenges::new(challenges, &claim);
182            dbg!(
183                "Rust-shadowing challenges: {}",
184                challenges.challenges.iter().join("\n")
185            );
186
187            stack.push(self.challenges_pointer);
188
189            insert_as_array(
190                self.challenges_pointer,
191                memory,
192                challenges.challenges.to_vec(),
193            );
194
195            Ok(Vec::new())
196        }
197
198        fn pseudorandom_initial_state(
199            &self,
200            seed: [u8; 32],
201            _: Option<BenchmarkCase>,
202        ) -> ProcedureInitialState {
203            let mut rng = StdRng::from_seed(seed);
204            let program_digest: Digest = rng.random();
205            let challenge = program_digest.0.into_iter().rev().collect_vec();
206            let stack = [self.init_stack_for_isolated_run(), challenge].concat();
207            let sponge = Tip5 {
208                state: rng.random(),
209            };
210
211            ProcedureInitialState {
212                stack,
213                sponge: Some(sponge),
214                ..Default::default()
215            }
216        }
217    }
218
219    #[macro_rules_attr::apply(test)]
220    fn new_challenge_empty_input_output_pbt() {
221        const NUM_OF_CLAIM_DERIVED_CHALLENGES: usize = 4;
222        ShadowedProcedure::new(NewEmptyInputAndOutput {
223            num_of_claim_derived_challenges: NUM_OF_CLAIM_DERIVED_CHALLENGES,
224            num_of_fiat_shamir_challenges: Challenges::COUNT - NUM_OF_CLAIM_DERIVED_CHALLENGES,
225            challenges_pointer: shared::conventional_challenges_pointer(),
226        })
227        .test();
228    }
229}
230
231#[cfg(test)]
232mod benches {
233    use triton_vm::challenges::Challenges;
234
235    use super::*;
236    use crate::test_prelude::*;
237    use crate::verifier::challenges::shared;
238
239    #[macro_rules_attr::apply(test)]
240    fn benchmark() {
241        const NUM_OF_CLAIM_DERIVED_CHALLENGES: usize = 4;
242        ShadowedProcedure::new(NewEmptyInputAndOutput {
243            num_of_claim_derived_challenges: 4,
244            num_of_fiat_shamir_challenges: Challenges::COUNT - NUM_OF_CLAIM_DERIVED_CHALLENGES,
245            challenges_pointer: shared::conventional_challenges_pointer(),
246        })
247        .bench();
248    }
249}
tasm_lib/verifier/challenges/new_empty_input_and_output.rs

tasm_lib/verifier/challenges/
new_empty_input_and_output.rs
