区块链100讲:总被提起的拜占庭问题到底是什么鬼?

2023-10-08 21:10

本文主要是介绍区块链100讲:总被提起的拜占庭问题到底是什么鬼?,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

image

接触区块链的同学,多少都听说过拜占庭将军问题,经常看到或听到:某某区块链使用某某算法解决了拜占庭将军问题,那么究竟什么是拜占庭将军问题呢?《区块链100讲》今天和大家说说什么是拜占庭将军问题。

1

拜占庭将军问题

这个问题是莱斯利·兰伯特(Leslie Lamport)等在论文The Byzantine Generals Problem论文提出的,部分原文如下:

We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement.

它是描述分布式系统一致性问题的著名例子。通过直译这个论文来理解这个问题还是比较困难,可以适当的补充或者添加一些说明来更好地解读。

设想在中世纪,拜占庭帝国拥有巨大的财富,周围邻邦垂诞已久。但拜占庭高墙耸立,固若金汤,没有一个单独的邻邦能够成功入侵。任何单个邻邦入侵的都会失败,同时也有可能自身被其他邻邦入侵。拜占庭帝国防御能力如此之强,至少要有一半以上邻邦同时进攻,才有可能攻破。

然而,如果其中的一个或者几个邻邦本身答应好一起进攻,但实际过程出现背叛,那么入侵者可能都会被歼灭。于是每一方都小心行事,不敢轻易相信邻国。(其实这与原文所描述有些偏差,但这样说更易于理解)

在拜占庭问题里,各邻国最重要的事情是:所有将军如何能过达成共识去攻打拜占庭帝国。

image

达成共识并非坐下来开个会那么简单,有的将军心机深不可测,口是心非,如果有叛徒,可能会出现各种问题:

  • 叛徒可能欺骗某些将军自己将采取进攻行动。

  • 叛徒可能怂恿其他将军行动。

  • 叛徒可能迷惑其他将军,使他们接受不一致的信息,从而感到迷惑。

我们这里假设:

有A、B、C三位将军,当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的是“撤退”的命令。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。

如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了“进攻”的命令,而无法与C保持一致。

叛徒发送前后不一致的进攻提议,被称为“拜占庭错误”,而能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」,简称为BFT

相信大家已经可以明白这个问题的复杂性了。

正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。

2

拜占庭将军问题的实质

回顾问题,一群将军想要实现某一个目标(一致进攻或者一致撤退),但是单独行动行不通,必须合作, 达成共识;由于叛徒的存在,将军们不知道应该如何达到一致。

注意,这里“一致性”才是拜占庭将军问题探讨的内容,如果本来叛徒数量就已经多到了问题不可解的地步,这个就是“反叛”的问题了;同时,我们的目标是忠诚的将军能够达成一致,对于这些忠诚的将军来说,进攻或者撤退都是可以的,只要他们能够达成一致就行。

但是,光靠“一致”就可以解决问题吗?考虑一下,如果万事俱备,客观上每个忠诚的将军只要进攻了就一定能够胜利,但是却因为叛徒的存在他们都“一致的”没有进攻;反之,条件不利,将军们不应该进攻,但是却因为叛徒的存在所有人都“一致的”进攻了。

可以发现,只有“一致性”是不足以解决拜占庭将军问题的,我们还需要提出一个“正确性”要求。这个要求是值得斟酌的,因为如果客观来看或许会有“绝对正确的”判断,但是针对每一个将军,大家的判断或许都不相同,我们如何定义“正确”呢?我们或许可以简单地说,正确就是每个忠诚的将军都正确的表达了自己的意思,不会因为叛徒让别的将军认为忠诚的将军是叛徒而不采用他传达的消息。

至此,我们将拜占庭将军问题简化成了,所有忠诚的将军都能够让别的将军接收到自己的真实意图,并最终一致行动;而形式化的要求就是,“一致性”与“正确性”。

如果将问题推广开来,可以发现针对一致性和正确性的算法并不要求命令必须是“进攻/撤退”或是“1/0”,而可以是“发送消息1/发送消息2/待机”或“x/y/z/w”,这意味着拜占庭将军问题算法可以为多种分布式系统提供启发,比如电力系统或网络系统。

由此可见,这个问题说到底是一个关于一致性和正确性的算法问题,这个算法是针对的是忠诚的将军,因为叛徒可以做出任何超出约定的判断。我们就是要在有叛徒的干扰下,找到一个抗干扰的算法。

3

中本聪的解决方案

这个问题困扰了科学家们数十年,直到区块链的出现。

现在让我们想象一下,给每个将军配备一台电脑(相当于分布式的节点),降低信息流通成本,让信息在极短的时间同步到各位将军。

同时,为了避免信息混乱,一段时间内只能有一位将军发送信息。

怎么来确定哪位将军发送信息呢?区块链系统一般通过工作量证明(POW)来确定谁先发言。(工作量证明将在后续文章介绍)

我们可以想象这是一个数独游戏,哪个将军最先解出来,谁就有权先发送信息。一般,数独的行与列可以增删,通过难度的调整保证这个一段时间是一个比较确定的数值。在比特币系统上,这个数字就是10分钟,也就是说比特币平均约每10分钟产生一个区块。

当某个节点发出统一进攻或者撤退的消息后,各个节点收到发起者的消息必须签名盖章,确认各自的身份。比特币在这里引用现代非对称加密技术为这个信息签名。

这个过程就像一位将军A在向其他的将军(B、C、D…)发起一个进攻提议一样,将军B、C、D…看到将军A签过名的进攻提议书,如果是诚实的将军就会立刻同意进攻提议,而不会发起自己新的进攻提议。

非对称加密算法的加密和解密使用不同的两个密钥,这两个密钥就是我们经常听到的公钥和私钥。一般公钥是公开的,用于加密。而私钥是用来解密公钥获取信息的。比如,将军A想给将军B发送消息,为防止消息泄露,将军A只需要使用B的公钥对信息加密,加密的信息只能用B私钥解密。(非对称加密算法将在后续文章介绍)

除了加密信息外,同时,信息经过每个节点都将进行备份,每个节点都保存了相同的完整数据,以防止少数叛徒篡改。

好了,我们再来重新走下一下整个过程:

每个将军分配了一台电脑,A将军第一个解出数独游戏拥有了第一个发言权,A发出攻打的信息,并立即广播至所有将军,所有人可以根据A的公钥来验证A的身份,确保信息的可信性,并发出自己赞成或反对的选票,在全网验证后得出结果。

于是,一个不可信的信息传递,就变成了一个分布式的可信网络,参与者都有权发表意见,并在一件事上达成一致。

拜占庭将军问题也就得到了解决,文章开头的问题相信你也已经有了答案。本期就讲到这里,下期继续。

本文内容来源于:百度百科、巴比特、币行观察等

以下是我们的社区介绍,欢迎各种合作、交流、学习:)

image

这篇关于区块链100讲:总被提起的拜占庭问题到底是什么鬼?的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/167986

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

【区块链 + 人才服务】可信教育区块链治理系统 | FISCO BCOS应用案例

伴随着区块链技术的不断完善,其在教育信息化中的应用也在持续发展。利用区块链数据共识、不可篡改的特性, 将与教育相关的数据要素在区块链上进行存证确权,在确保数据可信的前提下,促进教育的公平、透明、开放,为教育教学质量提升赋能,实现教育数据的安全共享、高等教育体系的智慧治理。 可信教育区块链治理系统的顶层治理架构由教育部、高校、企业、学生等多方角色共同参与建设、维护,支撑教育资源共享、教学质量评估、

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【区块链 + 人才服务】区块链集成开发平台 | FISCO BCOS应用案例

随着区块链技术的快速发展,越来越多的企业开始将其应用于实际业务中。然而,区块链技术的专业性使得其集成开发成为一项挑战。针对此,广东中创智慧科技有限公司基于国产开源联盟链 FISCO BCOS 推出了区块链集成开发平台。该平台基于区块链技术,提供一套全面的区块链开发工具和开发环境,支持开发者快速开发和部署区块链应用。此外,该平台还可以提供一套全面的区块链开发教程和文档,帮助开发者快速上手区块链开发。

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo

题目1254:N皇后问题

题目1254:N皇后问题 时间限制:1 秒 内存限制:128 兆 特殊判题:否 题目描述: N皇后问题,即在N*N的方格棋盘内放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在同一斜线上。因为皇后可以直走,横走和斜走如下图)。 你的任务是,对于给定的N,求出有多少种合法的放置方法。输出N皇后问题所有不同的摆放情况个数。 输入

vscode中文乱码问题,注释,终端,调试乱码一劳永逸版

忘记咋回事突然出现了乱码问题,很多方法都试了,注释乱码解决了,终端又乱码,调试窗口也乱码,最后经过本人不懈努力,终于全部解决了,现在分享给大家我的方法。 乱码的原因是各个地方用的编码格式不统一,所以把他们设成统一的utf8. 1.电脑的编码格式 开始-设置-时间和语言-语言和区域 管理语言设置-更改系统区域设置-勾选Bata版:使用utf8-确定-然后按指示重启 2.vscode