Introduction
In a recent post, we detailed our vision for a viable implementation of Vitalik’s 2024 proposal to save users’ fund in case of a quantum emergency. This proposal notably makes use of Account Abstraction to establish a user-space migration path. As Account Abstraction is an almost exclusive prerogative of Ethereum, it makes sense to believe such a course of action to be of difficult generalisation, especially when it comes to blockchains with limited smart contract capabilities as Bitcoin.
And yet, as Ordinals and the like have demonstrated, Bitcoin’s notorious limitations still provide space for elegant solutions. This has left us wondering, what if we could find a way to make our proposal work for Bitcoin too?
Bitcoin Script
First of all, if you come from the Ethereum/Solana world, you’ll need a crash course in how an UTXO-based cryptocurrency works. The most useful thing to do here is to imagine a Bitcoin transaction as some sort of spider: A block with $m$ legs to its left (we call these inputs), and $n$ legs to its right (we call these outputs). To each leg, we attach a number of satoshis, representing monetary value. Essentially, the transaction takes satoshis on the inputs and reallocates them as prescribed by the outputs. Clearly, \(\sum_{i=0}^m \text{input}_i \leq \sum_{i=0}^n \text{output}_i\), that is, we cannot spend more than what we put in the transaction; the difference between these two values is the fee we give to the block miner.
To create a new transaction, you wire the outputs of some transactions into your new transaction’s inputs. The outputs of the new transaction, together with the outputs of previous transactions not yet spent, will be themselves up for being used as inputs for new transactions in the future. All in all, we’re just wiring spiders together, as in the following picture.
In this setting though, everyone is able to spend everyone else’s money, as we haven’t introduced any notion of ‘ownership’ yet. To prevent this, the outputs of a transaction are locked with a bunch of code written into something called Bitcoin script, the programming language of a very simple dual-stack pushdown automaton. It consists of a set of instructions that allow to manipulate items on a stack, that is, a bunch of data that can be accessed in a “last in, first out” (LIFO) order. To give a tangible example, consider the following script:
OP_DUP
OP_HASH160
<recipient>
OP_EQUALVERIFY
OP_CHECKSIG
This locking script was the standard way of locking a transaction output before Taproot. All instructions starting with OP_ are Bitcoin script instructions that manipulate the stack in some way, whereas <recipient> is just the hash of the output’s recipient’s public key. This script was just attached to a transaction output. To spend such output, you had to provide the following script on the corresponding input:
<sig> <pKey>
which is nothing more than a signature and a public key that owns it. At evaluation time, input and output script would be concatenated and executed, as follows:
| STACK | SCRIPT | DESCRIPTION |
|---|---|---|
| empty |
<sig>
<pKey>
OP_DUP
OP_HASH160
<recipient>
OP_EQUALVERIFY
OP_CHECKSIG
|
scripts are concatenated. |
<pKey>
<sig>
|
OP_DUP
OP_HASH160
<recipient>
OP_EQUALVERIFY
OP_CHECKSIG
|
constants are loaded onto the stack. |
<pKey>
<pKey>
<sig>
|
OP_HASH160
<recipient>
OP_EQUALVERIFY
OP_CHECKSIG
|
top stack item is duplicated. |
<pKey hash>
<pKey>
<sig>
|
<recipient>
OP_EQUALVERIFY
OP_CHECKSIG
|
top stack item is hashed. |
<recipient>
<pKey hash>
<pKey>
<sig>
|
OP_EQUALVERIFY
OP_CHECKSIG
|
constants are loaded onto the stack. |
<pKey>
<sig>
|
OP_CHECKSIG
|
check if first two elements are equal. |
true |
empty | check if signature is valid. |
As you can see, a given output here is spendable if and only if the transaction trying to spend it is signed by the right key.
A simple change
Now that we kinda know how Bitcoin (used to) work, we can figure out a way to adapt our zk-based graceful fallback solution to BTC. To make our proposal viable, it would be enough to introduce a new opcode, called OP_ZKCHECKSIG. This opcode accepts three pieces of data, <sig>, <zkProof> and <pKey>. It would behave exactly as OP_CHECKSIG, but it would also check that <zkProof> is a valid proof of seed for the corresponding signature.
The fallback mechanism would work as follows:
- Under normal circumstances,
OP_ZKCHECKSIGis set to be equal to:OP_SWAP OP_DROP OP_CHECKSIG. This literally means “drop the zk proof part, and just verify the signature”. In doing so, nothing changes compared to the actual status quo. Notice that in particular users would not have to provide zk proofs at spending time (they can just provide a bunch of zeroes), making performance impact incredibly low both in terms of blockspace and computational capacity. - In case of a catastrophe, miners would automatically soft fork to a codebase where
OP_ZKCHECKSIGis implemented “for real”. HereOP_ZKCHECKSIG, does actually verify zk proofs, and user trying to spend their Bitcoin after this fork are required to provide valid proofs of seed, otherwise their transactions will be invalid. Notice that, at this point, all transactions that usedOP_ZKCHECKSIGin their locking scripts would be automatically protected.
We really like this mechanism because:
- It is completely opt-in, but
- Does not require active migration by generating a new address. Updating your Bitcoin wallet, so that on creating new txs
OP_ZKCHECKSIGis used in place ofOP_CHECKSIGwould be enough to stay protected, no further action required by the end user. This is basically a ‘transparent update’ and it is arguably better in terms of UX than what we can do with Ethereum. - Furthermore, this solution does not require the user to switch to a new, less battle-tested cryptographic scheme. This is important: In swapping ECDSA for, say, Falcon, one may end up being exposed to a not-yet-discovered weakness of the Falcon cypher. This is not the case here: The proof authentication sits on top of the already used pkey authentication, and a security breach can happen only if both fail at the same time, exactly as for any hybrid signature scheme proposal we heard about in the Web2 world.
Notice that, as already detailed in our last post, this protects only addresses generated from a seed phrase or a master key, using e.g. BIP-32 hierarchical deterministic derivation (cf. also BIP-39 and BIP-44). Moreover, this change is designed to be less invasive as possible and opt-it, hence it does not protect transactions that use OP_CHECKSIG. Still, once deployed, and if popular, it would protect an increasingly growing share of BTC in circulation.
There is another important thing to stress: In this setting, we need to make sure that the users we are paying do in fact use keys derived from a seed phrase. If this is not the case, in the wake of a catastrophic event the corresponding transaction outputs would be locked forever. Still, there are many different ways to fix this problem, so we won’t go too much in depth about it here.
Here comes despair
So, we saved Bitcoin and are now happy, right? Alas, no. When you try to make this work, you hit a giant wall, namely the fact that data pushed in the Bitcoin script stack cannot exceed 512 bytes. This is wildly insufficient, as no zk proof goes below a few Kbs at the moment, and probably never will.
So, no joy? Yes and no. Keep reading…
Taproot
In 2021, the Taproot update brought many changes to Bitcoin:
- First, it swapped the ECDSA signature scheme with a Schnorr signature scheme. This is of minimal concern to us.
- Then, it enabled Merkelized Abstract Syntax Trees (MASTs), which allow the implementation of more complex spending conditions on transactions. This is of the utmost interest for us because, among other things, it lifts the data push limitation highlighted above, making it possible to add up to several kilobytes of data to an unlocking script. This would make our proposal viable.
- It also introduces Tapscript, a redesigned scripting language for BTC. This, again, is mainly technical and of minimal interest to us.
So, it would seem that the Taproot update has everything we need to solve our problems. The only issue remaining at this time is that Taproot uses a weird — if I may — way of committing data or scripts to a transaction. This was somehow necessary to maintain backward compatibility with the older standard (something the Bitcoin crowd cares very much about), but unfortunately ends up being incredibly quantum weak. In a nutshell, the idea relies on the group properties of elliptic curve cryptography: Say that our public key is $P$ and the corresponding private key is $sk$. We commit our unlocking script to a value $t$, and use this to obtain a new key couple $(sk’,P’)$. If you know $sk$ and $t$, you can compute $sk’$ and thus sign things as $P’$, but if you only know $P’$, you cannot easily obtain $sk$, $t$ or $sk’$. The problem is exactly that the cannot easily obtain™ part gets completely annihilated by quantum computers. Given a public key $P’$, a quantum-enabled attacker would be able to:
- Make up any unlocking script that commits to any value $t’$, possibly one different from the original unlocking script which the tx was supposed to be using;
- Compute a corresponding private key $sk$ such that $sk$ and $t’$ generate $sk’$.
In layman terms: Every time we see a transaction, we can literally rewrite its unlocking conditions. This makes our (any?) fixes completely useless as a quantum-enabled hacker can bypass our unlocking script.
Enter BIP-360
Luckily for us, there’s a group of people, guided by Hunter Beast, that is pushing very hard to implement a new update proposal called BIP-360. This is rather technical, but in a nutshell, it is a patch to the “quantum-weak part” of taproot. Notice that this proposal does not directly fix Bitcoin’s problem, as the signatures BTC uses are still not quantum safe. But, as far as our proposal is concerned, BIP-360 is enough to make our fallback solution viable, effectively protecting everyone in a simple, opt-in fashion.
For now, this concludes our bumpy ride. We can only hope BIP-360 gets the attention it deserves, and is ultimately made part of the protocol. If this happens, we’ll be more than happy to do our part, as we are already doing for Ethereum!