sha256.cpp

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: }
// =====================
 
#include "sha256.hpp"
 
#include "barretenberg/stdlib/primitives/field/field.hpp"
#include "barretenberg/stdlib/primitives/plookup/plookup.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/plookup_tables.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/sha256.hpp"
 
using namespace bb;
 
namespace bb::stdlib {
using namespace bb::plookup;
 
template <typename Builder>
SHA256<Builder>::sparse_witness_limbs SHA256<Builder>::convert_witness(const field_t<Builder>& input)
{
    using field_pt = field_t<Builder>;
 
    sparse_witness_limbs result(input);
    const auto lookup = plookup_read<Builder>::get_lookup_accumulators(MultiTableId::SHA256_WITNESS_INPUT, input);
 
    result.sparse_limbs = std::array<field_pt, 4>{
        lookup[ColumnIdx::C2][0],
        lookup[ColumnIdx::C2][1],
        lookup[ColumnIdx::C2][2],
        lookup[ColumnIdx::C2][3],
    };
    result.rotated_limb_corrections = std::array<field_pt, 4>{
        lookup[ColumnIdx::C3][0],
        lookup[ColumnIdx::C3][1],
        lookup[ColumnIdx::C3][2],
        lookup[ColumnIdx::C3][3],
    };
    result.has_sparse_limbs = true;
 
    return result;
}
 
template <typename Builder>
std::array<field_t<Builder>, 64> SHA256<Builder>::extend_witness(const std::array<field_t<Builder>, 16>& w_in)
{
    using field_pt = field_t<Builder>;
 
    Builder* ctx = w_in[0].get_context();
 
    std::array<SHA256<Builder>::sparse_witness_limbs, 64> w_sparse;
 
    // Populate initial 16 words from input (sparse form computed lazily as needed)
    for (size_t i = 0; i < 16; ++i) {
        w_sparse[i] = SHA256<Builder>::sparse_witness_limbs(w_in[i]);
        // Extract builder context from inputs
        if ((ctx == nullptr) && w_in[i].get_context()) {
            ctx = w_in[i].get_context();
        }
    }
 
    // Compute extended words W[16..63]
    for (size_t i = 16; i < 64; ++i) {
        auto& w_left = w_sparse[i - 15];
        auto& w_right = w_sparse[i - 2];
 
        if (!w_left.has_sparse_limbs) {
            w_left = convert_witness(w_left.normal);
        }
        if (!w_right.has_sparse_limbs) {
            w_right = convert_witness(w_right.normal);
        }
 
        // Compute the (partially) rotated sparse limbs for σ₀
        // Note: remaining contributions accounted for via w_left.rotated_limb_corrections
        std::array<field_pt, 4> left{
            w_left.sparse_limbs[0] * left_multipliers[0],
            w_left.sparse_limbs[1] * left_multipliers[1],
            w_left.sparse_limbs[2] * left_multipliers[2],
            w_left.sparse_limbs[3] * left_multipliers[3],
        };
 
        // Compute the (partially) rotated sparse limbs for σ₁
        // Note: remaining contributions accounted for via w_right.rotated_limb_corrections
        std::array<field_pt, 4> right{
            w_right.sparse_limbs[0] * right_multipliers[0],
            w_right.sparse_limbs[1] * right_multipliers[1],
            w_right.sparse_limbs[2] * right_multipliers[2],
            w_right.sparse_limbs[3] * right_multipliers[3],
        };
 
        // Compute σ₀(w[i-15]) in sparse form where σ₀(x) = (x >>> 7) ⊕ (x >>> 18) ⊕ (x >> 3).
        // Each sparse digit holds the sum of contributions from the three rotation/shift operations (digit value in
        // {0,1,2,3}). The fr(4) scaling positions σ₀'s contribution in the upper 2 bits of each 4-bit digit slot: when
        // combined with σ₁ (unscaled, in lower 2 bits), each digit becomes 4*σ₀_digit + σ₁_digit ∈ [0,15].
        const field_pt left_xor_sparse =
            left[0].add_two(left[1], left[2]).add_two(left[3], w_left.rotated_limb_corrections[1]) * fr(4);
 
        // Compute σ₀(w[i-15]) + σ₁(w[i-2]) in sparse form where σ₁(x) = (x >>> 17) ⊕ (x >>> 19) ⊕ (x >> 10).
        const field_pt xor_result_sparse = right[0]
                                               .add_two(right[1], right[2])
                                               .add_two(right[3], w_right.rotated_limb_corrections[2])
                                               .add_two(w_right.rotated_limb_corrections[3], left_xor_sparse);
 
        // Normalize the sparse representation via a lookup to obtain the genuine result σ₀ + σ₁
        field_pt xor_result = plookup_read<Builder>::read_from_1_to_2_table(SHA256_WITNESS_OUTPUT, xor_result_sparse);
 
        // Compute W[i] = σ₁(W[i-2]) + W[i-7] + σ₀(W[i-15]) + W[i-16]
        field_pt w_out_raw = xor_result.add_two(w_sparse[i - 16].normal, w_sparse[i - 7].normal);
 
        // Natively compute value reduced to 32 bits per SHA-256 spec
        const uint64_t w_out_modded = w_out_raw.get_value().from_montgomery_form().data[0] & 0xffffffffULL;
 
        field_pt w_out;
        if (w_out_raw.is_constant()) {
            w_out = field_pt(ctx, fr(w_out_modded));
        } else {
            // Establish w_out as the 32-bit reduction of w_out_raw via w_out_raw = w_out + divisor*2^32
            w_out = witness_t<Builder>(ctx, fr(w_out_modded));
            static constexpr fr inv_pow_two = fr(2).pow(32).invert();
 
            field_pt w_out_raw_inv_pow_two = w_out_raw * inv_pow_two;
            field_pt w_out_inv_pow_two = w_out * inv_pow_two;
            field_pt divisor = w_out_raw_inv_pow_two - w_out_inv_pow_two;
            // AUDITTODO: The 3-bit constraint is currently necessary due to unconstrained inputs.
            //
            // w_out_raw = xor_result + w[i-16] + w[i-7], where:
            // - xor_result: 32-bit (from SHA256_WITNESS_OUTPUT lookup)
            // - w[i-16]: At i=16, this is input[0] which is NEVER lookup-constrained
            // - w[i-7]: At i=16..20, this is input[9..13] which are used BEFORE being converted
            //
            // If all three inputs were 32-bit constrained, max sum = 3*(2^32-1), so divisor <= 2
            // and a 2-bit constraint would suffice. However, with unconstrained inputs (~35 bits
            // per the add_normalize overflow slack), divisor could exceed 7 and reject the proof.
            //
            // This constraint implicitly enforces input bounds - if we add explicit 32-bit input
            // constraints (see AUDITTODO in sha256_block), this could be tightened to 2 bits.
            divisor.create_range_constraint(3);
        }
 
        w_sparse[i] = sparse_witness_limbs(w_out);
    }
 
    std::array<field_pt, 64> w_extended;
    for (size_t i = 0; i < 64; ++i) {
        w_extended[i] = w_sparse[i].normal;
    }
    return w_extended;
}
 
template <typename Builder>
SHA256<Builder>::sparse_value SHA256<Builder>::map_into_choose_sparse_form(const field_t<Builder>& input)
{
    sparse_value result;
    result.normal = input;
    result.sparse = plookup_read<Builder>::read_from_1_to_2_table(SHA256_CH_INPUT, input);
 
    return result;
}
 
template <typename Builder>
SHA256<Builder>::sparse_value SHA256<Builder>::map_into_maj_sparse_form(const field_t<Builder>& input)
{
    sparse_value result;
    result.normal = input;
    result.sparse = plookup_read<Builder>::read_from_1_to_2_table(SHA256_MAJ_INPUT, input);
 
    return result;
}
 
template <typename Builder>
field_t<Builder> SHA256<Builder>::choose_with_sigma1(sparse_value& e, const sparse_value& f, const sparse_value& g)
{
    using field_pt = field_t<Builder>;
    // Separates rotation contributions (0-3) from Choose encoding (0-6) in each base-28 digit
    constexpr fr SPARSE_MULT = fr(7);
 
    const auto lookup = plookup_read<Builder>::get_lookup_accumulators(SHA256_CH_INPUT, e.normal);
    const auto rotation_coefficients = sha256_tables::get_choose_rotation_multipliers();
 
    field_pt rotation_result = lookup[ColumnIdx::C3][0];
    e.sparse = lookup[ColumnIdx::C2][0];
    field_pt sparse_L2 = lookup[ColumnIdx::C2][2];
 
    // Compute e + 7*Σ₁(e) in sparse form
    field_pt xor_result = (rotation_result * SPARSE_MULT)
                              .add_two(e.sparse * (rotation_coefficients[0] * SPARSE_MULT + fr(1)),
                                       sparse_L2 * (rotation_coefficients[2] * SPARSE_MULT));
 
    // Add 2f + 3g to get e + 7*Σ₁(e) + 2f + 3g (each digit in 0..27)
    field_pt choose_result_sparse = xor_result.add_two(f.sparse + f.sparse, g.sparse + g.sparse + g.sparse);
 
    // Normalize via lookup: each digit maps to Σ₁(e)_i + Ch(e,f,g)_i
    field_pt choose_result = plookup_read<Builder>::read_from_1_to_2_table(SHA256_CH_OUTPUT, choose_result_sparse);
 
    return choose_result;
}
 
template <typename Builder>
field_t<Builder> SHA256<Builder>::majority_with_sigma0(sparse_value& a, const sparse_value& b, const sparse_value& c)
{
    using field_pt = field_t<Builder>;
    // Separates rotation contributions (0-3) from Majority encoding (0-3) in each base-16 digit
    constexpr fr SPARSE_MULT = fr(4);
 
    const auto lookup = plookup_read<Builder>::get_lookup_accumulators(SHA256_MAJ_INPUT, a.normal);
    const auto rotation_coefficients = sha256_tables::get_majority_rotation_multipliers();
 
    // first row of 3rd column gives accumulating sum of "non-trivial" wraps
    field_pt rotation_result = lookup[ColumnIdx::C3][0];
    a.sparse = lookup[ColumnIdx::C2][0];
    field_pt sparse_L1_acc = lookup[ColumnIdx::C2][1];
 
    // Compute a + 4*Σ₀(a) in sparse form
    field_pt xor_result = (rotation_result * SPARSE_MULT)
                              .add_two(a.sparse * (rotation_coefficients[0] * SPARSE_MULT + fr(1)),
                                       sparse_L1_acc * (rotation_coefficients[1] * SPARSE_MULT));
 
    // Add b + c to get a + 4*Σ₀(a) + b + c (each digit in 0..15)
    field_pt majority_result_sparse = xor_result.add_two(b.sparse, c.sparse);
 
    // Normalize via lookup: each digit maps to Σ₀(a)_i + Maj(a,b,c)_i
    field_pt majority_result = plookup_read<Builder>::read_from_1_to_2_table(SHA256_MAJ_OUTPUT, majority_result_sparse);
 
    return majority_result;
}
 
template <typename Builder>
field_t<Builder> SHA256<Builder>::add_normalize(const field_t<Builder>& a, const field_t<Builder>& b)
{
    using field_pt = field_t<Builder>;
    using witness_pt = witness_t<Builder>;
 
    Builder* ctx = a.get_context() ? a.get_context() : b.get_context();
 
    uint256_t sum = a.get_value() + b.get_value();
    uint256_t normalized_sum = static_cast<uint32_t>(sum.data[0]); // lower 32 bits
 
    if (a.is_constant() && b.is_constant()) {
        return field_pt(ctx, normalized_sum);
    }
 
    fr overflow_value = fr((sum - normalized_sum) >> 32);
    field_pt overflow = witness_pt(ctx, overflow_value);
 
    field_pt result = a.add_two(b, overflow * field_pt(ctx, -fr(1ULL << 32ULL)));
    // AUDITTODO: The 3-bit constraint is necessary. Analysis of call sites:
    //
    // Compression loop (lines ~439-450):
    //   ch, maj outputs: max = 2(2^32-1) each (lookup output digits are 0-2, see sha256.hpp:79)
    //   temp1 = ch + h.normal + (w[i] + K[i])  (max = 2(2^32-1) + (2^32-1) + 2(2^32-1) = 5(2^32-1))
    //   add_normalize(d.normal, temp1): max sum = (2^32-1) + 5(2^32-1) = 6(2^32-1), overflow <= 5
    //   add_normalize(temp1, maj): max sum = 5(2^32-1) + 2(2^32-1) = 7(2^32-1), overflow <= 6
    //   => Requires 3 bits (to represent overflow values 0-7)
    //
    // Final output (lines ~456-463):
    //   add_normalize(X.normal, h_init[i]): both 32-bit, max sum = 2(2^32-1), overflow <= 1
    //   => Could use 1 bit, but we use 3 for uniformity
    //
    // The 3-bit constraint is correct and necessary for the compression loop.
    // Consider adding argument overflow_bits to customize constraint size and make it more explicit.
    overflow.create_range_constraint(3);
    return result;
}
 
template <typename Builder>
std::array<field_t<Builder>, 8> SHA256<Builder>::sha256_block(const std::array<field_t<Builder>, 8>& h_init,
                                                              const std::array<field_t<Builder>, 16>& input)
{
    using field_pt = field_t<Builder>;
 
    // AUDITTODO: Input range constraints are not explicitly enforced here. Analysis shows:
    //
    // - h_init[1,2,5,6] are immediately lookup-constrained (32-bit) via map_into_*_sparse_form
    // - h_init[0,4] are lookup-constrained in round 0 via choose/majority functions
    // - h_init[3,7] are used in round 0 arithmetic BEFORE being lookup-constrained (they cycle
    //   through working variables and get constrained in later rounds)
    // - input[0] is NEVER lookup-constrained (only used as w[i-16] and in round 0, both additions)
    // - input[1..8] are lookup-constrained during extend_witness as w[i-15] (at i=16..23)
    // - input[9..13] are used as w[i-7] at i=16..20 BEFORE being constrained (converted later
    //   as w[i-15] at i=24..28)
    // - input[14..15] are lookup-constrained during extend_witness as w[i-2] (at i=16..17)
    //
    // The overflow constraints in extend_witness (3-bit divisor) and add_normalize (3-bit overflow)
    // provide weak implicit bounds. If unconstrained inputs exceed ~35 bits, these constraints
    // will reject the proof. This is safe (rejects invalid proofs) but not ideal.
    //
    // This is not practically exploitable (finding inputs that produce a specific hash still
    // requires ~2^208 work), but deviates from the SHA-256 spec which assumes 32-bit words.
    //
    // Potential fix: Use lookups (cheaper than create_range_constraint, ~1 gate vs multiple):
    // - For h_init[3], h_init[7]: convert immediately via map_into_*_sparse_form instead of
    //   wrapping in sparse_value(). The lookup constrains the input as a side effect.
    // - For input[0]: add a lookup in extend_witness via convert_witness() or SHA256_WITNESS_INPUT.
    // - For input[9..13]: reorder extend_witness to convert these before use, or add explicit lookups.
    //
    // After fixing, the extend_witness divisor constraint could be tightened to 2 bits.
 
    sparse_value a = sparse_value(h_init[0]); // delay conversion to maj sparse form
    auto b = map_into_maj_sparse_form(h_init[1]);
    auto c = map_into_maj_sparse_form(h_init[2]);
    sparse_value d = sparse_value(h_init[3]);
    sparse_value e = sparse_value(h_init[4]); // delay conversion to choose sparse form
    auto f = map_into_choose_sparse_form(h_init[5]);
    auto g = map_into_choose_sparse_form(h_init[6]);
    sparse_value h = sparse_value(h_init[7]);
 
    // Extend the 16-word message block to 64 words per SHA-256 specification
    const std::array<field_t<Builder>, 64> w = extend_witness(input);
 
    for (size_t i = 0; i < 64; ++i) {
        auto ch = choose_with_sigma1(e, f, g);
        auto maj = majority_with_sigma0(a, b, c);
        auto temp1 = ch.add_two(h.normal, w[i] + fr(round_constants[i]));
 
        h = g;
        g = f;
        f = e;
        e.normal = add_normalize(d.normal, temp1);
        d = c;
        c = b;
        b = a;
        a.normal = add_normalize(temp1, maj);
    }
 
    // Add into previous block output and return
    std::array<field_pt, 8> output;
    output[0] = add_normalize(a.normal, h_init[0]);
    output[1] = add_normalize(b.normal, h_init[1]);
    output[2] = add_normalize(c.normal, h_init[2]);
    output[3] = add_normalize(d.normal, h_init[3]);
    output[4] = add_normalize(e.normal, h_init[4]);
    output[5] = add_normalize(f.normal, h_init[5]);
    output[6] = add_normalize(g.normal, h_init[6]);
    output[7] = add_normalize(h.normal, h_init[7]);
 
    // The final add_normalize outputs are not consumed by lookup tables, so they must be
    // explicitly range-constrained. (Within the compression loop, lookup tables provide
    // implicit 32-bit constraints on add_normalize outputs.)
    for (size_t i = 0; i < 8; i++) {
        output[i].create_range_constraint(32);
    }
 
    return output;
}
 
template class SHA256<bb::UltraCircuitBuilder>;
template class SHA256<bb::MegaCircuitBuilder>;
 
} // namespace bb::stdlib