.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/proofs/pcp/plot_01_pcp_theorem.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` 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_01_pcp_theorem.py: The PCP theorem: checking a proof by reading a few bits (1992) ============================================================== Arora and Safra, and Arora, Lund, Motwani, Sudan and Szegedy, proved that every NP statement has a *probabilistically checkable proof*: a verifier tosses coins, reads a constant number of the proof's bits, and accepts a correct proof always and an incorrect one with probability at most 1/2. Repeating drives the error down to :math:`2^{-k}`. Its first ingredient is a proof that is exponentially long but very easy to check. To show that quadratic equations over GF(2) have a solution :math:`u`, write out every parity :math:`\langle u, x\rangle` and every :math:`\langle u \otimes u, y\rangle`. The verifier checks with 14 queries that both tables are linear (the Blum-Luby-Rubinfeld test, :math:`f(x) + f(y) = f(x + y)`), that the second is the tensor square of the first, and that a random sum of the equations holds. .. GENERATED FROM PYTHON SOURCE LINES 21-25 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk .. GENERATED FROM PYTHON SOURCE LINES 26-29 A system with two solutions --------------------------- u0 u1 + u2 = 1, u1 u2 = 0, and u0 + u1 = 0. .. GENERATED FROM PYTHON SOURCE LINES 29-38 .. code-block:: Python system = bk.proofs.QuadraticSystem( 3, ((((0, 1), (2, 2)), 1), (((1, 2),), 0), (((0, 0), (1, 1)), 0)) ) print("solutions:", system.solutions()) proof = bk.proofs.hadamard_proof([1, 1, 0]) print(f"the proof has {len(proof.bits)} bits for a 3-bit witness") assert all(bk.proofs.pcp_verify(system, proof, seed=s).accepted for s in range(200)) .. rst-class:: sphx-glr-script-out .. code-block:: none solutions: ((0, 0, 1), (1, 1, 0)) the proof has 520 bits for a 3-bit witness .. GENERATED FROM PYTHON SOURCE LINES 39-41 Wrong proofs are caught with constant probability per repetition ---------------------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 41-85 .. code-block:: Python wrong_assignment = bk.proofs.hadamard_proof([1, 0, 1]) # Well formed, but not a solution. corrupted_bits = list(proof.bits) for i in range(8, 520, 3): corrupted_bits[i] ^= 1 # A third of the quadratic table flipped. corrupted = bk.proofs.HadamardProof(tuple(corrupted_bits[:8]), tuple(corrupted_bits[8:])) unsatisfiable = bk.proofs.QuadraticSystem(2, ((((0, 0),), 1), (((0, 0),), 0))) repetitions = range(1, 9) cases = { "non-solution, encoded correctly": (system, wrong_assignment), "solution, one third corrupted": (system, corrupted), "unsatisfiable system": (unsatisfiable, bk.proofs.hadamard_proof([1, 0])), } rates = {} for label, (statement, candidate) in cases.items(): rates[label] = [ sum( bk.proofs.pcp_verify(statement, candidate, repetitions=k, seed=s).accepted for s in range(400) ) / 400 for k in repetitions ] print( f"{label}: accepted {rates[label][0]:.0%} with 14 queries, {rates[label][-1]:.1%} with 112" ) assert rates[label][-1] < 0.05 fig, ax = plt.subplots(figsize=(7, 4.5)) for (label, rate), color in zip(rates.items(), ("#2563eb", "#dc2626", "#16a34a"), strict=True): ax.semilogy( [14 * k for k in repetitions], [max(r, 1e-3) for r in rate], "o-", color=color, label=label ) ax.semilogy( [14 * k for k in repetitions], [0.5**k for k in repetitions], "k:", label="1 / 2 per repetition" ) ax.set(xlabel="proof bits read", ylabel="probability a wrong proof is accepted") ax.set_title("A Hadamard PCP read a few bits at a time") ax.legend() fig.tight_layout() plt.show() .. image-sg:: /api/gallery/proofs/pcp/images/sphx_glr_plot_01_pcp_theorem_001.png :alt: A Hadamard PCP read a few bits at a time :srcset: /api/gallery/proofs/pcp/images/sphx_glr_plot_01_pcp_theorem_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none non-solution, encoded correctly: accepted 55% with 14 queries, 0.2% with 112 solution, one third corrupted: accepted 21% with 14 queries, 0.0% with 112 unsatisfiable system: accepted 49% with 14 queries, 0.5% with 112 .. GENERATED FROM PYTHON SOURCE LINES 86-92 Exercise -------- A Hadamard proof for n variables has 2**n + 2**(n**2) bits. For n = 10, how many bits is that, and how many does the verifier read for an error below one in a million, assuming each repetition halves it? A worked solution is in :doc:`/exercises/proofs`. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.161 seconds) .. _sphx_glr_download_api_gallery_proofs_pcp_plot_01_pcp_theorem.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_01_pcp_theorem.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_pcp_theorem.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_pcp_theorem.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_pcp_theorem.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_