Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract

By Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer. 2013

106 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, methodology): “Prior work suggested achieving similar properties via Merkle hash trees [8, 12, 27, 29, 43], but implementations show that this approach increases the degree of the QAP by tens or hundreds per state element [9, 16, 54], whereas with MultiQAPs, the degree increases only by 1.”
Verifying computations with state (2013, background): “Moreover, very recent work [6] spells out a similar idea in the context of a theoretical protocol for verifiable computation that works in the RAM model.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “, uniform circuits); although any circuit can be converted to this form [16, 18], such a transformation incurs 10–1000× blowup in circuit size (which translates to a similar factor increase in the prover’s costs) when compared to equivalent but non-uniform circuits [90]; (4) The verifier in Aurora [”
Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture (2014, methodology): “Other works support more general functionality: [16] rely on nondeterministic routing to support randomaccess machine computations [14]; [27] rely on online memory checking [24, 14] to support accessing untrusted storage from a circuit.”
Verifying computations without reexecuting them (2015, background): “BCGTV [7] compiles programs in C (not just a subset) to an innovative circuit representation [6].”
Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “[19] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, and Eran Tromer.”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, background): “However, a line of recent work indicates that approaches based on IPs and PCPs are closer to practicality than previously thought [22, 47, 48, 53].”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “To verify the integrity of random access memory instructions (such as load and store) we follow [13, 14] and use a pair of execution traces.”
Practical verified computation with streaming interactive proofs (2011, background): “disadvantages of our approach are that it applies only to small-depth computations, since the cost to the verifier grows linearly with circuit depth, and that we cannot support “nondeterministic reductions”, which can be useful for turning high-level programs into small circuits [13, 91].”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “[12] suggested that verification of memory via Merkle hashing can be a useful computational alternative to the information-theoretic use of nondeterministic routing for efficient circuit generators.”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “We refer to such annotations and actions as being exogenous to the constraint formalism (the theoretical term is “non-deterministic input”).”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “This work is part of a theoretical literature that is establishing promising foundations for systems [9, 10].”