Implementing Garbled Circuits for BitVMX

In a previous article, we talked about how we used Garbled Circuits (GCs) in BitVMX to verify arbitrary programs on Bitcoin. This article explains how we integrated garbled circuits into the BitVMX client and how the resulting design compares to BitVMX-CPU.

Garbled Setup

Our protocol is divided into two parts: first the setup, and then the verification protocol itself. During setup, the Prover (or Garbler) will be responsible for garbling the publicly known circuit that will be used for this protocol. We will not go into details on what GCs are and how they are generated, but the main idea is that a garbled-circuit protocol is a protocol for secure two-party computation. GCs allow two mutually distrustful parties to jointly evaluate a function over their private inputs without requiring a trusted third party. In our use case, the input is only provided by the Prover and the circuit will have a unique Boolean output that indicates whether the input is correct for the function we want to evaluate. The function being evaluated is represented as an acyclic Boolean circuit. After garbling, the Prover should send to the Verifier the following artifacts:

• The garbled circuit ciphertexts used to evaluate the circuit.
• The public Lamport commitments of the true and false wire values associated with the circuit inputs and outputs. The commitments are used to verify the input’s validity at the label level. They also appear in the Bitcoin scripts: one script ensures each input label matches one of its two commitments, and another enables a spending path when an output wire label is known.
• A zero knowledge proof that the garbling of the circuit was done correctly.
• A zero knowledge proof that the Lamport commitments correspond to the garbled circuit input and output wires.
• The pre-signed input (optional).

We will now explain what each of these artifacts mean.

In this article we don’t focus on how garbled circuits are generated: what is important is that after some optimizations we end up needing one ciphertext per AND gate of the circuit and no ciphertexts per NOT or XOR gate. Regarding the inputs, for each input wire of the circuit the Prover generates two labels,

$X_0,X_1$

$X_0$ is randomly chosen and $X_1$ is derived from $X_0$. They represent the $0$ and $1$ bit values respectively and are generated during the garbling of the circuit; only one of those labels is used for evaluating the circuit. The Prover won’t send the labels but will commit to them by providing the hashes

$\mathrm{sha256}\left(X_0\right),\mathrm{sha256}\left(X_1\right)$

We call those hashes the public Lamport commitments because they act as public Lamport keys in a Lamport one-time signature scheme: in this analogy, each label $X_b$ is a private key, its hash is the corresponding public key, and revealing $X_b$ later serves as a Lamport signature for the bit value $b$. This commits the Prover to the wire labels without revealing them. The same kind of hash commitments exist for the output labels of the circuit, but those output labels are not randomly generated; they are determined by the last gate of the circuit and its input wires.

Those values on their own don’t mean anything to the Verifier, but the value of the output will let the Verifier spend an UTXO that uses the label as a hashlock, so during setup the Verifier must be convinced that the labels have been correctly computed and eventually he will be able to obtain the label. Therefore during Setup the Prover has to send a zero-knowledge proof that the labels were correctly generated. The proof has two parts: Roughly speaking, the first ZK-proof proves that the garbling was performed correctly, meaning that the provided ciphertexts follow the garbled circuit protocol and that the relation between $X_0$ and $X_1$ is preserved. The second ZK-proof proves that the commitments used by the Bitcoin scripts as hashlocks are precisely the hashes of the labels of the input and output wires of the circuit.

We chose to use Nova as the proving system that ensures the correctness of the garblings. The Nova proving system is a high-speed, interactive zero-knowledge proof system designed for incrementally verifiable computation (IVC). Each Nova proof carries several public outputs which include a set of digests. During verification, Nova does not compute these digests; instead it checks that the digests embedded in the proof are internally consistent with the rest of the proof. One of the digests is the root of a hash chain over the Lamport key commitments, defined by

$H_0=0$

$H_{i+1}=h(H_i\parallel \mathrm{sha256}(X_{i,0})\parallel \mathrm{sha256}(X_{i,1}\left)\right)$

where $\parallel$ denotes string concatenation, and

$h:{\{0,1\}}^{*}\to {\{0,1\}}^n$

is a one-way hash function. The Verifier recomputes this hash chain from the public commitments the Prover provided and checks that the resulting root equals the digest.

Another digest is a digest of the circuit itself, also as a hash chain but on the gates of the circuit as follows

$H_0=0$

$H_{i+1}=h(H_i\parallel \mathrm{gateKind}(i)\parallel \mathrm{isIO}(A_i)\parallel \mathrm{isIo}(B_i)\parallel \mathrm{isIo}(O_i)\parallel A_i\parallel B_i\parallel O_i)$

where $\mathrm{gateKind}\left(i\right)$ returns 1, 2 or 3 if the i-th gate is an XOR, AND or INV gate respectively. $A_i$ is the index of the first input wire of the i-th gate, $B_i$ is the index of the second input wire of the i-th gate, and $O_i$ is the index of the output wire of the i-th gate. If the gate is an INV gate then $B_i$ is 0. And $\mathrm{isIO}\left(n\right)$ takes a wire index and returns true if the wire is an input or output of the circuit.

The Verifier simply computes the digest of the known public circuit and compares it with the digest from the proof. If the digests match, the garbled circuit should match exactly the public one.

Finally, both Nova ZK-proofs (garbling correctness and commitment-binding) include a third digest: a hash chain over the raw labels $X_{i,0},X_{i,1}$ themselves. The Verifier cannot compute this digest directly, because it does not know the secret labels. The Verifier simply compares the two values (one from the garbling-correctness proof, one from the commitment-binding proof). If they match, it means the proofs are correctly linked and the whole proof is consistent.

To recap: the first digest binds the public circuit, the second binds the public commitments, and the third links both proofs through the hidden labels.

Among the values the Prover gives to the Verifier, there is also an optional pre-signed input. Here the Prover reveals some of the $X_0$ or $X_1$ labels. The Verifier hashes each revealed label and verifies that it matches one of the two commitments ($\mathrm{sha256}\left(X_0\right)$ or $\mathrm{sha256}\left(X_1\right)$) for that wire. This is used when the computation itself involves a publicly known, fixed value. Not something chosen by either party, but an inherent part of the problem being verified, much like the circuit. In that case the Verifier also checks that the pre-signed input equals the expected public value, and those labels will later be combined with the remaining input revealed in the Input transaction to evaluate the circuit. If no such fixed value is present, the pre-signed input is simply omitted.

For example if the circuit does a preimage check, the prearranged input could be a hash H and the rest of the input a string S such that hash(S) = H.

If any of those steps fails to verify, the Verifier should abort the setup and not continue with the rest of the protocol.

Building the protocol

After the garbled setup is done, both parties build the protocol transactions. The protocol consists of four main transactions:

1. Claim - The Prover broadcasts this transaction to assert a claim. It contains no additional data.
2. Challenge - The Verifier can broadcast this transaction to challenge the claim.
3. Input - If challenged, the Prover reveals the remaining input labels (the Lamport “signatures”) inside this transaction.
4. Equivocation - If the garbled circuit’s evaluation yields the output label $X_1$ (meaning the claim is invalid), the Verifier can use that label to penalize the Prover.

At every step, a timelock protects the responding party. If the expected party fails to act before a deadline, the counterparty can broadcast a timeout transaction and wins. Concretely:

• If the Prover never reveals the input labels in the Input transaction, the Verifier wins.
• If the Verifier does not send the Equivocation transaction in time (perhaps because the circuit output was $X_0$ and he doesn’t know $X_1$) or he never starts the challenge, the Prover wins.

The commitments from the setup are used to prevent the Prover from providing invalid inputs. The Bitcoin script in the Input transaction enforces that each witness hash matches one of the two commitments for that wire. For a single wire, the script looks like:

OP_SHA256
OP_DUP
<SHA(X_0)>
OP_EQUAL
OP_SWAP
<SHA(X_1)>
OP_EQUAL
OP_BOOLOR
OP_VERIFY

Bitcoin script is based on a stack-based machine. To verify the commitments, the script uses the following opcode sequence:

1. OP_SHA256 hashes the witness (the input label) provided in the spending transaction, leaving hash(label) on the stack.
2. OP_DUP duplicates that hash, so the stack now holds two copies of hash(label).
3. The hardcoded hash SHA(X_0) is pushed, and OP_EQUAL compares it to the top copy. The result (1 for equal, 0 otherwise) is left on the stack, with the second copy of hash(label) sitting just below it.
4. OP_SWAP exchanges the top two items, bringing hash(label) back to the top and placing the first comparison result underneath.
5. The second hardcoded hash SHA(X_1) is pushed, and OP_EQUAL compares it to hash(label), leaving the second comparison result on the stack.
6. OP_BOOLOR pops both results and leaves 1 if the label matches either commitment, 0 otherwise.
7. Finally, OP_VERIFY checks that the value is true; if not, the transaction becomes invalid.

In effect, the witness is hashed once, and its hash must match SHA(X_0) or SHA(X_1) for that wire. The same pattern is repeated for every input wire.

The Equivocation transaction’s script simply verifies that the witness is the “invalid” label:

OP_SHA256
<SHA(X_1)>
OP_EQUALVERIFY

A fundamental security property of garbled circuits is that they only produce a meaningful output when evaluated on the correct input labels. If the Prover attempted to cheat by sending any label other than $X_0$ or $X_1$ for a wire, the circuit’s evaluation would yield a garbage value, a label that matches neither output commitment. Such a label cannot satisfy the Equivocation transaction’s script, so the Verifier gains nothing from using incorrect inputs. Thus, the Prover is forced to supply the legitimate labels, and the Verifier correctly learns whether the claim is valid ($X_0$) or invalid ($X_1$).

The Verifier has no way to force the circuit into producing $X_1$ when the claim is valid, because he does not control the input labels. The Verifier must evaluate the circuit using exactly the labels the Prover reveals on-chain (those labels are already checked against the commitments by the Input transaction’s script). Any attempt to substitute a different label would be rejected by the Bitcoin script, and evaluating the circuit locally with random labels would only yield garbage that does not match the committed output labels. Consequently, the Verifier obtains $X_1$ if and only if the Prover’s claim was genuinely invalid.

During the build step, both parties construct all transactions and exchange signatures. Neither party can broadcast a transaction without the other’s signature, so any disagreement over a transaction’s content (such as the spending script) halts the protocol setup. This ensures that only mutually agreed-upon conditions are enforced on-chain.

With these Bitcoin Scripts, the Prover cannot send an Input transaction containing invalid data; it would be rejected by the blockchain. The same applies to the Equivocation transaction: the script enforces that the Verifier possesses $X_1$, meaning the Prover submitted an incorrect input.

Comparison with BitVMX-CPU

To verify arbitrary computations with the BitVMX-GC protocol it must use a large binary circuit that encodes a Groth16 verifier. However, once the circuit is thoroughly audited, it stays unchanged for all protocol instantiations. The execution of a BitVMX-GC instance is quite simple. The execution of the BitVMX-CPU protocol is substantially more complex than BitVMX-GC. In simplified terms, both parties agree on a program to be run on a virtual RISC-V CPU. The Prover sends the claimed result. If the Verifier disagrees, a challenge begins: a binary search over the program’s execution trace narrows down the exact step where the two parties first diverge. At that step, the Prover must reveal exactly how the CPU executed the instruction, including all memory reads and writes. Depending on what went wrong, the Verifier then uses a tailored Bitcoin Script that verifies the error. (In some cases, the disagreement may lead to a secondary binary search. For example, over the memory accesses.)

All of this happens on-chain, so it requires many more transactions. The number of transactions needed scales as $\Theta \left(\log \right(n\left)\right)$ due to the binary search, where $n$ is the number of executed RISC-V instructions. In contrast, BitVMX-GC uses only a constant number of transactions ($\Theta \left(1\right)$) regardless of program size.

This efficiency gain on-chain comes with a different cost: the setup phase is considerably heavier for BitVMX-GC. The Prover must garble the circuit and obtain the corresponding Nova proofs that can take a considerable amount of time.

Conclusion

BitVMX-GC thus brings garbled-circuit verification to Bitcoin with constant on-chain complexity. This trades a heavier setup for minimal on-chain footprint, opening the door to verifying larger programs without bloating the Bitcoin network.