Byzantine-tolerant distributed grow-only sets: specification and applications

In order to formalize Distributed Ledger Technologies and their interconnections, recent research has introduced the concept of a Distributed Ledger Object (denoted $$\mathcal {O}^L$$ ), a concurrent abstraction that maintains a totally ordered sequence of records, capturing the essence of blockchains and distributed ledgers. In this work, we introduce the Distributed Grow-only Set object (denoted $$\mathcal {O}^{GS}$$ ), a novel abstraction that, unlike the $$\mathcal {O}^L$$ , maintains an immutable set of records by supporting only Add and Get operations. This object is inspired by the Grow-only Set (G-Set) a well-known Conflict-free Replicated Data Type (CRDT). We formally define the $$\mathcal {O}^{GS}$$ and present a Byzantine-tolerant, consensus-free implementation (denoted as $$\mathcal {O}^{GS}_B$$ ) that ensures eventual consistency. Building on this implementation, we propose consensus-free algorithmic solutions to two fundamental problems: the Atomic Appends problem, which concerns atomically appending multiple records to distinct ledgers, and the Atomic Adds problem, its counterpart in the context of G-Sets. Additionally, we show how the $$\mathcal {O}^{GS}_B$$ can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant $$\mathcal {O}^L$$ . We argue that the applicability of the $$\mathcal {O}^{GS}_B$$ extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.