public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
@ 2024-04-29  0:30 Ethan Heilman
  2024-04-30 12:32 ` Matthew Zipkin
  0 siblings, 1 reply; 18+ messages in thread
From: Ethan Heilman @ 2024-04-29  0:30 UTC (permalink / raw)
  To: Bitcoin Development Mailing List

[-- Attachment #1: Type: text/plain, Size: 13647 bytes --]

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/

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 15004 bytes --]

^ permalink raw reply	[flat|nested] 18+ messages in thread
end of thread, other threads:[~2024-05-11 16:27 UTC | newest]

Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-04-29  0:30 [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed) Ethan Heilman
2024-04-30 12:32 ` Matthew Zipkin
2024-04-30 13:25   ` Ethan Heilman
2024-04-30 14:21   ` Andrew Poelstra
2024-04-30 20:43     ` Ethan Heilman
2024-05-01  3:46       ` Antoine Riard
2024-05-01 20:02         ` Ethan Heilman
2024-05-06  7:39     ` David A. Harding
2024-05-06 16:48       ` Andrew Poelstra
2024-05-06 18:56         ` David A. Harding
2024-05-06 19:06           ` Andrew Poelstra
2024-05-07  0:55             ` Antoine Riard
2024-05-07 16:05               ` Ethan Heilman
2024-05-07  4:11             ` David A. Harding
2024-05-07 14:34               ` Andrew Poelstra
2024-05-09  0:31     ` Ben Carman
2024-05-09 12:46       ` Andrew Poelstra
2024-05-11  2:53         ` Antoine Riard

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox