bb::plookup::sha256_tables Namespace Reference

Functions
plookup::BasicTable	generate_witness_extension_normalization_table (BasicTableId id, const size_t table_index)
BasicTable	generate_choose_normalization_table (BasicTableId id, const size_t table_index)
BasicTable	generate_majority_normalization_table (BasicTableId id, const size_t table_index)
MultiTable	get_witness_extension_output_table (const MultiTableId id=SHA256_WITNESS_OUTPUT)
MultiTable	get_choose_output_table (const MultiTableId id=SHA256_CH_OUTPUT)
MultiTable	get_majority_output_table (const MultiTableId id=SHA256_MAJ_OUTPUT)
std::array< bb::fr, 3 >	get_majority_rotation_multipliers ()
std::array< bb::fr, 3 >	get_choose_rotation_multipliers ()
MultiTable	get_witness_extension_input_table (const MultiTableId id=SHA256_WITNESS_INPUT)
MultiTable	get_choose_input_table (const MultiTableId id=SHA256_CH_INPUT)
MultiTable	get_majority_input_table (const MultiTableId id=SHA256_MAJ_INPUT)

Function Documentation

generate_choose_normalization_table()

BasicTable bb::plookup::sha256_tables::generate_choose_normalization_table ( BasicTableId  id, const size_t  table_index  )

inline

Definition at line 106 of file sha256.hpp.

generate_majority_normalization_table()

BasicTable bb::plookup::sha256_tables::generate_majority_normalization_table ( BasicTableId  id, const size_t  table_index  )

inline

Definition at line 111 of file sha256.hpp.

generate_witness_extension_normalization_table()

plookup::BasicTable bb::plookup::sha256_tables::generate_witness_extension_normalization_table ( BasicTableId  id, const size_t  table_index  )

inline

Definition at line 100 of file sha256.hpp.

get_choose_input_table()

MultiTable bb::plookup::sha256_tables::get_choose_input_table ( const MultiTableId  id = SHA256_CH_INPUT )

inline

When reading from our lookup tables, we can read from the differences between adjacent rows in program memory, instead of taking absolute values

For example, if our layout in memory is:

1	2	3
a_1	b_1	c_1
a_2	b_2	c_2
...	...	...

We can valdiate that (a_1 + q_0 * a_2) is a table key and (c_1 + q_1 * c_2), (b_1 + q_2 * b_2) are table values, where q_0, q_1, q_2 are precomputed constants

This allows us to assemble accumulating sums out of multiple table reads, without requiring extra addition gates.

We can also use this feature to evaluate our sha256 rotations more efficiently, when converting into sparse form.

Let column 1 represents our 'normal' scalar, column 2 represents our scalar in sparse form

It's simple enough to make columns 1 and 2 track the accumulating sum of our scalar in normal and sparse form.

Column 3 contains terms we can combine with our accumulated sparse scalar, to obtain our rotated scalar.

Each lookup table will be of size 2^11. as that allows us to decompose a 32-bit scalar into sparse form in 3 reads (2^16 is too expensive for small circuits)

For example, if we want to rotate a by 6 bits, we make the first lookup access the table that rotates b by 6 bits. Subsequent table reads do not need to be rotated, as the 11-bit limbs will not cross 32-bit boundary and can be scaled by constants

With this in mind, we want to tackle the SHA256 ch sub-algorithm

This requires us to compute ((a >>> 6) ^ (a >>> 11) ^ (a >>> 25)) + ((a ^ b) ^ (~a ^ c))

In sparse form, we can represent this as:

 7 * (a >>> 6) + (a >>> 11) + (a >>> 25) + (a + 2 * b + 3 * c)

When decomposing a into sparse form, we would therefore like to obtain the following:

 7 * (a >>> 6) + (a >>> 11) + (a >>> 25) + (a)

We need to determine the values of the constants (q_1, q_2, q_3) that we will be scaling our lookup values by, when assembling our accumulated sums.

We need the sparse representation of a elsewhere in the algorithm, so the constants in columns 1 and 2 are fixed.

Definition at line 246 of file sha256.hpp.

get_choose_output_table()

MultiTable bb::plookup::sha256_tables::get_choose_output_table ( const MultiTableId  id = SHA256_CH_OUTPUT )

inline

Definition at line 132 of file sha256.hpp.

get_choose_rotation_multipliers()

std::array< bb::fr, 3 > bb::plookup::sha256_tables::get_choose_rotation_multipliers ( )

inline

Definition at line 189 of file sha256.hpp.

get_majority_input_table()

MultiTable bb::plookup::sha256_tables::get_majority_input_table ( const MultiTableId  id = SHA256_MAJ_INPUT )

inline

We want to tackle the SHA256 maj sub-algorithm

This requires us to compute ((a >>> 2) ^ (a >>> 13) ^ (a >>> 22)) + ((a & b) ^ (a & c) ^ (b & c))

In sparse form, we can represent this as:

 4 * (a >>> 2) + (a >>> 13) + (a >>> 22) +  (a + b + c)

We need to determine the values of the constants (q_1, q_2, q_3) that we will be scaling our lookup values by, when assembling our accumulated sums.

We need the sparse representation of a elsewhere in the algorithm, so the constants in columns 1 and 2 are fixed.

Definition at line 344 of file sha256.hpp.

get_majority_output_table()

MultiTable bb::plookup::sha256_tables::get_majority_output_table ( const MultiTableId  id = SHA256_MAJ_OUTPUT )

inline

Definition at line 148 of file sha256.hpp.

get_majority_rotation_multipliers()

std::array< bb::fr, 3 > bb::plookup::sha256_tables::get_majority_rotation_multipliers ( )

inline

Definition at line 164 of file sha256.hpp.

get_witness_extension_input_table()

MultiTable bb::plookup::sha256_tables::get_witness_extension_input_table ( const MultiTableId  id = SHA256_WITNESS_INPUT )

inline

Definition at line 224 of file sha256.hpp.

get_witness_extension_output_table()

MultiTable bb::plookup::sha256_tables::get_witness_extension_output_table ( const MultiTableId  id = SHA256_WITNESS_OUTPUT )

inline

Definition at line 116 of file sha256.hpp.