11#if defined(PURIFY_INTERNAL_TEST_SUPPORT)
19const TaggedHash kBasisHash(
"Purify/BPPP/NormAccumBasisV2");
20const TaggedHash kClaimsHash(
"Purify/BPPP/AccumClaimsV1");
21const TaggedHash kBatchHash(
"Purify/BPPP/AccumBatchV1");
22const TaggedHash kEvaluationHash(
"Purify/BPPP/AccumEvaluationV1");
23const TaggedHash kOpeningBaseHash(
"Purify/BPPP/AccumOpeningBaseV1");
24const TaggedHash kOpeningHash(
"Purify/BPPP/AccumOpeningV1");
25const TaggedHash kRoundHash(
"Purify/BPPP/AccumRoundV1");
26const TaggedHash kNormBindingHash(
"Purify/BPPP/NormReduction/StatementV1");
27const TaggedHash kCircuitNormBindingHash(
28 "Purify/BPPP/CircuitNormReduction/StatementV3");
29const TaggedHash kNormOpeningBaseHash(
"Purify/BPPP/NormReduction/OpeningBaseV1");
30const TaggedHash kNormOpeningHash(
"Purify/BPPP/NormReduction/OpeningV1");
31const TaggedHash kNormFusionHash(
"Purify/BPPP/NormReduction/FusionV1");
32const TaggedHash kOpeningPairHash(
33 "Purify/BPPP/OpeningGeneratorPairV2");
35constexpr std::uint64_t kReductionOpeningRole = 1;
36constexpr std::uint64_t kAccumulationOpeningRole = 2;
37constexpr std::size_t kMaxAlgebraicClaims = 1024;
38constexpr std::size_t kMaxAlgebraicRounds = 24;
39constexpr std::string_view kAlgebraicStepDomain =
40 "Purify/BPPP/CandidateAccumStep/v1";
41constexpr std::string_view kAlgebraicBoundStepDomain =
42 "Purify/BPPP/CandidateBoundAccumStep/v1";
43constexpr std::string_view kAlgebraicNormDomain =
44 "Purify/BPPP/CandidateNormReduction/v2";
46void append_size(
Bytes& out, std::size_t value) {
47 static_assert(
sizeof(std::size_t) <=
sizeof(std::uint64_t));
48 const auto wide =
static_cast<std::uint64_t
>(value);
49 for (
unsigned int i = 0; i < 8; ++i) {
50 out.push_back(
static_cast<unsigned char>((wide >> (8 * i)) & 0xffU));
54void append(
Bytes& out, std::span<const unsigned char> bytes) {
55 out.insert(out.end(), bytes.begin(), bytes.end());
58Digest generator_digest(std::span<const PointBytes> generators) {
60 const auto bytes = std::as_bytes(generators);
62 reinterpret_cast<const unsigned char*
>(bytes.data()),
67std::size_t log2_dimension(std::size_t size) {
69 return static_cast<std::size_t
>(std::bit_width(size) - 1);
72Status validate_algebraic_dimension(std::size_t dimension) {
74 log2_dimension(dimension) > kMaxAlgebraicRounds) {
77 "accumulation:algebraic_dimension");
82FieldElement pow_size(FieldElement base, std::size_t exponent) {
84 while (exponent != 0) {
85 if ((exponent & 1U) != 0) out = out * base;
93 Bytes input(seed.begin(), seed.end());
94 for (std::size_t counter = 0; counter < 256; ++counter) {
95 input.resize(seed.size());
96 append_size(input, counter);
98 if (candidate.has_value() && !candidate->is_zero())
return candidate;
104 std::size_t dimension = 0;
105 std::size_t generators = 0;
108 basis.l_vec_len() > basis.n_vec_len() ||
111 basis.dimension() != dimension || basis.norm_generators().size() != generators) {
118 if (norm.basis_digest() != basis.digest()) {
121 const auto& g = norm.polynomial()[0];
122 const auto& h = norm.polynomial()[1];
123 if (norm.c_vec().size() != basis.l_vec_len() || g.offset != 0 || h.offset != basis.n_vec_len() ||
124 g.factors.size() != log2_dimension(basis.n_vec_len()) ||
125 h.factors.size() != log2_dimension(basis.l_vec_len())) {
131Status validate_algebraic_prepared(
134 validate_algebraic_dimension(basis.dimension()),
135 "accumulation:algebraic_prepared_dimension");
136 if (norm.basis_digest() != basis.digest()) {
139 "accumulation:algebraic_prepared_basis");
141 if (norm.prepared_binding().is_zero()) {
144 "accumulation:algebraic_prepared_binding_zero");
146 const auto& g = norm.polynomial()[0];
147 const auto& h = norm.polynomial()[1];
148 if (norm.c_vec().size() != basis.l_vec_len() ||
149 g.offset != 0 || h.offset != basis.n_vec_len() ||
150 g.factors.size() != log2_dimension(basis.n_vec_len()) ||
151 h.factors.size() != log2_dimension(basis.l_vec_len())) {
154 "accumulation:algebraic_prepared_shape");
159void append_polynomial(
Bytes& encoded, std::span<const PolynomialTerm> polynomial) {
160 append_size(encoded, polynomial.size());
161 for (
const auto& term : polynomial) {
162 append(encoded, term.scale.to_bytes_be());
163 append_size(encoded, term.offset);
164 append_size(encoded, term.factors.size());
165 for (
const auto& factor : term.factors) append(encoded, factor.to_bytes_be());
169Status append_algebraic_point(
170 candidate::Sha256Transcript& transcript,
const PointBytes& point) {
174 "accumulation:algebraic_point");
177 std::copy(point.begin() + 1, point.end(), x.begin());
178 return transcript.append_point(point[0], x);
181Status append_algebraic_polynomial(
182 candidate::Sha256Transcript& transcript,
183 std::span<const PolynomialTerm> polynomial) {
187 "accumulation:algebraic_polynomial_size");
189 transcript.append_u64(
static_cast<std::uint64_t
>(polynomial.size()));
190 for (
const auto& term : polynomial) {
195 "accumulation:algebraic_term_size");
197 transcript.append_scalar(term.scale);
198 transcript.append_u64(
static_cast<std::uint64_t
>(term.offset));
199 transcript.append_u64(
200 static_cast<std::uint64_t
>(term.factors.size()));
201 for (
const auto& factor : term.factors) {
202 transcript.append_scalar(factor);
209 if (claim.basis_digest() != basis.digest()) {
213 if (claim.polynomial().empty() || claim.polynomial().size() > 3) {
216 for (
const auto& term : claim.polynomial()) {
217 if (term.factors.size() >= std::numeric_limits<std::size_t>::digits) {
220 const std::size_t width = std::size_t{1} << term.factors.size();
221 if (width > basis.dimension() || term.offset > basis.dimension() - width) {
228FieldElement evaluate(std::span<const PolynomialTerm> polynomial,
const FieldElement& x) {
230 for (
const auto& term : polynomial) {
231 auto value = term.scale * pow_size(x, term.offset);
233 for (
const auto& factor : term.factors) {
235 x_power = x_power * x_power;
242void add_coefficients(std::vector<FieldElement>& out, std::span<const PolynomialTerm> polynomial,
243 const FieldElement& weight) {
244 for (
const auto& term : polynomial) {
245 std::vector<FieldElement> coefficients{weight * term.scale};
246 for (
const auto& factor : term.factors) {
247 const auto size = coefficients.size();
248 coefficients.resize(2 * size);
249 for (std::size_t i = 0; i < size; ++i) {
250 coefficients[size + i] = coefficients[i] * factor;
253 for (std::size_t i = 0; i < coefficients.size(); ++i) {
254 out[term.offset + i] = out[term.offset + i] + coefficients[i];
259Result<PointBytes> msm(std::span<const PointBytes> points, std::span<const FieldElement> scalars,
261 if (points.size() != scalars.size()) {
264 std::vector<ScalarBytes> encoded;
265 encoded.reserve(scalars.size());
266 for (
const auto& scalar : scalars) encoded.push_back(scalar.to_bytes_be());
269 reinterpret_cast<const unsigned char*
>(points.data()),
270 reinterpret_cast<const unsigned char*
>(encoded.data()), points.size(), out.data()) == 0) {
277 candidate::Sha256Transcript& transcript, std::uint64_t round) {
279 auto challenge, transcript.challenge(round),
280 "accumulation:algebraic_challenge");
281 return std::move(challenge.scalar);
285 const Basis& basis,
const candidate::Sha256Transcript& transcript,
287 if (role != kReductionOpeningRole &&
288 role != kAccumulationOpeningRole) {
291 "accumulation:opening_role");
295 transcript.opening_base_scalar(basis.digest(), role),
296 "accumulation:opening_scalar");
298 std::array<PointBytes, 2> pair{};
299 for (std::size_t index = 0; index < pair.size(); ++index) {
301 message.reserve(basis.digest().size() + 9);
302 append(message, basis.digest());
303 append_size(message,
static_cast<std::size_t
>(role));
304 message.push_back(
static_cast<unsigned char>(index));
305 const auto seed = kOpeningPairHash.digest(message);
307 context, seed.data(), seed.size(),
308 pair[index].data()) == 0 ||
312 "accumulation:opening_pair");
315 if (pair[0] == pair[1]) {
318 "accumulation:opening_pair_duplicate");
320 const std::array<FieldElement, 2> scalars{
323 auto opening_base, msm(pair, scalars, context),
324 "accumulation:opening_pair_msm");
328 "accumulation:opening_pair_identity");
337 "accumulation:root_claim_context");
339 "accumulation:root_claim");
340 if (claim.polynomial().size() != 1 ||
341 claim.polynomial()[0].offset != 0 ||
342 claim.polynomial()[0].factors.size() !=
343 log2_dimension(basis.dimension())) {
345 "accumulation:root_claim_shape");
347 const std::array<PointBytes, 1> points{claim.point()};
350 const auto& identity, msm(points, scalars, context),
351 "accumulation:root_claim_point");
356template <
typename Proof>
357Status validate_ipa_encoding(std::size_t dimension,
const Proof& proof,
360 "accumulation:context");
364 const auto rounds = log2_dimension(dimension);
365 if (proof.left.size() != rounds || proof.right.size() != rounds) {
369 "accumulation:step_encoding_scalar");
371 const auto is_canonical_point = [](
const PointBytes& point) {
374 for (std::size_t round = 0; round < rounds; ++round) {
375 if (!is_canonical_point(proof.left[round]) ||
376 !is_canonical_point(proof.right[round])) {
379 "accumulation:step_encoding_points");
382 if (!is_canonical_point(proof.folded_generator)) {
385 "accumulation:step_encoding_points");
390template <
typename Proof>
391void append_ipa(
Bytes& out,
const Proof& proof) {
392 for (std::size_t round = 0; round < proof.left.size(); ++round) {
393 append(out, proof.left[round]);
394 append(out, proof.right[round]);
396 append(out, proof.terminal_scalar);
397 append(out, proof.folded_generator);
400template <
typename Proof>
402 std::span<const unsigned char> encoded,
404 const auto rounds = log2_dimension(dimension);
405 if (encoded.size() != 66 * rounds + 65) {
409 proof.left.resize(rounds);
410 proof.right.resize(rounds);
411 std::size_t offset = 0;
412 for (std::size_t round = 0; round < rounds; ++round) {
413 std::copy_n(encoded.data() + offset, 33, proof.left[round].begin());
415 std::copy_n(encoded.data() + offset, 33, proof.right[round].begin());
418 std::copy_n(encoded.data() + offset, 32, proof.terminal_scalar.begin());
420 std::copy_n(encoded.data() + offset, 33, proof.folded_generator.begin());
437 "accumulation:context");
439 if (claims.empty()) {
443 append(encoded, basis.digest());
444 append_size(encoded, claims.size());
445 for (
const auto& claim : claims) {
447 append(encoded, claim.point());
448 append_polynomial(encoded, claim.polynomial());
450 const auto claims_digest = kClaimsHash.digest(encoded);
453 "accumulation:batch_challenge");
454 std::vector<PointBytes> commitments;
455 std::vector<FieldElement> weights;
456 commitments.reserve(claims.size());
457 weights.reserve(claims.size());
459 for (
const auto& claim : claims) {
460 commitments.push_back(claim.point());
461 weights.push_back(weight);
462 weight = weight * out.beta;
465 "accumulation:batch_commitment");
467 append(encoded, claims_digest);
468 append(encoded, out.beta.to_bytes_be());
469 append(encoded, out.commitment);
471 "accumulation:evaluation_challenge");
473 for (std::size_t i = 0; i < claims.size(); ++i) {
474 out.y = out.y + weights[i] * evaluate(claims[i].polynomial(), out.x);
476 append(encoded, out.x.to_bytes_be());
477 append(encoded, out.y.to_bytes_be());
480 const auto opening_seed = kOpeningBaseHash.digest(encoded);
482 out.opening_base.data()) == 0) {
485 append(encoded, out.opening_base);
486 out.transcript = kOpeningHash.digest(encoded);
490struct AlgebraicStepContext {
496 candidate::Sha256Transcript transcript;
500 const Basis& basis, std::span<const PendingClaim> claims,
504 "accumulation:context");
506 validate_basis(basis),
"accumulation:basis");
507 if (claims.empty()) {
511 const auto rounds = log2_dimension(basis.dimension());
512 if (claims.size() > kMaxAlgebraicClaims) {
515 "accumulation:algebraic_step_shape");
518 validate_algebraic_dimension(basis.dimension()),
519 "accumulation:algebraic_step_shape");
520 AlgebraicStepContext out;
521 const auto domain_name = statement_digest ==
nullptr
522 ? kAlgebraicStepDomain
523 : kAlgebraicBoundStepDomain;
524 const auto domain = std::span(
525 reinterpret_cast<const unsigned char*
>(
529 out.transcript.append_bytes(domain),
530 "accumulation:algebraic_step_domain");
531 if (statement_digest !=
nullptr) {
533 out.transcript.append_bytes(*statement_digest),
534 "accumulation:algebraic_step_statement");
537 out.transcript.append_bytes(basis.digest()),
538 "accumulation:algebraic_step_basis");
539 out.transcript.append_u64(
540 static_cast<std::uint64_t
>(rounds));
541 out.transcript.append_u64(
542 static_cast<std::uint64_t
>(claims.size()));
543 for (
const auto& claim : claims) {
545 validate_claim(basis, claim),
"accumulation:claim");
547 append_algebraic_point(out.transcript, claim.point()),
548 "accumulation:algebraic_claim_point");
550 append_algebraic_polynomial(
551 out.transcript, claim.polynomial()),
552 "accumulation:algebraic_claim_polynomial");
556 out.beta, append_algebraic_challenge(out.transcript, 0),
557 "accumulation:algebraic_batch_challenge");
558 std::vector<PointBytes> commitments;
559 std::vector<FieldElement> weights;
560 commitments.reserve(claims.size());
561 weights.reserve(claims.size());
563 for (
const auto& claim : claims) {
564 commitments.push_back(claim.point());
565 weights.push_back(weight);
566 weight = weight * out.beta;
569 out.commitment, msm(commitments, weights, context),
570 "accumulation:algebraic_batch_commitment");
572 append_algebraic_point(out.transcript, out.commitment),
573 "accumulation:algebraic_commitment");
576 out.x, append_algebraic_challenge(out.transcript, 1),
577 "accumulation:algebraic_evaluation_challenge");
579 for (std::size_t i = 0; i < claims.size(); ++i) {
581 weights[i] * evaluate(claims[i].polynomial(), out.x);
583 out.transcript.append_scalar(out.y);
587 derive_algebraic_opening_base(
588 basis, out.transcript, kAccumulationOpeningRole,
590 "accumulation:algebraic_opening_base");
592 append_algebraic_point(out.transcript, out.opening_base),
593 "accumulation:algebraic_opening_point");
600 append(encoded, transcript);
601 append_size(encoded, round);
602 append(encoded, left);
603 append(encoded, right);
605 append(encoded, t.to_bytes_be());
606 transcript = kRoundHash.digest(encoded);
610PolynomialTerm geometric_tensor(
const FieldElement& x, std::size_t dimension) {
613 for (std::size_t i = 0; i < log2_dimension(dimension); ++i) {
614 out.factors.push_back(power);
615 power = power * power;
621 assert(lhs.offset == 0 && rhs.offset == 0 && lhs.factors.size() == rhs.factors.size());
622 auto out = lhs.scale * rhs.scale;
623 for (std::size_t i = 0; i < lhs.factors.size(); ++i) {
629template <
typename Proof,
typename RoundChallenge>
631 std::span<const PointBytes> basis, std::vector<FieldElement> a,
635 assert(weights.offset == 0 && weights.factors.size() == log2_dimension(a.size()));
637 const std::array<PolynomialTerm, 1> tensor{weights};
639 std::vector<PointBytes> generators(basis.begin(), basis.end());
641 const auto rounds = log2_dimension(a.size());
642 proof.left.reserve(rounds);
643 proof.right.reserve(rounds);
644 for (std::size_t round = 0; round < rounds; ++round) {
645 const auto half = a.size() / 2;
646 std::vector<PointBytes> left_points, right_points;
647 std::vector<FieldElement> left_scalars, right_scalars;
648 left_points.reserve(half + 1);
649 right_points.reserve(half + 1);
650 left_scalars.reserve(half + 1);
651 right_scalars.reserve(half + 1);
654 for (std::size_t i = 0; i < half; ++i) {
655 left_points.push_back(generators[half + i]);
656 left_scalars.push_back(a[i]);
657 right_points.push_back(generators[i]);
658 right_scalars.push_back(a[half + i]);
659 left_inner = left_inner + a[i] * b[half + i];
660 right_inner = right_inner + a[half + i] * b[i];
662 left_points.push_back(opening_base);
663 right_points.push_back(opening_base);
664 left_scalars.push_back(left_inner);
665 right_scalars.push_back(right_inner);
667 "accumulation:prove_left");
669 "accumulation:prove_right");
670 proof.left.push_back(left);
671 proof.right.push_back(right);
673 round_challenge(round, left, right),
674 "accumulation:prove_round");
675 const auto t_inv = t.inverse();
676 for (std::size_t i = 0; i < half; ++i) {
677 a[i] = t * a[i] + t_inv * a[half + i];
678 b[i] = t_inv * b[i] + t * b[half + i];
679 const std::array<PointBytes, 2> pair{generators[i], generators[half + i]};
680 const std::array<FieldElement, 2> fold_weights{t_inv, t};
682 "accumulation:prove_fold_basis");
686 generators.resize(half);
688 proof.terminal_scalar = a[0].to_bytes_be();
689 proof.folded_generator = generators[0];
694 std::span<const PointBytes> basis, std::vector<FieldElement> a,
697 return prove_ipa_with_challenges<StepProof>(
698 basis, std::move(a), weights, opening_base,
699 [&transcript](std::size_t round,
const PointBytes& left,
701 return round_challenge(transcript, round, left, right);
706struct IpaVerification {
707 PolynomialTerm folded;
711template <
typename Proof,
typename RoundChallenge>
713 std::size_t dimension,
const Proof& proof,
715 const FieldElement& evaluation,
const PointBytes& opening_base,
718 assert(weights.offset == 0 && weights.factors.size() == log2_dimension(dimension));
719 const auto rounds = log2_dimension(dimension);
720 if (proof.left.size() != rounds || proof.right.size() != rounds) {
724 "accumulation:step_terminal_scalar");
727 std::vector<PointBytes> points{commitment};
729 for (std::size_t round = 0; round < rounds; ++round) {
731 round_challenge(round, proof.left[round],
733 "accumulation:verify_round");
734 const auto t_inv = t.inverse();
735 const auto t_squared = t * t;
736 folded.scale = folded.scale * t_inv;
738 folded.factors[rounds - 1 - round] = t_squared;
739 points.push_back(proof.left[round]);
740 scalars.push_back(t_squared);
741 points.push_back(proof.right[round]);
742 scalars.push_back(t_inv * t_inv);
744 const auto b_final = tensor_inner_product(weights, folded);
745 points.push_back(opening_base);
746 scalars.push_back(evaluation - a * b_final);
747 points.push_back(proof.folded_generator);
748 scalars.push_back(a.negate());
750 "accumulation:verify_equation");
751 return IpaVerification{std::move(folded), residual};
754template <
typename Proof,
typename RoundChallenge>
756 std::size_t dimension,
const Proof& proof,
758 const FieldElement& evaluation,
const PointBytes& opening_base,
762 evaluate_ipa_with_challenges(
763 dimension, proof, weights, commitment, evaluation,
764 opening_base, std::forward<RoundChallenge>(round_challenge),
766 "accumulation:evaluate_ipa");
771 return std::move(verified.folded);
775 std::size_t dimension,
const StepProof& proof,
777 const FieldElement& evaluation,
const PointBytes& opening_base,
779 return verify_ipa_with_challenges(
780 dimension, proof, weights, commitment, evaluation, opening_base,
781 [&transcript](std::size_t round,
const PointBytes& left,
783 return round_challenge(transcript, round, left, right);
789 std::span<const PointBytes> basis, std::vector<FieldElement> a,
791 candidate::Sha256Transcript& transcript,
793 return prove_ipa_with_challenges<AlgebraicStepProof>(
794 basis, std::move(a), weights, opening_base,
795 [&transcript, first_round](
799 append_algebraic_point(transcript, left),
800 "accumulation:algebraic_left");
802 append_algebraic_point(transcript, right),
803 "accumulation:algebraic_right");
804 return append_algebraic_challenge(
806 first_round +
static_cast<std::uint64_t
>(round));
814 const FieldElement& evaluation,
const PointBytes& opening_base,
815 candidate::Sha256Transcript& transcript,
817 return evaluate_ipa_with_challenges(
818 dimension, proof, weights, commitment, evaluation, opening_base,
819 [&transcript, first_round](
823 append_algebraic_point(transcript, left),
824 "accumulation:algebraic_left");
826 append_algebraic_point(transcript, right),
827 "accumulation:algebraic_right");
828 return append_algebraic_challenge(
830 first_round +
static_cast<std::uint64_t
>(round));
838 const FieldElement& evaluation,
const PointBytes& opening_base,
839 candidate::Sha256Transcript& transcript,
843 evaluate_algebraic_ipa(
844 dimension, proof, weights, commitment, evaluation,
845 opening_base, transcript, first_round, context),
846 "accumulation:evaluate_algebraic_ipa");
851 return std::move(verified.folded);
854struct NormOpeningContext {
855 FieldElement evaluation;
856 PolynomialTerm weights;
867 NormOpeningContext out;
869 "accumulation:coefficient_evaluation");
872 append(encoded, basis.digest());
873 append(encoded, norm.transcript_digest());
874 append(encoded, norm.coefficient_commitment());
875 const std::array<PolynomialTerm, 1> weights{out.weights};
876 append_polynomial(encoded, weights);
877 append(encoded, evaluation);
879 const auto seed = kNormOpeningBaseHash.digest(encoded);
883 append(encoded, out.opening_base);
884 out.transcript = kNormOpeningHash.digest(encoded);
888struct AlgebraicNormOpeningContext {
889 FieldElement evaluation;
890 PolynomialTerm weights;
892 candidate::Sha256Transcript transcript;
900 "accumulation:context");
902 validate_basis(basis),
"accumulation:basis");
904 validate_algebraic_prepared(basis, norm),
905 "accumulation:algebraic_prepared");
907 AlgebraicNormOpeningContext out;
908 const auto rounds = log2_dimension(basis.l_vec_len());
910 validate_algebraic_dimension(basis.l_vec_len()),
911 "accumulation:algebraic_norm_shape");
915 "accumulation:coefficient_evaluation");
918 norm.polynomial()[1].factors};
920 const auto domain = std::span(
921 reinterpret_cast<const unsigned char*
>(
922 kAlgebraicNormDomain.data()),
923 kAlgebraicNormDomain.size());
925 out.transcript.append_bytes(domain),
926 "accumulation:algebraic_norm_domain");
928 out.transcript.append_bytes(basis.digest()),
929 "accumulation:algebraic_norm_basis");
930 out.transcript.append_u64(
931 static_cast<std::uint64_t
>(rounds));
932 out.transcript.append_scalar(norm.prepared_binding());
934 append_algebraic_point(
935 out.transcript, norm.coefficient_commitment()),
936 "accumulation:algebraic_norm_commitment");
937 const std::array<PolynomialTerm, 1> weights{out.weights};
939 append_algebraic_polynomial(out.transcript, weights),
940 "accumulation:algebraic_norm_weights");
941 out.transcript.append_scalar(out.evaluation);
945 derive_algebraic_opening_base(
946 basis, out.transcript, kReductionOpeningRole,
948 "accumulation:algebraic_norm_opening_base");
950 append_algebraic_point(out.transcript, out.opening_base),
951 "accumulation:algebraic_norm_opening_point");
955struct CircuitPreparedNorm {
956 Digest transcript_digest{};
957 std::vector<ScalarBytes> c_vec;
960 std::array<PolynomialTerm, 2> polynomial;
965 const detail::PreparedExperimentalCircuitZkNormArg& prepared,
966 const ExperimentalCircuitZkNormArgProof& proof,
967 std::span<const PointBytes> public_commitments,
969 std::span<const unsigned char> statement_binding) {
970 const auto& norm = prepared.norm;
971 if (norm.n_vec_len != basis.n_vec_len() ||
972 norm.c_vec.size() != basis.l_vec_len() ||
973 norm.generators.size() !=
974 basis.n_vec_len() + basis.l_vec_len() ||
975 prepared.raw_generator_digest !=
976 generator_digest(basis.norm_generators())) {
978 "accumulation:circuit_raw_basis");
981 const auto rounds = log2_dimension(basis.n_vec_len());
982 std::vector<ScalarBytes> gammas(rounds);
986 context, norm.rho.data(),
987 reinterpret_cast<const unsigned char*
>(norm.generators.data()),
988 norm.generators.size(),
989 reinterpret_cast<const unsigned char*
>(norm.c_vec.data()),
990 norm.c_vec.size(), norm.n_vec_len, norm.commitment.data(),
991 norm.proof.data(), norm.proof.size(), n_bytes.data(),
993 reinterpret_cast<unsigned char*
>(gammas.data()), gammas.size(),
994 residual.data()) == 0) {
996 "accumulation:circuit_inner_norm");
1001 "accumulation:circuit_norm_n");
1004 "accumulation:circuit_norm_l");
1007 "accumulation:circuit_norm_rho");
1009 const auto& sqrt_minus_one,
1011 "accumulation:circuit_sqrt_minus_one");
1014 n * pow_size(rho, basis.n_vec_len()) *
1015 prepared.mul_scale.inverse(),
1019 const auto h_rounds = log2_dimension(basis.l_vec_len());
1020 auto ratio_inv_power = prepared.mul_ratio.inverse();
1021 for (std::size_t j = 0; j < rounds; ++j) {
1024 "accumulation:circuit_norm_gamma");
1026 g.factors.push_back(gamma * sqrt_minus_one.inverse());
1028 g.factors.push_back(gamma * ratio_inv_power);
1029 ratio_inv_power = ratio_inv_power * ratio_inv_power;
1031 if (j < h_rounds) h.factors.push_back(gamma);
1034 std::vector<FieldElement> coefficients;
1035 coefficients.reserve(norm.c_vec.size());
1036 for (
const auto& encoded : norm.c_vec) {
1038 const auto& coefficient,
1040 "accumulation:circuit_norm_coefficient");
1041 coefficients.push_back(coefficient);
1043 const auto h_basis = std::span(basis.points())
1044 .subspan(basis.n_vec_len(),
1047 auto coefficient_commitment,
1048 msm(h_basis, coefficients, context),
1049 "accumulation:circuit_coefficient_commitment");
1052 append(encoded, basis.digest());
1053 append(encoded, prepared.raw_generator_digest);
1054 append(encoded, prepared.challenge_digest);
1055 append(encoded, norm.rho);
1056 append(encoded, prepared.mul_scale.to_bytes_be());
1057 append(encoded, prepared.mul_ratio.to_bytes_be());
1058 append_size(encoded, statement_binding.size());
1059 append(encoded, statement_binding);
1060 append_size(encoded, public_commitments.size());
1061 for (
const auto& point : public_commitments) append(encoded, point);
1062 append(encoded, proof.a_commitment);
1063 append(encoded, proof.s_commitment);
1064 append(encoded, proof.t2);
1065 append(encoded, proof.public_commitment_dlog_nonce);
1066 append(encoded, proof.public_commitment_dlog_response);
1067 append(encoded, norm.commitment);
1068 for (
const auto& coefficient : norm.c_vec) append(encoded, coefficient);
1069 append(encoded, coefficient_commitment);
1070 append_size(encoded, norm.proof.size());
1071 append(encoded, norm.proof);
1073 return CircuitPreparedNorm{
1074 kCircuitNormBindingHash.digest(encoded), norm.c_vec,
1075 coefficient_commitment, residual,
1076 {std::move(g), std::move(h)}};
1084 "accumulation:context");
1090 if (semantic_domain.empty()) {
1097 "accumulation:deterministic_generators");
1100 reinterpret_cast<const unsigned char*
>(generators.data()), generators.size(),
1101 reinterpret_cast<unsigned char*
>(out.points_.data())) == 0) {
1105 out.norm_generators_ = std::move(generators);
1107 append_size(encoded, semantic_domain.size());
1108 append(encoded, std::span(
reinterpret_cast<const unsigned char*
>(semantic_domain.data()),
1109 semantic_domain.size()));
1112 for (
const auto& point : out.points_) append(encoded, point);
1113 out.digest_ = kBasisHash.digest(encoded);
1121 "accumulation:serialize_step");
1123 out.reserve(66 * log2_dimension(basis.
dimension()) + 66);
1125 append_ipa(out, proof);
1133 if (encoded.size() != 66 * log2_dimension(basis.
dimension()) + 66) {
1136 if (encoded[0] != 1) {
1139 return parse_ipa<StepProof>(
1140 basis.
dimension(), encoded.subspan(1), context);
1147 validate_basis(basis),
"accumulation:basis");
1149 validate_algebraic_dimension(basis.
dimension()),
1150 "accumulation:algebraic_step_dimension");
1152 validate_ipa_encoding(
1154 "accumulation:serialize_algebraic_step");
1157 66 * log2_dimension(basis.
dimension()) + 66);
1159 append_ipa(out, proof);
1164 const Basis& basis, std::span<const unsigned char> encoded,
1168 "accumulation:context");
1170 validate_basis(basis),
"accumulation:basis");
1172 validate_algebraic_dimension(basis.
dimension()),
1173 "accumulation:algebraic_step_dimension");
1174 if (encoded.size() !=
1175 66 * log2_dimension(basis.
dimension()) + 66) {
1178 "accumulation:parse_algebraic_step_size");
1180 if (encoded[0] != 2) {
1183 "accumulation:parse_algebraic_step_version");
1185 return parse_ipa<AlgebraicStepProof>(
1186 basis.
dimension(), encoded.subspan(1), context);
1194 validate_root_claim(basis, claim, context),
1195 "accumulation:serialize_root_claim");
1196 const auto& polynomial = claim.
polynomial()[0];
1198 out.reserve(65 + 32 * polynomial.factors.size());
1199 append(out, claim.
point());
1200 append(out, polynomial.scale.to_bytes_be());
1201 for (
const auto& factor : polynomial.factors) {
1202 append(out, factor.to_bytes_be());
1208 const Basis& basis, std::span<const unsigned char> encoded,
1211 const auto factor_count = log2_dimension(basis.
dimension());
1212 if (encoded.size() != 65 + 32 * factor_count) {
1214 "accumulation:parse_root_claim_size");
1218 std::copy_n(encoded.begin(),
point.size(),
point.begin());
1220 std::copy_n(encoded.begin() +
static_cast<std::ptrdiff_t
>(
point.size()),
1221 scalar.size(), scalar.begin());
1224 "accumulation:parse_root_claim_scale");
1225 std::vector<FieldElement> factors;
1226 factors.reserve(factor_count);
1227 std::size_t offset =
point.size() + scalar.size();
1228 for (std::size_t i = 0; i < factor_count; ++i) {
1229 std::copy_n(encoded.begin() +
static_cast<std::ptrdiff_t
>(offset),
1230 scalar.size(), scalar.begin());
1231 offset += scalar.size();
1234 "accumulation:parse_root_claim_factor");
1235 factors.push_back(factor);
1238 {PolynomialTerm{scale, 0, std::move(factors)}});
1240 validate_root_claim(basis, out, context),
1241 "accumulation:parse_root_claim");
1248 validate_algebraic_dimension(basis.
dimension()),
1249 "accumulation:zero_claim_dimension");
1250 return PendingClaim(
1253 FieldElement::zero(), 0,
1254 std::vector<FieldElement>(
1255 log2_dimension(basis.dimension()),
1256 FieldElement::zero())}});
1263 "accumulation:serialize_reduction_evaluation");
1266 "accumulation:serialize_reduction");
1268 out.reserve(66 * log2_dimension(basis.
l_vec_len()) + 98);
1279 if (encoded.size() != 66 * log2_dimension(basis.
l_vec_len()) + 98) {
1282 if (encoded[0] != 1) {
1288 "accumulation:parse_reduction_evaluation");
1291 parse_ipa<StepProof>(basis.
l_vec_len(), encoded.subspan(33),
1293 "accumulation:parse_reduction_ipa");
1302 validate_basis(basis),
"accumulation:basis");
1304 validate_algebraic_dimension(basis.
dimension()),
1305 "accumulation:algebraic_reduction_dimension");
1307 validate_algebraic_dimension(basis.
l_vec_len()),
1308 "accumulation:algebraic_reduction_dimension");
1313 "accumulation:serialize_algebraic_evaluation");
1316 validate_ipa_encoding(
1319 "accumulation:serialize_algebraic_reduction");
1322 66 * log2_dimension(basis.
l_vec_len()) + 98);
1331 const Basis& basis, std::span<const unsigned char> encoded,
1335 "accumulation:context");
1337 validate_basis(basis),
"accumulation:basis");
1339 validate_algebraic_dimension(basis.
dimension()),
1340 "accumulation:algebraic_reduction_dimension");
1342 validate_algebraic_dimension(basis.
l_vec_len()),
1343 "accumulation:algebraic_reduction_dimension");
1344 if (encoded.size() !=
1345 66 * log2_dimension(basis.
l_vec_len()) + 98) {
1348 "accumulation:parse_algebraic_reduction_size");
1350 if (encoded[0] != 2) {
1353 "accumulation:parse_algebraic_reduction_version");
1357 encoded.data() + 1, 32,
1363 "accumulation:parse_algebraic_evaluation");
1367 parse_ipa<AlgebraicStepProof>(
1368 basis.
l_vec_len(), encoded.subspan(33), context),
1369 "accumulation:parse_algebraic_reduction_ipa");
1376 "accumulation:context");
1382 const auto rounds = log2_dimension(basis.
n_vec_len());
1383 std::vector<ScalarBytes> gammas(rounds);
1388 reinterpret_cast<const unsigned char*
>(proof.
c_vec.data()), proof.
c_vec.size(),
1390 n_bytes.data(), l_bytes.data(),
reinterpret_cast<unsigned char*
>(gammas.data()),
1391 gammas.size(),
residual.data()) == 0) {
1399 auto rho_inv_power = rho.inverse();
1400 const auto h_rounds = log2_dimension(basis.
l_vec_len());
1401 for (std::size_t j = 0; j < rounds; ++j) {
1403 "accumulation:norm_gamma");
1404 g.
factors.push_back(gamma * rho_inv_power);
1405 if (j < h_rounds) h.
factors.push_back(gamma);
1406 rho_inv_power = rho_inv_power * rho_inv_power;
1408 std::vector<FieldElement> coefficients;
1409 coefficients.reserve(proof.
c_vec.size());
1410 for (
const auto& encoded : proof.
c_vec) {
1412 "accumulation:norm_coefficient");
1413 coefficients.push_back(coefficient);
1417 "accumulation:coefficient_commitment");
1419 append(encoded, basis.
digest());
1420 append(encoded, proof.
rho);
1422 for (
const auto& coefficient : proof.
c_vec) append(encoded, coefficient);
1423 append(encoded, commitment);
1424 append_size(encoded, proof.
proof.size());
1425 append(encoded, proof.
proof);
1426 return PreparedNorm(basis.
digest(), kNormBindingHash.digest(encoded), proof.
c_vec,
1427 commitment,
residual, {std::move(g), std::move(h)});
1435 std::span<const unsigned char> statement_binding,
1439 "accumulation:circuit_context");
1441 "accumulation:circuit_basis");
1445 circuit, proof, context, statement_binding, cache),
1446 "accumulation:circuit_prepare");
1447 if (!prepared.has_value()) {
1449 "accumulation:circuit_zero_dlog");
1453 prepare_circuit_norm_components(
1454 basis, *prepared, proof, {}, context, statement_binding),
1455 "accumulation:circuit_components");
1456 return PreparedNorm(
1457 basis.
digest(), components.transcript_digest,
1458 std::move(components.c_vec), components.coefficient_commitment,
1459 components.residual, std::move(components.polynomial));
1466 std::span<const PointBytes> public_commitments,
1468 std::span<const unsigned char> statement_binding,
1472 "accumulation:circuit_context");
1474 "accumulation:circuit_basis");
1478 circuit, proof, public_commitments, context, statement_binding,
1480 "accumulation:circuit_prepare");
1481 if (!prepared.has_value()) {
1483 "accumulation:circuit_public_dlog");
1487 prepare_circuit_norm_components(
1488 basis, *prepared, proof, public_commitments, context,
1490 "accumulation:circuit_components");
1491 return PreparedNorm(
1492 basis.
digest(), components.transcript_digest,
1493 std::move(components.c_vec), components.coefficient_commitment,
1494 components.residual, std::move(components.polynomial));
1503 "accumulation:v4_context");
1505 validate_basis(basis),
"accumulation:v4_basis");
1507 validate_algebraic_dimension(basis.
dimension()),
1508 "accumulation:v4_dimension");
1510 const auto& shape = prepared.
shape();
1512 const auto& transcript = prepared.
transcript();
1513 const auto& norm = prepared.
norm();
1514 const auto rounds = shape.round_count();
1515 std::size_t generator_count = 0;
1520 "accumulation:v4_generator_count");
1524 if (shape.n_vec_len() != basis.
n_vec_len() ||
1525 shape.l_vec_len() != basis.
l_vec_len() ||
1530 "accumulation:v4_raw_basis");
1532 const auto raw_generator_digest =
1534 if (transcript_input.raw_generator_digest != raw_generator_digest ||
1538 "accumulation:v4_raw_basis_digest");
1540 if (norm.n_vec_len != shape.n_vec_len() ||
1541 norm.generators.size() != generator_count ||
1542 norm.c_vec.size() != shape.l_vec_len() ||
1543 norm.rho != transcript.rho.scalar.to_bytes_be() ||
1544 norm.commitment != transcript_input.combined_commitment ||
1545 transcript_input.rounds.size() != rounds ||
1546 transcript.gammas.size() != rounds) {
1549 "accumulation:v4_prepared_shape");
1552 if (transcript.rho.scalar.is_zero() ||
1553 transcript.mul_scale.scalar.is_zero() ||
1554 transcript.mul_ratio.scalar.is_zero() ||
1555 transcript.prepared_binding.scalar.is_zero() ||
1557 transcript.gammas.begin(), transcript.gammas.end(),
1559 return gamma.scalar.is_zero();
1563 "accumulation:v4_zero_challenge");
1566 const auto& sqrt_minus_one,
1568 "accumulation:v4_sqrt_minus_one");
1572 auto rho_power = transcript.rho.scalar;
1573 auto generator_term = transcript.mul_scale.scalar;
1574 for (std::size_t i = 0; i < shape.n_vec_len(); ++i) {
1575 const auto term = (i % 2 == 0)
1577 : sqrt_minus_one * generator_term;
1578 const auto scale = rho_power * term.inverse();
1579 const auto encoded_scale = scale.to_bytes_be();
1583 encoded_scale.data(), expected_generator.data()) == 0) {
1586 "accumulation:v4_scale_generator");
1588 if (norm.generators[i] != expected_generator) {
1591 "accumulation:v4_scaled_basis");
1595 generator_term * transcript.mul_ratio.scalar;
1597 rho_power = rho_power * transcript.rho.scalar;
1600 norm.generators.begin() +
1601 static_cast<std::ptrdiff_t
>(shape.n_vec_len()),
1602 norm.generators.end(),
1604 static_cast<std::ptrdiff_t
>(shape.n_vec_len()))) {
1607 "accumulation:v4_linear_basis");
1610 std::size_t round_bytes = 0;
1611 std::size_t expected_proof_size = 0;
1616 expected_proof_size)) {
1619 "accumulation:v4_proof_size");
1621 if (norm.proof.size() != expected_proof_size) {
1624 "accumulation:v4_proof_size");
1626 for (std::size_t i = 0; i < rounds; ++i) {
1629 transcript_input.rounds[i].begin(),
1630 transcript_input.rounds[i].end(),
1631 norm.proof.begin() +
1632 static_cast<std::ptrdiff_t
>(offset))) {
1635 "accumulation:v4_round_payload");
1639 transcript_input.terminal_n.begin(),
1640 transcript_input.terminal_n.end(),
1641 norm.proof.begin() +
1642 static_cast<std::ptrdiff_t
>(round_bytes)) ||
1644 transcript_input.terminal_l.begin(),
1645 transcript_input.terminal_l.end(),
1646 norm.proof.begin() +
static_cast<std::ptrdiff_t
>(
1650 "accumulation:v4_terminal_payload");
1653 std::vector<ScalarBytes> encoded_gammas;
1654 encoded_gammas.reserve(rounds);
1655 for (
const auto& gamma : transcript.gammas) {
1664 context, norm.rho.data(),
1665 reinterpret_cast<const unsigned char*
>(
1666 norm.generators.data()),
1667 norm.generators.size(),
1668 reinterpret_cast<const unsigned char*
>(norm.c_vec.data()),
1669 norm.c_vec.size(), norm.n_vec_len, norm.commitment.data(),
1670 norm.proof.data(), norm.proof.size(),
1671 reinterpret_cast<const unsigned char*
>(
1672 encoded_gammas.data()),
1673 encoded_gammas.size(), terminal_n_bytes.data(),
1674 terminal_l_bytes.data(),
residual.data()) == 0) {
1677 "accumulation:v4_inner_norm");
1679 if (terminal_n_bytes != transcript_input.terminal_n ||
1680 terminal_l_bytes != transcript_input.terminal_l ||
1684 "accumulation:v4_prepared_norm");
1688 const auto& terminal_n,
1690 "accumulation:v4_terminal_n");
1692 const auto& terminal_l,
1694 "accumulation:v4_terminal_l");
1698 pow_size(transcript.rho.scalar, shape.n_vec_len()) *
1699 transcript.mul_scale.scalar.inverse(),
1705 auto ratio_inverse_power =
1706 transcript.mul_ratio.scalar.inverse();
1707 for (std::size_t i = 0; i < rounds; ++i) {
1708 const auto& gamma = transcript.gammas[i].
scalar;
1710 g.
factors.push_back(gamma * sqrt_minus_one.inverse());
1712 g.
factors.push_back(gamma * ratio_inverse_power);
1713 ratio_inverse_power =
1714 ratio_inverse_power * ratio_inverse_power;
1719 std::vector<FieldElement> coefficients;
1720 coefficients.reserve(norm.c_vec.size());
1721 for (
const auto& encoded : norm.c_vec) {
1725 "accumulation:v4_coefficient");
1726 coefficients.push_back(std::move(coefficient));
1728 const auto coefficient_basis =
1729 std::span(basis.
points())
1733 msm(coefficient_basis, coefficients, context),
1734 "accumulation:v4_coefficient_commitment");
1736 transcript_input.coefficient_commitment) {
1739 "accumulation:v4_coefficient_binding");
1743 transcript.prepared_binding.scalar;
1744 auto norm_data = std::move(prepared).take_norm();
1745 auto c_vec = std::move(norm_data.c_vec);
1746 return AlgebraicPreparedNorm(
1749 std::array<PolynomialTerm, 2>{std::move(g), std::move(h)});
1757 std::vector<FieldElement> coefficients;
1758 coefficients.reserve(norm.
c_vec().size());
1759 for (
const auto& encoded : norm.
c_vec()) {
1761 "accumulation:coefficient_scalar");
1762 coefficients.push_back(coefficient);
1765 const std::array<PolynomialTerm, 1> tensor{weights};
1769 for (std::size_t i = 0; i < coefficients.size(); ++i) {
1770 evaluation = evaluation + coefficients[i] * expanded_weights[i];
1775 "accumulation:prove_reduction_context");
1778 prove_ipa(h_basis, std::move(coefficients), state.weights, state.opening_base,
1779 state.transcript, context),
"accumulation:prove_coefficient_ipa");
1782 "accumulation:prove_reduction_check");
1791 const auto rounds = log2_dimension(basis.
l_vec_len());
1793 if (opening.left.size() != rounds || opening.right.size() != rounds) {
1797 "accumulation:reduction_terminal");
1800 "accumulation:verify_reduction_context");
1803 state.evaluation, state.opening_base, state.transcript, context),
1804 "accumulation:verify_coefficient_ipa");
1812 const std::array<PointBytes, 2> norm_points{norm.
residual(), generator};
1813 const std::array<FieldElement, 2> norm_scalars{
1816 "accumulation:unshifted_norm_claim");
1821 append(encoded, basis.
digest());
1823 append(encoded, state.transcript);
1825 append_ipa(encoded, opening);
1826 append(encoded, norm_point);
1827 append_polynomial(encoded, norm.
polynomial());
1828 append(encoded, opening.folded_generator);
1829 const std::array<PolynomialTerm, 1> folded_polynomial{folded};
1830 append_polynomial(encoded, folded_polynomial);
1832 const std::array<PointBytes, 2> fusion_points{norm_point, opening.folded_generator};
1835 "accumulation:combined_reduction_claim");
1837 folded.scale = folded.scale * chi;
1839 return PendingClaim(basis.
digest(), combined_point, std::move(
polynomial));
1848 "accumulation:context");
1850 validate_basis(basis),
"accumulation:basis");
1852 validate_algebraic_prepared(basis, norm),
1853 "accumulation:algebraic_prepared");
1855 std::vector<FieldElement> coefficients;
1856 coefficients.reserve(norm.
c_vec().size());
1857 for (
const auto& encoded : norm.
c_vec()) {
1861 "accumulation:algebraic_coefficient_scalar");
1862 coefficients.push_back(coefficient);
1867 const std::array<PolynomialTerm, 1> tensor{weights};
1868 std::vector<FieldElement> expanded_weights(
1873 for (std::size_t i = 0; i < coefficients.size(); ++i) {
1874 evaluation = evaluation +
1875 coefficients[i] * expanded_weights[i];
1882 make_algebraic_norm_context(
1884 "accumulation:prove_algebraic_reduction_context");
1885 const auto h_basis = std::span(basis.
points()).subspan(
1889 prove_algebraic_ipa(
1890 h_basis, std::move(coefficients), state.weights,
1891 state.opening_base, state.transcript, 0, context),
1892 "accumulation:prove_algebraic_coefficient_ipa");
1896 basis, norm, proof, context),
1897 "accumulation:prove_algebraic_reduction_check");
1907 validate_basis(basis),
"accumulation:basis");
1909 validate_algebraic_prepared(basis, norm),
1910 "accumulation:algebraic_prepared");
1911 const auto rounds = log2_dimension(basis.
l_vec_len());
1913 if (opening.left.size() != rounds ||
1914 opening.right.size() != rounds) {
1917 "accumulation:algebraic_reduction_rounds");
1922 "accumulation:algebraic_reduction_terminal");
1925 make_algebraic_norm_context(
1927 "accumulation:verify_algebraic_reduction_context");
1930 verify_algebraic_ipa(
1931 basis.
l_vec_len(), opening, state.weights,
1933 state.opening_base, state.transcript, 0, context),
1934 "accumulation:verify_algebraic_coefficient_ipa");
1940 context, generator_encoding.data(), 1,
1941 generator.data()) == 0) {
1944 "accumulation:algebraic_standard_generator");
1946 const std::array<PointBytes, 2> norm_points{
1948 const std::array<FieldElement, 2> norm_scalars{
1952 auto norm_point, msm(norm_points, norm_scalars, context),
1953 "accumulation:algebraic_unshifted_norm_claim");
1957 state.transcript.append_scalar(terminal);
1959 append_algebraic_point(
1960 state.transcript, opening.folded_generator),
1961 "accumulation:algebraic_folded_generator");
1963 append_algebraic_point(state.transcript, norm_point),
1964 "accumulation:algebraic_norm_point");
1966 append_algebraic_polynomial(
1968 "accumulation:algebraic_norm_polynomial");
1969 const std::array<PolynomialTerm, 1> folded_polynomial{folded};
1971 append_algebraic_polynomial(
1972 state.transcript, folded_polynomial),
1973 "accumulation:algebraic_folded_polynomial");
1976 append_algebraic_challenge(
1978 static_cast<std::uint64_t
>(rounds)),
1979 "accumulation:algebraic_reduction_fusion");
1981 const std::array<PointBytes, 2> fusion_points{
1982 norm_point, opening.folded_generator};
1983 const std::array<FieldElement, 2> fusion_scalars{
1986 auto combined_point,
1987 msm(fusion_points, fusion_scalars, context),
1988 "accumulation:algebraic_combined_reduction_claim");
1991 folded.scale = folded.scale * chi;
1993 return PendingClaim(
2000 "accumulation:prove_context");
2003 for (
const auto& claim : claims) {
2004 add_coefficients(a, claim.polynomial(), weight);
2005 weight = weight * state.beta;
2007 const auto weights = geometric_tensor(state.x, basis.
dimension());
2009 prove_ipa(basis.
points(), std::move(a), weights, state.opening_base, state.transcript, context),
2010 "accumulation:prove_ipa");
2014 "accumulation:prove_check");
2022 const auto rounds = log2_dimension(basis.
dimension());
2023 if (proof.
left.size() != rounds || proof.
right.size() != rounds) {
2027 "accumulation:step_terminal_scalar");
2030 "accumulation:verify_context");
2031 const auto weights = geometric_tensor(state.x, basis.
dimension());
2033 verify_ipa(basis.
dimension(), proof, weights, state.commitment, state.y,
2034 state.opening_base, state.transcript, context),
"accumulation:verify_ipa");
2041 const Basis& basis, std::span<const PendingClaim> claims,
2045 make_algebraic_step_context(
2046 basis, claims, statement_digest, context),
2047 "accumulation:prove_algebraic_context");
2048 std::vector<FieldElement> coefficients(
2051 for (
const auto& claim : claims) {
2053 coefficients, claim.polynomial(), weight);
2054 weight = weight * state.beta;
2056 const auto weights =
2057 geometric_tensor(state.x, basis.
dimension());
2060 prove_algebraic_ipa(
2061 basis.
points(), std::move(coefficients), weights,
2062 state.opening_base, state.transcript, 2, context),
2063 "accumulation:prove_algebraic_ipa");
2066 statement_digest ==
nullptr
2067 ? verify_algebraic_step(
2068 basis, claims, proof, context)
2069 : verify_bound_algebraic_step(
2070 basis, claims, *statement_digest, proof, context),
2071 "accumulation:prove_algebraic_check");
2076struct AlgebraicStepPendingData {
2078 PolynomialTerm polynomial;
2082 const Basis& basis, std::span<const PendingClaim> claims,
2083 const Digest* statement_digest,
const AlgebraicStepProof& proof,
2086 validate_basis(basis),
"accumulation:basis");
2087 const auto rounds = log2_dimension(basis.dimension());
2088 if (proof.left.size() != rounds ||
2089 proof.right.size() != rounds) {
2092 "accumulation:algebraic_step_rounds");
2097 "accumulation:algebraic_step_terminal_scalar");
2101 make_algebraic_step_context(
2102 basis, claims, statement_digest, context),
2103 "accumulation:verify_algebraic_context");
2104 const auto weights =
2105 geometric_tensor(state.x, basis.dimension());
2108 verify_algebraic_ipa(
2109 basis.dimension(), proof, weights,
2110 state.commitment, state.y, state.opening_base,
2111 state.transcript, 2, context),
2112 "accumulation:verify_algebraic_ipa");
2113 return AlgebraicStepPendingData{
2114 proof.folded_generator, std::move(folded)};
2120 const Basis& basis, std::span<const PendingClaim> claims,
2122 return prove_algebraic_step_impl(
2123 basis, claims,
nullptr, context);
2127 const Basis& basis, std::span<const PendingClaim> claims,
2132 verify_algebraic_step_impl(
2133 basis, claims,
nullptr, proof, context),
2134 "accumulation:verify_algebraic_step");
2135 return PendingClaim(
2136 basis.
digest(), pending.point,
2137 {std::move(pending.polynomial)});
2141 const Basis& basis, std::span<const PendingClaim> claims,
2143 return prove_algebraic_step_impl(
2144 basis, claims, &statement_digest, context);
2148 const Basis& basis, std::span<const PendingClaim> claims,
2153 verify_algebraic_step_impl(
2154 basis, claims, &statement_digest, proof, context),
2155 "accumulation:verify_bound_algebraic_step");
2156 return PendingClaim(
2157 basis.
digest(), pending.point,
2158 {std::move(pending.polynomial)});
2161#if defined(PURIFY_INTERNAL_TEST_SUPPORT)
2165 const Basis& basis, std::span<const PendingClaim> claims,
2169 validate_basis(basis),
"accumulation:test_basis");
2170 const auto rounds = log2_dimension(basis.
dimension());
2171 if (proof.
left.size() != rounds ||
2172 proof.
right.size() != rounds) {
2175 "accumulation:test_step_rounds");
2179 make_algebraic_step_context(basis, claims,
nullptr, context),
2180 "accumulation:test_step_context");
2181 const auto weights =
2182 geometric_tensor(state.x, basis.
dimension());
2185 evaluate_algebraic_ipa(
2187 state.commitment, state.y, state.opening_base,
2188 state.transcript, 2, context),
2189 "accumulation:test_step_evaluate");
2190 return evaluated.residual;
2198 "accumulation:context");
2204 "accumulation:decide_msm");
2205 if (expected != claim.
point()) {
int purify_bppp_prepare_norm_arg_claim_with_challenges(purify_secp_context *context, const unsigned char rho32[32], const unsigned char *generators33, size_t generators_count, const unsigned char *c_vec32, size_t c_vec_len, size_t n_vec_len, const unsigned char commitment33[33], const unsigned char *proof, size_t proof_len, const unsigned char *gammas32, size_t gamma_count, unsigned char terminal_n32[32], unsigned char terminal_l32[32], unsigned char residual33[33])
int purify_bppp_scale_generator(purify_secp_context *context, const unsigned char generator33[33], const unsigned char scalar32[32], unsigned char out33[33])
int purify_bppp_prepare_norm_arg_claim(purify_secp_context *context, const unsigned char rho32[32], const unsigned char *generators33, size_t generators_count, const unsigned char *c_vec32, size_t c_vec_len, size_t n_vec_len, const unsigned char commitment33[33], const unsigned char *proof, size_t proof_len, unsigned char terminal_n32[32], unsigned char terminal_l32[32], unsigned char *gammas32, size_t gamma_count, unsigned char residual33[33])
int purify_bppp_public_point_validate(const unsigned char point33[33])
int purify_bppp_public_msm(purify_secp_context *context, const unsigned char *points33, const unsigned char *scalars32, size_t count, unsigned char out33[33])
int purify_bppp_public_hash_to_point(purify_secp_context *context, const unsigned char *input, size_t input_len, unsigned char out33[33])
int purify_bppp_generators_to_points(purify_secp_context *context, const unsigned char *generators33, size_t generators_count, unsigned char *points_out33)
C ABI bridging Purify C++ code to secp256k1-zkp BPPP functionality.
static FieldElement one()
Returns the multiplicative identity of the scalar field.
static Result< FieldElement > try_from_bytes32(const std::array< unsigned char, 32 > &bytes)
Decodes a canonical 32-byte big-endian field element.
FieldElement negate() const
Returns the additive inverse modulo the field prime.
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.
Common interface for reusable experimental BPPP backend state.
const PointBytes & residual() const
friend Result< AlgebraicPreparedNorm > prepare_v4_circuit_norm_for_algebraic_reduction(const Basis &, candidate::PreparedCircuitZkNormArgV4, purify_secp_context *)
const std::vector< ScalarBytes > & c_vec() const
const FieldElement & prepared_binding() const
const std::array< PolynomialTerm, 2 > & polynomial() const
const PointBytes & coefficient_commitment() const
std::size_t n_vec_len() const
static Result< Basis > create(std::size_t n_vec_len, std::size_t l_vec_len, std::string_view semantic_domain, purify_secp_context *context)
std::size_t dimension() const
const Digest & digest() const
const std::vector< PointBytes > & points() const
std::size_t l_vec_len() const
const std::vector< PointBytes > & norm_generators() const
friend Result< PendingClaim > verify_algebraic_norm_reduction(const Basis &, const AlgebraicPreparedNorm &, const AlgebraicNormReductionProof &, purify_secp_context *)
const std::vector< PolynomialTerm > & polynomial() const
friend Result< PendingClaim > verify_algebraic_step(const Basis &, std::span< const PendingClaim >, const AlgebraicStepProof &, purify_secp_context *)
friend Result< PendingClaim > canonical_zero_claim(const Basis &)
const PointBytes & point() const
friend Result< PendingClaim > verify_norm_reduction(const Basis &, const PreparedNorm &, const NormReductionProof &, purify_secp_context *)
friend Result< PendingClaim > verify_bound_algebraic_step(const Basis &, std::span< const PendingClaim >, const Digest &, const AlgebraicStepProof &, purify_secp_context *)
friend Result< PendingClaim > verify_step(const Basis &, std::span< const PendingClaim >, const StepProof &, purify_secp_context *)
const std::array< PolynomialTerm, 2 > & polynomial() const
const PointBytes & residual() const
friend Result< PreparedNorm > prepare_experimental_circuit_zk_norm_arg(const Basis &, const NativeBulletproofCircuit &, const ExperimentalCircuitZkNormArgProof &, purify_secp_context *, std::span< const unsigned char >, ExperimentalCircuitBackend *)
friend Result< PreparedNorm > prepare_norm(const Basis &, const NormArgProof &, purify_secp_context *)
friend Result< PreparedNorm > prepare_experimental_circuit_zk_norm_arg_with_public_commitments(const Basis &, const NativeBulletproofCircuit &, const ExperimentalCircuitZkNormArgProof &, std::span< const PointBytes >, purify_secp_context *, std::span< const unsigned char >, ExperimentalCircuitBackend *)
const PointBytes & coefficient_commitment() const
const Digest & transcript_digest() const
const std::vector< ScalarBytes > & c_vec() const
const std::vector< PointBytes > & raw_generators() const noexcept
const CircuitProofTranscriptResultV4 & transcript() const noexcept
const CircuitTranscriptShapeV4 & shape() const noexcept
const CircuitProofTranscriptInputV4 & transcript_input() const noexcept
const NormArgProof & norm() const noexcept
const PointBytes & pending_norm_residual() const noexcept
#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.
Result< StepProof > prove_step(const Basis &basis, std::span< const PendingClaim > claims, purify_secp_context *context)
Result< Bytes > serialize_root_claim(const Basis &basis, const PendingClaim &claim, purify_secp_context *context)
Result< PendingClaim > parse_root_claim(const Basis &basis, std::span< const unsigned char > encoded, purify_secp_context *context)
Result< AlgebraicNormReductionProof > prove_algebraic_norm_reduction(const Basis &basis, const AlgebraicPreparedNorm &norm, purify_secp_context *context)
Result< AlgebraicStepProof > parse_algebraic_step(const Basis &basis, std::span< const unsigned char > encoded, purify_secp_context *context)
Result< PendingClaim > verify_norm_reduction(const Basis &basis, const PreparedNorm &norm, const NormReductionProof &proof, purify_secp_context *context)
Result< NormReductionProof > parse_norm_reduction(const Basis &basis, std::span< const unsigned char > encoded, purify_secp_context *context)
Result< AlgebraicNormReductionProof > parse_algebraic_norm_reduction(const Basis &basis, std::span< const unsigned char > encoded, purify_secp_context *context)
Result< AlgebraicStepProof > prove_algebraic_step(const Basis &basis, std::span< const PendingClaim > claims, purify_secp_context *context)
Result< PendingClaim > verify_algebraic_norm_reduction(const Basis &basis, const AlgebraicPreparedNorm &norm, const AlgebraicNormReductionProof &proof, purify_secp_context *context)
Result< Bytes > serialize_norm_reduction(const Basis &basis, const NormReductionProof &proof, purify_secp_context *context)
Result< StepProof > parse_step(const Basis &basis, std::span< const unsigned char > encoded, purify_secp_context *context)
Status decide(const Basis &basis, const PendingClaim &claim, purify_secp_context *context)
Result< AlgebraicStepProof > prove_bound_algebraic_step(const Basis &basis, std::span< const PendingClaim > claims, const Digest &statement_digest, purify_secp_context *context)
std::array< unsigned char, 32 > Digest
Result< NormReductionProof > prove_norm_reduction(const Basis &basis, const PreparedNorm &norm, purify_secp_context *context)
Result< Bytes > serialize_algebraic_norm_reduction(const Basis &basis, const AlgebraicNormReductionProof &proof, purify_secp_context *context)
Result< Bytes > serialize_algebraic_step(const Basis &basis, const AlgebraicStepProof &proof, purify_secp_context *context)
Result< Bytes > serialize_step(const Basis &basis, const StepProof &proof, purify_secp_context *context)
Result< PendingClaim > verify_step(const Basis &basis, std::span< const PendingClaim > claims, const StepProof &proof, purify_secp_context *context)
std::array< unsigned char, 32 > TranscriptBytes32
std::array< unsigned char, 65 > PackedPointPairV4
Result< std::optional< PreparedExperimentalCircuitZkNormArg > > prepare_experimental_circuit_zk_norm_arg(const NativeBulletproofCircuit &circuit, const ExperimentalCircuitZkNormArgProof &proof, purify_secp_context *secp_context, std::span< const unsigned char > statement_binding, ExperimentalCircuitBackend *cache)
Result< std::optional< PreparedExperimentalCircuitZkNormArg > > prepare_experimental_circuit_zk_norm_arg_with_public_commitments(const NativeBulletproofCircuit &circuit, const ExperimentalCircuitZkNormArgProof &proof, std::span< const PointBytes > public_commitments, purify_secp_context *secp_context, std::span< const unsigned char > statement_binding, ExperimentalCircuitBackend *cache)
Result< FieldElement > canonical_sqrt_minus_one()
GeneratorBytes base_generator(purify_secp_context *secp_context)
Returns the serialized secp256k1 base generator used as the blind generator.
Result< std::vector< PointBytes > > create_generators(std::size_t count, purify_secp_context *secp_context)
Expands the BPPP generator list.
std::array< unsigned char, 33 > PointBytes
Compressed 33-byte curve-point encoding.
std::array< unsigned char, 32 > ScalarBytes
Big-endian 32-byte scalar encoding.
Status require_secp_context(const purify_secp_context *context, const char *error_context)
constexpr Unexpected< Error > unexpected_error(ErrorCode code, const char *context=nullptr)
Constructs an unexpected Error value from a machine-readable code.
bool size_fits_u64(std::size_t value) noexcept
bool is_power_of_two_size(std::size_t value) noexcept
bool checked_mul_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
Expected< T, Error > Result
Expected-returning convenience alias for Purify value-producing APIs.
Expected< void, Error > Status
Expected-returning convenience alias for Purify status-only APIs.
std::vector< unsigned char > Bytes
Dynamically sized byte string used for messages, serialized witnesses, and proofs.
bool checked_add_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
void purify_sha256(unsigned char output32[32], const unsigned char *data, size_t data_len)
Computes SHA-256 over a byte string.
struct purify_secp_context purify_secp_context
Caller-owned reusable secp256k1 context handle shared across Purify C and C++ APIs.
Native in-memory representation of a Bulletproof-style arithmetic circuit.
Masked circuit proof with a pre-challenge raw-coordinate commitment.
Standalone BPPP norm-argument proof bundle with all verifier-side inputs.
std::vector< PointBytes > generators
std::vector< ScalarBytes > c_vec
PointBytes commitment
Finite compressed initial point; infinity is not accepted.
ScalarBytes coefficient_evaluation
AlgebraicStepProof coefficient_opening
std::vector< PointBytes > left
std::vector< PointBytes > right
ScalarBytes coefficient_evaluation
StepProof coefficient_opening
std::vector< FieldElement > factors
ScalarBytes terminal_scalar
PointBytes folded_generator
std::vector< PointBytes > left
std::vector< PointBytes > right