###### tags: `ZKP`
# ZKP 純方程式解析

https://medium.com/@imolfar/why-and-how-zk-snark-works-1-introduction-the-medium-of-a-proof-d946e931160#489a

介紹可說是簡易版的核心基礎

假設 驗證方具有一個
f ( x ) = x ³ – 6 x ² + 11 x – 6
可得的解最多為d個(x的最高係數3)
因為方程式的組成為 (x-3)(x-2)(x-1) 最多為三個解
代表與其他方程式最多有d個相同點

## 驗證開始
假設證明方也有一個方程式 x ³ – 6 x ² + 10 x – 5(與驗證方不同)

此時驗證方隨機選擇一個點x=10進行評估
x ³ – 6 x ² + 11 x – 6 = **504**
x ³ – 6 x ² + 10 x – 5 = **495**
可以看出明顯的答案不同

從這能發覺一個問題 雖然是不同的方程式
但這樣撞到同樣點的機率也是有阿

所以x的隨機點會取非常的大
假設我們取x=10^77好了
那機率是 d/10^77 本文是中d=3 3/10^77 機率上可以忽略不記了

所以評估某點兩個方程式的值 是否相同便是主要目的
當然如果兩個方程式一模一樣 x不管帶甚麼兩點都會相同

---
加入同態乘法後
(此處說隱藏隨機數 但概念上E() * witness 也是無法回推的)
這張很重要 **代表所有點都是用隨機數s帶入** 等於帶入一個s
但因為**同態乘法的緣故** 所以變成帶入E(s)
同態乘法沒有的加密數可以乘上未加密數 但不能做加密數的乘法或幕次
所以才需要產生1~d次的E(s) 應對上該次數帶入
後續只要把E(s)乘上係數 就等於評估s點的方程式 並產生答案值了

---


#### Verifer: 信任設定
t(s)應該就是拉格朗日
隨機數會是遠大於拉格朗日方程式的係數 所以不會有0
這邊計算應該跟下面一樣 用拉格朗日的係數乘上E(s)

這步驟就是在傳遞隨機值s的意思了 證明者只需將係數乘上就可以
會有一堆是因為E()沒辦法對自己做 幕次的運算
所以最初的設定者需要傳 E(S^1) E(S^2) E(S^3) ... E(S^d)
E()是可以跟係數相乘的 所以等於直接在隨機s點評估的意思
等於每個E(s)就是隨機數本身帶入係數的概念

### Prover:

先用最初的方程式乘上witness
產生 **p(x)** 還有/t(x) 算出**h(x)**
**p(s)計算** 在將象徵x的各幕次的E(s) 乘上p(x)的係數(cn)
(cn應是ABC*witness產生的)
看起來是能變一個ECC點
**h(s)計算** 計算過程一樣 只是改成h自己的係數

將p(s) h(s)兩個ECC點傳出

### Verifer
驗證p(s) = h(s) * t(s)

這樣便能達到隱藏s又能提供方程式驗證

---

### KEA:

假設現在有一對點 (P, Q) 其中 P * k = Q，沒人知道k的值是什麼，我得到這對點之後我給出一對新的點 (R, S)
並聲稱 R * k = S.指數知識假設可以保證我能得到這對點的唯一途徑
是用點 P 和 Q 同時乘以一個只有我自己知道的值 r.通過橢圓曲線對運算的性質
我們可以在不需要知道k的情況下驗證 R * k = S 是否成立：e(R, Q) ?= e(P, S).

重點是驗證 (R, S)與(P,Q)的係數相同 沒有改變
同時這個過程 驗證者的k不會洩漏於證明者 證明者r不會洩漏給驗證者

驗證者只知道 這個(R,Q)確實是一個k對 (文中是α對)
### POINT!
重點是防止s的幕次被竄改 而不是c的係數
(有道理 因為c的係數本身就應該會被隨意更動 因為會乘上witness)
所以是證明帶入的是 由驗證方提供對應的E(s)係數
而不是自行竄改的E(?)

**代表一系列升幕的E(s) 驗證確實帶入的都是該系數產生的對應E(s)值**
EX:
(x^3,x^2,x^1)
x帶入E(s)
(g* s^3,g* s^2,g * s^1)

可以看成
驗證者 提供 (E(s), E(s)* α) (a,a')
證明者 更改 (E(s)* c,E(s)* α * c) (b,b')
驗證者 驗證 b * α= b'

(α 跟 c 雙方互不知道 因為ECC點乘上隨機數的性質 )

---
## **算式point**

**該文都說exponentiated求幕 求指數
但ECC的求幕其實就是g的乘法
g^3=g+g+g 跟g點乘3的意思一樣**

---
KEA代入實際流程
### vertify
隨機挑選一個α
選擇一個a點(ECC) a點乘上α 變a' 產生對點(a,a')可以稱α對
將對點提供給證明者 證明者使用對點取幕(指數) 產生(b,b')
驗證者使用他知道的α點 就能對b做運算驗證
是否還是同樣的α對(代表係數沒改變)

### prover
選擇係數c(猜測是witness)
照上述方法產生(b,b')
傳回驗證者

### vertify
用驗證者已知的α
乘上傳來的b 是否等於b' 驗證等式
如果相等 代表他還是原來的α對 證明該系數沒有被改變

### 簡易結果
**是為了傳回來的值確實是α對 α對代表E(s)有確實被使用**
Bob knows the applied exponent c, because the only way to produce valid (b,b′) is to use the same exponent
意思是Bob也確實將該對都只乘上c(不然驗證會失敗 而且傳回來的(b,b')也是要拿去計算答案得)

---

上述流程簡化版本
簡化成g的版本 原文寫每項係數單獨計算完 可以同態相加
(this approach was introduced by Jens Groth in [Gro10])

Verifer:
驗證者提供 s的係數 還有s的係數乘上α

Prover:
證明者用上述的s係數值帶入方程式p(n) 再乘上自己方程式的係數c
產生兩個版本 c * s 和c * s * α的 p(n) p(n)' 傳回驗證者

Verifer:
確認轉回的p(n) * α 會等於 p(n)'
那就代表該多項式確實有使用s幕次後的加密值

Prover無法知道α是多少 自然無法去憑空創造α對的方程式
所以只能用驗證者提供的α對運算 (a,a')
且如果證明者使用不同的c乘上 (a * c ,a' * 不是c)
後續驗證α對一樣會失敗

---
### 小總結

while theoretically polynomial coefficients cᵢ can have a vast range of values, in reality, it might be quite limited (6 in the previous example)

以目前來說 跳過加密的部分
**(實際上加密的部分無法破解 MOD E(X)無法逆推成因式
因為組成太多 自然無法逆推 同理g點的倍數無法回推) **
零知識還是有很大的缺點
**因為實際上方程式的係數Ci就是我們的輸入產生的(witness)**
理論上Ci係數可以很大 如果他的值很小(範例中是6)
**這意味著驗證者可以暴力破解有限範圍的係數組合
直到結果等於證明者的答案**

假設有一個二次方程式 每個x的係數範圍是100
那破解便須試上100 * 100 * 100=1000000
只需一百萬次便能破解

## 解法
解法便是將證明都乘上δ(delta)
尤其是驗證等式兩邊會用到的都要乘上δ確保平衡
原理很簡單
上述Ci可以窮舉的原因是 方程式組成是E(s) * Ci產生p(E)
證明方**乘上一個未知的δ** 變成(E(s) * Ci) * δ = p(E) * δ
**驗證方看不到δ** 自然無法複刻 他只能看到答案( p(E) * δ 的點)
就算驗證方想作弊 窮舉E(s) * Ci也沒有意義
因為無法乘δ 在怎麼樣等式都無法相等p(E)

同時驗證的方程式一樣可以通過



---
# PPT

ZK-SNARKS是如何隱藏學生資料的呢?

今天要驗證特定的方程式
評估某一點s，證明者必須提供特定方程式的係數(witness)，帶入s產生的值除掉t(s)會等於0。
(t(s)=拉格朗日方程式代入s)

同態乘法會將s點變成ECC點，EX:x、x^2、x^3 x方程式帶入的s是，E(s)、E(s^2)、E(s^3)代表x幕次不同的指數
(ECC無法做代數方程式意義上的求幕，所以要逐個求x的指數，底下用運用到的E(S)^witness是ECC本身的乘法。

1.E(s)帶入並 * 方程式的係數(witness)產生解，因為ECC同態乘法的特性，一個加密值E(S)乘上一個未加密值(witness)產生新的E(X)，
觀察產生的proof
是無法在方程式計算時間內透過proof的E(X)回推出各個witness的係數
因為MOD的原因
同時EC世界的最高原則就是：隨便給你一個點座標，你沒辦法在 polynomial time 裡面分析出到底這個點座標是多少倍 scalar multiplication 的 generator G

所以無法透過觀察proof回推witness

---
**加密E(x)無法回推(MOD) 也只有窮舉有辦法破解**
**ECC沒有除法 應該是因為MOD 假設A和B兩個點 計算B/A=?
AB兩點都不一定是原先的答案值 因為101 mod 100 =1、100001 mod 100 = 1
所以相除也不知道實際的B是A的幾倍 因為兩者mod後都相同 不同運算也是一樣**

1.問題
證明者提供Ci 驗證者提供E(S)
一堆Ci * E(s) 加起來組合成一個E(X)
**再加密後無法回推的情況 也只有窮舉有辦法破解**

**已公開的角度 被公開的知識有**
(重要的1 and 3，1.E(s)的幕數、3.E(x) 一個ECC的答案值 從驗證方角度E(x)值根本沒有逆推的可能)
1.E(s)的幕數 2.t(s)
證明者提供的3.P(s)=E(x) H(s)一樣E()
驗證方只有E(s)幕數能用 他能看到的只是一個E(x)的點
**只能透過窮舉Ci(Ci是未知的) 去組成方程式對應到P(s)
加密後的值來說看到E(x)連去算他的組成都沒辦法**
#### POINT!
**(因為MOD的原因 其因子組成方式成千上百種 要還原E(x)到原係數不可能)**
**也是因為上述MOD的原因 所以無法得知一個ECC點是G的多少倍**


Without the modular arithmetic, the size of the result gives a clue to its solution. This piece of information is hidden otherwise, while common arithmetic properties are preserved.
同樣的答案2 因為mod的緣故可以有一堆不同的組合
同時也無法得知真正的答案值是多少(因為被mod運算 看不到商 自然無法透過商 * 乘數 + 餘數回推真正得答案 隨著MOD越大 其組成更多)
透過MOD隱藏真正的答案值 自然難以回推出因數有哪些

(witness足夠大的情況，太小窮舉還是有機會)。
(不太對 因為只要暴力組成Ci係數(即witness) 一樣有機會通過驗證，用是否能通過驗證當基準比較好
例如2
)

---
2.想得到正確的解需要讓方程式評估後等於0
代表破解需要原先的正確的方程式係數
**當Ci方程式係數夠大 窮舉也無法暴力破解範圍內的係數組合。**

某種程度 零知識不只是指出隱藏加密 提出的證明很難再方程式計算時間內破解也是零知識

---

### Non-interactivity & Distributed Setup

上述的α和t(s)
t(s)有可能被驗證者自行拿來造假 或是提供給特別的證明者串通
α留存於驗證者也可能被進行攻擊

因此我們應將參數加密後都公開(CRS)
那加密的方法如同E(s)點 就是套進ecc變 G^α G^(t(s))
如此原數字就安全了 同時也留存原本的運算特性

這時就產生一個問題 上述的驗證流程如截圖
這邊都是做加密值乘非加密乘的算式 沒有問題
但改成都是ECC加密點 加密值是無法乘上加密值的
此時便需要用到

---
### Cryptographic pairings (bilinear map) 雙線性映射

提供了一個e配對加密 g^a * g^b = e(g^a,g^b)

**可以簡單看成g^ab 同時具有同態加密的性質
以及e配對之間的交換律**

這樣便能驗證乘法性值
可以看成**額外提供一個特殊的乘法算式e()** 給ECC
同時具備一些算法特性
算式如下圖 可以使兩個ECC點相乘
使得底數指數對調相乘 使其具有乘法交換律相關性值

但無法使用已產出的e配對在乘上ECC點
（例如，e (( ab ) ᵍ , g ᵈ )） 因為沒有abd的存在

e配對的數值底數已被調換 看成指數相同 底數相乘

e配對的核心屬性 可看出具有交換律的特性
假設g=2 a=2 b=3:
2^2 * 2^3=2^6 底下運算性質調換都沒問題

Technically the result of a pairing is an encrypted product of raw values under a different generator g of the target set
技術上來說加密配對e 本質上是**使用不同g原始值的加密乘積相加**
將他也看成ECC加密
i.e., e(gᵃ, gᵇ ) = gᵃᵇ 因此具有同態加密的性質
**(可視為配對e保有同態加密的特性)**
底下範例 可用多個配對的加密乘積相加 g^ab+g^cd