.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/channels/scaling/plot_04_optimistic_rollups.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` 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_channels_scaling_plot_04_optimistic_rollups.py: Optimistic rollups and fraud-proof challenge windows (2019) =========================================================== An optimistic rollup, as Adler and Quintyne-Collins proposed in 2019, posts its batches and state roots with no proof. A root becomes final once a challenge window has passed, and anyone who recomputes a batch and disagrees can prove fraud within it, taking the proposer's bond. The proof is found by bisection, as in Arbitrum (Kalodner et al., 2018): the two sides compare intermediate state roots, halving the disputed range each round, until they disagree about one transaction, which the chain re-executes. A batch of ``n`` transactions needs .. math:: \lceil \log_2 n \rceil rounds, and one honest watcher suffices; the price is that withdrawals wait for the window. .. GENERATED FROM PYTHON SOURCE LINES 23-29 .. code-block:: Python from random import Random import matplotlib.pyplot as plt import blockchainkit as bk .. GENERATED FROM PYTHON SOURCE LINES 30-32 A fraudulent batch, challenged ------------------------------ .. GENERATED FROM PYTHON SOURCE LINES 32-51 .. code-block:: Python rng = Random(2) accounts = [f"user{i}" for i in range(10)] genesis = {a: 100 for a in accounts} rollup = bk.channels.OptimisticRollup(genesis, window=50, bond=25) batch = [ bk.channels.Transfer(rng.choice(accounts), rng.choice(accounts), rng.randint(1, 40)) for _ in range(64) ] _, honest = bk.channels.execute_batch(genesis, batch) # From transaction 36 on, the proposer's roots include 1,000 coins for itself. start = bk.channels.execute_batch(genesis, batch[:36])[0] | {"mallory": 1_000} _, tail = bk.channels.execute_batch(start, batch[36:]) forged = (*honest[:37], *tail[1:]) rollup.propose("mallory", batch, forged, height=1) proof = rollup.challenge(0, "watcher", height=30) print(f"fraud at transaction {proof.step}, found in {proof.rounds} rounds") assert proof.step == 36 and proof.rounds == 6 and rollup.payouts == {"watcher": 25} .. rst-class:: sphx-glr-script-out .. code-block:: none fraud at transaction 36, found in 6 rounds .. GENERATED FROM PYTHON SOURCE LINES 52-54 Bisection rounds grow with log n -------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 54-63 .. code-block:: Python sizes = [2**k for k in range(1, 15)] rounds = [] for n in sizes: truth = [bytes([0])] + [i.to_bytes(4, "big") for i in range(n)] lie = truth[: n // 3 + 1] + [b"x" + root for root in truth[n // 3 + 1 :]] rounds.append(bk.channels.bisect(lie, truth)[1]) assert rounds == [k for k in range(1, 15)] .. GENERATED FROM PYTHON SOURCE LINES 64-66 The price of optimism: waiting to withdraw ------------------------------------------ .. GENERATED FROM PYTHON SOURCE LINES 66-84 .. code-block:: Python honest_rollup = bk.channels.OptimisticRollup(genesis, window=50) honest_rollup.propose("operator", batch, honest, height=1) finalized_at = next(h for h in range(1, 200) if honest_rollup.finalize(height=h)) print("an honest batch becomes final at height", finalized_at) assert finalized_at == 51 fig, (left, right) = plt.subplots(1, 2, figsize=(11, 4)) left.semilogx(sizes, rounds, "o-", color="#2563eb", base=2) left.set(xlabel="transactions in the batch", ylabel="bisection rounds") left.set_title("One disputed step among n, in log2 n rounds") right.bar(["zk-rollup", "optimistic rollup"], [1, finalized_at - 1], color=["#16a34a", "#d97706"]) right.set(ylabel="blocks until a withdrawal is final") right.set_title("Validity proofs vs. challenge windows") fig.tight_layout() plt.show() .. image-sg:: /api/gallery/channels/scaling/images/sphx_glr_plot_04_optimistic_rollups_001.png :alt: One disputed step among n, in log2 n rounds, Validity proofs vs. challenge windows :srcset: /api/gallery/channels/scaling/images/sphx_glr_plot_04_optimistic_rollups_001.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-script-out .. code-block:: none an honest batch becomes final at height 51 .. GENERATED FROM PYTHON SOURCE LINES 85-93 Exercise -------- A challenge window must outlast a censorship attack: an attacker who can keep the honest challenger's transaction out of ``c`` consecutive blocks wins if ``c`` reaches the window. With block producers chosen at random and a fraction ``f`` of them censoring, how long a window makes the attack succeed with probability below one in a billion? A worked solution is in :doc:`/exercises/channels`. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.080 seconds) .. _sphx_glr_download_api_gallery_channels_scaling_plot_04_optimistic_rollups.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/channels/scaling/plot_04_optimistic_rollups.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_04_optimistic_rollups.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_04_optimistic_rollups.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_04_optimistic_rollups.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_