ark-r1cs-std/crypto-primitives/src/prf/blake2s/constraints.rs
crypto-primitives/src/prf/blake2s/constraints.rsRaw
1use algebra_core::PrimeField;
2use r1cs_core::{ConstraintSystemRef, Namespace, SynthesisError};
3
4use crate::{prf::PRFGadget, Vec};
5use r1cs_std::prelude::*;
6
7use core::borrow::Borrow;
8
9// 2.1. Parameters
10// The following table summarizes various parameters and their ranges:
11// | BLAKE2b | BLAKE2s |
12// --------------+------------------+------------------+
13// Bits in word | w = 64 | w = 32 |
14// Rounds in F | r = 12 | r = 10 |
15// Block bytes | bb = 128 | bb = 64 |
16// Hash bytes | 1 <= nn <= 64 | 1 <= nn <= 32 |
17// Key bytes | 0 <= kk <= 64 | 0 <= kk <= 32 |
18// Input bytes | 0 <= ll < 2**128 | 0 <= ll < 2**64 |
19// --------------+------------------+------------------+
20// G Rotation | (R1, R2, R3, R4) | (R1, R2, R3, R4) |
21// constants = | (32, 24, 16, 63) | (16, 12, 8, 7) |
22// --------------+------------------+------------------+
23//
24
25const R1: usize = 16;
26const R2: usize = 12;
27const R3: usize = 8;
28const R4: usize = 7;
29
30// Round | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
31// ----------+-------------------------------------------------+
32// SIGMA[0] | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
33// SIGMA[1] | 14 10 4 8 9 15 13 6 1 12 0 2 11 7 5 3 |
34// SIGMA[2] | 11 8 12 0 5 2 15 13 10 14 3 6 7 1 9 4 |
35// SIGMA[3] | 7 9 3 1 13 12 11 14 2 6 5 10 4 0 15 8 |
36// SIGMA[4] | 9 0 5 7 2 4 10 15 14 1 11 12 6 8 3 13 |
37// SIGMA[5] | 2 12 6 10 0 11 8 3 4 13 7 5 15 14 1 9 |
38// SIGMA[6] | 12 5 1 15 14 13 4 10 0 7 6 3 9 2 8 11 |
39// SIGMA[7] | 13 11 7 14 12 1 3 9 5 0 15 4 8 6 2 10 |
40// SIGMA[8] | 6 15 14 9 11 3 0 8 12 2 13 7 1 4 10 5 |
41// SIGMA[9] | 10 2 8 4 7 6 1 5 15 11 9 14 3 12 13 0 |
42// ----------+-------------------------------------------------+
43//
44
45const SIGMA: [[usize; 16]; 10] = [
46 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
47 [14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3],
48 [11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4],
49 [7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8],
50 [9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13],
51 [2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9],
52 [12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11],
53 [13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10],
54 [6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5],
55 [10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0],
56];
57
58// 3.1. Mixing Function G
59// The G primitive function mixes two input words, "x" and "y", into
60// four words indexed by "a", "b", "c", and "d" in the working vector
61// v[0..15]. The full modified vector is returned. The rotation
62// constants (R1, R2, R3, R4) are given in Section 2.1.
63// FUNCTION G( v[0..15], a, b, c, d, x, y )
64// |
65// | v[a] := (v[a] + v[b] + x) mod 2**w
66// | v[d] := (v[d] ^ v[a]) >>> R1
67// | v[c] := (v[c] + v[d]) mod 2**w
68// | v[b] := (v[b] ^ v[c]) >>> R2
69// | v[a] := (v[a] + v[b] + y) mod 2**w
70// | v[d] := (v[d] ^ v[a]) >>> R3
71// | v[c] := (v[c] + v[d]) mod 2**w
72// | v[b] := (v[b] ^ v[c]) >>> R4
73// |
74// | RETURN v[0..15]
75// |
76// END FUNCTION.
77//
78
79fn mixing_g<ConstraintF: PrimeField>(
80 v: &mut [UInt32<ConstraintF>],
81 a: usize,
82 b: usize,
83 c: usize,
84 d: usize,
85 x: &UInt32<ConstraintF>,
86 y: &UInt32<ConstraintF>,
87) -> Result<(), SynthesisError> {
88 v[a] = UInt32::addmany(&[v[a].clone(), v[b].clone(), x.clone()])?;
89 v[d] = v[d].xor(&v[a])?.rotr(R1);
90 v[c] = UInt32::addmany(&[v[c].clone(), v[d].clone()])?;
91 v[b] = v[b].xor(&v[c])?.rotr(R2);
92 v[a] = UInt32::addmany(&[v[a].clone(), v[b].clone(), y.clone()])?;
93 v[d] = v[d].xor(&v[a])?.rotr(R3);
94 v[c] = UInt32::addmany(&[v[c].clone(), v[d].clone()])?;
95 v[b] = v[b].xor(&v[c])?.rotr(R4);
96
97 Ok(())
98}
99
100// 3.2. Compression Function F
101// Compression function F takes as an argument the state vector "h",
102// message block vector "m" (last block is padded with zeros to full
103// block size, if required), 2w-bit offset counter "t", and final block
104// indicator flag "f". Local vector v[0..15] is used in processing. F
105// returns a new state vector. The number of rounds, "r", is 12 for
106// BLAKE2b and 10 for BLAKE2s. Rounds are numbered from 0 to r - 1.
107// FUNCTION F( h[0..7], m[0..15], t, f )
108// |
109// | // Initialize local work vector v[0..15]
110// | v[0..7] := h[0..7] // First half from state.
111// | v[8..15] := IV[0..7] // Second half from IV.
112// |
113// | v[12] := v[12] ^ (t mod 2**w) // Low word of the offset.
114// | v[13] := v[13] ^ (t >> w) // High word.
115// |
116// | IF f = TRUE THEN // last block flag?
117// | | v[14] := v[14] ^ 0xFF..FF // Invert all bits.
118// | END IF.
119// |
120// | // Cryptographic mixing
121// | FOR i = 0 TO r - 1 DO // Ten or twelve rounds.
122// | |
123// | | // Message word selection permutation for this round.
124// | | s[0..15] := SIGMA[i mod 10][0..15]
125// | |
126// | | v := G( v, 0, 4, 8, 12, m[s[ 0]], m[s[ 1]] )
127// | | v := G( v, 1, 5, 9, 13, m[s[ 2]], m[s[ 3]] )
128// | | v := G( v, 2, 6, 10, 14, m[s[ 4]], m[s[ 5]] )
129// | | v := G( v, 3, 7, 11, 15, m[s[ 6]], m[s[ 7]] )
130// | |
131// | | v := G( v, 0, 5, 10, 15, m[s[ 8]], m[s[ 9]] )
132// | | v := G( v, 1, 6, 11, 12, m[s[10]], m[s[11]] )
133// | | v := G( v, 2, 7, 8, 13, m[s[12]], m[s[13]] )
134// | | v := G( v, 3, 4, 9, 14, m[s[14]], m[s[15]] )
135// | |
136// | END FOR
137// |
138// | FOR i = 0 TO 7 DO // XOR the two halves.
139// | | h[i] := h[i] ^ v[i] ^ v[i + 8]
140// | END FOR.
141// |
142// | RETURN h[0..7] // New state.
143// |
144// END FUNCTION.
145//
146
147fn blake2s_compression<ConstraintF: PrimeField>(
148 h: &mut [UInt32<ConstraintF>],
149 m: &[UInt32<ConstraintF>],
150 t: u64,
151 f: bool,
152) -> Result<(), SynthesisError> {
153 assert_eq!(h.len(), 8);
154 assert_eq!(m.len(), 16);
155
156 // static const uint32_t blake2s_iv[8] =
157 // {
158 // 0x6A09E667, 0xBB67AE85, 0x3C6EF372, 0xA54FF53A,
159 // 0x510E527F, 0x9B05688C, 0x1F83D9AB, 0x5BE0CD19
160 // };
161 //
162
163 let mut v = Vec::with_capacity(16);
164 v.extend_from_slice(h);
165 v.push(UInt32::constant(0x6A09E667));
166 v.push(UInt32::constant(0xBB67AE85));
167 v.push(UInt32::constant(0x3C6EF372));
168 v.push(UInt32::constant(0xA54FF53A));
169 v.push(UInt32::constant(0x510E527F));
170 v.push(UInt32::constant(0x9B05688C));
171 v.push(UInt32::constant(0x1F83D9AB));
172 v.push(UInt32::constant(0x5BE0CD19));
173
174 assert_eq!(v.len(), 16);
175
176 v[12] = v[12].xor(&UInt32::constant(t as u32))?;
177 v[13] = v[13].xor(&UInt32::constant((t >> 32) as u32))?;
178
179 if f {
180 v[14] = v[14].xor(&UInt32::constant(u32::max_value()))?;
181 }
182
183 for i in 0..10 {
184 let s = SIGMA[i % 10];
185
186 mixing_g(&mut v, 0, 4, 8, 12, &m[s[0]], &m[s[1]])?;
187 mixing_g(&mut v, 1, 5, 9, 13, &m[s[2]], &m[s[3]])?;
188 mixing_g(&mut v, 2, 6, 10, 14, &m[s[4]], &m[s[5]])?;
189 mixing_g(&mut v, 3, 7, 11, 15, &m[s[6]], &m[s[7]])?;
190 mixing_g(&mut v, 0, 5, 10, 15, &m[s[8]], &m[s[9]])?;
191 mixing_g(&mut v, 1, 6, 11, 12, &m[s[10]], &m[s[11]])?;
192 mixing_g(&mut v, 2, 7, 8, 13, &m[s[12]], &m[s[13]])?;
193 mixing_g(&mut v, 3, 4, 9, 14, &m[s[14]], &m[s[15]])?;
194 }
195
196 for i in 0..8 {
197 h[i] = h[i].xor(&v[i])?;
198 h[i] = h[i].xor(&v[i + 8])?;
199 }
200
201 Ok(())
202}
203
204// FUNCTION BLAKE2( d[0..dd-1], ll, kk, nn )
205// |
206// | h[0..7] := IV[0..7] // Initialization Vector.
207// |
208// | // Parameter block p[0]
209// | h[0] := h[0] ^ 0x01010000 ^ (kk << 8) ^ nn
210// |
211// | // Process padded key and data blocks
212// | IF dd > 1 THEN
213// | | FOR i = 0 TO dd - 2 DO
214// | | | h := F( h, d[i], (i + 1) * bb, FALSE )
215// | | END FOR.
216// | END IF.
217// |
218// | // Final block.
219// | IF kk = 0 THEN
220// | | h := F( h, d[dd - 1], ll, TRUE )
221// | ELSE
222// | | h := F( h, d[dd - 1], ll + bb, TRUE )
223// | END IF.
224// |
225// | RETURN first "nn" bytes from little-endian word array h[].
226// |
227// END FUNCTION.
228//
229
230pub fn evaluate_blake2s<ConstraintF: PrimeField>(
231 input: &[Boolean<ConstraintF>],
232) -> Result<Vec<UInt32<ConstraintF>>, SynthesisError> {
233 assert!(input.len() % 8 == 0);
234 let mut parameters = [0; 8];
235 parameters[0] = 0x01010000 ^ 32;
236 evaluate_blake2s_with_parameters(input, ¶meters)
237}
238
239pub fn evaluate_blake2s_with_parameters<F: PrimeField>(
240 input: &[Boolean<F>],
241 parameters: &[u32; 8],
242) -> Result<Vec<UInt32<F>>, SynthesisError> {
243 assert!(input.len() % 8 == 0);
244
245 let mut h = Vec::with_capacity(8);
246 h.push(UInt32::constant(0x6A09E667).xor(&UInt32::constant(parameters[0]))?);
247 h.push(UInt32::constant(0xBB67AE85).xor(&UInt32::constant(parameters[1]))?);
248 h.push(UInt32::constant(0x3C6EF372).xor(&UInt32::constant(parameters[2]))?);
249 h.push(UInt32::constant(0xA54FF53A).xor(&UInt32::constant(parameters[3]))?);
250 h.push(UInt32::constant(0x510E527F).xor(&UInt32::constant(parameters[4]))?);
251 h.push(UInt32::constant(0x9B05688C).xor(&UInt32::constant(parameters[5]))?);
252 h.push(UInt32::constant(0x1F83D9AB).xor(&UInt32::constant(parameters[6]))?);
253 h.push(UInt32::constant(0x5BE0CD19).xor(&UInt32::constant(parameters[7]))?);
254
255 let mut blocks: Vec<Vec<UInt32<F>>> = vec![];
256
257 for block in input.chunks(512) {
258 let mut this_block = Vec::with_capacity(16);
259 for word in block.chunks(32) {
260 let mut tmp = word.to_vec();
261 while tmp.len() < 32 {
262 tmp.push(Boolean::constant(false));
263 }
264 this_block.push(UInt32::from_bits_le(&tmp));
265 }
266 while this_block.len() < 16 {
267 this_block.push(UInt32::constant(0));
268 }
269 blocks.push(this_block);
270 }
271
272 if blocks.is_empty() {
273 blocks.push((0..16).map(|_| UInt32::constant(0)).collect());
274 }
275
276 for (i, block) in blocks[0..blocks.len() - 1].iter().enumerate() {
277 blake2s_compression(&mut h, block, ((i as u64) + 1) * 64, false)?;
278 }
279
280 blake2s_compression(
281 &mut h,
282 &blocks[blocks.len() - 1],
283 (input.len() / 8) as u64,
284 true,
285 )?;
286
287 Ok(h)
288}
289
290use crate::prf::Blake2s;
291
292pub struct Blake2sGadget;
293#[derive(Clone, Debug)]
294pub struct OutputVar<ConstraintF: PrimeField>(pub Vec<UInt8<ConstraintF>>);
295
296impl<ConstraintF: PrimeField> EqGadget<ConstraintF> for OutputVar<ConstraintF> {
297 #[tracing::instrument(target = "r1cs")]
298 fn is_eq(&self, other: &Self) -> Result<Boolean<ConstraintF>, SynthesisError> {
299 self.0.is_eq(&other.0)
300 }
301
302 /// If `should_enforce == true`, enforce that `self` and `other` are equal; else,
303 /// enforce a vacuously true statement.
304 #[tracing::instrument(target = "r1cs")]
305 fn conditional_enforce_equal(
306 &self,
307 other: &Self,
308 should_enforce: &Boolean<ConstraintF>,
309 ) -> Result<(), SynthesisError> {
310 self.0.conditional_enforce_equal(&other.0, should_enforce)
311 }
312
313 /// If `should_enforce == true`, enforce that `self` and `other` are not equal; else,
314 /// enforce a vacuously true statement.
315 #[tracing::instrument(target = "r1cs")]
316 fn conditional_enforce_not_equal(
317 &self,
318 other: &Self,
319 should_enforce: &Boolean<ConstraintF>,
320 ) -> Result<(), SynthesisError> {
321 self.0
322 .as_slice()
323 .conditional_enforce_not_equal(other.0.as_slice(), should_enforce)
324 }
325}
326
327impl<ConstraintF: PrimeField> ToBytesGadget<ConstraintF> for OutputVar<ConstraintF> {
328 #[inline]
329 fn to_bytes(&self) -> Result<Vec<UInt8<ConstraintF>>, SynthesisError> {
330 Ok(self.0.clone())
331 }
332}
333
334impl<ConstraintF: PrimeField> AllocVar<[u8; 32], ConstraintF> for OutputVar<ConstraintF> {
335 #[tracing::instrument(target = "r1cs", skip(cs, f))]
336 fn new_variable<T: Borrow<[u8; 32]>>(
337 cs: impl Into<Namespace<ConstraintF>>,
338 f: impl FnOnce() -> Result<T, SynthesisError>,
339 mode: AllocationMode,
340 ) -> Result<Self, SynthesisError> {
341 let bytes = f().map(|b| *b.borrow()).unwrap_or([0u8; 32]);
342 match mode {
343 AllocationMode::Constant => Ok(Self(UInt8::constant_vec(&bytes))),
344 AllocationMode::Input => UInt8::new_input_vec(cs, &bytes).map(Self),
345 AllocationMode::Witness => UInt8::new_witness_vec(cs, &bytes).map(Self),
346 }
347 }
348}
349
350impl<F: PrimeField> R1CSVar<F> for OutputVar<F> {
351 type Value = [u8; 32];
352
353 fn cs(&self) -> ConstraintSystemRef<F> {
354 self.0.cs()
355 }
356
357 fn value(&self) -> Result<Self::Value, SynthesisError> {
358 let mut value = [0u8; 32];
359 for (val_i, self_i) in value.iter_mut().zip(&self.0) {
360 *val_i = self_i.value()?;
361 }
362 Ok(value)
363 }
364}
365
366impl<F: PrimeField> PRFGadget<Blake2s, F> for Blake2sGadget {
367 type OutputVar = OutputVar<F>;
368
369 #[tracing::instrument(target = "r1cs", skip(cs))]
370 fn new_seed(cs: impl Into<Namespace<F>>, seed: &[u8; 32]) -> Vec<UInt8<F>> {
371 let ns = cs.into();
372 let cs = ns.cs();
373 UInt8::new_witness_vec(r1cs_core::ns!(cs, "New Blake2s seed"), seed).unwrap()
374 }
375
376 #[tracing::instrument(target = "r1cs", skip(seed, input))]
377 fn evaluate(seed: &[UInt8<F>], input: &[UInt8<F>]) -> Result<Self::OutputVar, SynthesisError> {
378 assert_eq!(seed.len(), 32);
379 let input: Vec<_> = seed
380 .iter()
381 .chain(input)
382 .flat_map(|b| b.to_bits_le().unwrap())
383 .collect();
384 let result: Vec<_> = evaluate_blake2s(&input)?
385 .into_iter()
386 .flat_map(|int| int.to_bytes().unwrap())
387 .collect();
388 Ok(OutputVar(result))
389 }
390}
391
392#[cfg(test)]
393mod test {
394 use algebra::ed_on_bls12_381::Fq as Fr;
395 use rand::{Rng, SeedableRng};
396 use rand_xorshift::XorShiftRng;
397
398 use crate::prf::blake2s::{constraints::evaluate_blake2s, Blake2s as B2SPRF};
399 use blake2::VarBlake2s;
400 use r1cs_core::ConstraintSystem;
401
402 use super::Blake2sGadget;
403 use r1cs_std::prelude::*;
404
405 #[test]
406 fn test_blake2s_constraints() {
407 let cs = ConstraintSystem::<Fr>::new_ref();
408 let input_bits: Vec<_> = (0..512)
409 .map(|_| Boolean::new_witness(r1cs_core::ns!(cs, "input bit"), || Ok(true)).unwrap())
410 .collect();
411 evaluate_blake2s(&input_bits).unwrap();
412 assert!(cs.is_satisfied().unwrap());
413 assert_eq!(cs.num_constraints(), 21792);
414 }
415
416 #[test]
417 fn test_blake2s_prf() {
418 use crate::prf::{PRFGadget, PRF};
419 use rand::Rng;
420
421 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
422 let cs = ConstraintSystem::<Fr>::new_ref();
423
424 let mut seed = [0u8; 32];
425 rng.fill(&mut seed);
426
427 let mut input = [0u8; 32];
428 rng.fill(&mut input);
429
430 let seed_var = Blake2sGadget::new_seed(cs.clone(), &seed);
431 let input_var =
432 UInt8::new_witness_vec(r1cs_core::ns!(cs, "declare_input"), &input).unwrap();
433 let out = B2SPRF::evaluate(&seed, &input).unwrap();
434 let actual_out_var = <Blake2sGadget as PRFGadget<_, Fr>>::OutputVar::new_witness(
435 r1cs_core::ns!(cs, "declare_output"),
436 || Ok(out),
437 )
438 .unwrap();
439
440 let output_var = Blake2sGadget::evaluate(&seed_var, &input_var).unwrap();
441 output_var.enforce_equal(&actual_out_var).unwrap();
442
443 if !cs.is_satisfied().unwrap() {
444 println!(
445 "which is unsatisfied: {:?}",
446 cs.which_is_unsatisfied().unwrap()
447 );
448 }
449 assert!(cs.is_satisfied().unwrap());
450 }
451
452 #[test]
453 fn test_blake2s_precomp_constraints() {
454 // Test that 512 fixed leading bits (constants)
455 // doesn't result in more constraints.
456
457 let cs = ConstraintSystem::<Fr>::new_ref();
458 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
459 let input_bits: Vec<_> = (0..512)
460 .map(|_| Boolean::constant(rng.gen()))
461 .chain((0..512).map(|_| {
462 Boolean::new_witness(r1cs_core::ns!(cs, "input bit"), || Ok(true)).unwrap()
463 }))
464 .collect();
465 evaluate_blake2s(&input_bits).unwrap();
466 assert!(cs.is_satisfied().unwrap());
467 assert_eq!(cs.num_constraints(), 21792);
468 }
469
470 #[test]
471 fn test_blake2s_constant_constraints() {
472 let cs = ConstraintSystem::<Fr>::new_ref();
473 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
474 let input_bits: Vec<_> = (0..512)
475 .map(|_| Boolean::<Fr>::constant(rng.gen()))
476 .collect();
477 evaluate_blake2s(&input_bits).unwrap();
478 assert_eq!(cs.num_constraints(), 0);
479 }
480
481 #[test]
482 fn test_blake2s() {
483 let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
484
485 for input_len in (0..32).chain((32..256).filter(|a| a % 8 == 0)) {
486 use digest::*;
487 let mut h = VarBlake2s::new_keyed(&[], 32);
488
489 let data: Vec<u8> = (0..input_len).map(|_| rng.gen()).collect();
490
491 h.input(&data);
492
493 let mut hash_result = Vec::with_capacity(h.output_size());
494 h.variable_result(|res| hash_result.extend_from_slice(res));
495
496 let cs = ConstraintSystem::<Fr>::new_ref();
497
498 let mut input_bits = vec![];
499
500 for input_byte in data.into_iter() {
501 for bit_i in 0..8 {
502 let cs = r1cs_core::ns!(cs, "input bit");
503
504 input_bits.push(
505 Boolean::new_witness(cs, || Ok((input_byte >> bit_i) & 1u8 == 1u8))
506 .unwrap(),
507 );
508 }
509 }
510
511 let r = evaluate_blake2s(&input_bits).unwrap();
512
513 assert!(cs.is_satisfied().unwrap());
514
515 let mut s = hash_result
516 .iter()
517 .flat_map(|&byte| (0..8).map(move |i| (byte >> i) & 1u8 == 1u8));
518
519 for chunk in r {
520 for b in chunk.to_bits_le() {
521 match b {
522 Boolean::Is(b) => {
523 assert!(s.next().unwrap() == b.value().unwrap());
524 }
525 Boolean::Not(b) => {
526 assert!(s.next().unwrap() != b.value().unwrap());
527 }
528 Boolean::Constant(b) => {
529 assert!(input_len == 0);
530 assert!(s.next().unwrap() == b);
531 }
532 }
533 }
534 }
535 }
536 }
537}