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


Zerocoin: spending a coin without saying which (2013)
=====================================================

Miers, Garman, Green and Rubin proposed an extension to Bitcoin in which
a user *mints* a coin by publishing a commitment :math:`C = g^S h^r` to a
random serial number :math:`S`, and later *spends* it by revealing
:math:`S` with a zero-knowledge proof that some minted coin opens to it.
Spent serials are recorded, so no coin is spent twice, but the spend
points to no particular mint: every coin ever minted is in the anonymity
set.

To keep the proof short, the coins are gathered in an RSA accumulator
:math:`A = u^{c_1 c_2 \cdots c_n} \bmod N`; each coin's witness is the
accumulator of all the others, and

.. math::

   w_i^{\,c_i} \equiv A \pmod N .

Here the spend instead proves membership with a ring signature over all
coins, since :math:`C_i g^{-S} = h^{r}` exactly for the coin being spent.

.. GENERATED FROM PYTHON SOURCE LINES 26-30

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk








.. GENERATED FROM PYTHON SOURCE LINES 31-33

The accumulator
---------------

.. GENERATED FROM PYTHON SOURCE LINES 33-46

.. code-block:: Python


    pool = bk.privacy.ZerocoinPool()
    coins = [(1_000 + 37 * i, 50 + i) for i in range(12)]
    for serial, blinding in coins:
        pool.mint(bk.privacy.mint_coin(serial, blinding))
    primes = [bk.privacy.hash_to_prime(c) for c in pool.coins]
    accumulator = pool.accumulator
    for i, prime in enumerate(primes):
        assert bk.privacy.verify_membership(
            accumulator, prime, bk.privacy.membership_witness(primes, i)
        )
    print(f"12 coins, one {accumulator.bit_length()}-bit accumulator")





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

 .. code-block:: none

    12 coins, one 59-bit accumulator




.. GENERATED FROM PYTHON SOURCE LINES 47-49

Spending, once
--------------

.. GENERATED FROM PYTHON SOURCE LINES 49-59

.. code-block:: Python


    serial, blinding = coins[7]
    spend = bk.privacy.prove_zerocoin_spend(pool.coins, serial, blinding, b"pay alice", seed=1)
    pool.spend(spend, b"pay alice")
    try:
        pool.spend(spend, b"pay alice")
    except ValueError as error:
        print("second spend:", error)
    assert pool.spent == {serial}





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

 .. code-block:: none

    second spend: double spend: this serial was already revealed




.. GENERATED FROM PYTHON SOURCE LINES 60-63

The proof looks the same for every coin
---------------------------------------
Every ring member gets a response, so the spent coin does not stand out.

.. GENERATED FROM PYTHON SOURCE LINES 63-73

.. code-block:: Python


    q = bk.crypto.TEACHING_GROUP.q
    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.bar(range(12), [r / q for r in spend.proof.responses], color="#2563eb")
    ax.set(xlabel="minted coin", ylabel="response / q", ylim=(0, 1))
    ax.set_title("Which of the 12 coins was spent? The proof does not say")
    fig.tight_layout()

    plt.show()




.. image-sg:: /api/gallery/privacy/amounts/images/sphx_glr_plot_01_zerocoin_001.png
   :alt: Which of the 12 coins was spent? The proof does not say
   :srcset: /api/gallery/privacy/amounts/images/sphx_glr_plot_01_zerocoin_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 74-81

Exercise
--------
The proof here grows with the number of coins, while Zerocoin's stays
constant. Roughly how many group elements does a spend from a pool of a
million coins carry here, and why did Zerocoin need a trusted RSA
modulus to do better?
A worked solution is in :doc:`/exercises/privacy`.


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

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


.. _sphx_glr_download_api_gallery_privacy_amounts_plot_01_zerocoin.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/privacy/amounts/plot_01_zerocoin.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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