25#include <unordered_map>
39 std::unique_ptr<purify_bulletproof_backend_resources, BulletproofBackendResourceDeleter>;
42 std::unordered_map<std::size_t, BulletproofBackendResourcePtr>
resources;
56 if (impl_ !=
nullptr) {
57 impl_->resources.clear();
62 return impl_ !=
nullptr ? impl_->resources.
size() : 0;
66 std::size_t n_gates)
const {
68 if (impl_ ==
nullptr) {
72 auto it = impl_->resources.find(n_gates);
73 if (it == impl_->resources.end()) {
79 if (cloned ==
nullptr) {
82 "ExperimentalBulletproofBackendCache::clone_for_thread:backend_resources");
91 if (impl_ ==
nullptr || secp_context ==
nullptr) {
95 auto it = impl_->resources.find(n_gates);
96 if (it != impl_->resources.end()) {
97 return it->second.get();
102 if (created ==
nullptr) {
107 return inserted.first->second.get();
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");
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);
152struct ResolvedValues {
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) {}
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()) {
169 return witness[index];
170 case SymbolKind::Left:
171 if (index >= left.size()) {
175 case SymbolKind::Right:
176 if (index >= right.size()) {
180 case SymbolKind::Output:
181 if (index >= output.size()) {
184 return output[index];
185 case SymbolKind::Commitment:
186 if (index >= commitment.size()) {
189 return commitment[index];
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()) {
201 witness[index] = value;
203 case SymbolKind::Left:
204 if (index >= left.size()) {
209 case SymbolKind::Right:
210 if (index >= right.size()) {
213 right[index] = value;
215 case SymbolKind::Output:
216 if (index >= output.size()) {
219 output[index] = value;
221 case SymbolKind::Commitment:
222 if (index >= commitment.size()) {
225 commitment[index] = value;
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()) {
239 out = out + *value * term.second;
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) {
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;
260 for (
int i = 0; i < 4; ++i) {
261 out.push_back(
static_cast<unsigned char>((value >> (8 * i)) & 0xffU));
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));
272 using SymbolRank = std::underlying_type_t<purify::SymbolKind>;
273 append_u64_le(out,
static_cast<std::uint64_t
>(
static_cast<SymbolRank
>(symbol.
kind)));
275 "append_symbol_digest:index");
276 append_u64_le(out, symbol_index);
282 out.insert(out.end(), constant.begin(), constant.end());
284 "append_expr_digest:term_count");
285 append_u64_le(out, term_count);
286 for (
const auto& term : expr.
linear()) {
288 const auto coeff = term.second.to_bytes_be();
289 out.insert(out.end(), coeff.begin(), coeff.end());
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) {
299 for (
int i = 0; i < 4; ++i) {
300 value |=
static_cast<std::uint32_t
>(bytes[offset + i]) << (8 * i);
305Bytes flatten_scalars32(std::span<const FieldElement> values) {
308 for (
const FieldElement& value : values) {
309 auto bytes = value.to_bytes_be();
310 out.insert(out.end(), bytes.begin(), bytes.end());
315template <
typename RowEntriesFn>
316Status append_row_family_digest_generic(Bytes& out, std::size_t row_count,
const RowEntriesFn& row_entries,
317 const char* 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);
323 append_u64_le(out, encoded_entry_count);
324 for (
const auto& entry : entries) {
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());
335 std::span<const unsigned char> statement_binding) {
336 static const purify::TaggedHash kCircuitBindingTag(
"Purify/ExperimentalBulletproof/CircuitV1");
339 "circuit_binding_digest:native_shape");
341 std::size_t reserve_size = 0;
344 return unexpected_error(ErrorCode::Overflow,
"circuit_binding_digest:native_reserve");
348 serialized.reserve(reserve_size);
350 "circuit_binding_digest:native_n_gates");
353 "circuit_binding_digest:native_n_commitments");
355 "circuit_binding_digest:native_n_bits");
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);
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");
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");
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");
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());
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());
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()) {
401 "circuit_binding_digest:packed_shape");
403 std::size_t reserve_size = 0;
406 return unexpected_error(ErrorCode::Overflow,
"circuit_binding_digest:packed_reserve");
410 serialized.reserve(reserve_size);
412 "circuit_binding_digest:packed_n_gates");
414 narrow_size_to_u64(circuit.n_commitments(),
"circuit_binding_digest:packed_n_commitments"),
415 "circuit_binding_digest:packed_n_commitments");
417 "circuit_binding_digest:packed_n_bits");
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);
426 [&](std::size_t i) { return circuit.left_row(i).entries_view(); },
427 "circuit_binding_digest:packed_left"),
428 "circuit_binding_digest:packed_left");
430 [&](std::size_t i) { return circuit.right_row(i).entries_view(); },
431 "circuit_binding_digest:packed_right"),
432 "circuit_binding_digest:packed_right");
434 [&](std::size_t i) { return circuit.output_row(i).entries_view(); },
435 "circuit_binding_digest:packed_output"),
436 "circuit_binding_digest:packed_output");
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());
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());
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);
465 case SymbolKind::Right:
466 circuit.add_right_term(index, constraint_idx, term.second);
468 case SymbolKind::Output:
469 circuit.add_output_term(index, constraint_idx, term.second);
471 case SymbolKind::Commitment:
472 circuit.add_commitment_term(index, constraint_idx, term.second);
474 case SymbolKind::Witness:
475 assert(
false &&
"append_constraint_to_circuit() encountered an unmapped witness symbol");
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");
487 || base.n_commitments() != 1 || !base.commitment_row(0).entries_view().empty()) {
488 return unexpected_error(ErrorCode::InvalidDimensions,
"sum_circuit_gate_count:template_shape");
490 std::size_t used_gates = 0;
492 return unexpected_error(ErrorCode::Overflow,
"sum_circuit_gate_count:used_gates");
494 std::size_t padded_gates = 1;
495 while (padded_gates < used_gates) {
497 return unexpected_error(ErrorCode::Overflow,
"sum_circuit_gate_count:padded_gates");
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");
505 for (
const auto& public_key : public_keys) {
511Status validate_sum_expression(
const Expr& expr, std::size_t member_gates) {
512 for (
const auto& [symbol, scalar] : expr.linear()) {
514 if (symbol.
kind == SymbolKind::Commitment || symbol.
kind == SymbolKind::Witness) {
515 return unexpected_error(ErrorCode::UnsupportedSymbol,
"validate_sum_expression:symbol_kind");
517 if (symbol.
index >= member_gates) {
518 return unexpected_error(ErrorCode::IndexOutOfRange,
"validate_sum_expression:gate_index");
525 std::size_t gate_offset, std::size_t member_gates,
526 std::size_t constraint_index) {
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:
534 case SymbolKind::Right:
537 case SymbolKind::Output:
540 case SymbolKind::Commitment:
541 case SymbolKind::Witness:
543 return unexpected_error(ErrorCode::UnsupportedSymbol,
"append_sum_expression:symbol_kind");
549struct FlattenedRowFamily {
550 std::vector<purify_bulletproof_row_view> views;
551 std::vector<std::size_t> indices;
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);
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; });
571 flat.indices.reserve(total_entries);
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) {
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());
587 counts.push_back(kept);
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;
602struct FlattenedCircuitView {
603 FlattenedRowFamily wl;
604 FlattenedRowFamily wr;
605 FlattenedRowFamily wo;
606 FlattenedRowFamily wv;
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);
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();
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()));
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();
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();
678struct FlattenedAssignmentView {
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);
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();
706 return circuit.n_gates();
714 return circuit.n_commitments();
717struct ResolvedBulletproofBackendResources {
721ResolvedBulletproofBackendResources resolve_bulletproof_backend_resources(
725 ResolvedBulletproofBackendResources out;
727 if (cache !=
nullptr) {
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,
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) {
752 "prove_experimental_circuit:secp_context");
753 ExperimentalBulletproofProof out;
754 if (!circuit.has_valid_shape()) {
770 return unexpected_error(ErrorCode::SizeMismatch,
"prove_experimental_circuit:blinds_size");
772 if (require_assignment_validation && !circuit.evaluate(assignment)) {
773 return unexpected_error(ErrorCode::EquationMismatch, assignment_invalid_context);
776 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
777 FlattenedAssignmentView flat_assignment = flatten_assignment_view(assignment);
779 "prove_experimental_circuit_impl:binding_digest");
781 std::size_t proof_len = proof_bytes.size();
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);
788 if (proof_len == 0) {
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));
819 proof_bytes.resize(proof_len);
820 out.proof = std::move(proof_bytes);
824Result<FieldElement> evaluate_expr_with_assignment(
const Expr& expr,
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");
835 out = out + (assignment.
left[index] * term.second);
837 case SymbolKind::Right:
838 if (index >= assignment.
right.size()) {
840 "evaluate_expr_with_assignment:right_index");
842 out = out + (assignment.
right[index] * term.second);
844 case SymbolKind::Output:
845 if (index >= assignment.
output.size()) {
847 "evaluate_expr_with_assignment:output_index");
849 out = out + (assignment.
output[index] * term.second);
851 case SymbolKind::Commitment:
854 "evaluate_expr_with_assignment:commitment_index");
856 out = out + (assignment.
commitments[index] * term.second);
858 case SymbolKind::Witness:
860 "evaluate_expr_with_assignment:witness_symbol");
881 std::size_t scalar_count = 0;
882 std::size_t serialized_size = 0;
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));
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));
902 auto write_column = [&](std::span<const FieldElement> 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());
911 append_u32_le(
static_cast<std::uint32_t
>(
commitments.size()));
912 append_u64_le(
static_cast<std::uint64_t
>(
left.size()));
924 entries.push_back({idx, scalar});
934 wl.assign(gates, {});
935 wr.assign(gates, {});
936 wo.assign(gates, {});
937 wv.assign(commitments, {});
948 const auto rows_are_valid = [&](
const std::vector<NativeBulletproofCircuitRow>& rows) {
951 if (entry.
idx >=
c.size()) {
958 return rows_are_valid(
wl)
959 && rows_are_valid(
wr)
960 && rows_are_valid(
wo)
961 && rows_are_valid(
wv);
965 c.push_back(constant);
970 add_row_term(
wl,
n_gates, gate_idx, constraint_idx, scalar);
974 add_row_term(
wr,
n_gates, gate_idx, constraint_idx, scalar);
978 add_row_term(
wo,
n_gates, gate_idx, constraint_idx, scalar);
996 for (std::size_t i = 0; i <
n_gates; ++i) {
997 if (assignment.
left[i] * assignment.
right[i] != assignment.
output[i]) {
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()) {
1010 for (std::size_t i = 0; i < rows.size(); ++i) {
1011 if (negate_values) {
1015 if (entry.idx >= acc.size()) {
1018 acc[entry.idx] = acc[entry.idx] + entry.scalar * negated;
1023 if (entry.idx >= acc.size()) {
1026 acc[entry.idx] = acc[entry.idx] + entry.scalar * values[i];
1031 if (!accumulate(
wl, assignment.
left) || !accumulate(
wr, assignment.
right) || !accumulate(
wo, assignment.
output)) {
1038 for (std::size_t i = 0; i <
c.size(); ++i) {
1039 if (acc[i] !=
c[i]) {
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);
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));
1060std::byte* NativeBulletproofCircuit::PackedWithSlack::allocate_storage(std::size_t bytes) {
1064 return static_cast<std::byte*
>(::operator
new(bytes, std::align_val_t(kPackedStorageAlignment)));
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_);
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();
1093 if (
this == &other) {
1097 *
this = std::move(copy);
1103 if (
this == &other) {
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();
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)
1131 std::size_t terms_bytes = 0;
1135 std::size_t term_region_end = 0;
1137 || !checked_align_up(term_region_end,
alignof(FieldElement), constant_bytes_offset)) {
1140 std::size_t constants_bytes = 0;
1141 if (!
checked_mul_size(constraint_capacity,
sizeof(FieldElement), constants_bytes)) {
1144 return checked_add_size(constant_bytes_offset, constants_bytes, storage_bytes);
1147void NativeBulletproofCircuit::PackedWithSlack::reset_to_empty() noexcept {
1152 constraint_size_ = 0;
1153 constraint_base_size_ = 0;
1154 constraint_capacity_ = 0;
1156 term_bytes_offset_ = 0;
1157 constant_bytes_offset_ = 0;
1162 if (constraint_base_size_ > constraint_size_ || constraint_size_ > constraint_capacity_) {
1165 std::size_t row_count = 0;
1166 if (!packed_row_count(n_gates_, n_commitments_, row_count)) {
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)) {
1176 if (term_bytes_offset_ != expected_term_offset || constant_bytes_offset_ != expected_constant_offset
1177 || storage_bytes_ != expected_storage_bytes) {
1180 if ((storage_ ==
nullptr) != (storage_bytes_ == 0)) {
1183 if (storage_bytes_ == 0) {
1184 return row_count == 0 && term_capacity_ == 0 && constraint_capacity_ == 0;
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) {
1195 if (header.offset != term_cursor) {
1198 if (term_cursor > term_capacity_ || header.capacity > term_capacity_ - term_cursor) {
1202 for (std::size_t j = 0; j < header.size; ++j) {
1203 if (terms[header.offset + j].
idx >= constraint_size_) {
1207 term_cursor += header.capacity;
1209 return term_cursor == term_capacity_;
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;
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;
1230 case RowFamily::Left:
1233 case RowFamily::Right:
1236 case RowFamily::Output:
1237 base = 2 * n_gates_;
1239 case RowFamily::Commitment:
1240 base = 3 * n_gates_;
1243 return headers[base + idx];
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;
1251 case RowFamily::Left:
1254 case RowFamily::Right:
1257 case RowFamily::Output:
1258 base = 2 * n_gates_;
1260 case RowFamily::Commitment:
1261 base = 3 * n_gates_;
1264 return headers[base + idx];
1267NativeBulletproofCircuitTerm* NativeBulletproofCircuit::PackedWithSlack::term_data() noexcept {
1268 if (term_capacity_ == 0) {
1271 return std::launder(
reinterpret_cast<NativeBulletproofCircuitTerm*
>(raw_storage_bytes() + term_bytes_offset_));
1274const NativeBulletproofCircuitTerm* NativeBulletproofCircuit::PackedWithSlack::term_data() const noexcept {
1275 if (term_capacity_ == 0) {
1278 return std::launder(
reinterpret_cast<const NativeBulletproofCircuitTerm*
>(raw_storage_bytes() + term_bytes_offset_));
1281FieldElement* NativeBulletproofCircuit::PackedWithSlack::constant_data() noexcept {
1282 if (constraint_capacity_ == 0) {
1285 return std::launder(
reinterpret_cast<FieldElement*
>(raw_storage_bytes() + constant_bytes_offset_));
1288const FieldElement* NativeBulletproofCircuit::PackedWithSlack::constant_data() const noexcept {
1289 if (constraint_capacity_ == 0) {
1292 return std::launder(
reinterpret_cast<const FieldElement*
>(raw_storage_bytes() + constant_bytes_offset_));
1295unsigned char* NativeBulletproofCircuit::PackedWithSlack::raw_storage_bytes() noexcept {
1296 return reinterpret_cast<unsigned char*
>(storage_.get());
1299const unsigned char* NativeBulletproofCircuit::PackedWithSlack::raw_storage_bytes() const noexcept {
1300 return reinterpret_cast<const unsigned char*
>(storage_.get());
1303void NativeBulletproofCircuit::PackedWithSlack::start_storage_lifetimes() noexcept {
1304 if (storage_ ==
nullptr) {
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);
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_);
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_);
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};
1332 assert(constraint_size_ < constraint_capacity_ &&
"PackedWithSlack constraint capacity exceeded");
1336 return constraint_size_ - 1;
1339void NativeBulletproofCircuit::PackedWithSlack::add_row_term(RowFamily family, std::size_t expected_size,
1340 std::size_t row_idx, std::size_t constraint_idx,
1342 (void)expected_size;
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};
1358 add_row_term(RowFamily::Left, n_gates_, gate_idx, constraint_idx, scalar);
1363 add_row_term(RowFamily::Right, n_gates_, gate_idx, constraint_idx, scalar);
1368 add_row_term(RowFamily::Output, n_gates_, gate_idx, constraint_idx, scalar);
1373 add_row_term(RowFamily::Commitment, n_commitments_, commitment_idx, constraint_idx, scalar.
negate());
1378 return row_view(row_header(RowFamily::Left, gate_idx));
1383 return row_view(row_header(RowFamily::Right, gate_idx));
1388 return row_view(row_header(RowFamily::Output, gate_idx));
1393 return row_view(row_header(RowFamily::Commitment, commitment_idx));
1397 return std::span<const FieldElement>(constant_data(), constraint_size_);
1404 if (assignment.
left.size() != n_gates_ || assignment.
right.size() != n_gates_ || assignment.
output.size() != n_gates_) {
1407 if (assignment.
commitments.size() != n_commitments_) {
1410 for (std::size_t i = 0; i < n_gates_; ++i) {
1411 if (assignment.
left[i] * assignment.
right[i] != assignment.
output[i]) {
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) {
1424 for (std::size_t i = 0; i < row_count; ++i) {
1425 const PackedRowHeader& header = row_header(family, i);
1427 if (header.size == 0) {
1431 for (std::size_t j = 0; j < header.size; ++j) {
1433 if (entry.
idx >= acc.size()) {
1436 acc[entry.
idx] = acc[entry.
idx] + (entry.
scalar * factor);
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)) {
1447 for (std::size_t i = 0; i < constraint_size_; ++i) {
1448 if (acc[i] != constant_data()[i]) {
1460 if (constraint_size_ != 0) {
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();
1472 rows[i].entries.assign(all_terms + header.offset,
1473 all_terms + header.offset +
static_cast<std::ptrdiff_t
>(header.size));
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_);
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) {
1497 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wl");
1499 return unexpected_error(wl_status.
error(),
"NativeBulletproofCircuit::PackedWithSlack::from_circuit:wl");
1502 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wr");
1504 return unexpected_error(wr_status.
error(),
"NativeBulletproofCircuit::PackedWithSlack::from_circuit:wr");
1507 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wo");
1509 return unexpected_error(wo_status.
error(),
"NativeBulletproofCircuit::PackedWithSlack::from_circuit:wo");
1512 "NativeBulletproofCircuit::PackedWithSlack::from_circuit:wv");
1514 return unexpected_error(wv_status.
error(),
"NativeBulletproofCircuit::PackedWithSlack::from_circuit:wv");
1518 packed.n_gates_ = circuit.
n_gates;
1520 packed.n_bits_ = circuit.
n_bits;
1521 packed.constraint_size_ = circuit.
c.size();
1522 packed.constraint_base_size_ = circuit.
c.size();
1527 std::size_t row_count = 0;
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;
1538 || !
checked_add_size(total_term_capacity, row_capacity, total_term_capacity)) {
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)) {
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_)) {
1555 packed.storage_.reset(allocate_storage(packed.storage_bytes_));
1556 packed.start_storage_lifetimes();
1558 PackedWithSlack::PackedRowHeader* headers =
1559 row_count == 0 ? nullptr : std::launder(
reinterpret_cast<PackedWithSlack::PackedRowHeader*
>(packed.raw_storage_bytes()));
1561 if (packed.constraint_capacity_ != 0) {
1563 std::copy(circuit.
c.begin(), circuit.
c.end(),
constants);
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));
1581 term_cursor += header.capacity;
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");
1608 std::size_t commitment_bytes = 0;
1609 std::size_t serialized_size = 0;
1617 out.reserve(serialized_size);
1619 append_u32_le(out,
static_cast<std::uint32_t
>(
proof.size()));
1620 append_u32_le(out,
static_cast<std::uint32_t
>(
commitments.size()));
1622 out.insert(out.end(), commitment.begin(), commitment.end());
1624 out.insert(out.end(),
proof.begin(),
proof.end());
1629 if (bytes.size() < 9) {
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) {
1642 const std::size_t payload_size = bytes.size() - 9;
1643 if (*commitment_count > payload_size / 33) {
1646 const std::size_t commitment_bytes = std::size_t{*commitment_count} * 33;
1647 if (*proof_size != payload_size - commitment_bytes) {
1652 std::size_t offset = 9;
1654 std::copy_n(bytes.begin() +
static_cast<std::ptrdiff_t
>(offset), 33, commitment.begin());
1657 out.
proof.assign(bytes.begin() +
static_cast<std::ptrdiff_t
>(offset), bytes.end());
1667 std::span<const unsigned char> statement_binding,
1668 std::span<const BulletproofScalarBytes> blinds,
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");
1687 std::span<const unsigned char> statement_binding,
1688 std::span<const BulletproofScalarBytes> blinds,
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");
1707 std::span<const unsigned char> statement_binding,
1708 std::span<const BulletproofScalarBytes> blinds,
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");
1726 std::span<const unsigned char> statement_binding,
1729 "verify_experimental_circuit:secp_context");
1739 if (proof.
commitments.size() != circuit_n_commitments(circuit)) {
1742 if (proof.
proof.empty()) {
1746 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
1748 "verify_experimental_circuit:binding_digest");
1749 ResolvedBulletproofBackendResources resolved =
1750 resolve_bulletproof_backend_resources(circuit.
n_gates, secp_context, backend_cache);
1753 resources !=
nullptr
1755 value_generator.data(), binding_digest.data(),
1756 binding_digest.size(), proof.
proof.data(),
1757 proof.
proof.size()) != 0
1759 value_generator.data(), binding_digest.data(),
1760 binding_digest.size(), proof.
proof.data(),
1761 proof.
proof.size()) != 0;
1770 std::span<const unsigned char> statement_binding,
1773 "verify_experimental_circuit:packed_secp_context");
1783 if (proof.
commitments.size() != circuit_n_commitments(circuit)) {
1786 if (proof.
proof.empty()) {
1790 FlattenedCircuitView flat_circuit = flatten_circuit_view(circuit);
1792 "verify_experimental_circuit:packed_binding_digest");
1793 ResolvedBulletproofBackendResources resolved =
1794 resolve_bulletproof_backend_resources(circuit.
n_gates(), secp_context, backend_cache);
1797 resources !=
nullptr
1799 value_generator.data(), binding_digest.data(),
1800 binding_digest.size(), proof.
proof.data(),
1801 proof.
proof.size()) != 0
1803 value_generator.data(), binding_digest.data(),
1804 binding_digest.size(), proof.
proof.data(),
1805 proof.
proof.size()) != 0;
1810 for (
auto& term : expr.
linear()) {
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];
1820 if (!expr.
linear().empty()) {
1823 && expr.
linear().size() == 1
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});
1839 assignments_.push_back({symbol, std::move(expr), is_v});
1844 std::size_t minimum_gate_count) {
1846 minimum_gate_count >
1847 static_cast<std::size_t
>(
1848 std::numeric_limits<std::uint32_t>::max())) {
1851 "BulletproofTranscript::from_transcript:minimum_gate_count");
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();
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];
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)) {
1874 std::uint32_t witness_index = term.first.index;
1875 if (witness_index >= witness_to_a_.size() || witness_to_a_[witness_index].has_value()) {
1878 if (!seen_transcript_vars[witness_index]) {
1879 unmapped_transcript_vars.push_back(witness_index);
1880 seen_transcript_vars[witness_index] =
true;
1885 std::size_t total_gates = 0;
1890 "BulletproofTranscript::from_transcript:total_gates");
1893 static_cast<std::size_t
>(
1894 std::numeric_limits<std::uint32_t>::max())) {
1897 "BulletproofTranscript::from_transcript:total_gate_count");
1900 while (n_muls_ < std::max<std::size_t>(1, total_gates)) {
1901 if (n_muls_ > std::numeric_limits<std::size_t>::max() / 2) {
1904 "BulletproofTranscript::from_transcript:natural_gate_count");
1908 n_muls_ = std::max(n_muls_, minimum_gate_count);
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);
1918 for (std::size_t i = total_gates; i < n_muls_; ++i) {
1919 std::uint32_t gate_symbol = narrow_symbol_index(i);
1925 for (
const Expr& eq : transcript.
eqs()) {
1928 if (contains_transcript_var(lowered)) {
1931 constraints_.push_back({lowered,
Expr(0)});
1940 "BulletproofTranscript::bind_output_to_commitment:transcript");
1943 for (
const auto& [symbol, scalar] : output.
linear()) {
1945 switch (symbol.
kind) {
1949 if (symbol.
index >= n_muls_) {
1952 "BulletproofTranscript::bind_output_to_commitment:wire_index");
1959 "BulletproofTranscript::bind_output_to_commitment:symbol");
1963 "BulletproofTranscript::bind_output_to_commitment:symbol_kind");
1966 constraints_.push_back(
1974 return unexpected_error(unpacked.
error(),
"BulletproofTranscript::add_pubkey_and_out:unpack_public");
1978 auto parts = expr.split();
1981 return unexpected_error(constant.
error(),
"BulletproofTranscript::add_pubkey_and_out:field_constant");
1983 constraints_.push_back({parts.second,
Expr(*constant) - parts.first});
1997 output_status.
error(),
1998 "BulletproofTranscript::add_pubkey_and_out:output");
2004 std::size_t n_constraints = 0;
2005 for (
const auto& assignment : assignments_) {
2006 if (!assignment.is_v) {
2010 n_constraints += constraints_.size();
2011 std::ostringstream out;
2012 out << n_muls_ <<
"," << n_commitments_ <<
"," << n_bits_ <<
"," << (n_constraints - 2 * n_bits_) <<
";";
2014 for (
const auto& assignment : assignments_) {
2015 if (!assignment.is_v) {
2016 if (i < 2 * n_bits_) {
2020 auto parts = assignment.expr.split();
2021 out << assignment.symbol.to_string();
2022 if (!parts.second.linear().empty()) {
2023 out <<
" + " << (-parts.second).
to_string();
2025 out <<
" = " << parts.first.to_string() <<
";";
2028 for (
const auto& constraint : constraints_) {
2029 out << constraint.first.to_string() <<
" = " << constraint.second.to_string() <<
";";
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];
2042 for (
const auto& item : witness_to_a_order_) {
2043 if (item.first >= values.witness.size() || !values.witness[item.first].has_value()) {
2046 if (!values.set(item.second, *values.witness[item.first])) {
2050 for (
const auto& assignment : assignments_) {
2055 if (!values.set(assignment.symbol, *evaluated)) {
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()) {
2063 if (*values.left[i] * *values.right[i] != *values.output[i]) {
2067 for (
const auto& constraint : constraints_) {
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_);
2087 std::count_if(assignments_.begin(), assignments_.end(),
2088 [](
const auto& assignment) { return !assignment.is_v; })
2089 + constraints_.size());
2091 for (
const auto& assignment : assignments_) {
2092 if (!assignment.is_v) {
2093 append_constraint_to_circuit(circuit,
Expr::variable(assignment.symbol), assignment.expr);
2096 for (
const auto& constraint : constraints_) {
2097 append_constraint_to_circuit(circuit, constraint.first, constraint.second);
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;
2116 if (!base_packed_.has_valid_shape()) {
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()) {
2125 return base_packed_.evaluate(assignment);
2129 const UInt512& pubkey)
const {
2130 if (!base_packed_.has_valid_shape()) {
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()) {
2141 return unexpected_error(unpacked.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:unpack_public");
2145 return unexpected_error(expected_p1.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:expected_p1");
2149 return unexpected_error(expected_p2.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:expected_p2");
2153 return unexpected_error(actual_p1.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:actual_p1");
2157 return unexpected_error(actual_p2.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:actual_p2");
2161 return unexpected_error(actual_out.
error(),
"NativeBulletproofCircuitTemplate::final_evaluate:actual_out");
2163 return *actual_p1 == *expected_p1
2164 && *actual_p2 == *expected_p2
2169 if (!base_packed_.has_valid_shape()) {
2173 static const TaggedHash kTemplateDigestTag(
"Purify/VerifierCircuitTemplate/V1");
2175 "NativeBulletproofCircuitTemplate::integrity_digest:circuit_binding_digest");
2177 "NativeBulletproofCircuitTemplate::integrity_digest:p1x");
2179 "NativeBulletproofCircuitTemplate::integrity_digest:p2x");
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());
2190 return unexpected_error(unpacked.
error(),
"NativeBulletproofCircuitTemplate::instantiate_packed:unpack_public");
2195 auto append_pubkey_constraint = [&](
const UInt256& packed,
const Expr& expr) ->
Status {
2196 auto parts = expr.split();
2199 return unexpected_error(constant.
error(),
"NativeBulletproofCircuitTemplate::instantiate_packed:field_constant");
2201 append_constraint_to_circuit(circuit, parts.second,
Expr(*constant) - parts.first);
2205 Status p1_status = append_pubkey_constraint(unpacked->first, p1x_);
2207 return unexpected_error(p1_status.
error(),
"NativeBulletproofCircuitTemplate::instantiate_packed:p1x");
2209 Status p2_status = append_pubkey_constraint(unpacked->second, p2x_);
2211 return unexpected_error(p2_status.
error(),
"NativeBulletproofCircuitTemplate::instantiate_packed:p2x");
2220 return unexpected_error(packed.
error(),
"NativeBulletproofCircuitTemplate::instantiate:instantiate_packed");
2222 return packed->unpack();
2226 std::span<const UInt512> public_keys)
const {
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)
2240 circuit.
c.reserve(total_constraints);
2241 const std::size_t member_gates = base_packed_.n_gates();
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");
2251 destination.
add(constraint_offset + entry.idx, entry.scalar);
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) {
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");
2270 "NativeBulletproofCircuitTemplate::instantiate_sum:unpack_public");
2271 auto append_host_coordinate = [&](
const UInt256& coordinate,
const Expr& expr) ->
Status {
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);
2278 "NativeBulletproofCircuitTemplate::instantiate_sum:p1x");
2280 "NativeBulletproofCircuitTemplate::instantiate_sum:p2x");
2284 for (std::size_t member = 0; member < public_keys.size(); ++member) {
2285 circuit.
c[sum_constraint] = circuit.
c[sum_constraint] - out_.constant();
2287 member_gates, sum_constraint),
2288 "NativeBulletproofCircuitTemplate::instantiate_sum:output_sum");
2295 std::span<const UInt512> public_keys,
2296 std::span<const BulletproofAssignmentData> assignments)
const {
2297 if (assignments.size() != public_keys.size()) {
2301 "NativeBulletproofCircuitTemplate::sum_assignments:gate_count");
2302 for (
const Expr* expr : {&p1x_, &p2x_, &out_}) {
2304 "NativeBulletproofCircuitTemplate::sum_assignments:expression_shape");
2306 for (std::size_t member = 0; member < assignments.size(); ++member) {
2308 "NativeBulletproofCircuitTemplate::sum_assignments:partial_evaluate");
2311 "NativeBulletproofCircuitTemplate::sum_assignments:invalid_assignment");
2314 "NativeBulletproofCircuitTemplate::sum_assignments:final_evaluate");
2317 "NativeBulletproofCircuitTemplate::sum_assignments:host_or_output");
2322 sum.
left.reserve(gates);
2323 sum.
right.reserve(gates);
2324 sum.
output.reserve(gates);
2326 for (
const auto& assignment : assignments) {
2327 sum.
left.insert(sum.
left.end(), assignment.
left.begin(), assignment.
left.end());
2330 output_sum = output_sum + assignment.
commitments.front();
2340 return assignment_data_impl(vars,
nullptr);
2345 return assignment_data_impl(vars, &commitment);
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];
2357 for (
const auto& item : witness_to_a_order_) {
2358 if (item.first >= values.witness.size() || !values.witness[item.first].has_value()) {
2361 if (!values.set(item.second, *values.witness[item.first])) {
2365 for (
const auto& assignment : assignments_) {
2367 if (!evaluated.has_value()) {
2368 return unexpected_error(evaluated.error(),
"BulletproofTranscript::assignment_data:evaluate_assignment");
2370 if (!values.set(assignment.symbol, *evaluated)) {
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_);
2382 for (
const auto& value : source) {
2383 if (!value.has_value()) {
2386 column.push_back(*value);
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");
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");
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");
2402 for (
const auto& value : values.commitment) {
2403 if (!value.has_value()) {
2406 assignment.commitments.push_back(*value);
2414 return unexpected_error(assignment.
error(),
"BulletproofTranscript::serialize_assignment:assignment_data");
2416 return assignment->serialize();
2419bool BulletproofTranscript::is_transcript_var(
Symbol symbol) {
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); });
2436 Expr xy = transcript.
mul(x, y);
2441 .
add_scaled(xy, values[0] + values[3] - values[1] - values[2])
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);
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])
2465 std::array<AffinePoint, 2> affine_points{curve.
affine(points[0]), curve.
affine(points[1])};
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)
2474 std::array<AffinePoint, 4> affine_points{curve.
affine(points[0]), curve.
affine(points[1]), curve.
affine(points[2]), curve.
affine(points[3])};
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)
2483 std::array<AffinePoint, 8> affine_points{
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)
2498 return {point.first, transcript.
mul(
Expr(1) - 2 * negate_bit, point.second)};
2502 Expr lambda = transcript.
div(p2.second - p1.second, p2.first - p1.first);
2503 Expr lambda_sq = transcript.
mul(lambda, lambda);
2513 Expr lambda_delta = transcript.
mul(lambda, delta);
2522 Expr lambda = transcript.
div(p2.second - p1.second, p2.first - p1.first);
2523 Expr lambda_sq = transcript.
mul(lambda, lambda);
2533enum class CircuitEcMultiplyOutput {
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()));
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]);
2555 circuit_2bit_point(curve, {p1, p3, p5, p7}, transcript, bits[i * 3 + 1], bits[i * 3 + 2]),
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]);
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()));
2584 for (std::size_t i = 1; i + 1 < lookups.size(); ++i) {
2587 if (output == CircuitEcMultiplyOutput::FullPoint) {
2599 const JacobianPoint& point,
const std::vector<Expr>& bits) {
2600 return circuit_ec_multiply_impl(curve, transcript, point, bits,
2601 CircuitEcMultiplyOutput::FullPoint);
2605 const JacobianPoint& point,
const std::vector<Expr>& bits) {
2606 return circuit_ec_multiply_impl(curve, transcript, point, bits,
2607 CircuitEcMultiplyOutput::XOnly)
2619 Expr uv = transcript.
mul(x1, v);
2624 Expr numerator_mul = transcript.
mul(u_plus_v, uv_plus_a);
2633 Expr denominator = transcript.
mul(u_minus_v, u_minus_v);
2634 return transcript.
div(numerator, denominator);
2638 const std::optional<UInt256>& z1,
const std::optional<UInt256>& z2) {
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()) {
2652 z1_values = *z1_result;
2653 z2_values = *z2_result;
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) {
2662 for (
int bit : z2_values) {
2665 std::size_t
n_bits = z1_bits.size() + z2_bits.size();
2679 std::span<const unsigned char> statement_binding) {
2680 return ::circuit_binding_digest(circuit, statement_binding);
2685 std::span<const unsigned char> statement_binding) {
2686 return ::circuit_binding_digest(circuit, statement_binding);
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.
AffinePoint affine(const JacobianPoint &point) const
Converts a Jacobian point to affine coordinates.
bool has_value() const noexcept
Caller-owned cache for reusable legacy Bulletproof backend resources keyed by gate count.
ExperimentalBulletproofBackendCache()
ExperimentalBulletproofBackendCache & operator=(const ExperimentalBulletproofBackendCache &)=delete
~ExperimentalBulletproofBackendCache()
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.
std::size_t size() const noexcept
ExprBuilder & add(const FieldElement &value)
Adds a constant field term to the pending affine expression.
static ExprBuilder reserved(std::size_t terms)
Returns a builder with storage reserved for approximately terms linear slots.
Expr build()
Materializes the flattened affine expression.
ExprBuilder & add_scaled(const Expr &expr, const FieldElement &scale)
Adds an existing expression scaled by a field element.
ExprBuilder & subtract(const Expr &expr)
Subtracts an existing expression with implicit coefficient minus one.
Symbolic affine expression over indexed variables and field coefficients.
const FieldElement & constant() const
Returns the constant term of the affine expression.
std::vector< Term > & linear()
Returns mutable access to the sorted linear term list.
static Expr variable(Symbol symbol)
Returns a single-variable expression with coefficient one.
Field element modulo the backend scalar field used by this implementation.
static Result< FieldElement > try_from_uint256(const UInt256 &value)
Converts a canonical 256-bit unsigned integer into the scalar field representation.
static FieldElement one()
Returns the multiplicative identity of the scalar field.
FieldElement negate() const
Returns the additive inverse modulo the field prime.
static FieldElement from_int(std::int64_t value)
Constructs a field element from a signed integer, reducing negatives modulo the field.
bool is_zero() const
Returns true when the element is zero.
static FieldElement zero()
Returns the additive identity of the scalar field.
std::array< unsigned char, 32 > to_bytes_be() const
Serializes the field element in big-endian form.
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)
std::size_t n_commitments() const noexcept
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.
bool has_valid_shape() const noexcept
std::size_t n_gates() const noexcept
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.
PackedWithSlack()=default
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.
std::array< unsigned char, 32 > digest(std::span< const unsigned char > data) const
Mutable transcript used to record symbolic multiplication, division, and boolean constraints.
const std::vector< Expr > & eqs() const
Returns the linear equality constraints accumulated so far.
Expr secret(const std::optional< FieldElement > &value)
Allocates a new secret witness variable, optionally with a known concrete value.
Expr boolean(const Expr &expr)
Constrains an expression to be boolean by adding x * (x - 1) = 0.
const std::vector< MulConstraint > & muls() const
Returns the multiplication and division constraints accumulated so far.
Expr mul(const Expr &lhs, const Expr &rhs)
Allocates or reuses a multiplication witness enforcing lhs * rhs = out.
const WitnessAssignments & varmap() const
Returns the underlying witness assignment vector.
Expr div(const Expr &lhs, const Expr &rhs)
Allocates or reuses a division witness enforcing out * rhs = lhs.
#define PURIFY_RETURN_IF_ERROR(expr, context)
Evaluates an expected-like expression and returns the wrapped error on failure.
#define PURIFY_ASSIGN_OR_RETURN(lhs, expr, context)
Evaluates an expected-like expression, binds the value to lhs, and propagates errors.
std::optional< std::uint32_t > read_u32_le(std::span< const unsigned char > bytes, std::size_t offset)
void append_u32_le(Bytes &out, std::uint32_t value)
std::size_t circuit_n_gates(const NativeBulletproofCircuit &circuit)
std::size_t circuit_n_commitments(const NativeBulletproofCircuit &circuit)
Status require_secp_context(const purify_secp_context *context, const char *error_context)
FieldElement field_di()
Returns the inverse of the twist factor in the field.
const UInt256 & half_n1()
Returns floor(order_n1 / 2).
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.
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.
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.
bool size_fits_u64(std::size_t value) noexcept
std::unique_ptr< purify_bulletproof_backend_resources, BulletproofBackendResourceDeleter > BulletproofBackendResourcePtr
bool is_power_of_two_size(std::size_t value) noexcept
Result< std::uint64_t > narrow_size_to_u64(std::size_t value, const char *context)
Result< std::pair< UInt256, UInt256 > > unpack_public(const UInt512 &packed)
Splits a packed public key into its two x-coordinates.
ErrorCode
Machine-readable error codes shared across the library.
const UInt256 & half_n2()
Returns floor(order_n2 / 2).
bool checked_mul_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
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.
FieldElement field_a()
Returns the shared Weierstrass a coefficient used by Purify.
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.
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)
Expected< T, Error > Result
Expected-returning convenience alias for Purify value-producing APIs.
const JacobianPoint & generator1()
Returns the fixed generator for the first curve.
SymbolKind
Symbol classes used while deriving witness and Bulletproof wire relations.
std::vector< WitnessAssignment, detail::SecureAllocator< WitnessAssignment > > WitnessAssignments
constexpr std::string_view to_string(ErrorCategory category) noexcept
Returns a stable programmatic name for an error category.
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.
std::array< unsigned char, 32 > BulletproofScalarBytes
FieldElement field_b()
Returns the shared Weierstrass b coefficient used by Purify.
std::vector< unsigned char > Bytes
Dynamically sized byte string used for messages, serialized witnesses, and proofs.
bool size_fits_u32(std::size_t value) noexcept
const EllipticCurve & curve2()
Returns the second Purify curve instance.
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.
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
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.
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
Result< Bytes > serialize() const
static Result< ExperimentalBulletproofProof > deserialize(std::span< const unsigned char > bytes)
Jacobian point representation used for curve arithmetic.
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.
std::vector< std::size_t > wl
std::vector< std::size_t > wr
std::vector< std::size_t > wv
std::size_t constraint_slack
std::vector< std::size_t > wo
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.
NativeBulletproofCircuit()=default
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
std::size_t n_commitments
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.
static Symbol witness(std::uint32_t index)
static Symbol left(std::uint32_t index)
static Symbol output(std::uint32_t index)
static Symbol commitment(std::uint32_t index)
static Symbol right(std::uint32_t index)
const unsigned char * ar32
const unsigned char * al32
const unsigned char * ao32
const unsigned char * v32
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)