Skip to content
TheChatArchiveThe Chat Archive
o3-2025-04-16· OpenAIHugging Face LMArena Human Preference 140K

Make a proof of space algorithm

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Coherecommand-a-03-2025’s answer.
  1. User

    Make a proof of space algorithm

  2. 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

    ────────────────────────────

    1. 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 (mmap is convenient).
    • If you need proof-of-space-time (PoST), periodically force the prover to rewrite the plot (e.g., rotate seed every epoch).

    ──────────────────────────── 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 ────────────────────────────

    1. Use a directed-acyclic-graph pebbling construction (e.g., the stacked-expander graph from Ren & Devadas) instead of plain independent rows ⇒ smaller proofs.
    2. Batch-verify multiple MHF calls with a STARK/zk-SNARK ⇒ constant-size proof.
    3. Make the plot additionally useful data (decentralised storage market).
    4. Add verifiable delay (VDF) to convert this PoSpace into full PoST.

    ──────────────────────────── TL;DR ────────────────────────────

    1. Offline: compute N memory-hard hashes, Merkle-commit the table.
    2. Online: on random challenge, reveal k rows + Merkle paths.
    3. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.