#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_ (CircuitBuilder &circuit_builder, bool connect_variables=true)
	Construct a new StaticAnalyzer for Ultra Circuit Builder or Mega Circuit Builder.

std::vector< uint32_t >	to_real (std::vector< uint32_t > &variable_indices)
	Convert a vector of variable indices to their real indices.

uint32_t	to_real (const uint32_t &variable_index) const

std::optional< size_t >	find_block_index (const auto &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 () const

void	process_execution_trace ()

std::vector< uint32_t >	get_arithmetic_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from arithmetic gates

std::vector< uint32_t >	get_elliptic_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from elliptic gates

std::vector< uint32_t >	get_plookup_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from plookup gates

std::vector< uint32_t >	get_sort_constraint_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from sorted constraints

std::vector< uint32_t >	get_poseido2s_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from poseidon2 gates

std::vector< uint32_t >	get_non_native_field_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from Non-Native Field gates (bigfield operations)

std::vector< uint32_t >	get_memory_gate_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from Memory gates (RAM and ROM consistency checks)

std::vector< uint32_t >	get_rom_table_connected_component (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 (const bb::RamTranscript &ram_array)
	this method gets the RAM table connected component by processing RAM transcript records

std::vector< uint32_t >	get_databus_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from databus gates

std::vector< uint32_t >	get_eccop_connected_component (size_t index, size_t block_idx, auto &blk)

std::vector< uint32_t >	get_eccop_part_connected_component (size_t index, size_t block_idx, auto &blk)
	this method creates connected components from elliptic curve operation gates

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

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

void	mark_range_list_connected_components ()
	this method marks some connected componets like they represent range lists tool needs this method to remove range lists because after method finalize was called because they aren't connected to other variables in a circuit. It's intended behaviout but the tool shows them as another connected component

void	mark_finalize_connected_components ()
	this method marks some connected components like they represent separated finalize blocks the point is finalize method create additional gates for ecc_op in databus in Mega case and they aren't connected to other variables in the circuit. It's intended behaviour but the tool shows them as another connected component

void	mark_process_rom_connected_component ()
	this method marks some connected components if they were created by function process_rom_array. the point is process_ROM_array function uses only create_sorted_ROM_gate function internally for sorted_ROM_gate we know that (q_memory, q_1, q_2) == (1, 1, 1), so if all variables in connected_component are contained only in this type of gate, we can remove this connected component from the scope, cause it's a result of process_ROM_array function

bool	is_gate_sorted_rom (size_t memory_block_idx, size_t gate_idx) const
	this method checks if current gate is sorted ROM gate

bool	variable_only_in_sorted_rom_gates (uint32_t var_idx, size_t blk_idx) const
	this method checks that every gate for given variable in a given block is sorted ROM gate

std::vector< ConnectedComponent >	find_connected_components ()
	this methond finds all connected components in the graph described by adjacency lists and marks some of them as connected components that were created with functions in method finalize_circuit

bool	check_vertex_in_connected_component (const std::vector< uint32_t > &connected_component, const uint32_t &var_index)

void	connect_all_variables_in_vector (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 (const uint32_t &variable_index)
	this method checks whether the variable with given index is not constant

void	save_constant_variable_indices ()
	this method needs to save all constant variables indices in one data structure in order to not go through whole map constant variable indices every time when tool checks that variable isn't constant

size_t	process_current_decompose_chain (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 (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 (const std::unordered_set< uint32_t > &decompose_variables)
	this method removes unnecessary variables from decompose chains

void	remove_unnecessary_plookup_variables ()
	this method removes false cases plookup variables from variables in one gate

void	remove_unnecessary_range_constrains_variables ()
	this method removes variables from range constraints that are not security critical

void	remove_unnecessary_aes_plookup_variables (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 (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_unnecessary_keccak_plookup_variables (bb::plookup::BasicTableId &table_id, size_t gate_index)
	This method removes false positive cases from keccak lookup tables. Tables which are enumerated in keccak_plookup_tables are used by keccak lookup constraints. Some lookup-gate outputs are auxiliary (e.g. MSB) and may appear in only one gate but this is not dangerous. So we remove these variables.

void	remove_record_witness_variables ()
	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.

std::unordered_set< uint32_t >	get_variables_in_one_gate ()
	this method returns a final set of variables that were in one gate

std::pair< std::vector< ConnectedComponent >, std::unordered_set< uint32_t > >	analyze_circuit (bool filter_cc=true)
	this functions was made for more convenient testing process

void	print_connected_components_info ()
	this method prints additional information about 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_arithmetic_gate_info (size_t gate_idx, auto &block)
	this method prints all information about arithmetic gate where variable was found

void	print_elliptic_gate_info (size_t gate_idx, auto &block)
	this method prints all information about elliptic gate where variable was found

void	print_plookup_gate_info (size_t gate_idx, auto &block)
	this method prints all information about plookup gate where variable was found

void	print_poseidon2s_gate_info (size_t gate_idx, auto &block)
	this method prints all information about poseidon2s gate where variable was found

void	print_nnf_gate_info (size_t gate_idx, auto &block)
	this method prints all information about non natife field gate where variable was found

void	print_memory_gate_info (size_t gate_idx, auto &block)
	this method prints all information about memory gate where variable was found

void	print_delta_range_gate_info (size_t gate_idx, auto &block)
	this method prints all information about range constrain gate where variable was found

void	print_variable_info (const uint32_t real_idx)
	this method prints all information about gates where variable was found

	~StaticAnalyzer_ ()=default

Private Attributes
CircuitBuilder &	circuit_builder

bool	connect_variables

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

std::unordered_set< uint32_t >	constant_variable_indices_set

std::vector< ConnectedComponent >	connected_components

Detailed Description

template<typename FF, typename CircuitBuilder>
class cdg::StaticAnalyzer_< FF, CircuitBuilder >

Definition at line 80 of file graph.hpp.

Constructor & Destructor Documentation

◆ StaticAnalyzer_() [1/4]

template<typename FF , typename CircuitBuilder >

cdg::StaticAnalyzer_< FF, CircuitBuilder >::StaticAnalyzer_ ( )

default

◆ StaticAnalyzer_() [2/4]

template<typename FF , typename CircuitBuilder >

cdg::StaticAnalyzer_< FF, CircuitBuilder >::StaticAnalyzer_ ( const StaticAnalyzer_< FF, CircuitBuilder > & other )

delete

◆ StaticAnalyzer_() [3/4]

template<typename FF , typename CircuitBuilder >

cdg::StaticAnalyzer_< FF, CircuitBuilder >::StaticAnalyzer_ ( StaticAnalyzer_< FF, CircuitBuilder > && other )

delete

◆ StaticAnalyzer_() [4/4]

template<typename FF , typename CircuitBuilder >

cdg::StaticAnalyzer_< FF, CircuitBuilder >::StaticAnalyzer_	(	CircuitBuilder &	circuit_builder,
		bool	connect_variables = `true`
	)

Construct a new StaticAnalyzer for Ultra Circuit Builder or Mega Circuit Builder.

Template Parameters

FF	field type used in the circuit
CircuitBuilder

Parameters

CircuitBuilder
connect_variables

This constructor initializes the graph structure by: 1) Creating data structures for tracking:

Number of gates each variable appears in (variables_gate_counts)
Adjacency lists for each variable (variable_adjacency_lists)
Degree of each variable (variables_degree) 2) Processing different types of gates:
Arithmetic gates
Elliptic curve gates
Plookup gates
Poseidon2 gates
Memory gates
Non-native field gates
Delta range gates 3) Creating connections between variables that appear in the same gate 4) Special handling for sorted constraints in delta range blocks

Definition at line 760 of file graph.cpp.

◆ ~StaticAnalyzer_()

template<typename FF , typename CircuitBuilder >

cdg::StaticAnalyzer_< FF, CircuitBuilder >::~StaticAnalyzer_ ( )

default

Member Function Documentation

◆ add_new_edge()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::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

Template Parameters

FF
CircuitBuilder

Parameters

first_variable_index
second_variable_index

Definition at line 855 of file graph.cpp.

◆ analyze_circuit()

template<typename FF , typename CircuitBuilder >

std::pair< std::vector< ConnectedComponent >, std::unordered_set< uint32_t > > cdg::StaticAnalyzer_< FF, CircuitBuilder >::analyze_circuit ( bool filter_cc = true )

this functions was made for more convenient testing process

Template Parameters

FF
CircuitBuilder

Returns: std::pair<std::vector<ConnectedComponent>, std::unordered_set<uint32_t>>

it's important to mention that if you want to use this function and get all cc, you have to change flag filter_cc IN tests, because by default it's true

Definition at line 1804 of file graph.cpp.

◆ check_is_not_constant_variable()

template<typename FF , typename CircuitBuilder >

bool cdg::StaticAnalyzer_< FF, CircuitBuilder >::check_is_not_constant_variable ( const uint32_t & variable_index )

this method checks whether the variable with given index is not constant

Template Parameters

FF
CircuitBuilder

Parameters

variable_index

Definition at line 803 of file graph.cpp.

◆ check_vertex_in_connected_component()

template<typename FF , typename CircuitBuilder >

bool cdg::StaticAnalyzer_< FF, CircuitBuilder >::check_vertex_in_connected_component	(	const std::vector< uint32_t > &	connected_component,
		const uint32_t &	var_index
	)

◆ connect_all_variables_in_vector()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::connect_all_variables_in_vector ( 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

Template Parameters

FF
CircuitBuilder

Parameters

variables_vector

Definition at line 820 of file graph.cpp.

◆ depth_first_search()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::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

Template Parameters

FF
CircuitBuilder

Parameters

variable_index
is_used
connected_component

Definition at line 874 of file graph.cpp.

◆ find_block_index()

template<typename FF , typename CircuitBuilder >

std::optional< size_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::find_block_index ( const auto & block )

this method finds index of the block in circuit builder by comparing pointers to blocks

Template Parameters

FF	field type
CircuitBuilder

Parameters

block block to find

Returns: size_t index of the found block

Definition at line 30 of file graph.cpp.

◆ find_connected_components()

template<typename FF , typename CircuitBuilder >

std::vector< ConnectedComponent > cdg::StaticAnalyzer_< FF, CircuitBuilder >::find_connected_components ( )

this methond finds all connected components in the graph described by adjacency lists and marks some of them as connected components that were created with functions in method finalize_circuit

Template Parameters

FF
CircuitBuilder

Returns: std::vector<std::vector<uint32_t>> list of connected components where each component is a vector of variable indices

Definition at line 903 of file graph.cpp.

◆ get_arithmetic_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_arithmetic_gate_connected_component	(	size_t	index,
		size_t	block_idx,
		auto &	blk
	)

inline

this method creates connected components from arithmetic gates

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
block_idx	index of the current block
blk	block containing the gates

Returns: std::vector<std::vector<uint32_t>> vector of connected components from the gate and minigate

Processes both regular arithmetic gates and minigates, handling fixed witness gates and different arithmetic operations based on selector values

Definition at line 86 of file graph.cpp.

◆ get_databus_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_databus_connected_component	(	size_t	index,
		size_t	block_idx,
		auto &	blk
	)

inline

this method creates connected components from databus gates

Template Parameters

FF	field type

Parameters

CircuitBuilder
index	index of the current gate
block_idx	index of the current block
blk	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Processes databus read operations by collecting variables from left and right wires

Definition at line 595 of file graph.cpp.

◆ get_eccop_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_eccop_connected_component	(	size_t	index,
		size_t	block_idx,
		auto &	blk
	)

◆ get_eccop_part_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_eccop_part_connected_component	(	size_t	index,
		size_t	block_idx,
		auto &	blk
	)

inline

this method creates connected components from elliptic curve operation gates

Template Parameters

FF	field type

Parameters

CircuitBuilder
index	index of the current gate
block_idx	index of the current block
blk	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Processes elliptic curve operations by collecting variables from current and next gates, handling opcodes and coordinate variables for curve operations

Definition at line 620 of file graph.cpp.

◆ get_elliptic_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_elliptic_gate_connected_component	(	size_t	index,
		size_t	block_idx,
		auto &	blk
	)

inline

this method creates connected components from elliptic gates

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
block_idx	index of the current block
blk	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Handles both elliptic curve addition and doubling operations, collecting variables from current and next gates as needed

Definition at line 171 of file graph.cpp.

◆ get_memory_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_memory_gate_connected_component	(	size_t	index,
		size_t	blk_idx,
		auto &	block
	)

inline

this method creates connected components from Memory gates (RAM and ROM consistency checks)

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
blk_idx	index of the current block
block	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Definition at line 337 of file graph.cpp.

◆ get_non_native_field_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_non_native_field_gate_connected_component	(	size_t	index,
		size_t	blk_idx,
		auto &	block
	)

inline

this method creates connected components from Non-Native Field gates (bigfield operations)

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
blk_idx	index of the current block
block	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Definition at line 397 of file graph.cpp.

◆ get_plookup_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_plookup_gate_connected_component	(	size_t	index,
		size_t	blk_idx,
		auto &	block
	)

inline

this method creates connected components from plookup gates

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
block_idx	index of the current block
block	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Processes plookup gates by collecting variables based on selector values, including variables from the next gate when necessary

Definition at line 261 of file graph.cpp.

◆ get_poseido2s_gate_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_poseido2s_gate_connected_component	(	size_t	index,
		size_t	blk_idx,
		auto &	block
	)

inline

this method creates connected components from poseidon2 gates

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
blk_idx	index of the current block
block	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Definition at line 302 of file graph.cpp.

◆ get_ram_table_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_ram_table_connected_component ( const bb::RamTranscript & ram_array )

inline

this method gets the RAM table connected component by processing RAM transcript records

Template Parameters

FF	field type

Parameters

CircuitBuilder
ultra_builder	circuit builder containing the gates
ram_array	RAM transcript containing records with witness indices and gate information

Returns: std::vector<uint32_t> vector of connected variables from RAM table gates

Definition at line 540 of file graph.cpp.

◆ get_rom_table_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_rom_table_connected_component ( const bb::RomTranscript & rom_array )

inline

this method gets the ROM table connected component by processing ROM transcript records

Template Parameters

FF	field type
CircuitBuilder

Parameters

rom_array ROM transcript containing records with witness indices and gate information

Returns: std::vector<uint32_t> vector of connected variables from ROM table gates

Definition at line 477 of file graph.cpp.

◆ get_sort_constraint_connected_component()

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_sort_constraint_connected_component	(	size_t	index,
		size_t	blk_idx,
		auto &	block
	)

inline

this method creates connected components from sorted constraints

Template Parameters

FF	field type
CircuitBuilder

Parameters

index	index of the current gate
block_idx	index of the current block
block	block containing the gates

Returns: std::vector<uint32_t> vector of connected variables from the gate

Processes delta range constraints by collecting all wire indices from the current gate

Definition at line 223 of file graph.cpp.

◆ get_variables_gate_counts()

template<typename FF , typename CircuitBuilder >

std::unordered_map< uint32_t, size_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_variables_gate_counts ( ) const

inline

Definition at line 109 of file graph.hpp.

◆ get_variables_in_one_gate()

template<typename FF , typename CircuitBuilder >

std::unordered_set< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_variables_in_one_gate ( )

this method returns a final set of variables that were in one gate

Template Parameters

FF
CircuitBuilder

Returns: std::unordered_set<uint32_t> set of variable indices

Definition at line 1442 of file graph.cpp.

◆ is_gate_sorted_rom()

template<typename FF , typename CircuitBuilder >

bool cdg::StaticAnalyzer_< FF, CircuitBuilder >::is_gate_sorted_rom	(	size_t	memory_block_idx,
		size_t	gate_idx
	)		const

this method checks if current gate is sorted ROM gate

Template Parameters

FF
CircuitBuilder

Parameters

memory_block_idx
gate_idx

Definition at line 935 of file graph.cpp.

◆ mark_finalize_connected_components()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::mark_finalize_connected_components ( )

this method marks some connected components like they represent separated finalize blocks the point is finalize method create additional gates for ecc_op in databus in Mega case and they aren't connected to other variables in the circuit. It's intended behaviour but the tool shows them as another connected component

Template Parameters

FF
CircuitBuilder

Definition at line 1030 of file graph.cpp.

◆ mark_process_rom_connected_component()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::mark_process_rom_connected_component ( )

this method marks some connected components if they were created by function process_rom_array. the point is process_ROM_array function uses only create_sorted_ROM_gate function internally for sorted_ROM_gate we know that (q_memory, q_1, q_2) == (1, 1, 1), so if all variables in connected_component are contained only in this type of gate, we can remove this connected component from the scope, cause it's a result of process_ROM_array function

Template Parameters

FF
CircuitBuilder

Definition at line 976 of file graph.cpp.

◆ mark_range_list_connected_components()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::mark_range_list_connected_components ( )

this method marks some connected componets like they represent range lists tool needs this method to remove range lists because after method finalize was called because they aren't connected to other variables in a circuit. It's intended behaviout but the tool shows them as another connected component

Template Parameters

FF
CircuitBuilder

Definition at line 1002 of file graph.cpp.

◆ operator=() [1/2]

template<typename FF , typename CircuitBuilder >

StaticAnalyzer_ & cdg::StaticAnalyzer_< FF, CircuitBuilder >::operator= ( const StaticAnalyzer_< FF, CircuitBuilder > & other )

delete

◆ operator=() [2/2]

template<typename FF , typename CircuitBuilder >

StaticAnalyzer_ && cdg::StaticAnalyzer_< FF, CircuitBuilder >::operator= ( StaticAnalyzer_< FF, CircuitBuilder > && other )

delete

◆ print_arithmetic_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_arithmetic_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about arithmetic gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1523 of file graph.cpp.

◆ print_connected_components_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_connected_components_info ( )

this method prints additional information about connected components that were found in the graph

Template Parameters

FF
CircuitBuilder

Definition at line 1482 of file graph.cpp.

◆ print_delta_range_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_delta_range_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about range constrain gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1625 of file graph.cpp.

◆ print_elliptic_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_elliptic_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about elliptic gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1558 of file graph.cpp.

◆ print_memory_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_memory_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about memory gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1718 of file graph.cpp.

◆ print_nnf_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_nnf_gate_info	(	size_t	gate_idx,
		auto &	block
	)

this method prints all information about non natife field gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1678 of file graph.cpp.

◆ print_plookup_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_plookup_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about plookup gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1591 of file graph.cpp.

◆ print_poseidon2s_gate_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_poseidon2s_gate_info	(	size_t	gate_index,
		auto &	block
	)

this method prints all information about poseidon2s gate where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

block
gate_index

Definition at line 1649 of file graph.cpp.

◆ print_variable_info()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_variable_info ( const uint32_t real_idx )

this method prints all information about gates where variable was found

Template Parameters

FF
CircuitBuilder

Parameters

real_index

Definition at line 1757 of file graph.cpp.

◆ print_variables_gate_counts()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::print_variables_gate_counts ( )

this method prints a number of gates for each variable

Template Parameters

FF
CircuitBuilder

Definition at line 1508 of file graph.cpp.

◆ process_current_decompose_chain()

template<typename FF , typename CircuitBuilder >

size_t cdg::StaticAnalyzer_< FF, CircuitBuilder >::process_current_decompose_chain ( size_t index )

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.

Template Parameters

FF
CircuitBuilder

Parameters

ultra_circuit_constructor
variables_in_one_gate
index

Returns: size_t

Definition at line 1058 of file graph.cpp.

◆ process_current_plookup_gate()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::process_current_plookup_gate ( size_t 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

Template Parameters

FF
CircuitBuilder

Parameters

gate_index

Definition at line 1326 of file graph.cpp.

◆ process_execution_trace()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::process_execution_trace ( )

Definition at line 653 of file graph.cpp.

◆ process_gate_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::process_gate_variables	(	std::vector< uint32_t > &	gate_variables,
		size_t	gate_index,
		size_t	block_idx
	)

inline

this method processes variables from a gate by removing duplicates and updating tracking structures

Template Parameters

FF	field type
CircuitBuilder

Parameters

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

Definition at line 56 of file graph.cpp.

◆ remove_record_witness_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_record_witness_variables ( )

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.

Template Parameters

FF
CircuitBuilder

Definition at line 1400 of file graph.cpp.

◆ remove_unnecessary_aes_plookup_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_aes_plookup_variables	(	bb::plookup::BasicTableId &	table_id,
		size_t	gate_index
	)

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.

Template Parameters

FF
CircuitBuilder

Parameters

table_id
gate_index

Definition at line 1199 of file graph.cpp.

◆ remove_unnecessary_decompose_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_decompose_variables ( const std::unordered_set< uint32_t > & decompose_variables )

inline

this method removes unnecessary variables from decompose chains

Template Parameters

FF
CircuitBuilder

Parameters

variables_in_one_gate

Definition at line 1111 of file graph.cpp.

◆ remove_unnecessary_keccak_plookup_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_keccak_plookup_variables	(	bb::plookup::BasicTableId &	table_id,
		size_t	gate_index
	)

inline

This method removes false positive cases from keccak lookup tables. Tables which are enumerated in keccak_plookup_tables are used by keccak lookup constraints. Some lookup-gate outputs are auxiliary (e.g. MSB) and may appear in only one gate but this is not dangerous. So we remove these variables.

Template Parameters

FF
CircuitBuilder

Parameters

table_id
gate_index

Definition at line 1285 of file graph.cpp.

◆ remove_unnecessary_plookup_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_plookup_variables ( )

inline

this method removes false cases plookup variables from variables in one gate

Template Parameters

FF
CircuitBuilder

Definition at line 1381 of file graph.cpp.

◆ remove_unnecessary_range_constrains_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_range_constrains_variables ( )

this method removes variables from range constraints that are not security critical

Template Parameters

FF	field type
CircuitBuilder

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

Definition at line 1161 of file graph.cpp.

◆ remove_unnecessary_sha256_plookup_variables()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::remove_unnecessary_sha256_plookup_variables	(	bb::plookup::BasicTableId &	table_id,
		size_t	gate_index
	)

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.

Template Parameters

FF
CircuitBuilder

Parameters

table_id
gate_index

Definition at line 1237 of file graph.cpp.

◆ save_constant_variable_indices()

template<typename FF , typename CircuitBuilder >

void cdg::StaticAnalyzer_< FF, CircuitBuilder >::save_constant_variable_indices ( )

this method needs to save all constant variables indices in one data structure in order to not go through whole map constant variable indices every time when tool checks that variable isn't constant

Template Parameters

FF
CircuitBuilder

Definition at line 786 of file graph.cpp.

◆ to_real() [1/2]

template<typename FF , typename CircuitBuilder >

uint32_t cdg::StaticAnalyzer_< FF, CircuitBuilder >::to_real ( const uint32_t & variable_index ) const

inline

Definition at line 103 of file graph.hpp.

◆ to_real() [2/2]

template<typename FF , typename CircuitBuilder >

std::vector< uint32_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::to_real ( std::vector< uint32_t > & variable_indices )

inline

Convert a vector of variable indices to their real indices.

Parameters

variable_indices The vector of variable indices to convert

Returns: std::vector<uint32_t> A vector of real variable indices

Definition at line 94 of file graph.hpp.

◆ variable_only_in_sorted_rom_gates()

template<typename FF , typename CircuitBuilder >

bool cdg::StaticAnalyzer_< FF, CircuitBuilder >::variable_only_in_sorted_rom_gates	(	uint32_t	var_idx,
		size_t	blk_idx
	)		const

this method checks that every gate for given variable in a given block is sorted ROM gate

Template Parameters

FF
CircuitBuilder

Parameters

var_idx
blk_idx

Definition at line 952 of file graph.cpp.

Member Data Documentation

◆ circuit_builder

template<typename FF , typename CircuitBuilder >

CircuitBuilder& cdg::StaticAnalyzer_< FF, CircuitBuilder >::circuit_builder

private

Definition at line 171 of file graph.hpp.

◆ connect_variables

template<typename FF , typename CircuitBuilder >

bool cdg::StaticAnalyzer_< FF, CircuitBuilder >::connect_variables

private

Definition at line 172 of file graph.hpp.

◆ connected_components

template<typename FF , typename CircuitBuilder >

std::vector<ConnectedComponent> cdg::StaticAnalyzer_< FF, CircuitBuilder >::connected_components

private

Definition at line 188 of file graph.hpp.

◆ constant_variable_indices_set

template<typename FF , typename CircuitBuilder >

std::unordered_set<uint32_t> cdg::StaticAnalyzer_< FF, CircuitBuilder >::constant_variable_indices_set

private

Definition at line 186 of file graph.hpp.

◆ fixed_variables

template<typename FF , typename CircuitBuilder >

std::unordered_set<uint32_t> cdg::StaticAnalyzer_< FF, CircuitBuilder >::fixed_variables

private

Definition at line 185 of file graph.hpp.

◆ variable_adjacency_lists

template<typename FF , typename CircuitBuilder >

std::unordered_map<uint32_t, std::vector<uint32_t> > cdg::StaticAnalyzer_< FF, CircuitBuilder >::variable_adjacency_lists

private

Definition at line 175 of file graph.hpp.

◆ variable_gates

template<typename FF , typename CircuitBuilder >

std::unordered_map<KeyPair, std::vector<size_t>, KeyHasher, KeyEquals> cdg::StaticAnalyzer_< FF, CircuitBuilder >::variable_gates

private

Definition at line 182 of file graph.hpp.

◆ variables_degree

template<typename FF , typename CircuitBuilder >

std::unordered_map<uint32_t, size_t> cdg::StaticAnalyzer_< FF, CircuitBuilder >::variables_degree

private

Definition at line 180 of file graph.hpp.

◆ variables_gate_counts

template<typename FF , typename CircuitBuilder >

std::unordered_map<uint32_t, size_t> cdg::StaticAnalyzer_< FF, CircuitBuilder >::variables_gate_counts

private

Definition at line 178 of file graph.hpp.

◆ variables_in_one_gate

template<typename FF , typename CircuitBuilder >

std::unordered_set<uint32_t> cdg::StaticAnalyzer_< FF, CircuitBuilder >::variables_in_one_gate

private

Definition at line 184 of file graph.hpp.

The documentation for this class was generated from the following files:

src/barretenberg/boomerang_value_detection/graph.hpp
src/barretenberg/boomerang_value_detection/graph.cpp

Public Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ StaticAnalyzer_() [1/4]

◆ StaticAnalyzer_() [2/4]

◆ StaticAnalyzer_() [3/4]

◆ StaticAnalyzer_() [4/4]

◆ ~StaticAnalyzer_()

Member Function Documentation

◆ add_new_edge()

◆ analyze_circuit()

◆ check_is_not_constant_variable()

◆ check_vertex_in_connected_component()

◆ connect_all_variables_in_vector()

◆ depth_first_search()

◆ find_block_index()

◆ find_connected_components()

◆ get_arithmetic_gate_connected_component()

◆ get_databus_connected_component()

◆ get_eccop_connected_component()

◆ get_eccop_part_connected_component()

◆ get_elliptic_gate_connected_component()

◆ get_memory_gate_connected_component()

◆ get_non_native_field_gate_connected_component()

◆ get_plookup_gate_connected_component()

◆ get_poseido2s_gate_connected_component()

◆ get_ram_table_connected_component()

◆ get_rom_table_connected_component()

◆ get_sort_constraint_connected_component()

◆ get_variables_gate_counts()

◆ get_variables_in_one_gate()

◆ is_gate_sorted_rom()

◆ mark_finalize_connected_components()

◆ mark_process_rom_connected_component()

◆ mark_range_list_connected_components()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ print_arithmetic_gate_info()

◆ print_connected_components_info()

◆ print_delta_range_gate_info()

◆ print_elliptic_gate_info()

◆ print_memory_gate_info()

◆ print_nnf_gate_info()

◆ print_plookup_gate_info()

◆ print_poseidon2s_gate_info()

◆ print_variable_info()

◆ print_variables_gate_counts()

◆ process_current_decompose_chain()

◆ process_current_plookup_gate()

◆ process_execution_trace()

◆ process_gate_variables()

◆ remove_record_witness_variables()

◆ remove_unnecessary_aes_plookup_variables()

◆ remove_unnecessary_decompose_variables()

◆ remove_unnecessary_keccak_plookup_variables()

◆ remove_unnecessary_plookup_variables()

◆ remove_unnecessary_range_constrains_variables()

◆ remove_unnecessary_sha256_plookup_variables()

◆ save_constant_variable_indices()

◆ to_real() [1/2]

◆ to_real() [2/2]

◆ variable_only_in_sorted_rom_gates()

Member Data Documentation

◆ circuit_builder

◆ connect_variables

◆ connected_components

◆ constant_variable_indices_set

◆ fixed_variables

◆ variable_adjacency_lists

◆ variable_gates

◆ variables_degree

◆ variables_gate_counts

◆ variables_in_one_gate