recursive_flavor.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [Federico], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include <cstdint>
 
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/stdlib/proof/proof.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
#include "barretenberg/vm2/constraining/avm_fixed_vk.hpp"
#include "barretenberg/vm2/constraining/flavor.hpp"
#include "barretenberg/vm2/constraining/recursion/recursive_flavor_settings.hpp"
 
namespace bb::avm2 {
 
class AvmRecursiveFlavor {
  public:
    using CircuitBuilder = AvmRecursiveFlavorSettings::CircuitBuilder;
    using Curve = AvmRecursiveFlavorSettings::Curve;
    using PCS = AvmRecursiveFlavorSettings::PCS;
    using GroupElement = AvmRecursiveFlavorSettings::GroupElement;
    using Commitment = AvmRecursiveFlavorSettings::Commitment;
    using FF = AvmRecursiveFlavorSettings::FF;
    using BF = AvmRecursiveFlavorSettings::BF;
 
    using NativeFlavor = avm2::AvmFlavor;
    using NativeVerificationKey = NativeFlavor::VerificationKey;
 
    // Native one is used!
    using VerifierCommitmentKey = NativeFlavor::VerifierCommitmentKey;
 
    using Relations = NativeFlavor::Relations_<FF>;
 
    static constexpr size_t NUM_ALL_ENTITIES = NativeFlavor::NUM_ALL_ENTITIES;
    static constexpr size_t BATCHED_RELATION_PARTIAL_LENGTH = NativeFlavor::BATCHED_RELATION_PARTIAL_LENGTH;
    static constexpr size_t NUM_RELATIONS = std::tuple_size_v<Relations>;
 
    static constexpr size_t NUM_SUBRELATIONS = NativeFlavor::NUM_SUBRELATIONS;
    using SubrelationSeparators = std::array<FF, NUM_SUBRELATIONS - 1>;
 
    // This flavor would not be used with ZK Sumcheck
    static constexpr bool HasZK = false;
 
    // To achieve fixed proof size and that the recursive verifier circuit is constant, we are using padding in Sumcheck
    // and Shplemini
    static constexpr bool USE_PADDING = true;
 
    class AllValues : public NativeFlavor::AllEntities<FF> {
      public:
        using Base = NativeFlavor::AllEntities<FF>;
        using Base::Base;
    };
 
    class VerificationKey : public StdlibVerificationKey_<CircuitBuilder,
                                                          NativeFlavor::PrecomputedEntities<Commitment>,
                                                          NativeVerificationKey,
                                                          VKSerializationMode::NO_METADATA> {
      public:
        VerificationKey(CircuitBuilder* builder, const std::shared_ptr<NativeVerificationKey>& native_key)
        {
            for (auto [native_comm, comm] : zip_view(native_key->get_all(), this->get_all())) {
                comm = Commitment::from_witness(builder, native_comm);
            }
        }
 
        VerificationKey(std::span<const FF> elements)
        {
            using Codec = stdlib::StdlibCodec<FF>;
 
            size_t num_frs_read = 0;
            size_t num_frs_Comm = Codec::template calc_num_fields<Commitment>();
 
            for (Commitment& comm : this->get_all()) {
                comm =
                    Codec::template deserialize_from_fields<Commitment>(elements.subspan(num_frs_read, num_frs_Comm));
                num_frs_read += num_frs_Comm;
            }
        }
 
        FF hash_with_origin_tagging([[maybe_unused]] const OriginTag& tag) const override
        {
            throw_or_abort("Not intended to be used because vk is hardcoded in circuit.");
        }
 
        void fix_witness()
        {
            for (Commitment& commitment : this->get_all()) {
                commitment.fix_witness();
            }
        }
    };
    template <typename Builder> class TemplatedTranscript : public StdlibTranscript<Builder> {
        using Base = StdlibTranscript<Builder>;
        using FF = stdlib::field_t<Builder>;
 
      private:
        static std::shared_ptr<TemplatedTranscript<Builder>> perform_avm_transcript_operations(
            Builder& builder,
            const stdlib::Proof<Builder>& stdlib_proof,
            const std::vector<std::vector<stdlib::field_t<Builder>>>& public_inputs,
            const bool enable_manifest = false)
        {
            auto native_vk = std::make_shared<NativeVerificationKey>(constraining::AvmFixedVKCommitments::get_all());
            auto native_vk_hash = native_vk->hash();
            FF vk_hash = FF::from_witness(&builder, native_vk_hash);
            vk_hash.fix_witness();
 
            auto transcript = std::make_shared<TemplatedTranscript<Builder>>();
            if (enable_manifest) {
                transcript->enable_manifest();
            }
 
            transcript->load_proof(stdlib_proof);
 
            transcript->add_to_hash_buffer("avm_vk_hash", vk_hash);
 
            for (size_t i = 0; i < AVM_NUM_PUBLIC_INPUT_COLUMNS; i++) {
                for (size_t j = 0; j < public_inputs[i].size(); j++) {
                    transcript->add_to_hash_buffer("public_input_" + std::to_string(i) + "_" + std::to_string(j),
                                                   public_inputs[i][j]);
                }
            }
 
            size_t proof_idx = 0;
            std::span<const stdlib::field_t<Builder>> proof_span = stdlib_proof;
 
            constexpr size_t num_frs_comm =
                Base::Codec::template calc_num_fields<typename Base::Codec::bn254_commitment>();
            for (size_t idx = WIRE_START_IDX; idx < WIRE_START_IDX + NUM_WIRE_ENTITIES; idx++) {
                transcript->add_element_frs_to_hash_buffer(COLUMN_NAMES[idx],
                                                           proof_span.subspan(proof_idx, num_frs_comm));
                proof_idx += num_frs_comm;
            }
 
            [[maybe_unused]] auto [_beta, _gamma] =
                transcript->template get_challenges<FF>(std::array<std::string, 2>{ "beta", "gamma" });
 
            for (size_t idx = DERIVED_START_IDX; idx < DERIVED_START_IDX + NUM_DERIVED_ENTITIES; idx++) {
                transcript->add_element_frs_to_hash_buffer(COLUMN_NAMES[idx],
                                                           proof_span.subspan(proof_idx, num_frs_comm));
                proof_idx += num_frs_comm;
            }
 
            [[maybe_unused]] const FF _alpha = transcript->template get_challenge<FF>("Sumcheck:alpha");
 
            [[maybe_unused]] const FF _initial_gate_challenge =
                transcript->template get_challenge<FF>("Sumcheck:gate_challenge");
 
            for (size_t i = 0; i < native_vk->log_circuit_size; i++) {
                std::string round_univariate_label = "Sumcheck:univariate_" + std::to_string(i);
                transcript->add_element_frs_to_hash_buffer(
                    round_univariate_label, proof_span.subspan(proof_idx, AvmFlavor::BATCHED_RELATION_PARTIAL_LENGTH));
                proof_idx += AvmFlavor::BATCHED_RELATION_PARTIAL_LENGTH;
                [[maybe_unused]] FF _round_challenge =
                    transcript->template get_challenge<FF>("Sumcheck:u_" + std::to_string(i));
            }
 
            transcript->add_element_frs_to_hash_buffer("Sumcheck:evaluations",
                                                       proof_span.subspan(proof_idx, NUM_ALL_ENTITIES));
            proof_idx += NUM_ALL_ENTITIES;
 
            std::vector<std::string> unshifted_batching_challenge_labels;
            unshifted_batching_challenge_labels.reserve(NUM_UNSHIFTED_ENTITIES - 1);
            for (size_t idx = 0; idx < NUM_UNSHIFTED_ENTITIES - 1; idx++) {
                unshifted_batching_challenge_labels.push_back("rho_" + std::to_string(idx));
            }
            std::vector<std::string> shifted_batching_challenge_labels;
            shifted_batching_challenge_labels.reserve(NUM_WIRES_TO_BE_SHIFTED);
            for (size_t idx = 0; idx < NUM_WIRES_TO_BE_SHIFTED; idx++) {
                shifted_batching_challenge_labels.push_back("rho_" + std::to_string(NUM_UNSHIFTED_ENTITIES - 1 + idx));
            }
 
            [[maybe_unused]] auto _unshifted_challenges =
                transcript->template get_challenges<FF>(unshifted_batching_challenge_labels);
            [[maybe_unused]] auto _shifted_challenges =
                transcript->template get_challenges<FF>(shifted_batching_challenge_labels);
 
            [[maybe_unused]] const FF _gemini_batching_challenge = transcript->template get_challenge<FF>("rho");
 
            for (size_t i = 1; i < native_vk->log_circuit_size; ++i) {
                transcript->add_element_frs_to_hash_buffer("Gemini:FOLD_" + std::to_string(i),
                                                           proof_span.subspan(proof_idx, num_frs_comm));
                proof_idx += num_frs_comm;
            }
 
            [[maybe_unused]] const FF _gemini_evaluation_challenge = transcript->template get_challenge<FF>("Gemini:r");
 
            for (size_t i = 1; i <= native_vk->log_circuit_size; ++i) {
                transcript->add_to_hash_buffer("Gemini:a_" + std::to_string(i), proof_span[proof_idx++]);
            }
 
            [[maybe_unused]] const FF _shplonk_batching_challenge =
                transcript->template get_challenge<FF>("Shplonk:nu");
 
            transcript->add_element_frs_to_hash_buffer("Shplonk:Q", proof_span.subspan(proof_idx, num_frs_comm));
            proof_idx += num_frs_comm;
 
            [[maybe_unused]] const FF _shplonk_evaluation_challenge =
                transcript->template get_challenge<FF>("Shplonk:z");
 
            transcript->add_element_frs_to_hash_buffer("KZG:W", proof_span.subspan(proof_idx, num_frs_comm));
            proof_idx += num_frs_comm;
 
            [[maybe_unused]] const FF _masking_challenge =
                transcript->template get_challenge<FF>("KZG:masking_challenge");
 
            return transcript;
        };
 
        static stdlib::field_t<Builder> pad_and_hash_avm_transcript(
            const std::shared_ptr<TemplatedTranscript<Builder>>& transcript, const stdlib::Proof<Builder>& stdlib_proof)
        {
            if (stdlib_proof.size() == AVM_V2_PROOF_LENGTH_IN_FIELDS_PADDED) {
                // If the proof is padded, we need to add the padding values to the transcript because recursive
                // verification doesn't do that
                transcript->add_element_frs_to_hash_buffer(
                    "proof_padding",
                    std::span(stdlib_proof)
                        .subspan(AvmFlavor::COMPUTED_AVM_PROOF_LENGTH_IN_FIELDS,
                                 AVM_V2_PROOF_LENGTH_IN_FIELDS_PADDED -
                                     AvmFlavor::COMPUTED_AVM_PROOF_LENGTH_IN_FIELDS));
            }
            return transcript->template get_challenge<stdlib::field_t<Builder>>("final_transcript_state");
        };
 
      public:
        static stdlib::field_t<Builder> hash_avm_transcript(
            Builder& builder,
            const stdlib::Proof<Builder>& stdlib_proof,
            const std::vector<std::vector<stdlib::field_t<Builder>>>& public_inputs)
        {
            auto transcript = perform_avm_transcript_operations(builder, stdlib_proof, public_inputs);
            return pad_and_hash_avm_transcript(transcript, stdlib_proof);
        }
 
        static stdlib::field_t<Builder> hash_avm_transcript(
            const std::shared_ptr<TemplatedTranscript<Builder>>& transcript, const stdlib::Proof<Builder>& stdlib_proof)
        {
            return pad_and_hash_avm_transcript(transcript, stdlib_proof);
        }
 
        static std::pair<stdlib::field_t<Builder>, std::shared_ptr<TemplatedTranscript<Builder>>>
        hash_avm_transcript_for_testing(Builder& builder,
                                        const stdlib::Proof<Builder>& stdlib_proof,
                                        const std::vector<std::vector<stdlib::field_t<Builder>>>& public_inputs)
        {
            auto transcript = perform_avm_transcript_operations(builder, stdlib_proof, public_inputs, true);
 
            return { pad_and_hash_avm_transcript(transcript, stdlib_proof), transcript };
        }
    };
 
    using Transcript = TemplatedTranscript<CircuitBuilder>;
    using UltraTranscript = TemplatedTranscript<UltraCircuitBuilder>;
    using WitnessCommitments = NativeFlavor::WitnessEntities<Commitment>;
    using VerifierCommitments = NativeFlavor::VerifierCommitments_<Commitment, VerificationKey>;
};
 
} // namespace bb::avm2