From: Antoine Riard <antoine.riard@gmail•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
Date: Mon, 6 May 2024 17:55:26 -0700 (PDT) [thread overview]
Message-ID: <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com> (raw)
In-Reply-To: <ZjkqIzPSFLc0GJJ1@camus>
[-- Attachment #1.1: Type: text/plain, Size: 6410 bytes --]
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 == 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
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
using ACP flag / CPFP
- This assumes the consumption of a "fresh" fee-bumping UTXO
- This fee-bumping UTXO can be locked under a Lamport
emulated-pubkey
I think this scheme with a one-time usage property is more exposed to
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
coalition
of mining attackers force you to one-time sig all your Lamport pubkeys
committed
in UTXOs (original UTXO + fee-bumping UTXOs), in a way that the orignal
UTXO cannot
be moved because its feerate is perpetually under mempool min fee, or the
marginal
ancestor feerate unit of miners block templates.
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-layers scarce
liquidity allocation
(e.g dual-funding), where many UTXOs concurrent spends might compete to
confirm first.
> What do you mean by this? k=0? 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=0 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 field
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 assuming
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
might
be just a classicla time-space trade-off here.
> I think a more interesting open question of this post is if we have
already hash-chain-based covenant
> "today" in Bitcoin. If by fixing the integer `z` of the s-value of ECDSA
signature in redeem script, and
> computing backward the chain of chids redeem scripts to avoid hash-chain
dependencies.
Correcting myself on my initial email, the design bottleneck here is
obviously
that spent outpoints are committed in a child signature digest in a no-APO
world.
This is still an interesting question if you can remove spent outpoints
commitment
by leveraging OP_SIZE or fixing other ECDSA signature components.
Best,
Antoine
Le lundi 6 mai 2024 à 20:25:33 UTC+1, Andrew Poelstra a écrit :
> 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
> 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.
> >
> > Thanks for your answer! I think I understand. However, we don't have
> 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.
>
> --
> 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
>
>
--
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 email 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.
[-- Attachment #1.2: Type: text/html, Size: 7876 bytes --]
next prev parent reply other threads:[~2024-05-07 1:15 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-04-29 0:30 Ethan Heilman
2024-04-30 12:32 ` Matthew Zipkin
2024-04-30 13:25 ` Ethan Heilman
2024-04-30 14:21 ` Andrew Poelstra
2024-04-30 20:43 ` Ethan Heilman
2024-05-01 3:46 ` Antoine Riard
2024-05-01 20:02 ` Ethan Heilman
2024-05-06 7:39 ` David A. Harding
2024-05-06 16:48 ` Andrew Poelstra
2024-05-06 18:56 ` David A. Harding
2024-05-06 19:06 ` Andrew Poelstra
2024-05-07 0:55 ` Antoine Riard [this message]
2024-05-07 16:05 ` Ethan Heilman
2024-05-07 4:11 ` David A. Harding
2024-05-07 14:34 ` Andrew Poelstra
2024-05-09 0:31 ` Ben Carman
2024-05-09 12:46 ` Andrew Poelstra
2024-05-11 2:53 ` Antoine Riard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com \
--to=antoine.riard@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox