Let's take a look at how Mina describes itself:

Mina is the first cryptocurrency protocol with a succinct blockchain. Current cryptocurrencies like Bitcoin and Ethereum store hundreds of gigabytes of data, and as time goes on, their blockchains will only increase in size. With Mina however, no matter how much the usage grows, the blockchain always stays the same size - about 22kb (the size of a few tweets). This means participants can quickly sync and verify the network.

This breakthrough is made possible due to zk-SNARKs - a type of succinct cryptographic zero-knowledge proof . Each time a Mina node produces a new block, it also generates a SNARK proof verifying that the block is valid. All nodes can then store the small proof, as opposed to the entire chain. By not having to worry about block size, the Mina protocol enables a blockchain that is decentralised at scale.

We can sum up several key points from the above:

**Constant**blockchain size - 22kb only!- Only
**the latest block/proof**is needed to verify the entire blockchain.

These really sound thrilling! It means anyone who wants to be a node to participate in the blockchain only takes **a few seconds to sync**, while nodes of other blockchains have to sync blocks since genesis to verify. More importantly, light clients for end users, like a wallet, can now **confirm the block directly in a very lightweight manner** instead of relying on a 3rd party server/node to tell them what's going on in the chain without validating measures.

This magic lies within the **recursive zk-SNARKs** technology. A simple figurative example is: You will visit a park for 7 days. How to prove it in one photo?

Day 1, you take a photo with a calendar showing the date. Day 2, you hold the photo taken from Day 1 and a calendar showing the date. Day 3, you hold the photo taken from Day 2 and a calendar showing the date. Repeat the same procedure until Day 7. Now you have a recursive proof of your tour in one photo.

So, everything so far, from concept to technology, seems to make sense. But wait, something isn't right.

This is the easy part to be disproved. Everyone who has common sense can figure it out.

Imagine you have a growing number of users. How is the size of your database fixed? In any system that needs to express states on a growing scale, the only thing that can be a constant is the state root, not the state itself.

But, where is the state stored? It can be anywhere, in a real full node or an archive node, but not your 22Kb one. Actually, the state of a system can be very large without any upper limit. So if your node gets a constant size blockchain, it's unable to verify specific detail. Instead, you're merely verifying the validity of the proof from some computations. What are those computations? You have no clue at all without additional info. Apparently, it's not enough in most cases.

In fact, every blockchain can be named a constant sized blockchain, if you only store its latest block header. It does sound hilarious LOL.

You might say, but block headers of other blockchains are not recursive to all previous blocks since genesis, so it still makes a difference. So yeah, if you do, it proves you learned well on this topic.

But, what if ...?

Don't worry. We won't initiate a zero-knowledge or recursive snark course here. It's sufficient to fact check their claims with a thought experiment.

Let's start this part with a validator node's perspective: he wants to validate the blockchain because he's sceptical about:

- The
**latest block**is a fake one. In this case, he believes all other blocks are valid. - There are
**some blocks in the remote past**that are invalid. For some unusual reason, those blocks remain there formally or virtually: the majority of validators of the network colluded(formal), or the node he connected to is lying about the history(virtual), etc.. Someone may call the first reason a hard fork, but that doesn't justify the case, because hard fork is a neutral term, which can also be secret and dirty - maybe only the colluders know it happened as there were few users or validators in the past. Anyway, he's going to find out.

For case 1, it's easy to validate.

In the Mina blockchain, he can use `VerifyBlock(S[i−1], B[i])`

to verify, where `S[i-1]`

is the previous blockchain summary and `B[i]`

is the latest block.

In other blockchains, he can also use a similar technique: `σ[t] ≡ StateTransition(σ[t-1], T)`

, where `σ[t-1]`

is the previous state and `T`

is the transaction that caused the state change. Beware: here he only needs to download the previous state trie and the new transaction. Namely, he doesn't have to sync all data since genesis.

See? Neither Mina nor other blockchains have to sync data since genesis.

Note: The above description is **just a simplification in theory**. For blockchains like Ethereum, without a proper part of the state trie, there's no way to compute state transition.

Syncing doesn't have to start from the genesis point, but it also takes a significant amount of time to download the entire state trie in practice. If we consider there are up to 400 txs in a block, then we can find the relevant nodes of the state trie for those 400 txs and only sync the relevant ones in the trie, such that the state transition computation can be roughly in a short constant time. So for this particular task in our case, a customised client with small spacing download checkpoints(like Parity) and partial state trie syncing is preferred.

In case 2, ofc, you have to sync from genesis for an ordinary blockchain. There's no way to tell whether an indefinite remote block is valid or not if not from genesis. According to `StateTransition(σ[t-1], T)`

you have to validate block by block to justify the entire chain.

For Mina, can you really forget about the old blocks and only care about the latest one, due to recursive snarks directing a clear path to the very beginning?

In the Imaginary perfect Mina chain, a perfect **ZKP path**(blue line) leads to the genesis. Though you can't tell what happened along the path, it's unassailable that you can prove the path exists with recursive snarks proof.

But! **Which** path? Recursive to **where**?

Consider this: Someone runs a fork of the Mina chain. He copied Block 2' from the forked chain directly to Mina. How did he do that is irrelevant to our discussion here, as I just mentioned 2 possibilities in the above paragraphs. Anyway, it's just there. There is no cheating in Block 3, 4, 5, 6.

According to Mina's claim, our validator **should only check Block 6** to justify the entire blockchain. When he validates the proof of Block 6, he will find nothing wrong because the **ZKP path** leads him to the genesis of the **forked one**! And he doesn't know what the true path/genesis should be. Actually in the above picture the 2 paths even share an identical genesis. It's computationally correct, sound and solid, and indistinguishable if you don't sync from the real genesis to get a right path.

**Actually, case 1 is a subset of case 2. Thus it's inevitable to be fooled even only consider the latest block, if the same measure were applied.**

You'll get a detailed understanding if you know the data structure of Mina blocks.

I think you may get the point now: The recursive ZKP used here can prove you did come from **some origin**. The origin exists. The path exists. The computations and state transitions along the path exist.

But what it misses are, **who/where/what** are those things. Just like when it's cloudy in the daytime, you can tell there exists a light source in the sky, but is that the Sun? The moon? Or a giant light bulb? You have to confirm it above the cloud.

If we use the photo example again, I can just give you another recursive photo taken elsewhere. You have no idea whether it was taken in the park unless you know the **full view** of the park. Namely, you sync from the genesis to get a full view.

Mina is an excellent brand new paradigm of blockchain design that utilises ZKP. It's innovative enough to have its position in the fame hall of the industry. But:

- 22Kb constant size blockchain is only about marketing.
- One block to verify the entire blockchain is incorrect.

Things are better when they remain true and plain.

I give you 1998 boxes and claim that 1000 boxes among them can form a valid Mina chain. However, you only know the detail about Block Genesis and Latest 999, including the recursive ZKP proof in 999. Can you tell me, which other 998 boxes should be the correct blocks and their arrangement, i.e., show me the right path and history?

Ofc you can't. Or it just violates the information theory - your recursive ZKP is not an infinite compression algo. This is also true for the 22Kb constant size topic.

*If you find submirror valuable, please consider donate to wong2.eth to help cover server cost.*

- 只以故事和童话作例子来论述ZKP，无法深入其本质。
- 内含大量密码学术语，数学公式，学术论文等，对初学者而言过于复杂。

本文提供了对ZKP简明扼要的概述，并从数学、密码学和编程角度进一步阐述ZKP的核心要素。

如何向色盲患者证明两个球的颜色确实是不同的？这其实并不复杂：

让他在手里握住两个球，背到背后，然后随机选择交换或不交换两个球的位置，再展示给你看，你告诉他这两个球的位置是否有变化。

在他看来，你可以通过瞎蒙来完成一次证明。不过，如果成千上万次地重复这个过程：如果你总是能说出正确答案，那么靠纯蒙的方式来保持一直正确的概率，是小到可以忽略的。因此可以通过这种方式来向色盲患者证明：两个球的颜色确实不一样，并且我们也有感知和区分的能力。

上述证明过程是典型的零知识证明：

- 验证者无法在证明过程中获得任何关于颜色的知识，因为经过验证过程后他依然没有区分颜色的能力。
- 该验证过程是概率性的而非决定性的。
- 该过程是交互式的，需要多轮交互。不过，零知识证明中也有许多协议，通过高级技巧将证明过程转化成了非互动式的。

我们已经分享了一种现实世界中的零知识证明的例子，接下来再来看一下在二进制世界中如何实现零知识证明。

Arthur是Elon的朋友，并且知道对方的手机号。Betty不知道Elon的号码。如果Arthur想要向Betty证明他知道，但又不想泄露号码，应该怎么实现呢？

一种不成熟的方案是，Elon发布自己电话号码的哈希，Arthur通过一个程序输入哈希的原像，程序进行运算并检查结果。这个方法有一些致命的缺陷：

- 根据哈希，Betty可以通过暴力破解的方式得到原像，能破解出来的概率是不可忽略的，而且得到的结果几乎是确定性的。
- Arthur必须向该程序输入原像。如果程序在Arthur的电脑上，Betty就会对此有疑问：我怎么知道你有没有作弊，你的电脑也许会一直声称你的证明是对的？
- 如果程序在Betty的电脑上运行，Arthur也会担心，自己输入的信息会不会被窃取，即使程序肉眼可见的代码中并没有窃取信息的命令。
- 因为无法将程序分开在不同的环境中运行，这个信任问题是难以解决的。

常规的方法在这里碰壁了，是时候让零知识证明出场了！

在此我会用零知识证明中的Sigma Protocol来解决问题，因为它比较简单。并且，为了简洁和易于理解，这里不会使用严格的密码学和数学中的定义、术语及推导过程等。

使用零知识证明证明一个人有特定的知识，我们采取如下办法：

- 定义一个
`P`

阶的有限群及其生成元`g`

。我们可以暂时忽略这些奇怪的名词具体什么意思。 - 根据上面的定义，某个拥有知识或能接触到知识的第三方，将知识（记为
`w`

）通过`h = g^w (mod P)`

的方式加密后，将h发布出去。 - 证明者启动零知识证明流程。生成一个随机数r，计算
`a = g^r`

，并将`a`

发送给验证者。 - 验证者生成一个随机数
`e`

并发送给证明者。 - 证明者计算
`z = r + ew`

并发送给验证者。 - 验证者检查
`g^z == a·h^e(mod P)`

。如果为真，则验证者确实掌握其声称的知识。

好啦，该证明协议到此就结束了！非常简短，但你仍可能对上面的一些数学运算感到困惑，但这不要紧，我们先有个大概印象再深入理解。

我用Python写了一个简化的Sigma Protocol的示范程序，对理解上述过程有很大帮助。在程序中，你既可以扮演定义和发布知识的第三方，也可以成为掌握了知识或没有掌握知识的证明者。

```
from random import SystemRandom
# Cryptography Public Parameters
g = 22500 # Generator of the finite group
P = 3213876088517980551083924184682325205044405987565585670609523 # Order of the finite group. A big prime number.
# The encrypted knowledge, will be set by a 3rd party.
# Its preimage, which the prover needs to prove he knows, is not accessible to both the prover and verifier.
h = None
# These parameters will be set in further proving steps and passed from the verifier to the prover or vice versa.
a = e = z = None
def specifyKnowledge(w):
global h
h = pow(g,w,P)
print('\n'+'The knowledge topic has been designated.'+ '\n' +
'Neither the verifier nor prover can read since it\'s discarded after this func executed.' + '\n' +
'Only its encryption is publicly known.' '\n' +
'If the prover hasn\'t learned it somewhere else before, he won\'t be able to pass the verification.''\n')
class Verifier:
def __init__(self):
return
def verify_step1(self):
global e
e = SystemRandom().randrange(P)
print('Verifier:')
print('random number b = ',e,', b -----> Prover','\n')
def verify_step2(self):
print('Verifier:'+'\n'+'Checking if pow(g,z,P) == (a * pow(encryptedKnowledge,b,P)) % P:')
if pow(g,z,P) == (a * pow(h,e,P)) % P:
print('Accept! Prover knows the knowledge','\n')
else:
print('Reject! Prover knows nothing','\n')
class Prover:
def __init__(self, knowledge_to_verify):
self.k = knowledge_to_verify
self.r = SystemRandom().randrange(P)
print('Start proving','\n')
def prove_step1(self):
global a
a = pow(g,self.r,P)
print('Prover:')
print('random number r = ',self.r)
print('a = g ** r % p = ',a,', a -----> Verifier','\n')
def prove_step2(self):
global z
z = self.r + e * self.k
print('Prover:')
print('z = r + b * knowledge_to_verify = ',a,', z -----> Verifier','\n')
print('\n'+'-------- Zeroknowledge Example Begins --------'+'\n')
specifyKnowledge(w = int(input("Enter your secret knowledge (Intger):")))
prover = Prover(knowledge_to_verify = int(input("Enter Prover's knowledge (Intger) :")))
verifier = Verifier()
prover.prove_step1()
verifier.verify_step1()
prover.prove_step2()
verifier.verify_step2()
```

Source code: dysquard/SimpleZkpExplanation · GitHub

Just `python example.py`

.

这套流程背后的核心数学原理是离散对数难题：当P是一个很大的质数时，对于给定的`h`

，很难找到满足`h = g^w(mod P)`

的`w`

。该原理适用于上面所有类似的式子。

我们来一步一步解析下：
经过加密的知识`h = g^w (mod P)`

，是难以被暴力破解的。由于求余运算的特点，即使被破解了也不具备单一确定解。这意味着对证明者而言，通过暴力破解来作弊，欺骗验证者，是不可行的。

然后我们将3，4，5步作为一个整体来看一下他们为什么要交换这些随机数：

I. 证明者并不想暴露其秘密，所以他必须用随机数包裹一下将其隐藏起来。而验证者也需要通过添加一些随机数，让该知识可被自己验证的同时防止证明者作弊，而且不会窥探到证明者的秘密。

II. 如果验证者先发送了随机数`e`

（即将3和4步交换一下），很明显，证明者可以通过编造`a = g^z·h^-e`

来在最终检查中欺骗验证者，即使没有知识也可以通过。所以证明者必须先手发送一个承诺(a=g^r)，但非r本身，来避免可作弊场景，同时不让验证者通过`w = (z - r)/e`

提取到秘密。

III. 在收到承诺后，验证者向证明者发送随机数`e`

。由于其本身或者其衍生物无法泄露任何一方的信息，这个数不需要加密。之后证明者计算`z = r + ew`

并将z发送给验证者。验证者最终通过检查`g^z= g^(r+ew)= g^r·(gw)^e= a·h^e`

来确定证明者是否掌握知识。

通过这种往返交错的结构，我们收获了三个性质：

**完备性**:
当且仅当证明者输入正确知识，验证才能通过。

**可靠性**:
当且仅当证明者输入错误知识，验证才会失败。

**零知识性**:
验证者无法在验证过程中获取任何知识。

上述三点即零知识证明的核心特性。通过数学和密码学，我们构建出了一套光怪陆离的证明体系。恭喜你一路走了这么远，现在应该已经可以说正式迈入了富丽堂皇又奥妙无穷的ZKP圣殿。 Have fun!

我们现在来考虑一些魔幻场景。如果一个证明者具有预言或篡改验证者生成的随机数的超能力，我们称其为模拟器。

设想，模拟器在验证者的随机数`e`

生成前就对其进行了篡改，确保其生成后是自己预设的值。根据上面II所说，这种能力使模拟器能编造承诺`a`

来欺骗验证者。不论模拟器的输入是什么，验证者总会得出结论模拟器具有知识，然而实际上他并没有。

显然，经过这种思想实验我们可以得出结论，验证者无法在该零知识证明协议中获取任何知识，也即其零知识性是成立的：

零知识性 <== ∀模拟器S，使得S(x)与真实的协议执行不可区分，其中S(x)： 选择随机的`z`

和`e`

，令`a = g^z·h^-e`

，其中(a,e,z)的分布与真实的随机数环境一致并满足`g^z=a·h^e`

。

再来想象一下另一种超能力者——抽取器，具有时光倒流的能力。不过这次是抽取器作为验证者，面对一个正常的证明者。

当协议结束时，抽取器发起时间倒流，回到协议的起点，并持有上一轮得到的`(z, e, a)`

。现在，协议重新执行一遍。由于证明者没有超能力无法进行时间旅行只能在固定的时间线上做确定的事，他又生成了一个一模一样的随机数`r`

以及承诺`a = g^r`

，而抽取器则可以生成新的随机数`e'`

给证明者。

现在，抽取器获得了：
`g^z= a·h^e, g^z'=a·h^e => g^(z-z') = h(e-e') `

=> 加密后的知识 `h = g^((z-z')/(e-e'))`

=> 知识 `w = (z-z')/(e-e')`

.

显然，只要证明者真的掌握了知识，抽取器总是可以将其抽取出来，也即可靠性成立：

可靠性 <== ∀抽取器E，对给定的任何h，在掌握`(a,e,z)`

,`(a,e',z')`

且`e≠e'`

的情况下，都能输出`w`

s.t. (h,w) ∈ R.

完备性不需要任何特殊角色来证明，因为：
`g^z`

= `g^r+ew`

= `g^r·(g^w)^e`

= `a·h^e`

.

*If you find submirror valuable, please consider donate to wong2.eth to help cover server cost.*

- Too naive to explain in a deeper perspective, i.e., only employ some physical or real-world games or stories to exemplify ZK, without any insight into how it is implemented in practice and why it works.
- Too overwhelming for a beginner to understand, filled with plenty of cryptography jargon, mathematical formulas, academic papers, etc.

This article will provide a simple yet insightful elaboration for ZK in math, cryptography, and coding, with minimal prerequisite knowledge.

How to tell colour-blind people that two balls of distinct colours are literally different? It's not complicated:

Let him hold those two balls in hand, hide behind his body, and swap their position randomly. Then he shows you the balls, and you tell him whether the balls were swapped.

From his perspective, you can answer correctly by guessing. But repeat this process 100 or even more times: if you're always able to deliver the correct answer, the probability of guessing all by luck is negligible. Consequently, we can convince our colour-blind friend we are not lying about the truth that these two balls are different in colour and our ability to perceive and distinguish.

The proving method above is precisely a kind of zero-knowledge proof:

- Verifier never learns any knowledge of colour because he's still not able to distinguish them after the test.
- It's probabilistic proof instead of deterministic proof.
- It's interactive and multi-round. There are also non-interactive ZKP schemes with advanced transformation techniques.

We've seen an example of ZKP in the physical world. Now let's delve into cyberspace.

Arthur is Elon's friend, and he knows Elon's phone number. Betty doesn't know it, but Arthur wants to prove that he does without disclosing it to Betty, so how to do it?

A naive way is that Elon publishes a hash of his phone number, and Arthur enters the pre-image of that hash via a programme for hash calculation check. But this method is fundamentally flawed due to:

- Betty can brute-force the pre-image according to its hash to get the nearly deterministic single result with non-negligible odds.
- Arthur must input the pre-image to that programme. Betty will suspect it will always return a positive pass if it's on Arthur's computer.
- On the other hand, Arthur is afraid that Betty will steal the knowledge she typed if it's on Betty's side.
- As you can't separate the runtime to let Arthur and Betty run different codes on their own machines respectively, this trust issue is hard to solve.

So the regular easy way won't work. Time for ZKP to show up.

I'm gonna use a relatively simple ZKP scheme named Sigma Protocol here to solve this problem. Also, for the sake of simplicity and comprehensibility, rigorous definition / terminology / inference of cryptography or arithmetic won't be adopted here.

To prove one has certain knowledge with ZKP, we can do it by the following procedures:

- Set a finite group G of order
`P`

and its generator`g`

. We can ignore what these weirdos mean first. - With the terms defined above, a third party who has or has access to the knowledge(denoted by w) publishes the encrypted knowledge
`h = g^w (mod P)`

. - Prover starts the proving procedure. Generate a random number r, evaluate
`a = g^r`

, and send value`a`

to Verifier. - Verifier generates a random number
`e`

and sends it to Prover. - Prover evaluates z = r + ew and sends it to Verifier.
- Verifier checks
`g^z == a·h^e(mod P)`

. If true, Prover has the claimed knowledge.

Well, the protocol just finished here! It's short, but still seems a little bit overwhelming with these mathematical denotations. But it will be ok to have an overview first and delve into the details later.

I wrote an easy toy programme for Sigma Protocol in Python. You can cosplay the 3rd party knowledge publisher who defines the knowledge and the Prover with or without the exact knowledge waiting to be verified. It's pretty helpful for understanding the above procedures.

```
from random import SystemRandom
# Cryptography Public Parameters
g = 22500 # Generator of the finite group
P = 3213876088517980551083924184682325205044405987565585670609523 # Order of the finite group. A big prime number.
# The encrypted knowledge, will be set by a 3rd party.
# Its preimage, which the prover needs to prove he knows, is not accessible to both the prover and verifier.
h = None
# These parameters will be set in further proving steps and passed from the verifier to the prover or vice versa.
a = e = z = None
def specifyKnowledge(w):
global h
h = pow(g,w,P)
print('\n'+'The knowledge topic has been designated.'+ '\n' +
'Neither the verifier nor prover can read since it\'s discarded after this func executed.' + '\n' +
'Only its encryption is publicly known.' '\n' +
'If the prover hasn\'t learned it somewhere else before, he won\'t be able to pass the verification.''\n')
class Verifier:
def __init__(self):
return
def verify_step1(self):
global e
e = SystemRandom().randrange(P)
print('Verifier:')
print('random number b = ',e,', b -----> Prover','\n')
def verify_step2(self):
print('Verifier:'+'\n'+'Checking if pow(g,z,P) == (a * pow(encryptedKnowledge,b,P)) % P:')
if pow(g,z,P) == (a * pow(h,e,P)) % P:
print('Accept! Prover knows the knowledge','\n')
else:
print('Reject! Prover knows nothing','\n')
class Prover:
def __init__(self, knowledge_to_verify):
self.k = knowledge_to_verify
self.r = SystemRandom().randrange(P)
print('Start proving','\n')
def prove_step1(self):
global a
a = pow(g,self.r,P)
print('Prover:')
print('random number r = ',self.r)
print('a = g ** r % p = ',a,', a -----> Verifier','\n')
def prove_step2(self):
global z
z = self.r + e * self.k
print('Prover:')
print('z = r + b * knowledge_to_verify = ',a,', z -----> Verifier','\n')
print('\n'+'-------- Zeroknowledge Example Begins --------'+'\n')
specifyKnowledge(w = int(input("Enter your secret knowledge (Intger):")))
prover = Prover(knowledge_to_verify = int(input("Enter Prover's knowledge (Intger) :")))
verifier = Verifier()
prover.prove_step1()
verifier.verify_step1()
prover.prove_step2()
verifier.verify_step2()
```

Source code: dysquard/SimpleZkpExplanation · GitHub

Just `python example.py`

.

The core working mechanism is the hardness of Discrete Logarithm: when P is a big prime number, given h, it's hard to find w such that `h = g^w(mod P).`

This property also applies to similar equations above.

Let's take it step by step:
Encrypted knowledge `h = g^w (mod P).`

Here we encrypted the knowledge into a form that is hard to brute-force. And due to the nature of modulo operation, there's no definite single solution even if it's "compromised". This means it's infeasible for the Prover to cheat or for the Verifier to obtain knowledge by cracking it.

Then, we take steps 3,4,5 as a whole to understand why they are exchanging random numbers:

I. Prover doesn't want to reveal his secret knowledge, so he must encrypt that value with randomness to lock it up. The Verifier also needs to transform it to a checkable one to verify its validity while maintaining its secrecy by adding some randomness from Verifier.

II. If the Verifier sends the random number `e`

first(i.e., swap steps 3 & 4), it's obvious Prover can make up `a = g^z·h^-e`

such that it satisfies the final check even without knowing the knowledge. So Prover must first send a commitment(a=g^r) but not the random number r itself to avoid the cheating scenario, also disabling the way for the Verifier to extract knowledge w by evaluating `w = (z - r)/e`

.

III. After receiving the commitment, Verifier sends a random number `e`

as a challenge to Prover. It's not encrypted as no info can be inferred from it or further derivatives. Then Prover returns z = r + ew to Verifier. Verifier runs the final equality check `g^z= g^(r+ew)= g^r·(gw)^e= a·h^e`

.

With this interlacing weave structure, we got 3 sophisticated properties:

**Completeness**:
The Prover will pass the verification if and only if he entered the correct knowledge.

**Soundness**:
The Prover will fail to pass the verification if and only if he entered a wrong knowledge.

**Zero-knowledge(-ness)**:
Verifier won't obtain any knowledge during the verification.

They are just the very core essences of ZKP. Marvellous and melodramatic, isn't it? Congrats, you've made it this far, where I can assume you just entered a panoramic view of Zero-knowledge space. Have fun!

Let's consider some supernatural forces. A Prover, who has the ability to predict or tamper with Verifier's random number `e`

before its generation, we call him the Simulator.

Easy to see, in such a manner, Verifier can't obtain any knowledge in this protocol, i.e., the Zero-knowledge property holds true:

Zero-knowledge <== ∀ Simulator S s.t. S(x) is indistinguishable from a real proof execution, where S(x): Choose random `z`

and `e`

, and let `a = g^z·h^-e,`

where (a,e,z) have the same distribution as in a real run random values satisfying `g^z=a·h^e.`

Another supernatural force comes into play, the Extractor, with the ability to rewind time. She acts as Verifier vs. a normal Prover.

When the protocol finishes, Extractor launches her time rewind attack to dial back the clock to the beginning of the protocol, with `(z, e, a)`

in the previous execution. Now the protocol replays, but Extractor sends a different random `e'`

to Prover, who is not a time traveller so still outputs the same random `r`

, also `a = g^r`

.

Now, Extractor has:
`g^z= a·h^e, g^z'=a·h^e => g^(z-z') = h(e-e') `

=> Encrypted Knowledge `h = g^((z-z')/(e-e'))`

=> Knowledge `w = (z-z')/(e-e')`

.

Obviously, an Extractor can always extract knowledge as long as Prover owns it, i.e., the Soundness property holds true:
Soundness <== ∀ extractor E that given any h and pair of transcripts `(a,e,z)`

,`(a,e',z')`

with `e≠e'`

outputs `w`

s.t. (h,w) ∈ R.

There's no need to prove Completeness with any special character as this holds true:
`g^z`

= `g^r+ew`

= `g^r·(g^w)^e`

= `a·h^e`

.

*If you find submirror valuable, please consider donate to wong2.eth to help cover server cost.*

*If you find submirror valuable, please consider donate to wong2.eth to help cover server cost.*