This post was first published on Medium.
As quantum computing potentially transitions from theory to practice, its implications forcryptographic systems, particularly those underpinning cryptocurrencies like Bitcoin, become increasingly profound. Bitcoin, reliant on the Elliptic Curve Digital Signature Algorithm (ECDSA), faces potential vulnerability in the quantum era.
If quantum computers ever become sufficiently powerful, we provide a way to make Bitcoin resistant to its attacks by usingLamport Signatures. Thecrucial ideais to program Lamport Signatures insmart contracts, and thusnochange/”fix” to the base layer is needed. This drastically differs from existing approach of upgrading Bitcoin’s cryptographic algorithms via a fork (softfork or hardfork) to be quantum-resistant, which arecurrently favored by so-called Bitcoin experts.
The truth is that Bitcoin was always quantum resistant.1
Whether a quantum attack on Bitcoin is viable, both technically andeconomically, is outside the scope of this article. For interested readers seeking more in-depth information on the topic, it is recommended to explore additional resources such as [1].
Quantum computers and Bitcoin
Quantum computers operate on the principles of quantum mechanics, allowing them to perform complex calculations at speeds unattainable by classical computers. This capability poses a significant threat to cryptographic algorithms like the elliptic curve digital signature algorithm (ECDSA) used in Bitcoin, which hinges on the infeasibility of deriving private keys from public keys. Quantum algorithms, such asShor’s algorithm, could theoretically break ECDSA, thereby compromisingBitcoin’s security model.
Lamport Signatures
In response to this looming threat, Lamport signatures, a one-time signature scheme using hash functions, emerge as a quantum-resistant alternative. Contrary to ECDSA’s reliance on number-theoretic assumptions vulnerable to quantum computing, Lamport signatures derive their security from the difficulty of inverting hash functions, which remain robust against known quantum attacks.
Here is a concise technical description of how Lamport signatures work:
Key Generation
- Private Key:Generate a pair of large random numbers for each bit of the message to be signed. For a 256-bit message, this results in 512 random bitstrings. These 512 strings form the private key. To simplify matters, we will organize these strings into two distinct lists and designate each list by an index in the following manner:
- Public Key:Apply a cryptographic hash function H to each of the 512 strings in the private key. The output forms the public key.
Signing
- Message Hashing:First, hash the message using a secure hash function H to ensure a fixed-length output.
- Creating the Signature: For each bit of the hashed message, select one string from either pair in the private key. If the bit is 0, select from the first; if 1, select from the second. The collection of these selections forms the signature.
Signature Verification
- Hashing Selected Numbers:
- Apply the same cryptographic hash function used in the key generation to each string in the signature.
Comparing with Public Key:
- Alignment with Public Key Bits:Align the hashed numbers from the signature with the corresponding parts of the public key, based on the bits of the hashed message.
- Verification:Check if the hashes of the signature string match the corresponding strings in the public key. If all pairs match, the signature is valid.
Lamport signatures are “one time signature” and necessitate a new signing key for each transaction, whose one-time nature aligns with Bitcoin’s single-use address model. The signatures are larger than ECDSA signatures but only at ~16 KB, making them practical today.
Implementation
We have implemented a working example of Lamport signature verification. The code is rather simple. The smart contract exposes a single public method called “unlock,” which allows a redeemer to take thelocked bitcoinsby providing a valid Lamport signature. On a higher level, this is pretty much the same mechanism as in a standard P2PK(H) transaction.
We have successfully made the first transaction using Lamport signatures on Bitcoin:
97f055bccb27539604de9ed99f1067f76fb7cae29b00fbc0a7bb744c8e0c74d8
Thefull source codeof this contract, along withsome tests, can be found on GitHub.
Discussion
There areoptimizationsto make Lamport signatures more efficient in terms of signature and key size.
There are also alternative approaches to using smart contracts to make Bitcoin quantum-resistant without breaking changes, such asaddictive hashes.
***
[1]Bitcoin and Quantum Computing:Craig S Wright2017
Watch: sCrypt applications are proving how powerful Bitcoin is
