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
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