One day having lunch at the MIT DCI and discussing OP_CAT and lamport signatures we came up with a scheme to do lamport signatures on Bitcoin transactions without OP_CAT.
This scheme has the following properties:
1. Should work with today's Bitcoin (no OP_CAT required).
2. Unlike other lamport signatures in Bitcoin script, this scheme signs the spending transaction.
Disclaimer: This is very preliminary work and the security of these signatures rests on a number of simplifying assumptions about ECDSA signatures that may not be true. Do not use this signature scheme in a Bitcoin output unless your intent is for that output to be a fun crypto bounty. I have not tested this in Bitcoin script.
This idea of using signature length shares a lot in common with sigPOW (signature POW) proposed by Robin Linus [3,4] and implemented by VzxPLnHqr [5] which uses signature length grinding as a transaction level POW mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA signature length constraints to force revealing signing key [6].
Our approach differs from the Jeremy Rubin's approach in [7] as we do not require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin's approach in [8] as our goal is to verify a Lamport signature on the spending transaction rather than a Lamport signature on arbitrary data. When compared with [7,8] our scheme is far less practical as it requires very large numbers of signatures (below we discuss 1000 signatures).
## 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 randomly chosen nonce
- dA is the signing key,
- z is derived from the hash of the signed message, i.e., transaction hash.
Our Lamport scheme is based on the following observation. ECDSA signatures in bitcoin are variable in length and that the length of an s-value in an ECDSA signature for a fixed nonce, k, and fixed signing key has its length determined by the transaction hash. We can use OP_SIZE to get the size of a signature and we can use Lamport signatures to sign this size. We explain Lamport signatures below.
The security of our scheme rests on a way to fix the nonce k. Madars Virza and Andrew Poelstra both pointed out to me when discussing this scheme that setting k=1/2, that is setting k to the multiplicative inverse of 2, results in a k with a very short r (r=0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) [0]. This means that the first 11 bytes (88-bits of the r value are zero and truncated) so the r-value is only 21 bytes long! A publicly known k leaks the signing key, but that doesn't matter for our purposes.
Using this k, we can ensure that the r values on two signatures are the same by inspecting their length using `OP_SIZE(sig) < (21+32+6)`. Grinding r to find a smaller value requires 2^96 (12 bytes of zeros) computations assuming no mathematical shortcut such as the one used to find k=1/2.
To explain how to use the above observative to sign Bitcoin transactions with Lamport signatures, let's remind ourselves how Lamport signatures [1] work. To sign 1-bit with a Lamport signature you first use a hash function H, to compute: x0 = H(y0), x1 = H(y1). Next, you publish x0,x1 as your public key. Then, to sign the bit 0, you release the value y0. Anyone can use y0 to verify that x0 == H(y0). To sign the bit 1, you release y1.
We use Lamport signatures to sign the length of a bitcoin signature. The length of the signature serves as a proxy for the transaction hash of the spending transaction. Repeating this many times provides cryptographic levels of security. Let's look at an example:
Alice computes her Lamport public keys and signing keys
x00 = Hash(y00)
x01 = Hash(y01)
x10 = Hash(y10)
x11 = Hash(y11)
x20 = Hash(y20)
x21 = Hash(y21)
In pseudocode Alice's 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 ecdsaSig1
PUSH x20, x21
if OP_SIZE (ecdsaSig2) == 59:
if OP_HASH(y20) != x10: OP_RETURN
else if OP_SIZE (ecdsaSig2) < 59:
if OP_HASH(y21) != x21: OP_RETURN
```
Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For example let’s say OP_SIZE(ecdsaSig0)=59, OP_SIZE(ecdsaSig1)=58, OP_SIZE(ecdsaSig2)=59. Thus, to spend she generates a Lamport signature over those lengths by releasing the preimages: y00, y11, y20.
The spend script pseudocode:
```
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
```
The advantage Alice has over an attacker attempting to steal her funds is that all Alice has to do is release the preimages for the lengths of all of her ECDSA signatures, but an attacker has to construct a transaction hash that matches the size of her signatures for each different ECDSA signature. The probability an attacker manages this for three random ECDSA signatures given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~= 0.3%. Alice can arbitrarily amplify her security by adding additional ECDSA signatures.
It was pointed out to me by Andrew Poelstra that the probability that a random signature is shorter by one byte is 1/256 because OP_SIZE only measures the byte length of a value, not the bit length. This means most of the time if Alice just used three ECDSA signatures, they would all be length 59. In such a case the attacker would have (255/256)^3 = 98% probability of generating a transaction that can be spent using Alice's signature on the attacker's very first try!
For this reason Alice really needs a lot of ECDSA signatures and probably also needs to grind for safer values to sign (safer = high diversity in length).
Assuming a simplistic model of ECDSA signatures length Prob(1-1/256) for length 59 and Prob(1/256) for length <59, the probability that Alice will generate exactly m <59-length signatures and n-m 59 length signatures is: `(255/256)^(n-m)*(1/256)^m*(n choose m)`.
An attacker would need to not only generate m <59-length signatures and n-m 59 length signatures, but generate them in the same position as Alice generated them. The probability an attacker will generate exactly m <59-length signatures and n-m 59 length signatures in the same position as Alice is: (255/256)^(n-m)*(1/256)^m
On average Alice would need 1000 attempts to sign with n=800,m=10. Whereas an attacker would need to make 2^84 attempts to brute force the output after seeing alice attempt to spend that output using a n=800,m=10 signature.
## Known weaknesses
1. *The Tuning Attack:* The attacker can use different SIG_HASH flags per signature to attack each signature individually. For instance ecdsaSig1 doesn't have the right length, the attacker can try SIGHASH_NONE to try again without changing any of the other signature lengths. This provides the attacker some advantage but with sufficient numbers of signatures it does not break the scheme. Alice can also use this approach to increase the security of her signatures by increasing length diversity. Unclear if this helps or hurts security more.
2. *Mix and Match Attack:* Even if an attacker can not grind a shorter r-value, an r-value of roughly 21-23 bytes would allow an attacker to make a few more individual attempts on a particular signature length. This is because we only measure the total length of the ECDSA signature, so a 23-byte r-value combined with a 29-byte s-value would be 23+29+6 = 58 bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but if an attacker managed to grind a 23-byte r-value at a cost of 2^72 computations, it would provide the attacker some advantage.
## Known Improvements
1. Rather than only signing if the length is 59 or less. We could extend the scheme to sign multiple ECDSA signature length values, 59, 58, 57, 56... This could enable Alice to greatly increase her security as say 56 would only occur 1 out of every 2^32 signatures. Winternitz One Time signatures (WOTs) [2] could be used here to compress signature length.
1. Jeremy Rubun suggested the following optimization: rather than directly signing the ECDSA signatures lengths, you construct a 32-bit bit vector of the signature lengths using OP_MUL, OP_ADD.
bit vector = OP_SIZE(ecdsaSig0)==59 + 2*(OP_SIZE(ecdsaSig1)==59) + 4*(OP_SIZE(ecdsaSig2)==59) ...
Then you compute a Winternitz One Time signature over this bit vector. This would require also computing a WInternitz or Lamport signature over a checksum of the bit vector. This would substantially reduce the number of lamport public keys and signing keys and likely reduce the size of redeem script and spend script by half.
3. Since 59 is the default length, Alice does not in fact need to sign 59. It could be inferred that if no preimage is given or say the preimage 0 is given, the length that Alice intends is 59. This would save space on the spend script and redeem script.
## Open Questions
1. Could OP_CODESEPARATOR be used by Alice or the attacker to either strengthen or weaken the security of this scheme. Alice using OP_CODESEPARATOR to strengthen the security of this scheme by increasing signature length diversity was suggested by Jeremy Rubin. After some discussion, the fact that the redeem script is part of the P2SH address means that the data in OP_CODESEPARATOR would still influence all the other ECDSA signatures. That said, perhaps there is some way it can be exploited to either help Alice or help the attacker.
2. If a nonce value k was discovered such that k*G = r = 1, we could remove the assumption that no could find a smaller r. It is unknown how to find r=1 as it requires finding the discrete log. It is possible to create transaction signatures that have r=1 without knowing k, through the use of ECDSA pubkey recovery. This does not work for our scheme as we must commit to the ECDSA public key in the spent transaction. Are there any known smaller r values than r=1/2*G?
3. How many bits of security does each ECDSA signature contribute in this scheme given the SIGHASH mix and match attack above? How many ECDSA signatures are needed? We have modeled ECDSA s-values signatures being uniformly drawn from 2^256. It seems unlikely to me that the Elliptic Curve math lines up perfectly with a 256 bit space especially for a fixed r-value that has special mathematical properties. Non-uniformity here could end up helping (increasing length diversity) or hurting (a pattern an attacker could exploit to match the length faster than brute force) the security.
4. An attacker could trade off brute forcing the transaction hash lengths by computing a small r-value. What does the time-memory trade look like here?
5. Is there any use for this beyond a fun party trick?
Thanks to Madars Virza, Dan Gould, Armin Sabouri, Neha Narula, Jeremy Rubin, Andrew Poelstra, Robin Linus for discussing this with me and giving me feedback. This initial discuss was fueled by the MIT DCI espresso machine. I've attempted to credit all ideas contributed to the contributor, if I got this wrong or missed a contribution shoot me an email. Any mistakes are my own as I wrote this up.
[0]: "Bitcoin Wallet Recovery via ECDSA Short Signatures"
https://github.com/demining/Bitcoin-Wallet-Recovery?tab=readme-ov-file [1]: "Constructing Digital Signatures from a One Way Function", Leslie Lamport (1979),
https://www.microsoft.com/en-us/research/publication/constructing-digital-signatures-one-way-function/[2]: "A Certified Digital Signature", Ralph C. Merkle (1979),
https://www.ralphmerkle.com/papers/Certified1979.pdf[3]: "Timelocked Proof of Work via signature length", Robin Linus (2021),
https://gist.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md[4]: "Proof of Work in Bitcoin Script", Robin Linus (2020),
https://github.com/coins/bitcoin-scripts/blob/master/proof-of-work.md[5]: "sig-pow - work-locked outputs", VzxPLnHqr (2022),
https://github.com/VzxPLnHqr/sig-pow/[6]: "[Lightning-dev] Better privacy with SNARKs", Anthony Towns (2015),
https://lists.linuxfoundation.org/pipermail/lightning-dev/2015-November/000344.html[7]: "Quantum Proofing Bitcoin with a CAT", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/06/quantum-bitcoin/[8]: "CheckSigFromStack for 5 Byte Values", Jeremy Rubin (2021),
https://rubin.io/blog/2021/07/02/signing-5-bytes/