jf_relation/gadgets/
range.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
// Copyright (c) 2022 Espresso Systems (espressosys.com)
// This file is part of the Jellyfish library.

// You should have received a copy of the MIT License
// along with the Jellyfish library. If not, see <https://mit-license.org/>.

//! Implementation of circuit lookup related gadgets

use super::utils::next_multiple;
use crate::{constants::GATE_WIDTH, BoolVar, Circuit, CircuitError, PlonkCircuit, Variable};
use ark_ff::{BigInteger, PrimeField};
use ark_std::{format, string::ToString, vec::Vec};

impl<F: PrimeField> PlonkCircuit<F> {
    /// Constrain a variable to be within the [0, 2^`bit_len`) range
    /// Return error if the variable is invalid.
    pub fn enforce_in_range(&mut self, a: Variable, bit_len: usize) -> Result<(), CircuitError> {
        if self.support_lookup() {
            self.range_gate_with_lookup(a, bit_len)?;
        } else {
            self.range_gate_internal(a, bit_len)?;
        }
        Ok(())
    }

    /// Return a boolean variable indicating whether variable `a` is in the
    /// range [0, 2^`bit_len`). Return error if the variable is invalid.
    /// TODO: optimize the gate for UltraPlonk.
    pub fn is_in_range(&mut self, a: Variable, bit_len: usize) -> Result<BoolVar, CircuitError> {
        let a_bit_le: Vec<BoolVar> = self.unpack(a, F::MODULUS_BIT_SIZE as usize)?;
        let a_bit_le: Vec<Variable> = a_bit_le.into_iter().map(|b| b.into()).collect();
        // a is in range if and only if the bits in `a_bit_le[bit_len..]` are all
        // zeroes.
        let higher_bit_sum = self.sum(&a_bit_le[bit_len..])?;
        self.is_zero(higher_bit_sum)
    }

    /// Obtain the `bit_len`-long binary representation of variable `a`
    /// Return a list of variables [b0, ..., b_`bit_len`] which is the binary
    /// representation of `a`.
    /// Return error if the `a` is not the range of [0, 2^`bit_len`).
    pub fn unpack(&mut self, a: Variable, bit_len: usize) -> Result<Vec<BoolVar>, CircuitError> {
        if bit_len < F::MODULUS_BIT_SIZE as usize
            && self.witness(a)? >= F::from(2u32).pow([bit_len as u64])
        {
            return Err(CircuitError::ParameterError(
                "Failed to unpack variable to a range of smaller than 2^bit_len".to_string(),
            ));
        }
        self.range_gate_internal(a, bit_len)
    }

    /// a general decomposition gate (not necessarily binary decomposition)
    /// where `a` are enforced to decomposed to `a_chunks_le` which consists
    /// of chunks (multiple bits) in little-endian order and
    /// each chunk \in [0, `range_size`)
    pub(crate) fn decomposition_gate(
        &mut self,
        a_chunks_le: Vec<Variable>,
        a: Variable,
        range_size: F,
    ) -> Result<(), CircuitError> {
        // ensure (padded_len - 1) % 3 = 0
        let mut padded = a_chunks_le;
        let len = padded.len();
        let rate = GATE_WIDTH - 1; // rate at which lc add each round
        let padded_len = next_multiple(len - 1, rate)? + 1;
        padded.resize(padded_len, self.zero());

        let range_size_square = range_size.square();
        let range_size_cube = range_size * range_size_square;
        let coeffs = [range_size_cube, range_size_square, range_size, F::one()];
        let mut accum = padded[padded_len - 1];
        for i in 1..padded_len / rate {
            accum = self.lc(
                &[
                    accum,
                    padded[padded_len - 1 - rate * i + 2],
                    padded[padded_len - 1 - rate * i + 1],
                    padded[padded_len - 1 - rate * i],
                ],
                &coeffs,
            )?;
        }
        // final round
        let wires = [accum, padded[2], padded[1], padded[0], a];
        self.lc_gate(&wires, &coeffs)?;

        Ok(())
    }
}

/// Private helper function for range gate
impl<F: PrimeField> PlonkCircuit<F> {
    // internal of a range check gate
    pub(crate) fn range_gate_internal(
        &mut self,
        a: Variable,
        bit_len: usize,
    ) -> Result<Vec<BoolVar>, CircuitError> {
        self.check_var_bound(a)?;
        if bit_len == 0 {
            return Err(CircuitError::ParameterError(
                "Only allows positive bit length for range upper bound".to_string(),
            ));
        }

        let a_bits_le: Vec<bool> = self.witness(a)?.into_bigint().to_bits_le();
        if bit_len > a_bits_le.len() {
            return Err(CircuitError::ParameterError(format!(
                "Maximum field bit size: {}, requested range upper bound bit len: {}",
                a_bits_le.len(),
                bit_len
            )));
        }
        // convert to variable in the circuit from the vector of boolean as binary
        // representation
        let a_bits_le: Vec<BoolVar> = a_bits_le
            .iter()
            .take(bit_len) // since little-endian, truncate would remove MSBs
            .map(|&b| {
                self.create_boolean_variable(b)
            })
            .collect::<Result<Vec<_>, CircuitError>>()?;

        self.binary_decomposition_gate(a_bits_le.clone(), a)?;

        Ok(a_bits_le)
    }

    fn binary_decomposition_gate(
        &mut self,
        a_bits_le: Vec<BoolVar>,
        a: Variable,
    ) -> Result<(), CircuitError> {
        let a_chunks_le: Vec<Variable> = a_bits_le.into_iter().map(|b| b.into()).collect();
        self.decomposition_gate(a_chunks_le, a, 2u8.into())?;
        Ok(())
    }
}

#[cfg(test)]
mod test {
    use crate::{
        gadgets::test_utils::test_variable_independence_for_circuit, Circuit, CircuitError,
        PlonkCircuit,
    };
    use ark_bls12_377::Fq as Fq377;
    use ark_ed_on_bls12_377::Fq as FqEd377;
    use ark_ed_on_bls12_381::Fq as FqEd381;
    use ark_ed_on_bn254::Fq as FqEd254;
    use ark_ff::PrimeField;

    #[test]
    fn test_unpack() -> Result<(), CircuitError> {
        test_unpack_helper::<FqEd254>()?;
        test_unpack_helper::<FqEd377>()?;
        test_unpack_helper::<FqEd381>()?;
        test_unpack_helper::<Fq377>()
    }

    fn test_unpack_helper<F: PrimeField>() -> Result<(), CircuitError> {
        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
        let a = circuit.create_variable(F::one())?;
        let b = circuit.create_variable(F::from(1023u32))?;

        circuit.enforce_in_range(a, 1)?;
        let a_le = circuit.unpack(a, 3)?;
        assert_eq!(a_le.len(), 3);
        let b_le = circuit.unpack(b, 10)?;
        assert_eq!(b_le.len(), 10);
        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
        assert!(circuit.unpack(b, 9).is_err());
        Ok(())
    }

    #[test]
    fn test_range_gate() -> Result<(), CircuitError> {
        test_range_gate_helper::<FqEd254>()?;
        test_range_gate_helper::<FqEd377>()?;
        test_range_gate_helper::<FqEd381>()?;
        test_range_gate_helper::<Fq377>()
    }
    fn test_range_gate_helper<F: PrimeField>() -> Result<(), CircuitError> {
        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
        let a = circuit.create_variable(F::one())?;
        let b = circuit.create_variable(F::from(1023u32))?;

        circuit.enforce_in_range(a, 1)?;
        circuit.enforce_in_range(a, 3)?;
        circuit.enforce_in_range(b, 10)?;
        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());
        circuit.enforce_in_range(b, 9)?;
        assert!(circuit.enforce_in_range(a, 0).is_err());
        // non-positive bit length is undefined, thus fail
        assert!(circuit.enforce_in_range(a, 0).is_err());
        // bit length bigger than that of a field element (bit length takes 256 or 381
        // bits)
        let bit_len = (F::MODULUS_BIT_SIZE as usize / 8 + 1) * 8;
        assert!(circuit.enforce_in_range(a, bit_len + 1).is_err());
        // if mess up the wire value, should fail
        *circuit.witness_mut(b) = F::from(1024u32);
        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
        // Check variable out of bound error.
        assert!(circuit.enforce_in_range(circuit.num_vars(), 10).is_err());

        // build two fixed circuits with different variable assignments, checking that
        // the arithmetized extended permutation polynomial is variable
        // independent
        let circuit_1 = build_range_gate_circuit(F::from(314u32))?;
        let circuit_2 = build_range_gate_circuit(F::from(489u32))?;
        test_variable_independence_for_circuit(circuit_1, circuit_2)?;

        Ok(())
    }

    fn build_range_gate_circuit<F: PrimeField>(a: F) -> Result<PlonkCircuit<F>, CircuitError> {
        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
        let a_var = circuit.create_variable(a)?;
        circuit.enforce_in_range(a_var, 10)?;
        circuit.finalize_for_arithmetization()?;
        Ok(circuit)
    }

    #[test]
    fn test_check_in_range() -> Result<(), CircuitError> {
        test_check_in_range_helper::<FqEd254>()?;
        test_check_in_range_helper::<FqEd377>()?;
        test_check_in_range_helper::<FqEd381>()?;
        test_check_in_range_helper::<Fq377>()
    }
    fn test_check_in_range_helper<F: PrimeField>() -> Result<(), CircuitError> {
        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
        let a = circuit.create_variable(F::from(1023u32))?;

        let b1 = circuit.is_in_range(a, 5)?;
        let b2 = circuit.is_in_range(a, 10)?;
        let b3 = circuit.is_in_range(a, 0)?;
        assert_eq!(circuit.witness(b1.into())?, F::zero());
        assert_eq!(circuit.witness(b2.into())?, F::one());
        assert_eq!(circuit.witness(b3.into())?, F::zero());
        assert!(circuit.check_circuit_satisfiability(&[]).is_ok());

        // if mess up the wire value, should fail
        *circuit.witness_mut(a) = F::from(1024u32);
        assert!(circuit.check_circuit_satisfiability(&[]).is_err());
        // Check variable out of bound error.
        assert!(circuit.is_in_range(circuit.num_vars(), 10).is_err());

        // build two fixed circuits with different variable assignments, checking that
        // the arithmetized extended permutation polynomial is variable
        // independent
        let circuit_1 = build_check_in_range_circuit(F::from(314u32))?;
        let circuit_2 = build_check_in_range_circuit(F::from(1489u32))?;
        test_variable_independence_for_circuit(circuit_1, circuit_2)?;

        Ok(())
    }

    fn build_check_in_range_circuit<F: PrimeField>(a: F) -> Result<PlonkCircuit<F>, CircuitError> {
        let mut circuit: PlonkCircuit<F> = PlonkCircuit::new_turbo_plonk();
        let a_var = circuit.create_variable(a)?;
        circuit.is_in_range(a_var, 10)?;
        circuit.finalize_for_arithmetization()?;
        Ok(circuit)
    }
}