- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
#include <graph.hpp>
Public Member Functions | |
| StaticAnalyzer_ ()=default | |
| StaticAnalyzer_ (const StaticAnalyzer_ &other)=delete | |
| StaticAnalyzer_ (StaticAnalyzer_ &&other)=delete | |
| StaticAnalyzer_ & | operator= (const StaticAnalyzer_ &other)=delete |
| StaticAnalyzer_ && | operator= (StaticAnalyzer_ &&other)=delete |
| StaticAnalyzer_ (bb::UltraCircuitBuilder &ultra_circuit_constructor, bool connect_variables=true) | |
| Construct a new StaticAnalyzer from Ultra Circuit Builder. | |
| std::vector< uint32_t > | to_real (bb::UltraCircuitBuilder &ultra_circuit_constructor, std::vector< uint32_t > &variable_indices) |
| Convert a vector of variable indices to their real indices. | |
| uint32_t | to_real (bb::UltraCircuitBuilder &ultra_circuit_constructor, const uint32_t &variable_index) |
| size_t | find_block_index (bb::UltraCircuitBuilder &ultra_builder, const UltraBlock &block) |
| this method finds index of the block in circuit builder by comparing pointers to blocks | |
| void | process_gate_variables (std::vector< uint32_t > &gate_variables, size_t gate_index, size_t blk_idx) |
| this method processes variables from a gate by removing duplicates and updating tracking structures | |
| std::unordered_map< uint32_t, size_t > | get_variables_gate_counts () |
| std::vector< std::vector< uint32_t > > | get_arithmetic_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from arithmetic gates | |
| std::vector< uint32_t > | get_elliptic_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from elliptic gates | |
| std::vector< uint32_t > | get_plookup_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from plookup gates | |
| std::vector< uint32_t > | get_sort_constraint_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from sorted constraints | |
| std::vector< uint32_t > | get_poseido2s_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from poseidon2 gates | |
| std::vector< uint32_t > | get_memory_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from Memory gates (RAM and ROM consistency checks) | |
| std::vector< uint32_t > | get_non_native_field_gate_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t index, size_t block_idx, UltraBlock &blk) |
| this method creates connected components from Non-Native Field gates (bigfield operations) | |
| std::vector< uint32_t > | get_rom_table_connected_component (bb::UltraCircuitBuilder &ultra_circuit_builder, const bb::RomTranscript &rom_array) |
| this method gets the ROM table connected component by processing ROM transcript records | |
| std::vector< uint32_t > | get_ram_table_connected_component (bb::UltraCircuitBuilder &ultra_builder, const bb::RamTranscript &ram_array) |
| this method gets the RAM table connected component by processing RAM transcript records | |
| void | add_new_edge (const uint32_t &first_variable_index, const uint32_t &second_variable_index) |
| this method creates an edge between two variables in graph. All needed checks in a function above | |
| std::vector< uint32_t > | get_variable_adjacency_list (const uint32_t &variable_index) |
| void | depth_first_search (const uint32_t &variable_index, std::unordered_set< uint32_t > &is_used, std::vector< uint32_t > &connected_component) |
| this method implements depth-first search algorithm for undirected graphs | |
| std::vector< std::vector< uint32_t > > | find_connected_components () |
| this methond finds all connected components in the graph described by adjacency lists | |
| std::vector< uint32_t > | find_variables_with_degree_one () |
| std::unordered_set< uint32_t > | get_variables_in_one_gate () |
| bool | find_arithmetic_gate_for_variable (bb::UltraCircuitBuilder &ultra_circuit_builder, const uint32_t &variable_idx) |
| bool | find_elliptic_gate_for_variable (bb::UltraCircuitBuilder &ultra_circuit_builder, const uint32_t &variable_idx) |
| bool | find_lookup_gate_for_variable (bb::UltraCircuitBuilder &ultra_circuit_builder, const uint32_t &variable_idx) |
| size_t | get_distance_between_variables (const uint32_t &first_variable_index, const uint32_t &second_variable_index) |
| bool | check_vertex_in_connected_component (const std::vector< uint32_t > &connected_component, const uint32_t &var_index) |
| void | connect_all_variables_in_vector (bb::UltraCircuitBuilder &ultra_circuit_builder, const std::vector< uint32_t > &variables_vector) |
| this method connects 2 variables if they are in one gate and 1) have different indices, 2) not constant variables, 3) their indices != 0 | |
| bool | check_is_not_constant_variable (bb::UltraCircuitBuilder &ultra_circuit_builder, const uint32_t &variable_index) |
| this method checks whether the variable with given index is not constant | |
| std::pair< std::vector< uint32_t >, size_t > | get_connected_component_with_index (const std::vector< std::vector< uint32_t > > &connected_components, size_t index) |
| std::unordered_set< uint32_t > | get_variables_in_one_gate_without_range_constraints (bb::UltraCircuitBuilder &ultra_circuit_builder) |
| size_t | process_current_decompose_chain (bb::UltraCircuitBuilder &ultra_circuit_constructor, std::unordered_set< uint32_t > &variables_in_one_gate, size_t index) |
| this method removes variables that were created in a function decompose_into_default_range because they are false cases and don't give any useful information about security of the circuit. decompose_into_default_range function creates addition gates with shifts for intermediate variables, i.e. variables from left, right and output wires. They have variable gates count = 1 or 2, but they are not dangerous. so, we have to remove these variables from the analyzer. The situation is dangerous, if first variable from accumulators have variables gate count = 1. It means that it was used only in decompose gate, and it's not properly constrained. | |
| void | process_current_plookup_gate (bb::UltraCircuitBuilder &ultra_circuit_builder, size_t gate_index) |
| this method removes false cases in lookup table for a given gate. it uses all functions above for lookup tables to remove all variables that appear in one gate, if they are not dangerous | |
| void | remove_unnecessary_decompose_variables (bb::UltraCircuitBuilder &ultra_circuit_builder, std::unordered_set< uint32_t > &variables_in_on_gate, const std::unordered_set< uint32_t > &decompose_variables) |
| this method removes unnecessary variables from decompose chains | |
| void | remove_unnecessary_plookup_variables (bb::UltraCircuitBuilder &ultra_circuit_builder) |
| this method removes false cases plookup variables from variables in one gate | |
| void | remove_unnecessary_range_constrains_variables (bb::UltraCircuitBuilder &ultra_builder) |
| this method removes variables from range constraints that are not security critical | |
| std::unordered_set< uint32_t > | show_variables_in_one_gate (bb::UltraCircuitBuilder &ultra_circuit_builder) |
| this method returns a final set of variables that were in one gate | |
| void | remove_unnecessary_aes_plookup_variables (std::unordered_set< uint32_t > &variables_in_one_gate, bb::UltraCircuitBuilder &ultra_circuit_builder, bb::plookup::BasicTableId &table_id, size_t gate_index) |
| this method removes false positive cases variables from aes plookup tables. AES_SBOX_MAP, AES_SPARSE_MAP, AES_SPARSE_NORMALIZE tables are used in read_from_1_to_2_table function which return values C2[0], so C3[0] isn't used anymore in these cases, but this situation isn't dangerous. So, we have to remove these variables. | |
| void | remove_unnecessary_sha256_plookup_variables (std::unordered_set< uint32_t > &variables_in_one_gate, bb::UltraCircuitBuilder &ultra_circuit_builder, bb::plookup::BasicTableId &table_id, size_t gate_index) |
| this method removes false cases in sha256 lookup tables. tables which are enumerated in the unordered set sha256_plookup_tables are used in read_from_1_to_2_table function which return C2[0], so C3[0] isn't used anymore, but this situation isn't dangerous. So, we have to remove these variables. | |
| void | remove_record_witness_variables (bb::UltraCircuitBuilder &ultra_builder) |
| this method removes record witness variables from variables in one gate. initially record witness is added in the circuit as ctx->add_variable(0), where ctx – circuit builder. then aren't used anymore, so we can remove from the static analyzer. | |
| void | print_graph () |
| this method prints graph as vertices and their adjacency lists example: we have an undirected graph from 3 variables: a, b, c. we have edges: a - b, b - c, c - a. so, there will be next adjacency lists: a: b -> c -> 0\ b: a -> c -> 0\ c: a -> b -> 0\ | |
| void | print_connected_components () |
| this method prints all connected components that were found in the graph | |
| void | print_variables_gate_counts () |
| this method prints a number of gates for each variable | |
| void | print_variables_edge_counts () |
| void | print_variable_in_one_gate (bb::UltraCircuitBuilder &ultra_builder, const uint32_t real_idx) |
| this method prints all information about the gate where variable was found | |
| ~StaticAnalyzer_ ()=default | |
Private Attributes | |
| std::unordered_map< uint32_t, std::vector< uint32_t > > | variable_adjacency_lists |
| std::unordered_map< uint32_t, size_t > | variables_gate_counts |
| std::unordered_map< uint32_t, size_t > | variables_degree |
| std::unordered_map< KeyPair, std::vector< size_t >, KeyHasher, KeyEquals > | variable_gates |
| std::unordered_set< uint32_t > | variables_in_one_gate |
| std::unordered_set< uint32_t > | fixed_variables |
|
default |
|
delete |
|
delete |
| cdg::StaticAnalyzer_< FF >::StaticAnalyzer_ | ( | bb::UltraCircuitBuilder & | ultra_circuit_constructor, |
| bool | connect_variables = true |
||
| ) |
Construct a new StaticAnalyzer from Ultra Circuit Builder.
| FF | field type used in the circuit |
| ultra_circuit_constructor | circuit builder containing all gates and variables |
This constructor initializes the graph structure by: 1) Creating data structures for tracking:
|
default |
| void cdg::StaticAnalyzer_< FF >::add_new_edge | ( | const uint32_t & | first_variable_index, |
| const uint32_t & | second_variable_index | ||
| ) |
| bool cdg::StaticAnalyzer_< FF >::check_is_not_constant_variable | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder, |
| const uint32_t & | variable_index | ||
| ) |
| bool cdg::StaticAnalyzer_< FF >::check_vertex_in_connected_component | ( | const std::vector< uint32_t > & | connected_component, |
| const uint32_t & | var_index | ||
| ) |
| void cdg::StaticAnalyzer_< FF >::connect_all_variables_in_vector | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder, |
| const std::vector< uint32_t > & | variables_vector | ||
| ) |
| void cdg::StaticAnalyzer_< FF >::depth_first_search | ( | const uint32_t & | variable_index, |
| std::unordered_set< uint32_t > & | is_used, | ||
| std::vector< uint32_t > & | connected_component | ||
| ) |
| bool cdg::StaticAnalyzer_< FF >::find_arithmetic_gate_for_variable | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder, |
| const uint32_t & | variable_idx | ||
| ) |
| size_t cdg::StaticAnalyzer_< FF >::find_block_index | ( | bb::UltraCircuitBuilder & | ultra_builder, |
| const UltraBlock & | block | ||
| ) |
| std::vector< std::vector< uint32_t > > cdg::StaticAnalyzer_< FF >::find_connected_components | ( | ) |
| bool cdg::StaticAnalyzer_< FF >::find_elliptic_gate_for_variable | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder, |
| const uint32_t & | variable_idx | ||
| ) |
| bool cdg::StaticAnalyzer_< FF >::find_lookup_gate_for_variable | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder, |
| const uint32_t & | variable_idx | ||
| ) |
| std::vector< uint32_t > cdg::StaticAnalyzer_< FF >::find_variables_with_degree_one | ( | ) |
|
inline |
this method creates connected components from arithmetic gates
| FF | field type |
| ultra_circuit_builder | circuit builder containing the gates |
| index | index of the current gate |
| block_idx | index of the current block |
| blk | block containing the gates |
Processes both regular arithmetic gates and minigates, handling fixed witness gates and different arithmetic operations based on selector values
| std::pair< std::vector< uint32_t >, size_t > cdg::StaticAnalyzer_< FF >::get_connected_component_with_index | ( | const std::vector< std::vector< uint32_t > > & | connected_components, |
| size_t | index | ||
| ) |
| size_t cdg::StaticAnalyzer_< FF >::get_distance_between_variables | ( | const uint32_t & | first_variable_index, |
| const uint32_t & | second_variable_index | ||
| ) |
|
inline |
this method creates connected components from elliptic gates
| FF | field type |
| ultra_circuit_builder | circuit builder containing the gates |
| index | index of the current gate |
| block_idx | index of the current block |
| blk | block containing the gates |
Handles both elliptic curve addition and doubling operations, collecting variables from current and next gates as needed
|
inline |
this method creates connected components from Memory gates (RAM and ROM consistency checks)
| FF | field type |
| ultra_builder | circuit builder containing the gates |
| index | index of the current gate |
| blk_idx | index of the current block |
| block | block containing the gates |
|
inline |
this method creates connected components from Non-Native Field gates (bigfield operations)
| FF | field type |
| ultra_builder | circuit builder containing the gates |
| index | index of the current gate |
| blk_idx | index of the current block |
| block | block containing the gates |
|
inline |
this method creates connected components from plookup gates
| FF | field type |
| ultra_circuit_builder | circuit builder containing the gates |
| index | index of the current gate |
| block_idx | index of the current block |
| block | block containing the gates |
Processes plookup gates by collecting variables based on selector values, including variables from the next gate when necessary
|
inline |
this method creates connected components from poseidon2 gates
| FF | field type |
| ultra_circuit_builder | circuit builder containing the gates |
| index | index of the current gate |
| blk_idx | index of the current block |
| block | block containing the gates |
|
inline |
this method gets the RAM table connected component by processing RAM transcript records
| FF | field type |
| ultra_builder | circuit builder containing the gates |
| ram_array | RAM transcript containing records with witness indices and gate information |
|
inline |
this method gets the ROM table connected component by processing ROM transcript records
| FF | field type |
| ultra_builder | circuit builder containing the gates |
| rom_array | ROM transcript containing records with witness indices and gate information |
|
inline |
this method creates connected components from sorted constraints
| FF | field type |
| ultra_circuit_builder | circuit builder containing the gates |
| index | index of the current gate |
| block_idx | index of the current block |
| block | block containing the gates |
Processes delta range constraints by collecting all wire indices from the current gate
|
inline |
|
inline |
| std::unordered_set< uint32_t > cdg::StaticAnalyzer_< FF >::get_variables_in_one_gate | ( | ) |
| std::unordered_set< uint32_t > cdg::StaticAnalyzer_< FF >::get_variables_in_one_gate_without_range_constraints | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder | ) |
|
delete |
|
delete |
| void cdg::StaticAnalyzer_< FF >::print_connected_components | ( | ) |
| void cdg::StaticAnalyzer_< FF >::print_graph | ( | ) |
this method prints graph as vertices and their adjacency lists example: we have an undirected graph from 3 variables: a, b, c. we have edges: a - b, b - c, c - a. so, there will be next adjacency lists: a: b -> c -> 0\ b: a -> c -> 0\ c: a -> b -> 0\
| FF |
| void cdg::StaticAnalyzer_< FF >::print_variable_in_one_gate | ( | bb::UltraCircuitBuilder & | ultra_builder, |
| const uint32_t | real_idx | ||
| ) |
| void cdg::StaticAnalyzer_< FF >::print_variables_edge_counts | ( | ) |
| void cdg::StaticAnalyzer_< FF >::print_variables_gate_counts | ( | ) |
|
inline |
this method removes variables that were created in a function decompose_into_default_range because they are false cases and don't give any useful information about security of the circuit. decompose_into_default_range function creates addition gates with shifts for intermediate variables, i.e. variables from left, right and output wires. They have variable gates count = 1 or 2, but they are not dangerous. so, we have to remove these variables from the analyzer. The situation is dangerous, if first variable from accumulators have variables gate count = 1. It means that it was used only in decompose gate, and it's not properly constrained.
| FF |
| ultra_circuit_constructor | |
| variables_in_one_gate | |
| index |
|
inline |
this method removes false cases in lookup table for a given gate. it uses all functions above for lookup tables to remove all variables that appear in one gate, if they are not dangerous
| FF |
| ultra_circuit_builder | |
| variables_in_one_gate | |
| gate_index |
|
inline |
this method processes variables from a gate by removing duplicates and updating tracking structures
| FF | field type |
| ultra_circuit_builder | circuit builder containing the variables |
| gate_variables | vector of variables to process |
| gate_index | index of the current gate |
| block_idx | index of the current block |
The method performs several operations: 1) Removes duplicate variables from the input vector 2) Converts each variable to its real index using to_real 3) Creates key-value pairs of (variable_index, block_index) for tracking 4) Updates variable_gates map with gate indices for each variable 5) Increments the gate count for each processed variable
|
inline |
this method removes record witness variables from variables in one gate. initially record witness is added in the circuit as ctx->add_variable(0), where ctx – circuit builder. then aren't used anymore, so we can remove from the static analyzer.
| FF |
| ultra_builder |
|
inline |
this method removes false positive cases variables from aes plookup tables. AES_SBOX_MAP, AES_SPARSE_MAP, AES_SPARSE_NORMALIZE tables are used in read_from_1_to_2_table function which return values C2[0], so C3[0] isn't used anymore in these cases, but this situation isn't dangerous. So, we have to remove these variables.
| FF |
| variables_in_one_gate | |
| ultra_circuit_builder | |
| table_id | |
| gate_index |
|
inline |
|
inline |
| void cdg::StaticAnalyzer_< FF >::remove_unnecessary_range_constrains_variables | ( | bb::UltraCircuitBuilder & | ultra_builder | ) |
this method removes variables from range constraints that are not security critical
| FF | field type |
| ultra_builder | circuit builder containing the range lists |
Right now static analyzer removes two types of variables: 1) Variables from delta_range_constraints created by finalize_circuit() 2) Variables from range_constraints created by range_constraint_into_two_limbs
|
inline |
this method removes false cases in sha256 lookup tables. tables which are enumerated in the unordered set sha256_plookup_tables are used in read_from_1_to_2_table function which return C2[0], so C3[0] isn't used anymore, but this situation isn't dangerous. So, we have to remove these variables.
| FF |
| variables_in_one_gate | |
| ultra_circuit_builder | |
| table_id | |
| gate_index |
| std::unordered_set< uint32_t > cdg::StaticAnalyzer_< FF >::show_variables_in_one_gate | ( | bb::UltraCircuitBuilder & | ultra_circuit_builder | ) |
|
inline |
|
inline |
|
private |
|
private |
|
private |
|
private |
|
private |
1.9.8