transcript_builder.hpp

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 }
// =====================
 
#pragma once
 
#include "./eccvm_builder_types.hpp"
#include "barretenberg/ecc/groups/precomputed_generators_bn254_impl.hpp"
#include "barretenberg/op_queue/ecc_ops_table.hpp"
 
namespace bb {
 
class ECCVMTranscriptBuilder {
  public:
    using CycleGroup = bb::g1;
    using FF = grumpkin::fr;
    using Element = typename CycleGroup::element;
    using AffineElement = typename CycleGroup::affine_element;
    using Accumulator = typename std::vector<Element>;
 
    struct TranscriptRow {
        // These fields are populated in the first loop
 
        bool transcript_msm_infinity = false; // are we at the end of an MSM *and* is the output the point at infinity?
        bool accumulator_not_empty = false;   // not(is the accumulator either empty or point-at-infinity?)
        bool q_add = false;
        bool q_mul = false;
        bool q_eq = false;
        bool q_reset_accumulator = false;
        bool msm_transition = false;
        uint32_t pc = 0;
        uint32_t msm_count = 0; // number of multiplications in the MSM *up until and not including* this step.
        bool msm_count_zero_at_transition =
            false;     // is the number of scalar muls we have completed at the end of our "MSM block" zero?
        FF base_x = 0; // [P] = (base_x, base_y)
        FF base_y = 0; // [P] = (base_x, base_y)
        bool base_infinity = false; // is [P] == neutral element?
        uint256_t z1 = 0; // `scalar` = z1 - \lambda * z2 = z1 + \zeta * z2, where $\zeta$ is a primitive sixth root of
                          // unity and \lambda is -\zeta.
        uint256_t z2 = 0; // `scalar` = z1 - \lambda * z2 = z1 + \zeta * z2, where $\zeta$ is a primitive sixth root of
                          // unity and \lambda is -\zeta.
        bool z1_zero = false; // `z1 == 0`
        bool z2_zero = false; // `z2 == 0`
        uint32_t opcode = 0;  // opcode value, in {0, .., 15}, given by 8 * q_add + 4 * q_mul + 2 * q_eq + q_reset.
 
        // These fields are populated after converting projective to affine coordinates
 
        // [A] is the current accumulated point, in affine coordinates, for all EC operations.
        // this is affected by an `add` op-code, or the end of an MSM, or a reset.
        FF accumulator_x = 0; // [A] = (`accumulator_x`, `accumulator_y`)
        FF accumulator_y = 0; // [A] = (`accumulator_x`, `accumulator_y`)
 
        // the following two are accumulators for the MSM.
        // the difference between (`msm_output_x`, `msm_output_y`) and (`transcript_msm_intermediate_x`,
        // `transcript_msm_intermediate_y`) is the OFFSET.
        FF msm_output_x = 0; // if we are at the end of an MSM, output of MSM + OFFSET = (`msm_output_x`,
                             // `msm_output_y`), else, 0.
        FF msm_output_y = 0; // if we are at the end of an MSM, output of MSM + OFFSET = (`msm_output_x`,
                             // `msm_output_y`), else 0.
        FF transcript_msm_intermediate_x =
            0; // if we are at the end of an MSM, output of MSM  =
               // (`transcript_msm_intermediate_x`, `transcript_msm_intermediate_y`), else, 0.
        FF transcript_msm_intermediate_y =
            0; // if we are at the end of an MSM, output of MSM  =
               // (`transcript_msm_intermediate_x`, `transcript_msm_intermediate_y`), else, 0.
 
        // Computed during the lambda numerator and denominator computation
        bool transcript_add_x_equal = false;
        bool transcript_add_y_equal = false;
        // Computed after the batch inversion
        FF base_x_inverse = 0;
        FF base_y_inverse = 0;
        FF transcript_add_lambda = 0;
        FF transcript_msm_x_inverse = 0;
        FF msm_count_at_transition_inverse = 0;
    };
 
    static AffineElement offset_generator()
    {
        static constexpr auto offset_generator_base =
            get_precomputed_generators<CycleGroup, "ECCVM_OFFSET_GENERATOR", 1>()[0];
        static const AffineElement result =
            AffineElement(Element(offset_generator_base) * grumpkin::fq(uint256_t(1) << 124));
        return result;
    }
    static AffineElement remove_offset_generator(const AffineElement& other)
    {
        return AffineElement(Element(other) - offset_generator());
    }
 
    // maintains the state of the VM at any given "time" (i.e., at any given value of pc).
    struct VMState {
        uint32_t pc = 0; // decreasing program counter that tracks the total number of multiplications that our virtual
                         // machine has left to compute.
        uint32_t count = 0; // Number of muls in the current MSM _excluding the current row_.
        Element accumulator = CycleGroup::affine_point_at_infinity; // accumulator for all group operations.
        Element msm_accumulator =
            offset_generator(); // accumulator for the current MSM with an offset. (we start with offset_generator,
                                // i.e. random element of the group, to avoid bifurcated logic at each operation step.)
        bool is_accumulator_empty = true;
    };
 
    static std::vector<TranscriptRow> compute_rows(const std::vector<ECCVMOperation>& vm_operations,
                                                   const uint32_t total_number_of_muls)
    {
        const size_t num_vm_entries = vm_operations.size();
        // The transcript contains an extra zero row at the beginning and the accumulated state at the end
        const size_t transcript_size = num_vm_entries + 2;
        // `transcript_state[i+1]` corresponds to `vm_operation[i]`.
        std::vector<TranscriptRow> transcript_state(transcript_size);
 
        // These vectors track quantities that we need to invert.
        // We fill these vectors and then perform batch inversions to amortize the cost of FF inverts
        std::vector<FF> inverse_trace_x(num_vm_entries);
        std::vector<FF> inverse_trace_y(num_vm_entries);
        std::vector<FF> transcript_msm_x_inverse_trace(num_vm_entries);
        std::vector<FF> add_lambda_denominator(num_vm_entries);
        std::vector<FF> add_lambda_numerator(num_vm_entries);
        std::vector<FF> msm_count_at_transition_inverse_trace(num_vm_entries);
 
        Accumulator msm_accumulator_trace(num_vm_entries); // ith entry is either neutral element or the value of the
                                                           // just-completed MSM (shifted by the OFFSET).
        Accumulator accumulator_trace(num_vm_entries);     // ith entry is the total accumulated value up-to-now
        Accumulator intermediate_accumulator_trace(
            num_vm_entries); // ith entry is either the neutral element, or the actual value of the just-completed MSM
                             // (i.e., there is no OFFSET).
 
        VMState state{
            .pc = total_number_of_muls,
            .count = 0,
            .accumulator = CycleGroup::affine_point_at_infinity,
            .msm_accumulator = offset_generator(),
            .is_accumulator_empty = true,
        };
 
        VMState updated_state;
 
        // add an empty row: first row is all zeroes because of our shiftable polynomials.
        transcript_state[0] = (TranscriptRow{});
 
        // during the first iteration over the ECCOpQueue, the operations are being performed using Jacobian (a.k.a.
        // projective) coordinates and the base point coordinates are recorded in the transcript. at the same time, the
        // transcript logic is being populated
        for (size_t i = 0; i < num_vm_entries; i++) {
            TranscriptRow& row = transcript_state[i + 1];
            const ECCVMOperation& entry = vm_operations[i];
            updated_state = state;
 
            const bool is_mul = entry.op_code.mul;
            const bool is_add = entry.op_code.add;
            const bool z1_zero = is_mul ? entry.z1 == 0 : true;
            const bool z2_zero = is_mul ? entry.z2 == 0 : true;
 
            const bool base_point_infinity = entry.base_point.is_point_at_infinity();
            uint32_t num_muls = 0; // number of 128-bit multiplications the vm processes in this op_code.
                                   // `num_muls` ∈ {0, 1, 2}.
            if (is_mul) {
                num_muls = static_cast<uint32_t>(!z1_zero) + static_cast<uint32_t>(!z2_zero);
                if (base_point_infinity) {
                    num_muls = 0;
                }
            }
            updated_state.pc = state.pc - num_muls;
            // if we are at a `reset` or null op, reset the state.
            // logically, we should add `updated_state.count = 0`, but this is taken care of later by conditional
            // logic and hence is unnecessary here.
            if (entry.op_code.reset || entry.op_code.value() == 0) {
                updated_state.is_accumulator_empty = true;
                updated_state.accumulator = CycleGroup::point_at_infinity;
                updated_state.msm_accumulator = offset_generator();
            }
 
            const bool last_row = (i == (num_vm_entries - 1));
            // next_not_msm == True if either we are at the last row or the next op_code is *not* a mul.
            const bool next_not_msm = last_row || !vm_operations[i + 1].op_code.mul;
 
            // `msm_transition == True` iff we are at the end of an MSM.
            // this holds iff: current op_code is `mul`, `next_not_msm == True`, and the total number of muls so far in
            // this MSM (including this op_code) is positive. This later total number
            // is `state.count + num_muls`.
            const bool msm_transition = is_mul && next_not_msm && (state.count + num_muls > 0);
 
            // determine ongoing/continuing msm and update the respective counter
            const bool current_ongoing_msm = is_mul && !next_not_msm;
            // we reset the count in updated state if we are not accumulating and not doing an msm
            updated_state.count = current_ongoing_msm ? state.count + num_muls : 0;
 
            // process state based on whether we are at a `mul`, then whether or not this is the last mul in an MSM,
            // then finally if this is an add. note that this mutates `updated_state`. (note that the middle option
            // depends on the first.)
            if (is_mul) {
                process_mul(entry, updated_state, state);
            }
 
            if (msm_transition) {
                process_msm_transition(row, updated_state, state);
            } else {
                msm_accumulator_trace[i] = Element::infinity();
                intermediate_accumulator_trace[i] = Element::infinity();
            }
 
            if (is_add) {
                process_add(entry, updated_state, state);
            }
 
            // populate the first group of TranscriptRow entries
            populate_transcript_row(row, entry, state, num_muls, msm_transition, next_not_msm);
 
            msm_count_at_transition_inverse_trace[i] = ((state.count + num_muls) == 0) ? 0 : FF(state.count + num_muls);
 
            // update the accumulators. note that `msm_accumulator_trace` and `intermediate_accumulate_trace` are the
            // point-at-infinity *unless* we are at the end of an MSM.
            accumulator_trace[i] = state.accumulator;
            msm_accumulator_trace[i] = msm_transition ? updated_state.msm_accumulator : Element::infinity();
            intermediate_accumulator_trace[i] =
                msm_transition ? (updated_state.msm_accumulator - offset_generator()) : Element::infinity();
 
            state = updated_state;
            // if we are the last `mul`in an MSM, set the next state's `msm_accumulator` to the offset.
            if (is_mul && next_not_msm) {
                state.msm_accumulator = offset_generator();
            }
        }
        // compute affine coordinates of the accumulated points
        normalize_accumulators(accumulator_trace, msm_accumulator_trace, intermediate_accumulator_trace);
 
        // add required affine coordinates to the transcript
        add_affine_coordinates_to_transcript(
            transcript_state, accumulator_trace, msm_accumulator_trace, intermediate_accumulator_trace);
 
        // process the slopes when adding points or results of MSMs. to increase efficiency, we use batch inversion
        // after the loop
        for (size_t i = 0; i < accumulator_trace.size(); ++i) {
            TranscriptRow& row = transcript_state[i + 1];
            const bool msm_transition = row.msm_transition;
 
            const ECCVMOperation& entry = vm_operations[i];
            const bool is_add = entry.op_code.add;
 
            if (msm_transition || is_add) {
                // compute the differences between point coordinates
                compute_inverse_trace_coordinates(msm_transition,
                                                  row,
                                                  intermediate_accumulator_trace[i],
                                                  transcript_msm_x_inverse_trace[i],
                                                  msm_accumulator_trace[i],
                                                  accumulator_trace[i],
                                                  inverse_trace_x[i],
                                                  inverse_trace_y[i]);
 
                // compute the numerators and denominators of slopes between the points
                compute_lambda_numerator_and_denominator(row,
                                                         entry,
                                                         intermediate_accumulator_trace[i],
                                                         accumulator_trace[i],
                                                         add_lambda_numerator[i],
                                                         add_lambda_denominator[i]);
            } else {
                row.transcript_add_x_equal = 0;
                row.transcript_add_y_equal = 0;
                add_lambda_numerator[i] = 0;
                add_lambda_denominator[i] = 0;
                inverse_trace_x[i] = 0;
                inverse_trace_y[i] = 0;
            }
        }
 
        // Perform all required inversions at once
        FF::batch_invert(&inverse_trace_x[0], num_vm_entries);
        FF::batch_invert(&inverse_trace_y[0], num_vm_entries);
        FF::batch_invert(&transcript_msm_x_inverse_trace[0], num_vm_entries);
        FF::batch_invert(&add_lambda_denominator[0], num_vm_entries);
        FF::batch_invert(&msm_count_at_transition_inverse_trace[0], num_vm_entries);
 
        // Populate the fields of the transcript row containing inverted scalars
        for (size_t i = 0; i < num_vm_entries; ++i) {
            TranscriptRow& row = transcript_state[i + 1];
            row.base_x_inverse = inverse_trace_x[i];
            row.base_y_inverse = inverse_trace_y[i];
            row.transcript_msm_x_inverse = transcript_msm_x_inverse_trace[i];
            row.transcript_add_lambda = add_lambda_numerator[i] * add_lambda_denominator[i];
            row.msm_count_at_transition_inverse = msm_count_at_transition_inverse_trace[i];
        }
 
        // process the final row containing the result of the sequence of group ops in ECCOpQueue
        finalize_transcript(transcript_state, updated_state);
 
        return transcript_state;
    }
 
  private:
    static void populate_transcript_row(TranscriptRow& row,
                                        const ECCVMOperation& entry,
                                        const VMState& state,
                                        const uint32_t num_muls,
                                        const bool msm_transition,
                                        const bool next_not_msm)
    {
        const bool base_point_infinity = entry.base_point.is_point_at_infinity();
 
        row.accumulator_not_empty = !state.is_accumulator_empty;
        row.q_add = entry.op_code.add;
        row.q_mul = entry.op_code.mul;
        row.q_eq = entry.op_code.eq;
        row.q_reset_accumulator = entry.op_code.reset;
        row.msm_transition = msm_transition;
        row.pc = state.pc;
        row.msm_count = state.count;
        row.msm_count_zero_at_transition = ((state.count + num_muls) == 0) && entry.op_code.mul && next_not_msm;
        row.base_x = ((entry.op_code.add || entry.op_code.mul || entry.op_code.eq) && !base_point_infinity)
                         ? entry.base_point.x
                         : 0;
        row.base_y = ((entry.op_code.add || entry.op_code.mul || entry.op_code.eq) && !base_point_infinity)
                         ? entry.base_point.y
                         : 0;
        row.base_infinity =
            (entry.op_code.add || entry.op_code.mul || entry.op_code.eq) ? (base_point_infinity ? 1 : 0) : 0;
        row.z1 = entry.op_code.mul ? entry.z1 : 0;
        row.z2 = entry.op_code.mul ? entry.z2 : 0;
        row.z1_zero = entry.z1 == 0;
        row.z2_zero = entry.z2 == 0;
        row.opcode = entry.op_code.value();
    }
 
    static void process_mul(const ECCVMOperation& entry, VMState& updated_state, const VMState& state)
    {
        const auto P = typename CycleGroup::element(entry.base_point);
        const auto R = typename CycleGroup::element(state.msm_accumulator);
        updated_state.msm_accumulator = R + P * entry.mul_scalar_full;
    }
 
    static void process_add(const ECCVMOperation& entry, VMState& updated_state, const VMState& state)
    {
 
        if (state.is_accumulator_empty) {
            updated_state.accumulator = entry.base_point;
        } else {
            updated_state.accumulator = Element(state.accumulator) + entry.base_point;
        }
        updated_state.is_accumulator_empty = updated_state.accumulator.is_point_at_infinity();
    }
 
    static void process_msm_transition(TranscriptRow& row, VMState& updated_state, const VMState& state)
    {
        if (state.is_accumulator_empty) {
            updated_state.accumulator = updated_state.msm_accumulator - offset_generator();
        } else {
            const Element R = Element(state.accumulator);
            updated_state.accumulator = R + updated_state.msm_accumulator - offset_generator();
        }
        updated_state.is_accumulator_empty = updated_state.accumulator.is_point_at_infinity();
 
        const Element msm_output = updated_state.msm_accumulator - offset_generator();
        row.transcript_msm_infinity = msm_output.is_point_at_infinity();
    }
    static void normalize_accumulators(Accumulator& accumulator_trace,
                                       Accumulator& msm_accumulator_trace,
                                       std::vector<Element>& intermediate_accumulator_trace)
    {
        Element::batch_normalize(&accumulator_trace[0], accumulator_trace.size());
        Element::batch_normalize(&msm_accumulator_trace[0], msm_accumulator_trace.size());
        Element::batch_normalize(&intermediate_accumulator_trace[0], intermediate_accumulator_trace.size());
    }
    static void add_affine_coordinates_to_transcript(std::vector<TranscriptRow>& transcript_state,
                                                     const Accumulator& accumulator_trace,
                                                     const Accumulator& msm_accumulator_trace,
                                                     const Accumulator& intermediate_accumulator_trace)
    {
        for (size_t i = 0; i < accumulator_trace.size(); ++i) {
            TranscriptRow& row = transcript_state[i + 1];
            if (!accumulator_trace[i].is_point_at_infinity()) {
                row.accumulator_x = accumulator_trace[i].x;
                row.accumulator_y = accumulator_trace[i].y;
            }
            if (!msm_accumulator_trace[i].is_point_at_infinity()) {
                row.msm_output_x = msm_accumulator_trace[i].x;
                row.msm_output_y = msm_accumulator_trace[i].y;
            }
            if (!intermediate_accumulator_trace[i].is_point_at_infinity()) {
                row.transcript_msm_intermediate_x = intermediate_accumulator_trace[i].x;
                row.transcript_msm_intermediate_y = intermediate_accumulator_trace[i].y;
            }
        }
    }
    static void compute_inverse_trace_coordinates(const bool msm_transition,
                                                  const TranscriptRow& row,
                                                  const Element& msm_output,
                                                  FF& transcript_msm_x_inverse_trace,
                                                  Element& msm_accumulator_trace,
                                                  Element& accumulator_trace,
                                                  FF& inverse_trace_x,
                                                  FF& inverse_trace_y)
    {
 
        const bool msm_output_infinity = msm_output.is_point_at_infinity();
        const bool row_msm_infinity = row.transcript_msm_infinity;
 
        transcript_msm_x_inverse_trace = row_msm_infinity ? 0 : (msm_accumulator_trace.x - offset_generator().x);
 
        FF lhsx;
        FF lhsy;
        if (msm_transition) {
            lhsx = msm_output_infinity ? 0 : msm_output.x;
            lhsy = msm_output_infinity ? 0 : msm_output.y;
        } else {
            lhsx = row.base_x;
            lhsy = row.base_y;
        }
        const FF rhsx = accumulator_trace.is_point_at_infinity() ? 0 : accumulator_trace.x;
        const FF rhsy = accumulator_trace.is_point_at_infinity() ? 0 : accumulator_trace.y;
        inverse_trace_x = lhsx - rhsx;
        inverse_trace_y = lhsy - rhsy;
    }
 
    static void compute_lambda_numerator_and_denominator(TranscriptRow& row,
                                                         const ECCVMOperation& entry,
                                                         const Element& intermediate_accumulator,
                                                         const Element& accumulator,
                                                         FF& add_lambda_numerator,
                                                         FF& add_lambda_denominator)
    {
        const Element vm_point = entry.op_code.add ? Element(entry.base_point) : intermediate_accumulator;
 
        const bool vm_infinity = vm_point.is_point_at_infinity();
        const bool accumulator_infinity = accumulator.is_point_at_infinity();
 
        // extract coordinates of the current point in ECCOpQueue
        const FF vm_x = vm_infinity ? 0 : vm_point.x;
        const FF vm_y = vm_infinity ? 0 : vm_point.y;
 
        // extract coordinates of the current accumulator
        const FF accumulator_x = accumulator_infinity ? 0 : accumulator.x;
        const FF accumulator_y = accumulator_infinity ? 0 : accumulator.y;
 
        row.transcript_add_x_equal = (vm_x == accumulator_x) || (vm_infinity && accumulator_infinity);
        row.transcript_add_y_equal = (vm_y == accumulator_y) || (vm_infinity && accumulator_infinity);
 
        // compute the numerator and denominator of the slope
        if ((accumulator_x == vm_x) && (accumulator_y == vm_y) && !vm_infinity && !accumulator_infinity) {
            // Double case (x1 == x2, y1 == y2)
            add_lambda_denominator = vm_y + vm_y;
            add_lambda_numerator = vm_x * vm_x * 3;
        } else if ((accumulator_x != vm_x) && !vm_infinity && !accumulator_infinity) {
            // General case (x1 != x2)
            add_lambda_denominator = accumulator_x - vm_x;
            add_lambda_numerator = accumulator_y - vm_y;
        }
    }
    static void finalize_transcript(std::vector<TranscriptRow>& transcript_state, const VMState& updated_state)
    {
        TranscriptRow& final_row = transcript_state.back();
        final_row.pc = updated_state.pc;
        final_row.accumulator_x =
            updated_state.accumulator.is_point_at_infinity() ? 0 : AffineElement(updated_state.accumulator).x;
        final_row.accumulator_y =
            updated_state.accumulator.is_point_at_infinity() ? 0 : AffineElement(updated_state.accumulator).y;
        final_row.accumulator_not_empty = !updated_state.is_accumulator_empty;
    }
};
} // namespace bb