Constant size fully validating node

Research
1

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:

  1. prove - The owner can prove an element is in the accumulator
  2. verify - Given an inclusion proof, anyone can verify the element is in the accumulator
  3. add - Add an element to the accumulator
  4. 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:

  1. 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
  2. verify - Given a merkle inclusion proof for output MMR, anyone can verify the output was created
  3. prove not spent - Given a merkle inclusion proof for the bitmap MMR, anyone can verify the output was not spent
  4. 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.

Syncing

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.

1 Like
2

We already do this for performance reasons[1]. It would take forever if we were adding all kernels each block. What you’re proposing is to just delete old kernels, which is fairly trivial, but as you mention, the node is no longer able to bootstrap others.

[1] https://github.com/mimblewimble/grin/blob/e7bbda81a0a815994955ce8fc71f710cd17a11bb/core/src/core/block_sums.rs#L28

1 Like
3

Thanks for the link, I always wondered how this is done :+1: Yeah, this is just the kernel accumulator part of the proposal. The more important part is the one that prunes the whole MMRs except for the MMR peaks while keeping the ability to fully validate given the same assumptions as the utreexo (transaction inputs include merkle inclusion proofs)

4

I have thought a bit about this and described how the lightest fully validating node would look like. It doesn’t need to store a single rangeproof, kernel (except for NRD), output, or a bitmap leaf. As for header MMR, you need the last week of the block headers.

Here’s the approach described https://gist.github.com/phyro/0ad4ccf71e936dd90545648110224e96

2 Likes
5

Nimble node support requires a new pair of p2p messages.
One to request a merkle proof of all inputs in a block with given hash,
and one to provide such a merkle input witness block. The latter would contain leaf and internal node hashes of both the output MMR and unspent bitmap MMR. In particular, there will be a hash of node v if the subtree at v has no inputs spent in that block, but v’, the sibling of v, does.

3 Likes
7

I have expanded the document a bit with things that came to mind, but will leave it as is for now. I think we should prioritize work on the wallet improvements first, so that we make it easy for anyone to use Grin. In my opinion, we can focus on this later since our nodes are still relatively small - perhaps in 2022.

1 Like