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

这篇具有很好参考价值的文章主要介绍了【零知识证明】数独解的例子解释零知识证明。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

零知识证明

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提升效率,可以隐藏交易数额。文章来源地址https://www.toymoban.com/news/detail-783968.html

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

到了这里,关于【零知识证明】数独解的例子解释零知识证明的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 区块链基础知识7-比特币挖矿原理/工作量证明

    在前面《区块链基础知识6-区块链记账原理》我们了解到记账是把交易记录、交易时间、账本序号、上一个Hash值等信息计算Hash打包的过程。 我们知道所有的计算和存贮是需要消耗计算机资源的,既然要付出成本,那节点为什么还要参与记账呢?在中本聪(比特币之父)的设

    2024年04月28日
    浏览(46)
  • 求解器解的最优性 | cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明吗?

    作者: 刘兴禄,清华大学,清华-伯克利深圳学院博士在读 欢迎关注我们的微信公众号 运小筹 之前有人在【运小筹读者2群】里问:cplex、gurobi和COPT求解器求解出来的一定是最优解吗?有理论证明什么的吗? 我给除了下面的回答,我觉得对大家会有用,因此稍加整理分享一下

    2024年02月06日
    浏览(39)
  • Midjourney的--seed 解释,并附有例子

    探索Midjourney之旅,学习绘画与AI,一同成长。加入「阿杰与AI」公众号,参与内容社群建设。 1.Midjourney 新手快速起步指南 2.Prompts-提示指令 3.Explore Prompting-提示指令的探索 4.Blend-叠加 5.Midjourney Discord的使用手册 6.Versions-版本 7.UpScalers-放大器 8.Midjourney 命令教程 9.Midjourney 参数

    2024年02月12日
    浏览(28)
  • Python 变量?对象?引用?赋值?一个例子解释清楚

    哈喽大家好,我是咸鱼。 前天有个小伙伴找到我,给了我一段 python 代码: 然后问我为什么结果是 [1, [...]] ,我一看这个问题有意思,我说三言两语解释不清楚,我写篇文章到时候你看下吧,于是有了今天这篇文章。 在正式开始之前,让我们先弄清楚一些概念。 \\\"Python 中一

    2024年01月24日
    浏览(44)
  • 区块链项目 - 2 工作量证明

    我们在区块中添加一个属性Nonce来表示区块的生成难度,它是区块生成的一个重要条件,Nonce值越高,代表生成区块的难度越大,通过这种难度从而避免区块随意生成,工作量证明则是要完成这一系列难度区块生产所需要的工作量 /Users/xxx/go/src/publicChain/part5-Basic-Prototype/BLC/Bl

    2024年02月03日
    浏览(46)
  • 【设计模式】以国足的例子来解释代理模式,希望自己不要被退钱

    通过引入一个新的对象来实现对真实对象的操作或者将新的对象作为真是对象的一个替身,这种机制被称为代理模式。通过引入代理对象来间接访问一个对象,这就是代理模式的模式动机。 代理模式 :给某一个对象提供一个代理,并由代理对象控制对原对象的引用。代理模

    2024年02月21日
    浏览(29)
  • 动手学区块链学习笔记(二):区块链以及工作量证明算法

    紧接上文,在介绍完区块链中的加密解密以及公钥私钥等算法后,本篇开始正式进入区块链概念与一个简单区块链系统的实现过程介绍。 什么是区块链? 区块链,就是一个又一个区块组成的链条。每一个区块中保存了一定的信息,它们按照各自产生的时间顺序连接成链条。

    2024年01月17日
    浏览(49)
  • WPF入门实例 WPF完整例子 WPF DEMO WPF学习完整例子 WPF实战例子 WPF sql实例应用 WPF资料源码

    WPF 和 WinForms 都是用于创建 Windows 桌面应用程序的开发框架,它们有一些相似之处,但也有很多不同之处。 在开发速度方面,这取决于具体情况。如果您熟悉 WinForms 开发并且正在开发简单的界面应用程序,则可能会比使用 WPF 更快速地完成任务。然而,在设计和实现复杂的用

    2024年02月06日
    浏览(51)
  • 【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【星辰大海】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰    目录 ⭐时间复杂度分类 🍔 方法 🎈平方阶 🎈立方阶  🎈对数阶 🍔例子 ✨常数时间复杂度 O(1) 🎈数组读取、索引和

    2023年04月20日
    浏览(52)
  • 零知识证明学习(三)—— 非交互式零知识证明(zkSNARKs)

    本节主要介绍一种新的零知识证明- z k S N A R K zkSNARK z k S N A R K , z k S N A R K : z e r o − k n o w l e d g e S u c c i n c t N o n − I n t e r a c t i v e A r g u m e n t s o f K n o w l e d g e zkSNARK:zero-knowledge Succinct Non-Interactive Arguments of Knowledge z k S N A R K : z e r o − k n o w l e d g e S u c c i n c t

    2024年01月20日
    浏览(61)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包