<div>A Commitment-suitable UTXO set "Balances" file data structure<br></div><div>- Allows pruned nodes to satisfy SPV nodes<br></div><div>- Allows pruned nodes to trustlessly start synchronizing at a Balances file's block height instead of the genesis block<br></div><div>- Allows all nodes in the network to verify their UTXO set's data integrity<br></div><div><br></div><div>For this to work, Bitcoin would need a new policy:<br></div><div>- A UTXO commitment is made every "Balances/UTXO Commitment Period" (BCP) blocks.&nbsp; The UTXO commitment is made on the state of the UTXO at BCP blocks ago.&nbsp; For example, if BCP is 5000, and we are creating block 20,000, then block 20,000 would contain a commitment on what the state of the UTXO was at block 15,000, right before any changes due to block 15,001.<br></div><div>- The commitment is made on the state of the UTXO "BCP blocks ago" instead of the UTXO state at the tip because: 1. Such a commitment can be made in a background thread and not delay mining/synchronizing node operations; 2. The work of creating the commitment doesn't have to be redone in the case of a fork.<br></div><div>- The file/commitment is made in a background thread, starting at least BCP/2 blocks after the last block containing a utxo commitment.<br></div><div><br></div><div>Balances file summary:<br></div><div>{<br></div><div>Header: 48 bytes<br></div><div>{<br></div><div>File Type: 4 bytes<br></div><div>File version: 4 bytes<br></div><div>size of balances: 8 bytes<br></div><div>root hash: 32 bytes<br></div><div>}<br></div><div>balances: "size of balances" bytes<br></div><div>balance index: "piece count" * (N + 4) bytes, N=4 proposed<br></div><div>merkle tree hashes: ~ 2 * "piece count" * 32 bytes<br></div><div>}<br></div><div><br></div><div>balances: is a list of balances sorted by txid:<br></div><div>{<br></div><div>length: 4 bytes<br></div><div>txid: 32 bytes<br></div><div>CCoins: variable length, depends on UTXO size<br></div><div>}<br></div><div><br></div><div>A "piece" is like in bittorrent's piece.&nbsp; I propose piece size = 32*1024 bytes.&nbsp; 2GB of balance data would then be divided into 65536 pieces.<br></div><div><br></div><div>transaction index is an array (with "piece count" elements) of:<br></div><div>{<br></div><div>txix: the first N bytes of a txid. I'm proposing N = 4<br></div><div>piece offset: 4 bytes, location of the first balance in the piece.<br></div><div>}<br></div><div><br></div><div>merkle tree hashes:<br></div><div>- array of "piece count" leaf hashes, hashing the balance pieces<br></div><div>- array of "(child layer count + 1)/2" node hashes, hashing pairs of child hashes, or copying up if only one child<br></div><div>- repeat ^ until the root hash is written<br></div><div>... except reverse the layer order. In other words, it should be breadth first.<br></div><div><br></div><div>==========<br></div><div><br></div><div>Data structure design notes:<br></div><div>- Most of the file's space is used by the balances.&nbsp; For example, given a 32kB piece size and 2GB balances, the non-balances data only consumes about 4.5MB.&nbsp; If N was increased to 32, ~6.5MB.<br></div><div>- piece size should be small enough that not that much effort is wasted when invalid pieces are received.<br></div><div>- piece size should also be small in the case that this data structure is used instead of block history for SPV proof.&nbsp; Then pruned nodes can satisfy SPV clients.<br></div><div>- The child count = 2 merkle tree structure is only necessary for if this data structure is to be used to satisfy SPV clients.&nbsp; If not used for such a purpose, then technically the root hash could have the leaf hashes as it's direct children. But practically this doesn't make a difference: merkle tree size is nothing compared to sizeof(balances).<br></div><div>- The only purpose of the balance index is to support SPV clients<br></div><div>- txix is a truncation of txid to reduce memory usage for a fully in-memory index to support SPV nodes.&nbsp; Maybe this truncation isn't worthwhile.<br></div><div><br></div><div>Other notes:<br></div><div>- We could make BCP 4383 blocks, which would be 12 times per year, given block period was exactly 10 minutes.&nbsp; But since block period is not exactly 10 minutes, and file names generated with period 4283 are much less comprehensible than file names generated with period 5000...&nbsp; I propose 5000.<br></div><div>- Having a shorter BCP period would result in more frequent checks on UTXO set integrity, and permit new pruning nodes to start synching closer to the tip.&nbsp; But it may require nodes to keep more copies of the balances file to satisfy the same backup period, and require more background work of creating more balances files.<br></div><div><br></div><div>===========<br></div><div><br></div><div>Suggested design change to the chainstate "CCoinsViewDB" utxo database:<br></div><div>- As it is designed now, the above proposal would require maintaining a duplicate but lagging UTXO database.<br></div><div>- I propose changing the "CCoins" data structure so that it can keep track of spends that shouldn't be included in the commitment. Maybe call it "vtipspends".<br></div><div><br></div><div>Then the process for updating the CCoinsViewDB would be:<br></div><div>1. Mark a txo as spent by adding the vout_ix to vtipspends.<br></div><div>2. SetNull() and Cleanup() during the background thread that creates Balances commitments.&nbsp; vtipspends would also need to be cleaned.<br></div><div>- The method for checking whether a txo was spent would need to be changed to check vtipspends.<br></div><div><br></div><div>At the same time, I know there is currently a lot of code complexity with handling forks and txo spends.&nbsp; Let me propose something to handle this better too:<br></div><div>- vtipspends could hold {vout_ix, blockhash } instead of just vout_ix.<br></div><div>- Checking whether a txo is spent will then require a parameter that specifies the "fork tip hash" or "fork chain"<br></div><div><br></div><div>Then in the case of a fork, no work has to be done to update the utxo database... it is immediately ready to handle answering spend questions for a different fork.<br></div><div><br></div><div>Feedback welcome.&nbsp; FYI I have coded up the creation of such a file already... So I am working on the implementation, not just the spec.&nbsp; I'd really like to hear what you guys think about my proposed changes to CCoins.<br></div><div><br></div><div>Cheers,<br></div><div>Praxeology<br></div>