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, convert::TryFrom};
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: [Boolean<F>; 8],
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_ref().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 = [Boolean::FALSE; 8];
88
89 let mut tmp = value;
90 for i in 0..8 {
91 // If last bit is one, push one.
92 bits[i] = 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 let bits = <&[Boolean<F>; 8]>::try_from(bits).unwrap().clone();
205
206 let mut value = Some(0u8);
207 for (i, b) in bits.iter().enumerate() {
208 value = match b.value().ok() {
209 Some(b) => value.map(|v| v + (u8::from(b) << i)),
210 None => None,
211 }
212 }
213
214 Self { value, bits }
215 }
216
217 /// Outputs `self ^ other`.
218 ///
219 /// If at least one of `self` and `other` are constants, then this method
220 /// *does not* create any constraints or variables.
221 ///
222 /// ```
223 /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
224 /// // We'll use the BLS12-381 scalar field for our constraints.
225 /// use ark_test_curves::bls12_381::Fr;
226 /// use ark_relations::r1cs::*;
227 /// use ark_r1cs_std::prelude::*;
228 ///
229 /// let cs = ConstraintSystem::<Fr>::new_ref();
230 /// let a = UInt8::new_witness(cs.clone(), || Ok(16))?;
231 /// let b = UInt8::new_witness(cs.clone(), || Ok(17))?;
232 /// let c = UInt8::new_witness(cs.clone(), || Ok(1))?;
233 ///
234 /// a.xor(&b)?.enforce_equal(&c)?;
235 /// assert!(cs.is_satisfied().unwrap());
236 /// # Ok(())
237 /// # }
238 /// ```
239 #[tracing::instrument(target = "r1cs")]
240 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
241 let mut result = self.clone();
242 result.value = match (self.value, other.value) {
243 (Some(a), Some(b)) => Some(a ^ b),
244 _ => None,
245 };
246
247 let new_bits = self.bits.iter().zip(&other.bits).map(|(a, b)| a.xor(b));
248
249 for (res, new) in result.bits.iter_mut().zip(new_bits) {
250 *res = new?;
251 }
252
253 Ok(result)
254 }
255}
256
257impl<ConstraintF: Field> EqGadget<ConstraintF> for UInt8<ConstraintF> {
258 #[tracing::instrument(target = "r1cs")]
259 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
260 self.bits.as_ref().is_eq(&other.bits)
261 }
262
263 #[tracing::instrument(target = "r1cs")]
264 fn conditional_enforce_equal(
265 &self,
266 other: &Self,
267 condition: &Boolean<ConstraintF>,
268 ) -> Result<(), SynthesisError> {
269 self.bits.conditional_enforce_equal(&other.bits, condition)
270 }
271
272 #[tracing::instrument(target = "r1cs")]
273 fn conditional_enforce_not_equal(
274 &self,
275 other: &Self,
276 condition: &Boolean<ConstraintF>,
277 ) -> Result<(), SynthesisError> {
278 self.bits
279 .conditional_enforce_not_equal(&other.bits, condition)
280 }
281}
282
283impl<ConstraintF: Field> CondSelectGadget<ConstraintF> for UInt8<ConstraintF> {
284 #[tracing::instrument(target = "r1cs", skip(cond, true_value, false_value))]
285 fn conditionally_select(
286 cond: &Boolean<ConstraintF>,
287 true_value: &Self,
288 false_value: &Self,
289 ) -> Result<Self, SynthesisError> {
290 let selected_bits = true_value
291 .bits
292 .iter()
293 .zip(&false_value.bits)
294 .map(|(t, f)| cond.select(t, f));
295 let mut bits = [Boolean::FALSE; 8];
296 for (result, new) in bits.iter_mut().zip(selected_bits) {
297 *result = new?;
298 }
299
300 let 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 { bits, value })
308 }
309}
310
311impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
312 fn new_variable<T: Borrow<u8>>(
313 cs: impl Into<Namespace<ConstraintF>>,
314 f: impl FnOnce() -> Result<T, SynthesisError>,
315 mode: AllocationMode,
316 ) -> Result<Self, SynthesisError> {
317 let ns = cs.into();
318 let cs = ns.cs();
319 let value = f().map(|f| *f.borrow()).ok();
320
321 let mut values = [None; 8];
322 if let Some(val) = value {
323 values
324 .iter_mut()
325 .enumerate()
326 .for_each(|(i, v)| *v = Some((val >> i) & 1 == 1));
327 }
328
329 let mut bits = [Boolean::FALSE; 8];
330 for (b, v) in bits.iter_mut().zip(&values) {
331 *b = Boolean::new_variable(cs.clone(), || v.get(), mode)?;
332 }
333 Ok(Self { bits, value })
334 }
335}
336
337#[cfg(test)]
338mod test {
339 use super::UInt8;
340 use crate::{prelude::*, Vec};
341 use ark_relations::r1cs::{ConstraintSystem, SynthesisError};
342 use ark_test_curves::bls12_381::Fr;
343 use rand::{Rng, SeedableRng};
344 use rand_xorshift::XorShiftRng;
345
346 #[test]
347 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
348 let cs = ConstraintSystem::<Fr>::new_ref();
349 let byte_val = 0b01110001;
350 let byte =
351 UInt8::new_witness(ark_relations::ns!(cs, "alloc value"), || Ok(byte_val)).unwrap();
352 let bits = byte.to_bits_le()?;
353 for (i, bit) in bits.iter().enumerate() {
354 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
355 }
356 Ok(())
357 }
358
359 #[test]
360 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
361 let cs = ConstraintSystem::<Fr>::new_ref();
362 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
363 let bytes =
364 UInt8::new_input_vec(ark_relations::ns!(cs, "alloc value"), &byte_vals).unwrap();
365 dbg!(bytes.value())?;
366 for (native, variable) in byte_vals.into_iter().zip(bytes) {
367 let bits = variable.to_bits_le()?;
368 for (i, bit) in bits.iter().enumerate() {
369 assert_eq!(
370 bit.value()?,
371 (native >> i) & 1 == 1,
372 "native value {}: bit {:?}",
373 native,
374 i
375 )
376 }
377 }
378 Ok(())
379 }
380
381 #[test]
382 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
383 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
384
385 for _ in 0..1000 {
386 let v = (0..8)
387 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
388 .collect::<Vec<_>>();
389
390 let val = UInt8::from_bits_le(&v);
391
392 for (i, bit) in val.bits.iter().enumerate() {
393 match bit {
394 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
395 _ => unreachable!(),
396 }
397 }
398
399 let expected_to_be_same = val.to_bits_le()?;
400
401 for x in v.iter().zip(expected_to_be_same.iter()) {
402 match x {
403 (&Boolean::Constant(true), &Boolean::Constant(true)) => {}
404 (&Boolean::Constant(false), &Boolean::Constant(false)) => {}
405 _ => unreachable!(),
406 }
407 }
408 }
409 Ok(())
410 }
411
412 #[test]
413 fn test_uint8_xor() -> Result<(), SynthesisError> {
414 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
415
416 for _ in 0..1000 {
417 let cs = ConstraintSystem::<Fr>::new_ref();
418
419 let a: u8 = rng.gen();
420 let b: u8 = rng.gen();
421 let c: u8 = rng.gen();
422
423 let mut expected = a ^ b ^ c;
424
425 let a_bit = UInt8::new_witness(ark_relations::ns!(cs, "a_bit"), || Ok(a)).unwrap();
426 let b_bit = UInt8::constant(b);
427 let c_bit = UInt8::new_witness(ark_relations::ns!(cs, "c_bit"), || Ok(c)).unwrap();
428
429 let r = a_bit.xor(&b_bit).unwrap();
430 let r = r.xor(&c_bit).unwrap();
431
432 assert!(cs.is_satisfied().unwrap());
433
434 assert!(r.value == Some(expected));
435
436 for b in r.bits.iter() {
437 match b {
438 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
439 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
440 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
441 }
442
443 expected >>= 1;
444 }
445 }
446 Ok(())
447 }
448}