Link to the proposal overview: Nimblewimble
Nimblewimble sounded fun and hints at a fast/light implementation. This is just a name for fun, we should probanly just call it a pruning node to avoid confusing people.
Disclaimer: I don’t fully understand Utreexo so I could have made some mistake.
Constant size fully validating node for Grin
I was thinking how to have a fully validating node that is as small as possible.
There been many discussion on keybase around a pruning node (I sometimes refered to it as “nimble” node). I tried describe the discussed idea first here and later made another gist. It describes how to have a kernel accumulator curve point that holds the sum of all the kernels. A node that would use this would still be able to fully validate new blocks without keeping all the kernels around (just their sum). Such a node is of course not able to bootstrap new nodes because it doesn’t keep around the information needed to do that. So this reduces the kernels to a constant size, but we still have a UTXO set that grows linearly over time.
Bitcoin -> Utreexo
In Bitcoin space, a solution called Utreexo was proposed which is a hash based accumulator. It claims that by increasing the bandwidth of transactions by ~25%, you could have a fully validating node that would only be a few kilobytes in size.
Specifically the operations that seems to be needed for the Utreexo accumulator are:
- prove - The owner can prove an element is in the accumulator
- verify - Given an inclusion proof, anyone can verify the element is in the accumulator
- add - Add an element to the accumulator
- delete - Delete an element from the accumulator
Similarly as a pruning node, a ‘utreexo node’ would not be able to bootstrap new nodes. But nevertheless, it would allow running Bitcoin full node on a mobile phone.
Grin -> combination of MMRs
I was thinking about this a bit and it seems that our existing data structures already provide the functionality that the utreexo dynamic hash accumulator provides.
If I have the MMR peaks, then given a transaction where every input comes with an inclusion proof for the output PMMR and the inclusion proof for the Bitmap, then we can:
- prove - I can prove an output is in the output MMR by computing the merkle inclusion proof and adding it along the input in the transaction
- verify - Given a merkle inclusion proof for output MMR, anyone can verify the output was created
- prove not spent - Given a merkle inclusion proof for the bitmap MMR, anyone can verify the output was not spent
- add - Given the previous MMR peaks, we can compute what the new MMR peaks are (because MMRs are append-only)
I think that we don’t need to support the “delete” operation because the inclusion proof for the Bitmap MMR can already answer whether an output has been ‘deleted’ or not.
I’m not sure whether we would also need the inclusion proofs for rangeproofs. I also don’t know how much more this would add to the p2p layer block and transaction size.
When the node/wallet would sync, it would still need to download all the kernels but it would be reducing them to the accumulator curve point as described here. Similarly, the MMRs would need to be downloaded and verified but once the leaves are verified, the node could just drop the information about the leaves and just keep the MMR peaks. It would however probably need to keep the sum of the utxos in order to validate the ending state with the sum of the kernels. In case a wallet seed is given, the node could remember the merkle paths for the outputs it owns to have the information needed to spend the outputs.
NOTE: this node would not be able to bootstrap other nodes with the UTXO set while the variant that would only accumulate kernels points would be able to do that theoretically.
Edit: There is no point in the wallet remembering the merkle paths. This is because there is no guarantee that the merkle inclusion proof for output
O1 will be the same at the time of transaction broadcast and as at the time it gets included in a block. You’d really need others to provide the inclusion proofs, one such obvious solution would be that a node could support
MerkleBlock type which would be derived from the current
Block by checking the inputs and adding the needed inclusion proofs.