prover_instance.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Completed, auditors: [Sergei], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "prover_instance.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/common/log.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include "barretenberg/flavor/mega_avm_flavor.hpp"
#include "barretenberg/honk/composer/composer_lib.hpp"
#include "barretenberg/honk/composer/permutation_lib.hpp"
#include "barretenberg/honk/proof_system/logderivative_library.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
#include "barretenberg/trace_to_polynomials/trace_to_polynomials.hpp"
 
namespace bb {
 
template <typename Flavor> ProverInstance_<Flavor>::ProverInstance_(Circuit& circuit)
{
    BB_BENCH_NAME("ProverInstance(Circuit&)");
    vinfo("Constructing ProverInstance");
 
    // Check pairing point tagging: either no pairing points were created,
    // or all pairing points have been aggregated into a single equivalence class
    BB_ASSERT(circuit.pairing_points_tagging.has_single_pairing_point_tag(),
              "Pairing points must all be aggregated together. Either no pairing points should be created, or "
              "all created pairing points must be aggregated into a single pairing point. Found "
                  << circuit.pairing_points_tagging.num_unique_pairing_points() << " different pairing points.");
    // Check pairing point tagging: check that the pairing points have been set to public
    BB_ASSERT(circuit.pairing_points_tagging.has_public_pairing_points() ||
                  !circuit.pairing_points_tagging.has_pairing_points(),
              "Pairing points must be set to public in the circuit before constructing the ProverInstance.");
 
    // ProverInstances can be constructed multiple times, hence, we check whether the circuit has been finalized
    if (!circuit.circuit_finalized) {
        circuit.finalize_circuit(/* ensure_nonzero = */ true);
    }
    metadata.dyadic_size = compute_dyadic_size(circuit);
 
    // Find index of last non-trivial wire value in the trace
    circuit.blocks.compute_offsets(); // compute offset of each block within the trace
    for (auto& block : circuit.blocks.get()) {
        if (block.size() > 0) {
            final_active_wire_idx = block.trace_offset() + block.size() - 1;
        }
    }
 
    {
        BB_BENCH_NAME("allocating polynomials");
        vinfo("allocating polynomials object in prover instance...");
 
        populate_memory_records(circuit);
        allocate_wires();
        allocate_permutation_argument_polynomials();
        allocate_selectors(circuit);
        allocate_table_lookup_polynomials(circuit);
        allocate_lagrange_polynomials();
 
        if constexpr (IsMegaFlavor<Flavor>) {
            allocate_ecc_op_polynomials(circuit);
        }
        if constexpr (HasDataBus<Flavor>) {
            allocate_databus_polynomials(circuit);
        }
 
        // Set the shifted polynomials now that all of the to_be_shifted polynomials are defined.
        polynomials.set_shifted();
    }
 
    // Construct and add to proving key the wire, selector and copy constraint polynomials
    vinfo("populating trace...");
    TraceToPolynomials<Flavor>::populate(circuit, polynomials);
 
    if constexpr (IsMegaFlavor<Flavor>) {
        BB_BENCH_NAME("constructing databus polynomials");
        construct_databus_polynomials(circuit);
    }
 
    // Set the lagrange polynomials
    polynomials.lagrange_first.at(0) = 1;
    polynomials.lagrange_last.at(final_active_wire_idx) = 1;
 
    construct_lookup_polynomials(circuit);
 
    // Public inputs
    metadata.num_public_inputs = circuit.blocks.pub_inputs.size();
    metadata.pub_inputs_offset = circuit.blocks.pub_inputs.trace_offset();
    for (size_t i = 0; i < metadata.num_public_inputs; ++i) {
        size_t idx = i + metadata.pub_inputs_offset;
        public_inputs.emplace_back(polynomials.w_r[idx]);
    }
 
    // Copy IPA proof if present
    ipa_proof = circuit.ipa_proof;
 
    if (std::getenv("BB_POLY_STATS")) {
        analyze_prover_polynomials(polynomials);
    }
}
 
template <typename Flavor> size_t ProverInstance_<Flavor>::compute_dyadic_size(Circuit& circuit)
{
    // For the lookup argument the circuit size must be at least as large as the sum of all tables used
    const size_t tables_size = circuit.get_tables_size();
 
    // minimum size of execution trace due to everything else
    size_t min_size_of_execution_trace = circuit.blocks.get_total_content_size();
 
    // The number of gates is the maximum required by the lookup argument or everything else, plus a zero row to allow
    // for shifts.
    size_t total_num_gates =
        NUM_DISABLED_ROWS_IN_SUMCHECK + NUM_ZERO_ROWS + std::max(tables_size, min_size_of_execution_trace);
 
    // Next power of 2 (dyadic circuit size)
    return circuit.get_circuit_subgroup_size(total_num_gates);
}
 
template <typename Flavor> void ProverInstance_<Flavor>::allocate_wires()
{
    BB_BENCH_NAME("allocate_wires");
 
    // If no ZK, allocate only the active range of the trace; else allocate full dyadic size to allow for blinding
    const size_t wire_size = Flavor::HasZK ? dyadic_size() : trace_active_range_size();
 
    for (auto& wire : polynomials.get_wires()) {
        wire = Polynomial::shiftable(wire_size, dyadic_size());
    }
}
 
template <typename Flavor> void ProverInstance_<Flavor>::allocate_permutation_argument_polynomials()
{
    BB_BENCH_NAME("allocate_permutation_argument_polynomials");
 
    // Sigma and ID polynomials are zero outside the active trace range
    for (auto& sigma : polynomials.get_sigmas()) {
        sigma = Polynomial::shiftable(trace_active_range_size(), dyadic_size());
    }
    for (auto& id : polynomials.get_ids()) {
        id = Polynomial::shiftable(trace_active_range_size(), dyadic_size());
    }
 
    // If no ZK, allocate only the active range of the trace; else allocate full dyadic size to allow for blinding
    const size_t z_perm_size = Flavor::HasZK ? dyadic_size() : trace_active_range_size();
    polynomials.z_perm = Polynomial::shiftable(z_perm_size, dyadic_size());
}
 
template <typename Flavor> void ProverInstance_<Flavor>::allocate_lagrange_polynomials()
{
    BB_BENCH_NAME("allocate_lagrange_polynomials");
 
    polynomials.lagrange_first = Polynomial(
        /* size=*/1, /*virtual size=*/dyadic_size(), /*start_index=*/0);
 
    polynomials.lagrange_last = Polynomial(
        /* size=*/1, /*virtual size=*/dyadic_size(), /*start_index=*/final_active_wire_idx);
}
 
template <typename Flavor> void ProverInstance_<Flavor>::allocate_selectors(const Circuit& circuit)
{
    BB_BENCH_NAME("allocate_selectors");
 
    // Define gate selectors over the block they are isolated to
    for (auto [selector, block] : zip_view(polynomials.get_gate_selectors(), circuit.blocks.get_gate_blocks())) {
        selector = Polynomial(block.size(), dyadic_size(), block.trace_offset());
    }
 
    // Set the other non-gate selector polynomials (e.g. q_l, q_r, q_m etc.) to active trace size
    for (auto& selector : polynomials.get_non_gate_selectors()) {
        selector = Polynomial(trace_active_range_size(), dyadic_size());
    }
}
 
template <typename Flavor> void ProverInstance_<Flavor>::allocate_table_lookup_polynomials(const Circuit& circuit)
{
    BB_BENCH_NAME("allocate_table_lookup_and_lookup_read_polynomials");
 
    const size_t tables_size = circuit.get_tables_size(); // cumulative size of all lookup tables
 
    // Allocate polynomials containing the actual table data; offset to align with the lookup gate block
    BB_ASSERT_GT(dyadic_size(), tables_size);
    for (auto& table_poly : polynomials.get_tables()) {
        table_poly = Polynomial(tables_size, dyadic_size());
    }
 
    // Read counts and tags: track which table entries have been read
    // For non-ZK, allocate just the table size; for ZK: allocate full dyadic_size
    const size_t counts_and_tags_size = Flavor::HasZK ? dyadic_size() : tables_size;
    polynomials.lookup_read_counts = Polynomial(counts_and_tags_size, dyadic_size());
    polynomials.lookup_read_tags = Polynomial(counts_and_tags_size, dyadic_size());
 
    // Lookup inverses: used in the log-derivative lookup argument
    // Must cover both the lookup gate block (where reads occur) and the table data itself
    const size_t lookup_block_end = circuit.blocks.lookup.trace_offset() + circuit.blocks.lookup.size();
    const size_t lookup_inverses_end = std::max(lookup_block_end, tables_size);
 
    const size_t lookup_inverses_size = (Flavor::HasZK ? dyadic_size() : lookup_inverses_end);
    polynomials.lookup_inverses = Polynomial(lookup_inverses_size, dyadic_size());
}
 
template <typename Flavor>
void ProverInstance_<Flavor>::allocate_ecc_op_polynomials(const Circuit& circuit)
    requires IsMegaFlavor<Flavor>
{
    BB_BENCH_NAME("allocate_ecc_op_polynomials");
 
    // Allocate the ecc op wires and selector
    // Note: ECC op wires are not blinded directly so we do not need to allocate full dyadic size for ZK
    const size_t ecc_op_block_size = circuit.blocks.ecc_op.size();
    for (auto& wire : polynomials.get_ecc_op_wires()) {
        wire = Polynomial(ecc_op_block_size, dyadic_size());
    }
    polynomials.lagrange_ecc_op = Polynomial(ecc_op_block_size, dyadic_size());
}
 
template <typename Flavor>
void ProverInstance_<Flavor>::allocate_databus_polynomials(const Circuit& circuit)
    requires HasDataBus<Flavor>
{
    BB_BENCH_NAME("allocate_databus_and_lookup_inverse_polynomials");
 
    const size_t calldata_size = circuit.get_calldata().size();
    const size_t sec_calldata_size = circuit.get_secondary_calldata().size();
    const size_t return_data_size = circuit.get_return_data().size();
 
    // Allocate only enough space for the databus data; for ZK, allocate full dyadic size
    const size_t calldata_poly_size = Flavor::HasZK ? dyadic_size() : calldata_size;
    const size_t sec_calldata_poly_size = Flavor::HasZK ? dyadic_size() : sec_calldata_size;
    const size_t return_data_poly_size = Flavor::HasZK ? dyadic_size() : return_data_size;
 
    polynomials.calldata = Polynomial(calldata_poly_size, dyadic_size());
    polynomials.calldata_read_counts = Polynomial(calldata_poly_size, dyadic_size());
    polynomials.calldata_read_tags = Polynomial(calldata_poly_size, dyadic_size());
 
    polynomials.secondary_calldata = Polynomial(sec_calldata_poly_size, dyadic_size());
    polynomials.secondary_calldata_read_counts = Polynomial(sec_calldata_poly_size, dyadic_size());
    polynomials.secondary_calldata_read_tags = Polynomial(sec_calldata_poly_size, dyadic_size());
 
    polynomials.return_data = Polynomial(return_data_poly_size, dyadic_size());
    polynomials.return_data_read_counts = Polynomial(return_data_poly_size, dyadic_size());
    polynomials.return_data_read_tags = Polynomial(return_data_poly_size, dyadic_size());
 
    // Databus lookup inverses: used in the log-derivative lookup argument
    // Must cover both the databus gate block (where reads occur) and the databus data itself
    const size_t q_busread_end = circuit.blocks.busread.trace_offset() + circuit.blocks.busread.size();
    size_t calldata_inverses_size = Flavor::HasZK ? dyadic_size() : std::max(calldata_size, q_busread_end);
    size_t sec_calldata_inverses_size = Flavor::HasZK ? dyadic_size() : std::max(sec_calldata_size, q_busread_end);
    size_t return_data_inverses_size = Flavor::HasZK ? dyadic_size() : std::max(return_data_size, q_busread_end);
 
    polynomials.calldata_inverses = Polynomial(calldata_inverses_size, dyadic_size());
    polynomials.secondary_calldata_inverses = Polynomial(sec_calldata_inverses_size, dyadic_size());
    polynomials.return_data_inverses = Polynomial(return_data_inverses_size, dyadic_size());
 
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1555): Allocate minimum size >1 to avoid point at
    // infinity commitment.
    const size_t max_databus_column_size = std::max({ calldata_size, sec_calldata_size, return_data_size, 2UL });
    polynomials.databus_id = Polynomial(max_databus_column_size, dyadic_size());
}
 
template <typename Flavor> void ProverInstance_<Flavor>::construct_lookup_polynomials(Circuit& circuit)
{
    {
        BB_BENCH_NAME("constructing lookup table polynomials");
        construct_lookup_table_polynomials<Flavor>(polynomials.get_tables(), circuit);
    }
    {
        BB_BENCH_NAME("constructing lookup read counts");
        construct_lookup_read_counts<Flavor>(polynomials.lookup_read_counts, polynomials.lookup_read_tags, circuit);
    }
}
 
template <typename Flavor>
void ProverInstance_<Flavor>::construct_databus_polynomials(Circuit& circuit)
    requires HasDataBus<Flavor>
{
    auto& calldata_poly = polynomials.calldata;
    auto& calldata_read_counts = polynomials.calldata_read_counts;
    auto& calldata_read_tags = polynomials.calldata_read_tags;
    auto& secondary_calldata_poly = polynomials.secondary_calldata;
    auto& secondary_calldata_read_counts = polynomials.secondary_calldata_read_counts;
    auto& secondary_calldata_read_tags = polynomials.secondary_calldata_read_tags;
    auto& return_data_poly = polynomials.return_data;
    auto& return_data_read_counts = polynomials.return_data_read_counts;
    auto& return_data_read_tags = polynomials.return_data_read_tags;
 
    const auto& calldata = circuit.get_calldata();
    const auto& secondary_calldata = circuit.get_secondary_calldata();
    const auto& return_data = circuit.get_return_data();
 
    // Note: Databus columns start from index 0. If this ever changes, make sure to also update the active range
    // construction in ExecutionTraceUsageTracker::update(). We do not utilize a zero row for databus columns.
    for (size_t idx = 0; idx < calldata.size(); ++idx) {
        calldata_poly.at(idx) = circuit.get_variable(calldata[idx]);        // calldata values
        calldata_read_counts.at(idx) = calldata.get_read_count(idx);        // read counts
        calldata_read_tags.at(idx) = calldata_read_counts[idx] > 0 ? 1 : 0; // has row been read or not
    }
    for (size_t idx = 0; idx < secondary_calldata.size(); ++idx) {
        secondary_calldata_poly.at(idx) = circuit.get_variable(secondary_calldata[idx]); // secondary_calldata values
        secondary_calldata_read_counts.at(idx) = secondary_calldata.get_read_count(idx); // read counts
        secondary_calldata_read_tags.at(idx) =
            secondary_calldata_read_counts[idx] > 0 ? 1 : 0; // has row been read or not
    }
    for (size_t idx = 0; idx < return_data.size(); ++idx) {
        return_data_poly.at(idx) = circuit.get_variable(return_data[idx]);        // return data values
        return_data_read_counts.at(idx) = return_data.get_read_count(idx);        // read counts
        return_data_read_tags.at(idx) = return_data_read_counts[idx] > 0 ? 1 : 0; // has row been read or not
    }
 
    auto& databus_id = polynomials.databus_id;
    // Compute a simple identity polynomial for use in the databus lookup argument
    for (size_t i = 0; i < databus_id.size(); ++i) {
        databus_id.at(i) = i;
    }
}
 
template <typename Flavor> void ProverInstance_<Flavor>::populate_memory_records(const Circuit& circuit)
{
    // Store the read/write records as indices into the full trace by accounting for the offset of the memory block.
    uint32_t ram_rom_offset = circuit.blocks.memory.trace_offset();
    memory_read_records.reserve(circuit.memory_read_records.size());
    for (auto& index : circuit.memory_read_records) {
        memory_read_records.emplace_back(index + ram_rom_offset);
    }
    memory_write_records.reserve(circuit.memory_write_records.size());
    for (auto& index : circuit.memory_write_records) {
        memory_write_records.emplace_back(index + ram_rom_offset);
    }
}
 
template class ProverInstance_<UltraFlavor>;
template class ProverInstance_<UltraZKFlavor>;
template class ProverInstance_<UltraKeccakFlavor>;
#ifdef STARKNET_GARAGA_FLAVORS
template class ProverInstance_<UltraStarknetFlavor>;
template class ProverInstance_<UltraStarknetZKFlavor>;
#endif
template class ProverInstance_<UltraKeccakZKFlavor>;
template class ProverInstance_<MegaFlavor>;
template class ProverInstance_<MegaZKFlavor>;
template class ProverInstance_<MegaAvmFlavor>;
 
} // namespace bb