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 2 Grassroots Protocols Informally, when agents operate according to a grassroots protocol (i) the possible behaviors and interactions of an isolated community of agents are not constrained by placing the community within a larger community and (ii) agents in an isolated community, when placed within a larger community, may have behaviors and interactions not possible when in isolation. In particular, agents may interact with each other across community boundaries. This notion supports the grassroots deployment of a distributed system – autonomous independent instances deployed at different locations and over time that can possibly (but not necessarily) interoperate once interconnected. Asynchronous distributed multiagent transition systems. We formalize this intuitive notion of a grassroots protocol using asynchronous distributed multiagent transition system [24]. See Appendix A for a brief introduction; we repeat below essential definitions and results. Assume a set Π of agents, each equipped with a single and unique key-pair, and identify an agent p ∈ Π by its public key. While the set of all agents Π could in principle be infinite (think of all the agents that are yet to be born), when we refer to a particular set of agents P ⊆ Π we assume P to be finite. Note that the trivial liveness requirement entails the standard one: A run is live if for every agent p that is enabled infinitely often, the run has infinitely many p-transitions. A transition system is asynchronous if progress by other agents cannot prevent an agent from taking an already-enabled transition. Observation 9. An all-to-all dissemination protocol cannot be grassroots. Sufficient condition for a protocol to be grassroots. Here we define certain properties of a protocol and prove that satisfying them is sufficient for the protocol to be grassroots. Theorem 12 (Grassroots Protocol). An asynchronous, interactive, and non-interfering protocol is grassroots. We note that blockchain consensus protocols with hardcoded miners, e.g. the seed miners of Bitcoin [11] or the bootnodes of Ethereum [12], and permissioned consensus protocols with a predetermined set of participants such as Byzantine Atomic Broadcast [27, 16], are all interfering, as additional participants may be required and/or cannot be ignored. However, Theorem 12 and the examples above do not imply that ordering consensus protocols cannot be grassroots. The problem is not with the consensus protocol as such, but with the choice of its participants. If participants in an instance of an ordering consensus protocol are determined by the agents themselves via a grassroots protocol, rather than being provided externally and a priori as in standard permissioned consensus protocols, or are required to include a predetermined set of initial participants as in Bitcoin and Ethereum, then the participants can reach consensus without violating grassroots. Devising grassroots consensus protocols is a subject of future work. Next, we present the Grassroots Dissemination protocol and prove it to be grassroots. 2.2 The Grassroots Dissemination Protocol The All-to-All Dissemination protocol is asynchronous and interactive, and this is also true of Grassroots Dissemination. But, unlike All-to-All Dissemination, in the Grassroots Dissemination protocol dissemination occurs only among friends. Moreover, agents are free to choose their friends. Hence, additional agents may be ignored by a given group of agents without violating agent liveness, implying that Grassroots Dissemination is also non-interfering and thus grassroots, as proven below. We assume a given payloads function X that maps each set of agents P to a set of payloads X (P). For example, X could map P to all strings signed by members of P; or to all messages sent among members of P, signed by the sender and encrypted by the public key of the recipient; or to all financial transactions among members of P. Remember that here P are not ‘miners’ serving transactions by other agents, but are the full set of agents participating the in protocol. 2.3 Grassroots Implementation Here we define the notion of a grassroots implementation and prove that having a grassroots implementation is a sufficient condition for a protocol to be grassroots. First we recall the notion of implementation among multiagent transition systems [24] (See also Appendix A) The following theorem shatters the hope of a non-grassroots protocol to have a grassroots implementation, and can be used to prove that a protocol is grassroots by providing it with a grassroots implementation. Theorem 20 (Grassroots Implementation). A protocol that has a grassroots implementation is grassroots. 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 2 Grassroots Protocols Informally, when agents operate according to a grassroots protocol (i) the possible behaviors and interactions of an isolated community of agents are not constrained by placing the community within a larger community and (ii) agents in an isolated community, when placed within a larger community, may have behaviors and interactions not possible when in isolation. In particular, agents may interact with each other across community boundaries. This notion supports the grassroots deployment of a distributed system – autonomous independent instances deployed at different locations and over time that can possibly (but not necessarily) interoperate once interconnected. Asynchronous distributed multiagent transition systems. We formalize this intuitive notion of a grassroots protocol using asynchronous distributed multiagent transition system [24]. See Appendix A for a brief introduction; we repeat below essential definitions and results. Assume a set Π of agents, each equipped with a single and unique key-pair, and identify an agent p ∈ Π by its public key. While the set of all agents Π could in principle be infinite (think of all the agents that are yet to be born), when we refer to a particular set of agents P ⊆ Π we assume P to be finite. Note that the trivial liveness requirement entails the standard one: A run is live if for every agent p that is enabled infinitely often, the run has infinitely many p-transitions. A transition system is asynchronous if progress by other agents cannot prevent an agent from taking an already-enabled transition. Observation 9. An all-to-all dissemination protocol cannot be grassroots. Observation 9. An all-to-all dissemination protocol cannot be grassroots. Sufficient condition for a protocol to be grassroots. Here we define certain properties of a protocol and prove that satisfying them is sufficient for the protocol to be grassroots. Sufficient condition for a protocol to be grassroots. Theorem 12 (Grassroots Protocol). An asynchronous, interactive, and non-interfering protocol is grassroots. Theorem 12 We note that blockchain consensus protocols with hardcoded miners, e.g. the seed miners of Bitcoin [11] or the bootnodes of Ethereum [12], and permissioned consensus protocols with a predetermined set of participants such as Byzantine Atomic Broadcast [27, 16], are all interfering, as additional participants may be required and/or cannot be ignored. However, Theorem 12 and the examples above do not imply that ordering consensus protocols cannot be grassroots. The problem is not with the consensus protocol as such, but with the choice of its participants. If participants in an instance of an ordering consensus protocol are determined by the agents themselves via a grassroots protocol, rather than being provided externally and a priori as in standard permissioned consensus protocols, or are required to include a predetermined set of initial participants as in Bitcoin and Ethereum, then the participants can reach consensus without violating grassroots. Devising grassroots consensus protocols is a subject of future work. Next, we present the Grassroots Dissemination protocol and prove it to be grassroots. 2.2 The Grassroots Dissemination Protocol 2.2 The Grassroots Dissemination Protocol The All-to-All Dissemination protocol is asynchronous and interactive, and this is also true of Grassroots Dissemination. But, unlike All-to-All Dissemination, in the Grassroots Dissemination protocol dissemination occurs only among friends. Moreover, agents are free to choose their friends. Hence, additional agents may be ignored by a given group of agents without violating agent liveness, implying that Grassroots Dissemination is also non-interfering and thus grassroots, as proven below. We assume a given payloads function X that maps each set of agents P to a set of payloads X (P). For example, X could map P to all strings signed by members of P; or to all messages sent among members of P, signed by the sender and encrypted by the public key of the recipient; or to all financial transactions among members of P. Remember that here P are not ‘miners’ serving transactions by other agents, but are the full set of agents participating the in protocol. 2.3 Grassroots Implementation 2.3 Grassroots Implementation Here we define the notion of a grassroots implementation and prove that having a grassroots implementation is a sufficient condition for a protocol to be grassroots. First we recall the notion of implementation among multiagent transition systems [24] (See also Appendix A) The following theorem shatters the hope of a non-grassroots protocol to have a grassroots implementation, and can be used to prove that a protocol is grassroots by providing it with a grassroots implementation. Theorem 20 (Grassroots Implementation). A protocol that has a grassroots implementation Theorem 20 is grassroots.

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

Grassroots Distributed Systems for Digital Sovereignty: Grassroots Protocols

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 Implementation of Grassroots Dissemination

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 Implementation of Grassroots Dissemination

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