Stateless Distributed Ledgers^††thanks: This research is partly supported by Japan Science and Technology Agency (JST) OPERA Grant Number JY280149.

Distributed Ledger Technologies (DLTs) are usually partitioned depending on the type of consensus used to order incoming transactions. Here, we consider the three most used classes of technologies: Byzantine agreement, Proof of Work, and Proof of Stake.

Byzantine agreement protocols [7] are used to maintain consistent states replicated over multiple servers. It can tolerate crash or Byzantine faults, up to a number that depends on the synchrony assumption of the communications. Such protocols are executed by known servers in a fixed network environment, a setting called permissioned. They can easily be used by nodes to maintain a ledger of transactions. Every insertion in the ledger is the result of a consensus among participating nodes.

Blockchains based on Proof of Work (PoW) are the first distributed ledger technologies that work in an environment where nodes can join and leave and any node can participate to the protocol. Nodes are elected randomly proportionally to their computational power, and an elected node can append transactions to the ledger. All current PoW Blockchains, including Bitcoin, work with synchronous communications, and assume correct nodes to have strictly more computational power than Byzantine nodes.

Blockchains based on Proof of Stake (PoS) are similar to the PoW based ones, but nodes are elected proportionally to the amount of tokens they own in the blockchain itself. In protocols based on PoS, a well-known concern is called long-range attacks [2], where a group of nodes create an alternative chain extending an old block. This is made possible because block generation is not computationally heavy, and if a node can extend a block at a given time, nothing prevents it from extending the same block in a different way at a later time. This attack becomes even worse when the nodes owning a majority of tokens at a previous time, do not have stake at the current time. Performing such attacks could be appealing as they have nothing to lose. This problem is known as posterior corruption [1].

Existing Proof of Stake based protocols such as SnowWhite [1], Algorand [4], Ouroboros [6], have identified such risks. The main solution proposed is to have some sort of checkpointing mechanism to avoid considering past majorities of stake holders. A variant of this attack is called stake-bleeding attacks [3]. It uses other mechanisms such as block rewards and transaction fees to allow even a past minority of stake holders to execute long-range attacks.

We consider that time is discrete and at each time $t\in\mathbb{N}$, $\mathcal{N}_{t}$ represents the set of nodes in the network. We consider that communication is instantaneous and there is a communication link between any two nodes in the network at any given time. We also assume that each node is identified, and is able to securely sign messages.

A distributed ledger is a data structure with an “append” function. It is maintained by a set of processing nodes. The network receives events and the nodes react to the events according to the distributed ledger protocol. Each time the ledger is updated, a new time instant begins. Formally, a DLT is characterized by its initial state $I$ and a state transition function $\sigma$ that takes a current state $S_{t}$, the events $E_{t}$, and the network $\mathcal{N}_{t}$ containing all the nodes that are online at least once before the next “append”. Then $\sigma$ returns a new state $S_{t+1}$ when the “append” function is called at time $t+1$. A state can be seen as a sequence of “append” and we write $S\preccurlyeq S^{\prime}$ when state $S$ is a prefix of state $S^{\prime}$, i.e., $S^{\prime}$ can be obtained from $S$ by appending data. The state $S^{-k}$ denotes the truncated state $S$ where the last $k$ occurrences of “append” of $S$ are omitted.

Given a DLT $(I,\sigma)$, a sequence of $\mathcal{N}=(\mathcal{N}_{t})_{t\in\mathbb{N}}$ of networks and a sequence $E=(E_{t})_{t\in\mathbb{N}}$ of events, we can construct the sequence of states $\mathit{States}(I,\sigma,\mathcal{N},E)=(S_{t})_{t\in\mathbb{N}}$ in the following way $S_{0}=I$ and $\forall t\in\mathbb{N},S_{t+1}=\sigma(S_{t},\mathcal{N}_{t},E_{t})$.

In PoS Blockchains, the consensus at a given time $t$ is possible assuming the nodes owning a majority of the tokens are correct. So we can assume that the state transition function $\sigma_{\mathit{PoS}}$ is performed by those correct nodes, owning a majority of the tokens, creating a new state $S_{t+1}$ from state $S_{t}$ and incoming events $E_{t}$. However nothing prevents the nodes in $\mathcal{N}_{0}$ to create an alternative state after time $0$.

One way to make the PoS DLT stateless is to assume that any set of nodes owning a majority of the token at a given time $t$ are correct at any time $t^{\prime}>t$. This is a very strong assumption as for instance, it gives the same kind of trust in the initial set of nodes as in the Byzantine agreement protocol. Indeed, if the nodes in $\mathcal{N}_{0}$ are still connected at time $t$ then, they act as a trusted committee. We could even remove the proof of stake entirely and only rely on standard Byzantine agreement between nodes in $\mathcal{N}_{0}$. In the case where nodes in $\mathcal{N}_{0}$ go offline, they can select replacement nodes (using any method including election or simply one-to-one replacement), and include a signed message that define their choice in the state so that any joining node could identify the current set of trusted nodes. In future work, we plan to identify other sufficient conditions for the existence of Stateless DLTs.