白话区块链2-两军问题
发布于 2 个月前 作者 kidezyq 152 次浏览 来自 技术/人物

两军问题

    百度百科中说两军问题一般指拜占庭将军问题,其实非也。两军问题其实是讨论拜占庭将军问题之前需要了解的,接下来我们就来细细说道说道。

问题描述:

    假设现在有三支军队A、B、C(注意这里是3支军队)。其中A和B属于同一个国家,他们想要进攻C。C虽然招架不住A和B同时进攻,但如果A和B单独进攻,都不是C的对手。
    A和B之间只能靠信使进行通讯,但是呢C在A和B的通讯道路中间,不论A给B传递消息还是B给A传递消息,信使都有可能被C抓获而被处死。
    那么问题来了:**有没有一种通讯的方式,可以实现A和B最终达成一起进攻的时间点,从而取的战争的胜利**?
    ![两军问题.png](/public/upload/40db5b828b506c3f2ad82bc8470e24c1.png)

结论:

    很抱歉,结论就是没有办法达成想要的结果。

分析:

    假设是A首先看C不爽,首先写了一封信:二狗,二狗,明天13:15分进攻C,然后把信交给信使。
    此时站在A的角度,必须确认B收到了这条消息,才能发起进攻。
    那么A怎么确认这条消息B收到了呢?B得给A应答。
    于是B就得写一封回信:报告大福,二狗收到!然后也把信交给信使。
    假设信使同样很顺利地将回信送给了A,此时A是否能发起进攻了呢?
    其实还是是不能,至于为什么,这次我们得站在B的角度思考问题。B不能确定A是否已经收到他的回信,假设B给A的回信A没有收到,
    A因为没有收到B的回信,所以不会进攻。此时如果B贸然发起进攻,则必输无疑。所以同理B也要确认他的回信被A收到,才会发起攻击。
    于是乎A就需要再给B回信,A给B的回信不确认B是否收到,同样B又需要再给A回信......
    于是乎,我们就进入了死循环。A和B在不停地回信中被C给歼灭。

证明:

    证明的过程很简单,可以直接用反证法证明。假设存在一个最小的通讯序列A1B1A2B2..AnBn使得大福和二狗最终达成一致进攻时间点。那么取这个消息序列的最后一个Bn,因为
 Bn可能会丢失,这就导致最小的通讯序列根本没法保证,也就是有解和消息可能丢失是互相矛盾的。

意义:

在互联网的世界里,两军问题可以看做是网络上的两个节点,如何在通信渠道不可靠的情况下,确保对方收到消息,最终对消息达成共识。
    网络科学家和计算机科学家研究这个问题,其实就是向现代网络各种通讯协议的诞生迈开了第一步。

工程实践:

    TCP协议建立连接的三次握手过程,可以看做是两军问题在实际工程中的一个比较好的解决办法。具体步骤如下:
    1. 首先A给B发送一个SYN消息和一个序列号w,表示我想和你建立连接。
    2. B收到这个消息后,会给A回复一个ACK消息和一个序列号w+1,同时B也想和A建立连接,所以B也会给A发送一个SYN消息和一个序列号k
       A收到B回复的ACK消息后,会检查其中的序列号是否为w+1,如果为w+1则确认B确实收到了A之前发送的消息。同时A发现B发送的消息中也有SYN消息,也是A也会给B回复确认收到的消息
    3. A回复给B ACK消息和序列号k+1 (这一阶段也可以携带需要传递的其他信息)
    具体的过程可以见下图:
    ![tcp三次握手.gif](/public/upload/cc9b1ff624ba603e7ddbde1d24d66931.gif)
    
    
    为什么说TCP的三次握手比较完美地解决了两军问题呢?
    首先TCP的三次握手解决两军问题的出发点在于:A和B只需要收到对方对自己发送信息的一次确认就结束整个反馈过程,而不是像上面分析的那样无限循环下去。
    另外TCP为了解决发送信息可能丢失的问题,在每一步都有重传机制。而重传的信息的顺序,就是通过上面所说的顺序号来保证的。

百万富翁问题续:

    上一篇的最后留了一个百万富翁问题(https://www.insightcj.com/topic/609d51454c5a8e001f28ff92#609dc1174c5a8e001f2903c8)。这个问题其实是我国第一个图灵奖获得者姚期智1982年提出来的(清华的姚班也是以他的名字命名的)。
	
	这个姚期智还和Conflux有一定渊源,有兴趣的话大家可以去搜下。其实姚大神提出这个问题是为了解决安全多方计算问题。姚期智在给出这个问题之后,还给出了对应的算法。这里不会列出姚期智的算法。讲一个易于理解的解法:
    *首先我们假设两个富翁分别A和B,且A有i亿,B有j亿,且 (1< i, j <= 10)。我们可以这样处理,先准备10个信封和一个密室。首先A进去给10个信封分别贴上1到10十个标签,表示代表对应的资产(亿),并且在信封内的信纸上写字,写字的规则如下:
对于小于A财产的数字写上:<,对于等于A财产的写上:=,大于A财产的写上:>。然后将信纸装进去,信封密封好,A离开密室。之后通知B来到密室,B需要将不是代表他财产的信封当场烧毁,然后将代表他资产的信封外面的标签撕掉。
这时候,B再唤A一起进到密室打开信封。如果信封内的信纸上写的:<,则证明B的资产小于A的资产。如果信封内的信纸上写的:=,则证明A和B资产相等。如果写的:>,则证明B的资产大于A的资产。*
    是不是很神奇?A和B知道了谁更富有,但是都没有明确告知各自的实际资产!
1 回复

来回帖了,新帖才有积分哦,这个旧的不算

回到顶部