Using Garbled Circuits To Compute SHA-512 On Bitcoin

Introduction

Bitcoin Script, the language powering all Bitcoin transactions, has a limited set of opcodes. By design, the language is not Turing-complete and even some useful opcodes were disabled due to security concerns. Here is where BitVMX comes in. It is a protocol that allows two parties to execute a program off-chain, so Bitcoin Script's limitations don't apply to the computation itself. The correctness of the result of that execution, however, can then be challenged on-chain using much simpler logic that Bitcoin Script can handle, enabling transactions whose spend condition depends on the result of arbitrary computation.

To use BitVMX, the program must be agreed upon by both parties before locking the funds. Later, one party can provide an input that satisfies the conditions of the program and thus claim the funds.

Previously, this was done using a virtual CPU based on the RISC-V32IM architecture; you can see the article where we showed how to run Zero-Knowledge Proof Verification On Bitcoin using this CPU. In this article, we'll instead use the new Garbled Circuit backend and compute SHA-512 to unlock funds by providing a preimage of the expected hash. Note that Bitcoin Script does not natively support SHA-512.

The Circuit

The circuit is built in three steps: first we load the base SHA-512 circuit, then we extend it with an equality check so it can also tell us whether the resulting hash matches a target value, and finally we hardcode the Initialization Vector (IV) into the circuit.

We start from the SCALE-MAMBA SHA-512 circuit, which takes a 1024-bit message block and a 512-bit IV as input, and produces the 512-bit hash as output.

That circuit alone only computes a hash. It doesn't tell us whether that hash matches the expected value. To turn "compute the hash" into "prove you know a preimage," we need to compare the output against a target 512-bit value and collapse that comparison into a single bit. We do this with a dedicated equality-check circuit: it XORs each pair of corresponding bits from the two 512-bit values being compared. A XOR B is 0 if and only if the two bits match. The circuit then negates each of those 512 XOR results and ANDs them together. The output is 1 if and only if every bit-pair matches, meaning the two 512-bit values are identical.

We then compose the SHA-512 circuit with the equality-check circuit, wiring the 512 hash-output bits directly into one side of the equality check. The result is a single circuit whose inputs are the original message block and IV, plus the 512-bit expected hash value now feeding the other side of the comparison, and whose single output bit tells us whether hashing the given block under the given IV produces exactly the expected hash.

This can be visualized as follows:

Finally, we hardcode the IV to the values defined in section 6.3 of RFC 6234 as follows:

$H_0^{\left(0\right)}=\text{6a09e667f3bcc908}$

$H_1^{\left(0\right)}=\text{bb67ae8584caa73b}$

$H_2^{\left(0\right)}=\text{3c6ef372fe94f82b}$

$H_3^{\left(0\right)}=\text{a54ff53a5f1d36f1}$

$H_4^{\left(0\right)}=\text{510e527fade682d1}$

$H_5^{\left(0\right)}=\text{9b05688c2b3e6c1f}$

$H_6^{\left(0\right)}=\text{1f83d9abfb41bd6b}$

$H_7^{\left(0\right)}=\text{5be0cd19137e2179}$

Pre-signed Variables

Both the message padding and the output hash can be represented by constants embedded in our garbled circuit. However, we may prefer to always re-use the same (plaintext) circuit. In that case, we need to pre-sign some of these values as if they were circuit inputs. In the previous article, where we discussed how we implemented Garbled Circuits for BitVMX, we mentioned the possibility of exchanging part of the circuit's input during the setup phase. Here, we use that setup-phase exchange to have the Prover provide Lamport signatures over the wires corresponding to the already-agreed expected hash: for each bit of the hash, the Prover signs the specific value (0 or 1) that both parties expect for that bit. The Verifier checks every one of these signatures against the agreed hash image, bit by bit. If any signature doesn't match, for example if the Prover signs a 1 where a 0 was expected, or provides a signature that doesn't correspond to either bit, the Verifier aborts the setup and does not continue with the rest of the protocol. Note that the process of agreeing on the value of the expected hash must be handled outside of this protocol.

The second value that should also be pre-signed is the message padding. The circuit takes a full 1024-bit block as input, but the Prover should only need to provide the 512 bits that actually make up the preimage; the remaining 512 bits of the block are padding required by the SHA-512 specification, and their values are entirely determined by the length of the message. Since the message length is fixed at 512 bits for our use case, the padding is fixed too, and there is no reason to let the Prover supply it as free input, and we just embed it as constants in the circuit.

Per RFC 6234, the padding for a 512-bit message consists of a single 1 bit, followed by 383 zero bits, followed by the 128-bit encoding of the message length. Since this value never changes, the Prover should pre-sign it during setup exactly like the expected hash, so the only input the Prover ever needs to provide at claim time is the 512-bit preimage itself.

Protocol Recap

As shown in the diagram from the previous article, the first transaction is the Claim transaction. It is sent by the Prover when they want to claim the locked funds. If for some reason the Verifier thinks that the Prover should not be able to claim the funds, the Verifier sends the Challenge transaction and asks the Prover to provide a proof of their claim in the Input transaction. In this case, the proof is just the hash preimage. And finally, if the proof is incorrect, the evaluation of the garbled circuit will output the signature required to send the Equivocation transaction and release the funds to the Verifier.

Mainnet Run

We ran an example of this SHA-512 preimage check on mainnet. Here we followed the path where the Prover provided a wrong preimage and the Verifier blocked the Prover from claiming the funds. The expected hash we wanted to get was:

34efdf4a81000e1925063c36a50d542331ad23afa7d152e678378f70b6b5b91512b4acdd3dd6dafb105701c79f925b793fb2a57398069b104d50c8325c1e6f62

and its preimage is:

my_super_secret_string_that_noone_knowsAAAAAAAAAAAAAAAAAAAAAAAAA.

Unfortunately for the Prover, they don't know this preimage, so they send:

my_wrong_secret_string_that_noone_knowsAAAAAAAAAAAAAAAAAAAAAAAA

Note the substituted word.

The Claim Transaction

⛓️ Mempool link

This is where the protocol starts. The Prover sends this Claim transaction expecting to unlock the funds.

The Challenge Transaction

⛓️ Mempool link

Here we can see the Challenge transaction. We only describe a simplified version of it. As you can see, it has multiple outputs, but right now only the last one matters. That last UTXO can only be spent by the Input transaction, and it’s used to chain the rest of the protocol.

The Input Transaction

⛓️ Mempool link

This is the Input transaction. At first glance, it looks like the actual input data is not there, since the size is too small for a transaction that has to provide the 512 signatures for the circuit input. That assumption is correct: the input is not really there, but is instead in a child transaction that is consuming the first output of the Input transaction. It uses the Child Pays For Parent (CPFP) mechanism to bump the fee of the parent transaction and incentivize miners to include both transactions in the block. With this technique we can recursively boost the fee again if miners are still not including the transactions in their blocks, and we can pay the fees using funds from other UTXOs.

Of course, that means that only sending the Input transaction is not sufficient to continue with the protocol. The Prover also needs to provide the actual input in the child transaction, and failing to do so would cause the Verifier to penalize them via a timeout.

The Actual Input Transaction

⛓️ Mempool link

We can clearly see that this time the transaction is significantly bigger, requiring a much larger fee due to the 512 signatures. You can expand the transaction details and see all the witnesses. Those witnesses encode the string

my_wrong_secret_string_that_noone_knowsAAAAAAAAAAAAAAAAAAAAAAAAA

meaning that the Prover provided the wrong preimage. As a reminder, this is not the full circuit input, only the variable part of it containing the preimage. The constants (IV, expected hash, and padding) were already fixed during setup.

The Equivocation Transaction

⛓️ Mempool link

Once the Verifier sees the Actual Input transaction on-chain, they use the witnesses as inputs to the garbled circuit and compute the resulting signature. If the signature matches the expected signature for a failed preimage check, then the Verifier sends this Equivocation transaction. We use Lamport signatures here, and also for the Actual Input transaction, meaning that a signature is just the preimage of either the public key representing the 0 or the public key representing the 1. In this case, only the 0-bit signature should be considered, since 0 means the circuit failed.

Claim Gates

To finally claim the funds, we use what we call Claim Gates. A Claim Gate lets you connect multiple conditions to a single transaction and txid; that transaction can be executed as soon as any one of those conditions is met, rather than requiring a separate transaction or branch for each condition individually.

The Claim Gate flow is as follows:

• The Challenge transaction needs two extra UTXOs, CLAIM_PROVER_WON and STOP_PROVER_WON.
• Any transaction in the protocol that implies that the Prover won should consume the STOP_PROVER_WON UTXO.
• After consuming that UTXO, the Prover should initiate the claim by sending the ProverWonStart transaction that also consumes the CLAIM_PROVER_WON UTXO.
• The Prover then has to wait for some configurable number of mined blocks and send the ProverWonSuccess transaction. This is enforced by the Bitcoin Script using the OP_CSV opcode.
• If the Prover did not win the dispute, the STOP_PROVER_WON UTXO would still be present, and the Verifier should use it by sending the VerifierStopProverClaim transaction that blocks the claim and prevents the Prover from sending the ProverWonSuccess transaction. This is possible because the output of ProverWonStart can be consumed by both the ProverWonSuccess and VerifierStopProverClaim transactions. Without that output, neither transaction can be sent.
• Finally, the output of the ProverWonSuccess transaction enables the Prover to send the ProverWonAction transaction that consumes the locked funds.

This is a diagram showing what we just described:

For the full Claim Gate flow, we need to create the same wiring for the path where the Verifier wins. Symmetrically, this produces VerifierWonStart and VerifierWonSuccess transactions. To the Challenge transaction, we should add an extra UTXO called EXCLUSIVE_WON that is consumed by both ProverWonSuccess and VerifierWonSuccess so that only one of the two parties can claim they won.

Note that if both win conditions consume the same locked funds, this extra UTXO isn't strictly necessary, since only the first transaction to land on-chain will actually be able to spend those funds. But the funds being claimed here don't have to be a plain UTXO that locks funds. They can instead be the CLAIM_PROVER_WON UTXO of a different protocol instance that uses this protocol as one of its internal win conditions (and, symmetrically, CLAIM_VERIFIER_WON if the Verifier wins here). In that case the Prover-wins and Verifier-wins paths lead to two distinct outer UTXOs rather than one shared one, so we do need EXCLUSIVE_WON to guarantee that only one side is ever able to claim victory.

Also note that to prevent one party from claiming they won, the other party should be monitoring the blockchain to respond with the stop transaction. Thanks to the EXCLUSIVE_WON UTXO, once one party wins, they no longer need to be watching the transactions sent by the other party to stop that party’s claim.

Claiming The Funds

⛓️ Mempool link

After sending VerifierWonStart and then, some blocks later, VerifierWonSuccess, the Verifier can finally send this transaction to claim the protected funds.

Conclusion

This mainnet run demonstrates that SHA-512, a hash function Bitcoin Script has no native support for, can still be used as a spend condition on Bitcoin by evaluating it off-chain as a garbled circuit and only settling the result on-chain. Even when the Prover cheated by providing the wrong preimage, the dispute was resolved and the funds were correctly awarded to the Verifier, using a fixed, small set of transactions.

This is also where the garbled circuit backend's main advantage over the BitVMX-CPU backend shows up. With BitVMX-CPU, a disputed claim requires an n-ary search over the program's execution trace to locate the exact instruction where the two parties diverge, so the number of on-chain transactions needed for a dispute scales with the size of the program: Θ(log n) for n executed instructions. With BitVMX-GC, the entire dispute, regardless of how large or complex the underlying circuit is, resolves in a constant number of transactions: Claim, Challenge, Input, and Equivocation, plus the Claim Gate transactions used to settle the payout. The tradeoff is that this efficiency is paid for upfront: garbling the circuit and generating the proofs that attest it was garbled correctly is considerably heavier than compiling a program for BitVMX-CPU.

This walkthrough only shows a Claim Gate used standalone, but as mentioned above, ProverWonAction and VerifierWonAction can also plug directly into an outer protocol's Claim Gate, letting the outcome of one dispute gate the outcome of another. That composability, combined with the constant on-chain footprint of the garbled circuit approach, is what makes it a practical building block for larger BitVMX constructions such as bridges or oracles.