snarkvm_circuit_algorithms/keccak/
mod.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16mod hash;
17
18#[cfg(all(test, feature = "console"))]
19use snarkvm_circuit_types::environment::assert_scope;
20#[cfg(test)]
21use snarkvm_utilities::{TestRng, Uniform};
22
23use crate::Hash;
24use snarkvm_circuit_types::{Boolean, U64, environment::prelude::*};
25
26/// The Keccak-224 hash function.
27pub type Keccak224<E> = Keccak<E, { KeccakType::Keccak as u8 }, 224>;
28/// The Keccak-256 hash function.
29pub type Keccak256<E> = Keccak<E, { KeccakType::Keccak as u8 }, 256>;
30/// The Keccak-384 hash function.
31pub type Keccak384<E> = Keccak<E, { KeccakType::Keccak as u8 }, 384>;
32/// The Keccak-512 hash function.
33pub type Keccak512<E> = Keccak<E, { KeccakType::Keccak as u8 }, 512>;
34
35/// The SHA3-224 hash function.
36pub type Sha3_224<E> = Keccak<E, { KeccakType::Sha3 as u8 }, 224>;
37/// The SHA3-256 hash function.
38pub type Sha3_256<E> = Keccak<E, { KeccakType::Sha3 as u8 }, 256>;
39/// The SHA3-384 hash function.
40pub type Sha3_384<E> = Keccak<E, { KeccakType::Sha3 as u8 }, 384>;
41/// The SHA3-512 hash function.
42pub type Sha3_512<E> = Keccak<E, { KeccakType::Sha3 as u8 }, 512>;
43
44/// A helper to specify the hash type.
45enum KeccakType {
46    Keccak,
47    Sha3,
48}
49
50/// The rows and columns are 5-bit lanes.
51const MODULO: usize = 5;
52/// The permutation type `l`.
53const L: usize = 6;
54/// The number of rounds in a full-round operation.
55const NUM_ROUNDS: usize = 12 + 2 * L;
56/// The permutation width `b`.
57const PERMUTATION_WIDTH: usize = 1600;
58
59/// The sponge construction `Sponge[f, pad, r]` is a function that takes a variable-length input
60/// and produces a fixed-length output (the hash value).
61///
62/// The permutation `f` is a function that takes a fixed-length input and produces a fixed-length output,
63/// defined as `f = Keccak-f[b]`, where `b := 25 * 2^l` is the width of the permutation,
64/// and `l` is the log width of the permutation.
65/// For our case, `l = 6`, thus `b = 1600`.
66///
67/// The padding rule `pad` is a function that takes a variable-length input and produces a fixed-length output.
68/// In Keccak, `pad` is a multi-rate padding, defined as `pad(M) = M || 0x01 || 0x00…0x00 || 0x80`,
69/// where `M` is the input data, and `0x01 || 0x00…0x00 || 0x80` is the padding.
70/// In SHA-3, `pad` is a SHAKE, defined as `pad(M) = M || 0x06 || 0x00…0x00 || 0x80`,
71/// where `M` is the input data, and `0x06 || 0x00…0x00 || 0x80` is the padding.
72///
73/// The bitrate `r` is the number of bits that are absorbed into the sponge state in each iteration
74/// of the absorbing phase.
75///
76/// In addition, the capacity is defined as `c := b - r`.
77#[derive(Clone, Debug, Default)]
78pub struct Keccak<E: Environment, const TYPE: u8, const VARIANT: usize> {
79    /// The round constants `RC[t] ∈ GF(2)` are defined as the
80    /// output of a linear feedback shift register (LFSR).
81    round_constants: Vec<U64<E>>,
82    /// Precomputations for the ρ step.
83    rotl: [usize; MODULO * MODULO],
84}
85
86impl<E: Environment, const TYPE: u8, const VARIANT: usize> Keccak<E, TYPE, VARIANT> {
87    /// Initializes a new Keccak hash function.
88    pub fn new() -> Self {
89        Self {
90            round_constants: Self::ROUND_CONSTANTS.into_iter().map(|e| U64::constant(console::U64::new(e))).collect(),
91            rotl: Self::rotl_offsets(),
92        }
93    }
94}
95
96impl<E: Environment, const TYPE: u8, const VARIANT: usize> Keccak<E, TYPE, VARIANT> {
97    /// The values `ROUND_CONSTANTS[t] ∈ GF(2)` are defined as the
98    /// output of a binary linear feedback shift register (LFSR):
99    /// ```text
100    /// ROUND_CONSTANTS[t] = (x^t) mod (x^8 + x^6 + x^5 + x^4 + 1) mod x in GF(2)[x]
101    /// ```
102    /// where `t ∈ {0, 1, …, NUM_ROUNDS}`.
103    const ROUND_CONSTANTS: [u64; NUM_ROUNDS] = [
104        0x0000000000000001,
105        0x0000000000008082,
106        0x800000000000808A,
107        0x8000000080008000,
108        0x000000000000808B,
109        0x0000000080000001,
110        0x8000000080008081,
111        0x8000000000008009,
112        0x000000000000008A,
113        0x0000000000000088,
114        0x0000000080008009,
115        0x000000008000000A,
116        0x000000008000808B,
117        0x800000000000008B,
118        0x8000000000008089,
119        0x8000000000008003,
120        0x8000000000008002,
121        0x8000000000000080,
122        0x000000000000800A,
123        0x800000008000000A,
124        0x8000000080008081,
125        0x8000000000008080,
126        0x0000000080000001,
127        0x8000000080008008,
128    ];
129
130    /// Returns the ROTL offsets for the ρ step.
131    ///
132    /// The offsets are defined as follows:
133    /// ```text
134    /// for t = 0 to 23 do
135    ///   offset[t] = (t + 1)(t + 2)/2
136    /// end for
137    /// ```
138    ///
139    /// This method transposes the offsets to match the access pattern (i.e. for y, then for x).
140    fn rotl_offsets() -> [usize; MODULO * MODULO] {
141        let mut rotl = [0; MODULO * MODULO];
142        let mut x: usize = 1;
143        let mut y: usize = 0;
144
145        for t in 0..=23 {
146            let rotr = ((t + 1) * (t + 2) / 2) % 64;
147            rotl[x + (y * MODULO)] = (64 - rotr) % 64;
148
149            // Update x and y.
150            let x_old = x;
151            x = y;
152            y = (2 * x_old + 3 * y) % MODULO;
153        }
154        rotl
155    }
156}
snarkvm_circuit_algorithms/keccak/mod.rs

snarkvm_circuit_algorithms/keccak/
mod.rs
