diagram

Proof-based general-purpose computing

General-purpose cryptographic proof systems enable the following. A program runs, and along with its output it produces a short proof, a cryptographic certificate that this program, on these inputs, produced this output. The proof is small and fast to check. Whoever receives it can confirm the result in milliseconds without rerunning the program, and can pass the proof on to anyone else who needs the same assurance. With the zero-knowledge property, the proof also reveals nothing about inputs that should stay private.

Cryptographic proof systems were invented in the 1980s. Three challenges kept them from becoming a general tool, because all three were not solved at the same time.

  • Efficiency and scale. Producing a proof once took trillions of times more computation than running the program. The prover’s memory also grew with the length of the computation, which made long-running computations impractical to prove. 
  • Generality and usability. Many proof systems require developers to rewrite a program by hand as a cryptographic circuit. This takes months, must be redone on every change, and is a frequent source of security bugs. 
  • Security. Many proof systems rely on elliptic curves, which a sufficiently large quantum computer could break. Others need a trusted setup, or rest on newer assumptions that have had less scrutiny.

For more than a decade, Microsoft Research has worked to make cryptographic proof systems practical. We highlight two results: Nova (2022) and Magnetar (2026).

Spotlight: Nova and folding — proving computations of any size

The problem. Many real-world computations are long, or keep running indefinitely. Examples include ledgers and blockchains that keep processing transactions. Proving such a computation in one shot needs prover memory that grows with its length, which makes long-running computations impractical to prove.

The idea. Nova introduced folding schemes. With folding, a prover handles a computation of any length. This is done by producing a proof for a step and then updating it by executing another step. Updating the proof by a step costs the same however many steps came before, and checking the proof does not get harder as the computation grows. Nova started a line of folding-based proof systems, from elliptic-curve designs to plausibly post-quantum, lattice-based ones.

The Nova family. A series of works improved Nova’s prover time, verifier time, and proof sizes; built folding scheme using lattices; applied folding schemes to real-world applications.

  • HyperNova (opens in new tab) (CRYPTO 2024). Folding for a general class of problems while minimizing the prover’s work
  • NeutronNova (opens in new tab) (CRYPTO 2026). Improves upon HyperNova further to reduce recursion costs while expanding folding to a broader class of problems
  • Nebula (opens in new tab) (IEEE S&P 2026, Distinguished Paper Award). Extends folding schemes with memory checking, providing a folding-based zkVM
  • MicroNova (opens in new tab) (IEEE S&P 2025). Folding with a verifier efficient enough for Ethereum.
  • Neo and SuperNeo (opens in new tab) (CRYPTO 2026). Lattice-based folding for a general class of problems. Features a fast commitment scheme and plausible post-quantum security.
  • Vega (opens in new tab) (IEEE S&P 2026). Vega proves facts from government credentials such as mobile driver’s licenses. It uses NeutronNova to fold the many computation steps over a credential into one, and then folds with a random step using Nova to add zero-knowledge.

From Nova to Magnetar. The goal Nova set, proving computations of any size, carries through to Magnetar. Magnetar proves a computation in pieces and combines the pieces, using efficient recursion built on standard hash functions (see below).

Spotlight: Magnetar

Magnetar: High-speed post-quantum RV64 zkVM from standard hashes (opens in new tab)

Magnetar is a zero-knowledge virtual machine (zkVM), meaning it proves program executions on a standard machine (e.g., RV64IM). It is the first zkVM to have all three of these properties at once: it proves general-purpose programs, it is post-quantum secure from standard hash functions, and its recursion is efficient.

  • General-purpose. Magnetar proves programs compiled to 64-bit RISC-V (RV64IM). Developers write in Rust, Go, or C, compile as usual, and prove the program as written. An Ethereum Virtual Machine (EVM) written in Rust or Go runs inside Magnetar. That yields a zkEVM for existing smart contracts.
  • Fast. On a laptop, it proves 2^22-cycle executions at 7.2–8.7 million cycles per second. It is 10 to 39 times faster on average than the prior fastest comparable systems. An optimized Magnetar reaches 9.5–12.8 million cycles per second, which raises each speedup by about 1.3×.
  • Small proofs that are fast to check. Proofs are about 600 KiB and verify in 11–13 ms.
  • Standard cryptography only. Security rests on a standard hash function such as SHA-256 or SHA-3. Magnetar needs no elliptic curves and no lattices; no special-purpose hash functions such as Poseidon; no trusted setup; no unproven conjecture about error-correcting codes. Hash functions underlie the hash-based signatures that NIST standardized as its conservative post-quantum option.
  • Proofs of proofs. Checking a Magnetar proof is mostly hashing and binary-field arithmetic, which is exactly what Magnetar proves efficiently. So Magnetar can prove a computation of any size by proving it in pieces and combining them. It can also prove a long-running system such as a ledger or a blockchain.

Links: Blog