From: Ethan Heilman <eth3rs@gmail•com>
To: Antoine Riard <antoine.riard@gmail•com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)
Date: Tue, 7 May 2024 12:05:52 -0400 [thread overview]
Message-ID: <CAEM=y+X-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux=kqYbA@mail.gmail.com> (raw)
In-Reply-To: <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
Hi Antoine,
Responding in line:
> - 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.
It sounded like originally you were saying she can't bump her fee
without double signing, but as you point out ANYONECANPAY or CPFP
let's you do fee bumping without double signing. This doesn't seem
different from say a pre-signed bitcoin transaction that you can't
change transaction hash of.
> 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).
I don't see the attack. If the point at infinity is forbidden, how is
this exploited? Wouldn't the attacker's signature just be rejected by
the network?
> 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.
If someone discovers a smaller r than used in the signatures, they
would break the existing signatures I agree. Grover's might break P2SH
in general so Bitcoin might be in real trouble at that point.
> 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.
No APO?
Thanks,
Ethan
--
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/CAEM%3Dy%2BX-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux%3DkqYbA%40mail.gmail.com.
next prev parent reply other threads:[~2024-05-09 0:37 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
2024-05-07 16:05 ` Ethan Heilman [this message]
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='CAEM=y+X-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux=kqYbA@mail.gmail.com' \
--to=eth3rs@gmail$(echo .)com \
--cc=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