From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 06 May 2024 18:15:28 -0700 Received: from mail-yb1-f185.google.com ([209.85.219.185]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1s49QV-0004N4-GC for bitcoindev@gnusha.org; Mon, 06 May 2024 18:15:28 -0700 Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-dc6b269686asf4567163276.1 for ; Mon, 06 May 2024 18:15:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1715044521; x=1715649321; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=wT57utt5xz0jGuUcuJTWkeXfTUHj49qG3eR5FLDIeOA=; b=Yt6HXMTzW3eiqv04DilJQ7EP89+aXI6D67cEkln1NVbZAptZh2H0Y2JtKszllYjy0o xc/Y0cohywVpVlc8O4TlTkJBXn3F6vlW1OJ/fFsi2HHo/b2cKz53vxwaeMbFHMGVlZ2V pSkcyfNLSBqgCmQN+igt57RPhYg7kHvuRDtP8nF+BzZ+JtJKtI9qvGu9U/r4oVCmNm4e d32SrXrjLf3wmVp3gqLgmRvT4rfYmjgxUhsKPnwDxOgT9QJkyPnv4FprhUXNFD9WHp88 8BLoEGvsigiSdQs/XSoNsdDeUK5uWLRaIg32X10SyCdJj8mT/jkTUIhRZG2wrMqvIgMA CYug== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715044521; x=1715649321; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=wT57utt5xz0jGuUcuJTWkeXfTUHj49qG3eR5FLDIeOA=; b=DDviYBbW8e1xAfyx+sZOAOKXjJ1exDyZdpFEO2kdjDldBKeeZUahUrIvdaReZEas3P KXRKysqokXYHvkZueHxryypSzcGL67SyYGpHJRMwXVNRRqu+qY//ZLlwMfl1pAoiuOAS QaSfk9GoISxWFwp4tf34SlADJ8pfDO2csnu7ktoyV06JUEDzNcfshB47uLXOfwbtcJoT Zw8rwBPE7is12pfOF7tXlHSpQIM2qlpMmQDpvHiBUloHvU5s5LO9euW78KIdvzZiXUnH Gue4ZqN1/usCybHxbrP5ZqiaWH5gITrs1svFdZkPe++F/Dp+LR+2KYNsM2mE4n/gQATa LTxA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715044521; x=1715649321; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=wT57utt5xz0jGuUcuJTWkeXfTUHj49qG3eR5FLDIeOA=; b=rn+7Uz2KEHSc4KU8GVW8ZEwJlBeCBLayja5X9DUUK64U5tgKlW/CeS7G+mUflpLM7+ AldpwfWS6PrB0H/pDqC33cIxQjfnBYwROtXH62R6lys90yH/w05JDeOinZK1BxgDUygN LGJP3B2LFBRrJdRGKdZl7gy2Cc54CYJvVSVbMHQ8Td+DaE4qq7eXkAhWZkoQaGd5F7lb pfhlL3leV2xIr9GPaR/meyuK+U1cua7kZxdpSq8LAq+h4hGy/+IHcxDqKmdgdyUAr55b 8Gc8mF47CH+ynUa/grwYCMFu9zAg6GyY08xhA5td3yWqnyJUPCLfoSB8SNHtwubIifze czOQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXpeGXYR9LoZQ8YXl+6h4OBf8Y1yfH+At7V5EJOmFfAicqWE4Sj2CwWYZvYG9oZAhIyTIe2x4eHUK8ReaF4k1foaSjBMao= X-Gm-Message-State: AOJu0YzE4j0cKdVDP0QNb/ZE2Myovgw2PnSidU+k8Y9U8Xs/UvZnlwRB OHivuBY9p9Hnsov6htPtVdRT0cGcgUN+UX3EMyvwxVYJldRw/q9p X-Google-Smtp-Source: AGHT+IEWpk+VXG4aM7Pt4zNGn7lxTousMitqwg4Eo+BNdbFTlRbVght/R8PTwIxhx5haI6EUVdqXTQ== X-Received: by 2002:a25:ce8c:0:b0:de6:e4d:e990 with SMTP id x134-20020a25ce8c000000b00de60e4de990mr11692298ybe.37.1715044520967; Mon, 06 May 2024 18:15:20 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a25:d652:0:b0:deb:438a:43c1 with SMTP id 3f1490d57ef6-deb438a4588ls2271295276.1.-pod-prod-06-us; Mon, 06 May 2024 18:15:19 -0700 (PDT) X-Received: by 2002:a81:924e:0:b0:61b:e6d8:1c01 with SMTP id j75-20020a81924e000000b0061be6d81c01mr3085724ywg.10.1715044519458; Mon, 06 May 2024 18:15:19 -0700 (PDT) Received: by 2002:a05:690c:f88:b0:620:4018:7c57 with SMTP id 00721157ae682-62040188055ms7b3; Mon, 6 May 2024 17:55:27 -0700 (PDT) X-Received: by 2002:a81:6041:0:b0:61b:e678:2591 with SMTP id u62-20020a816041000000b0061be6782591mr3254494ywb.4.1715043326975; Mon, 06 May 2024 17:55:26 -0700 (PDT) Date: Mon, 6 May 2024 17:55:26 -0700 (PDT) From: Antoine Riard To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: <47711dc4ffe9d661e8321b05b6adab4e@dtrt.org> 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" X-Original-Sender: antoine.riard@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_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,

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

If my understanding of y= our 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 adversa= ries
with hashrate capabilities:
- Alice Lamport-emulated signs a= nd broadcast her transaction X
- Coalition of Miners (e.g 30% of netwo= rk) refuse to include Alice's transaction X
- Alice can:
=C2=A0 = =C2=A0 =C2=A0 =C2=A0 - a) wait for the 70% honest network to mine her trans= action
=C2=A0 =C2=A0 =C2=A0 =C2=A0 - b) increase her feerate to bump i= ncentives to mine transaction X
- If Alice picks up option b)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 - Alice Lamport-emulated signs and broadcast her t= ransaction X by using ACP flag / CPFP
=C2=A0 =C2=A0 =C2=A0 =C2=A0 - Th= is assumes the consumption of a "fresh" fee-bumping UTXO
=C2=A0 =C2=A0= =C2=A0 =C2=A0 - This fee-bumping UTXO can be locked under a Lamport emulat= ed-pubkey

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

I believe you might even have = a worst-case scenario of this DoS where a coalition
of mining attacker= s force you to one-time sig all your Lamport pubkeys committed
in UTXO= s (original UTXO + fee-bumping UTXOs), in a way that the orignal UTXO canno= t
be moved because its feerate is perpetually under mempool min fee, o= r the marginal
ancestor feerate unit of miners block templates.
<= br />I don't know if this vector of attack is correct, however one can note= it could arise
in alternative spontaneous scenarios, such as second-l= ayers scarce liquidity allocation
(e.g dual-funding), where many UTXOs= concurrent spends might compete to confirm first.

> What do = you mean by this? k=3D0? I do agree that this scheme is making
> so= me very odd assumptions about ecdsa signatures and they may not
> h= old. Certainly no one should expect this scheme to be secure without
&= gt; a proof of security or at the least some sort of justification for why<= br />> 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 d= on't know if you could play with the transaction hash to produce
a cur= ve point which is equals to the point at infinity, especially in
conte= xt where the transaction hash is including inputs from multiple
non-tr= usted counterparties (e.g if you're using SIGHASH flags).

> I= t'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^9= 6
> 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 wou= ld be
> computationally expensive as mining 1,125,899,906,842,620 b= itcoin
> blocks. You'd probably be better off mining those blocks t= han grinding
> the r-value.

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

> I = think a more interesting open question of this post is if we have already h= ash-chain-based covenant
> "today" in Bitcoin. If by fixing the int= eger `z` of the s-value of ECDSA signature in redeem script, and
> = computing backward the chain of chids redeem scripts to avoid hash-chain de= pendencies.

Correcting myself on my initial email, the design b= ottleneck here is obviously
that spent outpoints are committed in a ch= ild signature digest in a no-APO world.
This is still an interesting q= uestion if you can remove spent outpoints commitment
by leveraging OP_= SIZE or fixing other ECDSA signature components.

Best,
Anto= ine

Le lundi 6 mai 2024 =C3=A0 20:25:33 UTC+1, Andrew Poelstra a =C3=A9cr= it=C2=A0:
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 ele= ments it is
> > operating on fit into 4-byte CScriptNums. You can therefore i= mplement
> > SHA2, ECDSA, etc., and reconstruct the pattern of SIZE elemen= ts by
> > feeding in transaction data. Which of course can then be arbi= trarily
> > constrained.
>=20
> Thanks for your answer! I think I understand. However, we don= 9;t have ECDSA
> in tapscript; all signatures in tapscript are 64 bytes plus an opt= ional
> sighash byte, so there's no natural variation in signature siz= e.
>

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.wpsoftwar= e.net/andrew

The sun is always shining in space
-Justin Lewis-Webster

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg= id/bitcoindev/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.com.=
------=_Part_16977_913307175.1715043326554-- ------=_Part_16976_1588284193.1715043326554--