cycle_scalar.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke], commit: a48c205d6dcd4338f5b83b4fda18bff6015be07b}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "./cycle_scalar.hpp"
#include "./cycle_group.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders.hpp"
#include "barretenberg/stdlib/primitives/field/field_utils.hpp"
 
#include <tuple>
 
namespace bb::stdlib {
 
template <typename Builder>
cycle_scalar<Builder>::cycle_scalar(const field_t& lo, const field_t& hi, [[maybe_unused]] SkipValidation flag)
    : _lo(lo)
    , _hi(hi)
{}
 
template <typename Builder>
cycle_scalar<Builder>::cycle_scalar(const field_t& lo, const field_t& hi)
    : _lo(lo)
    , _hi(hi)
{
    validate_scalar_is_in_field();
}
 
template <typename Builder> cycle_scalar<Builder>::cycle_scalar(const ScalarField& in)
{
    const uint256_t value(in);
    const auto [lo_v, hi_v] = decompose_into_lo_hi_u256(value);
    _lo = lo_v;
    _hi = hi_v;
}
 
template <typename Builder>
cycle_scalar<Builder> cycle_scalar<Builder>::from_witness(Builder* context, const ScalarField& value)
{
    const uint256_t value_u256(value);
    const auto [lo_v, hi_v] = decompose_into_lo_hi_u256(value_u256);
    field_t lo = witness_t<Builder>(context, lo_v);
    field_t hi = witness_t<Builder>(context, hi_v);
    lo.set_free_witness_tag();
    hi.set_free_witness_tag();
 
    cycle_scalar result{ lo, hi };
 
    return result;
}
 
template <typename Builder> cycle_scalar<Builder>::cycle_scalar(BigScalarField& scalar)
{
    constexpr uint64_t NUM_LIMB_BITS = BigScalarField::NUM_LIMB_BITS;
 
    if (scalar.is_constant()) {
        const uint256_t value((scalar.get_value() % uint512_t(ScalarField::modulus)).lo);
        const auto [value_lo, value_hi] = decompose_into_lo_hi_u256(value);
 
        _lo = value_lo;
        _hi = value_hi;
        _lo.set_origin_tag(scalar.get_origin_tag());
        _hi.set_origin_tag(scalar.get_origin_tag());
        return;
    }
 
    // Step 1: Ensure the bigfield scalar fits into LO_BITS + HI_BITS by reducing if necessary. Note: we can tolerate
    // the scalar being > ScalarField::modulus, because performing a scalar mul implicitly performs a modular reduction.
    if (scalar.get_maximum_value() >= (uint512_t(1) << (LO_BITS + HI_BITS))) {
        scalar.self_reduce();
    }
 
    field_t limb0 = scalar.binary_basis_limbs[0].element;
    field_t limb1 = scalar.binary_basis_limbs[1].element;
    field_t limb2 = scalar.binary_basis_limbs[2].element;
    field_t limb3 = scalar.binary_basis_limbs[3].element;
 
    uint256_t limb1_max = scalar.binary_basis_limbs[1].maximum_value;
 
    // Step 2: Ensure that limb0 only contains at most NUM_LIMB_BITS. If not, slice off the excess and add it into limb1
    uint256_t limb0_max = scalar.binary_basis_limbs[0].maximum_value;
    if (limb0_max > BigScalarField::DEFAULT_MAXIMUM_LIMB) {
 
        // Split limb0 into lo (NUM_LIMB_BITS) and hi (remaining bits) slices. Note that no_wrap_split_at enforces range
        // constraints of NUM_LIMB_BITS and (limb0_max_bits - NUM_LIMB_BITS) respectively on the slices.
        const auto limb0_max_bits = static_cast<size_t>(limb0_max.get_msb() + 1);
        auto [limb0_lo, limb0_hi] = limb0.no_wrap_split_at(NUM_LIMB_BITS, limb0_max_bits);
 
        // Move the high bits from limb0 into limb1
        limb0 = limb0_lo;
        limb1 += limb0_hi;
        uint256_t limb0_hi_max = limb0_max >> NUM_LIMB_BITS;
        limb1_max += limb0_hi_max;
    }
 
    // Sanity check that limb1 is the limb that contributes both to *this.lo and *this.hi
    BB_ASSERT_GT(NUM_LIMB_BITS * 2, LO_BITS);
    BB_ASSERT_LT(NUM_LIMB_BITS, LO_BITS);
 
    // Step 3: limb1 may contribute to both *this._lo and *this._hi. Compute the values of the two limb1 slices
    const size_t lo_bits_in_limb_1 = LO_BITS - NUM_LIMB_BITS;
 
    field_t limb1_lo;
    field_t limb1_hi;
 
    // Edge case: If limb1's maximum value fits entirely in the low bits, no split is needed.
    if (limb1_max < (uint256_t(1) << lo_bits_in_limb_1)) {
        limb1_lo = limb1;
        limb1_hi = field_t(0);
    } else { // Otherwise, split limb1 into lo and hi parts
        const auto limb1_max_bits = static_cast<size_t>(limb1_max.get_msb() + 1);
        std::tie(limb1_lo, limb1_hi) = limb1.no_wrap_split_at(lo_bits_in_limb_1, limb1_max_bits);
    }
 
    // Propagate the origin tag to the chunks of limb1
    limb1_lo.set_origin_tag(limb1.get_origin_tag());
    limb1_hi.set_origin_tag(limb1.get_origin_tag());
 
    // Step 4: Construct *this._lo out of limb0 and limb1_lo
    _lo = limb0 + (limb1_lo * BigScalarField::shift_1);
 
    // Step 5: Construct *this._hi out of limb1_hi, limb2 and limb3
    const uint256_t limb_2_shift = uint256_t(1) << ((2 * NUM_LIMB_BITS) - LO_BITS);
    const uint256_t limb_3_shift = uint256_t(1) << ((3 * NUM_LIMB_BITS) - LO_BITS);
    _hi = limb1_hi.add_two(limb2 * limb_2_shift, limb3 * limb_3_shift);
 
    // Manually propagate the origin tag of the scalar to the lo/hi limbs
    _lo.set_origin_tag(scalar.get_origin_tag());
    _hi.set_origin_tag(scalar.get_origin_tag());
 
    validate_scalar_is_in_field();
};
 
template <typename Builder> bool cycle_scalar<Builder>::is_constant() const
{
    return (_lo.is_constant() && _hi.is_constant());
}
 
template <typename Builder> void cycle_scalar<Builder>::validate_scalar_is_in_field() const
{
    // Using _unsafe variant: range constraints are deferred to batch_mul's decompose_into_default_range
    validate_split_in_field_unsafe(_lo, _hi, LO_BITS, ScalarField::modulus);
}
 
template <typename Builder> typename cycle_scalar<Builder>::ScalarField cycle_scalar<Builder>::get_value() const
{
    uint256_t lo_v(_lo.get_value());
    uint256_t hi_v(_hi.get_value());
    return ScalarField(lo_v + (hi_v << LO_BITS));
}
 
template class cycle_scalar<bb::UltraCircuitBuilder>;
template class cycle_scalar<bb::MegaCircuitBuilder>;
 
} // namespace bb::stdlib