[Bitcoin-ml] Partial UTXO tree as commitment

Tomas tomas at bitcrust.org
Wed Sep 6 18:54:21 UTC 2017

On Wed, Sep 6, 2017, at 16:23, Chris Pacia via bitcoin-ml wrote:

> I tend to agree with all this. Assuming the ECMH is very cheap then
> this would seem to have the low cost we're looking for. You did
> mention three rolling hash operations per utxo. Couldn't the bucket
> hash just be updated with each utxo (1 operation) and then the tree
> could just be calculated once, as the last step when verifying the
> root? Not likely a huge savings but it's probably not necessary to
> update the root for each utxo.> 

This is possible and saves for the lower depth. I suggested 3 hash
operations per UTXO  with a tree depth of 5 depth, assuming we could
calculate the lowest 2 depth on calculating the root. The right balance
here needs to be found.

> Also, there would seem to be some issues to consider at the point
> when the transaction count passes the boundary. We would likely
> need to recompute all the buckets and take a performance hit for
> this one block.> 

This is certainly costly, though rare. And it would even be possible for
it to flip flop back. I think it will we acceptable (ECMH itself claims
4 million hashes/sec on modern hardware), but we'll have to carefully
look at benches to see if this is viable.
Tomas van der Wansem
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-ml/attachments/20170906/05c3a260/attachment.html>

More information about the bitcoin-ml mailing list