Utreexo Edits

[Sjors]

Back to you. I edited some of the beginning, but not further down.

In contrast to what I said in #25 let's use "utreexo" or "Utreexo" instead of "UTreeXO", since that's how it's spelled in most places:

• https://bitcoinops.org/en/topics/utreexo/
• https://eprint.iacr.org/2019/611.pdf
• https://github.com/mit-dci/utreexo

(I changed it in the whitepaper chapter; it was already correct here)

[Sjors]

I added a figure with explanation. utreexo-picture.pdf

The explanation starts in the last paragraph of the left page (but keep in mind that Latex has the annoying habit of moving figures around, so we can't say "the figure below").

Giving it another read and looking into your comments now...

[Sjors]

Back to you! Here's a preview: nado-c6.pdf

[Sjors]

Moving your comment here, because the inline stuff gets burried:

Here's where I don't quite get it: You have the scenario of all the UTXOs in existence in a tree. So if it's an even number, it's a perfect tree, and if it's odd, why not just a perfect tree but then this extra other tree? Like what is the limit to what can go in a tree? Is the limit based per block? I am probably hugely misunderstanding this...

It's multiple trees that form a forest. I added an example in the text: when the UTXO set has 6 coins, the forest has 1 tree with 4 coins and 1 tree with 2 coins. Your node then has to keep track of 2 root hashes, 32 bytes each, so 64 bytes in total (versus ~300 bytes if it had to store the UTXOs).

There's no per block limit; it's about the number of coins in existence, which goes up and down only a little bit with each block. And there's no limit in practice; the example I added for multiple UTXO's per person on earth would still only need a small number of trees (it's like writing the number 4 billion in binary; it just takes ~30 digits).

[deutschbitte]

Done! Feel free to merge if you're happy

[Sjors]

Thanks!