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


Sparse Merkle trees: proofs of absence (Dahlberg, Pulls and Peeters 2016)
=========================================================================

A blockchain's state is a map from accounts to balances. A sparse Merkle
tree commits to such a map: it is a tree with a leaf for every possible
key, almost all empty, so each key has a fixed position. Empty subtrees
have precomputed digests, so only paths to stored keys cost anything.
Dahlberg, Pulls and Peeters made them efficient and gave non-membership
proofs.

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

The root does not depend on insertion order. A key that is absent has a
proof too: the leaf at its position is empty. Ethereum's state root plays
this role with a related structure, the Merkle Patricia trie.

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

.. GENERATED FROM PYTHON SOURCE LINES 23-25

Commit to balances
------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-41

.. code-block:: Python

    from dataclasses import replace

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    balances = {b"alice": b"100", b"bob": b"5", b"carol": b"42"}
    tree = bk.structures.SparseMerkleTree()
    for key, value in balances.items():
        tree = tree.set(key, value)
    reordered = bk.structures.SparseMerkleTree()
    for key in reversed(list(balances)):
        reordered = reordered.set(key, balances[key])
    assert tree.root == reordered.root
    print(tree)





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

 .. code-block:: none

    SparseMerkleTree(depth=256, keys=3, root=eaba05c4beb9aa56...)




.. GENERATED FROM PYTHON SOURCE LINES 42-44

Prove a balance, and prove an absence
-------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 44-50

.. code-block:: Python

    member = tree.prove(b"bob")
    absent = tree.prove(b"mallory")
    assert bk.structures.verify_sparse_proof(member, tree.root) and member.value == b"5"
    assert bk.structures.verify_sparse_proof(absent, tree.root) and absent.value is None
    assert not bk.structures.verify_sparse_proof(replace(member, value=b"5000"), tree.root)








.. GENERATED FROM PYTHON SOURCE LINES 51-53

Most siblings are default digests of empty subtrees
---------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 53-71

.. code-block:: Python

    counts = []
    for size in (1, 4, 16, 64, 256):
        grown = bk.structures.SparseMerkleTree()
        for i in range(size):
            grown = grown.set(f"account {i}".encode(), b"1")
        empty = bk.structures.SparseMerkleTree()
        defaults = set(empty.prove(b"x").siblings)
        proof = grown.prove(b"account 0")
        counts.append(sum(s not in defaults for s in proof.siblings))
    fig, ax = plt.subplots(figsize=(7, 3.5))
    ax.semilogx([1, 4, 16, 64, 256], counts, "o-", base=2)
    ax.set(
        xlabel="keys stored",
        ylabel="non-default siblings (of 256)",
        title="Proofs compress to about log2(keys) hashes",
    )
    fig.tight_layout()




.. image-sg:: /api/gallery/structures/state/images/sphx_glr_plot_01_sparse_merkle_001.png
   :alt: Proofs compress to about log2(keys) hashes
   :srcset: /api/gallery/structures/state/images/sphx_glr_plot_01_sparse_merkle_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 72-76

Exercise
--------
Why does a fixed position per key make proofs of absence possible, while
an ordinary Merkle tree over a sorted list needs two neighbouring leaves?


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

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


.. _sphx_glr_download_api_gallery_structures_state_plot_01_sparse_merkle.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/state/plot_01_sparse_merkle.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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