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


Dandelion: hiding where a transaction came from (Bojja Venkatakrishnan et al. 2017)
===================================================================================

When a peer broadcasts its own transaction by diffusion, it is usually the
first to send it, so spy nodes that connect widely can guess the origin by
noting which peer delivered each transaction to them first. Bojja
Venkatakrishnan, Fanti and Viswanath proposed Dandelion: first pass the
transaction along a random path (the *stem*), each hop continuing with a
fixed probability, and only then diffuse it (the *fluff*). Spies then see
the end of the stem.

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

With 10% spies, the first-spy estimator names the true origin about half as
often under Dandelion as under diffusion. Precision does not reach zero:
when the origin's first stem hop happens to be a spy, the spy knows exactly
who sent it.

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

.. GENERATED FROM PYTHON SOURCE LINES 25-27

10% spies on a 300-peer network
-------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-42

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    graph = bk.network.watts_strogatz(300, 8, 0.3, seed=4)
    spies = set(Random(5).sample(range(300), 30))
    precision = {
        mode: bk.network.first_spy_precision(graph, spies, mode=mode, trials=600, seed=1)
        for mode in ("diffusion", "dandelion")
    }
    print(precision)
    assert precision["dandelion"] < 0.7 * precision["diffusion"]





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

 .. code-block:: none

    {'diffusion': 0.21666666666666667, 'dandelion': 0.12333333333333334}




.. GENERATED FROM PYTHON SOURCE LINES 43-47

Longer stems
------------
The stem continues with probability q at each hop, so its expected length
is 1 / (1 - q).

.. GENERATED FROM PYTHON SOURCE LINES 47-64

.. code-block:: Python

    qs = [0.0, 0.5, 0.75, 0.9]
    stem = [
        bk.network.first_spy_precision(
            graph, spies, mode="dandelion", stem_probability=q, trials=600, seed=2
        )
        for q in qs
    ]
    print([round(p, 3) for p in stem])
    assert stem[-1] < stem[0]

    fig, (left, right) = plt.subplots(1, 2, figsize=(10, 4))
    left.bar(precision.keys(), precision.values(), color=["#dc2626", "#16a34a"])
    left.set(ylabel="P(origin identified)", title="First-spy estimator")
    right.plot([1 / (1 - q) for q in qs], stem, "o-")
    right.set(xlabel="expected stem length", ylabel="P(origin identified)", title="Dandelion")
    fig.tight_layout()




.. image-sg:: /api/gallery/network/relay/images/sphx_glr_plot_04_dandelion_001.png
   :alt: First-spy estimator, Dandelion
   :srcset: /api/gallery/network/relay/images/sphx_glr_plot_04_dandelion_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    [0.15, 0.153, 0.143, 0.127]




.. GENERATED FROM PYTHON SOURCE LINES 65-71

Exercise
--------
Precision is roughly bounded below by the spy fraction: the chance the
first stem hop is a spy. Vary the number of spies and plot both modes.
Why does the original design route stems over a line-shaped anonymity
graph rather than the full peer graph?


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

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


.. _sphx_glr_download_api_gallery_network_relay_plot_04_dandelion.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/relay/plot_04_dandelion.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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