ecc_wnaf_relation_impl.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Raju], commit: 2a49eb6 }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "ecc_wnaf_relation.hpp"
 
namespace bb {
 
template <typename FF>
template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
void ECCVMWnafRelationImpl<FF>::accumulate(ContainerOverSubrelations& accumulator,
                                           const AllEntities& in,
                                           const Parameters& /*unused*/,
                                           const FF& scaling_factor)
{
    using Accumulator = std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
    auto lagrange_first = View(in.lagrange_first);
    auto scalar_sum = View(in.precompute_scalar_sum);
    auto scalar_sum_shift = View(in.precompute_scalar_sum_shift);
    auto q_transition = View(in.precompute_point_transition);
    auto round = View(in.precompute_round);
    auto round_shift = View(in.precompute_round_shift);
    auto pc = View(in.precompute_pc); // note that this is a _point-counter_.
    auto pc_shift = View(in.precompute_pc_shift);
    // precompute_select is a boolean column that is 0 at the initial row and 1 at all subsequent active rows in the
    // precompute table. We only evaluate the ecc_wnaf_relation and the ecc_point_table_relation if
    // `precompute_select=1`. As a reminder, this latter is 0 at the initial row and then 1 at the rest of the (active)
    // rows of the Precomputed table. The fact that `precompute_select` is correctly computed is mediated by the set
    // relation.
    auto precompute_select = View(in.precompute_select);
 
    auto precompute_select_shift = View(in.precompute_select_shift);
 
    const auto& precompute_skew = View(in.precompute_skew);
 
    const std::array<View, 8> slices{
        View(in.precompute_s1hi), View(in.precompute_s1lo), View(in.precompute_s2hi), View(in.precompute_s2lo),
        View(in.precompute_s3hi), View(in.precompute_s3lo), View(in.precompute_s4hi), View(in.precompute_s4lo),
    };
 
    const auto range_constraint_slice_to_2_bits = [&scaling_factor](const View& s, auto& acc) {
        acc += ((s - 1).sqr() - 1) * ((s - 2).sqr() - 1) * scaling_factor;
    };
 
    // given two 2-bit numbers `s0, `s1`, convert to a wNAF digit (in {-15, -13, ..., 13, 15}) via the formula:
    // `2(4s0 + s1) - 15`. (Here, `4s0 + s1` represents the 4-bit number corresponding to the concatenation of `s0` and
    // `s1`.)
    const auto convert_to_wnaf = [](const View& s0, const View& s1) {
        auto t = s0 + s0;
        t += t;
        t += s1;
        auto naf = t + t - 15;
        return naf;
    };
 
    const auto scaled_transition = q_transition * scaling_factor;
    const auto scaled_transition_is_zero =
        -scaled_transition + scaling_factor; // `scaling_factor * (1 - q_transition)`, i.e., is the scaling_factor if we
                                             // are _not_ at a transition, else 0.
 
    const auto scaled_lagrange_first = scaling_factor * lagrange_first; // for edge-case handling
    range_constraint_slice_to_2_bits(slices[0], std::get<0>(accumulator));
    range_constraint_slice_to_2_bits(slices[1], std::get<1>(accumulator));
    range_constraint_slice_to_2_bits(slices[2], std::get<2>(accumulator));
    range_constraint_slice_to_2_bits(slices[3], std::get<3>(accumulator));
    range_constraint_slice_to_2_bits(slices[4], std::get<4>(accumulator));
    range_constraint_slice_to_2_bits(slices[5], std::get<5>(accumulator));
    range_constraint_slice_to_2_bits(slices[6], std::get<6>(accumulator));
    range_constraint_slice_to_2_bits(slices[7], std::get<7>(accumulator));
 
    const auto s1_shift = View(in.precompute_s1hi_shift);
    const auto s1_shift_msb_set = (s1_shift - 2) * (s1_shift - 3);
    const auto scaled_transition_plus_lagrange_first = scaled_transition + scaled_lagrange_first;
    // away from row zero, add `scaled_transition * precompute_select_shift * s1_shift_msb_set`. however,
    // `q_transition[0] == 0`, so this constraint will not turn on at the 0th row unless we add
    // `scaled_lagrange_first`.
    std::get<20>(accumulator) += scaled_transition_plus_lagrange_first * precompute_select_shift * s1_shift_msb_set;
    const auto w0 = convert_to_wnaf(slices[0], slices[1]);
    const auto w1 = convert_to_wnaf(slices[2], slices[3]);
    const auto w2 = convert_to_wnaf(slices[4], slices[5]);
    const auto w3 = convert_to_wnaf(slices[6], slices[7]);
 
    auto row_slice = w0; // row_slice will eventually contain the truncated scalar corresponding to the current row,
                         // which is 2^12 * w_0 + 2^8 * w_1 + 2^4 * w_2 + w_3. (If one just looks at the wNAF digits in
                         // this row, this is the resulting odd number. Note that it is not necessarily positive.)
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += w1;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += w2;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += row_slice;
    row_slice += w3;
    auto sum_delta = scalar_sum * FF(1ULL << 16) + row_slice;
    const auto check_sum = scalar_sum_shift - sum_delta;
    std::get<8>(accumulator) += precompute_select * check_sum * scaled_transition_is_zero;
 
    // We combine two checks into a single relation
    // q_transition * (round - 7) + (-q_transition + 1) * (round_shift - round - 1)
    // => q_transition * (round - 7 - round_shift + round + 1) + (round_shift - round - 1)
    // => q_transition * (2 * round - round_shift - 6) + (round_shift - round - 1)
    const auto round_check = round_shift - round - 1;
    // This selector is 1 at row 0 (via lagrange_first) and at transition rows where precompute_select == 1.
    // It's used to constrain shifted values (like round_shift, scalar_sum_shift) that need to be checked
    // both at the first active row AND at subsequent transitions between scalars.
    const auto precompute_select_transition_plus_lagrange_first =
        precompute_select * scaled_transition + scaled_lagrange_first;
    std::get<9>(accumulator) +=
        precompute_select * (scaled_transition * (round - round_check - 7) + scaling_factor * round_check);
    // At a transition (or at row 0 via lagrange_first), the next round must be 0.
    std::get<10>(accumulator) += precompute_select_transition_plus_lagrange_first * round_shift;
 
    std::get<11>(accumulator) += precompute_select_transition_plus_lagrange_first * scalar_sum_shift;
    // (2, 3 combined): q_transition * (pc - pc_shift - 1) + (-q_transition + 1) * (pc_shift - pc)
    // => q_transition * (-2 * (pc_shift - pc) - 1) + (pc_shift - pc)
    const auto pc_delta = pc_shift - pc;
    std::get<12>(accumulator) +=
        precompute_select * (scaled_transition * ((-pc_delta - pc_delta - 1)) + pc_delta * scaling_factor);
 
    std::get<13>(accumulator) += precompute_select * (precompute_skew * (precompute_skew - 7)) * scaling_factor;
 
    // Set slices (a.k.a. compressed digits), pc, and round all to zero when `precompute_select == 0`.
    // (this is for one of the multiset equality checks.)
    const auto precompute_select_zero = (-precompute_select + 1) * scaling_factor;
    std::get<14>(accumulator) += precompute_select_zero * (w0 + 15);
    std::get<15>(accumulator) += precompute_select_zero * (w1 + 15);
    std::get<16>(accumulator) += precompute_select_zero * (w2 + 15);
    std::get<17>(accumulator) += precompute_select_zero * (w3 + 15);
 
    std::get<18>(accumulator) += precompute_select_zero * round;
    std::get<19>(accumulator) += precompute_select_zero * pc;
 
    // Note(@zac-williamson #2226)
    // if precompute_select = 0, validate pc, round, slice values are all zero
    // If we do this we can reduce the degree of the set equivalence relations
    // (currently when checking pc/round/wnaf tuples from WNAF columns match those from MSM columns,
    //  we conditionally include tuples depending on if precompute_select = 1 (for WNAF columns) or if q_add1/2/3/4 = 1
    //  (for MSM columns).
    // If we KNOW that the wnaf tuple values are 0 when precompute_select = 0, we can remove the conditional checks in
    // the set equivalence relation
}
} // namespace bb