kimchi/circuits/polynomials/keccak/
mod.rs

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

kimchi/circuits/polynomials/keccak/
mod.rs
