keccak.cpp

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 }
// =====================
 
#include "keccak.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/numeric/bitop/sparse_form.hpp"
#include "barretenberg/stdlib/primitives/logic/logic.hpp"
#include "barretenberg/stdlib/primitives/plookup/plookup.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_rho.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_theta.hpp"
namespace bb::stdlib {
 
using namespace bb::plookup;
 
template <typename Builder>
template <size_t lane_index>
field_t<Builder> keccak<Builder>::normalize_and_rotate(const field_ct& limb, field_ct& msb)
{
    // left_bits = the number of bits that wrap around 11^64 (left_bits)
    constexpr size_t left_bits = ROTATIONS[lane_index];
 
    // right_bits = the number of bits that don't wrap
    constexpr size_t right_bits = 64 - ROTATIONS[lane_index];
 
    // TODO read from same source as plookup table code
    constexpr size_t max_bits_per_table = plookup::keccak_tables::Rho<>::MAXIMUM_MULTITABLE_BITS;
 
    // compute the number of lookups required for our left and right bit slices
    constexpr size_t num_left_tables = left_bits / max_bits_per_table + (left_bits % max_bits_per_table > 0 ? 1 : 0);
    constexpr size_t num_right_tables = right_bits / max_bits_per_table + (right_bits % max_bits_per_table > 0 ? 1 : 0);
 
    // get the numerical value of the left and right bit slices
    // (lookup table input values derived from left / right)
    uint256_t input = limb.get_value();
    constexpr uint256_t slice_divisor = BASE.pow(right_bits);
    const auto [left, right] = input.divmod(slice_divisor);
 
    // compute the normalized values for the left and right bit slices
    // (lookup table output values derived from left_normalised / right_normalized)
    uint256_t left_normalized = normalize_sparse(left);
    uint256_t right_normalized = normalize_sparse(right);
 
    plookup::ReadData<bb::fr> lookup;
 
    // compute plookup witness values for a given slice
    // (same lambda can be used to compute witnesses for left and right slices)
    auto compute_lookup_witnesses_for_limb = [&]<size_t limb_bits, size_t num_lookups>(uint256_t& normalized) {
        // (use a constexpr loop to make some pow and div operations compile-time)
        bb::constexpr_for<0, num_lookups, 1>([&]<size_t i> {
            constexpr size_t num_bits_processed = i * max_bits_per_table;
 
            // How many bits can this slice contain?
            // We want to implicitly range-constrain `normalized < 11^{limb_bits}`,
            // which means potentially using a lookup table that is not of size 11^{max_bits_per_table}
            // for the most-significant slice
            constexpr size_t bit_slice = (num_bits_processed + max_bits_per_table > limb_bits)
                                             ? limb_bits % max_bits_per_table
                                             : max_bits_per_table;
 
            // current column values are tracked via 'input' and 'normalized'
            lookup[ColumnIdx::C1].push_back(input);
            lookup[ColumnIdx::C2].push_back(normalized);
 
            constexpr uint64_t divisor = numeric::pow64(static_cast<uint64_t>(BASE), bit_slice);
            constexpr uint64_t msb_divisor = divisor / static_cast<uint64_t>(BASE);
 
            // compute the value of the most significant bit of this slice and store in C3
            const auto [normalized_quotient, normalized_slice] = normalized.divmod(divisor);
 
            // 256-bit divisions are expensive! cast to u64s when we don't need the extra bits
            const uint64_t normalized_msb = (static_cast<uint64_t>(normalized_slice) / msb_divisor);
            lookup[ColumnIdx::C3].push_back(normalized_msb);
 
            // We need to provide a key/value object for this lookup in order for the Builder
            // to compute the plookup sorted list commitment
            const auto [input_quotient, input_slice] = input.divmod(divisor);
            lookup.lookup_entries.push_back(
                { { static_cast<uint64_t>(input_slice), 0 }, { normalized_slice, normalized_msb } });
 
            // reduce the input and output by 11^{bit_slice}
            input = input_quotient;
            normalized = normalized_quotient;
        });
    };
 
    // template lambda syntax is a little funky.
    // Need to explicitly write `.template operator()` (instead of just `()`).
    // Otherwise compiler cannot distinguish between `>` symbol referring to closing the template parameter list,
    // OR `>` being a greater-than operator :/
    compute_lookup_witnesses_for_limb.template operator()<right_bits, num_right_tables>(right_normalized);
    compute_lookup_witnesses_for_limb.template operator()<left_bits, num_left_tables>(left_normalized);
 
    // Call builder method to create plookup constraints.
    // The MultiTable table index can be derived from `lane_idx`
    // Each lane_idx has a different rotation amount, which changes sizes of left/right slices
    // and therefore the selector constants required (i.e. the Q1, Q2, Q3 values in the earlier example)
    const auto accumulator_witnesses = limb.context->create_gates_from_plookup_accumulators(
        (plookup::MultiTableId)((size_t)KECCAK_NORMALIZE_AND_ROTATE + lane_index),
        lookup,
        limb.normalize().get_witness_index());
 
    // extract the most significant bit of the normalized output from the final lookup entry in column C3
    msb = field_ct::from_witness_index(limb.get_context(),
                                       accumulator_witnesses[ColumnIdx::C3][num_left_tables + num_right_tables - 1]);
 
    // Extract the witness that maps to the normalized right slice
    const field_t<Builder> right_output =
        field_t<Builder>::from_witness_index(limb.get_context(), accumulator_witnesses[ColumnIdx::C2][0]);
 
    if (num_left_tables == 0) {
        // if the left slice size is 0 bits (i.e. no rotation), return `right_output`
        return right_output;
    } else {
        // Extract the normalized left slice
        const field_t<Builder> left_output = field_t<Builder>::from_witness_index(
            limb.get_context(), accumulator_witnesses[ColumnIdx::C2][num_right_tables]);
 
        // Stitch the right/left slices together to create our rotated output
        constexpr uint256_t shift = BASE.pow(ROTATIONS[lane_index]);
        return (left_output + right_output * shift);
    }
}
 
template <typename Builder> void keccak<Builder>::compute_twisted_state(keccak_state& internal)
{
    for (size_t i = 0; i < NUM_KECCAK_LANES; ++i) {
        internal.twisted_state[i] = ((internal.state[i] * 11) + internal.state_msb[i]).normalize();
    }
}
 
template <typename Builder> void keccak<Builder>::theta(keccak_state& internal)
{
    std::array<field_ct, 5> C;
    std::array<field_ct, 5> D;
 
    auto& state = internal.state;
    const auto& twisted_state = internal.twisted_state;
    for (size_t i = 0; i < 5; ++i) {
 
        C[i] = field_ct::accumulate({ twisted_state[i],
                                      twisted_state[5 + i],
                                      twisted_state[10 + i],
                                      twisted_state[15 + i],
                                      twisted_state[20 + i] });
    }
 
    for (size_t i = 0; i < 5; ++i) {
        const auto non_shifted_equivalent = (C[(i + 4) % 5]);
        const auto shifted_equivalent = C[(i + 1) % 5] * BASE;
        D[i] = (non_shifted_equivalent + shifted_equivalent);
    }
 
    static constexpr uint256_t divisor = BASE.pow(64);
    static constexpr uint256_t multiplicand = BASE.pow(65);
    for (size_t i = 0; i < 5; ++i) {
        uint256_t D_native = D[i].get_value();
        const auto [D_quotient, lo_native] = D_native.divmod(BASE);
        const uint256_t hi_native = D_quotient / divisor;
        const uint256_t mid_native = D_quotient - hi_native * divisor;
 
        field_ct hi(witness_ct(internal.context, hi_native));
        field_ct mid(witness_ct(internal.context, mid_native));
        field_ct lo(witness_ct(internal.context, lo_native));
 
        // assert equal should cost 1 gate (multipliers are all constants)
        D[i].assert_equal((hi * multiplicand).add_two(mid * 11, lo));
        internal.context->create_new_range_constraint(hi.get_witness_index(), static_cast<uint64_t>(BASE));
        internal.context->create_new_range_constraint(lo.get_witness_index(), static_cast<uint64_t>(BASE));
 
        // If number of bits in KECCAK_THETA_OUTPUT table does NOT cleanly divide 64,
        // we need an additional range constraint to ensure that mid < 11^64
        if constexpr (64 % plookup::keccak_tables::Theta::TABLE_BITS == 0) {
            // N.B. we could optimize out 5 gates per round here but it's very fiddly...
            // In previous section, D[i] = X + Y (non shifted equiv and shifted equiv)
            // We also want to validate D[i] == hi' + mid' + lo (where hi', mid' are hi, mid scaled by constants)
            // We *could* create a big addition gate to validate the previous logic w. following structure:
            // | w1 | w2  | w3 | w4 |
            // | -- | --- | -- | -- |
            // | hi | mid | lo | X  |
            // | P0 | P1  | P2 | Y  |
            // To save a gate, we would need to place the wires for the first KECCAK_THETA_OUTPUT plookup gate
            // at P0, P1, P2. This is fiddly builder logic that is circuit-width-dependent
            // (this would save 120 gates per hash block... not worth making the code less readable for that)
            D[i] = plookup_read<Builder>::read_from_1_to_2_table(KECCAK_THETA_OUTPUT, mid);
        } else {
            const auto accumulators = plookup_read<Builder>::get_lookup_accumulators(KECCAK_THETA_OUTPUT, D[i]);
            D[i] = accumulators[ColumnIdx::C2][0];
 
            // Ensure input to lookup is < 11^64,
            // by validating most significant input slice is < 11^{64 mod slice_bits}
            const field_ct most_significant_slice = accumulators[ColumnIdx::C1][accumulators[ColumnIdx::C1].size() - 1];
 
            // N.B. cheaper to validate (11^{64 mod slice_bits} - slice < 2^14) as this
            // prevents an extra range table from being created
            constexpr uint256_t maximum = BASE.pow(64 % plookup::keccak_tables::Theta::TABLE_BITS);
            const field_ct target = -most_significant_slice + maximum;
            BB_ASSERT_GT((uint256_t(1) << Builder::DEFAULT_PLOOKUP_RANGE_BITNUM) - 1, maximum);
            target.create_range_constraint(Builder::DEFAULT_PLOOKUP_RANGE_BITNUM,
                                           "input to KECCAK_THETA_OUTPUT too large!");
        }
    }
 
    // compute state[j * 5 + i] XOR D[i] in base-11 representation
    for (size_t i = 0; i < 5; ++i) {
        for (size_t j = 0; j < 5; ++j) {
            state[j * 5 + i] = state[j * 5 + i] + D[i];
        }
    }
}
 
template <typename Builder> void keccak<Builder>::rho(keccak_state& internal)
{
    constexpr_for<0, NUM_KECCAK_LANES, 1>(
        [&]<size_t i>() { internal.state[i] = normalize_and_rotate<i>(internal.state[i], internal.state_msb[i]); });
}
 
template <typename Builder> void keccak<Builder>::pi(keccak_state& internal)
{
    std::array<field_ct, NUM_KECCAK_LANES> B;
 
    for (size_t j = 0; j < 5; ++j) {
        for (size_t i = 0; i < 5; ++i) {
            B[j * 5 + i] = internal.state[j * 5 + i];
        }
    }
 
    for (size_t y = 0; y < 5; ++y) {
        for (size_t x = 0; x < 5; ++x) {
            size_t u = (0 * x + 1 * y) % 5;
            size_t v = (2 * x + 3 * y) % 5;
 
            internal.state[v * 5 + u] = B[5 * y + x];
        }
    }
}
 
template <typename Builder> void keccak<Builder>::chi(keccak_state& internal)
{
    // (cost = 12 * 25 = 300?)
    auto& state = internal.state;
 
    for (size_t y = 0; y < 5; ++y) {
        std::array<field_ct, 5> lane_outputs;
        for (size_t x = 0; x < 5; ++x) {
            const auto A = state[y * 5 + x];
            const auto B = state[y * 5 + ((x + 1) % 5)];
            const auto C = state[y * 5 + ((x + 2) % 5)];
 
            // vv should cost 1 gate
            lane_outputs[x] = (A + A + CHI_OFFSET).add_two(-B, C);
        }
        for (size_t x = 0; x < 5; ++x) {
            // Normalize lane outputs and assign to internal.state
            auto accumulators = plookup_read<Builder>::get_lookup_accumulators(KECCAK_CHI_OUTPUT, lane_outputs[x]);
            internal.state[y * 5 + x] = accumulators[ColumnIdx::C2][0];
            internal.state_msb[y * 5 + x] = accumulators[ColumnIdx::C3][accumulators[ColumnIdx::C3].size() - 1];
        }
    }
}
 
template <typename Builder> void keccak<Builder>::iota(keccak_state& internal, size_t round)
{
    const field_ct xor_result = internal.state[0] + SPARSE_RC[round];
 
    // normalize lane value so that we don't overflow our base11 modulus boundary in the next round
    internal.state[0] = normalize_and_rotate<0>(xor_result, internal.state_msb[0]);
 
    // No need to add constraints to compute twisted repr if this is the last round
    if (round != NUM_KECCAK_ROUNDS - 1) {
        compute_twisted_state(internal);
    }
}
 
template <typename Builder> void keccak<Builder>::keccakf1600(keccak_state& internal)
{
    for (size_t i = 0; i < NUM_KECCAK_ROUNDS; ++i) {
        theta(internal);
        rho(internal);
        pi(internal);
        chi(internal);
        iota(internal, i);
    }
}
 
template <typename Builder>
void keccak<Builder>::sponge_absorb(keccak_state& internal,
                                    const std::vector<field_ct>& input_buffer,
                                    const std::vector<field_ct>& msb_buffer)
{
    const size_t l = input_buffer.size();
 
    const size_t num_blocks = l / (BLOCK_SIZE / 8);
 
    for (size_t i = 0; i < num_blocks; ++i) {
        if (i == 0) {
            for (size_t j = 0; j < LIMBS_PER_BLOCK; ++j) {
                internal.state[j] = input_buffer[j];
                internal.state_msb[j] = msb_buffer[j];
            }
            for (size_t j = LIMBS_PER_BLOCK; j < NUM_KECCAK_LANES; ++j) {
                internal.state[j] = witness_ct::create_constant_witness(internal.context, 0);
                internal.state_msb[j] = witness_ct::create_constant_witness(internal.context, 0);
            }
        } else {
            for (size_t j = 0; j < LIMBS_PER_BLOCK; ++j) {
                internal.state[j] += input_buffer[i * LIMBS_PER_BLOCK + j];
                internal.state[j] = normalize_and_rotate<0>(internal.state[j], internal.state_msb[j]);
            }
        }
 
        compute_twisted_state(internal);
        keccakf1600(internal);
    }
}
 
template <typename Builder> byte_array<Builder> keccak<Builder>::sponge_squeeze(keccak_state& internal)
{
    byte_array_ct result(internal.context);
 
    // Each hash limb represents a little-endian integer. Need to reverse bytes before we write into the output array
    for (size_t i = 0; i < 4; ++i) {
        field_ct output_limb = plookup_read<Builder>::read_from_1_to_2_table(KECCAK_FORMAT_OUTPUT, internal.state[i]);
        byte_array_ct limb_bytes(output_limb, 8);
        byte_array_ct little_endian_limb_bytes(internal.context, 8);
        little_endian_limb_bytes[0] = limb_bytes[7];
        little_endian_limb_bytes[1] = limb_bytes[6];
        little_endian_limb_bytes[2] = limb_bytes[5];
        little_endian_limb_bytes[3] = limb_bytes[4];
        little_endian_limb_bytes[4] = limb_bytes[3];
        little_endian_limb_bytes[5] = limb_bytes[2];
        little_endian_limb_bytes[6] = limb_bytes[1];
        little_endian_limb_bytes[7] = limb_bytes[0];
        result.write(little_endian_limb_bytes);
    }
    return result;
}
 
template <typename Builder> std::vector<field_t<Builder>> keccak<Builder>::format_input_lanes(byte_array_ct& input)
{
    auto* ctx = input.get_context();
 
    const size_t input_size = input.size();
    // max_blocks_length = maximum number of bytes to hash
    const size_t max_blocks = (input_size + BLOCK_SIZE) / BLOCK_SIZE;
    const size_t max_blocks_length = (BLOCK_SIZE * (max_blocks));
 
    byte_array_ct block_bytes(input);
 
    const size_t byte_difference = max_blocks_length - input_size;
    byte_array_ct padding_bytes(ctx, byte_difference);
    for (size_t i = 0; i < byte_difference; ++i) {
        padding_bytes[i] = witness_ct::create_constant_witness(ctx, 0);
    }
    block_bytes.write(padding_bytes);
 
    // Keccak requires that 0x1 is appended after the final byte of input data.
    // Similarly, the final byte of the final padded block must be 0x80.
    const auto terminating_byte = input_size;
    const auto terminating_block_byte = block_bytes.size() - 1;
    block_bytes[terminating_byte] = witness_ct::create_constant_witness(ctx, 0x1);
    block_bytes[terminating_block_byte] = witness_ct::create_constant_witness(ctx, 0x80);
 
    // keccak lanes interpret memory as little-endian integers,
    // means we need to swap our byte ordering...
    for (size_t i = 0; i < block_bytes.size(); i += 8) {
        std::array<field_ct, 8> temp;
        for (size_t j = 0; j < 8; ++j) {
            temp[j] = block_bytes[i + j];
        }
        block_bytes[i] = temp[7];
        block_bytes[i + 1] = temp[6];
        block_bytes[i + 2] = temp[5];
        block_bytes[i + 3] = temp[4];
        block_bytes[i + 4] = temp[3];
        block_bytes[i + 5] = temp[2];
        block_bytes[i + 6] = temp[1];
        block_bytes[i + 7] = temp[0];
    }
    const size_t byte_size = block_bytes.size();
 
    const size_t num_limbs = byte_size / WORD_SIZE;
    std::vector<field_ct> sliced_buffer;
 
    // populate a vector of 64-bit limbs from our byte array
    for (size_t i = 0; i < num_limbs; ++i) {
        field_ct sliced;
        if (i * WORD_SIZE + WORD_SIZE > byte_size) {
            const size_t slice_size = byte_size - (i * WORD_SIZE);
            const size_t byte_shift = (WORD_SIZE - slice_size) * 8;
            sliced = field_ct(block_bytes.slice(i * WORD_SIZE, slice_size));
            sliced = (sliced * (uint256_t(1) << byte_shift)).normalize();
        } else {
            sliced = field_ct(block_bytes.slice(i * WORD_SIZE, WORD_SIZE));
        }
        sliced_buffer.emplace_back(sliced);
    }
 
    return sliced_buffer;
}
 
// Returns the keccak f1600 permutation of the input state
// We first convert the state into 'extended' representation, along with the 'twisted' state
// and then we call keccakf1600() with this keccak 'internal state'
// Finally, we convert back the state from the extented representation
template <typename Builder>
std::array<field_t<Builder>, keccak<Builder>::NUM_KECCAK_LANES> keccak<Builder>::permutation_opcode(
    std::array<field_t<Builder>, NUM_KECCAK_LANES> state, Builder* ctx)
{
    std::vector<field_t<Builder>> converted_buffer(NUM_KECCAK_LANES);
    std::vector<field_t<Builder>> msb_buffer(NUM_KECCAK_LANES);
    // populate keccak_state, convert our 64-bit lanes into an extended base-11 representation
    keccak_state internal;
    internal.context = ctx;
    for (size_t i = 0; i < state.size(); ++i) {
        const auto accumulators = plookup_read<Builder>::get_lookup_accumulators(KECCAK_FORMAT_INPUT, state[i]);
        internal.state[i] = accumulators[ColumnIdx::C2][0];
        internal.state_msb[i] = accumulators[ColumnIdx::C3][accumulators[ColumnIdx::C3].size() - 1];
    }
    compute_twisted_state(internal);
    keccakf1600(internal);
    // we convert back to the normal lanes
    return extended_2_normal(internal);
}
 
// This function is similar to sponge_absorb()
// but it uses permutation_opcode() instead of calling directly keccakf1600().
// As a result, this function is less efficient and should only be used to test permutation_opcode()
template <typename Builder>
void keccak<Builder>::sponge_absorb_with_permutation_opcode(keccak_state& internal,
                                                            std::vector<field_t<Builder>>& input_buffer,
                                                            const size_t input_size)
{
    // populate keccak_state
    const size_t num_blocks = input_size / (BLOCK_SIZE / 8);
    for (size_t i = 0; i < num_blocks; ++i) {
        if (i == 0) {
            for (size_t j = 0; j < LIMBS_PER_BLOCK; ++j) {
                internal.state[j] = input_buffer[j];
            }
            for (size_t j = LIMBS_PER_BLOCK; j < NUM_KECCAK_LANES; ++j) {
                internal.state[j] = witness_ct::create_constant_witness(internal.context, 0);
            }
        } else {
            for (size_t j = 0; j < LIMBS_PER_BLOCK; ++j) {
                // TODO(https://github.com/AztecProtocol/barretenberg/issues/1494): potential issue with usage of
                // `create_logic_constraint`?
                internal.state[j] = stdlib::logic<Builder>::create_logic_constraint(
                    internal.state[j], input_buffer[i * LIMBS_PER_BLOCK + j], 64, true);
            }
        }
        internal.state = permutation_opcode(internal.state, internal.context);
    }
}
 
// This function computes the keccak hash, like the hash() function
// but it uses permutation_opcode() instead of calling directly keccakf1600().
// As a result, this function is less efficient and should only be used to test permutation_opcode()
template <typename Builder>
stdlib::byte_array<Builder> keccak<Builder>::hash_using_permutation_opcode(byte_array_ct& input)
{
    auto ctx = input.get_context();
 
    if (ctx == nullptr) {
        // if buffer is constant compute hash and return w/o creating constraints
        byte_array_ct output(nullptr, 32);
        const std::vector<uint8_t> result = hash_native(input.get_value());
        for (size_t i = 0; i < 32; ++i) {
            output[i] = result[i];
        }
        return output;
    }
 
    // convert the input byte array into 64-bit keccak lanes (+ apply padding)
    auto formatted_slices = format_input_lanes(input);
 
    keccak_state internal;
    internal.context = ctx;
    sponge_absorb_with_permutation_opcode(internal, formatted_slices, formatted_slices.size());
 
    auto result = sponge_squeeze_for_permutation_opcode(internal.state, ctx);
 
    return result;
}
 
template <typename Builder> stdlib::byte_array<Builder> keccak<Builder>::hash(byte_array_ct& input)
{
    auto ctx = input.get_context();
 
    const auto constant_case = [&] { // if buffer is constant, compute hash and return w/o creating constraints
        byte_array_ct output(nullptr, 32);
        const std::vector<uint8_t> result = hash_native(input.get_value());
        for (size_t i = 0; i < 32; ++i) {
            output[i] = result[i];
        }
        return output;
    };
 
    if (ctx == nullptr) {
        return constant_case();
    }
 
    // convert the input byte array into 64-bit keccak lanes (+ apply padding)
    auto formatted_slices = format_input_lanes(input);
 
    std::vector<field_ct> converted_buffer(formatted_slices.size());
    std::vector<field_ct> msb_buffer(formatted_slices.size());
 
    // populate keccak_state, convert our 64-bit lanes into an extended base-11 representation
    keccak_state internal;
    internal.context = ctx;
    for (size_t i = 0; i < formatted_slices.size(); ++i) {
        const auto accumulators =
            plookup_read<Builder>::get_lookup_accumulators(KECCAK_FORMAT_INPUT, formatted_slices[i]);
        converted_buffer[i] = accumulators[ColumnIdx::C2][0];
        msb_buffer[i] = accumulators[ColumnIdx::C3][accumulators[ColumnIdx::C3].size() - 1];
    }
 
    sponge_absorb(internal, converted_buffer, msb_buffer);
 
    auto result = sponge_squeeze(internal);
 
    return result;
}
 
// Convert the 'extended' representation of the internal Keccak state into the usual array of 64 bits lanes
template <typename Builder>
std::array<field_t<Builder>, keccak<Builder>::NUM_KECCAK_LANES> keccak<Builder>::extended_2_normal(
    keccak_state& internal)
{
    std::array<field_t<Builder>, NUM_KECCAK_LANES> conversion;
 
    // Each hash limb represents a little-endian integer. Need to reverse bytes before we write into the output array
    for (size_t i = 0; i < internal.state.size(); ++i) {
        field_ct output_limb = plookup_read<Builder>::read_from_1_to_2_table(KECCAK_FORMAT_OUTPUT, internal.state[i]);
        conversion[i] = output_limb;
    }
 
    return conversion;
}
 
// This function is the same as sponge_squeeze, except that it does not convert
// from extended representation and assumes the input has already being converted
template <typename Builder>
stdlib::byte_array<Builder> keccak<Builder>::sponge_squeeze_for_permutation_opcode(
    std::array<field_t<Builder>, NUM_KECCAK_LANES> lanes, Builder* context)
{
    byte_array_ct result(context);
 
    // Each hash limb represents a little-endian integer. Need to reverse bytes before we write into the output array
    for (size_t i = 0; i < 4; ++i) {
        byte_array_ct limb_bytes(lanes[i], 8);
        byte_array_ct little_endian_limb_bytes(context, 8);
        little_endian_limb_bytes[0] = limb_bytes[7];
        little_endian_limb_bytes[1] = limb_bytes[6];
        little_endian_limb_bytes[2] = limb_bytes[5];
        little_endian_limb_bytes[3] = limb_bytes[4];
        little_endian_limb_bytes[4] = limb_bytes[3];
        little_endian_limb_bytes[5] = limb_bytes[2];
        little_endian_limb_bytes[6] = limb_bytes[1];
        little_endian_limb_bytes[7] = limb_bytes[0];
        result.write(little_endian_limb_bytes);
    }
    return result;
}
 
template <typename Builder> void generate_keccak_test_circuit(Builder& builder, size_t num_iterations)
{
    std::string in = "abcdefghijklmnopqrstuvwxyz0123456789abcdefghijklmnopqrstuvwxyz01";
 
    stdlib::byte_array<Builder> input(&builder, in);
    for (size_t i = 0; i < num_iterations; i++) {
        input = stdlib::keccak<Builder>::hash(input);
    }
}
 
template class keccak<bb::UltraCircuitBuilder>;
template class keccak<bb::MegaCircuitBuilder>;
template void generate_keccak_test_circuit(bb::UltraCircuitBuilder&, size_t);
template void generate_keccak_test_circuit(bb::MegaCircuitBuilder&, size_t);
 
} // namespace bb::stdlib