jf_relation/gadgets/ultraplonk/
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//! Range proof gates.
8use crate::{
9    Circuit,
10    CircuitError::{self, ParameterError},
11    PlonkCircuit, Variable,
12};
13use ark_ff::{BigInteger, PrimeField};
14use ark_std::{string::ToString, vec::Vec};
15
16impl<F: PrimeField> PlonkCircuit<F> {
17    /// Constrain a variable to be within the [0, 2^{bit_len}) range
18    /// Return error if one of the following holds:
19    /// 1. the variable is invalid;
20    /// 2. `RANGE_BIT_LEN` equals zero;
21    /// 3. the circuit does not support lookup.
22    pub(crate) fn range_gate_with_lookup(
23        &mut self,
24        a: Variable,
25        bit_len: usize,
26    ) -> Result<(), CircuitError> {
27        let range_bit_len = self.range_bit_len()?;
28        let range_size = self.range_size()?;
29        if bit_len == 0 {
30            return Err(ParameterError("bit_len cannot be zero".to_string()));
31        }
32        self.check_var_bound(a)?;
33        let leftover = bit_len % range_bit_len;
34        let lookup_len = bit_len / range_bit_len;
35        let len = lookup_len + if leftover > 0 { 1 } else { 0 };
36        let reprs_le = decompose_le(self.witness(a)?, len, range_bit_len);
37        let reprs_le_vars: Vec<Variable> = reprs_le
38            .iter()
39            .map(|&val| self.create_variable(val))
40            .collect::<Result<Vec<_>, CircuitError>>()?;
41
42        // add range gates for decomposed variables
43        for &var in reprs_le_vars[..lookup_len].iter() {
44            self.add_range_check_variable(var)?;
45        }
46
47        if leftover > 0 {
48            self.range_gate_internal(reprs_le_vars[lookup_len], leftover)?;
49        }
50
51        // add linear combination gates
52        self.decomposition_gate(reprs_le_vars, a, F::from(range_size as u64))?;
53
54        Ok(())
55    }
56
57    /// The number of range blocks, i.e., the minimal integer such that
58    /// RANGE_SIZE^NUM_RANGES >= p,
59    #[inline]
60    pub fn num_range_blocks(&self) -> Result<usize, CircuitError> {
61        Ok(F::MODULUS_BIT_SIZE as usize / self.range_bit_len()? + 1)
62    }
63}
64
65/// Decompose `val` into `a_0`, ..., `a_{len-1}` s.t.
66/// val = a_0 + RANGE_SIZE * a_1 + ... + RANGE_SIZE^{len-1} * a_{len-1}
67fn decompose_le<F: PrimeField>(val: F, len: usize, range_bit_len: usize) -> Vec<F> {
68    let repr_le = val.into_bigint().to_bits_le();
69    let mut res: Vec<F> = repr_le
70        .chunks(range_bit_len)
71        .map(|vec| {
72            let mut elem = 0;
73            for &b in vec.iter().rev() {
74                if !b {
75                    elem <<= 1;
76                } else {
77                    elem = (elem << 1) + 1;
78                }
79            }
80            F::from(elem as u64)
81        })
82        .collect();
83    res.resize(len, F::zero());
84
85    res
86}
87
88#[cfg(test)]
89mod test {
90    use super::*;
91    use ark_bls12_377::Fq as Fq377;
92    use ark_ed_on_bls12_377::Fq as FqEd377;
93    use ark_ed_on_bls12_381::Fq as FqEd381;
94    use ark_ed_on_bn254::Fq as FqEd254;
95    use ark_std::rand::Rng;
96    use jf_utils::test_rng;
97
98    const RANGE_BIT_LEN_FOR_TEST: usize = 8;
99    const RANGE_SIZE_FOR_TEST: usize = 256;
100
101    #[test]
102    fn test_decompose_le() {
103        test_decompose_le_helper::<FqEd254>();
104        test_decompose_le_helper::<FqEd377>();
105        test_decompose_le_helper::<FqEd381>();
106        test_decompose_le_helper::<Fq377>();
107    }
108    fn test_decompose_le_helper<F: PrimeField>() {
109        let len = F::MODULUS_BIT_SIZE as usize / RANGE_BIT_LEN_FOR_TEST + 1;
110        let mut rng = test_rng();
111        for _ in 0..10 {
112            let val = F::rand(&mut rng);
113            let repr_le = decompose_le(val, len, RANGE_BIT_LEN_FOR_TEST);
114            assert_eq!(repr_le.len(), len);
115            check_decomposition(repr_le, val);
116        }
117    }
118    // check that val = a_0 + RANGE_SIZE * a_1 + ... + RANGE_SIZE^{len-1} *
119    // a_{len-1}
120    fn check_decomposition<F: PrimeField>(a: Vec<F>, val: F) {
121        let (expected_val, _) = a.iter().fold((F::zero(), F::one()), |(acc, base), &x| {
122            (acc + base * x, base * F::from(RANGE_SIZE_FOR_TEST as u64))
123        });
124        assert_eq!(expected_val, val);
125    }
126
127    #[test]
128    fn test_range_gate_with_lookup() -> Result<(), CircuitError> {
129        (2 * RANGE_BIT_LEN_FOR_TEST..3 * RANGE_BIT_LEN_FOR_TEST)
130            .map(|bitlen| -> Result<(), CircuitError> {
131                test_range_gate_with_lookup_helper::<FqEd254>(bitlen)?;
132                test_range_gate_with_lookup_helper::<FqEd377>(bitlen)?;
133                test_range_gate_with_lookup_helper::<FqEd381>(bitlen)?;
134                test_range_gate_with_lookup_helper::<Fq377>(bitlen)
135            })
136            .collect::<Result<Vec<_>, CircuitError>>()?;
137        Ok(())
138    }
139    fn test_range_gate_with_lookup_helper<F: PrimeField>(
140        bit_len: usize,
141    ) -> Result<(), CircuitError> {
142        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
143        let mut rng = test_rng();
144
145        // Good path
146        let a = (0..10)
147            .map(|_| circuit.create_variable(F::from(rng.gen_range(0..u32::MAX))))
148            .collect::<Result<Vec<_>, CircuitError>>()?;
149        for &var in a.iter() {
150            circuit.range_gate_with_lookup(var, 32)?;
151        }
152        circuit.range_gate_with_lookup(circuit.zero(), bit_len)?;
153        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
154
155        // Error paths
156        //
157        // if mess up the witness value, should fail
158        let tmp = circuit.witness(a[0])?;
159        *circuit.witness_mut(a[0]) = F::from(u32::MAX as u64 + 1);
160        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
161        *circuit.witness_mut(a[0]) = tmp;
162
163        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_ultra_plonk(RANGE_BIT_LEN_FOR_TEST);
164        // Should fail when the value = 2^bit_len
165        let a_var = circuit.create_variable(F::from(1u64 << bit_len))?;
166        circuit.range_gate_with_lookup(a_var, bit_len)?;
167        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
168
169        // Should fail when the value = 2^{2*bit_len}
170        let a_var = circuit.create_variable(F::from(1u64 << (2 * bit_len)))?;
171        circuit.range_gate_with_lookup(a_var, 2 * bit_len)?;
172        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
173
174        let zero_var = circuit.zero();
175        // bit_len = 0
176        assert!(circuit.range_gate_with_lookup(zero_var, 0).is_err());
177        // Check variable out of bound error.
178        assert!(circuit
179            .range_gate_with_lookup(circuit.num_vars(), bit_len)
180            .is_err());
181        // TurboPlonk shouldn't be able to use the gate
182        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
183        assert!(circuit.range_gate_with_lookup(0, bit_len).is_err());
184
185        Ok(())
186    }
187}
jf_relation/gadgets/ultraplonk/range.rs

jf_relation/gadgets/ultraplonk/
range.rs
