openvm_stark_backend/gkr/
gate.rs

Help
1use p3_field::Field;
2
3use crate::{gkr::types::GkrMask, poly::uni::Fraction};
4
5/// Defines how a circuit operates locally on two input rows to produce a single output row.
6/// This local 2-to-1 constraint is what gives the whole circuit its "binary tree" structure.
7///
8/// Binary tree structured circuits have a highly regular wiring pattern that fit the structure of
9/// the circuits defined in [Thaler13] which allow for efficient linear time (linear in size of the
10/// circuit) GKR prover implementations.
11///
12/// [Thaler13]: https://eprint.iacr.org/2013/351.pdf
13#[derive(Debug, Clone, Copy)]
14pub enum Gate {
15    LogUp,
16    GrandProduct,
17}
18
19impl Gate {
20    /// Returns the output after applying the gate to the mask.
21    pub(crate) fn eval<F: Field>(
22        &self,
23        mask: &GkrMask<F>,
24    ) -> Result<Vec<F>, InvalidNumMaskColumnsError> {
25        Ok(match self {
26            Self::LogUp => {
27                if mask.columns().len() != 2 {
28                    return Err(InvalidNumMaskColumnsError);
29                }
30
31                let [numerator_a, numerator_b] = mask.columns()[0];
32                let [denominator_a, denominator_b] = mask.columns()[1];
33
34                let a = Fraction::new(numerator_a, denominator_a);
35                let b = Fraction::new(numerator_b, denominator_b);
36                let res = a + b;
37
38                vec![res.numerator, res.denominator]
39            }
40            Self::GrandProduct => {
41                if mask.columns().len() != 1 {
42                    return Err(InvalidNumMaskColumnsError);
43                }
44
45                let [a, b] = mask.columns()[0];
46                vec![a * b]
47            }
48        })
49    }
50}
51
52/// Error indicating the mask has an invalid number of columns for a gate's operation.
53#[derive(Debug)]
54pub struct InvalidNumMaskColumnsError;
openvm_stark_backend/gkr/gate.rs

openvm_stark_backend/gkr/
gate.rs
