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 OL ), 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 OGS ), a novel abstraction that, unlike the OL , 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 OGS and present a Byzantine-tolerant, consensus-free implementation (denoted as OGSB ) 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 OGSB can be leveraged to construct a consensus-free, Single-Writer Byzantine-tolerant OL . We argue that the applicability of the OGSB extends well beyond these specific use cases, offering a lightweight and efficient foundation for a variety of distributed applications.