Documentação Técnica Optimism

Analysis and Comparison between Optimism and StarkNet

Tác giả Optimism Collective · 2021

Optimism không có whitepaper truyền thống. Là một optimistic rollup Ethereum Layer 2, thiết kế và thông số kỹ thuật của nó được ghi lại qua tài liệu kỹ thuật, đặc tả OP Stack và các bài đăng nghiên cứu thay vì một bài báo học thuật chính thức duy nhất.

🇺🇸 English (Bản gốc)

🇧🇷 Português (Bản dịch)

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...

Resumo

O artigo aborda o problema de escalabilidade em blockchains descentralizados analisando a compensação entre o rendimento da transação e os requisitos de hardware para executar um nó. Rollups, ou seja, tecnologias para verificação on-chain de blocos executados fora da cadeia, são apresentados na forma de provas de falha ou de validade. Comparamos Rollups Otimistas e Rollups de Validade em relação ao tempo de retirada, custos de transação, técnicas de otimização e compatibilidade com o ecossistema Ethereum. Nossa análise revela que Optimism Bedrock atualmente tem uma taxa de compressão de gás de aproximadamente 20:1, enquanto StarkNet atinge uma taxa de compressão de custo de gravação de armazenamento de cerca de 24:1. Também discutimos técnicas para otimizar ainda mais essas taxas, como o uso de contratos de cache e filtros Bloom. Em última análise, as nossas conclusões destacam os compromissos entre complexidade e agilidade na escolha entre rollups otimistas e de validade. Palavras-chave Blockchain, Escalabilidade, Rollup 1. Introdução A tecnologia Blockchain ganhou atenção significativa devido ao seu potencial para revolucionar vários setores. No entanto, a escalabilidade continua a ser um grande desafio, já que a maioria dos blockchains enfrentam um compromisso entre escalabilidade, descentralização e segurança, comumente referido como o Trilema da Escalabilidade [1, 2]. Para aumentar o rendimento de um blockchain, uma solução trivial é aumentar o tamanho do bloco. No contexto de Ethereum, isso significa aumentar a quantidade máxima de gás que um bloco pode conter. Como cada nó completo deve validar todas as transações de cada bloco, à medida que o rendimento aumenta, os requisitos de hardware também aumentam, levando a uma maior centralização da rede. Alguns blockchains, como Bitcoin e Ethereum, otimizam seu design para maximizar sua descentralização arquitetônica, enquanto outros, como Binance Smart Chain e Solana, são projetados para serem o mais rápidos e baratos possível. As redes descentralizadas limitam artificialmente o rendimento do blockchain para reduzir os requisitos de hardware para participar da rede. Ao longo dos anos, foram feitas tentativas para encontrar uma solução para o Trilema, como os canais estaduais [3] e Plasma [4, 5]. Essas soluções têm a característica de mover algumas atividades para fora da cadeia, vincular atividades on-chain a atividades fora da cadeia usando smart contracts e verificar DLT 2023: 5th Distributed Ledger Technology Workshop, 25 a 26 de maio de 2023, Bolonha, Itália $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Direitos autorais deste artigo de seus autores. Uso permitido sob Creative Commons License Attribution 4.0 International (CC BY 4.0). Procedimentos do Workshop CEUR http://ceur-ws.org ISSN 1613-0073 Procedimentos do Workshop CEUR (CEUR-WS.org) na rede o que está acontecendo fora da rede. No entanto, os canais de plasma e de estado são limitados no suporte a smart contracts gerais. Rollups são blockchains (chamados Layer 2 ou L2) que publicam seus blocos em outro blockchain (Layer 1 ou L1) e, portanto, herdam seu consenso, disponibilidade de dados e propriedades de segurança. Elas, ao contrário de outras soluções, suportam computação arbitrária. Rollups possuem três componentes principais: • Sequenciadores: nós que recebem transações Rollup de usuários e as combinam em um bloco que é enviado para Layer 1. O bloco consiste em pelo menos a raiz do estado (por exemplo, uma raiz Merkle) e os dados necessários para reconstruir e validar o estado. O Layer 1 define o...

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.

Introdução

Introdução A tecnologia Blockchain ganhou atenção significativa devido ao seu potencial para revolucionar diversas indústrias. No entanto, a escalabilidade continua a ser um grande desafio, uma vez que a maioria dos blockchains enfrentam um compromisso entre escalabilidade, descentralização e segurança, comumente referido como o Trilema de escalabilidade [1, 2]. Para aumentar o rendimento de um blockchain, uma solução trivial é para aumentar o tamanho do bloco. No contexto de Ethereum, isso significa aumentar o máximo quantidade de gás que um bloco pode conter. Como cada nó completo deve validar todas as transações de cada bloco, à medida que a taxa de transferência aumenta, os requisitos de hardware também aumentam, levando a um maior centralização da rede. Alguns blockchains, como Bitcoin e Ethereum, otimizam seus design para maximizar sua descentralização arquitetônica, enquanto outros, como o Binance Smart Chain e Solana são projetados para serem o mais rápidos e baratos possíveis. Redes descentralizadas limitar artificialmente o rendimento do blockchain para reduzir os requisitos de hardware para participar da rede. Ao longo dos anos, foram feitas tentativas para encontrar uma solução para o Trilema, tais como medidas estatais canais [3] e Plasma [4, 5]. Estas soluções têm a característica de movimentar alguma atividade fora da cadeia, vinculando a atividade na cadeia à atividade fora da cadeia usando smart contracts e verificando DLT 2023: 5º Workshop de Tecnologia de Ledger Distribuído, 25 a 26 de maio de 2023, Bolonha, Itália $ [email protected] (L. Donno) https://lucadonnoh.github.io/ (L. Donno) 0000-0001-9221-3529 (L. Donno) © 2023 Direitos autorais deste artigo de seus autores. Uso permitido sob Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Oficina Processos http://ceur-ws.org ISSN 1613-0073 Anais do Workshop CEUR (CEUR-WS.org)na cadeia o que está acontecendo fora da cadeia. No entanto, tanto os canais de plasma quanto os de estado são limitados em seu apoio aos smart contracts gerais. Rollups são blockchains (chamados Layer 2 ou L2) que publicam seus blocos em outro blockchain (Layer 1 ou L1) e, portanto, herda seu consenso, disponibilidade de dados e propriedades de segurança. Eles, ao contrário de outras soluções, suporta computação arbitrária. Os rollups têm três componentes principais: • Sequenciadores: nós que recebem transações Rollup dos usuários e as combinam em um bloco que é enviado para Layer 1. O bloco consiste em pelo menos a raiz do estado (por exemplo, um Merkle root) e os dados necessários para reconstruir e validar o estado. O Layer 1 define o canônico blockchain do L2 estabelecendo a ordenação dos dados publicados. • Nós completos de rollup: nós que obtêm, processam e validam blocos de rollup da camada 1 verificando se a raiz está correta. Se um bloco contém transações inválidas, então descartado, o que impede que os sequenciadores criem blocos válidos que incluam blocos inválidos transações. • Nós light de rollup: nós que obtêm blocos de rollup de Layer 1, mas não calculam o novo estado eles mesmos. Eles verificam se a nova raiz de estado é válida usando técnicas como provas de culpa ou validade. Os rollups alcançam escalabilidade diminuindo o custo amortizado das transações conforme o número de usuários aumenta. Isso ocorre porque o custo para garantir a validade de blockchain cresce sublinearmente no que diz respeito ao custo de verificação individual das transações. Os rollups diferem de acordo com o mecanismo pelo qual eles garantem a validade da execução da transação em nós leves: em Rollups Otimistas são garantidos por um modelo econômico e por provas de falhas, enquanto em Validade Rollups são garantidos criptograficamente usando provas de validade. Os nós leves podem ser implementados como smart contracts em Layer 1. Eles aceitam a raiz do novo estado e verificar a validade ou provas de falha: esses Rollup são, portanto, chamados de Contrato Inteligente Acumulações. Se os nós leves forem independentes, eles serão chamados de Rollups Soberanos [6]. A vantagem de usar um Smart Contract Rollup é ser capaz de construir uma ponte com confiança minimizada entre os dois blockchains: como a validade do estado L2 é comprovada para L1, um sistema de transações de L2 a L1 podem ser implementados, permitindo saques. A desvantagem é que o custo do transações depende do custo de verificação do estado em L1: se a camada base estiver saturada por outras atividades, o custo das transações no Rollup também aumenta. As camadas de dados e de consenso são as que determinam a segurança do sistema como eles definem a ordem das transações, evitam ataques e disponibilizam dados para comprovar o estado validade. Contribuição em papel Neste artigo, estudamos Optimistic e Validity Rollups, dois inovadores soluções para o Trilema de Escalabilidade, com foco em implementações notáveis, como Optimism Bedrock e StarkNet. Nossas contribuições incluem uma comparação abrangente desses soluções, uma análise dos tempos de retirada e uma discussão sobre um possível ataque a Optimism Base rochosa. Além disso, calculamos suas taxas de compressão de gás, fornecemos otimizações específicas da aplicação e apresentamos as vantagens e desvantagens de se afastar do Ethereum Máquina Virtual (EVM).

Estrutura do papel O artigo está organizado da seguinte forma. Na seção 2, Rollups otimistas são introduzido pela análise de Optimism Bedrock. Na seção 3, os Rollups de Validade são introduzidos por analisando StarkNet. Na seção 4 comparamos as duas soluções. Finalmente, na seção 5 desenhamos algumas conclusões.

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.

Rollups otimistas

Rollups otimistas A ideia de aceitar de forma otimista a saída dos blocos sem verificar sua execução é já presente no white paper Bitcoin [7], discutindo nós de luz. Esses nós seguem apenas a cadeia de cabeçalho, verificando a regra de consenso, tornando-os vulneráveis à aceitação de blocos contendo transações inválidas no caso de um ataque de 51%. Nakamoto propõe resolver isso problema usando um sistema de “alerta” para avisar os nós leves de que um bloco contém transações inválidas. Este mecanismo foi implementado pela primeira vez por Al-Bassam, Sonnino e Buterin [8] em que uma falha sistema de prova baseado em códigos de correção de erros [9] é usado. Para permitir a criação de provas de falhas, é necessário que os dados de todos os blocos, inclusive os blocos inválidos, estejam disponíveis para a rede: este é o Problema de Disponibilidade de Dados, que é resolvido usando uma análise probabilística de dados mecanismo de amostragem. O primeiro design Optimistic Rollup foi apresentado por John Adler e Mikerah Quintyne-Collins em 2019 [10], em que os blocos são publicados em outro blockchain que define seu consenso sobre o pedido. 2.1. Optimism Base rochosa Bedrock [11] é a versão mais recente de Optimism, um Smart Contract Rollup. A versão anterior, a Optimistic Virtual Machine (OVM) exigia um compilador ad hoc para compilar o Solidity em seu próprio bytecode: em contraste, Bedrock é totalmente equivalente ao EVM em que o mecanismo de execução segue a especificação do papel amarelo Ethereum [12]. 2.1.1. Depósitos Os usuários podem depositar transações por meio de um contrato no Ethereum, o Portal Optimism, chamando a função depositTransaction. Quando uma transação é executada, um O evento TransactionDeposited é emitido, e cada nó no Rollup escuta para processar depósitos. Uma transação depositada é uma transação L2 derivada de L1. Se o chamador do função é um contrato, o endereço é transformado adicionando-lhe um valor constante: isso evita ataques em que um contrato em L1 tem o mesmo endereço que um contrato em L2, mas um código diferente. A inclusão em L2 de uma transação depositada é garantida pela especificação dentro de um sequenciamento janela. As transações depositadas são um novo tipo de transação compatível com EIP-2718 [13] com prefixo 0x7E, onde os campos codificados em rlp são: • bytes32 sourceHash: hash que identifica exclusivamente a origem da transação. • endereço de: o endereço do remetente. • endereço para: o endereço do destinatário, ou o endereço zero se a transação depositada for uma criação de contrato.• uint256 mint: o valor a ser criado em L2. • valor uint256: valor a ser enviado ao destinatário. • dados de bytes: os dados de entrada. • bytes gasLimit: o limite gas da transação. O sourceHash é calculado como o keccak256 hash do bloco L1 hash e o log L1 índice, identificando exclusivamente um evento em um bloco. Como as transações depositadas são iniciadas em L1, mas executadas em L2, o sistema precisa de um mecanismo para pagar em L1 pelo gás gasto em L2. Uma solução é enviar ETH pelo Portal, mas isso implica que cada chamador (mesmo os chamadores indiretos) deve ser marcado como pagável, e isso é não é possível para muitos projetos existentes. A alternativa é queimar o gás correspondente em L1. O gás 𝑔alocado para a transação depositada é chamado de gás garantido. O preço do gás L2 em L1 não é sincronizado automaticamente, mas é estimado usando um mecanismo semelhante ao EIP-1559 [14]. A quantidade máxima de gás garantida por bloco Ethereum é de 8 milhões, com meta de 2 milhões. A quantidade 𝑐de ETH necessária para pagar o gás em L2 é 𝑐= 𝑔𝑏L2 onde 𝑏L2 é o taxa base em L2. O contrato em L1 queima uma quantidade de gás igual a 𝑐/𝑏L2. O gás gasto para ligar depositTransaction é reembolsado em L2: se este valor for maior que o gás garantido, nenhum gás é queimado. A primeira transação de um bloco rollup é uma transação depositada com atributos L1, usada para registrar em um L2 pré-implante os atributos dos blocos Ethereum. Os atributos que a pré-implantação fornece acesso são o número do bloco, o carimbo de data / hora, a taxa base, o bloco hash e a sequência número, que é o número do bloco L2 relativo ao bloco L1 associado (também chamado de época); este número é redefinido quando uma nova época começa. 2.1.2. Sequenciamento Os nós Rollup derivam a cadeia Optimism inteiramente de Ethereum. Esta cadeia é estendida cada vez que novas transações são publicadas em L1, e seus blocos são reorganizados cada vez Ethereum blocos são reorganizados. O Rollup blockchain é dividido em épocas. Para cada 𝑛 número do bloco de Ethereum, há uma época 𝑛 correspondente. Cada época contém pelo menos um bloco, e cada bloco em uma época contém uma transação depositada com atributos L1. O primeiro bloco em uma época contém todas as transações depositadas através do Portal. Layer 2 blocos também podem continha transações sequenciadas, ou seja, transações enviadas diretamente ao sequenciador. O sequenciador aceita transações de usuários e constrói blocos. Para cada bloco, ele constrói um lote a ser publicado em Ethereum. Vários lotes podem ser publicados de forma compactada, tomando o nome do canal. Um canal pode ser dividido em vários frames, caso seja muito grande para uma única transação. Um canal é definido como a compactação com ZLIB [15] de canais codificados em rlp lotes. Os campos de um lote são o número da época, a época hash, o pai hash, o carimbo de data/hora e a lista de transações. Uma janela de sequenciação, identificada por uma época, contém um número fixo 𝑤de L1 consecutivos blocos que uma etapa de derivação toma como entrada para construir um número variável de blocos L2. Para época 𝑛, a janela de sequenciamento 𝑛 inclui os blocos [𝑛, 𝑛+𝑤). Isto implica que a ordenação O número de transações e blocos L2 dentro de uma janela de sequenciamento não é corrigido até que a janela termine. Uma transação rollup é chamada de segura se o lote que a contém foi confirmado em L1. Moldurassão lidos de blocos L1 para reconstruir lotes. A implementação atual não permite a descompressão de um canal comece até que todos os quadros correspondentes tenham sido recebidos. Inválido lotes são ignorados. As transações em bloco individuais são obtidas dos lotes, que são usado pelo mecanismo de execução para aplicar transições de estado e obter o estado Rollup. 2.1.3. Retiradas Para processar saques, é implementado um sistema de mensagens L2 para L1. Ethereum precisa saber o estado do L2 para aceitar saques, e isso é feito publicando no Oracle de saída L2 smart contract em L1 a raiz de estado de cada bloco L2. Essas raízes são otimistamente aceitos como válidos (ou finalizados) se nenhuma prova de falha for realizada durante o período de disputa. Somente endereços designados como Proponentes podem publicar raízes de saída. A validade das raízes da produção é incentivada fazendo com que os proponentes depositem uma participação que será reduzida se eles forem mostrado ter proposto uma raiz inválida. As transações são iniciadas chamando a função inicieWithdrawal em uma pré-implantação em L2 e, em seguida, finalize em L1 chamando a função finalizeWithdrawalTransaction no Portal Optimism mencionado anteriormente. A raiz de saída correspondente ao bloco L2 é obtida do L2 Output Oracle; é verificou que está finalizado, ou seja, que o período de disputa já passou; verifica-se que a Saída A Prova Raiz corresponde à Prova Oracle; verifica-se que o hash do saque está incluído nele utilizando um Comprovante de Saque; que a retirada ainda não foi finalizada; e então o a chamada para o endereço de destino é executada, com o limite de gás especificado, quantidade de Ether e dados. 2.1.4. Cannon: o sistema à prova de falhas Se um Rollup Full Node, ao executar localmente lotes e transações depositadas, descobrir que o estado Layer 2 não corresponde à raiz do estado publicada na cadeia por um proponente, ele pode ser executado uma prova de falha em L1 para provar que o resultado da transição do bloco está incorreto. Por causa do sobrecarga, processar um bloco Rollup inteiro em L1 é muito caro. A solução implementada por Bedrock é executar on-chain apenas a primeira instrução de desacordo de minigeth, compilando-o em uma arquitetura MIPS que é executada em um intérprete on-chain e publicada em L1. minigeth é uma versão simplificada do geth 1 em que o consenso, RPC e banco de dados foram removidos. Para encontrar a primeira instrução de desacordo, uma busca binária interativa é conduzida entre aquele que iniciou a prova de falhas e aquele que publicou a raiz de saída. Quando a prova começa, ambas as partes publicam a raiz do estado de memória MIPS no meio da execução de o bloqueio no contrato do Desafio: se hash corresponder, significa que ambas as partes concordam com o primeira metade da execução publicando assim a raiz da metade da segunda metade, caso contrário a metade do primeiro semestre é publicado e assim por diante. Fazer isso alcança a primeira instrução de desacordo em um número logarítmico de etapas em comparação com a execução original. Se um dos dois parar interagindo, ao final do período de disputa o outro participante ganha automaticamente. Para processar a instrução, o interpretador MIPS precisa de acesso à sua memória: já que a raiz é disponíveis, as células de memória necessárias podem ser publicadas comprovando sua inclusão. Para acessar o estado do EVM, é feito uso do Preimage Oracle: dado o hash de um bloco ele retorna 1https://geth.ethereum.org/docs

o cabeçalho do bloco, a partir do qual se pode obter o hash do bloco anterior e voltar no cadeia ou obtenha o hash do estado e dos logs dos quais é possível obter a pré-imagem. O oracle é implementado pelo minigeth e substitui o banco de dados. Consultas são feitas a outros nós para obter as pré-imagens.

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)

Rollups de validade

Rollups de validade O objetivo de um Validity Rollup é provar criptograficamente a validade da transição de estado dada a sequência de transações com uma prova curta que pode ser verificada sub-linearmente comparada ao tempo dos cálculos originais. Esses tipos de certificados são chamados de provas de integridade computacional e são praticamente implementados com SNARKs (Succint Non-interactive ARgument of Knowledge), que utilizam aritmética circuitos como seu modelo computacional. Diferentes implementações do SNARK diferem no tempo de prova, tempo de verificação, a necessidade de uma configuração confiável e resistência quântica [16, 17]. STARKs (escalável ARgumento Transparente de Conhecimento) [18] são um tipo de SNARKs que não requer um confiável configurados e são resistentes a quantum, ao mesmo tempo que abrem mão de alguma eficiência na prova e verificação em comparação com outras soluções. 3.1. StarkNet StarkNet é um Smart Contract Validity Rollup desenvolvido pela StarkWare que usa o STARK sistema de prova para validar seu estado para Ethereum. Para facilitar a construção de provas de validade, um É utilizada uma máquina virtual diferente da EVM, cuja linguagem de alto nível é Cairo. 3.1.1. Depósitos Os usuários podem depositar transações por meio de um contrato em Ethereum chamando sendMessageToL2 função. A mensagem é registrada calculando seu hash e aumentando um contador. Sequenciadores ouça o evento LogMessageToL2 e codifique as informações em uma transação StarkNet que chama uma função de um contrato que possui o decorador l1_handler. No final da execução, quando a prova de transição de estado é produzida, o consumo da mensagem é anexado a ela e é excluído diminuindo seu contador. A inclusão de transações depositadas não é exigida pela especificação StarkNet, portanto, um gás mercado é necessário para incentivar os sequenciadores a publicá-los em L2. Na versão atual, porque o Sequenciador é centralizado e gerenciado pela StarkWare, o custo das transações depositadas é determinado apenas pelo custo de execução do depósito. Este custo é pago enviando ETH para enviarMessageToL2. Esses Éteres permanecem bloqueados em L1 e são transferidos para o Sequenciador em L1, quando a transação depositada está incluída em uma transição de estado. A quantidade de ETH enviada, se a transação depositada está incluída, é totalmente gasta, independentemente da quantidade de gás consumida em L2. StarkNet não possui um sistema que disponibilize atributos do bloco L1 automaticamente. Alternativamente, Fossil é um protocolo desenvolvido pela Oiler Network 2 que permite, dado um hash de um bloco, qualquer informação a ser obtida de Ethereum através da publicação de pré-imagens. 2https://www.oiler.network/3.1.2. Sequenciamento O estado atual de StarkNet pode ser derivado inteiramente de Ethereum. Qualquer diferença de estado entre transições é publicado em L1 como calldata. As diferenças são publicadas para cada contrato e são salvos como uint256[] com a seguinte codificação: • Número de campos relativos a implantações contratuais. • Para cada contrato publicado: – O endereço do contrato publicado. – O hash do contrato publicado. – O número de argumentos do construtor do contrato. – A lista de argumentos do construtor • Número de contrato cuja armazenagem foi modificada. • Para cada contrato que foi modificado: – O endereço do contrato modificado. – O número de atualizações de armazenamento. – Os pares de valores-chave dos endereços de armazenamento com os novos valores. As diferenças de estado são publicadas em ordem, portanto é suficiente lê-las sequencialmente para reconstruir o estado. 3.1.3. Retiradas Para enviar uma mensagem de L2 para L1, é usado o syscall send_message_to_L1. A mensagem é publicado em L1 aumentando seu contador hash junto com a prova e finalizado chamando o função consomeMessageFromL2 no StarkGate smart contract em L1, que diminui o contador. Qualquer pessoa pode finalizar qualquer saque. 3.1.4. Provas de validade A Máquina Virtual Cairo [19] foi projetada para facilitar a construção de provas STARK. A linguagem Cairo permite que o cálculo seja descrito com uma programação de alto nível linguagem, e não diretamente como um circuito. Isso é conseguido por um sistema de equações polinomiais 3 representando um único cálculo: o ciclo FDE de uma arquitetura von Neumann. O número de restrições é, portanto, fixo e independente do tipo de computação, permitindo apenas um Programa verificador para cada programa cujo cálculo precisa ser provado. StarkNet agrega múltiplas transações em uma única prova STARK usando um provador compartilhado chamado SHARP. As provas são enviadas para smart contract em Ethereum, que verifica sua validade e atualiza a raiz Merkle correspondente ao novo estado. O custo sublinear de verificar um a prova de validade permite que seu custo seja amortizado em múltiplas transações. 3chamada Representação Algébrica Intermediária (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.

Comparação

Comparação 4.1. Tempo de retirada O aspecto mais importante que distingue os Rollups Otimistas dos Rollups de Validade é o tempo que decorre entre a inicialização de um levantamento e a sua finalização. Em ambos os casos, as retiradas são inicializadas em L2 e finalizadas em L1. Em StarkNet, a finalização é possível como assim que a prova de validade da nova raiz de estado for aceita em Ethereum: teoricamente, é possível retirar fundos no primeiro bloco de L1 após a inicialização. Na prática, o frequência de envio de provas de validade em Ethereum é uma compensação entre a velocidade do bloco finalização e agregação de provas. Atualmente StarkNet fornece provas de validade para verificação a cada 10 horas 4, mas pretende-se que diminua à medida que a atividade de transação aumenta. Em Optimism Bedrock é possível finalizar um saque somente no final da disputa período (atualmente 7 dias), após o qual uma raiz é automaticamente considerada válida. O comprimento de este período é determinado principalmente pelo fato de que as provas de falha podem ser censuradas em Ethereum até seu fim. A probabilidade de sucesso deste tipo de ataque diminui exponencialmente à medida que o tempo aumenta: E[valor subtraído] = 𝑉𝑝𝑛 onde 𝑛 é o número de blocos em um intervalo, 𝑉 é a quantidade de fundos que pode ser subtraída publicando uma raiz inválida, e 𝑝é a probabilidade de realizar uma censura com sucesso ataque em um único bloco. Suponha que esta probabilidade seja de 99%, que o valor bloqueado no Rollup é um milhão de Ether, e que os blocos em um intervalo são 1800 (6 horas de blocos com 12 intervalo de segundos): o valor esperado é cerca de 0,01391 Ether. O sistema é tornado seguro por pedindo aos proponentes que apostem uma quantidade muito maior de Ether do que o valor esperado. Winzer et al. mostrou como realizar um ataque de censura usando um simples smart contract isso garante que certas áreas da memória no estado não mudem [20]. Modelando o ataque como um jogo de Markov, o artigo mostra que a censura é a estratégia dominante para uma bloquear o produtor se receberem mais compensação do que incluindo a transação que muda a memória. O valor de 𝑝 discutido acima pode ser visto como a percentagem do bloco racional produtores da rede, onde “racional” não leva em conta possivelmente penalizar externalidades, como menos confiança no blockchain que diminui seu valor de criptomoeda. O código a seguir apresenta um smart contract que pode ser usado para realizar um ataque de censura em Bedrock. O ataque explora os incentivos dos produtores de blocos, oferecendo-lhes suborno censurar as transações que modificariam partes específicas do estado. O principal do contrato função, ClaimBribe, permite que os produtores de blocos reivindiquem o suborno se conseguirem censurar a transação alvo, verificando se a raiz de saída inválida não foi tocada. função reivindicaçãoSuborno(bytes memória storageProof) externo { require(!claimed[block.number], "suborno já reivindicado"); Memória OutputProposal atual = storageOracle.getStorage(L2_ORACLE, block.number, SLOT, prova de armazenamento); require(invalidOutputRoot == current.outputRoot, "ataque falhou"); reivindicado[bloco.número] = verdadeiro; (bool enviado,) = block.coinbase.call{valor: bribeAmount}(""); 4https://etherscan.io/address/0xc662c410c0ecf747543f5ba90660f6abebd9c8c4require(enviado, "falha ao enviar ether"); } Listagem 1: Exemplo de contrato que incentiva um ataque de censura a Bedrock. A duração do período de litígio também deve ter em conta o facto de a prova da culpa ser uma prova interativa e, portanto, deve ser fornecido tempo suficiente para os participantes interagirem e que qualquer interação poderia ser censurada. Se o último movimento ocorrer num momento muito próximo do final do período de disputa, o custo da censura é significativamente menor. Embora a censura seja o estratégia dominante, a probabilidade de sucesso é menor porque os nós de censura são vulneráveis a Ataques de negação de serviço: um invasor pode gerar transações muito complexas que terminam com o publicação de uma prova de culpa sem nenhum custo, uma vez que nenhuma taxa seria paga. Em casos extremos, um longo período de litígio permite a coordenação no caso de uma decisão bem-sucedida. ataque de censura para organizar um fork e excluir os produtores de blocos atacantes. Outro possível ataque consiste em publicar mais propostas de raiz estatal do que os disputantes podem verificar, que pode ser evitado usando um limite de frequência. 4.1.1. Retiradas rápidas e otimistas Como a validade de um Optimistic Rollup pode ser verificada a qualquer momento por qualquer Full Node, um confiável oracle pode ser usado para saber em L1 se a retirada pode ser finalizada com segurança. Isto mecanismo foi proposto pela primeira vez pelo Maker [21]: um oracle verifica a retirada, publica o resultado em L1 em que um empréstimo remunerado é atribuído ao usuário, que é automaticamente fechado ao final de 7 dias, ou seja, quando o saque pode realmente ser finalizado. Esta solução introduz uma suposição de confiança, mas no caso do Maker ela é minimizada, pois o operador oracle é gerido pela mesma organização que assume o risco ao conceder o empréstimo. 4.2. Custos de transação O custo das transações L2 é determinado principalmente pela interação com a L1. Em ambas as soluções o custo computacional das transações é muito barato, pois é executado inteiramente fora da cadeia. Optimism publica calldata de transações L2 como calldata e raramente (ou nunca) executa falha provas, portanto calldata é o recurso mais caro. Em 12 de janeiro de 2022, uma rede Bedrock foi lançado na testnet Goerli de Ethereum. Uma taxa de compressão de gás pode ser calculada rastreando a quantidade de gás usada em Bedrock em um determinado período e comparando-a com o quantidade de gás gasta em L1 para os blocos correspondentes. Usando este método, uma compressão de gás taxa de ∼20: 1 é encontrada, mas este número pode diferir com a atividade real na rede principal. StarkNet publica em Ethereum todas as alterações no estado L2 como dados de chamada, portanto, o armazenamento é o recurso mais caro. Como a rede não utiliza EVM, o custo da transação a compressão não pode ser estimada trivialmente. Ao assumir o custo de execução e calldata para ser insignificante, é possível calcular a taxa de compactação de gravações de armazenamento em comparação com L1. Supondo que nenhum contrato seja implantado e 10 células não acessadas anteriormente em StarkNet sejam modificado, uma taxa de compactação de custo de gravação de armazenamento de ∼24: 1 é encontrada. Se uma célula for sobrescrita 𝑛vezes entre publicações de dados, o custo de cada gravação será 1/𝑛comparado ao custo de uma única escrita, já que apenas a última é publicada. O custo pode ser ainda mais minimizado porcompactando valores usados com frequência. O custo da verificação da prova de validade é dividido entre as transações às quais se refere: por exemplo, o bloco StarkNet 4779 contém 200 transações e seu o comprovante de validade consome 267.830 unidades de gás, ou 1.339,15 gás para cada transação. 4.2.1. Otimizando calldata: contrato de cache Apresentado abaixo está um smart contract que implementa um cache de endereço para uso frequente endereços aproveitando o fato de que o armazenamento e a execução são muito mais baratos recursos, juntamente com um contrato de Amigos que demonstra seu uso. Este último acompanha o “amigos” de um endereço que pode ser registrado chamando a função addFriend. Se um endereço já foi usado pelo menos uma vez, ele pode ser adicionado chamando addFriendWithCache função: os índices de cache são inteiros de 4 bytes enquanto os endereços são representados por 20 bytes, portanto, há uma economia de 5:1 no argumento da função. A mesma lógica pode ser usada para outros dados tipos como inteiros ou, mais geralmente, bytes. contrato AddressCache { mapeamento (endereço => uint32) public address2key; endereço[] endereço-chave2 público; função cacheWrite(address _address) retornos internos (uint32) { require(key2address.length <type(uint32).max, "AddressCache: cache está cheio"); require(address2key[_address] == 0, "AddressCache: endereço já armazenado em cache"); // as chaves devem começar em 1 porque 0 significa "não encontrado" chave uint32 = uint32(key2address.length + 1); endereço2key[_endereço] = chave; key2address.push(_address); chave de retorno; } função cacheRead (uint32 _key) visualização pública retorna (endereço) { require(_key <= key2address.length && _key > 0, "AddressCache: chave não encontrada"); retornar key2address[_key - 1]; } } Listagem 2: Contrato de cache de endereço. contrato Amigos é AddressCache { mapeamento(endereço => endereço[]) amigos públicos; function addAmigo(endereço_amigo) public { amigos[msg.remetente].push(_amigo); cacheWrite(_amigo); } função addFriendWithCache(uint32 _friendKey) public { amigos[msg.sender].push(cacheRead(_friendKey)); } função getFriends() visualização pública retorna (endereço[] memória) { retornar amigos[msg.sender];} } Listagem 3: Exemplo de contrato que herda o cache de endereços. O contrato suporta em cache cerca de 4 bilhões (232) endereços, e adicionar um byte dá cerca de 1 trilhão (240). 4.2.2. Otimizando o armazenamento: filtros Bloom Em StarkNet existem diversas técnicas para minimizar o uso de armazenamento. Se não for necessário garantir a disponibilidade dos dados originais, então é suficiente salvar on-chain seu hash: este é o mecanismo usado para salvar dados para um ERC-721 (NFT) [22], ou seja, um link IPFS que resolve o hash dos dados, se disponíveis. Para dados armazenados diversas vezes, é possível usar uma pesquisa tabela semelhante ao sistema de cache introduzido para Optimism, exigindo que todos os valores sejam salvos em pelo menos uma vez. Para algumas aplicações, salvar todos os valores pode ser evitado usando um filtro Bloom [23, 24, 25], ou seja, uma estrutura de dados probabilística que permite saber com certeza se um elemento não pertence a um conjunto, mas admite uma probabilidade pequena, mas não desprezível, de falso positivos. Um filtro Bloom é inicializado como uma matriz de 𝑚bits em zero. Para adicionar um elemento, 𝑘hash funções com uma distribuição aleatória uniforme são usados, cada um mapeando para um bit da matriz que está definida para 1. Para verificar se um elemento pertence ao conjunto, executamos as funções 𝑘hash e verificamos que os 𝑘bits estão definidos como 1. Num filtro de Bloom simples, não há como distinguir se um elemento realmente pertence ao conjunto ou é um falso positivo, uma probabilidade que aumenta à medida que o número de entradas aumenta. Depois de inserir 𝑛elementos: P[falso positivo] = (︃ 1 - [︂ 1 −1 𝑚 ]︂𝑘𝑛)︃𝑘 ≈ (︁ 1 −𝑒−𝑘𝑛/𝑚)︁𝑘 assumindo a independência da probabilidade de cada conjunto de bits. Se 𝑛elementos (de tamanho arbitrário!) são espera-se que seja incluído e a probabilidade de um falso positivo tolerado é 𝑝, o tamanho da matriz pode ser calculado como: 𝑚= −𝑛ln 𝑝 (Em 2)2 Embora o número ideal de funções hash seja: 𝑘= 𝑚 𝑛ln 2 Se assumirmos a inserção de 1.000 elementos com tolerância de 1%, o tamanho do array será de 9.585 bits com 𝑘= 6, enquanto para uma tolerância de 0,1% torna-se 14377 bits com 𝑘= 9. Se um milhão de elementos espera-se que sejam inseridos, o tamanho da matriz torna-se cerca de 1170 kB para 1% e 1775 kB para 0,1%, com os mesmos valores de 𝑘, pois depende apenas de 𝑝[26]. Num jogo em que os jogadores não devem ser atribuídos a um adversário que já tenham desafiado, em vez de salvar no armazenamento para cada jogador a lista de oponentes anteriores, pode-se usar um Bloom filtro. O risco de não desafiar alguns jogadores é muitas vezes aceitável, e o filtro pode ser reiniciado periodicamente.4.3. Ethereum compatibilidade A principal vantagem de ser compatível com EVM e Ethereum é o reaproveitamento de todos os disponíveis ferramentas. Ethereum smart contracts podem ser publicados em Optimism sem qualquer modificação nem novas auditorias. As carteiras permanecem compatíveis, ferramentas de desenvolvimento e análise estática, análise geral ferramentas, ferramentas de indexação e oracles. Ethereum e Solidity têm uma longa história de estudos bem estudados vulnerabilidades, como ataques de reentrada, overflows e underflows, empréstimos instantâneos e oracle manipulações. Por causa disso, Optimism foi capaz de capturar uma grande quantidade de valor em um curto espaço de tempo tempo. Optar por adotar uma máquina virtual diferente implica reconstruir todo um ecossistema, com a vantagem de uma maior liberdade de implementação. StarkNet implementa conta nativamente abstração, que é um mecanismo pelo qual cada conta é um smart contract que pode implementar lógica arbitrária, desde que esteja em conformidade com uma interface (daí o termo abstração): isso permite o uso de diferentes esquemas de assinatura digital, a capacidade de alterar a chave privada usando o mesmo endereço ou use um multisig. A comunidade Ethereum propôs a introdução deste mecanismo com EIP-2938 em 2020, mas a proposta permaneceu obsoleta por mais de um ano como outras atualizações receberam mais prioridade [27]. Outro benefício importante obtido com a compatibilidade é a reutilização de clientes existentes: Optimism usa uma versão de geth para seu próprio nó com apenas 800 linhas de diferença, que foi desenvolvido, testado e mantido desde 2014. Ter um cliente robusto é crucial, pois define o que é aceito como válido ou não na rede. Um bug na implementação da prova de falhas sistema pode fazer com que uma prova incorreta seja aceita como correta ou uma prova correta para uma prova inválida. bloco seja aceito como incorreto, comprometendo o sistema. A probabilidade deste tipo de o ataque pode ser limitado com uma diversidade maior de clientes: Optimism pode reutilizar além de obter o outros clientes Ethereum já mantidos, e o desenvolvimento de outro cliente baseado em Erigon está já em andamento. Em 2016 um problema no gerenciamento de memória do geth foi explorado por um ataque DoS e a primeira linha de defesa foi recomendar o uso de Paridade, o segundo mais cliente usado na época 5. StarkNet enfrenta o mesmo problema com provas de validade, mas os clientes tem que ser escrito do zero e o sistema de provas é muito mais complexo e, conseqüentemente, também é muito mais complexo garantir a correção.

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.

Conclusão

Conclusão Rollups são a solução mais promissora disponível atualmente para resolver o problema de escalabilidade em blockchains descentralizados, abrindo caminho para a era dos blockchains modulares em oposição a blockchains monolíticos. A escolha de desenvolver um Rollup Otimista ou um Rollup de Validade é mostrada principalmente como uma compensação entre complexidade e agilidade. StarkNet tem inúmeras vantagens, como rapidez retiradas, incapacidade estrutural de ter transições de estado inválidas, menor custo de transação no despesa de um período de desenvolvimento mais longo e incompatibilidade com EVM, enquanto Optimism tem alavancou a economia de rede para ganhar rapidamente uma grande fatia do mercado. Optimism Bedrock, entretanto, possui um design modular que permite que ele se torne um Validity 5https://blog.ethereum.org/2016/09/22/ethereum-network-currently-undergoing-dos-attack

Rollup no futuro: Cannon atualmente usa minigeth compilado em MIPS para sua prova de falhas sistema, mas a mesma arquitetura pode ser usada para obter um circuito e produzir provas de validade. Compilar uma máquina complexa como EVM para uma microarquitetura resulta em uma solução mais simples circuito que não precisa ser modificado e verificado novamente em caso de atualizações. RISC Zero é um microarquitetura verificável com provas STARK já em desenvolvimento com base em RISC-V que pode ser usado para esta finalidade como uma alternativa a MIPS [28]. Um aspecto que não deve ser subestimado é a complexidade em compreender como o a tecnologia funciona. Um ponto forte dos blockchains tradicionais é ser capaz de verificar o estado de o blockchain sem confiar em nenhuma entidade terceirizada. No entanto, no caso de StarkNet, é necessário confiar na implementação quando não é possível verificar os vários componentes baseado em criptografia e matemática avançada. Isto pode inicialmente criar atrito para o adoção da tecnologia, mas à medida que as ferramentas e o uso de provas de integridade avançam ainda mais fora do campo blockchain este problema será resolvido.