Episode I — The Hitchhiker’s Guide to Subspace

An introductory guide for those seeking to understand the technical details of our v2 consensus, which constructs proofs-of-replication and proofs-of-archival-storage (among several other exciting things!) from polynomial schemes such as Reed-Solomon erasure codes and Kate-Zaverucha-Goldberg (KZG) commitments. This work is also a starting point for our version of The Hitchhiker’s Guide to Ethereum.

Special thanks to our Research Engineer, Dariia Porechna, for proofreading and adding examples to this article, and our Research Partner, Dr. Chen Feng, for proofreading.

Introduction

As part of our transition to v2 consensus (now called Dilithium, stay tuned!), we took a hard look at polynomial schemes and their applications and concluded (as have many others in the industry) that these primitives will be as central to the next decade of blockchain design as hash functions, Merkle trees, and ECC signatures have been to the last decade. Moreover, I firmly believe that Subspace is uniquely positioned to employ these primitives more naturally and effectively than any other project.

This is an accidental yet fortuitous result of our proof-of-archival-storage (PoAS) consensus and its novel mechanism for dynamically adjusting the cost of blockspace. The permissionless nature of farming and the dynamic cost of storage on our chain create a positive feedback loop, or flywheel, which allows the Subspace Network to scale in step with demand, such that the cost of blockspace remains constant. Polynomial schemes will allow us to more easily achieve linear scaling in the blockspace proportional to the number of farmers on our network than we had ever imagined.

We employ two specific polynomial-based schemes in our v2 consensus, Reed-Solomon (RS) erasure coding and Kate-Zaverucha-Goldberg (KZG) commitments. RS codes treat some useful data as a polynomial, allowing us to “extend” the data such that we can efficiently recover the data in the presence of either errors (communication) or erasures (storage). KZG commitments also treat the data as a polynomial, allowing us to create a tiny fingerprint of some larger data set (or file) and efficiently prove that any subset of the data matches the fingerprint (sometimes referred to as a Kate proof or witness).

The key takeaway is that both RS and KZG treat the underlying data as a polynomial, albeit for different reasons, but with exciting and often complementary side effects that we may compose into more extensive protocols.

What can you do with Polynomials?

Below is a taste of the exciting things now possible with polynomial schemes. These methods are currently being explored for ETH upgrades, Polygon Avail, and nearly all Zero-Knowledge (ZK) protocols. Additionally, it is important (and exciting) to note that new schemes and applications are still being discovered, and there is still plenty of room for imagination for protocol designers.

• Employing KZG as a vector commitment may replace Merkle proofs in many schemes, allowing a reduction of the proof size from logarithmic to constant, typically 48 bytes.
• As noted in a recent paper, KZG-based polynomial commitment schemes (PCS) have become an essential ingredient for zkSNARKs such as SONIC, Marlin, DARK, and PLONK. As a result, there are already several efficient implementations of the underlying KZG primitives and various reusable aggregation (batch proofs) techniques.
• If we use RS to erasure code some data, say a block, and commit to the block data using KZG, we can succinctly prove that an erasure-coded block fragment belongs to the original commitment. This could be a Zero-Knowledge (ZK) proof of correct erasure coding.
• We can leverage the information above to obviate the need for fraud proofs in 2D-RS schemes, such as those used by Celestia. This is primarily the direction ETH upgrades and Polygon Avail have gone for light client Data Availability Sampling (DAS) schemes.
• Various 2D-RS-KZG constructions can remove the scalability bottleneck of restricting the block size to the expected network bandwidth of the single block producer, as proposed (and later revised) for ETH data sharding upgrades.
• KZG commitments may be used to manage not only the history of a blockchain (as described above) but also the state database of user and contract accounts through a “stateless” database, significantly reducing the storage overhead of full nodes. Ethereum plans to employ Verkle trees (KZG-VC-based Merkle trees) and is also exploring the use of [aggregatable subvector commitments](https://eprint.iacr.org/2020/527#:~:text=An aggregatable subvector commitment (aSVC,from constant-sized polynomial commitments.) built from KZG.