bulletproof.hpp

Go to the documentation of this file.

// Copyright (c) 2026 Judica, Inc.
// Distributed under the MIT software license, see the accompanying
// file COPYING or https://opensource.org/license/mit/.
 
#pragma once
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <memory>
#include <optional>
#include <span>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "purify/curve.hpp"
#include "purify/expr.hpp"
 
struct purify_secp_context;
struct purify_bulletproof_backend_resources;
 
namespace purify {
 
using BulletproofScalarBytes = std::array<unsigned char, 32>;
using BulletproofPointBytes = std::array<unsigned char, 33>;
using BulletproofGeneratorBytes = std::array<unsigned char, 33>;
 
struct BulletproofAssignmentData {
    std::vector<FieldElement> left;
    std::vector<FieldElement> right;
    std::vector<FieldElement> output;
    std::vector<FieldElement> commitments;
 
    Result<Bytes> serialize() const;
};
 
struct NativeBulletproofCircuitTerm {
    std::size_t idx = 0;
    FieldElement scalar;
};
 
struct NativeBulletproofCircuitRow {
    std::vector<NativeBulletproofCircuitTerm> entries;
 
    void add(std::size_t idx, const FieldElement& scalar);
 
    struct PackedWithSlack {
        const NativeBulletproofCircuitTerm* data = nullptr;
        std::size_t size = 0;
        std::size_t capacity = 0;
 
        [[nodiscard]] std::span<const NativeBulletproofCircuitTerm> entries_view() const noexcept {
            return std::span<const NativeBulletproofCircuitTerm>(data, size);
        }
    };
};
 
struct NativeBulletproofCircuit {
    struct PackedSlackPlan {
        std::size_t constraint_slack = 0;
        std::vector<std::size_t> wl;
        std::vector<std::size_t> wr;
        std::vector<std::size_t> wo;
        std::vector<std::size_t> wv;
    };
 
    class PackedWithSlack {
    public:
        PackedWithSlack() = default;
        PackedWithSlack(const PackedWithSlack& other);
        PackedWithSlack& operator=(const PackedWithSlack& other);
        PackedWithSlack(PackedWithSlack&& other) noexcept;
        PackedWithSlack& operator=(PackedWithSlack&& other) noexcept;
 
        [[nodiscard]] static Result<PackedWithSlack> from_circuit(
            const NativeBulletproofCircuit& circuit,
            const PackedSlackPlan& slack);
 
        [[nodiscard]] std::size_t n_gates() const noexcept {
            return n_gates_;
        }
 
        [[nodiscard]] std::size_t n_commitments() const noexcept {
            return n_commitments_;
        }
 
        [[nodiscard]] std::size_t n_bits() const noexcept {
            return n_bits_;
        }
 
        [[nodiscard]] std::size_t constraint_count() const noexcept {
            return constraint_size_;
        }
 
        [[nodiscard]] std::size_t constraint_capacity() const noexcept {
            return constraint_capacity_;
        }
 
        [[nodiscard]] bool has_valid_shape() const noexcept;
 
        void reset() noexcept;
 
        std::size_t add_constraint(const FieldElement& constant = FieldElement::zero());
 
        void add_left_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
        void add_right_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
        void add_output_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
        void add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
        [[nodiscard]] bool evaluate(const BulletproofAssignmentData& assignment) const;
 
        [[nodiscard]] Result<NativeBulletproofCircuit> unpack() const;
 
        [[nodiscard]] NativeBulletproofCircuitRow::PackedWithSlack left_row(std::size_t gate_idx) const noexcept;
        [[nodiscard]] NativeBulletproofCircuitRow::PackedWithSlack right_row(std::size_t gate_idx) const noexcept;
        [[nodiscard]] NativeBulletproofCircuitRow::PackedWithSlack output_row(std::size_t gate_idx) const noexcept;
        [[nodiscard]] NativeBulletproofCircuitRow::PackedWithSlack commitment_row(std::size_t commitment_idx) const noexcept;
 
        [[nodiscard]] std::span<const FieldElement> constants() const noexcept;
 
    private:
        struct PackedRowHeader {
            std::size_t offset = 0;
            std::size_t size = 0;
            std::size_t base_size = 0;
            std::size_t capacity = 0;
        };
 
        enum class RowFamily : unsigned char {
            Left,
            Right,
            Output,
            Commitment,
        };
 
        PackedRowHeader& row_header(RowFamily family, std::size_t idx) noexcept;
        const PackedRowHeader& row_header(RowFamily family, std::size_t idx) const noexcept;
        NativeBulletproofCircuitTerm* term_data() noexcept;
        const NativeBulletproofCircuitTerm* term_data() const noexcept;
        FieldElement* constant_data() noexcept;
        const FieldElement* constant_data() const noexcept;
        unsigned char* raw_storage_bytes() noexcept;
        const unsigned char* raw_storage_bytes() const noexcept;
        static bool compute_storage_layout(std::size_t row_count, std::size_t term_capacity,
                                           std::size_t constraint_capacity, std::size_t& term_bytes_offset,
                                           std::size_t& constant_bytes_offset, std::size_t& storage_bytes) noexcept;
        static constexpr std::size_t kPackedStorageAlignment =
            std::max(std::max(alignof(PackedRowHeader), alignof(NativeBulletproofCircuitTerm)),
                     alignof(FieldElement));
        static std::byte* allocate_storage(std::size_t bytes);
        void reset_to_empty() noexcept;
        void start_storage_lifetimes() noexcept;
        NativeBulletproofCircuitRow::PackedWithSlack row_view(const PackedRowHeader& header) const noexcept;
        void add_row_term(RowFamily family, std::size_t expected_size, std::size_t row_idx,
                          std::size_t constraint_idx, const FieldElement& scalar);
 
        struct PackedStorageDeleter {
            void operator()(std::byte* storage) const noexcept;
        };
 
        using PackedStorageOwner = std::unique_ptr<std::byte[], PackedStorageDeleter>;
 
        std::size_t n_gates_ = 0;
        std::size_t n_commitments_ = 0;
        std::size_t n_bits_ = 0;
        std::size_t constraint_size_ = 0;
        std::size_t constraint_base_size_ = 0;
        std::size_t constraint_capacity_ = 0;
        std::size_t term_capacity_ = 0;
        std::size_t term_bytes_offset_ = 0;
        std::size_t constant_bytes_offset_ = 0;
        std::size_t storage_bytes_ = 0;
        PackedStorageOwner storage_;
 
        static_assert(std::is_trivially_copyable_v<PackedRowHeader>,
                      "PackedWithSlack row headers must remain trivially copyable");
        static_assert(std::is_trivially_destructible_v<PackedRowHeader>,
                      "PackedWithSlack row headers must remain trivially destructible");
        static_assert(std::is_trivially_copyable_v<NativeBulletproofCircuitTerm>,
                      "PackedWithSlack sparse terms must remain trivially copyable");
        static_assert(std::is_trivially_destructible_v<NativeBulletproofCircuitTerm>,
                      "PackedWithSlack sparse terms must remain trivially destructible");
        static_assert(std::is_trivially_copyable_v<FieldElement>,
                      "PackedWithSlack constants must remain trivially copyable");
        static_assert(std::is_trivially_destructible_v<FieldElement>,
                      "PackedWithSlack constants must remain trivially destructible");
        static_assert(alignof(PackedRowHeader) <= kPackedStorageAlignment,
                      "PackedWithSlack slab alignment must cover row headers");
        static_assert(alignof(NativeBulletproofCircuitTerm) <= kPackedStorageAlignment,
                      "PackedWithSlack slab alignment must cover sparse terms");
        static_assert(alignof(FieldElement) <= kPackedStorageAlignment,
                      "PackedWithSlack slab alignment must cover constants");
        static_assert(std::is_same_v<decltype(&PackedWithSlack::storage_), PackedStorageOwner PackedWithSlack::*>,
                      "PackedWithSlack must keep its backing storage in one owning slab");
 
    };
 
    std::size_t n_gates = 0;
    std::size_t n_commitments = 0;
    std::size_t n_bits = 0;
    std::vector<NativeBulletproofCircuitRow> wl;
    std::vector<NativeBulletproofCircuitRow> wr;
    std::vector<NativeBulletproofCircuitRow> wo;
    std::vector<NativeBulletproofCircuitRow> wv;
    std::vector<FieldElement> c;
 
    NativeBulletproofCircuit() = default;
    NativeBulletproofCircuit(std::size_t gates, std::size_t commitments, std::size_t bits = 0);
 
    void resize(std::size_t gates, std::size_t commitments, std::size_t bits = 0);
 
    bool has_valid_shape() const;
 
    std::size_t add_constraint(const FieldElement& constant = FieldElement::zero());
 
    void add_left_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
    void add_right_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
    void add_output_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
    void add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx, const FieldElement& scalar);
 
    bool evaluate(const BulletproofAssignmentData& assignment) const;
 
    Result<PackedWithSlack> pack_with_slack() const;
    Result<PackedWithSlack> pack_with_slack(const PackedSlackPlan& slack) const;
 
private:
    static void add_row_term(std::vector<NativeBulletproofCircuitRow>& rows, std::size_t expected_size,
                             std::size_t row_idx, std::size_t constraint_idx, const FieldElement& scalar);
};
 
struct ExperimentalBulletproofProof {
    static constexpr unsigned char kSerializationVersion = 2;
 
    BulletproofPointBytes commitment{};
    Bytes proof;
 
    Result<Bytes> serialize() const;
    static Result<ExperimentalBulletproofProof> deserialize(std::span<const unsigned char> bytes);
};
 
class ExperimentalBulletproofBackendCache {
public:
    ExperimentalBulletproofBackendCache();
    ExperimentalBulletproofBackendCache(const ExperimentalBulletproofBackendCache&) = delete;
    ExperimentalBulletproofBackendCache& operator=(const ExperimentalBulletproofBackendCache&) = delete;
    ExperimentalBulletproofBackendCache(ExperimentalBulletproofBackendCache&& other) noexcept;
    ExperimentalBulletproofBackendCache& operator=(ExperimentalBulletproofBackendCache&& other) noexcept;
    ~ExperimentalBulletproofBackendCache();
 
    void clear();
    [[nodiscard]] std::size_t size() const noexcept;
    [[nodiscard]] Result<ExperimentalBulletproofBackendCache> clone_for_thread(std::size_t n_gates) const;
    [[nodiscard]] purify_bulletproof_backend_resources* get_or_create(std::size_t n_gates,
                                                                      purify_secp_context* secp_context);
 
private:
    struct Impl;
    std::unique_ptr<Impl> impl_;
};
 
class NativeBulletproofCircuitTemplate {
public:
    [[nodiscard]] static NativeBulletproofCircuitTemplate from_parts(
        NativeBulletproofCircuit::PackedWithSlack base_packed,
        Expr p1x,
        Expr p2x,
        Expr out);
 
    Result<bool> partial_evaluate(const BulletproofAssignmentData& assignment) const;
 
    Result<bool> final_evaluate(const BulletproofAssignmentData& assignment, const UInt512& pubkey) const;
 
    Result<Bytes> integrity_digest() const;
 
    Result<NativeBulletproofCircuit::PackedWithSlack> instantiate_packed(const UInt512& pubkey) const;
    Result<NativeBulletproofCircuit> instantiate(const UInt512& pubkey) const;
 
private:
    NativeBulletproofCircuit::PackedWithSlack base_packed_;
    Expr p1x_;
    Expr p2x_;
    Expr out_;
};
 
Result<ExperimentalBulletproofProof> prove_experimental_circuit(
    const NativeBulletproofCircuit& circuit,
    const BulletproofAssignmentData& assignment,
    const BulletproofScalarBytes& nonce,
    const BulletproofGeneratorBytes& value_generator,
    purify_secp_context* secp_context,
    std::span<const unsigned char> statement_binding = {},
    std::optional<BulletproofScalarBytes> blind = std::nullopt,
    ExperimentalBulletproofBackendCache* backend_cache = nullptr);
Result<ExperimentalBulletproofProof> prove_experimental_circuit(
    const NativeBulletproofCircuit::PackedWithSlack& circuit,
    const BulletproofAssignmentData& assignment,
    const BulletproofScalarBytes& nonce,
    const BulletproofGeneratorBytes& value_generator,
    purify_secp_context* secp_context,
    std::span<const unsigned char> statement_binding = {},
    std::optional<BulletproofScalarBytes> blind = std::nullopt,
    ExperimentalBulletproofBackendCache* backend_cache = nullptr);
 
Result<bool> verify_experimental_circuit(
    const NativeBulletproofCircuit& circuit,
    const ExperimentalBulletproofProof& proof,
    const BulletproofGeneratorBytes& value_generator,
    purify_secp_context* secp_context,
    std::span<const unsigned char> statement_binding = {},
    ExperimentalBulletproofBackendCache* backend_cache = nullptr);
Result<bool> verify_experimental_circuit(
    const NativeBulletproofCircuit::PackedWithSlack& circuit,
    const ExperimentalBulletproofProof& proof,
    const BulletproofGeneratorBytes& value_generator,
    purify_secp_context* secp_context,
    std::span<const unsigned char> statement_binding = {},
    ExperimentalBulletproofBackendCache* backend_cache = nullptr);
 
Result<NativeBulletproofCircuitTemplate> verifier_circuit_template(const Bytes& message);
 
class BulletproofTranscript {
public:
    void replace_expr_v_with_bp_var(Expr& expr);
 
    bool replace_and_insert(Expr& expr, Symbol symbol);
 
    void add_assignment(Symbol symbol, Expr expr);
 
    Status from_transcript(const Transcript& transcript, std::size_t n_bits);
 
    Status add_pubkey_and_out(const UInt512& pubkey, Expr p1x, Expr p2x, Expr out);
 
    std::string to_string() const;
 
    bool evaluate(const WitnessAssignments& vars, const FieldElement& commitment) const;
 
    NativeBulletproofCircuit native_circuit() const;
 
    Result<BulletproofAssignmentData> assignment_data(const WitnessAssignments& vars) const;
 
    Result<BulletproofAssignmentData> assignment_data(const WitnessAssignments& vars, const FieldElement& commitment) const;
 
    Result<Bytes> serialize_assignment(const WitnessAssignments& vars) const;
 
private:
    struct Assignment {
        Symbol symbol;
        Expr expr;
        bool is_v;
    };
 
    static bool is_transcript_var(Symbol symbol);
    static bool contains_transcript_var(const Expr& expr);
    Result<BulletproofAssignmentData> assignment_data_impl(const WitnessAssignments& vars, const FieldElement* commitment) const;
 
    std::vector<Assignment> assignments_;
    std::vector<std::pair<Expr, Expr>> constraints_;
    std::vector<std::optional<Symbol>> witness_to_a_;
    std::vector<std::pair<std::uint32_t, Symbol>> witness_to_a_order_;
    std::size_t n_witnesses_ = 0;
    std::size_t n_muls_ = 0;
    std::size_t n_commitments_ = 1;
    std::size_t n_bits_ = 0;
};
 
Expr circuit_1bit(const std::array<FieldElement, 2>& values, Transcript& transcript, const Expr& x);
 
Expr circuit_2bit(const std::array<FieldElement, 4>& values, Transcript& transcript, const Expr& x, const Expr& y);
 
Expr circuit_3bit(const std::array<FieldElement, 8>& values, Transcript& transcript,
                  const Expr& x, const Expr& y, const Expr& z);
 
using ExprPoint = std::pair<Expr, Expr>;
 
ExprPoint circuit_1bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 2>& points,
                             Transcript& transcript, const Expr& b0);
 
ExprPoint circuit_2bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 4>& points,
                             Transcript& transcript, const Expr& b0, const Expr& b1);
 
ExprPoint circuit_3bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 8>& points,
                             Transcript& transcript, const Expr& b0, const Expr& b1, const Expr& b2);
 
ExprPoint circuit_optionally_negate_ec(const ExprPoint& point, Transcript& transcript, const Expr& negate_bit);
 
ExprPoint circuit_ec_add(Transcript& transcript, const ExprPoint& p1, const ExprPoint& p2);
 
Expr circuit_ec_add_x(Transcript& transcript, const ExprPoint& p1, const ExprPoint& p2);
 
Expr circuit_ec_multiply_x(const EllipticCurve& curve, Transcript& transcript,
                           const JacobianPoint& point, const std::vector<Expr>& bits);
 
Expr circuit_combine(Transcript& transcript, const Expr& x1, const Expr& x2);
 
struct CircuitMainResult {
    Expr out;
    Expr p1x;
    Expr p2x;
    std::size_t n_bits;
};
 
Result<CircuitMainResult> circuit_main(Transcript& transcript, const JacobianPoint& m1, const JacobianPoint& m2,
                                       const std::optional<UInt256>& z1 = std::nullopt,
                                       const std::optional<UInt256>& z2 = std::nullopt);
 
}  // namespace purify