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


Merkle mountain ranges: an append-only accumulator (Todd 2016)
==============================================================

Peter Todd described a structure for logs that only grow, designed for
OpenTimestamps: a list of perfect Merkle trees ("peaks") of decreasing
size. Appending adds a one-leaf peak and merges equal-sized neighbours,
like carrying in binary addition. Old peaks are never rewritten, so an
append costs about two hashes, however long the range is.

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

The number of peaks equals the number of 1-bits in the size. Every leaf
has a short proof to its peak. Grin and other chains use mountain ranges to
commit to their entire history of outputs or headers.

The history behind this experiment: :doc:`/history/structures_breakthroughs`.
See :doc:`/exercises/structures` for a worked solution to the exercise.

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Grow a range and watch the peaks
--------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-39

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    mmr = bk.structures.MerkleMountainRange()
    peak_counts, merges = [], []
    for i in range(64):
        before = len(mmr.peaks)
        mmr = mmr.append(f"header {i}".encode())
        peak_counts.append(len(mmr.peaks))
        merges.append(before + 1 - len(mmr.peaks))
    assert all(count == bin(n + 1).count("1") for n, count in enumerate(peak_counts))
    print(f"64 appends needed {sum(merges)} merges in total ({sum(merges) / 64:.2f} per append)")





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

 .. code-block:: none

    64 appends needed 63 merges in total (0.98 per append)




.. GENERATED FROM PYTHON SOURCE LINES 40-42

Prove one old leaf
------------------

.. GENERATED FROM PYTHON SOURCE LINES 42-46

.. code-block:: Python

    proof = mmr.proof(37)
    assert bk.structures.verify_mmr_proof(b"header 37", proof, mmr.root)
    assert not bk.structures.verify_mmr_proof(b"header 99", proof, mmr.root)








.. GENERATED FROM PYTHON SOURCE LINES 47-54

.. code-block:: Python

    fig, (top, bottom) = plt.subplots(2, 1, figsize=(8, 5), sharex=True)
    top.step(range(1, 65), peak_counts, where="post")
    top.set(ylabel="peaks", title="Peaks = 1-bits of the size; merges = carries")
    bottom.bar(range(1, 65), merges, color="#2563eb")
    bottom.set(xlabel="leaves", ylabel="merges at this append")
    fig.tight_layout()




.. image-sg:: /api/gallery/structures/merkle/images/sphx_glr_plot_04_mountain_ranges_001.png
   :alt: Peaks = 1-bits of the size; merges = carries
   :srcset: /api/gallery/structures/merkle/images/sphx_glr_plot_04_mountain_ranges_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 55-59

Exercise
--------
When does a single append cause the most merges? Relate the answer to
carries when adding 1 in binary, and compute the average over 2**k appends.


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

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


.. _sphx_glr_download_api_gallery_structures_merkle_plot_04_mountain_ranges.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_04_mountain_ranges.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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