Quantum-resistant Bitcoin using Lamport Signatures

Getting your Trinity Audio player ready...

This post was first published on Medium.

As quantum computing potentially transitions from theory to practice, its implications for cryptographic 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 using Lamport Signatures. The crucial idea is to program Lamport Signatures in smart contracts, and thus no change/”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 are currently favored by so-called Bitcoin experts.

The truth is that Bitcoin was always quantum resistant.¹

Whether a quantum attack on Bitcoin is viable, both technically and economically, 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].

Bitcoin shield digital security concept

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 as Shor’s algorithm, could theoretically break ECDSA, thereby compromising Bitcoin’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.

using private keys for hashing and signing

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.

Comparing with Public Key

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 the locked bitcoins by providing a valid Lamport signature. On a higher level, this is pretty much the same mechanism as in a standard P2PK(H) transaction.

Impelementation