kimchi/circuits/polynomials/range_check/
gadget.rs

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

kimchi/circuits/polynomials/range_check/
gadget.rs
