byte_array.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 "byte_array.hpp"
 
#include "../circuit_builders/circuit_builders.hpp"
#include "barretenberg/common/assert.hpp"
 
using namespace bb;
 
namespace bb::stdlib {
 
template <typename Builder>
byte_array<Builder>::byte_array(Builder* parent_context, std::vector<uint8_t> const& input)
    : context(parent_context)
    , values(input.size())
{
    BB_ASSERT(context);
    for (size_t i = 0; i < input.size(); ++i) {
        uint8_t c = input[i];
        field_t<Builder> value(witness_t(context, c));
        value.create_range_constraint(8, "byte_array: vector entry larger than 1 byte.");
        values[i] = value;
    }
    set_free_witness_tag();
}
template <typename Builder>
byte_array<Builder>::byte_array(Builder* parent_context, const std::string& input)
    : byte_array(parent_context, std::vector<uint8_t>(input.begin(), input.end()))
{}
 
template <typename Builder>
byte_array<Builder> byte_array<Builder>::from_constants(Builder* parent_context, std::vector<uint8_t> const& input)
{
    bytes_t const_values;
    const_values.reserve(input.size());
    for (const auto& byte : input) {
        // Create constant field elements - no witness, no constraints
        const_values.push_back(field_t<Builder>(parent_context, byte));
    }
    return byte_array(parent_context, const_values);
}
 
template <typename Builder>
byte_array<Builder>::byte_array(const field_t<Builder>& input,
                                const size_t num_bytes,
                                std::optional<uint256_t> test_val)
{
    using field_t = field_t<Builder>;
 
    static constexpr size_t max_num_bytes = 32;
    static constexpr size_t midpoint = max_num_bytes / 2;
    constexpr uint256_t one(1);
 
    BB_ASSERT_LTE(num_bytes, max_num_bytes);
    // If a test 256-bit is injected, use it to create a byte decomposition.
    const uint256_t value = test_val.has_value() ? *test_val : static_cast<uint256_t>(input.get_value());
 
    values.resize(num_bytes);
 
    // To optimize the computation of the reconstructed_hi  and reconstructed_lo, we use the `field_t::accumulate`
    // method.
    std::vector<field_t> accumulator_lo;
    std::vector<field_t> accumulator_hi;
 
    context = input.get_context();
 
    for (size_t i = 0; i < num_bytes; ++i) {
 
        size_t bit_start = (num_bytes - i - 1) * 8;
        size_t bit_end = bit_start + 8;
        const field_t scaling_factor = one << bit_start;
 
        // Extract the current byte
        const uint256_t byte_val = value.slice(bit_start, bit_end);
        // Ensure that current `byte_array` element is a witness iff input is a witness and that it is range
        // constrained.
        field_t byte = input.is_constant() ? field_t(byte_val) : witness_t(context, byte_val);
        byte.create_range_constraint(8, "byte_array: byte extraction failed.");
        values[i] = byte;
 
        if (i < midpoint) {
            accumulator_hi.push_back(scaling_factor * byte);
        } else {
            accumulator_lo.push_back(scaling_factor * byte);
        }
    }
 
    // Reconstruct the high and low limbs of input from the byte decomposition
    const field_t reconstructed_lo = field_t::accumulate(accumulator_lo);
    const field_t reconstructed_hi = field_t::accumulate(accumulator_hi);
    const field_t reconstructed = reconstructed_hi + reconstructed_lo;
 
    // Ensure that the reconstruction succeeded
    input.assert_equal(reconstructed);
 
    // Handle the case when the decomposition is not unique
    if (num_bytes == 32) {
        // For a modulus `r`, split `r - 1` into limbs
        constexpr uint256_t modulus_minus_one = fr::modulus - 1;
        constexpr uint256_t s_lo = modulus_minus_one.slice(0, 128);
        constexpr uint256_t s_hi = modulus_minus_one.slice(128, 256);
        const uint256_t shift = uint256_t(1) << 128;
 
        // Ensure that `(r - 1).lo + 2 ^ 128 - reconstructed_lo` is a 129 bit integer by slicing it into a 128- and 1-
        // bit chunks.
        const field_t diff_lo = -reconstructed_lo + s_lo + shift;
        const uint256_t diff_lo_value = diff_lo.get_value();
 
        // Extract the "borrow" bit
        const uint256_t diff_lo_hi_value = (diff_lo_value >> 128);
        const field_t diff_lo_hi =
            input.is_constant() ? field_t(diff_lo_hi_value) : witness_t<Builder>(context, diff_lo_hi_value);
        diff_lo_hi.create_range_constraint(1, "byte_array: y_overlap is not a bit");
 
        // Extract first 128 bits of `diff_lo`
        const uint256_t lo_mask = shift - 1;
        const uint256_t lo = diff_lo_value & lo_mask;
        const field_t diff_lo_lo = input.is_constant() ? field_t(lo) : witness_t(context, lo);
        diff_lo_lo.create_range_constraint(128, "byte_array: y_remainder doesn't fit in 128 bits.");
 
        // Both chunks were computed out-of-circuit - need to constrain. The range constraints above ensure that
        // they are not overlapping.
        diff_lo.assert_equal(diff_lo_lo + diff_lo_hi * shift);
 
        const field_t overlap = -diff_lo_hi + 1;
        // Ensure that (r - 1).hi  - reconstructed_hi/shift - overlap is positive.
        // SAFETY: reconstructed_hi is always a multiple of 2^128 by construction
        // (bytes 0-15 all have scaling factors ≥ 2^128)
        const field_t diff_hi = (-reconstructed_hi / shift).add_two(s_hi, -overlap);
        diff_hi.create_range_constraint(128, "byte_array: y_hi doesn't fit in 128 bits.");
    }
 
    set_origin_tag(input.tag);
}
 
template <typename Builder>
byte_array<Builder>::byte_array(Builder* parent_context, bytes_t const& input)
    : context(parent_context)
    , values(input)
{}
 
template <typename Builder>
byte_array<Builder>::byte_array(Builder* parent_context, bytes_t&& input)
    : context(parent_context)
    , values(std::move(input))
{}
 
template <typename Builder>
byte_array<Builder>::byte_array(const byte_array& other)
    : context(other.context)
{
    std::copy(other.values.begin(), other.values.end(), std::back_inserter(values));
}
 
template <typename Builder>
byte_array<Builder>::byte_array(byte_array&& other) noexcept
    : context(other.context)
    , values(std::move(other.values))
{}
 
template <typename Builder> byte_array<Builder>& byte_array<Builder>::operator=(const byte_array& other)
{
    context = other.context;
    values = std::vector<field_t<Builder>>();
    std::copy(other.values.begin(), other.values.end(), std::back_inserter(values));
    return *this;
}
 
template <typename Builder> byte_array<Builder>& byte_array<Builder>::operator=(byte_array&& other) noexcept
{
    context = other.context;
    values = std::move(other.values);
    return *this;
}
 
template <typename Builder> byte_array<Builder>::operator field_t<Builder>() const
{
    const size_t bytes = values.size();
    static constexpr uint256_t one(1);
    std::vector<field_t<Builder>> scaled_values;
 
    for (size_t i = 0; i < bytes; ++i) {
        const field_t<Builder> scaling_factor(one << (8 * (bytes - i - 1)));
        scaled_values.push_back(values[i] * scaling_factor);
    }
 
    return field_t<Builder>::accumulate(scaled_values);
}
 
template <typename Builder> byte_array<Builder>& byte_array<Builder>::write(byte_array const& other)
{
    values.insert(values.end(), other.bytes().begin(), other.bytes().end());
    return *this;
}
 
template <typename Builder> byte_array<Builder>& byte_array<Builder>::write_at(byte_array const& other, size_t index)
{
    BB_ASSERT_LTE(index + other.values.size(), values.size());
    for (size_t i = 0; i < other.values.size(); i++) {
        values[i + index] = other.values[i];
    }
    return *this;
}
 
template <typename Builder> byte_array<Builder> byte_array<Builder>::slice(size_t offset) const
{
    BB_ASSERT_LTE(offset, values.size());
    return byte_array(context, bytes_t(values.begin() + static_cast<ptrdiff_t>(offset), values.end()));
}
 
template <typename Builder> byte_array<Builder> byte_array<Builder>::slice(size_t offset, size_t length) const
{
    BB_ASSERT_LTE(offset, values.size());
    // it's <= cause vector constructor doesn't include end point
    BB_ASSERT_LTE(length, values.size() - offset);
    auto start = values.begin() + static_cast<ptrdiff_t>(offset);
    auto end = values.begin() + static_cast<ptrdiff_t>((offset + length));
    return byte_array(context, bytes_t(start, end));
}
 
template <typename Builder> byte_array<Builder> byte_array<Builder>::reverse() const
{
    if (values.empty()) {
        return *this;
    }
    bytes_t bytes(values.size());
    size_t offset = bytes.size() - 1;
    for (size_t i = 0; i < bytes.size(); i += 1, offset -= 1) {
        bytes[offset] = values[i];
    }
    return byte_array(context, bytes);
}
 
template <typename Builder> std::vector<uint8_t> byte_array<Builder>::get_value() const
{
    const size_t length = values.size();
    std::vector<uint8_t> bytes(length, 0);
    for (size_t i = 0; i < length; ++i) {
        bytes[i] = static_cast<uint8_t>(values[i].get_value());
    }
    return bytes;
}
 
template class byte_array<bb::UltraCircuitBuilder>;
template class byte_array<bb::MegaCircuitBuilder>;
 
} // namespace bb::stdlib