[DRAFT] Bitcoin’s Post-Quantum Transition

Status

This article depends on a (probably) incorrect assumption that in a post-quantum world, RIPEMD160(ECC_PUBLICKEY) addresses will be completely vulnerable.

This is (probably) not the case, as Grover’s algorithm reduces the effective bit strength of a preimage attack on RIPEMD160 to 80 bits or 1/2, not ~53 bits or 1/3 (which is actually the bit strength against collision attacks).

If a classical or post-quantum pre-image attack is found for RIPEMD160, then the final solution laid out in this article may be of value.

— Original Article —

How to prepare now — no hard forks required.

This article assumes a basic understanding of public key cryptography and the threat imposed by quantum computing.

Bitcoin’s relationship with ECDSA is temporary

Due to its nature as a store of value, Bitcoin is the first application of digital signatures that needs to operate on a time scale of decades: the same time scale in which major cryptographic advances are made.

This means that no matter which digital signature algorithm is protecting Bitcoin, there will always be a risk that the algorithm or implementation will be broken. Unlike the Internet, which may suffer losses but will ultimately recover after a switch — once broken, Bitcoin will never recover its value as ownership of any balance cannot be reliably proven.

The Bitcoin community needs to prepare for the day that the Elliptic Curve Digital Signature Algorithm (ECDSA) is broken — whether by the development of a quantum computer, or by the discovery of a flaw exploitable by classical computing.

How an ECDSA vulnerability could be exploited to attack Bitcoin

There are many ways in which an attacker in possession of an ECDSA vulnerability (either a quantum computer capable of breaking it, or another flaw in the algorithm) could attack Bitcoin.

The biggest challenge an attacker faces is avoiding detection: the moment the vulnerability in ECDSA is known, Bitcoin will quickly become worthless, limiting the attacker’s ability to profit from the exercise.

An adversary in possession of such a vulnerability may employ a combination of any of the following attacks:

1. Attacker subverts SSL to MITM a connection with an exchange, sending user’s Bitcoin to their own address
2. Attacker breaks addresses randomly and sends funds to themselves
3. Attacker waits until hard fork to a post-quantum DSA chain and uses the vulnerability to claim balances on the new chain
4. Attacker shorts Bitcoin, then releases the vulnerability, making Bitcoin worthless

Attack 1 is particularly effective because the symptoms of the attack are exactly the same as the exchange or user’s device being compromised. It may be a while before the exchanges and users stop blaming each other and realise there is a problem, by which point the attacker would have cashed out. This attack works because a vulnerability in ECDSA will also likely affect ECDH, a key agreement protocol widely supported by SSL.

Attack 2 is risky because the moment coins are stolen from a cold wallet belonging to a person with the right kind of knowledge/experience, the alarm will be raised. And if conducted at too high a volume the same will happen. This attack is most effective if carried out against a single high-value address (although not Satoshi’s, as any movement of these coins will likely crash the market).

Attack 3 is the most effective attack that does not reveal the identity of the attacker or even require the attacker have an account on an exchange — and if only a portion of addresses are attacked, the post-quantum fork will probably hold some value. This does, however, require that a scalable post-quantum cryptocurrency exists (none does currently, see more on this below).

Attack 4 is the most effective overall because:

1. The outcome (crash of Bitcoin price) is guaranteed, and thus the short can be highly leveraged
2. It does not rely on non-detection of the vulnerability
3. It does not rely on Bitcoin (or the post-quantum fork) retaining any value
4. It does not require theft of funds or hacking of any kind, which may reduce scope for legal fallout
5. The short can be executed as a gradually accumulated, leveraged long on an established post-quantum cryptocurrency, removing exposure to fiat and potentially protecting the attacker’s identity

If no scalable post-quantum cryptocurrency exists, the attacker will need to short Bitcoin on a fiat pairing — introducing a KYC check that can be used to identify the attacker. Either way, a leveraged short on Bitcoin is likely to be more profitable.

Suitable post-quantum algorithms for Bitcoin

Critical to the decentralization of Bitcoin is reducing the resources required to maintain the blockchain: storage, bandwidth and compute.

The DSA characteristics that impact this are public key length, signature length and verification time, and in all regards ECDSA shines.

XMSS

XMSS, one of the post-quantum digital signatures schemes recommended by the PQCrypto project and implemented by the Quantum Resistant Ledger project (QRL), has similar verification performance to ECDSA, but variable public key and signature sizes depending upon the signature capacity of a public address.

Using the configuration QRL selected and the best-case number of signatures (up to 4 per address), here is how XMSS compares against ECDSA if it were used at Bitcoin scale:

The figure for bandwidth assumes that every block is received once by each incoming connection and sent once to each outgoing connection.

It’s pretty clear that QRL decentralization will suffer if it operates even close to Bitcoin’s scale.

What XMSS does have, however, is provable security.

SPHINCS

The only other algorithm recommended by the PQCrypto group, SPHINCS, has a signature length of 41kb, making it completely unsuitable for Bitcoin.

Other Algorithms

At the moment the industry has its eyes on the work NIST is doing to analyse and standardize post-quantum cryptographic algorithms, however this process will take some years to complete.

Signature Compression

Back in the world of classical cryptography, significant advances in signature compression (and obfuscation) have been made with bulletproofs which have the potential to reduce the size of the blockchain by an order of magnitude while also increasing privacy. A similar approach could potentially be used to mitigate the large size of post-quantum digital signatures and/or public keys, however this is unlikely for hash-based cryptography due to complete non-malleability.

Post-Quantum Address Recovery

Not all cryptographic constructions are vulnerable to quantum computing.

The best quantum attack on most symmetric encryption and cryptographic hashing schemes is Grover’s Algorithm, which at best reduces the classical security margin of an algorithm to its square root.

This means that a 256 bit hash, in a post-quantum world, will have 128 bits of security — a widely accepted security margin, and the reason why hash algorithms underpin many of the proposed post-quantum digital signature algorithms (including SPHINCS and XMSS).

A cryptographic hash or hash-based digital signature algorithm can be used to securely transfer a balance from an ECDSA address to a post-quantum address, even if ECDSA is broken.

Here three progressively improving solutions are proposed that both mitigate an early ECDSA attack and allow secure transition to a post-quantum address space.

All three solutions have the following assumptions:

• The post-quantum hard fork will be initiated from a specific block, with all ECDSA transactions being rejected post-fork
• A post-quantum address will need to perform some action to claim the balance associated with a given ECDSA address

(Naive) Solution 1: OP_RETURN Commitment

Additional data can be added to any bitcoin transaction using the OP_RETURN opcode. This supports a variety of use cases — most notably proof of existence.

Whenever a Bitcoin address is generated, a null-value OP_RETURN transaction back to the same address can be crafted including a hash commitment, linking the commitment and the Bitcoin address. Only the first such commitment will be accepted — and the Bitcoin blockchain is perfect for establishing which commitment came first.

To claim the balance, the post-quantum address must first broadcast the ECDSA address, and then within a specified period of time, broadcast the pre-image used to generate that address.

It can’t just broadcast the pre-image in a single transaction as any peer or miner can instantly duplicate the broadcast and potentially claim the balance for themselves.

The claim is validated against the first commitment issued by the ECDSA address.

This solution has multiple issues:

1. As every Bitcoin address is single-use, this will double transaction volumes (and more than double transaction fees per actual movement of value)
2. Malicious users can “cybersquat” ECDSA addresses, preventing the real owner from claiming their balance
3. Broadcasting the pre-image necessarily reveals it to miners, which could work together to censor high-value claims, wait for the timeout and then claim the balances themselves

(Naive) Solution 2: Private Key Commitment

In this approach, a hash commitment is used to generate the private key.

The claim is validated by confirming that the pre-image does indeed generate the given ECDSA address.

As no transaction is required to associate the commitment with the ECDSA address, issue #1 in the above solution is solved, but issues #2 and #3 remain.

Solution 3: Multi-Layer Private Keys

This approach is like the above, except it uses the public key of a post-quantum digital signature algorithm to generate the private ECDSA key.

There is no need to claim balances — the underlying post-quantum public key becomes the new address. If no UTXO exists for the post-quantum address, then it is converted to an ECDSA keypair and UTXOs attached to the ECDSA public key can be used to fund the transaction.

This has the added advantage that the underlying post-quantum algorithm can be changed (upgraded) without modifying the Bitcoin client. As successive algorithms are developed (and sustain years of cryptanalysis), the algorithm used to generate post-quantum ECDSA addresses can be upgraded to mitigate against the worst possible outcome.

And finally, when an algorithm/scheme arrives that fulfils Bitcoin’s scalability needs, this very same mechanism can be used to perform the upgrade to post-quantum Bitcoin addresses.

For now, it seems like the optimal post-quantum digital signature scheme is XMSS with the configuration selected by the QRL project.

Conclusion

This article explored four attack vectors on Bitcoin utilizing an ECDSA vulnerability; assessed the scalability of recommended post-quantum digital signature algorithms and proposed an approach to safely transfer ownership of Bitcoin balances to a post-quantum chain.

Specifically, this approach works even if ECDSA is already compromised, and requires no changes to the Bitcoin protocol — only changes to wallets are required.

TOKENIZE.IO