ark-r1cs-std/r1cs-std/src/bits/uint8.rs
r1cs-std/src/bits/uint8.rsRaw
1use algebra::Field;
2use algebra::{FpParameters, PrimeField, ToConstraintField};
3
4use r1cs_core::{ConstraintSystemRef, Namespace, SynthesisError};
5
6use crate::{fields::fp::AllocatedFp, prelude::*, Assignment, Vec};
7use core::borrow::Borrow;
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: Vec<Boolean<F>>,
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_slice().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<(), r1cs_core::SynthesisError> {
45 /// // We'll use the BLS12-381 scalar field for our constraints.
46 /// use algebra::bls12_381::Fr;
47 /// use r1cs_core::*;
48 /// use 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<(), r1cs_core::SynthesisError> {
73 /// // We'll use the BLS12-381 scalar field for our constraints.
74 /// use algebra::bls12_381::Fr;
75 /// use r1cs_core::*;
76 /// use 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 = Vec::with_capacity(8);
89
90 let mut tmp = value;
91 for _ in 0..8 {
92 // If last bit is one, push one.
93 bits.push(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), allocating
120 /// these elements as public inputs, and then converting these field variables
121 /// `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<(), r1cs_core::SynthesisError> {
128 /// // We'll use the BLS12-381 scalar field for our constraints.
129 /// use algebra::bls12_381::Fr;
130 /// use r1cs_core::*;
131 /// use 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<(), r1cs_core::SynthesisError> {
181 /// // We'll use the BLS12-381 scalar field for our constraints.
182 /// use algebra::bls12_381::Fr;
183 /// use r1cs_core::*;
184 /// use 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
206 let bits = bits.to_vec();
207
208 let mut value = Some(0u8);
209 for (i, b) in bits.iter().enumerate() {
210 value = match b.value().ok() {
211 Some(b) => value.map(|v| v + (u8::from(b) << i)),
212 None => None,
213 }
214 }
215
216 Self { value, bits }
217 }
218
219 /// Outputs `self ^ other`.
220 ///
221 /// If at least one of `self` and `other` are constants, then this method
222 /// *does not* create any constraints or variables.
223 ///
224 /// ```
225 /// # fn main() -> Result<(), r1cs_core::SynthesisError> {
226 /// // We'll use the BLS12-381 scalar field for our constraints.
227 /// use algebra::bls12_381::Fr;
228 /// use r1cs_core::*;
229 /// use r1cs_std::prelude::*;
230 ///
231 /// let cs = ConstraintSystem::<Fr>::new_ref();
232 /// let a = UInt8::new_witness(cs.clone(), || Ok(16))?;
233 /// let b = UInt8::new_witness(cs.clone(), || Ok(17))?;
234 /// let c = UInt8::new_witness(cs.clone(), || Ok(1))?;
235 ///
236 /// a.xor(&b)?.enforce_equal(&c)?;
237 /// assert!(cs.is_satisfied().unwrap());
238 /// # Ok(())
239 /// # }
240 /// ```
241 #[tracing::instrument(target = "r1cs")]
242 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
243 let new_value = match (self.value, other.value) {
244 (Some(a), Some(b)) => Some(a ^ b),
245 _ => None,
246 };
247
248 let bits = self
249 .bits
250 .iter()
251 .zip(other.bits.iter())
252 .map(|(a, b)| a.xor(b))
253 .collect::<Result<_, _>>()?;
254
255 Ok(Self {
256 bits,
257 value: new_value,
258 })
259 }
260}
261
262impl<ConstraintF: Field> EqGadget<ConstraintF> for UInt8<ConstraintF> {
263 #[tracing::instrument(target = "r1cs")]
264 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
265 self.bits.as_slice().is_eq(&other.bits)
266 }
267
268 #[tracing::instrument(target = "r1cs")]
269 fn conditional_enforce_equal(
270 &self,
271 other: &Self,
272 condition: &Boolean<ConstraintF>,
273 ) -> Result<(), SynthesisError> {
274 self.bits.conditional_enforce_equal(&other.bits, condition)
275 }
276
277 #[tracing::instrument(target = "r1cs")]
278 fn conditional_enforce_not_equal(
279 &self,
280 other: &Self,
281 condition: &Boolean<ConstraintF>,
282 ) -> Result<(), SynthesisError> {
283 self.bits
284 .conditional_enforce_not_equal(&other.bits, condition)
285 }
286}
287
288impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
289 fn new_variable<T: Borrow<u8>>(
290 cs: impl Into<Namespace<ConstraintF>>,
291 f: impl FnOnce() -> Result<T, SynthesisError>,
292 mode: AllocationMode,
293 ) -> Result<Self, SynthesisError> {
294 let ns = cs.into();
295 let cs = ns.cs();
296 let value = f().map(|f| *f.borrow());
297 let values = match value {
298 Ok(val) => (0..8).map(|i| Some((val >> i) & 1 == 1)).collect(),
299 _ => vec![None; 8],
300 };
301 let bits = values
302 .into_iter()
303 .map(|v| Boolean::new_variable(cs.clone(), || v.get(), mode))
304 .collect::<Result<Vec<_>, _>>()?;
305 Ok(Self {
306 bits,
307 value: value.ok(),
308 })
309 }
310}
311
312#[cfg(test)]
313mod test {
314 use super::UInt8;
315 use crate::{prelude::*, Vec};
316 use algebra::bls12_381::Fr;
317 use r1cs_core::{ConstraintSystem, SynthesisError};
318 use rand::{Rng, SeedableRng};
319 use rand_xorshift::XorShiftRng;
320
321 #[test]
322 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
323 let cs = ConstraintSystem::<Fr>::new_ref();
324 let byte_val = 0b01110001;
325 let byte = UInt8::new_witness(r1cs_core::ns!(cs, "alloc value"), || Ok(byte_val)).unwrap();
326 let bits = byte.to_bits_le()?;
327 for (i, bit) in bits.iter().enumerate() {
328 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
329 }
330 Ok(())
331 }
332
333 #[test]
334 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
335 let cs = ConstraintSystem::<Fr>::new_ref();
336 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
337 let bytes = UInt8::new_input_vec(r1cs_core::ns!(cs, "alloc value"), &byte_vals).unwrap();
338 dbg!(bytes.value())?;
339 for (native, variable) in byte_vals.into_iter().zip(bytes) {
340 let bits = variable.to_bits_le()?;
341 for (i, bit) in bits.iter().enumerate() {
342 assert_eq!(
343 bit.value()?,
344 (native >> i) & 1 == 1,
345 "native value {}: bit {:?}",
346 native,
347 i
348 )
349 }
350 }
351 Ok(())
352 }
353
354 #[test]
355 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
356 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
357
358 for _ in 0..1000 {
359 let v = (0..8)
360 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
361 .collect::<Vec<_>>();
362
363 let val = UInt8::from_bits_le(&v);
364
365 for (i, bit) in val.bits.iter().enumerate() {
366 match bit {
367 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
368 _ => unreachable!(),
369 }
370 }
371
372 let expected_to_be_same = val.to_bits_le()?;
373
374 for x in v.iter().zip(expected_to_be_same.iter()) {
375 match x {
376 (&Boolean::Constant(true), &Boolean::Constant(true)) => {}
377 (&Boolean::Constant(false), &Boolean::Constant(false)) => {}
378 _ => unreachable!(),
379 }
380 }
381 }
382 Ok(())
383 }
384
385 #[test]
386 fn test_uint8_xor() -> Result<(), SynthesisError> {
387 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
388
389 for _ in 0..1000 {
390 let cs = ConstraintSystem::<Fr>::new_ref();
391
392 let a: u8 = rng.gen();
393 let b: u8 = rng.gen();
394 let c: u8 = rng.gen();
395
396 let mut expected = a ^ b ^ c;
397
398 let a_bit = UInt8::new_witness(r1cs_core::ns!(cs, "a_bit"), || Ok(a)).unwrap();
399 let b_bit = UInt8::constant(b);
400 let c_bit = UInt8::new_witness(r1cs_core::ns!(cs, "c_bit"), || Ok(c)).unwrap();
401
402 let r = a_bit.xor(&b_bit).unwrap();
403 let r = r.xor(&c_bit).unwrap();
404
405 assert!(cs.is_satisfied().unwrap());
406
407 assert!(r.value == Some(expected));
408
409 for b in r.bits.iter() {
410 match b {
411 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
412 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
413 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
414 }
415
416 expected >>= 1;
417 }
418 }
419 Ok(())
420 }
421}