tasm_lib/verifier/fri/
collinearity_check_x.rs

1use triton_vm::prelude::*;
2
3use crate::field;
4use crate::prelude::*;
5use crate::verifier::fri::verify::FriVerify;
6
7/// Compute domain\[index\]^(1<<round)
8#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
9pub struct GetCollinearityCheckX;
10
11impl BasicSnippet for GetCollinearityCheckX {
12    fn parameters(&self) -> Vec<(DataType, String)> {
13        vec![
14            (DataType::VoidPointer, "*fri_verify".to_string()),
15            (DataType::U32, "index".to_string()),
16            (DataType::U32, "round".to_string()),
17        ]
18    }
19
20    fn return_values(&self) -> Vec<(DataType, String)> {
21        vec![(DataType::Xfe, "evaluation_argument".to_string())]
22    }
23
24    fn entrypoint(&self) -> String {
25        "tasmlib_verifier_collinearity_check_x".to_string()
26    }
27
28    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
29        let entrypoint = self.entrypoint();
30        let domain_offset = field!(FriVerify::domain_offset);
31        let domain_generator = field!(FriVerify::domain_generator);
32
33        triton_asm! {
34            // BEFORE: _ *fri_verify index round
35            // AFTER:  _ x2 x1 x0
36            {entrypoint}:
37                dup 2               // _ *fri_verify index round *fri_verify
38                {&domain_generator} // _ *fri_verify index round *domain_generator
39                read_mem 1 pop 1    // _ *fri_verify index round domain_generator
40                dup 2               // _ *fri_verify index round domain_generator index
41                swap 1 pow          // _ *fri_verify index round domain_generator^index
42
43                dup 3               // _ *fri_verify index round domain_generator^index *fri_verify
44                {&domain_offset}    // _ *fri_verify index round domain_generator^index *domain_offset
45                read_mem 1 pop 1    // _ *fri_verify index round domain_generator^index domain_offset
46                mul                 // _ *fri_verify index round domain_generator^index*domain_offset
47
48                dup 1 push 2 pow    // _ *fri_verify index round domain_generator^index*domain_offset 2^round
49
50                swap 1 pow          // _ *fri_verify index round (domain_generator^index*domain_offset)^(1<<round)
51
52                swap 3 pop 3        // _ (g^i*o)^(1<<r)
53                push 0 push 0 swap 2
54                                    // _ 0 0 (g^i*o)^(1<<r)
55                return
56        }
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use num_traits::Zero;
63
64    use super::*;
65    use crate::empty_stack;
66    use crate::test_prelude::*;
67
68    impl Function for GetCollinearityCheckX {
69        fn rust_shadow(
70            &self,
71            stack: &mut Vec<BFieldElement>,
72            memory: &mut HashMap<BFieldElement, BFieldElement>,
73        ) -> Result<(), RustShadowError> {
74            // read stack arguments
75            let round = stack.pop().ok_or(RustShadowError::StackUnderflow)?.value() as usize;
76            let index = stack.pop().ok_or(RustShadowError::StackUnderflow)?.value() as u32;
77            let fri_verify_address = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
78
79            // read fri_verify object from memory
80            let fri_verify = FriVerify::decode_from_memory(memory, fri_verify_address)
81                .map_err(|_| RustShadowError::DecodingError)?;
82
83            // invoke actual function
84            let x = fri_verify.get_collinearity_check_x(index, round);
85
86            // push to stack
87            stack.push(x.coefficients[2]);
88            stack.push(x.coefficients[1]);
89            stack.push(x.coefficients[0]);
90            Ok(())
91        }
92
93        fn pseudorandom_initial_state(
94            &self,
95            seed: [u8; 32],
96            bench_case: Option<BenchmarkCase>,
97        ) -> FunctionInitialState {
98            let mut rng = StdRng::from_seed(seed);
99            let round = if let Some(case) = bench_case {
100                match case {
101                    BenchmarkCase::CommonCase => 10,
102                    BenchmarkCase::WorstCase => 20,
103                }
104            } else {
105                rng.random_range(0..10)
106            };
107            let fri_domain_length = if let Some(case) = bench_case {
108                match case {
109                    BenchmarkCase::CommonCase => 1 << 20,
110                    BenchmarkCase::WorstCase => 1 << 25,
111                }
112            } else {
113                1 << (rng.random_range(0..5) + round)
114            };
115            let index = rng.random_range(0..fri_domain_length);
116
117            let fri_verify = FriVerify::new(rng.random(), fri_domain_length, 4, 40);
118
119            let mut memory = HashMap::<BFieldElement, BFieldElement>::new();
120            let fri_verify_address = BFieldElement::zero();
121            encode_to_memory(&mut memory, fri_verify_address, &fri_verify);
122
123            let mut stack = empty_stack();
124            stack.push(fri_verify_address);
125            stack.push(BFieldElement::new(index as u64));
126            stack.push(BFieldElement::new(round as u64));
127
128            FunctionInitialState { stack, memory }
129        }
130    }
131
132    #[macro_rules_attr::apply(test)]
133    fn test() {
134        ShadowedFunction::new(GetCollinearityCheckX).test();
135    }
136}
137
138#[cfg(test)]
139mod bench {
140    use super::*;
141    use crate::test_prelude::*;
142
143    #[macro_rules_attr::apply(test)]
144    fn bench() {
145        ShadowedFunction::new(GetCollinearityCheckX).bench();
146    }
147}
tasm_lib/verifier/fri/collinearity_check_x.rs

tasm_lib/verifier/fri/
collinearity_check_x.rs
