sha256.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
 
#include "barretenberg/crypto/aes128/aes128.hpp"
#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 {
 
static constexpr uint64_t choose_normalization_table[28]{
    /* xor result = 0 */
    0, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
    0, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
    0, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
    1, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
    0, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
    1, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
    1, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
    /* xor result = 1 */
    1, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
    1, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
    1, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
    2, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
    1, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
    2, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
    2, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
    /* xor result = 2 */
    0, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
    0, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
    0, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
    1, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
    0, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
    1, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
    1, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
    1, // e + 2f + 3g = 0 => e = 0, f = 0, g = 0 => t = 0
    /* xor result = 3 */
    1, // e + 2f + 3g = 1 => e = 1, f = 0, g = 0 => t = 0
    1, // e + 2f + 3g = 2 => e = 0, f = 1, g = 0 => t = 0
    2, // e + 2f + 3g = 3 => e = 0, f = 0, g = 1 OR e = 1, f = 1, g = 0 => t = 1
    1, // e + 2f + 3g = 4 => e = 1, f = 0, g = 1 => t = 0
    2, // e + 2f + 3g = 5 => e = 0, f = 1, g = 1 => t = 1
    2, // e + 2f + 3g = 6 => e = 1, f = 1, g = 1 => t = 1
};
 
static constexpr uint64_t majority_normalization_table[16]{
    /* xor result = 0 */
    0, // a + b + c = 0 => (a & b) ^ (a & c) ^ (b & c) = 0
    0, // a + b + c = 1 => (a & b) ^ (a & c) ^ (b & c) = 0
    1, // a + b + c = 2 => (a & b) ^ (a & c) ^ (b & c) = 1
    1, // a + b + c = 3 => (a & b) ^ (a & c) ^ (b & c) = 1
    /* xor result = 1 */
    1,
    1,
    2,
    2,
    /* xor result = 2 */
    0,
    0,
    1,
    1,
    /* xor result = 3 */
    1,
    1,
    2,
    2,
};
 
static constexpr uint64_t witness_extension_normalization_table[16]{
    /* xor result = 0 */
    0,
    1,
    0,
    1,
    /* xor result = 1 */
    1,
    2,
    1,
    2,
    /* xor result = 2 */
    0,
    1,
    0,
    1,
    /* xor result = 3 */
    1,
    2,
    1,
    2,
};
 
inline plookup::BasicTable generate_witness_extension_normalization_table(BasicTableId id, const size_t table_index)
{
    return sparse_tables::generate_sparse_normalization_table<16, 3, 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<28, 2, 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<16, 3, 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;
 
    MultiTable table(numeric::pow64(16, 3), 1 << 3, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(numeric::pow64(16, 3));
        table.basic_table_ids.emplace_back(SHA256_WITNESS_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<16, witness_extension_normalization_table>);
    }
    return table;
}
 
inline MultiTable get_choose_output_table(const MultiTableId id = SHA256_CH_OUTPUT)
{
    const size_t num_entries = 16;
 
    MultiTable table(numeric::pow64(28, 2), 1 << 2, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(numeric::pow64(28, 2));
        table.basic_table_ids.emplace_back(SHA256_CH_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<28, choose_normalization_table>);
    }
    return table;
}
 
inline MultiTable get_majority_output_table(const MultiTableId id = SHA256_MAJ_OUTPUT)
{
    const size_t num_entries = 11;
 
    MultiTable table(numeric::pow64(16, 3), 1 << 3, 0, num_entries);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(numeric::pow64(16, 3));
        table.basic_table_ids.emplace_back(SHA256_MAJ_NORMALIZE);
        table.get_table_values.emplace_back(
            &sparse_tables::get_sparse_normalization_values<16, majority_normalization_table>);
    }
    return table;
}
 
inline std::array<bb::fr, 3> get_majority_rotation_multipliers()
{
    constexpr uint64_t base_temp = 16;
    auto base = bb::fr(base_temp);
    // scaling factors applied to a's sparse limbs, excluding the rotated limb
    const std::array<bb::fr, 3> rot2_coefficients{ 0, base.pow(11 - 2), base.pow(22 - 2) };
    const std::array<bb::fr, 3> rot13_coefficients{ base.pow(32 - 13), 0, base.pow(22 - 13) };
    const std::array<bb::fr, 3> rot22_coefficients{ base.pow(32 - 22), base.pow(32 - 22 + 11), 0 };
 
    // these are the coefficients that we want
    const std::array<bb::fr, 3> target_rotation_coefficients{
        rot2_coefficients[0] + rot13_coefficients[0] + rot22_coefficients[0],
        rot2_coefficients[1] + rot13_coefficients[1] + rot22_coefficients[1],
        rot2_coefficients[2] + rot13_coefficients[2] + rot22_coefficients[2],
    };
 
    bb::fr column_2_row_1_multiplier = target_rotation_coefficients[0];
    bb::fr column_2_row_2_multiplier =
        target_rotation_coefficients[0] * (-bb::fr(base).pow(11)) + target_rotation_coefficients[1];
 
    std::array<bb::fr, 3> rotation_multipliers = { column_2_row_1_multiplier, column_2_row_2_multiplier, bb::fr(0) };
    return rotation_multipliers;
}
 
// template <uint64_t rot_a, uint64_t rot_b, uint64_t rot_c>
inline std::array<bb::fr, 3> get_choose_rotation_multipliers()
{
    const std::array<bb::fr, 3> column_2_row_3_coefficients{
        bb::fr(1),
        bb::fr(28).pow(11),
        bb::fr(28).pow(22),
    };
 
    // scaling factors applied to a's sparse limbs, excluding the rotated limb
    const std::array<bb::fr, 3> rot6_coefficients{ bb::fr(0), bb::fr(28).pow(11 - 6), bb::fr(28).pow(22 - 6) };
    const std::array<bb::fr, 3> rot11_coefficients{ bb::fr(28).pow(32 - 11), bb::fr(0), bb::fr(28).pow(22 - 11) };
    const std::array<bb::fr, 3> rot25_coefficients{ bb::fr(28).pow(32 - 25), bb::fr(28).pow(32 - 25 + 11), bb::fr(0) };
 
    // these are the coefficients that we want
    const std::array<bb::fr, 3> target_rotation_coefficients{
        rot6_coefficients[0] + rot11_coefficients[0] + rot25_coefficients[0],
        rot6_coefficients[1] + rot11_coefficients[1] + rot25_coefficients[1],
        rot6_coefficients[2] + rot11_coefficients[2] + rot25_coefficients[2],
    };
 
    bb::fr column_2_row_1_multiplier = bb::fr(1) * target_rotation_coefficients[0]; // why multiply by one?
 
    // this gives us the correct scaling factor for a0's 1st limb
    std::array<bb::fr, 3> current_coefficients{
        column_2_row_3_coefficients[0] * column_2_row_1_multiplier,
        column_2_row_3_coefficients[1] * column_2_row_1_multiplier,
        column_2_row_3_coefficients[2] * column_2_row_1_multiplier,
    };
 
    bb::fr column_2_row_3_multiplier = -(current_coefficients[2]) + target_rotation_coefficients[2];
 
    std::array<bb::fr, 3> rotation_multipliers = { column_2_row_1_multiplier, bb::fr(0), column_2_row_3_multiplier };
    return rotation_multipliers;
}
 
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 };
    std::vector<bb::fr> column_3_coefficients{ 0, 0, 0, 0 };
    MultiTable table(column_1_coefficients, column_2_coefficients, column_3_coefficients);
    table.id = id;
    table.slice_sizes = { (1 << 3), (1 << 7), (1 << 8), (1 << 18) };
    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<16, 0>,
        &sparse_tables::get_sparse_table_with_rotation_values<16, 4>,
        &sparse_tables::get_sparse_table_with_rotation_values<16, 7>,
        &sparse_tables::get_sparse_table_with_rotation_values<16, 1>,
    };
    return table;
}
 
inline MultiTable get_choose_input_table(const MultiTableId id = SHA256_CH_INPUT)
{
    // scaling factors applied to a's sparse limbs, excluding the rotated limb
    const std::array<bb::fr, 3> rot6_coefficients{ bb::fr(0), bb::fr(28).pow(11 - 6), bb::fr(28).pow(22 - 6) };
    const std::array<bb::fr, 3> rot11_coefficients{ bb::fr(28).pow(32 - 11), bb::fr(0), bb::fr(28).pow(22 - 11) };
    const std::array<bb::fr, 3> rot25_coefficients{ bb::fr(28).pow(32 - 25), bb::fr(28).pow(32 - 25 + 11), bb::fr(0) };
 
    // these are the coefficients that we want
    const std::array<bb::fr, 3> target_rotation_coefficients{
        rot6_coefficients[0] + rot11_coefficients[0] + rot25_coefficients[0],
        rot6_coefficients[1] + rot11_coefficients[1] + rot25_coefficients[1],
        rot6_coefficients[2] + rot11_coefficients[2] + rot25_coefficients[2],
    };
 
    bb::fr column_2_row_1_multiplier = target_rotation_coefficients[0];
 
    // this gives us the correct scaling factor for a0's 1st limb
    std::array<bb::fr, 3> current_coefficients{
        column_2_row_1_multiplier,
        bb::fr(28).pow(11) * column_2_row_1_multiplier,
        bb::fr(28).pow(22) * column_2_row_1_multiplier,
    };
 
    // bb::fr column_2_row_3_multiplier = -(current_coefficients[2]) + target_rotation_coefficients[2];
    bb::fr column_3_row_2_multiplier = -(current_coefficients[1]) + target_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), bb::fr(28).pow(11), bb::fr(28).pow(22) };
    std::vector<bb::fr> column_3_coefficients{ bb::fr(1), column_3_row_2_multiplier + bb::fr(1), 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.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 6>);
    table.get_table_values.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 0>);
    table.get_table_values.push_back(&sparse_tables::get_sparse_table_with_rotation_values<28, 3>);
    // table.get_table_values = std::vector<MultiTable::table_out (*)(MultiTable::table_in)>{
 
    //     &get_sha256_sparse_map_values<28, 0, 0>,
    //     &get_sha256_sparse_map_values<28, 3, 0>,
    // };
    return table;
}
 
// This table (at third row and column) returns the sum of roations that "non-trivially wrap"
inline MultiTable get_majority_input_table(const MultiTableId id = SHA256_MAJ_INPUT)
{
    constexpr uint64_t base = 16;
 
    // scaling factors applied to a's sparse limbs, excluding the rotated limb
    const std::array<bb::fr, 3> rot2_coefficients{ bb::fr(0), bb::fr(base).pow(11 - 2), bb::fr(base).pow(22 - 2) };
    const std::array<bb::fr, 3> rot13_coefficients{ bb::fr(base).pow(32 - 13), bb::fr(0), bb::fr(base).pow(22 - 13) };
    const std::array<bb::fr, 3> rot22_coefficients{ bb::fr(base).pow(32 - 22),
                                                    bb::fr(base).pow(32 - 22 + 11),
                                                    bb::fr(0) };
 
    // these are the coefficients that we want
    const std::array<bb::fr, 3> target_rotation_coefficients{
        rot2_coefficients[0] + rot13_coefficients[0] + rot22_coefficients[0],
        rot2_coefficients[1] + rot13_coefficients[1] + rot22_coefficients[1],
        rot2_coefficients[2] + rot13_coefficients[2] + rot22_coefficients[2],
    };
 
    bb::fr column_2_row_3_multiplier =
        target_rotation_coefficients[1] * (-bb::fr(base).pow(11)) + target_rotation_coefficients[2];
 
    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), bb::fr(base).pow(11), bb::fr(base).pow(22) };
    std::vector<bb::fr> column_3_coefficients{ bb::fr(1), bb::fr(1), bb::fr(1) + column_2_row_3_multiplier };
 
    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<16, 2>,
        &sparse_tables::get_sparse_table_with_rotation_values<16, 2>,
        &sparse_tables::get_sparse_table_with_rotation_values<16, 0>,
    };
    return table;
}
 
} // namespace bb::plookup::sha256_tables