Delivery-date: Tue, 30 Apr 2024 05:45:16 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of pinheadmz@gmail.com designates 2607:f8b0:4864:20::62f as permitted sender) client-ip=2607:f8b0:4864:20::62f;
MIME-Version: 1.0
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
In-Reply-To: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
From: Matthew Zipkin <pinheadmz@gmail.com>
Date: Tue, 30 Apr 2024 08:32:42 -0400
Message-ID: <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
To: Ethan Heilman <eth3rs@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="000000000000a29bba06174f91a8"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--000000000000a29bba06174f91a8
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

We discussed this scheme at NY BitDevs last night and one participant made
a great point:

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

If we are assuming discrete log is still hard, why do we need Lamport
signatures at all? In a post-quantum world, finding k such that r is 21
bytes or less is efficient for the attacker.


On Sun, Apr 28, 2024 at 8:50=E2=80=AFPM Ethan Heilman <eth3rs@gmail.com> wr=
ote:

> 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 VzxPLnHq=
r
> [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 =3D (k*G)_x, s=3D (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 has=
h.
>
> Our Lamport scheme is based on the following observation. ECDSA signature=
s
> 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 lengt=
h
> 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 Virz=
a
> and Andrew Poelstra both pointed out to me when discussing this scheme th=
at
> setting k=3D1/2, that is setting k to the multiplicative inverse of 2,
> results in a k with a very short r
> (r=3D0x00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63) =
[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)`. Grindin=
g
> 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=3D1/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 functi=
on
> H, to compute: x0 =3D H(y0), x1 =3D H(y1). Next, you publish x0,x1 as you=
r
> public key. Then, to sign the bit 0, you release the value y0. Anyone can
> use y0 to verify that x0 =3D=3D 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 =3D Hash(y00)
> x01 =3D Hash(y01)
> x10 =3D Hash(y10)
> x11 =3D Hash(y11)
> x20 =3D Hash(y20)
> x21 =3D 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) =3D=3D 59:
>   if OP_HASH(y00) !=3D x00: OP_RETURN
> else if OP_SIZE (ecdsaSig0) < 59:
>   if OP_HASH(y01) !=3D x01: OP_RETURN
>
> PUSH ecdsaPubkey1
> OP_CHECKSIG (ecdsaSig1)
> // Verify lamport signature on ecdsaSig1
> PUSH x10, x11
> if OP_SIZE (ecdsaSig1) =3D=3D 59:
>   if OP_HASH(y10) !=3D x10: OP_RETURN
> else if OP_SIZE (ecdsaSig1) < 59:
>   if OP_HASH(y11) !=3D 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) =3D=3D 59:
>   if OP_HASH(y20) !=3D x10: OP_RETURN
> else if OP_SIZE (ecdsaSig2) < 59:
>   if OP_HASH(y21) !=3D x21: OP_RETURN
> ```
>
> Alice computes the ECDSA signatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For
> example let=E2=80=99s say OP_SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D5=
8,
> OP_SIZE(ecdsaSig2)=3D59. 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 has=
h
> that matches the size of her signatures for each different ECDSA signatur=
e.
> The probability an attacker manages this for three random ECDSA signature=
s
> given the lengths above (59,58,59) is 255/256 * 1/256 * 255/256 ~=3D 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 =3D 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 =3D 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 a=
s
> Alice is: (255/256)^(n-m)*(1/256)^m
>
> On average Alice would need 1000 attempts to sign with n=3D800,m=3D10. Wh=
ereas
> 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=3D800,m=3D10
> 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 t=
he
> security of her signatures by increasing length diversity. Unclear if thi=
s
> 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 mak=
e
> 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 =3D 58
> bytes. 29-byte s-value are rare and occur with ~1/2^24 probability, but i=
f
> 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 directl=
y
> signing the ECDSA signatures lengths, you construct a 32-bit bit vector o=
f
> the signature lengths using OP_MUL, OP_ADD.
>
> bit vector =3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D59=
) +
> 4*(OP_SIZE(ecdsaSig2)=3D=3D59) ...
>
> 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 i=
s
> 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 oth=
er
> ECDSA signatures. That said, perhaps there is some way it can be exploite=
d
> to either help Alice or help the attacker.
>
> 2. If a nonce value k was discovered such that k*G =3D r =3D 1, we could
> remove the assumption that no could find a smaller r. It is unknown how t=
o
> find r=3D1 as it requires finding the discrete log. It is possible to cre=
ate
> transaction signatures that have r=3D1 without knowing k, through the use=
 of
> ECDSA pubkey recovery. This does not work for our scheme as we must commi=
t
> to the ECDSA  public key in the spent transaction. Are there any known
> smaller r values than r=3D1/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 Cur=
ve
> math lines up perfectly with a 256 bit space especially for a fixed r-val=
ue
> that has special mathematical properties. Non-uniformity here could end u=
p
> 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 givin=
g
> me feedback. This initial discuss was fueled by the MIT DCI espresso
> machine. I've attempted to credit all ideas contributed to the contributo=
r,
> 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=3Dreadme-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/0=
00344.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%2BXyW8wNOekw13C5jDM=
zQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com
> <https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jD=
MzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com?utm_medium=3Demail&utm_so=
urce=3Dfooter>
> .
>

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/=
bitcoindev/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw%40mail.gma=
il.com.

--000000000000a29bba06174f91a8
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>We discussed this scheme at NY BitDevs last night and=
 one participant made a great point:</div><div><br></div><div>&gt; if an at=
tacker managed to grind a 23-byte r-value at a cost of 2^72 computations, i=
t would provide the attacker some advantage.</div><div><br></div><div>If we=
 are assuming discrete log is still hard, why do we need Lamport signatures=
 at all? In a post-quantum world, finding k such that r is 21 bytes or less=
 is efficient for the attacker.<br></div><div><br></div></div><br><div clas=
s=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sun, Apr 28, 202=
4 at 8:50=E2=80=AFPM Ethan Heilman &lt;<a href=3D"mailto:eth3rs@gmail.com">=
eth3rs@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa=
dding-left:1ex"><div dir=3D"ltr">One day having lunch at the MIT DCI and di=
scussing OP_CAT and lamport signatures we came up with a scheme to do lampo=
rt signatures on Bitcoin transactions without OP_CAT.<br><br>This scheme ha=
s the following properties:<br>1. Should work with today&#39;s Bitcoin (no =
OP_CAT required).<br>2. Unlike other lamport signatures in Bitcoin script, =
this scheme signs the spending transaction.<br><br>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 no=
t use this signature scheme in a Bitcoin output unless your intent is for t=
hat output to be a fun crypto bounty. I have not tested this in Bitcoin scr=
ipt.<br><br>This idea of using signature length shares a lot in common with=
 sigPOW (signature POW) proposed by Robin Linus [3,4] and implemented by Vz=
xPLnHqr [5] which uses signature length grinding as a transaction level POW=
 mechanism and earlier work by Anthony Towns and Greg Maxwell using ECDSA s=
ignature length constraints to force revealing signing key [6].<br><br>Our =
approach differs from the Jeremy Rubin&#39;s approach in [7] as we do not r=
equire OP_CAT and we use P2SH not tapscript and from Jeremy Rubin&#39;s app=
roach in [8] as our goal is to verify a Lamport signature on the spending t=
ransaction rather than a Lamport signature on arbitrary data. When compared=
 with [7,8] our scheme is far less practical as it requires very large numb=
ers of signatures (below we discuss 1000 signatures).<br><br>## Signing a B=
itcoin Transaction with Lamport Signatures<br><br>An ECDSA signature (r,s) =
is calculated as r =3D (k*G)_x, s=3D (z+r*dA)/k<br>- k is randomly chosen n=
once<br>- dA is the signing key, <br>- z is derived from the hash of the si=
gned message, i.e., transaction hash.<br><br>Our Lamport scheme is based on=
 the following observation. ECDSA signatures in bitcoin are variable in len=
gth and that the length of an s-value in an ECDSA signature for a fixed non=
ce, k, and fixed signing key has its length determined by the transaction h=
ash. We can use OP_SIZE to get the size of a signature and we can use Lampo=
rt signatures to sign this size. We explain Lamport signatures below.<br><b=
r>The security of our scheme rests on a way to fix the nonce k. Madars Virz=
a and Andrew Poelstra both pointed out to me when discussing this scheme th=
at setting k=3D1/2, that is setting k to the multiplicative inverse of 2, r=
esults in a k with a very short r (r=3D0x00000000000000000000003b78ce563f89=
a0ed9414f5aa28ad0d96d6795f9c63) [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 byte=
s long! A publicly known k leaks the signing key, but that doesn&#39;t matt=
er for our purposes.<br><br>Using this k, we can ensure that the r values o=
n two signatures are the same by inspecting their length using `OP_SIZE(sig=
) &lt; (21+32+6)`. Grinding r to find a smaller value requires 2^96 (12 byt=
es of zeros) computations assuming no mathematical shortcut such as the one=
 used to find k=3D1/2.<br><br><br>To explain how to use the above observati=
ve to sign Bitcoin transactions with Lamport signatures, let&#39;s remind o=
urselves how Lamport signatures [1] =C2=A0work. To sign 1-bit with a Lampor=
t signature you first use a hash function H, to compute: x0 =3D H(y0), x1 =
=3D H(y1). Next, you publish x0,x1 as your public key. Then, to sign the bi=
t 0, you release the value y0. Anyone can use y0 to verify that x0 =3D=3D H=
(y0). To sign the bit 1, you release y1.<br><br>We use Lamport signatures t=
o sign the length of a bitcoin signature. The length of the signature serve=
s as a proxy for the transaction hash of the spending transaction. Repeatin=
g this many times provides cryptographic levels of security. Let&#39;s look=
 at an example:<br><br>Alice computes her Lamport public keys and signing k=
eys<br>x00 =3D Hash(y00) <br>x01 =3D Hash(y01)<br>x10 =3D Hash(y10)<br>x11 =
=3D Hash(y11)<br>x20 =3D Hash(y20)<br>x21 =3D Hash(y21)<br><br>In pseudocod=
e Alice&#39;s redeem script looks like:<br>```<br>PUSH ecdsaPubkey0<br>OP_C=
HECKSIG (ecdsaSig0)<br>// Verify lamport signature on ecdsaSig0<br>PUSH x00=
, x01<br>if OP_SIZE (ecdsaSig0) =3D=3D 59:<br>=C2=A0 if OP_HASH(y00) !=3D x=
00: OP_RETURN<br>else if OP_SIZE (ecdsaSig0) &lt; 59:<br>=C2=A0 if OP_HASH(=
y01) !=3D x01: OP_RETURN<br><br>PUSH ecdsaPubkey1<br>OP_CHECKSIG (ecdsaSig1=
)<br>// Verify lamport signature on ecdsaSig1<br>PUSH x10, x11<br>if OP_SIZ=
E (ecdsaSig1) =3D=3D 59:<br>=C2=A0 if OP_HASH(y10) !=3D x10: OP_RETURN<br>e=
lse if OP_SIZE (ecdsaSig1) &lt; 59:<br>=C2=A0 if OP_HASH(y11) !=3D x11: OP_=
RETURN<br><br>// Verify lamport signature on ecdsaSig2<br>PUSH ecdsaPubkey2=
<br>OP_CHECKSIG (ecdsaSig2)<br>// Verify lamport signature on ecdsaSig1<br>=
PUSH x20, x21<br>if OP_SIZE (ecdsaSig2) =3D=3D 59:<br>=C2=A0 if OP_HASH(y20=
) !=3D x10: OP_RETURN<br>else if OP_SIZE (ecdsaSig2) &lt; 59:<br>=C2=A0 if =
OP_HASH(y21) !=3D x21: OP_RETURN<br>```<br><br>Alice computes the ECDSA sig=
natures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For example let=E2=80=99s say OP_=
SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D58, OP_SIZE(ecdsaSig2)=3D59. Thu=
s, to spend she generates a Lamport signature over those lengths by releasi=
ng the preimages: y00, y11, y20.<br><br>The spend script pseudocode:<br>```=
<br>PUSH ecdsaSig0<br>PUSH y00 // Signs that OP_SIZE(ecdsaSig0) should be 5=
9<br>PUSH ecdsaSig1<br>PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should be =
less than 59<br>PUSH ecdsaSig2<br>PUSH y20 // Signs that OP_SIZE(ecdsaSig2)=
 should be 59<br>```<br><br>The advantage Alice has over an attacker attemp=
ting to steal her funds is that all Alice has to do is release the preimage=
s for the lengths of all of her ECDSA signatures, but an attacker has =C2=
=A0to construct a transaction hash that matches the size of her signatures =
for each different ECDSA signature. The probability an attacker manages thi=
s for three random ECDSA signatures given the lengths above (59,58,59) is 2=
55/256 * 1/256 * 255/256 ~=3D 0.3%. Alice can arbitrarily amplify her secur=
ity by adding additional ECDSA signatures.<br><br>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 val=
ue, not the bit length. This means most of the time if Alice just used thre=
e ECDSA signatures, they would all be length 59. In such a case the attacke=
r would have (255/256)^3 =3D 98% probability of generating a transaction th=
at can be spent using Alice&#39;s signature on the attacker&#39;s very firs=
t try!<br><br>For this reason Alice really needs a lot of ECDSA signatures =
and probably also needs to grind for safer values to sign (safer =3D high d=
iversity in length).<br><br>Assuming a simplistic model of ECDSA signatures=
 length Prob(1-1/256) for length 59 and Prob(1/256) for length &lt;59, the =
probability that Alice will generate exactly m &lt;59-length signatures and=
 n-m 59 length signatures is: `(255/256)^(n-m)*(1/256)^m*(n choose m)`. <br=
><br>An attacker would need to not only generate m &lt;59-length signatures=
 and n-m 59 length signatures, but generate them in the same position as Al=
ice generated them. The probability an attacker will generate exactly m &lt=
;59-length signatures and n-m 59 length signatures in the same position as =
Alice is: (255/256)^(n-m)*(1/256)^m<br><br>On average Alice would need 1000=
 attempts to sign with n=3D800,m=3D10. Whereas an attacker would need to ma=
ke 2^84 attempts to brute force the output after seeing alice attempt to sp=
end that output using a n=3D800,m=3D10 signature.<br><br>## Known weaknesse=
s<br><br>1. *The Tuning Attack:* The attacker can use different SIG_HASH fl=
ags per signature to attack each signature individually. For instance ecdsa=
Sig1 doesn&#39;t have the right length, the attacker can try SIGHASH_NONE t=
o try again without changing any of the other signature lengths. This provi=
des the attacker some advantage but with sufficient numbers of signatures i=
t does not break the scheme. Alice can also use this approach to increase t=
he security of her signatures by increasing length diversity. Unclear if th=
is helps or hurts security more.<br><br>2. *Mix and Match Attack:* Even if =
an attacker can not grind a shorter r-value, an r-value of roughly 21-23 by=
tes would allow an attacker to make a few more individual attempts on a par=
ticular 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-valu=
e would be 23+29+6 =3D 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.=
<br><br>## Known Improvements<br><br>1. Rather than only signing if the len=
gth is 59 or less. We could extend the scheme to sign multiple ECDSA signat=
ure length values, 59, 58, 57, 56... This could enable Alice to greatly inc=
rease her security as say 56 would only occur 1 out of every 2^32 signature=
s. Winternitz One Time signatures (WOTs) [2] could be used here to compress=
 signature length.<br><br>1. Jeremy Rubun suggested the following optimizat=
ion: rather than directly signing the ECDSA signatures lengths, you constru=
ct a 32-bit bit vector of the signature lengths using OP_MUL, OP_ADD. <br><=
br>bit vector =3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D5=
9) + 4*(OP_SIZE(ecdsaSig2)=3D=3D59) ...<br><br>Then you compute a Winternit=
z One Time signature over this bit vector. This would require also computin=
g a WInternitz or Lamport signature over a checksum of the bit vector. This=
 would substantially reduce the number of lamport public keys and signing k=
eys and likely reduce the size of redeem script and spend script by half.<b=
r><br>3. Since 59 is the default length, Alice does not in fact need to sig=
n 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.<br><br><br>## Open Questions<br><br>1. =
Could OP_CODESEPARATOR be used by Alice or the attacker to either strengthe=
n or weaken the security of this scheme. Alice using OP_CODESEPARATOR to st=
rengthen the security of this scheme by increasing signature length diversi=
ty 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_CODESEP=
ARATOR would still influence all the other ECDSA signatures. That said, per=
haps there is some way it can be exploited to either help Alice or help the=
 attacker.<br><br>2. If a nonce value k was discovered such that k*G =3D r =
=3D 1, we could remove the assumption that no could find a smaller r. It is=
 unknown how to find r=3D1 as it requires finding the discrete log. It is p=
ossible to create transaction signatures that have r=3D1 without knowing k,=
 through the use of ECDSA pubkey recovery. This does not work for our schem=
e as we must commit to the ECDSA =C2=A0public key in the spent transaction.=
 Are there any known smaller r values than r=3D1/2*G?<br><br>3. How many bi=
ts of security does each ECDSA signature contribute in this scheme given th=
e 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 w=
ith a 256 bit space especially for a fixed r-value that has special mathema=
tical properties. Non-uniformity here could end up helping (increasing leng=
th diversity) or hurting (a pattern an attacker could exploit to match the =
length faster than brute force) the security.<br><br>4. An attacker could t=
rade off brute forcing the transaction hash lengths by computing a small r-=
value. What does the time-memory trade look like here?<br><br>5. Is there a=
ny use for this beyond a fun party trick?<br><br>Thanks to Madars Virza, Da=
n Gould, Armin Sabouri, Neha Narula, Jeremy Rubin, Andrew Poelstra, Robin L=
inus for discussing this with me and giving me feedback. This initial discu=
ss was fueled by the MIT DCI espresso machine. I&#39;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.=
<br><br>[0]: &quot;Bitcoin Wallet Recovery via ECDSA Short Signatures&quot;=
 <a href=3D"https://github.com/demining/Bitcoin-Wallet-Recovery?tab=3Dreadm=
e-ov-file" target=3D"_blank">https://github.com/demining/Bitcoin-Wallet-Rec=
overy?tab=3Dreadme-ov-file</a><br>=C2=A0<br>[1]: &quot;Constructing Digital=
 Signatures from a One Way Function&quot;, Leslie Lamport (1979), <a href=
=3D"https://www.microsoft.com/en-us/research/publication/constructing-digit=
al-signatures-one-way-function/" target=3D"_blank">https://www.microsoft.co=
m/en-us/research/publication/constructing-digital-signatures-one-way-functi=
on/</a><br><br>[2]: &quot;A Certified Digital Signature&quot;, Ralph C. Mer=
kle (1979), <a href=3D"https://www.ralphmerkle.com/papers/Certified1979.pdf=
" target=3D"_blank">https://www.ralphmerkle.com/papers/Certified1979.pdf</a=
><br><br>[3]: &quot;Timelocked Proof of Work via signature length&quot;, =
=C2=A0Robin Linus (2021), <a href=3D"https://gist.github.com/RobinLinus/95d=
e641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md" target=3D"_blank">https://gi=
st.github.com/RobinLinus/95de641ed1e3d9fde83bdcf5ac289ce9#file-sig_pow-md</=
a><br><br>[4]: &quot;Proof of Work in Bitcoin Script&quot;, Robin Linus (20=
20), <a href=3D"https://github.com/coins/bitcoin-scripts/blob/master/proof-=
of-work.md" target=3D"_blank">https://github.com/coins/bitcoin-scripts/blob=
/master/proof-of-work.md</a><br><br>[5]: &quot;sig-pow - work-locked output=
s&quot;, VzxPLnHqr (2022), <a href=3D"https://github.com/VzxPLnHqr/sig-pow/=
" target=3D"_blank">https://github.com/VzxPLnHqr/sig-pow/</a><br><br>[6]: &=
quot;[Lightning-dev] Better privacy with SNARKs&quot;, Anthony Towns (2015)=
, <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-dev/2015=
-November/000344.html" target=3D"_blank">https://lists.linuxfoundation.org/=
pipermail/lightning-dev/2015-November/000344.html</a><br><br>[7]: &quot;Qua=
ntum Proofing Bitcoin with a CAT&quot;, Jeremy Rubin (2021), <a href=3D"htt=
ps://rubin.io/blog/2021/07/06/quantum-bitcoin/" target=3D"_blank">https://r=
ubin.io/blog/2021/07/06/quantum-bitcoin/</a><br><br>[8]: &quot;CheckSigFrom=
Stack for 5 Byte Values&quot;, Jeremy Rubin (2021), <a href=3D"https://rubi=
n.io/blog/2021/07/02/signing-5-bytes/" target=3D"_blank">https://rubin.io/b=
log/2021/07/02/signing-5-bytes/</a><br></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com" target=
=3D"_blank">bitcoindev+unsubscribe@googlegroups.com</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25t=
M%3DXA%40mail.gmail.com?utm_medium=3Demail&amp;utm_source=3Dfooter" target=
=3D"_blank">https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNO=
ekw13C5jDMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com</a>.<br>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw=
%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.go=
ogle.com/d/msgid/bitcoindev/CA%2Bx5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwact=
Pnrgyw%40mail.gmail.com</a>.<br />

--000000000000a29bba06174f91a8--