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


Groth16: three group elements per proof (2016)
==============================================

Groth found the shortest pairing-based SNARK: a proof is three group
elements :math:`(A, B, C)`, and the verifier checks one equation,

.. math::

   e(A, B) = e(\alpha, \beta)\; e\Big(\sum_{i \le \ell} x_i L_i, \gamma\Big)\; e(C, \delta),

where the setup encodes the circuit's QAP at a secret point :math:`\tau`,
blinded by secrets :math:`\alpha, \beta, \gamma, \delta`. The prover adds
fresh random :math:`r, s` to every proof, so two proofs of the same
statement look unrelated: they reveal nothing but the public inputs.
Proofs stay the same size however large the circuit, which is why Zcash
(Sapling), Tornado Cash and many rollups use Groth16.

.. GENERATED FROM PYTHON SOURCE LINES 21-27

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    TRAPDOOR = bk.proofs.Groth16Trapdoor(tau=1001, alpha=22, beta=33, gamma=44, delta=55)








.. GENERATED FROM PYTHON SOURCE LINES 28-30

Prove x**3 + x + 5 = 35 without revealing x
-------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 30-43

.. code-block:: Python


    circuit = bk.proofs.Circuit()
    out, x = circuit.public(35), circuit.private(3)
    circuit.assert_equal(circuit.mul(circuit.mul(x, x), x) + x + 5, out)
    key = bk.proofs.groth16_setup(circuit.r1cs(), TRAPDOOR)
    first = bk.proofs.groth16_prove(key, circuit.witness(), seed=1)
    second = bk.proofs.groth16_prove(key, circuit.witness(), seed=2)
    vk = key.verifying_key
    assert bk.proofs.groth16_verify(vk, [35], first) and bk.proofs.groth16_verify(vk, [35], second)
    assert first != second  # Rerandomized: nothing links the two proofs.
    assert not bk.proofs.groth16_verify(vk, [36], first)
    print("proof A:", first.a)





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

 .. code-block:: none

    proof A: (21341727789, 3407614924)




.. GENERATED FROM PYTHON SOURCE LINES 44-47

The proof does not grow with the circuit
----------------------------------------
Prove knowledge of a cube root chain: y = x**(3**k) for growing k.

.. GENERATED FROM PYTHON SOURCE LINES 47-72

.. code-block:: Python


    constraints, elements = [], []
    for k in (1, 4, 16, 64, 256):
        chain = bk.proofs.Circuit()
        y = chain.public(pow(2, 3**k, bk.proofs.FIELD_PRIME))
        value = chain.private(2)
        for _ in range(k):
            value = chain.mul(chain.mul(value, value), value)
        chain.assert_equal(value, y)
        chain_key = bk.proofs.groth16_setup(chain.r1cs(), TRAPDOOR)
        proof = bk.proofs.groth16_prove(chain_key, chain.witness())
        assert bk.proofs.groth16_verify(chain_key.verifying_key, chain.public_inputs(), proof)
        constraints.append(chain.r1cs().num_constraints)
        elements.append(3)
    print("constraints:", constraints, "-> always 3 group elements")

    fig, ax = plt.subplots(figsize=(7, 4.5))
    ax.loglog(constraints, constraints, "o-", color="#dc2626", label="witness size (field elements)")
    ax.loglog(constraints, elements, "o-", color="#2563eb", label="Groth16 proof (group elements)")
    ax.set(xlabel="constraints", ylabel="elements", title="Groth16 proofs have constant size")
    ax.legend()
    fig.tight_layout()

    plt.show()




.. image-sg:: /api/gallery/proofs/snarks/images/sphx_glr_plot_03_groth16_001.png
   :alt: Groth16 proofs have constant size
   :srcset: /api/gallery/proofs/snarks/images/sphx_glr_plot_03_groth16_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    constraints: [5, 11, 35, 131, 515] -> always 3 group elements




.. GENERATED FROM PYTHON SOURCE LINES 73-78

Exercise
--------
The verifier's work is three pairings plus one point multiplication per
public input. Add 10 public inputs to the cube-chain circuit and check that
proofs still verify; which part of the verifying key grew?


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

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


.. _sphx_glr_download_api_gallery_proofs_snarks_plot_03_groth16.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/proofs/snarks/plot_03_groth16.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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