.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/proofs/transparent/plot_04_halo.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_transparent_plot_04_halo.py: Halo: recursive proof composition without a trusted setup (2019) ================================================================ A proof that a previous proof verified, applied at every block, would let anyone check a whole chain from one short proof. That needs verification cheap enough to run inside a proof. Inner-product arguments have no trusted setup, but verifying one costs a multi-exponentiation as long as the committed vector. Bowe, Grigg and Hopwood noticed that the expensive part is a commitment to the polynomial .. math:: g(X) = \prod_{j=1}^{k} \left(1 + c_j X^{2^{k-j}}\right), which anyone can evaluate in :math:`O(\log n)` from the round challenges :math:`c_j`. So the verifier *defers* it: it keeps the claim as an accumulator, merges accumulators by opening a random combination at a random point (which is another cheap check with its own deferred claim), and pays the :math:`O(n)` cost once, at the end. Zcash's Orchard (2022) and Mina rest on this idea. .. GENERATED FROM PYTHON SOURCE LINES 25-31 .. code-block:: Python import math import matplotlib.pyplot as plt import blockchainkit as bk .. GENERATED FROM PYTHON SOURCE LINES 32-34 A chain of 12 steps, each verified cheaply ------------------------------------------ .. GENERATED FROM PYTHON SOURCE LINES 34-49 .. code-block:: Python n = 64 gens = bk.proofs.ipa_generators(n) accumulator = None for step in range(12): poly = [(step + 1) * i + 7 for i in range(n)] opening = bk.proofs.ipa_open(poly, 100 + step, gens) claim = bk.proofs.ipa_defer(bk.proofs.ipa_commit(poly, gens), opening, gens) assert claim is not None # The cheap checks passed; G_final is still unchecked. group = [claim] if accumulator is None else [accumulator, claim] accumulator = bk.proofs.verify_accumulation(group, bk.proofs.accumulate(group, gens), gens) assert accumulator is not None assert bk.proofs.decide(accumulator, gens) print("12 openings verified with one final O(n) check") .. rst-class:: sphx-glr-script-out .. code-block:: none 12 openings verified with one final O(n) check .. GENERATED FROM PYTHON SOURCE LINES 50-52 A bad claim survives the cheap checks but not the end ----------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 52-58 .. code-block:: Python fake = bk.proofs.HaloAccumulator(claim.challenges, claim.g_final * 4 % bk.crypto.TEACHING_GROUP.p) merged = bk.proofs.verify_accumulation([fake], bk.proofs.accumulate([fake], gens), gens) assert merged is None or not bk.proofs.decide(merged, gens) print("a tampered accumulator is rejected by the final decision") .. rst-class:: sphx-glr-script-out .. code-block:: none a tampered accumulator is rejected by the final decision .. GENERATED FROM PYTHON SOURCE LINES 59-64 Group exponentiations: verify everything, or defer -------------------------------------------------- A full check costs about n + 2 log2 n + 3 exponentiations; a deferred check and one accumulation step about 2 (2 log2 n + 3) + 2, and the decision n once. .. GENERATED FROM PYTHON SOURCE LINES 64-79 .. code-block:: Python rounds = int(math.log2(n)) steps = range(1, 65) full = [s * (n + 2 * rounds + 3) for s in steps] deferred = [s * (2 * (2 * rounds + 3) + 2) + n for s in steps] fig, ax = plt.subplots(figsize=(7, 4.5)) ax.plot(steps, full, color="#dc2626", label="verify every opening fully") ax.plot(steps, deferred, color="#2563eb", label="Halo: defer and accumulate") ax.set(xlabel="proofs in the chain", ylabel="group exponentiations") ax.set_title(f"Amortizing inner-product verification, n = {n}") ax.legend() fig.tight_layout() plt.show() .. image-sg:: /api/gallery/proofs/transparent/images/sphx_glr_plot_04_halo_001.png :alt: Amortizing inner-product verification, n = 64 :srcset: /api/gallery/proofs/transparent/images/sphx_glr_plot_04_halo_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 80-85 Exercise -------- Check that ``challenge_polynomial(c, x)`` equals the inner product of the coefficient vector s, built from the challenges, with (1, x, x**2, ...): the fact that lets the verifier skip computing G_final. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.103 seconds) .. _sphx_glr_download_api_gallery_proofs_transparent_plot_04_halo.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_04_halo.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_04_halo.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_04_halo.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_04_halo.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_