隱藏(Hiding):很難區分不同價值的承諾。
約束力(Binding):一個人承諾後不能再宣稱自己已經承諾了另一個值:
建立承諾方案的一種方法是使用單向雜湊函式和加密安全的隨機位元組。應該注意的是,在這種情況下,該方案的安全性由雜湊函式本身的加密假設(即它是單向的)來控制。
為了更清楚地說明這一點,讓我們來看一個常見嫌疑人的例子。Alice和Bob決定玩一個石頭,剪刀,布的數字遊戲。他們都做出選擇並交換結果,以便確定贏家。在數字世界中,其中一個必須首先共享他/她的選擇,這使她/他處於不利的位置,因為他/她可以在檢視另一位玩家選擇的結果後再共享不同的選擇。這正是承諾方案要解決的問題!
另外,他們可以根據自己的選擇建立承諾並共享承諾,而不是實際選擇! 例如:
設定一個:
S = {“Rock”, ”Paper”,”Scissors”}
Bob和Alice都分別從S中隨機選擇Pᴬ和Pᴮ。現在他們計算:(||->表示串聯)
Cᴬ = sha256(Rᴬ || Pᴬ) and Cᴮ = sha256(Rᴮ || Pᴮ)
Bob和Alice共同共享Cᴬ,Alice和Bob共同共享Cᴮ。請注意,到現在為止,它們都承諾了這些值。
最後它們共享原始選擇和隨機位元組Pᴬ,Rᴬ和Pᴬ,Rᴮ。有了這些資訊,各方就可以透過對P||進行雜湊來驗證承諾。R並宣告它們的等效性。根據他們的選擇,可以確定獲勝者,而且由於雜湊值不匹配,他們都無法更改其初始選擇。
數獨ZKP
現在是本文的主要部分。數獨是一個非常著名的難題,也被稱為NP問題(實際上是NP-Complete),並被證明對於NP中的任何問題都有ZK。數獨ZKP絕非什麼新鮮事物,但我還沒有找到一個直觀和清晰的解釋協議與程式碼示例,所以至少這是本文旨在提供的。實際上,這裡描述的協議是Gradwohl等人的這項非常有趣的工作的實現。有趣的是,他們在論文中還描述了一種物理協議,可以使用一副紙牌來執行打樣,如果您想親自演示ZPK,但現在還是堅持使用數字打樣,這很有趣。
Alice想向Bob證明她有一個數獨謎題的解答方案,但Bob不相信她。假設她擱置以下難題和解答方案。
為了避免混淆,讓我們按照以下步驟進行驗證:
1.Alice建立數獨數字的排列,有效的方法是對每個數字進行一對一的對映。1->3,2->8…。
2.此外,她為每個數獨單元生成一個隨機位元組序列。這將會有81個隨機位元組序列。
3.她在數獨解決方案的編號上應用了對映,以獲取被掩蓋的解答方案。注意,透過對值進行排列,數字只會出現一次,因為它是一對一對映。
Alice從每一行、每一列、每一子網格和一組已知的數字中分離出一組被遮蔽的數字,這些數字最初是拼圖定義的一部分。實際上,她最終得到了27+1組數字,其中從行、列、子網格派生的27必須滿足數獨要求。i、從1到9的所有數字只出現一次。
然後,她透過用對應的隨機數對每個單元格進行雜湊來建立對遮蔽解答方案的承諾,將該承諾傳送給Bob,並要求Bob選擇行,列,子網格或已知數字集。
Bob選擇了一個,Alice向他傳送了與Bob的選擇相對應的隨機數和排列數字。
如果Bob選擇了已知號碼列表,則Alice還將最初生成的一對一對映傳送給他。然後,Bob驗證排列後的值確實只出現過一次,並使用隨機數重新建立承諾,以驗證Alice的承諾。
如果Bob選擇了已知號碼列表,他還將檢查對映是否正確。即讓M為對映,使n為1–9的整數:M(n)==接收到的已知數字列表。
很自然,你的腦海中已經出現了關於這些步驟的問號,所以請繼續關注這些步驟背後的基本原理。
執行步驟1、3時,驗證者不會了解任何有關謎題解答方案的資訊。
步驟2隨機數用於阻止驗證程式執行已知的純文字攻擊。 如果沒有隨機數,Bob可以僅對所有數字進行雜湊(1–9),並將相應的摘要與承諾相匹配以顯示值。
步驟5透過建立承諾並將其傳送給Bob,Alice承諾了自己的解答方案,因此無法更改它(或對映)。
步驟6,7,8,9是最難理解的。透過讓Bob選擇Alice中提供的任何一個解答方案,為驗證者提供了確認解答方案正確的機會。 回想一下,她自從完成對映後就無法更改它。 另外,您可能在想:“這證明她可能只是解決方案,而不是特定的解決方案”。 您是100%正確的! 這就是存在選擇請求拼圖給出的初始數字的原因。這樣Alice無法作弊,因為Bob可隨時選擇索要這些號碼,而且如果這是另一種解答方案,顯然它們將不匹配。
更重要的是,有必要強調這種方法的可靠性誤差。回想一下,穩健性是ZKP Verifier接受所有有效證明的屬性。在這種情況下,由於驗證者可以選擇28種選擇(3n + 1),這意味著協議的迴應僅為1/28%,這意味著存在1-1/28的迴應錯誤! 換句話說,在一次迭代之後,驗證者僅能確保1/28是有效的證明。那不是很高,不是嗎? 因此,可以對上述步驟進行多次迭代,以將健全性誤差降低到可以忽略的值。(可以使用貝葉斯規則來推斷每次迭代的健全率)
我希望這現在更有意義。讓我們繼續使用Python開發一個小的PoC證明。您可以在此處找到完整的程式碼:
Python ZKP PoC
由於生成和求解數獨不在本文的討論範圍內,我將暫時使用靜態數獨,但可以隨時用程式碼替換它,每次生成一個新的數獨拼圖:
def gen_sudoku_puzzle():
puzzle = [
0,0,0,0,0,0,6,8,0, \
0,0,0,0,7,3,0,0,9, \
3,0,9,0,0,0,0,4,5, \
4,9,0,0,0,0,0,0,0, \
8,0,3,0,5,0,9,0,2, \
0,0,0,0,0,0,0,3,6, \
9,6,0,0,0,0,3,0,8, \
7,0,0,6,8,0,0,0,0, \
0,2,8,0,0,0,0,0,0
]
# Indices of given values
presets = [6,7,13,14,17,18,20,25,26,27,28,36,38,40,42,44,52,53,54,55,60,62,63,66,67,73,74]
return puzzle, presets
def solve_sudoku_puzzle(puzzle):
solution = [
1,7,2,5,4,9,6,8,3, \
6,4,5,8,7,3,2,1,9, \
3,8,9,2,6,1,7,4,5, \
4,9,6,3,2,7,8,5,1, \
8,1,3,4,5,6,9,7,2, \
2,5,7,1,9,8,4,3,6, \
9,6,4,7,1,5,3,2,8, \
7,3,1,6,8,2,5,9,4, \
5,2,8,9,3,4,1,6,7
]
return solution
數獨拼圖儲存為一個簡單的python列表,以便於處理。
接下來,讓我們新增使用一對一對映排列數獨解決方案和建立隨機數的程式碼:
def create_permutations():
permutations = list(range(1,10))
random.shuffle(permutations)
permutations = [0] + permutations
return permutations
def puzzle_permute(puzzle, permutations):
return [permutations[x] for x in puzzle]
def gen_nonces():
nonces = [
random.SystemRandom().getrandbits(256) for _ in range(9**2)
]
return nonces
ero元素是在shuffle之後新增的,因為我不希望它成為對映的一部分。就在那裡,數字的索引從1開始。
此外,以下是建立數獨解決方案承諾的功能:
def puzzle_commitment(puzzle, nonces):
return [sha256((str(nonce)+str(val)).encode('utf-8')).hexdigest() for nonce, val in zip(nonces, puzzle)]
如上所示,對於承諾,使用SHA256雜湊演算法。此外,以下是將拼圖分為行,列和子網格的程式碼:
def chunk(iterable, size):
return [iterable[i:i+size] for i in range(0, len(iterable), size)]
def flatten(iterable):
return [item for sublist in iterable for item in sublist]
def puzzle_rows(puzzle):
return chunk(puzzle, 9)
def puzzle_columns(puzzle):
return list(zip(*puzzle_rows(puzzle)))
def puzzle_subgrids(puzzle, size=3, n=9):
subgrids = []
rows = puzzle_rows(puzzle)
for i in range(0,n,size):
for j in range(0,n,size):
subgrids.append(flatten([rows[j+k][i:i+size] for k in range(size)]))
return subgrids
最後,進行檢查以確認1–9中的所有數字都存在並且僅出現一次:
def all_digits_exist_once(iterable):
digit_mask = [0 for i in range(9)]
for x in iterable:
digit_mask[x-1]=1
return all(digit_mask)
現在,我們可以將所有這些功能組合在一起,以建立協議的概念證明並驗證其正確性:
# Alice:
puzzle, presets = gen_sudoku_puzzle()
solution = solve_sudoku_puzzle(puzzle)
# Alice sends: puzzle, presets, "Hey Bob! I found the solution!"
# Bob: "I don't believe you!"
# Alice: "Okay wait and see.."
permutations = create_permutations()
permuted_solution = puzzle_permute(solution, permutations)
nonces = gen_nonces()
commitment = puzzle_commitment(permuted_solution, nonces)
# Alice: <Commitment> "Here... pick a row, column, subgrid or presets"
# Bob: "Hmmm.. Okay! I pick the 3rd row"
# Alice:
third_row = puzzle_rows(permuted_solution)[2]
third_row_nonces = puzzle_rows(nonces)[2]
# Alice sends: <third_row, third_row_nonces> "Hey Bob check them out!"
# Bob: "Let me verify..."
third_row_commitment = puzzle_rows(commitment)[2]
sudoku_verification = all_digits_exist_once(third_row)
assert sudoku_verification == True
commitment_verification = puzzle_commitment(third_row, third_row_nonces)
assert commitment_verification== third_row_commitment
# Bob: "Okay seems like it is correct.. but I am only 1/28 confident..."
# Alice: "If you still ahve doubts we can repeat this as many times as you want! :)"
此程式碼僅用於演示目的,可能不具有安全性,因此請不要在生產環境中使用。
結論
希望該部落格文章提供了有關ZKP的一些基本知識,尤其是如何透過零知識證明來證明擁有數獨解決方案。在以後的文章中,我們將探索更復雜的證明,這些證明不需要證明者與驗證者之間的相互作用,並且還將使用更復雜的密碼原語。