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


scrypt and memory-hard key derivation (2009)
============================================

PBKDF2 makes each guess slow but needs almost no memory, so custom chips
run millions of guesses in parallel. Colin Percival's scrypt makes each
guess need a large table as well. Its core, ROMix, fills a table of N
blocks and then reads it at N data-dependent addresses,

.. math::

   V_i = \mathrm{BlockMix}^{\,i}(B), \qquad
   X \leftarrow \mathrm{BlockMix}(X \oplus V_{\mathrm{Integerify}(X) \bmod N}).

An attacker may keep only every k-th entry and recompute the rest, but then
spends about (k + 1)/2 times as long in the second loop: memory times time
stays near constant, so the chip area and time of an attack grow together.
Here the trade-off is measured.

.. GENERATED FROM PYTHON SOURCE LINES 22-29

.. code-block:: Python

    import hashlib

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.wallets.visualizers import plot_memory_tradeoff








.. GENERATED FROM PYTHON SOURCE LINES 30-32

scrypt as specified
-------------------

.. GENERATED FROM PYTHON SOURCE LINES 32-37

.. code-block:: Python


    ours = bk.wallets.scrypt(b"password", b"NaCl", 64, 2, 1, 32)
    assert ours == hashlib.scrypt(b"password", salt=b"NaCl", n=64, r=2, p=1, dklen=32)
    print("scrypt(N=64, r=2):", ours.hex())





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

 .. code-block:: none

    scrypt(N=64, r=2): bfdb7f756bcbf7bc0b1cc882d58fc202bb6635406880f18094158824044eca77




.. GENERATED FROM PYTHON SOURCE LINES 38-40

Forgetting part of the table
----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 40-62

.. code-block:: Python


    block = bk.wallets.pbkdf2(b"password", b"NaCl", 1, 128)
    n = 256
    reference, _ = bk.wallets.romix(block, n)
    costs = []
    for k in (1, 2, 4, 8, 16, 32, 64, 128, 256):
        out, cost = bk.wallets.romix(block, n, keep_every=k)
        assert out == reference
        costs.append(cost)
        print(
            f"keep every {k:3}: {cost.memory:6,} bytes, {cost.block_mixes:6,} BlockMix calls,"
            f" product {cost.memory * cost.block_mixes:,}"
        )

    # Filling the table costs N calls at any k, so the product falls from 2N
    # to about N/2 per byte-block: a factor of 4 at most, never a free lunch.
    products = [c.memory * c.block_mixes for c in costs]
    assert max(products) / min(products) < 4.5

    ax = plot_memory_tradeoff(costs)
    plt.show()




.. image-sg:: /api/gallery/wallets/stretching/images/sphx_glr_plot_02_scrypt_memory_hardness_001.png
   :alt: scrypt's trade-off, N = 256
   :srcset: /api/gallery/wallets/stretching/images/sphx_glr_plot_02_scrypt_memory_hardness_001.png
   :class: sphx-glr-single-img


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

 .. code-block:: none

    keep every   1: 32,768 bytes,    512 BlockMix calls, product 16,777,216
    keep every   2: 16,384 bytes,    632 BlockMix calls, product 10,354,688
    keep every   4:  8,192 bytes,    858 BlockMix calls, product 7,028,736
    keep every   8:  4,096 bytes,  1,330 BlockMix calls, product 5,447,680
    keep every  16:  2,048 bytes,  2,410 BlockMix calls, product 4,935,680
    keep every  32:  1,024 bytes,  4,410 BlockMix calls, product 4,515,840
    keep every  64:    512 bytes,  8,410 BlockMix calls, product 4,305,920
    keep every 128:    256 bytes, 17,306 BlockMix calls, product 4,430,336
    keep every 256:    128 bytes, 33,946 BlockMix calls, product 4,345,088




.. GENERATED FROM PYTHON SOURCE LINES 63-68

Exercise
--------
Keeping every k-th entry should cost about :math:`N + N(k + 1)/2`
BlockMix calls. Check this against the measured counts.
A worked solution is in :doc:`/exercises/wallets`.


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

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


.. _sphx_glr_download_api_gallery_wallets_stretching_plot_02_scrypt_memory_hardness.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/wallets/stretching/plot_02_scrypt_memory_hardness.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

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

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

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

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

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

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


.. only:: html

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

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