Documentation technique Optimism

Analysis and Comparison between Optimism and StarkNet

Yazan Optimism Collective · 2021

Optimism'in geleneksel bir teknik dokümanı yoktur. Ethereum Katman 2 iyimser rollup'ı olan Optimism'in tasarım ve spesifikasyonları, tek bir resmi akademik belge yerine teknik belgeler, OP Stack spesifikasyonu ve araştırma gönderileri aracılığıyla belgelenmiştir.

🇺🇸 English (Orijinal)

🇫🇷 Français (Çeviri)

Abstract

The paper addresses the problem of scalability in decentralized blockchains by analyzing the trade-off between transaction throughput and hardware requirements to run a node. Rollups, i.e. technologies for on-chain verification of blocks executed off-chain, are presented in the form of fault or validity proofs. We compare Optimistic Rollups and Validity Rollups with respect to withdrawal time, transaction costs, optimization techniques, and compatibility with the Ethereum ecosystem. Our analysis reveals that Optimism Bedrock currently has a gas compression rate of approximately 20:1, while StarkNet achieves a storage write cost compression rate of around 24:1. We also discuss techniques to further optimize these rates, such as the use of cache contracts and Bloom filters. Ultimately, our conclusions highlight the trade-offs between complexity and agility in the choice between Optimistic and Validity Rollups. Keywords Blockchain, Scalability, Rollup 1. Introduction Blockchain technology has gained significant attention due to its potential to revolutionize various industries. However, scalability remains a major challenge, as most blockchains face a trade-off between scalability, decentralization, and security, commonly referred to as the Scalability Trilemma [1, 2]. To increase the throughput of a blockchain, a trivial solution is to increase its block size. In the context of Ethereum, this means increasing the maximum amount of gas a block can hold. As each full node must validate every transaction of every block, as the throughput increases, the hardware requirements also increase, leading to a greater centralization of the network. Some blockchains, such as Bitcoin and Ethereum, optimize their design to maximize their architectural decentralization, while others, such as the Binance Smart Chain and Solana, are designed to be as fast and cheap as possible. Decentralized networks artificially limit the throughput of the blockchain to lower the hardware requirements to participate in the network. Over the years, attempts have been made to find a solution to the Trilemma, such as state channels [3] and Plasma [4, 5]. These solutions have the characteristic of moving some activity off-chain, linking on-chain activity to off-chain activity using smart contracts, and verifying DLT 2023: 5th Distributed Ledger Technology Workshop, May 25-26, 2023, Bologna, Italy $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) on-chain what is happening off-chain. However, both Plasma and state channels are limited in their support of general smart contracts. Rollups are blockchains (called Layer 2 or L2) that publish their blocks on another blockchain (Layer 1 or L1) and therefore inherit its consensus, data availability and security properties. They, unlike other solutions, support arbitrary computation. Rollups have three main components: • Sequencers: nodes that receive Rollup transactions from users and combine them into a block that is sent to Layer 1. The block consists of at least the state root (e.g. a Merkle root) and the data needed to reconstruct and validate the state. The Layer 1 defines the...

Résumé

L'article aborde le problème de l'évolutivité dans les blockchain décentralisés en analysant le compromis entre le débit des transactions et les exigences matérielles pour exécuter un nœud. Les rollups, c'est-à-dire les technologies de vérification en chaîne des blocs exécutés hors chaîne, sont présentés sous forme de preuves de faute ou de validité. Nous comparons les cumuls optimistes et les cumuls de validité en ce qui concerne le temps de retrait, les coûts de transaction, les techniques d'optimisation et la compatibilité avec l'écosystème Ethereum. Notre analyse révèle que Optimism Bedrock a actuellement un taux de compression de gaz d'environ 20:1, tandis que StarkNet atteint un taux de compression des coûts d'écriture de stockage d'environ 24:1. Nous discutons également des techniques permettant d'optimiser davantage ces taux, telles que l'utilisation de contrats de cache et de filtres Bloom. En fin de compte, nos conclusions mettent en évidence les compromis entre complexité et agilité dans le choix entre les rollups optimistes et de validité. Mots-clés Blockchain, Scalability, Rollup 1. Introduction La technologie Blockchain a attiré une attention considérable en raison de son potentiel à révolutionner diverses industries. Cependant, l'évolutivité reste un défi majeur, car la plupart des blockchain sont confrontés à un compromis entre évolutivité, décentralisation et sécurité, communément appelé le trilemme de l'évolutivité [1, 2]. Pour augmenter le débit d'un blockchain, une solution triviale consiste à augmenter la taille de son bloc. Dans le contexte de Ethereum, cela signifie augmenter la quantité maximale de gaz qu'un bloc peut contenir. Comme chaque nœud complet doit valider chaque transaction de chaque bloc, à mesure que le débit augmente, les exigences matérielles augmentent également, conduisant à une plus grande centralisation du réseau. Certains blockchain, tels que Bitcoin et Ethereum, optimisent leur conception pour maximiser leur décentralisation architecturale, tandis que d'autres, comme la Binance Smart Chain et Solana, sont conçus pour être aussi rapides et bon marché que possible. Les réseaux décentralisés limitent artificiellement le débit du blockchain pour réduire la configuration matérielle requise pour participer au réseau. Au fil des années, des tentatives ont été faites pour trouver une solution au trilemme, comme les chaînes d'État [3] et Plasma [4, 5]. Ces solutions ont la caractéristique de déplacer certaines activités hors chaîne, de relier l'activité en chaîne à l'activité hors chaîne à l'aide de smart contract et de vérifier DLT 2023 : 5e atelier sur la technologie du grand livre distribué, 25 et 26 mai 2023, Bologne, Italie $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Copyright pour cet article par ses auteurs. Utilisation autorisée sous Creative Commons License Attribution 4.0 International (CC BY 4.0). Actes de l'atelier CEUR http://ceur-ws.org ISSN 1613-0073 Actes de l'atelier CEUR (CEUR-WS.org) en chaîne ce qui se passe hors chaîne. Cependant, les canaux Plasma et étatiques sont limités dans leur prise en charge des smart contract généraux. Les rollups sont des blockchain (appelés Layer 2 ou L2) qui publient leurs blocs sur un autre blockchain (Layer 1 ou L1) et héritent donc de ses propriétés de consensus, de disponibilité des données et de sécurité. Contrairement à d’autres solutions, elles prennent en charge le calcul arbitraire. Les rollups comportent trois composants principaux : • Séquenceurs : nœuds qui reçoivent les transactions Rollup des utilisateurs et les combinent en un bloc envoyé à Layer 1. Le bloc comprend au moins la racine de l'état (par exemple une racine Merkle) et les données nécessaires pour reconstruire et valider l'état. Le Layer 1 définit le...

Introduction

Introduction Blockchain technology has gained significant attention due to its potential to revolutionize various industries. However, scalability remains a major challenge, as most blockchains face a trade-off between scalability, decentralization, and security, commonly referred to as the Scalability Trilemma [1, 2]. To increase the throughput of a blockchain, a trivial solution is to increase its block size. In the context of Ethereum, this means increasing the maximum amount of gas a block can hold. As each full node must validate every transaction of every block, as the throughput increases, the hardware requirements also increase, leading to a greater centralization of the network. Some blockchains, such as Bitcoin and Ethereum, optimize their design to maximize their architectural decentralization, while others, such as the Binance Smart Chain and Solana, are designed to be as fast and cheap as possible. Decentralized networks artificially limit the throughput of the blockchain to lower the hardware requirements to participate in the network. Over the years, attempts have been made to find a solution to the Trilemma, such as state channels [3] and Plasma [4, 5]. These solutions have the characteristic of moving some activity off-chain, linking on-chain activity to off-chain activity using smart contracts, and verifying DLT 2023: 5th Distributed Ledger Technology Workshop, May 25-26, 2023, Bologna, Italy $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org)

on-chain what is happening off-chain. However, both Plasma and state channels are limited in their support of general smart contracts. Rollups are blockchains (called Layer 2 or L2) that publish their blocks on another blockchain (Layer 1 or L1) and therefore inherit its consensus, data availability and security properties. They, unlike other solutions, support arbitrary computation. Rollups have three main components: • Sequencers: nodes that receive Rollup transactions from users and combine them into a block that is sent to Layer 1. The block consists of at least the state root (e.g. a Merkle root) and the data needed to reconstruct and validate the state. The Layer 1 defines the canonical blockchain of the L2 by establishing the ordering of the published data. • Rollup full nodes: nodes that obtain, process and validate Rollup blocks from Layer 1 by verifying that the root is correct. If a block contains invalid transactions it is then discarded, which prevents Sequencers from creating valid blocks that include invalid transactions. • Rollup light nodes: nodes that obtain Rollup blocks from Layer 1 but do not compute the new state themselves. They verify that the new state root is valid using techniques such as fault or validity proofs. Rollups achieve scalability by decreasing the amortized cost of transactions as the number of users increases. This is because the cost of ensuring blockchain validity grows sub-linearly with respect to the cost of verifying transactions individually. Rollups differ according to the mechanism by which they ensure the validity of transaction execution at light nodes: in Optimistic Rollups it is ensured by an economic model and by fault proofs, while in Validity Rollups it is cryptographically ensured using validity proofs. Light nodes can be implemented as smart contracts on Layer 1. They accept the root of the new state and verify validity or fault proofs: these Rollup are therefore called Smart Contract Rollups. If light nodes are independent, they are called Sovereign Rollups [6]. The advantage of using a Smart Contract Rollup is to be able to build a trust-minimized bridge between the two blockchains: since the validity of the L2 state is proven to L1, a system of transactions from L2 to L1 can be implemented, allowing withdrawals. The disadvantage is that the cost of the transactions depends on the cost of verifying the state on L1: if the base layer is saturated by other activities, the cost of transactions on the Rollup also increases. The data and consensus layers are the ones that determine the security of the system as they define the ordering of transactions, prevent attacks and make data available to prove state validity. Paper contribution In this paper, we study Optimistic and Validity Rollups, two innovative solutions to the Scalability Trilemma, with a focus on notable implementations, such as Optimism Bedrock and StarkNet. Our contributions include a comprehensive comparison of these solutions, an analysis of withdrawal times, and a discussion of a possible attack on Optimism Bedrock. Additionally, we calculate their gas compression ratios, provide application-specific optimizations, and present the advantages and disadvantages of moving away from the Ethereum Virtual Machine (EVM).

Paper structure The paper is organized as follows. In section 2 Optimistic Rollups are introduced by analyzing Optimism Bedrock. In section 3 Validity Rollups are introduced by analyzing StarkNet. In section 4 we compare the two solutions. Finally, in section 5 we draw some conclusions.

Introduction

Introduction La technologie Blockchain a suscité une attention considérable en raison de son potentiel de révolution. diverses industries. Cependant, l'évolutivité reste un défi majeur, car la plupart des blockchain sont confrontés à un compromis entre évolutivité, décentralisation et sécurité, communément appelé le Trilemme d’évolutivité [1, 2]. Pour augmenter le débit d'un blockchain, une solution triviale est pour augmenter la taille de son bloc. Dans le contexte de Ethereum, cela signifie augmenter le maximum quantité de gaz qu'un bloc peut contenir. Comme chaque nœud complet doit valider chaque transaction de chaque bloc, à mesure que le débit augmente, les exigences matérielles augmentent également, ce qui entraîne une plus grande centralisation du réseau. Certains blockchain, comme Bitcoin et Ethereum, optimisent leur conception pour maximiser leur décentralisation architecturale, tandis que d'autres, comme le Binance Smart Chain et Solana sont conçus pour être aussi rapides et bon marché que possible. Réseaux décentralisés limiter artificiellement le débit du blockchain pour réduire la configuration matérielle requise à participer au réseau. Au fil des années, des tentatives ont été faites pour trouver une solution au trilemme, notamment en canaux [3] et Plasma [4, 5]. Ces solutions ont la particularité de déplacer certaines activités hors chaîne, reliant l'activité en chaîne à l'activité hors chaîne à l'aide de smart contract et en vérifiant DLT 2023 : 5e atelier sur la technologie du grand livre distribué, 25 et 26 mai 2023, Bologne, Italie $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Copyright pour cet article par ses auteurs. Utilisation autorisée sous Creative Commons License Attribution 4.0 International (CC BY 4.0). EUR Atelier Actes http://ceur-ws.org ISSN1613-0073 Actes de l'atelier CEUR (CEUR-WS.org)en chaîne ce qui se passe hors chaîne. Cependant, les canaux plasma et étatiques sont limités dans leur soutien aux smart contract généraux. Les rollups sont des blockchain (appelés Layer 2 ou L2) qui publient leurs blocs sur un autre blockchain (Layer 1 ou L1) et hérite donc de ses propriétés de consensus, de disponibilité des données et de sécurité. Eux, contrairement à d’autres solutions, prend en charge le calcul arbitraire. Les rollups comportent trois composants principaux : • Séquenceurs : nœuds qui reçoivent les transactions Rollup des utilisateurs et les combinent dans un bloc qui est envoyé à Layer 1. Le bloc comprend au moins la racine de l'état (par exemple un Merkle racine) et les données nécessaires à la reconstruction et à la validation de l'état. Le Layer 1 définit le canonique blockchain de la L2 en établissant l'ordre des données publiées. • Nœuds complets de cumul : nœuds qui obtiennent, traitent et valident les blocs de cumul à partir de Layer. 1 en vérifiant que la racine est correcte. Si un bloc contient des transactions invalides, il est alors rejetés, ce qui empêche les séquenceurs de créer des blocs valides incluant des blocs invalides transactions. • Nœuds légers de cumul : nœuds qui obtiennent des blocs de cumul de Layer 1 mais ne calculent pas le nouvel État lui-même. Ils vérifient que la nouvelle racine d'état est valide à l'aide de techniques telles que des preuves de défaut ou de validité. Les rollups atteignent l'évolutivité en diminuant le coût amorti des transactions à mesure que le nombre des utilisateurs augmente. En effet, le coût pour garantir la validité de blockchain augmente de manière sublinéaire en ce qui concerne le coût de la vérification individuelle des transactions. Les rollups diffèrent selon le mécanisme par lequel ils garantissent la validité de l'exécution des transactions sur les nœuds légers : dans Optimistic Rollups il est assuré par un modèle économique et par des preuves de fautes, tout en étant en Validité Rollups il est assuré cryptographiquement à l’aide de preuves de validité. Les nœuds légers peuvent être implémentés en tant que smart contract sur Layer 1. Ils acceptent la racine du nouvel état et vérifier la validité ou les preuves de défauts : ces Rollup sont donc appelés Smart Contract Cumuls. Si les nœuds légers sont indépendants, ils sont appelés Sovereign Rollups [6]. L'avantage de utiliser un Smart Contract Rollup, c'est être capable de construire un pont de confiance minimisé entre les deux blockchains : la validité de l'état L2 étant prouvée à L1, un système de transactions de L2 à L1 peuvent être mis en œuvre, permettant des retraits. L'inconvénient est que le coût du les transactions dépendent du coût de vérification de l'état sur L1 : si la couche de base est saturée par d'autres activités, le coût des transactions sur le Rollup augmente également. Les couches de données et de consensus sont celles qui déterminent la sécurité du système. ils définissent l'ordre des transactions, préviennent les attaques et mettent à disposition des données pour prouver l'état validité. Contribution papier Dans cet article, nous étudions les cumuls optimistes et de validité, deux solutions innovantes. des solutions au trilemme d'évolutivité, en mettant l'accent sur des implémentations notables, telles que Optimism Bedrock et StarkNet. Nos contributions incluent une comparaison complète de ces solutions, une analyse des temps de retrait et une discussion sur une éventuelle attaque contre Optimism Socle rocheux. De plus, nous calculons leurs taux de compression de gaz, fournissons des optimisations spécifiques à l'application et présentons les avantages et les inconvénients de l'abandon du Ethereum. Machine virtuelle (EVM).

Structure du papier Le document est organisé comme suit. Dans la section 2, les cumuls optimistes sont introduit en analysant Optimism Bedrock. Dans la section 3, les cumuls de validité sont introduits par analysant StarkNet. Dans la section 4, nous comparons les deux solutions. Enfin, dans la section 5, nous dessinons quelques conclusions.

Optimistic Rollups

Optimistic Rollups The idea of accepting optimistically the output of blocks without verifying their execution is already present in the Bitcoin whitepaper [7], discussing light nodes. These nodes only follow the header chain by verifying the consensus rule, making them vulnerable to accept blocks containing invalid transactions in the event of a 51% attack. Nakamoto proposes to solve this problem by using an “alert" system to warn light nodes that a block contains invalid transactions. This mechanism is first implemented by Al-Bassam, Sonnino and Buterin [8] in which a fault proof system based on error correction codes [9] is used. In order to enable the creation of fault proofs, it is necessary that the data from all blocks, including invalid blocks, is available to the network: this is the Data Availability Problem, which is solved using a probabilistic data sampling mechanism. The first Optimistic Rollup design was presented by John Adler and Mikerah Quintyne-Collins in 2019 [10], in which blocks are published on another blockchain that defines their consensus on ordering. 2.1. Optimism Bedrock Bedrock [11] is the latest version of Optimism, a Smart Contract Rollup. The previous version, the Optimistic Virtual Machine (OVM) required an ad hoc compiler to compile Solidity into its own bytecode: in contrast, Bedrock is fully equivalent to the EVM in that the execution engine follows the Ethereum Yellow Paper specification [12]. 2.1.1. Deposits Users can deposit transactions through a contract on Ethereum, the Optimism Portal, by calling the depositTransaction function. When a transaction is executed, a TransactionDeposited event is emitted, which each node in the Rollup listens for to process deposits. A deposited transaction is a L2 transaction that is derived from L1. If the caller of the function is a contract, the address is transformed by adding a constant value to it: this prevents attacks in which a contract on L1 has the same address as a contract on L2 but a different code. The inclusion on L2 of a deposited transaction is ensured by specification within a sequencing window. Deposited transactions are a new EIP-2718 compatible transaction type [13] with prefix 0x7E, where the rlp-encoded fields are: • bytes32 sourceHash: hash that uniquely identifies the source of the transaction. • address from: the address of the sender. • address to: the receiver address, or the zero address if the deposited transaction is a contract creation.

• uint256 mint: the value to be created on L2. • uint256 value: the value to be sent to the recipient. • bytes data: the input data. • bytes gasLimit: the gas limit of the transaction. The sourceHash is computed as the keccak256 hash of the L1 block hash and the L1 log index, uniquely identifying an event in a block. Since deposited transactions are initiated on L1 but executed on L2, the system needs a mechanism to pay on L1 for the gas spent on L2. One solution is to send ETH through the Portal, but this implies that every caller (even indirect callers) must be marked as payable, and this is not possible for many existing projects. The alternative is to burn the corresponding gas on L1. The gas 𝑔allocated to deposited transaction is called guaranteed gas. The L2 gas price on L1 is not automatically synchronized but is estimated using a mechanism similar to EIP-1559 [14]. The maximum amount of gas guaranteed per Ethereum block is 8 million, with a target of 2 million. The quantity 𝑐of ETH required to pay for gas on L2 is 𝑐= 𝑔𝑏L2 where 𝑏L2 is the basefee on L2. The contract on L1 burns an amount of gas equal to 𝑐/𝑏L2. The gas spent to call depositTransaction is reimbursed on L2: if this amount is greater than the guaranteed gas, no gas is burned. The first transaction of a rollup block is a L1 attributes deposited transaction, used to register on a L2 predeploy the attributes of Ethereum blocks. The attributes that the predeploy gives access to are the block number, the timestamp, the basefee, the block hash and the sequence number, which is the block number of L2 relative to the associated L1 block (also called epoch); this number is reset when a new epoch starts. 2.1.2. Sequencing The Rollup nodes derive the Optimism chain entirely from Ethereum. This chain is extended each time new transactions are published on L1, and its blocks are reorganized each time Ethereum blocks are reorganized. The Rollup blockchain is divided into epochs. For each 𝑛 block number of Ethereum, there is a corresponding 𝑛epoch. Each epoch contains at least one block, and each block in an epoch contains a L1 attributes deposited transaction. The first block in an epoch contains all transactions deposited through the Portal. Layer 2 blocks may also contained sequenced transactions, i.e. transactions sent directly to the Sequencer. The Sequencer accepts transactions from users and builds blocks. For each block, it constructs a batch to be published on Ethereum. Several batches can be published in a compressed manner, taking the name channel. A channel can be divided into several frames, in case it is too large for a single transaction. A channel is defined as the compression with ZLIB [15] of rlp-encoded batches. The fields of a batch are the epoch number, the epoch hash, the parent hash, the timestamp and the transaction list. A sequencing window, identified by an epoch, contains a fixed number 𝑤of consecutive L1 blocks that a derivation step takes as input to construct a variable number of L2 blocks. For epoch 𝑛, the sequencing window 𝑛includes the blocks [𝑛, 𝑛+𝑤). This implies that the ordering of L2 transactions and blocks within a sequencing window is not fixed until the window ends. A rollup transaction is called safe if the batch containing it has been confirmed on L1. Frames

are read from L1 blocks to reconstruct batches. The current implementation does not allow the decompression of a channel to begin until all corresponding frames have been received. Invalid batches are ignored. Individual block transactions are obtained from the batches, which are used by the execution engine to apply state transitions and obtain the Rollup state. 2.1.3. Withdrawals In order to process withdrawals, an L2-to-L1 messaging system is implemented. Ethereum needs to know the state of L2 in order to accept withdrawals, and this is done by publishing on the L2 Output Oracle smart contract on L1 the state root of each L2 block. These roots are optimistically accepted as valid (or finalized) if no fault proof is performed during the dispute period. Only addresses designated as Proposers can publish output roots. The validity of output roots is incentivized by having Proposers deposit a stake that is slashed if they are shown to have proposed an invalid root. Transactions are initiated by calling the function initiateWithdrawal on a predeploy on L2 and then finalized on L1 by calling the function finalizeWithdrawalTransaction on the previously mentioned Optimism Portal. The output root corresponding to the L2 block is obtained from the L2 Output Oracle; it is verified that it is finalized, i.e. that the dispute period has passed; it is verified that the Output Root Proof matches the Oracle Proof; it is verified that the hash of the withdrawal is included in it using a Withdrawal Proof; that the withdrawal has not already been finalized; and then the call to the target address is executed, with the specified gas limit, amount of Ether and data. 2.1.4. Cannon: the fault proof system If a Rollup Full Node, by locally executing batches and deposited transactions, discovers that the Layer 2 state does not match the state root published on-chain by a Proposer, it can execute a fault proof on L1 to prove that the result of the block transition is incorrect. Because of the overhead, processing an entire Rollup block on L1 is too expensive. The solution implemented by Bedrock is to execute on-chain only the first instruction of disagreement of minigeth, compiling it into a MIPS architecture that is executed on an on-chain interpreter and published on L1. minigeth is a simplified version of geth 1 in which the consensus, RPC and database have been removed. To find the first instruction of disagreement, an interactive binary search is conducted between the one who initiated the fault proof and the one who published the output root. When the proof starts, both parties publish the root of the MIPS memory state halfway through the execution of the block on the Challenge contract: if the hash matches it means that both parties agree on the first half of the execution thus publishing the root of half of the second half, otherwise the half of the first half is published and so on. Doing so achieves the first instruction of disagreement in a logarithmic number of steps compared to the original execution. If one of the two stops interacting, at the end of the dispute period the other participant automatically wins. To process the instruction, the MIPS interpreter needs access to its memory: since the root is available, the necessary memory cells can be published by proving their inclusion. To access the state of the EVM, use is made of the Preimage Oracle: given the hash of a block it returns 1https://geth.ethereum.org/docs

the block header, from which one can get the hash of the previous block and go back in the chain, or get the hash of the state and logs from which one can get the preimage. The oracle is implemented by minigeth and replaces the database. Queries are made to other nodes to obtain the preimages.

Cumuls optimistes

Cumuls optimistes L'idée d'accepter avec optimisme la sortie des blocs sans vérifier leur exécution est déjà présent dans le livre blanc Bitcoin [7], traitant des nœuds lumineux. Ces nœuds suivent uniquement la chaîne d'en-tête en vérifiant la règle de consensus, les rendant vulnérables à l'acceptation de blocs contenant des transactions invalides en cas d'attaque à 51%. Nakamoto propose de résoudre ce problème problème en utilisant un système « d’alerte » pour avertir les nœuds légers qu’un bloc contient des transactions invalides. Ce mécanisme est mis en œuvre pour la première fois par Al-Bassam, Sonnino et Buterin [8] dans lequel une faute un système de preuve basé sur les codes de correction d’erreur [9] est utilisé. Afin de permettre la création de preuves de défauts, il est nécessaire que les données de tous les blocs, y compris les blocs invalides, soient disponibles pour le réseau : c'est le problème de disponibilité des données, qui est résolu à l'aide d'une approche probabiliste des données. mécanisme d’échantillonnage. La première conception Optimistic Rollup a été présentée par John Adler et Mikerah Quintyne-Collins en 2019 [10], dans lequel des blocs sont publiés sur un autre blockchain qui définit leur consensus sur la commande. 2.1. Optimism Socle rocheux Bedrock [11] est la dernière version de Optimism, un Smart Contract Rollup. La version précédente, la machine virtuelle optimiste (OVM) nécessitait un compilateur ad hoc pour compiler Solidity dans son propre bytecode : en revanche, Bedrock est tout à fait équivalent au EVM dans la mesure où le moteur d'exécution suit la spécification Ethereum Yellow Paper [12]. 2.1.1. Dépôts Les utilisateurs peuvent déposer des transactions via un contrat sur Ethereum, le portail Optimism, en appelant la fonction depositTransaction. Lorsqu'une transaction est exécutée, un L'événement TransactionDeposited est émis, que chaque nœud du Rollup écoute pour traiter dépôts. Une transaction déposée est une transaction L2 dérivée de L1. Si l'appelant du fonction est un contrat, l'adresse est transformée en lui ajoutant une valeur constante : cela évite attaques dans lesquelles un contrat sur L1 a la même adresse qu'un contrat sur L2 mais un code différent. L'inclusion sur L2 d'une transaction déposée est assurée par spécification au sein d'un séquençage fenêtre. Les transactions déposées sont un nouveau type de transaction compatible EIP-2718 [13] avec le préfixe 0x7E, où les champs codés rlp sont : • bytes32 sourceHash : hash qui identifie de manière unique la source de la transaction. • adresse de : l'adresse de l'expéditeur. • adresse à : l'adresse du destinataire, ou l'adresse zéro si la transaction déposée est une création de contrat.• uint256 mint : la valeur à créer sur L2. • valeur uint256 : la valeur à envoyer au destinataire. • données octets : les données d'entrée. • octets gasLimit : la limite de gaz de la transaction. Le sourceHash est calculé comme le keccak256 hash du bloc L1 hash et le journal L1 index, identifiant de manière unique un événement dans un bloc. Puisque les transactions déposées sont initiées sur L1 mais exécutées sur L2, le système a besoin d'un mécanisme permettant de payer sur L1 le gaz dépensé sur L2. Une solution consiste à envoyer de l'ETH via le portail, mais cela implique que chaque appelant (même les appelants indirects) doit être marqué comme payant, et ceci est pas possible pour de nombreux projets existants. L'alternative est de brûler le gaz correspondant sur L1. Le gaz 𝑔alloué à la transaction déposée est appelé gaz garanti. Le prix du gaz L2 sur L1 n'est pas automatiquement synchronisé mais est estimé à l'aide d'un mécanisme similaire à EIP-1559 [14]. La quantité maximale de gaz garantie par bloc Ethereum est de 8 millions, avec un objectif de 2 millions. La quantité 𝑐d’ETH nécessaire pour payer le gaz sur L2 est 𝑐= 𝑔𝑏L2 où 𝑏L2 est le frais de base sur L2. Le contrat sur L1 brûle une quantité de gaz égale à 𝑐/𝑏L2. Le gaz dépensé pour appeler depositTransaction est remboursé sur L2 : si ce montant est supérieur au gaz garanti, aucun gaz n'est brûlé. La première transaction d'un bloc rollup est une transaction déposée avec attributs L1, utilisée pour enregistrer sur un L2, prédéployez les attributs des blocs Ethereum. Les attributs que donne le pré-déploiement les accès sont le numéro de bloc, l'horodatage, les frais de base, le bloc hash et la séquence number, qui est le numéro de bloc de L2 par rapport au bloc L1 associé (également appelé époque) ; ce nombre est réinitialisé lorsqu'une nouvelle époque commence. 2.1.2. Séquençage Les nœuds Rollup dérivent entièrement la chaîne Optimism de Ethereum. Cette chaîne est prolongée à chaque fois de nouvelles transactions sont publiées sur L1, et ses blocs sont à chaque fois réorganisés Les blocs Ethereum sont réorganisés. Le Rollup blockchain est divisé en époques. Pour chaque 𝑛 numéro de bloc de Ethereum, il y a une époque 𝑛 correspondante. Chaque époque contient au moins un bloc, et chaque bloc d'une époque contient une transaction déposée avec des attributs L1. Le premier bloc dans une époque contient toutes les transactions déposées via le portail. Les blocs Layer 2 peuvent également contenait des transactions séquencées, c'est-à-dire des transactions envoyées directement au séquenceur. Le séquenceur accepte les transactions des utilisateurs et construit des blocs. Pour chaque bloc, il construit un lot à publier le Ethereum. Plusieurs lots peuvent être publiés de manière compressée, prenant le nom de la chaîne. Un canal peut être divisé en plusieurs trames, au cas où il serait trop grand pour une seule transaction. Un canal est défini comme la compression avec ZLIB [15] de fichiers codés en rlp. lots. Les champs d'un lot sont le numéro d'époque, l'époque hash, le parent hash, le l'horodatage et la liste des transactions. Une fenêtre de séquençage, identifiée par une époque, contient un nombre fixe 𝑤 de L1 consécutives blocs qu'une étape de dérivation prend en entrée pour construire un nombre variable de blocs L2. Pour époque 𝑛, la fenêtre de séquençage 𝑛inclut les blocs [𝑛, 𝑛+𝑤). Cela implique que la commande des transactions et des blocs L2 dans une fenêtre de séquençage n’est pas corrigé jusqu’à la fin de la fenêtre. Une transaction rollup est dite sécurisée si le lot la contenant a été confirmé sur L1. Cadressont lus à partir des blocs L1 pour reconstruire les lots. La mise en œuvre actuelle ne permet pas la décompression d'un canal doit commencer jusqu'à ce que toutes les trames correspondantes aient été reçues. Invalide les lots sont ignorés. Les transactions de bloc individuelles sont obtenues à partir des lots, qui sont utilisé par le moteur d'exécution pour appliquer des transitions d'état et obtenir l'état Rollup. 2.1.3. Retraits Afin de traiter les retraits, un système de messagerie L2 vers L1 est mis en place. Ethereum doit connaître l'état de L2 afin d'accepter les retraits, et cela se fait en publiant sur la sortie L2 Oracle smart contract sur L1, la racine d'état de chaque bloc L2. Ces racines sont acceptés avec optimisme comme valides (ou finalisés) si aucune vérification des défauts n'est effectuée pendant le période de litige. Seules les adresses désignées comme proposants peuvent publier des racines de sortie. La validité des racines de production est incité à ce que les proposants déposent une mise qui est réduite s'ils sont il a été démontré qu'il a proposé une racine invalide. Les transactions sont initiées en appelant la fonction initier un retrait sur un pré-déploiement sur L2 puis finalisé sur L1 en appelant la fonction finalizeWithdrawalTransaction sur le portail Optimism mentionné précédemment. La racine de sortie correspondant au bloc L2 est obtenue à partir de L2 Output Oracle ; c'est vérifié qu'il est finalisé, c'est-à-dire que le délai de contestation est écoulé ; il est vérifié que la Sortie Root Proof correspond à Oracle Proof ; il est vérifié que le hash du retrait est inclus en utilisant une preuve de retrait ; que le retrait n'est pas encore finalisé ; et puis le l'appel à l'adresse cible est exécuté, avec la limite de gaz, la quantité d'éther et les données spécifiées. 2.1.4. Cannon : le système sans faille Si un nœud complet de cumul, en exécutant localement des lots et des transactions déposées, découvre que l'état Layer 2 ne correspond pas à la racine d'état publiée en chaîne par un proposant, il peut s'exécuter une preuve de faute sur L1 pour prouver que le résultat de la transition de bloc est incorrect. À cause du surcharge, le traitement d'un bloc Rollup entier sur L1 est trop coûteux. La solution mise en œuvre par Bedrock est d'exécuter en chaîne uniquement la première instruction de désaccord de minigeth, le compiler dans une architecture MIPS qui est exécutée sur un interpréteur en chaîne et publiée sur L1. minigeth est une version simplifiée de geth 1 dans laquelle le consensus, le RPC et la base de données ont été supprimés. Pour trouver la première instruction de désaccord, une recherche binaire interactive est effectuée entre celui qui a initié la preuve de faute et celui qui a publié la racine de sortie. Quand la preuve démarre, les deux parties publient la racine de l'état mémoire MIPS à mi-chemin de l'exécution de le bloc sur le contrat Challenge : si le hash correspond cela signifie que les deux parties sont d'accord sur le première moitié de l'exécution publiant ainsi la racine de la moitié de la seconde moitié, sinon la moitié du premier semestre est publié et ainsi de suite. Cela permet d'obtenir la première instruction de désaccord en un nombre logarithmique d'étapes par rapport à l'exécution originale. Si l'un des deux s'arrête en interaction, à la fin de la période de contestation, l'autre participant gagne automatiquement. Pour traiter l'instruction, l'interpréteur MIPS a besoin d'accéder à sa mémoire : puisque la racine est disponibles, les cellules mémoire nécessaires peuvent être publiées en prouvant leur inclusion. Pour accéder l'état du EVM, on utilise le Preimage Oracle : étant donné le hash d'un bloc il renvoie 1https://geth.ethereum.org/docs

l'en-tête du bloc, à partir duquel on peut récupérer le hash du bloc précédent et remonter dans le chaîne, ou obtenez le hash de l'état et les journaux à partir desquels on peut obtenir la pré-image. Le oracle est implémenté par minigeth et remplace la base de données. Des requêtes sont adressées à d'autres nœuds pour obtenir les préimages.

Validity Rollups

Validity Rollups The goal of a Validity Rollup is to cryptographically prove the validity of the state transition given the sequence of transactions with a short proof that can be verified sub-linearly compared to the time of the original computations. These kind of certificates are called computational integrity proofs and are practically implemented with SNARKs (Succint Non-interactive ARgument of Knowledge), which use arithmetic circuits as their computational model. Different SNARK implementations differ in proving time, verification time, the need of a trusted setup and quantum resistance [16, 17]. STARKs (Scalable Transparent ARgument of Knowledge) [18] are a type of SNARKs that does not require a trusted setup and are quantum resistant, while giving up some efficiency on proving and verification compared to other solutions. 3.1. StarkNet StarkNet is a Smart Contract Validity Rollup developed by StarkWare that uses the STARK proof system to validate its state to Ethereum. To facilitate the construction of validity proofs, a virtual machine different than the EVM is used, whose high-level language is Cairo. 3.1.1. Deposits Users can deposit transactions via a contract on Ethereum by calling the sendMessageToL2 function. The message is recorded by computing its hash and increasing a counter. Sequencers listen for the LogMessageToL2 event and encode the information in a StarkNet transaction that calls a function of a contract that has the l1_handler decorator. At the end of execution, when the proof of state transition is produced, the consumption of the message is attached to it and it is deleted by decreasing its counter. The inclusion of deposited transactions is not required by the StarkNet specification, so a gas market is needed to incentivize Sequencers to publish them on L2. In the current version, because the Sequencer is centralized and managed by StarkWare, the cost of deposited transactions is only determined by the cost of executing the deposit. This cost is paid by sending ETH to sendMessageToL2. These Ethers remain locked on L1 and are transferred to the Sequencer on L1, when the deposited transaction is included in a state transition. The amount of ETH sent, if the deposited transaction is included, is fully spent, regardless of the amount of gas consumed on L2. StarkNet does not have a system that makes L1 block attributes available automatically. Alternatively, Fossil is a protocol developed by Oiler Network 2 that allows, given a hash of a block, any information to be obtained from Ethereum by publishing preimages. 2https://www.oiler.network/

3.1.2. Sequencing The current state of StarkNet can be derived entirely from Ethereum. Any state difference between transitions is published on L1 as calldata. Differences are published for each contract and are saved as uint256[] with the following encoding: • Number of field concerning contract deployments. • For each published contract: – The address of the published contract. – The hash of the published contract. – The number of arguments of the contract constructor. – The list of constructor arguments • Number of contract whose storage has been modified. • For each contract that has been modified: – The address of the modified contract. – The number of storage updates. – The key-value pairs of the storage addresses with the new values. The state differences are published in order, so it is sufficient to read them sequentially to reconstruct the state. 3.1.3. Withdrawals To send a message from L2 to L1, the syscall send_message_to_L1 is used. The message is published to L1 by increasing its hash counter along with the proof and finalized by calling the function consumeMessageFromL2 on the StarkGate smart contract on L1, which decrements the counter. Anyone can finalize any withdrawal. 3.1.4. Validity proofs The Cairo Virtual Machine [19] is designed to facilitate the construction of STARK proofs. The Cairo language allows the computation to be described with a high-level programming language, and not directly as a circuit. This is accomplished by a system of polynomial equations 3 representing a single computation: the FDE cycle of a von Neumann architecture. The number of constraints is thus fixed and independent of the type of computation, allowing for only one Verifier program for every program whose computation needs to be proved. StarkNet aggregates multiple transactions into a single STARK proof using a shared prover named SHARP. The proofs are sent to a smart contract on Ethereum, which verifies their validity and updates the Merkle root corresponding to the new state. The sub-linear cost of verifying a validity proof allows its cost to be amortized over multiple transactions. 3called Algebraic Intermediate Representation (AIR)

Cumuls de validité

Cumuls de validité L'objectif d'un Validity Rollup est de prouver cryptographiquement la validité de la transition d'état. étant donné la séquence de transactions avec une courte preuve qui peut être vérifiée de manière sublinéaire par rapport au moment des calculs originaux. Ces types de certificats sont appelés preuves d'intégrité informatique et sont pratiquement implémentés avec des SNARK (Succint Non-interactive ARgument of Knowledge), qui utilisent l'arithmétique. circuits comme modèle informatique. Différentes implémentations de SNARK diffèrent en termes de temps de preuve, temps de vérification, nécessité d’une configuration fiable et résistance quantique [16, 17]. STARK (évolutif ARgument transparent de connaissances) [18] sont un type de SNARK qui ne nécessite pas de confiance configuration et sont résistants aux quantiques, tout en renonçant à une certaine efficacité en matière de preuve et de vérification par rapport à d'autres solutions. 3.1. StarkNet StarkNet est un cumul de validité de contrat intelligent développé par StarkWare qui utilise le STARK système de preuve pour valider son état à Ethereum. Pour faciliter la construction de preuves de validité, un une machine virtuelle différente de EVM est utilisée, dont le langage de haut niveau est Le Caire. 3.1.1. Dépôts Les utilisateurs peuvent déposer des transactions via un contrat sur Ethereum en appelant sendMessageToL2 fonction. Le message est enregistré en calculant son hash et en augmentant un compteur. Séquenceurs écoutez l'événement LogMessageToL2 et codez les informations dans une transaction StarkNet qui appelle une fonction d'un contrat qui a le décorateur l1_handler. En fin d'exécution, lorsque la preuve de transition d'état est produite, la consommation du message y est attachée et il est supprimé en diminuant son compteur. L'inclusion des transactions déposées n'est pas requise par la spécification StarkNet, donc un gaz un marché est nécessaire pour inciter les séquenceurs à les publier sur L2. Dans la version actuelle, parce que le Séquenceur est centralisé et géré par StarkWare, le coût des transactions déposées est uniquement déterminé par le coût d’exécution du dépôt. Ce coût est payé en envoyant ETH à sendMessageToL2. Ces Ethers restent verrouillés sur L1 et sont transférés vers le Séquenceur sur L1, lorsque la transaction déposée est incluse dans une transition d'état. Le montant d’ETH envoyé, si la transaction déposée est incluse, est entièrement dépensée, quelle que soit la quantité de gaz consommée sur L2. StarkNet ne dispose pas d'un système rendant automatiquement disponibles les attributs de bloc L1. Alternativement, Fossil est un protocole développé par Oiler Network 2 qui permet, étant donné un hash d'un bloc, toute information à obtenir auprès de Ethereum en publiant des préimages. 2https://www.oiler.network/3.1.2. Séquençage L'état actuel de StarkNet peut être entièrement dérivé de Ethereum. Toute différence d'état entre les transitions est publié sur L1 en tant que données d'appel. Les écarts sont publiés pour chaque contrat et sont enregistrés sous uint256[] avec le codage suivant : • Nombre de champs concernant les déploiements sous contrat. • Pour chaque contrat publié : – L’adresse du contrat publié. – Le hash du contrat publié. – Le nombre d’arguments du constructeur du contrat. – La liste des arguments du constructeur • Numéro de contrat dont le stockage a été modifié. • Pour chaque contrat modifié : – L’adresse du contrat modifié. – Le nombre de mises à jour du stockage. – Les paires clé-valeur des adresses de stockage avec les nouvelles valeurs. Les différences d'état sont publiées dans l'ordre, il suffit donc de les lire séquentiellement pour reconstruire l'État. 3.1.3. Retraits Pour envoyer un message de L2 à L1, l'appel système send_message_to_L1 est utilisé. Le message est publié en L1 en augmentant son compteur hash avec la preuve et finalisé en appelant le fonction consumeMessageFromL2 sur le StarkGate smart contract sur L1, qui décrémente le compteur. N’importe qui peut finaliser n’importe quel retrait. 3.1.4. Preuves de validité La machine virtuelle du Caire [19] est conçue pour faciliter la construction de preuves STARK. Le langage Cairo permet de décrire le calcul avec une programmation de haut niveau langage, et non directement comme un circuit. Ceci est accompli par un système d'équations polynomiales 3 représentant un seul calcul : le cycle FDE d'une architecture de von Neumann. Le numéro des contraintes est ainsi fixe et indépendant du type de calcul, ne permettant qu'un seul Programme vérificateur pour chaque programme dont le calcul doit être prouvé. StarkNet regroupe plusieurs transactions en une seule preuve STARK à l'aide d'un prouveur partagé nommé SHARP. Les épreuves sont envoyées à un smart contract le Ethereum, qui vérifie leur validité et met à jour la racine Merkle correspondant au nouvel état. Le coût sous-linéaire de la vérification d'un la preuve de validité permet d’amortir son coût sur plusieurs transactions. 3appelée Représentation Algébrique Intermédiaire (AIR)

Comparison

Comparison 4.1. Withdrawal time The most important aspect that distinguishes Optimistic Rollups from Validity Rollups is the time that elapses between the initialization of a withdrawal and its finalization. In both cases, withdrawals are initialized on L2 and finalized on L1. On StarkNet, finalization is possible as soon as the validity proof of the new state root is accepted on Ethereum: theoretically, it is possible to withdraw funds in the first block of L1 following initialization. In practice, the frequency of sending validity proofs on Ethereum is a trade-off between the speed of block finalization and proof aggregation. Currently StarkNet provides validity proofs for verification every 10 hours 4, but it is intended to be decreased as transaction activity increases. On Optimism Bedrock it is possible to finalize a withdrawal only at the end of the dispute period (currently 7 days), after which a root is automatically considered valid. The length of this period is mainly determined by the fact that fault proofs can be censored on Ethereum until its end. The success probability of this type of attack decreases exponentially as time increases: E[subtracted value] = 𝑉𝑝𝑛 where 𝑛is the number of blocks in an interval, 𝑉is the amount of funds that can be subtracted by publishing an invalid root, and 𝑝is the probability of successfully performing a censorship attack in a single block. Suppose that this probability is 99%, that the value locked in the Rollup is one million Ether, and that the blocks in an interval are 1800 (6 hours of blocks with a 12 seconds interval): the expected value is about 0.01391 Ether. The system is made secure by asking Proposers to stake a much larger amount of Ether than the expected value. Winzer et al. showed how to carry out a censorship attack using a simple smart contract that ensures that certain areas of memory in the state do not change [20]. Modeling the attack as a Markov game, the paper shows that censoring is the dominant strategy for a rational block producer if they receive more compensation than including the transaction that changes the memory. The 𝑝value discussed above can be viewed as the percentage of rational block producers in the network, where “rational” does not take into account possibly penalizing externalities, such as less trust in the blockchain that decreases its cryptocurrency value. The following code presents a smart contract that can be used to perform a censorship attack on Bedrock. The attack exploits the incentives of block producers by offering them a bribe to censor the transactions that would modify specific parts of the state. The contract’s main function, claimBribe, allows block producers to claim the bribe if they successfully censor the targeted transaction by checking that the invalid output root is not touched. function claimBribe(bytes memory storageProof) external { require(!claimed[block.number], "bribe already claimed"); OutputProposal memory current = storageOracle.getStorage(L2_ORACLE, block.number, SLOT, storageProof); require(invalidOutputRoot == current.outputRoot, "attack failed"); claimed[block.number] = true; (bool sent, ) = block.coinbase.call{value: bribeAmount}(""); 4https://etherscan.io/address/0xc662c410c0ecf747543f5ba90660f6abebd9c8c4

require(sent, "failed to send ether"); } Listing 1: Example of a contract that incentivizes a censorship attack on Bedrock. The length of the dispute period must also take into account the fact that the fault proof is an interactive proof and therefore enough time must be provided for participants to interact and that any interaction could be censored. If the last move occurs at a time very close to the end of the dispute period, the cost of censoring is significantly less. Although censoring is the dominant strategy, the likelihood of success is lower because censoring nodes are vulnerable to Denial of Service attacks: an attacker can generate very complex transactions that end with the publication of a fault proof at no cost, as no fees would be paid. In extreme cases, a long dispute period allows coordination in the event of a successful censorship attack to organize a fork and exclude the attacking block producers. Another possible attack consists in publishing more state root proposals than disputants can verify, which can be avoided using a frequency limit. 4.1.1. Fast optimistic withdrawals Since the validity of an Optimistic Rollup can be verified at any time by any Full Node, a trusted oracle can be used to know on L1 whether the withdrawal can be finalized safely. This mechanism was first proposed by Maker [21]: an oracle verifies the withdrawal, publishes the result on L1 on which an interest-bearing loan is assigned to the user, which is automatically closed at the end of 7 days, i.e. when the withdrawal can actually be finalized. This solution introduces a trust assumption, but in the case of Maker it is minimized since the oracle operator is managed by the same organization that assumes the risk by providing the loan. 4.2. Transaction costs The cost of L2 transactions is mostly determined by the interaction with the L1. In both solutions the computational cost of transactions is very cheap as it is executed entirely off-chain. Optimism publishes L2 transactions calldata as calldata and rarely (or never) executes fault proofs, therefore calldata is the most expensive resource. On January 12, 2022 a Bedrock network has been launched on the Ethereum’s Goerli testnet. A gas compression rate can be calculated by tracking the amount of gas used on Bedrock in a certain period and by comparing it to the amount of gas spent on L1 for the corresponding blocks. Using this method a gas compression rate of ∼20 : 1 is found, but this figure may differ with real activity on mainnet. StarkNet publishes on Ethereum every change in L2 state as calldata, therefore storage is the most expensive resource. Since the network does not use the EVM, the transaction cost compression cannot be trivially estimated. By assuming the cost of execution and calldata to be negligible, it is possible to calculate the compression ratio of storage writes compared to L1. Assuming no contract is deployed and 10 cells not previously accessed on StarkNet are modified, a storage write cost compression rate of ∼24 : 1 is found. If a cell is overwritten 𝑛times between data publications, the cost of each write will be 1/𝑛compared to the cost of a single write, since only the last one is published. The cost can be further minimized by

compressing frequently used values. The cost of validity proof verification is divided among the transactions it refers to: for example, StarkNet block 4779 contains 200 transactions and its validity proof consumes 267830 units of gas, or 1339.15 gas for each transaction. 4.2.1. Optimizing calldata: cache contract Presented below is a smart contract that implements an address cache for frequently used addresses by taking advantage of the fact that storage and execution are much less expensive resources, along with a Friends contract that demonstrates its use. The latter keeps track of the “friends” of an address that can be registered by calling the addFriend function. If an address has already been used at least once, it can be added by calling the addFriendWithCache function: the cache indices are 4-byte integers while the addresses are represented by 20 bytes, so there is a 5:1 saving on the function argument. The same logic can be used for other data types such as integers or more generally bytes. contract AddressCache { mapping(address => uint32) public address2key; address[] public key2address; function cacheWrite(address _address) internal returns (uint32) { require(key2address.length < type(uint32).max, "AddressCache: cache is full"); require(address2key[_address] == 0, "AddressCache: address already cached"); // keys must start from 1 because 0 means "not found" uint32 key = uint32(key2address.length + 1); address2key[_address] = key; key2address.push(_address); return key; } function cacheRead(uint32 _key) public view returns (address) { require(_key <= key2address.length && _key > 0, "AddressCache: key not found"); return key2address[_key - 1]; } } Listing 2: Address cache contract. contract Friends is AddressCache { mapping(address => address[]) public friends; function addFriend(address _friend) public { friends[msg.sender].push(_friend); cacheWrite(_friend); } function addFriendWithCache(uint32 _friendKey) public { friends[msg.sender].push(cacheRead(_friendKey)); } function getFriends() public view returns (address[] memory) { return friends[msg.sender];

} } Listing 3: Example of a contract that inherits the address cache. The contract supports in cache about 4 billion (232) addresses, and adding one byte gives about 1 trillion (240). 4.2.2. Optimizing storage: Bloom’s filters On StarkNet there are several techniques for minimizing storage usage. If it is not necessary to guarantee the availability of the original data then it is sufficient to save on-chain its hash: this is the mechanism used to save data for an ERC-721 (NFT) [22], i.e., an IPFS link that resolves the hash of the data if available. For data that is stored multiple times, it is possible to use a look-up table similar to the caching system introduced for Optimism, requiring all values to be saved at least once. For some applications, saving all the values can be avoided by using a Bloom filter [23, 24, 25], i.e., a probabilistic data structure that allows one to know with certainty whether an element does not belong to a set but admits a small but non-negligible probability of false positives. A Bloom filter is initialized as an array of 𝑚bits at zero. To add an element, 𝑘hash functions with a uniform random distribution are used, each one mapping to a bit of the array that is set to 1. To check whether an element belongs to the set we run the 𝑘hash functions and verify that the 𝑘bits are set to 1. In a simple Bloom’s filter there is no way to distinguish whether an element actually belongs to the set or is a false positive, a probability that grows as the number of entries increases. After inserting 𝑛elements: P[false positive] = (︃ 1 − [︂ 1 −1 𝑚 ]︂𝑘𝑛)︃𝑘 ≈ (︁ 1 −𝑒−𝑘𝑛/𝑚)︁𝑘 assuming independence of the probability of each bit set. If 𝑛elements (of arbitrary size!) are expected to be included and the probability of a false positive tolerated is 𝑝, the size of the array can be calculated as: 𝑚= −𝑛ln 𝑝 (ln 2)2 While the optimal number of hash functions is: 𝑘= 𝑚 𝑛ln 2 If we assume to insert 1000 elements with a tolerance of 1%, the size of the array is 9585 bits with 𝑘= 6, while for a tolerance of 0.1% it becomes 14377 bits with 𝑘= 9. If a million elements are expected to be inserted, the size of the array becomes about 1170 kB for 1% and 1775 kB for 0.1%, with the same values of 𝑘, since it depends only on 𝑝[26]. In a game where players must not be assigned to an opponent they have already challenged, instead of saving in storage for each player the list of past opponents one can use a Bloom filter. The risk of not challenging some players is often acceptable, and the filter can be reset periodically.

4.3. Ethereum compatibility The main advantage of being compatible with EVM and Ethereum is the reuse of all the available tools. Ethereum smart contracts can be published on Optimism without any modification nor new audits. Wallets remain compatible, development and static analysis tools, general analysis tools, indexing tools and oracles. Ethereum and Solidity have a long history of well-studied vulnerabilities, such as reentrancy attacks, overflows and underflows, flash loans, and oracle manipulations. Because of this, Optimism was able to capture a large amount of value in a short time. Choosing to adopt a different virtual machine implies having to rebuild an entire ecosystem, with the advantage of a greater implementation freedom. StarkNet natively implements account abstraction, which is a mechanism whereby each account is a smart contract that can implement arbitrary logic as long as it complies with an interface (hence the term abstraction): this allows the use of different digital signature schemes, the ability to change the private key using the same address, or use a multisig. The Ethereum community proposed the introduction of this mechanism with EIP-2938 in 2020, but the proposal has remained stale for more than a year as other updates have been given more priority [27]. Another important benefit gained from compatibility is the reuse of existing clients: Optimism uses a version of geth for its own node with only ∼800 lines of difference, which has been developed, tested, and maintained since 2014. Having a robust client is crucial as it defines what is accepted as valid or not in the network. A bug in the implementation of the fault proof system could cause an incorrect proof to be accepted as correct or a correct proof for an invalid block to be accepted as incorrect, compromising the system. The likelihood of this type of attack can be limited with a wider client diversity: Optimism can reuse in addition to geth the other Ethereum clients already maintained, and development of another Erigon-based client is already underway. In 2016 a problem in the memory management of geth was exploited for a DoS attack and the first line of defense was to recommend the use of Parity, the second most used client at the time 5. StarkNet faces the same problem with validity proofs, but the clients have to be written from scratch and the proof system is much more complex, and consequently it is also much more complex to ensure correctness.

Comparaison

Comparaison 4.1. Délai de retrait L'aspect le plus important qui distingue les cumuls optimistes des cumuls de validité est le temps qui s'écoule entre l'initialisation d'un retrait et sa finalisation. Dans les deux cas, les retraits sont initialisés sur L2 et finalisés sur L1. Le StarkNet, la finalisation est possible car dès que la preuve de validité de la nouvelle racine d'état est acceptée le Ethereum : en théorie, c'est possible de retirer des fonds dans le premier bloc de L1 suivant l'initialisation. En pratique, le la fréquence d'envoi des preuves de validité le Ethereum est un compromis entre la vitesse de blocage finalisation et agrégation des preuves. Actuellement, StarkNet fournit des preuves de validité à des fins de vérification. toutes les 10 heures 4, mais il est prévu de diminuer à mesure que l'activité de transaction augmente. Sur Optimism Bedrock il est possible de finaliser un retrait uniquement à la fin du litige période (actuellement 7 jours), après laquelle une racine est automatiquement considérée comme valide. La longueur de ce délai est principalement déterminé par le fait que les preuves de défauts peuvent être censurées le Ethereum jusqu'à sa fin. La probabilité de réussite de ce type d’attaque diminue de façon exponentielle à mesure que le temps augmente : E[valeur soustraite] = 𝑉𝑝𝑛 où 𝑛est le nombre de blocs dans un intervalle, 𝑉est le montant des fonds qui peuvent être soustraits en publiant une racine invalide, et 𝑝 est la probabilité de réussir une censure attaque en un seul bloc. Supposons que cette probabilité soit de 99 %, que la valeur verrouillée dans le Rollup est d'un million d'Ether, et que les blocs dans un intervalle sont de 1800 (6 heures de blocs avec un 12 secondes d'intervalle) : la valeur attendue est d'environ 0,01391 Ether. Le système est sécurisé par demander aux proposants de miser une quantité d’Ether beaucoup plus importante que la valeur attendue. Winzer et coll. a montré comment mener une attaque de censure en utilisant un simple smart contract cela garantit que certaines zones de mémoire dans l'état ne changent pas [20]. Modélisation de l'attaque en tant que jeu de Markov, l'article montre que la censure est la stratégie dominante pour une société rationnelle. producteur de bloc s'il reçoit une compensation plus élevée que l'inclusion de la transaction qui change la mémoire. La valeur 𝑝 discutée ci-dessus peut être considérée comme le pourcentage du bloc rationnel producteurs du réseau, où le « rationnel » ne prend pas en compte les éventuelles pénalisations des externalités, telles qu'une moindre confiance dans le blockchain qui diminue sa valeur de crypto-monnaie. Le code suivant présente un smart contract qui peut être utilisé pour effectuer une attaque de censure sur le substrat rocheux. L'attaque exploite les incitations des producteurs de blocs en leur offrant un pot-de-vin censurer les transactions qui modifieraient des parties spécifiques de l’État. Le principal du contrat la fonction,claimBribe, permet aux producteurs de blocs de réclamer le pot-de-vin s'ils réussissent à censurer la transaction ciblée en vérifiant que la racine de sortie invalide n'est pas touchée. fonction réclamerBribe (octets de mémoire storageProof) externe { require(!claimed[block.number], "pot-de-vin déjà réclamé"); Mémoire actuelle de la proposition de sortie = storageOracle.getStorage (L2_ORACLE, block.number, SLOT, stockageProof); require(invalidOutputRoot == current.outputRoot, "l'attaque a échoué"); réclamé[bloc.numéro] = vrai ; (bool envoyé, ) = block.coinbase.call{value: bribeAmount}(""); 4https://etherscan.io/address/0xc662c410c0ecf747543f5ba90660f6abebd9c8c4require(sent, "échec de l'envoi d'éther"); } Liste 1 : Exemple de contrat qui incite à une attaque de censure contre Bedrock. La durée du délai de contestation doit également tenir compte du fait que la preuve de la faute est une preuve interactive et donc suffisamment de temps doit être prévu pour que les participants puissent interagir et que toute interaction pourrait être censurée. Si le dernier coup se produit à un moment très proche du À la fin de la période de litige, le coût de la censure est nettement moindre. Même si la censure est la stratégie dominante, la probabilité de succès est plus faible car les nœuds de censure sont vulnérables aux Attaques par déni de service : un attaquant peut générer des transactions très complexes se terminant par le publication d'une preuve de défaut sans frais, car aucun frais ne serait payé. Dans les cas extrêmes, une longue période de litige permet une coordination en cas de succès attaque de censure pour organiser un fork et exclure les producteurs de blocs attaquants. Un autre une attaque possible consiste à publier plus de propositions de racine d'état que les parties en conflit ne peuvent en vérifier, ce qui peut être évité en utilisant une limite de fréquence. 4.1.1. Retraits optimistes rapides Étant donné que la validité d'un cumul optimiste peut être vérifiée à tout moment par n'importe quel nœud complet, un oracle de confiance peut être utilisé pour savoir sur L1 si le retrait peut être finalisé en toute sécurité. Ceci mécanisme a été proposé pour la première fois par Maker [21] : un oracle vérifie le retrait, publie le résultat sur L1 sur lequel un prêt rémunéré est attribué à l'usager, qui est automatiquement clôturé au bout de 7 jours, c'est à dire lorsque le retrait peut effectivement être finalisé. Cette solution introduit une hypothèse de confiance, mais dans le cas de Maker elle est minimisée puisque l'opérateur oracle est géré par la même organisation qui assume le risque en accordant le prêt. 4.2. Coûts de transaction Le coût des transactions L2 est principalement déterminé par l’interaction avec le L1. Dans les deux solutions le coût de calcul des transactions est très bon marché car elles sont exécutées entièrement hors chaîne. Optimism publie les données d'appel des transactions L2 en tant que données d'appel et exécute rarement (ou jamais) les erreurs. preuves, donc les données d'appel sont la ressource la plus chère. Le 12 janvier 2022, un réseau Bedrock a été lancé sur le réseau de test Goerli de Ethereum. Un taux de compression de gaz peut être calculé en suivant la quantité de gaz utilisée sur Bedrock au cours d'une certaine période et en la comparant à la quantité de gaz dépensée sur L1 pour les blocs correspondants. En utilisant cette méthode, une compression de gaz un taux de ∼20 : 1 est trouvé, mais ce chiffre peut différer en fonction de l'activité réelle sur le réseau principal. StarkNet publie sur Ethereum chaque changement d'état L2 sous forme de données d'appel, le stockage est donc la ressource la plus chère. Puisque le réseau n'utilise pas le EVM, le coût de transaction la compression ne peut pas être estimée de manière triviale. En assumant le coût d'exécution et les données d'appel pour être négligeable, il est possible de calculer le taux de compression des écritures de stockage par rapport à L1. En supposant qu'aucun contrat n'est déployé et que 10 cellules non accessibles précédemment sur StarkNet sont modifié, un taux de compression du coût d'écriture du stockage de ∼24 : 1 est trouvé. Si une cellule est écrasée 𝑛fois entre les publications de données, le coût de chaque écriture sera de 1/𝑛 par rapport au coût d'une seule écriture, puisque seule la dernière est publiée. Le coût peut être encore minimisé encompresser les valeurs fréquemment utilisées. Le coût de la vérification de la preuve de validité est réparti entre les transactions auxquelles il fait référence : par exemple, le bloc StarkNet 4779 contient 200 transactions et son la preuve de validité consomme 267 830 unités de gaz, soit 1 339,15 gaz pour chaque transaction. 4.2.1. Optimisation des données d'appel : contrat de cache Présenté ci-dessous est un smart contract qui implémente un cache d'adresses pour les adresses en profitant du fait que le stockage et l’exécution sont beaucoup moins coûteux ressources, ainsi qu’un contrat Amis qui démontre son utilisation. Ce dernier assure le suivi des « amis » d'une adresse qui peut être enregistrée en appelant la fonction addFriend. Si une adresse a déjà été utilisé au moins une fois, il peut être ajouté en appelant la méthode addFriendWithCache fonction : les indices du cache sont des entiers de 4 octets tandis que les adresses sont représentées par 20 octets, il y a donc une économie de 5:1 sur l'argument de la fonction. La même logique peut être utilisée pour d'autres données des types tels que des entiers ou plus généralement des octets. contrat AddressCache { mapping(adresse => uint32) adresse publique2key ; adresse[] clé publique2adresse ; function cacheWrite(address _address) renvoie interne (uint32) { require(key2address.length < type(uint32).max, "AddressCache : le cache est plein"); require(address2key[_address] == 0, "AddressCache : adresse déjà mise en cache"); // les clés doivent commencer à 1 car 0 signifie "introuvable" clé uint32 = uint32(key2address.length + 1); adresse2key[_address] = clé ; key2address.push(_address); clé de retour ; } la fonction cacheRead (uint32 _key) renvoie la vue publique (adresse) { require(_key <= key2address.length && _key > 0, "AddressCache : clé introuvable"); return key2address[_key - 1] ; } } Listing 2 : Contrat de cache d’adresses. Le contrat Amis est AddressCache { mapping(adresse => adresse[]) amis publics ; function addFriend (adresse _friend) public { amis[msg.sender].push(_friend); cacheWrite(_friend); } function addFriendWithCache(uint32 _friendKey) public { amis[msg.sender].push(cacheRead(_friendKey)); } la fonction getFriends() vue publique renvoie (adresse[] mémoire) { renvoyer les amis[msg.sender] ;} } Listing 3 : Exemple de contrat qui hérite du cache d'adresses. Le contrat prend en charge en cache environ 4 milliards (232) d'adresses, et l'ajout d'un octet donne environ 1 billion (240). 4.2.2. Optimiser le stockage : les filtres Bloom Sur StarkNet, il existe plusieurs techniques pour minimiser l'utilisation du stockage. S'il n'est pas nécessaire de garantir la disponibilité des données originales alors il suffit de sauvegarder en chaîne ses hash : ce est le mécanisme utilisé pour sauvegarder les données d'un ERC-721 (NFT) [22], c'est-à-dire un lien IPFS qui résout le hash des données si disponibles. Pour les données stockées plusieurs fois, il est possible d'utiliser une recherche table similaire au système de mise en cache introduit pour Optimism, exigeant que toutes les valeurs soient enregistrées dans au moins une fois. Pour certaines applications, la sauvegarde de toutes les valeurs peut être évitée en utilisant un filtre Bloom [23, 24, 25], c'est-à-dire une structure de données probabiliste qui permet de savoir avec certitude si un élément n'appartient pas à un ensemble mais admet une probabilité faible mais non négligeable de faux points positifs. Un filtre Bloom est initialisé sous la forme d’un tableau de 𝑚bits à zéro. Pour ajouter un élément, les fonctions 𝑘hash avec une distribution aléatoire uniforme sont utilisés, chacun correspondant à un bit du tableau défini à 1. Pour vérifier si un élément appartient à l'ensemble, nous exécutons les fonctions 𝑘hash et vérifions que les 𝑘bits sont fixés à 1. Dans un simple filtre de Bloom, il n’y a aucun moyen de distinguer si un l'élément appartient réellement à l'ensemble ou est un faux positif, une probabilité qui augmente avec le nombre des entrées augmente. Après avoir inséré 𝑛éléments : P[faux positif] = (︃ 1 - [︂ 1 −1 𝑚 ]︂𝑘𝑛)︃𝑘 ≈ (︁ 1 −𝑒−𝑘𝑛/𝑚)︁𝑘 en supposant l'indépendance de la probabilité de chaque ensemble de bits. Si 𝑛éléments (de taille arbitraire !) sont devrait être inclus et la probabilité d’un faux positif toléré est 𝑝, la taille du tableau peut être calculé comme suit : 𝑚= −𝑛ln 𝑝 (ligne 2)2 Alors que le nombre optimal de fonctions hash est : 𝑘= 𝑚 𝑛ln 2 Si l'on suppose insérer 1000 éléments avec une tolérance de 1%, la taille du tableau est de 9585 bits avec 𝑘= 6, alors que pour une tolérance de 0,1% cela devient 14377 bits avec 𝑘= 9. Si un million d'éléments sont censés être insérés, la taille du tableau devient environ 1 170 Ko pour 1 % et 1 775 Ko pour 0,1%, avec les mêmes valeurs de 𝑘, puisque cela dépend uniquement de 𝑝[26]. Dans un jeu où les joueurs ne doivent pas être assignés à un adversaire qu'ils ont déjà défié, au lieu de sauvegarder en mémoire pour chaque joueur la liste des anciens adversaires, on peut utiliser un Bloom filtre. Le risque de ne pas défier certains joueurs est souvent acceptable, et le filtre peut être réinitialisé périodiquement.4.3. Compatibilité Ethereum Le principal avantage d'être compatible avec EVM et Ethereum est la réutilisation de tous les outils. Les Ethereum smart contracts peuvent être publiés sur Optimism sans aucune modification ni de nouveaux audits. Les wallets restent compatibles, outils de développement et d'analyse statique, analyse générale outils, outils d'indexation et oracles. Ethereum et Solidity ont une longue histoire de recherches bien étudiées vulnérabilités, telles que les attaques de réentrée, les débordements et les sous-versements, les prêts flash et oracle manipulations. Grâce à cela, Optimism a pu capturer une grande quantité de valeur en un court laps de temps. le temps. Choisir d'adopter une machine virtuelle différente implique de devoir reconstruire tout un écosystème, avec l’avantage d’une plus grande liberté de mise en œuvre. StarkNet implémente le compte de manière native abstraction, qui est un mécanisme par lequel chaque compte est un smart contract qui peut implémenter logique arbitraire pour autant qu’elle respecte une interface (d’où le terme abstraction) : cela permet l'utilisation de différents schémas de signature numérique, la possibilité de modifier la clé privée à l'aide du même adresse, ou utilisez un multisig. La communauté Ethereum a proposé l'introduction de ce mécanisme avec EIP-2938 en 2020, mais la proposition est restée obsolète pendant plus d'un an car les autres mises à jour ont reçu plus de priorité [27]. Un autre avantage important tiré de la compatibilité est la réutilisation des clients existants : Optimism utilise une version de geth pour son propre nœud avec seulement ∼800 lignes de différence, ce qui a été développé, testé et maintenu depuis 2014. Avoir un client robuste est crucial car il définit ce qui est accepté comme valide ou non dans le réseau. Un bug dans l'implémentation de la preuve de faute Le système pourrait faire en sorte qu'une preuve incorrecte soit acceptée comme correcte ou une preuve correcte pour un invalide. le bloc soit accepté comme incorrect, compromettant ainsi le système. La probabilité de ce type de l'attaque peut être limitée avec une plus grande diversité de clients : Optimism peut réutiliser en plus de geth le d'autres clients Ethereum sont déjà maintenus et le développement d'un autre client basé sur Erigon est en cours déjà en cours. En 2016, un problème dans la gestion de la mémoire de geth a été exploité pendant un certain temps. L'attaque DoS et la première ligne de défense consistaient à recommander l'utilisation de Parity, le deuxième plus client utilisé à l'époque 5. StarkNet est confronté au même problème avec les preuves de validité, mais les clients doivent être écrits à partir de zéro et le système de preuve est beaucoup plus complexe, et par conséquent il est également beaucoup plus complexe de garantir l'exactitude.

Conclusion

Conclusion Rollups are the most promising solution available today to solve the scalability problem in decentralized blockchains, paving the way for the era of modular blockchains as opposed to monolithic blockchains. The choice of developing either an Optimistic Rollup or a Validity Rollup is mainly shown as a trade-off between complexity and agility. StarkNet has numerous advantages such as fast withdrawals, structural inability to have invalid state transitions, lower transaction cost at the expense of a longer development period and incompatibility with EVM, while Optimism has leveraged the network economy to quickly gain a major share of the market. Optimism Bedrock, however, possesses a modular design that allows it to become a Validity 5https://blog.ethereum.org/2016/09/22/ethereum-network-currently-undergoing-dos-attack

Rollup in the future: Cannon currently uses minigeth compiled to MIPS for its fault proof system, but the same architecture can be used to obtain a circuit and produce validity proofs. Compiling a complex machine such as the EVM for a microarchitecture results in a simpler circuit that does not need to be modified and re-verified in case of upgrades. RISC Zero is a verifiable microarchitecture with STARK proofs already in development based on RISC-V that can be used for this purpose as an alternative to MIPS [28]. One aspect that should not be underestimated is the complexity in understanding how the technology works. A strength of traditional blockchains is to be able to verify the state of the blockchain without trusting any third party entity. However, in the case of StarkNet, it is necessary to trust the implementation when it is not possible to verify the various components based on cryptography and advanced mathematics. This may initially create friction for the adoption of the technology, but as the tools and the usage of integrity proofs advance even outside the blockchain field this problem will be hopefully solved.

Conclusion

Conclusion Les rollups sont la solution la plus prometteuse disponible aujourd'hui pour résoudre le problème d'évolutivité dans des blockchain décentralisés, ouvrant la voie à l'ère des blockchain modulaires par opposition aux blockchain monolithiques. Le choix de développer soit un Rollup Optimiste, soit un Rollup de Validité est principalement illustré comme un compromis entre complexité et agilité. StarkNet présente de nombreux avantages tels que la rapidité retraits, incapacité structurelle à avoir des transitions d'état invalides, coût de transaction inférieur au au prix d'une période de développement plus longue et d'une incompatibilité avec EVM, alors que Optimism a a tiré parti de l’économie de réseau pour conquérir rapidement une part importante du marché. Optimism Bedrock possède cependant une conception modulaire qui lui permet de devenir un Validity 5https://blog.ethereum.org/2016/09/22/ethereum-network-currently-undergoing-dos-attack

Rollup dans le futur : Cannon utilise actuellement minigeth compilé en MIPS pour sa preuve de panne système, mais la même architecture peut être utilisée pour obtenir un circuit et produire des preuves de validité. Compiler une machine complexe telle que la EVM pour une microarchitecture aboutit à un système plus simple. circuit qui n’a pas besoin d’être modifié et revérifié en cas de mises à niveau. RISC Zéro est un microarchitecture vérifiable avec des preuves STARK déjà en développement basées sur RISC-V qui peut être utilisé à cette fin comme alternative à MIPS [28]. Un aspect à ne pas sous-estimer est la complexité de comprendre comment le la technologie fonctionne. L’un des points forts des blockchain traditionnels est de pouvoir vérifier l’état de le blockchain sans faire confiance à aucune entité tierce. Cependant, dans le cas de StarkNet, il est nécessaire de faire confiance à la mise en œuvre lorsqu'il n'est pas possible de vérifier les différents composants basé sur la cryptographie et les mathématiques avancées. Cela peut initialement créer des frictions pour le l'adoption de la technologie, mais à mesure que les outils et l'utilisation des preuves d'intégrité progressent encore en dehors du champ blockchain, ce problème sera, espérons-le, résolu.