.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/channels/coding/plot_02_data_availability_sampling.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_channels_coding_plot_02_data_availability_sampling.py: 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. .. GENERATED FROM PYTHON SOURCE LINES 22-27 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk from blockchainkit.channels.visualizers import plot_detection .. GENERATED FROM PYTHON SOURCE LINES 28-32 Withholding just enough to block recovery ----------------------------------------- 32 data symbols extend to 64 shares; any 32 rebuild the block, so the producer must withhold 33. .. GENERATED FROM PYTHON SOURCE LINES 32-45 .. code-block:: Python 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 .. rst-class:: sphx-glr-script-out .. code-block:: none 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 .. GENERATED FROM PYTHON SOURCE LINES 46-50 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. .. GENERATED FROM PYTHON SOURCE LINES 50-59 .. code-block:: Python 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) .. rst-class:: sphx-glr-script-out .. code-block:: none clients needed to collect 32 distinct shares: 23 .. GENERATED FROM PYTHON SOURCE LINES 60-64 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. .. GENERATED FROM PYTHON SOURCE LINES 64-85 .. code-block:: Python 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() .. image-sg:: /api/gallery/channels/coding/images/sphx_glr_plot_02_data_availability_sampling_001.png :alt: Data-availability sampling, Sampling clients rebuild the block :srcset: /api/gallery/channels/coding/images/sphx_glr_plot_02_data_availability_sampling_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none fraud proof size: 33 shares of 64 .. GENERATED FROM PYTHON SOURCE LINES 86-92 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``? .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.084 seconds) .. _sphx_glr_download_api_gallery_channels_coding_plot_02_data_availability_sampling.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/channels/coding/plot_02_data_availability_sampling.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_02_data_availability_sampling.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_02_data_availability_sampling.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_02_data_availability_sampling.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_