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


Pricing via processing: making junk mail expensive (Dwork and Naor 1992)
========================================================================

Dwork and Naor proposed that a sender attach to each message the answer to
a puzzle that is moderately hard to solve but easy to check. One of their
pricing functions is a square root modulo a prime: computing it takes a
full modular exponentiation, checking it a single multiplication. The idea
of a cost asymmetry became proof of work.

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

The work to compute a root grows with the size of the prime; checking stays
at one multiplication. The asymmetry here is only logarithmic, which is why
Hashcash (the next example) switched to hash puzzles with tunable,
exponential cost.

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

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Price one message
-----------------

.. GENERATED FROM PYTHON SOURCE LINES 25-36

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    p = 2**61 - 1  # A Mersenne prime, = 3 mod 4.
    message_id = int.from_bytes(bk.crypto.sha256(b"Hello, buy my product!")[:8], "big") % p
    square = message_id * message_id % p  # Choose a puzzle with a guaranteed root.
    answer = bk.consensus.modular_square_root(square, p)
    assert answer.root * answer.root % p == square  # The recipient checks with one multiplication.
    print(f"sender: {answer.multiplications} multiplications; recipient: 1")





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

 .. code-block:: none

    sender: 61 multiplications; recipient: 1




.. GENERATED FROM PYTHON SOURCE LINES 37-39

Cost against prime size
-----------------------

.. GENERATED FROM PYTHON SOURCE LINES 39-53

.. code-block:: Python

    primes = [n for n in range(1000, 2**20, 997) if bk.crypto.is_prime(n) and n % 4 == 3][:40]
    primes += [2**31 - 1, 2**61 - 1]
    work = [bk.consensus.modular_square_root(4, q).multiplications for q in primes]
    fig, ax = plt.subplots(figsize=(7, 3.8))
    ax.semilogx(primes, work, "o", base=2, label="compute the root")
    ax.semilogx(primes, [1] * len(primes), "-", base=2, color="black", label="verify it")
    ax.set(
        xlabel="prime p",
        ylabel="modular multiplications",
        title="Computing costs about 1.5 log2 p; checking costs 1",
    )
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/consensus/pow/images/sphx_glr_plot_01_pricing_via_processing_001.png
   :alt: Computing costs about 1.5 log2 p; checking costs 1
   :srcset: /api/gallery/consensus/pow/images/sphx_glr_plot_01_pricing_via_processing_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 54-59

Exercise
--------
Dwork and Naor also wanted a *shortcut*: a trapdoor letting a trusted
authority price messages cheaply. Why is a logarithmic asymmetry too small
to stop a spammer with a fast computer, and how does Hashcash fix that?


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

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


.. _sphx_glr_download_api_gallery_consensus_pow_plot_01_pricing_via_processing.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/pow/plot_01_pricing_via_processing.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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