Paper 2022/455

Proof of Availability & Retrieval in a Modular Blockchain Architecture

Shir Cohen, Guy Goren, Lefteris Kokoris-Kogias, Alberto Sonnino, and Alexander Spiegelman

Abstract

This paper explores a modular design architecture aimed at helping blockchains (and other SMR implementation) to scale to a very large number of processes. This comes in contrast to existing monolithic architectures that interleave transaction dissemination, ordering, and execution in a single functionality. To achieve this we first split the monolith to multiple layers which can use existing distributed computing primitives. The exact specification of the data dissemination are formally defined by the Proof of Availability & Retrieval (PoA&R) abstraction. Solutions to the PoA&R problem contain two related sub-protocols: one that ``pushes'' information into the network and another that ``pulls'' this information. Regarding the latter, there is a dearth of research literature which is rectified in this paper. We present a family of pulling sub-protocols and rigorously analyzing them. Extensive simulations support the theoretical claims of efficiency and robustness in case of a very large number of players. Finally, actual implementation and deployment on a small number of machines (roughly the size of several industrial systems) demonstrates the viability of the architecture's paradigm.