.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/consensus/attacks/plot_01_gamblers_ruin.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_attacks_plot_01_gamblers_ruin.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_attacks_plot_01_gamblers_ruin.py:


The gambler's ruin: catching up from behind (Pascal, Fermat and Huygens 1656)
=============================================================================

Pascal posed, and Huygens published, the problem of a gambler who wins each
round with probability q and stops when ruined or ahead. The chance of ever
recovering a deficit of z is (q/p)**z when q < p. Nakamoto used exactly
this random walk for an attacker trying to overtake the honest chain from z
blocks behind.

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

Simulated random walks match (q/p)**z. An attacker with less than half the
hashrate falls exponentially further from success with every block of lead,
and at q = 1/2 the walk always catches up eventually.

The history behind this experiment: :doc:`/history/consensus_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 22-24

Simulate the race
-----------------

.. GENERATED FROM PYTHON SOURCE LINES 24-56

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk


    def caught_up(q, deficit, rng, horizon=500):
        for _ in range(horizon):
            if deficit <= 0:
                return True
            deficit += -1 if rng.random() < q else 1
        return deficit <= 0


    rng = Random(1656)
    deficits = range(0, 9)
    fig, ax = plt.subplots(figsize=(7, 4))
    for q, color in ((0.1, "#2563eb"), (0.25, "#16a34a"), (0.4, "#ea580c")):
        simulated = [sum(caught_up(q, z, rng) for _ in range(2000)) / 2000 for z in deficits]
        exact = [bk.consensus.eventual_catch_up(q, z) for z in deficits]
        assert all(abs(a - b) < 0.04 for a, b in zip(simulated, exact, strict=True))
        ax.semilogy(deficits, exact, "-", color=color, label=f"q = {q}: (q/p)**z")
        ax.semilogy(deficits, [max(s, 1e-4) for s in simulated], "o", color=color)
    ax.set(
        xlabel="blocks behind z",
        ylabel="probability of ever catching up",
        title="Exponentially unlikely, unless q >= 1/2",
    )
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/consensus/attacks/images/sphx_glr_plot_01_gamblers_ruin_001.png
   :alt: Exponentially unlikely, unless q >= 1/2
   :srcset: /api/gallery/consensus/attacks/images/sphx_glr_plot_01_gamblers_ruin_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 57-59

.. code-block:: Python

    assert bk.consensus.eventual_catch_up(0.5, 20) == 1.0








.. GENERATED FROM PYTHON SOURCE LINES 60-65

Exercise
--------
The model assumes the race never ends. Why does that make (q/p)**z an
overestimate of the attacker's chances against a merchant who waits only
for z confirmations? (The next example answers this.)


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

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


.. _sphx_glr_download_api_gallery_consensus_attacks_plot_01_gamblers_ruin.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/attacks/plot_01_gamblers_ruin.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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