Demystifying proofs of storage

The Math, Step by Step

Grab a pencil. This is the S-PDP scheme from Ateniese et al. (2007). It is not the scheme Pinion uses, but it shares the same core ideas, and the arithmetic is small enough to follow by hand. Pinion’s own scheme is described in the next section. Consider this a warm-up.

The real protocol requires RSA moduli of 2048 bits or more. We are using a toy modulus of 77 so the numbers fit on paper. The mathematics is correct; the parameters are not production-safe.

p = 7,   q = 11        (7 = 2×3+1, 11 = 2×5+1, both safe primes)
N = 7 × 11 = 77
φ = ((7−1)/2) × ((11−1)/2) = 3 × 5 = 15

g = 4    (order 15 in QR₇₇: 4¹⁵ ≡ 1 mod 77, no smaller power is 1)

e = 7,   d = 13        (7 × 13 = 91 = 6×15 + 1, so 7×13 ≡ 1 mod 15 ✓)

Public key:  (N = 77, g = 4, e = 7)
Private key: d = 13   ← keep this secret

m₁ = 10
m₂ = 7
m₃ = 15
m₄ = 9

Some powers of g = 4 mod 77:
  4¹  = 4
  4²  = 16
  4⁴  = 256 mod 77 = 25    (256 = 3×77 + 25)
  4⁸  = 25² = 625 mod 77 = 9    (625 = 8×77 + 9)
  4¹² = 4⁸ × 4⁴ = 9 × 25 = 225 mod 77 = 71    (225 = 2×77 + 71)

Tag for each block (exponent = mᵢ × 13 mod 15):
  T₁: 10×13 mod 15 = 130 mod 15 = 10  →  4¹⁰ = 4⁸×4² = 9×16 = 144 mod 77 = 67
  T₂:  7×13 mod 15 =  91 mod 15 =  1  →  4¹ = 4
  T₃: 15×13 mod 15 = 195 mod 15 =  0  →  4⁰ = 1
  T₄:  9×13 mod 15 = 117 mod 15 = 12  →  4¹² = 71

Tags: T₁=67, T₂=4, T₃=1, T₄=71

Challenge: { blocks = {1, 2},  coefficients = {a₁=3, a₂=5} }

T_agg = T₁^a₁ × T₂^a₂ mod N = 67³ × 4⁵ mod 77

  67²  = 4489 mod 77 = 23       (4489 = 58×77 + 23)
  67³  = 23 × 67 = 1541 mod 77 = 1     (1541 = 20×77 + 1)
  4⁵   = 4⁴ × 4 = 25×4 = 100 mod 77 = 23

  T_agg = 1 × 23 = 23

μ = a₁×m₁ + a₂×m₂ = 3×10 + 5×7 = 30 + 35 = 65

Server returns: { T_agg = 23,  μ = 65 }

With h(Wᵢ) = 1, the right side is g^(μ mod φ):
  μ mod φ = 65 mod 15 = 5
  g⁵ = 4⁵ = 23

Left side: T_agg^e mod N = 23⁷ mod 77
  23²  = 529 mod 77 = 67       (529 = 6×77 + 67)
  23⁴  = 67² = 4489 mod 77 = 23
  23⁷  = 23⁴ × 23² × 23 = 23 × 67 × 23
       = 23 × 1541 mod 77
       = 23 × 1 = 23           (1541 = 20×77 + 1)

Left side = 23.   Right side = 23.   ✓

Key Papers

If you want to go deeper, these are the papers to read. Most are freely available on eprint.iacr.org. We also published our own construction for IPFS:

Pinion’s Protocol: Why Publicly Verifiable POR

The walk-through above uses the Ateniese S-PDP scheme, a privately verified PDP. It is a good introduction to the problem category: you can see how tags are computed, how a challenge specifies which blocks to inspect, and how the verification equation closes. Pinion’s implementation makes different choices in both the class of scheme and several engineering details. This section explains what those choices are and why we made them.

The scheme Pinion uses by default is a publicly verifiable Proof of Retrievability (POR). We chose it for four reasons.

Unlimited challenges

Some protocols in the literature impose a maximum number of verification rounds. The limit comes from how the protocol constructs its tags: once you exhaust the challenge budget, the scheme offers no further guarantees. For Pinion’s default, we wanted clients to be able to challenge us as many times as they like. The scheme we use supports unlimited rounds with no degradation in the security guarantee.

IPFS-compatible data layout

Some protocols require the data to be erasure-coded before tagging, or rely on an authenticated skip list for update verification, or depend on a specific sequential block layout. Each of those requirements adds complexity and constrains what content can be covered. The protocol we selected for our default works directly with the Merkle DAG structure that IPFS uses. Any content that can be pinned can be tagged and challenged without transformation or a special storage layout.

Default protocol and advanced use

Everything described above is Pinion’s default. If you interact with the prover through the dashboard or the standard API, this is the protocol in use.

Advanced API users may specify a different protocol. The storage-proofs library implements a superset of the protocols Pinion supports. Two protocols in the library are not suitable for IPFS content: bjo requires erasure-coded data before tagging, which is impractical for a general pinning service. erwayis built around an authenticated skip list for mutable data, which conflicts with IPFS’s intentionally immutable Merkle DAGs and our CID-based sparse-array implementation.

In the default arrangement, Pinion generates the keypair, computes tags using the server-held private key, and stores them. Most users will not need to change this. If you have a specific requirement to hold your own private key, you can generate tags client-side using the storage-proofs library and register them with Pinion via the API. The challenge and verification flow is identical; only key custody changes.

From Theory to IPFS: Block Layout and the Sparse Array Problem

One of the first things to tackle for proof of storage on IPFS is the data layout. The academic schemes treat a file as a flat, sequentially indexed array of blocks. IPFS does not.

We considered a few approaches. One option was to work at the UnixFS layer and project each file into a numbered block array. UnixFS organizes file data as a DAG of chunks, and for simple files this lines up reasonably well. But not all pinned content is a UnixFS file. CAR archives can contain arbitrary DAG structures with no natural linear ordering, and shared blocks (two roots that include the same leaf CID) would be duplicated or mis-indexed under any sequential numbering scheme.

CIDs as a sparse array

The approach that held up was to treat the CID space as a sparse array. A CID is a multihash of the block contents. The space of all possible CIDs is astronomically large, but for any given root, walking the DAG produces the finite populated set. Each block has a unique CID by construction.

Whether this works for a given proof-of-storage protocol depends on how block identifiers are used in the math. Some schemes use the block index as an integer in the field arithmetic, for example to step through a polynomial evaluation or build a Merkle path. Those schemes expect indices like 1, 2, 3 and cannot accept arbitrary byte strings without a redesign of the core protocol.

When the math works out

In the Ateniese scheme and in the Shacham-Waters scheme, block identifiers appear only as inputs to a pseudorandom function (PRF) or a hash function. The per-block tag in Ateniese (from the code in our storage-proofs repository) is computed as:

where idi can be any byte string. Using a CID as id_i is mathematically identical to using a sequential integer, because h maps its input to a quadratic residue of N regardless of what went in. CID bytes flow into the hash; the hash output is a group element; the tag computation and verification equation are unaffected.

The same holds for the Shacham-Waters scheme and its publicly verifiable variant. Block indices appear inside PRF calls, not in arithmetic over the field. Substituting CID bytes for sequential integers preserves all security properties of both schemes.

This does not work for every proof-of-storage protocol. Schemes that require the index to be a field element in a polynomial evaluation, or that need the index to be small relative to the field size, cannot absorb arbitrary CID bytes without modification. The compatibility depends on where the index appears in the math, and for the schemes Pinion implements, the math works out.

Selecting blocks from a sparse set

Choosing a uniform random subset of blocks from an arbitrary set of CIDs requires a different approach than picking n integers in the range [0, count). Pinion’s implementation uses a keyed hash-sort: each block ID is ranked by HMAC-SHA256(idxKey, cid), and the top n by rank become the challenged set. idxKey is derived from the challenge seed, so the selection is deterministic from the seed and uniform across block IDs of any format.

Indexing past the block: proving specific bytes

CID-as-sparse-array-index is the whole story for the CID-addressed protocols (Ateniese, Erway, BJO): a challenge names real IPFS block CIDs, and possession is proven at the granularity IPFS already hands us, whole blocks. Pinion’s default protocol goes one level deeper. Rather than stopping at “does the server have this block,” it virtualizes every block’s content into fixed-size super-blocks, byte ranges within the block, and challenges those directly. A super-block’s id is not a CID at all: it’s the root’s CID with an 8-byte position appended, id = rootCID ∥ localIndex. Both sides compute a super-block’s byte range the same way, from its position and a fixed super-block size, so a challenge can name a specific slice of bytes inside a specific block without any manifest ever being transmitted, the id is derivable from the root CID plus an integer, nothing else.

This is a materially finer-grained claim than “the block with this hash exists.” It means a challenge can sample arbitrary byte ranges scattered across a large file, a much stronger statement about actually holding the content than spot-checking whole blocks would be, since a large IPFS block can otherwise hide a lot of missing data behind one intact CID.

One challenge, many files

Because a super-block id already carries its root CID as a prefix, super-blocks from entirely different pinned roots can share one index space with no collisions. That means a single challenge is not scoped to one file: it can sample bytes from several independently pinned pieces of content at once, and the response is a single proof covering all of them together. Most proof-of-storage protocols in the literature are defined over one store at a time, one file, one proof. Pinion’s default lets you fold an arbitrary number of tagged roots under one key into a single audit round, and, as the next section shows, the proof you get back does not grow with how many files you included.

Compact Challenges from a Single Seed

Each audit round starts with a fresh random 32-byte seed S. Everything about the challenge, which blocks to sample and with what coefficients, is derived from that seed using HMAC-SHA256:

This derivation is the reason the challenge message is so small. The client sends Pinion a 32-byte seed and an integer specifying how many blocks to sample. That is the entire challenge on the wire: 32 + 4 bytes, regardless of how many total blocks are in scope. Pinion reconstructs the full challenge set from the seed using the same derivation.

The proof response is similarly compact, and the reason why is concrete rather than magic. A proof is one accumulated elliptic curve point σ (64 bytes) plus a vector μ of s scalars (32 bytes each), where s is the number of sectors each block is split into for accumulation, a parameter fixed once when the key was created, not something that changes per challenge. Every challenged block folds into the same s running scalars rather than contributing its own; that is what keeps the total proof size at 64 + 32s bytes whether the round samples 100 blocks or 10,000. It also holds across the multi-root case from the previous section: folding in super-blocks from a second or third pinned root adds more terms to the same accumulation, not more output. One proof, fixed size, no matter how many blocks or how many separate files went into the challenge.

The stateless property also matters. Both sides can independently reproduce which blocks were challenged and with what coefficients, from the seed alone. No shared state and no coordination beyond passing the seed. A fresh seed each round produces a fresh, unpredictable challenge each round.

The Math of Catching a Lie

Here’s the key theorem. If a fraction p of your blocks are sampled each round, and each round is independent, then after k rounds your confidence that no corruption has gone undetected is:

Each round is independent, like asking about a different random page each time. The probability of missingcorruption multiplies: if you have a 10% chance of catching it each round, after 10 rounds you’ve had 10 independent shots at it, and the chance of missing all of them is only 0.9¹⁰≈ 35%. After 44 rounds at 10% sampling, you’re above 99% confidence.

The exponential convergence means you do not need to download the file to trust it. Keep asking, and the math accumulates the rest.

Challenge Us

Here’s the part that distinguishes a proof system from a promise: the POST /prover/prove endpoint requires no authentication. Anyone who obtains a client setup and a list of block IDs can issue a challenge and verify the response locally, with no Pinion involvement in the verification step.

Any Pinion account holder can share their key_id with you. Call GET /prover/api/v1/setup?key_id=<id> and you get back everything you need to construct and verify a challenge.

# 1. Get the client setup and block list
curl https://<env>.pinion.build/prover/api/v1/setup?key_id=<key_id>

# 2. Derive a challenge from a fresh random seed (client-side, offline)
#    → produces: challenge bytes + a local validator

# 3. Submit the challenge (no authentication needed)
curl -X POST https://<env>.pinion.build/prover/prove \
  -H "Content-Type: application/json" \
  -d '{"key_id": "<key_id>", "roots": [], "challenge": <base64>}'

# 4. Verify the proof locally against your validator
#    → true = data intact | false = tampering detected

Our storage-proofs benchmark site shows how each protocol implementation compares to theoretical predictions from the papers: detection probability curves measured against simulated corruption scenarios, timing data for setup, prove, and verify operations, and extraction success rates across varying file sizes. The curves there are the same formula as the graph above, measured rather than modeled.