.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/channels/scaling/plot_02_omniledger_sharding.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_scaling_plot_02_omniledger_sharding.py: OmniLedger and sharding (Kokoris-Kogias et al., 2018) ===================================================== Splitting validators into shards multiplies throughput, but each shard is only as safe as its own committee. OmniLedger reshuffles validators into shards every epoch from unbiasable randomness, so an adversary cannot concentrate its validators in one committee. A committee of ``m`` drawn from ``N`` validators, ``M`` of them malicious, fails if a third or more of it is malicious, which is a hypergeometric tail: .. math:: P(X \ge m/3) = \sum_{x \ge m/3} \frac{\binom{M}{x}\binom{N-M}{m-x}}{\binom{N}{m}}. Payments that span shards use Atomix: lock every input, then commit on the output shard if all inputs were accepted, or unlock them all. .. GENERATED FROM PYTHON SOURCE LINES 22-26 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk .. GENERATED FROM PYTHON SOURCE LINES 27-29 How large must a shard be? -------------------------- .. GENERATED FROM PYTHON SOURCE LINES 29-37 .. code-block:: Python validators, adversary = 1_800, 450 # A quarter of all validators. sizes = [10, 25, 50, 100, 200, 300, 450, 600] exact = [bk.channels.shard_failure_probability(validators, adversary, m) for m in sizes] for m, p in zip(sizes, exact, strict=True): print(f"shard of {m:3d}: fails with probability {p:.2e}") assert exact[-1] < 1e-6 < exact[3] .. rst-class:: sphx-glr-script-out .. code-block:: none shard of 10: fails with probability 2.24e-01 shard of 25: fails with probability 1.48e-01 shard of 50: fails with probability 9.52e-02 shard of 100: fails with probability 2.41e-02 shard of 200: fails with probability 2.63e-03 shard of 300: fails with probability 2.34e-04 shard of 450: fails with probability 2.52e-06 shard of 600: fails with probability 8.53e-09 .. GENERATED FROM PYTHON SOURCE LINES 38-40 Simulated epochs match the formula ---------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 40-52 .. code-block:: Python shards = [18, 9, 6] # Committees of 100, 200 and 300. simulated = [ bk.channels.compromised_epochs(validators, adversary, s, epochs=400, seed=s) for s in shards ] predicted = [ 1 - (1 - bk.channels.shard_failure_probability(validators, adversary, validators // s)) ** s for s in shards ] print("some shard compromised per epoch:", simulated, "predicted about", predicted) assert abs(simulated[0] - predicted[0]) < 0.05 .. rst-class:: sphx-glr-script-out .. code-block:: none some shard compromised per epoch: [0.3675, 0.025, 0.0] predicted about [0.35590430878510304, 0.023451848156125332, 0.001404365406948882] .. GENERATED FROM PYTHON SOURCE LINES 53-55 Atomix: all inputs or none -------------------------- .. GENERATED FROM PYTHON SOURCE LINES 55-78 .. code-block:: Python balances = [{"alice": 30}, {"alice": 20}, {}] ok = bk.channels.atomix_transfer(balances, [(0, "alice", 30), (1, "alice", 20)], (2, "bob")) short = bk.channels.atomix_transfer(balances, [(0, "alice", 30), (1, "alice", 25)], (2, "bob")) assert ok.committed and dict(ok.balances[2]) == {"bob": 50} assert not short.committed and [dict(b) for b in short.balances] == balances fig, ax = plt.subplots(figsize=(8, 4)) ax.semilogy(sizes, exact, "o-", color="#2563eb", label="25% adversary") ax.semilogy( sizes, [bk.channels.shard_failure_probability(validators, 540, m) for m in sizes], "s-", color="#dc2626", label="30% adversary", ) ax.set(xlabel="validators per shard", ylabel="chance a shard is a third malicious") ax.set_title("Larger committees are exponentially safer") ax.legend() fig.tight_layout() plt.show() .. image-sg:: /api/gallery/channels/scaling/images/sphx_glr_plot_02_omniledger_sharding_001.png :alt: Larger committees are exponentially safer :srcset: /api/gallery/channels/scaling/images/sphx_glr_plot_02_omniledger_sharding_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 79-85 Exercise -------- With 1,800 validators and a 25% adversary, how many shards can the network run while keeping the chance that *any* shard fails in an epoch below one in a million? What happens as the adversary nears a third? A worked solution is in :doc:`/exercises/channels`. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.477 seconds) .. _sphx_glr_download_api_gallery_channels_scaling_plot_02_omniledger_sharding.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/scaling/plot_02_omniledger_sharding.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_02_omniledger_sharding.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_02_omniledger_sharding.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_02_omniledger_sharding.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_