Faster Public Divergence Detection

[QuinnWilton]

Fission has had a little bit of discussion over the past week around techniques for optimizing WNFS divergence search, and now that we have a Github organization for WebNativeFileSystem, we thought it'd be worthwhile to open up that thread for discussion!

The thread can be found here: https://talk.fission.codes/t/optimizing-public-wnfs-divergence-search/2534

The problem being solved is one of determining at what point two public WNFS trees have diverged, and I've offered up one proposal that uses hash targets to construct a sort of skip list over the revision history that might be used to efficiently navigate through it and perform these kinds of divergence searches.

We're pretty big fans of the idea internally, but there's obviously a lot of questions that still need to be answered around the specific implementation details, how the concepts should be named, and so on, so any any all feedback is welcome!

Some of the info in there may assume some context that hasn't been explicitly written down yet, so feel free to ask for clarifications if anything isn't clear :)

[QuinnWilton]

@b5 I'm tagging you because you might find this topic interesting! Feel free to tag Kasey too if you'd like: I'm not sure what her Github handle is, but her thoughts are also more than welcome 😄

[expede]

I believe it's @ramfox

[b5]

Yep! @ramfox is Kasey's handle. Thanks for the heads up @QuinnWilton, I'll take a read through & report back 😊

[expede]

Via @matheus23 in the Discourse thread:

What are your thoughts on the idea of putting these skip links next to the public filesystem (sort of like an index) instead of inside of it?
This way we’re decoupling the correctness of the skip links/index from the public tree itself, more concretely: We can throw away the index and recreate it if we figure out something went wrong without having to change the public filesystem. I think this is a huge advantage since this makes changing the index/skip list for any reason (maybe we come up with a better structure in the future?) much cheaper: We want the hashes of blocks in the public filesystem to be as long-lived as possible, since they’re used to witness causal relationship.

Oh, I like that! Since we also probably want to send a BUNCH of these at once, we can maintain them really easily as essentially dag-json/dag-cbor, and not need to hold the entire node for old data that we don't care about, and send over really compact "sync list"

[QuinnWilton]

Agreed! I also really like the point about being able to experiment with different indexes later on, and separating the index from the data seems like a natural step toward supporting that.

[b5]

Fully support moving the skip list(s) out of the filesystem itself. I think the concept is great, and want to highlight two consequences of moving the lists out of the "core" data structure:

• algorithm can be defined to accept a WNFS instance as an arg, decoupling skip list implementations from WNFS implementations (fantastic from a getting things done perspective)
• internal WNFS methods lose any access to the optimizations afforded by a skip list.

Seems most of the benefits of a skip list are on the sync / merge side, which also accepts WNFS instances as args, so the match seems natural to me. It'll be interesting to see if "local history lookup heavy" use cases emerge, and in that case it may be reasonable to define an interface that treats skip lists as a local caching layer

[expede]

We've also been talking a bit about how to ensure that the skip list is correct / trustable, given BFT constraints. While SNARKs are probably too slow today for running against every update. Since hash targets let us globally agree on what the checkpoint nodes should be (e.g. every roughly 1024), then we can recursively SNARKify those. This lets us share these indices with much higher confidence than "trust me"

[b5]

hmmm.... I'm a fan of writing support for SNARKs into the spec, but can we skip 'em for a first implementation? I'll take a working "trust me" protocol (aka 99% of the internet at the moment) over one that includes all the complications SNARKs introduce at the moment.

[expede]

This is all optimization, so yeah we can totally push it off for now... and in fact skip the "trust me" completely (i.e. build a local index)