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 inputs(&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 outputs(&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        ) {
74            // read stack arguments
75            let round = stack.pop().unwrap().value() as usize;
76            let index = stack.pop().unwrap().value() as u32;
77            let fri_verify_address = stack.pop().unwrap();
78
79            // read fri_verify object from memory
80            let fri_verify = FriVerify::decode_from_memory(memory, fri_verify_address).unwrap();
81
82            // invoke actual function
83            let x = fri_verify.get_collinearity_check_x(index, round);
84
85            // push to stack
86            stack.push(x.coefficients[2]);
87            stack.push(x.coefficients[1]);
88            stack.push(x.coefficients[0]);
89        }
90
91        fn pseudorandom_initial_state(
92            &self,
93            seed: [u8; 32],
94            bench_case: Option<BenchmarkCase>,
95        ) -> FunctionInitialState {
96            let mut rng = StdRng::from_seed(seed);
97            let round = if let Some(case) = bench_case {
98                match case {
99                    BenchmarkCase::CommonCase => 10,
100                    BenchmarkCase::WorstCase => 20,
101                }
102            } else {
103                rng.random_range(0..10)
104            };
105            let fri_domain_length = if let Some(case) = bench_case {
106                match case {
107                    BenchmarkCase::CommonCase => 1 << 20,
108                    BenchmarkCase::WorstCase => 1 << 25,
109                }
110            } else {
111                1 << (rng.random_range(0..5) + round)
112            };
113            let index = rng.random_range(0..fri_domain_length);
114
115            let fri_verify = FriVerify::new(rng.random(), fri_domain_length, 4, 40);
116
117            let mut memory = HashMap::<BFieldElement, BFieldElement>::new();
118            let fri_verify_address = BFieldElement::zero();
119            encode_to_memory(&mut memory, fri_verify_address, &fri_verify);
120
121            let mut stack = empty_stack();
122            stack.push(fri_verify_address);
123            stack.push(BFieldElement::new(index as u64));
124            stack.push(BFieldElement::new(round as u64));
125
126            FunctionInitialState { stack, memory }
127        }
128    }
129
130    #[test]
131    fn test() {
132        ShadowedFunction::new(GetCollinearityCheckX).test();
133    }
134}
135
136#[cfg(test)]
137mod bench {
138    use super::*;
139    use crate::test_prelude::*;
140
141    #[test]
142    fn bench() {
143        ShadowedFunction::new(GetCollinearityCheckX).bench();
144    }
145}
tasm_lib/verifier/fri/collinearity_check_x.rs

tasm_lib/verifier/fri/
collinearity_check_x.rs
