ark-r1cs-std/src/eq.rs
src/eq.rsRaw
1use crate::{prelude::*, Vec};
2use ark_ff::{Field, PrimeField};
3use ark_relations::r1cs::SynthesisError;
4
5/// Specifies how to generate constraints that check for equality for two
6/// variables of type `Self`.
7pub trait EqGadget<F: Field> {
8 /// Output a `Boolean` value representing whether `self.value() ==
9 /// other.value()`.
10 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError>;
11
12 /// Output a `Boolean` value representing whether `self.value() !=
13 /// other.value()`.
14 ///
15 /// By default, this is defined as `self.is_eq(other)?.not()`.
16 fn is_neq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
17 Ok(!self.is_eq(other)?)
18 }
19
20 /// If `should_enforce == true`, enforce that `self` and `other` are equal;
21 /// else, enforce a vacuously true statement.
22 ///
23 /// A safe default implementation is provided that generates the following
24 /// constraints: `self.is_eq(other)?.conditional_enforce_equal(&Boolean:
25 /// :TRUE, should_enforce)`.
26 ///
27 /// More efficient specialized implementation may be possible; implementors
28 /// are encouraged to carefully analyze the efficiency and safety of these.
29 #[tracing::instrument(target = "r1cs", skip(self, other))]
30 fn conditional_enforce_equal(
31 &self,
32 other: &Self,
33 should_enforce: &Boolean<F>,
34 ) -> Result<(), SynthesisError> {
35 self.is_eq(&other)?
36 .conditional_enforce_equal(&Boolean::TRUE, should_enforce)
37 }
38
39 /// Enforce that `self` and `other` are equal.
40 ///
41 /// A safe default implementation is provided that generates the following
42 /// constraints: `self.conditional_enforce_equal(other,
43 /// &Boolean::TRUE)`.
44 ///
45 /// More efficient specialized implementation may be possible; implementors
46 /// are encouraged to carefully analyze the efficiency and safety of these.
47 #[tracing::instrument(target = "r1cs", skip(self, other))]
48 fn enforce_equal(&self, other: &Self) -> Result<(), SynthesisError> {
49 self.conditional_enforce_equal(other, &Boolean::TRUE)
50 }
51
52 /// If `should_enforce == true`, enforce that `self` and `other` are *not*
53 /// equal; else, enforce a vacuously true statement.
54 ///
55 /// A safe default implementation is provided that generates the following
56 /// constraints: `self.is_neq(other)?.conditional_enforce_equal(&
57 /// Boolean::TRUE, should_enforce)`.
58 ///
59 /// More efficient specialized implementation may be possible; implementors
60 /// are encouraged to carefully analyze the efficiency and safety of these.
61 #[tracing::instrument(target = "r1cs", skip(self, other))]
62 fn conditional_enforce_not_equal(
63 &self,
64 other: &Self,
65 should_enforce: &Boolean<F>,
66 ) -> Result<(), SynthesisError> {
67 self.is_neq(&other)?
68 .conditional_enforce_equal(&Boolean::TRUE, should_enforce)
69 }
70
71 /// Enforce that `self` and `other` are *not* equal.
72 ///
73 /// A safe default implementation is provided that generates the following
74 /// constraints: `self.conditional_enforce_not_equal(other,
75 /// &Boolean::TRUE)`.
76 ///
77 /// More efficient specialized implementation may be possible; implementors
78 /// are encouraged to carefully analyze the efficiency and safety of these.
79 #[tracing::instrument(target = "r1cs", skip(self, other))]
80 fn enforce_not_equal(&self, other: &Self) -> Result<(), SynthesisError> {
81 self.conditional_enforce_not_equal(other, &Boolean::TRUE)
82 }
83}
84
85impl<T: EqGadget<F> + R1CSVar<F>, F: PrimeField> EqGadget<F> for [T] {
86 #[tracing::instrument(target = "r1cs", skip(self, other))]
87 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
88 assert_eq!(self.len(), other.len());
89 if self.is_empty() & other.is_empty() {
90 Ok(Boolean::TRUE)
91 } else {
92 let mut results = Vec::with_capacity(self.len());
93 for (a, b) in self.iter().zip(other) {
94 results.push(a.is_eq(b)?);
95 }
96 Boolean::kary_and(&results)
97 }
98 }
99
100 #[tracing::instrument(target = "r1cs", skip(self, other))]
101 fn conditional_enforce_equal(
102 &self,
103 other: &Self,
104 condition: &Boolean<F>,
105 ) -> Result<(), SynthesisError> {
106 assert_eq!(self.len(), other.len());
107 for (a, b) in self.iter().zip(other) {
108 a.conditional_enforce_equal(b, condition)?;
109 }
110 Ok(())
111 }
112
113 #[tracing::instrument(target = "r1cs", skip(self, other))]
114 fn conditional_enforce_not_equal(
115 &self,
116 other: &Self,
117 should_enforce: &Boolean<F>,
118 ) -> Result<(), SynthesisError> {
119 assert_eq!(self.len(), other.len());
120 let some_are_different = self.is_neq(other)?;
121 if [&some_are_different, should_enforce].is_constant() {
122 assert!(some_are_different.value()?);
123 Ok(())
124 } else {
125 let cs = [&some_are_different, should_enforce].cs();
126 if cs.should_construct_matrices() {
127 cs.enforce_constraint(
128 some_are_different.lc(),
129 should_enforce.lc(),
130 should_enforce.lc(),
131 )?;
132 } else {
133 cs.borrow_mut().unwrap().num_constraints += 1;
134 }
135 Ok(())
136 }
137 }
138}
139
140/// This blanket implementation just forwards to the impl on [`[T]`].
141impl<T: EqGadget<F> + R1CSVar<F>, F: PrimeField> EqGadget<F> for Vec<T> {
142 #[tracing::instrument(target = "r1cs", skip(self, other))]
143 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
144 self.as_slice().is_eq(other.as_slice())
145 }
146
147 #[tracing::instrument(target = "r1cs", skip(self, other))]
148 fn conditional_enforce_equal(
149 &self,
150 other: &Self,
151 condition: &Boolean<F>,
152 ) -> Result<(), SynthesisError> {
153 self.as_slice()
154 .conditional_enforce_equal(other.as_slice(), condition)
155 }
156
157 #[tracing::instrument(target = "r1cs", skip(self, other))]
158 fn conditional_enforce_not_equal(
159 &self,
160 other: &Self,
161 should_enforce: &Boolean<F>,
162 ) -> Result<(), SynthesisError> {
163 self.as_slice()
164 .conditional_enforce_not_equal(other.as_slice(), should_enforce)
165 }
166}
167
168/// Dummy impl for `()`.
169impl<F: Field> EqGadget<F> for () {
170 /// Output a `Boolean` value representing whether `self.value() ==
171 /// other.value()`.
172 #[inline]
173 fn is_eq(&self, _other: &Self) -> Result<Boolean<F>, SynthesisError> {
174 Ok(Boolean::TRUE)
175 }
176
177 /// If `should_enforce == true`, enforce that `self` and `other` are equal;
178 /// else, enforce a vacuously true statement.
179 ///
180 /// This is a no-op as `self.is_eq(other)?` is always `true`.
181 #[tracing::instrument(target = "r1cs", skip(self, _other))]
182 fn conditional_enforce_equal(
183 &self,
184 _other: &Self,
185 _should_enforce: &Boolean<F>,
186 ) -> Result<(), SynthesisError> {
187 Ok(())
188 }
189
190 /// Enforce that `self` and `other` are equal.
191 ///
192 /// This does not generate any constraints as `self.is_eq(other)?` is always
193 /// `true`.
194 #[tracing::instrument(target = "r1cs", skip(self, _other))]
195 fn enforce_equal(&self, _other: &Self) -> Result<(), SynthesisError> {
196 Ok(())
197 }
198}
199
200/// This blanket implementation just forwards to the impl on [`[T]`].
201impl<T: EqGadget<F> + R1CSVar<F>, F: PrimeField, const N: usize> EqGadget<F> for [T; N] {
202 #[tracing::instrument(target = "r1cs", skip(self, other))]
203 fn is_eq(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
204 self.as_slice().is_eq(other.as_slice())
205 }
206
207 #[tracing::instrument(target = "r1cs", skip(self, other))]
208 fn conditional_enforce_equal(
209 &self,
210 other: &Self,
211 condition: &Boolean<F>,
212 ) -> Result<(), SynthesisError> {
213 self.as_slice()
214 .conditional_enforce_equal(other.as_slice(), condition)
215 }
216
217 #[tracing::instrument(target = "r1cs", skip(self, other))]
218 fn conditional_enforce_not_equal(
219 &self,
220 other: &Self,
221 should_enforce: &Boolean<F>,
222 ) -> Result<(), SynthesisError> {
223 self.as_slice()
224 .conditional_enforce_not_equal(other.as_slice(), should_enforce)
225 }
226}