ark-r1cs-std/src/bits/uint8.rs
src/bits/uint8.rsRaw
1use ark_ff::{Field, FpParameters, PrimeField, ToConstraintField};
2
3use ark_relations::r1cs::{ConstraintSystemRef, Namespace, SynthesisError};
4
5use crate::{fields::fp::AllocatedFp, prelude::*, Assignment, Vec};
6use core::borrow::Borrow;
7
8/// Represents an interpretation of 8 `Boolean` objects as an
9/// unsigned integer.
10#[derive(Clone, Debug)]
11pub struct UInt8<F: Field> {
12 /// Little-endian representation: least significant bit first
13 pub(crate) bits: Vec<Boolean<F>>,
14 pub(crate) value: Option<u8>,
15}
16
17impl<F: Field> R1CSVar<F> for UInt8<F> {
18 type Value = u8;
19
20 fn cs(&self) -> ConstraintSystemRef<F> {
21 self.bits.as_slice().cs()
22 }
23
24 fn value(&self) -> Result<Self::Value, SynthesisError> {
25 let mut value = None;
26 for (i, bit) in self.bits.iter().enumerate() {
27 let b = u8::from(bit.value()?);
28 value = match value {
29 Some(value) => Some(value + (b << i)),
30 None => Some(b << i),
31 };
32 }
33 debug_assert_eq!(self.value, value);
34 value.get()
35 }
36}
37
38impl<F: Field> UInt8<F> {
39 /// Construct a constant vector of `UInt8` from a vector of `u8`
40 ///
41 /// This *does not* create any new variables or constraints.
42 /// ```
43 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
44 /// // We'll use the BLS12-381 scalar field for our constraints.
45 /// use ark_test_curves::bls12_381::Fr;
46 /// use ark_relations::r1cs::*;
47 /// use ark_r1cs_std::prelude::*;
48 ///
49 /// let cs = ConstraintSystem::<Fr>::new_ref();
50 /// let var = vec![UInt8::new_witness(cs.clone(), || Ok(2))?];
51 ///
52 /// let constant = UInt8::constant_vec(&[2]);
53 /// var.enforce_equal(&constant)?;
54 /// assert!(cs.is_satisfied().unwrap());
55 /// # Ok(())
56 /// # }
57 /// ```
58 pub fn constant_vec(values: &[u8]) -> Vec<Self> {
59 let mut result = Vec::new();
60 for value in values {
61 result.push(UInt8::constant(*value));
62 }
63 result
64 }
65
66 /// Construct a constant `UInt8` from a `u8`
67 ///
68 /// This *does not* create new variables or constraints.
69 ///
70 /// ```
71 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
72 /// // We'll use the BLS12-381 scalar field for our constraints.
73 /// use ark_test_curves::bls12_381::Fr;
74 /// use ark_relations::r1cs::*;
75 /// use ark_r1cs_std::prelude::*;
76 ///
77 /// let cs = ConstraintSystem::<Fr>::new_ref();
78 /// let var = UInt8::new_witness(cs.clone(), || Ok(2))?;
79 ///
80 /// let constant = UInt8::constant(2);
81 /// var.enforce_equal(&constant)?;
82 /// assert!(cs.is_satisfied().unwrap());
83 /// # Ok(())
84 /// # }
85 /// ```
86 pub fn constant(value: u8) -> Self {
87 let mut bits = Vec::with_capacity(8);
88
89 let mut tmp = value;
90 for _ in 0..8 {
91 // If last bit is one, push one.
92 bits.push(Boolean::constant(tmp & 1 == 1));
93 tmp >>= 1;
94 }
95
96 Self {
97 bits,
98 value: Some(value),
99 }
100 }
101
102 /// Allocates a slice of `u8`'s as private witnesses.
103 pub fn new_witness_vec(
104 cs: impl Into<Namespace<F>>,
105 values: &[impl Into<Option<u8>> + Copy],
106 ) -> Result<Vec<Self>, SynthesisError> {
107 let ns = cs.into();
108 let cs = ns.cs();
109 let mut output_vec = Vec::with_capacity(values.len());
110 for value in values {
111 let byte: Option<u8> = Into::into(*value);
112 output_vec.push(Self::new_witness(cs.clone(), || byte.get())?);
113 }
114 Ok(output_vec)
115 }
116
117 /// Allocates a slice of `u8`'s as public inputs by first packing them into
118 /// elements of `F`, (thus reducing the number of input allocations),
119 /// allocating these elements as public inputs, and then converting
120 /// these field variables `FpVar<F>` variables back into bytes.
121 ///
122 /// From a user perspective, this trade-off adds constraints, but improves
123 /// verifier time and verification key size.
124 ///
125 /// ```
126 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
127 /// // We'll use the BLS12-381 scalar field for our constraints.
128 /// use ark_test_curves::bls12_381::Fr;
129 /// use ark_relations::r1cs::*;
130 /// use ark_r1cs_std::prelude::*;
131 ///
132 /// let cs = ConstraintSystem::<Fr>::new_ref();
133 /// let two = UInt8::new_witness(cs.clone(), || Ok(2))?;
134 /// let var = vec![two.clone(); 32];
135 ///
136 /// let c = UInt8::new_input_vec(cs.clone(), &[2; 32])?;
137 /// var.enforce_equal(&c)?;
138 /// assert!(cs.is_satisfied().unwrap());
139 /// # Ok(())
140 /// # }
141 /// ```
142 pub fn new_input_vec(
143 cs: impl Into<Namespace<F>>,
144 values: &[u8],
145 ) -> Result<Vec<Self>, SynthesisError>
146 where
147 F: PrimeField,
148 {
149 let ns = cs.into();
150 let cs = ns.cs();
151 let values_len = values.len();
152 let field_elements: Vec<F> = ToConstraintField::<F>::to_field_elements(values).unwrap();
153
154 let max_size = 8 * (F::Params::CAPACITY / 8) as usize;
155 let mut allocated_bits = Vec::new();
156 for field_element in field_elements.into_iter() {
157 let fe = AllocatedFp::new_input(cs.clone(), || Ok(field_element))?;
158 let fe_bits = fe.to_bits_le()?;
159
160 // Remove the most significant bit, because we know it should be zero
161 // because `values.to_field_elements()` only
162 // packs field elements up to the penultimate bit.
163 // That is, the most significant bit (`ConstraintF::NUM_BITS`-th bit) is
164 // unset, so we can just pop it off.
165 allocated_bits.extend_from_slice(&fe_bits[0..max_size]);
166 }
167
168 // Chunk up slices of 8 bit into bytes.
169 Ok(allocated_bits[0..(8 * values_len)]
170 .chunks(8)
171 .map(Self::from_bits_le)
172 .collect())
173 }
174
175 /// Converts a little-endian byte order representation of bits into a
176 /// `UInt8`.
177 ///
178 /// ```
179 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
180 /// // We'll use the BLS12-381 scalar field for our constraints.
181 /// use ark_test_curves::bls12_381::Fr;
182 /// use ark_relations::r1cs::*;
183 /// use ark_r1cs_std::prelude::*;
184 ///
185 /// let cs = ConstraintSystem::<Fr>::new_ref();
186 /// let var = UInt8::new_witness(cs.clone(), || Ok(128))?;
187 ///
188 /// let f = Boolean::FALSE;
189 /// let t = Boolean::TRUE;
190 ///
191 /// // Construct [0, 0, 0, 0, 0, 0, 0, 1]
192 /// let mut bits = vec![f.clone(); 7];
193 /// bits.push(t);
194 ///
195 /// let mut c = UInt8::from_bits_le(&bits);
196 /// var.enforce_equal(&c)?;
197 /// assert!(cs.is_satisfied().unwrap());
198 /// # Ok(())
199 /// # }
200 /// ```
201 #[tracing::instrument(target = "r1cs")]
202 pub fn from_bits_le(bits: &[Boolean<F>]) -> Self {
203 assert_eq!(bits.len(), 8);
204
205 let bits = bits.to_vec();
206
207 let mut value = Some(0u8);
208 for (i, b) in bits.iter().enumerate() {
209 value = match b.value().ok() {
210 Some(b) => value.map(|v| v + (u8::from(b) << i)),
211 None => None,
212 }
213 }
214
215 Self { value, bits }
216 }
217
218 /// Outputs `self ^ other`.
219 ///
220 /// If at least one of `self` and `other` are constants, then this method
221 /// *does not* create any constraints or variables.
222 ///
223 /// ```
224 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
225 /// // We'll use the BLS12-381 scalar field for our constraints.
226 /// use ark_test_curves::bls12_381::Fr;
227 /// use ark_relations::r1cs::*;
228 /// use ark_r1cs_std::prelude::*;
229 ///
230 /// let cs = ConstraintSystem::<Fr>::new_ref();
231 /// let a = UInt8::new_witness(cs.clone(), || Ok(16))?;
232 /// let b = UInt8::new_witness(cs.clone(), || Ok(17))?;
233 /// let c = UInt8::new_witness(cs.clone(), || Ok(1))?;
234 ///
235 /// a.xor(&b)?.enforce_equal(&c)?;
236 /// assert!(cs.is_satisfied().unwrap());
237 /// # Ok(())
238 /// # }
239 /// ```
240 #[tracing::instrument(target = "r1cs")]
241 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
242 let new_value = match (self.value, other.value) {
243 (Some(a), Some(b)) => Some(a ^ b),
244 _ => None,
245 };
246
247 let bits = self
248 .bits
249 .iter()
250 .zip(other.bits.iter())
251 .map(|(a, b)| a.xor(b))
252 .collect::<Result<_, _>>()?;
253
254 Ok(Self {
255 bits,
256 value: new_value,
257 })
258 }
259}
260
261impl<ConstraintF: Field> EqGadget<ConstraintF> for UInt8<ConstraintF> {
262 #[tracing::instrument(target = "r1cs")]
263 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
264 self.bits.as_slice().is_eq(&other.bits)
265 }
266
267 #[tracing::instrument(target = "r1cs")]
268 fn conditional_enforce_equal(
269 &self,
270 other: &Self,
271 condition: &Boolean<ConstraintF>,
272 ) -> Result<(), SynthesisError> {
273 self.bits.conditional_enforce_equal(&other.bits, condition)
274 }
275
276 #[tracing::instrument(target = "r1cs")]
277 fn conditional_enforce_not_equal(
278 &self,
279 other: &Self,
280 condition: &Boolean<ConstraintF>,
281 ) -> Result<(), SynthesisError> {
282 self.bits
283 .conditional_enforce_not_equal(&other.bits, condition)
284 }
285}
286
287impl<ConstraintF: Field> CondSelectGadget<ConstraintF> for UInt8<ConstraintF> {
288 #[tracing::instrument(target = "r1cs", skip(cond, true_value, false_value))]
289 fn conditionally_select(
290 cond: &Boolean<ConstraintF>,
291 true_value: &Self,
292 false_value: &Self,
293 ) -> Result<Self, SynthesisError> {
294 let selected_bits = true_value
295 .bits
296 .iter()
297 .zip(&false_value.bits)
298 .map(|(t, f)| cond.select(t, f))
299 .collect::<Result<Vec<_>, SynthesisError>>()?;
300 let selected_value = cond.value().ok().and_then(|cond| {
301 if cond {
302 true_value.value().ok()
303 } else {
304 false_value.value().ok()
305 }
306 });
307 Ok(Self {
308 bits: selected_bits,
309 value: selected_value,
310 })
311 }
312}
313
314impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
315 fn new_variable<T: Borrow<u8>>(
316 cs: impl Into<Namespace<ConstraintF>>,
317 f: impl FnOnce() -> Result<T, SynthesisError>,
318 mode: AllocationMode,
319 ) -> Result<Self, SynthesisError> {
320 let ns = cs.into();
321 let cs = ns.cs();
322 let value = f().map(|f| *f.borrow());
323 let values = match value {
324 Ok(val) => (0..8).map(|i| Some((val >> i) & 1 == 1)).collect(),
325 _ => vec![None; 8],
326 };
327 let bits = values
328 .into_iter()
329 .map(|v| Boolean::new_variable(cs.clone(), || v.get(), mode))
330 .collect::<Result<Vec<_>, _>>()?;
331 Ok(Self {
332 bits,
333 value: value.ok(),
334 })
335 }
336}
337
338#[cfg(test)]
339mod test {
340 use super::UInt8;
341 use crate::{prelude::*, Vec};
342 use ark_relations::r1cs::{ConstraintSystem, SynthesisError};
343 use ark_test_curves::bls12_381::Fr;
344 use rand::{Rng, SeedableRng};
345 use rand_xorshift::XorShiftRng;
346
347 #[test]
348 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
349 let cs = ConstraintSystem::<Fr>::new_ref();
350 let byte_val = 0b01110001;
351 let byte =
352 UInt8::new_witness(ark_relations::ns!(cs, "alloc value"), || Ok(byte_val)).unwrap();
353 let bits = byte.to_bits_le()?;
354 for (i, bit) in bits.iter().enumerate() {
355 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
356 }
357 Ok(())
358 }
359
360 #[test]
361 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
362 let cs = ConstraintSystem::<Fr>::new_ref();
363 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
364 let bytes =
365 UInt8::new_input_vec(ark_relations::ns!(cs, "alloc value"), &byte_vals).unwrap();
366 dbg!(bytes.value())?;
367 for (native, variable) in byte_vals.into_iter().zip(bytes) {
368 let bits = variable.to_bits_le()?;
369 for (i, bit) in bits.iter().enumerate() {
370 assert_eq!(
371 bit.value()?,
372 (native >> i) & 1 == 1,
373 "native value {}: bit {:?}",
374 native,
375 i
376 )
377 }
378 }
379 Ok(())
380 }
381
382 #[test]
383 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
384 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
385
386 for _ in 0..1000 {
387 let v = (0..8)
388 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
389 .collect::<Vec<_>>();
390
391 let val = UInt8::from_bits_le(&v);
392
393 for (i, bit) in val.bits.iter().enumerate() {
394 match bit {
395 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
396 _ => unreachable!(),
397 }
398 }
399
400 let expected_to_be_same = val.to_bits_le()?;
401
402 for x in v.iter().zip(expected_to_be_same.iter()) {
403 match x {
404 (&Boolean::Constant(true), &Boolean::Constant(true)) => {}
405 (&Boolean::Constant(false), &Boolean::Constant(false)) => {}
406 _ => unreachable!(),
407 }
408 }
409 }
410 Ok(())
411 }
412
413 #[test]
414 fn test_uint8_xor() -> Result<(), SynthesisError> {
415 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
416
417 for _ in 0..1000 {
418 let cs = ConstraintSystem::<Fr>::new_ref();
419
420 let a: u8 = rng.gen();
421 let b: u8 = rng.gen();
422 let c: u8 = rng.gen();
423
424 let mut expected = a ^ b ^ c;
425
426 let a_bit = UInt8::new_witness(ark_relations::ns!(cs, "a_bit"), || Ok(a)).unwrap();
427 let b_bit = UInt8::constant(b);
428 let c_bit = UInt8::new_witness(ark_relations::ns!(cs, "c_bit"), || Ok(c)).unwrap();
429
430 let r = a_bit.xor(&b_bit).unwrap();
431 let r = r.xor(&c_bit).unwrap();
432
433 assert!(cs.is_satisfied().unwrap());
434
435 assert!(r.value == Some(expected));
436
437 for b in r.bits.iter() {
438 match b {
439 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
440 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
441 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
442 }
443
444 expected >>= 1;
445 }
446 }
447 Ok(())
448 }
449}