Boosting SNARKs and Rate-1 Barrier in Arguments of Knowledge

Recall that a $\delta$-mild SNARK only guarantees that the proof size, $|\pi |$, is smaller than $m$, but it does not say anything about other parameters or algorithms. Thus, it is possible that CRS size and/or the verifier’s running time is greater than $|\omega |$, or the time taken to check $𝒞(x,\omega )=1$. In such scenarios, we cannot efficiently generate the full CRS. This is because, under ${\mathrm{𝖼𝗋𝗌}}_{i+1}$, the prover proves that it has a mild SNARK proof ${\pi }_i$ for $x$ w.r.t. ${\mathrm{𝖼𝗋𝗌}}_i$. Thus, the ${(i+1)}^{th}$ language membership circuit (for ${\mathrm{𝖼𝗋𝗌}}_{i+1}$) is the $i^{th}$ verification circuit (w.r.t. to ${\mathrm{𝖼𝗋𝗌}}_i$), and hence $|{\mathrm{𝖼𝗋𝗌}}_i|$ would grow with $|𝒞|,m,n$ and super-polynomially with $i$.

Recall that we already discussed how one can generically reduce the CRS size (as well as time needed to compute it) to only grow poly-logarithmically with $|𝒞|$. Isn’t that enough to ensure the above template works? Unfortunately, the answer is no! This is because RAM delegation only brings down CRS size from $\mathrm{𝗉𝗈𝗅𝗒}(\lambda ,|𝒞|,n,m)$ to $\mathrm{𝗉𝗈𝗅𝗒}(\lambda ,\log |𝒞|,n,m)$. But, for full-succinctness, our goal is to have the CRS size (as well as verification time) to grow only poly-logarithmically with $m$. Thus, the question is how can we compose mild SNARKs such that verification time and CRS size does not grow with $m$ or $n$?

Our idea is to switch an iterative straightline composition of SNARKs with an iterative, but tree-based, composition of SNARKs. Broadly speaking, the intuition is similar to how composing hash functions in a tree-based fashion [33] is more efficient than a straightline iterated hashing approach [34, 17].A similar issue was faced by Bitansky et al. [7] in the context of designing Proof Carrying Data (PCD) [13] and complexity-preserving SNARKs. Although Bitansky et al. assumed existence of a fully-succinct SNARK (which is what we want to design here), the underlying technical approach is more general. Our intuition is that a similar approach is quite meaningful for boosting non-trivial SNARKs.

In order to correctly implement such an idea, we need to break down the entire computation needed to verify $x\in ℒ$, given $\omega$, into smaller pieces. Otherwise, tree-based composition will not give desired amount of succinctness/compression. Basically, by interpreting the entire computation of $𝒞(x,\omega )=1$ as a step-by-step computation in the RAM model, we can ensure that the size of computation for which we will use mild SNARKs is of fixed size. That is, let ${\mathrm{𝖼𝗇𝖿𝗀}}_1,\mathrm{\dots },{\mathrm{𝖼𝗇𝖿𝗀}}_T$ be the configuration of the RAM machine, corresponding to $𝒞(x,\omega )=1$, where $T=\mathrm{𝗉𝗈𝗅𝗒}(\lambda )$ is the total running time. (A RAM machine configuration corresponds to the RAM memory, program state, and machine head at given time step.)

A prover runs a mild SNARK prover, at the base level of the tree, to prove that each step of the computation is correctly performed, i.e. ${\mathrm{𝖼𝗇𝖿𝗀}}_i\to {\mathrm{𝖼𝗇𝖿𝗀}}_{i+1}$ (here by “$\to$” we denote one RAM computation step). Further, it accumulates these proofs iteratively (as we go up the tree) by running a mild SNARK prover to prove that two configurations ${\mathrm{𝖼𝗇𝖿𝗀}}_i,{\mathrm{𝖼𝗇𝖿𝗀}}_j$ are consistent. By consistent, we mean that we can go from ${\mathrm{𝖼𝗇𝖿𝗀}}_i\to {\mathrm{𝖼𝗇𝖿𝗀}}_j$ after $(j-i)$ RAM computation steps. The intuition is that base level (i.e., level 0) we prove the configurations to be adjacent (i.e., 1 step apart), while for next level (i.e., level 1) we prove ${\mathrm{𝖼𝗇𝖿𝗀}}_i,{\mathrm{𝖼𝗇𝖿𝗀}}_j$ are $2$ steps apart, and so on. Thus, at level $i$, we prove the configurations to be $2^i$ steps apart. By continuously composing SNARKs for such step-by-step computations in a tree-based fashion, we can get around the succinctness problem. This is because the instance and witness size, for each mild SNARK proof computation, are always of fixed polynomial size, independent of $n,m,T$ as well as the level $i$. Thus, the CRS size doesn’t grow anymore, and the resulting SNARK will be fully-succinct.

Unfortunately, the above process brings up a major bottleneck. The problem is how to prove (knowledge) soundness of the above design? Soundness only states that ${\pi }_0$ (proof at the base level) is hard to compute if $x\notin ℒ$. But, it does not say any of the iteratively computed proofs are hard to compute! Thus, we cannot rely on standard soundness, but need to use knowledge soundness. But this would mean we have to recursively run the extractor $\log T$ many times. Unfortunately, such a recursive extractor would not run in polynomial time, since the depth of the tree is $\log T=O(\log \lambda )$.

While the above feels a pretty big problem, this can be easily resolved by simply increasing the arity of the tree (from $2$ to $\lambda$). That is, rather than proving the configurations to be $2^i$ steps apart (at level $i$), we will prove configurations to be ${\lambda }^i$ steps apart. With this change, the depth of the SNARK tree will be constant, ${\log }_{\lambda }T=O(1)$ (for any polynomial time computation). Thus, we can perform recursive extraction from any accepting proof, given a poly-time cheating prover. With this modification, we provide a more detailed sketch.

From here on, we assume we have a description of a RAM program $ℛ$ that verifies validity of instance-witness pair $(x,\omega )$, rather than a fixed circuit $𝒞$. $ℛ$ checks that validity of witness for an instance w.r.t. $ℒ$.

The prover starts by computing all configurations for every computation step, and hashing down just the RAM memory portion for each step using a Merkle hash tree [33]. At the bottom level, the instance at each node consists of two consecutive pseudo-configurations $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}}),({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })$, where $\rho$ is the memory digest, $\mathrm{𝗌𝗍𝖺𝗍𝖾}$ is the program state, and $i_{\mathrm{𝗋𝖾𝖺𝖽}}$ is the index of the bit read during that step (i.e., machine head location). We call this pseudo-configuration, because it only contains the digest of the memory instead of full memory. The witness includes the local read/write bit and the write index $b_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$, which can be used to verify the transition between the two configurations. It also includes the Merkle tree openings $u_{\mathrm{𝗋𝖾𝖺𝖽}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$ for the read/write bits w.r.t. memory digest. Given the above, the language for the nodes at bottom level is as follows:

Instance: $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})$, $({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })$.
Witness: $b_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},u_{\mathrm{𝗋𝖾𝖺𝖽}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$.
Check if the transition is valid, and the hash openings $u_{\mathrm{𝗋𝖾𝖺𝖽}}$ and $u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$, along with the memory hash values $\rho ,{\rho }^{\prime }$, the bits $b_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$, and memory indexes $i_{\mathrm{𝗋𝖾𝖺𝖽}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$ are all consistent.

At all other levels, each node aggregates $\lambda$ nodes from the lower level (see Figure 1). The instance contains just two pseudo-configurations: the initial and final pseudo-configuration out of the $\lambda$ nodes. And, the witness includes all pseudo-configurations and their corresponding SNARK proofs of transitions. Basically, the prover proves that it knows a valid sequence of transitions between the two pseudo-configurations. Below, we describe the language for intermediate levels informally:

Instance: $({\rho }_1,{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_1,i_{1,\mathrm{𝗋𝖾𝖺𝖽}})$, $({\rho }_{\lambda +1},{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_{\lambda +1},i_{\lambda +1,\mathrm{𝗋𝖾𝖺𝖽}})$.
Witness: ${\{{\pi }_j\}}_{j\in [\lambda ]}$, ${\{({\rho }_j,{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_j,i_{j,\mathrm{𝗋𝖾𝖺𝖽}})\}}_{j\in [\lambda +1]}$.
Check if the mild SNARK verifier accepts every pair of instance $(({\rho }_j,{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_j,i_{j,\mathrm{𝗋𝖾𝖺𝖽}}),({\rho }_{j+1},{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_{j+1},i_{j+1,\mathrm{𝗋𝖾𝖺𝖽}}))$ and proof ${\pi }_j$ for $j\in [\lambda ]$.

We highlight that all above languages have succinct description since the instance/witness sizes as well as size of the associated membership circuit for each language has a fixed polynomial size. Thus, this process can be iteratively carried out till the root of the tree. And, it ensures each individual CRS as well as the final proof size to be fully-succinct, i.e. independent of $n,m,T$.

Lastly, we can design a recursive extractor efficiently to prove knowledge soundness. The extractor first extracts a valid witness for the root node, and then it considers the extraction procedure that computes a valid witness for the root node as an attacker, and continues the recursive extraction procedure. Overall, by combining all the witnesses at the bottom level (leaves of the tree), the extractor can reconstruct a valid witness that satisfies the RAM computation. (Technically, the security argument also relies on the fact that the Merkle tree is secure, but we ignore that detail for the sake of simplicity.) Clearly, the running time of extractor faces a polynomial blow-up across each level of the tree (as the $i^{th}$ level extractor is treated as an attacker for ${(i-1)}^{th}$ level). However, as we discussed earlier, by designing trees with arity-$\lambda$, the height of the SNARK tree remains constant, and as a result, the extractor’s runtime is polynomially bounded. Our compiler is formally presented in Section 3.

Recently, Kalai et al. [28] designed a generic compiler to boost any non-trivial (flexible) RAM SNARGs to fully-succinct (flexible) RAM SNARGs, under a very mild assumption of rate-1 string OT. Moreover, they showed a near equivalence between such flexible RAM SNARGs and batch arguments (BARGs) for $\mathrm{𝐍𝐏}$. One can view their result as a generic compiler for boosting any non-trivial SNARK for $𝐏$ to a fully-succinct SNARK for $𝐏$⁵⁵5Recall SNARKs and SNARGs are the same object for $𝐏$, since there is no witness.. Our work gives a matching boosting result for the non-deterministic class $\mathrm{𝐍𝐏}$.

Proof Carrying Data (PCD) [13] generalizes SNARGs to distributed computation. Their goal is for a group of participants in a distributed computation to create proofs of integrity and legitimacy for their respective (local) computations that can be combined to create a global proof of integrity and legitimacy of the entire distributed computation. PCDs are a significant generalization of Incrementally Verifiable Computations (IVC) [40]. IVCs can be simply viewed as PCD for straightline incremental computations (i.e., path graphs).

In a beautiful work, Bitansky et al. [7] developed new approaches for recursively composing SNARKs, and provided new techniques for constructing and using PCD. One of their central results was development of a bootstrapping mechanism for fully-succinct SNARKs with “expensive” preprocessing to design fully-succinct complexity-preserving SNARKs. By complexity-preserving, they meant that the prover’s time/space complexity is essentially the same as that required for classical $\mathrm{𝐍𝐏}$ verification.

On a technical level, [7] relied on an elegant technique to recursively compose SNARKs over a tree-like structure. As discussed in the overview, our approach builds on their composition techniques. Apart from studying different problems, the key differences between our works are that we show that recursive composition works even for non-trivial SNARKs, while they relied on fully-succinct SNARKs. Moreover, a non-trivial SNARK verifier can be as large as some polynomial in the description of the classical $\mathrm{𝐍𝐏}$ verification circuit, thus we had to rely on additional techniques such as RAM delegation, while this was needed by Bitansky et al. since they assumed full-succinct SNARKs.

Interestingly, by combining our results with [7], we obtain that any $\delta$-mild SNARK, with either a fast extractor or $\delta ={\lambda }^{ϵ}$, is sufficient to design complexity-preserving SNARKs and PCDs.

Our work leaves a lot of interesting questions for further research. We list out some of them below.

1. 1.

   Our appraoch crucially relies on knowledge soundness. A great problem is can we boost non-trivial SNARGs, without or with very weak extractability?

2. 2.

   We also need SNARKs to be adaptively sound. Another great question is to similar compilers assuming non-adapative soundness.

3. 3.

   To shorten the CRS size, we need to rely on efficient RAM delegation. Can this be avoided, or could we instead reduce to simpler assumptions such as CRHFs?

4. 4.

   Do there exist such boosting SNARK results for other classes, other than $𝐏$ [28] and $\mathrm{𝐍𝐏}$ (this work)?

5. 5.

   Our fully-succinct SNARKs have “fixed” multiplicative overhead in the time/space needed for computing the proof, compared to classical $\mathrm{𝐍𝐏}$ verification. Can we make this optimal and only incur a “fixed” additive overhead?

Answering above questions will give us more insight in the study of SNARKs and related proof systems.

The rest of the paper is organized as follows. First, we describe our main boosting compiler for mild SNARKs (with short CRS) in Section 3. Later in Section 4, we show to boost even milder SNARKs, and finally, we describe how to use RAM delegation to shorten CRS in Section 5. Due to space constraints, preliminaries can be found in the full version.

We rely on a specialized notation that we call Composite Hash Trees. One may consider Composite Hash Tree as a set of $k$ Hash Trees, each assigned a section of input. For example, the hash value $h\leftarrow \mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},x)$ consists a number of $k$ hash values $h=(h_1,\mathrm{\dots },h_k)$ where each value corresponds to one section of $x$. As long as $k$ is a constant number, the efficiency and soundness properties all maintain from the original Hash Tree. The desired property from Composite Hash Tree is that the reading, opening, and writing at the $i$-th section of string $x$ only depends on and affects $h_i$. Composite Hash Tree overloads the syntax of Hash Tree, except for the following:

$\mathrm{𝖲𝖾𝗍𝗎𝗉}(1^{\lambda },N_1,\mathrm{\dots },N_k)\to \mathrm{𝗁𝗄}.$

The setup algorithm is modified to accept multiple inputs $N_1,\mathrm{\dots },N_k$. The size of hash input is ${\mathrm{\Sigma }}_{i=1}^k{N}_i$. Input is considered as a number of $k$ continuous segments, where the $i$-th segment is of size $N_i$. It also sets hash key $\mathrm{𝗁𝗄}$ as a sequence of of $k$ independent hash keys: $\mathrm{𝗁𝗄}=({\mathrm{𝗁𝗄}}_1,\mathrm{\dots },{\mathrm{𝗁𝗄}}_k)$.

We define the additional property of completeness: For every $\lambda ,k,N_1,\mathrm{\dots },N_k\in \mathbb{N}$, $x^{(i)}\in {\{0,1\}}^{N_i}$ for all $i\in [k]$, $x=(x^{(1)},\mathrm{\dots },x^{(k)})$, and $\mathrm{𝗁𝗄}=({\mathrm{𝗁𝗄}}_1,\mathrm{\dots },{\mathrm{𝗁𝗄}}_k)\leftarrow \mathrm{𝖲𝖾𝗍𝗎𝗉}(1^{\lambda },N_1,\mathrm{\dots },N_k)$,

For the rest of this section, we only rely on such Composite Hash Trees.

We rely on $\delta$-mild SNARK $\mathrm{\Gamma }=(\mathrm{\Gamma }.\mathrm{𝖲𝖾𝗍𝗎𝗉},\mathrm{\Gamma }.\mathrm{𝖯𝗋𝗈𝗏𝖾},\mathrm{\Gamma }.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒})$ for $\delta \ge 2\lambda$, and composite hash tree $𝖧=(𝖧.\mathrm{𝖲𝖾𝗍𝗎𝗉},𝖧.\mathrm{𝖧𝖺𝗌𝗁},𝖧.\mathrm{𝖮𝗉𝖾𝗇},𝖧.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒},𝖧.\mathrm{𝖶𝗋𝗂𝗍𝖾},𝖧.\mathrm{𝖴𝗉𝖽𝖺𝗍𝖾})$. Below is our design.

$\mathrm{𝖲𝖾𝗍𝗎𝗉}(1^{\lambda },ℛ,n,m,T,k)\to \mathrm{𝖼𝗋𝗌}.$

The setup algorithm follows these steps:

1. RAM machine $ℛ$ is as the following: $ℛ$ takes as input $(x,\omega )$, running time of $ℛ$ is $T$, and memory usage is capped at $k$. Size of input $(x,\omega )$ is $n+m$.

2. We then specify $\mathrm{\ell }$ as $\mathrm{\ell }=\lceil \frac{\log T}{\log \lambda }\rceil$. We also specify the state transformation circuit of $ℛ$ as ${𝒞}^{\mathrm{𝖱𝖠𝖬}}$ and the memory as $M=(M_1,\mathrm{\dots },M_k)$. It sets

$$\mathrm{𝗁𝗄}\leftarrow 𝖧.\mathrm{𝖲𝖾𝗍𝗎𝗉}(1^{\lambda },n,m,k-n-m).$$

The intuition is that the memory is splitted into three sections where the first two sections are used to record the input $x,\omega$ and the last section is used as a working tape. Then under the hash key $\mathrm{𝗁𝗄}=({\mathrm{𝗁𝗄}}_1,{\mathrm{𝗁𝗄}}_2,{\mathrm{𝗁𝗄}}_3)$, hash value $h$ consists of three independent values $(h_1,h_2,h_3)$.

3. It generates a number of $\mathrm{\ell }+1$ common reference strings: For all $i\in \{0,\mathrm{\dots },\mathrm{\ell }\}$,

$${\mathrm{𝖼𝗋𝗌}}_i\leftarrow \mathrm{\Gamma }.\mathrm{𝖲𝖾𝗍𝗎𝗉}(1^{\lambda },1^{n_i},1^{m_i},{𝒞}_i),$$

where ${𝒞}_i$ is defined as the following, and $n_i$ is the instance size, $m_i$ is the witness size for ${𝒞}_i$.

4. It outputs $\mathrm{𝖼𝗋𝗌}=(\mathrm{𝗁𝗄},{\mathrm{𝖼𝗋𝗌}}_0,\mathrm{\dots },{\mathrm{𝖼𝗋𝗌}}_{\mathrm{\ell }})$.

Circuit ${𝒞}_0$ Instance: $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})$, $({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })$.
Witness: $b_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},u_{\mathrm{𝗋𝖾𝖺𝖽}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$.
Hardwired: ${𝒞}^{\mathrm{𝖱𝖠𝖬}}$. Output: ${𝒞}_0$ outputs $1$ if and only if the followings are satisfied: $\mathrm{■}$ ${𝒞}^{\mathrm{𝖱𝖠𝖬}}(\mathrm{𝗌𝗍𝖺𝗍𝖾},b_{\mathrm{𝗋𝖾𝖺𝖽}})=({\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime },i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}})$. $\mathrm{■}$ $𝖧.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}(\mathrm{𝗁𝗄},\rho ,i_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗋𝖾𝖺𝖽}},u_{\mathrm{𝗋𝖾𝖺𝖽}})=1$. $\mathrm{■}$ $𝖧.\mathrm{𝖶𝗋𝗂𝗍𝖾}(\mathrm{𝗁𝗄},\rho ,i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}})={\rho }^{\prime }$.

For $i\in \{1,\mathrm{\dots },\mathrm{\ell }\}$:

Circuit ${𝒞}_i$ Instance: $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})$, $({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })$.
Witness: ${\{{\pi }_j\}}_{j\in \lambda }$, ${\{{(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_j\}}_{j\in [\lambda +1]}$.
Hardwired: ${\mathrm{𝖼𝗋𝗌}}_{i-1}$.
Output: ${𝒞}_i$ outputs $1$ if and only if: $\mathrm{■}$ $\mathrm{\Gamma }.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}({\mathrm{𝖼𝗋𝗌}}_{i-1},({(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_j,{(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_{j+1}),{\pi }_j)=1$, for all $j\in \left[\lambda \right]$. $\mathrm{■}$ $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})=({\rho }_1,{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_1,i_1)$ $\mathrm{■}$ $({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })=({\rho }_{\lambda +1},{\mathrm{𝗌𝗍𝖺𝗍𝖾}}_{\lambda +1},i_{\lambda +1})$

$\mathrm{𝖯𝗋𝗈𝗏𝖾}(\mathrm{𝖼𝗋𝗌},x,\omega )\to \pi$

. The prover algorithm follows these steps:

1. 1.

   It simulates $ℛ$ step by step. Previously we specified the state transformation circuit of $ℛ$ as ${𝒞}^{\mathrm{𝖱𝖠𝖬}}$ and the memory as $M$. Since $ℛ$ has a maximum number of $T$ steps, the simulation process involves a total number of $T+1$ states. Recall definition of RAM machine where for each step of computation, the original local state $\mathrm{𝗌𝗍𝖺𝗍𝖾}$ transforms into a new state ${\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime }$. Such transition involves an index to read $i_{\mathrm{𝗋𝖾𝖺𝖽}}$, the bit $b_{\mathrm{𝗋𝖾𝖺𝖽}}$ at index $i_{\mathrm{𝗋𝖾𝖺𝖽}}$. It sets $\rho =𝖧.\mathrm{𝖧𝖺𝗌𝗁}(\mathrm{𝗁𝗄},M)$ where $M=(M_1,\mathrm{\dots },M_k)$ represents the whole memory at such state. When reading the bit $b_{\mathrm{𝗋𝖾𝖺𝖽}}$ at index $i_{\mathrm{𝗋𝖾𝖺𝖽}}$, it simultaneously computes the opening $u_{\mathrm{𝗋𝖾𝖺𝖽}}=𝖧.\mathrm{𝖮𝗉𝖾𝗇}(\mathrm{𝗁𝗄},M,i_{\mathrm{𝗋𝖾𝖺𝖽}})$. Then state transformation circuit ${𝒞}^{\mathrm{𝖱𝖠𝖬}}$ takes $\mathrm{𝗌𝗍𝖺𝗍𝖾}$ and $b_{\mathrm{𝗋𝖾𝖺𝖽}}$ as input and outputs ${\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime },i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$. It updates the bit at index $i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$, setting $M_{i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}}^{\prime }$ as $b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}$, and $M_i^{\prime }$ as $M_i$ for all $i\in [k]\setminus \{i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}}\}$. It sets updated memory $M^{\prime }=(M_1^{\prime },\mathrm{\dots },M_k^{\prime })$. Next, it obtains updated hash value as ${\rho }^{\prime }=𝖧.\mathrm{𝖶𝗋𝗂𝗍𝖾}(\mathrm{𝗁𝗄},h,b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}})$.

   It records ${(\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗋𝖾𝖺𝖽}},\rho ,u_{\mathrm{𝗋𝖾𝖺𝖽}})}_i$, for $i\in [T+1]$ corresponding to the $i$-th state. It records ${(b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}})}_i$ for $i\in [T]$ as the parameters of writing while going from ${\mathrm{𝗌𝗍𝖺𝗍𝖾}}_i$ to ${\mathrm{𝗌𝗍𝖺𝗍𝖾}}_{i+1}$.

2. 2.

   For all $i\in [T]$, it sets instance $x_i$ and witness ${\omega }_i$ as the following:

   $$x_i=({(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_i,{(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_{i+1}),{\omega }_i={(b_{\mathrm{𝗋𝖾𝖺𝖽}},b_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},i_{\mathrm{𝗐𝗋𝗂𝗍𝖾}},u_{\mathrm{𝗋𝖾𝖺𝖽}},u_{\mathrm{𝗐𝗋𝗂𝗍𝖾}})}_i.$$

   Then for all $i\in [T]$, it generates ${\pi }_i\leftarrow \mathrm{\Gamma }.\mathrm{𝖯𝗋𝗈𝗏𝖾}({\mathrm{𝖼𝗋𝗌}}_0,x_i,{\omega }_i)$.

3. 3.

   It generates a tree $G=(V,E)$ of $\mathrm{\ell }+1$ levels, as the following: The top level is set as level $\mathrm{\ell }$ and the bottom level is set as level $0$. Level $0$ contains a number of $T$ nodes, and level $i$ contains approximately ${\lambda }^{\mathrm{\ell }-i}$ nodes. Every node at levels $1,\mathrm{\dots },\mathrm{\ell }$ is connected to a number of $\lambda$ nodes at the lower level. Specifically, the $j$-th node on level $i(1\le i\le \mathrm{\ell })$ has $\lambda$ child nodes: the $((j-1)\cdot \lambda +1)$-th node, the $((j-1)\cdot \lambda +2)$-th node, $\mathrm{\dots }$, and the $(j\cdot \lambda )$-th node on level $i-1$. Since $T\le {\lambda }^{\mathrm{\ell }}$, we assume without loss of generality that there is at most one node on level $\mathrm{\ell }$. Note that the graph $G$ has a tree structure, where each internal node has $\lambda$ child nodes.

4. 4.

   For each node $v\in V$, it assigns of a pair of instance and proof to $v$: $({\mathrm{𝗂𝗇𝗌𝗍}}_v,{\mathrm{𝗉𝗋𝗈𝗈𝖿}}_v)$. For the $i$-th node at level $0$ (denoted as $v_{0,i}$), it assigns instance ${\mathrm{𝗂𝗇𝗌𝗍}}_{v_{0,i}}=x_i$ and proof ${\mathrm{𝗉𝗋𝗈𝗈𝖿}}_{v_{0,i}}={\pi }_i$ to such node. Next, it assigns a pair of instance and proof to each node at level $1$ to $\mathrm{\ell }$.

5. 5.

   It starts from level $1$. Each node $v$ at level $1$ has a sequence of $\lambda$ child nodes: $v_1,\mathrm{\dots },v_{\lambda }$. It then takes instances ${\mathrm{𝗂𝗇𝗌𝗍}}_{v_i}$ and proofs ${\mathrm{𝗉𝗋𝗈𝗈𝖿}}_{v_i}$ for all $i\in [\lambda ]$. It parses instance ${\mathrm{𝗂𝗇𝗌𝗍}}_{v_i}$ as

   $${\mathrm{𝗂𝗇𝗌𝗍}}_{v_i}=({(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_i,{(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_{i+1}).$$

   Then for all $i\in [\lambda +1]$, it sets $z_i$ as ${(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})}_i$. It generates proof

   $$\sigma =\mathrm{\Gamma }.\mathrm{𝖯𝗋𝗈𝗏𝖾}({\mathrm{𝖼𝗋𝗌}}_i,(z_1,z_{\lambda +1}),({\{{\sigma }_i\}}_{i\in [\lambda ]},{\{z_i\}}_{i\in [\lambda +1]})).$$

   It assigns $(z_1,z_{\lambda +1})$ as the instance and $\sigma$ as the proof to such internal node:

   $${\mathrm{𝗂𝗇𝗌𝗍}}_v=(z_1,z_{\lambda +1}),{\mathrm{𝗉𝗋𝗈𝗈𝖿}}_v=\sigma .$$

6. 6.

   It repeats step $5$ for level $2,3,\mathrm{\dots },\mathrm{\ell }$.

7. 7.

   The root node is now assigned with the instances $(\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}})$ and $({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })$, along with the proof $\sigma$. Recall that one may consider hash value as three independent values, such that $\rho =({\rho }_1,{\rho }_2,{\rho }_3)$ and ${\rho }^{\prime }=({\rho }_1^{\prime },{\rho }_2^{\prime },{\rho }_3^{\prime })$. The output is $\pi =({\rho }_2,{\rho }^{\prime },\sigma )$.

$\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}(\mathrm{𝖼𝗋𝗌},x,\pi )\to \{0,1\}$

. It first parses $\mathrm{𝖼𝗋𝗌}$ as $(\mathrm{𝗁𝗄},{\mathrm{𝖼𝗋𝗌}}_0,\mathrm{\dots },{\mathrm{𝖼𝗋𝗌}}_{\mathrm{\ell }})$ and $\pi$ as $({\rho }_2,{\rho }^{\prime },\sigma )$. It sets ${\rho }_3$ as an all zeros string. Remark $3.5$ in the full version says that hash value of an all zeros string is also a string of all zeros. This is a straightforward property that can be added to to any collision-resistant hash function. Thus, ${\rho }_3$ is equivalent to $𝖧.\mathrm{𝖧𝖺𝗌𝗁}({\mathrm{𝗁𝗄}}_3,0^{k-n-m})$, which allows the verifier to directly generate ${\rho }_3$ without evaluating the hash function. Next, it sets ${\rho }_1$ as $𝖧.\mathrm{𝖧𝖺𝗌𝗁}({\mathrm{𝗁𝗄}}_1,x)$, and $\rho$ as $({\rho }_1,{\rho }_2,{\rho }_3)$. It then sets $\mathrm{𝗌𝗍𝖺𝗍𝖾}$ as the starting state and ${\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime }$ as the accepting state, and $i_{\mathrm{𝗋𝖾𝖺𝖽}}$ as the reading bit’s index for the starting state, $i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime }$ as such index for the accepting state. Without loss of generality, we take $i_{\mathrm{𝗋𝖾𝖺𝖽}}$ and $i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime }$ as fixed according to the definition of machine $ℛ$. The verifier outputs

$$\mathrm{\Gamma }.\mathrm{𝖵𝖾𝗋𝗂𝖿𝗒}({\mathrm{𝖼𝗋𝗌}}_{\mathrm{\ell }},((\rho ,\mathrm{𝗌𝗍𝖺𝗍𝖾},i_{\mathrm{𝗋𝖾𝖺𝖽}}),({\rho }^{\prime },{\mathrm{𝗌𝗍𝖺𝗍𝖾}}^{\prime },i_{\mathrm{𝗋𝖾𝖺𝖽}}^{\prime })),\sigma ).$$

The completeness of the above design directly follows from the completeness of composite hash tree $H$ and $\delta$-mild SNARK $\mathrm{\Gamma }$.

For all $i\in \{0,\mathrm{\dots },\mathrm{\ell }\}$, we denote $n_i$ as instance size, $m_i$ as witness size, and $|{\pi }_i|$ as proof size for each individual node at level $i$.

The soundness analysis is as below.

The recursive composition inherits the completeness of $\mathrm{\Gamma }$.