sha256.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#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"
 
namespace bb::plookup::sha256_tables {
 
// Sparse form bases used for SHA-256 operations; chosen to prevent overflow during sparse digit addition
static constexpr uint64_t CHOOSE_BASE = 28;
static constexpr uint64_t MAJORITY_BASE = 16;
static constexpr uint64_t WITNESS_EXTENSION_BASE = 16;
 
// Bits per lookup in the sparse form normalization tables
static constexpr uint64_t CHOOSE_BITS_PER_LOOKUP = 2;            // table size: 28² = 784
static constexpr uint64_t MAJORITY_BITS_PER_LOOKUP = 3;          // table size: 16³ = 4096
static constexpr uint64_t WITNESS_EXTENSION_BITS_PER_LOOKUP = 3; // table size: 16³ = 4096
 
static constexpr uint64_t choose_normalization_table[CHOOSE_BASE]{
    /* σ = 0 (Σ₁ = 0): output = 0 + Ch */
    0, // e + 2f + 3g = 0 => e=0, f=0, g=0 => Ch=0
    0, // e + 2f + 3g = 1 => e=1, f=0, g=0 => Ch=0
    0, // e + 2f + 3g = 2 => e=0, f=1, g=0 => Ch=0
    1, // e + 2f + 3g = 3 => e=0, f=0, g=1 OR e=1, f=1, g=0 => Ch=1
    0, // e + 2f + 3g = 4 => e=1, f=0, g=1 => Ch=0
    1, // e + 2f + 3g = 5 => e=0, f=1, g=1 => Ch=1
    1, // e + 2f + 3g = 6 => e=1, f=1, g=1 => Ch=1
    /* σ = 1 (Σ₁ = 1): output = 1 + Ch */
    1, // e + 2f + 3g = 0 => Ch=0
    1, // e + 2f + 3g = 1 => Ch=0
    1, // e + 2f + 3g = 2 => Ch=0
    2, // e + 2f + 3g = 3 => Ch=1
    1, // e + 2f + 3g = 4 => Ch=0
    2, // e + 2f + 3g = 5 => Ch=1
    2, // e + 2f + 3g = 6 => Ch=1
    /* σ = 2 (Σ₁ = 0): output = 0 + Ch */
    0, // e + 2f + 3g = 0 => Ch=0
    0, // e + 2f + 3g = 1 => Ch=0
    0, // e + 2f + 3g = 2 => Ch=0
    1, // e + 2f + 3g = 3 => Ch=1
    0, // e + 2f + 3g = 4 => Ch=0
    1, // e + 2f + 3g = 5 => Ch=1
    1, // e + 2f + 3g = 6 => Ch=1
    /* σ = 3 (Σ₁ = 1): output = 1 + Ch */
    1, // e + 2f + 3g = 0 => Ch=0
    1, // e + 2f + 3g = 1 => Ch=0
    1, // e + 2f + 3g = 2 => Ch=0
    2, // e + 2f + 3g = 3 => Ch=1
    1, // e + 2f + 3g = 4 => Ch=0
    2, // e + 2f + 3g = 5 => Ch=1
    2, // e + 2f + 3g = 6 => Ch=1
};
 
static constexpr uint64_t majority_normalization_table[MAJORITY_BASE]{
    /* σ = 0 (Σ₀ = 0): output = 0 + Maj */
    0, // a + b + c = 0 => Maj=0
    0, // a + b + c = 1 => Maj=0
    1, // a + b + c = 2 => Maj=1
    1, // a + b + c = 3 => Maj=1
    /* σ = 1 (Σ₀ = 1): output = 1 + Maj */
    1, // a + b + c = 0 => Maj=0
    1, // a + b + c = 1 => Maj=0
    2, // a + b + c = 2 => Maj=1
    2, // a + b + c = 3 => Maj=1
    /* σ = 2 (Σ₀ = 0): output = 0 + Maj */
    0, // a + b + c = 0 => Maj=0
    0, // a + b + c = 1 => Maj=0
    1, // a + b + c = 2 => Maj=1
    1, // a + b + c = 3 => Maj=1
    /* σ = 3 (Σ₀ = 1): output = 1 + Maj */
    1, // a + b + c = 0 => Maj=0
    1, // a + b + c = 1 => Maj=0
    2, // a + b + c = 2 => Maj=1
    2, // a + b + c = 3 => Maj=1
};
 
static constexpr uint64_t witness_extension_normalization_table[WITNESS_EXTENSION_BASE]{
    /* s_0 = 0 (σ₀_bit = 0): output = 0 + (s_1 mod 2) */
    0, // s_1 = 0 => σ₁_bit = 0
    1, // s_1 = 1 => σ₁_bit = 1
    0, // s_1 = 2 => σ₁_bit = 0
    1, // s_1 = 3 => σ₁_bit = 1
    /* s_0 = 1 (σ₀_bit = 1): output = 1 + (s_1 mod 2) */
    1, // s_1 = 0 => σ₁_bit = 0
    2, // s_1 = 1 => σ₁_bit = 1
    1, // s_1 = 2 => σ₁_bit = 0
    2, // s_1 = 3 => σ₁_bit = 1
    /* s_0 = 2 (σ₀_bit = 0): output = 0 + (s_1 mod 2) */
    0, // s_1 = 0 => σ₁_bit = 0
    1, // s_1 = 1 => σ₁_bit = 1
    0, // s_1 = 2 => σ₁_bit = 0
    1, // s_1 = 3 => σ₁_bit = 1
    /* s_0 = 3 (σ₀_bit = 1): output = 1 + (s_1 mod 2) */
    1, // s_1 = 0 => σ₁_bit = 0
    2, // s_1 = 1 => σ₁_bit = 1
    1, // s_1 = 2 => σ₁_bit = 0
    2, // s_1 = 3 => σ₁_bit = 1
};
 
static constexpr bb::fr choose_base{ CHOOSE_BASE };
 
static constexpr bb::fr HANDLED_VIA_TABLE{ 0 }; // indicates handling via lookup table instead of scalar multiplier
 
static constexpr std::array<bb::fr, 3> choose_rot6_coefficients{
    HANDLED_VIA_TABLE,       // splits across boundary
    choose_base.pow(11 - 6), // lands at bit 5
    choose_base.pow(22 - 6), // lands at bit 16
};
 
static constexpr std::array<bb::fr, 3> choose_rot11_coefficients{
    choose_base.pow(32 - 11), // lands at bit 21
    HANDLED_VIA_TABLE,        // lands at bit 0 can be handled using sparse limb base table
    choose_base.pow(22 - 11), // lands at bit 11
};
 
static constexpr std::array<bb::fr, 3> choose_rot25_coefficients{
    choose_base.pow(32 - 25),      // lands at bit 7
    choose_base.pow(32 - 25 + 11), // lands at bit 18
    HANDLED_VIA_TABLE,             // splits across boundary
};
 
// Combined per-limb rotation coefficients
static constexpr std::array<bb::fr, 3> choose_rotation_coefficients{
    choose_rot6_coefficients[0] + choose_rot11_coefficients[0] + choose_rot25_coefficients[0],
    choose_rot6_coefficients[1] + choose_rot11_coefficients[1] + choose_rot25_coefficients[1],
    choose_rot6_coefficients[2] + choose_rot11_coefficients[2] + choose_rot25_coefficients[2],
};
 
static constexpr bb::fr majority_base{ MAJORITY_BASE };
 
static constexpr std::array<bb::fr, 3> majority_rot2_coefficients{
    HANDLED_VIA_TABLE,         // splits across boundary
    majority_base.pow(11 - 2), // lands at bit 9
    majority_base.pow(22 - 2), // lands at bit 20
};
 
static constexpr std::array<bb::fr, 3> majority_rot13_coefficients{
    majority_base.pow(32 - 13), // lands at bit 19
    HANDLED_VIA_TABLE,          // splits across boundary
    majority_base.pow(22 - 13), // lands at bit 9
};
 
static constexpr std::array<bb::fr, 3> majority_rot22_coefficients{
    majority_base.pow(32 - 22),      // lands at bit 10
    majority_base.pow(32 - 22 + 11), // lands at bit 21
    HANDLED_VIA_TABLE,               // lands at bit 0, handled via sparse limb base table
};
 
// Combined per-limb rotation coefficients
static constexpr std::array<bb::fr, 3> majority_rotation_coefficients{
    majority_rot2_coefficients[0] + majority_rot13_coefficients[0] + majority_rot22_coefficients[0],
    majority_rot2_coefficients[1] + majority_rot13_coefficients[1] + majority_rot22_coefficients[1],
    majority_rot2_coefficients[2] + majority_rot13_coefficients[2] + majority_rot22_coefficients[2],
};
 
inline BasicTable generate_witness_extension_normalization_table(BasicTableId id, const size_t table_index)
{
    return sparse_tables::generate_sparse_normalization_table<WITNESS_EXTENSION_BASE,
                                                              WITNESS_EXTENSION_BITS_PER_LOOKUP,
                                                              witness_extension_normalization_table>(id, table_index);
}
 
inline BasicTable generate_choose_normalization_table(BasicTableId id, const size_t table_index)
{
    return sparse_tables::generate_sparse_normalization_table<CHOOSE_BASE,
                                                              CHOOSE_BITS_PER_LOOKUP,
                                                              choose_normalization_table>(id, table_index);
}
 
inline BasicTable generate_majority_normalization_table(BasicTableId id, const size_t table_index)
{
    return sparse_tables::generate_sparse_normalization_table<MAJORITY_BASE,
                                                              MAJORITY_BITS_PER_LOOKUP,
                                                              majority_normalization_table>(id, table_index);
}
 
inline MultiTable get_witness_extension_output_table(const MultiTableId id = SHA256_WITNESS_OUTPUT)
{
    const size_t num_entries = 11; // ceil(32 bits / WITNESS_EXTENSION_BITS_PER_LOOKUP)
    const auto slice_size = numeric::pow64(WITNESS_EXTENSION_BASE, WITNESS_EXTENSION_BITS_PER_LOOKUP);
 
    MultiTable table(slice_size, 1ULL << WITNESS_EXTENSION_BITS_PER_LOOKUP, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(slice_size);
        table.basic_table_ids.emplace_back(SHA256_WITNESS_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<WITNESS_EXTENSION_BASE,
                                                            witness_extension_normalization_table>);
    }
    return table;
}
 
inline MultiTable get_choose_output_table(const MultiTableId id = SHA256_CH_OUTPUT)
{
    const size_t num_entries = 16; // 32 bits / CHOOSE_BITS_PER_LOOKUP
    const auto slice_size = numeric::pow64(CHOOSE_BASE, CHOOSE_BITS_PER_LOOKUP);
 
    MultiTable table(slice_size, 1ULL << CHOOSE_BITS_PER_LOOKUP, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(slice_size);
        table.basic_table_ids.emplace_back(SHA256_CH_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<CHOOSE_BASE, choose_normalization_table>);
    }
    return table;
}
 
inline MultiTable get_majority_output_table(const MultiTableId id = SHA256_MAJ_OUTPUT)
{
    const size_t num_entries = 11; // ceil(32 bits / MAJORITY_BITS_PER_LOOKUP)
    const auto slice_size = numeric::pow64(MAJORITY_BASE, MAJORITY_BITS_PER_LOOKUP);
 
    MultiTable table(slice_size, 1ULL << MAJORITY_BITS_PER_LOOKUP, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(slice_size);
        table.basic_table_ids.emplace_back(SHA256_MAJ_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<MAJORITY_BASE, majority_normalization_table>);
    }
    return table;
}
 
inline std::array<bb::fr, 3> get_majority_rotation_multipliers()
{
    bb::fr limb1_correction =
        majority_rotation_coefficients[1] - majority_base.pow(11) * majority_rotation_coefficients[0];
 
    return { majority_rotation_coefficients[0], limb1_correction, bb::fr(0) };
}
 
inline std::array<bb::fr, 3> get_choose_rotation_multipliers()
{
    bb::fr limb2_correction = choose_rotation_coefficients[2] - choose_base.pow(22) * choose_rotation_coefficients[0];
 
    return { choose_rotation_coefficients[0], bb::fr(0), limb2_correction };
}
 
inline MultiTable get_witness_extension_input_table(const MultiTableId id = SHA256_WITNESS_INPUT)
{
    std::vector<bb::fr> column_1_coefficients{ 1, 1 << 3, 1 << 10, 1 << 18 };
    std::vector<bb::fr> column_2_coefficients{ 0, 0, 0, 0 }; // Not accumulated; accessed individually
    std::vector<bb::fr> column_3_coefficients{ 0, 0, 0, 0 }; // Not accumulated; accessed individually
    MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
    table.id = id;
    table.slice_sizes = { (1 << 3), (1 << 7), (1 << 8), (1 << 14) };
 
    table.basic_table_ids = { SHA256_WITNESS_SLICE_3,
                              SHA256_WITNESS_SLICE_7_ROTATE_4,
                              SHA256_WITNESS_SLICE_8_ROTATE_7,
                              SHA256_WITNESS_SLICE_14_ROTATE_1 };
 
    table.get_table_values = {
        &sparse_tables::get_sparse_table_with_rotation_values<WITNESS_EXTENSION_BASE, 0>,
        &sparse_tables::get_sparse_table_with_rotation_values<WITNESS_EXTENSION_BASE, 4>,
        &sparse_tables::get_sparse_table_with_rotation_values<WITNESS_EXTENSION_BASE, 7>,
        &sparse_tables::get_sparse_table_with_rotation_values<WITNESS_EXTENSION_BASE, 1>,
    };
    return table;
}
 
inline MultiTable get_choose_input_table(const MultiTableId id = SHA256_CH_INPUT)
{
 
    // L1 correction factor: δ = c1 - B¹¹·c0 (see block comment above)
    bb::fr limb1_table_correction =
        choose_rotation_coefficients[1] - choose_base.pow(11) * choose_rotation_coefficients[0];
 
    std::vector<bb::fr> column_1_coefficients{ bb::fr(1), bb::fr(1 << 11), bb::fr(1 << 22) };
    std::vector<bb::fr> column_2_coefficients{ bb::fr(1), choose_base.pow(11), choose_base.pow(22) };
    std::vector<bb::fr> column_3_coefficients{ bb::fr(1), bb::fr(1) + limb1_table_correction, bb::fr(1) };
    MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
    table.id = id;
    table.slice_sizes = { (1 << 11), (1 << 11), (1 << 10) };
 
    table.basic_table_ids = { SHA256_BASE28_ROTATE6, SHA256_BASE28, SHA256_BASE28_ROTATE3 };
    table.get_table_values = { &sparse_tables::get_sparse_table_with_rotation_values<CHOOSE_BASE, 6>,
                               &sparse_tables::get_sparse_table_with_rotation_values<CHOOSE_BASE, 0>,
                               &sparse_tables::get_sparse_table_with_rotation_values<CHOOSE_BASE, 3> };
 
    return table;
}
 
inline MultiTable get_majority_input_table(const MultiTableId id = SHA256_MAJ_INPUT)
{
    // L2 correction factor: δ = c2 - B¹¹·c1 (see block comment above)
    bb::fr limb2_table_correction =
        majority_rotation_coefficients[2] - majority_base.pow(11) * majority_rotation_coefficients[1];
 
    std::vector<bb::fr> column_1_coefficients{ bb::fr(1), bb::fr(1 << 11), bb::fr(1 << 22) };
    std::vector<bb::fr> column_2_coefficients{ bb::fr(1), majority_base.pow(11), majority_base.pow(22) };
    std::vector<bb::fr> column_3_coefficients{ bb::fr(1), bb::fr(1), bb::fr(1) + limb2_table_correction };
 
    MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
    table.id = id;
    table.slice_sizes = { (1 << 11), (1 << 11), (1 << 10) };
 
    table.basic_table_ids = { SHA256_BASE16_ROTATE2, SHA256_BASE16_ROTATE2, SHA256_BASE16 };
    table.get_table_values = { &sparse_tables::get_sparse_table_with_rotation_values<MAJORITY_BASE, 2>,
                               &sparse_tables::get_sparse_table_with_rotation_values<MAJORITY_BASE, 2>,
                               &sparse_tables::get_sparse_table_with_rotation_values<MAJORITY_BASE, 0> };
    return table;
}
 
} // namespace bb::plookup::sha256_tables