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


The Fiat-Shamir heuristic: from interaction to signatures (1986)
================================================================

Fiat and Shamir removed the live verifier: compute the challenge as a hash
of the commitment and the message, c = H(R, Q, m). If the hash behaves like
a random function, the prover cannot choose R after knowing c, and the
transcript becomes a non-interactive proof bound to the message: a
signature.

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

The hashed challenge changes completely with the message. The simulator
trick from the zero-knowledge example fails, because R must be fixed before
the hash reveals c. Schnorr signatures, EdDSA, and most zero-knowledge proof
systems used by blockchains rely on this transformation.

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

.. GENERATED FROM PYTHON SOURCE LINES 23-25

The challenge is a hash of everything said so far
-------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-37

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    x, k = 42, 17
    Q, R = bk.crypto.public_key(x), bk.crypto.public_key(k)
    c_bob = bk.crypto.challenge(b"pay Bob", R, Q)
    c_carol = bk.crypto.challenge(b"pay Carol", R, Q)
    assert c_bob != c_carol
    print("challenge for 'pay Bob':  ", hex(c_bob)[:20], "...")
    print("challenge for 'pay Carol':", hex(c_carol)[:20], "...")





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

 .. code-block:: none

    challenge for 'pay Bob':   0x414a0ed1464beee1c9 ...
    challenge for 'pay Carol': 0x794a9db7abda9064c4 ...




.. GENERATED FROM PYTHON SOURCE LINES 38-42

Simulation no longer works
--------------------------
A forger picks s and c, sets R = sG - cQ, but the hash then demands a
different c for that R.

.. GENERATED FROM PYTHON SOURCE LINES 42-48

.. code-block:: Python

    s_forged, c_forged = 98_765, 11
    R_forged = bk.crypto.simulate_transcript(Q, c_forged, s_forged)
    assert bk.crypto.challenge(b"pay Mallory", R_forged, Q) != c_forged
    forgery = bk.crypto.SchnorrSignature(R_forged, s_forged)
    assert not bk.crypto.verify(b"pay Mallory", forgery, Q)








.. GENERATED FROM PYTHON SOURCE LINES 49-53

Searching for a lucky challenge on a tiny curve
-----------------------------------------------
On a 19-element curve a forger succeeds when the hash happens to hit the
chosen c: about 1 time in 19. On secp256k1, 1 time in 2**256.

.. GENERATED FROM PYTHON SOURCE LINES 53-74

.. code-block:: Python

    toy = bk.crypto.TOY_CURVE
    Q_toy = bk.crypto.public_key(5, toy)
    hits = []
    for attempt in range(400):
        s_try, c_try = attempt % (toy.order - 1) + 1, 3
        if s_try == c_try * 5 % toy.order:
            continue  # s = c*x would make R the point at infinity.
        R_try = bk.crypto.simulate_transcript(Q_toy, c_try, s_try, toy)
        message = f"attempt {attempt}".encode()
        hits.append(bk.crypto.challenge(message, R_try, Q_toy, toy) == c_try)
    rate = sum(hits) / len(hits)
    assert 0.01 < rate < 0.12
    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.bar(
        ["measured forgery rate", "1 / group order"],
        [rate, 1 / toy.order],
        color=["#dc2626", "#64748b"],
    )
    ax.set(ylabel="probability", title="Forging = guessing the hash output")
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/signatures/images/sphx_glr_plot_02_fiat_shamir_001.png
   :alt: Forging = guessing the hash output
   :srcset: /api/gallery/crypto/signatures/images/sphx_glr_plot_02_fiat_shamir_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 75-80

Exercise
--------
Bind less into the hash: compute c = H(R, m) without Q. Read the
documentation of :func:`blockchainkit.crypto.systems.signatures.challenge` and explain what
including the public key and curve parameters protects against.


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

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


.. _sphx_glr_download_api_gallery_crypto_signatures_plot_02_fiat_shamir.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/crypto/signatures/plot_02_fiat_shamir.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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