origin_tag.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Planned, auditors: [], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "barretenberg/transcript/origin_tag.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include "barretenberg/numeric/uint256/uint256.hpp"
#include <cstring>
#include <string>
 
namespace bb {
using namespace numeric;
#ifndef AZTEC_NO_ORIGIN_TAGS
 
namespace {
inline int highest_set_bit_128(uint128_t value)
{
    if (value == 0) {
        return -1;
    }
    // Check high 64 bits first
    auto high = static_cast<uint64_t>(value >> 64);
    if (high != 0) {
        return 127 - __builtin_clzll(high);
    }
    // Check low 64 bits
    auto low = static_cast<uint64_t>(value);
    return 63 - __builtin_clzll(low);
}
 
inline uint128_t extract_uint128(const uint64_t* data)
{
    uint128_t result = 0;
    std::memcpy(&result, data, sizeof(uint128_t));
    return result;
}
} // namespace
 
void check_round_provenance(const uint256_t& provenance_a, const uint256_t& provenance_b)
{
    // Lower 128 bits = submitted rounds, Upper 128 bits = challenge rounds
    const auto submitted_a = extract_uint128(&provenance_a.data[0]);
    const auto submitted_b = extract_uint128(&provenance_b.data[0]);
 
    // Nothing to check if either has no submitted data or both are from the same round(s)
    if (submitted_a == 0 || submitted_b == 0 || submitted_a == submitted_b) {
        return;
    }
 
    // Ensure that values from different rounds are not mixing without max challenge round >= max submitted round
    const auto challenges_a = extract_uint128(&provenance_a.data[2]);
    const auto challenges_b = extract_uint128(&provenance_b.data[2]);
    const int max_challenge_round = highest_set_bit_128(challenges_a | challenges_b);
    const int max_submitted_round = highest_set_bit_128(submitted_a | submitted_b);
 
    if (max_challenge_round < max_submitted_round) {
        throw_or_abort("Round provenance check failed: max challenge round (" + std::to_string(max_challenge_round) +
                       ") < max submitted round (" + std::to_string(max_submitted_round) + ")");
    }
}
 
bool OriginTag::operator==(const OriginTag& other) const
{
    return this->transcript_index == other.transcript_index && this->round_provenance == other.round_provenance &&
           this->instant_death == other.instant_death;
}
OriginTag::OriginTag(const OriginTag& tag_a, const OriginTag& tag_b)
{
    // Elements with instant death should not be touched
    if (tag_a.instant_death || tag_b.instant_death) {
        throw_or_abort("Touched an element that should not have been touched. tag_a id: " +
                       std::to_string(tag_a.tag_id) + ", tag_b id: " + std::to_string(tag_b.tag_id));
    }
    // If one of the tags is a constant, just use the other tag
    if (tag_a.transcript_index == CONSTANT) {
        *this = tag_b;
        return;
    }
    if (tag_b.transcript_index == CONSTANT) {
        *this = tag_a;
        return;
    }
 
    // A free witness element should not interact with an element that has an origin
    if (tag_a.is_free_witness()) {
        if (!tag_b.is_free_witness() && !tag_b.is_empty()) {
            throw_or_abort(
                "A free witness element (id: " + std::to_string(tag_a.tag_id) +
                ") should not interact with an element that has an origin (id: " + std::to_string(tag_b.tag_id) + ")");
        } else {
            // If both are free witnesses or one of them is empty, just use tag_a
            *this = tag_a;
            return;
        }
    }
    if (tag_b.is_free_witness()) {
        if (!tag_a.is_free_witness() && !tag_a.is_empty()) {
            throw_or_abort(
                "A free witness element (id: " + std::to_string(tag_b.tag_id) +
                ") should not interact with an element that has an origin (id: " + std::to_string(tag_a.tag_id) + ")");
        } else {
            // If both are free witnesses or one of them is empty, just use tag_b
            *this = tag_b;
            return;
        }
    }
    // Elements from different transcripts shouldn't interact
    if (tag_a.transcript_index != tag_b.transcript_index) {
        throw_or_abort("Tags from different transcripts were involved in the same computation. tag_a: { id: " +
                       std::to_string(tag_a.tag_id) + ", transcript: " + std::to_string(tag_a.transcript_index) +
                       " } tag_b: { id: " + std::to_string(tag_b.tag_id) +
                       ", transcript: " + std::to_string(tag_b.transcript_index) + " }");
    }
    // Check that submitted values from different rounds don't mix without challenges
    check_round_provenance(tag_a.round_provenance, tag_b.round_provenance);
 
    transcript_index = tag_a.transcript_index;
    round_provenance = tag_a.round_provenance | tag_b.round_provenance;
}
 
#else
bool OriginTag::operator==(const OriginTag&) const
{
    return true;
}
 
#endif
} // namespace bb