This post will describe the basic strategy of the Spartan proof system for $\text{R1CS}$ constraints and pin-point a key trick which may be useful in other contexts. R1CS The Language $$\mathcal{L}_{\text{R1CS}} := {(\mathbb{F}, A, B, C, x, m, n) | \exists w \text{ s.t. } (Az)\circ (Bz) = Cz, z = (x,1,w) }$$ is $\text{NP}$-complete - i.e. it has enough structure to express arbitrary computations (proof sketch: take a circuit-sat instance and construct a collection of quadratic polynomials over $\mathbb{F}_2$ which are simulatenously satisfiable iff the circuit-sat instance is satisfiable). Here $\mathbb{F}$ is a field (Think scalar field of an elliptic curve $E/\mathbb{F}_p$) $A,B,C$ are $m\times m$ matrices with values in $\mathbb{F}$ with at most $n$ non-zero entries. ($A,B,C$ being square is for convenience) $x$ is a $\mathbb{F}$-vector of dimension $< m$ representing public I/O.

The Data Availability Problem Consider a p2p network of nodes maintaining a replicated state machine (e.g. the Bitcoin network). A full node, by definition, maintains a complete history of the chain from genesis. By replaying included transactions against the current state, such a node can independently verify new transactions. This begins to impose heavy hardware requirements for nodes looking to join the network - As of April 2023, the entire Bitcoin chain is ~475Gb (Growth rate determined by: Block size ~ 1Mb, One block mined every ~ 10 minutes) Light clients, as opposed to full nodes, only download block headers. Taken from the core Bitcoin implementation (note the quintessential copyright (c) 2009-2010 Satoshi Nakamoto), these describe meta-data about the block: /** Nodes collect new transactions into a block, hash them into a hash tree, * and scan through nonce values to make the block's hash satisfy proof-of-work * requirements. When they solve the proof-of-work, they broadcast the block * to everyone and the block is added to the block chain. The first transaction * in the block is a special one that creates a new coin owned by the creator