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


Append-only logs: consistency proofs (Certificate Transparency 2013)
====================================================================

After certificate authorities were compromised in 2011, Google proposed
Certificate Transparency: every certificate goes into a public Merkle-tree
log. Auditors need to know the log only ever *appends*: that today's tree
contains yesterday's as a prefix. A consistency proof shows it with a
logarithmic number of hashes.

What to look for
----------------

Every older version of the log is proven to be a prefix of the newer one.
A log that rewrote an old entry cannot produce a passing proof. Proof size
grows with log2 of the log, not with its length.

The history behind this experiment: :doc:`/history/structures_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 22-24

Prove that the log only appended
--------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 24-35

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    certificates = [f"certificate for site-{i}.example".encode() for i in range(1000)]
    yesterday = bk.structures.MerkleTree(certificates[:600])
    today = bk.structures.MerkleTree(certificates)
    proof = today.consistency_proof(600)
    assert bk.structures.verify_consistency(600, yesterday.root, 1000, today.root, proof)
    print(f"consistency proof from 600 to 1000 entries: {len(proof)} hashes")





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

 .. code-block:: none

    consistency proof from 600 to 1000 entries: 8 hashes




.. GENERATED FROM PYTHON SOURCE LINES 36-38

A rewritten history fails
-------------------------

.. GENERATED FROM PYTHON SOURCE LINES 38-46

.. code-block:: Python

    forged = list(certificates)
    forged[42] = b"certificate for bank.example, issued to an attacker"
    forged_today = bk.structures.MerkleTree(forged)
    forged_proof = forged_today.consistency_proof(600)
    assert not bk.structures.verify_consistency(
        600, yesterday.root, 1000, forged_today.root, forged_proof
    )








.. GENERATED FROM PYTHON SOURCE LINES 47-49

Proof size against log size
---------------------------

.. GENERATED FROM PYTHON SOURCE LINES 49-59

.. code-block:: Python

    sizes = [2**k for k in range(2, 12)]
    lengths = []
    for n in sizes:
        log = bk.structures.MerkleTree(f"entry {i}".encode() for i in range(n))
        lengths.append(len(log.consistency_proof(n // 2 + 1)))
    fig, ax = plt.subplots(figsize=(7, 4))
    ax.semilogx(sizes, lengths, "o-", base=2)
    ax.set(xlabel="log size", ylabel="hashes in proof", title="Consistency proofs are logarithmic")
    fig.tight_layout()




.. image-sg:: /api/gallery/structures/merkle/images/sphx_glr_plot_03_consistency_proofs_001.png
   :alt: Consistency proofs are logarithmic
   :srcset: /api/gallery/structures/merkle/images/sphx_glr_plot_03_consistency_proofs_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 60-65

Exercise
--------
A log could show one tree to you and another to everyone else ("split
view"). Why do consistency proofs alone not prevent that, and how do
gossiped signed tree heads help?


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

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


.. _sphx_glr_download_api_gallery_structures_merkle_plot_03_consistency_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/structures/merkle/plot_03_consistency_proofs.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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