Техническая документация Optimism

Analysis and Comparison between Optimism and StarkNet

作者 Optimism Collective · 2021

Optimism 没有传统意义上的白皮书。作为 Ethereum Layer 2 乐观 Rollup，其设计和规范通过技术文档、OP Stack 规范和研究文章记录，而非单一的正式学术论文。

🇺🇸 English (原文)

🇷🇺 Русский (译文)

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

Аннотация

В статье рассматривается проблема масштабируемости децентрализованных blockchain путем анализа компромисса между пропускной способностью транзакций и требованиями к оборудованию для запуска узла. Свертывания, то есть технологии проверки блоков, выполняемых вне сети, представлены в форме доказательств неисправности или достоверности. Мы сравниваем оптимистичные накопительные пакеты и накопительные пакеты по сроку действия с точки зрения времени вывода средств, транзакционных издержек, методов оптимизации и совместимости с экосистемой Ethereum. Наш анализ показывает, что Optimism Bedrock в настоящее время имеет степень сжатия газа примерно 20:1, а StarkNet обеспечивает степень сжатия стоимости записи в хранилище примерно 24:1. Мы также обсуждаем методы дальнейшей оптимизации этих скоростей, такие как использование контрактов кэша и фильтров Блума. В конечном счете, наши выводы подчеркивают компромисс между сложностью и гибкостью при выборе между оптимистичными и валидными накопительными пакетами. Ключевые слова Блокчейн, Масштабируемость, Объединение 1. Введение Технология Блокчейн привлекла значительное внимание благодаря своему потенциалу совершить революцию в различных отраслях. Однако масштабируемость остается серьезной проблемой, поскольку большинство blockchain сталкиваются с компромиссом между масштабируемостью, децентрализацией и безопасностью, обычно называемым «трилеммой масштабируемости» [1, 2]. Чтобы увеличить пропускную способность blockchain, тривиальным решением является увеличение размера его блока. В контексте Ethereum это означает увеличение максимального количества газа, которое может содержать блок. Поскольку каждый полный узел должен проверять каждую транзакцию каждого блока, по мере увеличения пропускной способности требования к оборудованию также возрастают, что приводит к большей централизации сети. Некоторые blockchain, такие как Bitcoin и Ethereum, оптимизируют свой дизайн, чтобы максимизировать архитектурную децентрализацию, в то время как другие, такие как Binance Smart Chain и Solana, спроектированы так, чтобы быть максимально быстрыми и дешевыми. Децентрализованные сети искусственно ограничивают пропускную способность blockchain, чтобы снизить требования к оборудованию для участия в сети. На протяжении многих лет предпринимались попытки найти решение Трилеммы, например, государственные каналы [3] и Plasma [4, 5]. Эти решения характеризуются перемещением некоторой активности за пределы цепочки, связыванием активности внутри цепочки с активностью вне цепочки с помощью smart contracts и проверкой DLT 2023: 5-й семинар по технологиям распределенного реестра, 25–26 мая 2023 г., Болонья, Италия $ [email protected] (Л. Донно) https://lucadonnoh.github.io/ (Л. Донно) 0000-0001-9221-3529 (Л. Донно) © 2023 Авторские права на эту статью принадлежат ее авторам. Использование разрешено в соответствии с лицензией Creative Commons License Attribution 4.0 International (CC BY 4.0). Материалы семинара CEUR http://ceur-ws.org ISSN 1613-0073 Материалы семинара CEUR (CEUR-WS.org) в сети, что происходит вне сети. Однако как Plasma, так и государственные каналы ограничены в поддержке общих smart contract. Накопительные пакеты — это blockchain (называемые Layer 2 или L2), которые публикуют свои блоки на другом blockchain (Layer 1 или L1) и, следовательно, наследуют его свойства консенсуса, доступности данных и безопасности. Они, в отличие от других решений, поддерживают произвольные вычисления. Rollups состоит из трех основных компонентов: • Секвенсоры: узлы, которые получают транзакции Rollup от пользователей и объединяют их в блок, который отправляется на Layer 1. Блок состоит как минимум из корня состояния (например, корня Меркла) и данных, необходимых для восстановления и проверки состояния. Layer 1 определяет...

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.

Введение

Введение Технология блокчейн привлекла значительное внимание благодаря своему потенциалу совершить революцию. различные отрасли промышленности. Однако масштабируемость остается серьезной проблемой, поскольку большинство blockchain сталкиваются с компромисс между масштабируемостью, децентрализацией и безопасностью, обычно называемый Трилемма масштабируемости [1, 2]. Чтобы увеличить пропускную способность blockchain, есть тривиальное решение: чтобы увеличить размер блока. В контексте Ethereum это означает увеличение максимального количество газа, которое может содержать блок. Поскольку каждый полный узел должен проверять каждую транзакцию каждого блок, поскольку пропускная способность увеличивается, требования к оборудованию также увеличиваются, что приводит к большему централизация сети. Некоторые blockchain, такие как Bitcoin и Ethereum, оптимизируют свои дизайн, чтобы максимизировать свою архитектурную децентрализацию, в то время как другие, такие как Binance Smart Chain и Solana созданы для того, чтобы быть максимально быстрыми и дешевыми. Децентрализованные сети искусственно ограничить пропускную способность blockchain, чтобы снизить требования к оборудованию до участвовать в сети. На протяжении многих лет предпринимались попытки найти решение трилеммы, например, каналы [3] и Плазма [4, 5]. Эти решения имеют свойство перемещать некоторую деятельность оффчейн, связывание активности внутри цепочки с активностью вне цепочки с использованием smart contracts и проверка DLT 2023: 5-й семинар по технологиям распределенного реестра, 25–26 мая 2023 г., Болонья, Италия $ [email protected] (Л. Донно) https://lucadonnoh.github.io/ (Л. Донно) 0000-0001-9221-3529 (Л. Донно) © 2023 Авторские права на данную статью принадлежат авторам. Использование разрешено в соответствии с лицензией Creative Commons License Attribution 4.0 International (CC BY 4.0). ЦЕВР Мастерская Слушания http://ceur-ws.org ISSN 1613-0073 Материалы семинара CEUR (CEUR-WS.org)в сети, что происходит вне сети. Однако как Plasma, так и государственные каналы ограничены в их поддержка генералов smart contracts. Накопительные пакеты — это blockchain (называемые Layer 2 или L2), которые публикуют свои блоки на другом blockchain. (Layer 1 или L1) и, следовательно, наследуют его свойства консенсуса, доступности данных и безопасности. Они, в отличие от других решений, поддерживают произвольные вычисления. Накопительные пакеты состоят из трех основных компонентов: • Секвенсоры: узлы, которые получают транзакции Rollup от пользователей и объединяют их в блок, который отправляется на Layer 1. Блок состоит как минимум из корня состояния (например, Меркла root) и данные, необходимые для восстановления и проверки состояния. Layer 1 определяет канонический blockchain L2 путем установления порядка опубликованных данных. • Полные узлы объединения: узлы, которые получают, обрабатывают и проверяют блоки объединения из слоя. 1, проверив правильность корня. Если блок содержит недействительные транзакции, то это так. отброшено, что не позволяет секвенаторам создавать действительные блоки, содержащие недопустимые транзакции. • Легкие узлы объединения: узлы, которые получают блоки объединения из Layer 1, но не выполняют вычисления. само новое государство. Они проверяют, что новый корень состояния действителен, используя методы такие как доказательства вины или действительности. Накопительные пакеты обеспечивают масштабируемость за счет уменьшения амортизированной стоимости транзакций по мере увеличения количества пользователей увеличивается. Это связано с тем, что стоимость обеспечения достоверности blockchain растет сублинейно. в отношении стоимости проверки транзакций в индивидуальном порядке. Свернутые пакеты различаются в зависимости от механизм, с помощью которого они обеспечивают достоверность выполнения транзакций на легких узлах: в Оптимистические накопительные пакеты обеспечиваются экономической моделью и доказательствами ошибок, пока они действительны. Rollups криптографически обеспечивается с использованием доказательств достоверности. Легкие узлы могут быть реализованы как smart contract на Layer 1. Они принимают корень новое состояние и проверка действительности или доказательств ошибок: поэтому эти накопительные пакеты называются смарт-контрактом. Ролл-апы. Если легкие узлы независимы, они называются суверенными накопительными пакетами [6]. Преимущество использование накопительного пакета смарт-контрактов позволяет построить между ними мост с минимальным доверием. blockchains: поскольку достоверность состояния L2 доказана для L1, система транзакций из Можно реализовать L2–L1, что позволит осуществлять снятие средств. Недостатком является то, что стоимость транзакций зависит от стоимости проверки состояния на L1: если базовый уровень насыщен других видов деятельности, стоимость транзакций в Rollup также увеличивается. Уровни данных и консенсуса — это те, которые определяют безопасность системы как они определяют порядок транзакций, предотвращают атаки и предоставляют данные для подтверждения состояния действительность. Бумажный вклад В этой статье мы изучаем оптимистические и валидные сводные данные, два инновационных метода. решения трилеммы масштабируемости с упором на известные реализации, такие как Optimism Bedrock и StarkNet. Наш вклад включает всестороннее сравнение этих решения, анализ времени вывода средств и обсуждение возможной атаки на Optimism. Коренная порода. Кроме того, мы рассчитываем степень сжатия газа, обеспечиваем оптимизацию для конкретных приложений и представляем преимущества и недостатки отказа от Ethereum. Виртуальная машина (EVM).

Структура бумаги Статья организована следующим образом. В разделе 2 приведены оптимистичные сводные данные. введено путем анализа Optimism коренных пород. В разделе 3 сводные данные о сроках действия представлены анализируем StarkNet. В разделе 4 мы сравниваем два решения. Наконец, в разделе 5 мы рисуем некоторые выводы.

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.

Оптимистичные сводки

Оптимистичные сводки Идея оптимистичного принятия вывода блоков без проверки их выполнения уже присутствует в официальном документе Bitcoin [7], где обсуждаются легкие узлы. Эти узлы следуют только цепочку заголовков, проверяя правило консенсуса, что делает их уязвимыми для приема блоков содержащие недействительные транзакции в случае атаки 51%. Накамото предлагает решить эту проблему проблема с использованием системы «оповещения», предупреждающей легкие узлы о том, что блок содержит недопустимые транзакции. Этот механизм впервые был реализован Аль-Бассамом, Соннино и Бутерином [8], в котором возникла ошибка используется система подтверждения, основанная на кодах исправления ошибок [9]. Для того, чтобы обеспечить возможность создания Для проверки ошибок необходимо, чтобы данные всех блоков, включая недействительные, были доступны сеть: это проблема доступности данных, которая решается с использованием вероятностных данных механизм выборки. Первый дизайн Optimistic Rollup был представлен Джоном Адлером и Микера Квинтайн-Коллинз в 2019 году [10], в котором блоки опубликованы на другом blockchain. это определяет их консенсус относительно порядка. 2.1. Optimism Коренная порода Bedrock [11] — это последняя версия Optimism, накопительного пакета смарт-контрактов. Предыдущая версия, Оптимистической виртуальной машине (OVM) требовался специальный компилятор для компиляции Solidity в свою программу. собственный байт-код: напротив, Bedrock полностью эквивалентен EVM в том смысле, что механизм выполнения соответствует спецификации Ethereum Yellow Paper [12]. 2.1.1. Депозиты Пользователи могут вносить транзакции через контракт на Ethereum, портале Optimism, вызывая функцию депозитаTransaction. Когда транзакция выполняется, Выдается событие TransactionDeposited, которое прослушивает каждый узел в накопительном пакете для обработки. депозиты. Депонированная транзакция — это транзакция L2, производная от L1. Если вызывающий абонент функция является контрактом, адрес преобразуется путем добавления к нему постоянного значения: это предотвращает атаки, при которых контракт на L1 имеет тот же адрес, что и контракт на L2, но другой код. Включение в L2 депонированной транзакции обеспечивается спецификацией в рамках секвенирования. окно. Депонированные транзакции — это новый тип транзакции [13], совместимый с EIP-2718, с префиксом 0x7E, где поля в кодировке rlp: • bytes32 sourceHash: hash, который однозначно идентифицирует источник транзакции. • Адрес от: адрес отправителя. • адрес: адрес получателя или нулевой адрес, если депонированная транзакция является создание договора.• uint256 mint: значение, которое будет создано на уровне L2. • Значение uint256: значение, которое будет отправлено получателю. • байтовые данные: входные данные. • байты gasLimit: лимит газа транзакции. SourceHash вычисляется как keccak256 hash блока L1 hash и журнала L1. индекс, однозначно идентифицирующий событие в блоке. Поскольку депонированные транзакции инициируются на L1, но выполняются на L2, системе требуется механизм оплаты на L1 газа, потраченного на L2. Одним из решений является отправка ETH через Портал. но это подразумевает, что каждый вызывающий абонент (даже косвенный вызывающий абонент) должен быть помечен как подлежащий оплате, и это невозможно для многих существующих проектов. Альтернативой является сжигание соответствующего газа на L1. Газ 𝑔, выделяемый для депозитной транзакции, называется гарантированным газом. Цена на газ L2 на L1 не синхронизируется автоматически, но оценивается с использованием механизма, аналогичного EIP-1559. [14]. Максимальное гарантированное количество газа на блок Ethereum составляет 8 миллионов, с целью из 2 миллионов. Количество 𝑐ETH, необходимое для оплаты газа на L2, равно 𝑐= 𝑔𝑏L2, где 𝑏L2 — это базовая плата за L2. Контракт на L1 сжигает количество газа, равное 𝑐/𝑏L2. Газ, потраченный на звонок депозитная транзакция возмещается на L2: если эта сумма превышает гарантированный газ, газ не горит. Первая транзакция блока rollup — это транзакция с депонированием атрибутов L1, используемая для регистрации на L2 предварительно разверните атрибуты блоков Ethereum. Атрибуты, которые дает предварительное развертывание доступом являются номер блока, временная метка, базовая плата, блок hash и последовательность номер, который является номером блока L2 относительно связанного блока L1 (также называемого эпохой); это число сбрасывается при начале новой эпохи. 2.1.2. Секвенирование Узлы объединения полностью наследуют цепочку Optimism от Ethereum. Эта цепочка расширена каждый раз новые транзакции публикуются на L1, и его блоки каждый раз реорганизуются Блоки Ethereum реорганизованы. Накопительный пакет blockchain разделен на эпохи. Для каждого 𝑛 номер блока Ethereum, существует соответствующая 𝑛эпоха. Каждая эпоха содержит по крайней мере один блок, и каждый блок в эпоху содержит транзакцию депонирования атрибутов L1. Первый блок в эпоху содержит все транзакции, проведенные через Портал. Блоки Layer 2 также могут содержали секвенированные транзакции, т.е. транзакции, отправленные непосредственно в секвенсор. Sequencer принимает транзакции от пользователей и строит блоки. Для каждого блока строится пакет будет опубликован Ethereum. Несколько пакетов могут быть опубликованы в сжатом виде, взяв название канала. Канал можно разделить на несколько кадров, если он слишком велик для одна транзакция. Канал определяется как сжатие с помощью ZLIB [15] файлов, закодированных в rlp. партии. Полями пакета являются номер эпохи, эпоха hash, родительская hash, временная метка и список транзакций. Окно секвенирования, идентифицируемое эпохой, содержит фиксированное количество 𝑤 последовательных L1. блоки, которые на этапе деривации используются в качестве входных данных для создания переменного числа блоков L2. Для эпоха 𝑛, окно последовательности 𝑛 включает блоки [𝑛, 𝑛+𝑤). Это означает, что упорядочение Количество транзакций и блоков L2 в окне последовательности не фиксируется до тех пор, пока окно не завершится. Транзакция rollup называется безопасной, если содержащий ее пакет был подтвержден на L1. Рамкисчитываются из блоков L1 для восстановления пакетов. Текущая реализация не позволяет распаковка канала начнется до тех пор, пока не будут получены все соответствующие кадры. Недействительный пакеты игнорируются. Отдельные блочные транзакции получаются из пакетов, которые используется механизмом выполнения для применения переходов между состояниями и получения состояния Rollup. 2.1.3. Вывод средств Для обработки вывода средств реализована система обмена сообщениями L2-L1. Ethereum необходимо знать состояние L2, чтобы принять вывод средств, и это делается путем публикации на выходе L2 Oracle smart contract на L1 - корень состояния каждого блока L2. Эти корни оптимистично принимаются как действительные (или завершенные), если в течение период спора. Только адреса, обозначенные как Предлагающие, могут публиковать выходные корни. Срок действия выходных корней стимулируется тем, что предлагающие вносят ставку, которая сокращается, если они показано, что он предложил неверный корень. Транзакции инициируются вызовом функции инициироватьВывод средств при предварительном развертывании на уровне L2, а затем завершать на уровне L1, вызывая функцию FinalizeWithdrawalTransaction на ранее упомянутом портале Optimism. Выходной корень, соответствующий блоку L2, получается из выходного оракула L2; это проверил, что он завершен, т. е. период диспута прошел; проверено, что Выход Root Proof соответствует Oracle Proof; подтверждено, что hash вывода включен в нем с использованием Доказательства вывода средств; что вывод еще не завершен; а затем выполняется вызов на целевой адрес с указанным лимитом газа, количеством эфира и данными. 2.1.4. Cannon: надежная система Если объединенный полный узел, локально выполняя пакеты и депонированные транзакции, обнаруживает, что состояние Layer 2 не соответствует корню состояния, опубликованному в цепочке Предлагающим, оно может быть выполнено доказательство неисправности на L1, чтобы доказать, что результат перехода к кадру неверен. Из-за накладные расходы, обработка всего блока Rollup на L1 слишком дорога. Решение реализовано от Bedrock — выполнить по цепочке только первую инструкцию несогласия минигетов, компиляция его в архитектуру MIPS, которая выполняется на интерпретаторе цепочки и публикуется на Л1. minigeth — это упрощенная версия geth 1, в которой консенсус, RPC и база данных были удалены. Для нахождения первой инструкции несогласия проводится интерактивный бинарный поиск между тот, кто инициировал проверку неисправности, и тот, кто опубликовал корень вывода. Когда доказательство начинается, обе стороны публикуют корень состояния памяти MIPS в середине выполнения блок в контракте Challenge: если hash совпадает, это означает, что обе стороны согласны на первая половина выполнения, таким образом публикуя корень половины второй половины, в противном случае половина первой половины публикуется и так далее. Таким образом достигается первая инструкция несогласия. за логарифмическое количество шагов по сравнению с исходным выполнением. Если один из двух останавливается взаимодействуя, по окончании периода спора автоматически побеждает другой участник. Для обработки инструкции интерпретатору MIPS необходим доступ к ее памяти: поскольку корень доступны, необходимые ячейки памяти можно опубликовать, доказав их включение. Чтобы получить доступ состояние EVM, используется Oracle Preimage: учитывая hash блока, который он возвращает 1https://geth.ethereum.org/docs

заголовок блока, из которого можно получить hash предыдущего блока и вернуться в цепочку или получить hash состояния и журналы, из которых можно получить прообраз. oracle реализуется minigeth и заменяет базу данных. Запросы выполняются к другим узлам для получить прообразы.

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)

Сводные данные о сроке действия

Сводные данные о сроках действия Целью валидного накопительного пакета является криптографическое доказательство достоверности перехода состояний. учитывая последовательность транзакций с коротким доказательством, которое можно проверить сублинейным сравнением ко времени первоначальных вычислений. Сертификаты такого типа называются доказательствами вычислительной целостности и практически реализуются с помощью SNARK (краткий неинтерактивный аргумент знаний), в которых используются арифметические действия. схемы в качестве их вычислительной модели. Различные реализации SNARK отличаются временем проверки, время проверки, необходимость доверенной установки и квантовое сопротивление [16, 17]. STARK (Масштабируемые Прозрачный аргумент знаний) [18] — это тип SNARK, не требующий доверенного настройки и являются квантово-устойчивыми, но при этом теряют некоторую эффективность при доказательстве и проверке. по сравнению с другими решениями. 3.1. StarkNet StarkNet — это накопительный пакет действительности смарт-контракта, разработанный StarkWare, который использует STARK система доказательства для подтверждения своего состояния до Ethereum. Чтобы облегчить построение доказательств достоверности, используется виртуальная машина, отличная от EVM, языком высокого уровня которой является Cairo. 3.1.1. Депозиты Пользователи могут вносить транзакции через контракт на Ethereum, вызвав sendMessageToL2. функция. Сообщение записывается путем вычисления его hash и увеличения счетчика. Секвенсоры прослушивайте событие LogMessageToL2 и кодируйте информацию в транзакции StarkNet который вызывает функцию контракта, имеющую декоратор l1_handler. В конце исполнения, когда создается доказательство перехода состояния, к нему прилагается потребление сообщения и он удаляется путем уменьшения его счетчика. Спецификация StarkNet не требует включения депонированных транзакций, поэтому газ рынок необходим, чтобы стимулировать секвенаторов публиковать их на L2. В текущей версии, поскольку Секвенсер централизован и управляется StarkWare, стоимость депонируемых транзакций определяется только стоимостью исполнения депозита. Эта стоимость оплачивается путем отправки ETH на sendMessageToL2. Эти эфиры остаются заблокированными на L1 и передаются в секвенсор L1, когда депонированная транзакция включена в переход состояния. Сумма отправленных ETH, если внесенная транзакция включена, расходуется полностью, независимо от количества потребленного газа на Л2. StarkNet не имеет системы, которая автоматически делает атрибуты блока L1 доступными. Альтернативно, Fossil — это протокол, разработанный Oiler Network 2, который позволяет при наличии hash блок, любая информация, которую можно получить от Ethereum путем публикации прообразов. 2https://www.oiler.network/3.1.2. Секвенирование Текущее состояние StarkNet может быть полностью получено из Ethereum. Любая государственная разница между переходами публикуется на L1 как данные вызова. Различия публикуются для каждого контракта и сохраняются как uint256[] со следующей кодировкой: • Количество полей, касающихся развертывания контрактов. • Для каждого опубликованного контракта: – Адрес опубликованного контракта. – hash опубликованного контракта. – Количество аргументов конструктора контракта. – Список аргументов конструктора • Номер контракта, хранилище которого было изменено. • Для каждого измененного контракта: – Адрес измененного контракта. – Количество обновлений хранилища. – Пары ключ-значение адресов хранения с новыми значениями. Государственные различия публикуются по порядку, поэтому достаточно прочитать их последовательно, чтобы реконструировать государство. 3.1.3. Вывод средств Чтобы отправить сообщение с L2 на L1, используется системный вызов send_message_to_L1. Сообщение опубликовано в L1 путем увеличения счетчика hash вместе с доказательством и завершено путем вызова метода функция ConsumerMessageFromL2 на StarkGate smart contract на L1, которая уменьшает счетчик. Любой может завершить вывод средств. 3.1.4. Доказательства действительности Виртуальная машина Cairo [19] предназначена для облегчения построения доказательств STARK. Язык Cairo позволяет описывать вычисления с помощью высокоуровневого программирования. языке, а не непосредственно как цепь. Это осуществляется с помощью системы полиномиальных уравнений 3 представляет одно вычисление: цикл FDE архитектуры фон Неймана. Число Таким образом, количество ограничений фиксировано и независимо от типа вычислений, что позволяет использовать только одно Программа-верификатор для каждой программы, вычисления которой необходимо доказать. StarkNet объединяет несколько транзакций в одно доказательство STARK с использованием общего доказательства. по имени ШАРП. Доказательства отправляются на smart contract Ethereum, который подтверждает их достоверность. и обновляет корень Меркла, соответствующий новому состоянию. Сублинейная стоимость проверки Доказательство действительности позволяет амортизировать его стоимость в рамках нескольких транзакций.
называется алгебраическим промежуточным представлением (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.

Сравнение

Сравнение 4.1. Время вывода Наиболее важным аспектом, который отличает оптимистические сводные данные от сводных данных по достоверности, является время, которое проходит между инициализацией вывода средств и его завершением. В обоих случаях Вывод средств инициализируется на L2 и завершается на L1. На StarkNet финализация возможна как как только подтверждение достоверности нового корня состояния будет принято Ethereum: теоретически это возможен вывод средств в первом блоке L1 после инициализации. На практике частота отправки доказательств достоверности на Ethereum — это компромисс между скоростью блока доработка и агрегирование доказательств. В настоящее время StarkNet предоставляет доказательства действительности для проверки. каждые 10 часов 4, но предполагается, что оно будет уменьшаться по мере увеличения активности транзакций. На Optimism Bedrock завершить вывод можно только по окончании диспута. период (на данный момент 7 дней), по истечении которого рут автоматически считается действительным. Длина этот период главным образом определяется тем фактом, что доказательства ошибок могут подвергаться цензуре Ethereum до тех пор, пока его конец. Вероятность успеха этого типа атаки уменьшается экспоненциально с увеличением времени: E[вычтенное значение] = 𝑉𝑝𝑛 где 𝑛 — количество блоков в интервале, 𝑉 — сумма средств, которую можно вычесть опубликовав недействительный корень, и 𝑝это вероятность успешного выполнения цензуры атаковать одним блоком. Предположим, что эта вероятность составляет 99%, что значение, зафиксированное в сводном списке, составляет один миллион эфиров, а блоков в интервале — 1800 (6 часов блоков по 12 интервал секунд): ожидаемое значение составляет около 0,01391 эфира. Система защищена благодаря просить предлагающих поставить на ставку гораздо большее количество эфира, чем ожидаемое значение. Винзер и др. показал, как осуществить цензурную атаку с помощью простого smart contract это гарантирует, что определенные области памяти в состоянии не изменятся [20]. Моделирование атаки как марковская игра, в статье показано, что цензура является доминирующей стратегией рационального производитель блока, если он получит больше компенсации, чем включая транзакцию, которая меняет память. Обсуждаемое выше значение 𝑝 можно рассматривать как процент рационального блока. производителей в сети, где «рационально» не учитывается возможное наказание внешние эффекты, такие как меньшее доверие к blockchain, что снижает его ценность в криптовалюте. Следующий код представляет smart contract, который можно использовать для проведения цензурной атаки. на Бедроке. Атака использует стимулы производителей блоков, предлагая им взятку. подвергать цензуре транзакции, которые изменят определенные части государства. Основной контракт Функция ClaimBribe позволяет производителям блоков требовать взятку, если они успешно подвергают цензуре целевую транзакцию, проверив, что недействительный выходной корень не затронут. функция претензииBribe (байты памяти StorageProof) внешний { require(!claimed[block.number], "взятка уже заявлена"); Текущий объем памяти OutputProposal = StorageOracle.getStorage(L2_ORACLE, block.number, SLOT, хранилищеДоказательство); require(invalidOutputRoot == current.outputRoot, «атака не удалась»); заявлено [блок.номер] = правда; (bool отправлено, ) =block.coinbase.call{значение: bribeAmount}(""); 4https://etherscan.io/address/0xc662c410c0ecf747543f5ba90660f6abebd9c8c4require(sent, «не удалось отправить эфир»); } Листинг 1: Пример контракта, стимулирующего цензурную атаку на Bedrock. Продолжительность периода спора также должна учитывать тот факт, что доказательство вины интерактивное доказательство, поэтому участникам необходимо предоставить достаточно времени для взаимодействия и что любое взаимодействие может подвергаться цензуре. Если последний ход происходит в момент, очень близкий к В конце периода спора стоимость цензуры значительно меньше. Хотя цензура – это доминирующей стратегии, вероятность успеха ниже, поскольку узлы цензуры уязвимы для Атаки типа «отказ в обслуживании»: злоумышленник может генерировать очень сложные транзакции, которые заканчиваются публикация доказательства неисправности осуществляется бесплатно, поскольку никакие сборы не взимаются. В крайних случаях длительный период спора позволяет скоординировать действия в случае успешного решения спора. цензурная атака для организации форка и исключения атакующих производителей блоков. Другой Возможная атака состоит в публикации большего количества предложений по созданию корней штата, чем могут проверить участники спора, чего можно избежать, используя ограничение частоты. 4.1.1. Быстрый оптимистичный вывод средств Поскольку достоверность оптимистического накопительного пакета может быть проверена в любое время любым полным узлом, доверенный oracle можно использовать, чтобы узнать на L1, можно ли безопасно завершить вывод средств. Это Механизм был впервые предложен Создателем [21]: oracle проверяет вывод средств, публикует результат на L1, по которому пользователю назначается процентный кредит, который автоматически закрывается по истечении 7 дней, т. е. когда вывод действительно может быть завершен. Это решение вводит предположение о доверии, но в случае Maker оно сведено к минимуму, поскольку оператор oracle управляется той же организацией, которая принимает на себя риск, предоставляя кредит. 4.2. Транзакционные издержки Стоимость транзакций L2 в основном определяется взаимодействием с L1. В обоих решениях Вычислительная стоимость транзакций очень низкая, поскольку они выполняются полностью вне сети. Optimism публикует данные вызовов транзакций L2 как данные вызовов и редко (или никогда) выполняет ошибку доказательства, поэтому данные вызова — самый дорогой ресурс. 12 января 2022 года сеть Bedrock был запущен в тестовой сети Goerli Ethereum. Можно рассчитать степень сжатия газа отслеживая количество газа, использованного на Bedrock за определенный период, и сравнивая его с количество газа, потраченного на L1 для соответствующих блоков. С помощью этого метода происходит сжатие газа. Обнаружена скорость ~20:1, но эта цифра может отличаться в зависимости от реальной активности в основной сети. StarkNet публикует на Ethereum каждое изменение состояния L2 в виде данных вызова, поэтому хранилище самый дорогой ресурс. Поскольку сеть не использует EVM, стоимость транзакции сжатие не может быть тривиально оценено. Предполагая, что стоимость выполнения и данные вызова равны быть незначительным, можно вычислить степень сжатия записи в хранилище по сравнению с Л1. Предполагая, что контракт не развернут и 10 ячеек, к которым ранее не осуществлялся доступ на StarkNet, после модификации получена степень сжатия стоимости записи в хранилище ~24:1. Если ячейка перезаписана 𝑛раз между публикациями данных стоимость каждой записи будет равна 1/𝑛по сравнению со стоимостью одной записи, поскольку публикуется только последняя запись. Затраты можно дополнительно минимизировать за счетсжатие часто используемых значений. Стоимость проверки подтверждения действительности делится между транзакции, к которым он относится: например, блок StarkNet 4779 содержит 200 транзакций и его Доказательство действительности потребляет 267830 единиц газа или 1339,15 газа на каждую транзакцию. 4.2.1. Оптимизация данных вызова: контракт кэша Ниже представлен smart contract, который реализует кэш адресов для часто используемых адреса, воспользовавшись тем фактом, что хранение и выполнение обходятся гораздо дешевле. ресурсы вместе с контрактом друзей, который демонстрирует их использование. Последний отслеживает «друзья» адреса, которые можно зарегистрировать, вызвав функцию addFriend. Если адрес уже использовался хотя бы один раз, его можно добавить, вызвав метод addFriendWithCache. функция: индексы кэша представляют собой 4-байтовые целые числа, а адреса представлены 20 байтами, поэтому экономия аргумента функции составляет 5:1. Ту же логику можно использовать и для других данных. такие типы, как целые числа или, в более общем случае, байты. контракт AddressCache { отображение (адрес => uint32) общедоступный адрес2ключ; адрес[] открытый ключ2адрес; функция cacheWrite(address _address) внутренний возврат (uint32) { require(key2address.length < type(uint32).max, "AddressCache: кеш заполнен"); require(address2key[_address] == 0, «AddressCache: адрес уже кэширован»); // ключи должны начинаться с 1, потому что 0 означает «не найдено» ключ uint32 = uint32(key2address.length + 1); адрес2ключ[_адрес] = ключ; key2address.push(_адрес); возвратный ключ; } function cacheRead(uint32 _key) возвращает публичное представление (адрес) { require(_key <= key2address.length && _key > 0, «AddressCache: ключ не найден»); вернуть адрес key2[_key - 1]; } } Листинг 2. Контракт кэша адресов. контракт Друзья — это AddressCache { сопоставление (адрес => адрес []) общедоступных друзей; функция addFriend(адрес _friend) public { друзья[msg.sender].push(_friend); кэшWrite (_друг); } функция addFriendWithCache(uint32 _friendKey) public { друзья[msg.sender].push(cacheRead(_friendKey)); } функция getFriends() возвращает публичное представление (адрес [] памяти) { вернуть друзей[msg.sender];} } Листинг 3. Пример контракта, который наследует кэш адресов. Контракт поддерживает в кеше около 4 миллиардов (232) адресов, а добавление одного байта дает около 1 триллиона (240). 4.2.2. Оптимизация хранения: фильтры Блума На StarkNet есть несколько способов минимизировать использование памяти. Если нет необходимости гарантировать доступность исходных данных, тогда достаточно сохранить в цепочке их hash: это это механизм, используемый для сохранения данных для ERC-721 (NFT) [22], т. е. канала IPFS, который разрешает hash данных, если они доступны. Для данных, которые сохраняются несколько раз, можно использовать поиск. таблица, аналогичная системе кэширования, представленной для Optimism, требующая сохранения всех значений по адресу хотя бы один раз. В некоторых приложениях сохранения всех значений можно избежать, используя фильтр Блума. [23, 24, 25], т.е. вероятностная структура данных, позволяющая с уверенностью знать, элемент не принадлежит множеству, но допускает небольшую, но не пренебрегаемую вероятность ложного результата. позитивы. Фильтр Блума инициализируется как массив 𝑚битов с нулевым значением. Чтобы добавить элемент, используйте функцию 𝑘hash. с равномерным случайным распределением, каждый из которых соответствует биту установленного массива до 1. Чтобы проверить, принадлежит ли элемент множеству, мы запускаем функции 𝑘hash и проверяем что биты 𝑘 установлены в 1. В простом фильтре Блума нет способа отличить элемент на самом деле принадлежит множеству или является ложноположительным, вероятность, которая растет с увеличением числа записей увеличивается. После вставки 𝑛elements: P[ложное срабатывание] = (︃ 1 — [︂ 1-1 𝑚 ]︂𝑘𝑛)︃𝑘 ≈ (︁ 1 −𝑒−𝑘𝑛/𝑚)︁𝑘 предполагая независимость вероятности каждого набора битов. Если 𝑛элементы (произвольного размера!) ожидается, что он будет включен, и вероятность ложного положительного результата равна 𝑝, размер массива можно рассчитать как: 𝑚= −𝑛ln 𝑝 (пер. 2)2 А оптимальное количество функций hash составляет: 𝑘= 𝑚 𝑛ln 2 Если предположить вставку 1000 элементов с допуском 1%, размер массива составит 9585 бит. с 𝑘= 6, а при допуске 0,1% оно становится 14377 бит с 𝑘= 9. Если миллион элементов будут вставлены, размер массива составит около 1170 КБ для 1% и 1775 КБ для 0,1%, с теми же значениями 𝑘, поскольку это зависит только от 𝑝[26]. В игре, где игроки не должны быть назначены противнику, которому они уже бросили вызов, вместо сохранения в хранилище для каждого игрока списка прошлых противников можно использовать Bloom фильтр. Риск не бросить вызов некоторым игрокам часто приемлем, и фильтр можно сбросить. периодически.4.3. Ethereum совместимость Основным преимуществом совместимости с EVM и Ethereum является повторное использование всех доступных инструменты. Ethereum smart contract могут быть опубликованы на Optimism без каких-либо изменений или новые проверки. Кошельки остаются совместимыми, инструменты разработки и статического анализа, общий анализ инструменты, инструменты индексирования и oracles. Ethereum и Solidity имеют долгую историю хорошо изученных уязвимости, такие как повторные атаки, переполнение и недостаточное переполнение, быстрые кредиты и oracle манипуляции. Благодаря этому Optimism смог за короткое время получить большую сумму денег. время. Выбор использования другой виртуальной машины подразумевает необходимость перестройки всей экосистемы. с преимуществом большей свободы реализации. StarkNet изначально реализует учетную запись абстракция, представляющая собой механизм, посредством которого каждая учетная запись представляет собой smart contract, который может реализовать произвольная логика, если она соответствует интерфейсу (отсюда и термин абстракция): это позволяет использование различных схем ЭЦП, возможность изменения закрытого ключа с помощью тот же адрес или используйте мультиподпись. Сообщество Ethereum предложило ввести это механизм с EIP-2938 в 2020 году, но предложение оставалось неактуальным уже более года, поскольку другим обновлениям присвоен больший приоритет [27]. Еще одним важным преимуществом совместимости является повторное использование существующих клиентов: Optimism. использует версию geth для своего собственного узла с разницей всего в ~800 строк, что было разрабатывается, тестируется и поддерживается с 2014 года. Наличие надежного клиента имеет решающее значение, поскольку оно определяет что считается действительным или нет в сети. Ошибка в реализации доказательства неисправности система может привести к тому, что неправильное доказательство будет принято за правильное, а правильное доказательство будет принято за недействительное. блок будет принят как неправильный, ставящий под угрозу систему. Вероятность такого типа Атака может быть ограничена за счет более широкого разнообразия клиентов: Optimism можно повторно использовать в дополнение к получению другие клиенты Ethereum уже поддерживаются, а разработка еще одного клиента на базе Erigon уже идет. В 2016 году проблема с управлением памятью geth была использована для DoS-атака и первая линия защиты заключались в том, чтобы рекомендовать использование четности, второй по значимости используемый клиент на тот момент 5. StarkNet сталкивается с той же проблемой с доказательствами достоверности, но клиенты приходится писать с нуля, а система доказательства гораздо сложнее, и, следовательно, также гораздо сложнее обеспечить правильность.

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.

Заключение

Заключение Накопительные пакеты — наиболее многообещающее решение, доступное сегодня для решения проблемы масштабируемости в децентрализованные blockchain, прокладывающие путь к эпохе модульных blockchain в отличие от монолитный blockchainс. В основном показан выбор между разработкой оптимистического сводного отчета или сводного отчета по достоверности. как компромисс между сложностью и гибкостью. StarkNet имеет множество преимуществ, таких как быстрая вывод средств, структурная неспособность иметь недействительные переходы между состояниями, более низкие транзакционные издержки на за счет более длительного периода разработки и несовместимости с EVM, тогда как Optimism имеет использовали сетевую экономику, чтобы быстро завоевать значительную долю рынка. Однако Optimism Bedrock имеет модульную конструкцию, которая позволяет ему стать действительным. 5https://blog.ethereum.org/2016/09/22/ethereum-network-currently-undergoing-dos-attack

Обновление в будущем: Cannon в настоящее время использует minigeth, скомпилированный в MIPS, для защиты от ошибок. система, но ту же самую архитектуру можно использовать для получения схемы и доказательства достоверности. Компиляция сложной машины, такой как EVM, для микроархитектуры приводит к более простому результату. схема, которую не нужно дорабатывать и перепроверять в случае модернизации. RISC Zero — это проверяемая микроархитектура с уже разрабатываемыми доказательствами STARK на основе RISC-V, которая может использоваться для этой цели как альтернатива MIPS [28]. Одним из аспектов, который не следует недооценивать, является сложность понимания того, как технология работает. Сильная сторона традиционных blockchain заключается в возможности проверять состояние blockchain, не доверяя какой-либо третьей стороне. Однако в случае StarkNet это необходимо доверять реализации, когда нет возможности проверить различные компоненты основанный на криптографии и высшей математике. Первоначально это может создать трения для внедрение технологии, но по мере развития инструментов и использования доказательств целостности даже за пределами поля blockchain эта проблема, надеюсь, будет решена.