darkfi/zk/gadget/
small_range_check.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2026 Dyne.org foundation
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU Affero General Public License as
7 * published by the Free Software Foundation, either version 3 of the
8 * License, or (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 * GNU Affero General Public License for more details.
14 *
15 * You should have received a copy of the GNU Affero General Public License
16 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18
19use std::marker::PhantomData;
20
21use halo2_proofs::{
22    circuit::{AssignedCell, Chip, Layouter},
23    pasta::group::ff::WithSmallOrderMulGroup,
24    plonk,
25    plonk::{Advice, Column, ConstraintSystem, Constraints, Expression, Selector},
26    poly::Rotation,
27};
28
29/// Checks that an expression is in the small range [0..range),
30/// i.e. 0 ≤ word < range.
31pub fn range_check<F: WithSmallOrderMulGroup<3> + Ord>(
32    word: Expression<F>,
33    range: u8,
34) -> Expression<F> {
35    assert!(range > 0);
36
37    (1..(range as usize))
38        .fold(word.clone(), |acc, i| acc * (Expression::Constant(F::from(i as u64)) - word.clone()))
39}
40
41#[derive(Clone, Debug)]
42pub struct SmallRangeCheckConfig {
43    pub z: Column<Advice>,
44    pub selector: Selector,
45}
46
47#[derive(Clone, Debug)]
48pub struct SmallRangeCheckChip<F> {
49    config: SmallRangeCheckConfig,
50    _marker: PhantomData<F>,
51}
52
53impl<F: WithSmallOrderMulGroup<3> + Ord> Chip<F> for SmallRangeCheckChip<F> {
54    type Config = SmallRangeCheckConfig;
55    type Loaded = ();
56
57    fn config(&self) -> &Self::Config {
58        &self.config
59    }
60
61    fn loaded(&self) -> &Self::Loaded {
62        &()
63    }
64}
65
66impl<F: WithSmallOrderMulGroup<3> + Ord> SmallRangeCheckChip<F> {
67    pub fn construct(config: SmallRangeCheckConfig) -> Self {
68        Self { config, _marker: PhantomData }
69    }
70
71    pub fn configure(
72        meta: &mut ConstraintSystem<F>,
73        z: Column<Advice>,
74        range: u8,
75    ) -> SmallRangeCheckConfig {
76        // Enable permutation on z column
77        meta.enable_equality(z);
78
79        let selector = meta.selector();
80
81        meta.create_gate("bool check", |meta| {
82            let selector = meta.query_selector(selector);
83            let advice = meta.query_advice(z, Rotation::cur());
84            Constraints::with_selector(selector, Some(range_check(advice, range)))
85        });
86
87        SmallRangeCheckConfig { z, selector }
88    }
89
90    pub fn small_range_check(
91        &self,
92        mut layouter: impl Layouter<F>,
93        value: AssignedCell<F, F>,
94    ) -> Result<(), plonk::Error> {
95        layouter.assign_region(
96            || "small range constrain",
97            |mut region| {
98                self.config.selector.enable(&mut region, 0)?;
99                value.copy_advice(|| "z_0", &mut region, self.config.z, 0)?;
100                Ok(())
101            },
102        )
103    }
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109    use crate::zk::assign_free_advice;
110    use halo2_proofs::{
111        circuit::{floor_planner, Value},
112        dev::MockProver,
113        pasta::pallas,
114        plonk::Circuit,
115    };
116
117    #[derive(Default)]
118    struct SmallRangeCircuit {
119        value: Value<pallas::Base>,
120    }
121
122    impl Circuit<pallas::Base> for SmallRangeCircuit {
123        type Config = (SmallRangeCheckConfig, Column<Advice>);
124        type FloorPlanner = floor_planner::V1;
125        type Params = ();
126
127        fn without_witnesses(&self) -> Self {
128            Self::default()
129        }
130
131        fn configure(meta: &mut ConstraintSystem<pallas::Base>) -> Self::Config {
132            let w = meta.advice_column();
133            let z = meta.advice_column();
134
135            meta.enable_equality(w);
136
137            // One bit
138            let config = SmallRangeCheckChip::configure(meta, z, 2);
139
140            (config, w)
141        }
142
143        fn synthesize(
144            &self,
145            config: Self::Config,
146            mut layouter: impl Layouter<pallas::Base>,
147        ) -> Result<(), plonk::Error> {
148            let chip = SmallRangeCheckChip::construct(config.0.clone());
149            let value = assign_free_advice(layouter.namespace(|| "val"), config.1, self.value)?;
150            chip.small_range_check(layouter.namespace(|| "boolean check"), value)?;
151            Ok(())
152        }
153    }
154
155    #[test]
156    fn boolean_range_check() {
157        let k = 3;
158
159        for i in 0..2 {
160            let circuit = SmallRangeCircuit { value: Value::known(pallas::Base::from(i as u64)) };
161            let prover = MockProver::run(k, &circuit, vec![]).unwrap();
162            prover.assert_satisfied();
163        }
164
165        let circuit = SmallRangeCircuit { value: Value::known(pallas::Base::from(2)) };
166        let prover = MockProver::run(k, &circuit, vec![]).unwrap();
167        assert!(prover.verify().is_err());
168    }
169}
darkfi/zk/gadget/small_range_check.rs

darkfi/zk/gadget/
small_range_check.rs
