State Validity and Data Availability
State Validity and Data Availability
The core idea in sharded blockchains is that most participants operating or using the network cannot validate blocks in all the shards. As such, whenever any participant needs to interact with a particular shard they generally cannot download and validate the entire history of the shard. The partitioning aspect of sharding, however, raises a significant potential problem: without downloading and validating the entire history of a particular shard the participant cannot necessarily be certain that the state with which 5This section, except for subsection 2.5.3, was previously published at https://near.ai/ shard2. If you read it before, skip to the next section.
they interact is the result of some valid sequence of blocks and that such sequence of blocks is indeed the canonical chain in the shard. A problem that doesn’t exist in a non-sharded blockchain. We will first present a simple solution to this problem that has been proposed by many protocols and then analyze how this solution can break and what attempts have been made to address it. 2.1 Validators rotation The naive solution to state validity is shown on figure 5: let’s say we assume that the entire system has on the order of thousands validators, out of which no more than 20% are malicious or will otherwise fail (such as by failing to be online to produce a block). Then if we sample 200 validators, the probability of more than 1 3 failing for practical purposes can be assumed to be zero. Figure 5: Sampling validators 1 3 is an important threshold. There’s a family of consensus protocols, called BFT consensus protocols, that guarantees that for as long as fewer than 1 3 of participants fail, either by crashing or by acting in some way that violates the protocol, the consensus will be reached. With this assumption of honest validator percentage, if the current set of validators in a shard provides us with some block, the naive solution assumes that the block is valid and that it is built on what the validators believed to be the canonical chain for that shard when they started validating. The validators learned the canonical chain from the previous set of validators, who by the same assumption built on top of the block which was the head of the canonical chain before that. By induction the entire chain is valid, and since no set of validators at any point produced forks, the naive solution is also certain that the current chain is the only chain in the shard. See figure 6 for a visualization.
Figure 6: A blockchain with each block finalized via BFT consensus This simple solution doesn’t work if we assume that the validators can be corrupted adaptively, which is not an unreasonable assumption6. Adaptively corrupting a single shard in a system with 1000 shards is significantly cheaper than corrupting the entire system. Therefore, the security of the protocol decreases linearly with the number of shards. To have certainty in the validity of a block, we must know that at any point in history no shard in the system has a majority of validators colluding; with adaptive adversaries, we no longer have such certainty. As we discussed in section 1.5, colluding validators can exercise two basic malicious behaviors: create forks, and produce invalid blocks. Malicious forks can be addressed by blocks being cross-linked to the Beacon chain that is generally designed to have significantly higher security than the shard chains. Producing invalid blocks, however, is a significantly more challenging problem to tackle. 2.2 State Validity Consider figure 7 on which Shard #1 is corrupted and a malicious actor produces invalid block B. Suppose in this block B 1000 tokens were minted out of thin air on Alice’s account. The malicious actor then produces valid block C (in a sense that the transactions in C are applied correctly) on top of B, obfuscating the invalid block B, and initiates a cross-shard transaction to Shard #2 that transfers those 1000 tokens to Bob’s account. From this moment the improperly created tokens reside on an otherwise completely valid blockchain in Shard #2. Some simple approaches to tackle this problem are: 6Read this article for details on how adaptive corruption can be carried out: https://medium.com/nearprotocol/d859adb464c8. For more details on adaptive corruption, read https://github.com/ethereum/wiki/wiki/Sharding-FAQ# what-are-the-security-models-that-we-are-operating-under
Figure 7: A cross-shard transaction from a chain that has an invalid block 1. For validators of Shard #2 to validate the block from which the transaction is initiated. This won’t work even in the example above, since block C appears to be completely valid. 2. For validators in Shard #2 to validate some large number of blocks preceding the block from which the transaction is initiated. Naturally, for any number of blocks N validated by the receiving shard the malicious validators can create N+1 valid blocks on top of the invalid block they produced. A promising idea to resolve this issue would be to arrange shards into an undirected graph in which each shard is connected to several other shards, and only allow cross-shard transactions between neighboring shards (e.g. this is how Vlad Zamfir’s sharding essentially works7, and similar idea is used in Kadena’s Chainweb [1]). If a cross-shard transaction is needed between shards that are not neighbors, such transaction is routed through multiple shards. In this design a validator in each shard is expected to validate both all the blocks in their shard as well as all the blocks in all the neighboring shards. Consider a figure below with 10 shards, each having four neighbors, and no two shards requiring more than two hops for a cross-shard communication shown on figure 8. Shard #2 is not only validating its own blockchain, but also blockchains of all the neighbors, including Shard #1. So if a malicious actor on Shard #1 is attempting to create an invalid block B, then build block C on top of it and initiate a cross-shard transaction, such cross-shard transaction will not go through since Shard #2 will have validated the entire history of Shard #1 which will cause it to identify invalid block B. 7Read more about the design here: https://medium.com/nearprotocol/37e538177ed9
Figure 8: An invalid cross-shard transaction in chainweb-like system that will get detected While corrupting a single shard is no longer a viable attack, corrupting a few shards remains a problem. On figure 9 an adversary corrupting both Shard
1 and Shard #2 successfully executes a cross-shard transaction to Shard #3
with funds from an invalid block B: Figure 9: An invalid cross-shard transaction in chainweb-like system that will not get detected Shard #3 validates all the blocks in Shard #2, but not in Shard #1, and has no way to detect the malicious block. There are two major directions of properly solving state validity: fishermen
and cryptographic proofs of computation. 2.3 Fisherman The idea behind the first approach is the following: whenever a block header is communicated between chains for any purpose (such as cross-linking to the beacon chain, or a cross-shard transaction), there’s a period of time during which any honest validator can provide a proof that the block is invalid. There are various constructions that enable very succinct proofs that the blocks are invalid, so the communication overhead for the receiving nodes is way smaller than that of receiving a full block. With this approach for as long as there’s at least one honest validator in the shard, the system is secure. Figure 10: Fisherman This is the dominant approach (besides pretending the problem doesn’t exist) among the proposed protocols today. This approach, however, has two major disadvantages: 1. The challenge period needs to be sufficiently long for the honest validator to recognize a block was produced, download it, fully verify it, and prepare the challenge if the block is invalid. Introducing such a period would significantly slow down the cross-shard transactions. 2. The existence of the challenge protocol creates a new vector of attacks when malicious nodes spam with invalid challenges. An obvious solution to this problem is to make challengers deposit some amount of tokens that are returned if the challenge is valid. This is only a partial solution, as it might still be beneficial for the adversary to spam the system (and burn the deposits) with invalid challenges, for example to prevent the valid
challenge from a honest validator from going through. These attacks are called Grieving Attacks. See section 3.7.2 for a way to get around the latter point. 2.4 Succinct Non-interactive Arguments of Knowledge The second solution to multiple-shard corruption is to use some sort of cryptographic constructions that allow one to prove that a certain computation (such as computing a block from a set of transactions) was carried out correctly. Such constructions do exist, e.g. zk-SNARKs, zk-STARKs and a few others, and some are actively used in blockchain protocols today for private payments, most notably ZCash. The primary problem with such primitives is that they are notoriously slow to compute. E.g. Coda Protocol, that uses zk-SNARKs specifically to prove that all the blocks in the blockchain are valid, said in one of the interviews that it can take 30 seconds per transaction to create a proof (this number is probably smaller by now). Interestingly, a proof doesn’t need to be computed by a trusted party, since the proof not only attests to the validity of the computation it is built for, but to the validity of the proof itself. Thus, the computation of such proofs can be split among a set of participants with significantly less redundancy than would be necessary to perform some trustless computation. It also allows for participants who compute zk-SNARKs to run on special hardware without reducing the decentralization of the system. The challenges of zk-SNARKs, besides performance, are: 1. Dependency on less-researched and less-time-tested cryptographic primitives; 2. ”Toxic waste” — zk-SNARKs depend on a trusted setup in which a group of people performs some computation and then discards the intermediate values of that computation. If all the participants of the procedure collude and keep the intermediate values, fake proofs can be created; 3. Extra complexity introduced into the system design; 4. zk-SNARKs only work for a subset of possible computations, so a protocol with a Turing-complete smart contract language wouldn’t be able to use SNARKs to prove the validity of the chain. 2.5 Data Availability The second problem we will touch upon is data availability. Generally nodes operating a particular blockchain are separated into two groups: Full Nodes, those that download every full block and validate every transaction, and Light Nodes, those that only download block headers, and use Merkle proofs for parts of the state and transactions they are interested in, as shown on figure 11.
Figure 11: Merkle Tree Now if a majority of full nodes collude, they can produce a block, valid or invalid, and send its hash to the light nodes, but never disclose the full content of the block. There are various ways they can benefit from it. For example, consider figure 12: Figure 12: Data Availability problem There are three blocks: the previous, A, is produced by honest validators; the current, B, has validators colluding; and the next, C, will be also produced by honest validators (the blockchain is depicted in the bottom right corner). You are a merchant. The validators of the current block (B) received block A from the previous validators, computed a block in which you receive money,
and sent you a header of that block with a Merkle proof of the state in which you have money (or a Merkle proof of a valid transaction that sends the money to you). Confident the transaction is finalized, you provide the service. However, the validators never distribute the full content of the block B to anyone. As such, the honest validators of block C can’t retrieve the block, and are either forced to stall the system or to build on top of A, depriving you as a merchant of money. When we apply the same scenario to sharding, the definitions of full and light node generally apply per shard: validators in each shard download every block in that shard and validate every transaction in that shard, but other nodes in the system, including those that snapshot shard chains state into the beacon chain, only download the headers. Thus the validators in the shard are effectively full nodes for that shard, while other participants in the system, including the beacon chain, operate as light nodes. For the fisherman approach we discussed above to work, honest validators need to be able to download blocks that are cross-linked to the beacon chain. If malicious validators cross-linked a header of an invalid block (or used it to initiate a cross-shard transaction), but never distributed the block, the honest validators have no way to craft a challenge. We will cover three approaches to address this problem that complement each other. 2.5.1 Proofs of Custody The most immediate problem to be solved is whether a block is available once it is published. One proposed idea is to have so-called Notaries that rotate between shards more often than validators whose only job is to download a block and attest to the fact that they were able to download it. They can be rotated more frequently because they don’t need to download the entire state of the shard, unlike the validators who cannot be rotated frequently since they must download the state of the shard each time they rotate, as shown on figure 13. The problem with this naive approach is that it is impossible to prove later whether the Notary was or was not able to download the block, so a Notary can choose to always attest that they were able to download the block without even attempting to retrieve it. One solution to this is for Notaries to provide some evidence or to stake some amount of tokens attesting that the block was downloaded. One such solution is discussed here: https://ethresear.ch/t/ 1-bit-aggregation-friendly-custody-bonds/2236. 2.5.2 Erasure Codes When a particular light node receives a hash of a block, to increase the node’s confidence that the block is available it can attempt to download a few random pieces of the block. This is not a complete solution, since unless the light nodes collectively download the entire block the malicious block producers can choose
Figure 13: Validators need to download state and thus cannot be rotated frequently to withhold the parts of the block that were not downloaded by any light node, thus still making the block unavailable. One solution is to use a construction called Erasure Codes to make it possible to recover the full block even if only some part of the block is available, as shown on figure 14. Figure 14: Merkle tree built on top of erasure coded data Both Polkadot and Ethereum Serenity have designs around this idea that provide a way for light nodes to be reasonably confident the blocks are available. The Ethereum Serenity approach has a detailed description in [2].
2.5.3 Polkadot’s approach to data availability In Polkadot, like in most sharded solutions, each shard (called parachain) snapshots its blocks to the beacon chain (called relay chain). Say there are 2f + 1 validators on the relay chain. The block producers of the parachain blocks, called collators, once the parachain block is produced compute an erasure coded version of the block that consists of 2f +1 parts such that any f parts are sufficient to reconstruct the block. They then distribute one part to each validator on the relay chain. A particular relay chain validator would only sign on a relay chain block if they have their part for each parachain block that is snapshotted to such relay chain block. Thus, if a relay chain block has signatures from 2f + 1 validators, and for as long as no more than f of them violated the protocol, each parachain block can be reconstructed by fetching the parts from the validators that follow the protocol. See figure 15. Figure 15: Polkadot’s data availability 2.5.4 Long term data availability Note that all the approaches discussed above only attest to the fact that a block was published at all, and is available now. Blocks can later become unavailable for a variety of reasons: nodes going offline, nodes intentionally erasing historical data, and others. A whitepaper worth mentioning that addresses this issue is Polyshard [3], which uses erasure codes to make blocks available across shards even if several shards completely lose their data. Unfortunately their specific approach requires all the shards to download blocks from all other shards, which is prohibitively expensive. The long term availability is not as pressing of an issue: since no participant in the system is expected to be capable of validating all the chains in all the
shards, the security of the sharded protocol needs to be designed in such a way that the system is secure even if some old blocks in some shards become completely unavailable.
Государственная достоверность и доступность данных
Основная идея сегментированных blockchain заключается в том, что большинство участников, работающих или использование сети не может проверить блоки во всех сегментах. Таким образом, всякий раз, когда любому участнику необходимо взаимодействовать с конкретным шардом, который он обычно не может загрузите и проверьте всю историю осколка. Однако аспект секционирования при шардинге открывает значительный потенциал. проблема: без скачивания и проверки всей истории конкретного шард участник не обязательно может быть уверен, что состояние, с которым 5Данный раздел, за исключением подраздела 2.5.3, ранее был опубликован по адресу https://near.ai/. осколок2. Если вы читали это раньше, перейдите к следующему разделу.
они взаимодействуют, является результатом некоторой допустимой последовательности блоков, и эта последовательность блоков действительно является канонической цепочкой в шарде. Проблема, которой нет существуют в несегментированном blockchain. Сначала мы представим простое решение этой проблемы, которое было предложено по множеству протоколов, а затем проанализировать, как это решение может сломаться и что были предприняты попытки решить эту проблему. 2.1 Ротация валидаторов Наивное решение проблемы валидности состояния показано на рисунке 5: скажем, мы предположим, что что вся система имеет порядка тысяч validator, из которых не более 20% являются вредоносными или потерпят неудачу по другим причинам (например, из-за невозможности онлайн для создания блока). Тогда, если мы выберем 200 validators, вероятность более 1 3 для практических целей можно принять равным нулю. Рисунок 5: Выборка validators 1 3 – важный порог. Существует семейство консенсусных протоколов, называемое BFT протоколы консенсуса, которые гарантируют, что до тех пор, пока меньше 1 3 из участники терпят неудачу либо из-за сбоя, либо из-за действий, нарушающих правила. протокол, консенсус будет достигнут. При этом предположении о честном validator проценте, если текущий набор validators в шарде предоставляют нам некоторый блок, предполагает наивное решение что блок действителен и что он построен на основе того, что считали validators каноническую цепочку для этого шарда, когда они начали проверять. validators изучил каноническую цепочку из предыдущего набора validators, которые тем же предположение, построенное на вершине блока, который был главой канонической цепочки до этого. По индукции вся цепочка действительна, и поскольку ни один набор validators в любой момент создаются вилки, наивное решение также уверено, что текущий Chain — единственная цепочка в шарде. См. рисунок 6 для визуализации.
Рисунок 6: blockchain, где каждый блок завершается консенсусом BFT. Это простое решение не сработает, если мы предположим, что validators могут быть повреждаются адаптивно, что не является необоснованным предположением6. Адаптивно повреждение одного шарда в системе с 1000 шардами обходится значительно дешевле. чем развращать всю систему. Таким образом, безопасность протокола снижается линейно с увеличением количества шардов. Чтобы быть уверенным в достоверности блок, мы должны знать, что в любой момент истории ни один шард в системе не большинство validator в сговоре; с адаптивными противниками у нас больше нет такая уверенность. Как мы обсуждали в разделе 1.5, вступившие в сговор validator могут осуществлять два основных вредоносных действия: создание разветвлений и создание недействительных блоков. Вредоносные форки могут быть устранены путем присоединения блоков к цепочке Beacon, которая обычно спроектирована так, чтобы обеспечить значительно более высокий уровень безопасности, чем цепочки осколков. Однако создание недействительных блоков является значительно более сложной задачей. сложная проблема, требующая решения. 2.2 Государственная действительность Рассмотрим рисунок 7, на котором шард №1 поврежден и злоумышленник создает недействительный блок B. Предположим, в этом блоке B было отчеканено 1000 token из тонких air за счет Алисы. Затем злоумышленник создает действительный блок C (в ощущение, что транзакции в C применяются правильно) поверх B, что запутывает недействительный блок B и инициирует межшардовую транзакцию с шардом №2, которая переводит эти 1000 __PH_0006__s на счет Боба. С этого момента неправильно созданные token находятся на полностью допустимом в остальном blockchain в осколке №2. Вот несколько простых способов решения этой проблемы: 6Читать это статья для детали на как адаптивный коррупция может быть нес выход: https://medium.com/nearprotocol/d859adb464c8. Для больше детали на адаптивный коррупция, читать https://github.com/ethereum/wiki/wiki/Sharding-FAQ# какие-модели-безопасности-мы-действуемРисунок 7: Межшардовая транзакция из цепочки с недействительным блоком 1. Для validator шарда №2 для проверки блока, из которого была выполнена транзакция. инициируется. Это не сработает даже в примере выше, так как блок C представляется вполне верным. 2. Для validator в шарде №2 для проверки большого количества блоков, предшествующих блоку, из которого инициируется транзакция. Естественно, для любое количество блоков N, проверенное принимающим шардом, вредоносный validators могут создавать N+1 действительных блоков поверх недействительного блока, который они произведено. Многообещающей идеей решения этой проблемы было бы объединение шардов в неориентированный граф, в котором каждый шард связан с несколькими другими шардами, и разрешать только межшардовые транзакции между соседними шардами (например, так Шардинг Влада Замфира по существу работает7, и аналогичная идея используется в методе Кадены. Цепная паутина [1]). Если необходима межшардовая транзакция между шардами, которые не соседи, такая транзакция маршрутизируется через несколько сегментов. В этом дизайне Ожидается, что validator в каждом сегменте будет проверять оба блока в их сегменте. а также все блоки во всех соседних шардах. Рассмотрим рисунок ниже с 10 шардами, каждый из которых имеет по четыре соседа, и никакие два шарда не требуют больше чем два прыжка для связи между сегментами, показанной на рисунке 8. Шард №2 проверяет не только свой собственный blockchain, но и blockchain все соседи, включая Осколок №1. Итак, если злоумышленник на Осколке №1 пытается создать недопустимый блок B, а затем построить блок C поверх него и инициировать межшардовую транзакцию, такая межшардовая транзакция не пройдет поскольку Шард №2 подтвердит всю историю Шарда №1, которая заставит его идентифицировать недействительный блок B. 7Подробнее о дизайне читайте здесь: https://medium.com/nearprotocol/37e538177ed9
Рисунок 8: Недействительная межсегментная транзакция в системе, похожей на цепную сеть, которая будет быть обнаруженным Хотя повреждение одного осколка больше не является жизнеспособной атакой, повреждение несколько осколков остаются проблемой. На рисунке 9 противник портит оба Шарда №1 и шард №2 успешно выполняют межсегментную транзакцию с шардом №3. со средствами из невалидного блока Б: Рисунок 9: Недействительная межсегментная транзакция в системе, похожей на цепную сеть, которая будет не быть обнаруженным Шард №3 проверяет все блоки в Шарде №2, но не в Шарде №1, и не имеет возможности обнаружить вредоносный блок. Есть два основных направления правильного решения государственной действительности: рыбаки
и криптографические доказательства вычислений. 2.3 Рыбак Идея первого подхода заключается в следующем: всякий раз, когда заголовок блока передается между цепочками для любых целей (например, сшивание с цепочке маяков или транзакции между шардами), существует период времени, в течение которого который любой честный validator может предоставить доказательство того, что блок недействителен. Там представляют собой различные конструкции, которые позволяют очень кратко доказать, что блоки недействителен, поэтому накладные расходы на связь для принимающих узлов намного меньше чем получение полного блока. При таком подходе до тех пор, пока в сети есть хотя бы один честный validator осколок, система безопасна. Рисунок 10: Рыбак Это доминирующий подход (помимо притворства, что проблемы не существует) среди предлагаемых сегодня протоколов. Однако этот подход имеет два основные недостатки: 1. Период проверки должен быть достаточно длительным для честного validator. распознать, что блок был создан, загрузить его, полностью проверить и подготовить вызов, если блок недействителен. Введение такого периода позволит значительно замедляют межсегментные транзакции. 2. Существование протокола вызова создает новый вектор атак. когда злонамеренные узлы спамят недействительными вызовами. Очевидное решение Чтобы решить эту проблему, нужно заставить претендентов внести некоторую сумму tokens, которая возвращаются, если вызов действителен. Это лишь частичное решение, так как оно злоумышленнику все равно может быть выгодно рассылать спам по системе (и сжигать депозиты) с недействительными проблемами, например, для предотвращения действительноговызов от честного validator прохождения. Эти атаки называемые «Атаки скорби». См. раздел 3.7.2, чтобы узнать, как обойти последний пункт. 2.4 Краткие неинтерактивные аргументы знаний Второе решение проблемы повреждения нескольких сегментов — использовать какие-то криптографические конструкции, позволяющие доказать, что определенное вычисление (например, как вычисление блока из набора транзакций) было проведено корректно. Такие конструкции существуют, напр. zk-SNARKs, zk-STARKs и некоторые другие, а некоторые сегодня активно используются в протоколах blockchain для частных платежей, в первую очередь ZCash. Основная проблема с такими примитивами заключается в том, что они известны своей медленностью вычислений. Например. Протокол Coda, использующий zk-SNARK специально для того, чтобы доказать, что все блоки в blockchain действительны, сказано в одном интервью, что для создания доказательства может потребоваться 30 секунд на одну транзакцию (сейчас это число, вероятно, меньше). Интересно, что доказательство не обязательно должно быть вычислено доверенной стороной, поскольку доказательство не только подтверждает достоверность вычислений, для которых оно построено, но и достоверность самого доказательства. Таким образом, вычисление таких доказательств можно разделить среди набора участников со значительно меньшей избыточностью, чем было бы необходимо выполнить некоторые ненадежные вычисления. Это также позволяет участникам которые вычисляют zk-SNARK для работы на специальном оборудовании без снижения децентрализация системы. Проблемы zk-SNARK, помимо производительности, заключаются в следующем: 1. Зависимость от менее исследованных и менее проверенных временем криптографических примитивов; 2. «Токсичные отходы» — zk-SNARK зависят от доверенной установки, в которой группа людей выполняет некоторые вычисления, а затем отбрасывает промежуточные значения этого вычисления. Если все участники процедуры вступили в сговор и сохраняйте промежуточные значения, могут быть созданы фальшивые доказательства; 3. Дополнительная сложность, вносимая в конструкцию системы; 4. zk-SNARK работают только для подмножества возможных вычислений, поэтому протокол с полным по Тьюрингу языком smart contract невозможно было бы использовать SNARK для подтверждения достоверности цепочки. 2,5 Доступность данных Вторая проблема, которую мы затронем, — доступность данных. Обычно узлы эксплуатирующие конкретный blockchain, разделены на две группы: полные узлы, те, которые загружают каждый полный блок и проверяют каждую транзакцию, и Light Узлы, которые загружают только заголовки блоков и используют доказательства Меркла для частей. состояния и транзакций, в которых они заинтересованы, как показано на рисунке 11.
Рисунок 11: Дерево Меркла Теперь, если большинство полных узлов вступают в сговор, они могут создать блок, действительный или недействителен и отправляет его hash на легкие узлы, но никогда не раскрывает полное содержимое блока. Есть разные способы, которыми они могут извлечь из этого выгоду. Например, рассмотрим рисунок 12: Рисунок 12: Проблема с доступностью данных Есть три блока: предыдущий, A, создан честными validators; текущий B имеет в сговоре validators; и следующий, C, также будет произведен честными validators (blockchain изображен в правом нижнем углу). Вы торговец. validator текущего блока (B) получил блок A из предыдущих validators вычислил блок, в котором вы получаете деньги,и отправил вам заголовок этого блока с доказательством Меркла о состоянии, в котором у вас есть деньги (или подтверждение Merkle о действительной транзакции, которая отправляет деньги тебе). Уверенные, что транзакция завершена, вы предоставляете услугу. Однако validator никогда не передают полное содержимое блока B кто угодно. Таким образом, честные validator блока C не могут получить блок и вынуждены либо останавливать систему, либо строить на вершине А, лишая вас как торговец деньгами. Когда мы применяем тот же сценарий к сегментированию, определения полного и Легкий узел обычно применяется к каждому сегменту: validators в каждом сегменте загружается каждые блокировать в этом сегменте и проверять каждую транзакцию в этом сегменте, но другие узлы в системе, включая те, которые сохраняют состояние цепочек осколков моментальных снимков в цепочка маяков, загружайте только заголовки. Таким образом, validator в осколке фактически полные узлы для этого шарда, в то время как другие участники системы включая маяковую цепь, работают как легкие узлы. Чтобы подход рыбака, который мы обсуждали выше, работал, честные validators необходимо иметь возможность загружать блоки, связанные с цепочкой маяков. Если злонамеренные validators связали заголовок недопустимого блока (или использовали его для инициировать транзакцию между шардами), но никогда не распределял блок, честный validator не имеют возможности придумать испытание. Мы рассмотрим три подхода к решению этой проблемы, которые дополняют друг друга. 2.5.1 Доказательства содержания под стражей Самая неотложная проблема, которую необходимо решить, — доступен ли блок один раз. оно опубликовано. Одна из предложенных идей заключается в том, чтобы иметь так называемых нотариусов, которые чередуются. между шардами чаще, чем validators, единственная задача которых — загрузить заблокировать и подтвердить, что они смогли его скачать. Они могут быть ротируются чаще, потому что им не нужно загружать все состояние осколка, в отличие от validator, которых нельзя часто менять, поскольку они должен загружать состояние шардов каждый раз, когда они вращаются, как показано на рисунке 13. Проблема с этим наивным подходом в том, что позже невозможно доказать смог или не смог нотариус загрузить блок, поэтому нотариус могут всегда подтверждать, что они смогли загрузить блок без даже пытаясь его вернуть. Одним из решений этой проблемы является предоставление нотариусам некоторые доказательства или поставить некоторое количество tokens, подтверждающих, что блок был скачал. Одно из таких решений обсуждается здесь: https://ethresear.ch/t/. 1-битные депозитарные облигации, благоприятные для агрегации/2236. 2.5.2 Коды стирания Когда конкретный легкий узел получает hash блока, чтобы увеличить будучи уверенным в том, что блок доступен, он может попытаться загрузить несколько случайных кусочки блока. Это не полное решение, так как разве что легкие узлы коллективно загрузить весь блок, который могут выбрать производители вредоносных блоков
Рисунок 13: Валидаторам необходимо загрузить состояние, и поэтому их нельзя менять. часто удерживать части блока, которые не были загружены каким-либо легким узлом, тем самым делая блок недоступным. Одним из решений является использование конструкции под названием «Коды стирания», позволяющей восстановить весь блок, даже если доступна только некоторая часть блока, как показано на рисунке 14. Рисунок 14: Merkle tree построен на основе данных стирающего кодирования И Polkadot, и Ethereum Serenity используют эту идею, предоставить легким узлам возможность быть достаточно уверенными в доступности блоков. Подход Ethereum Serenity подробно описан в [2].2.5.3 Подход Polkadot к доступности данных В Polkadot, как и в большинстве сегментированных решений, каждый сегмент (называемый парачейном) передает свои блоки в цепочку маяков (называемую цепочкой реле). Скажем, есть 2f + 1. validators в цепи реле. Производители блоков парачейна, называемые средства сортировки, как только блок парачейна создан, вычисляют версию блока со стирающим кодом, состоящую из 2f +1 частей, так что любых f частей достаточно. реконструировать блок. Затем они раздают по одной части каждому validator на релейная цепь. Определенная цепочка ретрансляции validator будет только подписываться на цепочку ретрансляции. блокировать, если у них есть своя часть для каждого блока парачейна, снимок которого сделан в такой блок релейной цепи. Таким образом, если блок релейной цепи имеет сигнатуры от 2f + 1 validators, и до тех пор, пока не более f из них нарушили протокол, каждый Блок парачейна можно реконструировать, извлекая части из validators которые следуют протоколу. См. рисунок 15. Рисунок 15: Доступность данных Polkadot 2.5.4 Долгосрочная доступность данных Заметим, что все рассмотренные выше подходы свидетельствуют лишь о том, что блок вообще был опубликован и доступен сейчас. Блоки могут позже стать недоступными. по разным причинам: узлы отключаются от сети, узлы намеренно стирают историю данные и другие. Стоит упомянуть технический документ, посвященный этой проблеме, — Polyshard [3], который использует коды стирания, чтобы сделать блоки доступными для всех осколков, даже если их несколько. осколки полностью теряют свои данные. К сожалению, их специфический подход требует все шарды для скачивания блоков со всех остальных шардов, что непомерно дорого. Долгосрочная доступность не является столь острой проблемой: поскольку ни один участник Ожидается, что система будет способна проверять все цепочки во всех
сегментов, безопасность сегментированного протокола должна быть спроектирована таким образом, способ обеспечить безопасность системы, даже если некоторые старые блоки в некоторых шардах станут совершенно недоступен.
Nightshade
Nightshade
3.1 From shard chains to shard chunks The sharding model with shard chains and a beacon chain is very powerful but has certain complexities. In particular, the fork choice rule needs to be executed in each chain separately, the fork choice rule in the shard chains and the beacon chain must be built differently and tested separately. In Nightshade we model the system as a single blockchain, in which each block logically contains all the transactions for all the shards, and changes the whole state of all the shards. Physically, however, no participant downloads the full state or the full logical block. Instead, each participant of the network only maintains the state that corresponds to the shards that they validate transactions for, and the list of all the transactions in the block is split into physical chunks, one chunks per shard. Under ideal conditions each block contains exactly one chunk per shard per block, which roughly corresponds to the model with shard chains in which the shard chains produce blocks with the same speed as the beacon chain. However, due to network delays some chunks might be missing, so in practice each block contains either one or zero chunks per shard. See section 3.3 for details on how blocks are produced. Figure 16: A model with shard chains on the left and with one chain having blocks split into chunks on the right
3.2 Consensus The two dominant approaches to the consensus in the blockchains today are the longest (or heaviest) chain, in which the chain that has the most work or stake used to build it is considered canonical, and BFT, in which for each block some set of validators reach a BFT consensus. In the protocols proposed recently the latter is a more dominant approach, since it provides immediate finality, while in the longest chain more blocks need to be built on top of the block to ensure the finality. Often for a meaningful security the time it takes for sufficient number of blocks to be built takes on the order of hours. Using BFT consensus on each block also has disadvantages, such as: 1. BFT consensus involves considerable amount of communication. While recent advances allow the consensus to be reached in linear time in number of participants (see e.g. [4]), it is still noticeable overhead per block; 2. It is unfeasible for all the network participants to participate in the BFT consensus per block, thus usually only a randomly sampled subset of participants reach the consensus. A randomly sampled set can be, in principle, adaptively corrupted, and a fork in theory can be created. The system either needs to be modelled to be ready for such an event, and thus still have a fork-choice rule besides the BFT consensus, or be designed to shut down in such an event. It is worth mentioning that some designs, such as Algorand [5], significantly reduce the probability of adaptive corruption. 3. Most importantly, the system stalls if 1 3 or more of all the participants are offline. Thus, any temporary network glitch or a network split can completely stall the system. Ideally the system must be able to continue to operate for as long as at least half of the participants are online (heaviest chain-based protocols continue operating even if less than half of the participants are online, but the desirability of this property is more debatable within the community). A hybrid model in which the consensus used is some sort of the heaviest chain, but some blocks are periodically finalized using a BFT finality gadget maintain the advantages of both models. Such BFT finality gadgets are Casper FFG [6] used in Ethereum 2.0 8, Casper CBC (see https://vitalik. ca/general/2018/12/05/cbc_casper.html) and GRANDPA (see https:// medium.com/polkadot-network/d08a24a021b5) used in Polkadot. Nightshade uses the heaviest chain consensus. Specifically when a block producer produces a block (see section 3.3), they can collect signatures from other block producers and validators attesting to the previous block. See section 3.8 for details how such large number of signatures is aggregated. The weight 8Also see the whiteboard session with Justin Drake for an indepth overview of Casper FFG, and how it is integrated with the GHOST heaviest chain consensus here: https://www. youtube.com/watch?v=S262StTwkmo
of a block is then the cumulative stake of all the signers whose signatures are included in the block. The weight of a chain is the sum of the block weights. On top of the heaviest chain consensus we use a finality gadget that uses the attestations to finalize the blocks. To reduce the complexity of the system, we use a finality gadget that doesn’t influence the fork choice rule in any way, and instead only introduces extra slashing conditions, such that once a block is finalized by the finality gadget, a fork is impossible unless a very large percentage of the total stake is slashed. Casper CBC is such a finality gadget, and we presently model with Casper CBC in mind. We also work on a separate BFT protocol called TxFlow. At the time of writing this document it is unclear if TxFlow will be used instead of Casper CBC. We note, however, that the choice of the finality gadget is largely orthogonal to the rest of the design. 3.3 Block production In Nightshade there are two roles: block producers and validators. At any point the system contains w block producers, w = 100 in our models, and wv validators, in our model v = 100, wv = 10, 000. The system is Proof-of-Stake, meaning that both block producers and validators have some number of internal currency (referred to as ”tokens”) locked for a duration of time far exceeding the time they spend performing their duties of building and validating the chain. As with all the Proof of Stake systems, not all the w block producers and not all the wv validators are different entities, since that cannot be enforced. Each of the w block producers and the wv validators, however, do have a separate stake. The system contains n shards, n = 1000 in our model. As mentioned in section 3.1, in Nightshade there are no shard chains, instead all the block producers and validators are building a single blockchain, that we refer to as the main chain. The state of the main chain is split into n shards, and each block producer and validator at any moment only have downloaded locally a subset of the state that corresponds to some subset of the shards, and only process and validate transactions that affect those parts of the state. To become a block producer, a participant of the network locks some large amount of tokens (a stake). The maintenance of the network is done in epochs, where an epoch is a period of time on the order of days. The participants with the w largest stakes at the beginning of a particular epoch are the block producers for that epoch. Each block producer is assigned to sw shards, (say sw = 40, which would make sww/n = 4 block producers per shard). The block producer downloads the state of the shard they are assigned to before the epoch starts, and throughout the epoch collects transactions that affect that shard, and applies them to the state. For each block b on the main chain, and for every shards s, there’s one of the assigned block producers to s who is responsible to produce the part of b related to the shard. The part of b related to shard s is called a chunk, and contains the list of the transactions for the shard to be included in b, as well as the merkle
root of the resulting state. b will ultimately only contain a very small header of the chunk, namely the merkle root of all the applied transactions (see section 3.7.1 for exact details), and the merkle root of the final state. Throughout the rest of the document we often refer to the block producer that is responsible to produce a chunk at a particular time for a particular shard as a chunk producer. Chunk producer is always one of the block producers. The block producers and the chunk producers rotate each block according to a fixed schedule. The block producers have an order and repeatedly produce blocks in that order. E.g. if there are 100 block producers, the first block producers is responsible for producing blocks 1, 101, 201 etc, the second is responsible for producing 2, 102, 202 etc). Since chunk production, unlike the block production, requires maintaining the state, and for each shard only sww/n block producers maintain the state per shard, correspondingly only those sww/n block producers rotate to create chunks. E.g. with the constants above with four block producers assigned to each shard, each block producer will be creating chunks once every four blocks. 3.4 Ensuring data availability To ensure the data availability we use an approach similar to that of Polkadot described in section 2.5.3. Once a block producer produces a chunk, they create an erasure coded version of it with an optimal (w, ⌊w/6 + 1⌋) block code of the chunk. They then send one piece of the erasure coded chunk (we call such pieces chunk parts, or just parts) to each block producer. We compute a merkle tree that contains all the parts as the leaves, and the header of each chunk contains the merkle root of such tree. The parts are sent to the validators via onepart messages. Each such message contains the chunk header, the ordinal of the part and the part contents. The message also contains the signature of the block producer who produced the chunk and the merkle path to prove that the part corresponds to the header and is produced by the proper block producer. Once a block producer receives a main chain block, they first check if they have onepart messages for each chunk included in the block. If not, the block is not processed until the missing onepart messages are retrieved. Once all the onepart messages are received, the block producer fetches the remaining parts from the peers and reconstructs the chunks for which they hold the state. The block producer doesn’t process a main chain block if for at least one chunk included in the block they don’t have the corresponding onepart message, or if for at least one shard for which they maintain the state they cannot reconstruct the entire chunk. For a particular chunk to be available it is enough that ⌊w/6⌋+1 of the block producers have their parts and serve them. Thus, for as long as the number of malicious actors doesn’t exceed ⌊w/3⌋no chain that has more than half block producers building it can have unavailable chunks.
Figure 17: Each block contains one or zero chunks per shard, and each chunk is erasure coded. Each part of the erasure coded chunk is sent to a designated block producer via a special onepart message 3.4.1 Dealing with lazy block producers If a block producer has a block for which a onepart message is missing, they might choose to still sign on it, because if the block ends up being on chain it will maximize the reward for the block producer. There’s no risk for the block producer since it is impossible to prove later that the block producer didn’t have the onepart message. To address it we make each chunk producer when creating the chunk to choose a color (red or blue) for each part of the future encoded chunk, and store the bitmask of assigned color in the chunk before it is encoded. Each onepart message then contains the color assigned to the part, and the color is used when computing the merkle root of the encoded parts. If the chunk producer deviates from the protocol, it can be easily proven, since either the merkle root will not correspond to onepart messages, or the colors in the onepart messages that correspond to the merkle root will not match the mask in the chunk. When a block producer signs on a block, they include a bitmask of all the red parts they received for the chunks included in the block. Publishing an incorrect bitmask is a slashable behavior. If a block producer hasn’t received a onepart message, they have no way of knowing the color of the message, and thus have a 50% chance of being slashed if they attempt to blidnly sign the block. 3.5 State transition application The chunk producers only choose which transactions to include in the chunk but do not apply the state transition when they produce a chunk. Correspondingly,
the chunk header contains the merkle root of the merkelized state as of before the transactions in the chunk are applied. The transactions are only applied when a full block that includes the chunk is processed. A participant only processes a block if 1. The previous block was received and processed; 2. For each chunk the participant doesn’t maintain the state for they have seen the onepart message; 3. For each chunk the participant does maintain the state for they have the full chunk. Once the block is being processed, for each shard for which the participant maintains the state for, they apply the transactions and compute the new state as of after the transactions are applied, after which they are ready to produce the chunks for the next block, if they are assigned to any shard, since they have the merkle root of the new merkelized state. 3.6 Cross-shard transactions and receipts If a transaction needs to affect more than one shard, it needs to be consecutively executed in each shard separately. The full transaction is sent to the first shard affected, and once the transaction is included in the chunk for such shard, and is applied after the chunk is included in a block, it generates a so called receipt transaction, that is routed to the next shard in which the transaction need to be executed. If more steps are required, the execution of the receipt transaction generates a new receipt transaction and so on. 3.6.1 Receipt transaction lifetime It is desirable that the receipt transaction is applied in the block that immediately follows the block in which it was generated. The receipt transaction is only generated after the previous block was received and applied by block producers that maintain the originating shard, and needs to be known by the time the chunk for the next block is produced by the block producers of the destination shard. Thus, the receipt must be communicated from the source shard to the destination shard in the short time frame between those two events. Let A be the last produced block which contains a transaction t that generates a receipt r. Let B be the next produced block (i.e. a block that has A as its previous block) that we want to contain r. Let t be in the shard a and r be in the shard b. The lifetime of the receipt, also depicted on figure 18, is the following: Producing and storing the receipts. The chunk producer cpa for shard a receives the block A, applies the transaction t and generates the receipt r. cpa then stores all such produced receipts in its internal persistent storage indexed by the source shard id.
Distributing the receipts. Once cpa is ready to produce the chunk for shard a for block B, they fetch all the receipts generated by applying the transactions from block A for shard a, and included them into the chunk for shrad a in block B. Once such chunk is generated, cpa produces its erasure coded version and all the corresponding onepart messages. cpa knows what block producers maintain the full state for which shards. For a particular block producer bp cpa includes the receipts that resulted from applying transactions in block A for shard a that have any of the shards that bp cares about as their destination in the onepart message when they distributed the chunk for shard a in block B (see figure 17, that shows receipts included in the onepart message). Receiving the receipts. Remember that the participants (both block producers and validators) do not process blocks until they have onepart messages for each chunk included in the block. Thus, by the time any particular particpiant applies the block B, they have all the onepart messages that correspond to chunks in B, and thus they have all the incoming receipts that have the shards the participant maintains state for as their destination. When applying the state transition for a particular shard, the participant apply both the receipts that they have collected for the shard in the onepart messages, as well as all the transactions included in the chunk itself. Figure 18: The lifetime of a receipt transaction 3.6.2 Handling too many receipts It is possible that the number of receipts that target a particular shard in a particular block is too large to be processed. For example, consider figure 19, in which each transaction in each shard generates a receipt that targets shard 1. By the next block the number of receipts that shard 1 needs to process is comparable to the load that all the shards combined processed while handling the previous block.
Figure 19: If all the receipts target the same shard, the shard might not have the capacity to process them To address it we use a technique similar to that used in QuarkChain 9. Specifically, for each shard the last block B and the last shard s within that block from which the receipts were applied is recorded. When the new shard is created, the receipt are applied in order first from the remaining shards in B, and then in blocks that follow B, until the new chunk is full. Under normal circumstances with a balanced load it will generally result in all the receipts being applied (and thus the last shard of the last block will be recorded for each chunk), but during times when the load is not balanced, and a particular shard receives disproportionately many receipts, this technique allows them to be processed while respecting the limits on the number of transactions included. Note that if such unbalanced load remains for a long time, the delay from the receipt creation until application can continue growing indefinitely. One way to address it is to drop any transaction that creates a receipt targeting a shard that has a processing delay that exceeds some constant (e.g. one epoch). Consider figure 20. By block B the shard 4 cannot process all the receipts, so it only processes receipts origination from up to shard 3 in block A, and records it. In block C the receipts up to shard 5 in block B are included, and then by block D the shard catches up, processing all the remaining receipts in block B and all the receipts from block C. 3.7 Chunks validation A chunk produced for a particular shard (or a shard block produced for a particular shard chain in the model with shard chains) can only be validated by the 9See the whiteboard episode with QuarkChain here: https://www.youtube.com/watch? v=opEtG6NM4x4, in which the approach to cross-shard transactions is discussed, among other things
Figure 20: Delayed receipts processing participants that maintain the state. They can be block producers, validators, or just external witnesses that downloaded the state and validate the shard in which they store assets. In this document we assume that majority of the participants cannot store the state for a large fraction of the shards. It is worth mentioning, however, that there are sharded blockchains that are designed with the assumption that most participants do have capacity to store the state for and validate most of the shards, such as QuarkChain. Since only a fraction of the participants have the state to validate the shard chunks, it is possible to adaptive corrupt just the participants that have the state, and apply an invalid state transition. Multiple sharding designs were proposed that sample validators every few days, and within a day any block in the shard chain that has more than 2/3 of signatures of the validators assigned to such shard is immediately considered final. With such approach an adaptive adversary only needs to corrupt 2n/3+1 of the validators in a shard chain to apply an invalid state transition, which, while is likely hard to pull off, is not a level of security sufficient for a public blockchain. As discussed in section 2.3, the common approach is to allow a certain window of time after a block is created for any participant that has state (whether it’s a block producer, a validator, or an external observer) to challenge its validity. Such participants are called Fishermen. For a fisherman to be able to challenge an invalid block, it must be ensured that such a block is available to them. The data availability in Nightshade is discussed in section 3.4. In Nightshade once a block is produced, the chunks were not validated by anyone but the actual chunk producer. In particular, the block producer that suggested the block naturally didn’t have the state for most of the shards, and
was not able to validate the chunks. When the next block is produced, it contains attestations (see section 3.2) of multiple block producers and validators, but since the majority of block producers and validators do not maintain state for most shards as well, a block with just one invalid chunk will collect significantly more than half of the attestations and will continue being on the heaviest chain. To address this issue, we allow any participant that maintains the state of a shard to submit a challenge on-chain for any invalid chunk produced in that shard. 3.7.1 State validity challenge Once a participant detects that a particular chunk is invalid, they need to provide a proof that the chunk is invalid. Since the majority of the network participants do not maintain the state for the shard in which the invalid chunk is produced, the proof needs to have sufficient information to confirm the block is invalid without having the state. We set a limit Ls of the amount of state (in bytes) that a single transaction can cumulatively read or write. Any transaction that touches more than Ls state is considered to be invalid. Remember from the section 3.5 that the chunk in a particular block B only contains the transactions to be applied, but not the new state root. The state root included in the chunk in block B is the state root before applying such transactions, but after applying the transactions from the last chunk in the same shard before the block B. A malicious actor that wishes to apply an invalid state transition would include an incorrect state root in block B that doesn’t correspond to the state root that results from applying the transactions in the preceding chunk. We extend the information that a chunk producer includes in the chunk. Instead of just including the state after applying all the transactions, it instead includes a state root after applying each contiguous set of transactions that collectively read and write Ls bytes of state. With this information for the fisherman to create a challenge that a state transition is applied incorrectly it is sufficient to find the first such invalid state root, and include just Ls bytes of state that are affected by the transactions between the last state root (which was valid) and the current state root with the merkle proofs. Then any participant can validate the transactions in the segment and confirm that the chunk is invalid. Similarly, if the chunk producer attempted to include transactions that read and write more than Ls bytes of state, for the challenge it is enough to include the first Ls bytes it touches with the merkle proofs, which will be enough to apply the transactions and confirm that there’s a moment when an attempt to read or write content beyond Ls bytes is made.
3.7.2 Fishermen and fast cross-shard transactions As discussed in section 2.3, once we assume that the shard chunks (or shard blocks in the model with shard chains) can be invalid and introduce a challenge period, it negatively affects the finality, and thus cross-shard communication. In particular, the destination shard of any cross-shard transction cannot be certain the originating shard chunk or block is final until the challenge period is over (see figure 21). Figure 21: Waiting for the challenge period before applying a receipt The way to address it in a way that makes the cross-shard transactions instantenious is for the destination shard to not wait for the challenge period after the source shard transaction is published, and apply the receipt transaction immediately, but then roll back the destination shard together with the source shard if later the originating chunk or block was found to be invalid (see figure 22). This applies very naturally to the Nightshade design in which the shard chains are not independent, but instead the shard chunks are all published together in the same main chain block. If any chunk is found to be invalid, the entire block with that chunk is considered invalid, and all the blocks built on top of it. See figure 23. Both of the above approaches provide atomicity assuming that the challenge period is sufficiently long. We use the latter approach since providing fast crossshard transactions under normal circumstances outweights the inconvenience of the destination shard rolling back due to an invalid state transition in one of the source shards, which is an extremely rare event. 3.7.3 Hiding validators The existence of the challenges already significantly reduces the probability of adaptive corruption, since to finalize a chunk with an invalid state transition post
Figure 22: Applying receipts immediately and rolling back the destination chain if the source chain had an invalid block Figure 23: Fisherman challenge in Nightshade the challenge period the adaptive adversary needs to corrupt all the participants that maintain the state of the shard, including all the validators. Estimating the likelihood of such an event is extremely complex, since no sharded blockchain has been live sufficiently long for any such attack to be attempted. We argue that the probability, while extremely low, is still sufficiently large for a system that is expected to execute multi-million transactions and run a world-wide financial operations. There are two main reasons for this belief: 1. Most of the validators of the Proof-of-Stake chains and miners of the
Proof-of-Work chains are primarily incentivized by the financial upside. If an adaptive adversary offers them more money then the expected return from operating honestly, it is reasonable to expect that many validators will accept the offer. 2. Many entities do validation of Proof-of-Stake chains professionally, and it is expected that a large percentage of the stake in any chain will be from such entities. The number of such entities is sufficiently small for an adaptive adversary to get to know most of them personally and have a good understanding of their inclanation to be corrupted. We take one step further in reducing the probability of the adaptive corruption by hiding which validators are assigned to which shard. The idea is remotely similar to the way Algorand [5] conceals validators. It is critical to note that even if the validators are concealed, as in Algorand or as described below, the adaptive corruption is still in theory possible. While the adaptive adversary doesn’t know the participants that will create or validate a block or a chunk, the participants themselves do know that they will perform such a task and have a cryptographic proof of it. Thus, the adversary can broadcast their intent to corrupt, and pay to any participant that will provide such a cryptographic proof. We note however, that since the adversary doesn’t know the validators that are assigned to the shard they want to corrupt, they have no other choice but to broadcast their intent to corrupt a particular shard to the entire community. At that point it is economically beneficial for any honest participant to spin up a full node that validates that shard, since there’s a high chance of an invalid block appearing in that shard, which is an opportunity to create a challenge and collect associated reward. To not reveal the validators that are assigned to a particular shard, we do the following (see figure 24): Using VRF to get the assignment. At the beginning of each epoch each validator uses a VRF to get a bitmask of the shards the validator is assigned to. The bitmask of each validator will have Sw bits (see section 3.3 for the definition of Sw). The validator then fetches the state of the corresponding shards, and during the epoch for each block received validates the chunks that correspond to the shards that the validator is assigned to. Sign on blocks instead of chunks. Since the shards assignment is concealed, the validator cannot sign on chunks. Instead it always signs on the entire block, thus not revealing what shards it validates. Specifically, when the validator receives a block and validates all the chunks, it either creates a message that attests that all the chunks in all the shards the validator is assigned to are valid (without indicating in any way what those shards are), or a message that contains a proof of an invalid state transition if any chunk is invalid. See the section 3.8 for the details on how such messages are aggregated, section 3.7.4 for the details on how to prevent validators from piggy-backing on messages from other validators, and section 3.7.5 for the details how to reward and punish validators should a successful invalid state transition challenge actually happen.
Figure 24: Concealing the validators in Nightshade 3.7.4 Commit-Reveal One of the common problems with validators is that a validator can skip downloading the state and actually validating the chunks and blocks, and instead observe the network, see what the other validators submit and repeat their messages. A validator that follows such a strategy doesn’t provide any extra security for the network, but collects rewards. A common solution for this problem is for each validator to provide a proof that they actually validated the block, for example by providing a unique trace of applying the state transition, but such proofs significantly increase the cost of validation. Figure 25: Commit-reveal
Instead we make the validators first commit to the validation result (either the message that attests to the validity of the chunks, or the proof of an invalid state transition), wait for a certain period, and only then reveal the actual validation result, as shown on figure 25. The commit period doesn’t intersect with the reveal period, and thus a lazy validator cannot copycat honest validators. Moreover, if a dishonest validator committed to a message that attests to the validity of the assigned chunks, and at least one chunk was invalid, once it is shown that the chunk is invalid the validator cannot avoid the slashing, since, as we show in section 3.7.5, the only way to not get slashed in such a situation is to present a message that contains a proof of the invalid state transition that matches the commit. 3.7.5 Handling challenges As discussed above, once a validator receives a block with an invalid chunk, they first prepare a proof of the invalid state transition (see section 3.7.1), then commit to such a proof (see 3.7.4), and after some period reveal the challenge. Once the revealed challenge is included in a block, the following happens: 1. All the state transitions that happened from the block containing the invalid chunk until the block in which the revealed challenge is included get nullyfied. The state before the block that includes the revealed challenge is considered to be the same as the state before the block that contained the invalid chunk. 2. Within a certain period of time each validator must reveal their bitmask of the shards they validate. Since the bitmask is created via a VRF, if they were assigned to the shard that had the invalid state transition, they cannot avoid revealing it. Any validator that fails to reveal the bitmask is assumed to be assigned to the shard. 3. Each validator that after such period is found to be assigned to the shard, that did commit to some validation result for the block containing the invalid chunk and that didn’t reveal the proof of invalid state transition that corresponds to their commit is slashed. 4. Each validator gets a new shards assignment, and a new epoch is scheduled to start after some time sufficient for all the validators to download the state, as shown on figure 26. Note that from the moment the validators reveal the shards they are assigned to until the new epoch starts the security of the system is reduced since the shards assignment is revealed. The participants of the network need to keep it in mind while using the network during such period. 3.8 Signature Aggregation For a system with hudreds of shards to operate securely, we want to have on the order of 10, 000 or more validators. As discussed in section 3.7, we want each
Figure 26: Handling the challenge validator to publish a commit to a certain message and a signature on average once per block. Even if the commit messages were the same, aggregating such a BLS-signature and validating it would have been prohibitively expensive. But naturally the commit and reveal messages are not the same across validators, and thus we need some way to aggregate such messages and the signatures in a way that allows for fast validation later. The specific approach we use is the following: Validators joining block producers. The block producers are known some time before the epoch starts, since they need some time to download the state before the epoch starts, and unlike the validators the block producers are not concealed. Each block producer has v validator slots. Validators submit off-chain proposals to the block producers to get included as one of their v validators. If a block producer wishes to include a validator, they submit a transaction that contains the initial off-chainrequest from the validator, and the block producer’s signature that makes the validator join the block producer. Note that the validators assigned to the block producers do not necessarily validate the same shards that the block producer produces chunks for. If a validator applied to join multiple block producers, only the transaction from the first block producer will succeed. Block producers collect commits. The block producer constantly collects the commit and reveal messages from the validators. Once a certain number of such messages are accumulated, the block producer computes a merkle tree of these messages, and sends to each validator the merkle root and the merkle path to their message. The validator validates the path and signs on the merkle root. The block producer then accumulates a BLS signature on the merkle root from the validators, and publishes only the merkle root and the accumulated signature. The block producer also signs on the validity of the multisignature using a cheap ECDSA signature. If the multisignature doesn’t match the merkle root submitted or the bitmask of the validators participating, it is a slashable behavior. When synchronizing the chain, a participant can choose to validate all the BLS signatures from the validators (which is extremely expensive since it involves aggregating validators public keys), or only
the ECDMA signatures from the block producers and rely on the fact that the block producer was not challenged and slashed. Using on-chain transactions and merkle proofs for challenges. It can be noted that there’s no value in revealing messages from validators if no invalid state transition was detected. Only the messages that contain the actual proofs of invalid state transition need to be revealed, and only for such messages it needs to be shown that they match the prior commit. The message needs to be revealed for two purposes: 1. To actually initiate the rollback of the chain to the moment before the invalid state transition (see section 3.7.5). 2. To prove that the validator didn’t attempt to attest to the validity of the invalid chunk. In either case we need to address two issues: 1. The actual commit was not included on chain, only the merkle root of the commit aggregated with other messages. The validator needs to use the merkle path provided by the block producer and their original commit to prove that they committed to the challenge. 2. It is possible that all the validators assigned to the shard with the invalid state transition happen to be assigned to corrupted block producers that are censoring them. To get around it we allow them to submit their reveals as a regular transaction on-chain and bypass the aggregation. The latter is only allowed for the proofs of invalid state transition, which are extremely rare, and thus should not result in spamming the blocks. The final issue that needs to be addressed is that the block producers can choose not to participate in messages aggregation or intentionally censor particular validators. We make it economically disadvantageous, by making the block producer reward proportional to the number of validators assigned to them. We also note that since the block producers between epochs largely intersect (since it’s always the top w participants with the highest stake), the validators can largely stick to working with the same block producers, and thus reduce the risk of getting assigned to a block producer that censored them in the past. 3.9 Snapshots Chain Since the blocks on the main chain are produced very frequently, downloading the full history might become expensive very quickly. Moreover, since every block contains a BLS signature of a large number of participants, just the aggregation of the public keys to check the signature might become prohibitively expensive as well. Finally, since in any foreseeable future Ethereum 1.0 will likely remain one of the most used blockchains, having a meaningful way to transfer assets from
Near to Ethereum is a requirement, and today verifying BLS signatures to ensure Near blocks validity on Ethereum’s side is not possible. Each block in the Nightshade main chain can optionally contain a Schnorr multisignature on the header of the last block that included such a Schnorr multisignature. We call such blocks snapshot blocks. The very first block of every epoch must be a snapshot block. While working on such a multisignature, the block producers must also accumulate the BLS signatures of the validators on the last snapshot block, and aggregate them the same way as described in section 3.8. Since the block producers set is constant throughout the epoch, validating only the first snapshot blocks in each epoch is sufficient assuming that at no point a large percentage of block producers and validators colluded and created a fork. The first block of the epoch must contain information sufficient to compute the block producers and validators for the epoch. We call the subchain of the main chain that only contains the snapshot blocks a snapshot chain. Creating a Schnorr multisignature is an interactive process, but since we only need to perform it infrequently, any, no matter how inefficient, process will suffice. The Schnorr multisignatures can be easily validated on Ethereum, thus providing crucial primitives for a secure way of performing cross-blockchain communication. To sync with the Near chain one only needs to download all the snapshot blocks and confirm that the Schnorr signatures are correct (optionally also verifying the individual BLS signatures of the validators), and then only syncing main chain blocks from the last snapshot block.
Nightshade
3.1 От цепочек осколков к чанкам осколков Модель шардинга с цепочками шардов и цепочкой маяков очень мощная, но имеет определенные сложности. В частности, необходимо выполнить правило выбора вилки. в каждой цепочке отдельно правило выбора форка в шардчейнах и маяке цепочка должна быть построена по-другому и протестирована отдельно. В Nightshade мы моделируем систему как единый blockchain, в котором каждый блок логически содержит все транзакции для всех шардов и изменяет целое состояние всех осколков. Однако физически ни один участник не загружает полное состояние или полный логический блок. Вместо этого каждый участник сети только поддерживает состояние, соответствующее шардам, для которых они проверяют транзакции, а список всех транзакций в блоке разбивается на физические куски, по одному куску на осколок. В идеальных условиях каждый блок содержит ровно один чанк на каждый шард. блок, что примерно соответствует модели с шардчейнами, в которых Цепочки осколков производят блоки с той же скоростью, что и цепочка маяков. Однако, из-за задержек в сети некоторые фрагменты могут отсутствовать, поэтому на практике каждый блок содержит один или ноль фрагментов на каждый сегмент. Подробную информацию о том, как производятся блоки. Рисунок 16: Модель с цепочками шардов слева и с одной цепочкой, имеющей блоки разделены на куски справа
3.2 Консенсус Сегодня в blockchains преобладают два подхода к консенсусу: самая длинная (или самая тяжелая) цепочка, в которой цепочка с наибольшим количеством работы или доли используемый для его построения, считается каноническим, а BFT, в котором для каждого блока несколько набор validator достигает консенсуса BFT. В предложенных недавно протоколах последний подход является более доминирующим. поскольку он обеспечивает немедленную завершенность, в то время как в самой длинной цепочке требуется больше блоков. будет построен поверх блока, чтобы обеспечить завершенность. Часто для значимого безопасность время, необходимое для построения достаточного количества блоков, берет на себя порядок часов. Использование консенсуса BFT для каждого блока также имеет недостатки, такие как: 1. BFT консенсус предполагает значительный объем общения. Пока последние достижения позволяют достичь консенсуса за линейное время по количеству участников (см., например, [4]), все равно заметные накладные расходы на блок; 2. Невозможно участие всех участников сети в BFT. консенсус для каждого блока, поэтому обычно только случайно выбранная подгруппа участников достигает консенсуса. В принципе, случайно выбранный набор может быть адаптивно повреждается, и теоретически может быть создан форк. Система либо необходимо смоделировать, чтобы быть готовым к такому событию, и, следовательно, по-прежнему иметь правило выбора вилки помимо консенсуса BFT или быть спроектировано так, чтобы закрывать вниз в таком случае. Стоит отметить, что некоторые конструкции, такие как Algorand [5], значительно снижают вероятность адаптивного повреждения. 3. Самое главное, система глохнет, если 1 3 или более из всех участников оффлайн. Таким образом, любой временный сбой в сети или ее раскол могут полностью остановить работу системы. В идеале система должна иметь возможность продолжать работать до тех пор, пока хотя бы половина участников онлайн (самый тяжелый протоколы на основе цепочки продолжают работать, даже если в сети менее половины участников, но желательность этого свойства более спорна внутри сообщества). Гибридная модель, в которой используется консенсус, является своего рода самым тяжелым цепочка, но некоторые блоки периодически дорабатываются с помощью гаджета окончательности BFT, сохраняя преимущества обеих моделей. Такие BFT гаджеты завершения Casper FFG [6] используется в Ethereum 2.0 8, Casper CBC (см. https://vitalik. ca/general/2018/12/05/cbc_casper.html) и ДЕДУШКА (см. https:// medium.com/polkadot-network/d08a24a021b5), используемый в Polkadot. Nightshade использует консенсус самой тяжелой цепи. В частности, когда блок производитель производит блок (см. раздел 3.3), он может собирать подписи от другие производители блоков и validator, подтверждающие предыдущий блок. См. раздел 3.8, где подробно описано, как агрегируется такое большое количество подписей. Вес 8. Также посмотрите сеанс с Джастином Дрейком, где представлен подробный обзор Casper. FFG и то, как он интегрирован с консенсусом по самой тяжелой цепи GHOST, здесь: https://www. youtube.com/watch?v=S262StTwkmoблока является тогда совокупной долей всех подписавших, чьи подписи включен в блок. Вес цепочки — это сумма весов блоков. Помимо консенсуса по самой тяжелой цепочке, мы используем гаджет окончательности, который использует аттестации для завершения блоков. Чтобы уменьшить сложность системы, мы используем гаджет окончательности, который никак не влияет на правило выбора вилки, и вместо этого только вводит дополнительные условия разрезания, например, когда блок завершено с помощью гаджета окончательности, форк невозможен, если не будет очень большого процента общая ставка сокращается. Casper CBC — такой гаджет окончательности, и мы в настоящее время модель с учетом Casper CBC. Мы также работаем над отдельным протоколом BFT под названием TxFlow. Во время при написании этого документа неясно, будет ли использоваться TxFlow вместо Casper ЦБК. Однако отметим, что выбор окончательного устройства во многом ортогонален остальной части конструкции. 3.3 Производство блоков В Nightshade есть две роли: производители блоков и validators. В любом точка, в которой система содержит w производителей блоков, w = 100 в наших моделях и wv validators, в нашей модели v = 100, wv = 10 000. Система Proof-of-Stake, это означает, что и производители блоков, и validator имеют некоторое количество внутренних валюта (именуемая «tokens») заблокирована на период времени, намного превышающий время, которое они тратят на выполнение своих обязанностей по построению и проверке цепочки. Как и во всех системах Proof of Stake, не все производители блоков и не все wv validator являются разными объектами, поскольку это невозможно обеспечить. Каждый однако производители блоков w и wv validator имеют отдельные ставка. Система содержит n шардов, в нашей модели n = 1000. Как упоминалось в раздел 3.1, в Nightshade нет цепочек сегментов, вместо этого все производители блоков и validator создают единый blockchain, который мы называем основная цепь. Состояние основной цепи разбито на n шардов, и каждый блок продюсер и validator в любой момент загрузили локально только часть состояние, которое соответствует некоторому подмножеству шардов, и только процесс и проверять транзакции, которые влияют на эти части состояния. Чтобы стать производителем блоков, участник сети блокирует какие-то крупные сумма tokens (ставка). Обслуживание сети осуществляется в эпохи, где эпоха – это период времени порядка дней. Участники с самыми большими ставками в начале определенной эпохи являются блоком продюсеры той эпохи. Каждый производитель блоков назначается шардам SW (скажем, sw = 40, что означает, что sww/n = 4 производителя блоков на шард). Блок продюсер загружает состояние шарда, которому он назначен, до начала эпохи запускается и на протяжении всей эпохи собирает транзакции, влияющие на этот шард, и применяет их к государству. Для каждого блока b в основной цепочке и для каждого шарда s существует один из назначил производителей блоков s, который отвечает за производство части b, связанной с к осколку. Часть b, связанная с шардом s, называется чанком и содержит список транзакций для шарда, которые будут включены в b, а также merkleкорень результирующего состояния. b в конечном итоге будет содержать только очень маленький заголовок чанк, а именно корень Меркла всех примененных транзакций (см. раздел 3.7.1 для получения точных деталей) и корень Меркле конечного состояния. В оставшейся части документа мы часто ссылаемся на производителя блоков. который отвечает за создание чанка в определенное время для определенного шарда в качестве производителя чанка. Производитель чанка всегда является одним из производителей блоков. Производители блоков и производители фрагментов вращают каждый блок в соответствии с по фиксированному графику. Производители блоков имеют заказ и неоднократно производят блоки в таком порядке. Например. если имеется 100 производителей блоков, первый блок производители отвечают за производство блоков 1, 101, 201 и т. д., второй — ответственный за производство 2, 102, 202 и т. д.). Поскольку производство кусков, в отличие от производства блоков, требует поддержания состояние, и для каждого шарда только производители блоков sww/n поддерживают состояние на каждый шард, соответственно, только те производители блоков sww/n вращаются для создания куски. Например. с константами, указанными выше, с четырьмя производителями блоков, назначенными каждый осколок, каждый производитель блоков будет создавать чанки каждые четыре блока. 3.4 Обеспечение доступности данных Чтобы обеспечить доступность данных, мы используем подход, аналогичный подходу Polkadot. описано в разделе 2.5.3. Как только производитель блоков создает чанк, он создает его версия со стирающим кодом с оптимальным (w, ⌊w/6 + 1⌋) блочным кодом кусок. Затем они отправляют один фрагмент фрагмента стирающего кода (мы называем такие фрагменты части фрагмента или только части) каждому производителю блока. Мы вычисляем дерево Меркла, которое содержит все части в виде листьев и заголовок каждого чанка содержит корень Меркла такого дерева. Детали отправляются на validator через сообщения onepart. Каждое такое сообщение содержит заголовок чанка, порядковый номер части и содержимое части. сообщение также содержит подпись производителя блока, создавшего чанк и путь Меркла, чтобы доказать, что часть соответствует заголовку и производится соответствующим производителем блоков. Как только производитель блоков получает блок основной цепи, он сначала проверяет, иметь одночастные сообщения для каждого фрагмента, включенного в блок. Если нет, то блок не обрабатывается до тех пор, пока не будут получены недостающие одночастные сообщения. Как только все одночастные сообщения получены, производитель блока извлекает оставшиеся части от одноранговых узлов и реконструирует фрагменты, для которых они хранятся государство. Производитель блока не обрабатывает блок основной цепи, если хотя бы один раз чанк, включенный в блок, у них нет соответствующего одночастного сообщения, или если хотя бы для одного шарда, для которого они поддерживают состояние, они не могут реконструировать весь кусок. Для того, чтобы конкретный чанк был доступен, достаточно, чтобы ⌊w/6⌋+1 блока продюсеры имеют свои роли и обслуживают их. Таким образом, до тех пор, пока количество злоумышленники не превышают ⌊w/3⌋нет цепочки, имеющей более половины блока производители, создающие его, могут иметь недоступные фрагменты.Рисунок 17: Каждый блок содержит один или ноль фрагментов на каждый сегмент, и каждый блок имеет стирающий код. Каждая часть фрагмента стирающего кода отправляется назначенному заблокировать производителя через специальное одночастное сообщение 3.4.1 Работа с ленивыми производителями блоков Если у производителя блока есть блок, для которого отсутствует одночастное сообщение, он может решить подписаться на него, потому что, если блок окажется в цепочке, он максимизирует вознаграждение для производителя блока. Риска для блока нет. производителя, так как впоследствии невозможно доказать, что у производителя блока не было одночастное сообщение. Чтобы решить эту проблему, мы заставляем каждого производителя чанка при создании чанка выберите цвет (красный или синий) для каждой части будущего закодированного фрагмента и сохраните битовая маска назначенного цвета в фрагменте перед его кодированием. Каждая часть сообщение затем содержит цвет, назначенный детали, и этот цвет используется, когда вычисление корня Меркле закодированных частей. Если производитель чанка отклоняется из протокола это легко доказывается, так как либо корень Меркле не будет соответствуют одночастным сообщениям или цветам одночастных сообщений, которые соответствующие корню Меркла, не будут соответствовать маске в чанк. Когда производитель блока подписывает блок, он включает битовую маску всех красные части они получили за чанки, включенные в блок. Публикация неправильная битовая маска — это поведение, допускающее косую черту. Если производитель блока не получил одночастное сообщение, у них нет возможности узнать цвет сообщения, и таким образом, они имеют 50% шанс быть порезанными, если попытаются вслепую подписать документ. блок. 3,5 Заявление о переходе состояния Производители чанка только выбирают, какие транзакции включать в чанк, но не применяйте переход состояния при создании фрагмента. Соответственно,
заголовок чанка содержит корень Меркла Меркелизованного состояния, как было раньше применяются транзакции в чане. Транзакции применяются только тогда, когда полный блок, включающий фрагмент, обрабатывается. Участник обрабатывает блок только в том случае, если 1. Предыдущий блок получен и обработан; 2. Для каждого фрагмента участник не поддерживает состояние, поскольку у него есть видел одночастное сообщение; 3. Для каждого фрагмента участник сохраняет состояние, поскольку у него есть полный кусок. После обработки блока для каждого шарда, по которому участник поддерживает состояние, они применяют транзакции и вычисляют новое состояние на момент применения транзакций, после чего они готовы производить чанки для следующего блока, если они назначены какому-либо шарду, поскольку у них есть Меркельский корень нового меркелизованного государства. 3.6 Межшардовые транзакции и квитанции Если транзакция должна затронуть более одного шарда, ее необходимо выполнить последовательно. выполняется в каждом шарде отдельно. Полная транзакция отправляется в первый шард затронуты, и как только транзакция будет включена в чанк такого шарда, и применяется после того, как чанк включен в блок, он генерирует так называемую квитанцию транзакция, которая направляется на следующий сегмент, в котором транзакция должна быть быть казнён. Если требуется больше шагов, выполнение транзакции поступления генерирует новую транзакцию получения и так далее. 3.6.1 Срок действия транзакции квитанции Желательно, чтобы транзакция получения применялась в блоке, который следует сразу за блоком, в котором она была сгенерирована. Операция прихода осуществляется только генерируется после того, как предыдущий блок был получен и применен производителями блоков которые поддерживают исходный шард, и должны быть известны к моменту создания чанк для следующего блока создается производителями блоков пункта назначения осколок. Таким образом, квитанция должна быть передана от исходного шарда к целевой осколок за короткий промежуток времени между этими двумя событиями. Пусть A — последний произведенный блок, содержащий транзакцию t, генерирующую квитанцию r. Пусть B будет следующим созданным блоком (т.е. блоком, в котором A является его предыдущий блок), который мы хотим содержать r. Пусть t будет в шарде a, а r будет в осколок б. Срок действия квитанции, также изображенной на рисунке 18, следующий: Изготовление и хранение чеков. Цена за конверсию производителя чанка для шарда a получает блок A, применяет транзакцию t и генерирует квитанцию r. цена за конверсию затем сохраняет все такие полученные квитанции в своем внутреннем постоянном хранилище, проиндексированном по идентификатору исходного шарда.Раздача квитанций. Как только cpa будет готов создать чанк для шард a для блока B, они извлекают все квитанции, сгенерированные применением транзакций из блока A для шарда a, и включают их в чанк для фрагмента a в блоке B. Как только такой фрагмент сгенерирован, cpa создает его код стирания version и все соответствующие одночастные сообщения. cpa знает, какие производители блоков поддерживают полное состояние тех или иных шардов. Для конкретного производителя блоков bp cpa включает поступления, возникшие в результате применения транзакций в блоке А. для шарда a, в котором есть любой из шардов, которые bp считает местом назначения в одночастном сообщении, когда раздавали чанк для шарда a в блоке B (см. рисунок 17, на котором показаны квитанции, включенные в одночастное сообщение). Получение квитанций. Помните, что участники (как производители блоков, так и validators) не обрабатывают блоки, пока не получат одночастные сообщения. для каждого фрагмента, включенного в блок. Таким образом, к тому моменту, когда какой-либо конкретный участник применит блок B, у него будут все одночастные сообщения, соответствующие куски в B, и, таким образом, у них есть все входящие квитанции, содержащие фрагменты участник сохраняет состояние в качестве пункта назначения. При применении переход состояния для конкретного шарда, участник применяет обе расписки которые они собрали для шарда в onepart сообщениях, а также все транзакции, включенные в сам чанк. Рисунок 18: Срок действия транзакции получения 3.6.2 Обработка слишком большого количества квитанций Возможно, что количество квитанций, нацеленных на конкретный шард в конкретный блок слишком велик для обработки. Например, рассмотрим рисунок 19, каждая транзакция в каждом сегменте генерирует квитанцию, предназначенную для сегмента 1. К следующему блоку количество квитанций, которые должен обработать шард 1, равно сопоставимо с нагрузкой, которую все шарды вместе обрабатывали при обработке предыдущий блок.
Рисунок 19: Если все квитанции нацелены на один и тот же сегмент, этот сегмент может не иметь способность их обрабатывать Чтобы решить эту проблему, мы используем технику, аналогичную той, которая использовалась в QuarkChain 9. В частности, для каждого шарда последний блок B и последний шард внутри него блок, из которого были применены поступления, фиксируется. Когда новый осколок созданы, квитанция применяется в порядке очереди от оставшихся осколков в B, а затем в блоках, следующих за B, пока новый чанк не заполнится. В норме обстоятельствах при сбалансированной нагрузке это вообще приведет ко всем поступлениям применяется (и, таким образом, последний осколок последнего блока будет записан для каждый фрагмент), но в периоды, когда нагрузка не сбалансирована и определенный шард получает непропорционально много квитанций, эта техника позволяет им обрабатываться с соблюдением ограничений на количество включенных транзакций. Обратите внимание, что если такая несбалансированная нагрузка сохраняется в течение длительного времени, задержка от создание квитанции до тех пор, пока приложение не сможет продолжать расти бесконечно. Один способ решить эту проблему — отменить любую транзакцию, которая создает квитанцию, нацеленную на осколок, задержка обработки которого превышает некоторую константу (например, одну эпоху). Рассмотрим рисунок 20. К блоку B шард 4 не может обработать все поступления, поэтому он обрабатывает только получение квитанций до сегмента 3 в блоке A, и записывает это. В блок C включены поступления до 5-го шарда в блоке B, и затем к блоку D шард догоняет его, обрабатывая все оставшиеся поступления в блок Б и все поступления из блока С. 3,7 Проверка кусков Чанк, созданный для конкретного шарда (или блок шарда, созданный для конкретной цепочки шардов в модели с цепочками шардов), может быть проверен только 9См. эпизод с доской с QuarkChain здесь: https://www.youtube.com/watch?. v=opEtG6NM4x4, в котором, среди прочего, обсуждается подход к межшардовым транзакциям. вещиРисунок 20: Задержка обработки чеков участники, поддерживающие государство. Это могут быть производители блоков, validators, или просто внешние свидетели, которые загрузили состояние и проверили осколок в где они хранят активы. В этом документе мы предполагаем, что большинство участников не могут хранить состояние для значительной части осколков. Однако стоит упомянуть, что существуют сегментированные blockchain, разработанные с учетом предположения, что большинство участников имеют возможность хранить состояние и проверять большую часть осколки, такие как QuarkChain. Поскольку только часть участников имеет состояние для проверки шарда куски, можно адаптивно испортить только тех участников, у которых есть состояние и применить недопустимый переход между состояниями. Было предложено несколько схем шардинга, в которых каждые несколько раз отбирались validators. дней, а в течение суток любой блок в цепочке шардов, имеющий более 2/3 подписей validators, присвоенных такому шарду, учитывается немедленно окончательный. При таком подходе адаптивному противнику достаточно испортить только 2n/3+1. validator в цепочке сегментов, чтобы применить недопустимый переход состояния, который, хотя это, вероятно, трудно осуществить, уровень безопасности не является достаточным для общественного blockchain. Как обсуждалось в разделе 2.3, общий подход заключается в том, чтобы предоставить определенное окно времени после создания блока для любого участника, у которого есть состояние (независимо от того, является ли он это производитель блока, validator или внешний наблюдатель), чтобы оспорить его достоверность. Таких участников называют Рыбаками. Чтобы рыбак мог оспорить недействительный блок, необходимо убедиться, что такой блок доступен для их. Доступность данных в Nightshade обсуждается в разделе 3.4. В Nightshade после создания блока фрагменты не проверялись кто угодно, кроме фактического производителя фрагментов. В частности, производитель блоков, который предположил, что блок, естественно, не имеет состояния большинства осколков, ине смог проверить фрагменты. Когда создается следующий блок, он содержит подтверждения (см. раздел 3.2) нескольких производителей блоков и validator, но поскольку большинство производителей блоков и validator не поддерживают состояние для большинства шардов блок всего с одним недействительным чанком соберет значительно больше половины аттестаций и продолжит находиться в самом тяжелом состоянии. цепь. Для решения этой проблемы мы разрешаем любому участнику, поддерживающему состояние осколок для отправки запроса в цепочке для любого недопустимого фрагмента, созданного в этом осколок. 3.7.1 Проблема государственной действительности Как только участник обнаруживает, что конкретный фрагмент недействителен, ему необходимо предоставить доказательство того, что этот фрагмент недействителен. Поскольку большинство участников сети не поддерживают состояние шарда, в котором находится недействительный чанк доказательство должно содержать достаточную информацию, чтобы подтвердить, что блок недействителен без наличия гос. Мы устанавливаем ограничение Ls на количество состояний (в байтах), которое может хранить одна транзакция. может кумулятивно читать или писать. Любая транзакция, которая касается более Ls состояние считается недействительным. Помните из раздела 3.5, что чанк в конкретном блоке B содержатся только транзакции, которые необходимо применить, но не новый корень государства. Корнем состояния, включенным в фрагмент блока B, является состояние root перед применением таких транзакций, но после применения транзакций из последний фрагмент того же шарда перед блоком B. Злоумышленник, который желает применить недопустимый переход состояния, будет включать неправильный корень состояния в блоке B, который не соответствует корню состояния, полученному в результате применения транзакции в предыдущем фрагменте. Мы расширяем информацию, которую производитель чанка включает в чанк. Вместо того, чтобы просто включать состояние после применения всех транзакций, вместо этого включает корень состояния после применения каждого непрерывного набора транзакций, которые коллективно читать и записывать Ls байтов состояния. Благодаря этой информации для рыбаку, чтобы создать проблему, что переход между состояниями применяется неправильно. достаточно найти первый такой недопустимый корень состояния и включить только Ls байтов состояния, на которые влияют транзакции между последним корнем состояния (который был действительный) и текущий корень состояния с доказательствами Меркла. Тогда любой участник может проверить транзакции в сегменте и подтвердить, что чанк недействителен. Аналогично, если производитель чанка попытается включить транзакции, которые читают и записать более Ls байт состояния, для вызова достаточно включить первые Ls байтов, которых он касается с помощью доказательств Меркла, которых будет достаточно, чтобы применить транзакции и убедиться, что наступает момент, когда попытка производится чтение или запись содержимого за пределами Ls байт.
3.7.2 Рыбаки и быстрые транзакции между шардами Как обсуждалось в разделе 2.3, если мы предположим, что фрагменты шарда (или шард блоки в модели с цепочками осколков) могут быть недействительными и создавать проблемы период, это отрицательно влияет на завершенность и, следовательно, на межсегментную коммуникацию. В в частности, не может быть определен целевой сегмент любой межсегментной транзакции. исходный фрагмент или блок является окончательным до тех пор, пока период вызова не закончится (см. рисунок 21). Рисунок 21: Ожидание периода вызова перед применением квитанции Способ решения этой проблемы таким образом, чтобы транзакции между сегментами Instantenious означает, что осколок назначения не должен ждать периода вызова. после публикации транзакции исходного сегмента и примените транзакцию получения немедленно, но затем откатите целевой сегмент вместе с исходным шард, если позже исходный чанк или блок оказался недействительным (см. рис. 22). Это очень естественно относится к дизайну Nightshade, в котором осколок цепочки не являются независимыми, вместо этого все фрагменты шардов публикуются. вместе в одном блоке основной цепи. Если какой-либо фрагмент окажется недействительным, весь блок с этим чанком считается недействительным, а все блоки, построенные на самое верхнее. См. рисунок 23. Оба вышеупомянутых подхода обеспечивают атомарность, предполагая, что задача период достаточно длительный. Мы используем последний подход, поскольку обеспечение быстрых перекрестных транзакций в обычных обстоятельствах перевешивает неудобства целевой сегмент откатывается из-за недопустимого перехода состояния в одном из исходные осколки, что является крайне редким событием. 3.7.3 Скрытие validators Наличие проблем уже существенно снижает вероятность адаптивное повреждение, поскольку для завершения фрагмента с недопустимым постом перехода состоянияРисунок 22: Немедленное применение квитанций и откат пункта назначения цепочка, если в исходной цепочке был недопустимый блок Рисунок 23: Испытание рыбака в Nightshade период испытания, который необходим адаптивному противнику, чтобы развратить всех участников которые поддерживают состояние шарда, включая все validator. Оценить вероятность такого события чрезвычайно сложно, поскольку нет sharded blockchain существует достаточно долго, чтобы можно было предпринять попытку такой атаки. Мы утверждаем, что вероятность, хотя и чрезвычайно мала, все же достаточно велика. большой для системы, которая, как ожидается, будет выполнять многомиллионные транзакции и управлять финансовыми операциями по всему миру. Есть две основные причины такого убеждения: 1. Большинство validator цепей Proof-of-Stake и майнеров
Цепочки Proof-of-Work в первую очередь стимулируются финансовым потенциалом. Если адаптивный противник предлагает им больше денег, чем ожидаемая прибыль от честной работы, разумно ожидать, что многие validators примет предложение. 2. Многие организации профессионально проводят проверку цепочек Proof-of-Stake, и ожидается, что большой процент акций в любой цепочке будет от таких субъектов. Число таких объектов достаточно мало для адаптивного противника, чтобы узнать большинство из них лично и получить хорошее понимание своей склонности к развращению. Мы делаем еще один шаг вперед в снижении вероятности адаптивного повреждения, скрывая, какие validator назначены какому шарду. Идея в том, отдаленно похоже на то, как Algorand [5] скрывает validators. Очень важно отметить, что даже если validator скрыты, как в Algorand, или, как описано ниже, адаптивное повреждение теоретически все еще возможно. Пока адаптивный противник не знает участников, которые будут создавать или проверять блок или чанк, участники сами знают, что будут выполнять такую задачу и иметь криптографическое доказательство этого. Таким образом, противник может сообщать о своем намерении совершить коррупцию и платить любому участнику, который предоставит такое криптографическое доказательство. Однако отметим, что, поскольку противник не знать validator, которые назначены на шард, который они хотят повредить, они не имеют другого выбора, кроме как передать свое намерение испортить конкретный осколок все сообщество. В этот момент это экономически выгодно для любого честного участнику развернуть полный узел, который проверяет этот шард, поскольку существует высокая вероятность появления недействительного блока в этом осколке, что дает возможность создайте испытание и получите соответствующую награду. Чтобы не раскрывать validator, назначенные конкретному шарду, мы делаем следующее (см. рисунок 24): Использование VRF для получения задания. В начале каждой эпохи каждый validator использует VRF для получения битовой маски сегментов, которым назначен validator. Битовая маска каждого validator будет иметь биты Sw (определение см. в разделе 3.3). Sw). Затем validator извлекает состояние соответствующих фрагментов и в течение эпохи для каждого полученного блока проверяет соответствующие фрагменты к шардам, которым назначен validator. Подписывайтесь на блоки, а не на куски. Поскольку назначение сегментов скрыто, validator не может подписывать фрагменты. Вместо этого он всегда подписывает всю блокировать, таким образом не раскрывая, какие шарды он проверяет. В частности, когда validator получает блок и проверяет все фрагменты, он либо создает сообщение это свидетельствует о том, что все чанки во всех шардах, которым назначен validator, являются действительным (без указания каким-либо образом, что это за осколки), или сообщение, которое содержит доказательство недопустимого перехода состояния, если какой-либо фрагмент недействителен. См. раздел 3.8 содержит подробную информацию о том, как агрегируются такие сообщения, раздел 3.7.4 — подробности о том, как предотвратить использование validators в сообщениях от другие validator и раздел 3.7.5, где подробно описано, как вознаграждать и наказывать. validators, если действительно произойдет успешный вызов недопустимого перехода состояния.Рисунок 24: Сокрытие validator в Nightshade 3.7.4 Фиксация-Раскрытие Одна из распространенных проблем с validator заключается в том, что validator может пропустить загрузку состояния и фактическую проверку фрагментов и блоков, а вместо этого понаблюдайте за сетью, посмотрите, что отправляют другие validator, и повторите свои сообщения. validator, следующий такой стратегии, не дает никаких дополнительных безопасность сети, но получает вознаграждение. Обычное решение этой проблемы состоит в том, чтобы каждый validator предоставил доказательство. что они действительно проверили блок, например, предоставив уникальную трассировку применения перехода состояний, но такие доказательства значительно увеличивают стоимость проверки. Рисунок 25: Фиксация-раскрытие
Вместо этого мы сначала делаем validator фиксацией результата проверки (либо сообщение, подтверждающее достоверность фрагментов или доказательство недействительности перехода состояния), подождите определенный период и только потом покажите фактический результат проверки, как показано на рисунке 25. Период фиксации не пересекается с период раскрытия, и поэтому ленивый validator не может подражать честным validator. Более того, если нечестный validator передал сообщение, подтверждающее достоверность назначенных фрагментов, и по крайней мере один фрагмент был недействителен, как только он будет показано, что чанк недействителен, validator не может избежать косой черты, поскольку как мы покажем в разделе 3.7.5, единственный способ не порезаться в такой ситуации состоит в том, чтобы представить сообщение, содержащее доказательство недопустимого перехода состояния, которое соответствует коммиту. 3.7.5 Решение проблем Как обсуждалось выше, как только validator получает блок с недопустимым чанком, сначала они готовят доказательство недопустимого перехода состояний (см. раздел 3.7.1), затем возьмите на себя такое доказательство (см. 3.7.4) и через некоторое время раскройте проблему. После включения выявленного вызова в блок происходит следующее: 1. Все переходы состояний, произошедшие из блока, содержащего недействительный фрагмент до тех пор, пока не будет получен блок, в который включен обнаруженный вызов. аннулировано. Состояние перед блоком, включающим обнаруженную задачу считается таким же, как состояние до блока, который содержал недействительный фрагмент. 2. В течение определенного периода времени каждый validator должен раскрыть свою битовую маску. осколков, которые они проверяют. Поскольку битовая маска создается через VRF, если они были назначены шарду с недопустимым переходом состояния, они не могу не раскрыть этого. Любой validator, который не раскрывает битовую маску. предполагается, что он назначен сегменту. 3. Каждый validator, который по истечении этого периода оказывается назначенным сегменту, который действительно зафиксировал некоторый результат проверки для блока, содержащего неверный фрагмент, и это не выявило доказательства недопустимого перехода состояния это соответствует их коммиту. 4. Каждый validator получает новое назначение осколков, и назначается новая эпоха. начать через некоторое время, достаточное для того, чтобы все validators загрузили состояние, как показано на рисунке 26. Обратите внимание, что с того момента, как validator раскрывают назначенные им шарды до тех пор, пока не начнется новая эпоха, безопасность системы снижается, поскольку Назначение осколков раскрыто. Участникам сети необходимо его сохранить иметь в виду при использовании сети в течение такого периода. 3,8 Агрегация подписей Чтобы система с сотнями шардов работала безопасно, мы хотим иметь порядка 10 000 или более validators. Как обсуждалось в разделе 3.7, мы хотим, чтобы каждыйРисунок 26: Решение проблемы validator для публикации коммита к определенному сообщению и подписи в среднем один раз за блок. Даже если сообщения о фиксации были одинаковыми, объединение таких BLS-подпись и ее проверка были бы непомерно дорогими. Но естественно, сообщения фиксации и раскрытия не одинаковы для validator, и поэтому нам нужен какой-то способ агрегировать такие сообщения и подписи в способ, позволяющий провести быструю проверку позже. Конкретный подход, который мы используем, заключается в следующем: Валидаторы присоединяются к производителям блоков. Известны производители блоков за некоторое время до начала эпохи, так как им нужно некоторое время, чтобы загрузить состояние до начала эпохи, и в отличие от validators производители блоков не скрыто. Каждый производитель блоков имеет v validator слотов. Валидаторы отправляют оффчейн предложения производителям блоков, чтобы они были включены в качестве одного из их v validatorс. Если производитель блока желает включить validator, он отправляет транзакция, которая содержит первоначальный запрос вне цепочки от validator и подпись производителя блока, которая заставляет validator присоединиться к производителю блока. Обратите внимание, что validator, назначенные производителям блоков, не обязательно проверять те же фрагменты, для которых производитель блоков создает фрагменты. Если validator применяется для объединения нескольких производителей блоков, только транзакция из первый производитель блоков добьется успеха. Производители блоков собирают коммиты. Производитель блоков постоянно собирает сообщения о фиксации и раскрытии от validator. Как только накапливается определенное количество таких сообщений, производитель блока вычисляет коэффициент Меркла. дерево этих сообщений и отправляет каждому validator корень Меркла и merkle путь к их сообщению. validator проверяет путь и регистрируется. корень Меркеля. Затем производитель блока накапливает подпись BLS на корень Меркла из validators и публикует только корень Меркла и накопленная подпись. Производитель блока также подписывает действительность мультиподпись с использованием дешевой подписи ECDSA. Если мультиподпись не соответствует отправленному корню Меркла или битовой маске участвующих validator, это поведение, допускающее косую черту. При синхронизации цепочки участник может выбрать проверку всех подписей BLS из validator (что чрезвычайно дорого, поскольку включает в себя агрегирование открытых ключей validator) или толькоподписи ECDMA от производителей блоков и полагаются на тот факт, что Продюсер блока не подвергся сомнению и не был порезан. Использование внутрисетевых транзакций и доказательств Меркла для решения проблем. Это можно отметить, что нет смысла раскрывать сообщения от validators, если нет Обнаружен недопустимый переход состояния. Только те сообщения, которые содержат реальные доказательства недопустимого перехода состояния должны быть выявлены, и только для таких сообщений необходимо показать, что они соответствуют предыдущему коммиту. Сообщение должно раскрываться с двумя целями: 1. Фактически инициировать откат цепочки к моменту перед недопустимый переход состояния (см. раздел 3.7.5). 2. Чтобы доказать, что validator не пытался подтвердить действительность недействительный фрагмент. В любом случае нам необходимо решить две проблемы: 1. Фактический коммит не был включен в цепочку, только корень Меркла commit в совокупности с другими сообщениями. validator необходимо использовать путь Меркла, предоставленный производителем блока, и их первоначальная фиксация доказать, что они приняли вызов. 2. Возможно, что все validator, назначенные шарду с невалидным переход состояния назначается поврежденным производителям блоков, которые подвергают их цензуре. Чтобы обойти это, мы позволяем им отправлять свои откровения. как обычная транзакция в цепочке и в обход агрегации. Последнее допускается только для доказательств недопустимого перехода состояния, которые крайне редко и, следовательно, не должно приводить к спаму блоков. Последний вопрос, который необходимо решить, заключается в том, что производители блоков могут отказаться от участия в агрегировании сообщений или намеренно подвергать цензуре отдельные validator. Мы делаем это экономически невыгодным, делая блок вознаграждение производителя, пропорциональное количеству назначенных ему validators. Мы также обратите внимание, что поскольку производители блоков между эпохами во многом пересекаются (поскольку это всегда лучшие участники с самой высокой ставкой), validators могут в основном придерживаться работы с одними и теми же производителями блоков и тем самым снизить риск о том, что их назначили производителю блоков, который подвергал их цензуре в прошлом. 3,9 Цепочка снимков Поскольку блоки в основной цепочке производятся очень часто, загрузка полная история может очень быстро стать дорогой. Более того, поскольку каждый блок содержит BLS-подпись большого количества участников, просто агрегирование открытых ключей для проверки подписи может стать непомерно высоким к тому же дорого. Наконец, поскольку в обозримом будущем Ethereum 1.0, скорее всего, так и останется из наиболее часто используемых blockchain, имеющих смысловой способ передачи активов из
Требуется близко к Ethereum, и сегодня проверка подписей BLS для обеспечения Действие ближних блоков на стороне Ethereum невозможно. Каждый блок в основной цепочке Nightshade может опционально содержать блок Шнорра. мультиподпись в заголовке последнего блока, в котором был такой Шнорр мультиподпись. Мы называем такие блоки блоками моментальных снимков. Самый первый блок каждая эпоха должна быть блоком моментального снимка. Работая над такой мультиподписью, производители блоков также должны накопить подписи BLS validator. в последнем блоке моментальных снимков и агрегируем их так же, как описано в разделе раздел 3.8. Поскольку набор производителей блоков постоянен на протяжении всей эпохи, проверка достаточно только первых блоков снимков в каждой эпохе, предполагая, что ни в одном случае указывает на то, что большой процент производителей блоков и validators вступили в сговор и создали вилка. Первый блок эпохи должен содержать информацию, достаточную для вычисления производители блоков и validators для эпохи. Мы вызываем подцепь основной цепочки, которая содержит только снимок. блокирует цепочку снимков. Создание мультиподписи Шнорра — интерактивный процесс, но поскольку мы только нужно выполнять его нечасто, любой, даже самый неэффективный процесс будет достаточно. Мультиподписи Шнорра можно легко проверить на Ethereum, тем самым предоставляя важные примитивы для безопасного выполнения перекрестного blockchain общение. Для синхронизации с цепочкой Near достаточно скачать весь снимок блоков и подтвердите правильность подписей Шнорра (при необходимости также проверьте отдельные подписи BLS validator), а затем только синхронизируйте блоки основной цепочки из последнего блока моментального снимка.
Conclusion
Conclusion
In this document we discussed approaches to building sharded blockchains and covered two major challenges with existing approaches, namely state validity and data availability. We then presented Nightshade, a sharding design that powers NEAR Protocol. The design is work in progress, if you have comments, questions or feedback on this document, please go to https://near.chat.
Заключение
В этом документе мы обсудили подходы к созданию сегментированных blockchain и охватили две основные проблемы существующих подходов, а именно валидность состояния и доступность данных. Затем мы представили Nightshade, дизайн шардинга, который полномочия NEAR Протокола. Дизайн находится в стадии разработки, если у вас есть комментарии, вопросы или отзывы. в этом документе перейдите по адресу https://near.chat.