状态有效性和数据可用性
分片 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 为我们提供了一些块，天真的解决方案假设 该块是有效的，并且它是建立在 validator 所认为的基础上的 当他们开始验证时该分片的规范链。 validators 从前一组 validator 中学习了规范链，它们由相同的 假设建立在作为规范链头部的区块之上 在那之前。通过归纳，整个链都是有效的，并且因为没有 validator 集合 在任何产生分叉的点，简单的解决方案也可以确定当前 chain 是分片中唯一的链。可视化见图 6。
图6： 每个区块都通过 BFT 共识最终确定的 blockchain 如果我们假设 validators 可以是 自适应地损坏，这不是一个不合理的假设6。适应性地 损坏具有 1000 个分片的系统中的单个分片的成本要低得多 而不是破坏整个系统。因此，协议的安全性随着分片数量的增加而线性下降。确定其有效性 一个区块，我们必须知道，在历史上的任何时刻，系统中都没有分片 大多数 validator 串通一气；有了适应性强的对手，我们不再有 这样的确定性。正如我们在 1.5 节中讨论的，串通 validators 可以行使 两种基本的恶意行为：创建分叉和产生无效区块。 恶意分叉可以通过与信标链交叉链接的区块来解决，信标链通常被设计为具有比信标链更高的安全性 分片链。 然而，产生无效块是一个更严重的问题。 具有挑战性的问题需要解决。 2.2 状态有效性 考虑图 7，其中 Shard #1 已损坏并且恶意行为者产生了 无效区块 B。假设在该区块 B 中，有 1000 个 token 被铸造出来 爱丽丝账户上的空气。然后，恶意行为者会生成有效的区块 C（在 感觉 C 中的交易被正确应用）在 B 之上，混淆 无效块 B，并向分片 #2 发起跨分片交易 将这 1000 个 token 转入 Bob 的帐户。从这一刻起，不当行为 创建的 token 驻留在分片 #2 中完全有效的 blockchain 上。 解决这个问题的一些简单方法是： 6阅读 这个 文章 为了 详情 上 如何 适应性 腐败 可以 是 携带 输出： https://medium.com/nearprotocol/d859adb464c8. 对于 更多 详情 上 适应性 腐败， 读 https://github.com/ethereum/wiki/wiki/Sharding-FAQ# 我们正在使用什么安全模型图7： 来自具有无效块的链的跨分片交易 1. 对于分片 #2 的 validators 来验证交易所在的块 已启动。即使在上面的例子中这也不起作用，因为块 C 似乎是完全有效的。 2. 对于分片 #2 中的 validators，验证发起交易的区块之前的大量区块。自然地，对于 由接收分片验证的任意数量的块 N 恶意 validators 可以在无效块之上创建 N+1 个有效块 产生的。 解决这个问题的一个有前途的想法是将分片排列成 无向图，其中每个分片都连接到其他几个分片，以及 只允许相邻分片之间的跨分片交易（例如，这就是 Vlad Zamfir 的分片本质上是有效的7，Kadena 的分片也使用了类似的想法 Chainweb [1])。如果分片之间需要跨分片交易 不是邻居，此类事务通过多个分片路由。在这个设计中 每个分片中的 validator 预计会验证其分片中的所有块 以及所有相邻分片中的所有块。考虑下图 有 10 个分片，每个分片有 4 个邻居，并且没有两个分片需要更多 跨分片通信的跳数少于图 8 所示。 分片 #2 不仅验证其自己的 blockchain，还验证 blockchain 所有邻居，包括 1 号分片。因此，如果 Shard #1 上有恶意行为者 试图创建一个无效的块 B，然后在其上构建块 C 并发起跨分片交易，这样的跨分片交易不会走 自从分片 #2 将验证分片 #1 的整个历史以来， 会导致它识别无效的块B。 7在此处阅读有关设计的更多信息：https://medium.com/nearprotocol/37e538177ed9
图8： 类链网系统中无效的跨分片交易将 被发现 虽然破坏单个分片不再是一种可行的攻击，但破坏一个分片 碎片很少仍然是一个问题。在图 9 中，对手破坏了两个分片
1 和分片 #2 成功执行到分片 #3 的跨分片交易
来自无效区块 B 的资金： 图9： 类链网系统中无效的跨分片交易将 不被检测到 分片 #3 验证分片 #2 中的所有块，但不验证分片 #1 中的所有块，并且 无法检测恶意块。 妥善解决状态有效性有两个主要方向：
和计算的密码证明。 2.3 渔夫 第一种方法背后的想法如下：每当块头 出于任何目的（例如交叉链接到 信标链，或跨分片交易），有一段时间 任何诚实的 validator 都可以提供该块无效的证据。那里 是各种结构，可以非常简洁地证明这些块是 无效，因此接收节点的通信开销要小得多 比收到一个完整的块。 只要存在至少一个诚实的 validator ，就可以使用这种方法 分片，系统是安全的。 图10： 渔夫 这是当今提议的协议中的主要方法（除了假装问题不存在之外）。 然而，这种方法有两个 主要缺点： 1. 对于诚实的validator来说，挑战期需要足够长 识别一个块已生成，下载它，完全验证它，并准备 如果块无效则提出挑战。 引入这样一个时期将 显着减慢跨分片交易的速度。 2. 挑战协议的存在创造了新的攻击向量 当恶意节点发送带有无效挑战的垃圾邮件时。一个显而易见的解决方案 解决这个问题的方法是让挑战者存入一定数量的 token 如果挑战有效则返回。这只是部分解决方案，因为它 对于对手向系统发送垃圾邮件（并烧毁 存款）进行无效挑战，例如阻止有效的挑战来自诚实的 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 语言将无法使用 SNARKs 证明链的有效性。 2.5 数据可用性 我们要讨论的第二个问题是数据可用性。一般节点 操作特定的 blockchain 分为两组：完整节点， 那些下载每个完整区块并验证每笔交易的人，以及 Light 节点，仅下载区块头并使用 Merkle 证明作为部分的节点 他们感兴趣的状态和交易，如图 11 所示。
图11： 默克尔树 现在，如果大多数全节点串通，他们可以生成一个区块，有效或 无效，并将其 hash 发送到轻节点，但绝不泄露完整内容 块的。他们可以通过多种方式从中受益。例如， 考虑图 12： 图 12： 数据可用性问题 共有三个区块：前一个 A，是由诚实的 validators 产生的； 当前 B 有 validator 串通；下一个C也将被生产 由诚实的 validators 提供（blockchain 位于右下角）。 你是一个商人。当前块（B）接收块的validators 来自之前的 validator 的 A，计算出您收到资金的区块，并向您发送了该区块的标头，其中包含状态的 Merkle 证明 你有钱（或者发送这笔钱的有效交易的 Merkle 证明） 给你）。确认交易完成后，您即可提供服务。 然而，validators 永远不会将块 B 的全部内容分发给 任何人。因此，块 C 的诚实 validators 无法检索该块，并且 要么被迫停止系统，要么在 A 之上构建，剥夺你作为 金钱商人。 当我们将相同的场景应用于分片时，完整和分片的定义 轻节点通常适用于每个分片：每个分片中的 validators 每下载一次 阻止该分片并验证该分片中的每笔交易，但其他 系统中的节点，包括那些将分片链状态快照到 信标链，仅下载标头。因此分片中的 validator 是 该分片的有效完整节点，而系统中的其他参与者， 包括信标链，作为轻节点运行。 为了使我们上面讨论的渔夫方法发挥作用，诚实的validators 需要能够下载与信标链交叉链接的块。 如果恶意 validators 交叉链接无效块的标头（或使用它来 发起跨分片交易），但从未分发过区块，诚实的人 validators 无法制定挑战。 我们将介绍解决这个问题的三种方法，这些方法相互补充 彼此。 2.5.1 监护权证明 最迫切需要解决的问题是区块一次是否可用 它被出版了。 一个提议的想法是让所谓的公证人进行轮换 分片之间比 validators 更频繁，其唯一的工作就是下载 阻止并证明他们能够下载它。他们可以是 轮换更频繁，因为他们不需要下载整个状态 分片的，与 validator 不同，后者不能频繁轮换，因为它们 每次旋转时都必须下载分片的状态，如图所示 13. 这种幼稚方法的问题是无法在以后证明 公证人是否能够下载该块，因此公证人 可以选择始终证明他们能够下载该块而无需 甚至试图找回它。解决此问题的一种方法是公证人提供 一些证据或抵押一定数量的 token 来证明该区块是 下载了。这里讨论了一种这样的解决方案：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 中继链。特定中继链 validator 只会在中继链上签名 块，如果它们对每个被快照的平行链块都有自己的部分 这样的中继链区块。因此，如果中继链区块具有来自 2f + 1 的签名 validators，只要不超过 f 个违反协议，每个 平行链区块可以通过从 validators 中获取部分来重建 遵循协议。见图 15。 图 15： Polkadot 的数据可用性 2.5.4 长期数据可用性 请注意，上面讨论的所有方法仅证明了以下事实：块 已全部发布，并且现已可用。块稍后可能会变得不可用 由于多种原因：节点离线、节点故意删除历史记录 数据等。 值得一提的解决此问题的白皮书是 Polyshard [3]， 它使用纠删码来使块可以跨分片使用，即使多个分片 分片完全丢失数据。不幸的是，他们的具体方法需要 所有分片从所有其他分片下载块，这是令人望而却步的 昂贵。 长期可用性并不是一个紧迫的问题：因为没有参与者 系统中预计能够验证所有链中的所有链
分片，分片协议的安全性需要这样设计 即使某些分片中的某些旧块变得如此，系统也是安全的 完全不可用。
상태 유효성 및 데이터 가용성
샤딩된 blockchains의 핵심 아이디어는 대부분의 참가자가 네트워크를 사용하면 모든 샤드의 블록을 확인할 수 없습니다. 이처럼, 언제든지 모든 참가자는 일반적으로 사용할 수 없는 특정 샤드와 상호 작용해야 합니다. 샤드의 전체 기록을 다운로드하고 검증합니다. 그러나 샤딩의 파티셔닝 측면은 상당한 잠재력을 불러일으킵니다. 문제: 특정 기록의 전체 기록을 다운로드하고 검증하지 않고 샤드 참가자는 반드시 상태가 무엇인지 확신할 수 없습니다. 5하위 섹션 2.5.3을 제외하고 이 섹션은 이전에 https://near.ai/에 게시되었습니다. 샤드2. 이전에 읽으셨다면 다음 섹션으로 건너뛰세요.
그들이 상호 작용하는 것은 유효한 블록 시퀀스의 결과이며 그러한 시퀀스는 of block은 실제로 샤드의 정식 체인입니다. 그렇지 않은 문제 샤딩되지 않은 blockchain에 존재합니다. 먼저 제안된 이 문제에 대한 간단한 해결책을 제시하겠습니다. 여러 프로토콜을 사용하여 이 솔루션이 어떻게 중단될 수 있는지 분석하고 이를 해결하기 위한 시도가 이루어졌습니다. 2.1 검증인 교체 상태 타당성에 대한 순진한 해결책은 그림 5에 나와 있습니다. 전체 시스템에는 수천 개의 validator이 있으며 그 중 20% 이하가 악의적이거나 다른 방식으로 실패합니다(예: 온라인으로 블록을 생성합니다). 그런 다음 200개의 validator을 샘플링하면 확률은 1개 이상의 실용적인 목적으로 3개의 실패는 0으로 가정될 수 있습니다. 그림 5: 샘플링 validators 1 3은 중요한 기준점이다. 합의 프로토콜 계열이 있습니다. BFT 합의 프로토콜은 1보다 적은 기간 동안 이를 보장합니다. 3개 참가자가 충돌하거나 규정을 위반하는 방식으로 행동하여 실패합니다. 프로토콜을 통해 합의에 도달할 것입니다. 정직한 validator 백분율을 가정하여 현재 세트가 샤드의 validators는 우리에게 일부 블록을 제공하며 순진한 솔루션은 가정합니다. 블록이 유효하고 validators가 믿었던 것을 기반으로 구축되었습니다. 검증을 시작할 때 해당 샤드에 대한 정식 체인입니다. validators 이전 validator 세트에서 표준 체인을 배웠습니다. 캐노니컬 체인의 선두인 블록 위에 구축된 가정 그 전에. 유도에 의해 전체 체인이 유효하며 validators 세트가 없기 때문에 어느 시점에서든 포크가 생성되면 순진한 솔루션은 현재의 체인은 샤드의 유일한 체인입니다. 시각화는 그림 6을 참조하세요.
그림 6: BFT 합의를 통해 확정된 각 블록의 blockchain validators가 다음과 같을 수 있다고 가정하면 이 간단한 솔루션은 작동하지 않습니다. 이는 적응적으로 손상되었으며 이는 불합리한 가정이 아닙니다6. 적응적으로 1000개의 샤드가 있는 시스템에서 단일 샤드를 손상시키는 것이 훨씬 저렴합니다. 전체 시스템을 손상시키는 것보다. 따라서 프로토콜의 보안은 샤드 수에 따라 선형적으로 감소합니다. 타당성에 대한 확신을 갖기 위해 블록을 생성하려면 역사상 어느 시점에서든 시스템의 샤드가 없음을 알아야 합니다. validator의 대다수가 공모하고 있습니다. 적응형 적과 함께라면 우리는 더 이상 그런 확신. 섹션 1.5에서 논의한 것처럼 validators의 공모는 행사할 수 있습니다. 두 가지 기본적인 악의적 행동: 포크 생성 및 유효하지 않은 블록 생성. 악의적인 포크는 일반적으로 기존보다 훨씬 더 높은 보안을 갖도록 설계된 비콘 체인에 블록을 교차 연결하여 처리할 수 있습니다. 샤드 체인. 그러나 유효하지 않은 블록을 생성하는 것은 훨씬 더 많은 것입니다. 해결해야 할 어려운 문제. 2.2 상태 유효성 샤드 #1이 손상되고 악의적인 행위자가 생성하는 그림 7을 생각해 보세요. 유효하지 않은 블록 B. 이 블록 B에서 1000 tokens가 씬에서 생성되었다고 가정합니다. 앨리스 계정으로 방송됩니다. 그런 다음 악의적인 행위자는 유효한 블록 C를 생성합니다( C의 트랜잭션이 올바르게 적용되었음을 감지) B 위에서 난독화 유효하지 않은 블록 B를 삭제하고 샤드 #2에 대한 교차 샤드 트랜잭션을 시작합니다. 1000 token을 Bob의 계좌로 이체합니다. 지금부터 부적절하게 생성된 token은 샤드 #2의 완전히 유효한 blockchain에 상주합니다. 이 문제를 해결하기 위한 몇 가지 간단한 접근 방식은 다음과 같습니다. 6읽기 이 기사 에 대한 세부사항 에 어떻게 적응형 부패 할 수 있다 있다 운반 밖으로: https://medium.com/nearprotocol/d859adb464c8. 에 대한 더 세부사항 에 적응형 부패, 읽다 https://github.com/ethereum/wiki/wiki/Sharding-FAQ# 우리가 운영하고 있는 보안 모델은 무엇입니까?그림 7: 유효하지 않은 블록이 있는 체인의 교차 샤드 트랜잭션 1. 샤드 #2의 validators에 대해 트랜잭션이 발생한 블록을 검증합니다. 시작됩니다. 위의 예에서도 블록 C 때문에 작동하지 않습니다. 완전히 유효한 것 같습니다. 2. 샤드 #2의 validators에서 트랜잭션이 시작되는 블록 이전에 있는 다수의 블록을 검증합니다. 당연히, 수신 샤드에 의해 검증된 블록 수 N validators는 잘못된 블록 위에 N+1개의 유효한 블록을 생성할 수 있습니다. 생산. 이 문제를 해결하기 위한 유망한 아이디어는 샤드를 배열하는 것입니다. 각 샤드가 여러 다른 샤드에 연결된 무방향 그래프 인접한 샤드 간의 교차 샤드 트랜잭션만 허용합니다. Vlad Zamfir의 샤딩은 기본적으로 작동하며7, Kadena의 샤딩에서도 비슷한 아이디어가 사용됩니다. 체인웹 [1]). 샤드 간 교차 샤드 트랜잭션이 필요한 경우 이웃이 아닌 경우 이러한 트랜잭션은 여러 샤드를 통해 라우팅됩니다. 이 디자인에서는 각 샤드의 validator는 샤드의 모든 블록을 모두 검증해야 합니다. 모든 인접 샤드의 모든 블록도 마찬가지입니다. 아래 그림을 고려하십시오 샤드 10개, 각 샤드에는 4개의 이웃이 있고 더 많은 샤드가 필요한 샤드는 2개 없습니다. 그림 8에 표시된 교차 샤드 통신의 경우 홉이 2개 이상입니다. 샤드 #2는 자체 blockchain뿐만 아니라 blockchain도 검증합니다. 샤드 #1을 포함한 모든 이웃. 따라서 샤드 #1의 악의적인 행위자가 유효하지 않은 블록 B를 생성하려고 시도한 다음 그 위에 블록 C를 구축하려고 합니다. 교차 샤드 트랜잭션을 시작하면 이러한 교차 샤드 트랜잭션은 진행되지 않습니다. 샤드 #2가 샤드 #1의 전체 기록을 검증했기 때문에 유효하지 않은 블록 B를 식별하게 됩니다. 7여기에서 디자인에 대해 자세히 알아보세요: https://medium.com/nearprotocol/37e538177ed9
그림 8: 체인웹과 같은 시스템에서 잘못된 교차 샤드 트랜잭션이 발생합니다. 감지되다 단일 샤드를 손상시키는 것은 더 이상 실행 가능한 공격이 아니지만 소수의 샤드가 문제로 남아 있습니다. 그림 9에서는 두 샤드 모두를 손상시키는 적
1과 샤드 #2는 샤드 #3에 대한 교차 샤드 트랜잭션을 성공적으로 실행합니다.
유효하지 않은 블록 B의 자금으로: 그림 9: 체인웹과 같은 시스템에서 잘못된 교차 샤드 트랜잭션이 발생합니다. 감지되지 않음 샤드 #3은 샤드 #2의 모든 블록을 검증하지만 샤드 #1에서는 그렇지 않습니다. 악성 블록을 탐지할 방법이 없습니다. 상태 타당성을 적절하게 해결하는 데에는 두 가지 주요 방향이 있습니다.
및 계산의 암호화 증명. 2.3 어부 첫 번째 접근 방식의 기본 아이디어는 다음과 같습니다. 어떤 목적으로든 체인 간에 통신됩니다(예: 비콘 체인 또는 교차 샤드 트랜잭션)에는 일정 기간이 있습니다. 정직한 validator은 블록이 유효하지 않다는 증거를 제공할 수 있습니다. 거기 블록이 다음과 같다는 매우 간결한 증거를 가능하게 하는 다양한 구성입니다. 유효하지 않으므로 수신 노드의 통신 오버헤드가 훨씬 작습니다. 전체 블록을 받는 것보다 적어도 하나의 정직한 validator이 있는 한 이 접근 방식을 사용합니다. 샤드, 시스템은 안전합니다. 그림 10: 어부 이는 오늘날 제안된 프로토콜 중에서 (문제가 존재하지 않는 척하는 것 외에도) 지배적인 접근 방식입니다. 그러나 이 접근 방식에는 두 가지가 있습니다. 주요 단점: 1. 정직한 validator을 위해서는 도전 기간이 충분히 길어야 합니다. 블록이 생성되었음을 인식하고, 다운로드하고, 완전히 검증하고, 준비하는 것 블록이 유효하지 않은 경우 챌린지입니다. 그러한 기간을 도입하면 샤드 간 트랜잭션 속도가 현저히 느려집니다. 2. 챌린지 프로토콜의 존재로 인해 새로운 공격 벡터가 생성됩니다. 악성 노드가 유효하지 않은 챌린지로 스팸을 보낼 때. 확실한 해결책 이 문제는 도전자가 일정량의 token을 입금하도록 하는 것입니다. 챌린지가 유효한 경우 반환됩니다. 이는 부분적인 해결책일 뿐이므로 공격자가 시스템에 스팸을 보내는 것은 여전히 유익할 수 있습니다. 예금) 유효하지 않은 도전과 함께, 예를 들어 유효한 것을 방지하기 위해정직한 validator의 도전을 통과하세요. 이러한 공격은 애도 공격이라고합니다. 후자의 지점을 우회하는 방법은 섹션 3.7.2를 참조하세요. 2.4 간결한 비대화형 지식 논증 다중 샤드 손상에 대한 두 번째 해결책은 특정 계산(예: 일련의 거래에서 블록을 계산하는 것처럼)이 올바르게 수행되었습니다. 이러한 구조가 존재합니다. zk-SNARK, zk-STARK 및 기타 몇 가지 일부는 오늘날 개인 결제를 위해 blockchain 프로토콜에서 적극적으로 사용됩니다. 가장 주목할만한 것은 ZCash입니다. 이러한 기본 요소의 주요 문제점은 다음과 같습니다. 계산 속도가 매우 느립니다. 예: zk-SNARK를 사용하는 Coda 프로토콜 특히 blockchain의 모든 블록이 유효하다는 것을 증명하기 위해 증거를 만드는 데 거래당 30초가 걸릴 수 있다는 인터뷰 (이 숫자는 아마도 지금쯤에는 더 작을 것입니다). 흥미롭게도, 신뢰할 수 있는 당사자가 증명을 계산할 필요가 없습니다. 증명은 그것이 만들어진 계산의 타당성을 증명할 뿐만 아니라 증명 자체의 타당성. 따라서 그러한 증명의 계산은 분할될 수 있습니다. 것보다 중복성이 훨씬 적은 참가자 집합 중에서 신뢰할 수 없는 계산을 수행하는 데 필요합니다. 참가자에게도 허용됩니다. zk-SNARK를 계산하여 비용을 줄이지 않고 특수 하드웨어에서 실행하는 사람 시스템의 분산화. 성능 외에도 zk-SNARK의 과제는 다음과 같습니다. 1. 덜 연구되고 덜 테스트된 암호화 기본 요소에 대한 의존성 2. "독성 폐기물" — zk-SNARK는 그룹이 신뢰하는 설정에 의존합니다. 의 사람들이 일부 계산을 수행한 다음 중간 결과를 버립니다. 해당 계산의 값. 절차의 모든 참가자가 공모하는 경우 중간 값을 유지하면 가짜 증거가 생성될 수 있습니다. 3. 시스템 설계에 추가 복잡성이 도입되었습니다. 4. zk-SNARK는 가능한 계산의 하위 집합에 대해서만 작동하므로 프로토콜은 Turing-complete smart contract 언어로는 사용할 수 없습니다 SNARK는 체인의 유효성을 증명합니다. 2.5 데이터 가용성 우리가 다룰 두 번째 문제는 데이터 가용성입니다. 일반적으로 노드 특정 blockchain을 운영하는 것은 두 그룹으로 구분됩니다: 전체 노드, 모든 전체 블록을 다운로드하고 모든 거래를 검증하는 것, 그리고 Light 블록 헤더만 다운로드하고 부분에 Merkle 증명을 사용하는 노드 그림 11에서 볼 수 있듯이 그들이 관심을 갖고 있는 상태와 트랜잭션에 대해 설명합니다.
그림 11: 머클 트리 이제 대다수의 전체 노드가 공모하면 유효하거나 유효한 블록을 생성할 수 있습니다. 유효하지 않으며 hash을 라이트 노드로 보내지만 전체 내용을 공개하지 마십시오. 블록의. 그들이 그것으로부터 이익을 얻을 수 있는 방법은 다양합니다. 예를 들어, 그림 12를 살펴보세요. 그림 12: 데이터 가용성 문제 세 가지 블록이 있습니다. 이전 블록 A는 정직한 validators에 의해 생성되었습니다. 현재 B에는 validators가 공모하고 있습니다. 그리고 다음 C도 생산될 것이다. 정직한 validators(blockchain는 오른쪽 하단에 표시되어 있습니다). 당신은 상인입니다. 현재 블록(B)의 validators가 수신된 블록입니다. 이전 validators의 A는 귀하가 돈을 받는 블록을 계산했습니다.상태에 대한 Merkle 증명과 함께 해당 블록의 헤더를 보냈습니다. 당신은 돈이 있습니다 (또는 돈을 보내는 유효한 거래에 대한 머클 증명 당신에게). 거래가 완료되었음을 확신하고 서비스를 제공합니다. 그러나 validators는 블록 B의 전체 내용을 절대 배포하지 않습니다. 누구나. 따라서 블록 C의 정직한 validators는 블록을 검색할 수 없으며, 강제로 시스템을 정지시키거나 A 위에 구축해야 하므로 돈 상인. 동일한 시나리오를 샤딩에 적용할 때 전체 및 샤딩의 정의는 다음과 같습니다. 라이트 노드는 일반적으로 샤드별로 적용됩니다. 각 샤드의 validators는 매 다운로드마다 해당 샤드를 차단하고 해당 샤드의 모든 트랜잭션을 검증하지만 다른 스냅샷 샤드 체인 상태를 포함하는 시스템의 노드 비콘 체인의 경우 헤더만 다운로드하세요. 따라서 샤드의 validator은 다음과 같습니다. 해당 샤드의 노드를 사실상 가득 채우는 반면, 시스템의 다른 참가자는 비콘 체인을 포함하여 라이트 노드로 작동합니다. 위에서 논의한 어부 접근 방식의 경우 정직한 validators 비콘 체인에 교차 연결된 블록을 다운로드할 수 있어야 합니다. 악의적인 validators가 유효하지 않은 블록의 헤더를 교차 연결하거나 이를 사용하여 교차 샤드 트랜잭션을 시작하지만 블록을 배포하지는 않습니다. validators는 도전 과제를 만들 방법이 없습니다. 우리는 이 문제를 보완하는 세 가지 접근 방식을 다룰 것입니다. 서로. 2.5.1 양육권 증명 해결해야 할 가장 시급한 문제는 블록이 한 번만 사용 가능한지 여부입니다. 출판되었습니다. 제안된 아이디어 중 하나는 회전하는 소위 공증인을 갖는 것입니다. 유일한 작업이 다운로드인 validator보다 더 자주 샤드 사이에 다운로드할 수 있었다는 사실을 차단하고 증명합니다. 그들은 수 있습니다 전체 상태를 다운로드할 필요가 없기 때문에 더 자주 회전됩니다. 자주 회전할 수 없는 validator과 달리 샤드의 그림과 같이 샤드가 회전할 때마다 샤드의 상태를 다운로드해야 합니다. 13. 이 순진한 접근 방식의 문제점은 나중에 증명하는 것이 불가능하다는 것입니다. 공증인이 블록을 다운로드했는지 여부에 따라 공증인은 없이 블록을 다운로드할 수 있었다는 것을 항상 증명하도록 선택할 수 있습니다. 그것을 되찾으려고도 합니다. 이에 대한 한 가지 해결책은 공증인이 다음을 제공하는 것입니다. 어떤 증거를 확보하거나 블록이 다운로드되었습니다. 그러한 솔루션 중 하나가 여기에서 논의됩니다: 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. 파라체인 블록의 블록 생산자는 콜레이터, 일단 파라체인 블록이 생성되면 모든 f 부분이 충분하도록 2f +1 부분으로 구성된 블록의 삭제 코딩 버전을 계산합니다. 블록을 재구성합니다. 그런 다음 각 validator에 하나의 부품을 배포합니다. 릴레이 체인. 특정 릴레이 체인 validator은 릴레이 체인에만 서명합니다. 스냅샷된 각 파라체인 블록에 해당 부분이 있는 경우 블록을 차단합니다. 그러한 릴레이 체인 블록. 따라서 릴레이 체인 블록에 2f + 1의 서명이 있는 경우 validators, 그리고 그 중 f개 이상이 프로토콜을 위반하지 않는 한, 각각은 파라체인 블록은 validators에서 부품을 가져와서 재구성할 수 있습니다. 프로토콜을 따르는 것입니다. 그림 15를 참조하십시오. 그림 15: Polkadot의 데이터 가용성 2.5.4 장기적인 데이터 가용성 위에서 논의한 모든 접근 방식은 블록이 다음과 같다는 사실만 입증합니다. 전혀 게시되지 않았으며 현재 사용할 수 있습니다. 블록은 나중에 사용할 수 없게 될 수 있습니다. 다양한 이유: 노드가 오프라인 상태가 됨, 노드가 의도적으로 기록을 삭제함 데이터 및 기타. 이 문제를 해결하기 위해 언급할 가치가 있는 백서는 Polyshard [3]입니다. 여러 개의 블록이 있더라도 샤드 전체에서 블록을 사용할 수 있도록 삭제 코드를 사용합니다. 샤드는 데이터를 완전히 잃습니다. 불행하게도 그들의 특정 접근 방식에는 다음이 필요합니다. 모든 샤드는 다른 모든 샤드에서 블록을 다운로드해야 합니다. 비싸다. 장기적인 가용성은 문제만큼 시급하지 않습니다. 참가자가 없기 때문입니다. 시스템의 모든 체인을 검증할 수 있을 것으로 예상됩니다.
샤딩된 프로토콜의 보안은 다음과 같이 설계되어야 합니다. 일부 샤드의 일부 오래된 블록이 손상되더라도 시스템은 안전합니다. 전혀 사용할 수 없습니다.
Nightshade
3.1 从分片链到分片块 具有分片链和信标链的分片模型非常强大，但是 具有一定的复杂性。特别需要执行分叉选择规则 分别在每个链中，分片链和信标中的分叉选择规则 链必须以不同的方式构建并单独测试。 在 Nightshade 中，我们将系统建模为单个 blockchain，其中每个 块逻辑上包含所有分片的所有交易，并更改 所有分片的完整状态。然而，实际上，没有参与者下载 完整状态或完整逻辑块。相反，网络的每个参与者仅 维护与验证交易的分片相对应的状态，并且块中所有交易的列表被分为物理部分 块，每个分片一个块。 在理想条件下，每个块每个分片仅包含一个块 块，它大致对应于分片链的模型，其中 分片链产生区块的速度与信标链相同。然而， 由于网络延迟，某些块可能会丢失，因此实际上每个块 每个分片包含一个或零个块。有关如何操作的详细信息，请参阅第 3.3 节 块被生产出来。 图 16： 左侧有分片链且其中一条链具有 块在右侧分成块
3.2 共识 今天 blockchain 达成共识的两种主要方法是 最长（或最重）的链，其中具有最多工作量或权益的链 用于构建它被认为是规范的，并且 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）和 GRANDPA（参见 https:// medium.com/polkadot-network/d08a24a021b5) 用于 Polkadot。 Nightshade 采用最重链共识。 特别是当一个块 生产者生产一个区块（参见第 3.3 节），他们可以收集签名 其他区块生产者和 validator 证明前一个区块。参见部分 3.8 了解如何聚合如此大量的签名的详细信息。重量 8另请参阅 Justin Drake 的白板会议，深入了解 Casper FFG，以及它如何与 GHOST 最重链共识集成：https://www. youtube.com/watch?v=S262StTwkmo一个区块的总权益就是所有签名者的累积权益 包含在块中。链的权重是块权重的总和。 在最重链共识之上，我们使用了一个最终性小工具，该小工具使用 完成区块的证明。为了降低系统的复杂度， 我们使用一个最终性小工具，它不会以任何方式影响分叉选择规则， 相反，只引入额外的削减条件，这样一旦一个块被 由最终性小工具最终确定，除非有很大比例，否则分叉是不可能的 总股份被削减。 Casper CBC 就是这样一个最终结果小工具，我们 目前模型考虑的是 Casper CBC。 我们还致力于一个名为 TxFlow 的独立 BFT 协议。当时 撰写本文档时，尚不清楚是否会使用 TxFlow 来代替 Casper 加拿大广播公司。然而，我们注意到，最终性小工具的选择很大程度上与设计的其余部分正交。 3.3 区块生产 在 Nightshade 中有两个角色：区块生产者和 validators。 在任何 点系统包含 w 个区块生产者，在我们的模型中 w = 100，并且 wv validators，在我们的模型中 v = 100, wv = 10, 000。该系统是权益证明系统， 这意味着区块生产者和 validators 都有一定数量的内部 货币（称为“tokens”）锁定时间远远超过 他们花时间履行构建和验证链的职责。 与所有权益证明系统一样，并非所有 w 区块生产者也不是 所有 wv validator 都是不同的实体，因为无法强制执行。每个 然而，w 区块生产者和 wv validators 确实有一个单独的 股份。 系统包含 n 个分片，在我们的模型中 n = 1000。正如中提到的 第 3.1 节，在 Nightshade 中，没有分片链，而是所有区块生产者和 validator 都在构建一个 blockchain，我们将其称为 主链。主链的状态被分成n个分片，每个区块 生产者和 validator 在任何时刻都只在本地下载了一个子集 对应于分片的某个子集的状态，并且仅处理和 验证影响状态这些部分的交易。 要成为区块生产者，网络参与者需要锁定一些大的区块 数量 tokens（股份）。网络的维护是分周期完成的， 其中纪元是一段以天为单位的时间段。 参加者 在特定时期开始时，w 最大的赌注是区块 那个时代的生产者。每个区块生产者都被分配给 sw 分片（比如 sw = 40，这将使 sww/n = 每个分片有 4 个区块生产者）。街区 生产者下载纪元之前分配给他们的分片的状态 开始，并在整个纪元中收集影响该分片的交易， 并将它们应用到国家。 对于主链上的每个区块 b 和每个分片 s，都有一个 将区块生产者分配给 s，s 负责生产与 b 相关的部分 到碎片。 b 中与 shard s 相关的部分称为 chunk，包含 b 中包含的分片交易列表以及 merkle结果状态的根。 b 最终只会包含一个非常小的标头 块，即所有应用交易的 Merkle 根（参见部分 3.7.1 了解具体细节），以及最终状态的 merkle 根。 在文档的其余部分中，我们经常提到区块生产者 负责在特定时间为特定分片生成块 作为块生产者。区块生产者始终是区块生产者之一。 块生产者和块生产者根据以下方式轮换每个块： 到固定的时间表。区块生产者有订单并重复生产 按该顺序块。 例如。 如果有 100 个区块生产者，则第一个区块 生产者负责生产区块 1、101、201 等，第二个是 负责生产2、102、202等）。 由于块生产与块生产不同，需要维护 状态，对于每个分片，只有 sww/n 块生产者维护状态 每个分片，相应地只有那些 sww/n 块生产者轮流创建 大块。例如。上面的常量被分配给四个区块生产者 每个分片，每个块生产者将每四个块创建一次块。 3.4 确保数据可用性 为了确保数据可用性，我们使用类似于 Polkadot 的方法 2.5.3 节中描述。一旦区块生产者产生了一个区块，他们就会创建 它的纠删码版本，具有最佳 (w, ⌊w/6 + 1⌋) 块代码 块。 然后，他们发送一块纠删码块（我们称这些块为 块部分，或只是部分）到每个块生产者。 我们计算一棵默克尔树，其中包含作为叶子的所有部分，并且 每个块的标头包含该树的默克尔根。 这些部件通过 onepart 消息发送到 validators。每一条这样的消息 包含块头、部分序号和部分内容。的 消息还包含产生该区块的区块生产者的签名 chunk 和merkle路径来证明该部分对应于header 并由适当的区块生产者生产。 一旦区块生产者收到主链区块，他们首先检查是否 块中包含的每个块都有 onepart 消息。如果没有，则块 在检索到丢失的 onepart 消息之前不会进行处理。 一旦收到所有 onepart 消息，区块生产者就会获取 来自对等体的剩余部分并重建它们所持有的块 国家。 区块生产者不会处理主链区块，如果至少有一个 块中包含的块没有相应的 onepart 消息，或者如果对于至少一个分片，他们无法维护其状态 重建整个块。 对于可用的特定块，该块的 ⌊w/6⌋+1 就足够了 生产者有自己的部分并为他们服务。因此，只要数量 恶意行为者不超过⌊w/3⌋没有超过一半区块的链 构建它的生产者可能有不可用的块。图 17： 每个块包含每个分片一个或零个块，并且每个块 是擦除编码的。纠删码块的每个部分都被发送到指定的 区块生产者通过特殊的 onepart 消息 3.4.1 对付懒惰的区块生产者 如果区块生产者有一个区块缺少 onepart 消息，那么他们 可能会选择仍然在其上签名，因为如果该块最终在链上 将使区块生产者的奖励最大化。区块没有风险 生产者，因为事后无法证明区块生产者没有 onepart 消息。 为了解决这个问题，我们在创建块时让每个块生成器 为未来编码块的每个部分选择一种颜色（红色或蓝色），并存储 编码之前块中指定颜色的位掩码。每一个部分 然后消息包含分配给该部件的颜色，并且在以下情况下使用该颜色 计算编码部分的默克尔根。如果块生产者偏离 从协议中，可以很容易地证明这一点，因为默克尔根不会 对应于 onepart 消息，或者 onepart 消息中的颜色 对应于merkle根将与块中的掩码不匹配。 当区块生产者签署区块时，它们会包含所有区块的位掩码 他们收到的红色部分是块中包含的块。出版一个 不正确的位掩码是一种可削减的行为。如果区块生产者还没有收到 onepart 消息，他们无法知道消息的颜色，并且 因此，如果他们试图盲目地签署协议，就有 50% 的机会被削减 块。 3.5 状态转换申请 块生产者仅选择要包含在块中的交易，但是 当它们生成块时不应用状态转换。相应地，
块头包含之前默克尔化状态的默克尔根 应用块中的事务。 仅当包含该块的完整块时才应用事务 已处理。参与者仅处理一个块，如果 1. 前一个区块被接收并处理； 2.对于每个块，参与者不维护他们拥有的状态 看到了 onepart 消息； 3. 对于每个块，参与者确实维护状态，因为他们有 完整的块。 一旦块被处理，对于参与者的每个分片 维护状态，他们应用交易并计算新状态 在应用交易后，它们就准备好生产 下一个块的块（如果它们被分配给任何分片），因为它们有 新默克尔化状态的默克尔根。 3.6 跨分片交易和收据 如果一笔交易需要影响多个分片，则需要连续进行 在每个分片中单独执行。完整的交易被发送到第一个分片 受影响，并且一旦交易包含在此类分片的块中，并且 在块包含在块中之后应用，它会生成所谓的收据 交易，即路由到交易需要的下一个分片 被处决。如果需要更多步骤，则执行收据交易 生成新的收据交易等。 3.6.1 收据交易生命周期 理想的是，收据交易应用于紧随其生成的块之后的块中。收据交易仅 区块生产者收到并应用前一个区块后生成 维护原始分片，并且需要在 下一个块的块由目的地的块生产者生成 碎片。因此，收据必须从源分片传送到 这两个事件之间的短时间内的目标分片。 令 A 为最后产生的区块，其中包含生成收据 r 的交易 t。令 B 为下一个生成的块（即具有 A 的块） 它的前一个块）我们想要包含 r。设 t 在分片 a 中，r 为 在碎片 b. 收据的生命周期（也如图 18 所示）如下： 制作并保存收据。分片的块生产者 cpa a 接收区块 A，应用交易 t 并生成收据 r。注册会计师 然后将所有此类生成的收据存储在其索引的内部持久存储中 通过源分片 ID。分发收据。一旦 cpa 准备好生成块 块 B 的分片 a，它们获取通过应用分片 a 的块 A 中的交易而生成的所有收据，并将它们包含到 shrad 的块中 块 B 中的 a。一旦生成这样的块，cpa 就会生成其纠删码 版本和所有相应的 onepart 消息。 cpa 知道哪些区块生产者维护哪些分片的完整状态。对于特定的区块生产者 bp cpa 包括在 A 块中应用交易产生的收据 对于具有 bp 关心的任何分片作为其目的地的分片 a 当他们在块 B 中分发分片 a 的块时，在 onepart 消息中 （见图 17，显示了 onepart 消息中包含的收据）。 收到收据。请记住，参与者（区块生产者和 validators）在收到 onepart 消息之前不会处理区块 对于块中包含的每个块。因此，当任何特定参与者应用块 B 时，他们拥有对应于的所有 onepart 消息 B 中的块，因此它们拥有包含分片的所有传入收据 参与者将状态维持为目的地。 当应用 特定分片的状态转换，参与者应用两个收据 他们在 onepart 消息中为分片收集的信息，以及所有 包含在块本身中的事务。 图 18： 收据交易的生命周期 3.6.2 处理过多的收据 有可能针对某个特定分片的收据数量 特定块太大而无法处理。例如，考虑图 19， 每个分片中的每笔交易都会生成一个针对分片 1 的收据。 到下一个块时，分片 1 需要处理的收据数量为 与处理时所有碎片组合处理的负载相当 前一个块。
图 19： 如果所有收据都针对同一个分片，则该分片可能没有 处理它们的能力 为了解决这个问题，我们使用了类似于 QuarkChain 9 中使用的技术。 具体来说，对于每个分片，最后一个块 B 和该分片中的最后一个分片 s 记录应用收据的块。当新分片出现时 创建后，收据首先从 B 中的剩余分片中应用， 然后在 B 之后的块中，直到新块已满。正常情况下 负载均衡的情况下，一般会导致所有收据 正在应用（因此最后一个块的最后一个分片将被记录为 每个块），但在负载不平衡的时候，以及特定的 分片收到不成比例的大量收据，这种技术使他们能够 进行处理，同时遵守所包含交易数量的限制。 请注意，如果这种不平衡负载持续较长时间，则延迟 收据创建直到应用程序可以无限期地继续增长。一 解决这个问题的方法是删除任何创建收据的交易 处理延迟超过某个常量（例如一个时期）的分片。 考虑图 20。到了区块 B，分片 4 无法处理所有收据， 因此它只处理来自区块 A 中最多分片 3 的收据，并且 记录下来。在区块 C 中，包含区块 B 中最多分片 5 的收据，并且 然后到了块 D，分片赶上了，处理所有剩余的收据 B 块和 C 块的所有收据。 3.7 块验证 为特定分片生成的块（或在具有分片链的模型中为特定分片链生成的分片块）只能由 9查看 QuarkChain 的白板片段：https://www.youtube.com/watch? v=opEtG6NM4x4，其中讨论了跨分片交易的方法等 东西图 20： 延迟收据处理 维持状态的参与者。他们可以是区块生产者，validators， 或者只是下载状态并验证分片的外部见证人 他们存储资产。 在本文档中，我们假设大多数参与者无法存储 大部分分片的状态。不过值得一提的是， 存在分片 blockchain ，其设计假设为 大多数参与者确实有能力存储状态并验证大部分 分片，例如 QuarkChain。 由于只有一小部分参与者拥有验证分片的状态 块，有可能自适应地破坏具有 状态，并应用无效的状态转换。 提出了多重分片设计，每隔几次采样 validators 天，以及一天之内分片链中任何拥有超过 2/3 的区块 立即考虑分配给此类分片的 validator 的签名 最终。通过这种方法，自适应对手只需要破坏 2n/3+1 分片链中的 validators 来应用无效状态转换，其中， 虽然可能很难实现，但对于公众来说安全水平还不够 blockchain。 正如第 2.3 节中所讨论的，常见的方法是在为任何具有状态的参与者（无论是 它是一个区块生产者、validator 或外部观察者）来挑战其有效性。这些参与者被称为渔民。为了让渔民能够 挑战无效区块，必须确保这样的区块可供使用 他们。 Nightshade 中的数据可用性将在第 3.4 节中讨论。 在 Nightshade 中，一旦生成了一个块，这些块就不会被验证 除了实际的块生产者之外的任何人。特别是，区块生产者 建议该块自然不具有大多数分片的状态，并且无法验证这些块。当下一个区块产生时，它包含多个区块生产者和 validator 的证明（参见第 3.2 节）， 但由于大多数区块生产者和 validator 不维护状态 对于大多数分片来说，只有一个无效块的区块将收集超过一半的证明，并且将继续处于最重的状态 链。 为了解决这个问题，我们允许任何维持以下状态的参与者 一个分片，用于针对该分片中产生的任何无效块在链上提交挑战 碎片。 3.7.1 状态有效性挑战 一旦参与者检测到特定块无效，他们需要提供该块无效的证明。由于大多数网络参与者不维护无效块所在分片的状态 产生后，证明需要有足够的信息来确认该块是 无状态无效。 我们设置单个事务的状态量（以字节为单位）的限制 Ls 可以累积读取或写入。任何触及 Ls 以上的交易 状态被认为是无效的。请记住 3.5 节中的块 特定区块B中仅包含要应用的交易，但不包含 新的状态根。块B中的块包含的状态根是状态 在应用此类事务之前，但在应用事务之后 块 B 之前同一分片中的最后一个块。恶意行为者 希望应用无效的状态转换将包括不正确的状态根 在块 B 中，它与应用产生的状态根不对应 前一个块中的交易。 我们扩展块生产者在块中包含的信息。 它不是只包含应用所有事务后的状态，而是 在应用每个连续的交易集之后包括一个状态根 共同读取和写入 Ls 个字节的状态。 有了这些信息对于 渔夫提出了一个挑战，即状态转换应用不正确 足以找到第一个这样的无效状态根，并且只包含 Ls 字节 受最后一个状态根（之前是 valid）和带有默克尔证明的当前状态根。那么任意参与者 可以验证段中的事务并确认该块是 无效。 类似地，如果块生产者尝试包含读取的事务 并写入超过 Ls 个字节的状态，对于挑战来说，包含就足够了 它与默克尔证明接触的第一个 Ls 字节，这足以 应用交易并确认有一个时刻尝试 读取或写入的内容超出 Ls 字节。
3.7.2 渔民和快速跨分片交易 正如 2.3 节中所讨论的，一旦我们假设分片块（或分片 具有分片链的模型中的块）可能无效并带来挑战 期间，它会对最终结果产生负面影响，从而影响跨分片通信。在 特别是，任何跨分片交易的目标分片都无法确定 在挑战期结束之前，原始分片块或块是最终的 （见图 21）。 图 21： 在申请收据之前等待挑战期 以使得跨分片交易的方式来解决这个问题 Instantinious 是指目标分片不等待挑战期 源分片交易发布后，应用收据交易 立即，然后将目标分片与源分片一起回滚 如果后来发现原始块或块无效（见图 22）。这非常自然地适用于 Nightshade 设计，其中碎片 链不是独立的，而是分片块全部发布 一起在同一个主链区块中。如果发现任何块无效， 包含该块的整个块被认为是无效的，并且构建在其上的所有块 其顶部。见图 23。 上述两种方法都提供原子性，假设挑战 周期足够长。我们使用后一种方法，因为在正常情况下提供快速的跨分片交易比 由于其中之一的状态转换无效，目标分片回滚 源碎片，这是极其罕见的事件。 3.7.3 隐藏 validators 挑战的存在已经大大降低了 自适应损坏，因为要使用无效的状态转换后完成一个块图 22： 立即应用收据并回滚目的地 链如果源链有无效块 图 23： 茄属渔夫挑战 适应性对手需要腐蚀所有参与者的挑战期 维护分片的状态，包括所有 validator。 估计此类事件的可能性极其复杂，因为没有 sharded blockchain 已经存在足够长的时间来尝试任何此类攻击。我们认为这种可能性虽然极低，但仍然足够 对于预计执行数百万笔交易的系统来说很大 经营全球金融业务。 这种信念有两个主要原因： 1. 权益证明链的大多数 validator 和矿工
工作量证明链主要受到财务上行的激励。如果 适应性强的对手为他们提供的钱多于预期回报 从诚实经营的角度来看，可以合理地预期许多 validator 将接受该提议。 2. 许多实体对权益证明链进行专业验证，并且 预计任何连锁店的大部分股权都将被 来自此类实体。此类实体的数量对于 适应性强的对手能够亲自了解他们中的大多数人并拥有 很好地理解了他们的本性被腐蚀了。 我们通过隐藏哪些 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 捎带消息的详细信息 其他 validators，以及第 3.7.5 节了解如何奖励和惩罚的详细信息 validators 应该成功地发生无效状态转换挑战。图 24： 将 validator 隐藏在茄属植物中 3.7.4 提交-揭示 validators 的常见问题之一是 validator 可以跳过下载状态并实际验证块和块，而是 观察网络，查看其他 validator 提交的内容并重复他们的 消息。遵循这种策略的 validator 不提供任何额外的 网络安全，但收取奖励。 此问题的常见解决方案是为每个 validator 提供一个证明 他们实际上验证了该块，例如通过提供唯一的跟踪 应用状态转换，但这样的证明显着增加了成本 的验证。 图 25： 提交-揭示
相反，我们让 validators 首先提交验证结果（或者 证明块有效性的消息，或无效证明 状态转换），等待一定的时间，然后才显示实际的验证结果，如图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得到一个新的分片分配，并安排一个新的epoch 一段时间后开始，足以让所有 validator 下载 状态，如图 26 所示。 请注意，从 validator 显示分配给它们的分片那一刻起 直到新纪元开始，系统的安全性都会降低，因为 分片分配被揭示。网络参与者需要保留它 在此期间使用网络时请谨记。 3.8 签名聚合 为了让拥有数百个分片的系统能够安全运行，我们希望 10、000 或更多 validator 的顺序。正如第 3.7 节中所讨论的，我们希望每个图 26： 应对挑战 validator 发布对特定消息的提交和平均签名 每个块一次。即使提交消息相同，聚合这样的 BLS 签名并对其进行验证的成本将高得令人望而却步。但是 当然，validator 中的提交和显示消息并不相同， 因此我们需要某种方法来聚合这些消息和签名 以便稍后快速验证的方式。 我们使用的具体方法如下： 验证者加入区块生产者。区块生产者是已知的 在纪元开始之前的某个时间，因为他们需要一些时间来下载 纪元开始之前的状态，与 validator 不同，区块生产者是 没有隐藏。每个区块生产者都有 v 个 validator 插槽。验证者提交 向区块生产者提出链下提案，将其纳入其 v 之一 validators。如果区块生产者希望包含 validator，他们会提交 包含来自 validator 的初始链外请求的交易，以及 区块生产者的签名，使 validator 加入区块生产者。 请注意，分配给区块生产者的 validator 不一定是 验证区块生产者为其生成块的相同分片。 如果一个 validator 申请加入多个区块生产者，仅来自 第一个区块生产者将会成功。 区块生产者收集提交。区块生产者不断收集来自 validator 的提交和显示消息。一旦累积了一定数量的此类消息，区块生产者就会计算默克尔 这些消息的树，并向每个 validator 发送 merkle 根和 他们的消息的默克尔路径。 validator 验证路径并登录 默克尔根。然后，区块生产者在区块链上累积 BLS 签名 来自 validators 的 merkle 根，并且仅发布 merkle 根和 累计签名。区块生产者还签署了该区块的有效性 使用廉价的 ECDSA 签名进行多重签名。如果多重签名没有 匹配提交的默克尔根或参与的 validator 的位掩码，这是可削减的行为。同步链时，参与者 可以选择验证来自 validators 的所有 BLS 签名（这非常昂贵，因为它涉及聚合 validators 公钥），或者仅验证来自区块生产者的 ECDMA 签名，并依赖于以下事实： 区块生产者没有受到挑战和削减。 使用链上交易和默克尔证明来应对挑战。它 可以注意到，如果没有，那么泄露来自 validators 的消息是没有价值的。 检测到无效的状态转换。仅包含实际内容的消息 需要揭示无效状态转换的证明，并且仅针对此类消息 需要证明它们与之前的提交相匹配。该消息需要 被披露有两个目的： 1. 真正启动链回滚到之前的那一刻 无效状态转换（参见第 3.7.5 节）。 2. 证明 validator 并未试图证明该信息的有效性 无效块。 无论哪种情况，我们都需要解决两个问题： 1. 实际提交并未包含在链上，仅包含在链上的merkle根 提交与其他消息聚合。 validator 需要使用 区块生产者提供的默克尔路径及其原始承诺 证明他们致力于挑战。 2. 有可能分配给无效分片的所有validator 状态转换恰好被分配给损坏的区块生产者 正在审查他们。为了解决这个问题，我们允许他们提交他们的揭露 作为链上的常规交易并绕过聚合。 后者仅适用于无效状态转换的证明，即 极其罕见，因此不应导致垃圾邮件块。 需要解决的最后一个问题是区块生产者可以 选择不参与消息聚合或故意审查特定的 validator。我们通过制作区块使其在经济上处于不利地位 生产者奖励与分配给他们的 validator 数量成正比。我们 还请注意，由于纪元之间的区块生产者很大程度上相交（因为 它始终是拥有最高赌注的前 w 参与者），validators 可以 很大程度上坚持与相同的区块生产者合作，从而降低风险 被分配给过去审查过他们的区块生产者。 3.9 快照链 由于主链上的区块产生非常频繁，因此下载 完整的历史可能很快就会变得昂贵。而且，由于每 区块包含大量参与者的 BLS 签名，仅聚合公钥来检查签名可能会变得令人望而却步 也很贵。 最后，因为在任何可预见的未来 Ethereum 1.0 可能仍然是一个 最常用的 blockchain 中，有一种有意义的方式来转移资产
要求接近 Ethereum，今天验证 BLS 签名以确保 Ethereum 一侧的近块有效性是不可能的。 Nightshade 主链中的每个区块都可以选择包含 Schnorr 包含此类 Schnorr 的最后一个块的标头上的多重签名 多重签名。我们将此类块称为快照块。第一个块 每个纪元必须是一个快照块。在研究这样的多重签名时， 区块生产者还必须累积 validator 的 BLS 签名 在最后一个快照块上，并按照与中所述相同的方式聚合它们 第 3.8 节。 由于区块生产者集在整个时期内保持不变，因此验证 假设在没有任何情况下，只有每个时期中的第一个快照块就足够了 指出很大一部分区块生产者和 validator 串通并创建 叉子。 纪元的第一个块必须包含足以计算的信息 该纪元的区块生产者和 validators。 我们称主链中只包含快照的子链为 阻止快照链。 创建 Schnorr 多重签名是一个交互式过程，但由于我们 只需要很少执行，任何流程，无论效率如何低下 就足够了。 Schnorr 多重签名可以在 Ethereum 上轻松验证， 从而为执行跨blockchain的安全方式提供关键原语 沟通。 与近链同步只需下载所有快照 块并确认 Schnorr 签名正确（也可以选择验证 validator 的各个 BLS 签名），然后仅同步 主链区块来自最后一个快照区块。
Nightshade
3.1 샤드 체인에서 샤드 청크로 샤드체인과 비콘체인을 이용한 샤딩 모델은 매우 강력하지만 특정 복잡성이 있습니다. 특히 포크 선택 규칙을 실행해야 합니다. 각 체인에서 별도로 샤드 체인과 비콘의 포크 선택 규칙 체인은 다르게 구축하고 별도로 테스트해야 합니다. Nightshade에서 우리는 시스템을 단일 blockchain로 모델링합니다. 블록은 논리적으로 모든 샤드에 대한 모든 트랜잭션을 포함하고 모든 샤드의 전체 상태. 그러나 물리적으로 참가자 중 누구도 다운로드하지 않습니다. 전체 상태 또는 전체 논리 블록. 대신, 네트워크의 각 참가자는 트랜잭션을 검증하는 샤드에 해당하는 상태를 유지하며, 블록의 모든 트랜잭션 목록은 물리적으로 분할됩니다. 청크, 샤드당 하나의 청크. 이상적인 조건에서 각 블록은 샤드당 정확히 하나의 청크를 포함합니다. 이는 샤드 체인이 있는 모델과 대략적으로 일치합니다. 샤드 체인은 비콘 체인과 동일한 속도로 블록을 생성합니다. 그러나, 네트워크 지연으로 인해 일부 청크가 누락될 수 있으므로 실제로는 각 블록이 샤드당 1개 또는 0개의 청크를 포함합니다. 방법에 대한 자세한 내용은 섹션 3.3을 참조하세요. 블록이 생산됩니다. 그림 16: 왼쪽에 샤드 체인이 있고 하나의 체인에 샤드 체인이 있는 모델 블록은 오른쪽의 덩어리로 분할됩니다.
3.2 합의 오늘날 blockchains의 합의에 대한 두 가지 지배적인 접근 방식은 가장 긴(또는 가장 무거운) 체인, 가장 많은 작업이나 스테이크가 있는 체인 이를 구축하는 데 사용된 것은 정식으로 간주되며 BFT, 각 블록에 대해 validator 세트는 BFT 합의에 도달합니다. 최근 제안된 프로토콜에서는 후자가 더 지배적인 접근 방식입니다. 즉각적인 최종성을 제공하는 반면 가장 긴 체인에서는 더 많은 블록이 필요하기 때문입니다. 최종성을 보장하기 위해 블록 위에 구축됩니다. 종종 의미 있는 일을 위해 보안상 충분한 수의 블록을 구축하는 데 걸리는 시간은 시간 순서. 각 블록에서 BFT 합의를 사용하면 다음과 같은 단점도 있습니다. 1. BFT 합의에는 상당한 양의 의사소통이 필요합니다. 동안 최근의 발전으로 선형적인 시간 내에 합의에 도달할 수 있게 되었습니다. 참가자 수(예: [4] 참조)에서는 여전히 블록당 오버헤드가 눈에 띕니다. 2. 모든 네트워크 참여자가 BFT에 참여하는 것은 불가능합니다. 블록당 합의에 도달하므로 일반적으로 무작위로 샘플링된 참가자 하위 집합만 합의에 도달합니다. 무작위로 추출된 세트는 원칙적으로 다음과 같습니다. 적응적으로 손상되고 이론적으로는 포크가 생성될 수 있습니다. 시스템 그러한 이벤트에 대비하려면 모델링이 필요하므로 여전히 BFT 합의 외에 포크 선택 규칙이 있거나 폐쇄되도록 설계되었습니다. 이런 경우에는 다운됩니다. 다음과 같은 일부 디자인을 언급할 가치가 있습니다. Algorand [5], 적응형 손상 가능성을 크게 줄입니다. 3. 가장 중요한 것은 다음과 같은 경우 시스템이 정지된다는 것입니다. 전체 참가자 중 3명 이상이 오프라인. 따라서 일시적인 네트워크 결함이나 네트워크 분할로 인해 시스템이 완전히 정지될 수 있습니다. 이상적으로 시스템은 계속해서 작동할 수 있어야 합니다. 참가자 중 최소 절반이 온라인 상태인 한(가장 무거운 체인 기반 프로토콜은 참가자의 절반 미만이 온라인 상태인 경우에도 계속 작동하지만 이 속성의 바람직성은 더 논쟁의 여지가 있습니다. 커뮤니티 내에서). 사용된 합의가 일종의 가장 무거운 하이브리드 모델 체인이지만 일부 블록은 BFT 최종성 가젯을 사용하여 주기적으로 마무리되며 두 모델의 장점을 모두 유지합니다. 이러한 BFT 최종 가젯은 Casper FFG [6]는 Ethereum 2.0 8, Casper CBC에서 사용됩니다(https://vitalik. 참조). ca/general/2018/12/05/cbc_casper.html) 및 GRANDPA(https:// Medium.com/polkadot-network/d08a24a021b5) Polkadot에서 사용됩니다. Nightshade는 가장 무거운 체인 합의를 사용합니다. 특히 블록일 때 생산자는 블록을 생성하고(섹션 3.3 참조) 다음에서 서명을 수집할 수 있습니다. 다른 블록 생산자와 이전 블록을 증명하는 validators. 섹션을 참조하세요 이렇게 많은 수의 서명이 어떻게 집계되는지 자세히 알아보려면 3.8을 참조하세요. 무게 8Casper에 대한 심층적인 개요는 Justin Drake와의 화이트보드 세션도 참조하세요. FFG 및 이것이 GHOST의 가장 무거운 체인 합의와 통합되는 방법은 다음과 같습니다: https://www. youtube.com/watch?v=S262StTwkmo블록의 서명은 다음과 같은 서명을 가진 모든 서명자의 누적 지분입니다. 블록에 포함됩니다. 체인의 무게는 블록 무게의 합입니다. 가장 무거운 체인 합의 위에 우리는 다음을 사용하는 최종 장치를 사용합니다. 블록을 마무리하기 위한 증명입니다. 시스템의 복잡성을 줄이기 위해, 우리는 포크 선택 규칙에 어떤 식으로든 영향을 주지 않는 최종 장치를 사용합니다. 대신 추가 슬래싱 조건만 도입합니다. 최종 가젯으로 마무리된 경우 매우 큰 비율이 아니면 포크는 불가능합니다. 전체 지분 중 삭감됩니다. Casper CBC는 그러한 최종 장치이며 우리는 현재 Casper CBC를 염두에 두고 모델을 만들고 있습니다. 우리는 또한 TxFlow라는 별도의 BFT 프로토콜을 개발하고 있습니다. 당시 이 문서를 작성하면 Casper 대신 TxFlow가 사용될지 확실하지 않습니다. CBC. 그러나 우리는 최종 가젯의 선택이 나머지 설계와 대체로 직교한다는 점에 주목합니다. 3.3 블록 생산 Nightshade에는 블록 생산자와 validator라는 두 가지 역할이 있습니다. 언제든지 시스템에 w개의 블록 생산자가 포함되어 있고, 우리 모델에서는 w = 100이며, wv validators, 우리 모델에서는 v = 100, wv = 10, 000입니다. 시스템은 지분 증명입니다. 이는 블록 생산자와 validator 모두 내부에 일정 수의 내부 정보가 있음을 의미합니다. 통화("tokens"라고 함)는 해당 통화를 훨씬 초과하는 기간 동안 잠겨 있습니다. 체인을 구축하고 검증하는 임무를 수행하는 데 소요되는 시간입니다. 모든 지분 증명 시스템과 마찬가지로, 모든 w 블록 생산자가 아니라 모든 wv validator은 시행할 수 없기 때문에 다른 엔터티입니다. 각각 그러나 w 블록 생산자와 wv validators는 별도의 스테이크. 시스템에는 n개의 샤드가 포함되어 있으며 모델에서는 n = 1000입니다. 에서 언급했듯이 섹션 3.1, Nightshade에는 샤드 체인이 없습니다. 대신 모든 블록 생산자와 validator가 단일 blockchain를 구축하고 있습니다. 메인 체인. 메인체인의 상태는 n개의 샤드로 분할되며, 각 블록은 producer 및 validator은 언제든지 로컬에 하위 집합만 다운로드했습니다. 샤드의 일부 하위 집합에 해당하는 상태이며, 처리 및 주의 해당 부분에 영향을 미치는 거래를 검증합니다. 블록 생산자가 되기 위해 네트워크 참가자는 일부 대규모 잠금을 설정합니다. tokens(스테이크)의 양. 네트워크의 유지 관리는 시대별로 이루어집니다. 여기서 에포크는 일 단위의 기간입니다. 참가자 특정 시대가 시작될 때 가장 큰 지분을 가진 블록은 다음과 같습니다. 그 시대의 생산자. 각 블록 생산자는 sw 샤드에 할당됩니다(예: sw = 40, 즉 샤드당 sww/n = 4명의 블록 생산자가 됩니다. 블록 생산자는 에포크 이전에 할당된 샤드의 상태를 다운로드합니다. 시작되고 에포크 전반에 걸쳐 해당 샤드에 영향을 미치는 트랜잭션을 수집합니다. 그리고 이를 국가에 적용합니다. 메인 체인의 각 블록 b와 모든 샤드 s에 대해 다음 중 하나가 있습니다. b 관련 부분을 생산할 책임이 있는 블록 생산자를 s에게 할당했습니다. 샤드에. 샤드 s와 관련된 b 부분을 청크라고 하며 다음을 포함합니다. b에 포함될 샤드에 대한 트랜잭션 목록과 머클결과 상태의 루트. b는 궁극적으로 매우 작은 헤더만 포함하게 됩니다. 청크, 즉 적용된 모든 트랜잭션의 머클 루트(섹션 참조) 정확한 세부 사항은 3.7.1 참조) 및 최종 상태의 머클 루트입니다. 문서의 나머지 부분에서 우리는 종종 블록 생산자를 언급합니다. 특정 샤드에 대해 특정 시간에 청크를 생성하는 역할을 담당합니다. 청크 프로듀서로서. 청크 생산자는 항상 블록 생산자 중 하나입니다. 블록 생산자와 청크 생산자는 각 블록을 다음과 같이 회전합니다. 정해진 일정으로. 블록 생산자는 주문을 받고 반복적으로 생산을 합니다. 그 순서대로 블록을 쌓으세요. 예: 블록 생산자가 100명이면 첫 번째 블록은 생산자는 블록 1, 101, 201 등을 생산할 책임이 있으며, 두 번째는 2, 102, 202 등 생산 담당). 청크 생산은 블록 생산과 달리 유지 관리가 필요하므로 상태를 유지하며, 각 샤드에 대해 sww/n 블록 생산자만이 상태를 유지합니다. 샤드별로 해당 sww/n 블록 생산자만 순환하여 생성합니다. 덩어리. 예: 위의 상수와 4명의 블록 생산자가 할당되어 있습니다. 각 샤드, 각 블록 생산자는 4개의 블록마다 한 번씩 청크를 생성합니다. 3.4 데이터 가용성 보장 데이터 가용성을 보장하기 위해 우리는 Polkadot과 유사한 접근 방식을 사용합니다. 섹션 2.5.3에 설명되어 있습니다. 블록 생산자가 청크를 생성하면 다음을 생성합니다. 최적의 (w, ⌊w/6 + 1⌋) 블록 코드를 사용하여 삭제 코딩된 버전 덩어리. 그런 다음 삭제 코딩된 청크의 한 조각을 보냅니다(우리는 이러한 조각을 호출합니다). 청크 부분 또는 부분)을 각 블록 생산자에게 전달합니다. 우리는 나뭇잎과 같은 모든 부분을 포함하는 머클 트리를 계산합니다. 각 청크의 헤더에는 해당 트리의 머클 루트가 포함됩니다. 부품은 onepart 메시지를 통해 validators로 전송됩니다. 그런 메시지 하나하나 청크 헤더, 부분의 서수 및 부분 내용을 포함합니다. 는 메시지에는 해당 블록을 생성한 블록 생산자의 서명도 포함되어 있습니다. 해당 부분이 헤더에 해당함을 증명하기 위한 청크와 머클 경로 그리고 적절한 블록 생산자에 의해 생산됩니다. 블록 생산자가 메인 체인 블록을 받으면 먼저 블록 생성 여부를 확인합니다. 블록에 포함된 각 청크에 대해 하나의 메시지를 가집니다. 그렇지 않으면 블록 누락된 onepart 메시지가 검색될 때까지 처리되지 않습니다. 모든 onepart 메시지가 수신되면 블록 생산자는 피어로부터 남은 부분을 가져와 그들이 보유하고 있는 청크를 재구성합니다. 상태. 블록 생산자는 메인 체인 블록을 처리하지 않습니다. 블록에 포함된 청크에는 해당 onepart 메시지가 없거나 상태를 유지하는 하나 이상의 샤드에 대해 사용할 수 없는 경우 전체 청크를 재구성합니다. 특정 청크를 사용하려면 블록의 ⌊w/6⌋+1이면 충분합니다. 생산자는 자신의 역할을 갖고 이를 제공합니다. 따라서, 그 수만큼은 악의적인 행위자는 블록이 절반 이상인 체인이 없는 ⌊w/3⌋을 초과하지 않습니다. 그것을 만드는 생산자는 사용할 수 없는 청크를 가질 수 있습니다.그림 17: 각 블록에는 샤드당 1개 또는 0개의 청크가 포함되어 있으며, 각 청크는 삭제 코딩되어 있습니다. 삭제 코딩된 청크의 각 부분은 지정된 위치로 전송됩니다. 특별한 onepart 메시지를 통한 블록 생산자 3.4.1 게으른 블록 생산자 다루기 블록 생산자가 한 부분 메시지가 누락된 블록을 가지고 있는 경우, 블록이 체인에 연결되면 계속 서명하기로 선택할 수 있습니다. 블록 생산자에 대한 보상을 극대화할 것입니다. 블록에 대한 위험이 없습니다 왜냐하면 블록 프로듀서가 블록 프로듀서를 갖고 있지 않았다는 것을 나중에 증명하는 것이 불가능하기 때문입니다. 한 부분 메시지. 이 문제를 해결하기 위해 청크를 생성할 때 각 청크 생산자를 만듭니다. 향후 인코딩된 청크의 각 부분에 대해 색상(빨간색 또는 파란색)을 선택하고 저장합니다. 인코딩되기 전 청크에 할당된 색상의 비트마스크입니다. 각 부분 메시지에는 부품에 할당된 색상이 포함되며, 색상은 다음과 같은 경우에 사용됩니다. 인코딩된 부분의 머클 루트를 계산합니다. 청크 생산자가 이탈하는 경우 머클 루트는 그렇지 않기 때문에 프로토콜에서 쉽게 증명할 수 있습니다. onepart 메시지에 해당하거나, onepart 메시지의 색상에 해당합니다. 머클 루트에 해당하는 것은 청크의 마스크와 일치하지 않습니다. 블록 생산자가 블록에 서명하면 모든 블록의 비트마스크가 포함됩니다. 블록에 포함된 청크에 대해 받은 빨간색 부분입니다. 게시 잘못된 비트마스크는 슬래시 가능한 동작입니다. 블록 생산자가 메시지를 받지 못한 경우 메시지를 한 부분으로만 읽어도 메시지의 색상을 알 수 없습니다. 따라서 맹목적으로 서명을 시도하면 베임을 당할 확률이 50%입니다. 블록. 3.5 상태 전이 신청 청크 생산자는 청크에 포함할 트랜잭션만 선택하지만 청크를 생성할 때 상태 전환을 적용하지 마십시오. 이에 따라,
청크 헤더에는 이전의 머켈화된 상태의 머클 루트가 포함되어 있습니다. 청크의 트랜잭션이 적용됩니다. 트랜잭션은 청크를 포함하는 전체 블록에만 적용됩니다. 처리됩니다. 참가자는 다음의 경우에만 블록을 처리합니다. 1. 이전 블록이 수신되어 처리되었습니다. 2. 각 청크에 대해 참가자는 자신이 가지고 있는 상태를 유지하지 않습니다. onepart 메시지를 보았습니다. 3. 각 청크에 대해 참가자는 상태를 유지합니다. 전체 덩어리. 블록이 처리되면 참가자가 사용하는 각 샤드에 대해 상태를 유지하고 트랜잭션을 적용하고 새로운 상태를 계산합니다. 거래가 적용된 후부터 생산 준비가 완료됩니다. 다음 블록의 청크(샤드에 할당된 경우) 새로운 머켈화된 상태의 머클 루트. 3.6 교차 샤드 거래 및 영수증 트랜잭션이 둘 이상의 샤드에 영향을 미쳐야 하는 경우 연속적으로 수행되어야 합니다. 각 샤드에서 개별적으로 실행됩니다. 전체 트랜잭션이 첫 번째 샤드로 전송됩니다. 영향을 받고 트랜잭션이 해당 샤드의 청크에 포함되면 청크가 블록에 포함된 후 적용되면 소위 영수증이 생성됩니다. 트랜잭션이 필요한 다음 샤드로 라우팅됩니다. 처형되다. 추가 단계가 필요한 경우 영수증 거래 실행 새로운 영수증 거래 등을 생성합니다. 3.6.1 영수증 거래 수명 영수증 거래는 해당 거래가 발생한 블록 바로 다음 블록에 적용하는 것이 바람직하다. 영수증 거래는 블록 생산자가 이전 블록을 수신하고 적용한 후에 생성됨 원래 샤드를 유지하고 샤드가 생성될 때까지 알려져야 합니다. 다음 블록의 청크는 대상의 블록 생산자가 생성합니다. 파편. 따라서 영수증은 소스 샤드에서 샤드에 전달되어야 합니다. 두 이벤트 사이의 짧은 시간 내에 대상 샤드를 생성합니다. A를 영수증 r을 생성하는 트랜잭션 t를 포함하는 마지막으로 생성된 블록이라고 가정합니다. B를 다음으로 생성된 블록(즉, A를 갖는 블록)이라고 가정합니다. 이전 블록)에 r을 포함하려고 합니다. t가 샤드 a와 r에 있도록 하세요. 샤드에서 b. 그림 18에도 표시된 영수증의 수명은 다음과 같습니다. 영수증을 생성하고 보관합니다. 샤드의 청크 생산자 CPA a는 블록 A를 수신하고, 트랜잭션 t를 적용하고 영수증 r을 생성합니다. CPA 그런 다음 생성된 모든 영수증을 색인이 생성된 내부 영구 저장소에 저장합니다. 소스 샤드 ID로영수증을 배포합니다. CPA가 청크를 생성할 준비가 되면 블록 B에 대한 샤드 a, 샤드 a에 대한 블록 A의 트랜잭션을 적용하여 생성된 모든 영수증을 가져와 shrad에 대한 청크에 포함했습니다. 블록 B의 a. 해당 청크가 생성되면 cpa는 삭제 코딩된 삭제 코드를 생성합니다. 버전 및 해당하는 모든 onepart 메시지. cpa는 어떤 블록 생산자가 샤드의 전체 상태를 유지하는지 알고 있습니다. 특정 블록 생산자의 경우 bp cpa에는 블록 A의 거래를 적용하여 발생한 영수증이 포함됩니다. bp가 대상으로 관심을 갖는 샤드 중 하나를 포함하는 샤드 a의 경우 블록 B의 샤드 A에 대한 청크를 배포할 때 onepart 메시지에서 (onepart 메시지에 포함된 영수증을 보여주는 그림 17 참조) 영수증을 받고 있습니다. 참가자(블록 생산자와 validator 모두)는 단일 메시지를 받을 때까지 블록을 처리하지 않는다는 점을 기억하십시오. 블록에 포함된 각 청크에 대해. 따라서 특정 참가자가 블록 B를 적용할 때쯤에는 블록 B에 해당하는 모든 단일 부분 메시지를 갖게 됩니다. B에 청크가 있으므로 샤드가 있는 모든 수신 영수증을 갖게 됩니다. 참가자는 목적지로 상태를 유지합니다. 신청할 때 특정 샤드에 대한 상태 전환, 참가자는 두 가지 영수증을 모두 적용합니다. 그들은 onepart 메시지의 샤드를 위해 수집한 것뿐만 아니라 모든 청크 자체에 포함된 트랜잭션입니다. 그림 18: 영수증 거래의 수명 3.6.2 너무 많은 영수증 처리 특정 샤드를 대상으로 하는 영수증의 수가 특정 블록이 너무 커서 처리할 수 없습니다. 예를 들어 그림 19를 살펴보겠습니다. 각 샤드의 각 거래는 샤드 1을 대상으로 하는 영수증을 생성합니다. 다음 블록까지 샤드 1이 처리해야 하는 영수증 수는 다음과 같습니다. 처리하는 동안 모든 샤드가 결합되어 처리하는 부하와 비슷합니다. 이전 블록.
그림 19: 모든 영수증이 동일한 샤드를 대상으로 하는 경우 샤드는 그것을 처리할 수 있는 능력 이를 해결하기 위해 우리는 QuarkChain 9에서 사용된 것과 유사한 기술을 사용합니다. 구체적으로, 각 샤드에 대해 마지막 블록 B와 해당 샤드 내의 마지막 샤드 영수증이 적용된 블록이 기록됩니다. 새로운 샤드가 생성되면 생성되면 B에 남아있는 샤드부터 순서대로 영수증이 적용되며, 그런 다음 새 청크가 가득 찰 때까지 B를 따르는 블록에서. 정상 이하 부하가 균형 잡힌 상황에서는 일반적으로 모든 영수증이 발생합니다. 적용됩니다(따라서 마지막 블록의 마지막 샤드가 기록됩니다). 각 청크), 하지만 로드가 균형을 이루지 못하는 경우, 그리고 특정 샤드는 불균형적으로 많은 영수증을 받습니다. 이 기술을 사용하면 샤드는 다음과 같은 일을 할 수 있습니다. 포함된 거래 수 제한을 준수하면서 처리됩니다. 이러한 불균형 부하가 오랫동안 지속되면 지연이 발생합니다. 영수증 생성 전까지 신청은 무한정 늘어날 수 있습니다. 하나 이 문제를 해결하는 방법은 다음을 대상으로 하는 영수증을 생성하는 모든 거래를 삭제하는 것입니다. 일부 상수(예: 1 에포크)를 초과하는 처리 지연이 있는 샤드. 그림 20을 살펴보세요. 블록 B에서는 샤드 4가 모든 영수증을 처리할 수 없습니다. 따라서 블록 A의 최대 샤드 3에서 발생한 영수증만 처리합니다. 그것을 기록합니다. 블록 C에는 블록 B의 샤드 5까지의 영수증이 포함됩니다. 그런 다음 블록 D에서 샤드가 따라잡아 나머지 영수증을 모두 처리합니다. 블록 B와 블록 C의 모든 영수증. 3.7 청크 검증 특정 샤드에 대해 생성된 청크(또는 샤드 체인이 있는 모델에서 특정 샤드 체인에 대해 생성된 샤드 블록)는 오직 9여기에서 QuarkChain의 화이트보드 에피소드를 확인하세요: https://www.youtube.com/watch? v=opEtG6NM4x4, 여기에서는 교차 샤드 트랜잭션에 대한 접근 방식이 논의됩니다. 것들그림 20: 지연된 영수증 처리 상태를 유지하는 참가자. 그들은 블록 생산자가 될 수 있습니다, validators, 또는 상태를 다운로드하고 샤드를 검증한 외부 증인일 수도 있습니다. 자산을 저장하는 곳입니다. 이 문서에서는 대부분의 참가자가 저장할 수 없다고 가정합니다. 샤드의 상당 부분에 대한 상태입니다. 언급할 가치는 있지만, 다음과 같은 가정으로 설계된 샤딩된 blockchain이 있습니다. 대부분의 참가자는 대부분의 상태를 저장하고 검증할 수 있는 능력을 가지고 있습니다. QuarkChain과 같은 샤드. 참가자 중 극히 일부만이 샤드를 검증할 수 있는 상태를 갖고 있기 때문에 청크를 갖고 있는 참가자만 적응적으로 손상시킬 수 있습니다. 상태를 확인하고 잘못된 상태 전환을 적용합니다. 몇 번씩 validator을 샘플링하는 다중 샤딩 설계가 제안되었습니다. 일, 그리고 하루 이내에 2/3 이상인 샤드 체인의 모든 블록 해당 샤드에 할당된 validator의 서명이 즉시 고려됩니다. 최종. 이러한 접근 방식을 사용하면 적응력이 뛰어난 공격자는 2n/3+1만 부패시키면 됩니다. 샤드 체인의 validator 중 잘못된 상태 전환을 적용합니다. 해내기 어려울 가능성이 높지만 대중에게 충분한 보안 수준은 아닙니다. blockchain. 섹션 2.3에서 설명한 것처럼 일반적인 접근 방식은 상태가 있는 모든 참가자에 대해 블록이 생성된 후 특정 시간을 허용하는 것입니다. 그 타당성에 도전하는 것은 블록 생산자, validator 또는 외부 관찰자입니다. 이러한 참가자를 어부(Fishermen)라고 합니다. 낚시꾼이 할 수 있는 일 유효하지 않은 블록에 대해 이의를 제기하려면 해당 블록을 사용할 수 있는지 확인해야 합니다. 그들. Nightshade의 데이터 가용성은 섹션 3.4에서 논의됩니다. Nightshade에서는 블록이 생성되면 해당 청크가 검증되지 않습니다. 실제 청크 생산자가 아닌 사람. 특히, 블록 프로듀서는 블록이 당연히 대부분의 샤드에 대한 상태를 갖고 있지 않다고 제안했습니다.청크의 유효성을 검사할 수 없습니다. 다음 블록이 생성되면 여러 블록 생산자와 validator의 증명(섹션 3.2 참조)이 포함됩니다. 하지만 대부분의 블록 생산자와 validator은 상태를 유지하지 않기 때문에 대부분의 샤드에서도 유효하지 않은 청크가 하나만 있는 블록은 증명의 절반 이상을 수집하고 계속해서 가장 무거운 상태를 유지하게 됩니다. 체인. 이 문제를 해결하기 위해 우리는 다음 상태를 유지하는 모든 참가자를 허용합니다. 생성된 유효하지 않은 청크에 대해 온체인으로 챌린지를 제출하는 샤드 파편. 3.7.1 상태 타당성 문제 참가자가 특정 청크가 유효하지 않음을 감지하면 해당 청크가 유효하지 않다는 증거를 제공해야 합니다. 대부분의 네트워크 참여자는 유효하지 않은 청크가 존재하는 샤드에 대한 상태를 유지하지 않기 때문에 생성되면 증거에는 블록이 다음과 같은지 확인하는 데 충분한 정보가 있어야 합니다. 상태가 없으면 유효하지 않습니다. 우리는 단일 트랜잭션이 처리하는 상태량(바이트)의 한계 Ls를 설정합니다. 누적적으로 읽거나 쓸 수 있습니다. Ls 이상에 영향을 미치는 모든 거래 상태는 유효하지 않은 것으로 간주됩니다. 섹션 3.5에서 청크가 특정 블록 B에는 적용할 트랜잭션만 포함되어 있지만 새로운 상태 루트. 블록 B의 청크에 포함된 상태 루트가 상태입니다. 그러한 트랜잭션을 적용하기 전에는 루트이지만 다음에서 트랜잭션을 적용한 후에는 블록 이전의 동일한 샤드의 마지막 청크 B. 악의적인 행위자 잘못된 상태 전환을 적용하려고 하면 잘못된 상태 루트가 포함됩니다. 적용 결과로 발생한 상태 루트에 해당하지 않는 블록 B에서 이전 청크의 트랜잭션. 청크 생산자가 청크에 포함하는 정보를 확장합니다. 모든 트랜잭션을 적용한 후 상태를 포함하는 대신 각 연속 트랜잭션 집합을 적용한 후 상태 루트를 포함합니다. 상태의 Ls 바이트를 집합적으로 읽고 씁니다. 이 정보를 통해 상태 전환이 잘못 적용되는 문제를 만드는 어부 첫 번째 유효하지 않은 상태 루트를 찾고 Ls 바이트만 포함하면 충분합니다. 마지막 상태 루트(이는 유효한) 및 머클 증명이 포함된 현재 상태 루트입니다. 그러면 어떤 참가자라도 세그먼트의 트랜잭션을 검증하고 청크가 다음과 같은지 확인할 수 있습니다. 유효하지 않습니다. 마찬가지로, 청크 생산자가 다음을 읽는 트랜잭션을 포함하려고 시도한 경우 Ls 바이트 이상의 상태를 작성합니다. 이 문제의 경우 다음을 포함하는 것으로 충분합니다. 머클 증명과 접촉하는 첫 번째 L 바이트는 다음과 같이 충분합니다. 트랜잭션을 적용하고 시도가 있는 순간이 있는지 확인합니다. Ls 바이트를 초과하는 콘텐츠를 읽거나 씁니다.
3.7.2 어부와 빠른 샤드 간 거래 섹션 2.3에서 설명한 것처럼 샤드 청크(또는 샤드)가 샤드 체인이 있는 모델의 블록)은 유효하지 않으며 문제가 발생할 수 있습니다. 기간 동안 이는 최종성에 부정적인 영향을 미쳐 샤드 간 통신에 부정적인 영향을 미칩니다. 에서 특히, 샤드 간 거래의 대상 샤드는 확실할 수 없습니다. 원래 샤드 청크 또는 블록은 챌린지 기간이 끝날 때까지 최종입니다. (그림 21 참조) 그림 21: 영수증을 적용하기 전에 챌린지 기간을 기다리는 중 교차 샤드 트랜잭션을 수행하는 방식으로 이를 해결하는 방법 Instantenious는 대상 샤드가 챌린지 기간을 기다리지 않는 것입니다. 소스 샤드 트랜잭션이 게시된 후 영수증 트랜잭션을 적용합니다. 즉시, 그러나 소스와 함께 대상 샤드를 롤백합니다. 나중에 원래 청크나 블록이 유효하지 않은 것으로 밝혀지면 샤딩합니다(그림 참조). 22). 이는 샤드가 사용되는 Nightshade 디자인에 매우 자연스럽게 적용됩니다. 체인은 독립적이지 않지만 대신 샤드 청크가 모두 게시됩니다. 동일한 메인 체인 블록에 함께 있습니다. 유효하지 않은 청크가 발견되면 해당 청크가 포함된 전체 블록은 유효하지 않은 것으로 간주되며, 그 위에 구축된 모든 블록은 그것의 꼭대기. 그림 23을 참조하십시오. 위의 두 접근 방식 모두 챌린지가 다음과 같다고 가정하여 원자성을 제공합니다. 기간은 충분히 길다. 정상적인 상황에서 빠른 크로스샤드 트랜잭션을 제공하는 것이 불편함을 능가하기 때문에 우리는 후자의 접근 방식을 사용합니다. 다음 중 하나의 잘못된 상태 전환으로 인해 대상 샤드 롤백 이는 극히 드문 이벤트입니다. 3.7.3 validator 숨기기 문제가 존재하면 이미 다음과 같은 가능성이 크게 감소합니다. 잘못된 상태 전환 포스트로 청크를 마무리하기 때문에 적응형 손상그림 22: 영수증 즉시 적용 및 대상 롤백 소스 체인에 유효하지 않은 블록이 있는 경우 체인 그림 23: Nightshade의 어부 도전 적응형 적이 모든 참가자를 부패시키는 데 필요한 도전 기간 모든 validator을 포함하여 샤드의 상태를 유지합니다. 그러한 사건의 가능성을 추정하는 것은 매우 복잡합니다. 샤딩된 blockchain은 그러한 공격이 시도될 만큼 오랫동안 활성화되었습니다. 우리는 확률이 극히 낮지만 여전히 충분하다고 주장합니다. 수백만 건의 트랜잭션을 실행할 것으로 예상되는 시스템에 비해 규모가 크고 세계적인 금융 운영을 운영합니다. 이러한 믿음에는 두 가지 주요 이유가 있습니다. 1. 대부분의 지분 증명 체인과 채굴자의 validator
작업 증명 체인은 주로 재정적 측면에서 인센티브를 받습니다. 만약에 적응형 적군은 예상 수익보다 더 많은 돈을 제공합니다. 정직하게 운영하면 많은 validator이 발생할 것으로 예상하는 것이 합리적입니다. 그 제안을 받아들일 것이다. 2. 많은 기업이 지분 증명 체인을 전문적으로 검증합니다. 어떤 체인에서든 지분의 상당 부분이 그러한 단체로부터. 그러한 개체의 수는 한 기업에 비해 충분히 적습니다. 적응력이 뛰어난 적은 그들 대부분을 개인적으로 알아가고 그들의 부패 성향을 잘 이해하고 있습니다. 우리는 어떤 validator이 어떤 샤드에 할당되어 있는지 숨김으로써 적응형 손상 가능성을 줄이는 데 한 단계 더 나아갔습니다. 아이디어는 Algorand [5]이 validator을 숨기는 방식과 원격으로 유사합니다. Algorand에서와 같이 validator이 숨겨져 있더라도 주의하는 것이 중요합니다. 또는 아래 설명된 것처럼 적응형 손상은 이론상으로는 여전히 가능합니다. 동안 적응형 적수는 생성하거나 검증할 참가자를 알지 못합니다. 블록이나 덩어리, 참가자 스스로는 자신이 수행할 것임을 알고 있습니다. 그러한 작업을 수행하고 이에 대한 암호화 증거를 가지고 있습니다. 따라서 상대방은 다음과 같이 할 수 있다. 부패하려는 의도를 알리고 이를 제공할 참가자에게 비용을 지불합니다. 그러한 암호화 증명. 그러나 우리는 적이 그렇지 않기 때문에 손상시키려는 샤드에 할당된 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: Nightshade에 validator을 숨기기 3.7.4 커밋-공개 validators의 일반적인 문제 중 하나는 validator이 상태 다운로드와 실제로 청크 및 블록 유효성 검사를 건너뛸 수 있다는 것입니다. 네트워크를 관찰하고 다른 validator이 제출한 내용을 확인하고 반복하세요. 메시지. 이러한 전략을 따르는 validator은 추가 기능을 제공하지 않습니다. 네트워크 보안을 강화하지만 보상을 수집합니다. 이 문제에 대한 일반적인 해결책은 각 validator이 증거를 제공하는 것입니다. 예를 들어 고유한 추적을 제공하여 실제로 블록의 유효성을 검사했습니다. 상태 전이를 적용하는 방법이 있지만 그러한 증명은 비용을 상당히 증가시킵니다. 검증의. 그림 25: 커밋-공개
대신 우리는 검증 결과에 대해 validators의 첫 번째 커밋을 만듭니다(둘 중 하나). 청크의 유효성을 증명하는 메시지 또는 유효하지 않은 청크의 증거 상태 전환), 일정 기간 동안 기다렸다가 그림 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은 새로운 샤드 할당을 받고 새로운 시대가 예약됩니다. 모든 validator가 다운로드하기에 충분한 시간이 지난 후에 시작하려면 상태는 그림 26과 같습니다. validators가 할당된 샤드를 공개하는 순간부터 참고하세요. 새로운 시대가 시작될 때까지 시스템의 보안은 샤드 할당이 공개되었습니다. 네트워크 참여자는 이를 유지해야 합니다. 해당 기간 동안 네트워크를 사용할 때 주의하세요. 3.8 서명 집계 수백 개의 샤드가 있는 시스템이 안전하게 작동하려면 다음을 수행해야 합니다. 10,000개 이상의 validator 주문. 섹션 3.7에서 논의한 것처럼 우리는 각각을 원합니다.그림 26: 과제 처리 validator 평균적으로 특정 메시지와 서명에 대한 커밋을 게시합니다. 블록당 한 번. 커밋 메시지가 동일하더라도 BLS 서명과 이를 검증하는 것은 엄청나게 비용이 많이 들었습니다. 하지만 당연히 커밋 및 공개 메시지는 validator에서 동일하지 않습니다. 따라서 그러한 메시지와 서명을 통합할 수 있는 방법이 필요합니다. 나중에 빠르게 검증할 수 있는 방법입니다. 우리가 사용하는 구체적인 접근 방식은 다음과 같습니다. 블록 생산자에 합류하는 검증인. 블록 생산자는 알려져 있습니다. 에포크가 시작되기 얼마 전에 다운로드할 시간이 필요하기 때문입니다. 에포크가 시작되기 전의 상태이며, validator과 달리 블록 생산자는 숨겨져 있지 않습니다. 각 블록 생산자는 v validator 슬롯을 갖습니다. 검증인이 제출 블록 생산자에게 v 중 하나로 포함되도록 오프체인 제안 validators. 블록 생산자가 validator을 포함하려는 경우 validator의 초기 오프체인 요청을 포함하는 트랜잭션, 그리고 validator을 블록 생산자에 참여시키는 블록 생산자의 서명입니다. 블록 생산자에게 할당된 validator이 반드시 필요한 것은 아닙니다. 블록 생산자가 청크를 생성하는 것과 동일한 샤드를 검증합니다. 만약 validator은 여러 블록 생산자에 합류하기 위해 적용되었으며, 첫 번째 블록 생산자가 성공할 것입니다. 블록 생산자는 커밋을 수집합니다. 블록 생산자는 validator에서 지속적으로 커밋 및 공개 메시지를 수집합니다. 이러한 메시지가 일정 개수 누적되면 블록 생산자는 머클을 계산합니다. 이러한 메시지의 트리를 만들고 각 validator에 머클 루트와 그들의 메시지에 대한 머클 경로. validator는 경로의 유효성을 검사하고 로그인합니다. 머클 루트. 그런 다음 블록 생산자는 BLS 서명을 블록에 축적합니다. validators의 머클 루트이며 머클 루트와 누적된 서명. 블록 생산자는 또한 해당 블록의 유효성에 서명합니다. 저렴한 ECDSA 서명을 사용하는 다중 서명. 다중 서명이 되지 않는 경우 제출된 머클 루트 또는 참여하는 validator의 비트마스크와 일치하면 슬래시 가능한 동작입니다. 체인을 동기화할 때 참가자는 validators의 모든 BLS 서명을 검증하도록 선택할 수 있습니다(validators 공개 키 집계가 포함되므로 매우 비쌉니다).블록 생산자의 ECDMA 서명을 사용하고 다음 사실에 의존합니다. 블록 프로듀서는 도전을 받고 삭감되지 않았습니다. 온체인 트랜잭션과 머클 증명을 사용하여 문제를 해결합니다. 그것 validators의 메시지가 없으면 공개할 가치가 없다는 점을 알 수 있습니다. 잘못된 상태 전환이 감지되었습니다. 실제 내용이 포함된 메시지만 유효하지 않은 상태 전환에 대한 증거가 공개되어야 하며, 그러한 메시지에 대해서만 이전 커밋과 일치하는지 표시해야 합니다. 메시지는 다음과 같습니다. 두 가지 목적으로 공개됩니다. 1. 실제로 체인의 롤백을 시작하기 전 순간으로 잘못된 상태 전환(섹션 3.7.5 참조). 2. validator이(가) 유효성을 증명하려고 시도하지 않았음을 증명하기 위해 잘못된 청크. 두 경우 모두 다음 두 가지 문제를 해결해야 합니다. 1. 실제 커밋은 체인에 포함되지 않았고 머클 루트만 포함되었습니다. 다른 메시지와 함께 집계된 커밋입니다. validator에서는 다음을 사용해야 합니다. 블록 생산자가 제공한 머클 경로와 원래 커밋 그들이 도전에 전념했음을 증명하십시오. 2. 잘못된 샤드에 할당된 모든 validator이(가) 가능합니다. 상태 전환은 손상된 블록 생산자에게 할당됩니다. 그들을 검열하고 있습니다. 이 문제를 해결하기 위해 우리는 그들이 공개 내용을 제출하도록 허용합니다. 온체인에서 일반 트랜잭션으로 처리하고 집계를 우회합니다. 후자는 유효하지 않은 상태 전환 증명에만 허용됩니다. 극히 드물기 때문에 블록에 스팸을 보내서는 안 됩니다. 해결해야 할 마지막 문제는 블록 생산자가 다음을 수행할 수 있다는 것입니다. 메시지 집계에 참여하지 않거나 특정 validator을 의도적으로 검열하지 않도록 선택하세요. 블록을 만들어 경제적으로 불리하게 만듭니다. 생산자 보상은 할당된 validator 수에 비례합니다. 우리 또한 시대 사이의 블록 생산자는 대체로 교차하기 때문에(이후 항상 가장 높은 지분을 가진 참가자 중 최고입니다.) validators는 대부분 동일한 블록 생산자와 협력하여 위험을 줄입니다. 과거에 그들을 검열했던 블록 생산자에게 배정되는 것입니다. 3.9 스냅샷 체인 메인체인의 블록은 매우 빈번하게 생성되기 때문에 다운로드가 전체 기록은 매우 빠르게 비용이 높아질 수 있습니다. 게다가 매 순간부터 블록에는 다수의 참가자의 BLS 서명이 포함되어 있으므로 서명을 확인하기 위한 공개 키의 집합이 엄청나게 커질 수 있습니다. 비싸기도 하고. 마지막으로, 가까운 미래에는 Ethereum 1.0이 1로 남을 가능성이 높기 때문입니다. 가장 많이 사용되는 blockchain 중 자산을 전송하는 의미 있는 방법이 있습니다.
Ethereum에 가까운 것이 요구 사항이며 오늘 BLS 서명을 확인하여 Ethereum 측의 근거리 차단 유효성은 불가능합니다. Nightshade 메인 체인의 각 블록은 선택적으로 Schnorr를 포함할 수 있습니다. 그러한 Schnorr를 포함하는 마지막 블록의 헤더에 다중 서명 다중 서명. 우리는 이러한 블록을 스냅샷 블록이라고 부릅니다. 가장 첫 번째 블록은 모든 에포크는 스냅샷 블록이어야 합니다. 이런 다중서명 작업을 하면서, 블록 생산자는 validators의 BLS 서명도 축적해야 합니다. 마지막 스냅샷 블록에서 설명된 것과 동일한 방식으로 집계합니다. 섹션 3.8. 블록 생산자 세트는 시대 전반에 걸쳐 일정하므로 유효성을 검사합니다. 각 에포크의 첫 번째 스냅샷 블록만 있으면 충분합니다. 많은 비율의 블록 생산자와 validator이 공모하고 생성되었다는 점을 지적합니다. 포크. 에포크의 첫 번째 블록에는 다음을 계산하기에 충분한 정보가 포함되어야 합니다. 해당 시대의 블록 생산자와 validator. 스냅샷만 포함된 메인체인의 서브체인을 호출합니다. 스냅샷 체인을 차단합니다. Schnorr 다중 서명을 생성하는 것은 대화형 프로세스이지만, 아무리 비효율적이라도 프로세스를 가끔씩만 수행하면 됩니다. 성공할 것이다. Schnorr 다중 서명은 Ethereum에서 쉽게 검증할 수 있습니다. 따라서 blockchain 교차 수행의 안전한 방법을 위한 중요한 기본 요소를 제공합니다. 의사소통. Near 체인과 동기화하려면 모든 스냅샷만 다운로드하면 됩니다. 차단하고 Schnorr 서명이 올바른지 확인한 다음(선택적으로 validators의 개별 BLS 서명도 확인) 동기화만 수행합니다. 마지막 스냅샷 블록의 메인 체인 블록.
结论
在本文档中，我们讨论了构建分片 blockchain 的方法和 克服了现有方法的两个主要挑战，即状态有效性 和数据可用性。然后我们提出了 Nightshade，一种分片设计 赋予 NEAR 协议权力。 设计正在进行中，如果您有意见、问题或反馈 对于本文档，请转至 https://near.chat.
결론
이 문서에서 우리는 샤딩된 blockchain을 구축하는 방법과 기존 접근 방식의 두 가지 주요 문제, 즉 상태 타당성을 다루었습니다. 및 데이터 가용성. 그런 다음 샤딩 디자인인 Nightshade를 선보였습니다. NEAR 프로토콜에 힘을 실어줍니다. 디자인 작업이 진행 중입니다. 의견, 질문 또는 피드백이 있는 경우 이 문서에서 https://near.chat.로 이동하세요.