Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
ultra_recursive_verifier.cpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: not started, auditors: [], date: YYYY-MM-DD }
3// external_1: { status: not started, auditors: [], date: YYYY-MM-DD }
4// external_2: { status: not started, auditors: [], date: YYYY-MM-DD }
5// =====================
6
7#include "barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.hpp"
8#include "barretenberg/commitment_schemes/shplonk/shplemini.hpp"
9#include "barretenberg/flavor/flavor.hpp"
10#include "barretenberg/honk/library/grand_product_delta.hpp"
11#include "barretenberg/numeric/bitop/get_msb.hpp"
12#include "barretenberg/stdlib/primitives/circuit_builders/circuit_builders_fwd.hpp"
13#include "barretenberg/stdlib/primitives/padding_indicator_array/padding_indicator_array.hpp"
14#include "barretenberg/stdlib/primitives/public_input_component/public_input_component.hpp"
15#include "barretenberg/stdlib/special_public_inputs/special_public_inputs.hpp"
16#include "barretenberg/transcript/transcript.hpp"
17
18namespace bb::stdlib::recursion::honk {
19
20template <typename Flavor>
21UltraRecursiveVerifier_<Flavor>::UltraRecursiveVerifier_(Builder* builder,
22 const std::shared_ptr<VKAndHash>& vk_and_hash,
23 const std::shared_ptr<Transcript>& transcript)
24 : verifier_instance(std::make_shared<RecursiveVerifierInstance>(builder, vk_and_hash))
25 , builder(builder)
26 , transcript(transcript)
27{}
28
35template <typename Flavor>
36template <class IO>
37UltraRecursiveVerifier_<Flavor>::Output UltraRecursiveVerifier_<Flavor>::verify_proof(
38 const stdlib::Proof<Builder>& proof)
39{
40 using Sumcheck = ::bb::SumcheckVerifier<Flavor>;
41 using PCS = typename Flavor::PCS;
42 using Curve = typename Flavor::Curve;
43 using Shplemini = ::bb::ShpleminiVerifier_<Curve>;
44 using VerifierCommitments = typename Flavor::VerifierCommitments;
45 using ClaimBatcher = ClaimBatcher_<Curve>;
46 using ClaimBatch = ClaimBatcher::Batch;
47
48 const size_t num_public_inputs =
49 static_cast<uint32_t>(verifier_instance->vk_and_hash->vk->num_public_inputs.get_value());
50 BB_ASSERT_EQ(proof.size(), Flavor::NativeFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS() + num_public_inputs);
51
52 StdlibProof ipa_proof;
53 StdlibProof honk_proof;
54 if constexpr (HasIPAAccumulator<Flavor>) {
55 const size_t HONK_PROOF_LENGTH = Flavor::NativeFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS() - IPA_PROOF_LENGTH;
56 // The extra calculation is for the IPA proof length.
57 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1182): Handle in ProofSurgeon.
58 BB_ASSERT_EQ(proof.size(), HONK_PROOF_LENGTH + IPA_PROOF_LENGTH + num_public_inputs);
59 // split out the ipa proof
60 const std::ptrdiff_t honk_proof_with_pub_inputs_length =
61 static_cast<std::ptrdiff_t>(HONK_PROOF_LENGTH + num_public_inputs);
62 ipa_proof = StdlibProof(proof.begin() + honk_proof_with_pub_inputs_length, proof.end());
63 honk_proof = StdlibProof(proof.begin(), proof.begin() + honk_proof_with_pub_inputs_length);
64 } else {
65 honk_proof = proof;
66 }
67 transcript->load_proof(honk_proof);
68 OinkVerifier oink_verifier{ verifier_instance, transcript };
69 oink_verifier.verify();
70 const std::vector<FF>& public_inputs = verifier_instance->public_inputs;
71
72 VerifierCommitments commitments{ verifier_instance->vk_and_hash->vk, verifier_instance->witness_commitments };
73
74 // For ZK flavors: set gemini_masking_poly commitment from verifier instance
75 if constexpr (Flavor::HasZK) {
76 commitments.gemini_masking_poly = verifier_instance->gemini_masking_commitment;
77 }
78
79 static constexpr size_t VIRTUAL_LOG_N = Flavor::NativeFlavor::VIRTUAL_LOG_N;
80 // Get the gate challenges for sumcheck computation
81 verifier_instance->gate_challenges =
82 transcript->template get_dyadic_powers_of_challenge<FF>("Sumcheck:gate_challenge", VIRTUAL_LOG_N);
83
84 // Execute Sumcheck Verifier and extract multivariate opening point u = (u_0, ..., u_{d-1}) and purported
85 // multivariate evaluations at u
86
87 std::vector<FF> padding_indicator_array(VIRTUAL_LOG_N, 1);
88 if constexpr (Flavor::HasZK) {
89 // TODO(https://github.com/AztecProtocol/barretenberg/issues/1521): ZK Recursive verifiers need to evaluate
90 // RowDisablingPolynomial, which requires knowing the actual `log_circuit_size`. Can be fixed by reserving the
91 // first rows of the trace for masking.
92 padding_indicator_array =
93 compute_padding_indicator_array<Curve, VIRTUAL_LOG_N>(verifier_instance->vk_and_hash->vk->log_circuit_size);
94 }
95
96 Sumcheck sumcheck(transcript, verifier_instance->alpha, VIRTUAL_LOG_N);
97
98 // Receive commitments to Libra masking polynomials
99 std::array<Commitment, NUM_LIBRA_COMMITMENTS> libra_commitments = {};
100 if constexpr (Flavor::HasZK) {
101 libra_commitments[0] = transcript->template receive_from_prover<Commitment>("Libra:concatenation_commitment");
102 }
103 SumcheckOutput<Flavor> sumcheck_output = sumcheck.verify(
104 verifier_instance->relation_parameters, verifier_instance->gate_challenges, padding_indicator_array);
105
106 // For MegaZKFlavor: the sumcheck output contains claimed evaluations of the Libra polynomials
107 if constexpr (Flavor::HasZK) {
108 libra_commitments[1] = transcript->template receive_from_prover<Commitment>("Libra:grand_sum_commitment");
109 libra_commitments[2] = transcript->template receive_from_prover<Commitment>("Libra:quotient_commitment");
110 }
111 // Execute Shplemini to produce a batch opening claim subsequently verified by a univariate PCS
112 bool consistency_checked = true;
113 ClaimBatcher claim_batcher{
114 .unshifted = ClaimBatch{ commitments.get_unshifted(), sumcheck_output.claimed_evaluations.get_unshifted() },
115 .shifted = ClaimBatch{ commitments.get_to_be_shifted(), sumcheck_output.claimed_evaluations.get_shifted() }
116 };
117 auto opening_claim = Shplemini::compute_batch_opening_claim(padding_indicator_array,
118 claim_batcher,
119 sumcheck_output.challenge,
120 Commitment::one(builder),
121 transcript,
122 Flavor::REPEATED_COMMITMENTS,
123 Flavor::HasZK,
124 &consistency_checked,
125 libra_commitments,
126 sumcheck_output.claimed_libra_evaluation);
127
128 PairingPoints<Curve> pairing_points = PCS::reduce_verify_batch_opening_claim(std::move(opening_claim), transcript);
129
130 // Reconstruct the public inputs
131 IO inputs;
132 inputs.reconstruct_from_public(public_inputs);
133
134 // Construct output
135 Output output(inputs);
136 output.ipa_proof = ipa_proof; // Add IPA proof
137
138 // Aggregate new pairing point with the ones reconstructed from the public inputs
139 output.points_accumulator.aggregate(pairing_points);
140
141 return output;
142}
143
144template class UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<UltraCircuitBuilder>>;
145template class UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<MegaCircuitBuilder>>;
146template class UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<UltraCircuitBuilder>>;
147template class UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<MegaCircuitBuilder>>;
148template class UltraRecursiveVerifier_<bb::UltraRollupRecursiveFlavor_<UltraCircuitBuilder>>;
149template class UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>;
150template class UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<MegaCircuitBuilder>>;
151template class UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<MegaCircuitBuilder>>;
152template class UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>;
153
154// UltraRecursiveFlavor_ specializations
155template UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
156 bb::UltraRecursiveFlavor_<UltraCircuitBuilder>>::
157 verify_proof<DefaultIO<UltraCircuitBuilder>>(
158 const UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
159
160template UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<MegaCircuitBuilder>>::Output UltraRecursiveVerifier_<
161 bb::UltraRecursiveFlavor_<MegaCircuitBuilder>>::
162 verify_proof<DefaultIO<MegaCircuitBuilder>>(
163 const UltraRecursiveVerifier_<bb::UltraRecursiveFlavor_<MegaCircuitBuilder>>::StdlibProof& proof);
164
165// UltraZKRecursiveFlavor_ specializations
166template UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
167 bb::UltraZKRecursiveFlavor_<UltraCircuitBuilder>>::
168 verify_proof<DefaultIO<UltraCircuitBuilder>>(
169 const UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
170
171template UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<MegaCircuitBuilder>>::Output UltraRecursiveVerifier_<
172 bb::UltraZKRecursiveFlavor_<MegaCircuitBuilder>>::
173 verify_proof<DefaultIO<MegaCircuitBuilder>>(
174 const UltraRecursiveVerifier_<bb::UltraZKRecursiveFlavor_<MegaCircuitBuilder>>::StdlibProof& proof);
175
176// UltraRollupRecursiveFlavor_ specialization
177template UltraRecursiveVerifier_<bb::UltraRollupRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
178 bb::UltraRollupRecursiveFlavor_<UltraCircuitBuilder>>::
179 verify_proof<RollupIO>(
180 const UltraRecursiveVerifier_<bb::UltraRollupRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
181
182// MegaRecursiveFlavor_ specialization with DefaultIO
183template UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
184 bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::
185 verify_proof<DefaultIO<UltraCircuitBuilder>>(
186 const UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
187
188template UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<MegaCircuitBuilder>>::Output UltraRecursiveVerifier_<
189 bb::MegaRecursiveFlavor_<MegaCircuitBuilder>>::
190 verify_proof<DefaultIO<MegaCircuitBuilder>>(
191 const UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<MegaCircuitBuilder>>::StdlibProof& proof);
192
193// MegaZKRecursiveFlavor_ specialization with DefaultIO
194template UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
195 bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::
196 verify_proof<DefaultIO<UltraCircuitBuilder>>(
197 const UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
198
199template UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<MegaCircuitBuilder>>::Output UltraRecursiveVerifier_<
200 bb::MegaZKRecursiveFlavor_<MegaCircuitBuilder>>::
201 verify_proof<DefaultIO<MegaCircuitBuilder>>(
202 const UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<MegaCircuitBuilder>>::StdlibProof& proof);
203
204// Chonk specialization
205template UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
206 bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::
207 verify_proof<HidingKernelIO<UltraCircuitBuilder>>(
208 const UltraRecursiveVerifier_<bb::MegaZKRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
209
210// GoblinAvm specialization
211template UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::Output UltraRecursiveVerifier_<
212 bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::
213 verify_proof<GoblinAvmIO<UltraCircuitBuilder>>(
214 const UltraRecursiveVerifier_<bb::MegaRecursiveFlavor_<UltraCircuitBuilder>>::StdlibProof& proof);
215
216} // namespace bb::stdlib::recursion::honk
BB_ASSERT_EQ
#define BB_ASSERT_EQ(actual, expected,...)
Definition assert.hpp:77
circuit_builders_fwd.hpp
bb::ECCVMFlavor::HasZK
static constexpr bool HasZK
Definition eccvm_flavor.hpp:57
bb::ECCVMFlavor::VerifierCommitments
VerifierCommitments_< Commitment, VerificationKey > VerifierCommitments
Definition eccvm_flavor.hpp:993
bb::ECCVMFlavor::Curve
curve::Grumpkin Curve
Definition eccvm_flavor.hpp:39
bb::ECCVMFlavor::PROOF_LENGTH_WITHOUT_PUB_INPUTS
static constexpr size_t PROOF_LENGTH_WITHOUT_PUB_INPUTS
Definition eccvm_flavor.hpp:123
bb::ECCVMFlavor::PCS
IPA< Curve > PCS
Definition eccvm_flavor.hpp:41
bb::ECCVMFlavor::REPEATED_COMMITMENTS
static constexpr RepeatedCommitmentsData REPEATED_COMMITMENTS
Definition eccvm_flavor.hpp:87
bb::MegaRecursiveFlavor_
The recursive counterpart to the "native" Mega flavor.
Definition mega_recursive_flavor.hpp:38
bb::MegaZKRecursiveFlavor_
The recursive counterpart to the "native" MegaZKFlavor.
Definition mega_zk_recursive_flavor.hpp:38
bb::OinkVerifier
Verifier class for all the presumcheck rounds, which are shared between the folding verifier and ultr...
Definition oink_verifier.hpp:35
bb::OinkVerifier::verify
void verify()
Oink Verifier function that runs all the rounds of the verifier.
Definition oink_verifier.cpp:28
bb::ShpleminiVerifier_
An efficient verifier for the evaluation proofs of multilinear polynomials and their shifts.
Definition shplemini.hpp:190
bb::SumcheckVerifier
Implementation of the sumcheck Verifier for statements of the form for multilinear polynomials .
Definition sumcheck.hpp:786
bb::UltraRecursiveFlavor_
The recursive counterpart to the "native" Ultra flavor.
Definition ultra_recursive_flavor.hpp:37
bb::UltraRollupRecursiveFlavor_
The recursive counterpart to the "native" UltraRollupFlavor.
Definition ultra_rollup_recursive_flavor.hpp:38
bb::UltraZKRecursiveFlavor_
The recursive counterpart to the Ultra flavor with ZK.
Definition ultra_zk_recursive_flavor.hpp:28
bb::stdlib::Proof
A simple wrapper around a vector of stdlib field elements representing a proof.
Definition proof.hpp:19
bb::stdlib::recursion::honk::RecursiveVerifierInstance_
The stdlib counterpart of VerifierInstance, used in recursive folding verification.
Definition recursive_verifier_instance.hpp:18
bb::stdlib::recursion::honk::UltraRecursiveVerifier_
Definition ultra_recursive_verifier.hpp:55
bb::stdlib::recursion::honk::UltraRecursiveVerifier_::UltraRecursiveVerifier_
UltraRecursiveVerifier_(Builder *builder, const std::shared_ptr< VKAndHash > &vk_and_hash, const std::shared_ptr< Transcript > &transcript=std::make_shared< Transcript >())
Definition ultra_recursive_verifier.cpp:21
bb::stdlib::recursion::honk::UltraRecursiveVerifier_::Builder
typename Flavor::CircuitBuilder Builder
Definition ultra_recursive_verifier.hpp:64
bb::stdlib::recursion::honk::UltraRecursiveVerifier_::verify_proof
Output verify_proof(const StdlibProof &proof)
builder
AluTraceBuilder builder
Definition alu.test.cpp:124
flavor.hpp
Base class templates for structures that contain data parameterized by the fundamental polynomials of...
get_msb.hpp
grand_product_delta.hpp
inputs
AvmProvingInputs inputs
Definition hinting_dbs.test.cpp:45
std
STL namespace.
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
padding_indicator_array.hpp
For a small integer N = virtual_log_n and a given witness x = log_n, compute in-circuit an indicator_...
public_input_component.hpp
special_public_inputs.hpp
bb::ClaimBatcher_
Logic to support batching opening claims for unshifted and shifted polynomials in Shplemini.
Definition claim_batcher.hpp:28
bb::SumcheckOutput
Contains the evaluations of multilinear polynomials at the challenge point . These are computed by S...
Definition sumcheck_output.hpp:22
bb::SumcheckOutput::claimed_evaluations
ClaimedEvaluations claimed_evaluations
Definition sumcheck_output.hpp:30
bb::SumcheckOutput::challenge
std::vector< FF > challenge
Definition sumcheck_output.hpp:28
bb::stdlib::recursion::PairingPoints
An object storing two EC points that represent the inputs to a pairing check.
Definition pairing_points.hpp:34
ultra_recursive_verifier.hpp