purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
expr.hpp
Go to the documentation of this file.
1// Copyright (c) 2026 Judica, Inc.
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or https://opensource.org/license/mit/.
4
9
10#pragma once
11
12#include <cstdint>
13#include <map>
14#include <optional>
15#include <set>
16#include <string>
17#include <type_traits>
18#include <utility>
19#include <vector>
20
21#include "purify/secret.hpp"
22
23namespace purify {
24
26enum class SymbolKind : std::uint8_t {
28 Left = 1,
29 Right = 2,
30 Output = 3,
32};
33
35struct Symbol {
37 std::uint32_t index = 0;
38
39 static Symbol witness(std::uint32_t index);
40 static Symbol left(std::uint32_t index);
41 static Symbol right(std::uint32_t index);
42 static Symbol output(std::uint32_t index);
43 static Symbol commitment(std::uint32_t index);
44
45 std::string to_string() const;
46 bool operator==(const Symbol&) const = default;
47};
48
49struct SymbolLess {
50 bool operator()(const Symbol& lhs, const Symbol& rhs) const noexcept {
51 using SymbolRank = std::underlying_type_t<SymbolKind>;
52 const SymbolRank lhs_kind = static_cast<SymbolRank>(lhs.kind);
53 const SymbolRank rhs_kind = static_cast<SymbolRank>(rhs.kind);
54 return lhs_kind < rhs_kind || (lhs_kind == rhs_kind && lhs.index < rhs.index);
55 }
56};
57
58inline bool operator<(const Symbol& lhs, const Symbol& rhs) noexcept {
59 return SymbolLess{}(lhs, rhs);
60}
61
63using WitnessAssignment = std::optional<FieldElement>;
65 std::vector<WitnessAssignment, detail::SecureAllocator<WitnessAssignment>>;
66
73class Expr {
74public:
75 using Term = std::pair<Symbol, FieldElement>;
76
78 Expr();
80 explicit Expr(const FieldElement& value);
82 explicit Expr(std::int64_t value);
83
85 static Expr variable(Symbol symbol);
86
88 const FieldElement& constant() const {
89 return constant_;
90 }
91
93 std::vector<Term>& linear() {
94 return linear_;
95 }
96
98 const std::vector<Term>& linear() const {
99 return linear_;
100 }
101
103 friend Expr operator+(const Expr& lhs, const Expr& rhs);
104
106 friend Expr operator+(const Expr& lhs, std::int64_t rhs);
107
109 friend Expr operator+(std::int64_t lhs, const Expr& rhs);
110
112 friend Expr operator-(const Expr& lhs, const Expr& rhs);
113
115 friend Expr operator-(const Expr& lhs, std::int64_t rhs);
116
118 friend Expr operator-(std::int64_t lhs, const Expr& rhs);
119
121 friend Expr operator-(const Expr& value);
122
124 friend Expr operator*(const Expr& expr, const FieldElement& scalar);
125
127 friend Expr operator*(const FieldElement& scalar, const Expr& expr);
128
130 friend Expr operator*(const Expr& expr, std::int64_t scalar);
131
133 friend Expr operator*(std::int64_t scalar, const Expr& expr);
134
136 friend bool operator==(const Expr& lhs, const Expr& rhs);
137
139 friend bool operator<(const Expr& lhs, const Expr& rhs);
140
142 std::string to_string() const;
143
145 std::optional<FieldElement> evaluate(const WitnessAssignments& values) const;
146
148 std::pair<Expr, Expr> split() const;
149
150private:
152 void push_term(const Term& term);
153
154 FieldElement constant_;
155 std::vector<Term> linear_;
156};
157
158struct ExprLess {
159 bool operator()(const Expr& lhs, const Expr& rhs) const;
160};
161
163 bool operator()(const std::pair<Expr, Expr>& lhs, const std::pair<Expr, Expr>& rhs) const;
164};
165
173public:
175 static ExprBuilder reserved(std::size_t terms);
176
178 ExprBuilder& reserve(std::size_t terms);
179
181 ExprBuilder& add(const FieldElement& value);
182
184 ExprBuilder& add(std::int64_t value);
185
187 ExprBuilder& add_term(Symbol symbol, const FieldElement& scale);
188
190 ExprBuilder& add(const Expr& expr);
191
193 ExprBuilder& subtract(const Expr& expr);
194
196 ExprBuilder& add_scaled(const Expr& expr, const FieldElement& scale);
197
199 ExprBuilder& add_scaled(const Expr& expr, std::int64_t scale);
200
202 Expr build();
203
204private:
205 FieldElement constant_ = FieldElement::zero();
206 std::vector<Expr::Term> terms_;
207};
208
210std::ostream& operator<<(std::ostream& out, const Expr& expr);
211
216public:
217 Transcript() = default;
218 Transcript(const Transcript&) = delete;
219 Transcript& operator=(const Transcript&) = delete;
220 Transcript(Transcript&&) noexcept = default;
221 Transcript& operator=(Transcript&&) = delete;
222 ~Transcript();
223
225 Expr secret(const std::optional<FieldElement>& value);
226
228 Expr mul(const Expr& lhs, const Expr& rhs);
229
231 Expr div(const Expr& lhs, const Expr& rhs);
232
234 Expr boolean(const Expr& expr);
235
237 void equal(const Expr& lhs, const Expr& rhs);
238
240 std::optional<FieldElement> evaluate(const Expr& expr) const;
241
243 const WitnessAssignments& varmap() const {
244 return varmap_;
245 }
246
253
255 const std::vector<MulConstraint>& muls() const {
256 return muls_;
257 }
258
260 const std::vector<Expr>& eqs() const {
261 return eqs_;
262 }
263
264private:
265 WitnessAssignments varmap_;
266 std::vector<MulConstraint> muls_;
267 std::map<std::pair<Expr, Expr>, Expr, ExprPairLess> mul_cache_;
268 std::map<std::pair<Expr, Expr>, Expr, ExprPairLess> div_cache_;
269 std::set<Expr, ExprLess> bool_cache_;
270 std::vector<Expr> eqs_;
271};
272
273Expr operator+(const Expr& lhs, const Expr& rhs);
274Expr operator+(const Expr& lhs, std::int64_t rhs);
275Expr operator+(std::int64_t lhs, const Expr& rhs);
276Expr operator-(const Expr& lhs, const Expr& rhs);
277Expr operator-(const Expr& lhs, std::int64_t rhs);
278Expr operator-(std::int64_t lhs, const Expr& rhs);
279Expr operator-(const Expr& value);
280Expr operator*(const Expr& expr, const FieldElement& scalar);
281Expr operator*(const FieldElement& scalar, const Expr& expr);
282Expr operator*(const Expr& expr, std::int64_t scalar);
283Expr operator*(std::int64_t scalar, const Expr& expr);
284bool operator==(const Expr& lhs, const Expr& rhs);
285bool operator<(const Expr& lhs, const Expr& rhs);
286
287} // namespace purify
Small runtime builder that flattens affine combinations into one expression.
Definition expr.hpp:172
ExprBuilder & add(const FieldElement &value)
Adds a constant field term to the pending affine expression.
Definition expr.cpp:183
ExprBuilder & add_term(Symbol symbol, const FieldElement &scale)
Adds one scaled symbolic variable term.
Definition expr.cpp:192
static ExprBuilder reserved(std::size_t terms)
Returns a builder with storage reserved for approximately terms linear slots.
Definition expr.cpp:172
Expr build()
Materializes the flattened affine expression.
Definition expr.cpp:254
ExprBuilder & add_scaled(const Expr &expr, const FieldElement &scale)
Adds an existing expression scaled by a field element.
Definition expr.cpp:226
ExprBuilder & subtract(const Expr &expr)
Subtracts an existing expression with implicit coefficient minus one.
Definition expr.cpp:211
ExprBuilder & reserve(std::size_t terms)
Reserves storage for approximately terms linear slots.
Definition expr.cpp:178
Symbolic affine expression over indexed variables and field coefficients.
Definition expr.hpp:73
friend bool operator==(const Expr &lhs, const Expr &rhs)
Compares two affine expressions structurally.
Definition expr.cpp:347
friend Expr operator*(const Expr &expr, const FieldElement &scalar)
Scales an affine expression by a field element.
Definition expr.cpp:323
const FieldElement & constant() const
Returns the constant term of the affine expression.
Definition expr.hpp:88
std::string to_string() const
Formats the expression in a stable human-readable form used for debugging and serialization.
Definition expr.cpp:116
std::vector< Term > & linear()
Returns mutable access to the sorted linear term list.
Definition expr.hpp:93
friend Expr operator+(const Expr &lhs, const Expr &rhs)
Adds two affine expressions and merges like terms.
Definition expr.cpp:277
Expr()
Constructs the zero expression.
Definition expr.cpp:104
friend Expr operator-(const Expr &lhs, const Expr &rhs)
Subtracts one affine expression from another.
Definition expr.cpp:307
std::pair< Symbol, FieldElement > Term
Definition expr.hpp:75
const std::vector< Term > & linear() const
Returns read-only access to the sorted linear term list.
Definition expr.hpp:98
static Expr variable(Symbol symbol)
Returns a single-variable expression with coefficient one.
Definition expr.cpp:110
std::optional< FieldElement > evaluate(const WitnessAssignments &values) const
Evaluates the expression against a possibly partial transcript witness assignment.
Definition expr.cpp:137
friend bool operator<(const Expr &lhs, const Expr &rhs)
Orders affine expressions structurally for cache keys.
Definition expr.cpp:381
std::pair< Expr, Expr > split() const
Splits the expression into a pure constant and a pure linear component.
Definition expr.cpp:152
Field element modulo the backend scalar field used by this implementation.
Definition numeric.hpp:834
static FieldElement zero()
Returns the additive identity of the scalar field.
Definition numeric.cpp:32
Transcript(const Transcript &)=delete
const std::vector< Expr > & eqs() const
Returns the linear equality constraints accumulated so far.
Definition expr.hpp:260
Expr secret(const std::optional< FieldElement > &value)
Allocates a new secret witness variable, optionally with a known concrete value.
Definition expr.cpp:390
std::optional< FieldElement > evaluate(const Expr &expr) const
Evaluates an expression against the transcript's current witness vector.
Definition expr.cpp:479
Transcript()=default
const std::vector< MulConstraint > & muls() const
Returns the multiplication and division constraints accumulated so far.
Definition expr.hpp:255
Expr mul(const Expr &lhs, const Expr &rhs)
Allocates or reuses a multiplication witness enforcing lhs * rhs = out.
Definition expr.cpp:398
const WitnessAssignments & varmap() const
Returns the underlying witness assignment vector.
Definition expr.hpp:243
Transcript(Transcript &&) noexcept=default
Transcript & operator=(const Transcript &)=delete
Expr div(const Expr &lhs, const Expr &rhs)
Allocates or reuses a division witness enforcing out * rhs = lhs.
Definition expr.cpp:424
void equal(const Expr &lhs, const Expr &rhs)
Records a linear equality constraint between two expressions.
Definition expr.cpp:469
bool operator<(const Symbol &lhs, const Symbol &rhs) noexcept
Definition expr.hpp:58
std::optional< FieldElement > WitnessAssignment
Partial witness assignment vector indexed by transcript witness id.
Definition expr.hpp:63
Expr operator*(const Expr &expr, const FieldElement &scalar)
Definition expr.cpp:323
std::ostream & operator<<(std::ostream &out, const Expr &expr)
Streams the human-readable expression form to an output stream.
Definition expr.cpp:385
SymbolKind
Symbol classes used while deriving witness and Bulletproof wire relations.
Definition expr.hpp:26
std::vector< WitnessAssignment, detail::SecureAllocator< WitnessAssignment > > WitnessAssignments
Definition expr.hpp:64
bool operator==(const Expr &lhs, const Expr &rhs)
Definition expr.cpp:347
Expr operator-(const Expr &lhs, const Expr &rhs)
Definition expr.cpp:307
Bytes operator+(Bytes lhs, const Bytes &rhs)
Concatenates two byte vectors.
Definition curve.cpp:172
Secret-owning Purify key material wrappers.
bool operator()(const Expr &lhs, const Expr &rhs) const
Definition expr.cpp:351
bool operator()(const std::pair< Expr, Expr > &lhs, const std::pair< Expr, Expr > &rhs) const
Definition expr.cpp:370
bool operator()(const Symbol &lhs, const Symbol &rhs) const noexcept
Definition expr.hpp:50
Compact symbolic variable identifier used inside expressions and transcripts.
Definition expr.hpp:35
bool operator==(const Symbol &) const =default
static Symbol witness(std::uint32_t index)
Definition expr.cpp:67
static Symbol left(std::uint32_t index)
Definition expr.cpp:71
static Symbol output(std::uint32_t index)
Definition expr.cpp:79
std::uint32_t index
Definition expr.hpp:37
std::string to_string() const
Definition expr.cpp:87
static Symbol commitment(std::uint32_t index)
Definition expr.cpp:83
static Symbol right(std::uint32_t index)
Definition expr.cpp:75
SymbolKind kind
Definition expr.hpp:36
One multiplicative relation emitted by the symbolic transcript.
Definition expr.hpp:248