.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/network/gossip/plot_03_reliable_broadcast.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_network_gossip_plot_03_reliable_broadcast.py: Byzantine reliable broadcast: echo, then ready (Bracha 1987) ============================================================ A sender broadcasts a value, but it may be Byzantine and tell different peers different things. Bracha's protocol makes delivery consistent anyway: peers *echo* what they received, become *ready* for a value once a large quorum echoed it (or once ``t + 1`` peers are ready for it), and *deliver* once ``2t + 1`` peers are ready. With ``n > 3t``, all correct peers deliver the same value, or none delivers at all. What to look for ---------------- Naively trusting the sender splits the correct peers. Bracha's quorums never do, for any split the faulty sender and its accomplices try, as long as at most a third are faulty. One faulty peer too many breaks agreement. Block gossip uses the same idea: a peer forwards what enough others vouch for. The history behind this experiment: :doc:`/history/network_breakthroughs`. See :doc:`/exercises/network` for a worked solution to the exercise. .. GENERATED FROM PYTHON SOURCE LINES 25-28 An equivocating sender ---------------------- Sender 0 is faulty and tells peers 1-3 "a" and peers 4-6 "b". .. GENERATED FROM PYTHON SOURCE LINES 28-43 .. code-block:: Python import itertools import matplotlib.pyplot as plt import blockchainkit as bk proposals = ["a", "a", "a", "a", "b", "b", "b"] naive = {p: proposals[p] for p in range(1, 7)} print("trust the sender:", naive) assert len(set(naive.values())) == 2 result = bk.network.reliable_broadcast(7, {0}, proposals) print("Bracha:", result.delivered) assert result.agreement and result.totality .. rst-class:: sphx-glr-script-out .. code-block:: none trust the sender: {1: 'a', 2: 'a', 3: 'a', 4: 'b', 5: 'b', 6: 'b'} Bracha: {1: None, 2: None, 3: None, 4: None, 5: None, 6: None} .. GENERATED FROM PYTHON SOURCE LINES 44-47 Every split, every set of faulty peers -------------------------------------- Check all faulty sets of size up to t and all ways to split the peers. .. GENERATED FROM PYTHON SOURCE LINES 47-63 .. code-block:: Python outcomes = {"all deliver": 0, "none deliver": 0, "disagree": 0} for faulty in itertools.chain.from_iterable(itertools.combinations(range(7), f) for f in (1, 2)): if 0 not in faulty: continue for split in itertools.product("ab", repeat=7): r = bk.network.reliable_broadcast(7, faulty, list(split)) delivered = set(r.delivered.values()) if not r.agreement: outcomes["disagree"] += 1 elif delivered == {None}: outcomes["none deliver"] += 1 else: outcomes["all deliver"] += 1 print(outcomes) assert outcomes["disagree"] == 0 .. rst-class:: sphx-glr-script-out .. code-block:: none {'all deliver': 856, 'none deliver': 40, 'disagree': 0} .. GENERATED FROM PYTHON SOURCE LINES 64-68 One faulty peer too many ------------------------ With n = 4 the protocol tolerates t = 1. Two colluding faulty peers can make each correct peer see a different echo quorum. .. GENERATED FROM PYTHON SOURCE LINES 68-77 .. code-block:: Python broken = bk.network.reliable_broadcast(4, {0, 3}, ["a", "a", "b", "b"]) print(broken.delivered) assert not broken.agreement fig, ax = plt.subplots(figsize=(6, 3.5)) ax.bar(outcomes.keys(), outcomes.values(), color=["#16a34a", "#94a3b8", "#dc2626"]) ax.set(ylabel="runs", title="n = 7, faulty sender plus up to one accomplice") fig.tight_layout() .. image-sg:: /api/gallery/network/gossip/images/sphx_glr_plot_03_reliable_broadcast_001.png :alt: n = 7, faulty sender plus up to one accomplice :srcset: /api/gallery/network/gossip/images/sphx_glr_plot_03_reliable_broadcast_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none {1: 'a', 2: 'b'} .. GENERATED FROM PYTHON SOURCE LINES 78-84 Exercise -------- The echo threshold is ``ceil((n + t + 1) / 2)``. Show that two sets of that size among n peers share at least ``t + 1`` peers, so at least one correct peer, which echoes only one value. What goes wrong with a simple majority threshold? .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.166 seconds) .. _sphx_glr_download_api_gallery_network_gossip_plot_03_reliable_broadcast.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/network/gossip/plot_03_reliable_broadcast.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_03_reliable_broadcast.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_03_reliable_broadcast.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_03_reliable_broadcast.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_