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");
49 out.reserve(prefix.size() +
static_cast<std::size_t
>(ptr - digits.data()) + suffix.size());
51 out.append(digits.data(), ptr);
61 static_assert(std::is_trivially_destructible_v<
62 WitnessAssignments::value_type>);
64 varmap_.data(), varmap_.size() *
sizeof(varmap_.front()));
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);
100 assert(
false &&
"unknown SymbolKind");
117 std::ostringstream out;
119 if (!constant_.is_zero() || linear_.empty()) {
120 out << constant_.to_decimal();
123 for (
const auto& term : linear_) {
128 out << term.first.to_string();
130 out << term.second.to_decimal() <<
" * " << term.first.to_string();
139 for (
const auto& term : linear_) {
143 std::size_t index = term.first.index;
144 if (index >= values.size() || !values[index].has_value()) {
147 out = out + (*values[index] * term.second);
154 linear_expr.linear_ = linear_;
155 return {
Expr(constant_), linear_expr};
158void Expr::push_term(
const Term& term) {
159 if (term.second.is_zero()) {
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()) {
169 linear_.push_back(term);
174 builder.terms_.reserve(terms);
184 constant_ = constant_ + value;
194 terms_.push_back({symbol, scale});
200 constant_ = constant_ + expr.
constant();
201 if (expr.
linear().empty()) {
204 terms_.reserve(terms_.size() + expr.
linear().size());
205 for (
const auto& term : expr.
linear()) {
206 terms_.push_back(term);
212 constant_ = constant_ - expr.
constant();
213 if (expr.
linear().empty()) {
216 terms_.reserve(terms_.size() + expr.
linear().size());
217 for (
const auto& term : expr.
linear()) {
220 terms_.push_back({term.first, coeff});
236 constant_ = constant_ + expr.
constant() * scale;
237 if (expr.
linear().empty()) {
240 terms_.reserve(terms_.size() + expr.
linear().size());
241 for (
const auto& term : expr.
linear()) {
244 terms_.push_back({term.first, coeff});
256 if (terms_.empty()) {
260 return SymbolLess{}(lhs.first, rhs.first);
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()) {
270 }
else if (!term.second.is_zero()) {
271 linear.push_back(term);
278 Expr out(lhs.constant_ + rhs.constant_);
279 out.linear_.reserve(lhs.linear_.size() + rhs.linear_.size());
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]);
287 }
else if (i == lhs.linear_.size() || less(rhs.linear_[j].first, lhs.linear_[i].first)) {
288 out.push_term(rhs.linear_[j]);
291 out.push_term({lhs.linear_[i].first, lhs.linear_[i].second + rhs.linear_[j].second});
300 return lhs +
Expr(rhs);
304 return Expr(lhs) + rhs;
312 return lhs -
Expr(rhs);
316 return Expr(lhs) - rhs;
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});
336 return expr * scalar;
344 return expr * scalar;
348 return lhs.constant_ == rhs.constant_ && lhs.linear_ == rhs.linear_;
353 if (constant_cmp != 0) {
354 return constant_cmp < 0;
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;
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;
372 if (less(lhs.first, rhs.first)) {
375 if (less(rhs.first, lhs.first)) {
378 return less(lhs.second, rhs.second);
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);
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()) {
405 it = mul_cache_.find(reverse);
406 if (it != mul_cache_.end()) {
409 std::optional<FieldElement> lhs_val = lhs.
evaluate(varmap_);
411 std::optional<FieldElement> rhs_val = rhs.
evaluate(varmap_);
413 std::optional<FieldElement> value;
415 if (lhs_val.has_value() && rhs_val.has_value()) {
416 value = *lhs_val * *rhs_val;
419 mul_cache_[direct] = out;
420 muls_.push_back({lhs, rhs, out});
425 auto direct = std::make_pair(lhs, rhs);
426 auto it = div_cache_.find(direct);
427 if (it != div_cache_.end()) {
430 std::optional<FieldElement> lhs_val = lhs.
evaluate(varmap_);
432 std::optional<FieldElement> rhs_val = rhs.
evaluate(varmap_);
434 assert((!rhs_val.has_value() || !rhs_val->is_zero()) &&
"Transcript::div() requires a non-zero known divisor");
435 std::optional<FieldElement> value;
437 if (lhs_val.has_value() && rhs_val.has_value()) {
440 value = *lhs_val * inverse;
443 div_cache_[direct] = out;
444 muls_.push_back({out, rhs, lhs});
449 if (bool_cache_.count(expr) != 0) {
453 std::optional<FieldElement> value = expr.
evaluate(varmap_);
456 if (value.has_value()) {
462 &&
"Transcript::boolean() requires a known value to be 0 or 1");
464 bool_cache_.insert(expr);
465 muls_.push_back({expr, expr - 1,
Expr(0)});
470 Expr diff = lhs - rhs;
472 std::optional<FieldElement> value = diff.
evaluate(varmap_);
474 assert((!value.has_value() || value->is_zero()) &&
"Transcript::equal() requires known values to match");
476 eqs_.push_back(diff);
Small runtime builder that flattens affine combinations into one expression.
ExprBuilder & add(const FieldElement &value)
Adds a constant field term to the pending affine expression.
ExprBuilder & add_term(Symbol symbol, const FieldElement &scale)
Adds one scaled symbolic variable term.
static ExprBuilder reserved(std::size_t terms)
Returns a builder with storage reserved for approximately terms linear slots.
Expr build()
Materializes the flattened affine expression.
ExprBuilder & add_scaled(const Expr &expr, const FieldElement &scale)
Adds an existing expression scaled by a field element.
ExprBuilder & subtract(const Expr &expr)
Subtracts an existing expression with implicit coefficient minus one.
ExprBuilder & reserve(std::size_t terms)
Reserves storage for approximately terms linear slots.
Symbolic affine expression over indexed variables and field coefficients.
friend bool operator==(const Expr &lhs, const Expr &rhs)
Compares two affine expressions structurally.
friend Expr operator*(const Expr &expr, const FieldElement &scalar)
Scales an affine expression by a field element.
const FieldElement & constant() const
Returns the constant term of the affine expression.
std::string to_string() const
Formats the expression in a stable human-readable form used for debugging and serialization.
std::vector< Term > & linear()
Returns mutable access to the sorted linear term list.
friend Expr operator+(const Expr &lhs, const Expr &rhs)
Adds two affine expressions and merges like terms.
Expr()
Constructs the zero expression.
friend Expr operator-(const Expr &lhs, const Expr &rhs)
Subtracts one affine expression from another.
std::pair< Symbol, FieldElement > Term
static Expr variable(Symbol symbol)
Returns a single-variable expression with coefficient one.
std::optional< FieldElement > evaluate(const WitnessAssignments &values) const
Evaluates the expression against a possibly partial transcript witness assignment.
friend bool operator<(const Expr &lhs, const Expr &rhs)
Orders affine expressions structurally for cache keys.
std::pair< Expr, Expr > split() const
Splits the expression into a pure constant and a pure linear component.
Field element modulo the backend scalar field used by this implementation.
bool is_one() const
Returns true when the element is one.
static FieldElement one()
Returns the multiplicative identity of the scalar field.
FieldElement negate() const
Returns the additive inverse modulo the field prime.
static FieldElement from_int(std::int64_t value)
Constructs a field element from a signed integer, reducing negatives modulo the field.
UInt256 to_uint256() const
Exports the field element as a canonical 256-bit unsigned integer.
bool is_zero() const
Returns true when the element is zero.
FieldElement inverse_consttime() const
Returns the multiplicative inverse modulo the field prime in constant time.
Expr secret(const std::optional< FieldElement > &value)
Allocates a new secret witness variable, optionally with a known concrete value.
std::optional< FieldElement > evaluate(const Expr &expr) const
Evaluates an expression against the transcript's current witness vector.
Expr boolean(const Expr &expr)
Constrains an expression to be boolean by adding x * (x - 1) = 0.
Expr mul(const Expr &lhs, const Expr &rhs)
Allocates or reuses a multiplication witness enforcing lhs * rhs = out.
Expr div(const Expr &lhs, const Expr &rhs)
Allocates or reuses a division witness enforcing out * rhs = lhs.
void equal(const Expr &lhs, const Expr &rhs)
Records a linear equality constraint between two expressions.
Symbolic expression and transcript machinery used to derive Purify circuits.
void secure_clear_bytes(void *data, std::size_t size) noexcept
std::ostream & operator<<(std::ostream &out, const Expr &expr)
Streams the human-readable expression form to an output stream.
std::vector< WitnessAssignment, detail::SecureAllocator< WitnessAssignment > > WitnessAssignments
Secret-owning Purify key material wrappers.
int compare(const BigUInt &other) const
Compares two fixed-width integers using unsigned ordering.
bool operator()(const Expr &lhs, const Expr &rhs) const
bool operator()(const std::pair< Expr, Expr > &lhs, const std::pair< Expr, Expr > &rhs) const
Compact symbolic variable identifier used inside expressions and transcripts.
static Symbol witness(std::uint32_t index)
static Symbol left(std::uint32_t index)
static Symbol output(std::uint32_t index)
std::string to_string() const
static Symbol commitment(std::uint32_t index)
static Symbol right(std::uint32_t index)