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


The Sybil attack: identities are cheap (Douceur 2002)
=====================================================

In an open network, nothing stops one person from running many nodes.
Douceur showed that without a trusted authority to certify identities, an
attacker can always present as many as its resources allow, and any
protocol that counts identities, such as voting or choosing which nodes
store a key, can be taken over. Proof of work is one answer: it makes
influence cost computation instead of counting identities.

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

When nodes choose their own identifiers, eight Sybils placed next to a key
become the eight closest nodes, so every honest lookup lands on the
attacker. When identifiers must be the hash of a public key, the attacker
has to grind keys instead: the cost doubles with every extra bit it must
match, but it is only a cost, not a barrier.

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

.. GENERATED FROM PYTHON SOURCE LINES 25-27

Chosen identifiers
------------------

.. GENERATED FROM PYTHON SOURCE LINES 27-43

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    bits = 20
    honest = Random(2).sample(range(2**bits), 300)
    key = bk.network.node_id(b"block 7", bits)
    sybils = [key ^ i for i in range(1, 9) if key ^ i not in honest]
    network = bk.network.KademliaNetwork(honest + sybils, bits=bits, k=4, seed=1)
    captured = [network.lookup(source, key).found in sybils for source in honest]
    print(f"{sum(captured)} of {len(honest)} honest lookups end at a Sybil")
    assert all(captured)
    assert set(network.closest(key, len(sybils))) == set(sybils)





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

 .. code-block:: none

    300 of 300 honest lookups end at a Sybil




.. GENERATED FROM PYTHON SOURCE LINES 44-48

Identifiers bound to keys
-------------------------
To land within d leading bits of the key, the attacker must try about
2**d public keys per Sybil.

.. GENERATED FROM PYTHON SOURCE LINES 48-71

.. code-block:: Python

    costs = {}
    for d in range(4, 15, 2):
        tries = 0
        for _ in range(4):  # Four Sybils per prefix length.
            while True:
                tries += 1
                candidate = bk.network.node_id(f"sybil key {tries}".encode(), bits)
                if (candidate ^ key) >> (bits - d) == 0:
                    break
        costs[d] = tries / 4
    print({d: round(c) for d, c in costs.items()})
    assert costs[14] > 50 * costs[4]

    nearest = min(bk.network.xor_distance(h, key) for h in honest)
    print("closest honest node shares", bits - nearest.bit_length(), "leading bits with the key")

    fig, ax = plt.subplots(figsize=(6, 4))
    ax.semilogy(list(costs), list(costs.values()), "o", label="measured")
    ax.semilogy(list(costs), [2**d for d in costs], color="black", label="2**d")
    ax.set(xlabel="leading bits matched d", ylabel="key attempts per Sybil", title="Grinding cost")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/network/overlays/images/sphx_glr_plot_02_sybil_attack_001.png
   :alt: Grinding cost
   :srcset: /api/gallery/network/overlays/images/sphx_glr_plot_02_sybil_attack_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    {4: 11, 6: 69, 8: 158, 10: 528, 12: 4358, 14: 13327}
    closest honest node shares 7 leading bits with the key




.. GENERATED FROM PYTHON SOURCE LINES 72-77

Exercise
--------
S/Kademlia (2007) additionally requires each node ID to come with a
proof-of-work puzzle solution. How does that change the attacker's cost
compared with the honest nodes' cost of joining once?


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

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


.. _sphx_glr_download_api_gallery_network_overlays_plot_02_sybil_attack.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/overlays/plot_02_sybil_attack.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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