purify
C++ Purify implementation with native circuit and BPP support
Loading...
Searching...
No Matches
certificate_nonce_parent_accumulation.cpp
Go to the documentation of this file.
1// Copyright (c) 2026 Judica, Inc.
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or https://opensource.org/license/mit/.
4
6
7#include "bppp_bridge.h"
8
9#include <algorithm>
10#include <array>
11#include <limits>
12#include <set>
13#include <type_traits>
14#include <utility>
15
17namespace {
18
19constexpr unsigned char kPublicInputVersion = 1;
20constexpr unsigned char kTreeNodeVersion = 1;
21constexpr std::size_t kRecursiveMemberMessageSize =
22 8 + 4 + 32 + 96 + 32 + 32 + 33 + 33 + 32;
23constexpr std::size_t kRecursiveStepMessageSize =
24 32 + 32 + 4 + 32 + 32 + 32;
25constexpr std::size_t kRecursiveManifestSeedMessageSize = 32 + 8;
26constexpr std::size_t kRecursiveManifestStepMessageSize =
27 32 + 8 + 4 + 32;
28constexpr std::array<unsigned char, 16> kNativeReceiptMagic{
29 'P', 'u', 'r', 'i', 'f', 'y', '/', 'C',
30 'e', 'r', 't', 'W', 'i', 't', '/', '1'};
32 4'096);
33static_assert(
35 66 * 12 + 98);
36static_assert(
38 66 * 13 + 66);
39static_assert(PublicKey::kSerializedSize == 96);
40static_assert(bppp::PointBytes{}.size() == 33);
41static_assert(bppp::accumulation::Digest{}.size() == 32);
42static_assert(
44 66 * 12 + 98);
45static_assert(
47 66 * 13 + 66);
48const TaggedHash kResponseStatementHash(
49 "Purify/Accountable/CertificateNonceResponse/v1");
50const TaggedHash kResponseAuthorizationHash(
51 "Purify/Accountable/CertificateResponseAuthorization/v1");
52const TaggedHash kResponseAuthorizationCommonHash(
53 "Purify/Accountable/CertificateResponseCommon/v1");
54const TaggedHash kResponseAuthorizationBindingHash(
55 "Purify/Accountable/CertificateResponseBinding/v1");
56const TaggedHash kMemberAuthorizationHash(
57 "Purify/Accountable/CertificateMemberAuthorization/v1");
58const TaggedHash kRecursiveMemberHash(
59 "Purify/Accountable/CertificateRecursiveMember/v1");
60const TaggedHash kRecursiveStepHash(
61 "Purify/Accountable/CertificateRecursiveStep/v1");
62const TaggedHash kRecursiveManifestSeedHash(
63 "Purify/Accountable/CertificateRecursiveManifest/v1/init");
64const TaggedHash kRecursiveManifestStepHash(
65 "Purify/Accountable/CertificateRecursiveManifest/v1/member");
66const TaggedHash kAuthorizationManifestSeedHash(
67 "Purify/Accountable/CertificateAuthorizationManifest/v1/init");
68const TaggedHash kAuthorizationManifestStepHash(
69 "Purify/Accountable/CertificateAuthorizationManifest/v1/member");
70const TaggedHash kTreeNodeHash(
71 "Purify/Accountable/CertificateNonceTreeNode/v1");
72
73template <std::size_t N>
74void append(Bytes& out, const std::array<unsigned char, N>& value) {
75 out.insert(out.end(), value.begin(), value.end());
76}
77
78void append(Bytes& out, std::span<const unsigned char> value) {
79 out.insert(out.end(), value.begin(), value.end());
80}
81
82void append_u32(Bytes& out, std::uint32_t value) {
83 out.push_back(static_cast<unsigned char>(value >> 24));
84 out.push_back(static_cast<unsigned char>(value >> 16));
85 out.push_back(static_cast<unsigned char>(value >> 8));
86 out.push_back(static_cast<unsigned char>(value));
87}
88
89void append_u64(Bytes& out, std::uint64_t value) {
90 for (unsigned int shift = 56; shift != 0; shift -= 8) {
91 out.push_back(static_cast<unsigned char>(value >> shift));
92 }
93 out.push_back(static_cast<unsigned char>(value));
94}
95
96std::uint64_t read_u64(std::span<const unsigned char> encoded)
97{
98 assert(encoded.size() == sizeof(std::uint64_t));
99 std::uint64_t value = 0;
100 for (const auto byte : encoded) {
101 value = (value << 8) | byte;
102 }
103 return value;
104}
105
106bool is_zero(const bppp::accumulation::Digest& digest) {
107 return std::ranges::all_of(
108 digest, [](unsigned char byte) { return byte == 0; });
109}
110
111template <typename Count>
112constexpr bool exceeds_response_limit(Count count) noexcept
113{
114 static_assert(std::is_unsigned_v<Count>);
115 if constexpr (
116 std::numeric_limits<Count>::max() <=
118 return false;
119 }
121}
122
123Status validate_recursive_member_frame(
124 const CertificateNonceResponseAuthorization& authorization,
125 std::uint32_t member_ordinal)
126{
127 const auto& frame = authorization.frame();
128 const auto member_digests = authorization.member_digests();
129 if (frame.total_responses == 0 ||
130 frame.total_responses >
132 frame.response_ordinal >= frame.total_responses ||
133 member_digests.empty() ||
134 member_digests.size() >
136 member_ordinal >= member_digests.size()) {
137 return unexpected_error(
139 "certificate_nonce_recursive:member_frame");
140 }
141 return {};
142}
143
144Status validate_recursive_public_response(
146{
147 const auto hosts = response.ordered_hosts();
148 const auto leaves = response.ordered_leaves();
149 const auto member_digests =
150 response.authorization().member_digests();
151 if (hosts.empty() ||
152 hosts.size() >
154 hosts.size() != leaves.size() ||
155 hosts.size() != member_digests.size()) {
156 return unexpected_error(
158 "certificate_nonce_recursive:public_response_members");
159 }
160
161 std::set<bppp::accumulation::Digest> unique_leaf_bindings;
162 for (const auto& leaf : leaves) {
163 if (!unique_leaf_bindings.insert(leaf.leaf_binding).second) {
164 return unexpected_error(
166 "certificate_nonce_recursive:public_response_leaf");
167 }
168 }
169 return validate_recursive_member_frame(
170 response.authorization(), 0);
171}
172
174recursive_member_digest_from_derived_constants(
175 const CertificateNonceResponseAuthorization& authorization,
176 std::uint32_t member_ordinal, const PublicKey& host,
177 std::span<const unsigned char> topic,
179 const bppp::accumulation::Digest& leaf_binding)
180{
181 const auto& frame = authorization.frame();
182 const auto member_digests = authorization.member_digests();
183 const auto host_bytes = host.serialize();
184 if (host_bytes.size() != PublicKey::kSerializedSize) {
185 return unexpected_error(
187 "certificate_nonce_recursive:member_host");
188 }
189
190 Bytes encoded;
191 encoded.reserve(kRecursiveMemberMessageSize);
192 append_u64(encoded, frame.response_ordinal);
193 append_u32(encoded, member_ordinal);
194 append(encoded, member_digests[member_ordinal]);
195 append(encoded, host_bytes);
196 append(encoded, topic);
197 append(encoded, constants.circuit_binding_digest);
198 append(encoded, constants.coefficient_commitment);
199 append(encoded, constants.anchored_offset);
200 append(encoded, leaf_binding);
201 assert(encoded.size() == kRecursiveMemberMessageSize);
202 return kRecursiveMemberHash.digest(encoded);
203}
204
206recursive_member_digest_from_public_descriptor(
207 const CertificateNonceLeafAccumulator& leaf_accumulator,
208 const CertificateNonceResponseAuthorization& authorization,
209 std::uint32_t member_ordinal, const PublicKey& host,
210 const CertificateNoncePublicLeafDescriptor& descriptor,
211 std::span<const unsigned char> topic,
212 const TopicProofCache& cache,
213 purify_secp_context* secp_context)
214{
216 const auto constants,
217 leaf_accumulator.derive_parent_constants_from_public_data(
218 host, cache, descriptor.circuit_precommitment,
219 descriptor.nonce_point, secp_context),
220 "certificate_nonce_recursive:public_member_constants");
221 return recursive_member_digest_from_derived_constants(
222 authorization, member_ordinal, host, topic, constants,
223 descriptor.leaf_binding);
224}
225
227recursive_response_step_digests_from_validated(
228 const CertificateNonceLeafAccumulator& leaf_accumulator,
230 purify_secp_context* secp_context)
231{
232 const auto hosts = response.ordered_hosts();
233 const auto leaves = response.ordered_leaves();
235 const auto topic,
237 response.context(), secp_context),
238 "certificate_nonce_recursive:public_response_topic");
240 const auto cache, TopicProofCache::build(topic),
241 "certificate_nonce_recursive:public_response_cache");
242
243 std::vector<bppp::accumulation::Digest> step_digests;
244 step_digests.reserve(hosts.size());
245 for (std::size_t member_index = 0;
246 member_index < hosts.size(); ++member_index) {
248 const auto member_digest,
249 recursive_member_digest_from_public_descriptor(
250 leaf_accumulator, response.authorization(),
251 static_cast<std::uint32_t>(member_index),
252 hosts[member_index], leaves[member_index], topic,
253 cache, secp_context),
254 "certificate_nonce_recursive:public_response_member");
256 auto step_digest,
258 response.authorization(), response.context(),
259 response.canonical_body(), response.response(),
260 member_digest, secp_context),
261 "certificate_nonce_recursive:public_response_step");
262 step_digests.push_back(std::move(step_digest));
263 }
264 return step_digests;
265}
266
267Status validate_authorization_inputs(
269 const accountable::NonceHostBoundSigningRoster& roster,
270 const accountable::ConflictContext& context,
271 std::span<const PublicKey> ordered_hosts,
272 std::span<const unsigned char> canonical_body,
273 purify_secp_context* secp_context)
274{
275 if (is_zero(frame.certificate_context_digest) ||
276 frame.total_responses == 0 ||
277 frame.total_responses >
279 frame.response_ordinal >= frame.total_responses ||
280 frame.electorate_weight == 0) {
281 return unexpected_error(
283 "certificate_nonce_authorization:frame");
284 }
285 if (frame.scope !=
287 return unexpected_error(
289 "certificate_nonce_authorization:scope");
290 }
291 if (ordered_hosts.empty() ||
292 ordered_hosts.size() >
294 kMemberBatchCapacity ||
295 roster.members().size() != ordered_hosts.size()) {
296 return unexpected_error(
298 "certificate_nonce_authorization:member_count");
299 }
301 const auto registered_hosts,
303 roster, ordered_hosts, secp_context),
304 "certificate_nonce_authorization:host_commitment");
305 if (registered_hosts != roster.nonce_host_commitment() ||
306 context.host_commitment != registered_hosts ||
307 context.signing_key != roster.signing_key() ||
308 context.coalition_core_digest !=
309 roster.coalition_core_digest()) {
310 return unexpected_error(
312 "certificate_nonce_authorization:roster");
313 }
314 if (!size_fits_u64(context.slot.size()) ||
315 !size_fits_u64(canonical_body.size())) {
316 return unexpected_error(
318 "certificate_nonce_authorization:length");
319 }
321 const auto nonce_input,
322 accountable::nonce_evaluation_input(context, secp_context),
323 "certificate_nonce_authorization:nonce_input");
325 const auto challenge,
327 context, canonical_body, secp_context),
328 "certificate_nonce_authorization:challenge");
329 (void)nonce_input;
330 (void)challenge;
331 return {};
332}
333
334void append_authorization_prefix(
335 Bytes& encoded, const CertificateNonceResponseFrame& frame,
336 const accountable::NonceHostBoundSigningRoster& roster,
337 const accountable::ConflictContext& context,
338 std::span<const unsigned char> canonical_body,
339 const accountable::ScalarSignature& response,
340 std::size_t member_count)
341{
342 encoded.push_back(kPublicInputVersion);
343 encoded.push_back(static_cast<unsigned char>(frame.scope));
344 append_u32(
345 encoded, static_cast<std::uint32_t>(
347 kMemberBatchCapacity));
348 append(encoded, frame.certificate_context_digest);
349 append_u64(encoded, frame.total_responses);
350 append_u64(encoded, frame.response_ordinal);
351 append_u32(encoded, frame.electorate_index);
352 append_u64(encoded, frame.electorate_weight);
353 append(encoded, context.signing_key);
354 append(encoded, context.host_commitment);
355 append(encoded, context.coalition_core_digest);
356 append_u64(encoded, static_cast<std::uint64_t>(context.slot.size()));
357 append(encoded, context.slot);
358 append_u64(
359 encoded, static_cast<std::uint64_t>(canonical_body.size()));
360 append(encoded, canonical_body);
361 append(encoded, response.serialize());
362 append(encoded, roster.key_list_hash());
363 encoded.push_back(
364 static_cast<unsigned char>(roster.aggregate_was_negated()));
365 append_u32(encoded, static_cast<std::uint32_t>(member_count));
366}
367
368void append_authorization_member(
369 Bytes& encoded, std::size_t index,
370 const accountable::SigningRosterMember& member,
371 const PublicKey& host)
372{
373 append_u32(encoded, static_cast<std::uint32_t>(index));
374 append(encoded, member.public_key);
375 append(encoded, member.coefficient.to_bytes_be());
376 append(encoded, host.serialize());
377}
378
379Result<bppp::PointBytes> sum_nonces(
380 std::span<const PreparedCertificateNonceLeaf> leaves,
381 purify_secp_context* secp_context) {
382 std::optional<bppp::PointBytes> aggregate;
383 for (const auto& leaf : leaves) {
384 const auto& point = leaf.nonce_point();
385 if (!aggregate) {
386 aggregate = point;
387 } else if ((*aggregate)[0] != point[0] &&
388 std::equal(aggregate->begin() + 1, aggregate->end(),
389 point.begin() + 1)) {
390 aggregate.reset();
391 } else {
392 bppp::PointBytes next{};
393 if (purify_point_add(secp_context, aggregate->data(),
394 point.data(), next.data()) == 0) {
395 return unexpected_error(
397 "certificate_nonce_parent:nonce_sum");
398 }
399 aggregate = next;
400 }
401 }
402 if (!aggregate) {
403 return unexpected_error(
405 "certificate_nonce_parent:nonce_infinity");
406 }
407 return *aggregate;
408}
409
410Status match_inputs_and_leaves(
412 std::span<const PreparedCertificateNonceLeaf> leaves) {
413 if (inputs.leaf_bindings().size() != leaves.size() ||
414 inputs.member_nonces().size() != leaves.size() ||
415 inputs.recursive_step_digests().size() != leaves.size()) {
416 return unexpected_error(
418 "certificate_nonce_parent:leaf_count");
419 }
420 for (std::size_t index = 0; index < leaves.size(); ++index) {
421 if (inputs.leaf_bindings()[index] !=
422 leaves[index].binding_digest() ||
423 inputs.member_nonces()[index] !=
424 leaves[index].nonce_point()) {
425 return unexpected_error(
427 "certificate_nonce_parent:leaf_order");
428 }
429 }
430 return {};
431}
432
433struct ParentMetadata {
434 bppp::accumulation::Digest certificate_context_digest{};
435 bppp::accumulation::Digest node_digest{};
436 std::uint64_t total_responses = 0;
437 std::uint32_t level = 0;
438 std::uint64_t first_response = 0;
439 std::uint64_t response_count = 0;
440};
441
442Result<std::uint64_t> level_span(std::uint32_t level) {
443 std::uint64_t span = 1;
444 for (std::uint32_t index = 0; index < level; ++index) {
445 if (span > std::numeric_limits<std::uint64_t>::max() /
447 return unexpected_error(
449 "certificate_nonce_tree:level_span");
450 }
452 }
453 return span;
454}
455
456Result<std::size_t> native_tree_proof_count(
457 std::size_t response_count)
458{
459 if (response_count == 0 ||
460 exceeds_response_limit(response_count)) {
461 return unexpected_error(
463 "certificate_nonce_native:response_count");
464 }
465 std::size_t proof_count = 0;
466 auto level_count = response_count;
467 while (level_count > 1) {
468 const auto parent_count =
469 1 + (level_count - 1) /
471 if (!checked_add_size(
472 proof_count, parent_count, proof_count)) {
473 return unexpected_error(
475 "certificate_nonce_native:tree_count");
476 }
477 level_count = parent_count;
478 }
479 return proof_count;
480}
481
482Status validate_native_receipt_shape(
483 const bppp::accumulation::Digest& context_digest,
484 std::span<const CertificateNonceNativeResponse> responses,
485 std::span<const CertificateNonceTreeProof> tree_proofs)
486{
487 if (is_zero(context_digest)) {
488 return unexpected_error(
490 "certificate_nonce_native:context_digest");
491 }
493 const auto expected_tree_proofs,
494 native_tree_proof_count(responses.size()),
495 "certificate_nonce_native:tree_shape");
496 if (tree_proofs.size() != expected_tree_proofs) {
497 return unexpected_error(
499 "certificate_nonce_native:tree_proofs");
500 }
501 for (const auto& response : responses) {
502 if (is_zero(response.statement_digest()) ||
503 response.proof().reductions.empty() ||
504 response.proof().reductions.size() >
506 kMemberBatchCapacity) {
507 return unexpected_error(
509 "certificate_nonce_native:member_count");
510 }
511 }
512 return {};
513}
514
515Status validate_linear_receipt_shape(
516 const bppp::accumulation::Digest& context_digest,
517 std::span<const CertificateNonceLinearResponseProof> responses)
518{
519 if (is_zero(context_digest) || responses.empty() ||
520 exceeds_response_limit(responses.size())) {
521 return unexpected_error(
523 "certificate_nonce_linear:response_count");
524 }
525 for (const auto& response : responses) {
526 if (response.members.empty() ||
527 response.members.size() >
529 kMemberBatchCapacity) {
530 return unexpected_error(
532 "certificate_nonce_linear:member_count");
533 }
534 }
535 return {};
536}
537
538Result<bppp::accumulation::Digest> validate_linear_public_inputs(
539 std::span<const CertificateNonceResponseVerificationView>
540 ordered_responses)
541{
542 if (ordered_responses.empty() ||
543 exceeds_response_limit(ordered_responses.size())) {
544 return unexpected_error(
546 "certificate_nonce_linear:public_responses");
547 }
548 const auto context_digest = ordered_responses.front()
549 .inputs()
550 .frame()
551 .certificate_context_digest;
552 if (is_zero(context_digest)) {
553 return unexpected_error(
555 "certificate_nonce_linear:context_digest");
556 }
557 for (std::size_t index = 0; index < ordered_responses.size(); ++index) {
558 const auto& view = ordered_responses[index];
559 const auto& frame = view.inputs().frame();
560 if (frame.certificate_context_digest != context_digest ||
561 frame.total_responses !=
562 static_cast<std::uint64_t>(ordered_responses.size()) ||
563 frame.response_ordinal !=
564 static_cast<std::uint64_t>(index)) {
565 return unexpected_error(
567 "certificate_nonce_linear:response_frame");
568 }
570 match_inputs_and_leaves(
571 view.inputs(), view.ordered_leaves()),
572 "certificate_nonce_linear:response_inputs");
573 }
574 return context_digest;
575}
576
577Result<ParentMetadata> parent_metadata(
578 std::span<const PendingCertificateNonceParent> children) {
579 if (children.empty() ||
580 children.size() >
582 return unexpected_error(
584 "certificate_nonce_tree:child_count");
585 }
586 const auto& first = children.front();
587 if (first.level() == std::numeric_limits<std::uint32_t>::max()) {
588 return unexpected_error(
589 ErrorCode::Overflow, "certificate_nonce_tree:level");
590 }
592 const auto child_span, level_span(first.level()),
593 "certificate_nonce_tree:child_span");
594 if (child_span > std::numeric_limits<std::uint64_t>::max() /
596 return unexpected_error(
597 ErrorCode::Overflow, "certificate_nonce_tree:parent_span");
598 }
599 const auto parent_span =
601 if (first.first_response() % parent_span != 0 ||
602 first.first_response() >= first.total_responses()) {
603 return unexpected_error(
605 "certificate_nonce_tree:parent_alignment");
606 }
607 const auto available =
608 first.total_responses() - first.first_response();
609 const auto parent_count = std::min(parent_span, available);
610 const auto expected_children =
611 (parent_count + child_span - 1) / child_span;
612 if (children.size() != expected_children) {
613 return unexpected_error(
615 "certificate_nonce_tree:framing");
616 }
617 if (children.size() == 1 && first.first_response() == 0 &&
618 first.response_count() == first.total_responses()) {
619 return unexpected_error(
621 "certificate_nonce_tree:redundant_root");
622 }
623
624 Bytes encoded;
625 encoded.push_back(kTreeNodeVersion);
626 append_u32(
627 encoded,
628 static_cast<std::uint32_t>(
630 append(encoded, first.certificate_context_digest());
631 append_u64(encoded, first.total_responses());
632 append_u32(encoded, first.level() + 1);
633 append_u64(encoded, first.first_response());
634 append_u64(encoded, parent_count);
635 append_u32(encoded, static_cast<std::uint32_t>(children.size()));
636 for (std::size_t index = 0; index < children.size(); ++index) {
637 const auto& child = children[index];
638 const auto expected_first =
639 first.first_response() + index * child_span;
640 const auto expected_count = std::min(
641 child_span, first.total_responses() - expected_first);
642 if (child.certificate_context_digest() !=
643 first.certificate_context_digest() ||
644 child.total_responses() != first.total_responses() ||
645 child.level() != first.level() ||
646 child.first_response() != expected_first ||
647 child.response_count() != expected_count) {
648 return unexpected_error(
650 "certificate_nonce_tree:child_order");
651 }
652 append(encoded, child.node_digest());
653 }
654 return ParentMetadata{
655 first.certificate_context_digest(),
656 kTreeNodeHash.digest(encoded), first.total_responses(),
657 first.level() + 1, first.first_response(), parent_count,
658 };
659}
660
661} // namespace
662
667 const accountable::ConflictContext& context,
668 std::span<const PublicKey> ordered_hosts,
669 std::span<const unsigned char> canonical_body,
670 const accountable::ScalarSignature& response,
671 purify_secp_context* secp_context)
672{
674 validate_authorization_inputs(
675 frame, roster, context, ordered_hosts, canonical_body,
676 secp_context),
677 "certificate_nonce_authorization:inputs");
678 Bytes prefix;
679 append_authorization_prefix(
680 prefix, frame, roster, context, canonical_body, response,
681 ordered_hosts.size());
682 const auto common_digest =
683 kResponseAuthorizationCommonHash.digest(prefix);
684
685 Bytes encoded = prefix;
686 for (std::size_t index = 0; index < ordered_hosts.size(); ++index) {
687 append_authorization_member(
688 encoded, index, roster.members()[index],
689 ordered_hosts[index]);
690 }
691 const auto response_digest =
692 kResponseAuthorizationHash.digest(encoded);
693
694 Bytes binding_bytes;
695 binding_bytes.reserve(common_digest.size() + response_digest.size());
696 append(binding_bytes, common_digest);
697 append(binding_bytes, response_digest);
698 const auto response_binding =
699 kResponseAuthorizationBindingHash.digest(binding_bytes);
700
701 std::vector<bppp::accumulation::Digest> member_digests;
702 member_digests.reserve(ordered_hosts.size());
703 for (std::size_t index = 0; index < ordered_hosts.size(); ++index) {
704 Bytes member_bytes;
705 append(member_bytes, response_binding);
706 append_u64(member_bytes, frame.response_ordinal);
707 append_authorization_member(
708 member_bytes, index, roster.members()[index],
709 ordered_hosts[index]);
710 member_digests.push_back(
711 kMemberAuthorizationHash.digest(member_bytes));
712 }
713 return CertificateNonceResponseAuthorization(
715 response_binding, std::move(member_digests));
716}
717
720 const CertificateNonceResponseAuthorization& authorization,
721 std::uint32_t member_ordinal, const PublicKey& host,
723 const accountable::ConflictContext& context,
724 purify_secp_context* secp_context)
725{
727 validate_recursive_member_frame(
728 authorization, member_ordinal),
729 "certificate_nonce_recursive:member_frame");
730 const auto purify_host = host.purify_pubkey.to_bytes_be();
732 const auto topic,
733 accountable::nonce_evaluation_input(context, secp_context),
734 "certificate_nonce_recursive:member_topic");
735 if (leaf.nonce_host() != purify_host ||
736 leaf.topic().size() != topic.size() ||
737 !std::equal(
738 leaf.topic().begin(), leaf.topic().end(), topic.begin())) {
739 return unexpected_error(
741 "certificate_nonce_recursive:member_binding");
742 }
743 return recursive_member_digest_from_derived_constants(
744 authorization, member_ordinal, host, topic,
745 leaf.parent_constants(), leaf.binding_digest());
746}
747
750 const CertificateNonceLeafAccumulator& leaf_accumulator,
751 const CertificateNonceResponseAuthorization& authorization,
752 std::uint32_t member_ordinal, const PublicKey& host,
753 const CertificateNoncePublicLeafDescriptor& descriptor,
754 const accountable::ConflictContext& context,
755 purify_secp_context* secp_context)
756{
758 validate_recursive_member_frame(
759 authorization, member_ordinal),
760 "certificate_nonce_recursive:public_member_frame");
762 const auto topic,
763 accountable::nonce_evaluation_input(context, secp_context),
764 "certificate_nonce_recursive:public_member_topic");
766 const auto cache, TopicProofCache::build(topic),
767 "certificate_nonce_recursive:public_member_cache");
768 return recursive_member_digest_from_public_descriptor(
769 leaf_accumulator, authorization, member_ordinal, host,
770 descriptor, topic, cache, secp_context);
771}
772
775 const CertificateNonceResponseAuthorization& authorization,
776 const accountable::ConflictContext& context,
777 std::span<const unsigned char> canonical_body,
778 const accountable::ScalarSignature& response,
779 const bppp::accumulation::Digest& member_digest,
780 purify_secp_context* secp_context)
781{
782 const auto& frame = authorization.frame();
783 const auto member_digests = authorization.member_digests();
784 if (frame.total_responses == 0 ||
785 frame.total_responses >
787 frame.response_ordinal >= frame.total_responses ||
788 member_digests.empty() ||
789 member_digests.size() >
791 return unexpected_error(
793 "certificate_nonce_recursive:step_frame");
794 }
796 const auto challenge,
798 context, canonical_body, secp_context),
799 "certificate_nonce_recursive:step_challenge");
800 const auto response_scalar = response.serialize();
801 const auto challenge_scalar = challenge.to_bytes_be();
802
803 Bytes encoded;
804 encoded.reserve(kRecursiveStepMessageSize);
805 append(encoded, member_digest);
806 append(encoded, authorization.response_binding());
807 append_u32(encoded, static_cast<std::uint32_t>(member_digests.size()));
808 append(encoded, context.signing_key);
809 append(encoded, response_scalar);
810 append(encoded, challenge_scalar);
811 assert(encoded.size() == kRecursiveStepMessageSize);
812 return kRecursiveStepHash.digest(encoded);
813}
814
817 const CertificateNonceLeafAccumulator& leaf_accumulator,
819 purify_secp_context* secp_context)
820{
822 validate_recursive_public_response(response),
823 "certificate_nonce_recursive:public_response");
824 return recursive_response_step_digests_from_validated(
825 leaf_accumulator, response, secp_context);
826}
827
830 const bppp::accumulation::Digest& certificate_context_digest,
831 std::uint64_t total_responses)
832{
833 if (is_zero(certificate_context_digest) || total_responses == 0 ||
834 total_responses >
836 return unexpected_error(
838 "certificate_nonce_recursive:manifest_seed");
839 }
840 Bytes encoded;
841 encoded.reserve(kRecursiveManifestSeedMessageSize);
842 append(encoded, certificate_context_digest);
843 append_u64(encoded, total_responses);
844 assert(encoded.size() == kRecursiveManifestSeedMessageSize);
845 auto manifest = kRecursiveManifestSeedHash.digest(encoded);
846 manifest[0] &= 0x7f;
847 return CertificateNonceRecursiveManifest(manifest);
848}
849
852 const CertificateNonceRecursiveManifest& prior,
853 std::uint64_t response_ordinal, std::uint32_t member_ordinal,
854 const bppp::accumulation::Digest& step_digest)
855{
856 if ((prior.bytes()[0] & 0x80) != 0 ||
857 member_ordinal >=
859 return unexpected_error(
861 "certificate_nonce_recursive:manifest_step");
862 }
863 Bytes encoded;
864 encoded.reserve(kRecursiveManifestStepMessageSize);
865 append(encoded, prior.bytes());
866 append_u64(encoded, response_ordinal);
867 append_u32(encoded, member_ordinal);
868 append(encoded, step_digest);
869 assert(encoded.size() == kRecursiveManifestStepMessageSize);
870 auto manifest = kRecursiveManifestStepHash.digest(encoded);
871 manifest[0] &= 0x7f;
872 return CertificateNonceRecursiveManifest(manifest);
873}
874
877 const CertificateNonceLeafAccumulator& leaf_accumulator,
879 std::span<const CertificateNonceRecursiveResponseView>
880 ordered_responses,
881 purify_secp_context* secp_context)
882{
883 if (ordered_responses.empty() ||
884 exceeds_response_limit(ordered_responses.size())) {
885 return unexpected_error(
887 "certificate_nonce_recursive:public_manifest_responses");
888 }
889 const auto total_responses =
890 static_cast<std::uint64_t>(ordered_responses.size());
891 std::size_t total_steps = 0;
892 for (std::size_t response_index = 0;
893 response_index < ordered_responses.size(); ++response_index) {
894 const auto& response = ordered_responses[response_index];
895 const auto& frame = response.authorization().frame();
896 if (frame.certificate_context_digest !=
898 frame.total_responses != total_responses ||
899 frame.response_ordinal !=
900 static_cast<std::uint64_t>(response_index)) {
901 return unexpected_error(
903 "certificate_nonce_recursive:public_manifest_frame");
904 }
906 validate_recursive_public_response(response),
907 "certificate_nonce_recursive:public_manifest_response");
908 const auto member_count = response.ordered_hosts().size();
909 if (!checked_add_size(
910 total_steps, member_count, total_steps)) {
911 return unexpected_error(
913 "certificate_nonce_recursive:public_manifest_steps");
914 }
915 }
917 auto manifest,
920 "certificate_nonce_recursive:public_manifest_seed");
921
922 std::vector<bppp::accumulation::Digest> step_digests;
923 step_digests.reserve(total_steps);
924 for (std::size_t response_index = 0;
925 response_index < ordered_responses.size(); ++response_index) {
926 const auto& response = ordered_responses[response_index];
927 const auto& frame = response.authorization().frame();
929 auto response_steps,
930 recursive_response_step_digests_from_validated(
931 leaf_accumulator, response, secp_context),
932 "certificate_nonce_recursive:public_manifest_response");
933 for (std::size_t member_index = 0;
934 member_index < response_steps.size(); ++member_index) {
936 manifest,
938 manifest, frame.response_ordinal,
939 static_cast<std::uint32_t>(member_index),
940 response_steps[member_index]),
941 "certificate_nonce_recursive:public_manifest_member");
942 step_digests.push_back(
943 std::move(response_steps[member_index]));
944 }
945 }
946 return CertificateNonceRecursiveManifestResolution(
948 std::move(step_digests), std::move(manifest));
949}
950
953 const bppp::accumulation::Digest& certificate_context_digest,
954 std::uint64_t total_responses)
955{
956 if (is_zero(certificate_context_digest) || total_responses == 0 ||
957 total_responses >
959 return unexpected_error(
961 "certificate_nonce_authorization:manifest_seed");
962 }
963 Bytes encoded;
964 append(encoded, certificate_context_digest);
965 append_u64(encoded, total_responses);
966 auto manifest = kAuthorizationManifestSeedHash.digest(encoded);
967 manifest[0] &= 0x7f;
968 return manifest;
969}
970
974 std::uint64_t response_ordinal, std::uint32_t member_ordinal,
975 const bppp::accumulation::Digest& member_digest)
976{
977 if ((prior[0] & 0x80) != 0 ||
978 member_ordinal >=
980 return unexpected_error(
982 "certificate_nonce_authorization:manifest_step");
983 }
984 Bytes encoded;
985 append(encoded, prior);
986 append_u64(encoded, response_ordinal);
987 append_u32(encoded, member_ordinal);
988 append(encoded, member_digest);
989 auto manifest = kAuthorizationManifestStepHash.digest(encoded);
990 manifest[0] &= 0x7f;
991 return manifest;
992}
993
996 const bppp::accumulation::Digest& certificate_context_digest,
997 std::uint64_t total_responses,
998 std::span<const CertificateNonceResponseAuthorization> responses)
999{
1000 if (!size_fits_u64(responses.size()) ||
1001 responses.size() != total_responses) {
1002 return unexpected_error(
1004 "certificate_nonce_authorization:manifest_responses");
1005 }
1007 auto manifest,
1009 certificate_context_digest, total_responses),
1010 "certificate_nonce_authorization:manifest_seed");
1011 for (std::size_t response_index = 0;
1012 response_index < responses.size(); ++response_index) {
1013 const auto& authorization = responses[response_index];
1014 const auto& frame = authorization.frame();
1015 if (frame.certificate_context_digest !=
1016 certificate_context_digest ||
1017 frame.total_responses != total_responses ||
1018 frame.response_ordinal != response_index) {
1019 return unexpected_error(
1021 "certificate_nonce_authorization:manifest_frame");
1022 }
1023 const auto member_digests = authorization.member_digests();
1024 for (std::size_t member_index = 0;
1025 member_index < member_digests.size(); ++member_index) {
1027 manifest,
1029 manifest, frame.response_ordinal,
1030 static_cast<std::uint32_t>(member_index),
1031 member_digests[member_index]),
1032 "certificate_nonce_authorization:manifest_member");
1033 }
1034 }
1035 return manifest;
1036}
1037
1042{
1043 if (is_zero(statement_digest) || proof.reductions.empty() ||
1044 proof.reductions.size() >
1046 kMemberBatchCapacity) {
1047 return unexpected_error(
1049 "certificate_nonce_native:response_shape");
1050 }
1051 return CertificateNonceNativeResponse(
1052 statement_digest, std::move(proof));
1053}
1054
1058 std::vector<CertificateNonceNativeResponse> responses,
1059 std::vector<CertificateNonceTreeProof> tree_proofs)
1060{
1062 validate_native_receipt_shape(
1064 "certificate_nonce_native:shape");
1065 return CertificateNonceNativeReceipt(
1067 std::move(tree_proofs));
1068}
1069
1073 std::vector<CertificateNonceLinearResponseProof> responses)
1074{
1076 validate_linear_receipt_shape(
1078 "certificate_nonce_linear:shape");
1079 return CertificateNonceLinearReceipt(
1081}
1082
1084 std::span<const std::size_t> member_counts)
1085{
1087 const auto tree_proofs,
1088 native_tree_proof_count(member_counts.size()),
1089 "certificate_nonce_native:size_tree");
1090
1091 std::size_t encoded_size =
1093 for (const auto member_count : member_counts) {
1094 if (member_count == 0 ||
1095 member_count >
1097 kMemberBatchCapacity) {
1098 return unexpected_error(
1100 "certificate_nonce_native:size_members");
1101 }
1102 std::size_t reduction_size = 0;
1103 std::size_t response_size = 0;
1104 if (!checked_mul_size(
1105 member_count,
1107 kReductionSerializedSize,
1108 reduction_size) ||
1111 kResponseHeaderSerializedSize,
1112 reduction_size, response_size) ||
1114 response_size,
1116 response_size) ||
1118 encoded_size, response_size, encoded_size)) {
1119 return unexpected_error(
1121 "certificate_nonce_native:size_responses");
1122 }
1123 }
1124 std::size_t tree_size = 0;
1125 if (!checked_mul_size(
1126 tree_proofs,
1128 tree_size) ||
1129 !checked_add_size(encoded_size, tree_size, encoded_size)) {
1130 return unexpected_error(
1132 "certificate_nonce_native:size_tree_proofs");
1133 }
1134 return encoded_size;
1135}
1136
1138 const CertificateNonceParentAccumulator& accumulator,
1139 const CertificateNonceNativeReceipt& receipt,
1140 purify_secp_context* secp_context)
1141{
1144 secp_context, "certificate_nonce_native:context"),
1145 "certificate_nonce_native:context");
1147 validate_native_receipt_shape(
1148 receipt.certificate_context_digest(), receipt.responses(),
1149 receipt.tree_proofs()),
1150 "certificate_nonce_native:shape");
1151
1152 std::vector<std::size_t> member_counts;
1153 member_counts.reserve(receipt.responses().size());
1154 for (const auto& response : receipt.responses()) {
1155 member_counts.push_back(response.proof().reductions.size());
1156 }
1158 const auto expected_size,
1160 "certificate_nonce_native:size");
1161
1162 Bytes encoded;
1163 encoded.reserve(expected_size);
1164 append(encoded, kNativeReceiptMagic);
1165 append(encoded, accumulator.leaves().basis().digest());
1166 append(encoded, receipt.certificate_context_digest());
1167 append_u64(
1168 encoded,
1169 static_cast<std::uint64_t>(receipt.responses().size()));
1170
1171 const auto& basis = accumulator.leaves().basis();
1172 for (const auto& response : receipt.responses()) {
1173 append(encoded, response.statement_digest());
1174 encoded.push_back(static_cast<unsigned char>(
1175 response.proof().reductions.size()));
1176 for (const auto& reduction : response.proof().reductions) {
1178 auto proof,
1180 serialize_algebraic_norm_reduction(
1181 basis, reduction, secp_context),
1182 "certificate_nonce_native:serialize_reduction");
1183 if (proof.size() !=
1185 kReductionSerializedSize) {
1186 return unexpected_error(
1188 "certificate_nonce_native:reduction_size");
1189 }
1190 append(encoded, proof);
1191 }
1193 auto step,
1195 basis, response.proof().accumulation,
1196 secp_context),
1197 "certificate_nonce_native:serialize_response_step");
1198 if (step.size() !=
1200 return unexpected_error(
1202 "certificate_nonce_native:response_step_size");
1203 }
1204 append(encoded, step);
1205 }
1206 for (const auto& tree_proof : receipt.tree_proofs()) {
1208 auto step,
1210 basis, tree_proof.accumulation, secp_context),
1211 "certificate_nonce_native:serialize_tree_step");
1212 if (step.size() !=
1214 return unexpected_error(
1216 "certificate_nonce_native:tree_step_size");
1217 }
1218 append(encoded, step);
1219 }
1220 if (encoded.size() != expected_size) {
1221 return unexpected_error(
1223 "certificate_nonce_native:final_size");
1224 }
1225 return encoded;
1226}
1227
1230 const CertificateNonceParentAccumulator& accumulator,
1231 std::span<const unsigned char> encoded,
1232 purify_secp_context* secp_context)
1233{
1236 secp_context, "certificate_nonce_native:context"),
1237 "certificate_nonce_native:context");
1238 if (encoded.size() <
1240 return unexpected_error(
1242 "certificate_nonce_native:header");
1243 }
1244 if (!std::equal(
1245 kNativeReceiptMagic.begin(), kNativeReceiptMagic.end(),
1246 encoded.begin())) {
1247 return unexpected_error(
1249 "certificate_nonce_native:magic");
1250 }
1251
1252 std::size_t offset = kNativeReceiptMagic.size();
1253 bppp::accumulation::Digest basis_digest{};
1254 std::copy_n(
1255 encoded.begin() + offset, basis_digest.size(),
1256 basis_digest.begin());
1257 offset += basis_digest.size();
1258 if (basis_digest != accumulator.leaves().basis().digest()) {
1259 return unexpected_error(
1261 "certificate_nonce_native:basis_digest");
1262 }
1263 bppp::accumulation::Digest context_digest{};
1264 std::copy_n(
1265 encoded.begin() + offset, context_digest.size(),
1266 context_digest.begin());
1267 offset += context_digest.size();
1268 if (is_zero(context_digest)) {
1269 return unexpected_error(
1271 "certificate_nonce_native:context_digest");
1272 }
1273 const auto response_count_u64 = read_u64(
1274 encoded.subspan(offset, sizeof(std::uint64_t)));
1275 offset += sizeof(std::uint64_t);
1276 if (response_count_u64 == 0 ||
1277 response_count_u64 >
1279 response_count_u64 >
1280 std::numeric_limits<std::size_t>::max()) {
1281 return unexpected_error(
1283 "certificate_nonce_native:response_count");
1284 }
1285 const auto response_count =
1286 static_cast<std::size_t>(response_count_u64);
1287 constexpr std::size_t kMinimumResponseSize =
1288 CertificateNonceNativeReceipt::
1289 kResponseHeaderSerializedSize +
1292 if (response_count >
1293 (encoded.size() - offset) / kMinimumResponseSize) {
1294 return unexpected_error(
1296 "certificate_nonce_native:response_bytes");
1297 }
1298
1299 const auto& basis = accumulator.leaves().basis();
1300 std::vector<CertificateNonceNativeResponse> responses;
1301 responses.reserve(response_count);
1302 std::vector<std::size_t> member_counts;
1303 member_counts.reserve(response_count);
1304 for (std::size_t response_index = 0;
1305 response_index < response_count; ++response_index) {
1306 if (encoded.size() - offset <
1308 kResponseHeaderSerializedSize) {
1309 return unexpected_error(
1311 "certificate_nonce_native:response_header");
1312 }
1313 bppp::accumulation::Digest statement_digest{};
1314 std::copy_n(
1315 encoded.begin() + offset, statement_digest.size(),
1316 statement_digest.begin());
1317 offset += statement_digest.size();
1318 const auto member_count = encoded[offset++];
1319 if (member_count == 0 ||
1320 member_count >
1322 kMemberBatchCapacity) {
1323 return unexpected_error(
1325 "certificate_nonce_native:member_count");
1326 }
1328 response.reductions.reserve(member_count);
1329 for (std::size_t member_index = 0;
1330 member_index < member_count; ++member_index) {
1331 constexpr auto kSize = CertificateNonceNativeReceipt::
1332 kReductionSerializedSize;
1333 if (encoded.size() - offset < kSize) {
1334 return unexpected_error(
1336 "certificate_nonce_native:reduction_bytes");
1337 }
1339 auto reduction,
1341 parse_algebraic_norm_reduction(
1342 basis, encoded.subspan(offset, kSize),
1343 secp_context),
1344 "certificate_nonce_native:parse_reduction");
1345 offset += kSize;
1346 response.reductions.push_back(std::move(reduction));
1347 }
1348 constexpr auto kStepSize =
1350 if (encoded.size() - offset < kStepSize) {
1351 return unexpected_error(
1353 "certificate_nonce_native:response_step_bytes");
1354 }
1356 response.accumulation,
1358 basis, encoded.subspan(offset, kStepSize),
1359 secp_context),
1360 "certificate_nonce_native:parse_response_step");
1361 offset += kStepSize;
1362 member_counts.push_back(member_count);
1364 auto native_response,
1366 statement_digest, std::move(response)),
1367 "certificate_nonce_native:response");
1368 responses.push_back(std::move(native_response));
1369 }
1370
1372 const auto tree_proof_count,
1373 native_tree_proof_count(response_count),
1374 "certificate_nonce_native:tree_count");
1375 std::size_t tree_bytes = 0;
1376 if (!checked_mul_size(
1377 tree_proof_count,
1379 tree_bytes) ||
1380 encoded.size() - offset != tree_bytes) {
1381 return unexpected_error(
1383 "certificate_nonce_native:tree_bytes");
1384 }
1385 std::vector<CertificateNonceTreeProof> tree_proofs;
1386 tree_proofs.reserve(tree_proof_count);
1387 for (std::size_t index = 0; index < tree_proof_count; ++index) {
1388 constexpr auto kStepSize =
1391 auto step,
1393 basis, encoded.subspan(offset, kStepSize),
1394 secp_context),
1395 "certificate_nonce_native:parse_tree_step");
1396 offset += kStepSize;
1397 tree_proofs.push_back(
1398 CertificateNonceTreeProof{std::move(step)});
1399 }
1400 assert(offset == encoded.size());
1402 const auto expected_size,
1404 "certificate_nonce_native:parsed_size");
1405 if (expected_size != encoded.size()) {
1406 return unexpected_error(
1408 "certificate_nonce_native:parsed_size");
1409 }
1411 context_digest, std::move(responses),
1412 std::move(tree_proofs));
1413}
1414
1419 const accountable::ConflictContext& context,
1420 std::span<const PublicKey> ordered_hosts,
1421 std::span<const unsigned char> canonical_body,
1422 const accountable::ScalarSignature& response,
1423 std::span<const PreparedCertificateNonceLeaf> ordered_leaves,
1424 purify_secp_context* secp_context) {
1426 auto authorization,
1428 frame, roster, context, ordered_hosts, canonical_body,
1429 response, secp_context),
1430 "certificate_nonce_parent:authorization");
1431 if (ordered_hosts.size() != ordered_leaves.size()) {
1432 return unexpected_error(
1434 "certificate_nonce_parent:member_count");
1435 }
1437 const auto nonce_input,
1438 accountable::nonce_evaluation_input(context, secp_context),
1439 "certificate_nonce_parent:topic");
1440
1441 std::set<bppp::accumulation::Digest> unique_leaves;
1442 std::vector<bppp::accumulation::Digest> leaf_bindings;
1443 std::vector<bppp::PointBytes> member_nonces;
1444 leaf_bindings.reserve(ordered_leaves.size());
1445 member_nonces.reserve(ordered_leaves.size());
1446 for (std::size_t index = 0; index < ordered_leaves.size(); ++index) {
1447 const auto& leaf = ordered_leaves[index];
1448 const auto host = ordered_hosts[index].purify_pubkey.to_bytes_be();
1449 if (leaf.nonce_host() != host ||
1450 leaf.topic().size() != nonce_input.size() ||
1451 !std::equal(leaf.topic().begin(), leaf.topic().end(),
1452 nonce_input.begin()) ||
1453 !unique_leaves.insert(leaf.binding_digest()).second) {
1454 return unexpected_error(
1456 "certificate_nonce_parent:leaf_binding");
1457 }
1458 leaf_bindings.push_back(leaf.binding_digest());
1459 member_nonces.push_back(leaf.nonce_point());
1460 }
1462 const auto aggregate_nonce,
1463 sum_nonces(ordered_leaves, secp_context),
1464 "certificate_nonce_parent:aggregate_nonce");
1466 const auto reconstructed,
1468 context, canonical_body, response, secp_context),
1469 "certificate_nonce_parent:response");
1470 if (aggregate_nonce != reconstructed) {
1471 return unexpected_error(
1473 "certificate_nonce_parent:response_nonce");
1474 }
1475
1476 std::vector<bppp::accumulation::Digest> recursive_step_digests;
1477 recursive_step_digests.reserve(ordered_leaves.size());
1478 for (std::size_t index = 0; index < ordered_leaves.size(); ++index) {
1480 const auto member_digest,
1482 authorization, static_cast<std::uint32_t>(index),
1483 ordered_hosts[index], ordered_leaves[index], context,
1484 secp_context),
1485 "certificate_nonce_parent:recursive_member");
1487 auto step_digest,
1489 authorization, context, canonical_body, response,
1490 member_digest, secp_context),
1491 "certificate_nonce_parent:recursive_step");
1492 recursive_step_digests.push_back(std::move(step_digest));
1493 }
1494
1495 Bytes encoded;
1496 append_authorization_prefix(
1497 encoded, frame, roster, context, canonical_body, response,
1498 ordered_leaves.size());
1499 for (std::size_t index = 0; index < ordered_leaves.size(); ++index) {
1500 const auto& member = roster.members()[index];
1501 append_authorization_member(
1502 encoded, index, member, ordered_hosts[index]);
1503 append(encoded, ordered_leaves[index].binding_digest());
1504 append(encoded, ordered_leaves[index].proof_digest());
1505 append(encoded,
1506 ordered_leaves[index].circuit_precommitment());
1507 append(encoded, ordered_leaves[index].nonce_point());
1508 }
1509 append(encoded, aggregate_nonce);
1510 const auto statement_digest = kResponseStatementHash.digest(encoded);
1511 return CertificateNonceParentPublicInputs(
1512 std::move(frame), std::move(encoded), statement_digest,
1513 std::move(authorization),
1514 aggregate_nonce, std::move(leaf_bindings),
1515 std::move(member_nonces),
1516 std::move(recursive_step_digests));
1517}
1518
1521 purify_secp_context* secp_context) {
1524 "certificate_nonce_parent:leaf_accumulator");
1525 return CertificateNonceParentAccumulator(std::move(leaves));
1526}
1527
1531 std::span<const PreparedCertificateNonceLeaf> ordered_leaves,
1532 purify_secp_context* secp_context) const {
1534 match_inputs_and_leaves(inputs, ordered_leaves),
1535 "certificate_nonce_parent:inputs");
1537 proof.reductions.reserve(ordered_leaves.size());
1538 std::vector<bppp::accumulation::PendingClaim> claims;
1539 claims.reserve(ordered_leaves.size());
1540 for (const auto& leaf : ordered_leaves) {
1542 auto reduction,
1544 leaves_.basis(), leaf.norm(), secp_context),
1545 "certificate_nonce_parent:prove_reduction");
1547 auto claim,
1549 leaves_.basis(), leaf.norm(), reduction, secp_context),
1550 "certificate_nonce_parent:verify_reduction");
1551 proof.reductions.push_back(std::move(reduction));
1552 claims.push_back(std::move(claim));
1553 }
1555 proof.accumulation,
1557 leaves_.basis(), claims, inputs.statement_digest(),
1558 secp_context),
1559 "certificate_nonce_parent:prove_step");
1560 return proof;
1561}
1562
1566 std::span<const PreparedCertificateNonceLeaf> ordered_leaves,
1567 const CertificateNonceResponseProof& proof,
1568 purify_secp_context* secp_context) const {
1570 match_inputs_and_leaves(inputs, ordered_leaves),
1571 "certificate_nonce_parent:inputs");
1572 if (proof.reductions.size() != ordered_leaves.size()) {
1573 return unexpected_error(
1575 "certificate_nonce_parent:reduction_count");
1576 }
1577 std::vector<bppp::accumulation::PendingClaim> claims;
1578 claims.reserve(ordered_leaves.size());
1579 for (std::size_t index = 0; index < ordered_leaves.size(); ++index) {
1581 auto claim,
1583 leaves_.basis(), ordered_leaves[index].norm(),
1584 proof.reductions[index], secp_context),
1585 "certificate_nonce_parent:verify_reduction");
1586 claims.push_back(std::move(claim));
1587 }
1589 auto pending,
1591 leaves_.basis(), claims, inputs.statement_digest(),
1592 proof.accumulation, secp_context),
1593 "certificate_nonce_parent:verify_step");
1594 const auto& frame = inputs.frame();
1596 frame.certificate_context_digest, inputs.statement_digest(),
1597 frame.total_responses, 0, frame.response_ordinal, 1,
1598 inputs.aggregate_nonce(), std::move(pending));
1599}
1600
1603 std::span<const PendingCertificateNonceParent> ordered_children,
1604 purify_secp_context* secp_context) const {
1606 const auto metadata, parent_metadata(ordered_children),
1607 "certificate_nonce_tree:metadata");
1608 std::vector<bppp::accumulation::PendingClaim> claims;
1609 claims.reserve(ordered_children.size());
1610 for (const auto& child : ordered_children) {
1611 claims.push_back(child.claim_);
1612 }
1614 auto accumulation,
1616 leaves_.basis(), claims, metadata.node_digest,
1617 secp_context),
1618 "certificate_nonce_tree:prove_step");
1619 return CertificateNonceTreeProof{std::move(accumulation)};
1620}
1621
1624 std::span<const PendingCertificateNonceParent> ordered_children,
1625 const CertificateNonceTreeProof& proof,
1626 purify_secp_context* secp_context) const {
1628 const auto metadata, parent_metadata(ordered_children),
1629 "certificate_nonce_tree:metadata");
1630 std::vector<bppp::accumulation::PendingClaim> claims;
1631 claims.reserve(ordered_children.size());
1632 for (const auto& child : ordered_children) {
1633 claims.push_back(child.claim_);
1634 }
1636 auto pending,
1638 leaves_.basis(), claims, metadata.node_digest,
1639 proof.accumulation, secp_context),
1640 "certificate_nonce_tree:verify_step");
1642 metadata.certificate_context_digest, metadata.node_digest,
1643 metadata.total_responses, metadata.level,
1644 metadata.first_response, metadata.response_count,
1645 std::nullopt, std::move(pending));
1646}
1647
1650 purify_secp_context* secp_context) const {
1651 if (root.first_response() != 0 || root.total_responses() == 0 ||
1652 root.response_count() != root.total_responses()) {
1653 return unexpected_error(
1655 "certificate_nonce_tree:incomplete_root");
1656 }
1658 leaves_.basis(), root.claim_, secp_context);
1659}
1660
1662 const CertificateNonceNativeReceipt& receipt,
1663 std::span<const CertificateNonceResponseVerificationView>
1664 ordered_responses,
1665 purify_secp_context* secp_context) const
1666{
1668 validate_native_receipt_shape(
1669 receipt.certificate_context_digest(), receipt.responses(),
1670 receipt.tree_proofs()),
1671 "certificate_nonce_native:shape");
1672 if (ordered_responses.size() != receipt.responses().size()) {
1673 return unexpected_error(
1675 "certificate_nonce_native:public_responses");
1676 }
1677
1678 std::vector<PendingCertificateNonceParent> current;
1679 current.reserve(ordered_responses.size());
1680 for (std::size_t index = 0; index < ordered_responses.size();
1681 ++index) {
1682 const auto& view = ordered_responses[index];
1683 const auto& inputs = view.inputs();
1684 const auto& frame = inputs.frame();
1685 if (inputs.statement_digest() !=
1686 receipt.responses()[index].statement_digest() ||
1687 frame.certificate_context_digest !=
1688 receipt.certificate_context_digest() ||
1689 frame.total_responses != ordered_responses.size() ||
1690 frame.response_ordinal != index) {
1691 return unexpected_error(
1693 "certificate_nonce_native:response_frame");
1694 }
1696 auto pending,
1698 inputs, view.ordered_leaves(),
1699 receipt.responses()[index].proof(), secp_context),
1700 "certificate_nonce_native:verify_response");
1701 current.push_back(std::move(pending));
1702 }
1703
1704 std::size_t tree_proof_index = 0;
1705 while (current.size() > 1) {
1706 std::vector<PendingCertificateNonceParent> parents;
1707 parents.reserve(
1708 1 + (current.size() - 1) / kTreeFanout);
1709 for (std::size_t offset = 0; offset < current.size();
1710 offset += kTreeFanout) {
1711 if (tree_proof_index >= receipt.tree_proofs().size()) {
1712 return unexpected_error(
1714 "certificate_nonce_native:missing_tree_proof");
1715 }
1716 const auto child_count =
1717 std::min(kTreeFanout, current.size() - offset);
1719 auto parent,
1721 std::span<const PendingCertificateNonceParent>{
1722 current}
1723 .subspan(offset, child_count),
1724 receipt.tree_proofs()[tree_proof_index],
1725 secp_context),
1726 "certificate_nonce_native:verify_tree_proof");
1727 ++tree_proof_index;
1728 parents.push_back(std::move(parent));
1729 }
1730 current = std::move(parents);
1731 }
1732 if (current.size() != 1 ||
1733 tree_proof_index != receipt.tree_proofs().size()) {
1734 return unexpected_error(
1736 "certificate_nonce_native:tree_shape");
1737 }
1738 return decide_root(current.front(), secp_context);
1739}
1740
1743 std::span<const CertificateNonceResponseVerificationView>
1744 ordered_responses,
1745 purify_secp_context* secp_context) const
1746{
1749 secp_context, "certificate_nonce_linear:context"),
1750 "certificate_nonce_linear:context");
1752 const auto context_digest,
1753 validate_linear_public_inputs(ordered_responses),
1754 "certificate_nonce_linear:public_inputs");
1756 auto root,
1758 "certificate_nonce_linear:zero_claim");
1759
1760 std::vector<CertificateNonceLinearResponseProof> responses;
1761 responses.reserve(ordered_responses.size());
1762 for (const auto& view : ordered_responses) {
1764 response.members.reserve(view.ordered_leaves().size());
1765 for (std::size_t member_index = 0;
1766 member_index < view.ordered_leaves().size();
1767 ++member_index) {
1768 const auto& leaf = view.ordered_leaves()[member_index];
1770 auto reduction,
1772 leaves_.basis(), leaf.norm(), secp_context),
1773 "certificate_nonce_linear:prove_reduction");
1775 auto leaf_claim,
1777 leaves_.basis(), leaf.norm(), reduction,
1778 secp_context),
1779 "certificate_nonce_linear:verify_reduction");
1780 const std::array claims{root, std::move(leaf_claim)};
1781 const auto& step_digest =
1782 view.inputs().recursive_step_digests()[member_index];
1784 auto accumulation,
1786 leaves_.basis(), claims, step_digest,
1787 secp_context),
1788 "certificate_nonce_linear:prove_step");
1790 auto next_root,
1792 leaves_.basis(), claims, step_digest,
1793 accumulation, secp_context),
1794 "certificate_nonce_linear:verify_step");
1795 root = std::move(next_root);
1796 response.members.push_back({std::move(reduction), std::move(accumulation)});
1797 }
1798 responses.push_back(std::move(response));
1799 }
1802 leaves_.basis(), root, secp_context),
1803 "certificate_nonce_linear:decide");
1805 context_digest, std::move(responses));
1806}
1807
1809 const CertificateNonceLinearReceipt& receipt,
1810 std::span<const CertificateNonceResponseVerificationView>
1811 ordered_responses,
1812 purify_secp_context* secp_context) const
1813{
1816 secp_context, "certificate_nonce_linear:context"),
1817 "certificate_nonce_linear:context");
1819 validate_linear_receipt_shape(
1821 receipt.responses()),
1822 "certificate_nonce_linear:shape");
1824 const auto context_digest,
1825 validate_linear_public_inputs(ordered_responses),
1826 "certificate_nonce_linear:public_inputs");
1827 if (context_digest != receipt.certificate_context_digest() ||
1828 receipt.responses().size() != ordered_responses.size()) {
1829 return unexpected_error(
1831 "certificate_nonce_linear:receipt_frame");
1832 }
1834 auto root,
1836 "certificate_nonce_linear:zero_claim");
1837 for (std::size_t response_index = 0;
1838 response_index < ordered_responses.size();
1839 ++response_index) {
1840 const auto& view = ordered_responses[response_index];
1841 const auto& proof = receipt.responses()[response_index];
1842 if (proof.members.size() != view.ordered_leaves().size()) {
1843 return unexpected_error(
1845 "certificate_nonce_linear:member_count");
1846 }
1847 for (std::size_t member_index = 0;
1848 member_index < view.ordered_leaves().size();
1849 ++member_index) {
1850 const auto& leaf = view.ordered_leaves()[member_index];
1851 const auto& member_proof = proof.members[member_index];
1853 auto leaf_claim,
1855 leaves_.basis(), leaf.norm(),
1856 member_proof.reduction, secp_context),
1857 "certificate_nonce_linear:verify_reduction");
1858 const std::array claims{root, std::move(leaf_claim)};
1860 auto next_root,
1862 leaves_.basis(), claims,
1863 view.inputs().recursive_step_digests()[member_index],
1864 member_proof.accumulation, secp_context),
1865 "certificate_nonce_linear:verify_step");
1866 root = std::move(next_root);
1867 }
1868 }
1870 leaves_.basis(), root, secp_context);
1871}
1872
1873} // namespace purify::puresign_plusplus
int purify_point_add(purify_secp_context *context, const unsigned char lhs33[33], const unsigned char rhs33[33], unsigned char out33[33])
C ABI bridging Purify C++ code to secp256k1-zkp BPPP functionality.
An ordered signing roster bound to one core and nonce-host list.
std::span< const SigningRosterMember > members() const
Canonical 32-byte scalar response; carries no nonce or proof.
std::array< unsigned char, 32 > serialize() const
Return the complete scalar-only wire representation.
const Digest & digest() const
static Result< CertificateNonceLeafAccumulator > create(purify_secp_context *secp_context)
Definition bppp.cpp:1115
static Result< CertificateNonceLinearReceipt > create(bppp::accumulation::Digest certificate_context_digest, std::vector< CertificateNonceLinearResponseProof > responses)
std::span< const CertificateNonceLinearResponseProof > responses() const noexcept
const bppp::accumulation::Digest & certificate_context_digest() const noexcept
std::span< const CertificateNonceTreeProof > tree_proofs() const noexcept
const bppp::accumulation::Digest & certificate_context_digest() const noexcept
std::span< const CertificateNonceNativeResponse > responses() const noexcept
static Result< CertificateNonceNativeReceipt > create(bppp::accumulation::Digest certificate_context_digest, std::vector< CertificateNonceNativeResponse > responses, std::vector< CertificateNonceTreeProof > tree_proofs)
static Result< CertificateNonceNativeResponse > create(bppp::accumulation::Digest statement_digest, CertificateNonceResponseProof proof)
Status verify_native_receipt(const CertificateNonceNativeReceipt &receipt, std::span< const CertificateNonceResponseVerificationView > ordered_responses, purify_secp_context *secp_context) const
Result< CertificateNonceTreeProof > prove_parent(std::span< const PendingCertificateNonceParent > ordered_children, purify_secp_context *secp_context) const
static Result< CertificateNonceParentAccumulator > create(purify_secp_context *secp_context)
Status verify_linear_receipt(const CertificateNonceLinearReceipt &receipt, std::span< const CertificateNonceResponseVerificationView > ordered_responses, purify_secp_context *secp_context) const
CertificateNonceParentAccumulator(const CertificateNonceParentAccumulator &)=delete
Result< CertificateNonceResponseProof > prove_response(const CertificateNonceParentPublicInputs &inputs, std::span< const PreparedCertificateNonceLeaf > ordered_leaves, purify_secp_context *secp_context) const
Result< PendingCertificateNonceParent > verify_response(const CertificateNonceParentPublicInputs &inputs, std::span< const PreparedCertificateNonceLeaf > ordered_leaves, const CertificateNonceResponseProof &proof, purify_secp_context *secp_context) const
Result< PendingCertificateNonceParent > verify_parent(std::span< const PendingCertificateNonceParent > ordered_children, const CertificateNonceTreeProof &proof, purify_secp_context *secp_context) const
Status decide_root(const PendingCertificateNonceParent &root, purify_secp_context *secp_context) const
Result< CertificateNonceLinearReceipt > prove_linear_receipt(std::span< const CertificateNonceResponseVerificationView > ordered_responses, purify_secp_context *secp_context) const
std::span< const bppp::accumulation::Digest > recursive_step_digests() const noexcept
static Result< CertificateNonceParentPublicInputs > create(CertificateNonceResponseFrame frame, const accountable::NonceHostBoundSigningRoster &roster, const accountable::ConflictContext &context, std::span< const PublicKey > ordered_hosts, std::span< const unsigned char > canonical_body, const accountable::ScalarSignature &response, std::span< const PreparedCertificateNonceLeaf > ordered_leaves, purify_secp_context *secp_context)
std::span< const bppp::accumulation::Digest > leaf_bindings() const noexcept
const CertificateNonceResponseAuthorization & authorization() const noexcept
std::span< const bppp::accumulation::Digest > step_digests() const noexcept
std::span< const bppp::accumulation::Digest > member_digests() const noexcept
static Result< CertificateNonceResponseAuthorization > create(CertificateNonceResponseFrame frame, const accountable::NonceHostBoundSigningRoster &roster, const accountable::ConflictContext &context, std::span< const PublicKey > ordered_hosts, std::span< const unsigned char > canonical_body, const accountable::ScalarSignature &response, purify_secp_context *secp_context)
const bppp::accumulation::Digest & binding_digest() const noexcept
const CertificateNonceLeafParentConstants & parent_constants() const noexcept
const std::array< unsigned char, 64 > & nonce_host() const noexcept
#define PURIFY_RETURN_IF_ERROR(expr, context)
Evaluates an expected-like expression and returns the wrapped error on failure.
Definition error.hpp:329
#define PURIFY_ASSIGN_OR_RETURN(lhs, expr, context)
Evaluates an expected-like expression, binds the value to lhs, and propagates errors.
Definition error.hpp:338
Result< std::array< unsigned char, 33 > > reconstruct_nonce(const ConflictContext &context, std::span< const unsigned char > canonical_body, const ScalarSignature &signature, purify_secp_context *secp_context)
Reconstruct the full nonce point as sigma*G - e*Q, rejecting infinity.
Result< NonceHostCommitment > nonce_host_commitment(const SigningRoster &roster, std::span< const puresign_plusplus::PublicKey > ordered_hosts, purify_secp_context *secp_context)
Result< std::array< unsigned char, 32 > > nonce_evaluation_input(const ConflictContext &context, purify_secp_context *secp_context)
Derive the candidate deterministic Purify input from the registered slot.
Result< FieldElement > signature_challenge(const ConflictContext &context, std::span< const unsigned char > canonical_body, purify_secp_context *secp_context)
Compute the versioned Q/U/core/T/body challenge, without a nonce point.
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_bound_algebraic_step(const Basis &basis, std::span< const PendingClaim > claims, const Digest &statement_digest, const AlgebraicStepProof &proof, purify_secp_context *context)
Result< PendingClaim > verify_algebraic_norm_reduction(const Basis &basis, const AlgebraicPreparedNorm &norm, const AlgebraicNormReductionProof &proof, purify_secp_context *context)
Result< PendingClaim > canonical_zero_claim(const Basis &basis)
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< Bytes > serialize_algebraic_step(const Basis &basis, const AlgebraicStepProof &proof, purify_secp_context *context)
std::array< unsigned char, 33 > PointBytes
Compressed 33-byte curve-point encoding.
Definition bppp.hpp:32
Result< std::size_t > certificate_nonce_native_receipt_size(std::span< const std::size_t > member_counts)
Result< bppp::accumulation::Digest > certificate_nonce_recursive_step_digest(const CertificateNonceResponseAuthorization &authorization, const accountable::ConflictContext &context, std::span< const unsigned char > canonical_body, const accountable::ScalarSignature &response, const bppp::accumulation::Digest &member_digest, purify_secp_context *secp_context)
Result< std::vector< bppp::accumulation::Digest > > certificate_nonce_recursive_response_step_digests(const CertificateNonceLeafAccumulator &leaf_accumulator, const CertificateNonceRecursiveResponseView &response, purify_secp_context *secp_context)
Result< CertificateNonceRecursiveManifest > certificate_nonce_recursive_manifest_seed(const bppp::accumulation::Digest &certificate_context_digest, std::uint64_t total_responses)
Result< CertificateNonceAuthorizationManifest > certificate_nonce_authorization_manifest_seed(const bppp::accumulation::Digest &certificate_context_digest, std::uint64_t total_responses)
Result< CertificateNonceAuthorizationManifest > certificate_nonce_authorization_manifest_step(const CertificateNonceAuthorizationManifest &prior, std::uint64_t response_ordinal, std::uint32_t member_ordinal, const bppp::accumulation::Digest &member_digest)
Result< CertificateNonceRecursiveManifest > certificate_nonce_recursive_manifest_step(const CertificateNonceRecursiveManifest &prior, std::uint64_t response_ordinal, std::uint32_t member_ordinal, const bppp::accumulation::Digest &step_digest)
Result< Bytes > serialize_certificate_nonce_native_receipt(const CertificateNonceParentAccumulator &accumulator, const CertificateNonceNativeReceipt &receipt, purify_secp_context *secp_context)
Result< CertificateNonceRecursiveManifestResolution > certificate_nonce_recursive_manifest(const CertificateNonceLeafAccumulator &leaf_accumulator, const bppp::accumulation::Digest &certificate_context_digest, std::span< const CertificateNonceRecursiveResponseView > ordered_responses, purify_secp_context *secp_context)
Result< CertificateNonceNativeReceipt > parse_certificate_nonce_native_receipt(const CertificateNonceParentAccumulator &accumulator, std::span< const unsigned char > encoded, purify_secp_context *secp_context)
Result< CertificateNonceAuthorizationManifest > certificate_nonce_authorization_manifest(const bppp::accumulation::Digest &certificate_context_digest, std::uint64_t total_responses, std::span< const CertificateNonceResponseAuthorization > responses)
Result< bppp::accumulation::Digest > certificate_nonce_recursive_member_digest(const CertificateNonceResponseAuthorization &authorization, std::uint32_t member_ordinal, const PublicKey &host, const PreparedCertificateNonceLeaf &leaf, const accountable::ConflictContext &context, purify_secp_context *secp_context)
Status require_secp_context(const purify_secp_context *context, const char *error_context)
Definition common.hpp:56
constexpr Unexpected< Error > unexpected_error(ErrorCode code, const char *context=nullptr)
Constructs an unexpected Error value from a machine-readable code.
Definition error.hpp:293
bool size_fits_u64(std::size_t value) noexcept
Definition common.hpp:83
bool checked_mul_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
Definition common.hpp:71
Expected< T, Error > Result
Expected-returning convenience alias for Purify value-producing APIs.
Definition error.hpp:99
Expected< void, Error > Status
Expected-returning convenience alias for Purify status-only APIs.
Definition error.hpp:102
std::vector< unsigned char > Bytes
Dynamically sized byte string used for messages, serialized witnesses, and proofs.
Definition common.hpp:99
bool checked_add_size(std::size_t lhs, std::size_t rhs, std::size_t &out) noexcept
Definition common.hpp:63
struct purify_secp_context purify_secp_context
Caller-owned reusable secp256k1 context handle shared across Purify C and C++ APIs.
std::array< unsigned char, Words *8 > to_bytes_be() const
Serializes the value to a fixed-width big-endian byte array.
Definition numeric.hpp:640
Public context shared by conflicting statements in one slashable slot.
std::array< unsigned char, 32 > signing_key
std::vector< bppp::accumulation::AlgebraicNormReductionProof > reductions
static constexpr std::size_t kSerializedSize
Definition bppp.hpp:73
Cacheable topic-bound nonce-proof template for the BPPP-backed PureSign++ proof(R) flow.
Definition bppp.hpp:278
static Result< TopicProofCache > build(std::span< const unsigned char > topic)
Builds a reusable verifier template for one exact topic.
Definition bppp.cpp:389
int PURIFY_UINT_FN is_zero(const uint64_t value[PURIFY_UINT_WORDS])
Definition uint_impl.h:38