https://cips.ceramic.network/CIPs/cip-124
Recon
Recon is a sets reconsideration protocol to be used for synchronization of stream tips in ceramic network.
Stream Sets bundle a number of streams together so the ceramic node with a common interest in those streams can synchronize efficiently.
Once a set of streams is bundled into a stream set Recon can be used to sync ranges within those sets.
Will the Recon protocol fully replace libp2p pubsub, or will pubsub still be offered as a fallback?
how could indexer adapt to this change? seems naive “pubsub topics → loadStream → DB” would no longer work? How does loadstream work with recon?
Moved your post here @0xEE3CA4dd4CeB341691. We are working on a new event stream API that would allow for subscription to a set of streams. This API would rely on Recon. Hope to have this up as a new CIP next week.
For context: Recon by AaronGoldman · Pull Request #124 · ceramicnetwork/CIPs · GitHub
So I was asking if using bloom filter would speed up the recon proces as it was used in some prior works mentioned in the paper
Low Complexity Set Reconciliation Using Bloom Filters | Paper Review - YouTube
you: [ your initial keys ]
they: [ their initial keys ]
-> ( request ) [ their keys after processing request]
<- ( response ) [ your keys after processing response]
Current
you: [ape,eel,fox,gnu]
they: [bee,cat,doe,eel,fox,hog]
-> (ape, h(eel,fox), gnu) [ape,bee,cat,doe,eel,fox,gnu,hog]
<- (ape, h(bee,cat), doe, h(eel,fox), gnu, 0, hog) [ape,doe,eel,fox,gnu,hog]
-> (ape, 0, doe, h(eel,fox,gnu), hog) [ape,bee,cat,doe,eel,fox,gnu,hog]
<- (ape, 0, bee, 0, cat, h(doe,eel,fox,gnu), hog) [ape,bee,cat,doe,eel,fox,gnu,hog]
-> (ape, h(bee,cat,doe,eel,fox,gnu), hog) [ape,bee,cat,doe,eel,fox,gnu,hog]
<- (ape, h(bee,cat,doe,eel,fox,gnu), hog) [ape,bee,cat,doe,eel,fox,gnu,hog]
After using a bloom filter
you: [ape,eel,fox,gnu]
they: [bee,cat,doe,eel,fox,hog]
-> ([ape, h(eel,fox), gnu] + bloom(eel,fox)) [ape,bee,cat,doe,eel,fox,gnu,hog]
<- ([bee,cat,doe,hog] + [ape, h(bee,cat), doe, h(eel,fox), gnu, 0, hog] + bloom(ape..hog)) [ape,bee,cat,doe,eel,fox,gnu,hog]
And @AaronDGoldman pointed out that bloom filter does have its bandwidth cost with it
e.g. If we through in a 2KiB filter we could probably send all remaining key when we got to about 1,000 keys in a range. Speeding up the last few rounds.
Markdowns rendering in the last few section of the doc seems broken
https://cips.ceramic.network/CIPs/cip-124
Have we looked at Car Mirror as as mentioned by Aaron? Is it possible to overlay recon on top Car Mirror ?
I have not studied deeply spec/SPEC.md at main · fission-codes/spec · GitHub
mostly cheating by watching the talks.
CAR Pool and more - @expede - Data and IPFS: Transfer - YouTube
CAR Mirror Reflections - James Walker - YouTube
The use case for Car Mirror was WNFS which has a filesystem in a DAG. It uses the structure of the dag to break up the blocks into sections with a good number of blocks for the bloom filter. This is great for the WNFS DAGs with large amounts of structural sharing.
Ceramic is a large number of streams most of which have less than 20 events and with 2 events being the most common case. This leaves us with much less structure to exploit. This is why we sort the events by the sharding key. Once both sides sort the events, they now have a structure to exploit to break up the ranges. While Car Mirror may be a useful protocol for syncing data between a ceramic node and a client it, at least unmodified, may not be well suited to our ceramic node to ceramic node sync.
I general there are many techniques that could be used to increase the likelihood of sending the needed data in earlier round to reduce the number of rounds, bloom filters among them.
This makes sense. I guess car mirror and recon are just similar at high level but quite different.
Just wondering how would loadStream work in the context of recon?
large stream are timeout like
Regarding size of bloom filter variations, it seems to rank like below but haven’t really digged into how each works …
To add my perspective here. Recon will be used to exchange eventIds only, not any of the actual event data. When Recon is first rolled out we will still rely on Bitswap to exchange the event data itself. At some later point it makes sense to swap bitswap for something that is more efficient. That might be CarMirror, or something else, possibly more optimized for Ceramic.
Another question, where is prolly tree used in recon?
Seems like a cuckoo filter might work because it grows in size to include more entries. Not sure if it is associative though?
My intuition is to start with an associative hash since we know it works, then at some later point investigate if some type of bloom filter could be used to optimize the protocol.
@AaronDGoldman thoughts about removing prevTimestamp from eventIds, and instead putting both after and before timestamps in events returned by ceramic_poll on the Ceramic API?
Not sure if it adds much value on eventIds and I think it could make the algorithm to implement eventIds more complicated.
It doesn’t have to be a prolyl tree specifically.
When you are doing recon interactively you send a range you are interested in and the hash of what you have.
(start_key, h(events_you_have), stop_key)
They can now compare the hash. If it is the same you are in sync, else they can send back a split range.
(start_key, h(events_they_have), middle_key, h(events_they_have), stop_key)
They can choose the middle_key they want to split on recon doesn’t care. They could split on the middle key like a binary search, bias to more recent keys that have a higher probability of being out of sync, or pick keys that allows the server to pre-compute the hashes.
By using a tree, we can do all the hashing ahead of time.
(start_key, (h(events_you_have), CID_of_subtree), stop_key)
Now the blocks can be stored in any dumb data store. The client could pull the root. Compare the client’s local hashes to the stored tree. Where the hashes match skip the sub-tree else follow the sub tree. This has turned recon from an interactive protocol to sync against a static data store.
The shape of the tree doesn’t really matter, it could be a b-tree, MST, prolyl tree, …
The more balanced the tree the faster the sync but we are probably better off sacrificing some of the balance to get better structural sharing if these trees are going to live a long time. e.g. Monthly snapshots.
This would let a node that is coming on line after a long time sync up to the most recent snapshots in some object store before interactively bothering the nodes doing live traffic.
Two answers here.
If you ask for a stream with an EventID then it has the NetworkID and separator in it. The ceramic node can respond with the events if it has an interest in that range. Otherwise, it can respond with an error that the stream is outside of its intrest ranges. The client then can decide if they want the node to add that separator, or specific stream to the interests. Adding the stream to the intrests will mean that it gets synced with recon. Once it is synced it can be sent to the requester.
For supporting this specific API where the only thing sent is the StreamID containing the CID of the Init Event. The node will need to look up the Init Event from IPFS to determine if it is in its interest ranges. Then produce the error if that stream is not in an intrest range for that node.
The shift from nodes that do WAN traffic at query time to ahead of time synchronization means that the node should have all the events to respond quickly to any request for a stream. As long as the stream is in the intrest ranges. This should drastically reduse the latency and timeout frequency for streams in the intrest ranges but will lead to some request responding with error not in intrest range and options for what you might want to subscribe to so that this stream will sync.
Seems related to CIP-137 CIP: Ceramic API by oed · Pull Request #137 · ceramicnetwork/CIPs · GitHub
Do I need to know which node is indexing the stream I am interested in? Like if I query an unindexed stream, it will just return 404? I mean ideally it should still return but just takes longer time (behave kinda like IPFS).
The main cost to the prevTimestamp is that to do the calculation we need all the blocks in the prev path from the event in question to the preceding time event. Without it we need just the init event and the event in question.
The value of (prevTimestamp, eventHeight) is that it keeps the novelty together. For small streams this probably doesn’t matter much but for a stream with thousands or millions of events we don’t really want ten new events in the stream to be sorted randomly with all the other events. Sorting the events within a stream by the CID of the event would do just that.
If we just did event height then we would need the prev path from the event in question to the last event that we have a EventID for with its own validated height. This seams expensive as we may need to pull an arbitrary number of blocks to validate a height but those blocks need to be synced anyway as we are interested in the stream. We also probably want to validate that a new event for a stream does in fact prev path back to the init event. To validate that we don’t need to follow all the way back to the init event just back to an event that we know we already validated and that is exactly the event height algorithm.
If we also want to validate all time events, we need to talk to an ETH node to know the ETH time of the block with the anchor in it. Including (prevTimestamp, eventHeight) in the EventID means that we force a node to validate both the chain back to the init event and the anchoring of the previous time event before generating the EventID and gossiping it around the network.
Not clear wether this is a good or a bad thing.
I don’t know what the ideal is here. With CIP137 we will probably want to make some kind of distinction between a point query and a subscription. If the client just asks for the latest value of a stream that the ceramic node is not syncing maybe the best answer is just that I am not syncing that stream.
The client could make a subscription call instead and tell the node to add that stream to its interest vector. Then as it calls around to sync it will pick up the events and forward them along to the interested client. I would like to know more about the use case here. For the most part the pattern I expect is that applications will have a known set of models that they use. A subscription to those events is being aggregated into latest states. Those states are being parsed and indexed. Then the app queries those local indexes.
In such a setup the subscriptions are the dominant way the data is consumed and we are unlikely to see queries for streams that are not part of some subscription. For systems that are handed a StreamID that is not in one of their interests I don’t know how often the client really wants to retrieve the stream vs just needs to know that it is a useless pointer as it does not know what to do with an instance of that model anyway.
@AaronDGoldman Do you think 4 bytes could be enough for the init-event-cid we don’t really have a risk of malicious attacks here.
Might not be completely map to our use case, but looking at solidity function signatures as they only use 4 bytes of the hash of the fn sig.