jf_relation/gadgets/
range.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! Implementation of circuit lookup related gadgets
8
9use super::utils::next_multiple;
10use crate::{constants::GATE_WIDTH, BoolVar, Circuit, CircuitError, PlonkCircuit, Variable};
11use ark_ff::{BigInteger, PrimeField};
12use ark_std::{format, string::ToString, vec::Vec};
13
14impl<F: PrimeField> PlonkCircuit<F> {
15    /// Constrain a variable to be within the [0, 2^`bit_len`) range
16    /// Return error if the variable is invalid.
17    pub fn enforce_in_range(&mut self, a: Variable, bit_len: usize) -> Result<(), CircuitError> {
18        if self.support_lookup() {
19            self.range_gate_with_lookup(a, bit_len)?;
20        } else {
21            self.range_gate_internal(a, bit_len)?;
22        }
23        Ok(())
24    }
25
26    /// Return a boolean variable indicating whether variable `a` is in the
27    /// range [0, 2^`bit_len`). Return error if the variable is invalid.
28    /// TODO: optimize the gate for UltraPlonk.
29    pub fn is_in_range(&mut self, a: Variable, bit_len: usize) -> Result<BoolVar, CircuitError> {
30        let a_bit_le: Vec<BoolVar> = self.unpack(a, F::MODULUS_BIT_SIZE as usize)?;
31        let a_bit_le: Vec<Variable> = a_bit_le.into_iter().map(|b| b.into()).collect();
32        // a is in range if and only if the bits in `a_bit_le[bit_len..]` are all
33        // zeroes.
34        let higher_bit_sum = self.sum(&a_bit_le[bit_len..])?;
35        self.is_zero(higher_bit_sum)
36    }
37
38    /// Obtain the `bit_len`-long binary representation of variable `a`
39    /// Return a list of variables [b0, ..., b_`bit_len`] which is the binary
40    /// representation of `a`.
41    /// Return error if the `a` is not the range of [0, 2^`bit_len`).
42    pub fn unpack(&mut self, a: Variable, bit_len: usize) -> Result<Vec<BoolVar>, CircuitError> {
43        if bit_len < F::MODULUS_BIT_SIZE as usize
44            && self.witness(a)? >= F::from(2u32).pow([bit_len as u64])
45        {
46            return Err(CircuitError::ParameterError(
47                "Failed to unpack variable to a range of smaller than 2^bit_len".to_string(),
48            ));
49        }
50        self.range_gate_internal(a, bit_len)
51    }
52
53    /// a general decomposition gate (not necessarily binary decomposition)
54    /// where `a` are enforced to decomposed to `a_chunks_le` which consists
55    /// of chunks (multiple bits) in little-endian order and
56    /// each chunk \in [0, `range_size`)
57    pub(crate) fn decomposition_gate(
58        &mut self,
59        a_chunks_le: Vec<Variable>,
60        a: Variable,
61        range_size: F,
62    ) -> Result<(), CircuitError> {
63        // ensure (padded_len - 1) % 3 = 0
64        let mut padded = a_chunks_le;
65        let len = padded.len();
66        let rate = GATE_WIDTH - 1; // rate at which lc add each round
67        let padded_len = next_multiple(len - 1, rate)? + 1;
68        padded.resize(padded_len, self.zero());
69
70        let range_size_square = range_size.square();
71        let range_size_cube = range_size * range_size_square;
72        let coeffs = [range_size_cube, range_size_square, range_size, F::one()];
73        let mut accum = padded[padded_len - 1];
74        for i in 1..padded_len / rate {
75            accum = self.lc(
76                &[
77                    accum,
78                    padded[padded_len - 1 - rate * i + 2],
79                    padded[padded_len - 1 - rate * i + 1],
80                    padded[padded_len - 1 - rate * i],
81                ],
82                &coeffs,
83            )?;
84        }
85        // final round
86        let wires = [accum, padded[2], padded[1], padded[0], a];
87        self.lc_gate(&wires, &coeffs)?;
88
89        Ok(())
90    }
91}
92
93/// Private helper function for range gate
94impl<F: PrimeField> PlonkCircuit<F> {
95    // internal of a range check gate
96    pub(crate) fn range_gate_internal(
97        &mut self,
98        a: Variable,
99        bit_len: usize,
100    ) -> Result<Vec<BoolVar>, CircuitError> {
101        self.check_var_bound(a)?;
102        if bit_len == 0 {
103            return Err(CircuitError::ParameterError(
104                "Only allows positive bit length for range upper bound".to_string(),
105            ));
106        }
107
108        let a_bits_le: Vec<bool> = self.witness(a)?.into_bigint().to_bits_le();
109        if bit_len > a_bits_le.len() {
110            return Err(CircuitError::ParameterError(format!(
111                "Maximum field bit size: {}, requested range upper bound bit len: {}",
112                a_bits_le.len(),
113                bit_len
114            )));
115        }
116        // convert to variable in the circuit from the vector of boolean as binary
117        // representation
118        let a_bits_le: Vec<BoolVar> = a_bits_le
119            .iter()
120            .take(bit_len) // since little-endian, truncate would remove MSBs
121            .map(|&b| {
122                self.create_boolean_variable(b)
123            })
124            .collect::<Result<Vec<_>, CircuitError>>()?;
125
126        self.binary_decomposition_gate(a_bits_le.clone(), a)?;
127
128        Ok(a_bits_le)
129    }
130
131    fn binary_decomposition_gate(
132        &mut self,
133        a_bits_le: Vec<BoolVar>,
134        a: Variable,
135    ) -> Result<(), CircuitError> {
136        let a_chunks_le: Vec<Variable> = a_bits_le.into_iter().map(|b| b.into()).collect();
137        self.decomposition_gate(a_chunks_le, a, 2u8.into())?;
138        Ok(())
139    }
140}
141
142#[cfg(test)]
143mod test {
144    use crate::{
145        gadgets::test_utils::test_variable_independence_for_circuit, Circuit, CircuitError,
146        PlonkCircuit,
147    };
148    use ark_bls12_377::Fq as Fq377;
149    use ark_ed_on_bls12_377::Fq as FqEd377;
150    use ark_ed_on_bls12_381::Fq as FqEd381;
151    use ark_ed_on_bn254::Fq as FqEd254;
152    use ark_ff::PrimeField;
153
154    #[test]
155    fn test_unpack() -> Result<(), CircuitError> {
156        test_unpack_helper::<FqEd254>()?;
157        test_unpack_helper::<FqEd377>()?;
158        test_unpack_helper::<FqEd381>()?;
159        test_unpack_helper::<Fq377>()
160    }
161
162    fn test_unpack_helper<F: PrimeField>() -> Result<(), CircuitError> {
163        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
164        let a = circuit.create_variable(F::one())?;
165        let b = circuit.create_variable(F::from(1023u32))?;
166
167        circuit.enforce_in_range(a, 1)?;
168        let a_le = circuit.unpack(a, 3)?;
169        assert_eq!(a_le.len(), 3);
170        let b_le = circuit.unpack(b, 10)?;
171        assert_eq!(b_le.len(), 10);
172        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
173        assert!(circuit.unpack(b, 9).is_err());
174        Ok(())
175    }
176
177    #[test]
178    fn test_range_gate() -> Result<(), CircuitError> {
179        test_range_gate_helper::<FqEd254>()?;
180        test_range_gate_helper::<FqEd377>()?;
181        test_range_gate_helper::<FqEd381>()?;
182        test_range_gate_helper::<Fq377>()
183    }
184    fn test_range_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
185        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
186        let a = circuit.create_variable(F::one())?;
187        let b = circuit.create_variable(F::from(1023u32))?;
188
189        circuit.enforce_in_range(a, 1)?;
190        circuit.enforce_in_range(a, 3)?;
191        circuit.enforce_in_range(b, 10)?;
192        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
193        circuit.enforce_in_range(b, 9)?;
194        assert!(circuit.enforce_in_range(a, 0).is_err());
195        // non-positive bit length is undefined, thus fail
196        assert!(circuit.enforce_in_range(a, 0).is_err());
197        // bit length bigger than that of a field element (bit length takes 256 or 381
198        // bits)
199        let bit_len = (F::MODULUS_BIT_SIZE as usize / 8 + 1) * 8;
200        assert!(circuit.enforce_in_range(a, bit_len + 1).is_err());
201        // if mess up the wire value, should fail
202        *circuit.witness_mut(b) = F::from(1024u32);
203        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
204        // Check variable out of bound error.
205        assert!(circuit.enforce_in_range(circuit.num_vars(), 10).is_err());
206
207        // build two fixed circuits with different variable assignments, checking that
208        // the arithmetized extended permutation polynomial is variable
209        // independent
210        let circuit_1 = build_range_gate_circuit(F::from(314u32))?;
211        let circuit_2 = build_range_gate_circuit(F::from(489u32))?;
212        test_variable_independence_for_circuit(circuit_1, circuit_2)?;
213
214        Ok(())
215    }
216
217    fn build_range_gate_circuit<F: PrimeField>(a: F) -> Result<PlonkCircuit<F>, CircuitError> {
218        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
219        let a_var = circuit.create_variable(a)?;
220        circuit.enforce_in_range(a_var, 10)?;
221        circuit.finalize_for_arithmetization()?;
222        Ok(circuit)
223    }
224
225    #[test]
226    fn test_check_in_range() -> Result<(), CircuitError> {
227        test_check_in_range_helper::<FqEd254>()?;
228        test_check_in_range_helper::<FqEd377>()?;
229        test_check_in_range_helper::<FqEd381>()?;
230        test_check_in_range_helper::<Fq377>()
231    }
232    fn test_check_in_range_helper<F: PrimeField>() -> Result<(), CircuitError> {
233        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
234        let a = circuit.create_variable(F::from(1023u32))?;
235
236        let b1 = circuit.is_in_range(a, 5)?;
237        let b2 = circuit.is_in_range(a, 10)?;
238        let b3 = circuit.is_in_range(a, 0)?;
239        assert_eq!(circuit.witness(b1.into())?, F::zero());
240        assert_eq!(circuit.witness(b2.into())?, F::one());
241        assert_eq!(circuit.witness(b3.into())?, F::zero());
242        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
243
244        // if mess up the wire value, should fail
245        *circuit.witness_mut(a) = F::from(1024u32);
246        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
247        // Check variable out of bound error.
248        assert!(circuit.is_in_range(circuit.num_vars(), 10).is_err());
249
250        // build two fixed circuits with different variable assignments, checking that
251        // the arithmetized extended permutation polynomial is variable
252        // independent
253        let circuit_1 = build_check_in_range_circuit(F::from(314u32))?;
254        let circuit_2 = build_check_in_range_circuit(F::from(1489u32))?;
255        test_variable_independence_for_circuit(circuit_1, circuit_2)?;
256
257        Ok(())
258    }
259
260    fn build_check_in_range_circuit<F: PrimeField>(a: F) -> Result<PlonkCircuit<F>, CircuitError> {
261        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
262        let a_var = circuit.create_variable(a)?;
263        circuit.is_in_range(a_var, 10)?;
264        circuit.finalize_for_arithmetization()?;
265        Ok(circuit)
266    }
267}
jf_relation/gadgets/range.rs

jf_relation/gadgets/
range.rs
