Quantum-Resistant Bitcoin using Lamport Signatures

No fork needed

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. [1]

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].

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

1. Message Hashing: First, hash the message using a secure hash function H to ensure a fixed-length output.
2. 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.

Source: blog.cryptographyengineering.com

Signature Verification

1. 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.

Source: blog.cryptographyengineering.com

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.

// 512 * 256 bit random byte strings
type LamportPubKey = ByteString

// For msg of 256 bits.
type LamportSig = ByteString

class LamportP2PK extends SmartContract {

    @prop()
    pubKey: LamportPubKey

    constructor(pubKey: LamportPubKey) {
        super(...arguments)
        this.pubKey = pubKey
    }

    @method()
    public unlock(sig: LamportSig) {
        const m = byteString2Int(hash256(this.ctx.serialize()))
        
        // Loop over each bit of the hash.
        for (let i = 0; i < 256; i++) {
            let offset = 0n
            if (and(lshift(m, BigInt(i)), 1n) == 0n) {
                offset = 256n * 32n
            }
            
            const start = BigInt(i) * 32n
            const sigChunk = slice(sig, start, start + 32n)

            const pkChunkStart = offset + start
            const pkChunk = slice(this.pubKey, pkChunkStart, pkChunkStart + 32n)
            assert(hash256(sigChunk) == pkChunk, `sig chunk ${i} hash mismatch`)
        }
    }
}

We have successfully made the first transaction using Lamport signatures on Bitcoin:

97f055bccb27539604de9ed99f1067f76fb7cae29b00fbc0a7bb744c8e0c74d8

The full source code of this contract along with some tests can be found on GitHub.

Discussion

There are optimizations to make Lamport signatures more efficient, in terms of signature and key size.

There are also alternative approaches of using smart contracts to make Bitcoin quantum-resistant without breaking changes, such as addictive hashes.

[1] Bitcoin and Quantum Computing: Craig S Wright 2017