libsnark::tbcs_circuit Class Reference

#include <tbcs.hpp>

Public Member Functions
	tbcs_circuit ()
size_t	num_inputs () const
size_t	num_gates () const
size_t	num_wires () const
std::vector< size_t >	wire_depths () const
size_t	depth () const
bool	is_valid () const
bool	is_satisfied (const tbcs_primary_input &primary_input, const tbcs_auxiliary_input &auxiliary_input) const
tbcs_variable_assignment	get_all_wires (const tbcs_primary_input &primary_input, const tbcs_auxiliary_input &auxiliary_input) const
tbcs_variable_assignment	get_all_outputs (const tbcs_primary_input &primary_input, const tbcs_auxiliary_input &auxiliary_input) const
void	add_gate (const tbcs_gate &g)
void	add_gate (const tbcs_gate &g, const std::string &annotation)
bool	operator== (const tbcs_circuit &other) const
void	print () const
void	print_info () const

Public Attributes
size_t	primary_input_size
size_t	auxiliary_input_size
std::vector< tbcs_gate >	gates

Friends
std::ostream &	operator<< (std::ostream &out, const tbcs_circuit &circuit)
std::istream &	operator>> (std::istream &in, tbcs_circuit &circuit)

Detailed Description

A TBCS circuit is a boolean circuit in which every gate has 2 inputs.

A TBCS circuit is satisfied by a TBCS variable assignment if every output evaluates to zero.

NOTE: The 0-th variable (i.e., "x_{0}") always represents the constant 1. Thus, the 0-th variable is not included in num_variables.

Definition at line 133 of file tbcs.hpp.

Constructor & Destructor Documentation

tbcs_circuit()

libsnark::tbcs_circuit::tbcs_circuit ( )

inline

Definition at line 140 of file tbcs.hpp.

: primary_input_size(0), auxiliary_input_size(0) {}

Member Function Documentation

add_gate() [1/2]

void libsnark::tbcs_circuit::add_gate

(

const tbcs_gate &

g

)

Definition at line 264 of file tbcs.cpp.

{
    assert(g.output == num_wires() + 1);
    gates.emplace_back(g);
}

Here is the call graph for this function:

Here is the caller graph for this function:

add_gate() [2/2]

void libsnark::tbcs_circuit::add_gate	(	const tbcs_gate &	g,
		const std::string &	annotation
	)

Definition at line 270 of file tbcs.cpp.

{
    assert(g.output == num_wires() + 1);
    gates.emplace_back(g);
#ifdef DEBUG
    gate_annotations[g.output] = annotation;
#else
    libff::UNUSED(annotation);
#endif
}

Here is the call graph for this function:

depth()

size_t libsnark::tbcs_circuit::depth

(

)

const

Definition at line 182 of file tbcs.cpp.

{
    std::vector<size_t> all_depths = this->wire_depths();
    return *(std::max_element(all_depths.begin(), all_depths.end()));
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_all_outputs()

tbcs_variable_assignment libsnark::tbcs_circuit::get_all_outputs	(	const tbcs_primary_input &	primary_input,
		const tbcs_auxiliary_input &	auxiliary_input
	)		const

Definition at line 232 of file tbcs.cpp.

{
    const tbcs_variable_assignment all_wires =
        get_all_wires(primary_input, auxiliary_input);
    tbcs_variable_assignment all_outputs;
 
    for (auto &g : gates) {
        if (g.is_circuit_output) {
            all_outputs.push_back(all_wires[g.output - 1]);
        }
    }
 
    return all_outputs;
}

Here is the call graph for this function:

Here is the caller graph for this function:

get_all_wires()

tbcs_variable_assignment libsnark::tbcs_circuit::get_all_wires	(	const tbcs_primary_input &	primary_input,
		const tbcs_auxiliary_input &	auxiliary_input
	)		const

Definition at line 211 of file tbcs.cpp.

{
    assert(primary_input.size() == primary_input_size);
    assert(auxiliary_input.size() == auxiliary_input_size);
 
    tbcs_variable_assignment result;
    result.insert(result.end(), primary_input.begin(), primary_input.end());
    result.insert(result.end(), auxiliary_input.begin(), auxiliary_input.end());
 
    assert(result.size() == num_inputs());
 
    for (auto &g : gates) {
        const bool gate_output = g.evaluate(result);
        result.push_back(gate_output);
    }
 
    return result;
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_satisfied()

bool libsnark::tbcs_circuit::is_satisfied	(	const tbcs_primary_input &	primary_input,
		const tbcs_auxiliary_input &	auxiliary_input
	)		const

Definition at line 249 of file tbcs.cpp.

{
    const tbcs_variable_assignment all_outputs =
        get_all_outputs(primary_input, auxiliary_input);
    for (size_t i = 0; i < all_outputs.size(); ++i) {
        if (all_outputs[i]) {
            return false;
        }
    }
 
    return true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

is_valid()

bool libsnark::tbcs_circuit::is_valid

(

)

const

The output wire of gates[i] must have index 1+num_inputs+i. (The '1+' accounts for the index of the constant wire.)

Gates must be topologically sorted.

Definition at line 188 of file tbcs.cpp.

{
    for (size_t i = 0; i < num_gates(); ++i) {
        if (gates[i].output != num_inputs() + i + 1) {
            return false;
        }
 
        if (gates[i].left_wire >= gates[i].output ||
            gates[i].right_wire >= gates[i].output) {
            return false;
        }
    }
 
    return true;
}

Here is the call graph for this function:

num_gates()

size_t libsnark::tbcs_circuit::num_gates

(

)

const

Definition at line 178 of file tbcs.cpp.

{ return gates.size(); }

Here is the caller graph for this function:

num_inputs()

size_t libsnark::tbcs_circuit::num_inputs

(

)

const

Definition at line 173 of file tbcs.cpp.

{
    return primary_input_size + auxiliary_input_size;
}

Here is the caller graph for this function:

num_wires()

size_t libsnark::tbcs_circuit::num_wires

(

)

const

Definition at line 180 of file tbcs.cpp.

{ return num_inputs() + num_gates(); }

Here is the call graph for this function:

Here is the caller graph for this function:

operator==()

bool libsnark::tbcs_circuit::operator==

(

const tbcs_circuit &

other

)

const

Definition at line 281 of file tbcs.cpp.

{
    return (
        this->primary_input_size == other.primary_input_size &&
        this->auxiliary_input_size == other.auxiliary_input_size &&
        this->gates == other.gates);
}

print()

void libsnark::tbcs_circuit::print

(

)

const

Definition at line 311 of file tbcs.cpp.

{
    libff::print_indent();
    printf("General information about the circuit:\n");
    this->print_info();
    libff::print_indent();
    printf("All gates:\n");
    for (size_t i = 0; i < gates.size(); ++i) {
        std::string annotation = "no annotation";
#ifdef DEBUG
        auto it = gate_annotations.find(i);
        if (it != gate_annotations.end()) {
            annotation = it->second;
        }
#endif
        printf("Gate %zu (%s):\n", i, annotation.c_str());
#ifdef DEBUG
        gates[i].print(variable_annotations);
#else
        gates[i].print();
#endif
    }
}

Here is the call graph for this function:

print_info()

void libsnark::tbcs_circuit::print_info

(

)

const

Definition at line 335 of file tbcs.cpp.

{
    libff::print_indent();
    printf("* Number of inputs: %zu\n", this->num_inputs());
    libff::print_indent();
    printf("* Number of gates: %zu\n", this->num_gates());
    libff::print_indent();
    printf("* Number of wires: %zu\n", this->num_wires());
    libff::print_indent();
    printf("* Depth: %zu\n", this->depth());
}

Here is the call graph for this function:

Here is the caller graph for this function:

wire_depths()

std::vector< size_t > libsnark::tbcs_circuit::wire_depths

(

)

const

Definition at line 161 of file tbcs.cpp.

{
    std::vector<size_t> depths(num_inputs(), 1);
 
    for (auto &g : gates) {
        depths.emplace_back(
            std::max(depths[g.left_wire], depths[g.right_wire]) + 1);
    }
 
    return depths;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  out, const tbcs_circuit &  circuit  )

friend

Definition at line 289 of file tbcs.cpp.

{
    out << circuit.primary_input_size << "\n";
    out << circuit.auxiliary_input_size << "\n";
    libff::operator<<(out, circuit.gates);
    out << OUTPUT_NEWLINE;
 
    return out;
}

operator>>

std::istream& operator>> ( std::istream &  in, tbcs_circuit &  circuit  )

friend

Definition at line 299 of file tbcs.cpp.

{
    in >> circuit.primary_input_size;
    libff::consume_newline(in);
    in >> circuit.auxiliary_input_size;
    libff::consume_newline(in);
    libff::operator>>(in, circuit.gates);
    libff::consume_OUTPUT_NEWLINE(in);
 
    return in;
}

Member Data Documentation

auxiliary_input_size

size_t libsnark::tbcs_circuit::auxiliary_input_size

Definition at line 137 of file tbcs.hpp.

gates

std::vector<tbcs_gate> libsnark::tbcs_circuit::gates

Definition at line 138 of file tbcs.hpp.

primary_input_size

size_t libsnark::tbcs_circuit::primary_input_size

Definition at line 136 of file tbcs.hpp.

---

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

• /home/runner/work/libsnark/libsnark/libsnark/relations/circuit_satisfaction_problems/tbcs/tbcs.hpp
• /home/runner/work/libsnark/libsnark/libsnark/relations/circuit_satisfaction_problems/tbcs/tbcs.cpp