Checking the correctness of memories

By Manuel Blum, William S. Evans, P. Gemmell, Sampath Kannan, Moni Naor. 1991

How researchers see this paper

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

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, methodology): “To do so, we apply the technique of embedding in data blocks the names (or references or hashes—these concepts are equivalent here) of other blocks [17, 29, 47, 49, 53] (see also §9).”
Aegis: A Single-Chip Secure Processor (2007, methodology): “[11] addressed the problem of securing various data structures in untrusted memory.”
Software protection and simulation on oblivious RAMs (1996, methodology): “Another application of our technique is for data-structure checking [B, BK, BEGKN ], where assuming that a data-structure has small reliable memory we can guarantee that it was not modified by an adversary.”
Doubly-Efficient zkSNARKs Without Trusted Setup (2018, background): “• Merkle tree proves to V that P knows an assignment to the leaves of a Merkle tree [72] corresponding to a root thatV provides [23].”
Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “Step 2: delegate the machine’s memory The second step is to reduce the footprint of the machineM, by delegating its random-access memory to an untrusted storage, via standardmemory-checking techniques based onMerkle trees [12,19].”
Caches and hash trees for efficient memory integrity verification (2003, background): “One scheme is to use a hash tree rooted in trusted memory [3].”
Fast Batch Verification for Modular Exponentiation and Digital Signatures (1998, methodology): “† Oﬁ-line checking: Our checking can be done oﬁ-line as in [10].”
Proofs of retrievability: theory and implementation (2009, background): “[5], describe a theoretical model that may be viewed as a generalization of PORs.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “• Pantry [37], using Merkle trees, trees [30, 85], offers a circuit of size O(m log m).”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “The principal costs are the setup work and the prover’s work to generate the certificate.”
Efficient memory integrity verification and encryption for secure processors (2003, methodology): “In the figures, a cache block, B, consists of four 128-bit chunks (B[1], B[2], B[3], and B[4]), and a processor holds a counter TIMER in secure on-chip storage.”