DAOrayaki DAO研究奖金池：
资助地址: DAOrayaki.eth
投票进展：DAO Reviewer 1/0 通 过
赏金总量：35 USD
研究种类：Quantum Computing, Qubits, Bayes
原文作者: Pierre Decoodt
创作者：SueT@DAOrayaki.org
审核者：Tan Zhi Xuan@DAOrayaki.org
原文: Byzantine Generals Turn to Bayes
该协议是从他们的相互信任程度推断出来的。
https://medium.com/geekculture/byzantine-generals-turn-to-bayes-b76a695b124e
在之前的文章中，我描述了一个解决四方拜占庭将军问题的量子协议，并有能力揭露最多两个叛徒。
没有考虑到的一个事实是，各方可能对他人的忠诚度有不同的看法。在分布式计算系统的协调问题中，远处的服务器可能比接收组件更频繁地发生故障。或者相反，服务器可能很少发生故障，而其他组件容易出错。在另一个领域，区块链验证，每一方都可以选择基于工作证明或股权证明的先验信念。
在拜占庭协议的量子解决方案中，指挥部在传递信息的同时，还提供了一份索引清单，供中尉们在追捕叛徒时使用。在理想的无噪音量子系统中，这些指数对应于各方拥有的完全相关的数值。
然而，噪音在量子系统中是不可避免的（参见 Zlatko Minev 最近的评论，第 1 部分和第 2 部分）。当重复测量高度纠缠态时，观察到的经典结果的分布由量子态向量控制，但受噪音影响。
对于一个假设的无噪音量子系统，事情很简单。在追捕叛徒的过程中，一位诚实的中尉从指挥部那里收到了错误的命令，但并没有犯任何错误。一个叛逆的中尉反复犯错误。随着噪音出现，诚实的中尉开始犯错误，而叛徒犯的错误则更多。随着噪音的增加，诚实者和叛徒之间的区别变得越来越困难。解决这个问题的一种方法是使用贝叶斯推理，这将在下面演示。这还将表明，贝叶斯定理的扩展形式可以考虑中尉的先验信念。
Adán Cabello 也将三通用拜占庭协议的量子解决方案称为“骗子检测问题”，已在真实的光子量子系统上得到证明。最近，Zoltán Guba 等人证明了它在嘈杂的中尺度量子 (NISQ) 设备上的可行性。
这是在最近添加到 IBM Quantum 计算资源中的 ibm-oslo 系统上运行的贝叶斯量子四则用运算方案的演示。发射次数（副本）为 8192。与我之前尝试的 5 量子比特系统不同，7 量子位 ibm-oslo 允许在所有可能的情况下检测叛徒。主要软件是用于 Python 编程的开源 Qiskit 包。让我们快速回顾一下我之前文章中描述的不同阶段，强调最终贝叶斯拜占庭协议的要点。
纠缠的量子比特的分布
量子比特五胞胎纠缠在一起，通过量子通道发送，并在本地进行测量。指挥部接收两个量子比特，每个中尉接收一个量子比特。测量后，各方都有一个有序的比特串列表。应用了“拜占庭缓解”。这减少了两个可能是 Alice 的指令的噪音水平差异。它包括用列表中的偶数索引翻转每个比特串。
当然，我们可以摆脱所有这些量子的东西。结果的分配可以委托给一个独立的机构，该机构将通过安全的经典渠道发送等效的模拟完美列表。但是，窃听者可以拦截和篡改数据。或者机构内的内奸可以复制 Alice 的名单并将其传递给叛徒中尉。
协议的量子部分避免了这种危险。付出的代价是噪音：对于一些五胞胎，没有达到预期的相关性。这就是贝叶斯方法将显示其有效性的地方。
检查纠缠情况
请记住，在这个阶段，每个列表只有其所有者知道。Alice 的名单大约是 ⅓ of ‘00’ （撤退）、⅓ of ‘11’（攻击）、 ⅓ of ‘01’ or ‘10’（陷阱）。一个中尉的名单由大约五十个 “1”（撤退）和 “0”（进攻）组成。
各方将随机抽取的一小部分经典结果用于检查。这构成了“试验数据集”。每一方都将她/他的剩余“游戏数据集”保密以备后用。
各方验证试验数据中的比特串分布是否合理地接近假设的无噪音系统的理想分布。为此，一个可能指标是经典的 Hellinger 保真度。如果这个检查失败，则协议中止。
在 ibm-oslo 中获得的经典结果的直方图。将试验数据的分布与理想分布进行比较，Hellinger 的保真度为 49%……而且它奏效了！图片由作者提供
此外，试验数据集允许对后来在追捕叛徒期间预期的每一次交换的错误进行估计。各方模拟每种可能性。他们获得了一个发生率表，该表定义了与每个案例相关的超几何分布的参数。由于拜占庭式的缓解，这些值可以汇集在两个可能的 Alice 的订单中。
发送订单
Alice 发送的命令（攻击或撤退）伴随着一组匹配的索引 Sₗ。按照惯例，一个集合的长度为 N，其中 N ≪ 游戏数据集中的副本数。如果 Alice 是诚实的，她应该向所有各方发送相同的集合。如果她是叛徒，她将向其中一名中尉发出不合群的命令，及其匹配的集合。
贝叶斯拜占庭协议
中尉们互相交流他们声称自己收到的命令。两个有相同主张的中尉不会在狩猎中面对面。相反，他们将轮流抽取并发送从 Alice 那里收到的列表索引。如果某些索引在两个列表中不通用，它们就会发出不一致的信号，协议就会中止。
两名声称不一致的中尉参与了一场游戏，玩家轮流发送索引。拒绝上场的中尉表明他在撒谎。
发送的索引必须在接收者列表中指向发送者声明的期望值。每个玩家计算对手在 N 次运行中犯错的次数 x。
叛徒无法获得所提出的声明的正确索引集。他必须在更大的集合 Sₐ 中抽取，即与 Sₗ 互补的集合。否则，他就会自我出卖。叛徒排除了不好的候选者，即 Sₐ 中不对应于要求的索引。然而，错误 x 的数量无论如何都会比诚实的要高：叛徒没有办法知道剩下的索引中有哪些是对应于原来 Alice 列表中的陷阱的。
在游戏结束时，玩家使用贝叶斯方法来解释结果。中尉的初始信念程度包括统计几率 oₐ ，其支持指挥部是叛徒而不是对面的中尉。反对的几率是oₗ，oₗ×oₐ=1。那么，相关的先验概率是 P(A) = oₐ / (oₐ + 1)。对面的中尉是叛徒的先验概率是 P(¬A) = 1 - P(A)。
现在让我们表示 P(B)，即在 N 次运行中观察到 x 个错误的概率。从试验数据集中，诚实的中尉从发生率表中得到分别为 Mₗ 和 Mₐ 交换预期的错误数 nₗ（如果面对叛徒）和 nₐ（否则）。观察到 x 个错误后，这位中尉使用开放访问 scipy stats 离散超几何模块来估计条件概率：
- P(B|A) = 超几何分布(Mₐ, nₐ, N).pmf(x)
- P(B|¬A) = 超几何分布(Mₗ, nₗ, N).pmf(x)
诚实的中尉使用贝叶斯推理来计算后验概率：
p(a|b) = p(b|a) × p(a) / { p(b|a) × p(a) + p(b|¬a) × p(¬a) }
对于 P(A|B)> ½ 的情况，诚实的中尉断定对手是诚实的，对于 P(A|B)< ½ 的情况，则断定对手是叛徒。
下面是两个猎杀叛徒的例子。你能暂停阅读，找出每个例子中有多少叛徒以及分别是谁吗？假设所有游戏中的赔率比都是 1:1。解决方案将在下一节中介绍。
提示：你不必计算概率，只要遵循逻辑推理。
从这里可以看出，将揭示两个示例的解决方案！
在第一个示例中，Bob 和 Dave 相互测试，并知道他们都是诚实的。但是 Dave 在测试 Carol 时发现她是个叛徒。Carol 的结论是 Dave 是诚实，这与最终协议无关，因为叛徒没有发言权。Bob 和 Dave 会遵循 Alice 发送的不同命令吗？当然不会，因为他们知道她也是叛徒，因为相反的命令已经到来。但是对于四指挥部协议，有一个优雅的解决方案：要成为一个有效的叛徒，Alice 只需欺骗一个中尉，此例子里是 Bob，因为骗子 Carol 声称收到了与 Bob 相同的命令。因此，和 Dave 一起，Bob 将遵循 Dave 从 Alice 那里收到的真实命令。
在第二个示例中，当 Carol 测试 Bob 和 Dave 时，她发现他们都是叛徒。当 Bob 和 Dave 测试 Carol 时，他们发现她很诚实（又是无关的叛徒目击事件）。如果 Carol 没有先入为主的想法，她会按照拜占庭式容错中的要求，遵循 Alice 收到的命令。
后一个示例中的另一个场景可以说明一个可能的问题。Carol 对 Bob 和 Dave 过度信任。受她的两个同事的影响，她对 Alice 非常怀疑。让 Alice 下令攻击。Bob 和 Dave 将设法通过对 Carol 撒谎来让 Alice 出局。事实上，使用 P(A) ≫ P(¬A) 的值，Carol 推断出 Alice 是叛徒。三名中尉开始撤退。通过更改我的 Jupyter 笔记本中的先验概率可以轻松模拟这种情况（请注意，如果 Alice 是叛徒并且所有中尉都是无辜的，那么将达成相同的协议，并且这次是正确的）。
还有一些镜像案例，过度信任指挥部可能会给无辜的中尉带来厄运。
这些问题可以通过递归贝叶斯更新来避免，如果将此类协议应用于分布式计算系统，则应考虑这一点。
结语
在一个概念验证中，使用七量子比特 NISQ 系统成功地实现了对四指挥部拜占庭协议的贝叶斯量子解决方案。
该解决方案考虑了中尉之间以及对指挥部的信任程度。在检查纠缠时，通过模拟所有可能的情况进行详细的噪声分析，从而提高性能。在此阶段，将制定一个错误发生表，这将有助于发现叛徒。因此，噪音的影响被最小化，并且可以更有信心地实现贝叶斯拜占庭协议。
有两名以上中尉的协议的一个好处是，当指挥部有问题时，可以达成共识。即使一名中尉也有问题，也会出现这种情况。
我承认使用 IBM Quantum 服务进行硬件测试。所表达的观点是作者的观点，并不反映 IBM 或 IBM Quantum 团队的官方政策或立场。
参考文献：
1.第 1 部分：
https://learn.qiskit.org/summer-school/2021/lec3-1-noise-quantum-computers-1
2.第 2 部分：
https://learn.qiskit.org/summer-school/2021/lec3-2-noise-quantum-computers-pt-2
3.贝叶斯推理：
https://en.wikipedia.org/wiki/Bayes'_theorem#Extended_form
4.骗子检测问题：https://arxiv.org/pdf/quant-ph/0210079.pdf
5.已在真实的光子量子系统上得到证明：https://arxiv.org/pdf/0710.0290v2.pdf
6.可行性：https://arxiv.org/pdf/2207.04939.pdf
7.IBM Quantum：
https://www.ibm.com/quantum
8.Qiskit：https://qiskit.org/
9.之前文章：
https://medium.com/geekculture/byzantine-generals-turn-to-quantum-ab81bd938cc2
10.scipy stats 离散超几何模块：
https://docs.scipy.org/doc/scipy/tutorial/stats/discrete_hypergeom.html
11.我的 Jupyter 笔记本：
https://github.com/pdc-quantum/byzantine-generals-in-qiskit/blob/main/wip-bayesian-byzantine-agreement.ipynb
通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容，瓜分10000USDC赏金池！欢迎加入DAOrayaki社区，了解去中心化自治组织（DAO），探讨最新话题！
Media：https://media.daorayaki.org
Discord server: https://discord.gg/wNUPmsGsa4
Medium: https://medium.com/@daorayaki
Email: daorayaki@dorafactory.org
Twitter: @daorayaki_
微信助手：DAOrayaki-Media
小宇宙：DAOrayaki
详情请参考：
Dora Factory支持去中心化DAO研究组织DAOrayaki
DAOrayaki ｜DAOrayaki 开启去中心化治理2.0时代
DAOrayaki ｜风险投资的范式转移：无限主义基金和无限游戏
DAOrayaki ｜DAOrayaki dGov 模型：基于Futarchy的正和游戏
更多关于DAO的文章，关注Dorafactory，查看往期文章。
