Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
acir_graph.cpp
Go to the documentation of this file.
1
5#include "acir_graph.hpp"
6#include "barretenberg/dsl/acir_format/acir_to_constraint_buf.hpp"
7#include <stack>
8#include <unordered_map>
9#include <variant>
10
11namespace acir_components_check {
12
13namespace {
14template <class... Ts> struct overloaded : Ts... {
15 using Ts::operator()...;
16};
17
18void collect_expression_witnesses(std::vector<uint32_t>& witnesses, const Acir::Expression& expression)
19{
20 for (const auto& [_, lhs, rhs] : expression.mul_terms) {
21 witnesses.push_back(lhs.value);
22 witnesses.push_back(rhs.value);
23 }
24 for (const auto& [_, witness] : expression.linear_combinations) {
25 witnesses.push_back(witness.value);
26 }
27}
28
29void collect_function_input_witness(std::vector<uint32_t>& witnesses, const Acir::FunctionInput& input)
30{
31 if (std::holds_alternative<Acir::FunctionInput::Witness>(input.value)) {
32 witnesses.push_back(std::get<Acir::FunctionInput::Witness>(input.value).value.value);
33 }
34}
35
36template <typename Container> void collect_function_inputs(std::vector<uint32_t>& witnesses, const Container& inputs)
37{
38 for (const auto& input : inputs) {
39 collect_function_input_witness(witnesses, input);
40 }
41}
42
43template <typename Container> void collect_witnesses(std::vector<uint32_t>& witnesses, const Container& outputs)
44{
45 for (const auto& output : outputs) {
46 witnesses.push_back(output.value);
47 }
48}
49
52bool is_disabled_recursive_aggregation(const Acir::BlackBoxFuncCall::RecursiveAggregation& recursion)
53{
54 auto predicate = acir_format::parse_input(recursion.predicate);
55 return predicate.is_constant && predicate.value.is_zero();
56}
57} // namespace
58
59void AcirGraph::add_constraint(const std::vector<uint32_t>& witnesses)
60{
61 if (witnesses.empty()) {
62 return;
63 }
64
65 std::unordered_set<uint32_t> unique_witnesses(witnesses.begin(), witnesses.end());
66 std::vector<uint32_t> ids(unique_witnesses.begin(), unique_witnesses.end());
67
68 for (auto witness : ids) {
69 adjacency_lists_[witness];
70 }
71
72 for (size_t i = 0; i < ids.size(); i++) {
73 for (size_t j = i + 1; j < ids.size(); j++) {
74 adjacency_lists_[ids[i]].insert(ids[j]);
75 adjacency_lists_[ids[j]].insert(ids[i]);
76 }
77 }
78}
79
80std::vector<std::vector<uint32_t>> AcirGraph::find_components() const
81{
82 std::vector<std::vector<uint32_t>> result;
83 std::unordered_set<uint32_t> visited;
84
85 for (const auto& [vertex, _] : adjacency_lists_) {
86 if (visited.contains(vertex)) {
87 continue;
88 }
89 std::vector<uint32_t> component;
90 std::stack<uint32_t> stack;
91 stack.push(vertex);
92 visited.insert(vertex);
93 while (!stack.empty()) {
94 auto current = stack.top();
95 stack.pop();
96 component.push_back(current);
97 auto it = adjacency_lists_.find(current);
98 if (it != adjacency_lists_.end()) {
99 for (auto neighbor : it->second) {
100 if (!visited.contains(neighbor)) {
101 visited.insert(neighbor);
102 stack.push(neighbor);
103 }
104 }
105 }
106 }
107 result.push_back(std::move(component));
108 }
109 return result;
110}
111
112std::unordered_map<uint32_t, size_t> AcirGraph::get_witness_component_map() const
113{
114 auto components = find_components();
115 std::unordered_map<uint32_t, size_t> witness_to_component;
116 for (size_t comp_id = 0; comp_id < components.size(); comp_id++) {
117 for (auto vertex : components[comp_id]) {
118 witness_to_component[vertex] = comp_id;
119 }
120 }
121 return witness_to_component;
122}
123
124void AcirGraph::process_acir_circuit(const Acir::Circuit& circuit)
125{
126 std::unordered_map<uint32_t, std::vector<uint32_t>> block_witnesses;
127
128 for (const auto& opcode : circuit.opcodes) {
129 std::visit(overloaded{ [&](const Acir::Opcode::AssertZero& assert_zero) {
130 std::vector<uint32_t> witnesses;
131 collect_expression_witnesses(witnesses, assert_zero.value);
132 add_constraint(witnesses);
133 },
134 [&](const Acir::Opcode::BlackBoxFuncCall& black_box) {
135 std::visit(overloaded{
136 [&](const Acir::BlackBoxFuncCall::AND& call) {
137 std::vector<uint32_t> witnesses;
138 collect_function_input_witness(witnesses, call.lhs);
139 collect_function_input_witness(witnesses, call.rhs);
140 witnesses.push_back(call.output.value);
141 add_constraint(witnesses);
142 },
143 [&](const Acir::BlackBoxFuncCall::XOR& call) {
144 std::vector<uint32_t> witnesses;
145 collect_function_input_witness(witnesses, call.lhs);
146 collect_function_input_witness(witnesses, call.rhs);
147 witnesses.push_back(call.output.value);
148 add_constraint(witnesses);
149 },
150 [&](const Acir::BlackBoxFuncCall::RANGE& call) {
151 std::vector<uint32_t> witnesses;
152 collect_function_input_witness(witnesses, call.input);
153 add_constraint(witnesses);
154 },
155 [&](const Acir::BlackBoxFuncCall::AES128Encrypt& call) {
156 std::vector<uint32_t> witnesses;
157 collect_function_inputs(witnesses, call.inputs);
158 collect_function_inputs(witnesses, *call.iv);
159 collect_function_inputs(witnesses, *call.key);
160 collect_witnesses(witnesses, call.outputs);
161 add_constraint(witnesses);
162 },
163 [&](const Acir::BlackBoxFuncCall::Sha256Compression& call) {
164 std::vector<uint32_t> witnesses;
165 collect_function_inputs(witnesses, *call.inputs);
166 collect_function_inputs(witnesses, *call.hash_values);
167 collect_witnesses(witnesses, *call.outputs);
168 add_constraint(witnesses);
169 },
170 [&](const Acir::BlackBoxFuncCall::Blake2s& call) {
171 std::vector<uint32_t> witnesses;
172 collect_function_inputs(witnesses, call.inputs);
173 collect_witnesses(witnesses, *call.outputs);
174 add_constraint(witnesses);
175 },
176 [&](const Acir::BlackBoxFuncCall::Blake3& call) {
177 std::vector<uint32_t> witnesses;
178 collect_function_inputs(witnesses, call.inputs);
179 collect_witnesses(witnesses, *call.outputs);
180 add_constraint(witnesses);
181 },
182 [&](const Acir::BlackBoxFuncCall::EcdsaSecp256k1& call) {
183 std::vector<uint32_t> witnesses;
184 collect_function_inputs(witnesses, *call.hashed_message);
185 collect_function_inputs(witnesses, *call.signature);
186 collect_function_inputs(witnesses, *call.public_key_x);
187 collect_function_inputs(witnesses, *call.public_key_y);
188 collect_function_input_witness(witnesses, call.predicate);
189 witnesses.push_back(call.output.value);
190 add_constraint(witnesses);
191 },
192 [&](const Acir::BlackBoxFuncCall::EcdsaSecp256r1& call) {
193 std::vector<uint32_t> witnesses;
194 collect_function_inputs(witnesses, *call.hashed_message);
195 collect_function_inputs(witnesses, *call.signature);
196 collect_function_inputs(witnesses, *call.public_key_x);
197 collect_function_inputs(witnesses, *call.public_key_y);
198 collect_function_input_witness(witnesses, call.predicate);
199 witnesses.push_back(call.output.value);
200 add_constraint(witnesses);
201 },
202 [&](const Acir::BlackBoxFuncCall::MultiScalarMul& call) {
203 std::vector<uint32_t> witnesses;
204 for (size_t i = 0; i + 1 < call.points.size(); i += 3) {
205 collect_function_input_witness(witnesses, call.points[i]);
206 collect_function_input_witness(witnesses, call.points[i + 1]);
207 }
208 collect_function_inputs(witnesses, call.scalars);
209 collect_function_input_witness(witnesses, call.predicate);
210 // skipping input/output is_infinite, it's unused (known)
211 witnesses.push_back((*call.outputs)[0].value);
212 witnesses.push_back((*call.outputs)[1].value);
213 add_constraint(witnesses);
214 },
215 [&](const Acir::BlackBoxFuncCall::EmbeddedCurveAdd& call) {
216 std::vector<uint32_t> witnesses;
217 collect_function_input_witness(witnesses, (*call.input1)[0]);
218 collect_function_input_witness(witnesses, (*call.input1)[1]);
219 collect_function_input_witness(witnesses, (*call.input2)[0]);
220 collect_function_input_witness(witnesses, (*call.input2)[1]);
221 collect_function_input_witness(witnesses, call.predicate);
222 // skipping input/output is_infinite, it's unused (known)
223 witnesses.push_back((*call.outputs)[0].value);
224 witnesses.push_back((*call.outputs)[1].value);
225 add_constraint(witnesses);
226 },
227 [&](const Acir::BlackBoxFuncCall::Keccakf1600& call) {
228 std::vector<uint32_t> witnesses;
229 collect_function_inputs(witnesses, *call.inputs);
230 collect_witnesses(witnesses, *call.outputs);
231 add_constraint(witnesses);
232 },
233 [&](const Acir::BlackBoxFuncCall::RecursiveAggregation& call) {
234 if (is_disabled_recursive_aggregation(call)) {
235 return;
236 }
237
238 std::vector<uint32_t> witnesses;
239 collect_function_inputs(witnesses, call.verification_key);
240 collect_function_inputs(witnesses, call.proof);
241 collect_function_inputs(witnesses, call.public_inputs);
242 collect_function_input_witness(witnesses, call.key_hash);
243 collect_function_input_witness(witnesses, call.predicate);
244 add_constraint(witnesses);
245 },
246 [&](const Acir::BlackBoxFuncCall::Poseidon2Permutation& call) {
247 std::vector<uint32_t> witnesses;
248 collect_function_inputs(witnesses, call.inputs);
249 collect_witnesses(witnesses, call.outputs);
250 add_constraint(witnesses);
251 } },
252 black_box.value.value);
253 },
254 [&](const Acir::Opcode::MemoryInit& memory_init) {
255 auto& witnesses = block_witnesses[memory_init.block_id.value];
256 collect_witnesses(witnesses, memory_init.init);
257 },
258 [&](const Acir::Opcode::MemoryOp& memory_op) {
259 auto& witnesses = block_witnesses[memory_op.block_id.value];
260 witnesses.push_back(memory_op.op.index.value);
261 witnesses.push_back(memory_op.op.value.value);
262 },
263 [&](const Acir::Opcode::BrilligCall&) {},
264 [&](const Acir::Opcode::Call&) {} },
265 opcode.value);
266 }
267
268 for (const auto& [_, witnesses] : block_witnesses) {
269 add_constraint(witnesses);
270 }
271}
272
273} // namespace acir_components_check
acir_graph.hpp
acir_to_constraint_buf.hpp
acir_components_check::AcirGraph::get_witness_component_map
std::unordered_map< uint32_t, size_t > get_witness_component_map() const
Map each witness that appears in at least one edge to a component id.
Definition acir_graph.cpp:112
acir_components_check::AcirGraph::find_components
std::vector< std::vector< uint32_t > > find_components() const
Iterative DFS over adjacency_lists_; each inner vector is one component's vertices.
Definition acir_graph.cpp:80
acir_components_check::AcirGraph::process_acir_circuit
void process_acir_circuit(const Acir::Circuit &circuit)
Walk circuit.opcodes, populate adjacency, then merge per-block memory witnesses.
Definition acir_graph.cpp:124
acir_components_check::AcirGraph::add_constraint
void add_constraint(const std::vector< uint32_t > &witnesses)
Add a clique on the given witness indices (deduplicated). Empty or singleton → no edges.
Definition acir_graph.cpp:59
acir_components_check::AcirGraph::adjacency_lists_
std::unordered_map< uint32_t, std::unordered_set< uint32_t > > adjacency_lists_
Definition acir_graph.hpp:47
overloaded
overloaded(Ts...) -> overloaded< Ts... >
inputs
AvmProvingInputs inputs
Definition hinting_dbs.test.cpp:46
acir_components_check
Validates that ACIR witness connectivity (from the Noir circuit) matches circuit variable connectivit...
Definition acir_graph.cpp:11
acir_format::parse_input
WitnessOrConstant< bb::fr > parse_input(const Acir::FunctionInput &input)
Parse an Acir::FunctionInput (which can either be a witness or a constant) into a WitnessOrConstant.
Definition acir_to_constraint_buf.cpp:43
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
lhs
bb::VectorAffineElementPushSpan< BaseParams > lhs
Definition scalar_multiplication_fast.cpp:174
rhs
bb::VectorAffineElementPushSpan< BaseParams > rhs
Definition scalar_multiplication_fast.cpp:175
Acir::Circuit::opcodes
std::vector< Acir::Opcode > opcodes
Definition acir.hpp:7232
Acir::Expression::linear_combinations
std::vector< std::tuple< std::vector< uint8_t >, Acir::Witness > > linear_combinations
Definition acir.hpp:5856
Acir::Expression::mul_terms
std::vector< std::tuple< std::vector< uint8_t >, Acir::Witness, Acir::Witness > > mul_terms
Definition acir.hpp:5855
Acir::FunctionInput::value
std::variant< Constant, Witness > value
Definition acir.hpp:4288
result
VectorField result
Definition vector_field_mont_mul_body.inl.hpp:14