BitSNARK VM - Verifying zkSNARKs On Bitcoin

BitSNARK VM is a virtual machine emulating a simplified register-based processor with only three instructions, natively supporting the finite field calculations required for elliptic curve pairing operations. As a result, the verification protocol is notably simplified, requires no memory consistency checks, and only requires two challenge scenarios:

1. Single-instruction execution error proofs

2. Reveal-equivocation proofs

The VM has a limited number of 256-bit registers, each with a unique ID. Each instruction receives register IDs, performs a single calculation, and emits its result into the target register. Certain registers can be marked as immutable, so their values cannot be modified and they can be optimized in the Bitcoin script. The following instructions are supported:

• addmod(𝑡, 𝑎, 𝑏, 𝑚) – Add the values of registers 𝑎 and 𝑏, modulo 𝑚, into register 𝑡.

• andbit(𝑡, 𝑎, 𝑏, 𝑐) – If bit 𝑏 of register 𝑎 is 1, write the value of register 𝑐 into register 𝑡; otherwise, write the value 0.

• equal(𝑡, 𝑎, 𝑏) – If the values of registers 𝑎 and 𝑏 are equal, write 0 into register 𝑡; otherwise, write 0.

Additionally, an attempt to write a value into an immutable register results in the program being rejected if the value being written is different from the value in that register.

It can be demonstrated that these instructions are sufficient to implement a zkSNARK verifier.

An Iterative Prover vs Challenger Loop - Verifyable Onchain

BitSNARK is designed as a two-party protocol for a prover and a verifier, where the prover initiates the execution by revealing the program’s input and its result, and the verifier can dispute it if they believe the claim is incorrect. When considering more than two operators, a two-party BitSNARK protocol is set up for each pair of agents, allowing any successful two-party challenge to block an invalid program execution.

The protocol is organized as a series of challenge-and-response interactions with a time lock. It also engages with the verifier via a peer-to-peer protocol to create a set of pre-signed transactions. These transactions can be used by the two parties to perform the steps of the protocol.

Each step of the iteration, if a proof is challenged:

• The prover splits the program execution in half and commits to the state of the virtual machine at the point of incision.

• The verifier chooses which of the two resulting parts they believe is false.

• The process iterates until the prover has committed to a single BitSNARK operation.

This process can be executed on-chain to determine the winner of the protocol.

If no challenge is entered during the allowed time period, or if the verifier fails to demonstrate a rejection, the funds are unlocked, and the prover can make use of them.

If the challenge is successful, the funds remain securely locked until any other operator initiates a withdrawal process on their own. The verifier is incentivized by receiving a sum from an output created beforehand by the prover in the initiating transaction.

Each iteration involves a time-locked transaction—if a party walks away, they lose the game once the timeout has expired.