Subject: Re: [bitcoindev] Signing a Bitcoin Transaction with Lamport Signatures (no changes needed)

From: Antoine Riard <[email-masked]>
Date: Mon, 6 May 2024 17:55:26 -0700 (PDT)

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 [email-masked].
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/bd37a9f1-7fb9-4111-a069-31c3665073d2n%40googlegroups.com.