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


The sum-check protocol: verifying a sum of 2**n terms (1990)
============================================================

Lund, Fortnow, Karloff and Nisan showed that a prover can convince a
verifier of a sum over the whole Boolean cube,

.. math::

   H = \sum_{b \in \{0,1\}^n} f(b),

while the verifier evaluates :math:`f` only once. In round :math:`i` the
prover sends the univariate polynomial
:math:`g_i(X) = \sum f(r_1, \dots, r_{i-1}, X, b_{i+1}, \dots, b_n)`; the
verifier checks :math:`g_i(0) + g_i(1)` against the previous claim and
fixes :math:`X` to a random :math:`r_i`. A lie must be repeated at the
random point, where by Schwartz-Zippel it survives with probability at most
:math:`d/|\mathbb{F}|` per round.

Here :math:`f` arithmetizes a Boolean formula, so :math:`H` counts its
satisfying assignments: the #SAT problem that LFKN placed in interactive
proofs.

.. GENERATED FROM PYTHON SOURCE LINES 26-32

.. code-block:: Python

    from random import Random

    import matplotlib.pyplot as plt

    import blockchainkit as bk








.. GENERATED FROM PYTHON SOURCE LINES 33-35

Counting the solutions of a formula
-----------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 35-53

.. code-block:: Python


    rng = Random(5)
    n = 10
    clauses = tuple(
        tuple(rng.choice([1, -1]) * v for v in rng.sample(range(1, n + 1), 3)) for _ in range(30)
    )
    formula = bk.proofs.CNF(n, clauses)


    def f(point):
        return formula.evaluate(point, bk.proofs.FIELD_PRIME)


    run = bk.proofs.sumcheck(f, n, formula.degree, seed=1)
    print(f"the prover claims {run.claim} solutions; accepted: {run.accepted}")
    assert run.accepted and run.claim == formula.count_solutions()
    print(f"{n} rounds of degree {formula.degree}; the verifier evaluated f once, not {2**n} times")





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

 .. code-block:: none

    the prover claims 12 solutions; accepted: True
    10 rounds of degree 14; the verifier evaluated f once, not 1024 times




.. GENERATED FROM PYTHON SOURCE LINES 54-58

A false claim survives only by luck
-----------------------------------
Over a small field the cheating prover's luck is measurable, and stays
below n d / p.

.. GENERATED FROM PYTHON SOURCE LINES 58-84

.. code-block:: Python


    small = bk.proofs.CNF(4, ((1, 2), (-2, 3), (3, 4), (-1, -4)))
    primes = [97, 193, 389, 769, 1543]
    measured, bounds = [], []
    for p in primes:
        true = small.count_solutions()
        runs = [
            bk.proofs.sumcheck(
                lambda x, p=p: small.evaluate(x, p), 4, small.degree, p, claim=true + 1, seed=s
            )
            for s in range(2000)
        ]
        measured.append(sum(r.accepted for r in runs) / len(runs))
        bounds.append(4 * small.degree / p)
        assert measured[-1] <= bounds[-1] + 0.01
    print("acceptance of a false count:", [round(m, 3) for m in measured])

    fig, ax = plt.subplots(figsize=(7, 4.5))
    ax.loglog(primes, measured, "o", color="#2563eb", label="false claims accepted")
    ax.loglog(primes, bounds, color="#dc2626", label="bound n d / p")
    ax.set(xlabel="field size", ylabel="probability", title="Sum-check soundness error")
    ax.legend()
    fig.tight_layout()

    plt.show()




.. image-sg:: /api/gallery/proofs/foundations/images/sphx_glr_plot_02_sumcheck_001.png
   :alt: Sum-check soundness error
   :srcset: /api/gallery/proofs/foundations/images/sphx_glr_plot_02_sumcheck_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    acceptance of a false count: [0.07, 0.029, 0.018, 0.012, 0.005]




.. GENERATED FROM PYTHON SOURCE LINES 85-91

Exercise
--------
Count the evaluations of f made by the honest prover and by the verifier
for the four-variable formula above, by wrapping f in a counter. How do
they grow with n?
A worked solution is in :doc:`/exercises/proofs`.


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

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


.. _sphx_glr_download_api_gallery_proofs_foundations_plot_02_sumcheck.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/foundations/plot_02_sumcheck.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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