Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
translator_circuit_builder.test.cpp
Go to the documentation of this file.
1#include "translator_circuit_builder.hpp"
2#include "barretenberg/circuit_checker/translator_circuit_checker.hpp"
3#include "barretenberg/ecc/curves/bn254/bn254.hpp"
4#include "barretenberg/op_queue/ecc_op_queue.hpp"
5#include <array>
6#include <cstddef>
7#include <gtest/gtest.h>
8
9using namespace bb;
10namespace {
11auto& engine = numeric::get_debug_randomness();
12
16fq compute_expected_result(const std::shared_ptr<ECCOpQueue>& op_queue, const fq& batching_challenge, const fq& x)
17{
18 using Fq = fq;
19 Fq x_inv = x.invert();
20 Fq op_accumulator = Fq(0);
21 Fq p_x_accumulator = Fq(0);
22 Fq p_y_accumulator = Fq(0);
23 Fq z_1_accumulator = Fq(0);
24 Fq z_2_accumulator = Fq(0);
25 Fq x_pow = Fq(1);
26
27 const auto& ultra_ops = op_queue->get_ultra_ops();
28 for (const auto& ultra_op : ultra_ops) {
29 if (ultra_op.op_code.is_random_op || ultra_op.op_code.value() == 0) {
30 continue;
31 }
32 op_accumulator = op_accumulator * x_inv + ultra_op.op_code.value();
33 const auto [x_fq, y_fq] = ultra_op.get_base_point_standard_form();
34 p_x_accumulator = p_x_accumulator * x_inv + x_fq;
35 p_y_accumulator = p_y_accumulator * x_inv + y_fq;
36 z_1_accumulator = z_1_accumulator * x_inv + uint256_t(ultra_op.z_1);
37 z_2_accumulator = z_2_accumulator * x_inv + uint256_t(ultra_op.z_2);
38 x_pow *= x;
39 }
40 x_pow *= x_inv;
41
42 // Compute batched polynomial evaluation using Horner's method
43 Fq total = z_2_accumulator; // z₂
44 total *= batching_challenge; // z₂ * v
45 total += z_1_accumulator; // z₂ * v + z₁
46 total *= batching_challenge; // z₂ * v² + z₁ * v
47 total += p_y_accumulator; // z₂ * v² + z₁ * v + P.y
48 total *= batching_challenge; // z₂ * v³ + z₁ * v² + P.y * v
49 total += p_x_accumulator; // z₂ * v³ + z₁ * v² + P.y * v + P.x
50 total *= batching_challenge; // z₂ * v⁴ + z₁ * v³ + P.y * v² + P.x * v
51 total += op_accumulator; // z₂ * v⁴ + z₁ * v³ + P.y * v² + P.x * v + op
52 total *= x_pow; // x_pow * ( ... )
53 return total;
54}
55} // namespace
56using CircuitChecker = TranslatorCircuitChecker;
57
58// Test that the circuit can handle several accumulations correctly
59TEST(TranslatorCircuitBuilder, SeveralOperationCorrectness)
60{
61 using point = g1::affine_element;
62 using scalar = fr;
63 using Fq = fq;
64
65 auto P1 = point::random_element();
66 auto P2 = point::random_element();
67 auto z = scalar::random_element();
68
69 // Add the same operations to the ECC op queue; the native computation is performed under the hood.
70 auto op_queue = std::make_shared<ECCOpQueue>();
71 op_queue->no_op_ultra_only();
72 op_queue->random_op_ultra_only();
73 op_queue->random_op_ultra_only();
74 op_queue->random_op_ultra_only();
75 op_queue->add_accumulate(P1);
76 op_queue->mul_accumulate(P2, z);
77 op_queue->eq_and_reset();
78 op_queue->merge();
79
80 op_queue->add_accumulate(P1);
81 op_queue->mul_accumulate(P2, z);
82 op_queue->add_accumulate(P1);
83 op_queue->mul_accumulate(P2, z);
84 op_queue->eq_and_reset();
85
86 // Placeholder for randomness
87 op_queue->random_op_ultra_only();
88 op_queue->random_op_ultra_only();
89 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
90
91 Fq batching_challenge = Fq::random_element();
92 Fq x = Fq::random_element();
93
94 // Create circuit builder and feed the queue inside
95 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
96 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
97
98 // Verify the accumulator result is correct
99 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
100 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
101}
102
103// Test with minimal operations (only required no-ops and random ops)
104TEST(TranslatorCircuitBuilder, MinimalOperations)
105{
106 using Fq = fq;
107
108 auto op_queue = std::make_shared<ECCOpQueue>();
109 op_queue->no_op_ultra_only();
110 op_queue->random_op_ultra_only();
111 op_queue->random_op_ultra_only();
112 op_queue->random_op_ultra_only();
113 op_queue->eq_and_reset();
114 op_queue->merge();
115 op_queue->random_op_ultra_only();
116 op_queue->random_op_ultra_only();
117 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
118
119 Fq batching_challenge = Fq::random_element();
120 Fq x = Fq::random_element();
121
122 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
123 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
124}
125
126// Test with only add operations
127TEST(TranslatorCircuitBuilder, OnlyAddOperations)
128{
129 using point = g1::affine_element;
130 using Fq = fq;
131
132 auto P1 = point::random_element();
133 auto P2 = point::random_element();
134
135 auto op_queue = std::make_shared<ECCOpQueue>();
136 op_queue->no_op_ultra_only();
137 op_queue->random_op_ultra_only();
138 op_queue->random_op_ultra_only();
139 op_queue->random_op_ultra_only();
140 op_queue->add_accumulate(P1);
141 op_queue->add_accumulate(P2);
142 op_queue->add_accumulate(P1);
143 op_queue->eq_and_reset();
144 op_queue->merge();
145 op_queue->random_op_ultra_only();
146 op_queue->random_op_ultra_only();
147 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
148
149 Fq batching_challenge = Fq::random_element();
150 Fq x = Fq::random_element();
151
152 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
153 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
154
155 // Verify the accumulator result is correct
156 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
157 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
158}
159
160// Test with only multiplication operations
161TEST(TranslatorCircuitBuilder, OnlyMulOperations)
162{
163 using point = g1::affine_element;
164 using scalar = fr;
165 using Fq = fq;
166
167 auto P = point::random_element();
168 auto z1 = scalar::random_element();
169 auto z2 = scalar::random_element();
170
171 auto op_queue = std::make_shared<ECCOpQueue>();
172 op_queue->no_op_ultra_only();
173 op_queue->random_op_ultra_only();
174 op_queue->random_op_ultra_only();
175 op_queue->random_op_ultra_only();
176 op_queue->mul_accumulate(P, z1);
177 op_queue->mul_accumulate(P, z2);
178 op_queue->eq_and_reset();
179 op_queue->merge();
180 op_queue->random_op_ultra_only();
181 op_queue->random_op_ultra_only();
182 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
183
184 Fq batching_challenge = Fq::random_element();
185 Fq x = Fq::random_element();
186
187 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
188 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
189
190 // Verify the accumulator result is correct
191 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
192 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
193}
194
195// Test with multiple no-ops interspersed with real operations
196TEST(TranslatorCircuitBuilder, InterspersedNoOps)
197{
198 using point = g1::affine_element;
199 using Fq = fq;
200
201 auto P = point::random_element();
202
203 auto op_queue = std::make_shared<ECCOpQueue>();
204 op_queue->no_op_ultra_only();
205 op_queue->random_op_ultra_only();
206 op_queue->random_op_ultra_only();
207 op_queue->random_op_ultra_only();
208 op_queue->add_accumulate(P);
209 op_queue->no_op_ultra_only();
210 op_queue->no_op_ultra_only();
211 op_queue->add_accumulate(P);
212 op_queue->no_op_ultra_only();
213 op_queue->eq_and_reset();
214 op_queue->merge();
215 op_queue->random_op_ultra_only();
216 op_queue->random_op_ultra_only();
217 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
218
219 Fq batching_challenge = Fq::random_element();
220 Fq x = Fq::random_element();
221
222 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
223 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
224
225 // Verify the accumulator result is correct
226 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
227 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
228}
229
230// Test with point at infinity
231TEST(TranslatorCircuitBuilder, PointAtInfinity)
232{
233 using point = g1::affine_element;
234 using Fq = fq;
235
236 auto P_infinity = point::infinity();
237
238 auto op_queue = std::make_shared<ECCOpQueue>();
239 op_queue->no_op_ultra_only();
240 op_queue->random_op_ultra_only();
241 op_queue->random_op_ultra_only();
242 op_queue->random_op_ultra_only();
243 op_queue->add_accumulate(P_infinity);
244 op_queue->eq_and_reset();
245 op_queue->merge();
246 op_queue->random_op_ultra_only();
247 op_queue->random_op_ultra_only();
248 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
249
250 Fq batching_challenge = Fq::random_element();
251 Fq x = Fq::random_element();
252
253 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
254 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
255
256 // Verify the accumulator result is correct (point at infinity should contribute P.x=0, P.y=0)
257 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
258 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
259}
260
261// Test with scalar = 0
262TEST(TranslatorCircuitBuilder, ZeroScalar)
263{
264 using point = g1::affine_element;
265 using scalar = fr;
266 using Fq = fq;
267
268 auto P = point::random_element();
269 auto zero = scalar::zero();
270
271 auto op_queue = std::make_shared<ECCOpQueue>();
272 op_queue->no_op_ultra_only();
273 op_queue->random_op_ultra_only();
274 op_queue->random_op_ultra_only();
275 op_queue->random_op_ultra_only();
276 op_queue->mul_accumulate(P, zero);
277 op_queue->eq_and_reset();
278 op_queue->merge();
279 op_queue->random_op_ultra_only();
280 op_queue->random_op_ultra_only();
281 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
282
283 Fq batching_challenge = Fq::random_element();
284 Fq x = Fq::random_element();
285
286 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
287 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
288
289 // Verify the accumulator result is correct (z=0 should result in P.x*0, P.y*0)
290 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
291 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
292}
293
294// Test with many operations to stress test the circuit
295TEST(TranslatorCircuitBuilder, ManyOperations)
296{
297 using point = g1::affine_element;
298 using scalar = fr;
299 using Fq = fq;
300
301 auto op_queue = std::make_shared<ECCOpQueue>();
302 op_queue->no_op_ultra_only();
303 op_queue->random_op_ultra_only();
304 op_queue->random_op_ultra_only();
305 op_queue->random_op_ultra_only();
306
307 // Add many operations
308 for (size_t i = 0; i < 20; ++i) {
309 auto P = point::random_element();
310 auto z = scalar::random_element();
311 op_queue->add_accumulate(P);
312 op_queue->mul_accumulate(P, z);
313 }
314
315 op_queue->eq_and_reset();
316 op_queue->merge();
317 op_queue->random_op_ultra_only();
318 op_queue->random_op_ultra_only();
319 op_queue->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue->get_current_subtable_size());
320
321 Fq batching_challenge = Fq::random_element();
322 Fq x = Fq::random_element();
323
324 auto circuit_builder = TranslatorCircuitBuilder(batching_challenge, x, op_queue);
325 EXPECT_TRUE(CircuitChecker::check(circuit_builder));
326
327 // Verify the accumulator result is correct (stress test with many operations)
328 Fq expected_result = compute_expected_result(op_queue, batching_challenge, x);
329 EXPECT_EQ(expected_result, CircuitChecker::get_computation_result(circuit_builder));
330}
331
332// Test determinism - same inputs should produce same circuit and same result
333TEST(TranslatorCircuitBuilder, Determinism)
334{
335 using point = g1::affine_element;
336 using scalar = fr;
337 using Fq = fq;
338
339 auto P = point::random_element();
340 auto z = scalar::random_element();
341 Fq batching_challenge = Fq::random_element();
342 Fq x = Fq::random_element();
343
344 // Build first circuit
345 auto op_queue1 = std::make_shared<ECCOpQueue>();
346 op_queue1->no_op_ultra_only();
347 op_queue1->random_op_ultra_only();
348 op_queue1->random_op_ultra_only();
349 op_queue1->random_op_ultra_only();
350 op_queue1->add_accumulate(P);
351 op_queue1->mul_accumulate(P, z);
352 op_queue1->eq_and_reset();
353 op_queue1->merge();
354 op_queue1->random_op_ultra_only();
355 op_queue1->random_op_ultra_only();
356 op_queue1->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue1->get_current_subtable_size());
357
358 auto circuit_builder1 = TranslatorCircuitBuilder(batching_challenge, x, op_queue1);
359 auto result1 = CircuitChecker::get_computation_result(circuit_builder1);
360
361 // Build second circuit with same operations
362 auto op_queue2 = std::make_shared<ECCOpQueue>();
363 op_queue2->no_op_ultra_only();
364 op_queue2->random_op_ultra_only();
365 op_queue2->random_op_ultra_only();
366 op_queue2->random_op_ultra_only();
367 op_queue2->add_accumulate(P);
368 op_queue2->mul_accumulate(P, z);
369 op_queue2->eq_and_reset();
370 op_queue2->merge();
371 op_queue2->random_op_ultra_only();
372 op_queue2->random_op_ultra_only();
373 op_queue2->merge(MergeSettings::APPEND, ECCOpQueue::OP_QUEUE_SIZE - op_queue2->get_current_subtable_size());
374
375 auto circuit_builder2 = TranslatorCircuitBuilder(batching_challenge, x, op_queue2);
376 auto result2 = CircuitChecker::get_computation_result(circuit_builder2);
377
378 EXPECT_EQ(result1, result2);
379}
bb::CircuitChecker
The unified interface for check circuit functionality implemented in the specialized CircuitChecker c...
Definition circuit_checker.hpp:12
bb::ECCOpQueue::OP_QUEUE_SIZE
static const size_t OP_QUEUE_SIZE
Definition ecc_op_queue.hpp:64
bb::TranslatorCircuitBuilder
TranslatorCircuitBuilder creates a circuit that evaluates the correctness of the evaluation of EccOpQ...
Definition translator_circuit_builder.hpp:69
bb::TranslatorCircuitChecker::get_computation_result
static Fq get_computation_result(const Builder &circuit)
Get the result of accumulation, stored as 4 binary limbs in the first row of the circuit.
Definition translator_circuit_checker.hpp:29
bb::TranslatorCircuitChecker::check
static bool check(const Builder &circuit)
Check the witness satisifies the circuit.
Definition translator_circuit_checker.cpp:20
bb::group::affine_element
group_elements::affine_element< Fq, Fr, Params > affine_element
Definition group.hpp:42
bb::numeric::uint256_t
Definition uint256.hpp:32
expected_result
bool expected_result
Definition field_gt.test.cpp:54
ecc_op_queue.hpp
engine
numeric::RNG & engine
Definition eccvm_transcript.test.cpp:285
bb::numeric::get_debug_randomness
RNG & get_debug_randomness(bool reset, std::uint_fast64_t seed)
Definition engine.cpp:217
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::fq
field< Bn254FqParams > fq
Definition fq.hpp:153
bb::fr
field< Bn254FrParams > fr
Definition fr.hpp:155
bb::TEST
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
Definition graph_description_megacircuitbuilder.test.cpp:22
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
bb::field::invert
constexpr field invert() const noexcept
Definition field_impl.hpp:397
bb::field< Bn254FqParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:783
Fq
curve::BN254::BaseField Fq
Definition translator.fuzzer.hpp:21
translator_circuit_builder.hpp
translator_circuit_checker.hpp