kimchi/circuits/polynomials/keccak/
mod.rs

1//! Keccak hash module
2pub mod constants;
3pub mod witness;
4
5use crate::circuits::expr::constraints::ExprOps;
6use ark_ff::PrimeField;
7
8use self::constants::{DIM, QUARTERS, RATE_IN_BYTES, ROUNDS};
9use super::super::berkeley_columns::BerkeleyChallengeTerm;
10
11#[macro_export]
12macro_rules! grid {
13    (5, $v:expr) => {{
14        |x: usize| $v[x].clone()
15    }};
16    (20, $v:expr) => {{
17        |x: usize, q: usize| $v[q + QUARTERS * x].clone()
18    }};
19    (80, $v:expr) => {{
20        |i: usize, x: usize, q: usize| $v[q + QUARTERS * (x + DIM * i)].clone()
21    }};
22    (100, $v:expr) => {{
23        |y: usize, x: usize, q: usize| $v[q + QUARTERS * (x + DIM * y)].clone()
24    }};
25    (400, $v:expr) => {{
26        |i: usize, y: usize, x: usize, q: usize| {
27            $v[q + QUARTERS * (x + DIM * (y + DIM * i))].clone()
28        }
29    }};
30}
31
32/// Creates the 5x5 table of rotation bits for Keccak modulo 64
33/// | x \ y |  0 |  1 |  2 |  3 |  4 |
34/// | ----- | -- | -- | -- | -- | -- |
35/// | 0     |  0 | 36 |  3 | 41 | 18 |
36/// | 1     |  1 | 44 | 10 | 45 |  2 |
37/// | 2     | 62 |  6 | 43 | 15 | 61 |
38/// | 3     | 28 | 55 | 25 | 21 | 56 |
39/// | 4     | 27 | 20 | 39 |  8 | 14 |
40/// Note that the order of the indexing is `[y][x]` to match the encoding of the witness algorithm
41pub const OFF: [[u64; DIM]; DIM] = [
42    [0, 1, 62, 28, 27],
43    [36, 44, 6, 55, 20],
44    [3, 10, 43, 25, 39],
45    [41, 45, 15, 21, 8],
46    [18, 2, 61, 56, 14],
47];
48
49/// Contains the 24 round constants for Keccak
50pub const RC: [u64; ROUNDS] = [
51    0x0000000000000001,
52    0x0000000000008082,
53    0x800000000000808a,
54    0x8000000080008000,
55    0x000000000000808b,
56    0x0000000080000001,
57    0x8000000080008081,
58    0x8000000000008009,
59    0x000000000000008a,
60    0x0000000000000088,
61    0x0000000080008009,
62    0x000000008000000a,
63    0x000000008000808b,
64    0x800000000000008b,
65    0x8000000000008089,
66    0x8000000000008003,
67    0x8000000000008002,
68    0x8000000000000080,
69    0x000000000000800a,
70    0x800000008000000a,
71    0x8000000080008081,
72    0x8000000000008080,
73    0x0000000080000001,
74    0x8000000080008008,
75];
76
77/// Naive Keccak structure
78pub struct Keccak {}
79
80/// Trait containing common operations for optimized Keccak
81impl Keccak {
82    /// Composes a vector of 4 dense quarters into the dense full u64 word
83    pub fn compose(quarters: &[u64]) -> u64 {
84        quarters[0] + (1 << 16) * quarters[1] + (1 << 32) * quarters[2] + (1 << 48) * quarters[3]
85    }
86    /// Takes a dense u64 word and decomposes it into a vector of 4 dense quarters.
87    /// The first element of the vector corresponds to the 16 least significant bits.
88    pub fn decompose(word: u64) -> Vec<u64> {
89        vec![
90            word % (1 << 16),
91            (word / (1 << 16)) % (1 << 16),
92            (word / (1 << 32)) % (1 << 16),
93            (word / (1 << 48)) % (1 << 16),
94        ]
95    }
96
97    /// Expands a quarter of a word into the sparse representation as a u64
98    pub fn expand(quarter: u64) -> u64 {
99        u64::from_str_radix(&format!("{:b}", quarter), 16).unwrap()
100    }
101
102    /// Expands a u64 word into a vector of 4 sparse u64 quarters
103    pub fn expand_word<F: PrimeField, T: ExprOps<F, BerkeleyChallengeTerm>>(word: u64) -> Vec<T> {
104        Self::decompose(word)
105            .iter()
106            .map(|q| T::literal(F::from(Self::expand(*q))))
107            .collect::<Vec<T>>()
108    }
109
110    /// Returns the expansion of the 4 dense decomposed quarters of a word where
111    /// the first expanded element corresponds to the 16 least significant bits of the word.
112    pub fn sparse(word: u64) -> Vec<u64> {
113        Self::decompose(word)
114            .iter()
115            .map(|q| Self::expand(*q))
116            .collect::<Vec<u64>>()
117    }
118    /// From each quarter in sparse representation, it computes its 4 resets.
119    /// The resulting vector contains 4 times as many elements as the input.
120    /// The output is placed in the vector as [shift0, shift1, shift2, shift3]
121    pub fn shift(state: &[u64]) -> Vec<u64> {
122        let n = state.len();
123        let mut shifts = vec![0; QUARTERS * n];
124        let aux = Self::expand(0xFFFF);
125        for (i, term) in state.iter().enumerate() {
126            shifts[i] = aux & term; // shift0 = reset0
127            shifts[n + i] = ((aux << 1) & term) / 2; // shift1 = reset1/2
128            shifts[2 * n + i] = ((aux << 2) & term) / 4; // shift2 = reset2/4
129            shifts[3 * n + i] = ((aux << 3) & term) / 8; // shift3 = reset3/8
130        }
131        shifts
132    }
133
134    /// From a vector of shifts, resets the underlying value returning only shift0
135    /// Note that shifts is always a vector whose length is a multiple of 4.
136    pub fn reset(shifts: &[u64]) -> Vec<u64> {
137        shifts[0..shifts.len() / QUARTERS].to_vec()
138    }
139
140    /// From a canonical expanded state, obtain the corresponding 16-bit dense terms
141    pub fn collapse(state: &[u64]) -> Vec<u64> {
142        state
143            .iter()
144            .map(|&reset| u64::from_str_radix(&format!("{:x}", reset), 2).unwrap())
145            .collect::<Vec<u64>>()
146    }
147
148    /// Outputs the state into dense quarters of 16-bits each in little endian order
149    pub fn quarters(state: &[u8]) -> Vec<u64> {
150        let mut quarters = vec![];
151        for pair in state.chunks(2) {
152            quarters.push(u16::from_le_bytes([pair[0], pair[1]]) as u64);
153        }
154        quarters
155    }
156
157    /// On input a vector of 16-bit dense quarters, outputs a vector of 8-bit bytes in the right order for Keccak
158    pub fn bytestring(dense: &[u64]) -> Vec<u64> {
159        dense
160            .iter()
161            .map(|x| vec![x % 256, x / 256])
162            .collect::<Vec<Vec<u64>>>()
163            .iter()
164            .flatten()
165            .copied()
166            .collect()
167    }
168
169    /// On input a 200-byte vector, generates a vector of 100 expanded quarters representing the 1600-bit state
170    pub fn expand_state(state: &[u8]) -> Vec<u64> {
171        let mut expanded = vec![];
172        for pair in state.chunks(2) {
173            let quarter = u16::from_le_bytes([pair[0], pair[1]]);
174            expanded.push(Self::expand(quarter as u64));
175        }
176        expanded
177    }
178
179    /// On input a length, returns the smallest multiple of RATE_IN_BYTES that is greater than the bytelength.
180    /// That means that if the input has a length that is a multiple of the RATE_IN_BYTES, then
181    /// it needs to add one whole block of RATE_IN_BYTES bytes just for padding purposes.
182    pub fn padded_length(bytelength: usize) -> usize {
183        Self::num_blocks(bytelength) * RATE_IN_BYTES
184    }
185
186    /// Pads the message with the 10*1 rule until reaching a length that is a multiple of the rate
187    pub fn pad(message: &[u8]) -> Vec<u8> {
188        let msg_len = message.len();
189        let pad_len = Self::padded_length(msg_len);
190        let mut padded = vec![0; pad_len];
191        for (i, byte) in message.iter().enumerate() {
192            padded[i] = *byte;
193        }
194        padded[msg_len] = 0x01;
195        padded[pad_len - 1] += 0x80;
196
197        padded
198    }
199
200    /// Number of blocks to be absorbed on input a given preimage bytelength
201    pub fn num_blocks(bytelength: usize) -> usize {
202        bytelength / RATE_IN_BYTES + 1
203    }
204}
205
206#[cfg(test)]
207mod tests {
208
209    use rand::{rngs::StdRng, thread_rng, Rng};
210    use rand_core::SeedableRng;
211
212    use super::*;
213
214    #[test]
215    // Shows that the expansion of the 16-bit dense quarters into 64-bit sparse quarters
216    // corresponds to the binary representation of the 16-bit dense quarter.
217    fn test_bitwise_sparse_representation() {
218        assert_eq!(Keccak::expand(0xFFFF), 0x1111111111111111);
219        assert_eq!(Keccak::expand(0x0000), 0x0000000000000000);
220        assert_eq!(Keccak::expand(0x1234), 0x0001001000110100)
221    }
222
223    #[test]
224    // Tests that composing and decomposition are the inverse of each other,
225    // and the order of the quarters is the desired one.
226    fn test_compose_decompose() {
227        let word: u64 = 0x70d324ac9215fd8e;
228        let dense = Keccak::decompose(word);
229        let expected_dense = [0xfd8e, 0x9215, 0x24ac, 0x70d3];
230        for i in 0..QUARTERS {
231            assert_eq!(dense[i], expected_dense[i]);
232        }
233        assert_eq!(word, Keccak::compose(&dense));
234    }
235
236    #[test]
237    // Tests that expansion works as expected with one quarter word
238    fn test_quarter_expansion() {
239        let quarter: u16 = 0b01011010111011011; // 0xB5DB
240        let expected_expansion = 0b0001000000010001000000010000000100010001000000010001000000010001; // 0x01011010111011011
241        assert_eq!(expected_expansion, Keccak::expand(quarter as u64));
242    }
243
244    #[test]
245    // Tests that expansion of decomposed quarters works as expected
246    fn test_sparse() {
247        let word: u64 = 0x1234567890abcdef;
248        let sparse = Keccak::sparse(word);
249        let expected_sparse: Vec<u64> = vec![
250            0x1100110111101111, // 0xcdef
251            0x1001000010101011, // 0x90ab
252            0x0101011001111000, // 0x5678
253            0x0001001000110100, // 0x1234
254        ];
255        for i in 0..QUARTERS {
256            assert_eq!(sparse[i], expected_sparse[i]);
257        }
258    }
259
260    #[test]
261    // Tests that the shifts are computed correctly
262    fn test_shifts() {
263        let seed: [u8; 32] = thread_rng().gen();
264        eprintln!("Seed: {:?}", seed);
265        let mut rng = StdRng::from_seed(seed);
266        let word: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
267        let sparse = Keccak::sparse(word);
268        let shifts = Keccak::shift(&sparse);
269        for i in 0..QUARTERS {
270            assert_eq!(
271                sparse[i],
272                shifts[i] + shifts[4 + i] * 2 + shifts[8 + i] * 4 + shifts[12 + i] * 8
273            )
274        }
275    }
276
277    #[test]
278    // Checks that reset function returns shift0, as the first positions of the shifts vector
279    fn test_reset() {
280        let seed: [u8; 32] = thread_rng().gen();
281        eprintln!("Seed: {:?}", seed);
282        let mut rng = StdRng::from_seed(seed);
283        let word: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
284        let shifts = Keccak::shift(&Keccak::sparse(word));
285        let reset = Keccak::reset(&shifts);
286        assert_eq!(reset.len(), 4);
287        assert_eq!(shifts.len(), 16);
288        for i in 0..QUARTERS {
289            assert_eq!(reset[i], shifts[i])
290        }
291    }
292
293    #[test]
294    // Checks that one can obtain the original word from the resets of the expanded word
295    fn test_collapse() {
296        let seed: [u8; 32] = thread_rng().gen();
297        eprintln!("Seed: {:?}", seed);
298        let mut rng = StdRng::from_seed(seed);
299        let word: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
300        let dense = Keccak::compose(&Keccak::collapse(&Keccak::reset(&Keccak::shift(
301            &Keccak::sparse(word),
302        ))));
303        assert_eq!(word, dense);
304    }
305
306    #[test]
307    // Checks that concatenating the maximum number of carries (15 per bit) result
308    // in the same original dense word, and just one more carry results in a different word
309    fn test_max_carries() {
310        let seed: [u8; 32] = thread_rng().gen();
311        eprintln!("Seed: {:?}", seed);
312        let mut rng = StdRng::from_seed(seed);
313        let word: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
314        let carries = 0xEEEE;
315        // add a few carry bits to the canonical representation
316        let mut sparse = Keccak::sparse(word)
317            .iter()
318            .map(|x| *x + carries)
319            .collect::<Vec<u64>>();
320        let dense = Keccak::compose(&Keccak::collapse(&Keccak::reset(&Keccak::shift(&sparse))));
321        assert_eq!(word, dense);
322
323        sparse[0] += 1;
324        let wrong_dense =
325            Keccak::compose(&Keccak::collapse(&Keccak::reset(&Keccak::shift(&sparse))));
326        assert_ne!(word, wrong_dense);
327    }
328
329    #[test]
330    // Tests that the XOR can be represented in the 4i-th
331    // positions of the addition of sparse representations
332    fn test_sparse_xor() {
333        let seed: [u8; 32] = thread_rng().gen();
334        eprintln!("Seed: {:?}", seed);
335        let mut rng = StdRng::from_seed(seed);
336        let a: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
337        let b: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
338        let xor = a ^ b;
339
340        let sparse_a = Keccak::sparse(a);
341        let sparse_b = Keccak::sparse(b);
342
343        // compute xor as sum of a and b
344        let sparse_sum = sparse_a
345            .iter()
346            .zip(sparse_b.iter())
347            .map(|(a, b)| a + b)
348            .collect::<Vec<u64>>();
349        let reset_sum = Keccak::reset(&Keccak::shift(&sparse_sum));
350
351        assert_eq!(Keccak::sparse(xor), reset_sum);
352    }
353
354    #[test]
355    // Tests that the AND can be represented in the (4i+1)-th positions of the
356    // addition of canonical sparse representations
357    fn test_sparse_and() {
358        let seed: [u8; 32] = thread_rng().gen();
359        eprintln!("Seed: {:?}", seed);
360        let mut rng = StdRng::from_seed(seed);
361        let a: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
362        let b: u64 = rng.gen_range(0..2u128.pow(64)) as u64;
363        let and = a & b;
364
365        let sparse_a = Keccak::sparse(a);
366        let sparse_b = Keccak::sparse(b);
367
368        // compute and as carries of sum of a and b
369        let sparse_sum = sparse_a
370            .iter()
371            .zip(sparse_b.iter())
372            .map(|(a, b)| a + b)
373            .collect::<Vec<u64>>();
374        let carries_sum = &Keccak::shift(&sparse_sum)[4..8];
375
376        assert_eq!(Keccak::sparse(and), carries_sum);
377    }
378
379    #[test]
380    // Tests that the NOT can be represented as subtraction with the expansion of
381    // the 16-bit dense quarter.
382    fn test_sparse_not() {
383        let seed: [u8; 32] = thread_rng().gen();
384        eprintln!("Seed: {:?}", seed);
385        let mut rng = StdRng::from_seed(seed);
386        let word = rng.gen_range(0..2u64.pow(16));
387        let expanded = Keccak::expand(word);
388
389        // compute not as subtraction with expand all ones
390        let all_ones = 0xFFFF;
391        let not = all_ones - word;
392        let sparse_not = Keccak::expand(all_ones) - expanded;
393
394        assert_eq!(not, Keccak::collapse(&[sparse_not])[0]);
395    }
396
397    #[test]
398    // Checks that the padding length is correctly computed
399    fn test_pad_length() {
400        assert_eq!(Keccak::padded_length(0), RATE_IN_BYTES);
401        assert_eq!(Keccak::padded_length(1), RATE_IN_BYTES);
402        assert_eq!(Keccak::padded_length(RATE_IN_BYTES - 1), RATE_IN_BYTES);
403        // If input is already a multiple of RATE bytes, it needs to add a whole new block just for padding
404        assert_eq!(Keccak::padded_length(RATE_IN_BYTES), 2 * RATE_IN_BYTES);
405        assert_eq!(
406            Keccak::padded_length(RATE_IN_BYTES * 2 - 1),
407            2 * RATE_IN_BYTES
408        );
409        assert_eq!(Keccak::padded_length(RATE_IN_BYTES * 2), 3 * RATE_IN_BYTES);
410    }
411
412    #[test]
413    // Checks that the padding is correctly computed
414    fn test_pad() {
415        let message = vec![0xFF; RATE_IN_BYTES - 1];
416        let padded = Keccak::pad(&message);
417        assert_eq!(padded.len(), RATE_IN_BYTES);
418        assert_eq!(padded[padded.len() - 1], 0x81);
419
420        let message = vec![0x01; RATE_IN_BYTES];
421        let padded = Keccak::pad(&message);
422        assert_eq!(padded.len(), 2 * RATE_IN_BYTES);
423        assert_eq!(padded[message.len()], 0x01);
424        assert_eq!(padded[padded.len() - 1], 0x80);
425    }
426}
kimchi/circuits/polynomials/keccak/mod.rs

kimchi/circuits/polynomials/keccak/
mod.rs
