Encryption

多方投票箱。所有人都可以閱讀,或者沒有人可以閱讀

  • June 20, 2014

我正在嘗試為遊戲“外交”創建一個分散的審核系統,該遊戲適用於 7 名玩家。在面對面遊戲的每一輪中,每個玩家在紙上寫下他們的動作,然後把它放在一個盒子裡;一次讀取所有動作。該遊戲以郵寄方式流行:您將您的動作郵寄給雜誌出版商,後者匯總所有動作並向所有人發布遊戲更新。在線上遊戲的每一輪中,每個玩家都會將他們的動作發送給第三方“主持人”,後者然後匯總這些動作並將所有動作傳遞給所有玩家。玩家必須事先同意第三方版主。

我想創建一個不需要主持人的去中心化系統。每個播放器都可以執行一個可通過網路訪問的伺服器。每一輪,每個玩家都會向所有其他玩家廣播他們的動作(以某種方式加密)。當所有玩家都廣播了他們的動作時,所有玩家才能閱讀其他玩家的動作。


最初,我想使用三通協議之類的東西:玩家 A 寫一條消息,將其放入帶有掛鎖 A 的盒子中,然後將其發送給玩家 B。玩家 B 將掛鎖 B 放在盒子上,然後將其返回給玩家 A . 玩家 A 移除掛鎖 A 並將盒子返回給玩家 B。玩家 B 現在可以移除掛鎖 B 並閱讀消息。

玩家將被安排在一個環中:玩家 A 總是將消息傳遞給玩家 B,玩家 B 總是將消息傳遞給玩家 C,等等。所以每條消息最終都會放在一個盒子裡,盒子上有七個掛鎖。只有當它繞了一圈之後,所有玩家才能閱讀消息。

但這並不能解決不合作的問題:在第六關,玩家 D 可以停止向玩家 E 發送消息,讀取其他人的動作,並且不再進一步合作。

玩家 D 和玩家 F 也可以選擇相互合作,讓玩家 E 置身事外。這對玩家 E 來說是不利的。

在像外交這樣的遊戲中,不允許一個玩家讀取任何其他玩家的動作,而所有玩家都讀取所有動作是不可接受的。


另一個想法是讓每個玩家私下發送他們的動作,鎖定在一個盒子裡,給其他玩家(通過私鑰-公鑰)。當玩家收到盒子時,該玩家向所有人廣播,“大家好,玩家 X 給我發了一個雜湊到 abc123 的盒子!”。當每個人都發現其他人都收到了所有其他盒子時,他們可以將它們換回去。這允許一些玩家對其他人撒謊,但缺點是“沒有人得到任何東西”。


我想我在這裡走在正確的軌道上,但我不確定。這是思考問題的正確方式嗎?這已經完成了嗎(我已經找不到其他解決方案了)?

延展性承諾方案

您顯然正在尋找同時廣播的共謀保護實現。

通過讓每個處理器控制至少一個玩家並指示每個處理器為其每個玩家選擇一個隨機位並輸出所有玩家隨機位的異或,由此產生的擲硬幣協議與系統一樣公平。 $ : $ 因此,人們直接進入了這篇論文的不可能結果。

我所知道的繞過這種不可能結果的方法是:

$ ; $ 時間鎖定謎題,配合玩家所需的工作量

$ ; $ 閱讀這些資訊的工作量“不會多於”

$ ; $ 敵對玩家閱讀消息,在這兩種情況下;僅相關工作

$ ; $ 需要少量記憶體並且不能(已知是可行的)可並行化

$ ; $ 部分公平,這樣當超過1/3的玩家合作時

$ ; $ (特別是當只有 2 個玩家時)並且可能的消息數量很少,

$ ; $ 合作玩家獲得的資訊比敵對玩家獲得的資訊“不多”

$ ; $ 有很多版主,只有在玩家停止參與時才需要聯繫

$ ; $ 在展示階段之前或期間,每個人都被分配一個小的正整數權重

$ ; $ (大概低於我稍後會在這個文本塊中提到的門檻值,否則沒有意義

$ ; $ 使用多個主持人),因此如果

$$ the sum of the weights assigned to adversarial

$;$ moderators $$小於$$ the threshold chosen before the reveal phase begins $$小於或

$ ; $ 等於[分配給似乎正在合作的主持人的權重之和]]

$ ; $ 那麼“所有人都可以閱讀它,或者沒有人可以閱讀它”屬性成立 .

(無法聯繫或失去私鑰的版主

既不是敵對的,也不是看似合作的版主。)

需要強調的是,即使所有版主都是對抗性的,他們唯一能做的就是讓

停止參與的玩家違反“所有人都可以閱讀它,或者沒有人可以閱讀它”的屬性。

特別是,仍然必須獨立於其他消息選擇每條消息。

可能還有其他方法可以解決這種不可能的結果;特別是,

我看不出為什麼 1/3 門檻值對於部分公平至關重要。

即使沒有,在我看來,人們可以將“部分公平”選項與

“大量主持人”選項結合起來,至少與後者一樣好,但在後者的不平等時也能提供部分公平距離不太遠,可能的消息數量很少。

請注意,我不知道我描述的三個選項中的哪一個 與共謀保護

兼容。

引用自:https://crypto.stackexchange.com/questions/17791