-
Notifications
You must be signed in to change notification settings - Fork 59
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Thread sync with gossip-about-gossip and Cordial Dissemination #456
Comments
It's an intriguing idea. I don't think we want to make DIDComm dependent on something that requires support from a particular type of blockchain, but making it capable of benefitting from such a technique seems really promising to me. I'll be interested to see where you go with the idea! |
@dhh1128, definitely. Pardon for a late reply. I went to learn about KERI more and given it more thought. I see how there's an effort in making KERI and DIDComm more interoperable (by drawing boundaries and benefiting from each other), I believe that's a good cause. The approach is darn simple, yet I found it a fair bit mindbending. Here's how it looks. We could imagine that Alice maintains her Personal AID, where "members" of this communication would be her devices. But here I got excited a bit, we'll get to it later, first let's see what a Blocklace is and Benefits for DIDCommWhat I like about Threads atop DIDComm is how they are meant to be a communication context. Hash is the IDA message can be uniquely identified by its hash. Increased BFTRelying on users to provide unique message IDs is not BFT. Linking by a non-content-based name is not safe. Hash URI / Generic addressingMessages addressable by hashes makes linking possible in a generic way with a Hash URI. {
"type": "https://didcomm.org/questionanswer/1.0/question",
// "id": "bafy...AliceMessage1", // this field is a derived hash of this JSON doc
"body": {
"question_text": "Alice, are you on the phone with Bob from Faber Bank right now?",
"question_detail": "This is optional fine-print giving context to the question and its various answers.",
"nonce": "<valid_nonce>",
"signature_required": true,
"valid_responses" : [
{"text": "Yes, it's me"},
{"text": "No, that's not me!"}
],
"expires_time": 1544722146
}
} one could use such Hash URI
Generic path addressingIf we'd like to link to a specific bit, we could capture JSON path as a URI's fragment, according to the JSON Pointer spec, as regarded here.
No need for heavy-lifting querying to get the value later on, just message.body.valid_responses[0] Which could be done, for example, with a help of object-path lib objectPath.get(message, ["body", "valid_responses", "0"])
// => {"text": "Yes, it's me"} Hash DAGJust ref from a message to Besides, that's what makes a message uniquely addressable by its hash (otherwise message with the same content (and no refs) used in a different context would have the same hash). However, in order to build a normalized DAG, where hash of a message Alice sent to Bob and (possibly later) to Carol are the same, we could not have Alternatively, Alice could include all group participants in And since we have messages signed - we have a normalized authentic Merkle-DAG, mouthful but cool, horrah! What's that surreptitious _receival_ you mention?
(optional) Authenticity of communicationI'm running ahead of myself here, so this will get complicated quickly. One Byzantine behaviour that is overlooked (to my knowledge) by works on Blocklace-like systems is "receiving" a message that wasn't sent to you. .. who cares? How would that work? And why is it possible? This opens a possibility for mischief. And DIDComm already thought of addressed messages! But wait, how would we have DAG normalized? And how to prove authenticity? I mean given signature would be on an addressed message (with In case of an ad-hoc ledger - members of that ledger. The outside folks don't care about how we talk, they care about the totally ordered event log we get as a result. A set of threshold signatures on the last event of this chain is enough for them. So addressed messages go rule! Giving even more BFT than state-of-the-art. Virtual self-parent chainMessages of a member form a virtual self-parent chain - are totally ordered. A kind of implicit BFT version of Thus making it possible to have: Duplicity detectionDissapointing those inspired by mischief of Byzantine generals that want to send different messages to others, as it's detectable. It's up to users to decide how they want to respond to this mischief. Is virtual self-parent chain really neded for that?
Won't giving an idx to a message be enough? Then we'll see that two messages with the same idx is mischief. Implicit ack/nakWhen Alice sends message to Bob - Bob learns what Alice knows, all gossip she heard is in her causal history ( Cordial DisseminationThe reason why surreptitious receival is possible. Not a good start, eh? Cordial Dissemination is sending to others messages that you know they need and, to the best of your knowledge, they don't yet have. This ensures that there won't be "gaps". It's possible due to agent's knowledge of what others know (event is an implicit ack/nak), that gets updated every time you receives a message. (you learn not only about what the sender knows, but also those who talked to him, it's gossip about gossip, after all) When Alice sends message to Bob she cordially includes all messages she knows he may not yet have - Bob learns what Alice knows, and will do the same cordially with his next message to her. A BFT way of dissemination. Cool. (optionally) optimistic update
Alice's knowledge of what Bob knows can be optimistically updated when she sends a message to him. (But it may not get delivered, hence "optimistic", prone to "gaps", (e.g., if Alice would sebsequently sent a sub-DAG/patch, expecting that Bob did recieve the previous one - Bob would have "gaps"). Alternatively, a more loosely strategy is to not send messages before learning that Bob knows stuff you sent him. But well, its optimization strategies, let's not get bogged in. Less signatures, same authenticityAs message of a member transitively links to all previous messages he created (forms a virtual self-parent chain), its signature alone is enough to prove authenticity of them all. Given you want to have authentic nodes - this will do. Is a trade-off though (what's not?:), if one wants to forward a message, in order to prove its authenticity one would need to provide closest higher-up signature of a member, alongside a sub-DAG that links to it. Related: Matrix forwarding proposal. Compact it down to a friggin' tapeThe downside of a Blocklace is an increased overhead from having to include hashes of Over-the-wire compaction of a cordially sent sub-DAG
A bit stale description. This data model, with a slight addition, could be employed to represent data at rest as well. Additionally, makes possible to use co-structuresfor efficient lookup of anything related to an event. Use-cases are many. If events are transactions (say in SPARQL), then one co-structure could be used to capture deltas, another for an occasional snapshots. Makes incremental compute and time-travel easy to implement. If we have consensus algo, then a co-structure with points of consensus can be used ("this event resulted in this blockchain"). Sky's the limmit. Kinda. Also RAM. Generic / UsageWhat I like about Blocklace is how generic it is - history of communication about whatever. KERI's IPEX is a kind of ad-hoc Blocklace. KERI's MultiSig/group AID's KEL can be build with help of a consensus algo atop a Blocklace. The way teased at the beginning.
E.g., Alice wants to manage her Personal MultiSig AID with her devices (smartphone, tablet, laptop), additionally she provided a set of witnesses. We can imagine how in viz above those devices could talk to rotate keys, add interaction events, anchor TEL events, etc - manage her identity and add authenticity to actions she does, and witnesses simply issue empty events, aiding dissemination. OrbitDB (js lib) is a CRDT, based on ipfs-log that is a Merkle-CRDT. Matrix uses Matrix Event Graph (MEG) that is a Merkle-DAG. Hashgraph, PARSEC and Cordial Miners are total-order algos as a function over a message. (DAG-based consensus protocols are all the rage). E. Shapiro defines Grassroots Cryptocurrencies, Social Networking (with WhatsApp-like and Twitter-like example protocols) and a whole Grassroots Architecture for the Digital Realm atop Blocklace. Indeed, Blocklace can be seen as a universal pure OP-CRDT, with optional total-order atop. Two missing bits of BlocklaceOne missing bit is how exactly do they talk?. And that's where DIDComm seems to fit right in. The second missing bit is who are talking? And here KERI could come into play. The bit I'm puzzled with is how to merry did:keri with "how to communicate with me" that did:peer provides. And whether full-blow KERI is needed? Sam says all KERI-light protocols that drop some parts of KERI have security drawbacks, these features are there for a reason. So I guess an approach is to build atop did:keri, enhancing it with discoverability of did:peer / make it suitable for DIDComm communication some way. Oh well, I guess it's plenty said for AID use-case, let's see how these goodies can be modeled as a DIDComm message and how to use it for social stuff. DIDComm Merkle-Threads Data ModelWell, you folks would be the ones best to model, but here's my speculation for a non-compacted case, in DIDComm v1 data model: ;; Alice created a group message (with Alice, Bob and Charlie as participants).
;; Say her software sends it to Bob.
{
"@type": "did:example:123456789abcdefghi#didcomm-1",
"@id": "bafy...AliceMessage1", ;; a hash (SAID) of this message, excluded fields: "cordial".
"from": "did:peer:Alice",
"body": {"message": "Heyo, guys! Up to grab a coffee?"},
"~merkle_thread": {
"members": ["did:peer:Alice", "did:peer:Bob", "did:peer:Charlie"], ;; or repurpose "to" instead?
}
}
;; Bob received, created a reply.
;; Say his software sends it to Charlie.
;; To the best of Bob's knowledge Charlie does not know Alice's message,
;; so it's included alongside, cordially.
{
"@type": "did:example:123456789abcdefghi#didcomm-1",
"@id": "bafy...BobMessage1",
"from": "did:peer:Bob",
"body": {"message": "Yo, I'm on."},
"~merkle_thread": {
"parents": ["bafy...AliceMessage1"],
"cordial": [<AliceMessage1>],
;; "thid": "bafy...AliceMessage1",
;; no need to include "thid", as it's implicit, root event can be traced through "parents"
}
}
;; Charlie received and replied.
;; Say his software sends it to Alice.
;; Bob's message is attached cordially.
{
"@type": "did:example:123456789abcdefghi#didcomm-1",
"@id": "bafy...CharlieMessage1",
"from": "did:peer:Charlie",
"body": {"message": "Hey! Where at?"},
"~merkle_thread": {
"parents": ["bafy...BobMessage1"],
"cordial": [<BobMessage1>],
}
}
;; Alice received and say started a parent thread to pick a good cafe nearby
;; Her software sends it to Bob
{
"@type": "did:example:123456789abcdefghi#didcomm-1",
"@id": "bafy...AliceMessage2",
"from": "did:peer:Charlie",
"body": {"message": "New on the block, what's a good place?"},
"~merkle_thread": {
"parents": ["bafy...CharlieMessage1"],
"cordial": [<CharlieMessage1>],
"thid": ["bafy...CharlieMessage1"], ;; new Thread branched off from Charlie's message
}
} Well, that's been a lot of talk to introduce three fields! 😅 Concerns
Replies as a treeLimiting reply to just 1 message is common. Thus, we could allow multiple replies from a message, building Replies as a DAG;; insert xzibitt joke Is different from causal Merkle-DAG we have. (optionally) with fine-grained pointers
We could allow even more fine-grained pointers (say to a specific part of a message user wants to annotate), as recently introduced in Telegram, and possible in Matrix with Rich Replies. Perhaps this could be done with help of Web Annotations. These granular pointers can be used to both select stuff you refer to and select stuff that refers. Akin to links. May it be useful for protocols? Interlinking Merkle-ThreadsMerkle-Thread is a communication context within which members cooperate and cordially disseminate to each other. It can be communication within a protocol, e.g., booking. When a parent coprotocol launches it may have a different set of members. E.g., payment may be a coprotocol between payer and his payment provider. Thus creating a different context. When co-protocol finishes its "finish" event (e.g., "payment succussful") can be referred to from its parent Merkle-Thread. A reply may reference messages in different Merkle-Threads. We would lose the virtual chain trait here if we to allow the same fella to create messages in different context without referring to its previous one. (To avoid it, we could take inspiration from KERI's ACDC, how they are separate interaction yet can be anchored to AID's KEL. Matrix uses one Merkle-DAG per Room (which is an unfortunate name) with (logical) threads in it. Room = Merkle-Thread. All in all, (logical) EncryptionThread Key / Group KeyTLDR; Not ideal, feel free to skip to E2EE. All events within a Merkle-Thread could be signed with the same symmetric key. It does have its cons:
As well as pros:
As well as having Dark Forest / Hierarchical EncryptionParent Thread could have its own Thread Key. If we fancy, we could encrypt parent Theard Key with child's Thread Key, building a Dark Forest. (optionally) causal DAG unencryptedThe way Matrix does. (optionally) replies (logical) DAG unencryptedMore down the road of the trade-off above. E2EWe can take a step in the opposite direction, valuable for those privacy-vital use-cases, and forego using Thread Key encryption, making use of E2E encryption. E2E Session KeyIt's been recently discussed on a DIDComm call to add session support. Additionally, sessions could be used to agree upon data serialization format. Related resourcesSam Curren showed prior art on this call. https://spec.matrix.org/proposals/ MLS - participants management, group encryption decentralized-identity/didcomm.org#108 Textile's Threads Closing noteWell, that got lengthy. 😅 Hope it's been a good read. I love how DIDComm and KERI reimagine communication and identity. CCing those I think may find it of interest: @nickreynolds @TelegramSam |
Spec defines Threads, a kind of context of communication, within which members exchange messages, where each member maintains a self-parent chain of his messages (meaning messages of a member form a chain / sequence).
Spec further specifies Advanced Sequencing as a protocol of how members can sync what they know with others.
In it, a member maintains a self-parent chain by assigning to his messages an index of a self-parent chain.
Then he can construct
received_orders
message as a kind of Version Vector. But since causal broadcast is not assumed, some self-parent messages of the stated known tips may be missing. This can be expressed by listing them asgaps
.Previously the approach of syncing peers "off-chain" at network layer via Reliable/Atomic/Causal Broadcasts received a lot of attention.
However, it suffers from message complexity.
Recent works recognize the value of having network layer abstracted away, captured as a DAG of communication. I.e., let processes not simply gossip, but gossip about gossip.
I first seen this idea in Hashgraph and then in more recent Cordial Miners.
They are consensus algorithms that give total order as a pure function of message, total_order(message), but that's beside interest here.
What's interesting is how easy it becomes for members to sync with each other when they know what others knew. So they can send the missing messages. (Cordial Dissemination)
I am curious whether this technique of having a Hashgraph/Blocklace data model of messages may be advantageous for DIDComm's Threads.
@dhh1128
P.s., thanks for the effort put in DIDComm, fascinating tech!
The text was updated successfully, but these errors were encountered: