.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/consensus/agreement/plot_05_pbft.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_consensus_agreement_plot_05_pbft.py>`
        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_consensus_agreement_plot_05_pbft.py:


Practical Byzantine Fault Tolerance (Castro and Liskov 1999)
============================================================

Castro and Liskov made Byzantine agreement fast enough for real services.
With n = 3f + 1 replicas, every quorum of 2f + 1 overlaps every other in at
least f + 1 replicas, so in at least one honest replica. A replica prepares
a value after 2f matching prepares and commits after 2f + 1 matching
commits; no two honest replicas can commit different values in one view.

What to look for
----------------

With one faulty replica among four, even an equivocating leader cannot make
honest replicas commit different values. With two faulty replicas the
quorums no longer intersect in an honest replica, and safety breaks.
Tendermint, HotStuff and many proof-of-stake chains descend from PBFT.

The history behind this experiment: :doc:`/history/consensus_breakthroughs`.
See :doc:`/exercises/consensus` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 24-26

An equivocating leader, one fault: still safe
---------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 26-34

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    safe = bk.consensus.pbft_round(4, faulty={0}, value="A", equivocate=True)
    print("one faulty leader:", safe.commits)
    assert len({v for v in safe.commits.values() if v}) <= 1





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    one faulty leader: {1: 'A', 2: 'A', 3: None}




.. GENERATED FROM PYTHON SOURCE LINES 35-37

Two faults among four: safety breaks
------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 37-41

.. code-block:: Python

    broken = bk.consensus.pbft_round(4, faulty={0, 1}, value="A", equivocate=True)
    print("two faulty replicas:", broken.commits)
    assert {v for v in broken.commits.values() if v} == {"A", "B"}





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    two faulty replicas: {2: 'A', 3: 'B'}




.. GENERATED FROM PYTHON SOURCE LINES 42-44

Quorum intersection
-------------------

.. GENERATED FROM PYTHON SOURCE LINES 44-57

.. code-block:: Python

    sizes = range(4, 32, 3)
    overlap = [2 * bk.consensus.quorum_size(n) - n for n in sizes]
    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.plot(sizes, overlap, "o-", label="minimum quorum overlap 2(2f+1) - n")
    ax.plot(sizes, [(n - 1) // 3 + 1 for n in sizes], "--", color="black", label="f + 1")
    ax.set(
        xlabel="replicas n = 3f + 1",
        ylabel="replicas",
        title="Two quorums always share an honest replica",
    )
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/consensus/agreement/images/sphx_glr_plot_05_pbft_001.png
   :alt: Two quorums always share an honest replica
   :srcset: /api/gallery/consensus/agreement/images/sphx_glr_plot_05_pbft_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 58-62

Exercise
--------
Why does a replica wait for 2f + 1 commits and not 2f? Find the run where
2f would let two honest replicas commit different values.


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.149 seconds)


.. _sphx_glr_download_api_gallery_consensus_agreement_plot_05_pbft.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/consensus/agreement/plot_05_pbft.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_05_pbft.ipynb <plot_05_pbft.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_05_pbft.py <plot_05_pbft.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_05_pbft.zip <plot_05_pbft.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_