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