This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license.
Authors:
(1) Ehud Shapiro,  Department of Computer Science and Applied Math, Weizmann Institute of Science, Israel and ehud.shapiro@weizmann.ac.il. Table of Links Abstract and Introduction
Grassroots Protocols
Grassroots Implementation of Grassroots Dissemination
Applications of Grassroots Dissemination Supporting Digital Sovereignty
Future Work & Discussion
References
A. Preliminaries: Asynchronous Distributed Multiagent Transition Systems
B. All-to-All Dissemination is not Grassroots
C. Proofs Grassroots Implementation of Grassroots Dissemination Here we present an implementation of the Grassroots Dissemination protocol GD, as depicted in Figure 1: The blocklace-based Cordial Grassroots Dissemination Protocol CGD (Def. 26), and its proof of being grassroots (Prop.28). The implementation σ (Def.33) of GD by CGD, and its proof of being grassroots (Thm. 29). Algorithm 1 with pseudocode for blocklace utilities and Algorithm 2 with pseudocode realizing CGD for the model of Asynchrony. The Cordial Grassroots Dissemination protocol employs the notions of follows, needs, friend, and friendship graph similarly to GD (Def. 14). A key difference is that in Grassroots Dissemination an agent that needs a block b may receive it from a friend that has b ‘by magic’, whereas in Cordial Grassroots Dissemination such an agent p must first disclose to a friend q the blocks it knows and the agents it follows, implying that it needs b, and based on such disclosure q may cordially send b to p. We employ the blocklace [15] to realize these principles. The blocklace is a DAGlike partially ordered generalization of the totally-ordered blockchain data structure that functions as a fault resilient, conflict-free replicated data type [26]. While the mathematical construction and proofs of the blocklace realization presented next are quite involved, the final result, presented as 30 lines of pseudocode in Algs. 1, 2, is quite simple. 3.1 Blocklace Preliminaries Each block in a blocklace may contain a finite set of cryptographic hash pointers to previous blocks, in contrast to one pointer (or zero for the initial block) in a blockchain. We assume a payload function X as above, and a collision-free cryptographic hash function hash. 3.2 The Cordial Grassroots Dissemination Protocol The Cordial Grassroots Dissemination protocol CGD realizes the two principles as follows. Disclosure is realized by a new p-block serving as a multichannel ack/nack message, informing its recipient whether it follows another agent q, and if so also of the latest q-block known to p, for every q ∈ P. This is realized by the notions defined next and illustrated in Figure 3. As we shall see, a correct agent p always maintains a p-closed blocklace and produces only maximally-closed p-blocks, thus abiding by the principle of disclosure. The local state in the protocol presented includes a blocklace and block messages. Notes. Disclosure is realized by the Create&Disclose transition choosing a maximally-closed p-block, and cordiality is realized by the Cordially-Send-b-to-q, with which p sends any p’-block b it knows to any friend q that p believes needs it. Namely, for which p knows that q follows p’ and p doesn’t know that q knows b. If q knows b then p would eventually know that, when it receives the next q-block that discloses knowledge of b. The special case of Cordially-Send, where p = p’ and b is a p-block, is simply dissemination among friends. Simple (volitional) Send can be used by an agent to send any block it has to any other agent. The recipient of a volitionally sent q-block can then follow q starting from that block. Similarly, two agents can send each other blocks to become friends. The liveness condition requires an agent to disclose every so often the blocks they know, to eventually send any block that satisfies the specified conditions, and receive any block sent to it that it does not know already, but it does not require an agent to follow other agents or to voluntarily send any block. Unlike in GD, where p can construct a simple initial q-block, here the initial q-block includes a hash pointer signed by q, which cannot be created/forged by p. Asynchrony. The model of asynchrony assumes that each message sent among correct agents is eventually received and an that an adversary may control, in addition to the faulty agents, also the order of message arrival among all agents. These assumptions are satisfied by the liveness requirement of CGD. Liveness ensures that communication is reliable, as any message sent among correct miners is eventually received, yet there is no bound on the finite delay of message arrival, as postulated by the model. Correctness of an agent requires it to be correct in all computations, hence the system has to be resilient to an adversary that controls not only faulty agents but also the order of transitions by correct agents. Controlling the order of Receive transitions amounts to control of the order of message arrival, as postulated by the model. The following proposition is the analogue of Proposition 16 for GD, with an analogue proof. 3.3 A Grassroots Implementation of CGD by GD We use the theorem above to show that: Theorem 29. CGD can provide a grassroots implementation of GD. We employ the notion of monotonic-completeness wrt to a partial order to prove the correctness of the implementation: 3.4 Pseudocode Implementation of Grassroots Cordial Dissemination The Cordial Grassroots Dissemination protocol was specified as a family of asynchronous distributed multiagent transition systems CGD (Def. 26). Asynchrony. Algorithm 2 presents pseudocode implementation of the protocol for a single agent p for the model of Asynchrony. The comments indicate which transition rule is realized by what code. We assume that the agent p can interact with the protocol application that runs on their personal device. In particular, p can specify the payload for a new block or decide to send any block it knows to any other agent. As according to the model of asynchrony each message sent is eventually received, we assume the reliably_send construct to keep a record of sent messages so as not to send the same message to the same agent twice, implementing the requirement (q, b) ∈/ Out of the Cordially-Send-b-to-q transition. The construct upon eventually is also geared for the model of asynchrony: It is a ‘timeless timeout’ with no notion of time, only with a guarantee of eventuality. The implementation of grassroots dissemination for asynchrony assumes reliable communication, readily implemented by TCP. However, for grassroots dissemination to reach its full potential it must be designed for mobile agents using unreliable communication, namely UDP. With TCP, smartphones can establish a connection only with the help of an agreed-upon third party, which undermines grassroots and digital sovereignty, and the connection needs reestablishing upon roaming to a new IP address. With UDP, a connection is not needed and incorporating the sender’s current IP address in a block lets recipients (re)transmit blocks to the sender’s updated IP address, allowing roaming agents to remain connected to their friends. Furthermore, the ability of a block in a blocklace to function as a multichannel ack/nack message shines in a UDP implementation, as a received p-block b (even if received indirectly, not from p) makes redundant the (re)transmission to p of any block observed by b. A refinement of the Cordial Grassroots Dissemination protocol for mobile (address-hopping) agents communicating over an unreliable network, namely smartphones communicating via UDP, is presented as Alg. 3. Mobile Agents Communicating via UDP. Cordial dissemination over UDP exploits the ack/nak information of blocklace blocks to its fullest, by p retransmitting to every friend q every block b that p knows (not only p-blocks) and believes that q needs, until q acknowledges knowing b. The sending of unsolicited blocks (Send-b-to-q) does not guaranteed delivery, and if delivered does not guarantee acknowledgement, unless the the block is a friendship offer (with a (‘follow’, q) payload), and the recipient q accept the offer (creating a block with a (‘follow’, p) payload). Assuming that timeouts are separated by seconds and mobile address hopping is separated by hours, then the probability of two friends hopping together without one successfully informing the other of its new IP address is around 10−7 . If the two hopping friends have a stationary joint friend, then it is enough that one of the hoppers successfully informs the stationary friend of the address change, for the other hopper to soon know this new address from the stationary friend. Under the same assumptions, the probability of a clique of n friends loosing a member due to all hopping simultaneously is around 10−3.6∗n. Note that such a loss is not terminal – assuming that friends have redundant ways to communicate (physical meetings, email, SMS, global social media), new addresses can be communicated and the digital friendship restored. We note that the timer need not be of fixed duration and global – an adaptive timer for each friend might prove more efficient. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. Authors: (1) Ehud Shapiro,  Department of Computer Science and Applied Math, Weizmann Institute of Science, Israel and ehud.shapiro@weizmann.ac.il. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. Authors: Authors: (1) Ehud Shapiro,  Department of Computer Science and Applied Math, Weizmann Institute of Science, Israel and ehud.shapiro@weizmann.ac.il. Table of Links Abstract and Introduction Grassroots Protocols Grassroots Implementation of Grassroots Dissemination Applications of Grassroots Dissemination Supporting Digital Sovereignty Future Work & Discussion References A. Preliminaries: Asynchronous Distributed Multiagent Transition Systems B. All-to-All Dissemination is not Grassroots C. Proofs Abstract and Introduction Abstract and Introduction Grassroots Protocols Grassroots Protocols Grassroots Implementation of Grassroots Dissemination Grassroots Implementation of Grassroots Dissemination Applications of Grassroots Dissemination Supporting Digital Sovereignty Applications of Grassroots Dissemination Supporting Digital Sovereignty Future Work & Discussion Future Work & Discussion References References A. Preliminaries: Asynchronous Distributed Multiagent Transition Systems A. Preliminaries: Asynchronous Distributed Multiagent Transition Systems B. All-to-All Dissemination is not Grassroots B. All-to-All Dissemination is not Grassroots C. Proofs C. Proofs Grassroots Implementation of Grassroots Dissemination Here we present an implementation of the Grassroots Dissemination protocol GD, as depicted in Figure 1: The blocklace-based Cordial Grassroots Dissemination Protocol CGD (Def. 26), and its proof of being grassroots (Prop.28). The implementation σ (Def.33) of GD by CGD, and its proof of being grassroots (Thm. 29). Algorithm 1 with pseudocode for blocklace utilities and Algorithm 2 with pseudocode realizing CGD for the model of Asynchrony. The Cordial Grassroots Dissemination protocol employs the notions of follows, needs, friend, and friendship graph similarly to GD (Def. 14). A key difference is that in Grassroots Dissemination an agent that needs a block b may receive it from a friend that has b ‘by magic’, whereas in Cordial Grassroots Dissemination such an agent p must first disclose to a friend q the blocks it knows and the agents it follows, implying that it needs b, and based on such disclosure q may cordially send b to p. We employ the blocklace [15] to realize these principles. The blocklace is a DAGlike partially ordered generalization of the totally-ordered blockchain data structure that functions as a fault resilient, conflict-free replicated data type [26]. While the mathematical construction and proofs of the blocklace realization presented next are quite involved, the final result, presented as 30 lines of pseudocode in Algs. 1, 2, is quite simple. 3.1 Blocklace Preliminaries 3.1 Blocklace Preliminaries Each block in a blocklace may contain a finite set of cryptographic hash pointers to previous blocks, in contrast to one pointer (or zero for the initial block) in a blockchain. We assume a payload function X as above, and a collision-free cryptographic hash function hash. 3.2 The Cordial Grassroots Dissemination Protocol 3.2 The Cordial Grassroots Dissemination Protocol The Cordial Grassroots Dissemination protocol CGD realizes the two principles as follows. Disclosure is realized by a new p-block serving as a multichannel ack/nack message, informing its recipient whether it follows another agent q, and if so also of the latest q-block known to p, for every q ∈ P. This is realized by the notions defined next and illustrated in Figure 3. As we shall see, a correct agent p always maintains a p-closed blocklace and produces only maximally-closed p-blocks, thus abiding by the principle of disclosure. The local state in the protocol presented includes a blocklace and block messages. Notes. Disclosure is realized by the Create&Disclose transition choosing a maximally-closed p-block, and cordiality is realized by the Cordially-Send-b-to-q, with which p sends any p’-block b it knows to any friend q that p believes needs it. Namely, for which p knows that q follows p’ and p doesn’t know that q knows b. If q knows b then p would eventually know that, when it receives the next q-block that discloses knowledge of b. The special case of Cordially-Send, where p = p’ and b is a p-block, is simply dissemination among friends. Simple (volitional) Send can be used by an agent to send any block it has to any other agent. The recipient of a volitionally sent q-block can then follow q starting from that block. Similarly, two agents can send each other blocks to become friends. The liveness condition requires an agent to disclose every so often the blocks they know, to eventually send any block that satisfies the specified conditions, and receive any block sent to it that it does not know already, but it does not require an agent to follow other agents or to voluntarily send any block. Notes. Unlike in GD, where p can construct a simple initial q-block, here the initial q-block includes a hash pointer signed by q, which cannot be created/forged by p. Asynchrony. The model of asynchrony assumes that each message sent among correct agents is eventually received and an that an adversary may control, in addition to the faulty agents, also the order of message arrival among all agents. These assumptions are satisfied by the liveness requirement of CGD. Liveness ensures that communication is reliable, as any message sent among correct miners is eventually received, yet there is no bound on the finite delay of message arrival, as postulated by the model. Correctness of an agent requires it to be correct in all computations, hence the system has to be resilient to an adversary that controls not only faulty agents but also the order of transitions by correct agents. Controlling the order of Receive transitions amounts to control of the order of message arrival, as postulated by the model. The following proposition is the analogue of Proposition 16 for GD, with an analogue proof. 3.3 A Grassroots Implementation of CGD by GD 3.3 A Grassroots Implementation of CGD by GD We use the theorem above to show that: Theorem 29. CGD can provide a grassroots implementation of GD. Theorem 29. We employ the notion of monotonic-completeness wrt to a partial order to prove the correctness of the implementation: 3.4 Pseudocode Implementation of Grassroots Cordial Dissemination 3.4 Pseudocode Implementation of Grassroots Cordial Dissemination The Cordial Grassroots Dissemination protocol was specified as a family of asynchronous distributed multiagent transition systems CGD (Def. 26). Asynchrony. Algorithm 2 presents pseudocode implementation of the protocol for a single agent p for the model of Asynchrony. The comments indicate which transition rule is realized by what code. We assume that the agent p can interact with the protocol application that runs on their personal device. In particular, p can specify the payload for a new block or decide to send any block it knows to any other agent. As according to the model of asynchrony each message sent is eventually received, we assume the reliably_send construct to keep a record of sent messages so as not to send the same message to the same agent twice, implementing the requirement (q, b) ∈/ Out of the Cordially-Send-b-to-q transition. The construct upon eventually is also geared for the model of asynchrony: It is a ‘timeless timeout’ with no notion of time, only with a guarantee of eventuality. Asynchrony. The implementation of grassroots dissemination for asynchrony assumes reliable communication, readily implemented by TCP. However, for grassroots dissemination to reach its full potential it must be designed for mobile agents using unreliable communication, namely UDP. With TCP, smartphones can establish a connection only with the help of an agreed-upon third party, which undermines grassroots and digital sovereignty, and the connection needs reestablishing upon roaming to a new IP address. With UDP, a connection is not needed and incorporating the sender’s current IP address in a block lets recipients (re)transmit blocks to the sender’s updated IP address, allowing roaming agents to remain connected to their friends. Furthermore, the ability of a block in a blocklace to function as a multichannel ack/nack message shines in a UDP implementation, as a received p-block b (even if received indirectly, not from p) makes redundant the (re)transmission to p of any block observed by b. A refinement of the Cordial Grassroots Dissemination protocol for mobile (address-hopping) agents communicating over an unreliable network, namely smartphones communicating via UDP, is presented as Alg. 3. Mobile Agents Communicating via UDP. Cordial dissemination over UDP exploits the ack/nak information of blocklace blocks to its fullest, by p retransmitting to every friend q every block b that p knows (not only p-blocks) and believes that q needs, until q acknowledges knowing b. The sending of unsolicited blocks (Send-b-to-q) does not guaranteed delivery, and if delivered does not guarantee acknowledgement, unless the the block is a friendship offer (with a (‘follow’, q) payload), and the recipient q accept the offer (creating a block with a (‘follow’, p) payload). Assuming that timeouts are separated by seconds and mobile address hopping is separated by hours, then the probability of two friends hopping together without one successfully informing the other of its new IP address is around 10−7 . If the two hopping friends have a stationary joint friend, then it is enough that one of the hoppers successfully informs the stationary friend of the address change, for the other hopper to soon know this new address from the stationary friend. Under the same assumptions, the probability of a clique of n friends loosing a member due to all hopping simultaneously is around 10−3.6∗n. Note that such a loss is not terminal – assuming that friends have redundant ways to communicate (physical meetings, email, SMS, global social media), new addresses can be communicated and the digital friendship restored. We note that the timer need not be of fixed duration and global – an adaptive timer for each friend might prove more efficient. Mobile Agents Communicating via UDP.

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Grassroots Implementation of Grassroots Dissemination

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Comparative Analysis of Crypto API Misuses Across Programming Languages

Grassroots Distributed Systems for Digital Sovereignty: Abstract and Introduction

Grassroots Distributed Systems: Preliminaries: Asynchronous Distributed Multiagent Transition System

Grassroots Distributed Systems for Digital Sovereignty: Grassroots Protocols

Applications of Grassroots Dissemination Supporting Digital Sovereignty

Grassroots Distributed Systems for Digital Sovereignty: References

A Comparative Analysis of Crypto API Misuses Across Programming Languages

Grassroots Distributed Systems for Digital Sovereignty: Abstract and Introduction

Grassroots Distributed Systems: Preliminaries: Asynchronous Distributed Multiagent Transition System

Grassroots Distributed Systems for Digital Sovereignty: Grassroots Protocols

Applications of Grassroots Dissemination Supporting Digital Sovereignty

Grassroots Distributed Systems for Digital Sovereignty: References

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps