Grassroots Distributed Systems for Digital Sovereignty: Grassroots Protocols

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.