darkfi/zk/gadget/
is_equal.rs

1/* This file is part of DarkFi (https://dark.fi)
2 *
3 * Copyright (C) 2020-2025 Dyne.org foundation
4 * Copyright (C) 2022 zkMove Authors (Apache-2.0)
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU Affero General Public License as
8 * published by the Free Software Foundation, either version 3 of the
9 * License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU Affero General Public License for more details.
15 *
16 * You should have received a copy of the GNU Affero General Public License
17 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
18 */
19
20use std::marker::PhantomData;
21
22use halo2_proofs::{
23    circuit::{AssignedCell, Chip, Layouter, Region},
24    pasta::group::ff::WithSmallOrderMulGroup,
25    plonk::{self, Advice, Column, ConstraintSystem, Expression, Selector},
26    poly::Rotation,
27};
28
29const NUM_OF_UTILITY_ADVICE_COLUMNS: usize = 4;
30
31#[derive(Clone, Debug)]
32pub struct IsEqualConfig<F: WithSmallOrderMulGroup<3> + Ord> {
33    s_is_eq: Selector,
34    advices: [Column<Advice>; NUM_OF_UTILITY_ADVICE_COLUMNS],
35    _marker: PhantomData<F>,
36}
37
38pub struct IsEqualChip<F: WithSmallOrderMulGroup<3> + Ord> {
39    config: IsEqualConfig<F>,
40}
41
42impl<F: WithSmallOrderMulGroup<3> + Ord> Chip<F> for IsEqualChip<F> {
43    type Config = IsEqualConfig<F>;
44    type Loaded = ();
45
46    fn config(&self) -> &Self::Config {
47        &self.config
48    }
49
50    fn loaded(&self) -> &Self::Loaded {
51        &()
52    }
53}
54
55impl<F: WithSmallOrderMulGroup<3> + Ord> IsEqualChip<F> {
56    pub fn construct(config: <Self as Chip<F>>::Config) -> Self {
57        Self { config }
58    }
59
60    pub fn configure(
61        meta: &mut ConstraintSystem<F>,
62        advices: [Column<Advice>; NUM_OF_UTILITY_ADVICE_COLUMNS],
63    ) -> <Self as Chip<F>>::Config {
64        let s_is_eq = meta.selector();
65        meta.create_gate("is_eq", |meta| {
66            let lhs = meta.query_advice(advices[0], Rotation::cur());
67            let rhs = meta.query_advice(advices[1], Rotation::cur());
68            let out = meta.query_advice(advices[2], Rotation::cur());
69            let delta_invert = meta.query_advice(advices[3], Rotation::cur());
70            let s_is_eq = meta.query_selector(s_is_eq);
71            let one = Expression::Constant(F::ONE);
72
73            vec![
74                // out is 0 or 1
75                s_is_eq.clone() * (out.clone() * (one.clone() - out.clone())),
76                // if a != b then (a - b) * inverse(a - b) == 1 - out
77                // if a == b then (a - b) * 1 == 1 - out
78                s_is_eq.clone() *
79                    ((lhs.clone() - rhs.clone()) * delta_invert.clone() + (out - one.clone())),
80                // constrain delta_invert: (a - b) * inverse(a - b) must be 1 or 0
81                s_is_eq * (lhs.clone() - rhs.clone()) * ((lhs - rhs) * delta_invert - one),
82            ]
83        });
84
85        IsEqualConfig { s_is_eq, advices, _marker: PhantomData }
86    }
87
88    pub fn is_eq_with_output(
89        &self,
90        layouter: &mut impl Layouter<F>,
91        a: AssignedCell<F, F>,
92        b: AssignedCell<F, F>,
93    ) -> Result<AssignedCell<F, F>, plonk::Error> {
94        let config = self.config();
95
96        let out = layouter.assign_region(
97            || "is_eq",
98            |mut region: Region<'_, F>| {
99                config.s_is_eq.enable(&mut region, 0)?;
100
101                a.copy_advice(|| "copy a", &mut region, config.advices[0], 0)?;
102                b.copy_advice(|| "copy b", &mut region, config.advices[1], 0)?;
103
104                let delta_invert = a.value().copied().to_field().zip(b.value()).map(|(a, b)| {
105                    if a == b.into() {
106                        F::ONE.into()
107                    } else {
108                        let delta = a - *b;
109                        delta.invert()
110                    }
111                });
112
113                region.assign_advice(|| "delta invert", config.advices[3], 0, || delta_invert)?;
114
115                let is_eq =
116                    a.value_field().evaluate().zip(b.value_field().evaluate()).map(|(lhs, rhs)| {
117                        if lhs == rhs {
118                            F::ONE
119                        } else {
120                            F::ZERO
121                        }
122                    });
123
124                let cell = region.assign_advice(|| "is_eq", config.advices[2], 0, || is_eq)?;
125                Ok(cell)
126            },
127        )?;
128
129        Ok(out)
130    }
131}
132
133#[derive(Clone, Debug)]
134pub struct AssertEqualConfig<F: WithSmallOrderMulGroup<3> + Ord> {
135    s_eq: Selector,
136    advices: [Column<Advice>; 2],
137    _marker: PhantomData<F>,
138}
139
140pub struct AssertEqualChip<F: WithSmallOrderMulGroup<3> + Ord> {
141    config: AssertEqualConfig<F>,
142}
143
144impl<F: WithSmallOrderMulGroup<3> + Ord> Chip<F> for AssertEqualChip<F> {
145    type Config = AssertEqualConfig<F>;
146    type Loaded = ();
147
148    fn config(&self) -> &Self::Config {
149        &self.config
150    }
151
152    fn loaded(&self) -> &Self::Loaded {
153        &()
154    }
155}
156
157impl<F: WithSmallOrderMulGroup<3> + Ord> AssertEqualChip<F> {
158    pub fn construct(config: <Self as Chip<F>>::Config) -> Self {
159        Self { config }
160    }
161
162    pub fn configure(
163        meta: &mut ConstraintSystem<F>,
164        advices: [Column<Advice>; 2],
165    ) -> <Self as Chip<F>>::Config {
166        let s_eq = meta.selector();
167        meta.create_gate("assert_eq", |meta| {
168            let lhs = meta.query_advice(advices[0], Rotation::cur());
169            let rhs = meta.query_advice(advices[1], Rotation::cur());
170            let s_eq = meta.query_selector(s_eq);
171
172            vec![s_eq * (lhs - rhs)]
173        });
174
175        AssertEqualConfig { s_eq, advices, _marker: PhantomData }
176    }
177
178    pub fn assert_equal(
179        &self,
180        layouter: &mut impl Layouter<F>,
181        a: AssignedCell<F, F>,
182        b: AssignedCell<F, F>,
183    ) -> Result<(), plonk::Error> {
184        let config = self.config();
185
186        layouter.assign_region(
187            || "assert_eq",
188            |mut region: Region<'_, F>| {
189                config.s_eq.enable(&mut region, 0)?;
190
191                a.copy_advice(|| "copy a", &mut region, config.advices[0], 0)?;
192                b.copy_advice(|| "copy b", &mut region, config.advices[1], 0)?;
193                Ok(())
194            },
195        )?;
196
197        Ok(())
198    }
199}
darkfi/zk/gadget/is_equal.rs

darkfi/zk/gadget/
is_equal.rs
