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 /// Little-endian representation: least significant bit first
16 pub(crate) value: Option<u8>,
17}
18
19impl<F: Field> R1CSVar<F> for UInt8<F> {
20 type Value = u8;
21
22 fn cs(&self) -> Option<ConstraintSystemRef<F>> {
23 self.bits.as_slice().cs()
24 }
25
26 fn value(&self) -> Result<Self::Value, SynthesisError> {
27 let mut value = None;
28 for (i, bit) in self.bits.iter().enumerate() {
29 let b = u8::from(bit.value()?);
30 value = match value {
31 Some(value) => Some(value + (b << i)),
32 None => Some(b << i),
33 };
34 }
35 debug_assert_eq!(self.value, value);
36 value.get()
37 }
38}
39
40impl<F: Field> UInt8<F> {
41 /// Construct a constant vector of `UInt8` from a vector of `u8`
42 pub fn constant_vec(values: &[u8]) -> Vec<Self> {
43 let mut result = Vec::new();
44 for value in values {
45 result.push(UInt8::constant(*value));
46 }
47 result
48 }
49
50 /// Construct a constant `UInt8` from a `u8`
51 pub fn constant(value: u8) -> Self {
52 let mut bits = Vec::with_capacity(8);
53
54 let mut tmp = value;
55 for _ in 0..8 {
56 // If last bit is one, push one.
57 bits.push(Boolean::constant(tmp & 1 == 1));
58 tmp >>= 1;
59 }
60
61 Self {
62 bits,
63 value: Some(value),
64 }
65 }
66
67 pub fn new_witness_vec(
68 cs: impl Into<Namespace<F>>,
69 values: &[impl Into<Option<u8>> + Copy],
70 ) -> Result<Vec<Self>, SynthesisError> {
71 let ns = cs.into();
72 let cs = ns.cs();
73 let mut output_vec = Vec::with_capacity(values.len());
74 for value in values {
75 let byte: Option<u8> = Into::into(*value);
76 output_vec.push(Self::new_witness(cs.clone(), || byte.get())?);
77 }
78 Ok(output_vec)
79 }
80
81 /// Allocates a vector of `u8`'s by first converting (chunks of) them to
82 /// `ConstraintF` elements, (thus reducing the number of input allocations),
83 /// and then converts this list of `ConstraintF` gadgets back into
84 /// bytes.
85 pub fn new_input_vec(
86 cs: impl Into<Namespace<F>>,
87 values: &[u8],
88 ) -> Result<Vec<Self>, SynthesisError>
89 where
90 F: PrimeField,
91 {
92 let ns = cs.into();
93 let cs = ns.cs();
94 let values_len = values.len();
95 let field_elements: Vec<F> = ToConstraintField::<F>::to_field_elements(values).unwrap();
96
97 let max_size = 8 * (F::Params::CAPACITY / 8) as usize;
98 let mut allocated_bits = Vec::new();
99 for field_element in field_elements.into_iter() {
100 let fe = AllocatedFp::new_input(cs.clone(), || Ok(field_element))?;
101 let mut fe_bits = fe.to_bits()?;
102 // FpGadget::to_bits outputs a big-endian binary representation of
103 // fe_gadget's value, so we have to reverse it to get the little-endian
104 // form.
105 fe_bits.reverse();
106
107 // Remove the most significant bit, because we know it should be zero
108 // because `values.to_field_elements()` only
109 // packs field elements up to the penultimate bit.
110 // That is, the most significant bit (`ConstraintF::NUM_BITS`-th bit) is
111 // unset, so we can just pop it off.
112 allocated_bits.extend_from_slice(&fe_bits[0..max_size]);
113 }
114
115 // Chunk up slices of 8 bit into bytes.
116 Ok(allocated_bits[0..8 * values_len]
117 .chunks(8)
118 .map(Self::from_bits_le)
119 .collect())
120 }
121
122 /// Turns this `UInt8` into its little-endian byte order representation.
123 /// LSB-first means that we can easily get the corresponding field element
124 /// via double and add.
125 pub fn into_bits_le(&self) -> Vec<Boolean<F>> {
126 self.bits.to_vec()
127 }
128
129 /// Converts a little-endian byte order representation of bits into a
130 /// `UInt8`.
131 pub fn from_bits_le(bits: &[Boolean<F>]) -> Self {
132 assert_eq!(bits.len(), 8);
133
134 let bits = bits.to_vec();
135
136 let mut value = Some(0u8);
137 for b in bits.iter().rev() {
138 value.as_mut().map(|v| *v <<= 1);
139
140 match *b {
141 Boolean::Constant(b) => {
142 value.as_mut().map(|v| *v |= u8::from(b));
143 }
144 Boolean::Is(ref b) => match b.value() {
145 Ok(b) => {
146 value.as_mut().map(|v| *v |= u8::from(b));
147 }
148 Err(_) => value = None,
149 },
150 Boolean::Not(ref b) => match b.value() {
151 Ok(b) => {
152 value.as_mut().map(|v| *v |= u8::from(!b));
153 }
154 Err(_) => value = None,
155 },
156 }
157 }
158
159 Self { value, bits }
160 }
161
162 /// XOR this `UInt8` with another `UInt8`
163 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
164 let new_value = match (self.value, other.value) {
165 (Some(a), Some(b)) => Some(a ^ b),
166 _ => None,
167 };
168
169 let bits = self
170 .bits
171 .iter()
172 .zip(other.bits.iter())
173 .map(|(a, b)| a.xor(b))
174 .collect::<Result<_, _>>()?;
175
176 Ok(Self {
177 bits,
178 value: new_value,
179 })
180 }
181}
182
183impl<ConstraintF: Field> EqGadget<ConstraintF> for UInt8<ConstraintF> {
184 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
185 self.bits.as_slice().is_eq(&other.bits)
186 }
187
188 fn conditional_enforce_equal(
189 &self,
190 other: &Self,
191 condition: &Boolean<ConstraintF>,
192 ) -> Result<(), SynthesisError> {
193 self.bits.conditional_enforce_equal(&other.bits, condition)
194 }
195
196 fn conditional_enforce_not_equal(
197 &self,
198 other: &Self,
199 condition: &Boolean<ConstraintF>,
200 ) -> Result<(), SynthesisError> {
201 self.bits
202 .conditional_enforce_not_equal(&other.bits, condition)
203 }
204}
205
206impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
207 fn new_variable<T: Borrow<u8>>(
208 cs: impl Into<Namespace<ConstraintF>>,
209 f: impl FnOnce() -> Result<T, SynthesisError>,
210 mode: AllocationMode,
211 ) -> Result<Self, SynthesisError> {
212 let ns = cs.into();
213 let cs = ns.cs();
214 let value = f().map(|f| *f.borrow());
215 let values = match value {
216 Ok(val) => (0..8).map(|i| Some((val >> i) & 1 == 1)).collect(),
217 _ => vec![None; 8],
218 };
219 let bits = values
220 .into_iter()
221 .map(|v| Boolean::new_variable(cs.clone(), || v.get(), mode))
222 .collect::<Result<Vec<_>, _>>()?;
223 Ok(Self {
224 bits,
225 value: value.ok(),
226 })
227 }
228}
229
230#[cfg(test)]
231mod test {
232 use super::UInt8;
233 use crate::{prelude::*, Vec};
234 use algebra::bls12_381::Fr;
235 use r1cs_core::{ConstraintSystem, SynthesisError};
236 use rand::{Rng, SeedableRng};
237 use rand_xorshift::XorShiftRng;
238
239 #[test]
240 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
241 let cs = ConstraintSystem::<Fr>::new_ref();
242 let byte_val = 0b01110001;
243 let byte = UInt8::new_witness(cs.ns("alloc value"), || Ok(byte_val)).unwrap();
244 let bits = byte.into_bits_le();
245 for (i, bit) in bits.iter().enumerate() {
246 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
247 }
248 Ok(())
249 }
250
251 #[test]
252 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
253 let cs = ConstraintSystem::<Fr>::new_ref();
254 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
255 let bytes = UInt8::new_input_vec(cs.ns("alloc value"), &byte_vals).unwrap();
256 for (native, variable) in byte_vals.into_iter().zip(bytes) {
257 let bits = variable.into_bits_le();
258 for (i, bit) in bits.iter().enumerate() {
259 assert_eq!(bit.value()?, (native >> i) & 1 == 1)
260 }
261 }
262 Ok(())
263 }
264
265 #[test]
266 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
267 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
268
269 for _ in 0..1000 {
270 let v = (0..8)
271 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
272 .collect::<Vec<_>>();
273
274 let val = UInt8::from_bits_le(&v);
275
276 for (i, bit) in val.bits.iter().enumerate() {
277 match bit {
278 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
279 _ => unreachable!(),
280 }
281 }
282
283 let expected_to_be_same = val.into_bits_le();
284
285 for x in v.iter().zip(expected_to_be_same.iter()) {
286 match x {
287 (&Boolean::Constant(true), &Boolean::Constant(true)) => {}
288 (&Boolean::Constant(false), &Boolean::Constant(false)) => {}
289 _ => unreachable!(),
290 }
291 }
292 }
293 Ok(())
294 }
295
296 #[test]
297 fn test_uint8_xor() -> Result<(), SynthesisError> {
298 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
299
300 for _ in 0..1000 {
301 let cs = ConstraintSystem::<Fr>::new_ref();
302
303 let a: u8 = rng.gen();
304 let b: u8 = rng.gen();
305 let c: u8 = rng.gen();
306
307 let mut expected = a ^ b ^ c;
308
309 let a_bit = UInt8::new_witness(cs.ns("a_bit"), || Ok(a)).unwrap();
310 let b_bit = UInt8::constant(b);
311 let c_bit = UInt8::new_witness(cs.ns("c_bit"), || Ok(c)).unwrap();
312
313 let r = a_bit.xor(&b_bit).unwrap();
314 let r = r.xor(&c_bit).unwrap();
315
316 assert!(cs.is_satisfied().unwrap());
317
318 assert!(r.value == Some(expected));
319
320 for b in r.bits.iter() {
321 match b {
322 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
323 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
324 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
325 }
326
327 expected >>= 1;
328 }
329 }
330 Ok(())
331 }
332}