零知识证明 Zero Knowledge Proof 以及 Layer2、跨链介绍

admin管理员组

文章数量:1530022

零知识证明

定义：20世纪80年代初发明，证明者在不向验证者提供任何有用信息的情况下，使验证者相信某个论断是正确的。
要求：完整性、可靠性、零知识性
分类：交互式证明、非交互式证明
角色：示证者/证明方(prover)、验证者(verifier)

eg：

主要技术： 零知识简洁无交互证明（zk-SNARK）、零知识可扩展透明证明（zk-STARK）和子弹证明（Bulletproof）

zkp中的基础概念

安全承诺（Commitment）：一个非交互式安全承诺机制（non-interactive commitment scheme）包含了一对基于概率的多项式时间算法，(Setup,Com )。其中，Setup算法对机制进行初始化：pp←Setup (1^λ )。在一个安全参数λ下，生成（多个）公有参数pp。Com定义了一个以公有参数pp生成的消息空间 M p p M_{pp} Mpp​和随机数空间 R p p R_{pp} Rpp​到安全承诺空间 C p p C_{pp} Cpp​的一个映射 M p p M_{pp} Mpp​× R p p R_{pp} Rpp​→ C p p C_{pp} Cpp​。对于给定消息x∈ M p p M_{pp} Mpp​，均匀选择的随机数r← R p p R_{pp} Rpp​，Com 可以生成出安全承诺com= C o m p p Com_{pp} Compp​ ( x; r) 。为了简化表达，记Com= C o m p p Com_{pp} Compp​。

目前的安全承诺往往通过同态承诺（Homomorphic Commitment）实现，并具有隐藏（Hiding）和绑定（Binding）的特性。但隐藏和绑定是对立的，即完美的隐藏（perfectly hiding）和完美绑定（perfectly binding）无法同时拥有，因此，目前研究大部分考虑在离散对数假设下的计算绑定（computationally binding）。以下我们对每一种定义进行详细描述。

同态承诺（Homomorphic Commitment）：同态承诺是一种非交互的安全承诺，其中， M p p M_{pp} Mpp​、 R p p R_{pp} Rpp​和 C p p C_{pp} Cpp​均为阿贝尔群(可交换群)，并且对于所有的 x 1 x_1 x1​, x 2 x_2 x2​∈ M p p M_{pp} Mpp​； r 1 r_1 r1​, r 2 r_2 r2​∈ R p p R_{pp} Rpp​，有：

隐藏承诺（Hiding Commitment）：对于所有PPT攻击者A，隐藏承诺满足有一个可忽略的函数μ(λ)使得：

隐藏承诺保证了攻击者无法通过承诺区分消息。 当μ(λ)=0时，该安全承诺具有完美隐藏（perfectly hiding）性质。
绑定承诺（Binding Commitment）：对于所有PPT攻击者A，绑定承诺满足有一个可忽略的函数μ(λ)使得：

绑定承诺保证了攻击者无法采用不同的消息来生成相同的承诺。 当μ(λ)=0时，该安全承诺具有完美绑定（perfectly binding）性质。在随后的定义中，本文用安全参数λ隐含生成群G的阶p，来保证离散对数在该群中对于PPT攻击者是困难的。

Pedersen承诺（Pedersen Commitment）：
Z p Z_p Zp​:模p非负最小完全剩余系(域)~


Pedersen向量承诺（Pedersen Vector Commitment）：

Pedersen向量承诺在n=1的条件下即为Pedersen承诺。Pedersen向量承诺具有完美隐藏的和在离散对数假设下的计算绑定（computationally binding）。 对于r=0的情况，Pedersen向量承诺具有绑定性质，但不具有隐藏性质。

对某种知识的零知识证明（zero-knowledge proof of knowledge）是一个使证明者说服验证者其拥有某种知识，并且不透露这种知识的任何信息（除“是否拥有该知识”的信息）。例如A拥有两个颜色不同，大小、重量等其他性质均相同的球。A希望向其色盲朋友B证明这两个球的颜色是不同的，同时不向B透露任何球的颜色对应信息。A可以通过以下方案进行：

① B将两个球藏在身后，随机选取一个球展示给A，然后再将球藏于身后，随机选取之前所展示的球，或者另一个球，再次展示给A；
② A告诉B两次展示的球是否是同一个；
③ 重复①②步骤n次，如果A均能正确告诉B结果，则A有1-(0.5)^n的概率能分辨两个球的颜色，即两个球的颜色是不同的。

上述过程中，A作为证明者，说服验证者B相信两个球的颜色不同，同时没有透露任何球的颜色对应信息，这便是零知识证明的一个应用。在区块链的保密交易过程中，零知识证明是证明者可以向验证者证明他发起的交易是合法的，同时不泄露交易的具体细节（如账户余额）。
严格上讲对某种知识的零知识证明和对某种知识的零知识论证（zero-knowledge argument of knowledge）是不同的。Zero-knowledge proof of knowledge具有统计上的可靠性（statistical soundness），而zero-knowledge argument of knowledge具有计算上的可靠性（computational soundness）。

基于离散对数困难问题构造零知识证明

DLP问题的基础知识:
公钥密码学之基于离散对数的密码体制

区块链中的零知识证明

跨链

跨链方法：公证人、哈希锁定、侧链、中继链

Layer2

Reference

1. Layer2、跨链技术常识和零知识证明入门
2. Amit Sahai介绍零知识证明
3. 零知识证明和其未来应用 Elad Verbin Web3 演讲
4. 零知识证明——区块链保密交易的核心实现方案
5. 《区块链实战：金融与贸易落地案例分析》

本文标签： 知识KnowledgeProof