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
50 // values here are chosen to check another test
51 static constexpr size_t multivariate_d(2);
52 static constexpr size_t multivariate_n(1 << multivariate_d);
53
54 FF v00 = 0;
55 FF v10 = 1;
56 FF v01 = 0;
57 FF v11 = 0;
58
59 Polynomial f0(4);
60 f0.template copy_vector<FF>({ v00, v10, v01, v11 });
61
62 typename Flavor::ProverPolynomials full_polynomials;
63 full_polynomials.q_m = f0;
64 auto transcript = Transcript::prover_init_empty();
65 FF alpha = FF(1);
66 std::vector<FF> gate_challenges{ 1, 1 };
67
68 SumcheckProver<Flavor> sumcheck(
69 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
70
71 FF round_challenge_0 = { 0x6c7301b49d85a46c, 0x44311531e39c64f6, 0xb13d66d8d6c1a24c, 0x04410c360230a295 };
72 round_challenge_0.self_to_montgomery_form();
73 FF expected_lo = v00 * (FF(1) - round_challenge_0) + v10 * round_challenge_0;
74 FF expected_hi = v01 * (FF(1) - round_challenge_0) + v11 * round_challenge_0;
75
76 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
77 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
78
79 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
80 EXPECT_EQ(first_polynomial[0], round_challenge_0);
81 EXPECT_EQ(first_polynomial[1], FF(0));
82
83 FF round_challenge_1 = 2;
84 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
85
86 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
87 EXPECT_EQ(first_polynomial[0], expected_val);
88}
89
90TYPED_TEST(PartialEvaluationTests, TwoRoundsGeneric)
91{
92 using Flavor = TypeParam;
93 using FF = Flavor::FF;
94 using Polynomial = Flavor::Polynomial;
95 using Transcript = Flavor::Transcript;
96
97 static constexpr size_t multivariate_d(2);
98 static constexpr size_t multivariate_n(1 << multivariate_d);
99
100 FF v00 = FF::random_element();
101 FF v10 = FF::random_element();
102 FF v01 = FF::random_element();
103 FF v11 = FF::random_element();
104
105 Polynomial f0(4);
106 f0.template copy_vector<FF>({ v00, v10, v01, v11 });
107
108 auto transcript = Transcript::prover_init_empty();
109 FF alpha = FF(1);
110 typename Flavor::ProverPolynomials full_polynomials;
111 full_polynomials.q_m = f0;
112 std::vector<FF> gate_challenges{ 1, 1 };
113
114 SumcheckProver<Flavor> sumcheck(
115 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
116
117 FF round_challenge_0 = FF::random_element();
118 FF expected_lo = v00 * (FF(1) - round_challenge_0) + v10 * round_challenge_0;
119 FF expected_hi = v01 * (FF(1) - round_challenge_0) + v11 * round_challenge_0;
120
121 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
122 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
123 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
124
125 EXPECT_EQ(first_polynomial[0], expected_lo);
126 EXPECT_EQ(first_polynomial[1], expected_hi);
127
128 FF round_challenge_1 = FF::random_element();
129 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
130 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
131 EXPECT_EQ(first_polynomial[0], expected_val);
132}
133
134/*
135 * Similarly for a trivariate polynomial f0(X0, X1, X2), we have
136 * f0(X0, X1, X2) = v000 * (1-X0) * (1-X1) * (1-X2)
137 * + v100 * X0 * (1-X1) * (1-X2)
138 * + v010 * (1-X0) * X1 * (1-X2)
139 * + v110 * X0 * X1 * (1-X2)
140 * + v001 * (1-X0) * (1-X1) * X2
141 * + v101 * X0 * (1-X1) * X2
142 * + v011 * (1-X0) * X1 * X2
143 * + v111 * X0 * X1 * X2.
144 * After round 0 (round challenge u0), we have
145 * f0(u0, X1, X2) = [v000 * (1-u0) + v100 * u0] * (1-X1) * (1-X2)
146 * + [v010 * (1-u0) + v110 * u0] * X1 * (1-X2)
147 * + [v001 * (1-u0) + v101 * u0] * (1-X1) * X2
148 * + [v011 * (1-u0) + v111 * u0] * X1 * X2.
149 * After round 1 (round challenge u1), we have
150 * f0(u0, u1, X2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-X2)
151 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * X2.
152 * After round 2 (round challenge u2), we have
153 * f0(u0, u1, u2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-u2)
154 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * u2.
155 */
156TYPED_TEST(PartialEvaluationTests, ThreeRoundsSpecial)
157{
158 using Flavor = TypeParam;
159 using FF = Flavor::FF;
160 using Polynomial = Flavor::Polynomial;
161 using Transcript = Flavor::Transcript;
162
163 static constexpr size_t multivariate_d(3);
164 static constexpr size_t multivariate_n(1 << multivariate_d);
165
166 FF v000 = 1;
167 FF v100 = 2;
168 FF v010 = 3;
169 FF v110 = 4;
170 FF v001 = 5;
171 FF v101 = 6;
172 FF v011 = 7;
173 FF v111 = 8;
174
175 Polynomial f0(8);
176 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
177
178 typename Flavor::ProverPolynomials full_polynomials;
179 full_polynomials.q_m = f0;
180 auto transcript = Transcript::prover_init_empty();
181 FF alpha = FF(1);
182
183 std::vector<FF> gate_challenges{ 1, 1, 1 };
184
185 SumcheckProver<Flavor> sumcheck(
186 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
187
188 FF round_challenge_0 = 1;
189 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0; // 2
190 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0; // 4
191 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0; // 6
192 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0; // 8
193
194 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
195 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
196
197 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
198 EXPECT_EQ(first_polynomial[0], expected_q1);
199 EXPECT_EQ(first_polynomial[1], expected_q2);
200 EXPECT_EQ(first_polynomial[2], expected_q3);
201 EXPECT_EQ(first_polynomial[3], expected_q4);
202
203 FF round_challenge_1 = 2;
204 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1; // 6
205 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1; // 10
206
207 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
208 EXPECT_EQ(first_polynomial[0], expected_lo);
209 EXPECT_EQ(first_polynomial[1], expected_hi);
210
211 FF round_challenge_2 = 3;
212 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2; // 18
213 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
214 EXPECT_EQ(first_polynomial[0], expected_val);
215}
216
217TYPED_TEST(PartialEvaluationTests, ThreeRoundsGeneric)
218{
219 using Flavor = TypeParam;
220 using FF = Flavor::FF;
221 using Polynomial = Flavor::Polynomial;
222 using Transcript = Flavor::Transcript;
223
224 static constexpr size_t multivariate_d(3);
225 static constexpr size_t multivariate_n(1 << multivariate_d);
226
227 FF v000 = FF::random_element();
228 FF v100 = FF::random_element();
229 FF v010 = FF::random_element();
230 FF v110 = FF::random_element();
231 FF v001 = FF::random_element();
232 FF v101 = FF::random_element();
233 FF v011 = FF::random_element();
234 FF v111 = FF::random_element();
235
236 Polynomial f0(8);
237 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
238
239 typename Flavor::ProverPolynomials full_polynomials;
240 full_polynomials.q_m = f0;
241
242 auto transcript = Transcript::prover_init_empty();
243 FF alpha = FF(1);
244 std::vector<FF> gate_challenges{ 1, 1, 1 };
245
246 SumcheckProver<Flavor> sumcheck(
247 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
248
249 FF round_challenge_0 = FF::random_element();
250 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0;
251 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0;
252 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0;
253 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0;
254
255 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
256 auto& first_polynomial = sumcheck.partially_evaluated_polynomials.get_all()[0];
257 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
258
259 EXPECT_EQ(first_polynomial[0], expected_q1);
260 EXPECT_EQ(first_polynomial[1], expected_q2);
261 EXPECT_EQ(first_polynomial[2], expected_q3);
262 EXPECT_EQ(first_polynomial[3], expected_q4);
263
264 FF round_challenge_1 = FF::random_element();
265 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1;
266 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1;
267
268 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
269 EXPECT_EQ(first_polynomial[0], expected_lo);
270 EXPECT_EQ(first_polynomial[1], expected_hi);
271
272 FF round_challenge_2 = FF::random_element();
273 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2;
274 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
275 EXPECT_EQ(first_polynomial[0], expected_val);
276}
277
278TYPED_TEST(PartialEvaluationTests, ThreeRoundsGenericMultiplePolys)
279{
280 using Flavor = TypeParam;
281 using FF = Flavor::FF;
282 using Polynomial = Flavor::Polynomial;
283 using Transcript = Flavor::Transcript;
284
285 static constexpr size_t multivariate_d(3);
286 static constexpr size_t multivariate_n(1 << multivariate_d);
287 std::array<FF, 3> v000;
288 std::array<FF, 3> v100;
289 std::array<FF, 3> v010;
290 std::array<FF, 3> v110;
291 std::array<FF, 3> v001;
292 std::array<FF, 3> v101;
293 std::array<FF, 3> v011;
294 std::array<FF, 3> v111;
295
296 for (size_t i = 0; i < 3; i++) {
297 v000[i] = FF::random_element();
298 v100[i] = FF::random_element();
299 v010[i] = FF::random_element();
300 v110[i] = FF::random_element();
301 v001[i] = FF::random_element();
302 v101[i] = FF::random_element();
303 v011[i] = FF::random_element();
304 v111[i] = FF::random_element();
305 }
306 Polynomial f0(8), f1(8), f2(8);
307 f0.template copy_vector<FF>({ v000[0], v100[0], v010[0], v110[0], v001[0], v101[0], v011[0], v111[0] });
308 f1.template copy_vector<FF>({ v000[1], v100[1], v010[1], v110[1], v001[1], v101[1], v011[1], v111[1] });
309 f2.template copy_vector<FF>({ v000[2], v100[2], v010[2], v110[2], v001[2], v101[2], v011[2], v111[2] });
310
311 typename Flavor::ProverPolynomials full_polynomials;
312 // Set the first 3 ProverPolynomials
313 full_polynomials.q_m = f0;
314 full_polynomials.q_c = f1;
315 full_polynomials.q_l = f2;
316 auto transcript = Transcript::prover_init_empty();
317 FF alpha = FF(1);
318 std::vector<FF> gate_challenges{ 1, 1, 1 };
319
320 SumcheckProver<Flavor> sumcheck(
321 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
322
323 std::array<FF, 3> expected_q1;
324 std::array<FF, 3> expected_q2;
325 std::array<FF, 3> expected_q3;
326 std::array<FF, 3> expected_q4;
327 FF round_challenge_0 = FF::random_element();
328 for (size_t i = 0; i < 3; i++) {
329 expected_q1[i] = v000[i] * (FF(1) - round_challenge_0) + v100[i] * round_challenge_0;
330 expected_q2[i] = v010[i] * (FF(1) - round_challenge_0) + v110[i] * round_challenge_0;
331 expected_q3[i] = v001[i] * (FF(1) - round_challenge_0) + v101[i] * round_challenge_0;
332 expected_q4[i] = v011[i] * (FF(1) - round_challenge_0) + v111[i] * round_challenge_0;
333 }
334
335 sumcheck.partially_evaluated_polynomials = typename Flavor::PartiallyEvaluatedMultivariates(multivariate_n);
336 sumcheck.partially_evaluate(full_polynomials, round_challenge_0);
337 auto polynomial_get_all = sumcheck.partially_evaluated_polynomials.get_all();
338 for (size_t i = 0; i < 3; i++) {
339 EXPECT_EQ((polynomial_get_all[i])[0], expected_q1[i]);
340 EXPECT_EQ((polynomial_get_all[i])[1], expected_q2[i]);
341 EXPECT_EQ((polynomial_get_all[i])[2], expected_q3[i]);
342 EXPECT_EQ((polynomial_get_all[i])[3], expected_q4[i]);
343 }
344
345 FF round_challenge_1 = FF::random_element();
346 std::array<FF, 3> expected_lo;
347 std::array<FF, 3> expected_hi;
348 for (size_t i = 0; i < 3; i++) {
349 expected_lo[i] = expected_q1[i] * (FF(1) - round_challenge_1) + expected_q2[i] * round_challenge_1;
350 expected_hi[i] = expected_q3[i] * (FF(1) - round_challenge_1) + expected_q4[i] * round_challenge_1;
351 }
352 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_1);
353 for (size_t i = 0; i < 3; i++) {
354 EXPECT_EQ((polynomial_get_all[i])[0], expected_lo[i]);
355 EXPECT_EQ((polynomial_get_all[i])[1], expected_hi[i]);
356 }
357 FF round_challenge_2 = FF::random_element();
358 std::array<FF, 3> expected_val;
359 for (size_t i = 0; i < 3; i++) {
360 expected_val[i] = expected_lo[i] * (FF(1) - round_challenge_2) + expected_hi[i] * round_challenge_2;
361 }
362 sumcheck.partially_evaluate(sumcheck.partially_evaluated_polynomials, round_challenge_2);
363 for (size_t i = 0; i < 3; i++) {
364 EXPECT_EQ((polynomial_get_all[i])[0], expected_val[i]);
365 }
366}
bb::BaseTranscript
Common transcript class for both parties. Stores the data for the current round, as well as the manif...
Definition transcript.hpp:41
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:438
bb::ECCVMFlavor::PartiallyEvaluatedMultivariates
A container for storing the partially evaluated multivariates produced by sumcheck.
Definition eccvm_flavor.hpp:767
bb::ECCVMFlavor::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:457
bb::ECCVMFlavor::FF
typename Curve::ScalarField FF
Definition eccvm_flavor.hpp:42
bb::ECCVMFlavor::Polynomial
bb::Polynomial< FF > Polynomial
Definition eccvm_flavor.hpp:44
bb::ECCVMFlavor::Transcript
NativeTranscript Transcript
Definition eccvm_flavor.hpp:50
bb::Polynomial
Structured polynomial class that represents the coefficients 'a' of a_0 + a_1 x .....
Definition polynomial.hpp:75
bb::SumcheckProver
The implementation of the sumcheck Prover for statements of the form for multilinear polynomials .
Definition sumcheck.hpp:289
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:353
Flavors
testing::Types< UltraRecursiveFlavor_< UltraCircuitBuilder >, UltraRollupRecursiveFlavor_< UltraCircuitBuilder >, UltraRecursiveFlavor_< MegaCircuitBuilder >, UltraZKRecursiveFlavor_< UltraCircuitBuilder >, UltraZKRecursiveFlavor_< MegaCircuitBuilder > > Flavors
Definition honk_recursion_constraint.test.cpp:166
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::TYPED_TEST_SUITE
TYPED_TEST_SUITE(ShpleminiTest, TestSettings)
bb::TYPED_TEST
TYPED_TEST(ShpleminiTest, CorrectnessOfMultivariateClaimBatching)
Definition shplemini.test.cpp:52
bb::field< bb::Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:675
ultra_flavor.hpp