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 /// Allocates a slice of `u8`'s as private witnesses.
68 pub fn new_witness_vec(
69 cs: impl Into<Namespace<F>>,
70 values: &[impl Into<Option<u8>> + Copy],
71 ) -> Result<Vec<Self>, SynthesisError> {
72 let ns = cs.into();
73 let cs = ns.cs();
74 let mut output_vec = Vec::with_capacity(values.len());
75 for value in values {
76 let byte: Option<u8> = Into::into(*value);
77 output_vec.push(Self::new_witness(cs.clone(), || byte.get())?);
78 }
79 Ok(output_vec)
80 }
81
82 /// Allocates a slice of `u8`'s as public inputs by first packing them into
83 /// `F` elements, (thus reducing the number of input allocations),
84 /// and then converts this list of `AllocatedFp<F>` variables back into
85 /// bytes.
86 ///
87 /// From a user perspective, this trade-off adds constraints, but improves
88 /// verifier time and verification key size.
89 pub fn new_input_vec(
90 cs: impl Into<Namespace<F>>,
91 values: &[u8],
92 ) -> Result<Vec<Self>, SynthesisError>
93 where
94 F: PrimeField,
95 {
96 let ns = cs.into();
97 let cs = ns.cs();
98 let values_len = values.len();
99 let field_elements: Vec<F> = ToConstraintField::<F>::to_field_elements(values).unwrap();
100
101 let max_size = 8 * (F::Params::CAPACITY / 8) as usize;
102 let mut allocated_bits = Vec::new();
103 for field_element in field_elements.into_iter() {
104 let fe = AllocatedFp::new_input(cs.clone(), || Ok(field_element))?;
105 let fe_bits = fe.to_bits_le()?;
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 /// Converts a little-endian byte order representation of bits into a
123 /// `UInt8`.
124 #[tracing::instrument(target = "r1cs")]
125 pub fn from_bits_le(bits: &[Boolean<F>]) -> Self {
126 assert_eq!(bits.len(), 8);
127
128 let bits = bits.to_vec();
129
130 let mut value = Some(0u8);
131 for (i, b) in bits.iter().enumerate() {
132 value = match b.value().ok() {
133 Some(b) => value.map(|v| v + (u8::from(b) << i)),
134 None => None,
135 }
136 }
137
138 Self { value, bits }
139 }
140
141 /// Outputs `self ^ other`.
142 ///
143 /// If at least one of `self` and `other` are constants, then this method
144 /// *does not* create any constraints or variables.
145 #[tracing::instrument(target = "r1cs")]
146 pub fn xor(&self, other: &Self) -> Result<Self, SynthesisError> {
147 let new_value = match (self.value, other.value) {
148 (Some(a), Some(b)) => Some(a ^ b),
149 _ => None,
150 };
151
152 let bits = self
153 .bits
154 .iter()
155 .zip(other.bits.iter())
156 .map(|(a, b)| a.xor(b))
157 .collect::<Result<_, _>>()?;
158
159 Ok(Self {
160 bits,
161 value: new_value,
162 })
163 }
164}
165
166impl<ConstraintF: Field> EqGadget<ConstraintF> for UInt8<ConstraintF> {
167 #[tracing::instrument(target = "r1cs")]
168 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
169 self.bits.as_slice().is_eq(&other.bits)
170 }
171
172 #[tracing::instrument(target = "r1cs")]
173 fn conditional_enforce_equal(
174 &self,
175 other: &Self,
176 condition: &Boolean<ConstraintF>,
177 ) -> Result<(), SynthesisError> {
178 self.bits.conditional_enforce_equal(&other.bits, condition)
179 }
180
181 #[tracing::instrument(target = "r1cs")]
182 fn conditional_enforce_not_equal(
183 &self,
184 other: &Self,
185 condition: &Boolean<ConstraintF>,
186 ) -> Result<(), SynthesisError> {
187 self.bits
188 .conditional_enforce_not_equal(&other.bits, condition)
189 }
190}
191
192impl<ConstraintF: Field> AllocVar<u8, ConstraintF> for UInt8<ConstraintF> {
193 fn new_variable<T: Borrow<u8>>(
194 cs: impl Into<Namespace<ConstraintF>>,
195 f: impl FnOnce() -> Result<T, SynthesisError>,
196 mode: AllocationMode,
197 ) -> Result<Self, SynthesisError> {
198 let ns = cs.into();
199 let cs = ns.cs();
200 let value = f().map(|f| *f.borrow());
201 let values = match value {
202 Ok(val) => (0..8).map(|i| Some((val >> i) & 1 == 1)).collect(),
203 _ => vec![None; 8],
204 };
205 let bits = values
206 .into_iter()
207 .map(|v| Boolean::new_variable(cs.clone(), || v.get(), mode))
208 .collect::<Result<Vec<_>, _>>()?;
209 Ok(Self {
210 bits,
211 value: value.ok(),
212 })
213 }
214}
215
216#[cfg(test)]
217mod test {
218 use super::UInt8;
219 use crate::{prelude::*, Vec};
220 use algebra::bls12_381::Fr;
221 use r1cs_core::{ConstraintSystem, SynthesisError};
222 use rand::{Rng, SeedableRng};
223 use rand_xorshift::XorShiftRng;
224
225 #[test]
226 fn test_uint8_from_bits_to_bits() -> Result<(), SynthesisError> {
227 let cs = ConstraintSystem::<Fr>::new_ref();
228 let byte_val = 0b01110001;
229 let byte = UInt8::new_witness(r1cs_core::ns!(cs, "alloc value"), || Ok(byte_val)).unwrap();
230 let bits = byte.to_bits_le()?;
231 for (i, bit) in bits.iter().enumerate() {
232 assert_eq!(bit.value()?, (byte_val >> i) & 1 == 1)
233 }
234 Ok(())
235 }
236
237 #[test]
238 fn test_uint8_new_input_vec() -> Result<(), SynthesisError> {
239 let cs = ConstraintSystem::<Fr>::new_ref();
240 let byte_vals = (64u8..128u8).collect::<Vec<_>>();
241 let bytes = UInt8::new_input_vec(r1cs_core::ns!(cs, "alloc value"), &byte_vals).unwrap();
242 dbg!(bytes.value())?;
243 for (native, variable) in byte_vals.into_iter().zip(bytes) {
244 let bits = variable.to_bits_le()?;
245 for (i, bit) in bits.iter().enumerate() {
246 assert_eq!(
247 bit.value()?,
248 (native >> i) & 1 == 1,
249 "native value {}: bit {:?}",
250 native,
251 i
252 )
253 }
254 }
255 Ok(())
256 }
257
258 #[test]
259 fn test_uint8_from_bits() -> Result<(), SynthesisError> {
260 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
261
262 for _ in 0..1000 {
263 let v = (0..8)
264 .map(|_| Boolean::<Fr>::Constant(rng.gen()))
265 .collect::<Vec<_>>();
266
267 let val = UInt8::from_bits_le(&v);
268
269 for (i, bit) in val.bits.iter().enumerate() {
270 match bit {
271 Boolean::Constant(b) => assert!(*b == ((val.value()? >> i) & 1 == 1)),
272 _ => unreachable!(),
273 }
274 }
275
276 let expected_to_be_same = val.to_bits_le()?;
277
278 for x in v.iter().zip(expected_to_be_same.iter()) {
279 match x {
280 (&Boolean::Constant(true), &Boolean::Constant(true)) => {}
281 (&Boolean::Constant(false), &Boolean::Constant(false)) => {}
282 _ => unreachable!(),
283 }
284 }
285 }
286 Ok(())
287 }
288
289 #[test]
290 fn test_uint8_xor() -> Result<(), SynthesisError> {
291 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
292
293 for _ in 0..1000 {
294 let cs = ConstraintSystem::<Fr>::new_ref();
295
296 let a: u8 = rng.gen();
297 let b: u8 = rng.gen();
298 let c: u8 = rng.gen();
299
300 let mut expected = a ^ b ^ c;
301
302 let a_bit = UInt8::new_witness(r1cs_core::ns!(cs, "a_bit"), || Ok(a)).unwrap();
303 let b_bit = UInt8::constant(b);
304 let c_bit = UInt8::new_witness(r1cs_core::ns!(cs, "c_bit"), || Ok(c)).unwrap();
305
306 let r = a_bit.xor(&b_bit).unwrap();
307 let r = r.xor(&c_bit).unwrap();
308
309 assert!(cs.is_satisfied().unwrap());
310
311 assert!(r.value == Some(expected));
312
313 for b in r.bits.iter() {
314 match b {
315 Boolean::Is(b) => assert!(b.value()? == (expected & 1 == 1)),
316 Boolean::Not(b) => assert!(!b.value()? == (expected & 1 == 1)),
317 Boolean::Constant(b) => assert!(*b == (expected & 1 == 1)),
318 }
319
320 expected >>= 1;
321 }
322 }
323 Ok(())
324 }
325}