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

[Amaury Séchet]

Hi all,

If we want to scale big we'll have to do a HF from time to time. Longer
term, we may want to use extension point to add new features, but we are
not there yet - more on extension points later on.

There seems to be a few changes that are relatively obvious, but hard to
advocate for in a climate where HF are not acceptable.

The first that come to mind is the ordering of transactions in a block.
When transactions spend from each others they need to be in the block in a
specific order. This create a situation where the block needs to be
verified serially, or where you need to work with a spend tree rather than
the UTXO set - and it is significantly larger. Both options are hindering
options for vertical scaling. But this ordering is completely unnecessary.
Because transaction hash their input, producing an invalid chain of
transaction require to break SHA256, and if that happens, transaction
ordering is doomed anyway. As a result, we may which to get rid of the
transaction ordering rule within a block. Validation would go as follow:

newUTXO = utxo.add(block.getAllOutputs());
foreach (i; block.GetAllInput()) {
    if (!newUtxo.spend(i)) {
        // Error !
    }
}

utxo = newUTXO;

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.

Which leads to the way the merkle root is computed. It has a few issues.
The first one is that it is susceptible to subtree repetition that would
recompute the same root. It is possible to check for this, and indeed the
software does it, but any software that does so incorrectly will be
susceptible to being fed invalid blocks. This is undesirable. The second
problem is that as blocks gets bigger, swapping the coinbase become
expensive. On the other hand, we want to deploy solution to build the block
over time sub as NG, subchains or alike (not that they are alike in what
they do, but the underlying idea, to build the block over time, is the
same). This is important for scaling. Finally, if we get rid of the strict
ordering rule above, we can define a canonical ordering in the merkle tree
so that block can be merged in a deterministic manner which is useful for
NG or subchains, but also opens opportunity for extra compression in
CB/XThin and allows for proof of absence in a block.

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

Interestingly enough, this allow for the same kind of merkle proof that
already are possible today. In addition, because transaction are ordered by
txid, it is possible to prove absence from the tree easily.

These changes are not very glamorous, but good data structure as the key
for successful scaling and I think these will bring us in that direction.

Now among the more sexy changes. One is adopting a more interesting
difficulty adjustment algorithm would also be nice. I discussed this in
another email, so there is no point repeating it all here.

The maximal target ensure that several bits in the block hash are always 0,
no matter what. These bits can be repurposed as an extra nonce. This is a
very small and easy patch and current nonce space is not quite large enough.

I voluntarily put the topic of malleability asside here as it is not clear
what path forward we should take. Hopefully the one above shouldn't be too
controversial and impact for wallet should be minimal.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-ml/attachments/20170826/5e8cd1cb/attachment.html>