Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
logderiv_lookup_relation.test.cpp
Go to the documentation of this file.
1
17#include "barretenberg/relations/logderiv_lookup_relation.hpp"
18#include "barretenberg/ecc/curves/bn254/fr.hpp"
19#include "barretenberg/flavor/generated/ultra_flavor_generated.hpp"
20#include "barretenberg/relations/relation_parameters.hpp"
21#include <array>
22#include <gtest/gtest.h>
23
24using namespace bb;
25
26using FF = fr;
27using Inputs = UltraFlavor_Generated::AllEntities<FF>;
28using EntityId = Inputs::EntityId;
29using LookupRelation = LogDerivLookupRelationImpl<FF>;
30
31static constexpr size_t NUM_SUBRELATIONS = 3;
32using SubrelationAccumulator = std::array<FF, NUM_SUBRELATIONS>;
33
35static FF compute_L(const Inputs& in, const RelationParameters<FF>& params)
36{
37 const auto& beta = params.beta;
38 const auto& beta_sqr = params.beta_sqr;
39 const auto& beta_cube = params.beta_cube;
40 const auto& gamma = params.gamma;
41 const auto derived_1 = in[EntityId::w_l] + gamma + in[EntityId::q_r] * in[EntityId::w_l_shift];
42 const auto derived_2 = in[EntityId::w_r] + in[EntityId::q_m] * in[EntityId::w_r_shift];
43 const auto derived_3 = in[EntityId::w_o] + in[EntityId::q_c] * in[EntityId::w_o_shift];
44 return derived_1 + derived_2 * beta + derived_3 * beta_sqr + in[EntityId::q_o] * beta_cube;
45}
46
48static FF compute_T(const Inputs& in, const RelationParameters<FF>& params)
49{
50 const auto& beta = params.beta;
51 const auto& beta_sqr = params.beta_sqr;
52 const auto& beta_cube = params.beta_cube;
53 const auto& gamma = params.gamma;
54 return in[EntityId::table_1] + gamma + in[EntityId::table_2] * beta + in[EntityId::table_3] * beta_sqr +
55 in[EntityId::table_4] * beta_cube;
56}
57
59static FF compute_inverse_exists(const Inputs& in)
60{
61 const FF q_lookup = in[EntityId::q_lookup];
62 const FF read_tag = in[EntityId::lookup_read_tags];
63 return q_lookup + read_tag - q_lookup * read_tag;
64}
65
67static SubrelationAccumulator compute_expected_values(const Inputs& in,
68 const RelationParameters<FF>& params,
69 const FF& scaling_factor)
70{
71 const FF L = compute_L(in, params);
72 const FF T = compute_T(in, params);
73 const FF I = in[EntityId::lookup_inverses];
74 const FF q_lookup = in[EntityId::q_lookup];
75 const FF read_counts = in[EntityId::lookup_read_counts];
76 const FF read_tag = in[EntityId::lookup_read_tags];
77 const FF inverse_exists = compute_inverse_exists(in);
78 return {
79 (L * T * I - inverse_exists) * scaling_factor, // (1) inverse correctness
80 (q_lookup * T - read_counts * L) * I, // (2) lookup identity (no scaling)
81 (read_tag * read_tag - read_tag) * scaling_factor // (3) read_tag boolean check
82 };
83}
84
86static SubrelationAccumulator eval_row(const Inputs& in,
87 const RelationParameters<FF>& params,
88 const FF& scaling_factor = FF(1))
89{
90 SubrelationAccumulator acc{};
91 LookupRelation::accumulate(acc, in, params, scaling_factor);
92 return acc;
93}
94
100static Inputs make_valid_lookup_row(const RelationParameters<FF>& params,
101 FF entry_1 = FF(1),
102 FF entry_2 = FF(2),
103 FF entry_3 = FF(3),
104 FF table_idx = FF(1))
105{
106 Inputs in{};
107 in[EntityId::q_lookup] = FF(1);
108 // Trivial step sizes so derived_table_entry_i == w_i.
109 in[EntityId::q_r] = FF(0);
110 in[EntityId::q_m] = FF(0);
111 in[EntityId::q_c] = FF(0);
112 in[EntityId::w_l] = entry_1;
113 in[EntityId::w_r] = entry_2;
114 in[EntityId::w_o] = entry_3;
115 in[EntityId::q_o] = table_idx;
116 // Matching table side.
117 in[EntityId::table_1] = entry_1;
118 in[EntityId::table_2] = entry_2;
119 in[EntityId::table_3] = entry_3;
120 in[EntityId::table_4] = table_idx;
121 in[EntityId::lookup_read_counts] = FF(1);
122 in[EntityId::lookup_read_tags] = FF(1); // table-side: this row has been read
123 const FF L = compute_L(in, params);
124 const FF T = compute_T(in, params);
125 in[EntityId::lookup_inverses] = (L * T).invert();
126 return in;
127}
128
130static Inputs make_random_row()
131{
132 Inputs in{};
133 for (auto id : { EntityId::w_l,
134 EntityId::w_r,
135 EntityId::w_o,
136 EntityId::w_l_shift,
137 EntityId::w_r_shift,
138 EntityId::w_o_shift,
139 EntityId::q_lookup,
140 EntityId::q_o,
141 EntityId::q_r,
142 EntityId::q_m,
143 EntityId::q_c,
144 EntityId::table_1,
145 EntityId::table_2,
146 EntityId::table_3,
147 EntityId::table_4,
148 EntityId::lookup_inverses,
149 EntityId::lookup_read_counts,
150 EntityId::lookup_read_tags }) {
151 in[id] = FF::random_element();
152 }
153 return in;
154}
155
156class LogDerivLookupRelationConsistency : public testing::Test {};
157
159TEST_F(LogDerivLookupRelationConsistency, RandomInputsMatchReference)
160{
161 const auto params = RelationParameters<FF>::get_random();
162 for (FF scaling_factor : { FF(1), FF::random_element() }) {
163 for (auto in : { make_random_row(), make_valid_lookup_row(params) }) {
164 SubrelationAccumulator actual{};
165 LookupRelation::accumulate(actual, in, params, scaling_factor);
166 EXPECT_EQ(actual, compute_expected_values(in, params, scaling_factor));
167 }
168 }
169}
170
172TEST_F(LogDerivLookupRelationConsistency, InactiveRow)
173{
174 const auto params = RelationParameters<FF>::get_random();
175 Inputs in{};
176 const auto acc = eval_row(in, params);
177 for (size_t i = 0; i < NUM_SUBRELATIONS; ++i) {
178 EXPECT_EQ(acc[i], FF(0)) << "Subrelation " << i << " should be zero on inactive row";
179 }
180}
181
183TEST_F(LogDerivLookupRelationConsistency, ValidLookupRow)
184{
185 const auto params = RelationParameters<FF>::get_random();
186 auto in = make_valid_lookup_row(params, /*entry_1=*/FF(7), /*entry_2=*/FF(11), /*entry_3=*/FF(13));
187 const auto acc = eval_row(in, params);
188 EXPECT_EQ(acc[0], FF(0)); // inverse correctness: I·L·T − 1 = 0
189 EXPECT_EQ(acc[1], FF(0)); // lookup identity: (T − L)·I = 0 since L == T at this row
190 EXPECT_EQ(acc[2], FF(0)); // boolean check: read_tag = 1 satisfies 1² − 1 = 0
191}
192
196TEST_F(LogDerivLookupRelationConsistency, ValidWriteRow)
197{
198 const auto params = RelationParameters<FF>::get_random();
199 Inputs in{};
200 in[EntityId::table_1] = FF(7);
201 in[EntityId::table_2] = FF(11);
202 in[EntityId::table_3] = FF(13);
203 in[EntityId::table_4] = FF(1);
204 in[EntityId::lookup_read_counts] = FF(3);
205 in[EntityId::lookup_read_tags] = FF(1);
206 const FF L = compute_L(in, params);
207 const FF T = compute_T(in, params);
208 in[EntityId::lookup_inverses] = (L * T).invert();
209 const auto acc = eval_row(in, params);
210 EXPECT_EQ(acc[0], FF(0)); // inverse correctness: I·L·T − 1 = 0 (inverse_exists = read_tag = 1)
211 EXPECT_EQ(acc[1], (FF(0) * T - FF(3) * L) * in[EntityId::lookup_inverses]);
212 EXPECT_NE(acc[1], FF(0));
213 EXPECT_EQ(acc[2], FF(0)); // boolean check
214}
215
217TEST_F(LogDerivLookupRelationConsistency, ValidTraceSumsToZero)
218{
219 const auto params = RelationParameters<FF>::get_random();
220
221 // Row A: lookup gate reading (7, 11, 13) from table index 1. No table data lives here.
222 auto row_a = make_valid_lookup_row(params, FF(7), FF(11), FF(13), FF(1));
223 row_a[EntityId::table_1] = FF(0);
224 row_a[EntityId::table_2] = FF(0);
225 row_a[EntityId::table_3] = FF(0);
226 row_a[EntityId::table_4] = FF(0);
227 row_a[EntityId::lookup_read_counts] = FF(0);
228 row_a[EntityId::lookup_read_tags] = FF(0); // read row, not a table row — inverse_exists = q_lookup = 1
229 {
230 const FF L = compute_L(row_a, params);
231 const FF T = compute_T(row_a, params);
232 row_a[EntityId::lookup_inverses] = (L * T).invert();
233 }
234
235 // Row B: the table entry, with read_count = 1, no lookup gate.
236 Inputs row_b{};
237 row_b[EntityId::table_1] = FF(7);
238 row_b[EntityId::table_2] = FF(11);
239 row_b[EntityId::table_3] = FF(13);
240 row_b[EntityId::table_4] = FF(1);
241 row_b[EntityId::lookup_read_counts] = FF(1);
242 row_b[EntityId::lookup_read_tags] = FF(1);
243 const FF L_b = compute_L(row_b, params);
244 const FF T_b = compute_T(row_b, params);
245 row_b[EntityId::lookup_inverses] = (L_b * T_b).invert();
246
247 SubrelationAccumulator acc{};
248 LookupRelation::accumulate(acc, row_a, params, FF(1));
249 LookupRelation::accumulate(acc, row_b, params, FF(1));
250 EXPECT_EQ(acc[0], FF(0)); // inverse correctness on both rows
251 EXPECT_EQ(acc[1], FF(0)); // (1/L_a) − (1/T_b), and L_a == T_b → cancels
252 EXPECT_EQ(acc[2], FF(0));
253}
254
256TEST_F(LogDerivLookupRelationConsistency, WrongInverseFires)
257{
258 const auto params = RelationParameters<FF>::get_random();
259 auto in = make_valid_lookup_row(params);
260 in[EntityId::lookup_inverses] = FF(42); // deliberately wrong
261
262 const FF L = compute_L(in, params);
263 const FF T = compute_T(in, params);
264 const FF inverse_exists = compute_inverse_exists(in); // = 1 since q_lookup = read_tag = 1
265 const auto acc = eval_row(in, params);
266 EXPECT_EQ(acc[0], (L * T * FF(42) - inverse_exists) * FF(1));
267 EXPECT_NE(acc[0], FF(0));
268}
269
274TEST_F(LogDerivLookupRelationConsistency, InverseMustBeZeroOnInactiveRows)
275{
276 const auto params = RelationParameters<FF>::get_random();
277 Inputs in{};
278 in[EntityId::w_l] = FF(7);
279 in[EntityId::w_r] = FF(11);
280 in[EntityId::w_o] = FF(13);
281 in[EntityId::table_1] = FF(17);
282 in[EntityId::table_2] = FF(19);
283 in[EntityId::table_3] = FF(23);
284 in[EntityId::table_4] = FF(29);
285 // q_lookup = read_tag = read_counts = 0 by default → inverse_exists = 0.
286
287 // With I = 0 the inactive row satisfies all three subrelations.
288 in[EntityId::lookup_inverses] = FF(0);
289 {
290 const auto acc = eval_row(in, params);
291 for (size_t i = 0; i < NUM_SUBRELATIONS; ++i) {
292 EXPECT_EQ(acc[i], FF(0)) << "Subrelation " << i << " should vanish on inactive row when I = 0";
293 }
294 }
295
296 // With I ≠ 0 the inverse subrelation fires: L·T·I − 0 = L·T·I ≠ 0.
297 in[EntityId::lookup_inverses] = FF(123);
298 {
299 const FF L = compute_L(in, params);
300 const FF T = compute_T(in, params);
301 const auto acc = eval_row(in, params);
302 EXPECT_EQ(acc[0], L * T * FF(123));
303 EXPECT_NE(acc[0], FF(0));
304 }
305}
306
309TEST_F(LogDerivLookupRelationConsistency, WrongReadCount)
310{
311 const auto params = RelationParameters<FF>::get_random();
312
313 // Read row: one lookup of (7, 11, 13).
314 auto row_a = make_valid_lookup_row(params, FF(7), FF(11), FF(13), FF(1));
315 row_a[EntityId::table_1] = FF(0);
316 row_a[EntityId::table_2] = FF(0);
317 row_a[EntityId::table_3] = FF(0);
318 row_a[EntityId::table_4] = FF(0);
319 row_a[EntityId::lookup_read_counts] = FF(0);
320 row_a[EntityId::lookup_read_tags] = FF(0);
321 {
322 const FF L = compute_L(row_a, params);
323 const FF T = compute_T(row_a, params);
324 row_a[EntityId::lookup_inverses] = (L * T).invert();
325 }
326
327 // Write row: table entry; lie about read_count.
328 Inputs row_b{};
329 row_b[EntityId::table_1] = FF(7);
330 row_b[EntityId::table_2] = FF(11);
331 row_b[EntityId::table_3] = FF(13);
332 row_b[EntityId::table_4] = FF(1);
333 row_b[EntityId::lookup_read_counts] = FF(2); // truth would be 1
334 row_b[EntityId::lookup_read_tags] = FF(1);
335 const FF L_b = compute_L(row_b, params);
336 const FF T_b = compute_T(row_b, params);
337 row_b[EntityId::lookup_inverses] = (L_b * T_b).invert();
338
339 SubrelationAccumulator acc{};
340 LookupRelation::accumulate(acc, row_a, params, FF(1));
341 LookupRelation::accumulate(acc, row_b, params, FF(1));
342 EXPECT_EQ(acc[0], FF(0));
343 EXPECT_NE(acc[1], FF(0)); // 1/L_a − 2/T_b ≠ 0
344 EXPECT_EQ(acc[2], FF(0));
345}
346
348TEST_F(LogDerivLookupRelationConsistency, NonBooleanReadTagFiresBooleanCheck)
349{
350 const auto params = RelationParameters<FF>::get_random();
351 Inputs in{};
352 in[EntityId::lookup_read_tags] = FF(5); // not in {0, 1}
353 const auto acc = eval_row(in, params);
354 EXPECT_EQ(acc[2], FF(5) * FF(5) - FF(5));
355 EXPECT_NE(acc[2], FF(0));
356}
357
359TEST_F(LogDerivLookupRelationConsistency, SkipBehavior)
360{
361 Inputs in{};
362 EXPECT_TRUE(LookupRelation::skip(in));
363
364 in[EntityId::q_lookup] = FF(1);
365 EXPECT_FALSE(LookupRelation::skip(in));
366
367 in[EntityId::q_lookup] = FF(0);
368 in[EntityId::lookup_read_counts] = FF(3);
369 EXPECT_FALSE(LookupRelation::skip(in));
370}
371
376TEST_F(LogDerivLookupRelationConsistency, ZeroTableIndex)
377{
378 const auto params = RelationParameters<FF>::get_random();
379
380 // Construct a pure lookup row
381 auto lookup_row = make_valid_lookup_row(params, FF(0), FF(0), FF(0), FF(1));
382 lookup_row[EntityId::lookup_read_counts] = FF(0);
383 lookup_row[EntityId::lookup_read_tags] = FF(0);
384 const FF L = compute_L(lookup_row, params);
385 const FF T = compute_T(lookup_row, params);
386 lookup_row[EntityId::lookup_inverses] = (L * T).invert();
387
388 const auto acc = eval_row(lookup_row, params);
389 EXPECT_EQ(acc[0], 0);
390 EXPECT_EQ(acc[1], (params.gamma + params.beta_cube).invert()); // since L = gamma + beta^3 and T = gamma + beta^3
391 EXPECT_EQ(acc[2], 0);
392}
bb::LogDerivLookupRelationImpl
Log-derivative lookup argument relation for establishing lookup reads from tables with 3 or fewer col...
Definition logderiv_lookup_relation.hpp:100
bb::LogDerivLookupRelationImpl::accumulate
static void accumulate(ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
Accumulate the subrelation contributions for reads from a lookup table.
Definition logderiv_lookup_relation.hpp:320
bb::LogDerivLookupRelationImpl::skip
static bool skip(const AllEntities &in)
Definition logderiv_lookup_relation.hpp:122
bb::MegaFlavor_Generated::EntityId
EntityId
Definition mega_flavor_generated.hpp:40
bb::UltraFlavor_Generated::AllEntities
Definition ultra_flavor_generated.hpp:162
bb::UltraFlavor_Generated::AllEntities::EntityId
UltraFlavor_Generated::EntityId EntityId
Definition ultra_flavor_generated.hpp:164
logderiv_lookup_relation.hpp
SubrelationAccumulator
std::array< FF, NUM_SUBRELATIONS > SubrelationAccumulator
Definition logderiv_lookup_relation.test.cpp:32
FF
fr FF
Definition logderiv_lookup_relation.test.cpp:26
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::TEST_F
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:160
bb::fr
field< Bn254FrParams > fr
Definition fr.hpp:155
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
relation_parameters.hpp
bb::RelationParameters
Container for parameters used by the grand product (permutation, lookup) Honk relations.
Definition relation_parameters.hpp:19
bb::RelationParameters::get_random
static RelationParameters get_random()
Definition relation_parameters.hpp:128
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:802
ultra_flavor_generated.hpp