expr.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 <cstdint>
#include <map>
#include <optional>
#include <set>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "purify/numeric.hpp"
 
namespace purify {
 
enum class SymbolKind : std::uint8_t {
    Witness = 0,
    Left = 1,
    Right = 2,
    Output = 3,
    Commitment = 4,
};
 
struct Symbol {
    SymbolKind kind = SymbolKind::Witness;
    std::uint32_t index = 0;
 
    static Symbol witness(std::uint32_t index);
    static Symbol left(std::uint32_t index);
    static Symbol right(std::uint32_t index);
    static Symbol output(std::uint32_t index);
    static Symbol commitment(std::uint32_t index);
 
    std::string to_string() const;
    bool operator==(const Symbol&) const = default;
};
 
struct SymbolLess {
    bool operator()(const Symbol& lhs, const Symbol& rhs) const noexcept {
        using SymbolRank = std::underlying_type_t<SymbolKind>;
        const SymbolRank lhs_kind = static_cast<SymbolRank>(lhs.kind);
        const SymbolRank rhs_kind = static_cast<SymbolRank>(rhs.kind);
        return lhs_kind < rhs_kind || (lhs_kind == rhs_kind && lhs.index < rhs.index);
    }
};
 
inline bool operator<(const Symbol& lhs, const Symbol& rhs) noexcept {
    return SymbolLess{}(lhs, rhs);
}
 
using WitnessAssignments = std::vector<std::optional<FieldElement>>;
 
class Expr {
public:
    using Term = std::pair<Symbol, FieldElement>;
 
    Expr();
    explicit Expr(const FieldElement& value);
    explicit Expr(std::int64_t value);
 
    static Expr variable(Symbol symbol);
 
    const FieldElement& constant() const {
        return constant_;
    }
 
    std::vector<Term>& linear() {
        return linear_;
    }
 
    const std::vector<Term>& linear() const {
        return linear_;
    }
 
    friend Expr operator+(const Expr& lhs, const Expr& rhs);
 
    friend Expr operator+(const Expr& lhs, std::int64_t rhs);
 
    friend Expr operator+(std::int64_t lhs, const Expr& rhs);
 
    friend Expr operator-(const Expr& lhs, const Expr& rhs);
 
    friend Expr operator-(const Expr& lhs, std::int64_t rhs);
 
    friend Expr operator-(std::int64_t lhs, const Expr& rhs);
 
    friend Expr operator-(const Expr& value);
 
    friend Expr operator*(const Expr& expr, const FieldElement& scalar);
 
    friend Expr operator*(const FieldElement& scalar, const Expr& expr);
 
    friend Expr operator*(const Expr& expr, std::int64_t scalar);
 
    friend Expr operator*(std::int64_t scalar, const Expr& expr);
 
    friend bool operator==(const Expr& lhs, const Expr& rhs);
 
    friend bool operator<(const Expr& lhs, const Expr& rhs);
 
    std::string to_string() const;
 
    std::optional<FieldElement> evaluate(const WitnessAssignments& values) const;
 
    std::pair<Expr, Expr> split() const;
 
private:
    void push_term(const Term& term);
 
    FieldElement constant_;
    std::vector<Term> linear_;
};
 
struct ExprLess {
    bool operator()(const Expr& lhs, const Expr& rhs) const;
};
 
struct ExprPairLess {
    bool operator()(const std::pair<Expr, Expr>& lhs, const std::pair<Expr, Expr>& rhs) const;
};
 
class ExprBuilder {
public:
    static ExprBuilder reserved(std::size_t terms);
 
    ExprBuilder& reserve(std::size_t terms);
 
    ExprBuilder& add(const FieldElement& value);
 
    ExprBuilder& add(std::int64_t value);
 
    ExprBuilder& add_term(Symbol symbol, const FieldElement& scale);
 
    ExprBuilder& add(const Expr& expr);
 
    ExprBuilder& subtract(const Expr& expr);
 
    ExprBuilder& add_scaled(const Expr& expr, const FieldElement& scale);
 
    ExprBuilder& add_scaled(const Expr& expr, std::int64_t scale);
 
    Expr build();
 
private:
    FieldElement constant_ = FieldElement::zero();
    std::vector<Expr::Term> terms_;
};
 
std::ostream& operator<<(std::ostream& out, const Expr& expr);
 
class Transcript {
public:
    Expr secret(const std::optional<FieldElement>& value);
 
    Expr mul(const Expr& lhs, const Expr& rhs);
 
    Expr div(const Expr& lhs, const Expr& rhs);
 
    Expr boolean(const Expr& expr);
 
    void equal(const Expr& lhs, const Expr& rhs);
 
    std::optional<FieldElement> evaluate(const Expr& expr) const;
 
    const WitnessAssignments& varmap() const {
        return varmap_;
    }
 
    struct MulConstraint {
        Expr lhs;
        Expr rhs;
        Expr out;
    };
 
    const std::vector<MulConstraint>& muls() const {
        return muls_;
    }
 
    const std::vector<Expr>& eqs() const {
        return eqs_;
    }
 
private:
    WitnessAssignments varmap_;
    std::vector<MulConstraint> muls_;
    std::map<std::pair<Expr, Expr>, Expr, ExprPairLess> mul_cache_;
    std::map<std::pair<Expr, Expr>, Expr, ExprPairLess> div_cache_;
    std::set<Expr, ExprLess> bool_cache_;
    std::vector<Expr> eqs_;
};
 
Expr operator+(const Expr& lhs, const Expr& rhs);
Expr operator+(const Expr& lhs, std::int64_t rhs);
Expr operator+(std::int64_t lhs, const Expr& rhs);
Expr operator-(const Expr& lhs, const Expr& rhs);
Expr operator-(const Expr& lhs, std::int64_t rhs);
Expr operator-(std::int64_t lhs, const Expr& rhs);
Expr operator-(const Expr& value);
Expr operator*(const Expr& expr, const FieldElement& scalar);
Expr operator*(const FieldElement& scalar, const Expr& expr);
Expr operator*(const Expr& expr, std::int64_t scalar);
Expr operator*(std::int64_t scalar, const Expr& expr);
bool operator==(const Expr& lhs, const Expr& rhs);
bool operator<(const Expr& lhs, const Expr& rhs);
 
}  // namespace purify