Porting Utreexo to Monero about research-lab

[expiredhotdog]

@kayabaNerve I'm starting to look into this concept, and I have a question regarding your FCMP implementation.

If I understand correctly, the state of the enote set could be represented as a sort of merkle root, since that is what the proofs will be checked against, correct? If so, what amount of data is needed to append new enotes to the set (that is, to update the root)?

I would think that you wouldn't need access to the full enote set. Since in a normal merkle tree, optimizations aside, a merkle proof suffices to insert a new leaf, I would hope that the FCMP root would be the same. Unless my understanding of your work is completely off.

Thanks, and sorry to bother you :)

[kayabaNerve]

You cannot insert into a Merkle tree with a Merkle tree proof. You need the list of right-most branches. That comment holds here.

Mind if I ask what the interest is for this? Utreexo doesn't reduce the requirements of running a node. It introduces a new class of node which can validate new transactions when spoonfed the relevant pieces of data from actual nodes (increasing bandwidth notably). While the argument for Utreexo is the replacement of the blockchain state with an accumulator to better service wallets, this accumulator wouldn't be usable to create TXs under Monero. You'd still need the full blockchain state.

If you have the full blockchain state, you don't need the accumulator to verify old TXs.

Accordingly, this seems completely pointless.

[kayabaNerve]

If the goal is solely pruning the blockchain history, then #110 would solve this for the future and the history could be replaced by a meta-proof as well (as proposed for Bitcoin by... ZeroSync?).

[expiredhotdog]

I was being general by saying you need a merkle proof to insert new leaves. In this case, you would have an inclusion proof of the rightmost leaf, allowing you to recompute the rightmost "wall" of the tree. Or, and this is what I was hoping could be done instead, it can be optimized in the style of Utreexo where the client can cache only the rightmost leaves and not need external proofs for adding new outputs. So it sounds like the FCMP tree can be treated as a normal merkle tree?

Utreexo has about 10-15% bandwidth overhead with good caching, and I would hope to get "Enotree" down to at least 25-30% with FCMPs. I don't think your assessment of Utreexo is accurate, since by that standard, Bitcoin pruned nodes also seem to be "spoonfed the relevant pieces of data from actual nodes."

As for the interest, I think effectively eliminating the storage requirement can make a strong argument for this in certain use cases. Here are some that come to mind.

• Fully verifying recent blocks for light wallet users, significantly improving upon the security of SPV clients
• Fully verifying blocks on storage- or I/O-constrained hardware
• Transfer state between devices - for example, do IBD on a desktop computer and use a QR code to transfer the state to a cellphone

[kayabaNerve]

The proof for the right-most leaf is a poor indirection for the right-most leaves. It just lets you recalculate them.

Yes, FCMPs are a standard merkle tree.

Bitcoin pruned nodes do not need active spoonfeeding. They maintain the full state, unless Bitcoin pruning has radically diverged from my concept of pruned nodes. They simply don't have the blockchain history and can't be synced from. Utreexo nodes, with each new block, need the relevant pieces of state given to them (with proofs) to avoid even keeping the state around.

With Monero, such a design would also work to avoid keeping the state, except it'd be unusable to service wallets. Wallets must be serviced by a node with state. Accordingly, a pruned node does have state, doesn't have the blockchain history, can verify new blocks (without overhead and spoonfeeding), and can service wallets.

Light wallet users should be willing to carry state around if they also want to fully verify blocks IMO. Full verification is extremely computationally expensive (Borromean signatures 🤮) and state is theoretically just a few hundred MB by my estimate? I personally think it's a really weird device to posit where it can't store a few hundred MB of state, yet does have the computational power to reasonably verify Monero. I do concede such devices do exist however. Why they'd want to be used is a distinct question.

I also do know you specified "recent blocks", but I don't personally think the age of the block should make a difference. Once the claimed TX is at a specific confirmation depth on the best chain, the only additional assumption you make by not verifying the block is that the TX is correct. I'd find it weird to have two confirmation depths, one for assume correct, one for accept payment without assuming correct. If they're the same, no actual benefit is offered.

Transfer state between devices

You can already do that and then just verify blocks normally. The whole point of Utreexo is so you don't keep/have the state. If you're transferring a state snapshot, and are willing to store the state snapshot, you can verify as a pruned node (pruned as in theory, not as in Monero which has some specific pruning configurations).

Though of course, my opinions on the matter don't prevent, and shouldn't if you still believe in, your work. Happy to answer questions re: FCMPs :)

[expiredhotdog]

My point with pruned nodes is that the way they're given a new block is fundamentally the same as when Utreexo nodes are given a new block, albeit Utreexo needs the proofs. They can both propagate the new block to their peers, but as you said, do not maintain history. I think of the proofs as analogous to SegWit witness data, just not on the consensus-level. Utreexo being the "SegWit nodes" and the rest of the network being "non-SegWit nodes". A pruned node can be queried for the UTXO set, true, but its response cannot necessarily be trusted.

If a post-FCMP node only needs the merkle root and key images for full verification of new Seraphis transactions, then yes, that would probably only take up at most a couple gigabytes. The bigger problem would be verifying then-old RingCT transactions, which would require access to dozens of times more state. The Enotree proofs for these would be large, but would become rare enough (like pre-RCT spends are today) to not be a huge deal. Maybe it would be better to store key images locally, and only rely on Enotree for transactions spending RingCT enotes.

(How many key images have been spent at this point? I would think it would be at least a gigabyte or two's worth)

The goal for this would be to act as a sort of SPV+ client that doesn't blindly trust PoW as much as normal SPV clients. The best chain is by definition the longest valid chain, so SPV clients are giving up this verification, not the other way around. A miner who's lucky or quickly rents more hashpower can easily fool SPV clients, but would find it significantly harder to fool "SPV+" clients. The SPV+ client could check the most recent say 50 or 100 or 200 etc blocks, to have more confidence in the chain tip's validity. Additionally, if it sees a long chainsplit between the attacker and the honest network, it can go back to the fork height and identify which chain is valid.

Thank you for answering my silly questions :)

[kayabaNerve]

Those "proofs" are the spoonfeeding I'm referring to. It's trading state storage for bandwidth + additional external work, which of course is its point.

I would not at all call this analogous to SegWit. Non-SegWit nodes can verify new blocks without the SegWit data (as their consensus rules are to follow the best chain, with the unrecognized opcode meaning the TX is valid). They accordingly don't need any additional data. Even if they did have the additional data sent to them, they'd just ignore it.

Under RingCT, the blockchain state can be summarized as the output keys, commitments, and key images. For the current ~90m outputs on-chain (under RingCT, I'm ignoring the cryptonote pools) that's 90,000,000 * 32 * 3 bytes, or ~8.7 GB. If we had that output set under Seraphis, it'd only be * 2 under Grootle (as the output keys and commitments would be squashed). With FCMPs, it's * 1, with the logarithmically sized tree edge.