sha256.hpp File Reference

Plookup tables for SHA-256 using sparse form representation. More...

#include "barretenberg/numeric/bitop/pow.hpp"
#include "barretenberg/numeric/bitop/rotate.hpp"
#include "barretenberg/numeric/bitop/sparse_form.hpp"
#include "sparse.hpp"
#include "types.hpp"

Go to the source code of this file.

Namespaces
namespace	bb
	Entry point for Barretenberg command-line interface.
namespace	bb::plookup
namespace	bb::plookup::sha256_tables

Functions
BasicTable	bb::plookup::sha256_tables::generate_witness_extension_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing witness extension sparse digits.
BasicTable	bb::plookup::sha256_tables::generate_choose_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing choose sparse digits.
BasicTable	bb::plookup::sha256_tables::generate_majority_normalization_table (BasicTableId id, const size_t table_index)
	Generates a BasicTable for normalizing majority sparse digits.
MultiTable	bb::plookup::sha256_tables::get_witness_extension_output_table (const MultiTableId id=SHA256_WITNESS_OUTPUT)
	Constructs a MultiTable for normalizing witness extension sparse results back to normal form.
MultiTable	bb::plookup::sha256_tables::get_choose_output_table (const MultiTableId id=SHA256_CH_OUTPUT)
	Constructs a MultiTable for normalizing choose sparse results back to normal form.
MultiTable	bb::plookup::sha256_tables::get_majority_output_table (const MultiTableId id=SHA256_MAJ_OUTPUT)
	Constructs a MultiTable for normalizing majority sparse results back to normal form.
std::array< bb::fr, 3 >	bb::plookup::sha256_tables::get_majority_rotation_multipliers ()
	Returns multipliers for computing Σ₀(a) rotations in majority_with_sigma0.
std::array< bb::fr, 3 >	bb::plookup::sha256_tables::get_choose_rotation_multipliers ()
	Returns multipliers for computing Σ₁(e) rotations in choose_with_sigma1.
MultiTable	bb::plookup::sha256_tables::get_witness_extension_input_table (const MultiTableId id=SHA256_WITNESS_INPUT)
	Constructs a MultiTable for decomposing a 32-bit word for message schedule extension.
MultiTable	bb::plookup::sha256_tables::get_choose_input_table (const MultiTableId id=SHA256_CH_INPUT)
	Constructs a MultiTable for decomposing e into sparse form and computing rotation components for Σ₁(e).
MultiTable	bb::plookup::sha256_tables::get_majority_input_table (const MultiTableId id=SHA256_MAJ_INPUT)
	Constructs a MultiTable for decomposing a into sparse form and computing rotation components for Σ₀(a).

Detailed Description

Plookup tables for SHA-256 using sparse form representation.

This file defines lookup tables that enable efficient SHA-256 computation in circuits by converting bitwise XOR operations into arithmetic additions via "sparse form" representation.

In sparse form, each bit of a value is stored in its own base-B digit, where B is chosen large enough to prevent overflow when multiple values are added. This allows:

• XOR of N values becomes addition of N sparse values plus normalization (digit mod 2)
• Boolean functions (Ch, Maj) to be encoded alongside rotations in a single sparse digit

Each SHA-256 operation proceeds in three stages:

1. Input Table (decomposition): Converts a 32-bit word into sparse limbs
   • Splits the word into limbs at boundaries aligned with rotation parameters
   • Produces sparse form (C2) and rotated sparse form corrections (C3) (for certain limbs)
2. Sparse Computation (in sha256.cpp): Combines sparse limbs via arithmetic
   • Multiplies limbs by rotation coefficients to position them correctly
   • Adds multiple rotated/shifted copies together
   • Result is a sparse value encoding the XOR (and optionally Ch/Maj) result
3. Output Table (normalization): Converts sparse form back to normal form

Tables overview

Operation	Input Table	Output Table	Base
Message extension σ₀/σ₁	SHA256_WITNESS_INPUT	SHA256_WITNESS_OUTPUT	16
Choose + Σ₁	SHA256_CH_INPUT	SHA256_CH_OUTPUT	28
Majority + Σ₀	SHA256_MAJ_INPUT	SHA256_MAJ_OUTPUT	16

See corresponding table generation functions for details, including choice of base and limb structure.

Definition in file sha256.hpp.