Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
partial_evaluation.test.cpp
Go to the documentation of this file.
1#include "barretenberg/flavor/ultra_flavor.hpp"
2#include "barretenberg/sumcheck/sumcheck.hpp"
3
4#include <cstddef>
5#include <gtest/gtest.h>
6
7using namespace bb;
8
9namespace {
10template <typename Flavor> class PartialEvaluationTests : public testing::Test {};
11
12using Flavors = testing::Types<bb::UltraFlavor>;
13} // namespace
14
15TYPED_TEST_SUITE(PartialEvaluationTests, Flavors);
16
17/*
18 * We represent a bivariate f0 as f0(X0, X1). The indexing starts from 0 to match with the round number in sumcheck.
19 * The idea is variable X0 (lsb) will be folded at round 2 (the first sumcheck round),
20 * then the variable X1 (msb) will be folded at round 1 (the last rond in this case). Pictorially we have,
21 * v10 ------ v11
22 * | |
23 * X0(lsb) | |
24 * | X1(msb) |
25 * v00 ------ v01
26 * f0(X0, X1) = v00 * (1-X0) * (1-X1)
27 * + v10 * X0 * (1-X1)
28 * + v01 * (1-X0) * X1
29 * + v11 * X0 * X1.
30 *
31 * To effectively represent folding we write,
32 * f0(X0, X1) = [v00 * (1-X0) + v10 * X0] * (1-X1)
33 * + [v01 * (1-X0) + v11 * X0] * X1.
34 *
35 * After folding at round 0 (round challenge u0), we have,
36 * f0(u0,X1) = (v00 * (1-u0) + v10 * u0) * (1-X1)
37 * + (v01 * (1-u0) + v11 * u0) * X1.
38 *
39 * After folding at round 1 (round challenge u1), we have,
40 * f0(u0,u1) = (v00 * (1-u0) + v10 * u0) * (1-u1)
41 * + (v01 * (1-u0) + v11 * u0) * u1.
42 */
43TYPED_TEST(PartialEvaluationTests, TwoRoundsSpecial)
44{
45 using Flavor = TypeParam;
46 using FF = Flavor::FF;
47 using Polynomial = Flavor::Polynomial;
48 using Transcript = Flavor::Transcript;
49 using SubrelationSeparators = Flavor::SubrelationSeparators;
50
51 // values here are chosen to check another test
52 static constexpr size_t multivariate_d(2);
53 static constexpr size_t multivariate_n(1 << multivariate_d);
54
55 FF v00 = 0;
56 FF v10 = 1;
57 FF v01 = 0;
58 FF v11 = 0;
59
60 Polynomial f0(4);
61 f0.template copy_vector<FF>({ v00, v10, v01, v11 });
62
63 typename Flavor::ProverPolynomials full_polynomials;
64 full_polynomials.q_m = f0;
65 auto transcript = Transcript::prover_init_empty();
66 SubrelationSeparators alpha{ 1 };
67 std::vector<FF> gate_challenges{ 1, 1 };
68
69 SumcheckProver<Flavor> sumcheck(
70 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
71
72 FF round_challenge_0 = { 0x6c7301b49d85a46c, 0x44311531e39c64f6, 0xb13d66d8d6c1a24c, 0x04410c360230a295 };
73 round_challenge_0.self_to_montgomery_form();
74 FF expected_lo = v00 * (FF(1) - round_challenge_0) + v10 * round_challenge_0;
75 FF expected_hi = v01 * (FF(1) - round_challenge_0) + v11 * round_challenge_0;
76
77 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
78 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
79
80 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
81 EXPECT_EQ(first_polynomial[0], round_challenge_0);
82 EXPECT_EQ(first_polynomial[1], FF(0));
83
84 FF round_challenge_1 = 2;
85 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
86
87 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
88 EXPECT_EQ(first_polynomial[0], expected_val);
89}
90
91TYPED_TEST(PartialEvaluationTests, TwoRoundsGeneric)
92{
93 using Flavor = TypeParam;
94 using FF = Flavor::FF;
95 using Polynomial = Flavor::Polynomial;
96 using Transcript = Flavor::Transcript;
97 using SubrelationSeparators = Flavor::SubrelationSeparators;
98
99 static constexpr size_t multivariate_d(2);
100 static constexpr size_t multivariate_n(1 << multivariate_d);
101
102 FF v00 = FF::random_element();
103 FF v10 = FF::random_element();
104 FF v01 = FF::random_element();
105 FF v11 = FF::random_element();
106
107 Polynomial f0(4);
108 f0.template copy_vector<FF>({ v00, v10, v01, v11 });
109
110 auto transcript = Transcript::prover_init_empty();
111 SubrelationSeparators alpha{ 1 };
112 typename Flavor::ProverPolynomials full_polynomials;
113 full_polynomials.q_m = f0;
114 std::vector<FF> gate_challenges{ 1, 1 };
115
116 SumcheckProver<Flavor> sumcheck(
117 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
118
119 FF round_challenge_0 = FF::random_element();
120 FF expected_lo = v00 * (FF(1) - round_challenge_0) + v10 * round_challenge_0;
121 FF expected_hi = v01 * (FF(1) - round_challenge_0) + v11 * round_challenge_0;
122
123 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
124 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
125 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
126
127 EXPECT_EQ(first_polynomial[0], expected_lo);
128 EXPECT_EQ(first_polynomial[1], expected_hi);
129
130 FF round_challenge_1 = FF::random_element();
131 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
132 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
133 EXPECT_EQ(first_polynomial[0], expected_val);
134}
135
136/*
137 * Similarly for a trivariate polynomial f0(X0, X1, X2), we have
138 * f0(X0, X1, X2) = v000 * (1-X0) * (1-X1) * (1-X2)
139 * + v100 * X0 * (1-X1) * (1-X2)
140 * + v010 * (1-X0) * X1 * (1-X2)
141 * + v110 * X0 * X1 * (1-X2)
142 * + v001 * (1-X0) * (1-X1) * X2
143 * + v101 * X0 * (1-X1) * X2
144 * + v011 * (1-X0) * X1 * X2
145 * + v111 * X0 * X1 * X2.
146 * After round 0 (round challenge u0), we have
147 * f0(u0, X1, X2) = [v000 * (1-u0) + v100 * u0] * (1-X1) * (1-X2)
148 * + [v010 * (1-u0) + v110 * u0] * X1 * (1-X2)
149 * + [v001 * (1-u0) + v101 * u0] * (1-X1) * X2
150 * + [v011 * (1-u0) + v111 * u0] * X1 * X2.
151 * After round 1 (round challenge u1), we have
152 * f0(u0, u1, X2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-X2)
153 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * X2.
154 * After round 2 (round challenge u2), we have
155 * f0(u0, u1, u2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-u2)
156 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * u2.
157 */
158TYPED_TEST(PartialEvaluationTests, ThreeRoundsSpecial)
159{
160 using Flavor = TypeParam;
161 using FF = Flavor::FF;
162 using Polynomial = Flavor::Polynomial;
163 using Transcript = Flavor::Transcript;
164 using SubrelationSeparators = Flavor::SubrelationSeparators;
165
166 static constexpr size_t multivariate_d(3);
167 static constexpr size_t multivariate_n(1 << multivariate_d);
168
169 FF v000 = 1;
170 FF v100 = 2;
171 FF v010 = 3;
172 FF v110 = 4;
173 FF v001 = 5;
174 FF v101 = 6;
175 FF v011 = 7;
176 FF v111 = 8;
177
178 Polynomial f0(8);
179 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
180
181 typename Flavor::ProverPolynomials full_polynomials;
182 full_polynomials.q_m = f0;
183 auto transcript = Transcript::prover_init_empty();
184 SubrelationSeparators alpha{ 1 };
185
186 std::vector<FF> gate_challenges{ 1, 1, 1 };
187
188 SumcheckProver<Flavor> sumcheck(
189 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
190
191 FF round_challenge_0 = 1;
192 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0; // 2
193 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0; // 4
194 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0; // 6
195 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0; // 8
196
197 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
198 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
199
200 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
201 EXPECT_EQ(first_polynomial[0], expected_q1);
202 EXPECT_EQ(first_polynomial[1], expected_q2);
203 EXPECT_EQ(first_polynomial[2], expected_q3);
204 EXPECT_EQ(first_polynomial[3], expected_q4);
205
206 FF round_challenge_1 = 2;
207 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1; // 6
208 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1; // 10
209
210 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
211 EXPECT_EQ(first_polynomial[0], expected_lo);
212 EXPECT_EQ(first_polynomial[1], expected_hi);
213
214 FF round_challenge_2 = 3;
215 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2; // 18
216 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
217 EXPECT_EQ(first_polynomial[0], expected_val);
218}
219
220TYPED_TEST(PartialEvaluationTests, ThreeRoundsGeneric)
221{
222 using Flavor = TypeParam;
223 using FF = Flavor::FF;
224 using Polynomial = Flavor::Polynomial;
225 using Transcript = Flavor::Transcript;
226 using SubrelationSeparators = Flavor::SubrelationSeparators;
227
228 static constexpr size_t multivariate_d(3);
229 static constexpr size_t multivariate_n(1 << multivariate_d);
230
231 FF v000 = FF::random_element();
232 FF v100 = FF::random_element();
233 FF v010 = FF::random_element();
234 FF v110 = FF::random_element();
235 FF v001 = FF::random_element();
236 FF v101 = FF::random_element();
237 FF v011 = FF::random_element();
238 FF v111 = FF::random_element();
239
240 Polynomial f0(8);
241 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
242
243 typename Flavor::ProverPolynomials full_polynomials;
244 full_polynomials.q_m = f0;
245
246 auto transcript = Transcript::prover_init_empty();
247 SubrelationSeparators alpha{ 1 };
248 std::vector<FF> gate_challenges{ 1, 1, 1 };
249
250 SumcheckProver<Flavor> sumcheck(
251 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
252
253 FF round_challenge_0 = FF::random_element();
254 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0;
255 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0;
256 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0;
257 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0;
258
259 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
260 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
261 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
262
263 EXPECT_EQ(first_polynomial[0], expected_q1);
264 EXPECT_EQ(first_polynomial[1], expected_q2);
265 EXPECT_EQ(first_polynomial[2], expected_q3);
266 EXPECT_EQ(first_polynomial[3], expected_q4);
267
268 FF round_challenge_1 = FF::random_element();
269 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1;
270 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1;
271
272 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
273 EXPECT_EQ(first_polynomial[0], expected_lo);
274 EXPECT_EQ(first_polynomial[1], expected_hi);
275
276 FF round_challenge_2 = FF::random_element();
277 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2;
278 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
279 EXPECT_EQ(first_polynomial[0], expected_val);
280}
281
282TYPED_TEST(PartialEvaluationTests, ThreeRoundsGenericMultiplePolys)
283{
284 using Flavor = TypeParam;
285 using FF = Flavor::FF;
286 using Polynomial = Flavor::Polynomial;
287 using Transcript = Flavor::Transcript;
288 using SubrelationSeparators = Flavor::SubrelationSeparators;
289
290 static constexpr size_t multivariate_d(3);
291 static constexpr size_t multivariate_n(1 << multivariate_d);
292 std::array<FF, 3> v000;
293 std::array<FF, 3> v100;
294 std::array<FF, 3> v010;
295 std::array<FF, 3> v110;
296 std::array<FF, 3> v001;
297 std::array<FF, 3> v101;
298 std::array<FF, 3> v011;
299 std::array<FF, 3> v111;
300
301 for (size_t i = 0; i < 3; i++) {
302 v000[i] = FF::random_element();
303 v100[i] = FF::random_element();
304 v010[i] = FF::random_element();
305 v110[i] = FF::random_element();
306 v001[i] = FF::random_element();
307 v101[i] = FF::random_element();
308 v011[i] = FF::random_element();
309 v111[i] = FF::random_element();
310 }
311 Polynomial f0(8), f1(8), f2(8);
312 f0.template copy_vector<FF>({ v000[0], v100[0], v010[0], v110[0], v001[0], v101[0], v011[0], v111[0] });
313 f1.template copy_vector<FF>({ v000[1], v100[1], v010[1], v110[1], v001[1], v101[1], v011[1], v111[1] });
314 f2.template copy_vector<FF>({ v000[2], v100[2], v010[2], v110[2], v001[2], v101[2], v011[2], v111[2] });
315
316 typename Flavor::ProverPolynomials full_polynomials;
317 // Set the first 3 ProverPolynomials
318 full_polynomials.q_m = f0;
319 full_polynomials.q_c = f1;
320 full_polynomials.q_l = f2;
321 auto transcript = Transcript::prover_init_empty();
322 SubrelationSeparators alpha{ 1 };
323 std::vector<FF> gate_challenges{ 1, 1, 1 };
324
325 SumcheckProver<Flavor> sumcheck(
326 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
327
328 std::array<FF, 3> expected_q1;
329 std::array<FF, 3> expected_q2;
330 std::array<FF, 3> expected_q3;
331 std::array<FF, 3> expected_q4;
332 FF round_challenge_0 = FF::random_element();
333 for (size_t i = 0; i < 3; i++) {
334 expected_q1[i] = v000[i] * (FF(1) - round_challenge_0) + v100[i] * round_challenge_0;
335 expected_q2[i] = v010[i] * (FF(1) - round_challenge_0) + v110[i] * round_challenge_0;
336 expected_q3[i] = v001[i] * (FF(1) - round_challenge_0) + v101[i] * round_challenge_0;
337 expected_q4[i] = v011[i] * (FF(1) - round_challenge_0) + v111[i] * round_challenge_0;
338 }
339
340 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
341 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
342 auto polynomial_get_all = sumcheck.partially_evaluated_polynomials.get_all();
343 for (size_t i = 0; i < 3; i++) {
344 EXPECT_EQ((polynomial_get_all[i])[0], expected_q1[i]);
345 EXPECT_EQ((polynomial_get_all[i])[1], expected_q2[i]);
346 EXPECT_EQ((polynomial_get_all[i])[2], expected_q3[i]);
347 EXPECT_EQ((polynomial_get_all[i])[3], expected_q4[i]);
348 }
349
350 FF round_challenge_1 = FF::random_element();
351 std::array<FF, 3> expected_lo;
352 std::array<FF, 3> expected_hi;
353 for (size_t i = 0; i < 3; i++) {
354 expected_lo[i] = expected_q1[i] * (FF(1) - round_challenge_1) + expected_q2[i] * round_challenge_1;
355 expected_hi[i] = expected_q3[i] * (FF(1) - round_challenge_1) + expected_q4[i] * round_challenge_1;
356 }
357 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
358 for (size_t i = 0; i < 3; i++) {
359 EXPECT_EQ((polynomial_get_all[i])[0], expected_lo[i]);
360 EXPECT_EQ((polynomial_get_all[i])[1], expected_hi[i]);
361 }
362 FF round_challenge_2 = FF::random_element();
363 std::array<FF, 3> expected_val;
364 for (size_t i = 0; i < 3; i++) {
365 expected_val[i] = expected_lo[i] * (FF(1) - round_challenge_2) + expected_hi[i] * round_challenge_2;
366 }
367 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
368 for (size_t i = 0; i < 3; i++) {
369 EXPECT_EQ((polynomial_get_all[i])[0], expected_val[i]);
370 }
371}
bb::BaseTranscript
Common transcript class for both parties. Stores the data for the current round, as well as the manif...
Definition transcript.hpp:154
bb::BaseTranscript::prover_init_empty
static std::shared_ptr< BaseTranscript > prover_init_empty()
For testing: initializes transcript with some arbitrary data so that a challenge can be generated aft...
Definition transcript.hpp:653
bb::ECCVMFlavor::PartiallyEvaluatedMultivariates
A container for storing the partially evaluated multivariates produced by sumcheck.
Definition eccvm_flavor.hpp:739
bb::ECCVMFlavor::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:437
bb::MegaFlavor::FF
Curve::ScalarField FF
Definition mega_flavor.hpp:37
bb::MegaFlavor::SubrelationSeparators
std::array< FF, NUM_SUBRELATIONS - 1 > SubrelationSeparators
Definition mega_flavor.hpp:126
bb::MegaFlavor::Transcript
NativeTranscript Transcript
Definition mega_flavor.hpp:45
bb::MegaFlavor::Polynomial
bb::Polynomial< FF > Polynomial
Definition mega_flavor.hpp:41
bb::Polynomial
Structured polynomial class that represents the coefficients 'a' of a_0 + a_1 x .....
Definition polynomial.hpp:74
bb::SumcheckProver
The implementation of the sumcheck Prover for statements of the form for multilinear polynomials .
Definition sumcheck.hpp:123
bb::SumcheckProver::partially_evaluate
SumcheckOutput< Flavor > prove(ZKData &zk_sumcheck_data) void partially_evaluate(auto &polynomials, const FF &round_challenge)
ZK-version of prove that runs Sumcheck with disabled rows and masking of Round Univariates....
Definition sumcheck.hpp:503
bb::SumcheckProver::partially_evaluated_polynomials
PartiallyEvaluatedMultivariates partially_evaluated_polynomials
Container for partially evaluated Prover Polynomials at a current challenge. Upon computing challenge...
Definition sumcheck.hpp:187
Flavors
testing::Types< UltraRecursiveFlavor_< UltraCircuitBuilder >, UltraRollupRecursiveFlavor_< UltraCircuitBuilder >, UltraRecursiveFlavor_< MegaCircuitBuilder >, UltraZKRecursiveFlavor_< UltraCircuitBuilder >, UltraZKRecursiveFlavor_< MegaCircuitBuilder > > Flavors
Definition honk_recursion_constraint.test.cpp:236
bb
Entry point for Barretenberg command-line interface.
Definition acir_format_getters.cpp:6
bb::TYPED_TEST_SUITE
TYPED_TEST_SUITE(ShpleminiTest, TestSettings)
bb::FF
typename Flavor::FF FF
Definition protogalaxy.bench.cpp:16
bb::TYPED_TEST
TYPED_TEST(ShpleminiTest, CorrectnessOfMultivariateClaimBatching)
Definition shplemini.test.cpp:47
ultra_flavor.hpp