mega_execution_trace.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 "barretenberg/common/ref_vector.hpp"
#include "barretenberg/common/zip_view.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "barretenberg/flavor/flavor_concepts.hpp"
#include "barretenberg/honk/execution_trace/execution_trace_block.hpp"
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include <cstdint>
 
namespace bb {
 
struct TraceStructure {
    uint32_t ecc_op;
    uint32_t busread;
    uint32_t lookup;
    uint32_t pub_inputs;
    uint32_t arithmetic;
    uint32_t delta_range;
    uint32_t elliptic;
    uint32_t memory;
    uint32_t nnf;
    uint32_t poseidon2_external;
    uint32_t poseidon2_internal;
    uint32_t overflow; // block gates of arbitrary type that overflow their designated block
 
    auto get()
    {
        return RefArray{ ecc_op,   busread, lookup, pub_inputs,         arithmetic,         delta_range,
                         elliptic, memory,  nnf,    poseidon2_external, poseidon2_internal, overflow };
    }
 
    auto get() const
    {
        return RefArray{ ecc_op,   busread, lookup, pub_inputs,         arithmetic,         delta_range,
                         elliptic, memory,  nnf,    poseidon2_external, poseidon2_internal, overflow };
    }
 
    size_t size() const
    {
        size_t result{ 0 };
        for (const auto& block_size : get()) {
            result += block_size;
        }
        return static_cast<size_t>(result);
    }
};
 
struct TraceSettings {
    std::optional<TraceStructure> structure;
    // The size of the overflow block. Specified separately because it is allowed to be determined at runtime in the
    // context of VK computation
    uint32_t overflow_capacity = 0;
 
    // This size is used as a hint to the BN254 Commitment Key needed in the CIVC.
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1319): This can be removed once the prover knows all
    // the circuit sizes in advance.
    size_t size() const { return (structure ? structure->size() : 0) + static_cast<size_t>(overflow_capacity); }
 
    size_t dyadic_size() const { return numeric::round_up_power_2(size()); }
};
 
class MegaTraceBlock : public ExecutionTraceBlock<fr, /*NUM_WIRES_ */ 4> {
  public:
    using SelectorType = Selector<fr>;
 
    virtual SelectorType& q_busread() { return this->zero_selectors[0]; };
    virtual SelectorType& q_lookup_type() { return this->zero_selectors[1]; };
    virtual SelectorType& q_arith() { return this->zero_selectors[2]; };
    virtual SelectorType& q_delta_range() { return this->zero_selectors[3]; };
    virtual SelectorType& q_elliptic() { return this->zero_selectors[4]; };
    virtual SelectorType& q_memory() { return this->zero_selectors[5]; };
    virtual SelectorType& q_nnf() { return this->zero_selectors[6]; };
    virtual SelectorType& q_poseidon2_external() { return this->zero_selectors[7]; };
    virtual SelectorType& q_poseidon2_internal() { return this->zero_selectors[8]; };
 
    virtual const SelectorType& q_busread() const { return this->zero_selectors[0]; };
    virtual const SelectorType& q_lookup_type() const { return this->zero_selectors[1]; };
    virtual const SelectorType& q_arith() const { return this->zero_selectors[2]; };
    virtual const SelectorType& q_delta_range() const { return this->zero_selectors[3]; };
    virtual const SelectorType& q_elliptic() const { return this->zero_selectors[4]; };
    virtual const SelectorType& q_memory() const { return this->zero_selectors[5]; };
    virtual const SelectorType& q_nnf() const { return this->zero_selectors[6]; };
    virtual const SelectorType& q_poseidon2_external() const { return this->zero_selectors[7]; };
    virtual const SelectorType& q_poseidon2_internal() const { return this->zero_selectors[8]; };
 
    RefVector<SelectorType> get_gate_selectors()
    {
        return {
            q_busread(),     q_lookup_type(),        q_arith(),
            q_delta_range(), q_elliptic(),           q_memory(),
            q_nnf(),         q_poseidon2_external(), q_poseidon2_internal(),
        };
    }
 
    RefVector<Selector<fr>> get_selectors() override
    {
        return RefVector{
            q_m(),
            q_c(),
            q_1(),
            q_2(),
            q_3(),
            q_4(),
            q_busread(),
            q_lookup_type(),
            q_arith(),
            q_delta_range(),
            q_elliptic(),
            q_memory(),
            q_nnf(),
            q_poseidon2_external(),
            q_poseidon2_internal(),
        };
    }
 
    void pad_additional() { q_busread().emplace_back(0); };
 
    void resize_additional(size_t new_size) { q_busread().resize(new_size); };
 
    virtual void set_gate_selector([[maybe_unused]] const fr& value) {}
 
  private:
    std::array<ZeroSelector<fr>, 9> zero_selectors;
};
 
class MegaTracePublicInputBlock : public MegaTraceBlock {};
 
class MegaTraceBusReadBlock : public MegaTraceBlock {
  public:
    SelectorType& q_busread() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        gate_selector.emplace_back(value);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceLookupBlock : public MegaTraceBlock {
  public:
    SelectorType& q_lookup_type() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        gate_selector.emplace_back(value);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceArithmeticBlock : public MegaTraceBlock {
  public:
    SelectorType& q_arith() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        gate_selector.emplace_back(value);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceDeltaRangeBlock : public MegaTraceBlock {
  public:
    SelectorType& q_delta_range() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        gate_selector.emplace_back(value);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceEllipticBlock : public MegaTraceBlock {
  public:
    SelectorType& q_elliptic() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        gate_selector.emplace_back(value);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceMemoryBlock : public MegaTraceBlock {
  public:
    SelectorType& q_memory() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        gate_selector.emplace_back(value);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceNonNativeFieldBlock : public MegaTraceBlock {
  public:
    SelectorType& q_nnf() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        gate_selector.emplace_back(value);
        q_poseidon2_external().emplace_back(0);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTracePoseidon2ExternalBlock : public MegaTraceBlock {
  public:
    SelectorType& q_poseidon2_external() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        gate_selector.emplace_back(value);
        q_poseidon2_internal().emplace_back(0);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTracePoseidon2InternalBlock : public MegaTraceBlock {
  public:
    SelectorType& q_poseidon2_internal() override { return gate_selector; }
 
    void set_gate_selector(const fr& value) override
    {
        q_busread().emplace_back(0);
        q_lookup_type().emplace_back(0);
        q_arith().emplace_back(0);
        q_delta_range().emplace_back(0);
        q_elliptic().emplace_back(0);
        q_memory().emplace_back(0);
        q_nnf().emplace_back(0);
        q_poseidon2_external().emplace_back(0);
        gate_selector.emplace_back(value);
    }
 
  private:
    SlabVectorSelector<fr> gate_selector;
};
 
class MegaTraceOverflowBlock : public MegaTraceBlock {
  public:
    SelectorType& q_busread() override { return gate_selectors[0]; };
    SelectorType& q_lookup_type() override { return gate_selectors[1]; };
    SelectorType& q_arith() override { return gate_selectors[2]; }
    SelectorType& q_delta_range() override { return gate_selectors[3]; }
    SelectorType& q_elliptic() override { return gate_selectors[4]; }
    SelectorType& q_memory() override { return gate_selectors[5]; }
    SelectorType& q_nnf() override { return gate_selectors[6]; }
    SelectorType& q_poseidon2_external() override { return gate_selectors[7]; }
    SelectorType& q_poseidon2_internal() override { return gate_selectors[8]; }
 
  private:
    std::array<SlabVectorSelector<fr>, 9> gate_selectors;
};
 
struct MegaTraceBlockData {
    MegaTraceBlock ecc_op;
    MegaTraceBusReadBlock busread;
    MegaTraceLookupBlock lookup;
    MegaTracePublicInputBlock pub_inputs;
    MegaTraceArithmeticBlock arithmetic;
    MegaTraceDeltaRangeBlock delta_range;
    MegaTraceEllipticBlock elliptic;
    MegaTraceMemoryBlock memory;
    MegaTraceNonNativeFieldBlock nnf;
    MegaTracePoseidon2ExternalBlock poseidon2_external;
    MegaTracePoseidon2InternalBlock poseidon2_internal;
    MegaTraceOverflowBlock overflow; // block gates of arbitrary type that overflow their designated block
 
    std::vector<std::string_view> get_labels() const
    {
        return { "ecc_op",   "busread", "lookup", "pub_inputs",         "arithmetic",         "delta_range",
                 "elliptic", "memory",  "nnf",    "poseidon2_external", "poseidon2_internal", "overflow" };
    }
 
    auto get()
    {
        return RefArray(std::array<MegaTraceBlock*, 12>{ &ecc_op,
                                                         &busread,
                                                         &lookup,
                                                         &pub_inputs,
                                                         &arithmetic,
                                                         &delta_range,
                                                         &elliptic,
                                                         &memory,
                                                         &nnf,
                                                         &poseidon2_external,
                                                         &poseidon2_internal,
                                                         &overflow });
    }
 
    auto get() const
    {
        return RefArray(std::array<const MegaTraceBlock*, 12>{ &ecc_op,
                                                               &busread,
                                                               &lookup,
                                                               &pub_inputs,
                                                               &arithmetic,
                                                               &delta_range,
                                                               &elliptic,
                                                               &memory,
                                                               &nnf,
                                                               &poseidon2_external,
                                                               &poseidon2_internal,
                                                               &overflow });
    }
 
    auto get_gate_blocks() const
    {
        return RefArray(std::array<const MegaTraceBlock*, 9>{
            &busread,
            &lookup,
            &arithmetic,
            &delta_range,
            &elliptic,
            &memory,
            &nnf,
            &poseidon2_external,
            &poseidon2_internal,
        });
    }
 
    bool operator==(const MegaTraceBlockData& other) const = default;
};
 
class MegaExecutionTraceBlocks : public MegaTraceBlockData {
  public:
    static constexpr size_t NUM_WIRES = MegaTraceBlock::NUM_WIRES;
 
    using FF = fr;
 
    bool has_overflow = false; // indicates whether the overflow block has non-zero fixed or actual size
 
    MegaExecutionTraceBlocks() = default;
 
    void set_fixed_block_sizes(const TraceSettings& settings)
    {
        if (settings.structure) {
            for (auto [block, size] : zip_view(this->get(), settings.structure.value().get())) {
                block.fixed_size = size;
            }
        }
 
        this->overflow.fixed_size = settings.overflow_capacity;
    }
 
    void compute_offsets(bool is_structured)
    {
        uint32_t offset = 1; // start at 1 because the 0th row is unused for selectors for Honk
        for (auto& block : this->get()) {
            block.trace_offset_ = offset;
            offset += block.get_fixed_size(is_structured);
        }
    }
 
    void summarize() const
    {
        info("Gate blocks summary: (actual gates / fixed capacity)");
        info("goblin ecc op :\t", this->ecc_op.size(), "/", this->ecc_op.get_fixed_size());
        info("busread       :\t", this->busread.size(), "/", this->busread.get_fixed_size());
        info("lookups       :\t", this->lookup.size(), "/", this->lookup.get_fixed_size());
        info("pub inputs    :\t",
             this->pub_inputs.size(),
             "/",
             this->pub_inputs.get_fixed_size(),
             " (populated in decider pk constructor)");
        info("arithmetic    :\t", this->arithmetic.size(), "/", this->arithmetic.get_fixed_size());
        info("delta range   :\t", this->delta_range.size(), "/", this->delta_range.get_fixed_size());
        info("elliptic      :\t", this->elliptic.size(), "/", this->elliptic.get_fixed_size());
        info("memory        :\t", this->memory.size(), "/", this->memory.get_fixed_size());
        info("nnf           :\t", this->nnf.size(), "/", this->nnf.get_fixed_size());
        info("poseidon ext  :\t", this->poseidon2_external.size(), "/", this->poseidon2_external.get_fixed_size());
        info("poseidon int  :\t", this->poseidon2_internal.size(), "/", this->poseidon2_internal.get_fixed_size());
        info("overflow      :\t", this->overflow.size(), "/", this->overflow.get_fixed_size());
        info("");
        info("Total structured size: ", get_structured_size());
    }
 
    // Get cumulative size of all blocks
    size_t get_total_content_size()
    {
        size_t total_size(0);
        for (const auto& block : this->get()) {
            total_size += block.size();
        }
        return total_size;
    }
 
    size_t get_structured_size() const
    {
        size_t total_size = 1; // start at 1 because the 0th row is unused for selectors for Honk
        for (const auto& block : this->get()) {
            total_size += block.get_fixed_size();
        }
        return total_size;
    }
 
    size_t get_structured_dyadic_size() const
    {
        size_t total_size = get_structured_size();
 
        auto log2_n = static_cast<size_t>(numeric::get_msb(total_size));
        if ((1UL << log2_n) != (total_size)) {
            ++log2_n;
        }
        return 1UL << log2_n;
    }
 
    bool operator==(const MegaExecutionTraceBlocks& other) const = default;
};
 
static constexpr TraceStructure TINY_TEST_STRUCTURE{ .ecc_op = 18,
                                                     .busread = 3,
                                                     .lookup = 2,
                                                     .pub_inputs = 52, // Accomodate 4 + HidingKernelIO = 4 + 48
                                                     .arithmetic = 1 << 14,
                                                     .delta_range = 5,
                                                     .elliptic = 2,
                                                     .memory = 10,
                                                     .nnf = 2,
                                                     .poseidon2_external = 2,
                                                     .poseidon2_internal = 2,
                                                     .overflow = 0 };
 
static constexpr TraceStructure SMALL_TEST_STRUCTURE{ .ecc_op = 1 << 14,
                                                      .busread = 1 << 14,
                                                      .lookup = 1 << 14,
                                                      .pub_inputs = 1 << 14,
                                                      .arithmetic = 1 << 15,
                                                      .delta_range = 1 << 14,
                                                      .elliptic = 1 << 14,
                                                      .memory = 1 << 14,
                                                      .nnf = 1 << 7,
                                                      .poseidon2_external = 1 << 14,
                                                      .poseidon2_internal = 1 << 15,
                                                      .overflow = 0 };
 
static constexpr TraceStructure EXAMPLE_18{ .ecc_op = 1 << 10,
                                            .busread = 1 << 6,
                                            .lookup = 36000,
                                            .pub_inputs = 1 << 6,
                                            .arithmetic = 84000,
                                            .delta_range = 45000,
                                            .elliptic = 9000,
                                            .memory = 67000,
                                            .nnf = 1000,
                                            .poseidon2_external = 2500,
                                            .poseidon2_internal = 14000,
                                            .overflow = 0 };
 
static constexpr TraceStructure EXAMPLE_20{ .ecc_op = 1 << 11,
                                            .busread = 1 << 8,
                                            .lookup = 144000,
                                            .pub_inputs = 1 << 8,
                                            .arithmetic = 396000,
                                            .delta_range = 180000,
                                            .elliptic = 18000,
                                            .memory = 268000,
                                            .nnf = 4000,
                                            .poseidon2_external = 5000,
                                            .poseidon2_internal = 28000,
                                            .overflow = 0 };
 
static constexpr TraceStructure AZTEC_TRACE_STRUCTURE{ .ecc_op = 1000,
                                                       .busread = 4000,
                                                       .lookup = 13000,
                                                       .pub_inputs = 3500,
                                                       .arithmetic = 59000,
                                                       .delta_range = 15500,
                                                       .elliptic = 6500,
                                                       .memory = 25000,
                                                       .nnf = 19000,
                                                       .poseidon2_external = 17000,
                                                       .poseidon2_internal = 96500,
                                                       .overflow = 0 };
 
} // namespace bb