r"""
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

.. math::

   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

# %%
# 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)

# %%
# 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()

# %%
# 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``?