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

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

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

This is true, however there is a fix. Someone at the DCI, I think Madars,
pointed out that if you had a quantum computer you could find r=3D1 and the=
n
everyone could use r=3D1 in the scheme and not have to worry about grinding
attacks. So the ability to compute discrete logs would strengthen this
scheme.

Interestingly, you can generate valid ecdsa signatures where (r=3D1,s=3D1)
using ecdsa pubkey recovery because "An ECDSA signature itself does not
prove knowledge of a discrete log."
<https://bitcointalk.org/index.php?topic=3D1729534.msg17309060#msg17309060>

I am not aware of any technique, even if we had OP_LAMPORT, to make Bitcoin
outputs quantum resistant without a softfork to add the ability to disable
key-spend paths in a taproot output. I'd love to be proven wrong on this
point.

On Tue, Apr 30, 2024 at 8:32=E2=80=AFAM Matthew Zipkin <pinheadmz@gmail.com=
> wrote:

> We discussed this scheme at NY BitDevs last night and one participant mad=
e
> 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> =
wrote:
>
>> 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 VzxPLnH=
qr
>> [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 no=
t
>> 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
>> 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 ke=
y
>> 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 th=
is
>> 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=3D1/2, that is setting k to the multiplicative inv=
erse
>> 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 leak=
s
>> 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)`. Grindi=
ng
>> 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 funct=
ion
>> H, to compute: x0 =3D H(y0), x1 =3D H(y1). Next, you publish x0,x1 as yo=
ur
>> public key. Then, to sign the bit 0, you release the value y0. Anyone ca=
n
>> 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 th=
e
>> 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. Fo=
r
>> example let=E2=80=99s say OP_SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D=
58,
>> OP_SIZE(ecdsaSig2)=3D59. Thus, to spend she generates a Lamport signatur=
e
>> 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 i=
s
>> 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 ha=
sh
>> that matches the size of her signatures for each different ECDSA signatu=
re.
>> The probability an attacker manages this for three random ECDSA signatur=
es
>> 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 probabl=
y
>> also needs to grind for safer values to sign (safer =3D high diversity i=
n
>> 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 wil=
l
>> 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 Alic=
e
>> 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=3D800,m=3D10.
>> 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=3D800,m=
=3D10
>> signature.
>>
>> ## Known weaknesses
>>
>> 1. *The Tuning Attack:* The attacker can use different SIG_HASH flags pe=
r
>> 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 th=
is
>> 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 ma=
ke
>> 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 =
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 bi=
t
>> vector of the signature lengths using OP_MUL, OP_ADD.
>>
>> bit vector =3D OP_SIZE(ecdsaSig0)=3D=3D59 + 2*(OP_SIZE(ecdsaSig1)=3D=3D5=
9) +
>> 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 o=
f
>> lamport public keys and signing keys and likely reduce the size of redee=
m
>> 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 preimag=
e 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 ot=
her
>> ECDSA signatures. That said, perhaps there is some way it can be exploit=
ed
>> 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 =
to
>> find r=3D1 as it requires finding the discrete log. It is possible to cr=
eate
>> transaction signatures that have r=3D1 without knowing k, through the us=
e of
>> ECDSA pubkey recovery. This does not work for our scheme as we must comm=
it
>> 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 thi=
s
>> 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 Cu=
rve
>> math lines up perfectly with a 256 bit space especially for a fixed r-va=
lue
>> 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 length=
s
>> 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 givi=
ng
>> me feedback. This initial discuss was fueled by the MIT DCI espresso
>> machine. I've attempted to credit all ideas contributed to the contribut=
or,
>> 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-digita=
l-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 Group=
s
>> "Bitcoin Development Mailing List" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> email to bitcoindev+unsubscribe@googlegroups.com.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5jD=
MzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com
>> <https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXyW8wNOekw13C5j=
DMzQ-dOJpQrBC%2BqR8-uDot25tM%3DXA%40mail.gmail.com?utm_medium=3Demail&utm_s=
ource=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/CAEM%3Dy%2BW9x70K-nSW1FvKyK%2BjYn2LnzPR8cRGxPJ4tpKsBzT8fA%40mail=
.gmail.com.

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

<div dir=3D"ltr">&gt; 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.<div><br>This is =
true, however there is a fix. Someone at the DCI, I think Madars, pointed o=
ut that if you had a quantum computer you could find r=3D1 and then everyon=
e could use r=3D1 in the scheme and not have to worry about grinding attack=
s. So the ability to compute discrete logs would strengthen this scheme.<br=
><br>Interestingly, you can generate valid ecdsa signatures where <a href=
=3D"https://bitcointalk.org/index.php?topic=3D1729534.msg17309060#msg173090=
60">(r=3D1,s=3D1) using ecdsa pubkey recovery because &quot;An ECDSA signat=
ure itself does not prove knowledge of a discrete log.&quot;</a><br><br>I a=
m not aware of any technique, even if we had OP_LAMPORT, to make Bitcoin ou=
tputs quantum resistant without a softfork to add=C2=A0the ability to disab=
le key-spend paths in a taproot output. I&#39;d love to be proven wrong on =
this point.</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" clas=
s=3D"gmail_attr">On Tue, Apr 30, 2024 at 8:32=E2=80=AFAM Matthew Zipkin &lt=
;<a href=3D"mailto:pinheadmz@gmail.com">pinheadmz@gmail.com</a>&gt; wrote:<=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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 attacker managed t=
o grind a 23-byte r-value at a cost of 2^72 computations, it would provide =
the attacker some advantage.</div><div><br></div><div>If we are assuming di=
screte log is still hard, why do we need Lamport signatures at all? In a po=
st-quantum world, finding k such that r is 21 bytes or less is efficient fo=
r the attacker.<br></div><div><br></div></div><br><div class=3D"gmail_quote=
"><div dir=3D"ltr" class=3D"gmail_attr">On Sun, Apr 28, 2024 at 8:50=E2=80=
=AFPM Ethan Heilman &lt;<a href=3D"mailto:eth3rs@gmail.com" target=3D"_blan=
k">eth3rs@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex"><div dir=3D"ltr">One day having lunch at the MIT DCI and=
 discussing OP_CAT and lamport signatures we came up with a scheme to do la=
mport signatures on Bitcoin transactions without OP_CAT.<br><br>This scheme=
 has the following properties:<br>1. Should work with today&#39;s Bitcoin (=
no OP_CAT required).<br>2. Unlike other lamport signatures in Bitcoin scrip=
t, this scheme signs the spending transaction.<br><br>Disclaimer: This is v=
ery 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 fo=
r that output to be a fun crypto bounty. I have not tested this in Bitcoin =
script.<br><br>This idea of using signature length shares a lot in common w=
ith 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 ECDS=
A signature length constraints to force revealing signing key [6].<br><br>O=
ur approach differs from the Jeremy Rubin&#39;s approach in [7] as we do no=
t require OP_CAT and we use P2SH not tapscript and from Jeremy Rubin&#39;s =
approach in [8] as our goal is to verify a Lamport signature on the spendin=
g transaction rather than a Lamport signature on arbitrary data. When compa=
red with [7,8] our scheme is far less practical as it requires very large n=
umbers of signatures (below we discuss 1000 signatures).<br><br>## Signing =
a Bitcoin 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 chose=
n nonce<br>- dA is the signing key, <br>- z is derived from the hash of the=
 signed message, i.e., transaction hash.<br><br>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 transactio=
n hash. We can use OP_SIZE to get the size of a signature and we can use La=
mport signatures to sign this size. We explain Lamport signatures below.<br=
><br>The security of our scheme rests on a way to fix the nonce k. Madars V=
irza and Andrew Poelstra both pointed out to me when discussing this scheme=
 that setting k=3D1/2, that is setting k to the multiplicative inverse of 2=
, results in a k with a very short r (r=3D0x00000000000000000000003b78ce563=
f89a0ed9414f5aa28ad0d96d6795f9c63) [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 b=
ytes long! A publicly known k leaks the signing key, but that doesn&#39;t m=
atter for our purposes.<br><br>Using this k, we can ensure that the r value=
s on 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 =
bytes 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 observ=
ative to sign Bitcoin transactions with Lamport signatures, let&#39;s remin=
d ourselves how Lamport signatures [1] =C2=A0work. To sign 1-bit with a Lam=
port signature you first use a hash function H, to compute: x0 =3D H(y0), x=
1 =3D 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 =3D=3D=
 H(y0). To sign the bit 1, you release y1.<br><br>We use Lamport signatures=
 to sign the length of a bitcoin signature. The length of the signature ser=
ves as a proxy for the transaction hash of the spending transaction. Repeat=
ing this many times provides cryptographic levels of security. Let&#39;s lo=
ok at an example:<br><br>Alice computes her Lamport public keys and signing=
 keys<br>x00 =3D Hash(y00) <br>x01 =3D Hash(y01)<br>x10 =3D Hash(y10)<br>x1=
1 =3D Hash(y11)<br>x20 =3D Hash(y20)<br>x21 =3D Hash(y21)<br><br>In pseudoc=
ode Alice&#39;s redeem script looks like:<br>```<br>PUSH ecdsaPubkey0<br>OP=
_CHECKSIG (ecdsaSig0)<br>// Verify lamport signature on ecdsaSig0<br>PUSH x=
00, x01<br>if OP_SIZE (ecdsaSig0) =3D=3D 59:<br>=C2=A0 if OP_HASH(y00) !=3D=
 x00: OP_RETURN<br>else if OP_SIZE (ecdsaSig0) &lt; 59:<br>=C2=A0 if OP_HAS=
H(y01) !=3D x01: OP_RETURN<br><br>PUSH ecdsaPubkey1<br>OP_CHECKSIG (ecdsaSi=
g1)<br>// Verify lamport signature on ecdsaSig1<br>PUSH x10, x11<br>if OP_S=
IZE (ecdsaSig1) =3D=3D 59:<br>=C2=A0 if OP_HASH(y10) !=3D x10: OP_RETURN<br=
>else if OP_SIZE (ecdsaSig1) &lt; 59:<br>=C2=A0 if OP_HASH(y11) !=3D x11: O=
P_RETURN<br><br>// Verify lamport signature on ecdsaSig2<br>PUSH ecdsaPubke=
y2<br>OP_CHECKSIG (ecdsaSig2)<br>// Verify lamport signature on ecdsaSig1<b=
r>PUSH x20, x21<br>if OP_SIZE (ecdsaSig2) =3D=3D 59:<br>=C2=A0 if OP_HASH(y=
20) !=3D x10: OP_RETURN<br>else if OP_SIZE (ecdsaSig2) &lt; 59:<br>=C2=A0 i=
f OP_HASH(y21) !=3D x21: OP_RETURN<br>```<br><br>Alice computes the ECDSA s=
ignatures: ecdsaSig0, ecdsaSig1, ecdsaSig2. For example let=E2=80=99s say O=
P_SIZE(ecdsaSig0)=3D59, OP_SIZE(ecdsaSig1)=3D58, OP_SIZE(ecdsaSig2)=3D59. T=
hus, to spend she generates a Lamport signature over those lengths by relea=
sing 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=
 59<br>PUSH ecdsaSig1<br>PUSH y11 // Signs that OP_SIZE(ecdsaSig1) should b=
e less than 59<br>PUSH ecdsaSig2<br>PUSH y20 // Signs that OP_SIZE(ecdsaSig=
2) should be 59<br>```<br><br>The advantage Alice has over an attacker atte=
mpting to steal her funds is that all Alice has to do is release the preima=
ges 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>
</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/CAEM%3Dy%2BW9x70K-nSW1FvKyK%2BjYn2LnzPR8cRGxPJ4tpKsBz=
T8fA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://group=
s.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BW9x70K-nSW1FvKyK%2BjYn2LnzPR8cRG=
xPJ4tpKsBzT8fA%40mail.gmail.com</a>.<br />

--0000000000008ec5690617505118--