SNARKs for Virtual Machines Are Non-malleable

Cryptographic proof systems have a plethora of applications: from building other cryptographic tools (e.g., malicious security for MPC protocols) to concrete settings such as private transactions or rollups. In several settings it is important for proof systems to be non-malleable : an adversary should not to be able to modify a proof they have observed into another for a statement for which they do not know the witness.

Proof systems that have been deployed in practice should arguably satisfy this notion: it is crucial in settings such as transaction systems and in order to securely compose proofs with other cryptographic protocols. As a consequence, results on non-malleability should keep up with designs of proofs being deployed.

Recently, Arun et al. proposed Jolt (Eurocrypt 2024), arguably the rst ecient proof system whose architecture is based on the lookup singularity approach (Barry Whitehat, 2022). This approach consists in representing a general computation as a series of table lookups. The nal result is a SNARK for a Virtual Machine execution (or SNARK VM).

Both SNARK VMs and lookup-singularity SNARKs are architectures with enormous potential and will probably be adopted more and more in the next years (and they already are).

As of today, however, there is no literature regarding the non-malleability of SNARK VMs. The goal of this work is to ll this gap by providing both concrete non-malleability results and a set of technical tools for a more general study of SNARK VMs security (as well as modular SNARKs in general). As a concrete result, we study the non-malleability of (an idealized version of ) Jolt and its fundamental building block, the lookup argument Lasso. While connecting our new result on the nonmalleability of Lasso to that of Jolt, we develop a set of tools that enable the composition of non-malleable SNARKs. We believe this toolbox to be valuable in its own right.