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


Kilian's succinct arguments: a Merkle-committed PCP (1992)
==========================================================

A PCP is cheap to check but expensive to send. Kilian's argument sends only
a Merkle root of it. The verifier then chooses its queries, and the prover
opens each queried bit with its authentication path. Changing an answer
after committing would mean finding a SHA-256 collision, so the prover is
bound to one proof, and the conversation costs

.. math::

   32 + q \left(1 + 32 \lceil \log_2 N \rceil\right) \text{ bytes}

for :math:`q` queries into an :math:`N`-bit proof: logarithmic in the proof
it stands for. Soundness now holds only against provers who cannot find
collisions, which makes this an *argument* rather than a proof.

.. GENERATED FROM PYTHON SOURCE LINES 21-27

.. code-block:: Python

    import math

    import matplotlib.pyplot as plt

    import blockchainkit as bk








.. GENERATED FROM PYTHON SOURCE LINES 28-30

One run, and a prover who changes its answers
---------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 30-44

.. code-block:: Python


    system = bk.proofs.QuadraticSystem(3, ((((0, 1), (2, 2)), 1), (((1, 2),), 0)))
    proof = bk.proofs.hadamard_proof(list(system.solutions()[0]))
    run = bk.proofs.kilian_argument(system, proof, repetitions=4, seed=1)
    print(
        f"{run.queries} bits opened, {run.communication} bytes sent, for a {run.proof_length}-bit PCP"
    )
    assert run.accepted

    lying = bk.proofs.kilian_argument(
        system, proof, repetitions=4, seed=1, respond=lambda i: 1 - proof.bits[i]
    )
    assert not lying.accepted  # Its answers no longer match the committed root.





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

 .. code-block:: none

    56 bits opened, 18456 bytes sent, for a 520-bit PCP




.. GENERATED FROM PYTHON SOURCE LINES 45-47

Communication grows with log N, the PCP with N
----------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 47-74

.. code-block:: Python


    sizes, sent = [], []
    for n in range(1, 5):
        statement = bk.proofs.QuadraticSystem(n, ((((0, 0),), 1),))
        pcp = bk.proofs.hadamard_proof([1] * n)
        result = bk.proofs.kilian_argument(statement, pcp, repetitions=20)
        assert result.accepted
        sizes.append(result.proof_length)
        sent.append(result.communication)
    for n in range(5, 9):  # Beyond n = 4 the PCP is too long to build; count its bytes instead.
        length = 2**n + 2 ** (n * n)
        sizes.append(length)
        sent.append(32 + 280 * (9 + 32 * math.ceil(math.log2(length))))
    print("PCP bits:", sizes[-1], "argument bytes:", sent[-1])
    assert sent[-1] * 8 < sizes[-1]

    fig, ax = plt.subplots(figsize=(7, 4.5))
    ax.loglog(sizes, [s / 8 for s in sizes], "o-", color="#dc2626", label="sending the whole PCP")
    ax.loglog(sizes, sent, "o-", color="#2563eb", label="Kilian: root plus 280 openings")
    ax.axvline(sizes[3], color="#64748b", linestyle=":", label="measured up to here")
    ax.set(xlabel="PCP length (bits)", ylabel="bytes the prover sends")
    ax.set_title("Merkle commitments make PCPs succinct")
    ax.legend()
    fig.tight_layout()

    plt.show()




.. image-sg:: /api/gallery/proofs/pcp/images/sphx_glr_plot_02_kilian_arguments_001.png
   :alt: Merkle commitments make PCPs succinct
   :srcset: /api/gallery/proofs/pcp/images/sphx_glr_plot_02_kilian_arguments_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    PCP bits: 18446744073709551872 argument bytes: 575992




.. GENERATED FROM PYTHON SOURCE LINES 75-80

Exercise
--------
Kilian's verifier must pick its queries *after* receiving the root. Show
what goes wrong if the prover learns the queries first: write a ``respond``
function that answers the queried bits so that a non-solution passes.


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

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


.. _sphx_glr_download_api_gallery_proofs_pcp_plot_02_kilian_arguments.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/pcp/plot_02_kilian_arguments.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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