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


How many confirmations? Nakamoto's double-spend calculation (2008)
==================================================================

Section 11 of the Bitcoin whitepaper asks how long a merchant should wait.
While the honest chain adds z blocks, the attacker's secret chain grows by
a Poisson-distributed amount with mean z q/p; from each possible lead the
gambler's ruin gives the chance to catch up. The whitepaper tabulates the
result, and concludes that the risk drops exponentially with z.

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

The function reproduces the whitepaper's table, and a Monte-Carlo race
between two chains agrees. Six confirmations against a 10% attacker leave
about a 0.02% risk; against 30% it takes 24.

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 23-25

The whitepaper's table
----------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-36

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    for z, expected in ((0, 1.0), (1, 0.2045873), (2, 0.0509779), (5, 0.0009137), (10, 0.0000012)):
        assert abs(bk.consensus.attacker_success_probability(0.1, z) - expected) < 5e-8
    print("q = 0.1, z = 6:", f"{bk.consensus.attacker_success_probability(0.1, 6):.7f}")






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

 .. code-block:: none

    q = 0.1, z = 6: 0.0002428




.. GENERATED FROM PYTHON SOURCE LINES 37-39

A Monte-Carlo double-spend race
-------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 39-74

.. code-block:: Python

    def attack_succeeds(q, z, rng, horizon=300):
        honest = attacker = 0
        while honest < z:  # The merchant waits for z blocks.
            if rng.random() < q:
                attacker += 1
            else:
                honest += 1
        for _ in range(horizon):  # Then the attacker keeps racing.
            if attacker > honest:
                return True
            if rng.random() < q:
                attacker += 1
            else:
                honest += 1
        return attacker > honest


    rng = Random(2008)
    zs = range(0, 11)
    fig, ax = plt.subplots(figsize=(7, 4))
    for q, color in ((0.1, "#2563eb"), (0.3, "#ea580c")):
        exact = [bk.consensus.attacker_success_probability(q, z) for z in zs]
        simulated = [sum(attack_succeeds(q, z, rng) for _ in range(3000)) / 3000 for z in zs]
        ax.semilogy(zs, exact, "-", color=color, label=f"q = {q}, whitepaper formula")
        ax.semilogy(
            zs, [max(s, 3e-4) for s in simulated], "o", color=color, label=f"q = {q}, simulated"
        )
    ax.set(
        xlabel="confirmations z",
        ylabel="attacker success probability",
        title="Waiting longer makes double spends exponentially rarer",
    )
    ax.legend(fontsize=8)
    fig.tight_layout()




.. image-sg:: /api/gallery/consensus/attacks/images/sphx_glr_plot_02_double_spend_001.png
   :alt: Waiting longer makes double spends exponentially rarer
   :srcset: /api/gallery/consensus/attacks/images/sphx_glr_plot_02_double_spend_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 75-79

Exercise
--------
Find the smallest z with risk below 0.1% for q = 0.1, 0.2 and 0.3. Why does
the required z grow so quickly as q approaches 1/2?


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

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


.. _sphx_glr_download_api_gallery_consensus_attacks_plot_02_double_spend.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_02_double_spend.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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