Delivery-date: Wed, 08 May 2024 17:37:23 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::12d as permitted sender) client-ip=2a00:1450:4864:20::12d;
MIME-Version: 1.0
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> <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
In-Reply-To: <bd37a9f1-7fb9-4111-a069-31c3665073d2n@googlegroups.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Tue, 7 May 2024 12:05:52 -0400
Message-ID: <CAEM=y+X-bhUuDxyYQ-MJGA49BgvnHW9-7L3zvBLPyJux=kqYbA@mail.gmail.com>
Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport
 Signatures (no changes needed)
To: Antoine Riard <antoine.riard@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@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.