蔡誌遠繼續解釋道:
“比如,現在一共有五名將軍,其中兩名將軍認為應該進攻,而另外兩名將軍認為應該撤退。“這時候,第五名將軍是個叛徒,他告訴進攻的將軍『我也會進攻』,又告訴撤退的將軍『我也會撤退』。
“於是,想要進攻的將軍認為,現在有三支軍隊同意進攻,超過了半數,所以明天應該進攻。“而想要撤退的將軍認為明天應該撤退。
“最後的結果,就是兩個將軍進攻,兩個將軍撤退,導致戰爭失敗。
“這就是『去中心化』所帶來的問題,因為這五個將軍都是平級的,沒有一個擁有絕對權限的指揮者,所以在互相商量策略的過程中,就會產生這樣的問題。”
鄭傑恍然點頭:“原來如此!那這個辦法怎解決呢?也沒辦法驗證具體是哪個將軍在說謊吧?”蔡誌遠解釋道:“其實要解決這個問題很簡單:多問幾遍就行了。
“假設我是其中一名將軍A,而將軍B告訴我他要和我一起進攻。
“如果我信了,那就有可能會被騙,因為將軍B有可能是叛徒,他可能隻跟我說了進攻,跟別人說了撤退。
“所以,這時候我應該再去問將軍C,我問他:“將軍B跟你說的是進攻還是撤退?’
“然後我再去挨個問其他所有的將軍,匯總將軍B給他們說的所有信息。
“其他將軍告訴我的『將軍B給他們的信息』也不一定真實,因為其他將軍麵可能也有叛徒,可能存在『將軍B跟他們說進攻,他們卻告訴我將軍B說了撤退』這種情況。
“所以,我挨個問一遍『將軍B對你們說了什」,如果『進攻』比較多,那我就把將軍B的意見記為『進攻』;
“然後再挨個問一遍『將軍C對你們說了什」,如果『撤退』比較多,那我就把將軍C的意見記為『撤退』。
“就這樣,我通過反複套娃的方式,不斷地排除少數派答案,最後得出的結論,就是更準確的『多數派答案』。
“在滿足『拜占庭容錯』的情況下,我們強製要求所有將軍都遵守這一套策略,並且必須堅決執行最終的結論。
“那我們就可以確保大家一起進攻或者一起撤退。”
鄭傑有些困惑:“在滿足『拜占庭容錯』的情況下?也就是蔡哥你之前說過的,叛徒人數必須少於三分之一?”
蔡誌遠點了點頭:“是的。
“我們用3名將軍的情況來舉個例子:
“假設3名將軍麵,將軍C是叛徒,故意傳遞錯誤的信息。
“將軍A會首先向將軍B和C說『進攻』。
“但是將軍B接到命令之後無法確認將軍A是不是叛徒,所以他要先問將軍c,『將軍A給你的命令是什」,而將軍C是叛徒,所以會故意說『將軍A給我的命令是撤退」。
“因為隻有三個將軍,所以將軍B就無法判斷將軍A和將軍C到底哪個是叛徒,因為『進攻』和『撤退』的命令各一票,無法形成多數。
“同理,將軍B在執行這個策略的時候,也沒法判斷將軍A和將軍C哪個是叛徒。
“這是最簡單的一種情況,如果將軍的數量變多,比如同時有7個將軍,其中有2個是叛徒的話,情況會變得複雜很多,要套娃很多次才能最終得到結論。
“所以我才說,這種問題不需要自己真的推算,隻要記住結論就行了。
“結論就是,當叛徒人數達到三分之一或者更多時,這個問題就不可解。
“反過來說,想要讓這個問題可解,就要把叛徒人數控製在少於三分之一的情況。
“套一下三個房間的人數,就一目了然了。
“『4人房間』,3人答題,所以隻要有1名惡意自由人,這個問題就不可解。
“『8人房間』,7人答題,在房間中有3名惡意自由人的情況下,不可解。
“『13人房間』,12人答題,在房間中有4名惡意自由人的情況下不可解。”
鄭傑恍然大悟:“原來如此!
“所以蔡哥你用這個公式套了一下,立刻就知道『8人房間」其實是最安全的,因為我們隻需要進入1名己方的自由人占位置,這個問題就一定可解。”
秦瑤還是沒明白:“等一下,雖然我聽得還是不太明白,但這個公式我記住了。
“我現在的疑問是,這個拜占庭問題,具體是怎套到遊戲規則的?”
鄭傑自告奮勇地說道:“我來解釋吧!
“在第二階段進入房間之後,實際上是『答題人』和『出題人』之間的博弈。
“比如說,我們在『8人房間』開黑店,那就是我們來扮演『答題人』,而其他社區後進入房間的玩家扮演『出題人』。
“我們『答題人」一方的目標是,達成一致選項,這樣就能拿到額外獎勵,從『出題人』身上賺簽證時間;
“而反過來,『出題人』一方的目標是,讓我們無法達成一致選項。
“比較簡單的方法是,『出題人」一方的普通玩家,隻要故意跟我們選擇不同選項就可以了。“所以,我們才需要設置房間規則,強製這些玩家必須提交多數派選項。
“『提交建議』這個功能,實際上就是在模擬『拜占庭容錯算法』的運算過程,每個玩家都必須強製發送當前的多數派建議,但是會有一定的時間間隔。
“所以在一遍一遍地發送之後,除自由人以外,所有普通答題人的建議會變成同一個選項。“之後,遊戲規則會強製這些玩家提交這個選項,就達成了『全員一致』的目標。
“但就像蔡哥說的,『提交建議』的模擬過程,本身需要『多數派建議達到一定數量』之後才能成立。“『自由人』玩家,實際上扮演了『惡意節點』和『叛徒』,他們會不斷發送少數派建議,來擾亂運算。
“假設這些惡意的『自由人』比較多的話,就可能出現這樣的情況:
“此時本來是A選項建議比較多,但突然出現了很多B選項建議反超了,導致一些玩家改成了B選項建議,然後又突然出現了一些A選項建議……
“這會導致玩家們提交的建議一直在變,始終無法固定下來,那當『提交建議』功能截止的時候,有些玩家提交的是A,有些玩家提交的是B,大家就沒法達成一致。
“『答題人』一方無法穩定地強製『出題人』連莊,無法穩定地獲得收益,那就相當於,黑店被拆掉了蔡誌遠點了點頭:“是的,所以隻要通過公式確定『拜占庭容錯』成立的條件,再比對各個房間能夠進入的自由人數量,就能確定進入房間的策略。
“『8人房間」,允許進入3名『自由人』,這個問題會在出現3個叛徒時不可解。所以,我們隻需要確保房間內有1名己方的『自由人』占住位置,就安全了。
“當然,這名己方的『自由人』必須是善意的,也就是他會主動執行『發送多數建議』的策略。“『13人房間」,允許進入6名自由人,這個問題會在出現4個叛徒時不可解,所以王衛東就必須確保最後進入『13人房間』的惡意自由人低於4人。
“所以,他們需要用於占位的『善意自由人』要更多一些。
“如果他們意識不到這一點的話,我們也可以選擇主動進攻。但既然王衛東意識到了,並做出了防守,再強行進攻就意義不大了。
“所以我換了一種思路,也就是利用這遊戲的『違心懲罰』,針對王衛東的特點提出一些可能會讓他在社區內身敗名裂的問題,從而強迫他取消房間規則。”