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


Threshold ECDSA (Gennaro and Goldfeder, 2018)
=============================================

A multisig script shows its policy on chain and needs a signature per
signer. A threshold signature is one ordinary signature under one key,
made by any t of n parties holding Shamir shares of a private key that no
one ever assembles. Schnorr responses add, but ECDSA's

.. math::

   s = k^{-1}(z + r x)

multiplies secrets. Rosario Gennaro and Steven Goldfeder's protocol
converts products of secrets held by two parties into sums with a
multiplicative-to-additive (MtA) conversion, one for every ordered pair of
signers and each of two products, :math:`k\gamma` and :math:`kx`. Here a
2-of-3 key is generated jointly and used to sign. The MtA step is an ideal
function; the real protocol runs it under Paillier encryption.

.. GENERATED FROM PYTHON SOURCE LINES 23-29

.. code-block:: Python

    from itertools import combinations

    import matplotlib.pyplot as plt

    import blockchainkit as bk








.. GENERATED FROM PYTHON SOURCE LINES 30-32

A jointly generated 2-of-3 key
------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 32-51

.. code-block:: Python


    keys = bk.wallets.threshold_keygen(2, 3, seed=2018)
    print("joint key address:", bk.wallets.p2pkh_address(keys.public))
    for index, _ in keys.shares:
        assert bk.wallets.verify_key_share(keys, index)
    print("every share matches the dealers' Feldman commitments")

    message = b"pay bob 5 BTC"
    for signers in combinations((1, 2, 3), 2):
        signing = bk.wallets.threshold_sign(message, keys, signers, seed=sum(signers))
        valid = bk.wallets.ecdsa_verify(message, signing.signature, keys.public)
        print(f"signers {signers}: r = {hex(signing.signature.r)[:12]}..., valid {valid}")
        assert valid

    try:
        bk.wallets.threshold_sign(message, keys, [2])
    except ValueError as exc:
        print("one signer:", exc)





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

 .. code-block:: none

    joint key address: 1GDvqoYSTqkBLJfFDM1Ecvd2YtUjUAzq5x
    every share matches the dealers' Feldman commitments
    signers (1, 2): r = 0xbe6dbf6df9..., valid True
    signers (1, 3): r = 0x8d111bb4c2..., valid True
    signers (2, 3): r = 0x91a247ac58..., valid True
    one signer: need at least 2 signers




.. GENERATED FROM PYTHON SOURCE LINES 52-56

The work ECDSA's nonlinearity costs
-----------------------------------
A Schnorr threshold signature needs no conversions; ECDSA needs
2 t (t - 1).

.. GENERATED FROM PYTHON SOURCE LINES 56-75

.. code-block:: Python


    thresholds = list(range(1, 8))
    conversions = []
    for t in thresholds:
        big = bk.wallets.threshold_keygen(t, t, seed=t)
        signing = bk.wallets.threshold_sign(b"m", big, range(1, t + 1), seed=t)
        assert bk.wallets.ecdsa_verify(b"m", signing.signature, big.public)
        conversions.append(signing.conversions)
    assert conversions == [2 * t * (t - 1) for t in thresholds]

    fig, ax = plt.subplots(figsize=(6, 4))
    ax.plot(thresholds, conversions, "o-", color="#dc2626", label="threshold ECDSA (MtA runs)")
    ax.plot(thresholds, [0] * len(thresholds), "o-", color="#2563eb", label="threshold Schnorr")
    ax.set(xlabel="signers t", ylabel="two-party conversions")
    ax.set_title("Quadratic interaction for one ECDSA signature")
    ax.legend()
    fig.tight_layout()
    plt.show()




.. image-sg:: /api/gallery/wallets/custody/images/sphx_glr_plot_02_threshold_ecdsa_001.png
   :alt: Quadratic interaction for one ECDSA signature
   :srcset: /api/gallery/wallets/custody/images/sphx_glr_plot_02_threshold_ecdsa_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 76-81

Exercise
--------
Recover the joint private key from two shares with Lagrange coefficients,
and check it against ``keys.public``. Why does the protocol never do this?
A worked solution is in :doc:`/exercises/wallets`.


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

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


.. _sphx_glr_download_api_gallery_wallets_custody_plot_02_threshold_ecdsa.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/wallets/custody/plot_02_threshold_ecdsa.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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