purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
expr.cpp
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#include "purify/expr.hpp"
11
12#include "purify/secret.hpp"
13#include "secure_cleanup.hpp"
14
15#include <algorithm>
16#include <array>
17#include <cassert>
18#include <charconv>
19#include <limits>
20#include <sstream>
21#include <string_view>
22#include <utility>
23
24namespace {
25
27
28int compare_field_elements(const purify::FieldElement& lhs, const purify::FieldElement& rhs) {
29 return lhs.to_uint256().compare(rhs.to_uint256());
30}
31
32int compare_symbols(const purify::Symbol& lhs, const purify::Symbol& rhs) {
33 const purify::SymbolLess less;
34 if (less(lhs, rhs)) {
35 return -1;
36 }
37 if (less(rhs, lhs)) {
38 return 1;
39 }
40 return 0;
41}
42
43std::string make_symbol_string(std::string_view prefix, std::uint32_t index, std::string_view suffix = {}) {
44 std::array<char, std::numeric_limits<std::uint32_t>::digits10 + 1> digits{};
45 const auto [ptr, ec] = std::to_chars(digits.data(), digits.data() + digits.size(), index);
46 assert(ec == std::errc() && "uint32_t index must format into a fixed-size decimal buffer");
47
48 std::string out;
49 out.reserve(prefix.size() + static_cast<std::size_t>(ptr - digits.data()) + suffix.size());
50 out.append(prefix);
51 out.append(digits.data(), ptr);
52 out.append(suffix);
53 return out;
54}
55
56} // namespace
57
58namespace purify {
59
61 static_assert(std::is_trivially_destructible_v<
62 WitnessAssignments::value_type>);
64 varmap_.data(), varmap_.size() * sizeof(varmap_.front()));
65}
66
68 return {SymbolKind::Witness, index};
69}
70
71Symbol Symbol::left(std::uint32_t index) {
72 return {SymbolKind::Left, index};
73}
74
75Symbol Symbol::right(std::uint32_t index) {
76 return {SymbolKind::Right, index};
77}
78
79Symbol Symbol::output(std::uint32_t index) {
80 return {SymbolKind::Output, index};
81}
82
85}
86
87std::string Symbol::to_string() const {
88 switch (kind) {
90 return make_symbol_string("v[", index, "]");
92 return make_symbol_string("L", index);
94 return make_symbol_string("R", index);
96 return make_symbol_string("O", index);
98 return make_symbol_string("V", index);
99 }
100 assert(false && "unknown SymbolKind");
101 return "?";
102}
103
104Expr::Expr() : constant_(FieldElement::zero()) {}
105
106Expr::Expr(const FieldElement& value) : constant_(value) {}
107
108Expr::Expr(std::int64_t value) : constant_(FieldElement::from_int(value)) {}
109
111 Expr out;
112 out.linear_.push_back({symbol, FieldElement::one()});
113 return out;
114}
115
116std::string Expr::to_string() const {
117 std::ostringstream out;
118 bool first = true;
119 if (!constant_.is_zero() || linear_.empty()) {
120 out << constant_.to_decimal();
121 first = false;
122 }
123 for (const auto& term : linear_) {
124 if (!first) {
125 out << " + ";
126 }
127 if (term.second == FieldElement::one()) {
128 out << term.first.to_string();
129 } else {
130 out << term.second.to_decimal() << " * " << term.first.to_string();
131 }
132 first = false;
133 }
134 return out.str();
135}
136
137std::optional<FieldElement> Expr::evaluate(const WitnessAssignments& values) const {
138 FieldElement out = constant_;
139 for (const auto& term : linear_) {
140 if (term.first.kind != SymbolKind::Witness) {
141 return std::nullopt;
142 }
143 std::size_t index = term.first.index;
144 if (index >= values.size() || !values[index].has_value()) {
145 return std::nullopt;
146 }
147 out = out + (*values[index] * term.second);
148 }
149 return out;
150}
151
152std::pair<Expr, Expr> Expr::split() const {
153 Expr linear_expr(0);
154 linear_expr.linear_ = linear_;
155 return {Expr(constant_), linear_expr};
156}
157
158void Expr::push_term(const Term& term) {
159 if (term.second.is_zero()) {
160 return;
161 }
162 if (!linear_.empty() && linear_.back().first == term.first) {
163 linear_.back().second = linear_.back().second + term.second;
164 if (linear_.back().second.is_zero()) {
165 linear_.pop_back();
166 }
167 return;
168 }
169 linear_.push_back(term);
170}
171
173 ExprBuilder builder;
174 builder.terms_.reserve(terms);
175 return builder;
176}
177
179 terms_.reserve(terms);
180 return *this;
181}
182
184 constant_ = constant_ + value;
185 return *this;
186}
187
188ExprBuilder& ExprBuilder::add(std::int64_t value) {
189 return add(FieldElement::from_int(value));
190}
191
193 if (!scale.is_zero()) {
194 terms_.push_back({symbol, scale});
195 }
196 return *this;
197}
198
200 constant_ = constant_ + expr.constant();
201 if (expr.linear().empty()) {
202 return *this;
203 }
204 terms_.reserve(terms_.size() + expr.linear().size());
205 for (const auto& term : expr.linear()) {
206 terms_.push_back(term);
207 }
208 return *this;
209}
210
212 constant_ = constant_ - expr.constant();
213 if (expr.linear().empty()) {
214 return *this;
215 }
216 terms_.reserve(terms_.size() + expr.linear().size());
217 for (const auto& term : expr.linear()) {
218 FieldElement coeff = term.second.negate();
219 if (!coeff.is_zero()) {
220 terms_.push_back({term.first, coeff});
221 }
222 }
223 return *this;
224}
225
227 if (scale.is_zero()) {
228 return *this;
229 }
230 if (scale.is_one()) {
231 return add(expr);
232 }
233 if (scale == FieldElement::from_int(-1)) {
234 return subtract(expr);
235 }
236 constant_ = constant_ + expr.constant() * scale;
237 if (expr.linear().empty()) {
238 return *this;
239 }
240 terms_.reserve(terms_.size() + expr.linear().size());
241 for (const auto& term : expr.linear()) {
242 FieldElement coeff = term.second * scale;
243 if (!coeff.is_zero()) {
244 terms_.push_back({term.first, coeff});
245 }
246 }
247 return *this;
248}
249
250ExprBuilder& ExprBuilder::add_scaled(const Expr& expr, std::int64_t scale) {
251 return add_scaled(expr, FieldElement::from_int(scale));
252}
253
255 Expr out(constant_);
256 if (terms_.empty()) {
257 return out;
258 }
259 std::sort(terms_.begin(), terms_.end(), [](const Expr::Term& lhs, const Expr::Term& rhs) {
260 return SymbolLess{}(lhs.first, rhs.first);
261 });
262 auto& linear = out.linear();
263 linear.reserve(terms_.size());
264 for (const auto& term : terms_) {
265 if (!linear.empty() && linear.back().first == term.first) {
266 linear.back().second = linear.back().second + term.second;
267 if (linear.back().second.is_zero()) {
268 linear.pop_back();
269 }
270 } else if (!term.second.is_zero()) {
271 linear.push_back(term);
272 }
273 }
274 return out;
275}
276
277Expr operator+(const Expr& lhs, const Expr& rhs) {
278 Expr out(lhs.constant_ + rhs.constant_);
279 out.linear_.reserve(lhs.linear_.size() + rhs.linear_.size());
280 const SymbolLess less;
281 std::size_t i = 0;
282 std::size_t j = 0;
283 while (i < lhs.linear_.size() || j < rhs.linear_.size()) {
284 if (j == rhs.linear_.size() || (i < lhs.linear_.size() && less(lhs.linear_[i].first, rhs.linear_[j].first))) {
285 out.push_term(lhs.linear_[i]);
286 ++i;
287 } else if (i == lhs.linear_.size() || less(rhs.linear_[j].first, lhs.linear_[i].first)) {
288 out.push_term(rhs.linear_[j]);
289 ++j;
290 } else {
291 out.push_term({lhs.linear_[i].first, lhs.linear_[i].second + rhs.linear_[j].second});
292 ++i;
293 ++j;
294 }
295 }
296 return out;
297}
298
299Expr operator+(const Expr& lhs, std::int64_t rhs) {
300 return lhs + Expr(rhs);
301}
302
303Expr operator+(std::int64_t lhs, const Expr& rhs) {
304 return Expr(lhs) + rhs;
305}
306
307Expr operator-(const Expr& lhs, const Expr& rhs) {
308 return lhs + (-rhs);
309}
310
311Expr operator-(const Expr& lhs, std::int64_t rhs) {
312 return lhs - Expr(rhs);
313}
314
315Expr operator-(std::int64_t lhs, const Expr& rhs) {
316 return Expr(lhs) - rhs;
317}
318
319Expr operator-(const Expr& value) {
320 return value * FieldElement::from_int(-1);
321}
322
323Expr operator*(const Expr& expr, const FieldElement& scalar) {
324 if (scalar.is_zero()) {
325 return Expr(0);
326 }
327 Expr out(expr.constant_ * scalar);
328 out.linear_.reserve(expr.linear_.size());
329 for (const auto& term : expr.linear_) {
330 out.linear_.push_back({term.first, term.second * scalar});
331 }
332 return out;
333}
334
335Expr operator*(const FieldElement& scalar, const Expr& expr) {
336 return expr * scalar;
337}
338
339Expr operator*(const Expr& expr, std::int64_t scalar) {
340 return expr * FieldElement::from_int(scalar);
341}
342
343Expr operator*(std::int64_t scalar, const Expr& expr) {
344 return expr * scalar;
345}
346
347bool operator==(const Expr& lhs, const Expr& rhs) {
348 return lhs.constant_ == rhs.constant_ && lhs.linear_ == rhs.linear_;
349}
350
351bool ExprLess::operator()(const Expr& lhs, const Expr& rhs) const {
352 int constant_cmp = compare_field_elements(lhs.constant(), rhs.constant());
353 if (constant_cmp != 0) {
354 return constant_cmp < 0;
355 }
356 std::size_t common = std::min(lhs.linear().size(), rhs.linear().size());
357 for (std::size_t i = 0; i < common; ++i) {
358 int symbol_cmp = compare_symbols(lhs.linear()[i].first, rhs.linear()[i].first);
359 if (symbol_cmp != 0) {
360 return symbol_cmp < 0;
361 }
362 int coeff_cmp = compare_field_elements(lhs.linear()[i].second, rhs.linear()[i].second);
363 if (coeff_cmp != 0) {
364 return coeff_cmp < 0;
365 }
366 }
367 return lhs.linear().size() < rhs.linear().size();
368}
369
370bool ExprPairLess::operator()(const std::pair<Expr, Expr>& lhs, const std::pair<Expr, Expr>& rhs) const {
371 const ExprLess less;
372 if (less(lhs.first, rhs.first)) {
373 return true;
374 }
375 if (less(rhs.first, lhs.first)) {
376 return false;
377 }
378 return less(lhs.second, rhs.second);
379}
380
381bool operator<(const Expr& lhs, const Expr& rhs) {
382 return ExprLess{}(lhs, rhs);
383}
384
385std::ostream& operator<<(std::ostream& out, const Expr& expr) {
386 out << expr.to_string();
387 return out;
388}
389
390Expr Transcript::secret(const std::optional<FieldElement>& value) {
391 std::size_t index = varmap_.size();
392 assert(index <= static_cast<std::size_t>(std::numeric_limits<std::uint32_t>::max())
393 && "Transcript::secret() witness index must fit in uint32_t");
394 varmap_.push_back(value);
395 return Expr::variable(Symbol::witness(static_cast<std::uint32_t>(index)));
396}
397
398Expr Transcript::mul(const Expr& lhs, const Expr& rhs) {
399 auto direct = std::make_pair(lhs, rhs);
400 auto reverse = std::make_pair(rhs, lhs);
401 auto it = mul_cache_.find(direct);
402 if (it != mul_cache_.end()) {
403 return it->second;
404 }
405 it = mul_cache_.find(reverse);
406 if (it != mul_cache_.end()) {
407 return it->second;
408 }
409 std::optional<FieldElement> lhs_val = lhs.evaluate(varmap_);
410 WipeOnDestruction lhs_guard(lhs_val);
411 std::optional<FieldElement> rhs_val = rhs.evaluate(varmap_);
412 WipeOnDestruction rhs_guard(rhs_val);
413 std::optional<FieldElement> value;
414 WipeOnDestruction value_guard(value);
415 if (lhs_val.has_value() && rhs_val.has_value()) {
416 value = *lhs_val * *rhs_val;
417 }
418 Expr out = secret(value);
419 mul_cache_[direct] = out;
420 muls_.push_back({lhs, rhs, out});
421 return out;
422}
423
424Expr Transcript::div(const Expr& lhs, const Expr& rhs) {
425 auto direct = std::make_pair(lhs, rhs);
426 auto it = div_cache_.find(direct);
427 if (it != div_cache_.end()) {
428 return it->second;
429 }
430 std::optional<FieldElement> lhs_val = lhs.evaluate(varmap_);
431 WipeOnDestruction lhs_guard(lhs_val);
432 std::optional<FieldElement> rhs_val = rhs.evaluate(varmap_);
433 WipeOnDestruction rhs_guard(rhs_val);
434 assert((!rhs_val.has_value() || !rhs_val->is_zero()) && "Transcript::div() requires a non-zero known divisor");
435 std::optional<FieldElement> value;
436 WipeOnDestruction value_guard(value);
437 if (lhs_val.has_value() && rhs_val.has_value()) {
438 FieldElement inverse = rhs_val->inverse_consttime();
439 WipeOnDestruction inverse_guard(inverse);
440 value = *lhs_val * inverse;
441 }
442 Expr out = secret(value);
443 div_cache_[direct] = out;
444 muls_.push_back({out, rhs, lhs});
445 return out;
446}
447
449 if (bool_cache_.count(expr) != 0) {
450 return expr;
451 }
452#ifndef NDEBUG
453 std::optional<FieldElement> value = expr.evaluate(varmap_);
454 WipeOnDestruction value_guard(value);
455 bool valid = true;
456 if (value.has_value()) {
457 FieldElement check = *value * (*value - FieldElement::one());
458 WipeOnDestruction check_guard(check);
459 valid = check.is_zero();
460 }
461 assert(valid
462 && "Transcript::boolean() requires a known value to be 0 or 1");
463#endif
464 bool_cache_.insert(expr);
465 muls_.push_back({expr, expr - 1, Expr(0)});
466 return expr;
467}
468
469void Transcript::equal(const Expr& lhs, const Expr& rhs) {
470 Expr diff = lhs - rhs;
471#ifndef NDEBUG
472 std::optional<FieldElement> value = diff.evaluate(varmap_);
473 WipeOnDestruction value_guard(value);
474 assert((!value.has_value() || value->is_zero()) && "Transcript::equal() requires known values to match");
475#endif
476 eqs_.push_back(diff);
477}
478
479std::optional<FieldElement> Transcript::evaluate(const Expr& expr) const {
480 return expr.evaluate(varmap_);
481}
482
483} // 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
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
bool is_one() const
Returns true when the element is one.
Definition numeric.cpp:108
static FieldElement one()
Returns the multiplicative identity of the scalar field.
Definition numeric.cpp:36
FieldElement negate() const
Returns the additive inverse modulo the field prime.
Definition numeric.cpp:121
static FieldElement from_int(std::int64_t value)
Constructs a field element from a signed integer, reducing negatives modulo the field.
Definition numeric.cpp:46
UInt256 to_uint256() const
Exports the field element as a canonical 256-bit unsigned integer.
Definition numeric.cpp:79
bool is_zero() const
Returns true when the element is zero.
Definition numeric.cpp:104
FieldElement inverse_consttime() const
Returns the multiplicative inverse modulo the field prime in constant time.
Definition numeric.cpp:131
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
Expr boolean(const Expr &expr)
Constrains an expression to be boolean by adding x * (x - 1) = 0.
Definition expr.cpp:448
Expr mul(const Expr &lhs, const Expr &rhs)
Allocates or reuses a multiplication witness enforcing lhs * rhs = out.
Definition expr.cpp:398
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
Symbolic expression and transcript machinery used to derive Purify circuits.
void secure_clear_bytes(void *data, std::size_t size) noexcept
Definition secret.hpp:22
std::ostream & operator<<(std::ostream &out, const Expr &expr)
Streams the human-readable expression form to an output stream.
Definition expr.cpp:385
std::vector< WitnessAssignment, detail::SecureAllocator< WitnessAssignment > > WitnessAssignments
Definition expr.hpp:64
Secret-owning Purify key material wrappers.
int compare(const BigUInt &other) const
Compares two fixed-width integers using unsigned ordering.
Definition numeric.hpp:304
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
Compact symbolic variable identifier used inside expressions and transcripts.
Definition expr.hpp:35
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