Delivery-date: Mon, 06 May 2024 18:15:28 -0700
Sender: bitcoindev@googlegroups.com
Date: Mon, 6 May 2024 17:55:26 -0700 (PDT)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
In-Reply-To: <ZjkqIzPSFLc0GJJ1@camus>
References: <CAEM=y+XyW8wNOekw13C5jDMzQ-dOJpQrBC+qR8-uDot25tM=XA@mail.gmail.com>
 <CA+x5asTOTai_4yNGEgtKEqAchuWJ0jGDEgMqHFYDwactPnrgyw@mail.gmail.com>
 <ZjD-dMMGxoGNgzIg@camus>
 <47711dc4ffe9d661e8321b05b6adab4e@dtrt.org>
 <ZjkJ0fPyzuAPTLWS@camus>
 <a5a86fcd50e2cdbdf40a12ac9463a828@dtrt.org>
 <ZjkqIzPSFLc0GJJ1@camus>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_16976_1588284193.1715043326554"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_16976_1588284193.1715043326554
Content-Type: multipart/alternative; 
	boundary="----=_Part_16977_913307175.1715043326554"

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

Hi Ethan,

> I'm not sure I understand what you are saying here. I agree that once
> Alice broadcasts a transaction spending such an output, she can not
> double spend that output without losing security. You'd want to define
> the unforgeability property to be EU-CMA with only a single signature.
> Why would Alice simply just not rebroadcast her original transaction?
> If she wants the capability to bump the fees without changing the sig
> hash, she can use the SIGHASH flag anyone can pay or CPFP.

If my understanding of your scheme is correct, the Lamport public key
(e.g x00 =3D=3D Hash(y00) is committed in the redeem script of a said UTXO.
scriptpubkey.

I think this opens the following denial-of-service attack by adversaries
with hashrate capabilities:
- Alice Lamport-emulated signs and broadcast her transaction X
- Coalition of Miners (e.g 30% of network) refuse to include Alice's=20
transaction X
- Alice can:
        - a) wait for the 70% honest network to mine her transaction
        - b) increase her feerate to bump incentives to mine transaction X
- If Alice picks up option b)
        - Alice Lamport-emulated signs and broadcast her transaction X by=
=20
using ACP flag / CPFP
        - This assumes the consumption of a "fresh" fee-bumping UTXO
        - This fee-bumping UTXO can be locked under a Lamport=20
emulated-pubkey

I think this scheme with a one-time usage property is more exposed to=20
denial-of-service
attacks (or wallet UTXO deanonymization) than ECDSA / Schnorr scheme.

I believe you might even have a worst-case scenario of this DoS where a=20
coalition
of mining attackers force you to one-time sig all your Lamport pubkeys=20
committed
in UTXOs (original UTXO + fee-bumping UTXOs), in a way that the orignal=20
UTXO cannot
be moved because its feerate is perpetually under mempool min fee, or the=
=20
marginal
ancestor feerate unit of miners block templates.

I don't know if this vector of attack is correct, however one can note it=
=20
could arise
in alternative spontaneous scenarios, such as second-layers scarce=20
liquidity allocation
(e.g dual-funding), where many UTXOs concurrent spends might compete to=20
confirm first.

> What do you mean by this? k=3D0? I do agree that this scheme is making
> some very odd assumptions about ecdsa signatures and they may not
> hold. Certainly no one should expect this scheme to be secure without
> a proof of security or at the least some sort of justification for why
> anyone expects these assumptions to hold.

I think the ECDSA signature verification algorithm forbids the usage
of the point at infinity for the curve point resulting from the modular
arithmetic on your r-value and s-value, not k=3D0 where k is the nonce.

I don't know if you could play with the transaction hash to produce
a curve point which is equals to the point at infinity, especially in
context where the transaction hash is including inputs from multiple
non-trusted counterparties (e.g if you're using SIGHASH flags).

> It's worse than that! Storage and lookup would not require anything so
> fancy as rainbow tables. Once you have precomputed a 20 byte r-value
> you can use it everywhere. Grinding such an r-value would cost 2^96
> queries for 50% success rate, but would let you trivially break any of
> these signatures which used a 21 byte r-value with a pen and some
> paper. Still, if you could do 2^96 ecdsa queries, it would be
> computationally expensive as mining 1,125,899,906,842,620 bitcoin
> blocks. You'd probably be better off mining those blocks than grinding
> the r-value.

Well, we're not comparing "apple-to-apple" here as on one side you have
modular arithmetic operations, on the other side bitwise rotations. I'm
thinking you might have an advantage in your ecdsa queries as a finite fiel=
d
is, as the name say so, "finite" so you could theoretically pre-compute all
entries in your storage. On the other hand, with block mining (even assumin=
g
a functional implementation of Grover's algorithm) you have lookup and
propagation latency under 10 min in average. Sounds you can parellize both
problems resolution (re-use hash round states or point addition), so it=20
might
be just a classicla time-space trade-off here.

> I think a more interesting open question of this post is if we have=20
already 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.=20

Correcting myself on my initial email, the design bottleneck here is=20
obviously
that spent outpoints are committed in a child signature digest in a no-APO=
=20
world.
This is still an interesting question if you can remove spent outpoints=20
commitment
by leveraging OP_SIZE or fixing other ECDSA signature components.

Best,
Antoine

Le lundi 6 mai 2024 =C3=A0 20:25:33 UTC+1, Andrew Poelstra a =C3=A9crit :

> On Mon, May 06, 2024 at 08:56:21AM -1000, David A. Harding wrote:
> > On 2024-05-06 06:48, Andrew Poelstra wrote:
> > > [...] post-Taproot script can verify a
> > > trace of any program execution, as long as the individual elements it=
=20
> is
> > > operating on fit into 4-byte CScriptNums. You can therefore implement
> > > SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elements by
> > > feeding in transaction data. Which of course can then be arbitrarily
> > > constrained.
> >=20
> > Thanks for your answer! I think I understand. However, we don't have=20
> ECDSA
> > in tapscript; all signatures in tapscript are 64 bytes plus an optional
> > sighash byte, so there's no natural variation in signature size.
> >
>
> You can implement ECDSA. It will just take a *lot* of opcodes.
>
> --=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/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.com.

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

Hi Ethan,<br /><br />&gt; I'm not sure I understand what you are saying her=
e. I agree that once<br />&gt; Alice broadcasts a transaction spending such=
 an output, she can not<br />&gt; double spend that output without losing s=
ecurity. You'd want to define<br />&gt; the unforgeability property to be E=
U-CMA with only a single signature.<br />&gt; Why would Alice simply just n=
ot rebroadcast her original transaction?<br />&gt; If she wants the capabil=
ity to bump the fees without changing the sig<br />&gt; hash, she can use t=
he SIGHASH flag anyone can pay or CPFP.<br /><br />If my understanding of y=
our scheme is correct, the Lamport public key<br />(e.g x00 =3D=3D Hash(y00=
) is committed in the redeem script of a said UTXO.<br />scriptpubkey.<br /=
><br />I think this opens the following denial-of-service attack by adversa=
ries<br />with hashrate capabilities:<br />- Alice Lamport-emulated signs a=
nd broadcast her transaction X<br />- Coalition of Miners (e.g 30% of netwo=
rk) refuse to include Alice's transaction X<br />- Alice can:<br />=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 - a) wait for the 70% honest network to mine her trans=
action<br />=C2=A0 =C2=A0 =C2=A0 =C2=A0 - b) increase her feerate to bump i=
ncentives to mine transaction X<br />- If Alice picks up option b)<br />=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 - Alice Lamport-emulated signs and broadcast her t=
ransaction X by using ACP flag / CPFP<br />=C2=A0 =C2=A0 =C2=A0 =C2=A0 - Th=
is assumes the consumption of a "fresh" fee-bumping UTXO<br />=C2=A0 =C2=A0=
 =C2=A0 =C2=A0 - This fee-bumping UTXO can be locked under a Lamport emulat=
ed-pubkey<br /><br />I think this scheme with a one-time usage property is =
more exposed to denial-of-service<br />attacks (or wallet UTXO deanonymizat=
ion) than ECDSA / Schnorr scheme.<br /><br />I believe you might even have =
a worst-case scenario of this DoS where a coalition<br />of mining attacker=
s force you to one-time sig all your Lamport pubkeys committed<br />in UTXO=
s (original UTXO + fee-bumping UTXOs), in a way that the orignal UTXO canno=
t<br />be moved because its feerate is perpetually under mempool min fee, o=
r the marginal<br />ancestor feerate unit of miners block templates.<br /><=
br />I don't know if this vector of attack is correct, however one can note=
 it could arise<br />in alternative spontaneous scenarios, such as second-l=
ayers scarce liquidity allocation<br />(e.g dual-funding), where many UTXOs=
 concurrent spends might compete to confirm first.<br /><br />&gt; What do =
you mean by this? k=3D0? I do agree that this scheme is making<br />&gt; so=
me very odd assumptions about ecdsa signatures and they may not<br />&gt; h=
old. Certainly no one should expect this scheme to be secure without<br />&=
gt; a proof of security or at the least some sort of justification for why<=
br />&gt; anyone expects these assumptions to hold.<br /><br />I think the =
ECDSA signature verification algorithm forbids the usage<br />of the point =
at infinity for the curve point resulting from the modular<br />arithmetic =
on your r-value and s-value, not k=3D0 where k is the nonce.<br /><br />I d=
on't know if you could play with the transaction hash to produce<br />a cur=
ve point which is equals to the point at infinity, especially in<br />conte=
xt where the transaction hash is including inputs from multiple<br />non-tr=
usted counterparties (e.g if you're using SIGHASH flags).<br /><br />&gt; I=
t's worse than that! Storage and lookup would not require anything so<br />=
&gt; fancy as rainbow tables. Once you have precomputed a 20 byte r-value<b=
r />&gt; you can use it everywhere. Grinding such an r-value would cost 2^9=
6<br />&gt; queries for 50% success rate, but would let you trivially break=
 any of<br />&gt; these signatures which used a 21 byte r-value with a pen =
and some<br />&gt; paper. Still, if you could do 2^96 ecdsa queries, it wou=
ld be<br />&gt; computationally expensive as mining 1,125,899,906,842,620 b=
itcoin<br />&gt; blocks. You'd probably be better off mining those blocks t=
han grinding<br />&gt; the r-value.<br /><br />Well, we're not comparing "a=
pple-to-apple" here as on one side you have<br />modular arithmetic operati=
ons, on the other side bitwise rotations. I'm<br />thinking you might have =
an advantage in your ecdsa queries as a finite field<br />is, as the name s=
ay so, "finite" so you could theoretically pre-compute all<br />entries in =
your storage. On the other hand, with block mining (even assuming<br />a fu=
nctional implementation of Grover's algorithm) you have lookup and<br />pro=
pagation latency under 10 min in average. Sounds you can parellize both<br =
/>problems resolution (re-use hash round states or point addition), so it m=
ight<br />be just a classicla time-space trade-off here.<br /><br />&gt; I =
think a more interesting open question of this post is if we have already h=
ash-chain-based covenant<br />&gt; "today" in Bitcoin. If by fixing the int=
eger `z` of the s-value of ECDSA signature in redeem script, and<br />&gt; =
computing backward the chain of chids redeem scripts to avoid hash-chain de=
pendencies. <br /><br />Correcting myself on my initial email, the design b=
ottleneck here is obviously<br />that spent outpoints are committed in a ch=
ild signature digest in a no-APO world.<br />This is still an interesting q=
uestion if you can remove spent outpoints commitment<br />by leveraging OP_=
SIZE or fixing other ECDSA signature components.<br /><br />Best,<br />Anto=
ine<br /><br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_=
attr">Le lundi 6 mai 2024 =C3=A0 20:25:33 UTC+1, Andrew Poelstra a =C3=A9cr=
it=C2=A0:<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 =
Mon, May 06, 2024 at 08:56:21AM -1000, David A. Harding wrote:
<br>&gt; On 2024-05-06 06:48, Andrew Poelstra wrote:
<br>&gt; &gt; [...] post-Taproot script can verify a
<br>&gt; &gt; trace of any program execution, as long as the individual ele=
ments it is
<br>&gt; &gt; operating on fit into 4-byte CScriptNums. You can therefore i=
mplement
<br>&gt; &gt; SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elemen=
ts by
<br>&gt; &gt; feeding in transaction data. Which of course can then be arbi=
trarily
<br>&gt; &gt; constrained.
<br>&gt;=20
<br>&gt; Thanks for your answer!  I think I understand.  However, we don=
9;t have ECDSA
<br>&gt; in tapscript; all signatures in tapscript are 64 bytes plus an opt=
ional
<br>&gt; sighash byte, so there&#39;s no natural variation in signature siz=
e.
<br>&gt;
<br>
<br>You can implement ECDSA. It will just take a *lot* of opcodes.
<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=3Df=
r&amp;q=3Dhttp://wpsoftware.net&amp;source=3Dgmail&amp;ust=3D17151294815300=
00&amp;usg=3DAOvVaw2zSaowE8QPY_5pe0-Ar_OD">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=3Dfr=
&amp;q=3Dhttps://www.wpsoftware.net/andrew&amp;source=3Dgmail&amp;ust=3D171=
5129481530000&amp;usg=3DAOvVaw1UjRgzo3NpzxwX6z6t0dzD">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/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.com</a>.=
<br />

------=_Part_16977_913307175.1715043326554--

------=_Part_16976_1588284193.1715043326554--