Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM

Two Shuffles Make a RAM: Improved Constant Overhead Zero Knowledge RAM

Speakers: Yibin Yang; David Heath

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=jVdFnHjBurQ

Overview

This talk, presented by Yibin Yang in collaboration with David Heath from UI, introduces a novel and highly efficient construction for Zero-Knowledge Random Access Memory (ZK-RAM). ZK-RAM is a critical primitive that enables general-purpose computation within zero-knowledge proofs, moving beyond the limitations of purely circuit-based proofs. While prior work had achieved asymptotically optimal constant-overhead ZK-RAM, this research significantly reduces the constant factor associated with the overhead, making ZK-RAM substantially more practical for real-world applications.

The core contribution is a construction that achieves an amortized constant cost per memory access, leveraging the power of permutation proofs. The speaker emphasizes that their method effectively reduces the complex problem of building ZK-RAM to just two fundamental permutation proofs. This not only simplifies the underlying mechanism but also translates directly into a smaller circuit size, which is a paramount concern for the efficiency and scalability of zero-knowledge proof systems.

The practical implications of this work are profound, especially for emerging applications like privacy-preserving machine learning. By providing a ZK-RAM construction with a hidden constant of merely 10 nonlinear gates per access, the researchers enable more complex and memory-intensive computations to be proven in zero-knowledge with unprecedented efficiency. This advancement pushes the boundaries of what is feasible with current zero-knowledge technologies, paving the way for a new generation of privacy-preserving protocols.

Background

▶ Watch: Introduction to Zero-Knowledge Proofs (ZKPs) (0:00)

Zero-Knowledge Proofs (ZKPs), first introduced by Goldwasser, Micali, and Rackoff in 1985, are cryptographic protocols that allow a prover to convince a verifier that a statement is true, without revealing any information beyond the truth of the statement itself. ZKPs are characterized by three properties: completeness (a truthful prover can always convince a verifier), soundness (a malicious prover cannot convince a verifier of a false statement), and zero-knowledge (the verifier learns nothing beyond the truth of the statement).

While ZKPs are powerful, building generic ZKPs for arbitrary computations often involves compiling the computation into a circuit composed of basic gates like addition and multiplication. This approach works well for computations that naturally map to circuits, but it becomes highly inefficient for operations involving Random Access Memory (RAM). In a traditional circuit model, accessing an arbitrary memory location requires traversing the entire memory or using complex, costly conditional logic, leading to prohibitive circuit sizes.

The need for efficient ZK-RAM arises from the desire to prove general-purpose computations, such as those found in CPU execution, databases, or complex algorithms like machine learning inference, in zero-knowledge. A ZK-RAM essentially provides two fundamental gates:

• Load: Takes an index I and outputs the value stored at that position.
• Store: Takes an index I and a new value X, updating the memory at position I.

Crucially, a subsequent load operation at I must retrieve the X that was most recently stored at I. The paper extends this to a universal "assess" gate that can perform either read or write based on a single bit input.

The cost of ZK-RAM constructions is typically measured by the number of nonlinear gates (multiplication and input gates), as linear gates are often "almost free" in many ZKP systems. The size of the RAM is denoted by n (number of slots), and the number of accesses by T. A naive solution for ZK-RAM, involving a linear scan of memory for each access, would result in O(T * n) nonlinear gates, which is clearly impractical for large n or T.

Prior research has made significant strides in achieving asymptotically optimal ZK-RAM. Notably, works by Frish et al. (CCS '21) and Deshpande et al. (SC '22) achieved an asymptotic complexity of O(T + n) nonlinear gates. This represents a major improvement over the naive approach, as it means the cost per access can be amortized to a constant when T is sufficiently large (i.e., T = Ω(n)). However, the constant factor hidden within this asymptotic notation can still be substantial, limiting practical applicability. This talk focuses precisely on improving this hidden constant.

Key Findings

▶ Watch: Our main result: T+N gates, 'two shuffles' (4:00)

The central finding of this research is a new construction for Zero-Knowledge RAM that achieves the optimal O(T + n) asymptotic complexity while drastically reducing the constant factor overhead. Specifically, the proposed ZK-RAM construction requires an amortized cost of approximately 10 nonlinear gates per memory access when the number of accesses T is greater than or equal to the memory size n.

This is a critical improvement over prior art because, while the asymptotic complexity was already known, the practical utility of ZK-RAM is heavily dependent on the actual number of gates required. A smaller constant factor directly translates to smaller circuit sizes, faster proof generation, and quicker verification times, making ZK-RAM much more viable for real-world deployment. The speaker emphasizes that this improvement is not in implementation details but in the fundamental size of the underlying circuit itself.

The core insight enabling this efficiency gain is the reduction of the ZK-RAM problem to two permutation proofs. A permutation proof is a highly efficient cryptographic primitive that allows a prover to demonstrate that one set of elements is a permutation of another set, without revealing the permutation itself. By cleverly encoding memory operations and their history into sets that can be related via permutations, the authors achieve a constant-overhead ZK-RAM.

This elegant reduction simplifies the construction significantly and provides a clear, intuitive framework for understanding the underlying security guarantees. The construction's efficiency, particularly the small hidden constant, makes it a strong candidate for integration into existing ZKP systems, especially those designed for complex computations where memory access patterns are crucial, such as verifiable machine learning inference, as highlighted by the speaker with a reference to a related work presented at the same conference.

Technical Deep Dive

▶ Watch: Key improvement: smaller constant factor over prior work (4:45)

The technical foundation of this ZK-RAM construction relies heavily on permutation proofs. A standard permutation proof aims to allow a prover to demonstrate that a set of wires X (of length n) can be permuted to form another set of wires Y (also of length n). The common technique for this involves polynomial identity testing. If X can be permuted to Y, then two polynomials, P_X(z) = Π (z - x_i) and P_Y(z) = Π (z - y_i), will be identical. More practically, a related approach uses product polynomials: if X permutes to Y, then Π (α - x_i) must equal Π (α - y_i) for a random challenge α issued by the verifier. The soundness of this check relies on the Schwartz-Zippel lemma. This type of permutation proof is highly efficient, requiring only 2n - 2 multiplication gates to compute the two products. It can also be generalized to handle vectors of tuples as elements, not just single values.

The speaker then illustrates how a single permutation proof can be used to construct a Read-Only Memory (ROM). The goal for a ROM is to support only the load gate, fetching a value X_I at index I. For simplicity, the example uses a small public table with three elements: (x_0, x_1, x_2). The key insight is that while the prover knows the memory's contents and can directly input X_I, a mechanism is needed to prevent cheating.

The solution involves maintaining entries as triples: (index, value, version). The version acts as a counter, incrementing each time an entry at a specific index is accessed. Two arrays are maintained: Y_write and Y_read.

1. Setup Phase: The Y_write array is initialized with the initial state of the memory. For the example, Y_write would contain (0, x_0, 0), (1, x_1, 0), (2, x_2, 0). These represent the "available" memory units.
2. Access Phase (Load): When a load operation for index I is performed:

• The prover provides the value Y (expected X_I) and the latest version V of that index.
• An entry (I, Y, V) is added to the Y_read array, effectively logging the read operation.
• An entry (I, Y, V+1) is added to the Y_write array. This creates a "new version" of that memory slot, making the old one "consumed."
• The entry (I, X_I, V) that was consumed from Y_write is effectively matched by the entry (I, Y, V) in Y_read.

1. Tear-down Phase: After all T accesses, the prover reveals the final state of all memory slots, effectively adding the latest versions of each (index, value, version) triple to Y_write.

The crucial check is then performed: a permutation proof is used to show that the Y_read array is a permutation of the Y_write array. If they are permutations of each other, it implies that every entry consumed from Y_write was correctly accounted for in Y_read, and every entry created in Y_write was a valid update. For the ROM, this construction costs 2n + 2T - 2 multiplication gates.

The speaker provides an intuitive explanation for the soundness of this ROM construction. If Y_read permutes to Y_write, it means that for every (index, value, version) tuple in Y_read, there's a corresponding tuple in Y_write, and vice versa. An honest read operation (I, X_I, V) consumes (I, X_I, V) from Y_write and adds (I, X_I, V+1) to Y_write, while (I, X_I, V) is added to Y_read. The (I, X_I, V) in Y_read cancels out the original (I, X_I, V) in Y_write (in the permutation check sense), and the (I, X_I, V+1) remains in Y_write to be matched by a future read or the tear-down phase. This ensures that the values read (Y) must match the actual values (X_I) in the memory.

However, a key limitation of this ROM construction is that it inherently allows "reading from the future." Because the version number simply increments, a malicious prover could claim to read (I, Y, V_future) and then later in the sequence, actually store Y at index I with version V_future. While this doesn't break the semantics of a ROM (the value Y is consistent throughout), it would break the soundness of a full ZK-RAM where values can change arbitrarily.

To upgrade this ROM to a full ZK-RAM, the "read from the future" problem must be prevented. The speaker provides a hint: instead of simple version numbers, timestamps are used. The prover must then provide an additional proof that the time difference between the read operation and the last write operation for that specific index is positive, meaning it reads from the past. This prevents the prover from "pre-committing" to a future value. The full details of this timestamp-based mechanism, which involves a second permutation proof and careful handling of time values, are left to the paper but complete the "two shuffles" mentioned in the title. The amortized cost per access for the full ZK-RAM construction is stated as approximately two inputs and two multiplication gates, which translates to the constant of 10 mentioned earlier when considering the full complexity.

Demo / Proof of Concept

▶ Watch: Explaining the permutation proof primitive (6:00)

While the talk did not feature a live demonstration or a specific proof-of-concept implementation walkthrough, the speaker did mention that the Read-Only Memory (ROM) construction was implemented using a Volley-based setting. This indicates that the theoretical construction has been translated into a practical system, allowing for validation of its performance characteristics. The "real numbers" referred to by the speaker likely stem from this implementation and its asymptotic analysis, confirming the small constant factor achieved in practice.

Defensive Implications

▶ Watch: Applying permutation proof to build read-only memory (7:00)

This research primarily provides advancements for developers and researchers building zero-knowledge proof systems and applications, rather than offering direct defensive measures for end-users or traditional IT security. The implications are foundational and enable stronger security guarantees and broader applicability for ZKP technologies:

1. Enhanced Efficiency for ZKP Applications: By significantly reducing the constant overhead of ZK-RAM, this work makes it more practical to build ZKP systems for complex, memory-intensive computations. This includes applications like privacy-preserving machine learning inference, verifiable smart contracts that need to interact with state, or proving correct execution of general-purpose programs (e.g., CPU execution) in a zero-knowledge context.
2. Broader Adoption of ZKPs: The improved efficiency removes a significant bottleneck for ZKP deployment. When memory access costs are low, developers can design more sophisticated ZKP applications without incurring prohibitive proof generation times or verification costs. This can lead to broader adoption of ZKPs in areas requiring both privacy and verifiability, such as secure multi-party computation, verifiable cloud computing, and decentralized finance.
3. Foundation for Future Research: This work provides a new state-of-the-art ZK-RAM construction that can serve as a building block for subsequent research in ZKP compilers, hardware acceleration for ZKPs, and new ZKP protocols. It allows researchers to focus on other challenges, assuming an efficient ZK-RAM is available.
4. Reduced Proof Size and Verification Time: Directly, a smaller circuit size (due to the reduced constant factor) translates to smaller proof sizes and faster verification for applications that heavily rely on ZK-RAM. This is crucial for environments with limited bandwidth or computational resources, such as blockchain networks.

In essence, this work empowers defenders (or those building defensive tools) by providing more efficient cryptographic primitives, allowing them to construct more robust, private, and verifiable systems across various domains.

Key Takeaways

• ZK-RAM is Essential for General ZKP: Zero-Knowledge Random Access Memory is a critical primitive for enabling general-purpose computations, beyond simple circuits, within zero-knowledge proofs, opening doors for complex applications like verifiable machine learning.
• Constant Overhead with Drastically Improved Constant Factor: The new construction achieves an asymptotically optimal O(T+N) complexity (where T is accesses, N is memory size) with a significantly reduced hidden constant of approximately 10 nonlinear gates per amortized access.
• Two Permutation Proofs are Key: The core innovation lies in reducing the ZK-RAM problem to two highly efficient permutation proofs, simplifying the construction and improving efficiency.
• Read-Only Memory (ROM) Uses One Shuffle: A basic Read-Only Memory can be built using one permutation proof by tracking (index, value, version) triples and ensuring Y_read is a permutation of Y_write.
• Full ZK-RAM Prevents "Read from Future": To extend ROM to full ZK-RAM, the construction must prevent a prover from "reading from the future." This is achieved by using timestamps and proving that read operations occur after write operations.
• Significant Practical Impact: This work makes ZK-RAM constructions more practical and efficient, fostering the development of more complex and privacy-preserving applications, particularly in areas like verifiable machine learning and other memory-intensive ZKP use cases.

About the Speaker(s)

Yibin Yang is a researcher who presented this work, indicating his significant contribution to the field of zero-knowledge proofs. The talk was a joint effort with David Heath, affiliated with the University of Illinois (UI). Together, their research focuses on advancing the efficiency and practicality of fundamental cryptographic primitives like Zero-Knowledge RAM, pushing the boundaries of what is achievable in privacy-preserving computation.