ram_universal_gadget.hpp File Reference

#include <libsnark/gadgetlib1/gadgets/routing/as_waksman_routing_gadget.hpp>
#include <libsnark/reductions/ram_to_r1cs/gadgets/memory_checker_gadget.hpp>
#include <libsnark/reductions/ram_to_r1cs/gadgets/trace_lines.hpp>
#include <libsnark/relations/ram_computations/rams/ram_params.hpp>
#include <libsnark/reductions/ram_to_r1cs/gadgets/ram_universal_gadget.tcc>

Include dependency graph for ram_universal_gadget.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	libsnark::ram_universal_gadget< ramT >

Namespaces
	libsnark

Detailed Description

Declaration of interfaces for ram_universal_gadget.

Given bounds on a RAM computation size (program size bound, primary input size bound, and time bound), the "RAM universal gadget" checks the correct execution of any RAM computation that fits the bounds.

The implementation follows, extends, and optimizes the approach described in [BCTV14] (itself building on [BCGTV13]). The code is parameterized by the template parameter ramT, in order to support any RAM that fits certain abstract interfaces.

Roughly, the gadget has three main components:

• For each time step, a copy of a execution checker (which is the RAM CPU checker).
• For each time step, a copy of a memory checker (which verifies memory consistency between two 'memory lines' that are adjacent in a memory sort).
• A single routing network (specifically, an arbitrary-size Waksman network), which is used check that memory accesses are permutated according to some permutation.

References:

[BCGTV13]: "SNARKs for C: verifying program executions succinctly and in zero knowledge", Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza, CRYPTO 2014, http://eprint.iacr.org/2013/507

[BCTV14]: "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture", Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, USENIX Security 2014, http://eprint.iacr.org/2013/879

Author

This file is part of libsnark, developed by SCIPR Lab and contributors (see AUTHORS).

Copyright

MIT license (see LICENSE file)

Definition in file ram_universal_gadget.hpp.