:orphan:

Examples
========

This gallery walks through ``blockchainkit.structures``, one experiment per
breakthrough on the :doc:`structures history page
</history/structures_breakthroughs>`: double-entry ledgers and account nonces,
Bloom filters, hash chains, Merkle trees and their pitfalls, linked and batched
timestamps, unspent outputs, light clients, transaction ids, replay protection,
sparse Merkle trees, and mountain ranges. The chain examples follow a payment
through blocks, forks and reorganizations.

Each script is self-contained and runs with
``python examples/structures/<section>/<script>.py``.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. thumbnail-parent-div-close

.. raw:: html

    </div>

Bloom filters
-------------

Compact, approximate set membership for light clients.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Burton Bloom traded accuracy for space: set k bit positions per item in an m-bit array, and report an item present if all its positions are set. Items added are always found; others are occasionally found by mistake. Bitcoin light wallets (BIP 37, 2012) sent full nodes a Bloom filter of their addresses instead of the addresses themselves.">

.. only:: html

  .. image:: /api/gallery/structures/bloom/images/thumb/sphx_glr_plot_01_bloom_filter_thumb.png
    :alt:

  :doc:`/api/gallery/structures/bloom/plot_01_bloom_filter`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Bloom filters: membership with false positives (Bloom 1970)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Chains and payments
-------------------

Linked blocks, cumulative-work fork choice, reorganizations, and a payment
from signature to confirmation.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Prerequisites: the quick start, gossip, and the fork experiment. By the end you should distinguish a signed, pending, included, and displaced payment. A pending queue (often called a mempool) is local to each peer.">

.. only:: html

  .. image:: /api/gallery/structures/chain/images/thumb/sphx_glr_plot_02_payment_lifecycle_thumb.png
    :alt:

  :doc:`/api/gallery/structures/chain/plot_02_payment_lifecycle`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">One payment from signature to reorganization and reinclusion</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Hash chains
-----------

Repeated hashing as a source of one-time secrets.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Lamport proposed logging in without ever sending a reusable password. Hash a secret seed n times and give the server only the last value. Each login reveals the value before it: the server hashes it once and compares. A captured password is useless, because the next one is its preimage. This became S/KEY (1995), and hash chains reappear in blockchains as commit-reveal randomness and in Lamport-style signatures.">

.. only:: html

  .. image:: /api/gallery/structures/hash_chains/images/thumb/sphx_glr_plot_01_lamport_hash_chain_thumb.png
    :alt:

  :doc:`/api/gallery/structures/hash_chains/plot_01_lamport_hash_chain`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Hash chains and one-time passwords (Lamport 1981)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Ledgers
-------

Account balances: conservation of value and per-account sequence numbers.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Luca Pacioli&#x27;s Summa de arithmetica gave the first printed account of Venetian double-entry bookkeeping: every transaction is recorded twice, as a debit in one account and a credit in another, so the books always balance. A blockchain ledger enforces the same invariant mechanically: transfers move value between accounts, so the total supply never changes.">

.. only:: html

  .. image:: /api/gallery/structures/ledger/images/thumb/sphx_glr_plot_01_double_entry_thumb.png
    :alt:

  :doc:`/api/gallery/structures/ledger/plot_01_double_entry`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Double-entry bookkeeping: value is moved, never created (Pacioli 1494)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Ethereum replaced Bitcoin&#x27;s coins with accounts: a balance per address, and a nonce counting the transactions each account has sent. A transaction must carry the next expected nonce, so it can be applied once and only in order. Without it, anyone could replay a signed payment again and again.">

.. only:: html

  .. image:: /api/gallery/structures/ledger/images/thumb/sphx_glr_plot_02_account_nonces_thumb.png
    :alt:

  :doc:`/api/gallery/structures/ledger/plot_02_account_nonces`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The account model and nonces (Ethereum 2014)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Merkle trees
------------

Inclusion proofs, ambiguity attacks, append-only logs, and mountain ranges.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A root commits to an ordered collection. An inclusion proof reveals the sibling digests needed to recompute that root, rather than the full dataset. The verifier must already trust the root by some independent mechanism.">

.. only:: html

  .. image:: /api/gallery/structures/merkle/images/thumb/sphx_glr_plot_01_merkle_proofs_thumb.png
    :alt:

  :doc:`/api/gallery/structures/merkle/plot_01_merkle_proofs`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Merkle trees: authenticate one item with a short proof (Merkle 1979)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Bitcoin&#x27;s Merkle tree pairs an odd node with a copy of itself. So the lists [a, b, c] and [a, b, c, c] have the same root. In 2012 this let an attacker send a block with a duplicated transaction: nodes rejected it as invalid and remembered its hash as bad, so they later refused the valid block with the same hash. The bug was fixed by checking for the duplication.">

.. only:: html

  .. image:: /api/gallery/structures/merkle/images/thumb/sphx_glr_plot_02_duplicate_leaf_thumb.png
    :alt:

  :doc:`/api/gallery/structures/merkle/plot_02_duplicate_leaf`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Two lists, one root: the duplicated-leaf ambiguity (CVE-2012-2459)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="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&#x27;s tree contains yesterday&#x27;s as a prefix. A consistency proof shows it with a logarithmic number of hashes.">

.. only:: html

  .. image:: /api/gallery/structures/merkle/images/thumb/sphx_glr_plot_03_consistency_proofs_thumb.png
    :alt:

  :doc:`/api/gallery/structures/merkle/plot_03_consistency_proofs`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Append-only logs: consistency proofs (Certificate Transparency 2013)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Peter Todd described a structure for logs that only grow, designed for OpenTimestamps: a list of perfect Merkle trees (&quot;peaks&quot;) 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.">

.. only:: html

  .. image:: /api/gallery/structures/merkle/images/thumb/sphx_glr_plot_04_mountain_ranges_thumb.png
    :alt:

  :doc:`/api/gallery/structures/merkle/plot_04_mountain_ranges`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Merkle mountain ranges: an append-only accumulator (Todd 2016)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Light clients
-------------

Verifying a payment with block headers only.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Section 8 of the Bitcoin whitepaper describes a client that never downloads blocks. It keeps only the chain of block headers, checks that they link and carry proof of work, and asks a full node for a Merkle proof that a payment is in one of them. Phones run wallets this way.">

.. only:: html

  .. image:: /api/gallery/structures/spv/images/thumb/sphx_glr_plot_01_light_clients_thumb.png
    :alt:

  :doc:`/api/gallery/structures/spv/plot_01_light_clients`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Simplified payment verification: light clients (Nakamoto 2008)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

State commitments
-----------------

Committing to a whole key-value state with one root.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A blockchain&#x27;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.">

.. only:: html

  .. image:: /api/gallery/structures/state/images/thumb/sphx_glr_plot_01_sparse_merkle_thumb.png
    :alt:

  :doc:`/api/gallery/structures/state/plot_01_sparse_merkle`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Sparse Merkle trees: proofs of absence (Dahlberg, Pulls and Peeters 2016)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Timestamping
------------

Proving that a document existed by a given time.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Haber and Stornetta asked how to timestamp a digital document so that not even the timestamping service could backdate it. Their answer: each certificate includes the hash of the previous one. Changing any old record changes its hash, which breaks every later link. A blockchain is this chain of linked timestamps, with blocks as the records.">

.. only:: html

  .. image:: /api/gallery/structures/timestamps/images/thumb/sphx_glr_plot_01_linked_timestamps_thumb.png
    :alt:

  :doc:`/api/gallery/structures/timestamps/plot_01_linked_timestamps`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Linked timestamps: tamper evidence by hashing the past (Haber and Stornetta 1991)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Linking every document into a chain costs one record per document. Bayer, Haber and Stornetta batched them: put a round&#x27;s documents in a Merkle tree and timestamp only the root. Each document keeps a short proof linking it to that root. This is exactly how a block commits to its transactions.">

.. only:: html

  .. image:: /api/gallery/structures/timestamps/images/thumb/sphx_glr_plot_02_merkle_batching_thumb.png
    :alt:

  :doc:`/api/gallery/structures/timestamps/plot_02_merkle_batching`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Batching timestamps with a Merkle tree (Bayer, Haber and Stornetta 1993)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Transaction identity
--------------------

What a transaction id covers, and which network a signature belongs to.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Bitcoin&#x27;s transaction id hashed the whole transaction, signatures included. Anyone relaying a transaction could alter its signature encoding without invalidating it, changing the id. In 2014 the Mt. Gox exchange blamed malleability for lost withdrawals; Decker and Wattenhofer found it explained only a small fraction. Segregated witness (2017) moved signatures out of the id, which also made payment channels such as Lightning safe to build.">

.. only:: html

  .. image:: /api/gallery/structures/transactions/images/thumb/sphx_glr_plot_01_malleability_thumb.png
    :alt:

  :doc:`/api/gallery/structures/transactions/plot_01_malleability`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Transaction malleability and segregated witness (2014-2017)</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="In 2016 Ethereum split into two chains, Ethereum and Ethereum Classic, with the same accounts and keys. A transaction signed for one was valid on the other: anyone could replay it, moving the sender&#x27;s coins on both. EIP-155 added the chain id to what is signed, so a signature belongs to exactly one network.">

.. only:: html

  .. image:: /api/gallery/structures/transactions/images/thumb/sphx_glr_plot_02_replay_protection_thumb.png
    :alt:

  :doc:`/api/gallery/structures/transactions/plot_02_replay_protection`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Replay protection with a chain identifier (EIP-155, 2016)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>

Unspent outputs
---------------

Bitcoin's coin-based ledger.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Bitcoin keeps no balances. Value lives in coins, the outputs of earlier transactions, each locked to an owner. A payment consumes whole coins as inputs and creates new outputs: one to the payee, usually one back to the payer as change. Whatever is not assigned to an output goes to the miner as a fee. A coin can be spent once; a double spend is two transactions consuming the same coin.">

.. only:: html

  .. image:: /api/gallery/structures/utxo/images/thumb/sphx_glr_plot_01_utxo_thumb.png
    :alt:

  :doc:`/api/gallery/structures/utxo/plot_01_utxo`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Coins, not accounts: the unspent-output model (Nakamoto 2008)</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:
   :includehidden:


   /api/gallery/structures/bloom/index.rst
   /api/gallery/structures/chain/index.rst
   /api/gallery/structures/hash_chains/index.rst
   /api/gallery/structures/ledger/index.rst
   /api/gallery/structures/merkle/index.rst
   /api/gallery/structures/spv/index.rst
   /api/gallery/structures/state/index.rst
   /api/gallery/structures/timestamps/index.rst
   /api/gallery/structures/transactions/index.rst
   /api/gallery/structures/utxo/index.rst


.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-gallery

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

      :download:`Download all examples in Python source code: structures_python.zip </api/gallery/structures/structures_python.zip>`

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

      :download:`Download all examples in Jupyter notebooks: structures_jupyter.zip </api/gallery/structures/structures_jupyter.zip>`


.. only:: html

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

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