<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body><div><br></div>
<div>On Sat, Aug 26, 2017, at 14:31, Amaury Séchet via bitcoin-ml wrote:<br></div>
<blockquote type="cite"><div dir="ltr"><div><div><div><div><div><div><br></div>
</div>
<div>newUTXO = utxo.add(block.getAllOutputs()<wbr>);<br></div>
</div>
<div>foreach (i; block.GetAllInput()) {<br></div>
</div>
<div>&nbsp;&nbsp;&nbsp; if (!newUtxo.spend(i)) {<br></div>
</div>
<div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // Error !<br></div>
<div>&nbsp;&nbsp;&nbsp; }<br></div>
<div>}<br></div>
<div><br></div>
</div>
<div>utxo = newUTXO;<br></div>
<div><div><div><div><div><div><div><br></div>
<div>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.<br></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote><div><br></div>
<div>This would allow "back references". A block could contain:<br></div>
<div><br></div>
<div>Transaction 1. spending A containing output B.<br></div>
<div>Transaction 2. spending B containing output A.</div>
<div><br></div>
<div>This would complicate clients/tools that prefer tx-by-tx processing.<br></div>
<div><br></div>
<div>You can use canonical ordering in the merkle tree without this. The "consensus" rule would then be that their must be a valid linear reordering of the transactions that hash to merkle root. The implementation would then work tx-by-tx but simply pushing txs with missing imputs to the end of the queue.<br></div>
<div><br></div>
<blockquote type="cite"><div dir="ltr"><div><div><div><div><div><div><div><div><br></div>
<div>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.<br></div>
</div>
<div><div>The merkle tree computation could be changed as follow:<br></div>
</div>
<div>The left branch starting from the root contains only the coinbase.<br></div>
<div>The right branch contains all the transactions - minus the coinbase, ordered by txid.<br></div>
<div><div>Empty subtrees (when there is an odd number of nodes at some level) are 0x000...0001<br></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote><div><br></div>
<div>Note, I think you can just as well take the remainder hash of an odd set one level up without hashing it to 1? <br></div>
<div><br></div>
<div>I certainly see that an ordered merkle tree and a left branch for the coinbase are an improvement, though I am not sure whether it is enough to merit changing.<br></div>
<div><br></div>
<div>The compression by ordering seems to be rather tiny on 32-byte hashes, and although coinbase reordering is expensive, it is equally expensive for all miners. If we want to pursue subchains/NG/other block-over-time solutions) shouldn't we first be work out of the viability of this direction?<br></div>
<div><br></div>
<blockquote type="cite"><div dir="ltr"><div><div><div><div><div><div><div><div>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.<br></div>
</div>
<div>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.<br></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote><div><br></div>
<div><br></div>
<div><div>Personally, although we shouldn't be afraid of hardforks, I think we should aim for protocol change minimalism. Changing things that can be worked around and are only an optimization should be avoided as for every change, a fully validating client must understand old and new. The spec can only grow.<br></div>
<div><div><br></div>
</div>
<div>For instance, if it is deemed unnecessary&nbsp; to update the difficulty algorithm as an emergency patch for the oscillations, then why change at all? Are we suspecting more problems than we currently have? I think that apart from the current fork problems, the existing algorithm serves us well.<br></div>
</div>
<div><br></div>
<div>It is tempting to try to improve stuff,&nbsp; but is there really  strong enough motivation or demand for such fundamental changes to the merkle tree or the long term difficulty rules at this moment?<br></div>
<div><br></div>
<div>Regards,<br></div>
<div>Tomas<br></div>
<div>bitcrust<br></div>
</body>
</html>