Introduction Zero Knowledge -- Alon Rosen
Introduction Zero Knowledge -- Alon Rosen
Zero-Knowledge Proofs
It's mainly about the content of The 9th BIU Winter School on Cryptography-Zero Knowledge and some understanding of my own.
What is zero knowledge good for
Can prove that I know a secret without having to reveal it.
Identification, Membership, Ownership and so on
A zero-knowledge identity proof is a term used to refer to an authentication scheme where one party proves to the other to have a particular piece of knowledge that proves ownership of the identity.
Protocol Design
Design against parties that follow instructions. (against 针对)
Secure against arbitrary deviation from the protocol.
Use ZK proof to force honest behavior
Trusted Party, a general cryptography framework which is more general even than zero knowledge, can be turned into a cryptographic protocol using zero-knowledge. Zero knowledge is what enables us to go from a setting which we trust into a setting in which we don't trust.
1 | graph LR |
Note: Crypto is not just about zero knowledge. Zero-Knowledge is just a means to an end.
Weaker definitions are also useful. (WI/WH/NIZK)
Proof Systems
A proof is a method for establishing truth. what is the method depends on the context in which it's deployed, such as legal(truth is determined by a jury or by a judge), authoritative, scientific, philosophical, mathematical(Axiom ->π->-> Propositions).
Euclid put forward that inference should be cast in terms of axioms and rules of inference. After that,
Two element have been added to the notion of proof: probabilistic and interactive. You are willing to accept that small statement with the small probability of error and the notion of interaction
The language of true statements
There is no prover here. To define a classic proof, you don't need to talk about prover at all and verifier is what matters. The verifier is the most important entity in a proof and this is also for people implementing a protocol. All that matters is what the verifier does at least for the soundness of proof.
NP Proof System
Boolean Satisfiability【布尔可满足性问题 SAT】
SAT 是一个 NPC 问题，每一个属于 NP 的都可以归纳到 SAT 问题上。
线性等式：P 问题，容易计算。 Structured：是一个结构化的问题。
矩阵乘法 linear equations 是 P 问题，期最佳渐进复杂度为\(O(n^{2.373})\).wikipedia reference
the Class P：P 类问题 poly-time(多项式时间) P 类问题：在多项式时间下有解。 NP 类问题：在多项式时间下不能确定能找到答案，但可验证。 NPC 类问题：NP 类问题都可以归约到一个 NPC 类问题。
二次剩余 Quadratic Residuosity
[Quadratic Residues] - What are Quadratic Residues? - YouTube
是一个 NP 问题，在多项式时间内不一定能解出来，但是一定能在多项式时间内能验证。
总结 有效的验证者 等价于 多项式时间的验证者，下面说明如果是下面的问题，则都是可以在多项式时间下可验证的问题，即说明是有效的验证。
证明非成员
对于 Linear Equation 是 P 问题，可以在多项式时间内确定。
对于 SAT 和二次剩余是 NP 问题，无法在多项式时间内确定。
最原始的证明就是：发送所有可能的 witness，逐个检查他是否满足 SAT 或 QR。而二者的 witness 都是按指数增长的。所以 naive proof exponentially large 按照指数增大。所以现在没有什么可以帮助你验证 non-membership 的 statement 的。这便是 Shafi Goldwass 等人想法的来源。
他们在 GMR’85 中提出了交互式证明，允许证明使用：随机性（概率容错）和交互（增加 prover）
从 DAPP 开发角度看
相关内容的公开资料很丰富，我 post 一些希望对你有帮助：
从需求出发如何根据不同 zk 技术的 tradeoffs 进行方案设计:
具体应用的交互建议看一些 zk dapp 的源码以及在本地跑一跑客户端，这样会有更直观的理解： 例如：https://github.com/vplasencia/zkSudoku
