Fraud proofs and data-availability sampling (Al-Bassam, Sonnino and Buterin, 2018)

A light client cannot download every block, so it relies on full nodes to prove fraud. That fails if the block producer publishes a header but withholds part of the data: nobody can then prove anything about it. Al-Bassam, Sonnino and Buterin extend the data with a Reed-Solomon code, so that any half of the shares rebuilds the block. To hide even one transaction the producer must withhold more than half of the shares, and a client sampling s random shares notices with probability

\[1 - \left(1 - f\right)^s, \qquad f > \tfrac{1}{2}.\]

If the producer instead publishes shares that are not a codeword, an encoding fraud proof of k + 1 shares exposes it.

import matplotlib.pyplot as plt

import blockchainkit as bk
from blockchainkit.channels.visualizers import plot_detection

Withholding just enough to block recovery

32 data symbols extend to 64 shares; any 32 rebuild the block, so the producer must withhold 33.

data = list(range(100, 132))
block = bk.channels.extend(data)
withheld = set(range(31, 64))
assert len(block.shares) - len(withheld) == block.k - 1

for samples in (1, 4, 8, 15):
    result = bk.channels.simulate_sampling(
        block, withheld, clients=500, samples=samples, seed=samples
    )
    print(f"{samples:2d} samples: {result.detected:.3f} of clients detect withholding")
assert result.detected > 0.999

 1 samples: 0.516 of clients detect withholding
 4 samples: 0.940 of clients detect withholding
 8 samples: 0.998 of clients detect withholding
15 samples: 1.000 of clients detect withholding

Many clients rebuild an honest block

Every share a client downloads is also served to the network, so enough clients collect a half between them.

clients = range(1, 41)
collected = [
    bk.channels.simulate_sampling(block, (), clients=c, samples=2, seed=1).collected
    for c in clients
]
enough = next(c for c, total in zip(clients, collected, strict=True) if total >= block.k)
print("clients needed to collect 32 distinct shares:", enough)

clients needed to collect 32 distinct shares: 23

An encoding fraud proof

A producer who changes one parity share commits to a root that no single polynomial explains; k + 1 shares with their Merkle proofs show it.

bad_shares = list(block.shares)
bad_shares[40] += 1
bad = bk.channels.commit_shares(block.k, tuple(bad_shares))
proof = bk.channels.encoding_fraud_proof(bad)
assert proof is not None and proof.positions[-1] == 40
assert bk.channels.verify_encoding_fraud_proof(proof, bad.root, block.k)
assert not bk.channels.verify_encoding_fraud_proof(proof, block.root, block.k)
print("fraud proof size:", len(proof.shares), "shares of", len(bad_shares))

fig, (left, right) = plt.subplots(1, 2, figsize=(11, 4))
plot_detection(range(1, 16), withheld=(0.25, 33 / 64), ax=left)
right.plot(clients, collected, "o-", color="#2563eb", markersize=3)
right.axhline(block.k, color="#dc2626", linestyle="--", label="k = 32: enough to rebuild")
right.set(xlabel="light clients, 2 samples each", ylabel="distinct shares collected")
right.set_title("Sampling clients rebuild the block")
right.legend()
fig.tight_layout()

plt.show()

fraud proof size: 33 shares of 64

Exercise

The paper’s two-dimensional code arranges k * k data symbols in a square and extends every row and column, so a fraud proof needs only one row of 2k shares. How large is a one-dimensional fraud proof for the same data, and how does the ratio grow with k?