blake_util.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Nishat], commit: 66052c96cc754339ac3f2761f341f150130555b3}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/stdlib/hash/hash_utils.hpp"
#include "barretenberg/stdlib/primitives/plookup/plookup.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/plookup_tables.hpp"
 
namespace bb::stdlib::blake_util {
 
using namespace bb::plookup;
 
// constants
enum blake_constant { BLAKE_STATE_SIZE = 16 };
 
constexpr uint8_t MSG_SCHEDULE_BLAKE3[7][16] = {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, { 2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8 },
    { 3, 4, 10, 12, 13, 2, 7, 14, 6, 5, 9, 0, 11, 15, 8, 1 }, { 10, 7, 12, 9, 14, 3, 13, 15, 4, 0, 11, 2, 5, 8, 1, 6 },
    { 12, 13, 9, 11, 15, 10, 14, 8, 7, 2, 5, 3, 0, 1, 6, 4 }, { 9, 14, 11, 5, 8, 12, 15, 1, 13, 3, 0, 10, 2, 6, 4, 7 },
    { 11, 15, 5, 0, 1, 9, 8, 6, 14, 10, 2, 12, 3, 4, 7, 13 },
};
 
constexpr uint8_t MSG_SCHEDULE_BLAKE2[10][16] = {
    { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }, { 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 },
    { 11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 }, { 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 },
    { 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 }, { 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 },
    { 12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 }, { 13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 },
    { 6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 }, { 10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0 },
};
 
template <typename Builder>
void g(field_t<Builder> state[BLAKE_STATE_SIZE],
       size_t a,
       size_t b,
       size_t c,
       size_t d,
       field_t<Builder> x,
       field_t<Builder> y)
{
    typedef field_t<Builder> field_pt;
 
    // For simplicity, state[a] is written as `a' in comments.
    // a = a + b + x
    state[a] = state[a].add_two(state[b], x);
 
    // d = (d ^ a).ror(16)
    // Get the lookup accumulator where `lookup_1[ColumnIdx::C3][0]` contains the
    // XORed and rotated (by 16) value scaled by 2^{-16}.
    const auto lookup_1 = plookup_read<Builder>::get_lookup_accumulators(BLAKE_XOR_ROTATE_16, state[d], state[a], true);
    // Compute the scaling factor 2^{32-16} = 2^{16} to get the correct rotated value.
    field_pt scaling_factor_1 = (1 << (32 - 16));
    // Multiply by the scaling factor to get the final rotated value.
    state[d] = lookup_1[ColumnIdx::C3][0] * scaling_factor_1;
 
    // c = c + d
    state[c] = state[c] + state[d];
 
    // b = (b ^ c).ror(12)
    // Does not require a special XOR_ROTATE_12 table since we can get the correct value
    // by combining values from BLAKE_XOR table itself.
    // Let u = s_0 + 2^6 * s_1 + 2^{12} * s_2 + 2^{18} * s_3 + 2^{24} * s_4 + 2^{30} * s_5
    // be a 32-bit output of XOR, split into slices s_0, s_1, s_2, s_3, s_4 (6-bits each) and s_5 (5-bit).
    // We want to compute ROTATE_12(u) = s_2 + 2^6 * s_3 + 2^{12} * s_4 + 2^{18} * s_5 + 2^{20} * s_0 + 2^{26} * s_1.
    // The BLAKE_XOR table gives:
    // lookup_2[ColumnIdx::C3][0] = s_0 + 2^6 * s_1 + 2^{12} * s_2 + 2^{18} * s_3 + 2^{24} * s_4 + 2^{30} * s_5 = u.
    // lookup_2[ColumnIdx::C3][2] = s_2 + 2^6 * s_3 + 2^{12} * s_4 + 2^{18} * s_5 (i.e., u without s_0 and s_1).
    // Thus, we can compute ROTATE_12(u) as:
    // ROTATE_12(u) = lookup_2[ColumnIdx::C3][2] + (lookup_2[ColumnIdx::C3][0] - 2^{12} * lookup_2[ColumnIdx::C3][2]) *
    // 2^{20}.
 
    // Get the lookup accumulator for BLAKE_XOR table where lookup_2[ColumnIdx::C3][0] = u.
    const auto lookup_2 = plookup_read<Builder>::get_lookup_accumulators(BLAKE_XOR, state[b], state[c], true);
    // lookup_2[ColumnIdx::C3][2] = s_2 + 2^6 * s_3 + 2^{12} * s_4 + 2^{18} * s_5 (i.e., u without s_0 and s_1).
    field_pt lookup_output = lookup_2[ColumnIdx::C3][2];
    // Compute 2^{12} * lookup_2[ColumnIdx::C3][2].
    field_pt t2_term = field_pt(1 << 12) * lookup_2[ColumnIdx::C3][2];
    // Compute the final rotated value as described for ROTATE_12(u) above.
    lookup_output += (lookup_2[ColumnIdx::C3][0] - t2_term) * field_pt(1 << 20);
    state[b] = lookup_output;
 
    // a = a + b + y
    state[a] = hash_utils::add_normalize_unsafe(state[a], state[b] + y, /*overflow_bits=*/3);
 
    // d = (d ^ a).ror(8)
    // Get the lookup accumulator where `lookup_3[ColumnIdx::C3][0]` contains the
    // XORed and rotated (by 8) value scaled by 2^{-24}.
    const auto lookup_3 = plookup_read<Builder>::get_lookup_accumulators(BLAKE_XOR_ROTATE_8, state[d], state[a], true);
    // Compute the scaling factor 2^{32-8} = 2^{24} to get the correct rotated value.
    field_pt scaling_factor_3 = (1 << (32 - 8));
    // Multiply by the scaling factor to get the final rotated value.
    state[d] = lookup_3[ColumnIdx::C3][0] * scaling_factor_3;
 
    // c = c + d
    state[c] = hash_utils::add_normalize_unsafe(state[c], state[d], /*overflow_bits=*/3);
 
    // b = (b ^ c).ror(7)
    // Get the lookup accumulator where `lookup_4[ColumnIdx::C3][0]` contains the
    // XORed and rotated (by 7) value scaled by 2^{-25}.
    const auto lookup_4 = plookup_read<Builder>::get_lookup_accumulators(BLAKE_XOR_ROTATE_7, state[b], state[c], true);
    // Compute the scaling factor 2^{32-7} = 2^{25} to get the correct rotated value.
    field_pt scaling_factor_4 = (1 << (32 - 7));
    // Multiply by the scaling factor to get the final rotated value.
    state[b] = lookup_4[ColumnIdx::C3][0] * scaling_factor_4;
}
 
/*
 * This is the round function used in Blake2s and Blake3s for Ultra.
 * Inputs: - 16-word state
 *         - 16-word msg
 *         - round number
 *         - which_blake to choose Blake2 or Blake3 (false -> Blake2)
 */
template <typename Builder>
void round_fn(field_t<Builder> state[BLAKE_STATE_SIZE],
              field_t<Builder> msg[BLAKE_STATE_SIZE],
              size_t round,
              const bool which_blake = false)
{
    // Select the message schedule based on the round.
    const uint8_t* schedule = which_blake ? MSG_SCHEDULE_BLAKE3[round] : MSG_SCHEDULE_BLAKE2[round];
 
    // Mix the columns.
    g<Builder>(state, 0, 4, 8, 12, msg[schedule[0]], msg[schedule[1]]);
    g<Builder>(state, 1, 5, 9, 13, msg[schedule[2]], msg[schedule[3]]);
    g<Builder>(state, 2, 6, 10, 14, msg[schedule[4]], msg[schedule[5]]);
    g<Builder>(state, 3, 7, 11, 15, msg[schedule[6]], msg[schedule[7]]);
 
    // Mix the rows.
    g<Builder>(state, 0, 5, 10, 15, msg[schedule[8]], msg[schedule[9]]);
    g<Builder>(state, 1, 6, 11, 12, msg[schedule[10]], msg[schedule[11]]);
    g<Builder>(state, 2, 7, 8, 13, msg[schedule[12]], msg[schedule[13]]);
    g<Builder>(state, 3, 4, 9, 14, msg[schedule[14]], msg[schedule[15]]);
}
 
} // namespace bb::stdlib::blake_util