kimchi/circuits/polynomials/range_check/
gadget.rs

1//! Range check gate
2
3use ark_ff::{FftField, PrimeField};
4
5use crate::{
6    alphas::Alphas,
7    circuits::{
8        argument::Argument,
9        berkeley_columns::E,
10        expr::Cache,
11        gate::{CircuitGate, Connect, GateType},
12        lookup::{
13            self,
14            tables::{GateLookupTable, LookupTable},
15        },
16        wires::Wire,
17    },
18};
19
20use super::circuitgates::{RangeCheck0, RangeCheck1};
21
22pub const GATE_COUNT: usize = 2;
23
24impl<F: PrimeField> CircuitGate<F> {
25    /// Create range check gate for constraining three 88-bit values.
26    ///     Inputs the starting row
27    ///     Outputs tuple (`next_row`, `circuit_gates`) where
28    ///       `next_row`      - next row after this gate
29    ///       `circuit_gates` - vector of circuit gates comprising this gate
30    pub fn create_multi_range_check(start_row: usize) -> (usize, Vec<Self>) {
31        Self::create_multi_range_check_gadget(start_row, false)
32    }
33
34    /// Create range check gate for constraining compact limbs.
35    ///     Inputs the starting row
36    ///     Outputs tuple (`next_row`, `circuit_gates`) where
37    ///       `next_row`      - next row after this gate
38    ///       `circuit_gates` - vector of circuit gates comprising this gate
39    pub fn create_compact_multi_range_check(start_row: usize) -> (usize, Vec<Self>) {
40        Self::create_multi_range_check_gadget(start_row, true)
41    }
42
43    /// Create foreign field muti-range-check gadget by extending the existing gates
44    pub fn extend_multi_range_check(gates: &mut Vec<Self>, curr_row: &mut usize) {
45        let (next_row, circuit_gates) = Self::create_multi_range_check(*curr_row);
46        *curr_row = next_row;
47        gates.extend_from_slice(&circuit_gates);
48    }
49
50    /// Create foreign field muti-range-check gadget by extending the existing gates
51    pub fn extend_compact_multi_range_check(gates: &mut Vec<Self>, curr_row: &mut usize) {
52        let (next_row, circuit_gates) = Self::create_compact_multi_range_check(*curr_row);
53        *curr_row = next_row;
54        gates.extend_from_slice(&circuit_gates);
55    }
56
57    /// Create single range check gate
58    ///     Inputs the starting row
59    ///     Outputs tuple (`next_row`, `circuit_gates`) where
60    ///       `next_row`      - next row after this gate
61    ///       `circuit_gates` - vector of circuit gates comprising this gate
62    pub fn create_range_check(start_row: usize) -> (usize, Vec<Self>) {
63        let gate = CircuitGate::new(
64            GateType::RangeCheck0,
65            Wire::for_row(start_row),
66            vec![F::zero()],
67        );
68        (start_row + 1, vec![gate])
69    }
70
71    /// Create foreign field range-check gate by extending the existing gates
72    pub fn extend_range_check(gates: &mut Vec<Self>, curr_row: &mut usize) {
73        let (next_row, circuit_gates) = Self::create_range_check(*curr_row);
74        *curr_row = next_row;
75        gates.extend_from_slice(&circuit_gates);
76    }
77
78    // Create range check gate for constraining three 88-bit values.
79    //     Inputs the starting row and whether the limbs are in compact format
80    //     Outputs tuple (`next_row`, `circuit_gates`) where
81    //       `next_row`      - next row after this gate
82    //       `circuit_gates` - vector of circuit gates comprising this gate
83    fn create_multi_range_check_gadget(start_row: usize, compact: bool) -> (usize, Vec<Self>) {
84        let coeff = if compact { F::one() } else { F::zero() };
85
86        let mut circuit_gates = vec![
87            CircuitGate::new(
88                GateType::RangeCheck0,
89                Wire::for_row(start_row),
90                vec![F::zero()],
91            ),
92            CircuitGate::new(
93                GateType::RangeCheck0,
94                Wire::for_row(start_row + 1),
95                vec![coeff],
96            ),
97            CircuitGate::new(GateType::RangeCheck1, Wire::for_row(start_row + 2), vec![]),
98            CircuitGate::new(GateType::Zero, Wire::for_row(start_row + 3), vec![]),
99        ];
100
101        // copy v0p0
102        circuit_gates.connect_cell_pair((0, 1), (3, 3));
103
104        // copy v0p1
105        circuit_gates.connect_cell_pair((0, 2), (3, 4));
106
107        // copy v1p0
108        circuit_gates.connect_cell_pair((1, 1), (3, 5));
109
110        // copy v1p1
111        circuit_gates.connect_cell_pair((1, 2), (3, 6));
112
113        (start_row + circuit_gates.len(), circuit_gates)
114    }
115}
116
117/// Get vector of range check circuit gate types
118pub fn circuit_gates() -> [GateType; GATE_COUNT] {
119    [GateType::RangeCheck0, GateType::RangeCheck1]
120}
121
122/// Number of constraints for a given range check circuit gate type
123///
124/// # Panics
125///
126/// Will panic if `typ` is not `RangeCheck`-related gate type.
127pub fn circuit_gate_constraint_count<F: PrimeField>(typ: GateType) -> u32 {
128    match typ {
129        GateType::RangeCheck0 => RangeCheck0::<F>::CONSTRAINTS,
130        GateType::RangeCheck1 => RangeCheck1::<F>::CONSTRAINTS,
131        _ => panic!("invalid gate type"),
132    }
133}
134
135/// Get combined constraints for a given range check circuit gate type
136///
137/// # Panics
138///
139/// Will panic if `typ` is not `RangeCheck`-related gate type.
140pub fn circuit_gate_constraints<F: PrimeField>(
141    typ: GateType,
142    alphas: &Alphas<F>,
143    cache: &mut Cache,
144) -> E<F> {
145    match typ {
146        GateType::RangeCheck0 => RangeCheck0::combined_constraints(alphas, cache),
147        GateType::RangeCheck1 => RangeCheck1::combined_constraints(alphas, cache),
148        _ => panic!("invalid gate type"),
149    }
150}
151
152/// Get the combined constraints for all range check circuit gate types
153pub fn combined_constraints<F: PrimeField>(alphas: &Alphas<F>, cache: &mut Cache) -> E<F> {
154    RangeCheck0::combined_constraints(alphas, cache)
155        + RangeCheck1::combined_constraints(alphas, cache)
156}
157
158/// Get the range check lookup table
159pub fn lookup_table<F: FftField>() -> LookupTable<F> {
160    lookup::tables::get_table::<F>(GateLookupTable::RangeCheck)
161}
kimchi/circuits/polynomials/range_check/gadget.rs

kimchi/circuits/polynomials/range_check/
gadget.rs
