witness_computation.cpp

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 }
// =====================
 
#include "barretenberg/ultra_honk/witness_computation.hpp"
#include "barretenberg/common/bb_bench.hpp"
#include "barretenberg/ext/starknet/flavor/ultra_starknet_flavor.hpp"
#include "barretenberg/ext/starknet/flavor/ultra_starknet_zk_flavor.hpp"
#include "barretenberg/flavor/mega_zk_flavor.hpp"
#include "barretenberg/flavor/ultra_keccak_flavor.hpp"
#include "barretenberg/flavor/ultra_keccak_zk_flavor.hpp"
#include "barretenberg/flavor/ultra_rollup_flavor.hpp"
#include "barretenberg/flavor/ultra_zk_flavor.hpp"
#include "barretenberg/honk/library/grand_product_delta.hpp"
#include "barretenberg/honk/library/grand_product_library.hpp"
#include "barretenberg/honk/prover_instance_inspector.hpp"
#include "barretenberg/relations/databus_lookup_relation.hpp"
#include "barretenberg/relations/logderiv_lookup_relation.hpp"
#include "barretenberg/relations/permutation_relation.hpp"
 
namespace bb {
 
template <IsUltraOrMegaHonk Flavor>
void WitnessComputation<Flavor>::add_ram_rom_memory_records_to_wire_4(typename Flavor::ProverPolynomials& polynomials,
                                                                      const std::vector<uint32_t>& memory_read_records,
                                                                      const std::vector<uint32_t>& memory_write_records,
                                                                      const typename Flavor::FF& eta,
                                                                      const typename Flavor::FF& eta_two,
                                                                      const typename Flavor::FF& eta_three)
{
    // The memory record values are computed at the indicated indices as
    // w4 = w3 * eta^3 + w2 * eta^2 + w1 * eta + read_write_flag;
    // (See the Memory relation for details)
    auto wires = polynomials.get_wires();
 
    // Compute read record values
    for (const auto& gate_idx : memory_read_records) {
        wires[3].at(gate_idx) = wires[2][gate_idx] * eta_three;
        wires[3].at(gate_idx) += wires[1][gate_idx] * eta_two;
        wires[3].at(gate_idx) += wires[0][gate_idx] * eta;
    }
 
    // Compute write record values
    for (const auto& gate_idx : memory_write_records) {
        wires[3].at(gate_idx) = wires[2][gate_idx] * eta_three;
        wires[3].at(gate_idx) += wires[1][gate_idx] * eta_two;
        wires[3].at(gate_idx) += wires[0][gate_idx] * eta;
        wires[3].at(gate_idx) += 1;
    }
}
 
template <IsUltraOrMegaHonk Flavor>
void WitnessComputation<Flavor>::compute_logderivative_inverses(Flavor::ProverPolynomials& polynomials,
                                                                const size_t circuit_size,
                                                                RelationParameters<FF>& relation_parameters)
{
    BB_BENCH_NAME("compute_logderivative_inverses");
 
    // Compute inverses for conventional lookups
    LogDerivLookupRelation<FF>::compute_logderivative_inverse(polynomials, relation_parameters, circuit_size);
 
    if constexpr (HasDataBus<Flavor>) {
        // Compute inverses for calldata reads
        DatabusLookupRelation<FF>::template compute_logderivative_inverse</*bus_idx=*/0>(
            polynomials, relation_parameters, circuit_size);
 
        // Compute inverses for secondary_calldata reads
        DatabusLookupRelation<FF>::template compute_logderivative_inverse</*bus_idx=*/1>(
            polynomials, relation_parameters, circuit_size);
 
        // Compute inverses for return data reads
        DatabusLookupRelation<FF>::template compute_logderivative_inverse</*bus_idx=*/2>(
            polynomials, relation_parameters, circuit_size);
    }
}
 
template <IsUltraOrMegaHonk Flavor>
void WitnessComputation<Flavor>::compute_grand_product_polynomial(Flavor::ProverPolynomials& polynomials,
                                                                  std::vector<FF>& public_inputs,
                                                                  const size_t pub_inputs_offset,
                                                                  RelationParameters<FF>& relation_parameters,
                                                                  size_t size_override)
{
    relation_parameters.public_input_delta = compute_public_input_delta<Flavor>(
        public_inputs, relation_parameters.beta, relation_parameters.gamma, pub_inputs_offset);
 
    // Compute permutation grand product polynomial
    compute_grand_product<Flavor, UltraPermutationRelation<FF>>(polynomials, relation_parameters, size_override);
}
 
template <IsUltraOrMegaHonk Flavor>
void WitnessComputation<Flavor>::complete_prover_instance_for_test(
    const std::shared_ptr<ProverInstance_<Flavor>>& prover_inst)
{
    // Generate random eta, beta and gamma
    prover_inst->relation_parameters.eta = FF::random_element();
    prover_inst->relation_parameters.eta = FF::random_element();
    prover_inst->relation_parameters.eta_two = FF::random_element();
    prover_inst->relation_parameters.eta_three = FF::random_element();
    prover_inst->relation_parameters.beta = FF::random_element();
    prover_inst->relation_parameters.gamma = FF::random_element();
 
    add_ram_rom_memory_records_to_wire_4(prover_inst->polynomials,
                                         prover_inst->memory_read_records,
                                         prover_inst->memory_write_records,
                                         prover_inst->relation_parameters.eta,
                                         prover_inst->relation_parameters.eta_two,
                                         prover_inst->relation_parameters.eta_three);
 
    compute_logderivative_inverses(
        prover_inst->polynomials, prover_inst->dyadic_size(), prover_inst->relation_parameters);
 
    compute_grand_product_polynomial(prover_inst->polynomials,
                                     prover_inst->public_inputs,
                                     prover_inst->pub_inputs_offset(),
                                     prover_inst->relation_parameters,
                                     prover_inst->get_final_active_wire_idx() + 1);
}
 
template class WitnessComputation<UltraFlavor>;
template class WitnessComputation<UltraZKFlavor>;
template class WitnessComputation<UltraKeccakFlavor>;
#ifdef STARKNET_GARAGA_FLAVORS
template class WitnessComputation<UltraStarknetFlavor>;
template class WitnessComputation<UltraStarknetZKFlavor>;
#endif
template class WitnessComputation<UltraKeccakZKFlavor>;
template class WitnessComputation<UltraRollupFlavor>;
template class WitnessComputation<MegaFlavor>;
template class WitnessComputation<MegaZKFlavor>;
 
} // namespace bb