ark-r1cs-std/src/bits/uint8.rs
src/bits/uint8.rsRaw
1use ark_ff::{Field, PrimeField, ToConstraintField};
2
3use ark_relations::r1cs::{ConstraintSystemRef, Namespace, SynthesisError};
4
5use crate::{
6 fields::fp::{AllocatedFp, FpVar},
7 prelude::*,
8 Assignment, ToConstraintFieldGadget, Vec,
9};
10use core::{borrow::Borrow, convert::TryFrom};
11
12/// Represents an interpretation of 8 `Boolean` objects as an
13/// unsigned integer.
14#[derive(Clone, Debug)]
15pub struct UInt8<F: Field> {
16 /// Little-endian representation: least significant bit first
17 pub(crate) bits: [Boolean<F>; 8],
18 pub(crate) value: Option<u8>,
19}
20
21impl<F: Field> R1CSVar<F> for UInt8<F> {
22 type Value = u8;
23
24 fn cs(&self) -> ConstraintSystemRef<F> {
25 self.bits.as_ref().cs()
26 }
27
28 fn value(&self) -> Result<Self::Value, SynthesisError> {
29 let mut value = None;
30 for (i, bit) in self.bits.iter().enumerate() {
31 let b = u8::from(bit.value()?);
32 value = match value {
33 Some(value) => Some(value + (b << i)),
34 None => Some(b << i),
35 };
36 }
37 debug_assert_eq!(self.value, value);
38 value.get()
39 }
40}
41
42impl<F: Field> UInt8<F> {
43 /// Construct a constant vector of `UInt8` from a vector of `u8`
44 ///
45 /// This *does not* create any new variables or constraints.
46 /// ```
47 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
48 /// // We'll use the BLS12-381 scalar field for our constraints.
49 /// use ark_test_curves::bls12_381::Fr;
50 /// use ark_relations::r1cs::*;
51 /// use ark_r1cs_std::prelude::*;
52 ///
53 /// let cs = ConstraintSystem::<Fr>::new_ref();
54 /// let var = vec![UInt8::new_witness(cs.clone(), || Ok(2))?];
55 ///
56 /// let constant = UInt8::constant_vec(&[2]);
57 /// var.enforce_equal(&constant)?;
58 /// assert!(cs.is_satisfied().unwrap());
59 /// # Ok(())
60 /// # }
61 /// ```
62 pub fn constant_vec(values: &[u8]) -> Vec<Self> {
63 let mut result = Vec::new();
64 for value in values {
65 result.push(UInt8::constant(*value));
66 }
67 result
68 }
69
70 /// Construct a constant `UInt8` from a `u8`
71 ///
72 /// This *does not* create new variables or constraints.
73 ///
74 /// ```
75 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
76 /// // We'll use the BLS12-381 scalar field for our constraints.
77 /// use ark_test_curves::bls12_381::Fr;
78 /// use ark_relations::r1cs::*;
79 /// use ark_r1cs_std::prelude::*;
80 ///
81 /// let cs = ConstraintSystem::<Fr>::new_ref();
82 /// let var = UInt8::new_witness(cs.clone(), || Ok(2))?;
83 ///
84 /// let constant = UInt8::constant(2);
85 /// var.enforce_equal(&constant)?;
86 /// assert!(cs.is_satisfied().unwrap());
87 /// # Ok(())
88 /// # }
89 /// ```
90 pub fn constant(value: u8) -> Self {
91 let mut bits = [Boolean::FALSE; 8];
92
93 let mut tmp = value;
94 for i in 0..8 {
95 // If last bit is one, push one.
96 bits[i] = Boolean::constant((tmp & 1) == 1);
97 tmp >>= 1;
98 }
99
100 Self {
101 bits,
102 value: Some(value),
103 }
104 }
105
106 /// Allocates a slice of `u8`'s as private witnesses.
107 pub fn new_witness_vec(
108 cs: impl Into<Namespace<F>>,
109 values: &[impl Into<Option<u8>> + Copy],
110 ) -> Result<Vec<Self>, SynthesisError> {
111 let ns = cs.into();
112 let cs = ns.cs();
113 let mut output_vec = Vec::with_capacity(values.len());
114 for value in values {
115 let byte: Option<u8> = Into::into(*value);
116 output_vec.push(Self::new_witness(cs.clone(), || byte.get())?);
117 }
118 Ok(output_vec)
119 }
120
121 /// Allocates a slice of `u8`'s as public inputs by first packing them into
122 /// elements of `F`, (thus reducing the number of input allocations),
123 /// allocating these elements as public inputs, and then converting
124 /// these field variables `FpVar<F>` variables back into bytes.
125 ///
126 /// From a user perspective, this trade-off adds constraints, but improves
127 /// verifier time and verification key size.
128 ///
129 /// ```
130 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
131 /// // We'll use the BLS12-381 scalar field for our constraints.
132 /// use ark_test_curves::bls12_381::Fr;
133 /// use ark_relations::r1cs::*;
134 /// use ark_r1cs_std::prelude::*;
135 ///
136 /// let cs = ConstraintSystem::<Fr>::new_ref();
137 /// let two = UInt8::new_witness(cs.clone(), || Ok(2))?;
138 /// let var = vec![two.clone(); 32];
139 ///
140 /// let c = UInt8::new_input_vec(cs.clone(), &[2; 32])?;
141 /// var.enforce_equal(&c)?;
142 /// assert!(cs.is_satisfied().unwrap());
143 /// # Ok(())
144 /// # }
145 /// ```
146 pub fn new_input_vec(
147 cs: impl Into<Namespace<F>>,
148 values: &[u8],
149 ) -> Result<Vec<Self>, SynthesisError>
150 where
151 F: PrimeField,
152 {
153 let ns = cs.into();
154 let cs = ns.cs();
155 let values_len = values.len();
156 let field_elements: Vec<F> = ToConstraintField::<F>::to_field_elements(values).unwrap();
157
158 let max_size = 8 * ((F::MODULUS_BIT_SIZE - 1) / 8) as usize;
159 let mut allocated_bits = Vec::new();
160 for field_element in field_elements.into_iter() {
161 let fe = AllocatedFp::new_input(cs.clone(), || Ok(field_element))?;
162 let fe_bits = fe.to_bits_le()?;
163
164 // Remove the most significant bit, because we know it should be zero
165 // because `values.to_field_elements()` only
166 // packs field elements up to the penultimate bit.
167 // That is, the most significant bit (`ConstraintF::NUM_BITS`-th bit) is
168 // unset, so we can just pop it off.
169 allocated_bits.extend_from_slice(&fe_bits[0..max_size]);
170 }
171
172 // Chunk up slices of 8 bit into bytes.
173 Ok(allocated_bits[0..(8 * values_len)]
174 .chunks(8)
175 .map(Self::from_bits_le)
176 .collect())
177 }
178
179 /// Converts a little-endian byte order representation of bits into a
180 /// `UInt8`.
181 ///
182 /// ```
183 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
184 /// // We'll use the BLS12-381 scalar field for our constraints.
185 /// use ark_test_curves::bls12_381::Fr;
186 /// use ark_relations::r1cs::*;
187 /// use ark_r1cs_std::prelude::*;
188 ///
189 /// let cs = ConstraintSystem::<Fr>::new_ref();
190 /// let var = UInt8::new_witness(cs.clone(), || Ok(128))?;
191 ///
192 /// let f = Boolean::FALSE;
193 /// let t = Boolean::TRUE;
194 ///
195 /// // Construct [0, 0, 0, 0, 0, 0, 0, 1]
196 /// let mut bits = vec![f.clone(); 7];
197 /// bits.push(t);
198 ///
199 /// let mut c = UInt8::from_bits_le(&bits);
200 /// var.enforce_equal(&c)?;
201 /// assert!(cs.is_satisfied().unwrap());
202 /// # Ok(())
203 /// # }
204 /// ```
205 #[tracing::instrument(target = "r1cs")]
206 pub fn from_bits_le(bits: &[Boolean<F>]) -> Self {
207 assert_eq!(bits.len(), 8);
208 let bits = <&[Boolean<F>; 8]>::try_from(bits).unwrap().clone();
209
210 let mut value = Some(0u8);
211 for (i, b) in bits.iter().enumerate() {
212 value = match b.value().ok() {
213 Some(b) => value.map(|v| v + (u8::from(b) << i)),
214 None => None,
215 }
216 }
217
218 Self { value, bits }
219 }
220
221 /// Outputs `self ^ other`.
222 ///
223 /// If at least one of `self` and `other` are constants, then this method
224 /// *does not* create any constraints or variables.
225 ///
226 /// ```
227 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
228 /// // We'll use the BLS12-381 scalar field for our constraints.
229 /// use ark_test_curves::bls12_381::Fr;
230 /// use ark_relations::r1cs::*;
231 /// use ark_r1cs_std::prelude::*;
232 ///
233 /// let cs = ConstraintSystem::<Fr>::new_ref();
234 /// let a = UInt8::new_witness(cs.clone(), || Ok(16))?;
235 /// let b = UInt8::new_witness(cs.clone(), || Ok(17))?;
236 /// let c = UInt8::new_witness(cs.clone(), || Ok(1))?;
237 ///
238 /// a.xor(&b)?.enforce_equal(&c)?;
239 /// assert!(cs.is_satisfied().unwrap());
240 /// # Ok(())
241 /// # }
242 /// ```
243 #[tracing::instrument(target = "r1cs")]
244 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
245 let mut result = self.clone();
246 result.value = match (self.value, other.value) {
247 (Some(a), Some(b)) => Some(a ^ b),
248 _ => None,
249 };
250
251 let new_bits = self.bits.iter().zip(&other.bits).map(|(a, b)| a.xor(b));
252
253 for (res, new) in result.bits.iter_mut().zip(new_bits) {
254 *res = new?;
255 }
256
257 Ok(result)
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_ref().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 let mut bits = [Boolean::FALSE; 8];
300 for (result, new) in bits.iter_mut().zip(selected_bits) {
301 *result = new?;
302 }
303
304 let value = cond.value().ok().and_then(|cond| {
305 if cond {
306 true_value.value().ok()
307 } else {
308 false_value.value().ok()
309 }
310 });
311 Ok(Self { bits, value })
312 }
313}
314
315impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
316 fn new_variable<T: Borrow<u8>>(
317 cs: impl Into<Namespace<ConstraintF>>,
318 f: impl FnOnce() -> Result<T, SynthesisError>,
319 mode: AllocationMode,
320 ) -> Result<Self, SynthesisError> {
321 let ns = cs.into();
322 let cs = ns.cs();
323 let value = f().map(|f| *f.borrow()).ok();
324
325 let mut values = [None; 8];
326 if let Some(val) = value {
327 values
328 .iter_mut()
329 .enumerate()
330 .for_each(|(i, v)| *v = Some((val >> i) & 1 == 1));
331 }
332
333 let mut bits = [Boolean::FALSE; 8];
334 for (b, v) in bits.iter_mut().zip(&values) {
335 *b = Boolean::new_variable(cs.clone(), || v.get(), mode)?;
336 }
337 Ok(Self { bits, value })
338 }
339}
340
341/// Parses the `Vec<UInt8<ConstraintF>>` in fixed-sized
342/// `ConstraintF::MODULUS_BIT_SIZE - 1` chunks and converts each chunk, which is
343/// assumed to be little-endian, to its `FpVar<ConstraintF>` representation.
344/// This is the gadget counterpart to the `[u8]` implementation of
345/// [ToConstraintField](ark_ff::ToConstraintField).
346impl<ConstraintF: PrimeField> ToConstraintFieldGadget<ConstraintF> for [UInt8<ConstraintF>] {
347 #[tracing::instrument(target = "r1cs")]
348 fn to_constraint_field(&self) -> Result<Vec<FpVar<ConstraintF>>, SynthesisError> {
349 let max_size = ((ConstraintF::MODULUS_BIT_SIZE - 1) / 8) as usize;
350 self.chunks(max_size)
351 .map(|chunk| Boolean::le_bits_to_fp_var(chunk.to_bits_le()?.as_slice()))
352 .collect::<Result<Vec<_>, SynthesisError>>()
353 }
354}
355
356impl<ConstraintF: PrimeField> ToConstraintFieldGadget<ConstraintF> for Vec<UInt8<ConstraintF>> {
357 #[tracing::instrument(target = "r1cs")]
358 fn to_constraint_field(&self) -> Result<Vec<FpVar<ConstraintF>>, SynthesisError> {
359 self.as_slice().to_constraint_field()
360 }
361}
362
363#[cfg(test)]
364mod test {
365 use super::UInt8;
366 use crate::{
367 fields::fp::FpVar,
368 prelude::{
369 AllocationMode::{Constant, Input, Witness},
370 *,
371 },
372 ToConstraintFieldGadget, Vec,
373 };
374 use ark_ff::{PrimeField, ToConstraintField};
375 use ark_relations::r1cs::{ConstraintSystem, SynthesisError};
376 use ark_std::rand::{distributions::Uniform, Rng};
377 use ark_test_curves::bls12_381::Fr;
378
379 #[test]
380 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
381 let cs = ConstraintSystem::<Fr>::new_ref();
382 let byte_val = 0b01110001;
383 let byte =
384 UInt8::new_witness(ark_relations::ns!(cs, "alloc value"), || Ok(byte_val)).unwrap();
385 let bits = byte.to_bits_le()?;
386 for (i, bit) in bits.iter().enumerate() {
387 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
388 }
389 Ok(())
390 }
391
392 #[test]
393 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
394 let cs = ConstraintSystem::<Fr>::new_ref();
395 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
396 let bytes =
397 UInt8::new_input_vec(ark_relations::ns!(cs, "alloc value"), &byte_vals).unwrap();
398 dbg!(bytes.value())?;
399 for (native, variable) in byte_vals.into_iter().zip(bytes) {
400 let bits = variable.to_bits_le()?;
401 for (i, bit) in bits.iter().enumerate() {
402 assert_eq!(
403 bit.value()?,
404 (native >> i) & 1 == 1,
405 "native value {}: bit {:?}",
406 native,
407 i
408 )
409 }
410 }
411 Ok(())
412 }
413
414 #[test]
415 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
416 let mut rng = ark_std::test_rng();
417
418 for _ in 0..1000 {
419 let v = (0..8)
420 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
421 .collect::<Vec<_>>();
422
423 let val = UInt8::from_bits_le(&v);
424
425 for (i, bit) in val.bits.iter().enumerate() {
426 match bit {
427 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
428 _ => unreachable!(),
429 }
430 }
431
432 let expected_to_be_same = val.to_bits_le()?;
433
434 for x in v.iter().zip(expected_to_be_same.iter()) {
435 match x {
436 (&Boolean::Constant(true), &Boolean::Constant(true)) => {},
437 (&Boolean::Constant(false), &Boolean::Constant(false)) => {},
438 _ => unreachable!(),
439 }
440 }
441 }
442 Ok(())
443 }
444
445 #[test]
446 fn test_uint8_xor() -> Result<(), SynthesisError> {
447 let mut rng = ark_std::test_rng();
448
449 for _ in 0..1000 {
450 let cs = ConstraintSystem::<Fr>::new_ref();
451
452 let a: u8 = rng.gen();
453 let b: u8 = rng.gen();
454 let c: u8 = rng.gen();
455
456 let mut expected = a ^ b ^ c;
457
458 let a_bit = UInt8::new_witness(ark_relations::ns!(cs, "a_bit"), || Ok(a)).unwrap();
459 let b_bit = UInt8::constant(b);
460 let c_bit = UInt8::new_witness(ark_relations::ns!(cs, "c_bit"), || Ok(c)).unwrap();
461
462 let r = a_bit.xor(&b_bit).unwrap();
463 let r = r.xor(&c_bit).unwrap();
464
465 assert!(cs.is_satisfied().unwrap());
466
467 assert!(r.value == Some(expected));
468
469 for b in r.bits.iter() {
470 match b {
471 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
472 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
473 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
474 }
475
476 expected >>= 1;
477 }
478 }
479 Ok(())
480 }
481
482 #[test]
483 fn test_uint8_to_constraint_field() -> Result<(), SynthesisError> {
484 let mut rng = ark_std::test_rng();
485 let max_size = ((<Fr as PrimeField>::MODULUS_BIT_SIZE - 1) / 8) as usize;
486
487 let modes = [Input, Witness, Constant];
488 for mode in &modes {
489 for _ in 0..1000 {
490 let cs = ConstraintSystem::<Fr>::new_ref();
491
492 let bytes: Vec<u8> = (&mut rng)
493 .sample_iter(&Uniform::new_inclusive(0, u8::max_value()))
494 .take(max_size * 3 + 5)
495 .collect();
496
497 let bytes_var = bytes
498 .iter()
499 .map(|byte| UInt8::new_variable(cs.clone(), || Ok(*byte), *mode))
500 .collect::<Result<Vec<_>, SynthesisError>>()?;
501
502 let f_vec: Vec<Fr> = bytes.to_field_elements().unwrap();
503 let f_var_vec: Vec<FpVar<Fr>> = bytes_var.to_constraint_field()?;
504
505 assert!(cs.is_satisfied().unwrap());
506 assert_eq!(f_vec, f_var_vec.value()?);
507 }
508 }
509
510 Ok(())
511 }
512
513 #[test]
514 fn test_uint8_random_access() {
515 let mut rng = ark_std::test_rng();
516
517 for _ in 0..100 {
518 let cs = ConstraintSystem::<Fr>::new_ref();
519
520 // value array
521 let values: Vec<u8> = (0..128).map(|_| rng.gen()).collect();
522 let values_const: Vec<UInt8<Fr>> = values.iter().map(|x| UInt8::constant(*x)).collect();
523
524 // index array
525 let position: Vec<bool> = (0..7).map(|_| rng.gen()).collect();
526 let position_var: Vec<Boolean<Fr>> = position
527 .iter()
528 .map(|b| {
529 Boolean::new_witness(ark_relations::ns!(cs, "index_arr_element"), || Ok(*b))
530 .unwrap()
531 })
532 .collect();
533
534 // index
535 let mut index = 0;
536 for x in position {
537 index *= 2;
538 index += if x { 1 } else { 0 };
539 }
540
541 assert_eq!(
542 UInt8::conditionally_select_power_of_two_vector(&position_var, &values_const)
543 .unwrap()
544 .value()
545 .unwrap(),
546 values[index]
547 )
548 }
549 }
550}