Delivery-date: Wed, 08 May 2024 17:37:26 -0700
Sender: bitcoindev@googlegroups.com
Date: Wed, 8 May 2024 17:31:18 -0700 (PDT)
From: Ben Carman <benthecarman1@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n@googlegroups.com>
In-Reply-To: <ZjD-dMMGxoGNgzIg@camus>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
 <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
 <ZjD-dMMGxoGNgzIg@camus>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_85989_269653429.1715214678205"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_85989_269653429.1715214678205
Content-Type: multipart/alternative; 
	boundary="----=_Part_85990_406851706.1715214678205"

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

I think it is possible to get past the 201 op code limit doing it in=20
tapscript. I don't think it would have the same quantum security but could=
=20
maybe be a path to covenants. My understanding is that you're using the=20
OP_SIZE of the sig to basically decide to verify if the bit is a 0 or a 1,=
=20
then do that verification. You could do the same trick with schnorr sigs,=
=20
just for 0 bits don't include the sighash_all flag, and for 1 bits include=
=20
it. This would allow you to get around all the resource limits that taproot=
=20
lifted. This still should be safe since the the signature commits to if it=
=20
is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable very=
=20
complex things or just let you do it on 1 bit of information in tapscript.

Best,
benthecarman

On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra wrot=
e:

> 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 21
> > 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/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com.

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

<div>I think it is possible to get past the 201 op code limit doing it in t=
apscript. <span style=3D"text-overflow: unset;">I don't think it would have=
 the same quantum security  but could maybe be a path to covenants. My unde=
rstanding is that you're using the OP_SIZE of the sig to basically decide t=
o verify if the bit is a 0 or a 1, then do that verification. You could do =
the same trick with schnorr sigs, just for 0 bits don't include the sighash=
_all flag, and for 1 bits include it.

This would allow you to get around all the resource limits that taproot lif=
te</span>d. This still should be safe since the the signature commits to if=
 it is SIGHASH_DEFAULT vs SIGHASH_ALL. I am not sure if this will enable ve=
ry complex things or just let you do it on 1 bit of information in tapscrip=
t.</div><div><br /></div><div>Best,</div><div>benthecarman<br /></div><div>=
<br /></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_att=
r">On Tuesday, April 30, 2024 at 9:22:54=E2=80=AFAM UTC-5 Andrew Poelstra w=
rote:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.=
8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">On 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 o=
f 2^72
<br>&gt; computations, it would provide the attacker some advantage.
<br>&gt;=20
<br>&gt; If we are assuming discrete log is still hard, why do we need Lamp=
ort
<br>&gt; signatures at all? In a post-quantum world, finding k such that r =
is 21
<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 o=
n
<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 yo=
u can
<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>--=20
<br>Andrew Poelstra
<br>Director, Blockstream Research
<br>Email: apoelstra at <a href=3D"http://wpsoftware.net" target=3D"_blank"=
 rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3De=
n&amp;q=3Dhttp://wpsoftware.net&amp;source=3Dgmail&amp;ust=3D17153008146390=
00&amp;usg=3DAOvVaw3wIDzlUj1wqXmVV4RyaQhz">wpsoftware.net</a>
<br>Web:   <a href=3D"https://www.wpsoftware.net/andrew" target=3D"_blank" =
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&amp;q=3Dhttps://www.wpsoftware.net/andrew&amp;source=3Dgmail&amp;ust=3D171=
5300814639000&amp;usg=3DAOvVaw1ZlDWyULQOphaSgTZFgrBT">https://www.wpsoftwar=
e.net/andrew</a>
<br>
<br>The sun is always shining in space
<br>    -Justin Lewis-Webster
<br>
<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/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/b50b6b09-4d13-46ab-9776-f6b8a02aa2e0n%40googlegroups.com</a>.=
<br />

------=_Part_85990_406851706.1715214678205--

------=_Part_85989_269653429.1715214678205--