草庐IT

【零知识证明】数独解的例子解释零知识证明

long龙没装DNS 2023-11-05 原文

零知识证明

2022年11月14日 in 中国科学院大学

零知识证明

数独解的例子解释零知识证明

如何证明数独有解?不能直接给出解(数据保护问题:数独题目存在价值)。

一、零知识证明方法:

  1. 承诺
    将谜底卡片扣在桌子上,谜面卡片放在桌子上。(Alice不能查看)
  2. 随机挑战
    链下互动:Bob让Alice用任意一种(行、列、宫格)方法检查,Alice严格随机选择一种规则进行检查。
  3. 响应
    将Alice选择验证方式的每一行/列/宫格放入一个麻袋中打乱交由Alice验证。(放入过程Alice监视)
    Bob在每一次Alice选择验证方式的随机中无法猜测,重复若干次。
  4. 验证
    在Bob没有解的情况下,欺骗成功的概率是1/3,Alice抓住欺骗的概率是2/3。

二、如何让Alice以外的人相信?

  • 将同样的解做多次备份,放入机器中(机器可以根据指令自动完成按行/列/宫格打包)。
  • 指令结合不能由Bob生成,找到可信方法生成随机串为机器提供指令,完成非交互式的证明
  • 由此,随机串必须采用所有人公认方法。
  • 至此,零知识证明问题的核心是解决随机串的选取问题

三、数独问题零知识证明中出现的问题

  • 交互式证明无法上链
  • 非交互式证明在验证的过程数据量过大,无法在一个交易的扩展部分中进行说明。
  • 方法:将过大的数据量进行简洁处理,使用Merkle Tree做多次Hash。

零知识证明相关理论

一、交互证明系统

交互证明系统中进行证明者和验证者之间的信息交换。通过信息交换,参与方证明某个声明成立。

1、交互证明的性质:
  • 完备性:正确的声明“验证者”总是接受。
  • 可靠性:错误的生命“验证者”总是拒绝。
  • 交互式:证明者和验证者之间采用交互形式完成证明过程
2、交互证明系统的定义:
  • 一个0,1组成的字符串称为语言L,一对交互图灵机<P,V>,P表示证明者(拥有无限计算能力),V表示验证者(在概率多项式时间内可验证)
  • 称<P,V>为语言L的交互证明系统,满足以下条件:
    a. 完备性:Pr[(P,V)(x) = 1|x属于L] <= 1 - negl(|x|)
    b. 可靠性:Pr[(P*,V)(x) = 0|x不属于L] >= 1 - negl(|x|)
3、IP语言类
  • 拥有交互证明系统的语言类称为IP语言类。

二、零知识证明

零知识证明是交互证明系统的一个实例,目标是:证明某一个事实且不泄漏知识

1、定义

在交互证明系统基础上增加零知识性(验证者无法从该证明过程中获得额外的信息)。

  • 零知识:在任意概率多项式时间验证者V*,都存在一个概率多项式时间的模拟器S(代表未参与验证的局外人),使得任意x属于L:<P,V*>(x) ~=c S(x)
2、零知识性的三种形式
  • 计算零知识性:没有有效算法区分两个分部
  • 统计零知识性:统计距离可忽略
  • 完美零知识性:两个分布同分布

利用零知识证明的应用

一、小零币(Zerocoin)

铸币过程中只公布序列号的承诺(序列号与身份绑定),使得承诺与拥有者割裂开,没有指定币值。

1、做法
a. 生成一个序列号S和随机密钥r
b. 生成序列号s的承诺Commit(S,r),可以充当该币地址
c. 在区块链`bitcoin的链`上公布承诺(烧币)
2、如何花小零币
a. 将铸好的小零币注入零币池中,构建承诺对象中r的集合
b. 交易时,交易包涵序列号S和自己能打开承诺的声明
c. 矿工验证零知识证明,认为你可以打开区块链中一个零币
d. 矿工查询序列号S确认没被花费过
e. 花费交易的输出形成一个新的零币,用自己比特币拥有地址来作为输出地址

二、大零币(ZeroCash)

引入了zk-SNARKs提升效率,可以隐藏交易数额。

承诺过程
  1. 公钥地址和序列号与随机数r进行承诺生成commit(k)
  2. commit(k)和币值v与随机数s进行承诺生成commit(coin)
  3. 将commit(coin)上链

有关【零知识证明】数独解的例子解释零知识证明的更多相关文章

  1. ruby - 有人可以帮助解释类创建的 post_initialize 回调吗 (Sandi Metz) - 2

    我正在阅读SandiMetz的POODR,并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时,因为它没有自己的initialize方法

  2. ruby - 解释为局部变量会覆盖方法名称吗? - 2

    如thisquestion,当在其自己的赋值中使用未定义的局部变量时,它的计算结果为nil。x=x#=>nil但是当局部变量的名称与现有的方法名称冲突时,就比较棘手了。为什么下面的最后一个示例返回nil?{}.instance_eval{a=keys}#=>[]{}.instance_eval{keys=self.keys}#=>[]{}.instance_eval{keys=keys}#=>nil 最佳答案 在Ruby中,因为可以在没有显式接收器和括号的情况下调用方法,所以在局部变量引用和无接收器无参数方法调用之间存在语法歧义:f

  3. 语法类似于 GitHub Flavored Markdown 的 Ruby markdown 解释器? - 2

    我使用Jekyll运行博客,并认为我会解决RedcarpetMarkdown解释器,因为它是developedandusedbyGitHub.好吧,我只是碰巧遇到了一个错误,去检查问题,然后foundthis.Maintainersays,"Asyouprobablyhavenoticed(harharharhar)Idon'thavetimetomaintainRedcarpetanymore.It'snotapriorityforme(IfindMarkdownthoroughlyboring)andit'snotapriorityforGitHub,becausewenolong

  4. ruby - 有人可以解释一下在 Ruby 中注入(inject)的真实、通俗易懂的用法吗? - 2

    我正在学习Ruby,遇到了inject。我正处于理解它的风口浪尖,但当我是那种需要真实世界的例子来学习一些东西的人时。我遇到的最常见的例子是人们使用inject来添加一个(1..10)范围的总和,我不太关心这个。这是一个任意的例子。在实际程序中我会用它做什么?我正在学习,所以我可以继续使用Rails,但我不必有一个以Web为中心的示例。我只需要一些我可以全神贯注的目标。谢谢大家。 最佳答案 inject有时可以通过它的“其他”名称reduce更好地理解。它是一个对Enumerable进行操作(迭代一次)并返回单个值的函数。它有许多有

  5. ruby - 如何证明 Ruby `for` 循环实际上是使用 `each` 方法实现的? - 2

    在EloquentRuby(第21页,第一版,第六次打印)一书中,作者(RussOlsen)提倡使用each方法而不是for循环,这与我在其他地方读到的所有内容一致。但是作者还继续说,这样做的一个原因是for循环实际上调用了each方法,所以为什么不直接删掉中间人并使用each?所以我想知道这实际上是如何工作的。为了调查,我确实在github上的Ruby存储库上进行了搜索,但发现很难确定我在哪里/如何看到它的实际效果。重述问题:我如何证明Rubyfor循环实际上是使用each方法实现的? 最佳答案 您可以通过编写一个实现每个的类来展

  6. ruby - 一种语言如何被自身解释(如 Rubinius)? - 2

    我使用Ruby编程已经有一段时间了,现在只使用Ruby的标准MRI实现,但我一直对我经常听到的其他实现感到好奇。前几天我在读有关Rubinius的文章,这是一个用Ruby编写的Ruby解释器。我试着在不同的地方查找它,但我很难弄清楚这样的东西到底是如何工作的。我在编译器或语言编写方面从来没有太多经验,但我真的很想弄明白。一门语言究竟如何才能被自己解释?编译中是否有一个我不明白这有意义的基本步骤?有人可以像我是个白痴一样向我解释这个吗(因为无论如何这都不会太离谱) 最佳答案 它比你想象的要简单。Rubinius并非100%用Ruby编

  7. Ruby 代码解释 - 2

    谁能解释一下这段Ruby代码:defadd_spec_path_to(args)#:nodoc:args我看到了运算符用于连接字符串或在其他语言中用作按位运算符,但有人可以在这种情况下对其进行解释。它是以某种方式将一个空白的lamda附加到args上还是我完全错了?我还可以看到它是这样使用的:before_parts(*args)是Hash关键字?我也不确定||=是什么接线员在说。我同样对什么一无所知caller(0)[2]是。 最佳答案 我假设args是一个Array。Hash是类的名称-第一行将空哈希{}推送到argsunles

  8. python - 解释性语言中的链接和加载 - 2

    在编译型语言中,源代码由编译器转化为目标代码,不同的目标文件(如果有多个文件)由链接器链接并由加载器加载到内存中执行。如果我有一个使用解释性语言(例如ruby​​或python)编写的应用程序,并且如果源代码跨多个文件拆分,那么这些文件究竟何时组合在一起。换句话说,链接何时完成?解释型语言一开始就有链接器和加载器,还是解释器包揽一切?我真的很困惑,无法理解它!!谁能对此有所启发?! 最佳答案 解释型语言或多或少是可执行文件的大型配置,称为解释器。该可执行文件(例如/usr/bin/python)是实际运行的程序。然后它读取它要执行的

  9. ruby - 什么标准证明在 Ruby 中使用模块而不是类? - 2

    我正在阅读我的ruby书。查看下面的代码,moduleDestroydefdestroy(anyObject)@anyObject=anyObjectputs"Iwilldestroytheobject:#{anyObject}"endendclassUserincludeDestroyattr_accessor:name,:emaildefinitialize(name,email)@name=name@email=emailendendmy_info=User.new("Bob","Bob@example.com")puts"Soyournameis:#{my_info.name}

  10. ruby - 解释型语言(如 Ruby)如何运行? - 2

    我打算学习Ruby。我知道这是一种解释语言。我知道编译语言最终会被翻译成机器码,但是ruby​​解释器是做什么的呢?我读到解释器是用C编写的,但是每一行ruby​​都转换为c,然后再次编译为机器代码吗?我也听说过JIT,但是如果这会增加答案的复杂性,那么您就不需要回答它了。我正在寻找的是我的Ruby代码发生了什么。 最佳答案 它将Ruby代码转换为某种更简单的“中间”表示形式(在最近的版本中,它编译为字节码)。它还会在您计算机的内存中构建一个虚拟机,模拟执行该表示的物理机。这台机器是一台物理机器的镜像,至少在合理和有用的范围内。它通

随机推荐