#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

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

std::vector< ConnectedComponent >	find_connected_components (bool return_all_connected_components=false)
	this methond finds all connected components in the graph described by adjacency lists

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

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)

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

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

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_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::pair< std::vector< ConnectedComponent >, std::unordered_set< uint32_t > >	analyze_circuit ()

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::vector< ConnectedComponent >	connected_components

std::vector< ConnectedComponent >	main_connected_components

Detailed Description

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

Definition at line 72 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

Parameters

ultra_circuit_constructor circuit builder containing all gates and 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 749 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

Parameters

first_variable_index
second_variable_index

Definition at line 834 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 ( )

Definition at line 1658 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

Parameters

ultra_circuit_builder
variable_index

Returns: true; false

Definition at line 775 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

Parameters

ultra_circuit_builder
variables_vector
is_sorted_variables

Definition at line 800 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

Parameters

variable_index
is_used
connected_component

Definition at line 852 of file graph.cpp.

◆ find_block_index()

template<typename FF , typename CircuitBuilder >

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

Parameters

ultra_builder	circuit builder containing the blocks
block	block to find

Returns: size_t index of the found block

Definition at line 22 of file graph.cpp.

◆ find_connected_components()

template<typename FF , typename CircuitBuilder >

std::vector< ConnectedComponent > cdg::StaticAnalyzer_< FF, CircuitBuilder >::find_connected_components ( bool return_all_connected_components = false )

this methond finds all connected components in the graph described by adjacency lists

Template Parameters

FF

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

Definition at line 879 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

Parameters

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

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 80 of file graph.cpp.

◆ get_connected_component_with_index()

template<typename FF , typename CircuitBuilder >

std::pair< std::vector< uint32_t >, size_t > cdg::StaticAnalyzer_< FF, CircuitBuilder >::get_connected_component_with_index	(	const std::vector< std::vector< uint32_t > > &	connected_components,
		size_t	index
	)

◆ 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

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 587 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

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 611 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

Parameters

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

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 165 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

Parameters

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

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

Definition at line 331 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

Parameters

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

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

Definition at line 391 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

Parameters

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

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 255 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

Parameters

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

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

Definition at line 296 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

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 533 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

Parameters

ultra_builder	circuit builder containing the gates
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 471 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

Parameters

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

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 217 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 101 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

Parameters

ultra_circuit_builder circuit builder containing the variables

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

Definition at line 1325 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 948 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 920 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

Parameters

ultra_builder
real_idx

Definition at line 1397 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

Definition at line 1363 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

Parameters

ultra_builder
real_idx

Definition at line 1496 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

Parameters

ultra_builder
real_idx

Definition at line 1431 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

Parameters

ultra_builder
real_idx

Definition at line 1586 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

Parameters

ultra_builder
real_idx

Definition at line 1547 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

Parameters

ultra_builder
real_idx

Definition at line 1463 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

Parameters

ultra_builder
real_idx

Definition at line 1519 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

Parameters

ultra_builder
real_idx

Definition at line 1620 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

Definition at line 1383 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

Parameters

ultra_circuit_constructor
variables_in_one_gate
index

Returns: size_t

Definition at line 975 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

Parameters

ultra_circuit_builder
variables_in_one_gate
gate_index

Definition at line 1210 of file graph.cpp.

◆ process_execution_trace()

template<typename FF , typename CircuitBuilder >

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

Definition at line 644 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

Parameters

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

Definition at line 50 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

Parameters

ultra_builder

Definition at line 1283 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

Parameters

variables_in_one_gate
ultra_circuit_builder
table_id
gate_index

Definition at line 1118 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

Parameters

ultra_circuit_builder
variables_in_one_gate
decompose_variables

Definition at line 1029 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

Parameters

ultra_circuit_builder
variables_in_one_gate

Definition at line 1264 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

Parameters

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

Definition at line 1079 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

Parameters

variables_in_one_gate
ultra_circuit_builder
table_id
gate_index

Definition at line 1157 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 95 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 86 of file graph.hpp.

Member Data Documentation

◆ circuit_builder

template<typename FF , typename CircuitBuilder >

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

private

Definition at line 161 of file graph.hpp.

◆ connect_variables

template<typename FF , typename CircuitBuilder >

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

private

Definition at line 162 of file graph.hpp.

◆ connected_components

template<typename FF , typename CircuitBuilder >

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

private

Definition at line 176 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 175 of file graph.hpp.

◆ main_connected_components

template<typename FF , typename CircuitBuilder >

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

private

Definition at line 178 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 165 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 172 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 170 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 168 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 174 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_connected_component_with_index()

◆ 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()

◆ mark_finalize_connected_components()

◆ 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_plookup_variables()

◆ remove_unnecessary_range_constrains_variables()

◆ remove_unnecessary_sha256_plookup_variables()

◆ to_real() [1/2]

◆ to_real() [2/2]

Member Data Documentation

◆ circuit_builder

◆ connect_variables

◆ connected_components

◆ fixed_variables

◆ main_connected_components

◆ variable_adjacency_lists

◆ variable_gates

◆ variables_degree

◆ variables_gate_counts

◆ variables_in_one_gate