.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/proofs/pcp/plot_03_micali_cs_proofs.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_03_micali_cs_proofs.py: Micali's computationally sound proofs: hashing the verifier away (1994) ======================================================================= Micali made Kilian's argument non-interactive: the queries are derived by hashing the Merkle root, so the prover can write the whole argument down at once, and anyone can check it later. If the hash behaves like a random oracle, the prover cannot predict which bits will be read before committing. But it can try again. A cheating prover recommits (here, it changes a salt hashed with the root) until the derived queries happen to miss its lies. If one repetition catches a false proof with probability 1/2, the expected number of attempts is .. math:: \mathbb{E}[\text{attempts}] = 2^{k} for :math:`k` repetitions: the soundness of a non-interactive proof is a cost in hashing, which is why deployed systems target :math:`2^{100}` or more. .. GENERATED FROM PYTHON SOURCE LINES 24-28 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk .. GENERATED FROM PYTHON SOURCE LINES 29-31 An honest proof anyone can check -------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 31-39 .. code-block:: Python system = bk.proofs.QuadraticSystem( 3, ((((0, 1), (2, 2)), 1), (((1, 2),), 0), (((0, 0), (1, 1)), 0)) ) honest = bk.proofs.micali_proof(system, bk.proofs.hadamard_proof([1, 1, 0]), repetitions=8) assert bk.proofs.verify_cs_proof(system, honest, repetitions=8) print(f"a CS proof of {len(honest.openings)} openings and {honest.size} bytes") .. rst-class:: sphx-glr-script-out .. code-block:: none a CS proof of 112 openings and 36888 bytes .. GENERATED FROM PYTHON SOURCE LINES 40-42 Grinding: a false proof, rehashed until the queries miss -------------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 42-71 .. code-block:: Python false_proof = bk.proofs.hadamard_proof([1, 0, 1]) # Encodes a non-solution. repetitions = range(1, 8) attempts = [] for k in repetitions: tries = [] for start in range(0, 6 * 2**k * 4, 6 * 2**k): # Four independent searches. salt = start while not bk.proofs.verify_cs_proof( system, bk.proofs.micali_proof(system, false_proof, repetitions=k, salt=salt), repetitions=k, ): salt += 1 tries.append(salt - start + 1) attempts.append(sum(tries) / len(tries)) print(f"{k} repetitions: about {attempts[-1]:.0f} attempts to forge") assert attempts[-1] > 8 * attempts[0] fig, ax = plt.subplots(figsize=(7, 4.5)) ax.semilogy(repetitions, attempts, "o", color="#dc2626", label="measured, mean of 4 searches") ax.semilogy(repetitions, [2**k for k in repetitions], color="#2563eb", label="2**k") ax.set(xlabel="repetitions k", ylabel="attempts until a false proof passes") ax.set_title("Non-interactive soundness is a price in hashes") ax.legend() fig.tight_layout() plt.show() .. image-sg:: /api/gallery/proofs/pcp/images/sphx_glr_plot_03_micali_cs_proofs_001.png :alt: Non-interactive soundness is a price in hashes :srcset: /api/gallery/proofs/pcp/images/sphx_glr_plot_03_micali_cs_proofs_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none 1 repetitions: about 3 attempts to forge 2 repetitions: about 2 attempts to forge 3 repetitions: about 10 attempts to forge 4 repetitions: about 13 attempts to forge 5 repetitions: about 21 attempts to forge 6 repetitions: about 59 attempts to forge 7 repetitions: about 138 attempts to forge .. GENERATED FROM PYTHON SOURCE LINES 72-76 Exercise -------- How many repetitions would make grinding cost 2**80 hashes, if every attempt rebuilds a 520-leaf Merkle tree? How many bytes is the proof then? .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.621 seconds) .. _sphx_glr_download_api_gallery_proofs_pcp_plot_03_micali_cs_proofs.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_03_micali_cs_proofs.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_03_micali_cs_proofs.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_03_micali_cs_proofs.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_03_micali_cs_proofs.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_