KECCAAAAAAAAAAK. More...

#include <keccak.hpp>

Classes
struct	keccak_state

Public Types
using	witness_ct = stdlib::witness_t< Builder >

using	field_ct = stdlib::field_t< Builder >

using	bool_ct = stdlib::bool_t< Builder >

using	byte_array_ct = stdlib::byte_array< Builder >

Static Public Member Functions
static constexpr uint256_t	convert_to_sparse (uint256_t input)
	Convert a binary integer into a base11 integer.

static constexpr uint256_t	normalize_sparse (uint256_t input)
	Normalize a base-11 integer where each base value can be > 1.

static constexpr std::array< uint256_t, NUM_KECCAK_ROUNDS >	get_sparse_round_constants ()
	Get the sparse round constants object.

static constexpr uint256_t	get_chi_offset ()
	Compute the constant offset added in the `Chi` round.

template<size_t lane_index>
static field_t< Builder >	normalize_and_rotate (const field_ct &limb, field_ct &msb)
	Normalize a base-11 limb and left-rotate by keccak::ROTATIONS[lane_index] bits. This method also extracts the most significant bit of the normalised rotated limb. Used in the RHO and IOTA rounds and in `sponge_absorb`.

static void	compute_twisted_state (keccak_state &internal)
	Compute twisted representation of hash lane.

static void	theta (keccak_state &state)
	THETA round.

static void	rho (keccak_state &state)
	RHO round.

static void	pi (keccak_state &state)
	PI.

static void	chi (keccak_state &state)
	CHI.

static void	iota (keccak_state &state, size_t round)
	IOTA.

static void	sponge_absorb (keccak_state &internal, const std::vector< field_ct > &input_buffer, const std::vector< field_ct > &msb_buffer)

static byte_array_ct	sponge_squeeze (keccak_state &internal)

static void	keccakf1600 (keccak_state &state)

static byte_array_ct	hash (byte_array_ct &input)

static std::vector< field_ct >	format_input_lanes (byte_array_ct &input)
	Convert the input buffer into 8-bit keccak lanes in little-endian form. Additionally, insert padding bytes if required, and add the keccak terminating bytes 0x1/0x80 (0x1 inserted after the final byte of input data) (0x80 inserted at the end of the final block)

static std::vector< uint8_t >	hash_native (const std::vector< uint8_t > &data)

static byte_array_ct	hash_using_permutation_opcode (byte_array_ct &input)

static std::array< field_ct, NUM_KECCAK_LANES >	permutation_opcode (std::array< field_ct, NUM_KECCAK_LANES > state, Builder *context)

static void	sponge_absorb_with_permutation_opcode (keccak_state &internal, std::vector< field_ct > &input_buffer, const size_t input_size)

static std::array< field_ct, NUM_KECCAK_LANES >	extended_2_normal (keccak_state &internal)

static byte_array_ct	sponge_squeeze_for_permutation_opcode (std::array< field_ct, NUM_KECCAK_LANES > lanes, Builder *context)

Static Public Attributes
static constexpr uint256_t	BASE = 11

static constexpr size_t	BITS = 256

static constexpr size_t	WORD_SIZE = 8

static constexpr size_t	BLOCK_SIZE = (1600 - BITS * 2) / WORD_SIZE

static constexpr size_t	LIMBS_PER_BLOCK = BLOCK_SIZE / 8

static constexpr size_t	NUM_KECCAK_ROUNDS = 24

static constexpr size_t	NUM_KECCAK_LANES = 25

static constexpr std::array< uint64_t, NUM_KECCAK_ROUNDS >	RC

static constexpr std::array< size_t, NUM_KECCAK_LANES >	ROTATIONS

static constexpr std::array< uint256_t, NUM_KECCAK_ROUNDS >	SPARSE_RC = get_sparse_round_constants()

static constexpr uint256_t	CHI_OFFSET = get_chi_offset()

Detailed Description

template<typename Builder>
class bb::stdlib::keccak< Builder >

KECCAAAAAAAAAAK.

Creates constraints that evaluate the Keccak256 hash algorithm.

Ultra only due to heavy lookup table use.

Current cost 17,329 constraints for a 1-block hash using small(ish) lookup tables (total size < 2^64)

Template Parameters

Builder

Definition at line 25 of file keccak.hpp.

Member Typedef Documentation

◆ bool_ct

template<typename Builder >

using bb::stdlib::keccak< Builder >::bool_ct = stdlib::bool_t<Builder>

Definition at line 29 of file keccak.hpp.

◆ byte_array_ct

template<typename Builder >

using bb::stdlib::keccak< Builder >::byte_array_ct = stdlib::byte_array<Builder>

Definition at line 30 of file keccak.hpp.

◆ field_ct

template<typename Builder >

using bb::stdlib::keccak< Builder >::field_ct = stdlib::field_t<Builder>

Definition at line 28 of file keccak.hpp.

◆ witness_ct

template<typename Builder >

using bb::stdlib::keccak< Builder >::witness_ct = stdlib::witness_t<Builder>

Definition at line 27 of file keccak.hpp.

Member Function Documentation

◆ chi()

template<typename Builder >

void bb::stdlib::keccak< Builder >::chi ( keccak_state & internal )

static

CHI.

The CHI round applies the following logic to the hash lanes: A XOR (~B AND C)

In base-11 representation we can create an equivalent linear operation: 1 + 2A - B + C

Output values will range from [0, 1, 2, 3, 4] and are mapped back into [0, 1] via the KECCAK_CHI_OUTPUT lookup table

N.B. the KECCAK_CHI_OUTPUT table also has a column for the most significant bit of each lookup. We use this to create a 'twisted representation of each hash lane (see THETA comments for more details)

Template Parameters

Builder

Definition at line 438 of file keccak.cpp.

◆ compute_twisted_state()

template<typename Builder >

void bb::stdlib::keccak< Builder >::compute_twisted_state ( keccak_state & internal )

static

Compute twisted representation of hash lane.

The THETA round requires computation of XOR(A, ROTL(B, 1))

We do this via a 'twisted' base-11 representation.

If the bit slices for a regular variable are arranged [b63, ..., b0], the twisted representation is a 65-bit variable [b63, ..., b0, b63]

The equivalent of XOR(A, ROTL(B, 1)) is A.twist + 2B.twist (in base-11 form) The output is present in bit slices 1-64

Template Parameters

Builder

Parameters

internal

Definition at line 199 of file keccak.cpp.

◆ convert_to_sparse()

template<typename Builder >

static constexpr uint256_t bb::stdlib::keccak< Builder >::convert_to_sparse ( uint256_t input )

inlinestaticconstexpr

Convert a binary integer into a base11 integer.

Input = \sum_{i=0}^63 b_i * 2^i Output = \sum_{i=0}^63 b_i * 11^i

Parameters

input

Returns: constexpr uint256_t sparse form of input

Definition at line 76 of file keccak.hpp.

◆ extended_2_normal()

template<typename Builder >

std::array< field_t< Builder >, keccak< Builder >::NUM_KECCAK_LANES > bb::stdlib::keccak< Builder >::extended_2_normal ( keccak_state & internal )

static

Definition at line 748 of file keccak.cpp.

◆ format_input_lanes()

template<typename Builder >

std::vector< field_t< Builder > > bb::stdlib::keccak< Builder >::format_input_lanes ( byte_array_ct & input )

static

Convert the input buffer into 8-bit keccak lanes in little-endian form. Additionally, insert padding bytes if required, and add the keccak terminating bytes 0x1/0x80 (0x1 inserted after the final byte of input data) (0x80 inserted at the end of the final block)

Template Parameters

Builder

Parameters

input

Returns: std::vector<field_t<Builder>>

Definition at line 559 of file keccak.cpp.

◆ get_chi_offset()

template<typename Builder >

static constexpr uint256_t bb::stdlib::keccak< Builder >::get_chi_offset ( )

inlinestaticconstexpr

Compute the constant offset added in the Chi round.

We want to compute, for each bit slice of the inputs A, B, C... 1 + 2A - B + C

i.e. we need to add the constant value \sum_{i=0}^63 11^i

Returns: constexpr uint256_t

Definition at line 147 of file keccak.hpp.

◆ get_sparse_round_constants()

template<typename Builder >

static constexpr std::array< uint256_t, NUM_KECCAK_ROUNDS > bb::stdlib::keccak< Builder >::get_sparse_round_constants ( )

inlinestaticconstexpr

Get the sparse round constants object.

Returns: constexpr std::array<uint256_t, 24>

Definition at line 127 of file keccak.hpp.

◆ hash()

template<typename Builder >

stdlib::byte_array< Builder > bb::stdlib::keccak< Builder >::hash ( byte_array_ct & input )

static

Definition at line 706 of file keccak.cpp.

◆ hash_native()

template<typename Builder >

static std::vector< uint8_t > bb::stdlib::keccak< Builder >::hash_native ( const std::vector< uint8_t > & data )

inlinestatic

Definition at line 181 of file keccak.hpp.

◆ hash_using_permutation_opcode()

template<typename Builder >

stdlib::byte_array< Builder > bb::stdlib::keccak< Builder >::hash_using_permutation_opcode ( byte_array_ct & input )

static

Definition at line 680 of file keccak.cpp.

◆ iota()

template<typename Builder >

void bb::stdlib::keccak< Builder >::iota	(	keccak_state &	internal,
		size_t	round
	)

static

IOTA.

XOR first hash limb with a precomputed constant. We re-use the RHO_OUTPUT table to normalize after this operation

Template Parameters

Builder

Parameters

internal
round

Definition at line 471 of file keccak.cpp.

◆ keccakf1600()

template<typename Builder >

void bb::stdlib::keccak< Builder >::keccakf1600 ( keccak_state & state )

static

Definition at line 484 of file keccak.cpp.

◆ normalize_and_rotate()

template<typename Builder >

template<size_t lane_index>

field_t< Builder > bb::stdlib::keccak< Builder >::normalize_and_rotate	(	const field_ct &	limb,
		field_ct &	msb
	)

static

Normalize a base-11 limb and left-rotate by keccak::ROTATIONS[lane_index] bits. This method also extracts the most significant bit of the normalised rotated limb. Used in the RHO and IOTA rounds and in sponge_absorb.

Normalize process: Input v = \sum_{i=0}^63 b_i * 11^i , where b is in range [0, 1, 2] Output = \sum_{i=0}^63 (b_i & 1) * 11^i (i.e. even values go to 0)

Implementation is via a sequence of lookup tables

Template Parameters

lane_index What keccak lane are we working on?

Parameters

limb	Input limb we want to normalize and rotate
msb	(return parameter) The most significant bit of the normalized and rotated limb

Returns: field_t<Builder> The normalized and rotated output

manually construct the ReadData object required to generate plookup gate constraints. To explain in more detail: the input integer can be represented via two the bit slices [A, B] (A = left, B = right)

For example, imagine our input is a 32-bit integer A represented as: A = A3.11^24 + A2.11^16 + A1.11^8 + A0, and our output is a 32-bit integer B = B3.11^24 + B2.11^16 + B1.11^8 + B0

In this example, we want to normalize A and left-rotate by 16 bits.

Our lookup gate wire values will look like the following:

Row	C0	C1	C2
0	A3.11^24 + A2.11^16 + A1.11^8 + A0	B1.11^8 + B0	A0.msb()
1	A3.11^16 + A2.11^8 + A1	B1	A1.msb()
2	A1311^8 + A2	B3.11^8 + B2	A2.msb()
3	A3	B3	A3.msb()

The plookup table keys + values are derived via the expression:

C1[i] + C1[i+1].q1[i] = LOOKUP[C0[i] + C0[i+1].q0[i]]

(the same applies for C2, however q2[i] = 0 for all rows)

The plookup coefficients for the rows treat Column0 as a single accumulating sum, but Column1 is a pair of accumulating sums. In the above example, the q coefficient value are:

Row	Q1	Q2
0	11^8	11^8
1	11^8	0
2	11^8	11^8
3	0	0

stdlib::plookup cannot derive witnesses in the above pattern without a substantial rewrite, so we do it manually in this method!

Definition at line 37 of file keccak.cpp.

◆ normalize_sparse()

template<typename Builder >

static constexpr uint256_t bb::stdlib::keccak< Builder >::normalize_sparse ( uint256_t input )

inlinestaticconstexpr

Normalize a base-11 integer where each base value can be > 1.

Input = \sum_{i=0}^63 b_i * 11^i Output = \sum_{i=0}^63 (b_i & 1) * 11^i

(XORs are evaluated by adding integers in sparse-form and normalizing. Even = 0, Odd = 1)

Parameters

input

Returns: constexpr uint256_t

Definition at line 104 of file keccak.hpp.

◆ permutation_opcode()

template<typename Builder >

std::array< field_t< Builder >, keccak< Builder >::NUM_KECCAK_LANES > bb::stdlib::keccak< Builder >::permutation_opcode	(	std::array< field_ct, NUM_KECCAK_LANES >	state,
		Builder *	context
	)

static

Definition at line 627 of file keccak.cpp.

◆ pi()

template<typename Builder >

void bb::stdlib::keccak< Builder >::pi ( keccak_state & internal )

static

PI.

PI permutes the keccak lanes. Adds 0 constraints as this is simply a re-ordering of witnesses

Template Parameters

Builder

Parameters

internal

Definition at line 402 of file keccak.cpp.

◆ rho()

template<typename Builder >

void bb::stdlib::keccak< Builder >::rho ( keccak_state & internal )

static

RHO round.

Template Parameters

Builder

The limbs of internal.state are represented via base-11 integers limb = \sum_{i=0}^63 b_i * 11^i The value of each b_i can be in the range [0, 1, 2] due to the THETA round XOR operations

We need to do the following:

'normalize' each limb so that each b_i value is 0 or 1
left-rotate each limb as defined by the keccak rotations matrix

The KECCAK_RHO_OUTPUT lookup table is used for both. See normalize_and_rotate for more details

COST PER LIMB... 8 gates for first lane (no rotation. Lookup table is 8-bits per slice = 8 lookups for 64 bits) 10 gates for other 24 lanes (lookup sequence is split into 6 8-bit slices and 2 slices that sum to 8 bits, an addition gate is required to complete the rotation)

Total costs is 248 gates.

N.B. Can reduce lookup costs by using larger lookup tables. Current algo is optimized for lookup tables where sum of all table sizes is < 2^64

Definition at line 387 of file keccak.cpp.

◆ sponge_absorb()

template<typename Builder >

void bb::stdlib::keccak< Builder >::sponge_absorb	(	keccak_state &	internal,
		const std::vector< field_ct > &	input_buffer,
		const std::vector< field_ct > &	msb_buffer
	)

static

Definition at line 496 of file keccak.cpp.

◆ sponge_absorb_with_permutation_opcode()

template<typename Builder >

void bb::stdlib::keccak< Builder >::sponge_absorb_with_permutation_opcode	(	keccak_state &	internal,
		std::vector< field_ct > &	input_buffer,
		const size_t	input_size
	)

static

Definition at line 650 of file keccak.cpp.

◆ sponge_squeeze()

template<typename Builder >

byte_array< Builder > bb::stdlib::keccak< Builder >::sponge_squeeze ( keccak_state & internal )

static

Definition at line 526 of file keccak.cpp.

◆ sponge_squeeze_for_permutation_opcode()

template<typename Builder >

stdlib::byte_array< Builder > bb::stdlib::keccak< Builder >::sponge_squeeze_for_permutation_opcode	(	std::array< field_ct, NUM_KECCAK_LANES >	lanes,
		Builder *	context
	)

static

Definition at line 765 of file keccak.cpp.

◆ theta()

template<typename Builder >

void bb::stdlib::keccak< Builder >::theta ( keccak_state & internal )

static

THETA round.

Template Parameters

Builder

THETA consists of XOR operations as well as left rotations by 1 bit.

We represent 64-bit integers in a base-11 representation where limb = \sum_{i=0}^63 b_i * 11^i

At the start of THETA, all b_i values are either 0 or 1

We can efficiently evaluate XOR operations via simple additions! If b_i = even, this represents a bit value of 0 If b_i = odd, this represents a bit value of 1

The KECCAK_THETA_OUTPUT lookup table is used to 'normalize' base-11 integers, i.e. convert b_i values from [0, ..., 10] to [0, 1] where even == 0, odd == 1

The choice of base for our representation effects the following:

the number of normalization lookups required to avoid overflowing the base
the cost of normalization lookups

Bigger base reduces (1) but increases (2). For THETA, base-11 is optimal (I think...)

HANDLING ROTATIONS

We need to left-rotate the C[5] array by 1-bit to compute D[5]. Naive way is expensive so we cheat! When converting integers into base-11 representation, we use a lookup table column to give us the most significant bit of the integer.

This enables us to create a 'twisted' representation of the integer in base-11:

twisted_limb = (b_63) + \sum_{i=0}^63 b_i * 11^{i + 1}

e.g. if limb's bit ordering is [0, b63, ..., b1, b0 ] twisted limb bit ordering is [b63, b62, ..., b0, b63]

We want to be able to compute XOR(A, B.rotate_left(1)) and can do this via twisted representations

The equivalent in base-11 world is twisted_A * 2 + twisted_B. The output of the XOR operation exists in bit-slices 1, ..., 63 (which can be extracted by removing the least and most significant slices of the output) This is MUCH cheaper than the extra range constraints required for a naive left-rotation

Total cost of theta = 20.5 gates per 5 lanes + 25 = 127.5 per round

field_ct::accumulate can compute 5 addition operations in only 2 gates: Gate 0 wires [a0, a1, a2, a3] Gate 1 wires [b0, b1, b2, b3] b3 = a0 + a1 + a2 + a3 b2 = b3 + b0 + b1 (b2 is the output wire)

Compute D by exploiting twisted representation to get a cheap left-rotation by 1 bit

D contains 66 base-11 slices.

We need to remove the 2 most significant slices as they are artifacts of our twist operation.

We also need to 'normalize' D (i.e. convert each base value to be 0 or 1), to prevent our base from overflowing when we XOR D into internal.state

create sliced_D witness, plus lo and hi slices
validate D == lo + (sliced_D * 11) + (hi * 11^65)
feed sliced_D into KECCAK_THETA_OUTPUT lookup table

constexpr std::array<uint64_t, NUM_KECCAK_ROUNDS> bb::stdlib::keccak< Builder >::RC

staticconstexpr

Initial value:

= {
        0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000, 0x000000000000808b,
        0x0000000080000001, 0x8000000080008081, 0x8000000000008009, 0x000000000000008a, 0x0000000000000088,
        0x0000000080008009, 0x000000008000000a, 0x000000008000808b, 0x800000000000008b, 0x8000000000008089,
        0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a,
        0x8000000080008081, 0x8000000000008080, 0x0000000080000001, 0x8000000080008008
    }

Definition at line 54 of file keccak.hpp.

◆ ROTATIONS

template<typename Builder >

constexpr std::array<size_t, NUM_KECCAK_LANES> bb::stdlib::keccak< Builder >::ROTATIONS

staticconstexpr

Initial value:

= {
        0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14,
    }

Definition at line 63 of file keccak.hpp.

◆ SPARSE_RC

template<typename Builder >

constexpr std::array<uint256_t, NUM_KECCAK_ROUNDS> bb::stdlib::keccak< Builder >::SPARSE_RC = get_sparse_round_constants()

staticconstexpr

Definition at line 135 of file keccak.hpp.

◆ WORD_SIZE

template<typename Builder >

constexpr size_t bb::stdlib::keccak< Builder >::WORD_SIZE = 8

staticconstexpr

Definition at line 39 of file keccak.hpp.

The documentation for this class was generated from the following files:

src/barretenberg/stdlib/hash/keccak/keccak.hpp
src/barretenberg/stdlib/hash/keccak/keccak.cpp

Classes

Public Types

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ bool_ct

◆ byte_array_ct

◆ field_ct

◆ witness_ct

Member Function Documentation

◆ chi()

◆ compute_twisted_state()

◆ convert_to_sparse()

◆ extended_2_normal()

◆ format_input_lanes()

◆ get_chi_offset()

◆ get_sparse_round_constants()

◆ hash()

◆ hash_native()

◆ hash_using_permutation_opcode()

◆ iota()

◆ keccakf1600()

◆ normalize_and_rotate()

◆ normalize_sparse()

◆ permutation_opcode()

◆ pi()

◆ rho()

◆ sponge_absorb()

◆ sponge_absorb_with_permutation_opcode()

◆ sponge_squeeze()

◆ sponge_squeeze_for_permutation_opcode()

◆ theta()

HANDLING ROTATIONS

Member Data Documentation

◆ BASE

◆ BITS

◆ BLOCK_SIZE

◆ CHI_OFFSET

◆ LIMBS_PER_BLOCK

◆ NUM_KECCAK_LANES

◆ NUM_KECCAK_ROUNDS

◆ RC

◆ ROTATIONS

◆ SPARSE_RC

◆ WORD_SIZE