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 auto partially_evaluated_polynomials = sumcheck.partially_evaluate_first_round(full_polynomials, round_challenge_0);
77
78 auto& first_polynomial = partially_evaluated_polynomials.get_all()[0];
79 EXPECT_EQ(first_polynomial[0], round_challenge_0);
80 EXPECT_EQ(first_polynomial[1], FF(0));
81
82 FF round_challenge_1 = 2;
83 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
84
85 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_1);
86 EXPECT_EQ(first_polynomial[0], expected_val);
87}
88
89TYPED_TEST(PartialEvaluationTests, TwoRoundsGeneric)
90{
91 using Flavor = TypeParam;
92 using FF = Flavor::FF;
93 using Polynomial = Flavor::Polynomial;
94 using Transcript = Flavor::Transcript;
95
96 static constexpr size_t multivariate_d(2);
97 static constexpr size_t multivariate_n(1 << multivariate_d);
98
99 FF v00 = FF::random_element();
100 FF v10 = FF::random_element();
101 FF v01 = FF::random_element();
102 FF v11 = FF::random_element();
103
104 Polynomial f0(4);
105 f0.template copy_vector<FF>({ v00, v10, v01, v11 });
106
107 auto transcript = Transcript::prover_init_empty();
108 FF alpha = FF(1);
109 typename Flavor::ProverPolynomials full_polynomials;
110 full_polynomials.q_m = f0;
111 std::vector<FF> gate_challenges{ 1, 1 };
112
113 SumcheckProver<Flavor> sumcheck(
114 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
115
116 FF round_challenge_0 = FF::random_element();
117 FF expected_lo = v00 * (FF(1) - round_challenge_0) + v10 * round_challenge_0;
118 FF expected_hi = v01 * (FF(1) - round_challenge_0) + v11 * round_challenge_0;
119
120 auto partially_evaluated_polynomials = sumcheck.partially_evaluate_first_round(full_polynomials, round_challenge_0);
121 auto& first_polynomial = partially_evaluated_polynomials.get_all()[0];
122
123 EXPECT_EQ(first_polynomial[0], expected_lo);
124 EXPECT_EQ(first_polynomial[1], expected_hi);
125
126 FF round_challenge_1 = FF::random_element();
127 FF expected_val = expected_lo * (FF(1) - round_challenge_1) + expected_hi * round_challenge_1;
128 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_1);
129 EXPECT_EQ(first_polynomial[0], expected_val);
130}
131
132/*
133 * Similarly for a trivariate polynomial f0(X0, X1, X2), we have
134 * f0(X0, X1, X2) = v000 * (1-X0) * (1-X1) * (1-X2)
135 * + v100 * X0 * (1-X1) * (1-X2)
136 * + v010 * (1-X0) * X1 * (1-X2)
137 * + v110 * X0 * X1 * (1-X2)
138 * + v001 * (1-X0) * (1-X1) * X2
139 * + v101 * X0 * (1-X1) * X2
140 * + v011 * (1-X0) * X1 * X2
141 * + v111 * X0 * X1 * X2.
142 * After round 0 (round challenge u0), we have
143 * f0(u0, X1, X2) = [v000 * (1-u0) + v100 * u0] * (1-X1) * (1-X2)
144 * + [v010 * (1-u0) + v110 * u0] * X1 * (1-X2)
145 * + [v001 * (1-u0) + v101 * u0] * (1-X1) * X2
146 * + [v011 * (1-u0) + v111 * u0] * X1 * X2.
147 * After round 1 (round challenge u1), we have
148 * f0(u0, u1, X2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-X2)
149 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * X2.
150 * After round 2 (round challenge u2), we have
151 * f0(u0, u1, u2) = [(v000 * (1-u0) + v100 * u0) * (1-u1) + (v010 * (1-u0) + v110 * u0) * u1] * (1-u2)
152 * + [(v001 * (1-u0) + v101 * u0) * (1-u1) + (v011 * (1-u0) + v111 * u0) * u1] * u2.
153 */
154TYPED_TEST(PartialEvaluationTests, ThreeRoundsSpecial)
155{
156 using Flavor = TypeParam;
157 using FF = Flavor::FF;
158 using Polynomial = Flavor::Polynomial;
159 using Transcript = Flavor::Transcript;
160
161 static constexpr size_t multivariate_d(3);
162 static constexpr size_t multivariate_n(1 << multivariate_d);
163
164 FF v000 = 1;
165 FF v100 = 2;
166 FF v010 = 3;
167 FF v110 = 4;
168 FF v001 = 5;
169 FF v101 = 6;
170 FF v011 = 7;
171 FF v111 = 8;
172
173 Polynomial f0(8);
174 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
175
176 typename Flavor::ProverPolynomials full_polynomials;
177 full_polynomials.q_m = f0;
178 auto transcript = Transcript::prover_init_empty();
179 FF alpha = FF(1);
180
181 std::vector<FF> gate_challenges{ 1, 1, 1 };
182
183 SumcheckProver<Flavor> sumcheck(
184 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
185
186 FF round_challenge_0 = 1;
187 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0; // 2
188 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0; // 4
189 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0; // 6
190 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0; // 8
191
192 auto partially_evaluated_polynomials = sumcheck.partially_evaluate_first_round(full_polynomials, round_challenge_0);
193
194 auto& first_polynomial = partially_evaluated_polynomials.get_all()[0];
195 EXPECT_EQ(first_polynomial[0], expected_q1);
196 EXPECT_EQ(first_polynomial[1], expected_q2);
197 EXPECT_EQ(first_polynomial[2], expected_q3);
198 EXPECT_EQ(first_polynomial[3], expected_q4);
199
200 FF round_challenge_1 = 2;
201 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1; // 6
202 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1; // 10
203
204 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_1);
205 EXPECT_EQ(first_polynomial[0], expected_lo);
206 EXPECT_EQ(first_polynomial[1], expected_hi);
207
208 FF round_challenge_2 = 3;
209 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2; // 18
210 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_2);
211 EXPECT_EQ(first_polynomial[0], expected_val);
212}
213
214TYPED_TEST(PartialEvaluationTests, ThreeRoundsGeneric)
215{
216 using Flavor = TypeParam;
217 using FF = Flavor::FF;
218 using Polynomial = Flavor::Polynomial;
219 using Transcript = Flavor::Transcript;
220
221 static constexpr size_t multivariate_d(3);
222 static constexpr size_t multivariate_n(1 << multivariate_d);
223
224 FF v000 = FF::random_element();
225 FF v100 = FF::random_element();
226 FF v010 = FF::random_element();
227 FF v110 = FF::random_element();
228 FF v001 = FF::random_element();
229 FF v101 = FF::random_element();
230 FF v011 = FF::random_element();
231 FF v111 = FF::random_element();
232
233 Polynomial f0(8);
234 f0.template copy_vector<FF>({ v000, v100, v010, v110, v001, v101, v011, v111 });
235
236 typename Flavor::ProverPolynomials full_polynomials;
237 full_polynomials.q_m = f0;
238
239 auto transcript = Transcript::prover_init_empty();
240 FF alpha = FF(1);
241 std::vector<FF> gate_challenges{ 1, 1, 1 };
242
243 SumcheckProver<Flavor> sumcheck(
244 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
245
246 FF round_challenge_0 = FF::random_element();
247 FF expected_q1 = v000 * (FF(1) - round_challenge_0) + v100 * round_challenge_0;
248 FF expected_q2 = v010 * (FF(1) - round_challenge_0) + v110 * round_challenge_0;
249 FF expected_q3 = v001 * (FF(1) - round_challenge_0) + v101 * round_challenge_0;
250 FF expected_q4 = v011 * (FF(1) - round_challenge_0) + v111 * round_challenge_0;
251
252 auto partially_evaluated_polynomials = sumcheck.partially_evaluate_first_round(full_polynomials, round_challenge_0);
253 auto& first_polynomial = partially_evaluated_polynomials.get_all()[0];
254
255 EXPECT_EQ(first_polynomial[0], expected_q1);
256 EXPECT_EQ(first_polynomial[1], expected_q2);
257 EXPECT_EQ(first_polynomial[2], expected_q3);
258 EXPECT_EQ(first_polynomial[3], expected_q4);
259
260 FF round_challenge_1 = FF::random_element();
261 FF expected_lo = expected_q1 * (FF(1) - round_challenge_1) + expected_q2 * round_challenge_1;
262 FF expected_hi = expected_q3 * (FF(1) - round_challenge_1) + expected_q4 * round_challenge_1;
263
264 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_1);
265 EXPECT_EQ(first_polynomial[0], expected_lo);
266 EXPECT_EQ(first_polynomial[1], expected_hi);
267
268 FF round_challenge_2 = FF::random_element();
269 FF expected_val = expected_lo * (FF(1) - round_challenge_2) + expected_hi * round_challenge_2;
270 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_2);
271 EXPECT_EQ(first_polynomial[0], expected_val);
272}
273
274TYPED_TEST(PartialEvaluationTests, ThreeRoundsGenericMultiplePolys)
275{
276 using Flavor = TypeParam;
277 using FF = Flavor::FF;
278 using Polynomial = Flavor::Polynomial;
279 using Transcript = Flavor::Transcript;
280
281 static constexpr size_t multivariate_d(3);
282 static constexpr size_t multivariate_n(1 << multivariate_d);
283 std::array<FF, 3> v000;
284 std::array<FF, 3> v100;
285 std::array<FF, 3> v010;
286 std::array<FF, 3> v110;
287 std::array<FF, 3> v001;
288 std::array<FF, 3> v101;
289 std::array<FF, 3> v011;
290 std::array<FF, 3> v111;
291
292 for (size_t i = 0; i < 3; i++) {
293 v000[i] = FF::random_element();
294 v100[i] = FF::random_element();
295 v010[i] = FF::random_element();
296 v110[i] = FF::random_element();
297 v001[i] = FF::random_element();
298 v101[i] = FF::random_element();
299 v011[i] = FF::random_element();
300 v111[i] = FF::random_element();
301 }
302 Polynomial f0(8), f1(8), f2(8);
303 f0.template copy_vector<FF>({ v000[0], v100[0], v010[0], v110[0], v001[0], v101[0], v011[0], v111[0] });
304 f1.template copy_vector<FF>({ v000[1], v100[1], v010[1], v110[1], v001[1], v101[1], v011[1], v111[1] });
305 f2.template copy_vector<FF>({ v000[2], v100[2], v010[2], v110[2], v001[2], v101[2], v011[2], v111[2] });
306
307 typename Flavor::ProverPolynomials full_polynomials;
308 // Set the first 3 ProverPolynomials
309 full_polynomials.q_m = f0;
310 full_polynomials.q_c = f1;
311 full_polynomials.q_l = f2;
312 auto transcript = Transcript::prover_init_empty();
313 FF alpha = FF(1);
314 std::vector<FF> gate_challenges{ 1, 1, 1 };
315
316 SumcheckProver<Flavor> sumcheck(
317 multivariate_n, full_polynomials, transcript, alpha, gate_challenges, {}, multivariate_d);
318
319 std::array<FF, 3> expected_q1;
320 std::array<FF, 3> expected_q2;
321 std::array<FF, 3> expected_q3;
322 std::array<FF, 3> expected_q4;
323 FF round_challenge_0 = FF::random_element();
324 for (size_t i = 0; i < 3; i++) {
325 expected_q1[i] = v000[i] * (FF(1) - round_challenge_0) + v100[i] * round_challenge_0;
326 expected_q2[i] = v010[i] * (FF(1) - round_challenge_0) + v110[i] * round_challenge_0;
327 expected_q3[i] = v001[i] * (FF(1) - round_challenge_0) + v101[i] * round_challenge_0;
328 expected_q4[i] = v011[i] * (FF(1) - round_challenge_0) + v111[i] * round_challenge_0;
329 }
330
331 auto partially_evaluated_polynomials = sumcheck.partially_evaluate_first_round(full_polynomials, round_challenge_0);
332 auto polynomial_get_all = partially_evaluated_polynomials.get_all();
333 for (size_t i = 0; i < 3; i++) {
334 EXPECT_EQ((polynomial_get_all[i])[0], expected_q1[i]);
335 EXPECT_EQ((polynomial_get_all[i])[1], expected_q2[i]);
336 EXPECT_EQ((polynomial_get_all[i])[2], expected_q3[i]);
337 EXPECT_EQ((polynomial_get_all[i])[3], expected_q4[i]);
338 }
339
340 FF round_challenge_1 = FF::random_element();
341 std::array<FF, 3> expected_lo;
342 std::array<FF, 3> expected_hi;
343 for (size_t i = 0; i < 3; i++) {
344 expected_lo[i] = expected_q1[i] * (FF(1) - round_challenge_1) + expected_q2[i] * round_challenge_1;
345 expected_hi[i] = expected_q3[i] * (FF(1) - round_challenge_1) + expected_q4[i] * round_challenge_1;
346 }
347 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_1);
348 for (size_t i = 0; i < 3; i++) {
349 EXPECT_EQ((polynomial_get_all[i])[0], expected_lo[i]);
350 EXPECT_EQ((polynomial_get_all[i])[1], expected_hi[i]);
351 }
352 FF round_challenge_2 = FF::random_element();
353 std::array<FF, 3> expected_val;
354 for (size_t i = 0; i < 3; i++) {
355 expected_val[i] = expected_lo[i] * (FF(1) - round_challenge_2) + expected_hi[i] * round_challenge_2;
356 }
357 sumcheck.partially_evaluate_in_place(partially_evaluated_polynomials, round_challenge_2);
358 for (size_t i = 0; i < 3; i++) {
359 EXPECT_EQ((polynomial_get_all[i])[0], expected_val[i]);
360 }
361}
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::ProverPolynomials
A container for the prover polynomials.
Definition eccvm_flavor.hpp:459
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
BaseTranscript< Codec, HashFunction > Transcript
Definition eccvm_flavor.hpp:52
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_evaluate_first_round
PartiallyEvaluatedMultivariates partially_evaluate_first_round(ProverPolynomials &full_polynomials, const FF &round_challenge)
Initialize partially evaluated polynomials and perform first round of partial evaluation.
Definition sumcheck.hpp:646
bb::stdlib::recursion::honk::Flavors
testing::Types< UltraRecursiveFlavor_< UltraCircuitBuilder > > Flavors
Definition graph_description_ultra_recursive_verifier.test.cpp:153
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::TYPED_TEST_SUITE
TYPED_TEST_SUITE(CommitmentKeyTest, Curves)
bb::TYPED_TEST
TYPED_TEST(CommitmentKeyTest, CommitToZeroPoly)
Definition commitment_key.test.cpp:133
bb::field< bb::Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:677
ultra_flavor.hpp