Make a proof of space algorithm
- User
Make a proof of space algorithm
- Assistant
Below is a minimalist but complete Proof-of-Space (PoS) scheme that you can lift into real code (Python-like pseudo-code is included).
It is not the most storage-efficient construction in academia, but it is simple, self-contained, and already captures the essential security intuition:• The prover must pre-compute and store a large table (“plot”) to answer future challenges in (quasi) real time.
• Re-computing on-the-fly is intentionally expensive because every table entry is derived with a memory-hard hash.
• The verifier can audit any single challenge in O(log N) time and O(1) space by using a Merkle root commitment.──────────────────────────── High-level flow ──────────────────────────── ┌─────────┐ setup / “plotting” │ Prover │────────────────────────────────────────────────────┐ └─────────┘ │ ▲ │ │ challenge / response ▼ ┌─────────┐ ───────────────────────────────────────▶ ┌────────────┐ │Verifier │ │Blockchain /│ └─────────┘ ◀─────────────────────────────────────── │ network │ └────────────┘
──────────────────────────── Notation ──────────────────────────── H(x) : Blake3(x) (fast)
MHF(x) : Argon2id(x, m_cost=2 MiB, t_cost=1) ← 2 MiB RAM & ~2 ms/CPU
⊕ : XOR
∥ : byte concatenation
N : 2ᴱ table rows (E = table exponent, e.g., E = 30 ⇒ 1 Gi rows)
k : Number of indices the verifier will challenge per proof (e.g., 64)
seed : 32-byte random chosen by the prover once during plotting────────────────────────────
- Plotting phase (offline, one-time cost) ──────────────────────────── Goal: Fill an N-row table T so that recreating any single row without all (or most) previous rows is as expensive as the initial plot. Then commit to a Merkle root R.
Pseudo-code
function Plot(seed, N): for i in 0 .. N-1: // 1. Derive raw data with a memory-hard function raw = MHF(seed ∥ LE64(i)) // costs RAM & time // 2. Compress to 32 B using cheap hash to save space T[i] = H(raw) // 3. Wrap the whole table in a Merkle tree R = MerkleRoot(T) persist_to_disk(T, R, seed) return R // commitment sent to the network
Disk-footprint: N × 32 B (e.g. N = 2³⁰ ≈ 1 Gi rows ⇒ 32 GiB plot)
──────────────────────────── 2. Online phase – generating a proof for challenge c ──────────────────────────── Assume the network (or the next block header) issues a random 32-byte challenge chal. Derive k pseudo-random indices, grab those rows from the plot, and attach their Merkle authentication paths.
function Prove(chal, T, seed, R): // Map chal into k indices with a stream cipher-like construction PRNG = ChaCha20(key=chal, nonce=0) idxes = [] // length k for j in 0..k-1: idxes.append(PRNG.next_u64() mod N)
proof_elems = [] for idx in idxes: value = T[idx] path = MerklePath(T, idx) // O(log N) sibling hashes proof_elems.append((idx, value, path)) return { R, seed, proof_elems }Size of a proof
≈ k × (32 B value + 32 B × log₂N sibling hashes)
For N=2³⁰ (log₂N = 30) and k=64 → ≈ 64 × (32 + 32×30) ≈ 64 KiB.──────────────────────────── 3. Verification ──────────────────────────── function Verify(chal, R, seed, proof_elems): PRNG = ChaCha20(key=chal, nonce=0) for j in 0..k-1: expected_idx = PRNG.next_u64() mod N (idx, value, path) = proof_elems[j] if idx ≠ expected_idx: return reject // Re-compute memory-hard row from scratch raw = MHF(seed ∥ LE64(idx)) // attacker must pay this once if H(raw) ≠ value: // ensures correct value return reject if MerkleVerify(R, idx, value, path) = false: return reject return accept
──────────────────────────── Why does the prover need the disk? ──────────────────────────── • To answer with k=64 rows fast (within, say, <1 s) the prover would have to recompute k×MHF evaluations in real time.
Each MHF call grabs 2 MiB of RAM and ≈2 ms CPU ⇒ 64×2 ms = 128 ms per proof
– still doable – but in most PoSpace deployments k is set larger (128…512).• More importantly, when the network can fire challenges back-to-back (or in parallel), the prover’s CPU-RAM bottleneck becomes overwhelming unless the full plot is cached on disk.
• Because the verifier checks at least one MHF call per challenged row, any prover who tries to store only a fraction α of the plot faces an unavoidable cost blow-up proportional to (1-α)×k×MHF.
──────────────────────────── Security parameters at a glance ──────────────────────────── E = 30 # 1 Gi entries ≈ 32 GiB plot
k = 128 # 128 random indices per proof
MHF memory = 2 MiB, time ≈2 ms on desktop CPU
Proof size ≈ k × (32+32×E) ≈ 128×(32+960) ≈ 127 KiB
Verifier work = k×(MHF+log N hashes) ≈ 128×(2 ms + 30 µs) ≈ 260 ms──────────────────────────── Porting to real code ──────────────────────────── • Substitute Argon2id with any well-tested MHF (Argon2, scrypt-N, Lyra2).
• Blake3 is an attractive 32-B digest; SHA-256 works too.
• Use an incremental Merkle tree library; Blake3 supports that natively.
• Persist the plot in append-only chunks (mmapis convenient).
• If you need proof-of-space-time (PoST), periodically force the prover to rewrite the plot (e.g., rotateseedeveryepoch).──────────────────────────── How this compares with “big-name” projects ──────────────────────────── Chia (k-plots) – Uses a much more storage-optimised bit-shuffle plot with no memory-hard hash at proof time; verification is lightweight (≈μs). Far more engineering.
Filecoin – Employs Proof of Replication + PoSpace + SNARKs to seal data and yield succinct on-chain proofs.
SpaceMint / Burst – Academic & niche coins derived from very similar “hash-then-Merkle” ideas as the toy scheme above.──────────────────────────── Possible extensions ────────────────────────────
- Use a directed-acyclic-graph pebbling construction (e.g., the stacked-expander graph from Ren & Devadas) instead of plain independent rows ⇒ smaller proofs.
- Batch-verify multiple MHF calls with a STARK/zk-SNARK ⇒ constant-size proof.
- Make the plot additionally useful data (decentralised storage market).
- Add verifiable delay (VDF) to convert this PoSpace into full PoST.
──────────────────────────── TL;DR ────────────────────────────
- Offline: compute N memory-hard hashes, Merkle-commit the table.
- Online: on random challenge, reveal k rows + Merkle paths.
- Verifier recomputes each row’s MHF once and checks the Merkle root.
Holding the plot saves you ≈k×(MHF-time) per challenge – otherwise the prover is quickly overwhelmed; that economic mismatch underlies the security of Proof of Space.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.