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


FRI: fast Reed-Solomon proximity testing (2018)
===============================================

How can a verifier tell that a million committed values are evaluations of
a polynomial of degree below :math:`d`, reading only a few of them?
Ben-Sasson, Bentov, Horesh and Riabzev fold the problem in half each
round. Writing :math:`f(X) = f_e(X^2) + X f_o(X^2)`, a random
:math:`\alpha` gives a polynomial of half the degree on a domain of half
the size,

.. math::

   f'(x^2) = \frac{f(x) + f(-x)}{2} + \alpha\,\frac{f(x) - f(-x)}{2x},

and after :math:`\log_2 d` folds a low-degree function has become a
constant. The prover commits to every layer with a Merkle tree; the
verifier checks each fold at a few random positions. FRI needs only a hash
function: it is the engine of STARKs, and of Plonky2 and RISC Zero.

.. GENERATED FROM PYTHON SOURCE LINES 23-28

.. 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 29-32

Degree below the bound passes, above it fails
---------------------------------------------
Evaluations on a coset of 512 points: a blowup of 8 over the bound 64.

.. GENERATED FROM PYTHON SOURCE LINES 32-41

.. code-block:: Python


    within = bk.proofs.evaluate_on_domain(range(1, 65), 512, offset=31)  # Degree 63.
    beyond = bk.proofs.evaluate_on_domain(range(1, 66), 512, offset=31)  # Degree 64.
    for label, values in (("degree 63", within), ("degree 64", beyond)):
        proof = bk.proofs.fri_prove(values, 64, num_queries=16)
        ok = bk.proofs.fri_verify(proof, domain_size=512, degree_bound=64, num_queries=16)
        print(f"{label}: {len(proof.roots)} folding layers, accepted {ok}")
        assert ok == (label == "degree 63")





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

 .. code-block:: none

    degree 63: 6 folding layers, accepted True
    degree 64: 6 folding layers, accepted False




.. GENERATED FROM PYTHON SOURCE LINES 42-46

The proof grows with log**2 of the domain
-----------------------------------------
Each of 16 queries opens two values and their paths in each of log2(d)
layers.

.. GENERATED FROM PYTHON SOURCE LINES 46-64

.. code-block:: Python


    points = []
    for log_n in range(6, 15, 2):
        n = 2**log_n
        proof = bk.proofs.fri_prove(
            bk.proofs.evaluate_on_domain(range(n // 8), n, offset=31), n // 8, num_queries=16
        )
        assert bk.proofs.fri_verify(proof, domain_size=n, degree_bound=n // 8, num_queries=16)
        points.append((n, proof.size))
    print("domain size and proof bytes:", points)

    ax = plot_proof_sizes(
        {"sending all evaluations": [(n, 8 * n) for n, _ in points], "FRI, 16 queries": points},
        xlabel="evaluations committed",
    )
    ax.set_title("FRI proofs grow polylogarithmically")
    plt.show()




.. image-sg:: /api/gallery/proofs/transparent/images/sphx_glr_plot_02_fri_001.png
   :alt: FRI proofs grow polylogarithmically
   :srcset: /api/gallery/proofs/transparent/images/sphx_glr_plot_02_fri_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    domain size and proof bytes: [(64, 16232), (256, 32168), (1024, 52200), (4096, 76328), (16384, 104552)]




.. GENERATED FROM PYTHON SOURCE LINES 65-70

Exercise
--------
With blowup 8, a function far from every low-degree polynomial passes each
query with probability at most about 1/8 + small terms. How many queries
give 80 bits of soundness, and how large is the proof for a domain of 2**14?


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

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


.. _sphx_glr_download_api_gallery_proofs_transparent_plot_02_fri.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_02_fri.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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