Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
ultra_circuit_builder_sort_permutation.test.cpp
Go to the documentation of this file.
1#include "barretenberg/circuit_checker/circuit_checker.hpp"
2#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
3
4#include <gtest/gtest.h>
5
6using namespace bb;
7
8namespace bb {
9
10static std::vector<uint32_t> add_variables(UltraCircuitBuilder& builder, const std::vector<fr>& variables)
11{
12 std::vector<uint32_t> res;
13 for (size_t i = 0; i < variables.size(); i++) {
14 res.emplace_back(builder.add_variable(variables[i]));
15 }
16 return res;
17}
18
19TEST(UltraCircuitBuilder, NonTrivialTagPermutation)
20{
21 UltraCircuitBuilder builder;
22 fr a = fr::random_element();
23 fr b = -a;
24
25 auto a_idx = builder.add_variable(a);
26 auto b_idx = builder.add_variable(b);
27 auto c_idx = builder.add_variable(b);
28 auto d_idx = builder.add_variable(a);
29
30 builder.create_add_gate({ a_idx, b_idx, builder.zero_idx(), fr::one(), fr::one(), fr::zero(), fr::zero() });
31 builder.create_add_gate({ c_idx, d_idx, builder.zero_idx(), fr::one(), fr::one(), fr::zero(), fr::zero() });
32
33 auto first_tag = builder.get_new_tag();
34 auto second_tag = builder.get_new_tag();
35 builder.set_tau_transposition(first_tag, second_tag);
36
37 builder.assign_tag(a_idx, first_tag);
38 builder.assign_tag(b_idx, first_tag);
39 builder.assign_tag(c_idx, second_tag);
40 builder.assign_tag(d_idx, second_tag);
41
42 EXPECT_TRUE(CircuitChecker::check(builder));
43
44 // Break the tag
45 builder.real_variable_tags[builder.real_variable_index[a_idx]] = 2;
46 EXPECT_FALSE(CircuitChecker::check(builder));
47}
48
49TEST(UltraCircuitBuilder, NonTrivialTagPermutationAndCycles)
50{
51 UltraCircuitBuilder builder;
52 fr a = fr::random_element();
53 fr c = -a;
54
55 auto a_idx = builder.add_variable(a);
56 auto b_idx = builder.add_variable(a);
57 builder.assert_equal(a_idx, b_idx);
58 auto c_idx = builder.add_variable(c);
59 auto d_idx = builder.add_variable(c);
60 builder.assert_equal(c_idx, d_idx);
61 auto e_idx = builder.add_variable(a);
62 auto f_idx = builder.add_variable(a);
63 builder.assert_equal(e_idx, f_idx);
64 auto g_idx = builder.add_variable(c);
65 auto h_idx = builder.add_variable(c);
66 builder.assert_equal(g_idx, h_idx);
67
68 auto first_tag = builder.get_new_tag();
69 auto second_tag = builder.get_new_tag();
70 builder.set_tau_transposition(first_tag, second_tag);
71
72 builder.assign_tag(a_idx, first_tag);
73 builder.assign_tag(c_idx, first_tag);
74 builder.assign_tag(e_idx, second_tag);
75 builder.assign_tag(g_idx, second_tag);
76
77 builder.create_add_gate({ b_idx, a_idx, builder.zero_idx(), fr::one(), fr::neg_one(), fr::zero(), fr::zero() });
78 builder.create_add_gate({ c_idx, g_idx, builder.zero_idx(), fr::one(), -fr::one(), fr::zero(), fr::zero() });
79 builder.create_add_gate({ e_idx, f_idx, builder.zero_idx(), fr::one(), -fr::one(), fr::zero(), fr::zero() });
80
81 EXPECT_TRUE(CircuitChecker::check(builder));
82
83 // Break the tag
84 builder.real_variable_tags[builder.real_variable_index[a_idx]] = 2;
85 EXPECT_FALSE(CircuitChecker::check(builder));
86}
87
88TEST(UltraCircuitBuilder, BadTagPermutation)
89{
90 UltraCircuitBuilder builder;
91 fr a = fr::random_element();
92 fr b = -a;
93
94 auto a_idx = builder.add_variable(a);
95 auto b_idx = builder.add_variable(b);
96 auto c_idx = builder.add_variable(b);
97 auto d_idx = builder.add_variable(a + 1);
98
99 builder.create_add_gate({ a_idx, b_idx, builder.zero_idx(), 1, 1, 0, 0 });
100 builder.create_add_gate({ c_idx, d_idx, builder.zero_idx(), 1, 1, 0, -1 });
101
102 EXPECT_TRUE(CircuitChecker::check(builder));
103
104 auto first_tag = builder.get_new_tag();
105 auto second_tag = builder.get_new_tag();
106 builder.set_tau_transposition(first_tag, second_tag);
107
108 builder.assign_tag(a_idx, first_tag);
109 builder.assign_tag(b_idx, first_tag);
110 builder.assign_tag(c_idx, second_tag);
111 builder.assign_tag(d_idx, second_tag);
112
113 EXPECT_FALSE(CircuitChecker::check(builder));
114}
115
116TEST(UltraCircuitBuilder, SortWidget)
117{
118 UltraCircuitBuilder builder;
119 fr a = fr::one();
120 fr b = fr(2);
121 fr c = fr(3);
122 fr d = fr(4);
123
124 auto a_idx = builder.add_variable(a);
125 auto b_idx = builder.add_variable(b);
126 auto c_idx = builder.add_variable(c);
127 auto d_idx = builder.add_variable(d);
128 builder.create_sort_constraint({ a_idx, b_idx, c_idx, d_idx });
129
130 EXPECT_TRUE(CircuitChecker::check(builder));
131}
132
133TEST(UltraCircuitBuilder, SortWithEdgesGate)
134{
135 fr a = fr::one();
136 fr b = fr(2);
137 fr c = fr(3);
138 fr d = fr(4);
139 fr e = fr(5);
140 fr f = fr(6);
141 fr g = fr(7);
142 fr h = fr(8);
143
144 {
145 UltraCircuitBuilder builder;
146 auto a_idx = builder.add_variable(a);
147 auto b_idx = builder.add_variable(b);
148 auto c_idx = builder.add_variable(c);
149 auto d_idx = builder.add_variable(d);
150 auto e_idx = builder.add_variable(e);
151 auto f_idx = builder.add_variable(f);
152 auto g_idx = builder.add_variable(g);
153 auto h_idx = builder.add_variable(h);
154 builder.create_sort_constraint_with_edges({ a_idx, b_idx, c_idx, d_idx, e_idx, f_idx, g_idx, h_idx }, a, h);
155 EXPECT_TRUE(CircuitChecker::check(builder));
156 }
157
158 {
159 UltraCircuitBuilder builder;
160 auto a_idx = builder.add_variable(a);
161 auto b_idx = builder.add_variable(b);
162 auto c_idx = builder.add_variable(c);
163 auto d_idx = builder.add_variable(d);
164 auto e_idx = builder.add_variable(e);
165 auto f_idx = builder.add_variable(f);
166 auto g_idx = builder.add_variable(g);
167 auto h_idx = builder.add_variable(h);
168 builder.create_sort_constraint_with_edges({ a_idx, b_idx, c_idx, d_idx, e_idx, f_idx, g_idx, h_idx }, a, g);
169
170 EXPECT_FALSE(CircuitChecker::check(builder));
171 }
172 {
173 UltraCircuitBuilder builder;
174 auto a_idx = builder.add_variable(a);
175 auto b_idx = builder.add_variable(b);
176 auto c_idx = builder.add_variable(c);
177 auto d_idx = builder.add_variable(d);
178 auto e_idx = builder.add_variable(e);
179 auto f_idx = builder.add_variable(f);
180 auto g_idx = builder.add_variable(g);
181 auto h_idx = builder.add_variable(h);
182 builder.create_sort_constraint_with_edges({ a_idx, b_idx, c_idx, d_idx, e_idx, f_idx, g_idx, h_idx }, b, h);
183
184 EXPECT_FALSE(CircuitChecker::check(builder));
185 }
186 {
187 UltraCircuitBuilder builder;
188 auto a_idx = builder.add_variable(a);
189 auto c_idx = builder.add_variable(c);
190 auto d_idx = builder.add_variable(d);
191 auto e_idx = builder.add_variable(e);
192 auto f_idx = builder.add_variable(f);
193 auto g_idx = builder.add_variable(g);
194 auto h_idx = builder.add_variable(h);
195 auto b2_idx = builder.add_variable(fr(15));
196 builder.create_sort_constraint_with_edges({ a_idx, b2_idx, c_idx, d_idx, e_idx, f_idx, g_idx, h_idx }, b, h);
197 EXPECT_FALSE(CircuitChecker::check(builder));
198 }
199 {
200 UltraCircuitBuilder builder;
201 auto idx = add_variables(builder, { 1, 2, 5, 6, 7, 10, 11, 13, 16, 17, 20, 22, 22, 25,
202 26, 29, 29, 32, 32, 33, 35, 38, 39, 39, 42, 42, 43, 45 });
203 builder.create_sort_constraint_with_edges(idx, 1, 45);
204 EXPECT_TRUE(CircuitChecker::check(builder));
205 }
206 {
207 UltraCircuitBuilder builder;
208 auto idx = add_variables(builder, { 1, 2, 5, 6, 7, 10, 11, 13, 16, 17, 20, 22, 22, 25,
209 26, 29, 29, 32, 32, 33, 35, 38, 39, 39, 42, 42, 43, 45 });
210
211 builder.create_sort_constraint_with_edges(idx, 1, 29);
212 EXPECT_FALSE(CircuitChecker::check(builder));
213 }
214}
215
216TEST(UltraCircuitBuilder, SortWidgetComplex)
217{
218 {
219
220 UltraCircuitBuilder builder;
221 std::vector<fr> a = { 1, 3, 4, 7, 7, 8, 11, 14, 15, 15, 18, 19, 21, 21, 24, 25, 26, 27, 30, 32 };
222 std::vector<uint32_t> ind;
223 for (size_t i = 0; i < a.size(); i++)
224 ind.emplace_back(builder.add_variable(a[i]));
225 builder.create_sort_constraint(ind);
226
227 EXPECT_TRUE(CircuitChecker::check(builder));
228 }
229 {
230
231 UltraCircuitBuilder builder;
232 std::vector<fr> a = { 1, 3, 4, 7, 7, 8, 16, 14, 15, 15, 18, 19, 21, 21, 24, 25, 26, 27, 30, 32 };
233 std::vector<uint32_t> ind;
234 for (size_t i = 0; i < a.size(); i++)
235 ind.emplace_back(builder.add_variable(a[i]));
236 builder.create_sort_constraint(ind);
237
238 EXPECT_FALSE(CircuitChecker::check(builder));
239 }
240}
241
242TEST(UltraCircuitBuilder, SortWidgetNeg)
243{
244 UltraCircuitBuilder builder;
245 fr a = fr::one();
246 fr b = fr(2);
247 fr c = fr(3);
248 fr d = fr(8);
249
250 auto a_idx = builder.add_variable(a);
251 auto b_idx = builder.add_variable(b);
252 auto c_idx = builder.add_variable(c);
253 auto d_idx = builder.add_variable(d);
254 builder.create_sort_constraint({ a_idx, b_idx, c_idx, d_idx });
255
256 EXPECT_FALSE(CircuitChecker::check(builder));
257}
258
259} // namespace bb
circuit_checker.hpp
bb::CircuitBuilderBase::add_variable
virtual uint32_t add_variable(const FF &in)
Add a variable to variables.
Definition circuit_builder_base_impl.hpp:53
bb::TranslatorCircuitChecker::check
static bool check(const Builder &circuit)
Check the witness satisifies the circuit.
Definition translator_circuit_checker.cpp:20
bb::UltraCircuitBuilder_
Definition ultra_circuit_builder.hpp:41
builder
AluTraceBuilder builder
Definition alu.test.cpp:124
a
FF a
Definition field_gt.test.cpp:52
b
FF b
Definition field_gt.test.cpp:53
bb
Entry point for Barretenberg command-line interface.
Definition api.hpp:5
bb::fr
field< Bn254FrParams > fr
Definition fr.hpp:174
bb::TEST
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
Definition graph_description_megacircuitbuilder.test.cpp:22
bb::field< Bn254FrParams >::neg_one
static constexpr field neg_one()
Definition field_declarations.hpp:241
bb::field< Bn254FrParams >::one
static constexpr field one()
Definition field_declarations.hpp:242
bb::field< Bn254FrParams >::random_element
static field random_element(numeric::RNG *engine=nullptr) noexcept
Definition field_impl.hpp:675
bb::field< Bn254FrParams >::zero
static constexpr field zero()
Definition field_declarations.hpp:240
ultra_circuit_builder.hpp