Conclusions

For example, in WOOT [ 33]and YATA [ 32 ], an insertion operation must referencethe IDs of the predecessor and successor elements, andthe algorithms depend on the predecessor appearingbefore the successor in the sequence. The order ofthese elements is not apparent from the IDs alone, sothe algorithm must inspect the CRDT state to checkthat the predecessor and successor references are valid

but Byzantine nodes maynot set this metadata correctly

The 3f + 1 assumption meansthese protocols cannot be deployed in open peer-to-peersystems, since they would be vulnerable to Sybil attacks [ 15].

blockchains [ 5 ]

If authentication of updates is desired, i.e. if it is importantto know which node generated which update, then updatescan additionally be cryptographically signed. However, thisis not necessary for achieving Strong Eventual Consistency

When updates are generatedconcurrently and then merged, the next update containsmultiple predecessors

Consequently, if updateu2 depends on update u1, it could happen that somenodes deliver u1 before u2 and hence process bothupdates correctly, but other nodes may try to deliveru2 and fail because they have not yet delivered u1. Thissituation also leads to divergence.

Say a Byzantine node generates twodifferent updates u1 and u2 that create two differentitems with the same ID. If a node has already deliveredu1 and then subsequently delivers u2, the update u2will be rejected, but a node that has not previously de-livered u1 may accept u2. Since one node accepted u2and the other rejected it, those nodes fail to converge,even if we have eventual delivery

Unfortunately, version vectors are not safe in the presenceof Byzantine nodes, as shown in Figure 1. This is because aByzantine node may generate several distinct updates withthe same sequence number, and send them to different nodes(this failure mode is known as equivocation). Subsequently,when correct nodes p and q exchange version vectors, theymay believe that they have delivered the same set of updatesbecause their version vectors are identical, even though theyhave in fact delivered different updates.

This algorithm has the downside thatmany updates may be sent to nodes that have already re-ceived them from another node, wasting network bandwidth

In some cases, a causal de-livery algorithm additionally ensures that when one updatehas a dependency on an earlier update, the earlier update isdelivered before the later update on all replicas

The network is not necessarily com-plete, i.e. it is not required for every node to be able to com-municate with every other node

they must either exer-cise centralised control over which nodes are allowed to jointhe network

Virtual chain axiom

This, in turn, requires either having knowledge of thecurrent replica-set or using an external source of truth (i.e. ablockchain), a system constraint that we did not have before

Operations are easy to define, asthey just need to be commutative, so that the resulting state willbe the same in every replica regardless of the order in whichthey have received the operations

wecan sign the broadcast messages, thus leaving signatures outof the Merkle-DAG

Comparing version vectors betweenpayloads is an inclusion check without the need to perform aDAG-walking

It is clear thatthis approach will bring some benefits

Smart Merge is built on a customized adaptation of Myer's diff algorithm and Google's diff-match-patch

Please note that it is impossible to revoke a device

initial

¬∃b′ ∈ blocklace : (b′ ̸ = b ∧ b′.creator = b.creator ∧ observes(b′, b))

received_orders

Once a recipient has received one copy of a message, they MUST ignore subsequent copies that arrive, such that resends are idempotent

When Alice and Bob are both bidding in an auction protocol, each of them marks their first bid with sender_order: 1, their second bid with sender_order: 2, and so forth.

sender_order

We suggest that the messaging standards all erred by treating public-key encryption and digital signatures as if they were fully independent operations

When B receives A's signed & encrypted message, B can't know how many hands it has passed through, even if B trusts A to be careful.

But in reality, when Charlie gets Alice's message via Bob, Charlie very likely will assume that Alice sent it to him directly

In this case, Alice will be blamed conclusively for Bob's exposure of their company's secrets.

Here, Bob has misled Charlie to believe that ``Alice loves Charlie.''

forces the sender to talk “on the record”

centralized servers and certificate authorities perpetuate a power and UX imbalance between servers and clients that doesn’t fit with peer-oriented DIDComm Messaging

web security is provided at the transport level (TLS); it is not an independent attribute of the messages themselves

The Broadcast Channel API allows basic communication between browsing contexts (that is, windows, tabs, frames, or iframes) and workers on the same origin.

withtokens provided by their IdP.

The new device needs to receive the secret s withoutleaking it to any third party

Finally, EL PASSO supports multi-device scenarios. It en-ables users to easily register new devices (e.g., laptop, phone,tablet) and supports easy identity recovery in case of the theftof one device. It natively supports 2FA: An RP may requestand assess that users connect from two different devices inorder to sign on their services (multi-device support).

intra-RP linkability

Commonly, this is accomplished through a pub-licly available list of credential statuses (either listing the revokedor valid credentials).

Trust anchors affirm the provenance of identitiesand public attributes (DIDDocs)

Alternatively, a simple public key canserve as an identifier, eliminating the DID/DIDDoc abstraction2

according to my entire history

Adding time todigital social contracts is an anticipated future extension

If one user marks a word as bold and another user marks the same word as non-bold, thereis no final state that preserves both users’ intentions and also ensures convergence

If the context has changed

Rather than seeing document history as a linear sequence of versions,we could see it as a multitude of projected views on top of a database of granular changes

Another approach is to maintain all operations for a particular document version in anordered log, and to append new operations at the end when they are generated. To mergetwo document versions with logs 𝐿1 and 𝐿2 respectively, we scan over the operations in𝐿1, ignoring any operations that already exist in 𝐿2; any operations that do not exist in 𝐿2are applied to the 𝐿1 document and appended to 𝐿1 in the order they appear in 𝐿2.

Peritext works bycapturing a document’s edit history as a log of operations

but since a given client never uses the same counter value twice, the combination ofcounter and nodeId is globally unique

Another area for future exploration is moving and duplicating text within a document. If twopeople concurrently cut-paste the same text to different places in a document, and then furthermodify the pasted text, what is the most sensible outcome?

span can be deleted once causalstability [2] has ensured that there will be no more concurrent insertions into that span

Fig. 4

For example, a developer mightdecide that colored text marks should be allowed to overlap, with the overlap region rendering ablend of the colors

No

Conflicts occur not only with colors; even simple bold formatting operations canproduce conflicts

Consider assigning colored highlighting to some text

Furthermore, as with plain text CRDTs, this model only preserves low-level syntactic intent,and manual intervention will often be necessary to preserve semantic intent based on a humanunderstanding of the text

With this strategy, the rendered result is

The key idea is to store formatting spans alongside the plaintext character sequence,linked to a stable identifier for the first and last character of each span, and then to derive the final formattedtext from these spans in a deterministic way that ensures concurrent operations commute

Privacy is realized by the group founder creating a specialkeypair for the group and secretly sharing the private group key with every new group member.When a member is removed from a group or leaves it, the founder has to renew the group’s keypair

However, by doing so the sender mayreveal additional information through the block’s hash pointers, e.g. the identities of other groupmembers

reserved words

A group creator can invite other agents to become members and remove members atwill.

Thegrassroots WhatsApp-like protocol WL employs a hypergraph (a graph in which an edge mayconnect any number of vertices). A hyperedge connecting agents 𝑃 ⊂ Π means that the agents in 𝑃are members in a group represented by the hyperedge

SMS

has an IPaddress

Inpractice, an agent is an app running on a smartphone

Federated systems aimto distribute control, but federated servers are still controlled autocratically

Note that Grassroots Social Networking requires dissemination, and Grassroots Cryptocurrenciesrequire also equivocation exclusion, but neither require consensus. Consensus is needed only byhigher-level applications that employ “on-chain” governance such as grassroots social contracts [7 ],the grassroots counterpart of miner-operated smart contracts, and grassroots representative assem-blies (in preparation).

and if located behind a firewall that preventssmartphones from communicating directly,

In particular, adeep-fake payload that is not attributed to its source can be promptly filtered as spam

However, sinceevery block in GSN is signed, when one breaches privacy within the protocol the breach carriestheir signature so the culprit can be identified.

A rather elaborate set of protocols and infrastructure (named STUN, TURN, TURNS, ICE)is needed to overcome these Internet limitations.

Furthermore, each block sent includes the most recent IP address of the sender,allowing agents to keep track of their friend’s changing IP addresses.

Every so often, an agent 𝑝sends to every friend 𝑞 every block 𝑝 knows and believes that 𝑞 needs, based on the last blockreceived from 𝑞.

Agents communicate only with their friends

However, their exclusion is not required in social networking, and hence social networking protocolscan be simpler than payment systems protocols

Grassroots Social Networking safety implies that each member can be held accountable to theirown utterances, as well as to utterances that they forward. As Grassroots Social Networking hasno controlling entity that can be held accountable in case members of the social network breakthe law, accountability and law enforcement in Grassroots Social Networking are more similarto real life then to the social networks we are familiar with.

In WhatsApp, members of a group must trust the serviceto correctly identify the member who authored an utterance, and utterances forwarded from onegroup to another have no credible attribution or context

In existing social networks, utterances by members do not carry intrinsic attribution orprovenance. Hence, Twitter members must trust the social network operator to correctly identifythe authorship of a tweet

As a screenshot with a tweet could easily be a fake, an author of a tweetcan later repudiate it simply by deleting it, and no proof that the tweet ever existed can be provided,except perhaps by the operator itself.

Naturally, an actual Grassroots Social Networking application may integratethe two protocols to provide both public feeds and private groups

The WhatsApp-like network has private groups, members of each group being both the authors andfollowers of its feed

The Twitter-like network has public feeds

friendsneed

, free of third-party control

The consensus is reached in the same way as fortransactions i.e. using hasgraph consensus algorithm. The onlydifference is, that the concerning events in the hashgraph nowcontain other type of data instead of transactions

DL

Composing Implementations

This implies that any correct run of the imple-mentation that stutters indefinitely has infinitely many opportunities to activatethe specification. Under the standard assumption that an opportunity that ispresented infinitely often is eventually seized, a live implementation does notdeadlock as it eventually activates the specification.

Live

Complete

Safe

implementedtransition system (henceforth – specification),

An implementation is correct if it is safe, complete and live.

Given two transition systems T S = (S, s0, T ) and T S′ = (S′, s′0, T ′) an im-plementation of T S by T S′ is a function σ : S′ → S where σ(s′0) = s0.

empty if s = s′

Also note that T and T f are not necessarydisjoint, for the same reason that even a broken clock shows the correct houronce in a while

We denote by s ∗−→ s′ ∈ T the existence of a correctcomputation (empty if s = s′) from s to s′

A transition in T f \ T is faulty, and a computation is faulty if it

A transition s → s′ ∈ T is correct, and a computation of correct transitionsis correct.

a run of T S is a computation that starts froms0.

A computation of T S is a sequenceof transitions s −→ s′ −→ · · · ,

Atransition system T S = (S, s0, T, T f ) consists of a set of states S, an initialstate s0 ∈ S, a set of (correct) transitions T ⊆ S2 and a set of faulty transitionsT f ⊆ S2. If T f = ∅ then it may be omitted

the transitions over S are all pairs (s, s′) ∈ S2, also written s → s′.

Given a set S, referred to asstates,

◦

and σ32 :S3 → S3

→

TL;DR: Decoupling data dissemination from metadata ordering is the key mechanism to allow scalable and high throughput consensus systems. Moreover, using an efficient implementation of a DAG to abstract the network communication layer from the (zero communication overhead) consensus logic allows for embarrassingly simple and efficient implementations (e.g., more than one order of magnitude throughput improvement compared to Hotstuff).

Every p-block with a payment in r-coins by a correct trader p ̸ = ris eventually approved or disapproved by an r-block [provided p and r are friends or have acommon friend in SG(B)]a.

An r-block b that repays a redemption claim with comment (redeem, P ), P =[p1, p2, . . . , pk], k ≥ 1, has a payment in pi-coins, i ∈ [k], provided the balance of r does notinclude any pj -coins for any 1 ≤ j < i at the time of creating b, and has a payment in r-coins,r /∈ P , provided the balance of r does not include any P -coins at the time of creating b

An r-block b with an empty payment and comment (disapprove, h′) pointsto an r-coin payment block b′, where h′ points to the reason for disapproval: To b′, if it isunbalanced, or to a block b′′ equivocating with b′

An r-block b with an empty payment and comment approve points to balancedr-coin payments block b′, where b does not observe a block equivocating with b′

Given a blocklace B and two agents p, r ∈ Π, the r-coins balance of p in B isthe sum of r-coins payments accepted by p in B minus the sum of r-coins payments issued by p in B.

Finality: A p-block consumes a non-p-block b′ with a payment to p only if r approves b′.

and only if r does not have enough p1 coins then r pays any remainder inp2 coins, and only if r does not have enough p2 coins then r pays to p any remainder in r-coins

not letting

consisting of r-coins, which can be thought of as IOUs issued and signed by r

The black agent mints a black coin, increasing its balance from 3 to 4 coins

C

and the red agent acceptsthe payment, increasing its balance to 6 black coins.

The black agent approves the payment

decreasing its balance to 2 black coins

Agree to redeem any domestic coin issued in return for any foreign coin held. Forexample, Alice must agree to a request by Bob to redeem an Alice-coin Bob holds against any coin heldby Alice.

eachpricing their goods and services in terms of their own personal coins. Next, assume that every two villagersexchange 100 personal coins with each other

If all agents must obtain and maintain a complete copy of the entire data structure in order to operate it shouldbe called replicated ; it should be called distributed if different agents access, maintain and store different parts ofthe data structure. Similarly for distributed ledgers vs. replicated ledgers, with blockchains falling under the secondcategory. Note that sharded blockchains are replicated, as an agent must obtain all shards in order to operate onthe blockchain

lest any tem-porary decline in personal productivity would result in theperson going broke

Minting: Each agent p mints (i.e. creates initial NFTs with)its own p-coins, as many as it pleases

Economically, sovereign cryptocurrenciesprovide for grassroots liquidity without external capital or credit,as mutual credit lines can be established via sovereign coinexchange among members of the cryptoeconomy

Weshow that the blue leader is ratified by any subsequent cordial leader

for any p, q ∈ P and anyp-block b ∈ B there is a q-block b′ ∈ B such that b′ ≻ b

ratified by ablock b if it is ratified by the set of blocks [b

if [B] includes a supermajority of blocks that approve

For each wave, one of the miners is elected as the leader, and if the first round of thewave has a block produced by the leader, then it is the leader block.

When a waveends, i.e., when the last round of the wave is cordial, the leader block becomes final if it hassufficient blocks that approve it, namely, it is not equivocating and there is a supermajoritywhere each block observes a supermajority that observes the leader block

Correct minersare cordial in that they wait for round r to attain a supermajority before contributing ablock to round r + 1.

A set of blocks by more than 12 (n + f ) miners is termed asupermajority

The depth of a block in a blocklaceis the length of the maximal path emanating from it

To this end, theblocklace is divided into waves, each consisting of several rounds, the number of which isdifferent for ES and asynchrony (3 and 5 rounds per wave, respectively).

In case a wave ends with no finalleader block, unordered blocks will be ordered when some subsequent wave ends with a finalleader block.

The protocol might even say that afterAlice syncs to Bob, then Bob will immediately sync back to Alice

and gossips to him all the events thatshe knows. Bob then creates a new event to record the fact of that gossip

When Bobgossiped to Alice, he would give her all of the events which he knew and she didnot.

Data structures withgraphs of hashes have been used for other purposes, such as in Git where the ver-tices are versions of a file tree, and the edges represent changes

The red eventcan also contain a payload of any transactions that Alice chooses to create at thatmoment, and perhaps a timestamp which is the time and date that Alice claims tohave created it

Alice then repeats with a differentrandom member.

Figure 1

We believe that thelack of a business model that can incentivize ‘genuine’ peer-to-peer applications and the lackof suitable architectural foundations for such applications are the culprit

The block content isa pair 퐶 = (푣, 푃) of an arbitrary value 푣 (the block payload)and a set 푃 of the block identities of the predecessors of 푏

the block is valid: valid(푣, ≺푏),using the definition of valid provided by the data type

Contrary to current DAG-like structures that use hashesof content, a blocklace uses signed hashes from which theblock creator can be known. Not only this can aid dissemina-tion, by knowing which node is missing which blocks, butmore importantly, it can be used to detect equivocations andequivocators

In-deed, the blocklace-based Cordial Dissemination protocol [7,12] employs the fact that a 푝-block 푏 by a correct node 푝 ac-knowledges all the blocks known to 푝 at the time of blockcreation

To be a colluder, 푝 must violate liveness, as it must refuseindefinitely to accept blocks by correct agents that acknowl-edge 푞 as Byzantine.

Accept the block into the blocklace, resulting in all nodeseventually knowing that 푝 is Byzantine

node

Correct nodes create a new block in 퐵 using the identitiesof the set of maximals in 퐵 as predecessors. By definition,all the elements in this set are incomparable, forming anantichain. If that is not the case, the creator is Byzantine

and eventu-ally excluding any new blocks created by Byzantine agents

Extant approaches no not attempt to detect equivocations.Messages from Byzantine equivocators that are not rejectedas invalid are simply accepted and treated as if they wereconcurrent operations from different correct nodes.

A blocklace 퐵 is then isomorphic to a PO-Log from thepure-op framework, thus is also a pure-op CRDT

were max≺ (퐵) is the set of maximal blocks in 퐵 under the≺ relation, i.e., the blocks which are not pointed from anyother block in 퐵

Note that the virtual chain axiom holds for correct nodessince they create blocks in sequence and include each newblock in their blocklace

Thus, there are no “dangling pointers” in a blocklace: eachidentity in each set of predecessors of a block in a blocklaceidentifies a block in the blocklace.

Weassume that the identity (public key) of the node can be ex-tracted from its signature, e.g., using ECDSA.

We remark that even if two nodes 푝, 푞 ∈ Π hold identi-cal blocklaces, and each of these nodes creates a new blockwith the same payload and same set of predecessor blocks,and therefore with the same hash, block identities will bedifferent as the hash will be signed by the different privatekeys of 푝 and 푞.

A block is final when subsequent blocks issuedby a supermajority of the agents approve it. See Figure 1.A

If the block is urgent then issue an ack block.

Existing algorithms for payment systems, including the onesin [ 1, 6 , 11], are based on reliable broadcast (RB) [ 2] to disseminateblocks to other agents. RB is an abstraction that prevents Byzantineagents from equivocating, which in the context of a payment systemprevents Byzantine agents from doublespending

An op-based CRDT is pure if mes-sages contain only the operation (including arguments, if any).

The possi-bility of a stable operation obsoleting a new arrival, in its causal future, is notconsidered, but this can easily be changed if some example shows its usefulness

Here we not only need this to happen but also that no further concur-rent messages may be delivered. Therefore, causal stability is a stronger notion,implying classic message stability

As such, a pure op-basedCRDT implementation is trivial: as when using the standard causal broadcast,the message returned from prepare, containing the operation, will arrive exactlyonce at each replica, it is enough to make effect consist simply in applying thereceived operation to the state, over a standard sequential datatype, i.e., definingfor any datatype operation o:

Commutative datatypes reflect a principle of permutation equivalence [11]stating that “If all sequential permutations of updates lead to equivalent states,then it should also hold that concurrent executions of the updates lead to equiv-alent states”

Op-based CRDTs can often have a simple and compact state since they can relyon the exactly-once delivery properties of the broadcast service, and thus donot have to explicitly handle non-idempotent operations.

I think this would modify your trust model. Say you trusted 10 peers. If one of them was malicious, then you have 1/10 malcious peers and the majority of nodes are good so you could identify the bad node. In the changes you propose, (if I understand correctly), the 1 malicious node, could then send you 100 more malicious nodes. So then you'd be connected to 101/110 malicious peers and the malicious peers would be the majority.

VectorSync [31] is an enhanced version of ChronoSync[35] which uses version vectors to make synchronisationbetween peers more efficient. Version vectors are more efficientin detection of inconsistencies, than simple message digests, asmentioned earlier. However, similarly to other proposals in thearea, VectorSync needs to realise a ‘leader-based membershipmanagement’ in order to deal with active members that updatethe state of the dataset.

Moreover, after executing an inverse opera-tion like O2, the document state can no longer be properlyrepresented by the state vector, which is only capable ofrepresenting original normal editing operations

I get a new ClientID for every session, is there a way to make it static for a peer accessing the document?

Furthermore, due to its design, the garbage collector inYATA may break late join mechanisms. This is becausewhen a user is offline for a period longer than t seconds,it will still hold references to deleted operations, while on-line users who already performed certain removals do not.Therefore, YATA does not support garbage collection for asite while it is offline.

From our practical experi-ences and the use in production, such a delay is sufficientto ensure that content will be removed safely, without anylosses that may lead to inconsistencies

Conceptually, an insertion marked for deletioncan be garbage collected when all sites received the removeoperation and have in their internal representation the op-eration that is to be garbage collected

We denote an insert operation as ok (idk , origink , lef tk ,rightk , isDeletedk , contentk )

Upon its creation, the operation thus gets as-signed a unique identifier which is composed of the useridand the current operation counter

The downside ofthis approach is that a state vector must be transmittedwith every operation, where the size of the state vector isproportional to the number of users in a collaborative ses-sion.

COT has a simplified design, as only onetransformation function must be defined

The ideabehind COT is to save every received operation “as is” in adocument state and preprocess it afterwards given the op-eration context.

If you tried to join two lists together, but somebody has added a paragraph between them, your change becomes impossible to execute (you can't join nodes that aren't adjacent), so it is dropped.

Instead of a central server calling the shots, you could use a consensus algorithm like Raft to pick an arbiter. (But note that I have not actually tried this.)

Secondly, though most OT systems just represent changes as a series of insertions and deletions, mapping seems to require us to distinguish replacements from the corresponding delete/insert pair. When a replacement happens next to a given position, the position should never move across the replacement, regardless of whether you're mapping forward or backward. In order to be able to support this, CodeMirror's change representation is encoded as a series of replacements. (Insertions become replacements that don't delete anything, and deletions replacements that don't insert anything.)

This can be derived from a sequence of individual changes, but it seems like it'd be more pleasant if changes were directly kept in that shape.

When a client receives conflicting remote changes, it first undoes all its local pending changes, applies the remote changes, and then the transformed form of its local changes.

OT algorithms that support decentralized editing rather resemble CRDT algorithms

along with data (often a logical clock) embedded in the IDs

That is where CRDTs come in. They are another approach to convergence that, contrary to operational transformation, does provide a way for us mortals to reason about convergence.

And when you don't have a centralized party to determine the order in which changes get applied, you need, as far as I understand the literature, to keep data beyond the current document (“tombstones” that describe where deletions happened), to guarantee convergence.

Periodically try to send those to the server, which will either accept them or, if another client sent a change first, reject them because your changes start in a base document that doesn't match the current central document.

Consistency models