Thread sync with gossip-about-gossip and Cordial Dissemination

[andrewzhurov]

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 as gaps.

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!

[dhh1128]

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!

[andrewzhurov]

@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. Perhaps both projects could benefit if we were to take inspiration from the latest DAG-based blockchain techniques. As KERI is a micro-ledger and all we need to maintain one is a DAG of communication of its members (given a MultiSig/group AID), where DIDComm communication can naturally build such a DAG with Threads.

The approach is darn simple, yet I found it a fair bit mindbending. Here's how it looks. Nevermind the details, the juxt is people chatter - chatter gets totally ordered. Merkle-DAG is simple, Byzantine Agreement as a function of a message is more involved, but eh it's a pure function that fits on one page, how hard can it be?).

We could imagine that Alice maintains her Personal AID, where "members" of this communication would be her devices. Interestingly, there is no need for re-design on the KERI side, members could simply sign the last block of a newly appended blockchain they got derived as result of their chatter. Moreover, DIDComm would only care about building a chatter DAG and a consenus algo is an optional plug-in atop. To name a few options, Hashgraph, PARSEC, Cordial Miners (requires a specific flavor of DAG, but seems can be adapted to work on an arbitrary DAG).

But here I got excited a bit, we'll get to it later, first let's see what a Blocklace is and

Benefits for DIDComm

What I like about Threads atop DIDComm is how they are meant to be a communication context. Having it as Blocklace (a Merkle-DAG of how processes talked) seems to give it even more powers. Let's call it Merkle-Threads for now.

Hash is the ID

A message can be uniquely identified by its hash.

Increased BFT

Relying on users to provide unique message IDs is not BFT. A malicious fella can create two messages with the same id and different payload. A Byzantine wannabe.

Linking by a non-content-based name is not safe. Kleppmann proposes to use hashes as message ids - sweet, better BFT and smaller message size due to no @id field (which can be derived out of message if needed).

Hash URI / Generic addressing

Messages addressable by hashes makes linking possible in a generic way with a Hash URI. E.g., to ref to the this question-answer message

{
  "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

hash://sha256/bafy...AliceMessage1

Generic path addressing

If 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. E.g., to ref to the first value of valid_responses from the message above one could craft such a Hash URI

hash://sha256/bafy...AliceMessage1#/body/valid_responses/0

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 DAG

Just ref from a message to parents (tips/heads) - that alone will build a Merkle-DAG, baking causality into a message.

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 to field in its hash. The way it's done in DAG-based blockchains and well, everywhere. Prone to surreptitious forwarding and receival, but in a group context where it's meant for everybody - who cares? Intended audience is known from parents.

Alternatively, Alice could include all group participants in to, thus making it normalized, but it would not play well with gossip we are about to embrace here and dynamic membership.

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 communication

I'm running ahead of myself here, so this will get complicated quickly. And this section is optional anyways, so feel free to skip and mayb read up later. For those curious.

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? The fairness of a consensus algo. :smile: And well, you.

How would that work? DAG-based consensus algos work along the lines "whatever event is observed by majority first is first". Given you gossip-about-gossip, cordially disseminating stuff you know that others do not, you would want them to "receive" the whole bit you shared, and not cherry-pick some event that they want to, would you?

And why is it possible? This is possible due to nodes of a DAG being messages without the to field.

This opens a possibility for mischief. E.g., Alice, Bob and Charlie talk. Alice sends message to Bob, Bob sends message to Charlie (cordially including message from Alice), but Charlie "receives" the Alice's message, and drops Charlie's. I.e., if we model it as a DAG, message's signature provides authenticity of a node (message), but not an incoming edge (one from a node that refs to it). Whereas an addressed message's signature provide authenticity of a node & incoming edge.

And DIDComm already thought of addressed messages!

But wait, how would we have DAG normalized? Do not include "to" field in message's hash (ID). Now whoop, parents build a normalized structure.

And how to prove authenticity? I mean given signature would be on an addressed message (with to field), right? Indeed, just keep addressed messages' signatures around. Show them to whoever cares.

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. This may incur more addressed signatures to keep around vs would be were we sign messages without to, and not every use-case may care. Thus could be made optional. For those uses like auction that could care plenty about the fairness of consensus, were they to run a distributed system. Probably an overkill though. Even Blockchains don't care, should we? Well, tool's in our toolbox, let's nevermind and move on.

Virtual self-parent chain

Messages of a member form a virtual self-parent chain - are totally ordered. A kind of implicit BFT version of sender_order.

Thus making it possible to have:

Duplicity detection

Dissapointing 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. In a social context - social measures may do.

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. Well, it would suffice were one to learn those two messages. But that would get complicated. Basically we'd try to re-construct virtual self-parent chain from lack of it explicitly. And use idx as a tool. Whereas if it's explicit - no problem in the first place. Moreover, idx can be derived out of it, in case we care for some reason.

Implicit ack/nak

When Alice sends message to Bob - Bob learns what Alice knows, all gossip she heard is in her causal history (parents). A kind of implicit BFT version of received_orders. Or, in other words, node of a Merkle-DAG can be seen as a Merkle-Clock. A kind of Vector Clock, except secure. But hey, that message she sent includes just hashes of parents, what if he doesn't know some (has "gaps")? Well spotted, enter

Cordial Dissemination

The reason why surreptitious receival is possible. Not a good start, eh? But it has some advantages to offer.

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". A kind of gossip married with causal delivery.

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"). Could be catered by employing tit-for-tat strategy though. I.e., do not send any more messages before hearing back. System could deadlock though, given messages may not get delivered.

Alternatively, a more loosely strategy is to not send messages before learning that Bob knows stuff you sent him. E.g., you also shared it with Carol, and they talked with Bob, and then Carol talked to you - you know Bob learned your stuff. Safe to send more.

But well, its optimization strategies, let's not get bogged in.

Less signatures, same authenticity

As 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. Akin how a signature of a KERI's KEL event is enough to prove authenticity of the whole KEL below. That may be some storage saved and plenty bandwidth saved when a new member joins a group (and wants all those messages).

Given you want to have authentic nodes - this will do. Given you want to have authentic nodes & edges - more signatures (of addressed messages) to keep around.

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' tape

The downside of a Blocklace is an increased overhead from having to include hashes of parents (well, it can be just one per event, but that's the best case) and signatures (one per event). Signature overhead been covered above, could we compact the hashes somehow? Oh yes we could plenty.

Over-the-wire compaction of a cordially sent sub-DAG

A bit stale description. This compaction uses Hashgraph's flavor of Blocklace. Nodes are signed messages. Nevermind the signatures on each message at rest, could be also pruned, as well as redundant self-parent refs, the interesting bit is hashes compaction.

This data model, with a slight addition, could be employed to represent data at rest as well. The slight addition is parents, as indexes. This would make lookup damm fast. As well it'll make possible to represent equivocations. (we could have parents idxs over-the-wire for this purpose as well)

Additionally, makes possible to use

co-structures

for efficient lookup of anything related to an event. Co-structure is a sparse array, where idx is an "id" of our makeshift entity. We can go as far as having a co-structure per "attribute", may it be an overkill.

Use-cases are many. For one, we could create a reversed version of a DAG. Or a logical (reply) DAG.

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 / Usage

What 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. Whereas were we implement it without, where each node tries to add the next block directly to blockchain (KERL), some problems arise:

1. Not conflict-free - members fight for who gets the next block accreted. Resembles Bitcoin in that there are competing "forks" that race to be authorized, inevitably some of them get chopped - those events need to be re-issued atop. Not a prob if it's 1 event / day, (except that you'd still need to have logic to recover from colission, e.g., re-issue the chopped event) but higher the rate - higher the collision chance.
2. Requires members to be online connected. Of course one could create a bunch of events locally, being offline, and sync with the rest later, but chances are they'll get chopped.
3. How to collect signatures? Sam Smith mentioned these approaches: Option 1: A (designated) controller would need to collect all the signatures and propagate to witnesses. Option 2: Witnesses collect signatures, serving as an escrow. Both options raise concerns. We could solve all of these by leveraging Blocklace + a consensus algo to build a KERL blockchain, where members are key holders and (optionally) witnesses. Witnesses is yet another set of key for your KEL, after all. As additional benefit, witnesses could help key holder disseminate their events, making it easier to have a connected graph. (high availability is one of their purposes, why not use it to help Controller? his devices may not have static IPs (say phones), knowing how to reach each other)

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. Eventually we get events totally ordered in a blockchain, last event can be signed by controller's devices and witnesses.

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. event_id is event's hash. And it may have prev_events that are "forwards extremities" / heads / tips / parents, whatever we call them.

Hashgraph, PARSEC and Cordial Miners are total-order algos as a function over a message. (DAG-based consensus protocols are all the rage). Dr. Leemon Baird built whole Hedera atop his Hashgraph algo. (Hedera provides global ledger, whereas we could be intrested in an ad-hoc micro-ledgers, a p2p bottoms-up (grassroots) story) source

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 Blocklace

One missing bit is how exactly do they talk?. And that's where DIDComm seems to fit right in. It seems to be a vital communication layer, that could be used to construct Merkle-Threads, unlocking all those powerful use-cases.

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 Model

Well, 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! :sweat_smile:

Concerns

1. When cordially sending large sub-DAGs a message may get big. May harm privacy as it could be traced through mediators. Solution: send smaller batches? Buffer on receival end, receive whole. I guess that would be a generic pattern, perhaps suitable for a separate protocol. E.g., also usable when sending out poem-like messages.

2. Cordial Dissemination works on a stale knowledge of what others know. Thus, same events may be sent cordially to a member. Well, can't escape that, your knowledge will always be stale. Even when you talk with just one fella - messages you sent may not got delivered. Even when you just received a message - sender may have learned something new already. Sender could be the one asking to fill his gaps when he receives an event, before accepting it, keeping it in a buffer for the time being. He could disclose what he knows with Bloom filters, or ask specific events by hashes. This route is open for consideration. In Matrix gaps are possible, we can take a look at their art of gap-filling.

Replies as a tree

Limiting reply to just 1 message is common. It allows to further detail reasoning. Yet I find it too restrictive, as it does not allow to synthesise knowledge, which require to refer to multiple things at once, the Zettlekasten way. Protocols may benefit from it as well. E.g., referring from "booking complete" event to both "booking requested" event and "payment successfull" event.

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. Perhaps we could use a better name for a causal Merkle-DAG that I've been calling Merkle-Threads so far, to avoid colission with social "threads" feature.

(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. Specifies variety of pointers, including text ranges, within a referenced resource (our Hash URI). Bread and butter of Hypothes.is, damm handy for taking notes on the Web. One of the fields in WebAnnotations is motivation, which could be used to express comment and whatnot. Making it p2p-friendly and beefing it up to be ala Notion curiosed me for a while. But I digress.

These granular pointers can be used to both select stuff you refer to and select stuff that refers. Akin to links. Except no need to bake links into the text, they are annotations atop.

May it be useful for protocols?

Interlinking Merkle-Threads

Merkle-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. When a reply that references messages in different Merkle-Threads is created (by a member who has access to both Threads), it would includes parents from both Threads. (parents and reply refs are different) Thus making it possible to have two contexts interact. What I like about it is how Threads are independent yet interoperable once interconnected by a common member - the grassroots style.

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. Same technique for Merkle-Threads, anchor your events to one and only "KEL". Resembles idea of having Matrix's Room as Profile. Your AID where all interactions go. A kind of Twitter feed. Except Merkle-Threads in it are not necessarily public.)

Matrix uses one Merkle-DAG per Room (which is an unfortunate name) with (logical) threads in it. Room = Merkle-Thread.

All in all, (logical) thid may just do.

Encryption

Thread Key / Group Key

TLDR; 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:

1. Less privacy. Members of a thread become detectable, as the same encrypted payload travels to them all.
2. Need to rotate Thread Key, givem membership is dynamic.
3. Need for members to support the same group profile (serialization, encryption).

As well as pros:

1. Makes possible to rely on a third-party broker/mirror for availability of content, usable if we have a need to fill gaps. E.g., pin encrypted content by hash on IPFS. The way TheardDB does. E.g., Matrix's Home Servers.
2. Fancy name - a normalized authentic encrypted Merkle-DAG. It doesn't get shorter, eh? :grin:

As well as having

Dark Forest / Hierarchical Encryption

Parent 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. Allows for members of a parent thread to read child threads, but not vice-versa.

(optionally) causal DAG unencrypted

The way Matrix does. Helpful when heavily relying on servers/brokers to do dissemination - relying on third-party that is not authorized to see the content to disseminate it. Does harm privacy.

(optionally) replies (logical) DAG unencrypted

More down the road of the trade-off above. Brokers can serve users even better with the cost of even less privacy.

E2E

We 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. This side-steps the cons of Thread Key - no need to rotate, simple.

E2E Session Key

It's been recently discussed on a DIDComm call to add session support. Session is Thread-agnostic, two peers could talk about whatever using the same Session Key. My personal favorite.

Additionally, sessions could be used to agree upon data serialization format.

Related resources

Sam Curren showed prior art on this call. Referred docs: ThreadSync Protocol ThreadParticipant protocol BasicMessage Replacement Protocol GOSSYP (uses special data model, BasicMessage Replacement Protocol is favored over as more idiomatic, good read though, gossip ideas are interesting, kudos for crafting)

https://spec.matrix.org/proposals/ Matrix uses client-server model, where events are crafted on a Home Server. There's an effort in making it p2p. Event id as hash (accepted proposal, in use since Room v3) User as pub key (proposal) Typed rooms (proposal) - indicate use-cases other than messaging (profile, blog), akin to DIDComm's @type, were these messages form a Merkle-DAG. Spaces (accepted proposal) - a room of rooms. Akin to channels in Discord/Slack. Room as Profile - begs to be a KERI's MultiSig AID. (Could we make use of Matrix Event Graph?)

MLS - participants management, group encryption

https://github.com/decentralized-identity/didcomm.org/pull/108

Textile's Threads Peers as mediators, which we'd naturally have via Cordial Dissemination.

Closing note

Well, that got lengthy. :sweat_smile: Hope it's been a good read. Keen to hear your thoughts on it, folks. I bet there's plenty to think-through and re-shape, any input is welcome.

I love how DIDComm and KERI reimagine communication and identity. They aim to have a p2p grassroots world no one needs, except the 8b of people (may they not realize it yet). Appreciation for all the effort put in. :muscle:

CCing those I think may find it of interest: @nickreynolds @TelegramSam No pressure to reply, plenty to brew on. Poke with questions.