互動式零知識證明的演練-數獨難題

買賣虛擬貨幣
簡述學習如何透過使用零知識證明方法解答數獨,並用Python構建PoC。毫無疑問,我們當前生活在一個資料驅動的社會中,事實上,資料已成為比黃金或石油更有價值的資源。 認真考慮一下我們每天每分鐘線上共享的個人資料量。 位置,感覺,喜好,密碼,訊息……而且清單還在不斷增長……幸運的是,對稱和非對稱的加密技術使我們能夠保護我們的資料免受試圖竊聽我們通訊通道的惡意對手的攻擊。但是資料控制器(我們合法傳送資料的人)呢?消費者如何確保自己的資料不被錯誤處理或濫用?一種確定的方法是首先拒絕傳送資料。但實際上,並不是那麼簡單。這是一次交換。我們為他們提供的某種服務交換了一些隱私權嗎? 儘管如此,在很多情況下,從消費者的角度來看,這種交換並不公平,因為資料處理程式要求的資料比實際需要的要多得多。同樣,密碼學可能對此有解決方案。如果我告訴您,可以避免共享您的資料怎麼辦。例如與其將完整的薪水概覽和工作詳細資訊傳送給租賃機構以進行信用檢查,不如僅傳送證明您每年收入超過4萬的證明。這正是零知識證明(ZKP)所提供的!儘管有很多方法可以構造ZKP,但在本文中,我將給出一個演練(包含完整的程式碼片段),說明如何為僅使用雜湊函式作為承諾的數獨謎題解決方案建立ZKP。ZKP一開始理解起來可能會讓人望而生畏,因此我真的相信數獨拼圖是理解ZKP如何在很高的層次上工作的一個很好的例子。另外,數獨是大多數人都熟悉的東西。但讓我們切入正題。
背景知識零知識證明零知識協議起源於80年代,最初是由Shafi Goldwasser,Silvio Micali和Charles Rackoff在麻省理工學院提出的。更準確地說,他們描述了一種互動式證明系統,其中涉及一個當事方(“證明方”)向另一方(“驗證方”)證明某項陳述成立。將此背景化為常見的Alice/Bob示例,我們可以考慮以下場景:Alice偶然發現了一個線上比賽,需要解開一個謎題,並獲得100英鎊的獎金。她請求Bob的幫助,如果他們中的任何一個解決了,他們同意平分獎金。不久之後,Bob聲稱自己已經解決了問題,Alice請他分享解決方案。然而Bob不願意分享,因為他認為Alice可以自己提交解決方案,而不分享獎金。因此,他正在尋找一種安全的方法來向Alice證明他有解決方案,但又不直接與她分享。是的,你猜對了!ZKP正是他所追求的!讓我們更徹底地定義“安全方式”一詞的含義。通常ZKP必須提供以下屬性(至少具有很高的信心!):完整性:驗證者必須拒絕所有無效的證明
健全性:驗證人必須接受每一個有效的證明零知識:驗證程式除了斷言外,不理會其它語句的任何資訊請注意,這是互動式ZKP的非常基本的定義。有各種各樣更復雜的互動式/非互動式ZKP,但是對於本演練而言,此定義就足夠了。承諾方案(Commitment Schemes)承諾方案是ZKP的關鍵組成部分,總體而言,它是加密的關鍵部分。簡而言之,它們是密碼原語,它允許當事方承諾特定的價值而無需透露實際價值,同時提供一種方式來揭示價值並在以後的階段中驗證承諾。更正式地說,讓C作為承諾方案,它必須提供以下兩個屬性:

隱藏(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的一些基本知識,尤其是如何透過零知識證明來證明擁有數獨解決方案。在以後的文章中,我們將探索更復雜的證明,這些證明不需要證明者與驗證者之間的相互作用,並且還將使用更復雜的密碼原語。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;