零知識賓果
賓果遊戲是一種機會遊戲，每個玩家將他們卡片上的數字與來電者隨機抽取的數字相匹配。當第一個玩家在他們的卡上收集到足夠的被叫號碼時，他們宣布他們贏了，他們的卡得到驗證。
想像一下這個遊戲是線上玩的，玩家可以選擇自己的卡片。
**問題：**有沒有辦法線上玩賓果遊戲並斷言你的牌贏了，而不透露你的牌是什麼，只是你一開始就選擇了這張牌並且它確實包含被叫號碼？
**子問題：**這是對現有的普遍問題的實際應用嗎？
**自己的想法：**在這個遊戲的第一次迭代中，我們可以要求玩家在遊戲開始時發布，簽名，他們選擇了哪張卡片。當第一個玩家收集到足夠的被叫號碼時，獲勝者將顯而易見。但我不希望玩家在遊戲開始時發布他們的卡片。
在這個遊戲的第二次迭代中，我們可以要求玩家在遊戲開始時發布並加密他們選擇的卡片。我們可以包含鹽以避免反向查找，我們可以包含一個校驗和以確保他們發布的內容不能輕易地解密到任何卡中。但我也不希望玩家在遊戲結束時發布他們的卡片！
一旦贏了一場比賽，我們就知道哪些牌可以贏。也許可以說你的卡屬於這個子集（有一定的可能性？）而不說它是什麼成員？也許這涉及到生成大量的中獎牌，其中一張可能是真正的中獎牌，然後證明你的牌就是其中之一，而不說是哪一張。
***澄清1：***這個問題沒有以公平的方式處理呼叫號碼。假設玩家無法預測叫到什麼數字。
***澄清2：*為了證明你已經收集了所有的數字，可能贏得的牌子集正好包含那張牌，所以第一次和第二次迭代的方法是相同的；這個問題適用於收集一排，兩排……的子目標
我將在Meir Maor 的回答的基礎上建構一個簡單的 $ f $ 用於 R1CS，如libsnark或 dalek 的“防彈”庫。事實證明這是非常有效的！
- 每個玩家都對董事會作出承諾。我們假設董事會 $ B(i,j) $ 是大小 $ n\times m $ . 製作 $ nm $ 我們發布的 Pedersen 承諾。
- 數字被呼叫。呼叫這些 $ l $ 公眾號 $ B’(k):1<k<l $
- 當玩家聲稱他贏了（賓果遊戲！）時，他可以建構一個證明。請注意，如果玩家有一整行匹配的數字，則玩家獲勝。我們可以說對於獲勝的行 $ i<m $ :
$$ \bigwedge^m_{j=1}\left(\bigvee^l_{k=1} B(i,j)=B’(k)\right) $$
在整個董事會上，這變成了
$$ f(B)=\bigvee^n_{i=1}\left[\bigwedge^m_{j=1}\left(\bigvee^l_{k=1} B(i,j)=B’(k)\right)\right]. $$
這是放入算術電路的一種非常漂亮的形式。它成為了 $$ \prod^n_{i=1}\left[\sum_{j=1}^m\left(\prod_{k=0}^l(B(i,j)-B’(k))\right)z^{j-1}\right] $$
對於一些隨機挑戰 $ z $ . 使用 Fiat-Shamir 轉換，可以將其設為非互動式。這個方案需要 $ (l-1)(n-1) $ 私有乘法，這意味著像 dalek 的系統可以在 $ \log(n\cdot l) $ 空間，在數量或行和已經呼叫的數字中是對數的。