IMCAFS

 Home

initial understanding of "zero knowledge" and "proof"

Posted by santillano at 2020-02-27
all

This article has been updated to GitHub

https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/1/zkp-back.md

Introduction

Past life and present life of "proof"

Ancient Greece: proof = = insight

At the beginning of the 20th century: "proof" = = "symbolic reasoning"

110.643

1960s: "proof" = = "procedure"

In the 1980s, "proof" = = "interaction"

Interactive proof

Alice: I want to prove to you that I have a solution to an equation,

W ^ 3 - (W + 1) ^ 2 + 7 = 0 (solution of equation: w = 3)

Bob: OK, I'm listening

Alice: but I won't tell you exactly what x is,

I'll let you know unless you're willing to pay.

Bob: Yes, but you have to prove it first

I'll give you the money if there's a solution to the equation.

Alice: @ × $% ^ & (black Technology)

Bob: (black Technology)

Alice: & * (black Tech)

Bob: (black Technology)

... (continue black Technology)

Alice: OK, it's over

Bob: Well, you do have solutions,

But did I pay for it,

You'll tell me the answer?

Alice: don't talk nonsense. Pay!

f(w) = 0 w w w w f(w)=0 w

Zero

零

knowledge

知识

Prove

证明

Zero: Alice revealed "zero" knowledge about W, that is, no knowledge.

w

Knowledge: This is w.

w

Proof: it's the black technology part of Alice's conversation with Bob.

What is the use of zero knowledge proof?

Show me the proof X 断言 NP X 断言

Privacy protection of data: in a data form, there are some information that I don't want to be exposed. For example, in that year's report card, I just want to prove to others that I passed the test, but I don't want to let others know whether I got 61 or 62, which will be very embarrassing. I don't have a heart attack, but the insurance company needs to know this, but I don't want the insurance company to know my privacy information. Then I can prove to the insurance company that I have no heart disease, but the whole medical record does not need to be exposed. I am an enterprise, I want to borrow money from the bank, I just want to prove to the bank that I have healthy business and repayment ability, but I don't want the bank to know some of our business secrets.

Computing compression and blockchain capacity expansion: among many blockchain capacity expansion technologies, vitalik's zksnark technology can bring dozens of times performance improvement to the existing Ethereum framework. Because of the proof of calculation, the same calculation does not need to be repeated many times. In the traditional blockchain architecture, the same calculation is repeated many times, such as signature verification, transaction legitimacy verification, smart contract execution, etc. These processes can be compressed by zero knowledge proof technology.

End to end communication encryption: users can send messages to each other, but don't worry about the server getting all the message records. At the same time, the message can also show corresponding zero knowledge proof according to the requirements of the server, such as the source and destination of the message.

Identity authentication: the user can prove to the website that he has a private key, or knows a secret answer that only the user knows, but the website does not need to know, but the website can confirm the user's identity by verifying the zero knowledge proof

Decentralized storage: servers can prove to users that their data is well preserved and do not disclose any content of the data.

Credit record: credit record is another field that can give full play to the advantage of zero knowledge proof. Users can selectively show their own credit records to the other party. On the one hand, they can selectively show the record scores that meet the requirements of the other party, and at the same time, they can prove the authenticity of credit records.

Construct a completely fair transaction protocol for online digital goods [9].

More examples can be any form of data sharing, data processing and data transmission.

Example: map three coloring problem

"Certifier" Alice

"Verifier" Bob

n |E| n Pr

Information vs. knowledge

Information

Knowledge

2^2^41-1

"Knowledge" is related to "computational difficulty", while "information" is not

"Knowledge" is related to what the public knows, while "information" is mainly related to part of what is publicly known

Verifiable computation and circuit satisfiability

P x y y P y P y P

Drawback 1: if the circuit is relatively large, the proof will be very large, and the workload of Bob's inspection and proof will be very large.

Drawback 2: Bob knows all the circuit operation details, including the input, during the verification process.

Black Technology

Written in the end

Roughly speaking, "proof" is the product of "logic", but "logic" and "computation" are closely related. You may feel vaguely some connections between "proof" and "computation", which run through all the time: mechanical reasoning, proof representation and interactive computation. This is an interesting but larger philosophical question.

Reference

Past review

Zkpod: blockchain, zero knowledge proof and formal verification, realizing fair transaction without intermediary and zero trust

Pod tiny -- the simplest protocol to realize zero trust transaction

The vulnerability of "input kana" in zksnark contract resulted in the explosion of many mixed currency projects

Move language: the biggest highlight of Libra in my eyes

Secbit Laboratory

[email protected]

© 2023