purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
bulletproof.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
11#include "purify/secret.hpp"
13#include "bppp_bridge.h"
14#include "secure_cleanup.hpp"
15
16#include <algorithm>
17#include <cassert>
18#include <cstdint>
19#include <cstring>
20#include <limits>
21#include <memory>
22#include <new>
23#include <sstream>
24#include <type_traits>
25#include <unordered_map>
26
27namespace purify {
28
29static_assert(sizeof(BulletproofPointBytes) == 33);
30static_assert(sizeof(BulletproofScalarBytes) == 32);
31
37
39 std::unique_ptr<purify_bulletproof_backend_resources, BulletproofBackendResourceDeleter>;
40
42 std::unordered_map<std::size_t, BulletproofBackendResourcePtr> resources;
43};
44
46
48 ExperimentalBulletproofBackendCache&& other) noexcept = default;
49
51 ExperimentalBulletproofBackendCache&& other) noexcept = default;
52
54
56 if (impl_ != nullptr) {
57 impl_->resources.clear();
58 }
59}
60
61std::size_t ExperimentalBulletproofBackendCache::size() const noexcept {
62 return impl_ != nullptr ? impl_->resources.size() : 0;
63}
64
66 std::size_t n_gates) const {
68 if (impl_ == nullptr) {
69 return clone;
70 }
71
72 auto it = impl_->resources.find(n_gates);
73 if (it == impl_->resources.end()) {
74 return clone;
75 }
76
79 if (cloned == nullptr) {
80 return unexpected_error(
82 "ExperimentalBulletproofBackendCache::clone_for_thread:backend_resources");
83 }
84 clone.impl_->resources.emplace(it->first, BulletproofBackendResourcePtr(cloned));
85 return clone;
86}
87
89 std::size_t n_gates,
90 purify_secp_context* secp_context) {
91 if (impl_ == nullptr || secp_context == nullptr) {
92 return nullptr;
93 }
94
95 auto it = impl_->resources.find(n_gates);
96 if (it != impl_->resources.end()) {
97 return it->second.get();
98 }
99
101 purify_bulletproof_backend_resources_create(secp_context, n_gates);
102 if (created == nullptr) {
103 return nullptr;
104 }
105
106 auto inserted = impl_->resources.emplace(n_gates, BulletproofBackendResourcePtr(created));
107 return inserted.first->second.get();
108}
109
110} // namespace purify
111
112namespace {
113
114using purify::Expr;
119using purify::Result;
121using purify::Symbol;
124using purify::Bytes;
132using purify::Status;
138
139static_assert(std::is_trivially_copyable_v<purify::NativeBulletproofCircuitTerm>,
140 "Packed circuit storage requires trivially copyable terms");
141static_assert(std::is_trivially_copyable_v<purify::FieldElement>,
142 "Packed circuit storage requires trivially copyable field elements");
143
145
146std::uint32_t narrow_symbol_index(std::size_t index) {
147 assert(index <= static_cast<std::size_t>(std::numeric_limits<std::uint32_t>::max())
148 && "symbol index must fit in uint32_t");
149 return static_cast<std::uint32_t>(index);
150}
151
152struct ResolvedValues {
153 WitnessAssignments witness;
155 WitnessAssignments right;
156 WitnessAssignments output;
157 WitnessAssignments commitment;
158
159 ResolvedValues(std::size_t witness_count, std::size_t gate_count, std::size_t commitment_count)
160 : witness(witness_count), left(gate_count), right(gate_count), output(gate_count), commitment(commitment_count) {}
161
162 std::optional<FieldElement> get(Symbol symbol) const {
163 std::size_t index = symbol.index;
164 switch (symbol.kind) {
165 case SymbolKind::Witness:
166 if (index >= witness.size()) {
167 return std::nullopt;
168 }
169 return witness[index];
170 case SymbolKind::Left:
171 if (index >= left.size()) {
172 return std::nullopt;
173 }
174 return left[index];
175 case SymbolKind::Right:
176 if (index >= right.size()) {
177 return std::nullopt;
178 }
179 return right[index];
180 case SymbolKind::Output:
181 if (index >= output.size()) {
182 return std::nullopt;
183 }
184 return output[index];
185 case SymbolKind::Commitment:
186 if (index >= commitment.size()) {
187 return std::nullopt;
188 }
189 return commitment[index];
190 }
191 return std::nullopt;
192 }
193
194 bool set(Symbol symbol, const FieldElement& value) {
195 std::size_t index = symbol.index;
196 switch (symbol.kind) {
197 case SymbolKind::Witness:
198 if (index >= witness.size()) {
199 return false;
200 }
201 witness[index] = value;
202 return true;
203 case SymbolKind::Left:
204 if (index >= left.size()) {
205 return false;
206 }
207 left[index] = value;
208 return true;
209 case SymbolKind::Right:
210 if (index >= right.size()) {
211 return false;
212 }
213 right[index] = value;
214 return true;
215 case SymbolKind::Output:
216 if (index >= output.size()) {
217 return false;
218 }
219 output[index] = value;
220 return true;
221 case SymbolKind::Commitment:
222 if (index >= commitment.size()) {
223 return false;
224 }
225 commitment[index] = value;
226 return true;
227 }
228 return false;
229 }
230};
231
232Result<FieldElement> evaluate_known(const Expr& expr, const ResolvedValues& values) {
233 FieldElement out = expr.constant();
234 for (const auto& term : expr.linear()) {
235 std::optional<FieldElement> value = values.get(term.first);
236 if (!value.has_value()) {
237 return purify::unexpected_error(purify::ErrorCode::MissingValue, "BulletproofTranscript::evaluate_known:missing_term");
238 }
239 out = out + *value * term.second;
240 }
241 return out;
242}
243
244bool checked_align_up(std::size_t value, std::size_t alignment, std::size_t& out) {
245 assert(alignment != 0 && "alignment must be non-zero");
246 const std::size_t remainder = value % alignment;
247 if (remainder == 0) {
248 out = value;
249 return true;
250 }
251 return checked_add_size(value, alignment - remainder, out);
252}
253
254bool packed_row_count(std::size_t n_gates, std::size_t n_commitments, std::size_t& out) {
255 std::size_t gate_rows = 0;
256 return checked_mul_size(n_gates, 3, gate_rows) && checked_add_size(gate_rows, n_commitments, out);
257}
258
259void append_u32_le(Bytes& out, std::uint32_t value) {
260 for (int i = 0; i < 4; ++i) {
261 out.push_back(static_cast<unsigned char>((value >> (8 * i)) & 0xffU));
262 }
263}
264
265void append_u64_le(Bytes& out, std::uint64_t value) {
266 for (int i = 0; i < 8; ++i) {
267 out.push_back(static_cast<unsigned char>((value >> (8 * i)) & 0xffU));
268 }
269}
270
271Status append_symbol_digest(Bytes& out, const purify::Symbol& symbol) {
272 using SymbolRank = std::underlying_type_t<purify::SymbolKind>;
273 append_u64_le(out, static_cast<std::uint64_t>(static_cast<SymbolRank>(symbol.kind)));
274 PURIFY_ASSIGN_OR_RETURN(const auto& symbol_index, narrow_size_to_u64(symbol.index, "append_symbol_digest:index"),
275 "append_symbol_digest:index");
276 append_u64_le(out, symbol_index);
277 return {};
278}
279
280Status append_expr_digest(Bytes& out, const purify::Expr& expr) {
281 const auto constant = expr.constant().to_bytes_be();
282 out.insert(out.end(), constant.begin(), constant.end());
283 PURIFY_ASSIGN_OR_RETURN(const auto& term_count, narrow_size_to_u64(expr.linear().size(), "append_expr_digest:term_count"),
284 "append_expr_digest:term_count");
285 append_u64_le(out, term_count);
286 for (const auto& term : expr.linear()) {
287 PURIFY_RETURN_IF_ERROR(append_symbol_digest(out, term.first), "append_expr_digest:symbol");
288 const auto coeff = term.second.to_bytes_be();
289 out.insert(out.end(), coeff.begin(), coeff.end());
290 }
291 return {};
292}
293
294std::optional<std::uint32_t> read_u32_le(std::span<const unsigned char> bytes, std::size_t offset) {
295 std::uint32_t value = 0;
296 if (offset > bytes.size() || bytes.size() - offset < 4) {
297 return std::nullopt;
298 }
299 for (int i = 0; i < 4; ++i) {
300 value |= static_cast<std::uint32_t>(bytes[offset + i]) << (8 * i);
301 }
302 return value;
303}
304
305Bytes flatten_scalars32(std::span<const FieldElement> values) {
306 Bytes out;
307 best_effort_reserve_mul(out, values.size(), 32);
308 for (const FieldElement& value : values) {
309 auto bytes = value.to_bytes_be();
310 out.insert(out.end(), bytes.begin(), bytes.end());
311 }
312 return out;
313}
314
315template <typename RowEntriesFn>
316Status append_row_family_digest_generic(Bytes& out, std::size_t row_count, const RowEntriesFn& row_entries,
317 const char* context) {
318 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_row_count, narrow_size_to_u64(row_count, context), context);
319 append_u64_le(out, encoded_row_count);
320 for (std::size_t i = 0; i < row_count; ++i) {
321 std::span<const purify::NativeBulletproofCircuitTerm> entries = row_entries(i);
322 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_entry_count, narrow_size_to_u64(entries.size(), context), context);
323 append_u64_le(out, encoded_entry_count);
324 for (const auto& entry : entries) {
325 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_entry_index, narrow_size_to_u64(entry.idx, context), context);
326 append_u64_le(out, encoded_entry_index);
327 auto scalar = entry.scalar.to_bytes_be();
328 out.insert(out.end(), scalar.begin(), scalar.end());
329 }
330 }
331 return {};
332}
333
334Result<Bytes> circuit_binding_digest(const purify::NativeBulletproofCircuit& circuit,
335 std::span<const unsigned char> statement_binding) {
336 static const purify::TaggedHash kCircuitBindingTag("Purify/ExperimentalBulletproof/CircuitV1");
337 if (!circuit.has_valid_shape()) {
338 return unexpected_error(ErrorCode::InvalidDimensions,
339 "circuit_binding_digest:native_shape");
340 }
341 std::size_t reserve_size = 0;
342 if (!checked_mul_size(circuit.c.size(), 32, reserve_size)
343 || !checked_add_size(64, reserve_size, reserve_size)) {
344 return unexpected_error(ErrorCode::Overflow, "circuit_binding_digest:native_reserve");
345 }
346
347 Bytes serialized;
348 serialized.reserve(reserve_size);
349 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_gates, narrow_size_to_u64(circuit.n_gates, "circuit_binding_digest:native_n_gates"),
350 "circuit_binding_digest:native_n_gates");
351 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_commitments,
352 narrow_size_to_u64(circuit.n_commitments, "circuit_binding_digest:native_n_commitments"),
353 "circuit_binding_digest:native_n_commitments");
354 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_bits, narrow_size_to_u64(circuit.n_bits, "circuit_binding_digest:native_n_bits"),
355 "circuit_binding_digest:native_n_bits");
356 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_constant_count,
357 narrow_size_to_u64(circuit.c.size(), "circuit_binding_digest:native_constant_count"),
358 "circuit_binding_digest:native_constant_count");
359 append_u64_le(serialized, encoded_n_gates);
360 append_u64_le(serialized, encoded_n_commitments);
361 append_u64_le(serialized, encoded_n_bits);
362 append_u64_le(serialized, encoded_constant_count);
363 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(
364 serialized, circuit.wl.size(),
365 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wl[i].entries); },
366 "circuit_binding_digest:native_wl"),
367 "circuit_binding_digest:native_wl");
368 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(
369 serialized, circuit.wr.size(),
370 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wr[i].entries); },
371 "circuit_binding_digest:native_wr"),
372 "circuit_binding_digest:native_wr");
373 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(
374 serialized, circuit.wo.size(),
375 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wo[i].entries); },
376 "circuit_binding_digest:native_wo"),
377 "circuit_binding_digest:native_wo");
378 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(
379 serialized, circuit.wv.size(),
380 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wv[i].entries); },
381 "circuit_binding_digest:native_wv"),
382 "circuit_binding_digest:native_wv");
383 for (const FieldElement& constant : circuit.c) {
384 auto bytes = constant.to_bytes_be();
385 serialized.insert(serialized.end(), bytes.begin(), bytes.end());
386 }
387 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_binding_size,
388 narrow_size_to_u64(statement_binding.size(), "circuit_binding_digest:native_statement_binding"),
389 "circuit_binding_digest:native_statement_binding");
390 append_u64_le(serialized, encoded_binding_size);
391 serialized.insert(serialized.end(), statement_binding.begin(), statement_binding.end());
392 std::array<unsigned char, 32> digest =
393 kCircuitBindingTag.digest(std::span<const unsigned char>(serialized.data(), serialized.size()));
394 return Bytes(digest.begin(), digest.end());
395}
396
397Result<Bytes> circuit_binding_digest(const PackedCircuit& circuit, std::span<const unsigned char> statement_binding) {
398 static const purify::TaggedHash kCircuitBindingTag("Purify/ExperimentalBulletproof/CircuitV1");
399 if (!circuit.has_valid_shape()) {
400 return unexpected_error(ErrorCode::InvalidDimensions,
401 "circuit_binding_digest:packed_shape");
402 }
403 std::size_t reserve_size = 0;
404 if (!checked_mul_size(circuit.constraint_count(), 32, reserve_size)
405 || !checked_add_size(64, reserve_size, reserve_size)) {
406 return unexpected_error(ErrorCode::Overflow, "circuit_binding_digest:packed_reserve");
407 }
408
409 Bytes serialized;
410 serialized.reserve(reserve_size);
411 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_gates, narrow_size_to_u64(circuit.n_gates(), "circuit_binding_digest:packed_n_gates"),
412 "circuit_binding_digest:packed_n_gates");
413 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_commitments,
414 narrow_size_to_u64(circuit.n_commitments(), "circuit_binding_digest:packed_n_commitments"),
415 "circuit_binding_digest:packed_n_commitments");
416 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_n_bits, narrow_size_to_u64(circuit.n_bits(), "circuit_binding_digest:packed_n_bits"),
417 "circuit_binding_digest:packed_n_bits");
418 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_constraint_count,
419 narrow_size_to_u64(circuit.constraint_count(), "circuit_binding_digest:packed_constraint_count"),
420 "circuit_binding_digest:packed_constraint_count");
421 append_u64_le(serialized, encoded_n_gates);
422 append_u64_le(serialized, encoded_n_commitments);
423 append_u64_le(serialized, encoded_n_bits);
424 append_u64_le(serialized, encoded_constraint_count);
425 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(serialized, circuit.n_gates(),
426 [&](std::size_t i) { return circuit.left_row(i).entries_view(); },
427 "circuit_binding_digest:packed_left"),
428 "circuit_binding_digest:packed_left");
429 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(serialized, circuit.n_gates(),
430 [&](std::size_t i) { return circuit.right_row(i).entries_view(); },
431 "circuit_binding_digest:packed_right"),
432 "circuit_binding_digest:packed_right");
433 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(serialized, circuit.n_gates(),
434 [&](std::size_t i) { return circuit.output_row(i).entries_view(); },
435 "circuit_binding_digest:packed_output"),
436 "circuit_binding_digest:packed_output");
437 PURIFY_RETURN_IF_ERROR(append_row_family_digest_generic(serialized, circuit.n_commitments(),
438 [&](std::size_t i) { return circuit.commitment_row(i).entries_view(); },
439 "circuit_binding_digest:packed_commitment"),
440 "circuit_binding_digest:packed_commitment");
441 for (const FieldElement& constant : circuit.constants()) {
442 auto bytes = constant.to_bytes_be();
443 serialized.insert(serialized.end(), bytes.begin(), bytes.end());
444 }
445 PURIFY_ASSIGN_OR_RETURN(const auto& encoded_binding_size,
446 narrow_size_to_u64(statement_binding.size(), "circuit_binding_digest:packed_statement_binding"),
447 "circuit_binding_digest:packed_statement_binding");
448 append_u64_le(serialized, encoded_binding_size);
449 serialized.insert(serialized.end(), statement_binding.begin(), statement_binding.end());
450 std::array<unsigned char, 32> digest =
451 kCircuitBindingTag.digest(std::span<const unsigned char>(serialized.data(), serialized.size()));
452 return Bytes(digest.begin(), digest.end());
453}
454
455template <typename CircuitLike>
456void append_constraint_to_circuit(CircuitLike& circuit, const Expr& lhs, const Expr& rhs) {
457 Expr combined = lhs - rhs;
458 std::size_t constraint_idx = circuit.add_constraint(combined.constant().negate());
459 for (const auto& term : combined.linear()) {
460 std::size_t index = term.first.index;
461 switch (term.first.kind) {
462 case SymbolKind::Left:
463 circuit.add_left_term(index, constraint_idx, term.second);
464 break;
465 case SymbolKind::Right:
466 circuit.add_right_term(index, constraint_idx, term.second);
467 break;
468 case SymbolKind::Output:
469 circuit.add_output_term(index, constraint_idx, term.second);
470 break;
471 case SymbolKind::Commitment:
472 circuit.add_commitment_term(index, constraint_idx, term.second);
473 break;
474 case SymbolKind::Witness:
475 assert(false && "append_constraint_to_circuit() encountered an unmapped witness symbol");
476 break;
477 }
478 }
479}
480
481Result<std::size_t> sum_circuit_gate_count(const PackedCircuit& base,
482 std::span<const purify::UInt512> public_keys) {
483 if (public_keys.empty()) {
484 return unexpected_error(ErrorCode::EmptyInput, "sum_circuit_gate_count:empty_roster");
485 }
486 if (!base.has_valid_shape() || !is_power_of_two_size(base.n_gates())
487 || base.n_commitments() != 1 || !base.commitment_row(0).entries_view().empty()) {
488 return unexpected_error(ErrorCode::InvalidDimensions, "sum_circuit_gate_count:template_shape");
489 }
490 std::size_t used_gates = 0;
491 if (!checked_mul_size(base.n_gates(), public_keys.size(), used_gates)) {
492 return unexpected_error(ErrorCode::Overflow, "sum_circuit_gate_count:used_gates");
493 }
494 std::size_t padded_gates = 1;
495 while (padded_gates < used_gates) {
496 if (!checked_mul_size(padded_gates, 2, padded_gates)) {
497 return unexpected_error(ErrorCode::Overflow, "sum_circuit_gate_count:padded_gates");
498 }
499 }
500 std::vector<purify::UInt512> sorted_keys(public_keys.begin(), public_keys.end());
501 std::sort(sorted_keys.begin(), sorted_keys.end());
502 if (std::adjacent_find(sorted_keys.begin(), sorted_keys.end()) != sorted_keys.end()) {
503 return unexpected_error(ErrorCode::BindingMismatch, "sum_circuit_gate_count:duplicate_host");
504 }
505 for (const auto& public_key : public_keys) {
506 PURIFY_RETURN_IF_ERROR(purify::unpack_public(public_key), "sum_circuit_gate_count:public_key");
507 }
508 return padded_gates;
509}
510
511Status validate_sum_expression(const Expr& expr, std::size_t member_gates) {
512 for (const auto& [symbol, scalar] : expr.linear()) {
513 (void)scalar;
514 if (symbol.kind == SymbolKind::Commitment || symbol.kind == SymbolKind::Witness) {
515 return unexpected_error(ErrorCode::UnsupportedSymbol, "validate_sum_expression:symbol_kind");
516 }
517 if (symbol.index >= member_gates) {
518 return unexpected_error(ErrorCode::IndexOutOfRange, "validate_sum_expression:gate_index");
519 }
520 }
521 return {};
522}
523
524Status append_sum_expression(purify::NativeBulletproofCircuit& circuit, const Expr& expr,
525 std::size_t gate_offset, std::size_t member_gates,
526 std::size_t constraint_index) {
527 PURIFY_RETURN_IF_ERROR(validate_sum_expression(expr, member_gates), "append_sum_expression:shape");
528 for (const auto& [symbol, scalar] : expr.linear()) {
529 const std::size_t gate_index = gate_offset + symbol.index;
530 switch (symbol.kind) {
531 case SymbolKind::Left:
532 circuit.add_left_term(gate_index, constraint_index, scalar);
533 break;
534 case SymbolKind::Right:
535 circuit.add_right_term(gate_index, constraint_index, scalar);
536 break;
537 case SymbolKind::Output:
538 circuit.add_output_term(gate_index, constraint_index, scalar);
539 break;
540 case SymbolKind::Commitment:
541 case SymbolKind::Witness:
542 default:
543 return unexpected_error(ErrorCode::UnsupportedSymbol, "append_sum_expression:symbol_kind");
544 }
545 }
546 return {};
547}
548
549struct FlattenedRowFamily {
550 std::vector<purify_bulletproof_row_view> views;
551 std::vector<std::size_t> indices;
552 Bytes scalars32;
553};
554
555template <typename RowEntriesFn>
556FlattenedRowFamily flatten_row_family_generic(std::size_t row_count, const RowEntriesFn& row_entries,
557 std::size_t constraint_offset) {
558 FlattenedRowFamily flat;
559 std::vector<std::size_t> offsets;
560 std::vector<std::size_t> counts;
561 offsets.reserve(row_count);
562 counts.reserve(row_count);
563 flat.views.resize(row_count);
564
565 std::size_t total_entries = 0;
566 for (std::size_t i = 0; i < row_count; ++i) {
567 std::span<const purify::NativeBulletproofCircuitTerm> entries = row_entries(i);
568 total_entries += std::count_if(entries.begin(), entries.end(),
569 [&](const auto& entry) { return entry.idx >= constraint_offset; });
570 }
571 flat.indices.reserve(total_entries);
572 best_effort_reserve_mul(flat.scalars32, total_entries, 32);
573
574 for (std::size_t i = 0; i < row_count; ++i) {
575 std::span<const purify::NativeBulletproofCircuitTerm> entries = row_entries(i);
576 std::size_t kept = 0;
577 offsets.push_back(flat.indices.size());
578 for (const auto& entry : entries) {
579 if (entry.idx < constraint_offset) {
580 continue;
581 }
582 ++kept;
583 flat.indices.push_back(entry.idx - constraint_offset);
584 auto bytes = entry.scalar.to_bytes_be();
585 flat.scalars32.insert(flat.scalars32.end(), bytes.begin(), bytes.end());
586 }
587 counts.push_back(kept);
588 }
589
590 const std::size_t* indices_base = flat.indices.empty() ? nullptr : flat.indices.data();
591 const unsigned char* scalars_base = flat.scalars32.empty() ? nullptr : flat.scalars32.data();
592 for (std::size_t i = 0; i < row_count; ++i) {
593 const std::size_t count = counts[i];
594 const std::size_t start = offsets[i];
595 flat.views[i].size = count;
596 flat.views[i].indices = count == 0 ? nullptr : indices_base + start;
597 flat.views[i].scalars32 = count == 0 ? nullptr : scalars_base + start * 32;
598 }
599 return flat;
600}
601
602struct FlattenedCircuitView {
603 FlattenedRowFamily wl;
604 FlattenedRowFamily wr;
605 FlattenedRowFamily wo;
606 FlattenedRowFamily wv;
607 Bytes constants32;
609};
610
611FlattenedCircuitView flatten_circuit_view(const purify::NativeBulletproofCircuit& circuit) {
612 FlattenedCircuitView flat;
613 const std::size_t implicit_bit_constraints = 2 * circuit.n_bits;
614 assert(circuit.c.size() >= implicit_bit_constraints && "native circuit must contain all implicit bit constraints");
615 flat.wl = flatten_row_family_generic(circuit.wl.size(),
616 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wl[i].entries); },
617 implicit_bit_constraints);
618 flat.wr = flatten_row_family_generic(circuit.wr.size(),
619 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wr[i].entries); },
620 implicit_bit_constraints);
621 flat.wo = flatten_row_family_generic(circuit.wo.size(),
622 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wo[i].entries); },
623 implicit_bit_constraints);
624 flat.wv = flatten_row_family_generic(circuit.wv.size(),
625 [&](std::size_t i) { return std::span<const purify::NativeBulletproofCircuitTerm>(circuit.wv[i].entries); },
626 implicit_bit_constraints);
627 std::vector<FieldElement> explicit_constants(circuit.c.begin() + static_cast<std::ptrdiff_t>(implicit_bit_constraints), circuit.c.end());
628 flat.constants32 = flatten_scalars32(explicit_constants);
629 flat.view.n_gates = circuit.n_gates;
630 flat.view.n_commits = circuit.n_commitments;
631 flat.view.n_bits = circuit.n_bits;
632 flat.view.n_constraints = explicit_constants.size();
633 flat.view.wl = flat.wl.views.data();
634 flat.view.wr = flat.wr.views.data();
635 flat.view.wo = flat.wo.views.data();
636 flat.view.wv = flat.wv.views.data();
637 flat.view.c32 = flat.constants32.empty() ? nullptr : flat.constants32.data();
638 return flat;
639}
640
641FlattenedCircuitView flatten_circuit_view(const PackedCircuit& circuit) {
642 FlattenedCircuitView flat;
643 const std::size_t implicit_bit_constraints = 2 * circuit.n_bits();
644 assert(circuit.constraint_count() >= implicit_bit_constraints
645 && "packed circuit must contain all implicit bit constraints");
646 flat.wl = flatten_row_family_generic(circuit.n_gates(),
647 [&](std::size_t i) { return circuit.left_row(i).entries_view(); },
648 implicit_bit_constraints);
649 flat.wr = flatten_row_family_generic(circuit.n_gates(),
650 [&](std::size_t i) { return circuit.right_row(i).entries_view(); },
651 implicit_bit_constraints);
652 flat.wo = flatten_row_family_generic(circuit.n_gates(),
653 [&](std::size_t i) { return circuit.output_row(i).entries_view(); },
654 implicit_bit_constraints);
655 flat.wv = flatten_row_family_generic(circuit.n_commitments(),
656 [&](std::size_t i) { return circuit.commitment_row(i).entries_view(); },
657 implicit_bit_constraints);
658 std::vector<FieldElement> explicit_constants;
659 std::span<const FieldElement> constants = circuit.constants();
660 if (constants.size() > implicit_bit_constraints) {
661 const FieldElement* constants_begin = constants.data();
662 explicit_constants.assign(constants_begin + static_cast<std::ptrdiff_t>(implicit_bit_constraints),
663 constants_begin + static_cast<std::ptrdiff_t>(constants.size()));
664 }
665 flat.constants32 = flatten_scalars32(explicit_constants);
666 flat.view.n_gates = circuit.n_gates();
667 flat.view.n_commits = circuit.n_commitments();
668 flat.view.n_bits = circuit.n_bits();
669 flat.view.n_constraints = explicit_constants.size();
670 flat.view.wl = flat.wl.views.data();
671 flat.view.wr = flat.wr.views.data();
672 flat.view.wo = flat.wo.views.data();
673 flat.view.wv = flat.wv.views.data();
674 flat.view.c32 = flat.constants32.empty() ? nullptr : flat.constants32.data();
675 return flat;
676}
677
678struct FlattenedAssignmentView {
679 Bytes left32;
680 Bytes right32;
681 Bytes output32;
682 Bytes commitments32;
684};
685
686FlattenedAssignmentView flatten_assignment_view(const purify::BulletproofAssignmentData& assignment) {
687 FlattenedAssignmentView flat;
688 flat.left32 = flatten_scalars32(assignment.left);
689 flat.right32 = flatten_scalars32(assignment.right);
690 flat.output32 = flatten_scalars32(assignment.output);
691 flat.commitments32 = flatten_scalars32(assignment.commitments);
692 flat.view.n_gates = assignment.left.size();
693 flat.view.n_commits = assignment.commitments.size();
694 flat.view.al32 = flat.left32.empty() ? nullptr : flat.left32.data();
695 flat.view.ar32 = flat.right32.empty() ? nullptr : flat.right32.data();
696 flat.view.ao32 = flat.output32.empty() ? nullptr : flat.output32.data();
697 flat.view.v32 = flat.commitments32.empty() ? nullptr : flat.commitments32.data();
698 return flat;
699}
700
701std::size_t circuit_n_gates(const purify::NativeBulletproofCircuit& circuit) {
702 return circuit.n_gates;
703}
704
705std::size_t circuit_n_gates(const PackedCircuit& circuit) {
706 return circuit.n_gates();
707}
708
710 return circuit.n_commitments;
711}
712
713std::size_t circuit_n_commitments(const PackedCircuit& circuit) {
714 return circuit.n_commitments();
715}
716
717struct ResolvedBulletproofBackendResources {
718 purify_bulletproof_backend_resources* resources = nullptr;
719};
720
721ResolvedBulletproofBackendResources resolve_bulletproof_backend_resources(
722 std::size_t n_gates,
723 purify_secp_context* secp_context,
725 ResolvedBulletproofBackendResources out;
726
727 if (cache != nullptr) {
728 out.resources = cache->get_or_create(n_gates, secp_context);
729 }
730 return out;
731}
732
733template <typename CircuitLike>
734Result<ExperimentalBulletproofProof> prove_experimental_circuit_impl(
735 const CircuitLike& circuit,
736 const BulletproofAssignmentData& assignment,
737 const BulletproofScalarBytes& nonce,
738 const BulletproofGeneratorBytes& value_generator,
739 purify_secp_context* secp_context,
740 std::span<const unsigned char> statement_binding,
741 std::span<const BulletproofScalarBytes> blinds,
742 ExperimentalBulletproofBackendCache* backend_cache,
743 bool require_assignment_validation,
744 const char* shape_context,
745 const char* gates_context,
746 const char* commitments_context,
747 const char* assignment_shape_context,
748 const char* assignment_invalid_context,
749 const char* proof_size_context,
750 const char* bridge_context) {
751 PURIFY_RETURN_IF_ERROR(require_secp_context(secp_context, "prove_experimental_circuit:secp_context"),
752 "prove_experimental_circuit:secp_context");
753 ExperimentalBulletproofProof out;
754 if (!circuit.has_valid_shape()) {
755 return unexpected_error(ErrorCode::InvalidDimensions, shape_context);
756 }
757 if (!is_power_of_two_size(circuit_n_gates(circuit))) {
758 return unexpected_error(ErrorCode::InvalidDimensions, gates_context);
759 }
760 if (circuit_n_commitments(circuit) == 0) {
761 return unexpected_error(ErrorCode::InvalidDimensions, commitments_context);
762 }
763 if (assignment.left.size() != circuit_n_gates(circuit)
764 || assignment.right.size() != circuit_n_gates(circuit)
765 || assignment.output.size() != circuit_n_gates(circuit)
766 || assignment.commitments.size() != circuit_n_commitments(circuit)) {
767 return unexpected_error(ErrorCode::SizeMismatch, assignment_shape_context);
768 }
769 if (!blinds.empty() && blinds.size() != circuit_n_commitments(circuit)) {
770 return unexpected_error(ErrorCode::SizeMismatch, "prove_experimental_circuit:blinds_size");
771 }
772 if (require_assignment_validation && !circuit.evaluate(assignment)) {
773 return unexpected_error(ErrorCode::EquationMismatch, assignment_invalid_context);
774 }
775
776 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
777 FlattenedAssignmentView flat_assignment = flatten_assignment_view(assignment);
778 PURIFY_ASSIGN_OR_RETURN(const auto& binding_digest, circuit_binding_digest(circuit, statement_binding),
779 "prove_experimental_circuit_impl:binding_digest");
780 Bytes proof_bytes(std::max<std::size_t>(purify_bulletproof_required_proof_size(circuit_n_gates(circuit)), 4096), 0);
781 std::size_t proof_len = proof_bytes.size();
782 out.commitments.resize(circuit_n_commitments(circuit));
783 const unsigned char* blind_ptr = blinds.empty() ? nullptr : reinterpret_cast<const unsigned char*>(blinds.data());
784 ResolvedBulletproofBackendResources resolved =
785 resolve_bulletproof_backend_resources(circuit_n_gates(circuit), secp_context, backend_cache);
786 purify_bulletproof_backend_resources* resources = resolved.resources;
787
788 if (proof_len == 0) {
789 return unexpected_error(ErrorCode::UnexpectedSize, proof_size_context);
790 }
791 const int ok =
792 resources != nullptr
793 ? (require_assignment_validation
795 resources, &flat_circuit.view, &flat_assignment.view, blind_ptr,
796 value_generator.data(), nonce.data(),
797 binding_digest.data(), binding_digest.size(),
798 reinterpret_cast<unsigned char*>(out.commitments.data()), proof_bytes.data(), &proof_len)
800 resources, &flat_circuit.view, &flat_assignment.view, blind_ptr,
801 value_generator.data(), nonce.data(),
802 binding_digest.data(), binding_digest.size(),
803 reinterpret_cast<unsigned char*>(out.commitments.data()), proof_bytes.data(), &proof_len))
804 : (require_assignment_validation
806 secp_context, &flat_circuit.view, &flat_assignment.view, blind_ptr,
807 value_generator.data(), nonce.data(),
808 binding_digest.data(), binding_digest.size(),
809 reinterpret_cast<unsigned char*>(out.commitments.data()), proof_bytes.data(), &proof_len)
811 secp_context, &flat_circuit.view, &flat_assignment.view, blind_ptr,
812 value_generator.data(), nonce.data(),
813 binding_digest.data(), binding_digest.size(),
814 reinterpret_cast<unsigned char*>(out.commitments.data()), proof_bytes.data(), &proof_len));
815 if (!ok) {
816 return unexpected_error(ErrorCode::BackendRejectedInput, bridge_context);
817 }
818
819 proof_bytes.resize(proof_len);
820 out.proof = std::move(proof_bytes);
821 return out;
822}
823
824Result<FieldElement> evaluate_expr_with_assignment(const Expr& expr,
825 const purify::BulletproofAssignmentData& assignment) {
826 FieldElement out = expr.constant();
827 for (const auto& term : expr.linear()) {
828 std::size_t index = term.first.index;
829 switch (term.first.kind) {
830 case SymbolKind::Left:
831 if (index >= assignment.left.size()) {
833 "evaluate_expr_with_assignment:left_index");
834 }
835 out = out + (assignment.left[index] * term.second);
836 break;
837 case SymbolKind::Right:
838 if (index >= assignment.right.size()) {
840 "evaluate_expr_with_assignment:right_index");
841 }
842 out = out + (assignment.right[index] * term.second);
843 break;
844 case SymbolKind::Output:
845 if (index >= assignment.output.size()) {
847 "evaluate_expr_with_assignment:output_index");
848 }
849 out = out + (assignment.output[index] * term.second);
850 break;
851 case SymbolKind::Commitment:
852 if (index >= assignment.commitments.size()) {
854 "evaluate_expr_with_assignment:commitment_index");
855 }
856 out = out + (assignment.commitments[index] * term.second);
857 break;
858 case SymbolKind::Witness:
860 "evaluate_expr_with_assignment:witness_symbol");
861 }
862 }
863 return out;
864}
865
866} // namespace
867
868namespace purify {
869
871 if (left.size() != right.size() || left.size() != output.size()) {
872 return unexpected_error(ErrorCode::SizeMismatch, "BulletproofAssignmentData::serialize:column_sizes");
873 }
874 if (!size_fits_u32(commitments.size())) {
875 return unexpected_error(ErrorCode::UnexpectedSize, "BulletproofAssignmentData::serialize:commitment_count");
876 }
877 if (!size_fits_u64(left.size())) {
878 return unexpected_error(ErrorCode::UnexpectedSize, "BulletproofAssignmentData::serialize:row_count");
879 }
880
881 std::size_t scalar_count = 0;
882 std::size_t serialized_size = 0;
883 if (!checked_mul_size(left.size(), 3, scalar_count)
884 || !checked_add_size(scalar_count, commitments.size(), scalar_count)
885 || !checked_mul_size(scalar_count, 33, serialized_size)
886 || !checked_add_size(16, serialized_size, serialized_size)) {
887 return unexpected_error(ErrorCode::Overflow, "BulletproofAssignmentData::serialize:reserve");
888 }
889
890 Bytes out;
891 out.reserve(serialized_size);
892 auto append_u32_le = [&](std::uint32_t value) {
893 for (int i = 0; i < 4; ++i) {
894 out.push_back(static_cast<unsigned char>((value >> (8 * i)) & 0xffU));
895 }
896 };
897 auto append_u64_le = [&](std::uint64_t value) {
898 for (int i = 0; i < 8; ++i) {
899 out.push_back(static_cast<unsigned char>((value >> (8 * i)) & 0xffU));
900 }
901 };
902 auto write_column = [&](std::span<const FieldElement> column) {
903 for (const FieldElement& value : column) {
904 out.push_back(static_cast<unsigned char>(0x20));
905 std::array<unsigned char, 32> bytes = value.to_bytes_le();
906 out.insert(out.end(), bytes.begin(), bytes.end());
907 }
908 };
909
910 append_u32_le(1);
911 append_u32_le(static_cast<std::uint32_t>(commitments.size()));
912 append_u64_le(static_cast<std::uint64_t>(left.size()));
913 write_column(left);
914 write_column(right);
915 write_column(output);
916 write_column(commitments);
917 return out;
918}
919
920void NativeBulletproofCircuitRow::add(std::size_t idx, const FieldElement& scalar) {
921 if (scalar.is_zero()) {
922 return;
923 }
924 entries.push_back({idx, scalar});
925}
926
927NativeBulletproofCircuit::NativeBulletproofCircuit(std::size_t gates, std::size_t commitments, std::size_t bits)
928 : n_gates(gates), n_commitments(commitments), n_bits(bits), wl(gates), wr(gates), wo(gates), wv(commitments) {}
929
930void NativeBulletproofCircuit::resize(std::size_t gates, std::size_t commitments, std::size_t bits) {
931 n_gates = gates;
932 n_commitments = commitments;
933 n_bits = bits;
934 wl.assign(gates, {});
935 wr.assign(gates, {});
936 wo.assign(gates, {});
937 wv.assign(commitments, {});
938 c.clear();
939}
940
942 if (wl.size() != n_gates
943 || wr.size() != n_gates
944 || wo.size() != n_gates
945 || wv.size() != n_commitments) {
946 return false;
947 }
948 const auto rows_are_valid = [&](const std::vector<NativeBulletproofCircuitRow>& rows) {
949 for (const NativeBulletproofCircuitRow& row : rows) {
950 for (const NativeBulletproofCircuitTerm& entry : row.entries) {
951 if (entry.idx >= c.size()) {
952 return false;
953 }
954 }
955 }
956 return true;
957 };
958 return rows_are_valid(wl)
959 && rows_are_valid(wr)
960 && rows_are_valid(wo)
961 && rows_are_valid(wv);
962}
963
965 c.push_back(constant);
966 return c.size() - 1;
967}
968
969void NativeBulletproofCircuit::add_left_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar) {
970 add_row_term(wl, n_gates, gate_idx, constraint_idx, scalar);
971}
972
973void NativeBulletproofCircuit::add_right_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar) {
974 add_row_term(wr, n_gates, gate_idx, constraint_idx, scalar);
975}
976
977void NativeBulletproofCircuit::add_output_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement& scalar) {
978 add_row_term(wo, n_gates, gate_idx, constraint_idx, scalar);
979}
980
981void NativeBulletproofCircuit::add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx, const FieldElement& scalar) {
982 add_row_term(wv, n_commitments, commitment_idx, constraint_idx, scalar.negate());
983}
984
986 if (!has_valid_shape()) {
987 return false;
988 }
989 if (assignment.left.size() != n_gates || assignment.right.size() != n_gates || assignment.output.size() != n_gates) {
990 return false;
991 }
992 if (assignment.commitments.size() != n_commitments) {
993 return false;
994 }
995
996 for (std::size_t i = 0; i < n_gates; ++i) {
997 if (assignment.left[i] * assignment.right[i] != assignment.output[i]) {
998 return false;
999 }
1000 }
1001
1002 std::vector<FieldElement> acc(c.size(), FieldElement::zero());
1003 WipeOnDestruction acc_wiper(acc);
1004 auto accumulate = [&](const std::vector<NativeBulletproofCircuitRow>& rows,
1005 std::span<const FieldElement> values,
1006 bool negate_values = false) {
1007 if (rows.size() != values.size()) {
1008 return false;
1009 }
1010 for (std::size_t i = 0; i < rows.size(); ++i) {
1011 if (negate_values) {
1012 FieldElement negated = values[i].negate();
1013 WipeOnDestruction negated_wiper(negated);
1014 for (const NativeBulletproofCircuitTerm& entry : rows[i].entries) {
1015 if (entry.idx >= acc.size()) {
1016 return false;
1017 }
1018 acc[entry.idx] = acc[entry.idx] + entry.scalar * negated;
1019 }
1020 continue;
1021 }
1022 for (const NativeBulletproofCircuitTerm& entry : rows[i].entries) {
1023 if (entry.idx >= acc.size()) {
1024 return false;
1025 }
1026 acc[entry.idx] = acc[entry.idx] + entry.scalar * values[i];
1027 }
1028 }
1029 return true;
1030 };
1031 if (!accumulate(wl, assignment.left) || !accumulate(wr, assignment.right) || !accumulate(wo, assignment.output)) {
1032 return false;
1033 }
1034 if (!accumulate(wv, assignment.commitments, true)) {
1035 return false;
1036 }
1037
1038 for (std::size_t i = 0; i < c.size(); ++i) {
1039 if (acc[i] != c[i]) {
1040 return false;
1041 }
1042 }
1043 return true;
1044}
1045
1046void NativeBulletproofCircuit::add_row_term(std::vector<NativeBulletproofCircuitRow>& rows, std::size_t expected_size,
1047 std::size_t row_idx, std::size_t constraint_idx, const FieldElement& scalar) {
1048 (void)expected_size;
1049 assert(rows.size() == expected_size && "NativeBulletproofCircuit rows must be initialized before adding terms");
1050 assert(row_idx < rows.size() && "NativeBulletproofCircuit row index out of range");
1051 rows[row_idx].add(constraint_idx, scalar);
1052}
1053
1054void NativeBulletproofCircuit::PackedWithSlack::PackedStorageDeleter::operator()(std::byte* storage) const noexcept {
1055 if (storage != nullptr) {
1056 ::operator delete(storage, std::align_val_t(NativeBulletproofCircuit::PackedWithSlack::kPackedStorageAlignment));
1057 }
1058}
1059
1060std::byte* NativeBulletproofCircuit::PackedWithSlack::allocate_storage(std::size_t bytes) {
1061 if (bytes == 0) {
1062 return nullptr;
1063 }
1064 return static_cast<std::byte*>(::operator new(bytes, std::align_val_t(kPackedStorageAlignment)));
1065}
1066
1068 : n_gates_(other.n_gates_), n_commitments_(other.n_commitments_), n_bits_(other.n_bits_),
1069 constraint_size_(other.constraint_size_), constraint_base_size_(other.constraint_base_size_),
1070 constraint_capacity_(other.constraint_capacity_), term_capacity_(other.term_capacity_),
1071 term_bytes_offset_(other.term_bytes_offset_), constant_bytes_offset_(other.constant_bytes_offset_),
1072 storage_bytes_(other.storage_bytes_) {
1073 assert((other.storage_ != nullptr) == (other.storage_bytes_ != 0)
1074 && "PackedWithSlack source storage must match its byte count");
1075 if (storage_bytes_ != 0) {
1076 storage_.reset(allocate_storage(storage_bytes_));
1077 start_storage_lifetimes();
1078 std::memcpy(storage_.get(), other.storage_.get(), storage_bytes_);
1079 }
1080}
1081
1083 : n_gates_(other.n_gates_), n_commitments_(other.n_commitments_), n_bits_(other.n_bits_),
1084 constraint_size_(other.constraint_size_), constraint_base_size_(other.constraint_base_size_),
1085 constraint_capacity_(other.constraint_capacity_), term_capacity_(other.term_capacity_),
1086 term_bytes_offset_(other.term_bytes_offset_), constant_bytes_offset_(other.constant_bytes_offset_),
1087 storage_bytes_(other.storage_bytes_), storage_(std::move(other.storage_)) {
1088 other.reset_to_empty();
1089}
1090
1093 if (this == &other) {
1094 return *this;
1095 }
1096 PackedWithSlack copy(other);
1097 *this = std::move(copy);
1098 return *this;
1099}
1100
1103 if (this == &other) {
1104 return *this;
1105 }
1106 n_gates_ = other.n_gates_;
1107 n_commitments_ = other.n_commitments_;
1108 n_bits_ = other.n_bits_;
1109 constraint_size_ = other.constraint_size_;
1110 constraint_base_size_ = other.constraint_base_size_;
1111 constraint_capacity_ = other.constraint_capacity_;
1112 term_capacity_ = other.term_capacity_;
1113 term_bytes_offset_ = other.term_bytes_offset_;
1114 constant_bytes_offset_ = other.constant_bytes_offset_;
1115 storage_bytes_ = other.storage_bytes_;
1116 storage_ = std::move(other.storage_);
1117 other.reset_to_empty();
1118 return *this;
1119}
1120
1121bool NativeBulletproofCircuit::PackedWithSlack::compute_storage_layout(std::size_t row_count, std::size_t term_capacity,
1122 std::size_t constraint_capacity,
1123 std::size_t& term_bytes_offset,
1124 std::size_t& constant_bytes_offset,
1125 std::size_t& storage_bytes) noexcept {
1126 std::size_t row_headers_bytes = 0;
1127 if (!checked_mul_size(row_count, sizeof(PackedRowHeader), row_headers_bytes)
1128 || !checked_align_up(row_headers_bytes, alignof(NativeBulletproofCircuitTerm), term_bytes_offset)) {
1129 return false;
1130 }
1131 std::size_t terms_bytes = 0;
1132 if (!checked_mul_size(term_capacity, sizeof(NativeBulletproofCircuitTerm), terms_bytes)) {
1133 return false;
1134 }
1135 std::size_t term_region_end = 0;
1136 if (!checked_add_size(term_bytes_offset, terms_bytes, term_region_end)
1137 || !checked_align_up(term_region_end, alignof(FieldElement), constant_bytes_offset)) {
1138 return false;
1139 }
1140 std::size_t constants_bytes = 0;
1141 if (!checked_mul_size(constraint_capacity, sizeof(FieldElement), constants_bytes)) {
1142 return false;
1143 }
1144 return checked_add_size(constant_bytes_offset, constants_bytes, storage_bytes);
1145}
1146
1147void NativeBulletproofCircuit::PackedWithSlack::reset_to_empty() noexcept {
1148 storage_.reset();
1149 n_gates_ = 0;
1150 n_commitments_ = 0;
1151 n_bits_ = 0;
1152 constraint_size_ = 0;
1153 constraint_base_size_ = 0;
1154 constraint_capacity_ = 0;
1155 term_capacity_ = 0;
1156 term_bytes_offset_ = 0;
1157 constant_bytes_offset_ = 0;
1158 storage_bytes_ = 0;
1159}
1160
1162 if (constraint_base_size_ > constraint_size_ || constraint_size_ > constraint_capacity_) {
1163 return false;
1164 }
1165 std::size_t row_count = 0;
1166 if (!packed_row_count(n_gates_, n_commitments_, row_count)) {
1167 return false;
1168 }
1169 std::size_t expected_term_offset = 0;
1170 std::size_t expected_constant_offset = 0;
1171 std::size_t expected_storage_bytes = 0;
1172 if (!compute_storage_layout(row_count, term_capacity_, constraint_capacity_,
1173 expected_term_offset, expected_constant_offset, expected_storage_bytes)) {
1174 return false;
1175 }
1176 if (term_bytes_offset_ != expected_term_offset || constant_bytes_offset_ != expected_constant_offset
1177 || storage_bytes_ != expected_storage_bytes) {
1178 return false;
1179 }
1180 if ((storage_ == nullptr) != (storage_bytes_ == 0)) {
1181 return false;
1182 }
1183 if (storage_bytes_ == 0) {
1184 return row_count == 0 && term_capacity_ == 0 && constraint_capacity_ == 0;
1185 }
1186
1187 const PackedRowHeader* headers =
1188 std::launder(reinterpret_cast<const PackedRowHeader*>(raw_storage_bytes()));
1189 std::size_t term_cursor = 0;
1190 for (std::size_t i = 0; i < row_count; ++i) {
1191 const PackedRowHeader& header = headers[i];
1192 if (header.base_size > header.size || header.size > header.capacity) {
1193 return false;
1194 }
1195 if (header.offset != term_cursor) {
1196 return false;
1197 }
1198 if (term_cursor > term_capacity_ || header.capacity > term_capacity_ - term_cursor) {
1199 return false;
1200 }
1201 const NativeBulletproofCircuitTerm* terms = term_data();
1202 for (std::size_t j = 0; j < header.size; ++j) {
1203 if (terms[header.offset + j].idx >= constraint_size_) {
1204 return false;
1205 }
1206 }
1207 term_cursor += header.capacity;
1208 }
1209 return term_cursor == term_capacity_;
1210}
1211
1213 constraint_size_ = constraint_base_size_;
1214 std::size_t row_count = 0;
1215 [[maybe_unused]] const bool ok = packed_row_count(n_gates_, n_commitments_, row_count);
1216 assert(ok && "PackedWithSlack row count should fit in size_t");
1217 PackedRowHeader* headers = row_count == 0 ? nullptr
1218 : std::launder(reinterpret_cast<PackedRowHeader*>(raw_storage_bytes()));
1219 for (std::size_t i = 0; i < row_count; ++i) {
1220 PackedRowHeader& header = headers[i];
1221 header.size = header.base_size;
1222 }
1223}
1224
1225NativeBulletproofCircuit::PackedWithSlack::PackedRowHeader&
1226NativeBulletproofCircuit::PackedWithSlack::row_header(RowFamily family, std::size_t idx) noexcept {
1227 PackedRowHeader* headers = std::launder(reinterpret_cast<PackedRowHeader*>(raw_storage_bytes()));
1228 std::size_t base = 0;
1229 switch (family) {
1230 case RowFamily::Left:
1231 base = 0;
1232 break;
1233 case RowFamily::Right:
1234 base = n_gates_;
1235 break;
1236 case RowFamily::Output:
1237 base = 2 * n_gates_;
1238 break;
1239 case RowFamily::Commitment:
1240 base = 3 * n_gates_;
1241 break;
1242 }
1243 return headers[base + idx];
1244}
1245
1246const NativeBulletproofCircuit::PackedWithSlack::PackedRowHeader&
1247NativeBulletproofCircuit::PackedWithSlack::row_header(RowFamily family, std::size_t idx) const noexcept {
1248 const PackedRowHeader* headers = std::launder(reinterpret_cast<const PackedRowHeader*>(raw_storage_bytes()));
1249 std::size_t base = 0;
1250 switch (family) {
1251 case RowFamily::Left:
1252 base = 0;
1253 break;
1254 case RowFamily::Right:
1255 base = n_gates_;
1256 break;
1257 case RowFamily::Output:
1258 base = 2 * n_gates_;
1259 break;
1260 case RowFamily::Commitment:
1261 base = 3 * n_gates_;
1262 break;
1263 }
1264 return headers[base + idx];
1265}
1266
1267NativeBulletproofCircuitTerm* NativeBulletproofCircuit::PackedWithSlack::term_data() noexcept {
1268 if (term_capacity_ == 0) {
1269 return nullptr;
1270 }
1271 return std::launder(reinterpret_cast<NativeBulletproofCircuitTerm*>(raw_storage_bytes() + term_bytes_offset_));
1272}
1273
1274const NativeBulletproofCircuitTerm* NativeBulletproofCircuit::PackedWithSlack::term_data() const noexcept {
1275 if (term_capacity_ == 0) {
1276 return nullptr;
1277 }
1278 return std::launder(reinterpret_cast<const NativeBulletproofCircuitTerm*>(raw_storage_bytes() + term_bytes_offset_));
1279}
1280
1281FieldElement* NativeBulletproofCircuit::PackedWithSlack::constant_data() noexcept {
1282 if (constraint_capacity_ == 0) {
1283 return nullptr;
1284 }
1285 return std::launder(reinterpret_cast<FieldElement*>(raw_storage_bytes() + constant_bytes_offset_));
1286}
1287
1288const FieldElement* NativeBulletproofCircuit::PackedWithSlack::constant_data() const noexcept {
1289 if (constraint_capacity_ == 0) {
1290 return nullptr;
1291 }
1292 return std::launder(reinterpret_cast<const FieldElement*>(raw_storage_bytes() + constant_bytes_offset_));
1293}
1294
1295unsigned char* NativeBulletproofCircuit::PackedWithSlack::raw_storage_bytes() noexcept {
1296 return reinterpret_cast<unsigned char*>(storage_.get());
1297}
1298
1299const unsigned char* NativeBulletproofCircuit::PackedWithSlack::raw_storage_bytes() const noexcept {
1300 return reinterpret_cast<const unsigned char*>(storage_.get());
1301}
1302
1303void NativeBulletproofCircuit::PackedWithSlack::start_storage_lifetimes() noexcept {
1304 if (storage_ == nullptr) {
1305 return;
1306 }
1307 std::size_t row_count = 0;
1308 [[maybe_unused]] const bool ok = packed_row_count(n_gates_, n_commitments_, row_count);
1309 assert(ok && "PackedWithSlack row count should fit in size_t");
1310 if (row_count != 0) {
1311 PackedRowHeader* headers = reinterpret_cast<PackedRowHeader*>(raw_storage_bytes());
1312 std::uninitialized_value_construct_n(headers, row_count);
1313 }
1314 if (term_capacity_ != 0) {
1315 NativeBulletproofCircuitTerm* terms =
1316 reinterpret_cast<NativeBulletproofCircuitTerm*>(raw_storage_bytes() + term_bytes_offset_);
1317 std::uninitialized_value_construct_n(terms, term_capacity_);
1318 }
1319 if (constraint_capacity_ != 0) {
1320 FieldElement* constants = reinterpret_cast<FieldElement*>(raw_storage_bytes() + constant_bytes_offset_);
1321 std::uninitialized_value_construct_n(constants, constraint_capacity_);
1322 }
1323}
1324
1325NativeBulletproofCircuitRow::PackedWithSlack
1326NativeBulletproofCircuit::PackedWithSlack::row_view(const PackedRowHeader& header) const noexcept {
1327 const NativeBulletproofCircuitTerm* terms = term_data();
1328 return {header.capacity == 0 ? nullptr : terms + header.offset, header.size, header.capacity};
1329}
1330
1332 assert(constraint_size_ < constraint_capacity_ && "PackedWithSlack constraint capacity exceeded");
1333 FieldElement* constants = constant_data();
1334 constants[constraint_size_] = constant;
1335 ++constraint_size_;
1336 return constraint_size_ - 1;
1337}
1338
1339void NativeBulletproofCircuit::PackedWithSlack::add_row_term(RowFamily family, std::size_t expected_size,
1340 std::size_t row_idx, std::size_t constraint_idx,
1341 const FieldElement& scalar) {
1342 (void)expected_size;
1343 if (scalar.is_zero()) {
1344 return;
1345 }
1346 assert(constraint_idx < constraint_size_ && "PackedWithSlack constraint index out of range");
1347 assert(((family == RowFamily::Commitment) ? n_commitments_ : n_gates_) == expected_size
1348 && "PackedWithSlack expected row family size mismatch");
1349 assert(row_idx < expected_size && "PackedWithSlack row index out of range");
1350 PackedRowHeader& header = row_header(family, row_idx);
1351 assert(header.size < header.capacity && "PackedWithSlack row capacity exceeded");
1352 term_data()[header.offset + header.size] = {constraint_idx, scalar};
1353 ++header.size;
1354}
1355
1356void NativeBulletproofCircuit::PackedWithSlack::add_left_term(std::size_t gate_idx, std::size_t constraint_idx,
1357 const FieldElement& scalar) {
1358 add_row_term(RowFamily::Left, n_gates_, gate_idx, constraint_idx, scalar);
1359}
1360
1361void NativeBulletproofCircuit::PackedWithSlack::add_right_term(std::size_t gate_idx, std::size_t constraint_idx,
1362 const FieldElement& scalar) {
1363 add_row_term(RowFamily::Right, n_gates_, gate_idx, constraint_idx, scalar);
1364}
1365
1366void NativeBulletproofCircuit::PackedWithSlack::add_output_term(std::size_t gate_idx, std::size_t constraint_idx,
1367 const FieldElement& scalar) {
1368 add_row_term(RowFamily::Output, n_gates_, gate_idx, constraint_idx, scalar);
1369}
1370
1371void NativeBulletproofCircuit::PackedWithSlack::add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx,
1372 const FieldElement& scalar) {
1373 add_row_term(RowFamily::Commitment, n_commitments_, commitment_idx, constraint_idx, scalar.negate());
1374}
1375
1377NativeBulletproofCircuit::PackedWithSlack::left_row(std::size_t gate_idx) const noexcept {
1378 return row_view(row_header(RowFamily::Left, gate_idx));
1379}
1380
1382NativeBulletproofCircuit::PackedWithSlack::right_row(std::size_t gate_idx) const noexcept {
1383 return row_view(row_header(RowFamily::Right, gate_idx));
1384}
1385
1387NativeBulletproofCircuit::PackedWithSlack::output_row(std::size_t gate_idx) const noexcept {
1388 return row_view(row_header(RowFamily::Output, gate_idx));
1389}
1390
1392NativeBulletproofCircuit::PackedWithSlack::commitment_row(std::size_t commitment_idx) const noexcept {
1393 return row_view(row_header(RowFamily::Commitment, commitment_idx));
1394}
1395
1396std::span<const FieldElement> NativeBulletproofCircuit::PackedWithSlack::constants() const noexcept {
1397 return std::span<const FieldElement>(constant_data(), constraint_size_);
1398}
1399
1401 if (!has_valid_shape()) {
1402 return false;
1403 }
1404 if (assignment.left.size() != n_gates_ || assignment.right.size() != n_gates_ || assignment.output.size() != n_gates_) {
1405 return false;
1406 }
1407 if (assignment.commitments.size() != n_commitments_) {
1408 return false;
1409 }
1410 for (std::size_t i = 0; i < n_gates_; ++i) {
1411 if (assignment.left[i] * assignment.right[i] != assignment.output[i]) {
1412 return false;
1413 }
1414 }
1415
1416 std::vector<FieldElement> acc(constraint_size_, FieldElement::zero());
1417 const NativeBulletproofCircuitTerm* all_terms = term_data();
1418 auto accumulate = [&](RowFamily family, std::size_t row_count,
1419 std::span<const FieldElement> values,
1420 bool negate_values = false) {
1421 if (values.size() != row_count) {
1422 return false;
1423 }
1424 for (std::size_t i = 0; i < row_count; ++i) {
1425 const PackedRowHeader& header = row_header(family, i);
1426 FieldElement factor = negate_values ? values[i].negate() : values[i];
1427 if (header.size == 0) {
1428 continue;
1429 }
1430 const NativeBulletproofCircuitTerm* row_terms = all_terms + header.offset;
1431 for (std::size_t j = 0; j < header.size; ++j) {
1432 const NativeBulletproofCircuitTerm& entry = row_terms[j];
1433 if (entry.idx >= acc.size()) {
1434 return false;
1435 }
1436 acc[entry.idx] = acc[entry.idx] + (entry.scalar * factor);
1437 }
1438 }
1439 return true;
1440 };
1441 if (!accumulate(RowFamily::Left, n_gates_, assignment.left)
1442 || !accumulate(RowFamily::Right, n_gates_, assignment.right)
1443 || !accumulate(RowFamily::Output, n_gates_, assignment.output)
1444 || !accumulate(RowFamily::Commitment, n_commitments_, assignment.commitments, true)) {
1445 return false;
1446 }
1447 for (std::size_t i = 0; i < constraint_size_; ++i) {
1448 if (acc[i] != constant_data()[i]) {
1449 return false;
1450 }
1451 }
1452 return true;
1453}
1454
1456 if (!has_valid_shape()) {
1457 return unexpected_error(ErrorCode::InvalidDimensions, "NativeBulletproofCircuit::PackedWithSlack::unpack:shape");
1458 }
1459 NativeBulletproofCircuit out(n_gates_, n_commitments_, n_bits_);
1460 if (constraint_size_ != 0) {
1461 const FieldElement* constants = constant_data();
1462 out.c.assign(constants, constants + static_cast<std::ptrdiff_t>(constraint_size_));
1463 }
1464 const NativeBulletproofCircuitTerm* all_terms = term_data();
1465 auto unpack_family = [&](RowFamily family, std::vector<NativeBulletproofCircuitRow>& rows, std::size_t row_count) {
1466 for (std::size_t i = 0; i < row_count; ++i) {
1467 const PackedRowHeader& header = row_header(family, i);
1468 if (header.size == 0) {
1469 rows[i].entries.clear();
1470 continue;
1471 }
1472 rows[i].entries.assign(all_terms + header.offset,
1473 all_terms + header.offset + static_cast<std::ptrdiff_t>(header.size));
1474 }
1475 };
1476 unpack_family(RowFamily::Left, out.wl, n_gates_);
1477 unpack_family(RowFamily::Right, out.wr, n_gates_);
1478 unpack_family(RowFamily::Output, out.wo, n_gates_);
1479 unpack_family(RowFamily::Commitment, out.wv, n_commitments_);
1480 return out;
1481}
1482
1484 const NativeBulletproofCircuit& circuit,
1485 const PackedSlackPlan& slack) {
1486 if (!circuit.has_valid_shape()) {
1487 return unexpected_error(ErrorCode::InvalidDimensions, "NativeBulletproofCircuit::PackedWithSlack::from_circuit:shape");
1488 }
1489 auto validate_family_slack = [](const std::vector<std::size_t>& family_slack, std::size_t expected,
1490 const char* context) -> Status {
1491 if (!family_slack.empty() && family_slack.size() != expected) {
1493 }
1494 return {};
1495 };
1496 Status wl_status = validate_family_slack(slack.wl, circuit.n_gates,
1497 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wl");
1498 if (!wl_status.has_value()) {
1499 return unexpected_error(wl_status.error(), "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wl");
1500 }
1501 Status wr_status = validate_family_slack(slack.wr, circuit.n_gates,
1502 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wr");
1503 if (!wr_status.has_value()) {
1504 return unexpected_error(wr_status.error(), "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wr");
1505 }
1506 Status wo_status = validate_family_slack(slack.wo, circuit.n_gates,
1507 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wo");
1508 if (!wo_status.has_value()) {
1509 return unexpected_error(wo_status.error(), "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wo");
1510 }
1511 Status wv_status = validate_family_slack(slack.wv, circuit.n_commitments,
1512 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wv");
1513 if (!wv_status.has_value()) {
1514 return unexpected_error(wv_status.error(), "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wv");
1515 }
1516
1517 PackedWithSlack packed;
1518 packed.n_gates_ = circuit.n_gates;
1519 packed.n_commitments_ = circuit.n_commitments;
1520 packed.n_bits_ = circuit.n_bits;
1521 packed.constraint_size_ = circuit.c.size();
1522 packed.constraint_base_size_ = circuit.c.size();
1523 if (!checked_add_size(circuit.c.size(), slack.constraint_slack, packed.constraint_capacity_)) {
1524 return unexpected_error(ErrorCode::Overflow, "NativeBulletproofCircuit::PackedWithSlack::from_circuit:constraint_capacity");
1525 }
1526
1527 std::size_t row_count = 0;
1528 if (!packed_row_count(circuit.n_gates, circuit.n_commitments, row_count)) {
1529 return unexpected_error(ErrorCode::Overflow, "NativeBulletproofCircuit::PackedWithSlack::from_circuit:row_count");
1530 }
1531 std::size_t total_term_capacity = 0;
1532 auto sum_capacity = [&](const std::vector<NativeBulletproofCircuitRow>& rows,
1533 const std::vector<std::size_t>& family_slack) -> bool {
1534 for (std::size_t i = 0; i < rows.size(); ++i) {
1535 const std::size_t extra = family_slack.empty() ? 0 : family_slack[i];
1536 std::size_t row_capacity = 0;
1537 if (!checked_add_size(rows[i].entries.size(), extra, row_capacity)
1538 || !checked_add_size(total_term_capacity, row_capacity, total_term_capacity)) {
1539 return false;
1540 }
1541 }
1542 return true;
1543 };
1544 if (!sum_capacity(circuit.wl, slack.wl)
1545 || !sum_capacity(circuit.wr, slack.wr)
1546 || !sum_capacity(circuit.wo, slack.wo)
1547 || !sum_capacity(circuit.wv, slack.wv)) {
1548 return unexpected_error(ErrorCode::Overflow, "NativeBulletproofCircuit::PackedWithSlack::from_circuit:term_capacity");
1549 }
1550 packed.term_capacity_ = total_term_capacity;
1551 if (!compute_storage_layout(row_count, packed.term_capacity_, packed.constraint_capacity_,
1552 packed.term_bytes_offset_, packed.constant_bytes_offset_, packed.storage_bytes_)) {
1553 return unexpected_error(ErrorCode::Overflow, "NativeBulletproofCircuit::PackedWithSlack::from_circuit:storage_layout");
1554 }
1555 packed.storage_.reset(allocate_storage(packed.storage_bytes_));
1556 packed.start_storage_lifetimes();
1557
1558 PackedWithSlack::PackedRowHeader* headers =
1559 row_count == 0 ? nullptr : std::launder(reinterpret_cast<PackedWithSlack::PackedRowHeader*>(packed.raw_storage_bytes()));
1560 FieldElement* constants = packed.constant_data();
1561 if (packed.constraint_capacity_ != 0) {
1562 std::fill_n(constants, packed.constraint_capacity_, FieldElement::zero());
1563 std::copy(circuit.c.begin(), circuit.c.end(), constants);
1564 }
1565
1566 std::size_t row_cursor = 0;
1567 std::size_t term_cursor = 0;
1568 auto fill_family = [&](const std::vector<NativeBulletproofCircuitRow>& rows,
1569 const std::vector<std::size_t>& family_slack) {
1570 for (std::size_t i = 0; i < rows.size(); ++i, ++row_cursor) {
1571 const std::size_t extra = family_slack.empty() ? 0 : family_slack[i];
1572 PackedWithSlack::PackedRowHeader& header = headers[row_cursor];
1573 header.offset = term_cursor;
1574 header.size = rows[i].entries.size();
1575 header.base_size = rows[i].entries.size();
1576 header.capacity = rows[i].entries.size() + extra;
1577 if (!rows[i].entries.empty()) {
1578 std::copy(rows[i].entries.begin(), rows[i].entries.end(),
1579 packed.term_data() + static_cast<std::ptrdiff_t>(term_cursor));
1580 }
1581 term_cursor += header.capacity;
1582 }
1583 };
1584 fill_family(circuit.wl, slack.wl);
1585 fill_family(circuit.wr, slack.wr);
1586 fill_family(circuit.wo, slack.wo);
1587 fill_family(circuit.wv, slack.wv);
1588 assert(term_cursor == packed.term_capacity_ && "packed term cursor should consume the entire term buffer");
1589
1590 return packed;
1591}
1592
1596
1600
1602 if (commitments.empty() || proof.empty()) {
1603 return unexpected_error(ErrorCode::EmptyInput, "ExperimentalBulletproofProof::serialize:empty");
1604 }
1605 if (!size_fits_u32(proof.size()) || !size_fits_u32(commitments.size())) {
1606 return unexpected_error(ErrorCode::UnexpectedSize, "ExperimentalBulletproofProof::serialize:size");
1607 }
1608 std::size_t commitment_bytes = 0;
1609 std::size_t serialized_size = 0;
1610 if (!checked_mul_size(commitments.size(), 33, commitment_bytes)
1611 || !checked_add_size(9, commitment_bytes, serialized_size)
1612 || !checked_add_size(serialized_size, proof.size(), serialized_size)) {
1613 return unexpected_error(ErrorCode::Overflow, "ExperimentalBulletproofProof::serialize:reserve");
1614 }
1615
1616 Bytes out;
1617 out.reserve(serialized_size);
1618 out.push_back(kSerializationVersion);
1619 append_u32_le(out, static_cast<std::uint32_t>(proof.size()));
1620 append_u32_le(out, static_cast<std::uint32_t>(commitments.size()));
1621 for (const auto& commitment : commitments) {
1622 out.insert(out.end(), commitment.begin(), commitment.end());
1623 }
1624 out.insert(out.end(), proof.begin(), proof.end());
1625 return out;
1626}
1627
1629 if (bytes.size() < 9) {
1630 return unexpected_error(ErrorCode::InvalidFixedSize, "ExperimentalBulletproofProof::deserialize:header");
1631 }
1632 if (bytes[0] != kSerializationVersion) {
1633 return unexpected_error(ErrorCode::BackendRejectedInput, "ExperimentalBulletproofProof::deserialize:version");
1634 }
1635 const auto proof_size = read_u32_le(bytes, 1);
1636 const auto commitment_count = read_u32_le(bytes, 5);
1637 assert(proof_size.has_value() && commitment_count.has_value());
1638 if (*proof_size == 0 || *commitment_count == 0) {
1639 return unexpected_error(ErrorCode::EmptyInput, "ExperimentalBulletproofProof::deserialize:empty");
1640 }
1641 // Bound allocations by the received bytes before constructing any vectors.
1642 const std::size_t payload_size = bytes.size() - 9;
1643 if (*commitment_count > payload_size / 33) {
1644 return unexpected_error(ErrorCode::InvalidFixedSize, "ExperimentalBulletproofProof::deserialize:commitments");
1645 }
1646 const std::size_t commitment_bytes = std::size_t{*commitment_count} * 33;
1647 if (*proof_size != payload_size - commitment_bytes) {
1648 return unexpected_error(ErrorCode::InvalidFixedSize, "ExperimentalBulletproofProof::deserialize:proof_length");
1649 }
1651 out.commitments.resize(*commitment_count);
1652 std::size_t offset = 9;
1653 for (auto& commitment : out.commitments) {
1654 std::copy_n(bytes.begin() + static_cast<std::ptrdiff_t>(offset), 33, commitment.begin());
1655 offset += 33;
1656 }
1657 out.proof.assign(bytes.begin() + static_cast<std::ptrdiff_t>(offset), bytes.end());
1658 return out;
1659}
1660
1662 const NativeBulletproofCircuit& circuit,
1663 const BulletproofAssignmentData& assignment,
1664 const BulletproofScalarBytes& nonce,
1665 const BulletproofGeneratorBytes& value_generator,
1666 purify_secp_context* secp_context,
1667 std::span<const unsigned char> statement_binding,
1668 std::span<const BulletproofScalarBytes> blinds,
1669 ExperimentalBulletproofBackendCache* backend_cache) {
1670 return prove_experimental_circuit_impl(circuit, assignment, nonce, value_generator, secp_context, statement_binding,
1671 blinds, backend_cache, true,
1672 "prove_experimental_circuit:circuit_shape",
1673 "prove_experimental_circuit:n_gates_power_of_two",
1674 "prove_experimental_circuit:n_commitments",
1675 "prove_experimental_circuit:assignment_shape",
1676 "prove_experimental_circuit:assignment_invalid",
1677 "prove_experimental_circuit:proof_size",
1678 "prove_experimental_circuit:bridge");
1679}
1680
1683 const BulletproofAssignmentData& assignment,
1684 const BulletproofScalarBytes& nonce,
1685 const BulletproofGeneratorBytes& value_generator,
1686 purify_secp_context* secp_context,
1687 std::span<const unsigned char> statement_binding,
1688 std::span<const BulletproofScalarBytes> blinds,
1689 ExperimentalBulletproofBackendCache* backend_cache) {
1690 return prove_experimental_circuit_impl(circuit, assignment, nonce, value_generator, secp_context, statement_binding,
1691 blinds, backend_cache, true,
1692 "prove_experimental_circuit:packed_circuit_shape",
1693 "prove_experimental_circuit:packed_n_gates_power_of_two",
1694 "prove_experimental_circuit:packed_n_commitments",
1695 "prove_experimental_circuit:packed_assignment_shape",
1696 "prove_experimental_circuit:packed_assignment_invalid",
1697 "prove_experimental_circuit:packed_proof_size",
1698 "prove_experimental_circuit:packed_bridge");
1699}
1700
1703 const BulletproofAssignmentData& assignment,
1704 const BulletproofScalarBytes& nonce,
1705 const BulletproofGeneratorBytes& value_generator,
1706 purify_secp_context* secp_context,
1707 std::span<const unsigned char> statement_binding,
1708 std::span<const BulletproofScalarBytes> blinds,
1709 ExperimentalBulletproofBackendCache* backend_cache) {
1710 return prove_experimental_circuit_impl(circuit, assignment, nonce, value_generator, secp_context, statement_binding,
1711 blinds, backend_cache, false,
1712 "prove_experimental_circuit_assume_valid:packed_circuit_shape",
1713 "prove_experimental_circuit_assume_valid:packed_n_gates_power_of_two",
1714 "prove_experimental_circuit_assume_valid:packed_n_commitments",
1715 "prove_experimental_circuit_assume_valid:packed_assignment_shape",
1716 "prove_experimental_circuit_assume_valid:packed_assignment_invalid",
1717 "prove_experimental_circuit_assume_valid:packed_proof_size",
1718 "prove_experimental_circuit_assume_valid:packed_bridge");
1719}
1720
1722 const NativeBulletproofCircuit& circuit,
1723 const ExperimentalBulletproofProof& proof,
1724 const BulletproofGeneratorBytes& value_generator,
1725 purify_secp_context* secp_context,
1726 std::span<const unsigned char> statement_binding,
1727 ExperimentalBulletproofBackendCache* backend_cache) {
1728 PURIFY_RETURN_IF_ERROR(require_secp_context(secp_context, "verify_experimental_circuit:secp_context"),
1729 "verify_experimental_circuit:secp_context");
1730 if (!circuit.has_valid_shape()) {
1731 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:circuit_shape");
1732 }
1733 if (!is_power_of_two_size(circuit.n_gates)) {
1734 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:n_gates_power_of_two");
1735 }
1736 if (circuit.n_commitments == 0) {
1737 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:n_commitments");
1738 }
1739 if (proof.commitments.size() != circuit_n_commitments(circuit)) {
1740 return unexpected_error(ErrorCode::SizeMismatch, "verify_experimental_circuit:commitments_size");
1741 }
1742 if (proof.proof.empty()) {
1743 return unexpected_error(ErrorCode::EmptyInput, "verify_experimental_circuit:proof_empty");
1744 }
1745
1746 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
1747 PURIFY_ASSIGN_OR_RETURN(const auto& binding_digest, circuit_binding_digest(circuit, statement_binding),
1748 "verify_experimental_circuit:binding_digest");
1749 ResolvedBulletproofBackendResources resolved =
1750 resolve_bulletproof_backend_resources(circuit.n_gates, secp_context, backend_cache);
1751 purify_bulletproof_backend_resources* resources = resolved.resources;
1752 bool ok =
1753 resources != nullptr
1754 ? purify_bulletproof_verify_circuit_with_resources(resources, &flat_circuit.view, reinterpret_cast<const unsigned char*>(proof.commitments.data()),
1755 value_generator.data(), binding_digest.data(),
1756 binding_digest.size(), proof.proof.data(),
1757 proof.proof.size()) != 0
1758 : purify_bulletproof_verify_circuit(secp_context, &flat_circuit.view, reinterpret_cast<const unsigned char*>(proof.commitments.data()),
1759 value_generator.data(), binding_digest.data(),
1760 binding_digest.size(), proof.proof.data(),
1761 proof.proof.size()) != 0;
1762 return ok;
1763}
1764
1767 const ExperimentalBulletproofProof& proof,
1768 const BulletproofGeneratorBytes& value_generator,
1769 purify_secp_context* secp_context,
1770 std::span<const unsigned char> statement_binding,
1771 ExperimentalBulletproofBackendCache* backend_cache) {
1772 PURIFY_RETURN_IF_ERROR(require_secp_context(secp_context, "verify_experimental_circuit:packed_secp_context"),
1773 "verify_experimental_circuit:packed_secp_context");
1774 if (!circuit.has_valid_shape()) {
1775 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:packed_circuit_shape");
1776 }
1777 if (!is_power_of_two_size(circuit.n_gates())) {
1778 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:packed_n_gates_power_of_two");
1779 }
1780 if (circuit.n_commitments() == 0) {
1781 return unexpected_error(ErrorCode::InvalidDimensions, "verify_experimental_circuit:packed_n_commitments");
1782 }
1783 if (proof.commitments.size() != circuit_n_commitments(circuit)) {
1784 return unexpected_error(ErrorCode::SizeMismatch, "verify_experimental_circuit:commitments_size");
1785 }
1786 if (proof.proof.empty()) {
1787 return unexpected_error(ErrorCode::EmptyInput, "verify_experimental_circuit:packed_proof_empty");
1788 }
1789
1790 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
1791 PURIFY_ASSIGN_OR_RETURN(const auto& binding_digest, circuit_binding_digest(circuit, statement_binding),
1792 "verify_experimental_circuit:packed_binding_digest");
1793 ResolvedBulletproofBackendResources resolved =
1794 resolve_bulletproof_backend_resources(circuit.n_gates(), secp_context, backend_cache);
1795 purify_bulletproof_backend_resources* resources = resolved.resources;
1796 bool ok =
1797 resources != nullptr
1798 ? purify_bulletproof_verify_circuit_with_resources(resources, &flat_circuit.view, reinterpret_cast<const unsigned char*>(proof.commitments.data()),
1799 value_generator.data(), binding_digest.data(),
1800 binding_digest.size(), proof.proof.data(),
1801 proof.proof.size()) != 0
1802 : purify_bulletproof_verify_circuit(secp_context, &flat_circuit.view, reinterpret_cast<const unsigned char*>(proof.commitments.data()),
1803 value_generator.data(), binding_digest.data(),
1804 binding_digest.size(), proof.proof.data(),
1805 proof.proof.size()) != 0;
1806 return ok;
1807}
1808
1810 for (auto& term : expr.linear()) {
1811 if (term.first.kind == SymbolKind::Witness
1812 && term.first.index < witness_to_a_.size()
1813 && witness_to_a_[term.first.index].has_value()) {
1814 term.first = *witness_to_a_[term.first.index];
1815 }
1816 }
1817}
1818
1820 if (!expr.linear().empty()) {
1822 if (expr.constant().is_zero()
1823 && expr.linear().size() == 1
1824 && expr.linear()[0].second == FieldElement::one()
1825 && expr.linear()[0].first.kind == SymbolKind::Witness) {
1826 std::uint32_t witness_index = expr.linear()[0].first.index;
1827 if (witness_index < witness_to_a_.size() && !witness_to_a_[witness_index].has_value()) {
1828 witness_to_a_[witness_index] = symbol;
1829 witness_to_a_order_.push_back({witness_index, symbol});
1830 return true;
1831 }
1832 }
1833 }
1834 return false;
1835}
1836
1838 bool is_v = replace_and_insert(expr, symbol);
1839 assignments_.push_back({symbol, std::move(expr), is_v});
1840}
1841
1843 const Transcript& transcript, std::size_t n_bits,
1844 std::size_t minimum_gate_count) {
1845 if (!is_power_of_two_size(minimum_gate_count) ||
1846 minimum_gate_count >
1847 static_cast<std::size_t>(
1848 std::numeric_limits<std::uint32_t>::max())) {
1849 return unexpected_error(
1851 "BulletproofTranscript::from_transcript:minimum_gate_count");
1852 }
1853 assignments_.clear();
1854 constraints_.clear();
1855 witness_to_a_.assign(transcript.varmap().size(), std::nullopt);
1856 witness_to_a_order_.clear();
1857 n_witnesses_ = transcript.varmap().size();
1858 n_bits_ = n_bits;
1859 std::size_t source_muls = transcript.muls().size();
1860 for (std::size_t i = 0; i < source_muls; ++i) {
1861 const auto& mul = transcript.muls()[i];
1862 add_assignment(Symbol::left(narrow_symbol_index(i)), mul.lhs);
1863 add_assignment(Symbol::right(narrow_symbol_index(i)), mul.rhs);
1864 add_assignment(Symbol::output(narrow_symbol_index(i)), mul.out);
1865 }
1866
1867 std::vector<std::uint32_t> unmapped_transcript_vars;
1868 std::vector<bool> seen_transcript_vars(n_witnesses_, false);
1869 for (const Expr& eq : transcript.eqs()) {
1870 for (const auto& term : eq.linear()) {
1871 if (!is_transcript_var(term.first)) {
1872 continue;
1873 }
1874 std::uint32_t witness_index = term.first.index;
1875 if (witness_index >= witness_to_a_.size() || witness_to_a_[witness_index].has_value()) {
1876 continue;
1877 }
1878 if (!seen_transcript_vars[witness_index]) {
1879 unmapped_transcript_vars.push_back(witness_index);
1880 seen_transcript_vars[witness_index] = true;
1881 }
1882 }
1883 }
1884
1885 std::size_t total_gates = 0;
1886 if (!checked_add_size(source_muls, unmapped_transcript_vars.size(),
1887 total_gates)) {
1888 return unexpected_error(
1890 "BulletproofTranscript::from_transcript:total_gates");
1891 }
1892 if (total_gates >
1893 static_cast<std::size_t>(
1894 std::numeric_limits<std::uint32_t>::max())) {
1895 return unexpected_error(
1897 "BulletproofTranscript::from_transcript:total_gate_count");
1898 }
1899 n_muls_ = 1;
1900 while (n_muls_ < std::max<std::size_t>(1, total_gates)) {
1901 if (n_muls_ > std::numeric_limits<std::size_t>::max() / 2) {
1902 return unexpected_error(
1904 "BulletproofTranscript::from_transcript:natural_gate_count");
1905 }
1906 n_muls_ <<= 1;
1907 }
1908 n_muls_ = std::max(n_muls_, minimum_gate_count);
1909
1910 for (std::size_t i = 0; i < unmapped_transcript_vars.size(); ++i) {
1911 std::size_t gate_idx = source_muls + i;
1912 std::uint32_t gate_symbol = narrow_symbol_index(gate_idx);
1913 add_assignment(Symbol::left(gate_symbol), Expr::variable(Symbol::witness(unmapped_transcript_vars[i])));
1914 add_assignment(Symbol::right(gate_symbol), Expr(0));
1915 add_assignment(Symbol::output(gate_symbol), Expr(0));
1916 }
1917
1918 for (std::size_t i = total_gates; i < n_muls_; ++i) {
1919 std::uint32_t gate_symbol = narrow_symbol_index(i);
1920 add_assignment(Symbol::left(gate_symbol), Expr(0));
1921 add_assignment(Symbol::right(gate_symbol), Expr(0));
1922 add_assignment(Symbol::output(gate_symbol), Expr(0));
1923 }
1924
1925 for (const Expr& eq : transcript.eqs()) {
1926 Expr lowered = eq;
1928 if (contains_transcript_var(lowered)) {
1929 return unexpected_error(ErrorCode::UnsupportedSymbol, "BulletproofTranscript::from_transcript:unmapped_eq_var");
1930 }
1931 constraints_.push_back({lowered, Expr(0)});
1932 }
1933 return {};
1934}
1935
1937 if (n_muls_ == 0) {
1938 return unexpected_error(
1940 "BulletproofTranscript::bind_output_to_commitment:transcript");
1941 }
1943 for (const auto& [symbol, scalar] : output.linear()) {
1944 (void)scalar;
1945 switch (symbol.kind) {
1946 case SymbolKind::Left:
1947 case SymbolKind::Right:
1948 case SymbolKind::Output:
1949 if (symbol.index >= n_muls_) {
1950 return unexpected_error(
1952 "BulletproofTranscript::bind_output_to_commitment:wire_index");
1953 }
1954 break;
1957 return unexpected_error(
1959 "BulletproofTranscript::bind_output_to_commitment:symbol");
1960 default:
1961 return unexpected_error(
1963 "BulletproofTranscript::bind_output_to_commitment:symbol_kind");
1964 }
1965 }
1966 constraints_.push_back(
1967 {output - Expr::variable(Symbol::commitment(0)), Expr(0)});
1968 return {};
1969}
1970
1973 if (!unpacked.has_value()) {
1974 return unexpected_error(unpacked.error(), "BulletproofTranscript::add_pubkey_and_out:unpack_public");
1975 }
1976 auto add_constraint = [&](const UInt256& packed, Expr expr) -> Status {
1978 auto parts = expr.split();
1980 if (!constant.has_value()) {
1981 return unexpected_error(constant.error(), "BulletproofTranscript::add_pubkey_and_out:field_constant");
1982 }
1983 constraints_.push_back({parts.second, Expr(*constant) - parts.first});
1984 return {};
1985 };
1986 Status p1_status = add_constraint(unpacked->first, std::move(p1x));
1987 if (!p1_status.has_value()) {
1988 return unexpected_error(p1_status.error(), "BulletproofTranscript::add_pubkey_and_out:p1x");
1989 }
1990 Status p2_status = add_constraint(unpacked->second, std::move(p2x));
1991 if (!p2_status.has_value()) {
1992 return unexpected_error(p2_status.error(), "BulletproofTranscript::add_pubkey_and_out:p2x");
1993 }
1994 Status output_status = bind_output_to_commitment(std::move(out));
1995 if (!output_status.has_value()) {
1996 return unexpected_error(
1997 output_status.error(),
1998 "BulletproofTranscript::add_pubkey_and_out:output");
1999 }
2000 return {};
2001}
2002
2004 std::size_t n_constraints = 0;
2005 for (const auto& assignment : assignments_) {
2006 if (!assignment.is_v) {
2007 ++n_constraints;
2008 }
2009 }
2010 n_constraints += constraints_.size();
2011 std::ostringstream out;
2012 out << n_muls_ << "," << n_commitments_ << "," << n_bits_ << "," << (n_constraints - 2 * n_bits_) << ";";
2013 std::size_t i = 0;
2014 for (const auto& assignment : assignments_) {
2015 if (!assignment.is_v) {
2016 if (i < 2 * n_bits_) {
2017 ++i;
2018 continue;
2019 }
2020 auto parts = assignment.expr.split();
2021 out << assignment.symbol.to_string();
2022 if (!parts.second.linear().empty()) {
2023 out << " + " << (-parts.second).to_string();
2024 }
2025 out << " = " << parts.first.to_string() << ";";
2026 }
2027 }
2028 for (const auto& constraint : constraints_) {
2029 out << constraint.first.to_string() << " = " << constraint.second.to_string() << ";";
2030 }
2031 return out.str();
2032}
2033
2034bool BulletproofTranscript::evaluate(const WitnessAssignments& vars, const FieldElement& commitment) const {
2035 ResolvedValues values(n_witnesses_, n_muls_, n_commitments_);
2036 for (std::size_t i = 0; i < std::min(vars.size(), values.witness.size()); ++i) {
2037 values.witness[i] = vars[i];
2038 }
2039 if (!values.set(Symbol::commitment(0), commitment)) {
2040 return false;
2041 }
2042 for (const auto& item : witness_to_a_order_) {
2043 if (item.first >= values.witness.size() || !values.witness[item.first].has_value()) {
2044 return false;
2045 }
2046 if (!values.set(item.second, *values.witness[item.first])) {
2047 return false;
2048 }
2049 }
2050 for (const auto& assignment : assignments_) {
2051 Result<FieldElement> evaluated = ::evaluate_known(assignment.expr, values);
2052 if (!evaluated.has_value()) {
2053 return false;
2054 }
2055 if (!values.set(assignment.symbol, *evaluated)) {
2056 return false;
2057 }
2058 }
2059 for (std::size_t i = 0; i < n_muls_; ++i) {
2060 if (!values.left[i].has_value() || !values.right[i].has_value() || !values.output[i].has_value()) {
2061 return false;
2062 }
2063 if (*values.left[i] * *values.right[i] != *values.output[i]) {
2064 return false;
2065 }
2066 }
2067 for (const auto& constraint : constraints_) {
2068 Result<FieldElement> lhs = ::evaluate_known(constraint.first, values);
2069 Result<FieldElement> rhs = ::evaluate_known(constraint.second, values);
2070 if (!lhs.has_value() || !rhs.has_value() || *lhs != *rhs) {
2071 return false;
2072 }
2073 }
2074 return true;
2075}
2076
2079 circuit.n_gates = n_muls_;
2080 circuit.n_commitments = n_commitments_;
2081 circuit.n_bits = n_bits_;
2082 circuit.wl.resize(n_muls_);
2083 circuit.wr.resize(n_muls_);
2084 circuit.wo.resize(n_muls_);
2085 circuit.wv.resize(n_commitments_);
2086 circuit.c.reserve(
2087 std::count_if(assignments_.begin(), assignments_.end(),
2088 [](const auto& assignment) { return !assignment.is_v; })
2089 + constraints_.size());
2090
2091 for (const auto& assignment : assignments_) {
2092 if (!assignment.is_v) {
2093 append_constraint_to_circuit(circuit, Expr::variable(assignment.symbol), assignment.expr);
2094 }
2095 }
2096 for (const auto& constraint : constraints_) {
2097 append_constraint_to_circuit(circuit, constraint.first, constraint.second);
2098 }
2099 return circuit;
2100}
2101
2104 Expr p1x,
2105 Expr p2x,
2106 Expr out) {
2107 NativeBulletproofCircuitTemplate template_circuit;
2108 template_circuit.base_packed_ = std::move(base_packed);
2109 template_circuit.p1x_ = std::move(p1x);
2110 template_circuit.p2x_ = std::move(p2x);
2111 template_circuit.out_ = std::move(out);
2112 return template_circuit;
2113}
2114
2116 if (!base_packed_.has_valid_shape()) {
2117 return unexpected_error(ErrorCode::InvalidDimensions, "NativeBulletproofCircuitTemplate::partial_evaluate:shape");
2118 }
2119 if (assignment.left.size() != base_packed_.n_gates()
2120 || assignment.right.size() != base_packed_.n_gates()
2121 || assignment.output.size() != base_packed_.n_gates()
2122 || assignment.commitments.size() != base_packed_.n_commitments()) {
2123 return unexpected_error(ErrorCode::SizeMismatch, "NativeBulletproofCircuitTemplate::partial_evaluate:assignment_shape");
2124 }
2125 return base_packed_.evaluate(assignment);
2126}
2127
2129 const UInt512& pubkey) const {
2130 if (!base_packed_.has_valid_shape()) {
2131 return unexpected_error(ErrorCode::InvalidDimensions, "NativeBulletproofCircuitTemplate::final_evaluate:shape");
2132 }
2133 if (assignment.left.size() != base_packed_.n_gates()
2134 || assignment.right.size() != base_packed_.n_gates()
2135 || assignment.output.size() != base_packed_.n_gates()
2136 || assignment.commitments.size() != base_packed_.n_commitments()) {
2137 return unexpected_error(ErrorCode::SizeMismatch, "NativeBulletproofCircuitTemplate::final_evaluate:assignment_shape");
2138 }
2140 if (!unpacked.has_value()) {
2141 return unexpected_error(unpacked.error(), "NativeBulletproofCircuitTemplate::final_evaluate:unpack_public");
2142 }
2143 Result<FieldElement> expected_p1 = FieldElement::try_from_uint256(unpacked->first);
2144 if (!expected_p1.has_value()) {
2145 return unexpected_error(expected_p1.error(), "NativeBulletproofCircuitTemplate::final_evaluate:expected_p1");
2146 }
2147 Result<FieldElement> expected_p2 = FieldElement::try_from_uint256(unpacked->second);
2148 if (!expected_p2.has_value()) {
2149 return unexpected_error(expected_p2.error(), "NativeBulletproofCircuitTemplate::final_evaluate:expected_p2");
2150 }
2151 Result<FieldElement> actual_p1 = evaluate_expr_with_assignment(p1x_, assignment);
2152 if (!actual_p1.has_value()) {
2153 return unexpected_error(actual_p1.error(), "NativeBulletproofCircuitTemplate::final_evaluate:actual_p1");
2154 }
2155 Result<FieldElement> actual_p2 = evaluate_expr_with_assignment(p2x_, assignment);
2156 if (!actual_p2.has_value()) {
2157 return unexpected_error(actual_p2.error(), "NativeBulletproofCircuitTemplate::final_evaluate:actual_p2");
2158 }
2159 Result<FieldElement> actual_out = evaluate_expr_with_assignment(out_, assignment);
2160 if (!actual_out.has_value()) {
2161 return unexpected_error(actual_out.error(), "NativeBulletproofCircuitTemplate::final_evaluate:actual_out");
2162 }
2163 return *actual_p1 == *expected_p1
2164 && *actual_p2 == *expected_p2
2165 && *actual_out == assignment.commitments[0];
2166}
2167
2169 if (!base_packed_.has_valid_shape()) {
2170 return unexpected_error(ErrorCode::InvalidDimensions, "NativeBulletproofCircuitTemplate::integrity_digest:shape");
2171 }
2172
2173 static const TaggedHash kTemplateDigestTag("Purify/VerifierCircuitTemplate/V1");
2174 PURIFY_ASSIGN_OR_RETURN(auto serialized, circuit_binding_digest(base_packed_, {}),
2175 "NativeBulletproofCircuitTemplate::integrity_digest:circuit_binding_digest");
2176 PURIFY_RETURN_IF_ERROR(append_expr_digest(serialized, p1x_),
2177 "NativeBulletproofCircuitTemplate::integrity_digest:p1x");
2178 PURIFY_RETURN_IF_ERROR(append_expr_digest(serialized, p2x_),
2179 "NativeBulletproofCircuitTemplate::integrity_digest:p2x");
2180 PURIFY_RETURN_IF_ERROR(append_expr_digest(serialized, out_),
2181 "NativeBulletproofCircuitTemplate::integrity_digest:out");
2182 const std::array<unsigned char, 32> digest =
2183 kTemplateDigestTag.digest(std::span<const unsigned char>(serialized.data(), serialized.size()));
2184 return Bytes(digest.begin(), digest.end());
2185}
2186
2189 if (!unpacked.has_value()) {
2190 return unexpected_error(unpacked.error(), "NativeBulletproofCircuitTemplate::instantiate_packed:unpack_public");
2191 }
2192
2193 NativeBulletproofCircuit::PackedWithSlack circuit = base_packed_;
2194 circuit.reset();
2195 auto append_pubkey_constraint = [&](const UInt256& packed, const Expr& expr) -> Status {
2196 auto parts = expr.split();
2198 if (!constant.has_value()) {
2199 return unexpected_error(constant.error(), "NativeBulletproofCircuitTemplate::instantiate_packed:field_constant");
2200 }
2201 append_constraint_to_circuit(circuit, parts.second, Expr(*constant) - parts.first);
2202 return {};
2203 };
2204
2205 Status p1_status = append_pubkey_constraint(unpacked->first, p1x_);
2206 if (!p1_status.has_value()) {
2207 return unexpected_error(p1_status.error(), "NativeBulletproofCircuitTemplate::instantiate_packed:p1x");
2208 }
2209 Status p2_status = append_pubkey_constraint(unpacked->second, p2x_);
2210 if (!p2_status.has_value()) {
2211 return unexpected_error(p2_status.error(), "NativeBulletproofCircuitTemplate::instantiate_packed:p2x");
2212 }
2213 append_constraint_to_circuit(circuit, out_, Expr::variable(Symbol::commitment(0)));
2214 return circuit;
2215}
2216
2219 if (!packed.has_value()) {
2220 return unexpected_error(packed.error(), "NativeBulletproofCircuitTemplate::instantiate:instantiate_packed");
2221 }
2222 return packed->unpack();
2223}
2224
2226 std::span<const UInt512> public_keys) const {
2227 PURIFY_ASSIGN_OR_RETURN(const auto& gates, sum_circuit_gate_count(base_packed_, public_keys),
2228 "NativeBulletproofCircuitTemplate::instantiate_sum:gate_count");
2229 std::size_t member_constraints = 0;
2230 std::size_t total_constraints = 0;
2231 if (!checked_add_size(base_packed_.constraint_count(), 2, member_constraints)
2232 || !checked_mul_size(member_constraints, public_keys.size(), total_constraints)
2233 || !checked_add_size(total_constraints, 1, total_constraints)) {
2234 return unexpected_error(ErrorCode::Overflow, "NativeBulletproofCircuitTemplate::instantiate_sum:constraints");
2235 }
2236
2237 // Each member's bit equations are already explicit. They no longer form the
2238 // global gate prefix required by the legacy implicit-bit optimization.
2239 NativeBulletproofCircuit circuit(gates, 1, 0);
2240 circuit.c.reserve(total_constraints);
2241 const std::size_t member_gates = base_packed_.n_gates();
2242 auto append_row = [&](NativeBulletproofCircuitRow& destination,
2244 std::size_t constraint_offset) -> Status {
2245 destination.entries.reserve(source.size);
2246 for (const auto& entry : source.entries_view()) {
2247 if (entry.idx >= base_packed_.constraint_count()) {
2249 "NativeBulletproofCircuitTemplate::instantiate_sum:constraint_index");
2250 }
2251 destination.add(constraint_offset + entry.idx, entry.scalar);
2252 }
2253 return {};
2254 };
2255
2256 for (std::size_t member = 0; member < public_keys.size(); ++member) {
2257 const std::size_t gate_offset = member * member_gates;
2258 const std::size_t constraint_offset = circuit.c.size();
2259 const auto constants = base_packed_.constants();
2260 circuit.c.insert(circuit.c.end(), constants.begin(), constants.end());
2261 for (std::size_t gate = 0; gate < member_gates; ++gate) {
2262 PURIFY_RETURN_IF_ERROR(append_row(circuit.wl[gate_offset + gate], base_packed_.left_row(gate), constraint_offset),
2263 "NativeBulletproofCircuitTemplate::instantiate_sum:left_row");
2264 PURIFY_RETURN_IF_ERROR(append_row(circuit.wr[gate_offset + gate], base_packed_.right_row(gate), constraint_offset),
2265 "NativeBulletproofCircuitTemplate::instantiate_sum:right_row");
2266 PURIFY_RETURN_IF_ERROR(append_row(circuit.wo[gate_offset + gate], base_packed_.output_row(gate), constraint_offset),
2267 "NativeBulletproofCircuitTemplate::instantiate_sum:output_row");
2268 }
2269 PURIFY_ASSIGN_OR_RETURN(const auto& unpacked, unpack_public(public_keys[member]),
2270 "NativeBulletproofCircuitTemplate::instantiate_sum:unpack_public");
2271 auto append_host_coordinate = [&](const UInt256& coordinate, const Expr& expr) -> Status {
2272 PURIFY_ASSIGN_OR_RETURN(const auto& value, FieldElement::try_from_uint256(coordinate),
2273 "NativeBulletproofCircuitTemplate::instantiate_sum:coordinate");
2274 const std::size_t constraint = circuit.add_constraint(value - expr.constant());
2275 return append_sum_expression(circuit, expr, gate_offset, member_gates, constraint);
2276 };
2277 PURIFY_RETURN_IF_ERROR(append_host_coordinate(unpacked.first, p1x_),
2278 "NativeBulletproofCircuitTemplate::instantiate_sum:p1x");
2279 PURIFY_RETURN_IF_ERROR(append_host_coordinate(unpacked.second, p2x_),
2280 "NativeBulletproofCircuitTemplate::instantiate_sum:p2x");
2281 }
2282
2283 const std::size_t sum_constraint = circuit.add_constraint();
2284 for (std::size_t member = 0; member < public_keys.size(); ++member) {
2285 circuit.c[sum_constraint] = circuit.c[sum_constraint] - out_.constant();
2286 PURIFY_RETURN_IF_ERROR(append_sum_expression(circuit, out_, member * member_gates,
2287 member_gates, sum_constraint),
2288 "NativeBulletproofCircuitTemplate::instantiate_sum:output_sum");
2289 }
2290 circuit.add_commitment_term(0, sum_constraint, FieldElement::one().negate());
2291 return circuit;
2292}
2293
2295 std::span<const UInt512> public_keys,
2296 std::span<const BulletproofAssignmentData> assignments) const {
2297 if (assignments.size() != public_keys.size()) {
2298 return unexpected_error(ErrorCode::SizeMismatch, "NativeBulletproofCircuitTemplate::sum_assignments:roster_size");
2299 }
2300 PURIFY_ASSIGN_OR_RETURN(const auto& gates, sum_circuit_gate_count(base_packed_, public_keys),
2301 "NativeBulletproofCircuitTemplate::sum_assignments:gate_count");
2302 for (const Expr* expr : {&p1x_, &p2x_, &out_}) {
2303 PURIFY_RETURN_IF_ERROR(validate_sum_expression(*expr, base_packed_.n_gates()),
2304 "NativeBulletproofCircuitTemplate::sum_assignments:expression_shape");
2305 }
2306 for (std::size_t member = 0; member < assignments.size(); ++member) {
2307 PURIFY_ASSIGN_OR_RETURN(const auto& partial_ok, partial_evaluate(assignments[member]),
2308 "NativeBulletproofCircuitTemplate::sum_assignments:partial_evaluate");
2309 if (!partial_ok) {
2311 "NativeBulletproofCircuitTemplate::sum_assignments:invalid_assignment");
2312 }
2313 PURIFY_ASSIGN_OR_RETURN(const auto& final_ok, final_evaluate(assignments[member], public_keys[member]),
2314 "NativeBulletproofCircuitTemplate::sum_assignments:final_evaluate");
2315 if (!final_ok) {
2317 "NativeBulletproofCircuitTemplate::sum_assignments:host_or_output");
2318 }
2319 }
2320
2322 sum.left.reserve(gates);
2323 sum.right.reserve(gates);
2324 sum.output.reserve(gates);
2325 FieldElement output_sum = FieldElement::zero();
2326 for (const auto& assignment : assignments) {
2327 sum.left.insert(sum.left.end(), assignment.left.begin(), assignment.left.end());
2328 sum.right.insert(sum.right.end(), assignment.right.begin(), assignment.right.end());
2329 sum.output.insert(sum.output.end(), assignment.output.begin(), assignment.output.end());
2330 output_sum = output_sum + assignment.commitments.front();
2331 }
2332 sum.left.resize(gates, FieldElement::zero());
2333 sum.right.resize(gates, FieldElement::zero());
2334 sum.output.resize(gates, FieldElement::zero());
2335 sum.commitments.push_back(output_sum);
2336 return sum;
2337}
2338
2340 return assignment_data_impl(vars, nullptr);
2341}
2342
2344 const FieldElement& commitment) const {
2345 return assignment_data_impl(vars, &commitment);
2346}
2347
2348Result<BulletproofAssignmentData> BulletproofTranscript::assignment_data_impl(const WitnessAssignments& vars,
2349 const FieldElement* commitment) const {
2350 ResolvedValues values(n_witnesses_, n_muls_, n_commitments_);
2351 for (std::size_t i = 0; i < std::min(vars.size(), values.witness.size()); ++i) {
2352 values.witness[i] = vars[i];
2353 }
2354 if (commitment != nullptr && !values.set(Symbol::commitment(0), *commitment)) {
2355 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:commitment_slot");
2356 }
2357 for (const auto& item : witness_to_a_order_) {
2358 if (item.first >= values.witness.size() || !values.witness[item.first].has_value()) {
2359 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:mapped_value");
2360 }
2361 if (!values.set(item.second, *values.witness[item.first])) {
2362 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:mapped_symbol");
2363 }
2364 }
2365 for (const auto& assignment : assignments_) {
2366 Result<FieldElement> evaluated = ::evaluate_known(assignment.expr, values);
2367 if (!evaluated.has_value()) {
2368 return unexpected_error(evaluated.error(), "BulletproofTranscript::assignment_data:evaluate_assignment");
2369 }
2370 if (!values.set(assignment.symbol, *evaluated)) {
2371 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:store_assignment");
2372 }
2373 }
2374
2375 BulletproofAssignmentData assignment;
2376 assignment.left.reserve(n_muls_);
2377 assignment.right.reserve(n_muls_);
2378 assignment.output.reserve(n_muls_);
2379 assignment.commitments.reserve(n_commitments_);
2380 auto read_column = [&](const WitnessAssignments& source,
2381 BulletproofWitnessColumn& column) -> Status {
2382 for (const auto& value : source) {
2383 if (!value.has_value()) {
2384 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:column_value");
2385 }
2386 column.push_back(*value);
2387 }
2388 return {};
2389 };
2390 Status left_status = read_column(values.left, assignment.left);
2391 if (!left_status.has_value()) {
2392 return unexpected_error(left_status.error(), "BulletproofTranscript::assignment_data:left_column");
2393 }
2394 Status right_status = read_column(values.right, assignment.right);
2395 if (!right_status.has_value()) {
2396 return unexpected_error(right_status.error(), "BulletproofTranscript::assignment_data:right_column");
2397 }
2398 Status output_status = read_column(values.output, assignment.output);
2399 if (!output_status.has_value()) {
2400 return unexpected_error(output_status.error(), "BulletproofTranscript::assignment_data:output_column");
2401 }
2402 for (const auto& value : values.commitment) {
2403 if (!value.has_value()) {
2404 return unexpected_error(ErrorCode::MissingValue, "BulletproofTranscript::assignment_data:commitment");
2405 }
2406 assignment.commitments.push_back(*value);
2407 }
2408 return assignment;
2409}
2410
2413 if (!assignment.has_value()) {
2414 return unexpected_error(assignment.error(), "BulletproofTranscript::serialize_assignment:assignment_data");
2415 }
2416 return assignment->serialize();
2417}
2418
2419bool BulletproofTranscript::is_transcript_var(Symbol symbol) {
2420 return symbol.kind == SymbolKind::Witness;
2421}
2422
2423bool BulletproofTranscript::contains_transcript_var(const Expr& expr) {
2424 return std::any_of(expr.linear().begin(), expr.linear().end(),
2425 [](const auto& term) { return is_transcript_var(term.first); });
2426}
2427
2428Expr circuit_1bit(const std::array<FieldElement, 2>& values, Transcript&, const Expr& x) {
2429 return ExprBuilder::reserved(x.linear().size())
2430 .add(values[0])
2431 .add_scaled(x, values[1] - values[0])
2432 .build();
2433}
2434
2435Expr circuit_2bit(const std::array<FieldElement, 4>& values, Transcript& transcript, const Expr& x, const Expr& y) {
2436 Expr xy = transcript.mul(x, y);
2437 return ExprBuilder::reserved(x.linear().size() + y.linear().size() + xy.linear().size())
2438 .add(values[0])
2439 .add_scaled(x, values[1] - values[0])
2440 .add_scaled(y, values[2] - values[0])
2441 .add_scaled(xy, values[0] + values[3] - values[1] - values[2])
2442 .build();
2443}
2444
2445Expr circuit_3bit(const std::array<FieldElement, 8>& values, Transcript& transcript, const Expr& x, const Expr& y, const Expr& z) {
2446 Expr xy = transcript.mul(x, y);
2447 Expr yz = transcript.mul(y, z);
2448 Expr zx = transcript.mul(z, x);
2449 Expr xyz = transcript.mul(xy, z);
2450 return ExprBuilder::reserved(x.linear().size() + y.linear().size() + z.linear().size()
2451 + xy.linear().size() + yz.linear().size() + zx.linear().size() + xyz.linear().size())
2452 .add(values[0])
2453 .add_scaled(x, values[1] - values[0])
2454 .add_scaled(y, values[2] - values[0])
2455 .add_scaled(z, values[4] - values[0])
2456 .add_scaled(xy, values[0] + values[3] - values[1] - values[2])
2457 .add_scaled(zx, values[0] + values[5] - values[1] - values[4])
2458 .add_scaled(yz, values[0] + values[6] - values[2] - values[4])
2459 .add_scaled(xyz, values[1] + values[2] + values[4] + values[7] - values[0] - values[3] - values[5] - values[6])
2460 .build();
2461}
2462
2463ExprPoint circuit_1bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 2>& points,
2464 Transcript& transcript, const Expr& b0) {
2465 std::array<AffinePoint, 2> affine_points{curve.affine(points[0]), curve.affine(points[1])};
2466 return {
2467 circuit_1bit({affine_points[0].x, affine_points[1].x}, transcript, b0),
2468 circuit_1bit({affine_points[0].y, affine_points[1].y}, transcript, b0)
2469 };
2470}
2471
2472ExprPoint circuit_2bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 4>& points,
2473 Transcript& transcript, const Expr& b0, const Expr& b1) {
2474 std::array<AffinePoint, 4> affine_points{curve.affine(points[0]), curve.affine(points[1]), curve.affine(points[2]), curve.affine(points[3])};
2475 return {
2476 circuit_2bit({affine_points[0].x, affine_points[1].x, affine_points[2].x, affine_points[3].x}, transcript, b0, b1),
2477 circuit_2bit({affine_points[0].y, affine_points[1].y, affine_points[2].y, affine_points[3].y}, transcript, b0, b1)
2478 };
2479}
2480
2481ExprPoint circuit_3bit_point(const EllipticCurve& curve, const std::array<JacobianPoint, 8>& points,
2482 Transcript& transcript, const Expr& b0, const Expr& b1, const Expr& b2) {
2483 std::array<AffinePoint, 8> affine_points{
2484 curve.affine(points[0]), curve.affine(points[1]), curve.affine(points[2]), curve.affine(points[3]),
2485 curve.affine(points[4]), curve.affine(points[5]), curve.affine(points[6]), curve.affine(points[7])
2486 };
2487 return {
2488 circuit_3bit({affine_points[0].x, affine_points[1].x, affine_points[2].x, affine_points[3].x,
2489 affine_points[4].x, affine_points[5].x, affine_points[6].x, affine_points[7].x},
2490 transcript, b0, b1, b2),
2491 circuit_3bit({affine_points[0].y, affine_points[1].y, affine_points[2].y, affine_points[3].y,
2492 affine_points[4].y, affine_points[5].y, affine_points[6].y, affine_points[7].y},
2493 transcript, b0, b1, b2)
2494 };
2495}
2496
2497ExprPoint circuit_optionally_negate_ec(const ExprPoint& point, Transcript& transcript, const Expr& negate_bit) {
2498 return {point.first, transcript.mul(Expr(1) - 2 * negate_bit, point.second)};
2499}
2500
2501ExprPoint circuit_ec_add(Transcript& transcript, const ExprPoint& p1, const ExprPoint& p2) {
2502 Expr lambda = transcript.div(p2.second - p1.second, p2.first - p1.first);
2503 Expr lambda_sq = transcript.mul(lambda, lambda);
2504 Expr x = ExprBuilder::reserved(lambda_sq.linear().size() + p1.first.linear().size() + p2.first.linear().size())
2505 .add(lambda_sq)
2506 .subtract(p1.first)
2507 .subtract(p2.first)
2508 .build();
2509 Expr delta = ExprBuilder::reserved(p1.first.linear().size() + x.linear().size())
2510 .add(p1.first)
2511 .subtract(x)
2512 .build();
2513 Expr lambda_delta = transcript.mul(lambda, delta);
2514 Expr y = ExprBuilder::reserved(lambda_delta.linear().size() + p1.second.linear().size())
2515 .add(lambda_delta)
2516 .subtract(p1.second)
2517 .build();
2518 return {x, y};
2519}
2520
2521Expr circuit_ec_add_x(Transcript& transcript, const ExprPoint& p1, const ExprPoint& p2) {
2522 Expr lambda = transcript.div(p2.second - p1.second, p2.first - p1.first);
2523 Expr lambda_sq = transcript.mul(lambda, lambda);
2524 return ExprBuilder::reserved(lambda_sq.linear().size() + p1.first.linear().size() + p2.first.linear().size())
2525 .add(lambda_sq)
2526 .subtract(p1.first)
2527 .subtract(p2.first)
2528 .build();
2529}
2530
2531namespace {
2532
2533enum class CircuitEcMultiplyOutput {
2534 XOnly,
2535 FullPoint,
2536};
2537
2538ExprPoint circuit_ec_multiply_impl(const EllipticCurve& curve, Transcript& transcript,
2539 const JacobianPoint& point, const std::vector<Expr>& bits,
2540 CircuitEcMultiplyOutput output) {
2541 std::vector<JacobianPoint> powers;
2542 powers.reserve(bits.size());
2543 powers.push_back(point);
2544 for (std::size_t i = 1; i < bits.size(); ++i) {
2545 powers.push_back(curve.double_point(powers.back()));
2546 }
2547
2548 std::vector<ExprPoint> lookups;
2549 for (std::size_t i = 0; i < (bits.size() - 1) / 3; ++i) {
2550 JacobianPoint p1 = powers[i * 3];
2551 JacobianPoint p3 = curve.add(p1, powers[i * 3 + 1]);
2552 JacobianPoint p5 = curve.add(p3, powers[i * 3 + 1]);
2553 JacobianPoint p7 = curve.add(p5, powers[i * 3 + 1]);
2554 lookups.push_back(circuit_optionally_negate_ec(
2555 circuit_2bit_point(curve, {p1, p3, p5, p7}, transcript, bits[i * 3 + 1], bits[i * 3 + 2]),
2556 transcript,
2557 bits[i * 3 + 3]));
2558 }
2559
2560 if (bits.size() % 3 == 0) {
2561 JacobianPoint pn = powers[powers.size() - 3];
2562 JacobianPoint p3n = curve.add(pn, powers[powers.size() - 2]);
2563 JacobianPoint p5n = curve.add(p3n, powers[powers.size() - 2]);
2564 JacobianPoint p7n = curve.add(p5n, powers[powers.size() - 2]);
2565 JacobianPoint pn1 = curve.add(pn, powers[0]);
2566 JacobianPoint p3n1 = curve.add(p3n, powers[0]);
2567 JacobianPoint p5n1 = curve.add(p5n, powers[0]);
2568 JacobianPoint p7n1 = curve.add(p7n, powers[0]);
2569 lookups.push_back(circuit_3bit_point(curve, {pn, pn1, p3n, p3n1, p5n, p5n1, p7n, p7n1},
2570 transcript, bits[0], bits[bits.size() - 2], bits[bits.size() - 1]));
2571 } else if (bits.size() % 3 == 1) {
2572 JacobianPoint pn = powers.back();
2573 JacobianPoint pn1 = curve.add(pn, powers[0]);
2574 lookups.push_back(circuit_1bit_point(curve, {pn, pn1}, transcript, bits[0]));
2575 } else {
2576 JacobianPoint pn = powers[powers.size() - 2];
2577 JacobianPoint p3n = curve.add(pn, powers.back());
2578 JacobianPoint pn1 = curve.add(pn, powers[0]);
2579 JacobianPoint p3n1 = curve.add(p3n, powers[0]);
2580 lookups.push_back(circuit_2bit_point(curve, {pn, pn1, p3n, p3n1}, transcript, bits[0], bits.back()));
2581 }
2582
2583 ExprPoint out = lookups[0];
2584 for (std::size_t i = 1; i + 1 < lookups.size(); ++i) {
2585 out = circuit_ec_add(transcript, out, lookups[i]);
2586 }
2587 if (output == CircuitEcMultiplyOutput::FullPoint) {
2588 return circuit_ec_add(transcript, out, lookups.back());
2589 }
2590 // Keep the historical x-only circuit byte-for-byte stable. Computing an
2591 // unused final y-coordinate would append one multiplication gate and
2592 // change every existing circuit transcript and proof vector.
2593 return {circuit_ec_add_x(transcript, out, lookups.back()), Expr(0)};
2594}
2595
2596} // namespace
2597
2599 const JacobianPoint& point, const std::vector<Expr>& bits) {
2600 return circuit_ec_multiply_impl(curve, transcript, point, bits,
2601 CircuitEcMultiplyOutput::FullPoint);
2602}
2603
2605 const JacobianPoint& point, const std::vector<Expr>& bits) {
2606 return circuit_ec_multiply_impl(curve, transcript, point, bits,
2607 CircuitEcMultiplyOutput::XOnly)
2608 .first;
2609}
2610
2611Expr circuit_combine(Transcript& transcript, const Expr& x1, const Expr& x2) {
2612 Expr v = ExprBuilder::reserved(x2.linear().size())
2613 .add_scaled(x2, field_di())
2614 .build();
2615 Expr u_plus_v = ExprBuilder::reserved(x1.linear().size() + v.linear().size())
2616 .add(x1)
2617 .add(v)
2618 .build();
2619 Expr uv = transcript.mul(x1, v);
2620 Expr uv_plus_a = ExprBuilder::reserved(uv.linear().size())
2621 .add(field_a())
2622 .add(uv)
2623 .build();
2624 Expr numerator_mul = transcript.mul(u_plus_v, uv_plus_a);
2625 Expr numerator = ExprBuilder::reserved(numerator_mul.linear().size())
2627 .add(numerator_mul)
2628 .build();
2629 Expr u_minus_v = ExprBuilder::reserved(x1.linear().size() + v.linear().size())
2630 .add(x1)
2631 .subtract(v)
2632 .build();
2633 Expr denominator = transcript.mul(u_minus_v, u_minus_v);
2634 return transcript.div(numerator, denominator);
2635}
2636
2638 const std::optional<UInt256>& z1, const std::optional<UInt256>& z2) {
2639 int z1_bits_len = static_cast<int>(half_n1().bit_length());
2640 int z2_bits_len = static_cast<int>(half_n2().bit_length());
2641 std::vector<int> z1_values(static_cast<std::size_t>(z1_bits_len), -1);
2642 std::vector<int> z2_values(static_cast<std::size_t>(z2_bits_len), -1);
2643 if (z1.has_value() && z2.has_value()) {
2644 Result<std::vector<int>> z1_result = key_to_bits(*z1, half_n1());
2645 if (!z1_result.has_value()) {
2646 return unexpected_error(z1_result.error(), "circuit_main:key_to_bits_z1");
2647 }
2648 Result<std::vector<int>> z2_result = key_to_bits(*z2, half_n2());
2649 if (!z2_result.has_value()) {
2650 return unexpected_error(z2_result.error(), "circuit_main:key_to_bits_z2");
2651 }
2652 z1_values = *z1_result;
2653 z2_values = *z2_result;
2654 }
2655 std::vector<Expr> z1_bits;
2656 std::vector<Expr> z2_bits;
2657 z1_bits.reserve(z1_values.size());
2658 z2_bits.reserve(z2_values.size());
2659 for (int bit : z1_values) {
2660 z1_bits.push_back(transcript.boolean(transcript.secret(bit < 0 ? std::nullopt : std::optional<FieldElement>(FieldElement::from_int(bit)))));
2661 }
2662 for (int bit : z2_values) {
2663 z2_bits.push_back(transcript.boolean(transcript.secret(bit < 0 ? std::nullopt : std::optional<FieldElement>(FieldElement::from_int(bit)))));
2664 }
2665 std::size_t n_bits = z1_bits.size() + z2_bits.size();
2666 Expr out_p1x = circuit_ec_multiply_x(curve1(), transcript, generator1(), z1_bits);
2667 Expr out_p2x = circuit_ec_multiply_x(curve2(), transcript, generator2(), z2_bits);
2668 Expr out_x1 = circuit_ec_multiply_x(curve1(), transcript, m1, z1_bits);
2669 Expr out_x2 = circuit_ec_multiply_x(curve2(), transcript, m2, z2_bits);
2670 return CircuitMainResult{circuit_combine(transcript, out_x1, out_x2), out_p1x, out_p2x, n_bits};
2671}
2672
2673} // namespace
2674
2675namespace purify {
2676
2678 const NativeBulletproofCircuit& circuit,
2679 std::span<const unsigned char> statement_binding) {
2680 return ::circuit_binding_digest(circuit, statement_binding);
2681}
2682
2685 std::span<const unsigned char> statement_binding) {
2686 return ::circuit_binding_digest(circuit, statement_binding);
2687}
2688
2689} // namespace purify
int purify_bulletproof_prove_circuit_with_resources(purify_bulletproof_backend_resources *resources, const purify_bulletproof_circuit_view *circuit, const purify_bulletproof_assignment_view *assignment, const unsigned char *blinds32, const unsigned char value_gen33[33], const unsigned char nonce32[32], const unsigned char *extra_commit, size_t extra_commit_len, unsigned char *commitments_out33, unsigned char *proof_out, size_t *proof_len)
int purify_bulletproof_verify_circuit(purify_secp_context *context, const purify_bulletproof_circuit_view *circuit, const unsigned char *commitments33, const unsigned char value_gen33[33], const unsigned char *extra_commit, size_t extra_commit_len, const unsigned char *proof, size_t proof_len)
int purify_bulletproof_verify_circuit_with_resources(purify_bulletproof_backend_resources *resources, const purify_bulletproof_circuit_view *circuit, const unsigned char *commitments33, const unsigned char value_gen33[33], const unsigned char *extra_commit, size_t extra_commit_len, const unsigned char *proof, size_t proof_len)
int purify_bulletproof_prove_circuit(purify_secp_context *context, const purify_bulletproof_circuit_view *circuit, const purify_bulletproof_assignment_view *assignment, const unsigned char *blinds32, const unsigned char value_gen33[33], const unsigned char nonce32[32], const unsigned char *extra_commit, size_t extra_commit_len, unsigned char *commitments_out33, unsigned char *proof_out, size_t *proof_len)
int purify_bulletproof_prove_circuit_assume_valid(purify_secp_context *context, const purify_bulletproof_circuit_view *circuit, const purify_bulletproof_assignment_view *assignment, const unsigned char *blinds32, const unsigned char value_gen33[33], const unsigned char nonce32[32], const unsigned char *extra_commit, size_t extra_commit_len, unsigned char *commitments_out33, unsigned char *proof_out, size_t *proof_len)
int purify_bulletproof_prove_circuit_assume_valid_with_resources(purify_bulletproof_backend_resources *resources, const purify_bulletproof_circuit_view *circuit, const purify_bulletproof_assignment_view *assignment, const unsigned char *blinds32, const unsigned char value_gen33[33], const unsigned char nonce32[32], const unsigned char *extra_commit, size_t extra_commit_len, unsigned char *commitments_out33, unsigned char *proof_out, size_t *proof_len)
void purify_bulletproof_backend_resources_destroy(purify_bulletproof_backend_resources *resources)
purify_bulletproof_backend_resources * purify_bulletproof_backend_resources_create(purify_secp_context *context, size_t n_gates)
purify_bulletproof_backend_resources * purify_bulletproof_backend_resources_clone(const purify_bulletproof_backend_resources *resources)
size_t purify_bulletproof_required_proof_size(size_t n_gates)
C ABI bridging Purify C++ code to secp256k1-zkp BPPP functionality.
struct purify_bulletproof_backend_resources purify_bulletproof_backend_resources
struct purify_bulletproof_circuit_view purify_bulletproof_circuit_view
struct purify_bulletproof_assignment_view purify_bulletproof_assignment_view
Native Bulletproof-style circuit types and witness serialization helpers.
bool replace_and_insert(Expr &expr, Symbol symbol)
Detects simple witness aliases and records them for later assignment lowering.
Status from_transcript(const Transcript &transcript, std::size_t n_bits, std::size_t minimum_gate_count=1)
Imports a symbolic transcript with a fixed power-of-two gate floor.
Status bind_output_to_commitment(Expr output)
Binds a scalar expression to public commitment slot zero.
bool evaluate(const WitnessAssignments &vars, const FieldElement &commitment) const
Evaluates the lowered symbolic constraints with a concrete commitment value.
std::string to_string() const
Renders the lowered circuit in the legacy textual verifier format.
void add_assignment(Symbol symbol, Expr expr)
Adds one symbolic wire assignment to the lowering state.
void replace_expr_v_with_bp_var(Expr &expr)
Rewrites transcript variable names to their eventual Bulletproof wire aliases.
Status add_pubkey_and_out(const UInt512 &pubkey, Expr p1x, Expr p2x, Expr out)
Binds packed public-key coordinates and the output commitment into explicit constraints.
NativeBulletproofCircuit native_circuit() const
Builds the native sparse circuit object from the lowered assignments and constraints.
Result< BulletproofAssignmentData > assignment_data(const WitnessAssignments &vars) const
Materializes the witness columns expected by the native circuit representation.
Result< Bytes > serialize_assignment(const WitnessAssignments &vars) const
Serializes the derived witness assignment using the legacy blob format.
Minimal elliptic-curve arithmetic over the Purify base field.
Definition curve.hpp:46
AffinePoint affine(const JacobianPoint &point) const
Converts a Jacobian point to affine coordinates.
Definition curve.cpp:91
bool has_value() const noexcept
Definition expected.hpp:170
Caller-owned cache for reusable legacy Bulletproof backend resources keyed by gate count.
ExperimentalBulletproofBackendCache & operator=(const ExperimentalBulletproofBackendCache &)=delete
purify_bulletproof_backend_resources * get_or_create(std::size_t n_gates, purify_secp_context *secp_context)
Returns cached backend resources for this gate count, creating them on first use.
Result< ExperimentalBulletproofBackendCache > clone_for_thread(std::size_t n_gates) const
Clones one warmed backend-resource entry for independent use on another thread.
ExprBuilder & add(const FieldElement &value)
Adds a constant field term to the pending affine expression.
Definition expr.cpp:183
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
Symbolic affine expression over indexed variables and field coefficients.
Definition expr.hpp:73
const FieldElement & constant() const
Returns the constant term of the affine expression.
Definition expr.hpp:88
std::vector< Term > & linear()
Returns mutable access to the sorted linear term list.
Definition expr.hpp:93
static Expr variable(Symbol symbol)
Returns a single-variable expression with coefficient one.
Definition expr.cpp:110
Field element modulo the backend scalar field used by this implementation.
Definition numeric.hpp:834
static Result< FieldElement > try_from_uint256(const UInt256 &value)
Converts a canonical 256-bit unsigned integer into the scalar field representation.
Definition numeric.cpp:69
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
bool is_zero() const
Returns true when the element is zero.
Definition numeric.cpp:104
static FieldElement zero()
Returns the additive identity of the scalar field.
Definition numeric.cpp:32
std::array< unsigned char, 32 > to_bytes_be() const
Serializes the field element in big-endian form.
Definition numeric.cpp:84
Public-key-agnostic native verifier-circuit template.
Result< BulletproofAssignmentData > sum_assignments(std::span< const UInt512 > public_keys, std::span< const BulletproofAssignmentData > assignments) const
Validates and concatenates local assignments for instantiate_sum.
Result< NativeBulletproofCircuit::PackedWithSlack > instantiate_packed(const UInt512 &pubkey) const
Result< NativeBulletproofCircuit > instantiate(const UInt512 &pubkey) const
Result< bool > partial_evaluate(const BulletproofAssignmentData &assignment) const
Evaluates only the public-key-agnostic base circuit cached inside the template.
Result< Bytes > integrity_digest() const
Returns a stable digest of the packed base circuit plus late-bound expressions.
static NativeBulletproofCircuitTemplate from_parts(NativeBulletproofCircuit::PackedWithSlack base_packed, Expr p1x, Expr p2x, Expr out)
Builds a template from a lowered base circuit plus late-bound public expressions.
Result< bool > final_evaluate(const BulletproofAssignmentData &assignment, const UInt512 &pubkey) const
Evaluates only the late-bound public-key/output constraints against one assignment.
Result< NativeBulletproofCircuit > instantiate_sum(std::span< const UInt512 > public_keys) const
Builds one circuit binding the sum of distinct hosts' outputs to one commitment.
Resettable packed circuit representation backed by one aligned owning slab.
void add_right_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the right-wire matrix.
PackedWithSlack & operator=(const PackedWithSlack &other)
Result< NativeBulletproofCircuit > unpack() const
Materializes the packed circuit back into the ergonomic row-vector representation.
void add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the commitment matrix using the Bulletproof sign convention.
void add_output_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the output-wire matrix.
void reset() noexcept
Restores the packed circuit to its original base row sizes and constraint count.
NativeBulletproofCircuitRow::PackedWithSlack right_row(std::size_t gate_idx) const noexcept
Returns a read-only packed right-wire row view.
void add_left_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the left-wire matrix.
NativeBulletproofCircuitRow::PackedWithSlack left_row(std::size_t gate_idx) const noexcept
Returns a read-only packed left-wire row view.
NativeBulletproofCircuitRow::PackedWithSlack output_row(std::size_t gate_idx) const noexcept
Returns a read-only packed output-wire row view.
std::span< const FieldElement > constants() const noexcept
Returns the live constraint constants stored in the slab.
NativeBulletproofCircuitRow::PackedWithSlack commitment_row(std::size_t commitment_idx) const noexcept
Returns a read-only packed commitment row view.
std::size_t add_constraint(const FieldElement &constant=FieldElement::zero())
Appends a new linear constraint constant term and returns its index.
static Result< PackedWithSlack > from_circuit(const NativeBulletproofCircuit &circuit, const PackedSlackPlan &slack)
Packs a native circuit into one aligned slab with caller-supplied row and constraint slack.
bool evaluate(const BulletproofAssignmentData &assignment) const
Evaluates the packed circuit directly against a witness assignment.
Reusable BIP340-style tagged SHA-256 helper.
Definition curve.hpp:111
std::array< unsigned char, 32 > digest(std::span< const unsigned char > data) const
Definition curve.hpp:117
Mutable transcript used to record symbolic multiplication, division, and boolean constraints.
Definition expr.hpp:215
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
Expr boolean(const Expr &expr)
Constrains an expression to be boolean by adding x * (x - 1) = 0.
Definition expr.cpp:448
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
Expr div(const Expr &lhs, const Expr &rhs)
Allocates or reuses a division witness enforcing out * rhs = lhs.
Definition expr.cpp:424
#define PURIFY_RETURN_IF_ERROR(expr, context)
Evaluates an expected-like expression and returns the wrapped error on failure.
Definition error.hpp:329
#define PURIFY_ASSIGN_OR_RETURN(lhs, expr, context)
Evaluates an expected-like expression, binds the value to lhs, and propagates errors.
Definition error.hpp:338
std::optional< std::uint32_t > read_u32_le(std::span< const unsigned char > bytes, std::size_t offset)
Definition common.hpp:35
void append_u32_le(Bytes &out, std::uint32_t value)
Definition common.hpp:29
std::size_t circuit_n_gates(const NativeBulletproofCircuit &circuit)
Definition common.hpp:47
std::size_t circuit_n_commitments(const NativeBulletproofCircuit &circuit)
Definition common.hpp:55
Status require_secp_context(const purify_secp_context *context, const char *error_context)
Definition common.hpp:56
FieldElement field_di()
Returns the inverse of the twist factor in the field.
Definition curve.cpp:256
const UInt256 & half_n1()
Returns floor(order_n1 / 2).
Definition curve.cpp:219
Result< Bytes > experimental_circuit_binding_digest(const NativeBulletproofCircuit &circuit, std::span< const unsigned char > statement_binding)
ExprPoint circuit_3bit_point(const EllipticCurve &curve, const std::array< JacobianPoint, 8 > &points, Transcript &transcript, const Expr &b0, const Expr &b1, const Expr &b2)
Selects between eight affine point constants using three boolean expression bits.
constexpr Unexpected< Error > unexpected_error(ErrorCode code, const char *context=nullptr)
Constructs an unexpected Error value from a machine-readable code.
Definition error.hpp:293
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::span< const BulletproofScalarBytes > blinds={}, ExperimentalBulletproofBackendCache *backend_cache=nullptr)
Proves a native circuit with the experimental imported Bulletproof circuit backend.
BigUInt< 8 > UInt512
512-bit unsigned integer used for private and packed public keys.
Definition numeric.hpp:821
Result< std::vector< int > > key_to_bits(UInt256 n, const UInt256 &max_value)
Encodes a scalar into the signed 3-bit window bit schedule used by the circuit.
Definition curve.cpp:413
bool size_fits_u64(std::size_t value) noexcept
Definition common.hpp:83
std::unique_ptr< purify_bulletproof_backend_resources, BulletproofBackendResourceDeleter > BulletproofBackendResourcePtr
bool is_power_of_two_size(std::size_t value) noexcept
Definition common.hpp:94
Result< std::uint64_t > narrow_size_to_u64(std::size_t value, const char *context)
Definition common.hpp:87
Result< std::pair< UInt256, UInt256 > > unpack_public(const UInt512 &packed)
Splits a packed public key into its two x-coordinates.
Definition curve.cpp:360
ErrorCode
Machine-readable error codes shared across the library.
Definition error.hpp:42
const UInt256 & half_n2()
Returns floor(order_n2 / 2).
Definition curve.cpp:224
bool checked_mul_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
Definition common.hpp:71
Expr circuit_combine(Transcript &transcript, const Expr &x1, const Expr &x2)
Builds the symbolic Purify output combiner over two x-coordinates.
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)
Verifies a proof produced by prove_experimental_circuit against the same native circuit and ordered o...
ExprPoint circuit_ec_add(Transcript &transcript, const ExprPoint &p1, const ExprPoint &p2)
Symbolically adds two affine elliptic-curve points.
BigUInt< 4 > UInt256
256-bit unsigned integer used for field elements and curve orders.
Definition numeric.hpp:817
FieldElement field_a()
Returns the shared Weierstrass a coefficient used by Purify.
Definition curve.cpp:244
std::array< unsigned char, 33 > BulletproofGeneratorBytes
Expr circuit_ec_add_x(Transcript &transcript, const ExprPoint &p1, const ExprPoint &p2)
Symbolically adds two affine points and returns only the resulting x-coordinate.
const EllipticCurve & curve1()
Returns the first Purify curve instance.
Definition curve.cpp:261
Expr circuit_ec_multiply_x(const EllipticCurve &curve, Transcript &transcript, const JacobianPoint &point, const std::vector< Expr > &bits)
Builds the symbolic x-coordinate multiplication gadget for one curve point.
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)
Builds the full symbolic Purify circuit from message points and optional witness scalars.
void best_effort_reserve_mul(std::vector< T > &out, std::size_t lhs, std::size_t rhs)
Definition common.hpp:115
Expected< T, Error > Result
Expected-returning convenience alias for Purify value-producing APIs.
Definition error.hpp:99
const JacobianPoint & generator1()
Returns the fixed generator for the first curve.
Definition curve.cpp:282
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
constexpr std::string_view to_string(ErrorCategory category) noexcept
Returns a stable programmatic name for an error category.
Definition error.hpp:146
Expr circuit_1bit(const std::array< FieldElement, 2 > &values, Transcript &transcript, const Expr &x)
Selects one of two field constants using a single boolean expression bit.
std::pair< Expr, Expr > ExprPoint
Symbolic affine point represented as independent x and y expressions.
std::array< unsigned char, 33 > BulletproofPointBytes
Expected< void, Error > Status
Expected-returning convenience alias for Purify status-only APIs.
Definition error.hpp:102
std::array< unsigned char, 32 > BulletproofScalarBytes
FieldElement field_b()
Returns the shared Weierstrass b coefficient used by Purify.
Definition curve.cpp:248
std::vector< unsigned char > Bytes
Dynamically sized byte string used for messages, serialized witnesses, and proofs.
Definition common.hpp:99
bool size_fits_u32(std::size_t value) noexcept
Definition common.hpp:79
const EllipticCurve & curve2()
Returns the second Purify curve instance.
Definition curve.cpp:266
Result< ExperimentalBulletproofProof > prove_experimental_circuit_assume_valid(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::span< const BulletproofScalarBytes > blinds, ExperimentalBulletproofBackendCache *backend_cache)
const JacobianPoint & generator2()
Returns the fixed generator for the second curve.
Definition curve.cpp:293
ExprPoint circuit_ec_multiply_point(const EllipticCurve &curve, Transcript &transcript, const JacobianPoint &point, const std::vector< Expr > &bits)
Builds the symbolic affine-point multiplication gadget for one curve point.
Expr circuit_3bit(const std::array< FieldElement, 8 > &values, Transcript &transcript, const Expr &x, const Expr &y, const Expr &z)
Selects one of eight field constants using three boolean expression bits.
ExprPoint circuit_1bit_point(const EllipticCurve &curve, const std::array< JacobianPoint, 2 > &points, Transcript &transcript, const Expr &b0)
Selects between two affine point constants using one boolean expression bit.
ExprPoint circuit_optionally_negate_ec(const ExprPoint &point, Transcript &transcript, const Expr &negate_bit)
Conditionally negates an elliptic-curve point encoded as symbolic affine expressions.
bool checked_add_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
Definition common.hpp:63
std::vector< FieldElement, detail::SecureAllocator< FieldElement > > BulletproofWitnessColumn
ExprPoint circuit_2bit_point(const EllipticCurve &curve, const std::array< JacobianPoint, 4 > &points, Transcript &transcript, const Expr &b0, const Expr &b1)
Selects between four affine point constants using two boolean expression bits.
Expr circuit_2bit(const std::array< FieldElement, 4 > &values, Transcript &transcript, const Expr &x, const Expr &y)
Selects one of four field constants using two boolean expression bits.
Secret-owning Purify key material wrappers.
std::size_t bit_length() const
Returns the index of the highest set bit plus one.
Definition numeric.hpp:493
Columnar witness assignment compatible with the native Bulletproof circuit layout.
BulletproofWitnessColumn left
BulletproofWitnessColumn output
BulletproofWitnessColumn commitments
BulletproofWitnessColumn right
Result< Bytes > serialize() const
Serializes the witness columns in the legacy assignment blob format.
void operator()(purify_bulletproof_backend_resources *resources) const noexcept
Result bundle returned by the main symbolic Purify circuit construction.
std::unordered_map< std::size_t, BulletproofBackendResourcePtr > resources
Experimental single-proof wrapper over the imported legacy Bulletproof circuit backend.
std::vector< BulletproofPointBytes > commitments
static constexpr unsigned char kSerializationVersion
static Result< ExperimentalBulletproofProof > deserialize(std::span< const unsigned char > bytes)
Jacobian point representation used for curve arithmetic.
Definition curve.hpp:17
Non-owning packed row view used by NativeBulletproofCircuit::PackedWithSlack.
One sparse row of circuit coefficients.
void add(std::size_t idx, const FieldElement &scalar)
Appends a sparse coefficient to the row, skipping zero entries.
std::vector< NativeBulletproofCircuitTerm > entries
One sparse matrix entry in a native circuit row.
Native in-memory representation of a Bulletproof-style arithmetic circuit.
std::size_t add_constraint(const FieldElement &constant=FieldElement::zero())
Appends a new linear constraint constant term and returns its index.
std::vector< NativeBulletproofCircuitRow > wv
void resize(std::size_t gates, std::size_t commitments, std::size_t bits=0)
Reinitializes the circuit shape and clears all accumulated constraints.
bool evaluate(const BulletproofAssignmentData &assignment) const
Evaluates the circuit against a witness assignment and checks all gate and row equations.
std::vector< NativeBulletproofCircuitRow > wr
bool has_valid_shape() const
Checks declared dimensions and every sparse constraint index.
std::vector< NativeBulletproofCircuitRow > wl
void add_left_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the left-wire matrix.
std::vector< NativeBulletproofCircuitRow > wo
Result< PackedWithSlack > pack_with_slack() const
Packs the circuit into one aligned slab with no additional row or constraint slack.
void add_right_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the right-wire matrix.
void add_output_term(std::size_t gate_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the output-wire matrix.
std::vector< FieldElement > c
void add_commitment_term(std::size_t commitment_idx, std::size_t constraint_idx, const FieldElement &scalar)
Adds a coefficient to the commitment matrix using the Bulletproof sign convention.
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
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
const purify_bulletproof_row_view * wr
const purify_bulletproof_row_view * wo
const purify_bulletproof_row_view * wl
const purify_bulletproof_row_view * wv
const unsigned char * c32
int PURIFY_UINT_FN bit(const uint64_t value[PURIFY_UINT_WORDS], size_t index)
Definition uint_impl.h:133