Merkle Tree and Trillian – Good idea, bad idea?

[tbarker]

Storing 100,000 or even 100 of millions of ENS entries on-chain could be very expensive. And in most cases, we simply need to prove inclusion. (Except Firefly who are an interesting side-problem here... 🙂)

Merkle-Trees are the usual way of doing this... and we have libraries https://github.com/OpenZeppelin/openzeppelin-solidity/blob/master/contracts/MerkleProof.sol

And this is how Google Certificate Transparency, and the spin-out open source project Trillian works https://github.com/google/trillian

Questions include :-

• How do we modify entries reliably?
• Where do these trees get stored? Swarm?
• What on-chain logic does this hinder?

Hopefully this can lead to wider solutions in terms of tracking and building on-chain logic around large datasets.

[makoto]

@tbarker can you start adding members? If no member till tea time, I will close this issue.

[makoto]

@tbarker can you start adding members? If no member till tea time, I will close this issue.

[tbarker]

Suppose a domain, say facelook.eth has a resolver which handles it's subdomains through a Merkle-Tree. We can manage this through defining an additional interface, as a resolver is only required to implement EIP165. The main ENS doesn't define how this look-up should happen.

So we could create an additional interface with a method addrByTree(bytes32 node, bytes32[] proof) mirroring EIP137 and so on. Each of these would then inherit from an interface implementing a treeRootUri() function returning a URI. And treeRoot() giving the corresponding root hash.

This does leave this resolver only storing the root hash, so the entire set of sub-domains is logically erased and re-written on any update. It would not be possible to change, ex. thomasthomas.facelook.eth in isolation.

There's also the question of where the full-tree is stored. Possibilities include a Trillian node with an HTTP endpoint, or as a blob on Swarm.

[tbarker]

If we wanted to be able to modify the tree in a controlled way, we'd would need to keep past versions of the tree, allow incorrect modifications to be challenged, and give incentives for doing so.

Perhaps a ring of 128 previous root hashes, and a challengeAndRevert(...) function.

I'm not sure I want to re-implement Plasma right now, so I'm going to shelve this and join a team 🙂

But I do like the notion of there being a resolvable319845134.pacemaker.gmedicaldevices.eth domain, or MySpace-style social handles for a single service.

[Arachnid]

If we wanted to be able to modify the tree in a controlled way, we'd would need to keep past versions of the tree, allow incorrect modifications to be challenged, and give incentives for doing so.

Why not just require the user to pass in the part of the tree they're modifying, along with a proof?

[tbarker]

This would work for insertions/deletions permissioned by 1-or-more key pairs. Which when I think of it, is all that most applications would ever need. Sparse Merkle trees are also interesting...