交互式零知识证明的演练-数独难题

简述

学习如何通过使用零知识证明方法解答数独,并用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的一些基本知识,尤其是如何通过零知识证明来证明拥有数独解决方案。在以后的文章中,我们将探索更复杂的证明,这些证明不需要证明者与验证者之间的相互作用,并且还将使用更复杂的密码原语。

关键词: 零知识证明    

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28152

联系我们

aliyinhang@gmail.com