[Bitcoin-ml] What i would like to see in the next HF + timeline

[Tom Zander]

On Saturday, 26 August 2017 14:31:07 CEST Amaury Séchet via bitcoin-ml 
wrote:
> Validation would go as follow:
> 
> newUTXO = utxo.add(block.getAllOutputs());
> foreach (i; block.GetAllInput()) {
>     if (!newUtxo.spend(i)) {
>         // Error !
>     }
> }
> 
> utxo = newUTXO;

This will fail in the case of these two transactions are included in a 
block.
a) a TX that spends the last output of txid1
b) a new TX that also hashes to txid1

I can think of a simple 3-transaction loop that is capable of creating a 
duplicate transaction-id. (and, yes, this is legal even wrt to bip 30).

This unfortunately kills the optimization you are thinking about.

But I have not seen a need of protocol changes for this, to be honest;
> Note that it is superior because the live set we are working with is the
> UTXO set, but all the spend operation do not need to be ordered anymore,
> so
> they can processed in parallel, or even on a cluster of machines.

The same effect can be had by simply pre-processing the transactions before 
the utxo check and sorting them based on dependencies. If a transaction does 
not depend on another in the same block, it can be done in parallel.
This is a relatively cheap solution to do because  if we already have the 
majority of that data in-memory in the mempool (assuming xthin usage here).

Notice that in Bitcoin Classic I have a research project where validation is 
almost entirely parallel already. The only part left that is not parallel is 
the utxo access. And the sorting optimization would make that even cheaper.
Currently it takes my not that expensive machine 2½ hours to validate from 
genesis to today. And there are plenty of optimizations left to do.

> The merkle tree computation could be changed as follow:
> 
> The left branch starting from the root contains only the coinbase.
> The right branch contains all the transactions - minus the coinbase,
> ordered by txid.
> Empty subtrees (when there is an odd number of nodes at some level) are
> 0x000...0001

This has been a wishlist for a long time, I agree. Would not mind increasing 
the block version for this :-)

> I voluntarily put the topic of malleability asside here as it is not clear
> what path forward we should take.

I have no problems with that, I still see no usecase in the next 12 months 
that requires a malleability fix on the main chain.

-- 
Tom Zander
Blog: https://zander.github.io
Vlog: https://vimeo.com/channels/tomscryptochannel