On Subspace Proof-of-Archival-Storage Consensus

This first post in our open research space describes where Subspace consensus stands in a global taxonomy, abstractly and formally. Thanks to @rg3l3dr for putting this together.
This post is written primarily for potential collaborators to develop a common understanding of our definitions and interests.

Proof-of-Archival-Storage (PoAS) Consensus

Simply put, proof-of-archival-storage (PoAS) consensus is an adaption of Nakamoto’s longest-chain protocol in which the proof-of-work (PoW) puzzle is replaced with a proof-of-replication (PoRep).
In PoAS, the input data to the PoR is the history of the blockchain itself (i.e., the past blocks).

PoAS consensus is designed to solve one part of a very specific problem for proof-of-capacity (PoC) blockchains, the farmer’s dilemma, as described in the Subspace Technical Whitepaper.

“farmers must decide whether to allocate scarce storage resources to maintain the chain state and history or maximize the amount of space they pledge towards consensus. Rational farmers will always choose the latter, at best becoming light clients, while at worst encouraging pooled farming under a few trusted operators.”

Terminology

We are solely interested in Nakamoto consensus (longest-chain) protocols. We treat these abstractly as black box protocols, which include some sybil-resistant (resource-constrained) cryptographic puzzle that can be sampled, audited, or challenged in a manner that may be modeled as a Poisson arrival process. Example puzzles include PoW (computation), PoS (capital) and PoC (storage).

We use proof-of-capacity as an abstract umbrella term, capturing proofs of storage, space, replication, reterievability, and space-time. We view them as primitives that can be used to construct or implement a specific PoC consensus protocol. We broadly divide PoC into two categories, somewhat prejoritavely as:

  • proofs-of-(useless)-space,
    where the data being stored is randomly generated (Burst, Spacemint, Chia, Spacemesh);
  • proofs-of-(useful )-storage,
    where the data being stored on disk is some transformation of meaningful, real-world data (Filecoin, Subspace).

With respect to proofs-of-storage, we broadly follow the framework and terminology provided in the PoReps paper by Ben Fisch. Specifically, a proof-of-replication is a useful proof-of-storage, which composes a proof-of-space (PoSpace) with a proof-of-retreivability (PoRet) — more formally defined as a proof-of-retrievable-commitment (PoRC).
For any PoRep to be secure, the transformed data must be indistinguishable from random, achieved through a proof-of-space. A similar idea is captured by Publically Incompressible Encodings (PIEs) since truly random data is, by definition, information-theoretically incompressible.

Using this framework, we define generic PoAS as:

  • A Nakamoto (longest-chain) consensus protocol
  • Employing a PoC resource puzzle for space-bound sybil resistance
  • Where the space reflects some useful storage (PoRep)
  • And the specific data being replicated is the archival history of the blockchain
11 Likes