Delivery-date: Wed, 01 May 2024 01:57:26 -0700
Sender: bitcoindev@googlegroups.com
Date: Tue, 30 Apr 2024 20:46:07 -0700 (PDT)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n@googlegroups.com>
In-Reply-To: <CAEM=y+UnxB2vKQpJAa-z-qGZQfpR1ZeW3UyuFFZ6_WTWFYGfjw@mail.gmail.com>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
 <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
 <ZjD-dMMGxoGNgzIg@camus>
 <CAEM=y+UnxB2vKQpJAa-z-qGZQfpR1ZeW3UyuFFZ6_WTWFYGfjw@mail.gmail.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_25720_608833718.1714535167151"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_25720_608833718.1714535167151
Content-Type: multipart/alternative; 
	boundary="----=_Part_25721_1931232839.1714535167151"

------=_Part_25721_1931232839.1714535167151
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Ethan,

From my understanding, you're proposing to emulate Lamport signature=20
verification / generation
scheme by leveraging the implicit signature digest of the OP_CHECKSIG=20
operation, which has been
a valid Bitcoin Script opcode since genesis block. Signature digests is a=
=20
commitment to a bitcoin
transaction fields, and this is verified by the interpreter both for ECDSA=
=20
and Schnorr schemes.

Here you're proposing to use the ECDSA's `k` nonce as a fixed public value=
=20
by committing the
ECDSA-signature length as a parameter of an OP_SIZE and the cleartext `r,s`=
=20
signature itself as
the verification parameter of a OP_SHA256, emulating the h(x) =3D y for=20
Lamport signature range of
bits, all in a redeem script (i.e P2SH).

I don't know if your proposed scheme is secure against message forgery=20
attacks or invalid curve
domain parameters, e.g using the point at infinity as your point R, and if=
=20
from them you could play
tricks with coordinates.

On the usage of such emulated Lamport signature scheme in a public=20
transaction-relay network,
there is one fundamental security property of Lamport signature to be aware=
=20
off, mainly the one-time
usage. So this is very unclear if as soon you're broadcasting the=20
transaction, miners coalition could
withhold the transaction inclusion to trigger the initial signer to reveal=
=20
more a lot of pre-committed
fixed-nonce ECDSA signatures.

Apart of concerns of this scheme in a blockchain and assuming it's not=20
utterly broken due to
message forgery attacks, I'm skeptical on the robustness of the scheme as=
=20
the number of on-chain
pre-committed signatures is a parameter of the preimage-resistance of the=
=20
Lamport signature scheme
itself. Sounds a classic time-space tradeoff, by increasing the lot of=20
fixed-nonce signatures we're making
it harder to break, even for observers with significant computational=20
ressources.

Beyond, 2^64 bit of security doesn't seem a lot in considerations of=20
state-of-the-art collision attacks
on hash functions from recent academic literature. And one have to consider=
=20
how you can take the
short-cut by pre-computing rainbow tables for ECDSA r-value of a given=20
signature size.

I think a more interesting open question of this post is if we have already=
=20
hash-chain-based covenant
"today" in Bitcoin. If by fixing the integer `z` of the s-value of ECDSA=20
signature in redeem script, and
computing backward the chain of chids redeem scripts to avoid hash-chain=20
dependencies. This is unclear
what would be the security guarantees and average btc units cost for=20
scriptSig / witness under current block
size limit of 4MWU.

Best,
Antoine
Le mardi 30 avril 2024 =C3=A0 22:18:36 UTC+1, Ethan Heilman a =C3=A9crit :

> One could redesign this scheme to minimize the number of opcodes.
>
> Back of the napkin scheme follows:
>
> Alice, rather than Lamport signing the length of each ECDSA signature,=20
> instead Lamport (or WOTS) signs a vector of the positions of the low-leng=
th=20
> ECDSA signatures (low length here means length=3D58 rather than length=3D=
59).=20
> Then the redeem script would only check the length of those particular=20
> signatures and could drop the other other public keys. This saves=20
> significantly on the number of opcodes because we only need to check the=
=20
> Lamport signature on the vector, no one each signature length and we can=
=20
> drop unused checked signatures without evaluating them.
>
> Alice's advantage over the attacker is that she gets to fix the positions=
=20
> of the low length ECDSA signatures after she generates them. This means i=
f=20
> the total number of signatures is N and the number of low length signatur=
es=20
> is M, her advantage over the attacker is (N choose M). For instance if=20
> N=3DM=3D10, to generate 10 59-length signatures, Alice needs to perform=
=20
> 2^(8*10) work. This is because we assume the probability of generating a=
=20
> 58-byte ECDSA signature is 1/256 (1/2^8). However if N=3D40, M=3D10 she o=
nly=20
> needs to perform 2^(8*10)/(40 choose 10) work.
>
> If we assume that we want 80 bits of security, this means we need M=3D10 =
low=20
> length ECDCSA signatures (2^(8*10)). The next parameter is how cheap we=
=20
> want this to be for Alice to compute, we can boost Alice's signing time b=
y=20
> increasing N and remove log2(N choose 10) from the work she needs to=20
> compute the signature. If we want to ensure Alice has to do no more than=
=20
> 2^32 work to sign, then we need N=3D46 or 46 ecdsa signatures.
>
> On Tue, Apr 30, 2024 at 10:21=E2=80=AFAM Andrew Poelstra <apoe...@wpsoftw=
are.net>=20
> wrote:
>
>> On Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:
>> > > 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.
>> >=20
>> > 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 2=
1
>> > bytes or less is efficient for the attacker.
>> >
>>
>> Aside from Ethan's point that a variant of this technique is still
>> secure in the case that discrete log is totally broken (or even
>> partially broken...all we need is that _somebody_ is able to find the
>> discrete log of the x=3D1 point and for them to publish this).
>>
>> Another reason this is useful is that if you have a Lamport signature on
>> the stack which is composed of SIZE values, all of which are small
>> enough to be manipulated with the numeric script opcodes, then you can
>> do covenants in Script.
>>
>> (Sadly(?), I think none of this works in the context of the 201-opcode
>> limit...and absent BitVM challenge-response tricks it's unlikely you can
>> do much in the context of the 4MWu block size limit..), but IMO it's a
>> pretty big deal that size limits are now the only reason that Bitcoin
>> doesn't have covenants.)
>>
>> --=20
>> Andrew Poelstra
>> Director, Blockstream Research
>> Email: apoelstra at wpsoftware.net
>> Web:   https://www.wpsoftware.net/andrew
>>
>> The sun is always shining in space
>>     -Justin Lewis-Webster
>>
>>

--=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/2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n%40googlegroups.com.

------=_Part_25721_1931232839.1714535167151
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Ethan,<div><br /></div><div>From my understanding, you're proposing to e=
mulate Lamport signature verification / generation</div><div>scheme by leve=
raging the implicit signature digest of the OP_CHECKSIG operation, which ha=
s been</div><div>a valid Bitcoin Script opcode since genesis block. Signatu=
re digests is a commitment to a bitcoin</div><div>transaction fields, and t=
his is verified by the interpreter both for ECDSA and Schnorr schemes.</div=
><div><br /></div><div>Here you're proposing to use the ECDSA's `k` nonce a=
s a fixed public value by committing the</div><div>ECDSA-signature length a=
s a parameter of an OP_SIZE and the cleartext `r,s` signature itself as</di=
v><div>the verification parameter of a OP_SHA256, emulating the h(x) =3D y =
for Lamport signature range of</div><div>bits, all in a redeem script (i.e =
P2SH).</div><div><br /></div><div>I don't know if your proposed scheme is s=
ecure against message forgery attacks or invalid curve</div><div>domain par=
ameters, e.g using the point at infinity as your point R, and if from them =
you could play</div><div>tricks with coordinates.</div><div><br /></div><di=
v>On the usage of such emulated Lamport signature scheme in a public transa=
ction-relay network,</div><div>there is one fundamental security property o=
f Lamport signature to be aware off, mainly the one-time</div><div>usage. S=
o this is very unclear if as soon you're broadcasting the transaction, mine=
rs coalition could</div><div>withhold the transaction inclusion to trigger =
the initial signer to reveal more a lot of pre-committed</div><div>fixed-no=
nce ECDSA signatures.</div><div><br /></div><div>Apart of concerns of this =
scheme in a blockchain and assuming it's not utterly broken due to</div><di=
v>message forgery attacks, I'm skeptical on the robustness of the scheme as=
 the number of on-chain</div><div>pre-committed signatures is a parameter o=
f the preimage-resistance of the Lamport signature scheme</div><div>itself.=
 Sounds a classic time-space tradeoff, by increasing the lot of fixed-nonce=
 signatures we're making</div><div>it harder to break, even for observers w=
ith significant computational ressources.</div><div><br /></div><div>Beyond=
, 2^64 bit of security doesn't seem a lot in considerations of state-of-the=
-art collision attacks</div><div>on hash functions from recent academic lit=
erature. And one have to consider how you can take the</div><div>short-cut =
by pre-computing rainbow tables for ECDSA r-value of a given signature size=
.</div><div><br /></div><div>I think a more interesting open question of th=
is post is if we have already hash-chain-based covenant</div><div>"today" i=
n Bitcoin. If by fixing the integer `z` of the s-value of ECDSA signature i=
n redeem script, and</div><div>computing backward the chain of chids redeem=
 scripts to avoid hash-chain dependencies. This is unclear</div><div>what w=
ould be the security guarantees and average btc units cost for scriptSig / =
witness under current block</div><div>size limit of 4MWU.</div><div><br /><=
/div><div>Best,</div><div>Antoine</div><div class=3D"gmail_quote"><div dir=
=3D"auto" class=3D"gmail_attr">Le mardi 30 avril 2024 =C3=A0 22:18:36 UTC+1=
, Ethan Heilman a =C3=A9crit=C2=A0:<br/></div><blockquote class=3D"gmail_qu=
ote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204=
); padding-left: 1ex;"><div dir=3D"ltr">One could redesign this scheme to m=
inimize the number of opcodes.<br><br>Back of the napkin scheme follows:<br=
><br>Alice, rather than Lamport signing the length of each ECDSA signature,=
 instead Lamport (or WOTS) signs a vector of the positions of the low-lengt=
h ECDSA signatures (low length here means length=3D58 rather than length=3D=
59). Then the redeem script would only check the length of those particular=
 signatures and could drop the other other public keys. This saves signific=
antly on the number of opcodes because we only need to check the Lamport si=
gnature on the vector, no one each signature length and we can drop unused =
checked signatures without evaluating them.<br><br>Alice&#39;s advantage ov=
er the attacker is that she gets to fix the positions of the low length ECD=
SA signatures after she generates them. This means if the total number of s=
ignatures is N and the number of low length signatures is M, her advantage =
over the attacker is (N choose M). For instance if N=3DM=3D10, to generate =
10 59-length signatures, Alice=C2=A0needs to perform 2^(8*10) work. This is=
 because we assume the probability of generating a 58-byte ECDSA signature =
is 1/256 (1/2^8). However if N=3D40, M=3D10 she only needs to perform 2^(8*=
10)/(40 choose 10) work.<br><br>If we assume that we want 80 bits of securi=
ty, this means we need M=3D10 low length ECDCSA signatures (2^(8*10)). The =
next parameter is how cheap we want this to be for Alice to compute, we can=
 boost Alice&#39;s signing time by increasing N and remove log2(N choose 10=
) from the work she needs to compute the signature. If we want to ensure Al=
ice has to do no more than 2^32 work to sign, then we need=C2=A0N=3D46 or 4=
6 ecdsa signatures.<br></div><br><div class=3D"gmail_quote"><div dir=3D"ltr=
" class=3D"gmail_attr">On Tue, Apr 30, 2024 at 10:21=E2=80=AFAM Andrew Poel=
stra &lt;<a href data-email-masked rel=3D"nofollow">apoe...@wpsoftware.net<=
/a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">O=
n Tue, Apr 30, 2024 at 08:32:42AM -0400, Matthew Zipkin wrote:<br>
&gt; &gt; if an attacker managed to grind a 23-byte r-value at a cost of 2^=
72<br>
&gt; computations, it would provide the attacker some advantage.<br>
&gt; <br>
&gt; If we are assuming discrete log is still hard, why do we need Lamport<=
br>
&gt; signatures at all? In a post-quantum world, finding k such that r is 2=
1<br>
&gt; bytes or less is efficient for the attacker.<br>
&gt;<br>
<br>
Aside from Ethan&#39;s point that a variant of this technique is still<br>
secure in the case that discrete log is totally broken (or even<br>
partially broken...all we need is that _somebody_ is able to find the<br>
discrete log of the x=3D1 point and for them to publish this).<br>
<br>
Another reason this is useful is that if you have a Lamport signature on<br=
>
the stack which is composed of SIZE values, all of which are small<br>
enough to be manipulated with the numeric script opcodes, then you can<br>
do covenants in Script.<br>
<br>
(Sadly(?), I think none of this works in the context of the 201-opcode<br>
limit...and absent BitVM challenge-response tricks it&#39;s unlikely you ca=
n<br>
do much in the context of the 4MWu block size limit..), but IMO it&#39;s a<=
br>
pretty big deal that size limits are now the only reason that Bitcoin<br>
doesn&#39;t have covenants.)<br>
<br>
-- <br>
Andrew Poelstra<br>
Director, Blockstream Research<br>
Email: apoelstra at <a href=3D"http://wpsoftware.net" rel=3D"noreferrer nof=
ollow" target=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url=
?hl=3Dfr&amp;q=3Dhttp://wpsoftware.net&amp;source=3Dgmail&amp;ust=3D1714620=
601370000&amp;usg=3DAOvVaw10AS58ONx0CuWBf6GFMDuE">wpsoftware.net</a><br>
Web:=C2=A0 =C2=A0<a href=3D"https://www.wpsoftware.net/andrew" rel=3D"noref=
errer nofollow" target=3D"_blank" data-saferedirecturl=3D"https://www.googl=
e.com/url?hl=3Dfr&amp;q=3Dhttps://www.wpsoftware.net/andrew&amp;source=3Dgm=
ail&amp;ust=3D1714620601370000&amp;usg=3DAOvVaw1S8MAOAtRNOo00YP3mqlBD">http=
s://www.wpsoftware.net/andrew</a><br>
<br>
The sun is always shining in space<br>
=C2=A0 =C2=A0 -Justin Lewis-Webster<br>
<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/2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/2775e9e8-4f1a-4f03-a8f0-4a4c2f6e93a9n%40googlegroups.com</a>.=
<br />

------=_Part_25721_1931232839.1714535167151--

------=_Part_25720_608833718.1714535167151--