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


STARKs: transparent proofs of computation from hashes (2018)
============================================================

Ben-Sasson, Bentov, Horesh and Riabzev built scalable, transparent
arguments of knowledge: no trusted setup, nothing but a hash function, and
proofs that grow polylogarithmically with the computation. Write the
computation as an execution trace, here the Fibonacci sequence
:math:`a_{i+2} = a_{i+1} + a_i`, interpolate it as a polynomial
:math:`f` over a subgroup :math:`\langle g\rangle`, and turn each rule into
a divisibility:

.. math::

   \frac{f(g^2 X) - f(gX) - f(X)}{\prod_{i < T-2} (X - g^i)}, \qquad
   \frac{f(X) - a_{T-1}}{X - g^{T-1}}

are polynomials exactly when the trace follows the rule and ends at the
claimed value. The prover commits to :math:`f` on a larger domain and proves
with FRI that a random combination of the quotients has low degree.
StarkNet and many zkVMs use this design.

.. GENERATED FROM PYTHON SOURCE LINES 25-30

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.proofs.visualizers import plot_proof_sizes








.. GENERATED FROM PYTHON SOURCE LINES 31-33

Proving the 1024th Fibonacci number modulo p
--------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 33-44

.. code-block:: Python


    steps = 1024
    result = bk.proofs.fibonacci_trace(steps)[-1]
    proof = bk.proofs.stark_prove(steps)
    assert bk.proofs.stark_verify(proof, steps=steps, result=result)
    print(f"a_{steps - 1} = {result}; proof of {proof.size:,} bytes")

    false = bk.proofs.stark_prove(steps, claimed=result + 1)
    assert not bk.proofs.stark_verify(false, steps=steps, result=result + 1)
    print("a false result fails: its boundary quotient is not a polynomial, and FRI notices")





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

 .. code-block:: none

    a_1023 = 95215208; proof of 130,664 bytes
    a false result fails: its boundary quotient is not a polynomial, and FRI notices




.. GENERATED FROM PYTHON SOURCE LINES 45-51

Proof size against computation length
-------------------------------------
The proof grows like log**2 of the trace, the trace itself linearly. For
the tiny traces here the proof is still the larger, by a shrinking
factor; extrapolated, the lines cross near 2**15 steps, and real STARKs
prove billions.

.. GENERATED FROM PYTHON SOURCE LINES 51-68

.. code-block:: Python


    points = []
    for log_t in range(4, 12):
        t = 2**log_t
        p = bk.proofs.stark_prove(t)
        assert bk.proofs.stark_verify(p, steps=t, result=bk.proofs.fibonacci_trace(t)[-1])
        points.append((t, p.size))
    print("trace length and proof bytes:", points)
    assert points[-1][1] < 4 * points[0][1]

    ax = plot_proof_sizes(
        {"the trace itself (8 bytes a step)": [(t, 8 * t) for t, _ in points], "STARK": points},
        xlabel="steps of computation",
    )
    ax.set_title("STARK proofs grow with log**2 of the computation")
    plt.show()




.. image-sg:: /api/gallery/proofs/transparent/images/sphx_glr_plot_03_starks_001.png
   :alt: STARK proofs grow with log**2 of the computation
   :srcset: /api/gallery/proofs/transparent/images/sphx_glr_plot_03_starks_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    trace length and proof bytes: [(16, 45992), (32, 57544), (64, 70120), (128, 83720), (256, 98344), (512, 113992), (1024, 130664), (2048, 148360)]




.. GENERATED FROM PYTHON SOURCE LINES 69-74

Exercise
--------
The low-degree extension lives on a coset ``31 * <w>`` that avoids the
trace domain ``<g>``. Why? Evaluate the boundary quotient (f(x) - 1)/(x - 1)
on the subgroup ``<w>`` itself and see which point breaks it.


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

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


.. _sphx_glr_download_api_gallery_proofs_transparent_plot_03_starks.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/transparent/plot_03_starks.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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