jbenet
commented
8 years ago Very nice post!
Good summary of many discussions.
Some nits here.
- Your tags diagram shows a "topic path", a hierarchy of topics. when we discussed, we agreed to treat "tags" as different values, such as
/a, /b/, /c, /d, and "paths" as a hierarchy of topics (not necessarily tags) (/earth/portugal/lisbon). - Your "coselectors" are just paths. just call that a path. IIRC "coselector" as described by mikola/nicola was meant to be something different, an expression (dual to an IPLD Selector) that can express a filter that defines what events to listen to (similar to a subscription).
- Note: an IPLD Selector includes a path, but the point is to be much more than a path. specifically, it is supposed to select an authenticated subgraph from a given authenticated dag root. This can be a path, but it's most useful to discuss in terms of non-chain subgraphs.
- I think there are several superflous abstractions here, that define pieces that don't need to be defined (i.e. are not actually different).
- For example, I disagree that "Self-certified streams" means anything special, i think you just mean "certified streams" (which just means signed streams) using a "self-certified name" (the link to the value which happens to be a stream). You can call that a "self-certified stream", but i think "authenticated stream" covers it much nicer.
- Self-certified means "self-signed", meaning something similar to "self-signed certificates". It's useful in "Self-certified names" because we give the user authenticated data for a given name -- the "specialness" comes from leveraging given trust in the name to also mean trust in the value. I dont think "Self-certified streams" is a useful abstraction beyond just saying they're "authenticated streams", some of which are signed, and some of with are just hash-linked.
- "Self Certified Links (SCL)" this is not different at all from a Self Certified Name. It's not useful to call it Self Certified Link. It's superfluous. (my reaction: "now you're just trolling")
- Your "Authenticated vs Certified" section is incorrect. "Authenticated" has a formal definition, which includes hashing AND digital signatures. So "authenticated data structure" covers the signed ones too.
- I'm not sure what the formal definition of "Certified" is, but i also have been using it to just mean signed (i.e."certificates" are signed attestations). It may be broader, not sure.
- And we do want to be able to create chains that every node can publish to. that's okay, it is useful.
Authenticated I would put it like this, but i'm sure there are more succinct and correct definitions: A value is said to be authenticated when one can reliably prove it is the intended value (authentic). It is usually used in relation to values or messages created by a sender; the values are authenticated if we can reliably prove whether a value was originally constructed by the sender, or it is a different or modified value, not created by the sender.
- This can be done with hashes (eg the sender can send a message m in an insecure channel, then give us the hash in a secure side channel. We can then prove whether a given byte sequence is really m).
- Or it can be done with digital signatures (the sender digitally signs m, producing sm, then sends sm. Assuming we have sender's signing key, we can reliably prove sm is authentic).
- Or it can be done with proofs. (eg sender agrees to send the sequence of all prime numbers. we can reliably prove -- though expensively -- that the sequence received is the sequence of all primes.)
daviddias
A Self Certified Stream (SCS) is an authenticated and certified data structure uses Self Certified Links (SCL) to create an chain of of blocks.
Another type of a Self Certified Link is IPNS (also known as Self Certified Names), described by the IPRS spec.
In contrast with IPLD and its Selector, SCS use coSelectors to query the IPFS network to find what are the next blocks in the chain.
While selectors offer a way to do recursion(traversal) of any IPLD graph, coSelectors are form to show interest blocks that will follow (i.e append-only logs, blockchains)
This way, we get a coBitswap, that instead of sending a wantlist for specific blocks, sends a list for interest of blocks that point to the ones in the list. (coBitswap is a way to describe it, in the end, might all just be part of bitswap)
Participants Discovery (Peer Discovery)
To find the peers participating in the feed, namely: publishers and subscribers; we can use:
There isn’t quite a one perfect size solution, most probably the best is using something hybrid or letting the application developer select what makes more sense for their app requirements. libp2p already supports multiple discovery mechanisms for Peer Discovery to live at the same time.
Subscription Models
There are 4 categories of subscription models in the pubsub literature, these are:
We can achieve Type based subscriptions, the most requested ones, with CoSelectors, where a CoSelector can represent a whole chain of events that follow the same tag:
Reliability
One of the cruxes to achieve scalable pubsub, is the rule in how Acknowledgements are performed. With Self Certified Streams, the receiver can infer if it has received all the packets in one chain by validating its ancestry, requesting again only the ones it missed. In some sense, it is the strategy of NACK, but where the packets hashes are the NACK and these are authenticated, giving the received the possibility to ask for any peer in the network for the missing packets.
Tree forming
Getting a sound algorithm for tree forming, would give IPFS Self Certified Streams a way to scale up without increasing insanely the network traffic generated. Our plan is to make the API solid first and then involve the networking and treeforming bits of the implementation, so that prototypes that need PubSub today can start testing it.
Other notes
Authenticated vs Certified
An authenticated data structure is something like an hash chain (merkledag). For pubsub, we need our data structure to be Certified (Cryptographically signed), otherwise it would be very easy to spam the network with unwanted events, since every node could publish to that stream.
——
Previous pubsub discussions