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


Feldman's verifiable secret sharing (1987)
==========================================

In Shamir's scheme every share holder must trust the dealer: nothing stops
a dealer from handing out shares that do not lie on one polynomial. Feldman
had the dealer publish g**a_j for each coefficient a_j. Each holder checks
g**y == product of C_j**(x**j), which holds only for points on the
committed polynomial.

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

Honest shares pass the check and any three of them recover the secret. A
corrupted share is caught by its holder before reconstruction. Verifiable
sharing is the starting point of distributed key generation, used for
threshold signatures in modern wallets.

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

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Deal and verify
---------------

.. GENERATED FROM PYTHON SOURCE LINES 25-41

.. code-block:: Python

    from itertools import combinations
    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    G = bk.crypto.TEACHING_GROUP
    secret = 2026
    dealt = bk.crypto.feldman_split(secret, 3, 5, randbelow=Random(87).randrange)
    assert all(bk.crypto.feldman_verify(share, dealt.commitments) for share in dealt.shares)
    assert dealt.commitments[0] == pow(G.g, secret, G.p)  # g**secret is public; secret is not.
    for subset in combinations(dealt.shares, 3):
        assert bk.crypto.recover_secret(subset, prime=G.q) == secret
    print("5 shares, all verified; any 3 recover the secret")





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

 .. code-block:: none

    5 shares, all verified; any 3 recover the secret




.. GENERATED FROM PYTHON SOURCE LINES 42-44

A cheating dealer is caught
---------------------------

.. GENERATED FROM PYTHON SOURCE LINES 44-50

.. code-block:: Python

    x, y = dealt.shares[2]
    bad_share = (x, (y + 1) % G.q)
    assert not bk.crypto.feldman_verify(bad_share, dealt.commitments)
    corrupted = [dealt.shares[0], dealt.shares[1], bad_share]
    assert bk.crypto.recover_secret(corrupted, prime=G.q) != secret  # Unverified, it would mislead.








.. GENERATED FROM PYTHON SOURCE LINES 51-53

Which shares pass?
------------------

.. GENERATED FROM PYTHON SOURCE LINES 53-65

.. code-block:: Python

    offsets = range(-3, 4)
    passes = [bk.crypto.feldman_verify((x, (y + d) % G.q), dealt.commitments) for d in offsets]
    fig, ax = plt.subplots(figsize=(7, 3.2))
    ax.bar([str(d) for d in offsets], passes, color=["#16a34a" if p else "#dc2626" for p in passes])
    ax.set(
        xlabel="error added to share 3",
        ylabel="passes the check",
        yticks=[0, 1],
        title="Only the committed share verifies",
    )
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/sharing/images/sphx_glr_plot_02_feldman_vss_001.png
   :alt: Only the committed share verifies
   :srcset: /api/gallery/crypto/sharing/images/sphx_glr_plot_02_feldman_vss_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 66-71

Exercise
--------
Feldman's commitments reveal g**secret. Explain why that hides the secret
only computationally, and how Pedersen (1991) used his commitments to make
verifiable sharing hide the secret perfectly.


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

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


.. _sphx_glr_download_api_gallery_crypto_sharing_plot_02_feldman_vss.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/sharing/plot_02_feldman_vss.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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