Quantum-Resistant Bitcoin Transactions with Lamport Signatures

Quantum-Resistant Bitcoin Transactions with Lamport Signatures
Photo by Dan Cristian Pădureț / Unsplash

Ethan Heilman shared a method on the Bitcoin-Dev mailing list for requiring transactions to be signed by a Lamport signature to be considered valid. This approach can make spending P2SH and P2WSH outputs quantum-resistant. Additionally, according to Andrew Poelstra, it ensures that "size limits are now the only reason that Bitcoin doesn’t have covenants."

Key Properties

  1. Compatibility with Current Bitcoin Script: Works with current Bitcoin (no OP_CAT required).
  2. Direct Signing of Transactions: Unlike other Lamport signatures in Bitcoin script, this scheme signs the spending transaction.

Signing a Bitcoin Transaction with Lamport Signatures

An ECDSA signature (r, s) is calculated as:

  • r = (k * G)_x
  • s = (z + r * dA) / k
    • k is a randomly chosen nonce
    • dA is the signing key
    • z is derived from the hash of the signed message, i.e., the transaction hash

Heilman's Lamport scheme exploits the variability of ECDSA signature lengths and uses the OP_SIZE opcode to measure the size of the signature. The length of the signature is then signed using Lamport signatures.

Example Protocol

  1. Lamport Signatures: To sign one bit with a Lamport signature:
    • Compute: x0 = H(y0), x1 = H(y1)
    • Publish x0, x1 as the public key
    • To sign the bit 0, reveal y0; to sign the bit 1, reveal y1
  2. Signing Bitcoin Signature Lengths: Use Lamport signatures to sign the length of a Bitcoin signature, which serves as a proxy for the transaction hash.

Lamport Signature Example in Bitcoin Script

Alice computes her Lamport public and private keys:

x00 = Hash(y00)
x01 = Hash(y01)
x10 = Hash(y10)
x11 = Hash(y11)
x20 = Hash(y20)
x21 = Hash(y21)

Her redeem script looks like:

PUSH ecdsaPubkey0
OP_CHECKSIG (ecdsaSig0)
// Verify lamport signature on ecdsaSig0
PUSH x00, x01
if OP_SIZE(ecdsaSig0) == 59:
  if OP_HASH(y00) != x00: OP_RETURN
else if OP_SIZE(ecdsaSig0) < 59:
  if OP_HASH(y01) != x01: OP_RETURN

PUSH ecdsaPubkey1
OP_CHECKSIG (ecdsaSig1)
// Verify lamport signature on ecdsaSig1
PUSH x10, x11
if OP_SIZE(ecdsaSig1) == 59:
  if OP_HASH(y10) != x10: OP_RETURN
else if OP_SIZE(ecdsaSig1) < 59:
  if OP_HASH(y11) != x11: OP_RETURN

// Verify lamport signature on ecdsaSig2
PUSH ecdsaPubkey2
OP_CHECKSIG (ecdsaSig2)
// Verify lamport signature on ecdsaSig2
PUSH x20, x21
if OP_SIZE(ecdsaSig2) == 59:
  if OP_HASH(y20) != x20: OP_RETURN
else if OP_SIZE(ecdsaSig2) < 59:
  if OP_HASH(y21) != x21: OP_RETURN

Alice computes ECDSA signatures:

  • ecdsaSig0, ecdsaSig1, and ecdsaSig2

For instance, if OP_SIZE(ecdsaSig0)=59, OP_SIZE(ecdsaSig1)=58, and OP_SIZE(ecdsaSig2)=59, to spend, she releases the preimages y00, y11, and y20:

PUSH ecdsaSig0
PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 59
PUSH ecdsaSig1
PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be less than 59
PUSH ecdsaSig2
PUSH y20 // Signs that OP_SIZE(ecdsaSig2) should be 59

Understanding the Lamport Signature

Lamport public keys consist of two lists of hash digests, while Lamport signatures comprise preimages of selected hashes. A program shared between the signer and validator interprets the revealed preimages as instructions.

For instance, if Bob wants to verify that Alice has signed a number between 0 and 31 (binary range: 00000 to 11111), Alice would generate a Lamport private key from two lists of random numbers:

private_zeroes = [random(), random(), random(), random(), random()]
private_ones   = [random(), random(), random(), random(), random()]

She would then hash these private numbers to create her Lamport public key:

public_zeroes = [hash(private_zeroes[0]), ..., hash(private_zeroes[4])]
public_ones   = [hash(private_ones[0]), ..., hash(private_ones[4])]

Alice would share this public key with Bob. Later, if she wants to communicate the number 21 to him, she would send the following preimages:

private_ones[0]
private_zeroes[1]
private_ones[2]
private_zeroes[3]
private_ones[4]

In binary, the number 21 is represented as 10101. Bob verifies that each preimage matches the public keys he previously received, confirming that only Alice, with knowledge of the preimages, could have generated the message "21."

Understanding Bitcoin Signature Standards

Bitcoin uses the DER encoding standard for ECDSA signatures, which removes leading zero (0x00) bytes from the signature's two components. With random values, a 0x00 byte occurs naturally 1/256th of the time, causing Bitcoin signatures to vary in size. This variation is exacerbated by the fact that R values lead with a 0x00 byte half the time (see low-r grinding). In theory, this variation can reduce a transaction by one byte 1/256th of the time.

Even if a powerful quantum computer allows an attacker to create signatures without the private key, DER-encoded ECDSA signatures will still vary in length and must commit to the transactions that contain them. These transactions will also need to include any additional data necessary to make them valid, such as hash preimages.

This allows a P2SH redeem script to include an ECDSA signature check that commits to the transaction and a Lamport signature that commits to the exact size of the ECDSA signature. For instance:

OP_DUP <pubkey> OP_CHECKSIG OP_SIZE <size> OP_EQUAL
OP_IF
  # Size equals <size> bytes
  OP_SHA256 <digest_x> OP_CHECKEQUALVERIFY
OP_ELSE
  # Size is not equal to <size> bytes
  OP_SHA256 <digest_y> OP_CHECKEQUALVERIFY
OP_ENDIF

To satisfy this script fragment, the spender provides an ECDSA signature. The signature is duplicated and validated, and the script fails if it's not valid. In a post-quantum world, an attacker might pass this test, allowing validation to continue. The size of the duplicate signature is measured. If it's exactly <size> bytes, the spender must reveal the preimage for <digest_x>. This <size> can be set one byte smaller than usual, which occurs once every 256 signatures. Otherwise, in most cases or with a size-inflated signature, the spender must reveal the preimage for <digest_y>. If a valid preimage for the actual signature size isn't revealed, the script fails.

Strengthening Security with Multiple Signatures

Even if ECDSA is fully compromised, an attacker cannot spend the bitcoins unless they also know the Lamport private key. While this isn't groundbreaking on its own (since P2SH and P2WSH already offer this when script preimages are kept private), once the Lamport signature is published, an attacker reusing it with a forged ECDSA signature will have to ensure the ECDSA signature is the same length as the original. This may require signature grinding, which demands extra computational effort that an honest user wouldn't need to expend.

The amount of grinding required can be exponentially increased by including additional pairs of ECDSA and Lamport signatures. However, since ECDSA signatures vary in byte size only 1/256th of the time,

implementing this straightforwardly would require an impractically large number of signatures for meaningful security.

Ethan Heilman describes a more efficient mechanism that, although it exceeds P2SH's consensus limits (520-byte redeem script size), might just work within P2WSH's higher limits (10,000-byte max script size).

Known Weaknesses

  1. The Tuning Attack: The attacker can use different SIG_HASH flags per signature to attack each signature individually. For instance, if ecdsaSig1 doesn't have the right length, the attacker can try SIGHASH_NONE to try again without changing any of the other signature lengths.
  2. Mix and Match Attack: Even if an attacker can't grind a shorter r-value, an r-value of roughly 21-23 bytes allows an attacker to make more individual attempts on a particular signature length.

Known Improvements

  1. Rather than only signing if the length is 59 or less, the scheme could be extended to sign multiple ECDSA signature length values (e.g., 59, 58, 57, etc.).
  2. Jeremy Rubin suggested optimizing the signing process by constructing a 32-bit bit vector of the signature lengths using OP_MUL and OP_ADD.

Open Questions

  1. Could OP_CODESEPARATOR be used by Alice or the attacker to strengthen or weaken the security of this scheme?
  2. How many bits of security does each ECDSA signature contribute in this scheme?

Lamport Signatures and Covenant Implementation

This Lamport signature verification is conceptually similar to the proposed OP_CHECKSIGFROMSTACK opcode. Andrew Poelstra explained how Lamport signatures could be used alongside BitVM-style operations to implement a covenant. However, he cautions that such a combination would almost certainly violate at least one consensus size limit.

Heilman's approach to quantum-resistant Bitcoin transactions using Lamport signatures provides a creative solution to enhancing Bitcoin security in a future quantum computing world. Though challenges remain, further exploration and refinement of these techniques could lead to even stronger transaction mechanisms for Bitcoin.

Read more