Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
eccvm_transcript.test.cpp
Go to the documentation of this file.
9#include <gtest/gtest.h>
10
11using namespace bb;
12
13class ECCVMTranscriptTests : public ::testing::Test {
14 public:
19
32 {
33 TranscriptManifest manifest_expected;
34 // Size of types is number of bb::frs needed to represent the type
35 size_t frs_per_Fq = bb::field_conversion::calc_num_bn254_frs<FF>();
36 size_t frs_per_Fr = bb::field_conversion::calc_num_bn254_frs<Flavor::BF>();
37 size_t frs_per_G = bb::field_conversion::calc_num_bn254_frs<typename Flavor::Commitment>();
38 size_t frs_per_evals = (Flavor::NUM_ALL_ENTITIES)*frs_per_Fq;
39
40 size_t round = 0;
41 manifest_expected.add_entry(round, "vk_hash", frs_per_Fr);
42 manifest_expected.add_entry(round, "TRANSCRIPT_ADD", frs_per_G);
43 manifest_expected.add_entry(round, "TRANSCRIPT_EQ", frs_per_G);
44 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_TRANSITION", frs_per_G);
45 manifest_expected.add_entry(round, "TRANSCRIPT_PX", frs_per_G);
46 manifest_expected.add_entry(round, "TRANSCRIPT_PY", frs_per_G);
47 manifest_expected.add_entry(round, "TRANSCRIPT_Z1", frs_per_G);
48 manifest_expected.add_entry(round, "TRANSCRIPT_Z2", frs_per_G);
49 manifest_expected.add_entry(round, "TRANSCRIPT_Z1ZERO", frs_per_G);
50 manifest_expected.add_entry(round, "TRANSCRIPT_Z2ZERO", frs_per_G);
51 manifest_expected.add_entry(round, "TRANSCRIPT_OP", frs_per_G);
52 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_X", frs_per_G);
53 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_Y", frs_per_G);
54 manifest_expected.add_entry(round, "PRECOMPUTE_POINT_TRANSITION", frs_per_G);
55 manifest_expected.add_entry(round, "PRECOMPUTE_S1LO", frs_per_G);
56 manifest_expected.add_entry(round, "PRECOMPUTE_S2HI", frs_per_G);
57 manifest_expected.add_entry(round, "PRECOMPUTE_S2LO", frs_per_G);
58 manifest_expected.add_entry(round, "PRECOMPUTE_S3HI", frs_per_G);
59 manifest_expected.add_entry(round, "PRECOMPUTE_S3LO", frs_per_G);
60 manifest_expected.add_entry(round, "PRECOMPUTE_S4HI", frs_per_G);
61 manifest_expected.add_entry(round, "PRECOMPUTE_S4LO", frs_per_G);
62 manifest_expected.add_entry(round, "PRECOMPUTE_SKEW", frs_per_G);
63 manifest_expected.add_entry(round, "MSM_SIZE_OF_MSM", frs_per_G);
64 manifest_expected.add_entry(round, "MSM_ADD2", frs_per_G);
65 manifest_expected.add_entry(round, "MSM_ADD3", frs_per_G);
66 manifest_expected.add_entry(round, "MSM_ADD4", frs_per_G);
67 manifest_expected.add_entry(round, "MSM_X1", frs_per_G);
68 manifest_expected.add_entry(round, "MSM_Y1", frs_per_G);
69 manifest_expected.add_entry(round, "MSM_X2", frs_per_G);
70 manifest_expected.add_entry(round, "MSM_Y2", frs_per_G);
71 manifest_expected.add_entry(round, "MSM_X3", frs_per_G);
72 manifest_expected.add_entry(round, "MSM_Y3", frs_per_G);
73 manifest_expected.add_entry(round, "MSM_X4", frs_per_G);
74 manifest_expected.add_entry(round, "MSM_Y4", frs_per_G);
75 manifest_expected.add_entry(round, "MSM_COLLISION_X1", frs_per_G);
76 manifest_expected.add_entry(round, "MSM_COLLISION_X2", frs_per_G);
77 manifest_expected.add_entry(round, "MSM_COLLISION_X3", frs_per_G);
78 manifest_expected.add_entry(round, "MSM_COLLISION_X4", frs_per_G);
79 manifest_expected.add_entry(round, "MSM_LAMBDA1", frs_per_G);
80 manifest_expected.add_entry(round, "MSM_LAMBDA2", frs_per_G);
81 manifest_expected.add_entry(round, "MSM_LAMBDA3", frs_per_G);
82 manifest_expected.add_entry(round, "MSM_LAMBDA4", frs_per_G);
83 manifest_expected.add_entry(round, "MSM_SLICE1", frs_per_G);
84 manifest_expected.add_entry(round, "MSM_SLICE2", frs_per_G);
85 manifest_expected.add_entry(round, "MSM_SLICE3", frs_per_G);
86 manifest_expected.add_entry(round, "MSM_SLICE4", frs_per_G);
87 manifest_expected.add_entry(round, "TRANSCRIPT_RESET_ACCUMULATOR", frs_per_G);
88 manifest_expected.add_entry(round, "LOOKUP_READ_COUNTS_0", frs_per_G);
89 manifest_expected.add_entry(round, "LOOKUP_READ_COUNTS_1", frs_per_G);
90 manifest_expected.add_entry(round, "TRANSCRIPT_BASE_INFINITY", frs_per_G);
91 manifest_expected.add_entry(round, "TRANSCRIPT_BASE_X_INVERSE", frs_per_G);
92 manifest_expected.add_entry(round, "TRANSCRIPT_BASE_Y_INVERSE", frs_per_G);
93 manifest_expected.add_entry(round, "TRANSCRIPT_ADD_X_EQUAL", frs_per_G);
94 manifest_expected.add_entry(round, "TRANSCRIPT_ADD_Y_EQUAL", frs_per_G);
95 manifest_expected.add_entry(round, "TRANSCRIPT_ADD_LAMBDA", frs_per_G);
96 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_INTERMEDIATE_X", frs_per_G);
97 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_INTERMEDIATE_Y", frs_per_G);
98 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_INFINITY", frs_per_G);
99 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_X_INVERSE", frs_per_G);
100 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_COUNT_ZERO_AT_TRANSITION", frs_per_G);
101 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_COUNT_AT_TRANSITION_INVERSE", frs_per_G);
102 manifest_expected.add_entry(round, "TRANSCRIPT_MUL", frs_per_G);
103 manifest_expected.add_entry(round, "TRANSCRIPT_MSM_COUNT", frs_per_G);
104 manifest_expected.add_entry(round, "PRECOMPUTE_SCALAR_SUM", frs_per_G);
105 manifest_expected.add_entry(round, "PRECOMPUTE_S1HI", frs_per_G);
106 manifest_expected.add_entry(round, "PRECOMPUTE_DX", frs_per_G);
107 manifest_expected.add_entry(round, "PRECOMPUTE_DY", frs_per_G);
108 manifest_expected.add_entry(round, "PRECOMPUTE_TX", frs_per_G);
109 manifest_expected.add_entry(round, "PRECOMPUTE_TY", frs_per_G);
110 manifest_expected.add_entry(round, "MSM_TRANSITION", frs_per_G);
111 manifest_expected.add_entry(round, "MSM_ADD", frs_per_G);
112 manifest_expected.add_entry(round, "MSM_DOUBLE", frs_per_G);
113 manifest_expected.add_entry(round, "MSM_SKEW", frs_per_G);
114 manifest_expected.add_entry(round, "MSM_ACCUMULATOR_X", frs_per_G);
115 manifest_expected.add_entry(round, "MSM_ACCUMULATOR_Y", frs_per_G);
116 manifest_expected.add_entry(round, "MSM_COUNT", frs_per_G);
117 manifest_expected.add_entry(round, "MSM_ROUND", frs_per_G);
118 manifest_expected.add_entry(round, "MSM_ADD1", frs_per_G);
119 manifest_expected.add_entry(round, "MSM_PC", frs_per_G);
120 manifest_expected.add_entry(round, "PRECOMPUTE_PC", frs_per_G);
121 manifest_expected.add_entry(round, "TRANSCRIPT_PC", frs_per_G);
122 manifest_expected.add_entry(round, "PRECOMPUTE_ROUND", frs_per_G);
123 manifest_expected.add_entry(round, "PRECOMPUTE_SELECT", frs_per_G);
124 manifest_expected.add_entry(round, "TRANSCRIPT_ACCUMULATOR_NOT_EMPTY", frs_per_G);
125 manifest_expected.add_entry(round, "TRANSCRIPT_ACCUMULATOR_X", frs_per_G);
126 manifest_expected.add_entry(round, "TRANSCRIPT_ACCUMULATOR_Y", frs_per_G);
127 manifest_expected.add_challenge(round, "beta", "gamma");
128
129 round++;
130 manifest_expected.add_entry(round, "LOOKUP_INVERSES", frs_per_G);
131 manifest_expected.add_entry(round, "Z_PERM", frs_per_G);
132 manifest_expected.add_challenge(round, "Sumcheck:alpha");
133
134 for (size_t i = 0; i < CONST_ECCVM_LOG_N; i++) {
135 round++;
136 std::string label = "Sumcheck:gate_challenge_" + std::to_string(i);
137 manifest_expected.add_challenge(round, label);
138 }
139 round++;
140
141 manifest_expected.add_entry(round, "Libra:concatenation_commitment", frs_per_G);
142 manifest_expected.add_entry(round, "Libra:Sum", frs_per_Fq);
143 // get the challenge for the ZK Sumcheck claim
144 manifest_expected.add_challenge(round, "Libra:Challenge");
145
146 for (size_t i = 0; i < CONST_ECCVM_LOG_N; ++i) {
147 round++;
148 std::string idx = std::to_string(i);
149 manifest_expected.add_entry(round, "Sumcheck:univariate_comm_" + idx, frs_per_G);
150 manifest_expected.add_entry(round, "Sumcheck:univariate_" + idx + "_eval_0", frs_per_Fq);
151 manifest_expected.add_entry(round, "Sumcheck:univariate_" + idx + "_eval_1", frs_per_Fq);
152 std::string label = "Sumcheck:u_" + idx;
153 manifest_expected.add_challenge(round, label);
154 }
155
156 round++;
157
158 manifest_expected.add_entry(round, "Sumcheck:evaluations", frs_per_evals);
159 manifest_expected.add_entry(round, "Libra:claimed_evaluation", frs_per_Fq);
160 manifest_expected.add_entry(round, "Libra:grand_sum_commitment", frs_per_G);
161 manifest_expected.add_entry(round, "Libra:quotient_commitment", frs_per_G);
162 manifest_expected.add_entry(round, "Gemini:masking_poly_comm", frs_per_G);
163 manifest_expected.add_entry(round, "Gemini:masking_poly_eval", frs_per_Fq);
164
165 manifest_expected.add_challenge(round, "rho");
166
167 round++;
168 for (size_t i = 1; i < CONST_ECCVM_LOG_N; ++i) {
169 std::string idx = std::to_string(i);
170 manifest_expected.add_entry(round, "Gemini:FOLD_" + idx, frs_per_G);
171 }
172 manifest_expected.add_challenge(round, "Gemini:r");
173 round++;
174 for (size_t i = 1; i <= CONST_ECCVM_LOG_N; ++i) {
175 std::string idx = std::to_string(i);
176 manifest_expected.add_entry(round, "Gemini:a_" + idx, frs_per_Fq);
177 }
178 manifest_expected.add_entry(round, "Libra:concatenation_eval", frs_per_Fq);
179 manifest_expected.add_entry(round, "Libra:shifted_grand_sum_eval", frs_per_Fq);
180 manifest_expected.add_entry(round, "Libra:grand_sum_eval", frs_per_Fq);
181 manifest_expected.add_entry(round, "Libra:quotient_eval", frs_per_Fq);
182 manifest_expected.add_challenge(round, "Shplonk:nu");
183 round++;
184 manifest_expected.add_entry(round, "Shplonk:Q", frs_per_G);
185 manifest_expected.add_challenge(round, "Shplonk:z");
186
187 round++;
188 manifest_expected.add_entry(round, "Translation:concatenated_masking_term_commitment", frs_per_G);
189 manifest_expected.add_challenge(round, "Translation:evaluation_challenge_x");
190
191 round++;
192 manifest_expected.add_entry(round, "Translation:op", frs_per_Fq);
193 manifest_expected.add_entry(round, "Translation:Px", frs_per_Fq);
194 manifest_expected.add_entry(round, "Translation:Py", frs_per_Fq);
195 manifest_expected.add_entry(round, "Translation:z1", frs_per_Fq);
196 manifest_expected.add_entry(round, "Translation:z2", frs_per_Fq);
197 manifest_expected.add_challenge(round, "Translation:batching_challenge_v");
198
199 round++;
200 manifest_expected.add_entry(round, "Translation:masking_term_eval", frs_per_Fq);
201 manifest_expected.add_entry(round, "Translation:grand_sum_commitment", frs_per_G);
202 manifest_expected.add_entry(round, "Translation:quotient_commitment", frs_per_G);
203 manifest_expected.add_challenge(round, "Translation:small_ipa_evaluation_challenge");
204
205 round++;
206 manifest_expected.add_entry(round, "Translation:concatenation_eval", frs_per_Fq);
207 manifest_expected.add_entry(round, "Translation:grand_sum_shift_eval", frs_per_Fq);
208 manifest_expected.add_entry(round, "Translation:grand_sum_eval", frs_per_Fq);
209 manifest_expected.add_entry(round, "Translation:quotient_eval", frs_per_Fq);
210 manifest_expected.add_challenge(round, "Shplonk:nu");
211
212 round++;
213 manifest_expected.add_entry(round, "Shplonk:Q", frs_per_G);
214 manifest_expected.add_challenge(round, "Shplonk:z");
215
216 return manifest_expected;
217 }
218
220 {
221 TranscriptManifest manifest_expected;
222 // Size of types is number of bb::frs needed to represent the type
223 size_t frs_per_Fq = bb::field_conversion::calc_num_bn254_frs<FF>();
224 size_t frs_per_G = bb::field_conversion::calc_num_bn254_frs<typename Flavor::Commitment>();
225 size_t round = 0;
226
227 manifest_expected.add_entry(round, "IPA:commitment", frs_per_G);
228 manifest_expected.add_entry(round, "IPA:challenge", frs_per_Fq);
229 manifest_expected.add_entry(round, "IPA:evaluation", frs_per_Fq);
230 manifest_expected.add_challenge(round, "IPA:generator_challenge");
231
232 for (size_t i = 0; i < CONST_ECCVM_LOG_N; ++i) {
233 round++;
234 std::string idx = std::to_string(CONST_ECCVM_LOG_N - i - 1);
235 manifest_expected.add_entry(round, "IPA:L_" + idx, frs_per_G);
236 manifest_expected.add_entry(round, "IPA:R_" + idx, frs_per_G);
237 std::string label = "IPA:round_challenge_" + idx;
238 manifest_expected.add_challenge(round, label);
239 }
240
241 round++;
242 manifest_expected.add_entry(round, "IPA:G_0", frs_per_G);
243 manifest_expected.add_entry(round, "IPA:a_0", frs_per_Fq);
244 return manifest_expected;
245 }
246
248 {
250 using G1 = typename Flavor::CycleGroup;
251 using Fr = typename G1::Fr;
252
253 auto generators = G1::derive_generators("test generators", 3);
254
255 typename G1::element a = generators[0];
256 typename G1::element b = generators[1];
257 typename G1::element c = generators[2];
260
261 op_queue->add_accumulate(a);
262 op_queue->mul_accumulate(a, x);
263 op_queue->mul_accumulate(b, x);
264 op_queue->mul_accumulate(b, y);
265 op_queue->add_accumulate(a);
266 op_queue->mul_accumulate(b, x);
267 op_queue->eq_and_reset();
268 op_queue->add_accumulate(c);
269 op_queue->mul_accumulate(a, x);
270 op_queue->mul_accumulate(b, x);
271 op_queue->eq_and_reset();
272 op_queue->mul_accumulate(a, x);
273 op_queue->mul_accumulate(b, x);
274 op_queue->mul_accumulate(c, x);
275 op_queue->merge();
276
277 ECCVMCircuitBuilder builder{ op_queue };
278 return builder;
279 }
280};
281
283
288TEST_F(ECCVMTranscriptTests, ProverManifestConsistency)
289{
290 // Construct a simple circuit
291 auto builder = this->generate_trace(&engine);
292
293 // Automatically generate a transcript manifest by constructing a proof
294 std::shared_ptr<Transcript> prover_transcript = std::make_shared<Transcript>();
295 ECCVMProver prover(builder, prover_transcript);
296 prover.transcript->enable_manifest();
297 prover.ipa_transcript->enable_manifest();
298 ECCVMProof proof = prover.construct_proof();
299
300 // Check that the prover generated manifest agrees with the manifest hard coded in this suite
301 auto manifest_expected = this->construct_eccvm_honk_manifest();
302 auto prover_manifest = prover.transcript->get_manifest();
303
304 // Note: a manifest can be printed using manifest.print()
305 ASSERT_GT(manifest_expected.size(), 0);
306 for (size_t round = 0; round < manifest_expected.size(); ++round) {
307 ASSERT_EQ(prover_manifest[round], manifest_expected[round]) << "Prover manifest discrepency in round " << round;
308 }
309
310 auto ipa_manifest_expected = this->construct_eccvm_ipa_manifest();
311 auto prover_ipa_manifest = prover.ipa_transcript->get_manifest();
312
313 // Note: a manifest can be printed using manifest.print()
314 ASSERT_GT(ipa_manifest_expected.size(), 0);
315 for (size_t round = 0; round < ipa_manifest_expected.size(); ++round) {
316 ASSERT_EQ(prover_ipa_manifest[round], ipa_manifest_expected[round])
317 << "IPA prover manifest discrepency in round " << round;
318 }
319}
320
326TEST_F(ECCVMTranscriptTests, VerifierManifestConsistency)
327{
328 // Construct a simple circuit
329 auto builder = this->generate_trace(&engine);
330
331 // Automatically generate a transcript manifest in the prover by constructing a proof
332 std::shared_ptr<Transcript> prover_transcript = std::make_shared<Transcript>();
333 ECCVMProver prover(builder, prover_transcript);
334 prover_transcript->enable_manifest();
335 prover.ipa_transcript->enable_manifest();
336 ECCVMProof proof = prover.construct_proof();
337
338 // Automatically generate a transcript manifest in the verifier by verifying a proof
339 std::shared_ptr<Transcript> verifier_transcript = std::make_shared<Transcript>();
340 ECCVMVerifier verifier(verifier_transcript);
341 verifier.transcript->enable_manifest();
342 verifier.ipa_transcript->enable_manifest();
343 verifier.verify_proof(proof);
344
345 // Check consistency between the manifests generated by the prover and verifier
346 auto prover_manifest = prover.transcript->get_manifest();
347 auto verifier_manifest = verifier.transcript->get_manifest();
348
349 // Note: a manifest can be printed using manifest.print()
350 // The last challenge generated by the ECCVM Prover is the translation univariate batching challenge and, on the
351 // verifier side, is only generated in the translator verifier hence the ECCVM prover's manifest will have one extra
352 // challenge
353 ASSERT_GT(prover_manifest.size(), 0);
354 for (size_t round = 0; round < prover_manifest.size() - 1; ++round) {
355 ASSERT_EQ(prover_manifest[round], verifier_manifest[round])
356 << "Prover/Verifier manifest discrepency in round " << round;
357 }
358
359 // Check consistency of IPA transcripts
360 auto prover_ipa_manifest = prover.ipa_transcript->get_manifest();
361 auto verifier_ipa_manifest = verifier.ipa_transcript->get_manifest();
362 ASSERT_GT(prover_ipa_manifest.size(), 0);
363 for (size_t round = 0; round < prover_ipa_manifest.size(); ++round) {
364 ASSERT_EQ(prover_ipa_manifest[round], verifier_ipa_manifest[round])
365 << "Prover/Verifier IPA manifest discrepency in round " << round;
366 }
367}
368
374TEST_F(ECCVMTranscriptTests, ChallengeGenerationTest)
375{
376 // initialized with random value sent to verifier
377 auto transcript = Flavor::Transcript::prover_init_empty();
378 // test a bunch of challenges
379 auto challenges = transcript->template get_challenges<FF>("a", "b", "c", "d", "e", "f");
380 // check they are not 0
381 for (size_t i = 0; i < challenges.size(); ++i) {
382 ASSERT_NE(challenges[i], 0) << "Challenge " << i << " is 0";
383 }
384 constexpr uint32_t random_val{ 17 }; // arbitrary
385 transcript->send_to_verifier("random val", random_val);
386 // test more challenges
387 auto [a, b, c] = transcript->template get_challenges<FF>("a", "b", "c");
388
389 ASSERT_NE(a, 0) << "Challenge a is 0";
390 ASSERT_NE(b, 0) << "Challenge b is 0";
391 ASSERT_NE(c, 0) << "Challenge c is 0";
392}
ECCVMCircuitBuilder generate_trace(numeric::RNG *engine=nullptr)
TranscriptManifest construct_eccvm_honk_manifest()
Construct a manifest for a ECCVM Honk proof.
TranscriptManifest construct_eccvm_ipa_manifest()
Common transcript class for both parties. Stores the data for the current round, as well as the manif...
static constexpr size_t NUM_ALL_ENTITIES
NativeTranscript Transcript
ECCVMProof construct_proof()
std::shared_ptr< Transcript > ipa_transcript
std::shared_ptr< Transcript > transcript
bool verify_proof(const ECCVMProof &proof)
This function verifies an ECCVM Honk proof for given program settings.
std::shared_ptr< Transcript > ipa_transcript
std::shared_ptr< Transcript > transcript
void add_entry(size_t round, const std::string &element_label, size_t element_size)
void add_challenge(size_t round, Strings &... labels)
AluTraceBuilder builder
Definition alu.test.cpp:123
FF a
FF b
numeric::RNG & engine
Base class templates for structures that contain data parameterized by the fundamental polynomials of...
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:190
std::filesystem::path bb_crs_path()
void init_file_crs_factory(const std::filesystem::path &path)
Entry point for Barretenberg command-line interface.
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:123
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
std::string to_string(bb::avm2::ValueTag tag)
Curve::AffineElement G1
static field random_element(numeric::RNG *engine=nullptr) noexcept