transcript.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
// #define LOG_CHALLENGES
// #define LOG_INTERACTIONS
 
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/debug_log.hpp"
#include "barretenberg/common/serialize.hpp"
#include "barretenberg/crypto/poseidon2/poseidon2.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "barretenberg/ecc/curves/bn254/g1.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "barretenberg/ecc/fields/field_conversion.hpp"
#include "barretenberg/honk/proof_system/types/proof.hpp"
#include "barretenberg/stdlib/hash/poseidon2/poseidon2.hpp"
#include "barretenberg/stdlib/primitives/field/field_conversion.hpp"
#include "transcript_manifest.hpp"
#include <atomic>
#include <concepts>
 
namespace bb {
 
// TODO(https://github.com/AztecProtocol/barretenberg/issues/1226): univariates should also be logged
template <typename T, typename... U>
concept Loggable = (IsAnyOf<T, bb::fr, grumpkin::fr, bb::g1::affine_element, grumpkin::g1::affine_element, uint32_t>);
 
// A concept for detecting whether a type is native or in-circuit
template <typename T>
concept InCircuit = !IsAnyOf<T, bb::fr, grumpkin::fr, uint256_t>;
 
template <typename T, typename = void> struct is_iterable : std::false_type {};
 
// this gets used only when we can call std::begin() and std::end() on that type
template <typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T&>())), decltype(std::end(std::declval<T&>()))>>
    : std::true_type {};
 
template <typename T> constexpr bool is_iterable_v = is_iterable<T>::value;
 
// A static counter for the number of transcripts created
// This is used to generate unique labels for the transcript origin tags
 
// ‘inline’ (since C++17) ensures a single shared definition with external linkage.
inline std::atomic<size_t> unique_transcript_index{ 0 };
template <typename Codec_, typename HashFunction> class BaseTranscript {
  public:
    using Codec = Codec_;
    using DataType = typename Codec::DataType;
    using Proof = std::vector<DataType>;
 
    // Detects whether the transcript is in-circuit or not
    static constexpr bool in_circuit = InCircuit<DataType>;
 
    // The unique index of the transcript
    size_t transcript_index = 0;
 
    // The index of the current round of the transcript (used for the origin tag, round is only incremented if we switch
    // from generating to receiving)
    size_t round_index = 0;
 
    // Indicates whether the transcript is receiving data from the prover
    bool reception_phase = true;
 
    BaseTranscript()
    {
        // If we are in circuit, we need to get a unique index for the transcript
        if constexpr (in_circuit) {
            transcript_index = unique_transcript_index.fetch_add(1);
        }
    }
 
    std::ptrdiff_t proof_start = 0;
    size_t num_frs_written = 0; // the number of bb::frs written to proof_data by the prover
    size_t num_frs_read = 0;    // the number of bb::frs read from proof_data by the verifier
    size_t round_number = 0;    // current round for manifest
 
  private:
    bool is_first_challenge = true; // indicates if this is the first challenge this transcript is generating
    DataType previous_challenge{};  // default-initialized to zeros
    std::vector<DataType>
        current_round_data; // the data for the current round that will be hashed to generate challenges
    std::vector<DataType>
        independent_hash_buffer; // data that will be independently hashed to get the hash of an object
 
    bool use_manifest = false; // indicates whether the manifest is turned on, currently only on for manifest tests.
 
    // "Manifest" object that records a summary of the transcript interactions
    TranscriptManifest manifest;
 
    [[nodiscard]] std::array<DataType, 2> get_next_duplex_challenge_buffer(size_t num_challenges)
    {
        // challenges need at least 110 bits in them to match the presumed security parameter of the BN254 curve.
        BB_ASSERT_LTE(num_challenges, 2U);
        // Prevent challenge generation if this is the first challenge we're generating,
        // AND nothing was sent by the prover.
        if (is_first_challenge) {
            ASSERT(!current_round_data.empty());
        }
 
        // concatenate the previous challenge (if this is not the first challenge) with the current round data.
        // TODO(Adrian): Do we want to use a domain separator as the initial challenge buffer?
        // We could be cheeky and use the hash of the manifest as domain separator, which would prevent us from
        // having to domain separate all the data. (See https://safe-hash.dev)
        std::vector<DataType> full_buffer;
        if (!is_first_challenge) {
            // if not the first challenge, we can use the previous_challenge
            full_buffer.emplace_back(previous_challenge);
        } else {
            // Update is_first_challenge for the future
            is_first_challenge = false;
        }
        if (!current_round_data.empty()) {
            // TODO(https://github.com/AztecProtocol/barretenberg/issues/832): investigate why
            // full_buffer.insert(full_buffer.end(), current_round_data.begin(), current_round_data.end()); fails to
            // compile with gcc
            std::copy(current_round_data.begin(), current_round_data.end(), std::back_inserter(full_buffer));
            current_round_data.clear(); // clear the round data buffer since it has been used
        }
 
        // Hash the full buffer with poseidon2, which is believed to be a collision resistant hash function and a
        // random oracle, removing the need to pre-hash to compress and then hash with a random oracle, as we
        // previously did with Pedersen and Blake3s.
        DataType new_challenge = HashFunction::hash(full_buffer);
        std::array<DataType, 2> new_challenges = Codec::split_challenge(new_challenge);
        // update previous challenge buffer for next time we call this function
        previous_challenge = new_challenge;
        return new_challenges;
    };
 
  protected:
    Proof proof_data; // Contains the raw data sent by the prover.
 
    void add_element_frs_to_hash_buffer(const std::string& label, std::span<const DataType> element_frs)
    {
        if (use_manifest) {
            // Add an entry to the current round of the manifest
            manifest.add_entry(round_number, label, element_frs.size());
        }
 
        current_round_data.insert(current_round_data.end(), element_frs.begin(), element_frs.end());
    }
 
    template <typename T> void serialize_to_buffer(const T& element, Proof& proof_data)
    {
        auto element_frs = Codec::serialize_to_fields(element);
        proof_data.insert(proof_data.end(), element_frs.begin(), element_frs.end());
    }
    template <typename T> T deserialize_from_buffer(const Proof& proof_data, size_t& offset) const
    {
        constexpr size_t element_fr_size = Codec::template calc_num_fields<T>();
        BB_ASSERT_LTE(offset + element_fr_size, proof_data.size());
 
        auto element_frs = std::span{ proof_data }.subspan(offset, element_fr_size);
        offset += element_fr_size;
 
        auto element = Codec::template deserialize_from_fields<T>(element_frs);
 
        return element;
    }
 
  public:
    std::vector<DataType> export_proof()
    {
        std::vector<DataType> result(num_frs_written);
        std::copy_n(proof_data.begin() + proof_start, num_frs_written, result.begin());
        proof_start += static_cast<std::ptrdiff_t>(num_frs_written);
        num_frs_written = 0;
        return result;
    };
 
    void load_proof(const std::vector<DataType>& proof)
    {
        std::copy(proof.begin(), proof.end(), std::back_inserter(proof_data));
    }
 
    size_t size_proof_data() { return proof_data.size(); }
 
    void enable_manifest() { use_manifest = true; }
 
    static DataType hash(const std::vector<DataType>& data) { return HashFunction::hash(data); }
 
    template <typename T> static std::vector<DataType> serialize(const T& element)
    {
        return Codec::serialize_to_fields(element);
    }
 
    template <typename T> static T deserialize(std::span<const DataType> frs)
    {
        return Codec::template deserialize_from_fields<T>(frs);
    }
 
    template <typename T> static size_t calc_num_data_types() { return Codec::template calc_num_fields<T>(); }
 
    template <typename ChallengeType, typename... Strings>
    std::array<ChallengeType, sizeof...(Strings)> get_challenges(const Strings&... labels)
    {
        constexpr size_t num_challenges = sizeof...(Strings);
 
        if (use_manifest) {
            // Add challenge labels for current round to the manifest
            manifest.add_challenge(round_number, labels...);
        }
 
        // In case the transcript is used for recursive verification, we need to sanitize current round data so we don't
        // get an origin tag violation inside the hasher. We are doing this to ensure that the free witness tagged
        // elements that are sent to the transcript and are assigned tags externally, don't trigger the origin tag
        // security mechanism while we are hashing them
        if constexpr (in_circuit) {
            for (auto& element : current_round_data) {
                element.unset_free_witness_tag();
            }
        }
        // Compute the new challenge buffer from which we derive the challenges.
 
        // Create challenges from Frs.
        std::array<ChallengeType, num_challenges> challenges{};
 
        // Generate the challenges by iteratively hashing over the previous challenge.
        for (size_t i = 0; i < num_challenges / 2; i += 1) {
            auto challenge_buffer = get_next_duplex_challenge_buffer(2);
            challenges[2 * i] = Codec::template convert_challenge<ChallengeType>(challenge_buffer[0]);
            challenges[(2 * i) + 1] = Codec::template convert_challenge<ChallengeType>(challenge_buffer[1]);
        }
        if ((num_challenges & 1) == 1) {
            auto challenge_buffer = get_next_duplex_challenge_buffer(1);
            challenges[num_challenges - 1] = Codec::template convert_challenge<ChallengeType>(challenge_buffer[0]);
        }
 
        // In case the transcript is used for recursive verification, we can track proper Fiat-Shamir usage
        if constexpr (in_circuit) {
            // We are in challenge generation mode
            if (reception_phase) {
                reception_phase = false;
            }
            // Assign origin tags to the challenges
            for (size_t i = 0; i < num_challenges; i++) {
                challenges[i].set_origin_tag(OriginTag(transcript_index, round_index, /*is_submitted=*/false));
            }
        }
        // Prepare for next round.
        ++round_number;
 
        return challenges;
    }
 
    template <typename ChallengeType, typename String, std::size_t N>
    std::array<ChallengeType, N> get_challenges(std::array<String, N> const& labels)
    {
        // Expand the array elements into the existing variadic get_challenges
        return std::apply([this](auto const&... xs) { return this->get_challenges<ChallengeType>(xs...); }, labels);
    }
 
    template <typename ChallengeType>
    std::vector<ChallengeType> compute_round_challenge_pows(const size_t num_powers,
                                                            const ChallengeType& round_challenge)
    {
        std::vector<ChallengeType> pows(num_powers);
        pows[0] = round_challenge;
        for (size_t i = 1; i < num_powers; i++) {
            pows[i] = pows[i - 1].sqr();
        }
        return pows;
    }
 
    template <typename ChallengeType, typename String>
    std::vector<ChallengeType> get_powers_of_challenge(const String& label, size_t num_challenges)
    {
        return compute_round_challenge_pows(num_challenges, get_challenge<ChallengeType>(label));
    }
 
    template <class T> void add_to_independent_hash_buffer([[maybe_unused]] const std::string& label, const T& element)
    {
        DEBUG_LOG(label, element);
        // In case the transcript is used for recursive verification, we can track proper Fiat-Shamir usage
        if constexpr (in_circuit) {
            // The verifier is receiving data from the prover. If before this we were in the challenge generation phase,
            // then we need to increment the round index
            if (!reception_phase) {
                reception_phase = true;
                round_index++;
            }
            // If the element is iterable, then we need to assign origin tags to all the elements
            if constexpr (is_iterable_v<T>) {
                for (const auto& subelement : element) {
                    subelement.set_origin_tag(OriginTag(transcript_index, round_index, /*is_submitted=*/true));
                }
            } else {
                // If the element is not iterable, then we need to assign an origin tag to the element
                element.set_origin_tag(OriginTag(transcript_index, round_index, /*is_submitted=*/true));
            }
        }
        auto element_frs = Codec::serialize_to_fields(element);
 
#ifdef LOG_INTERACTIONS
        if constexpr (Loggable<T>) {
            info("independent hash buffer consumed:     ", label, ": ", element);
        }
#endif
        independent_hash_buffer.insert(independent_hash_buffer.end(), element_frs.begin(), element_frs.end());
    }
 
    DataType hash_independent_buffer()
    {
        // In case the transcript is used for recursive verification, we need to sanitize current round data so we don't
        // get an origin tag violation inside the hasher
        if constexpr (in_circuit) {
            for (auto& element : independent_hash_buffer) {
                element.unset_free_witness_tag();
            }
        }
        DataType buffer_hash = HashFunction::hash(independent_hash_buffer);
        independent_hash_buffer.clear();
        return buffer_hash;
    }
 
    template <class T> void add_to_hash_buffer(const std::string& label, const T& element)
    {
        DEBUG_LOG(label, element);
        // In case the transcript is used for recursive verification, we can track proper Fiat-Shamir usage
        if constexpr (in_circuit) {
            // The verifier is receiving data from the prover. If before this we were in the challenge generation phase,
            // then we need to increment the round index
            if (!reception_phase) {
                reception_phase = true;
                round_index++;
            }
            // If the element is iterable, then we need to assign origin tags to all the elements
            if constexpr (is_iterable_v<T>) {
                for (const auto& subelement : element) {
                    subelement.set_origin_tag(OriginTag(transcript_index, round_index, /*is_submitted=*/true));
                }
            } else {
                // If the element is not iterable, then we need to assign an origin tag to the element
                element.set_origin_tag(OriginTag(transcript_index, round_index, /*is_submitted=*/true));
            }
        }
        auto elements = Codec::serialize_to_fields(element);
 
#ifdef LOG_INTERACTIONS
        if constexpr (Loggable<T>) {
            info("consumed:     ", label, ": ", element);
        }
#endif
        add_element_frs_to_hash_buffer(label, elements);
    }
 
    template <class T> void send_to_verifier(const std::string& label, const T& element)
    {
        DEBUG_LOG(label, element);
        auto element_frs = Codec::template serialize_to_fields<T>(element);
        proof_data.insert(proof_data.end(), element_frs.begin(), element_frs.end());
        num_frs_written += element_frs.size();
 
#ifdef LOG_INTERACTIONS
        if constexpr (Loggable<T>) {
            info("sent:     ", label, ": ", element);
        }
#endif
        add_element_frs_to_hash_buffer(label, element_frs);
    }
 
    template <class T> T receive_from_prover(const std::string& label)
    {
        const size_t element_size = Codec::template calc_num_fields<T>();
        BB_ASSERT_LTE(num_frs_read + element_size, proof_data.size());
 
        auto element_frs = std::span{ proof_data }.subspan(num_frs_read, element_size);
        // In case the transcript is used for recursive verification, we can track proper Fiat-Shamir usage
        if constexpr (in_circuit) {
            // The verifier is receiving data from the prover. If before this we were in the challenge generation phase,
            // then we need to increment the round index
            if (!reception_phase) {
                reception_phase = true;
                round_index++;
            }
            // Assign an origin tag to the elements going into the hash buffer
            const auto element_origin_tag = OriginTag(transcript_index, round_index, /*is_submitted=*/true);
            for (auto& subelement : element_frs) {
                subelement.set_origin_tag(element_origin_tag);
            }
        }
        num_frs_read += element_size;
 
        add_element_frs_to_hash_buffer(label, element_frs);
 
        auto element = Codec::template deserialize_from_fields<T>(element_frs);
        DEBUG_LOG(label, element);
 
        // Ensure that the element got assigned an origin tag
        if constexpr (in_circuit) {
            const auto element_origin_tag = OriginTag(transcript_index, round_index, /*is_submitted=*/true);
            // If the element is iterable, then we need to check origin tags to all the elements
            if constexpr (is_iterable_v<T>) {
                for (auto& subelement : element) {
                    ASSERT(subelement.get_origin_tag() == element_origin_tag);
                }
            } else {
                // If the element is not iterable, then we need to check an origin tag of the element
                ASSERT(element.get_origin_tag() == element_origin_tag);
            }
        }
#ifdef LOG_INTERACTIONS
        if constexpr (Loggable<T>) {
            info("received: ", label, ": ", element);
        }
#endif
 
        return element;
    }
 
    static std::shared_ptr<BaseTranscript> convert_prover_transcript_to_verifier_transcript(
        const std::shared_ptr<BaseTranscript>& prover_transcript)
    {
        // We expect this function to only be used when the transcript has just been exported.
        BB_ASSERT_EQ(prover_transcript->num_frs_written, static_cast<size_t>(0), "Expected to be empty");
        auto verifier_transcript = std::make_shared<BaseTranscript>(*prover_transcript);
        verifier_transcript->num_frs_read = static_cast<size_t>(verifier_transcript->proof_start);
        verifier_transcript->proof_start = 0;
        return verifier_transcript;
    }
    static std::shared_ptr<BaseTranscript> prover_init_empty()
    {
        auto transcript = std::make_shared<BaseTranscript>();
        constexpr uint32_t init{ 42 }; // arbitrary
        transcript->send_to_verifier("Init", init);
        return transcript;
    };
 
    static std::shared_ptr<BaseTranscript> verifier_init_empty(const std::shared_ptr<BaseTranscript>& transcript)
    {
        auto verifier_transcript = std::make_shared<BaseTranscript>();
        verifier_transcript->load_proof(transcript->proof_data);
        [[maybe_unused]] auto _ = verifier_transcript->template receive_from_prover<DataType>("Init");
        return verifier_transcript;
    };
 
    template <typename ChallengeType> ChallengeType get_challenge(const std::string& label)
    {
        ChallengeType result = get_challenges<ChallengeType>(label)[0];
#if defined LOG_CHALLENGES || defined LOG_INTERACTIONS
        info("challenge: ", label, ": ", result);
#endif
        DEBUG_LOG(label, result);
        return result;
    }
 
    [[nodiscard]] TranscriptManifest get_manifest() const { return manifest; };
 
    void print()
    {
        if (!use_manifest) {
            info("Warning: manifest is not enabled!");
        }
        manifest.print();
    }
 
    BaseTranscript branch_transcript()
    {
        ASSERT(current_round_data.empty(), "Branching a transcript with non empty round data");
 
        BaseTranscript branched_transcript;
 
        // Need to fetch_sub because the constructor automatically increases unique_transcript_index by 1
        unique_transcript_index.fetch_sub(1);
        branched_transcript.transcript_index = transcript_index;
        branched_transcript.round_index = round_index;
        branched_transcript.add_to_hash_buffer("init", previous_challenge);
        round_index += BRANCHING_JUMP;
 
        return branched_transcript;
    }
};
 
using NativeTranscript = BaseTranscript<FrCodec, bb::crypto::Poseidon2<bb::crypto::Poseidon2Bn254ScalarFieldParams>>;
using KeccakTranscript = BaseTranscript<U256Codec, bb::crypto::Keccak>;
 
template <typename Builder>
using StdlibTranscript = BaseTranscript<stdlib::StdlibCodec<stdlib::field_t<Builder>>, stdlib::poseidon2<Builder>>;
using UltraStdlibTranscript =
    BaseTranscript<stdlib::StdlibCodec<stdlib::field_t<UltraCircuitBuilder>>, stdlib::poseidon2<UltraCircuitBuilder>>;
using MegaStdlibTranscript =
    BaseTranscript<stdlib::StdlibCodec<stdlib::field_t<MegaCircuitBuilder>>, stdlib::poseidon2<MegaCircuitBuilder>>;
 
} // namespace bb