# 隱私信貸應用程式
###### tags: `NCKU`

## 介紹傳統信貸流程
### KYC
傳統 KYC 可以透過核對使用者身份證、護照或其他相關資訊，以及客戶照片等方式來驗證使用者身份。

過程中，如果有第三方竊聽或駭入資料儲存的組織，則使用者存在被冒充的風險，因此，銀行資安組織成本也需要持續投入。

### 聯合徵信
徵信用紀錄主要包含5個部分：借貸資料、信用卡資料、信用評分分數、聯徵查詢紀錄、通報紀錄資訊…等項目。

* 借貸資料：包含借款餘額、共同債務、其他債務資訊、借款逾期、催收或呆帳紀錄。
* 信用卡資料：包含持卡紀錄、帳款資訊以及帳款總餘額。
* 信用評分分數：信用分數介於200到800之間，一般來說400分以下即視為信用不良。
* 聯徵查詢紀錄：最近1年內的查詢紀錄，包含被查詢紀錄及當事人查詢紀錄。
* 通報紀錄資訊：如果被通報為可疑帳戶或詐騙，也會註記於聯徵紀錄。

### 可以改進的地方
對使用者而言可以更好的地方
* 個人身份的資料洩漏
* 無法得到準確貸款金額，除非完成聯徵
* 流程等待時間很久

對銀行端而言可以更好的地方
* 電話行銷成本
* 審核信用與身份成本
* 時間成本 (從接觸客戶至完成信貸週期較長)

## 隱私信貸應用程式流程
若有人聲稱他為使用者 Alice，此人應掌握了 Alice 相關的重要知識，包含 Alice 擁有的隱私，例如，網路銀行帳號密碼、護照照片、最近一次的消費記錄以及 Alice 的生物數據(e.g. 臉部)...等。

這些隱私知識，極有可能與相關組織共享(身分證號與政府共享、網路銀行密碼與所屬銀行共享...etc)

而 Alice 若聲稱其擁有數種資產，則 Alice 應掌握了與資產購買方共享的秘密，例如，拍賣所商品的購買證明、信用卡刷卡紀錄與存摺數據。

### 零知識 KYC 與資產聲明
KYC 可分成幾個步驟:

* Rules: 零知識證明首先需要遵守一組預定義規則，例如需要提供與護照的合照，並清楚將護照號碼與照片顯示出來。
* zk-circuct generator: 中介透過所定義的 rule，產生可供驗證的方程式，例如，將 **生物資訊變成電路參數**。
* Generate parameters: 中介產生要交給證明密鑰組 $p_k$ 與驗證密鑰組 $v_k$。這邊的密鑰組是類似 Session Key 的存在。
* Proving: 證明者使用 **自身知識帶入 $p_k$ 做隨機處理，產生證明** 並回覆給中介。
* Verification: 驗證者使用 $v_k$ 對證明驗證，確認是否正確且符合規則。


當使用者能夠證明身份時，資產證明也跟 KYC 過程類似。

#### 特性
* 快速
* 隱私
* 成本低廉且無人為偏見

## 技術實現 Demo

### 生成包含生物數據與隱私資料的問題
這邊之所要轉為約束是，當帶入正確的輸入時，若計算出的係數滿足下面約束的所有門，代表者每一步驟的計算皆滿足，而當每一步驟計算皆滿足，則視為計算結果滿足正確性。

**1. 透過將生物數據轉換為方程式參數，例如 $\lambda$ 代表生物數據**

| Algebraic Circuit | R1CS |
| -------- | -------- |
|  |  |

**2. 將參數作為算數門，並求出一階約束函式 R1CS**
Provided variable: [$one$, $x$, $\overline{y}$, ${\lambda}_1$, ${\lambda}_2$, ${\lambda}_3$]

| First Gate | Second Gate | Third Gate | Fourth Gate |
| -------- | -------- | -------- | -------- |
|  |  |  |  |

| A | B | C |
| -------- | -------- | -------- |
|  |  |  |

**3. 將 R1CS 轉為二次計算函式**

為了使得計算結果可快速驗證，不需反覆確認每個門的運算，我們可以接約束轉為一個方程式格式。 $R1CS \rightarrow QAP(Quadratic Arithmetic Programs)$

* 生成挑戰
Let $(a, b, c)$ pass through $T(x)=(x-1)(x-2)(x-3)(x-4)$
這邊過點 $(1, 0), (2, 0), (3, 0), (4, 0)$ 是挑戰函式，此函式可以是隨機生成的

* 轉換 $R1CS$ 的矩陣
Use Lagrange polynomials Form:
A  ，我們將 A 的第一行與挑戰函式點帶入拉格朗日插值法公式中，
E.g. Transform $A_{i1}$ $\rightarrow (1, 0), (2, 0), (3, 0), (4, 5) \rightarrow 0.833x^3 - 5x^2 + 9.166x - 5 \rightarrow [-5.0, 9.166, -5.0, 0.833]$

* 證明的格式
最終可得三個新的 A, B, C 矩陣
  

**證明者必須求出一組 S 使得條件成立，S 為對應的係數，在此情況，唯有帶入正確的 $x$ (生物數據與 ID 雜湊...) 才能找出正確的 S 使得條件成立**


$S . A(x) * S . B(x) - S . C(x) = H(x)T(x)$
為了簡化這邊以 $P(x)=H(x)T(x)$ 表示

### 證明與驗證

零知識部分以 $\color{magenta}{此顏色}$ 表示，這邊採用精簡過的 Pinocchio Protocol (https://ieeexplore.ieee.org/document/6547113)

* **Setup**
- sample random values $s, \alpha$
- calucalate encryptions $g^{\alpha}$ and $\{g^{s^i}\}_{i \in [d]}, \{g^{\alpha s^i}\}_{i \in [d]}$
- generate $p_k: (\{g^{s^i}\}_{i \in [d]}, \{g^{\alpha s^i}\}_{i \in [d]})$ , $v_k: (g^{\alpha}, g^{t(s)})$

* **Compute (Proving)**
* assign coeffients $\{c_i\}_{i \in \{0,...,d\}}, p(x) = c_dx^d + ... + c_1x^1 + c_0x^0$
and find $h(x)=\frac {p(x)}{t(x)}$
* using $\{g^{s^i}\}_{i \in [d]}, \{g^{\alpha s^i}\}_{i \in [d]}$ to evaluate encrypted polynomials
$g^{p(s)}, g^{h(s)}$ and $g^{\alpha p(s)}$
* sample random $\color{magenta}{\delta}$ and make the randomized proof
$\color{magenta}{\pi = (g^{\delta p(s)}, g^{\delta h(s)}, g^{\delta \alpha p(s)})}$

* **Verify**
* parse proof $\pi$ as $(g^p, g^h, g^{p'})$
* check polynomial restriction $e(g^{p'}, g) = e(g^p, g^{\alpha})$
* check polynomial cofactors $e(g^p, g) = e(g^{t(s)}, g^h)$

### 總結
1. TP 中介協助生成算數電路函式 $F'$, 證明密鑰$p_k$ 與驗證密鑰 $v_k$，$F'$ 是由影像辨識與使用者和秘密儲存單位(e.g. 政府機構) 作為係數。
2. 證明者透過使用中介的軟體，在本地端設備取得正確的生物數據(e.g. 臉部辨識數據)並輸入正確的隱私資訊(e.g. 身分證號)，計算出 $F'$ 的係數知識，並透過 $p_k$ 與係數知識生成證明 $\pi$
3. 驗證者透過 $v_k$ 驗證 $\pi$，檢查是否為合法證明

在數據交換過程中，驗證者與證明者有共享秘密資料(身分證照片的生物數據)，中介提供 SDK 讓驗證者與證明者在其本地端生成 **問題 $F'$** 與 **證明 $\pi$**，並協助轉交。並選擇隨機數生成證明與驗證的密鑰 $p_k, v_k$，讓證明者與驗證者在 **不傳遞隱私數據** 的情況下驗證身份或資產。而對於中介(銀行端或智能合約而言，由於不知道正確輸入，也無法得知確切係數。並且在證明生成過程中，由於加入了隨機數，也難以取得證明數據)

#### 採用這個應用程式帶來的業務改善
* **對使用者而言可以更好的地方**
- [x] 個人身份的資料洩漏 (零知識數據交換)
- [x] 無法得到準確貸款金額，除非完成聯徵 (資產證明可快速由驗證者確認)
- [x] 流程等待時間很久 (可自動化的資產驗證過程)

* **對銀行端而言可以更好的地方**
- [x] 電話行銷成本 (網路應用的無成本準確試算)
- [x] 審核信用與身份成本 (可自動化的資產驗證過程)
- [x] 時間成本 (自動化與程式化的審核流程)
---

### 細節備考 (非報告內容)
驗證過程大綱

| 1. 設置 | 2. 證明 | 3. 驗證 |
| ----------- | ------------------------- | ------------------------- |
電路生成 $\rightarrow$ 電路轉換為約束多項式 $\rightarrow$ 約束多項式生成 $p_k$ 與 $v_k$ | 計算電路方程式取得係數知識 $\rightarrow$ 選擇隨機數 $\delta$ $\rightarrow$ 透過 $p_k$, $\delta$ 產生係數知識的證明 $\pi_y$ | 用 $v_k$ 確認證明依照約束 $\rightarrow$ 用 $v_k$ 驗證使用了正確的輸入 $\rightarrow$ 用 $v_k$ 做有效計算檢查 |

零知識部分以 $\color{magenta}{顏色}$ 表示

| | 1. 設置 | 2. 證明 | 3. 驗證 |
| --- | ------- | ------- | ------- |
| 步驟內容 | 1. 選擇生成元 $g$ 和加密配對 $e$ <br><br> 2. 將變量總數為 $n$ 其中輸入/輸出變量數位 $m$ <br> 的函數 $f(u) = y$，轉換為階數為 $d$ 大小為 <br> $n+1$ 的多項式形式 $\{l_i(x), r_i(x), o_i(x)\}_{i \in \{0, ..., n\}}, t(x)$ <br><br> 3. 選擇隨機數 $s, \rho_l, \rho_r, \alpha_l, \alpha_r, \alpha_o, \beta, \gamma$<br><br> 4. 設置 $\rho_o = \rho_l \cdot \rho_r$ 和操作數生成元 $g_l=g^{\rho_l}, g_r = g^{\rho_r}, g_o = g^{\rho_o}$ <br><br> 5. 設置 proving key $p_k$: <br>$(\{g^{s^k}\}_{k \in [d]}, \\ \{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)}\}_{i \in {0,…,n}}\}, \\ \{g_l^{\alpha_ll_i(s)},g_r^{\alpha_rr_i(s)}, g_o^{\alpha_oo_i(s)}, g_l^{\beta l_i(s)},g_r^{\beta r_i(s)},g_o^{\beta o_i(s)}\}_{i \in \{m+1,…,n\}}, \\ \color{magenta}{{g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)},g_r^{\beta t(s)}, g_o^{\beta t(s)}}})$ <br><br> 6. 設置 verification key $v_k$: <br> $(g^1, {g_o}^{t(s)}, \{ {g_l}^{l_i(s)}, {g_r}^{r_i(s)}, {g_o}^{o_i(s)} \}_{i \in \{0, ..., m\}}, g^{\alpha_l}, g^{\alpha_r}, g^{\alpha_o}, g^{\gamma}, g^{\beta})$ | 1. 以輸入 $u$，計算 $f(u)$ 獲取所有的電路係數 <br> $\{v_i\}_{i \in \{m+1,……，n\}}$ <br><br> 2. 把電路係數賦值給 $L(x) = l_0(x) + \sum_{i=1}^n {v_i l_i(x)}$，similarly $R(x), O(x)$ <br><br> 3. 選擇隨機數 $\delta_l, \delta_r, \delta_o$ <br><br> 4. 計算 $h(x) = \frac{L(x)R(x)-O(x)}{t(x)} \color{magenta}{+ \delta_r L(x) + \delta_lR(x) + \delta_l \delta_r t(x) - \delta_o}$ <br><br> 5. 將 prover 的變量值賦值給加密的可變多項式 $\color{magenta}{並進行零知識的\delta-轉換}\quad g_l^{L_p(s)}= \color{magenta}{(g_l^{t(s)})^{\delta_l}} \cdot \prod_{i=m+1}^n{(g_l^{l_i(s)})^{v_i}}$<br>, similarly $g_r^{R_p(s)}$ 和 $g_o^{O_p(s)}$ <br><br> 6. 為其 $\alpha -$ 變換賦值 $g_l^{L_p'(s)}= \color{magenta}{(g_l^{\alpha _l t(s)})^{\delta_l}} \cdot \prod_{i=m+1}^n{(g_l^{\alpha _l l_i(s)})^{v_i}}$, similarly $g_r^{R_p'(s)}, g_o^{O_p'(s)}$ <br><br> 7. 為變量值一致性多項式賦值 <br> $g^{Z(s) = \color{magenta}{(g_l^{\beta t(s)})^{\delta_l}(g_r^{\beta t(s)})^{\delta_r}(g_o^{\beta t(s)})^{\delta_o}}} \cdot \prod_{i=m+1}^n{(g_l^{\beta l_i(s)}g_r^{\beta r_i(s)}g_o^{\beta o_i(s)})^{v_i}}$ <br><br> 8.計算證明 $(g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g^{h(s)}, g_l^{L_p'(s)}, g_r^{R_p'(s)}, g_o^{O_p'(s)}, g^Z)$ | 1. 解析提供的證明為 $(g_l^{L_p},g_r^{R_p},g_o^{O_p},g^h,g_l^{L_p'},g_r^{R_p'},g_o^{O_p'},g^Z)$ <br><br> 2. 將輸入/輸出值賦值給 verifier 的加密多項式並加 1， $g_l^{L_v(s)} = g_l^{l_o(s)} \cdot \prod_{i=1}^m{(g_l^{l_i(s)})^{v_i}}$, similarly $g_r^{R_v(s)}, g_o^{O_v(s)}$ <br><br> 3. 可變多項式約束檢查，$e(g_l^{L_p}, g^{\alpha_l}) = e(g_l^{L'_p}, g)$, similarly $g_r^{R_p}, g_o^{O_p}$ <br><br> 4. 變量值一致性檢查，$e(g_l^{L_p},g_r^{R_p},g_o^{O_p},g^{\beta \gamma}) = e(g^Z, g^{\gamma})$ <br><br> 5. 有效的計算檢查，$e(g_l^{L_p}g_l^{L_v(s)},g_r^{R_p}g_r^{R_v(s)}) = e(g_o^{t(s)},g^h) \cdot e(g_o^{O_p}g_o^{O_v(s)},g)$ |

規則轉換為函數
Algebraic Circuit $\rightarrow$ R1CS

$F(x) = x^3+x+5$, input $u = 3$, output $y = 35$
| Algebraic Circuit | R1CS |
| -------- | -------- |
|  |  |

Provided variable: [$one$, $x$, $\overline{y}$, ${\lambda}_1$, ${\lambda}_2$, ${\lambda}_3$]

| First Gate | Second Gate | Third Gate | Fourth Gate |
| -------- | -------- | -------- | -------- |
|  |  |  |  |

First Gate:
${\lambda}_1 = x * x \rightarrow x * x - {\lambda}_1 = 0$
$a_1 = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0
\end{vmatrix}$
$b_1 = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0
\end{vmatrix}$
$c_1 = \begin{vmatrix}
0 & 0 & 0 & 1 & 0 & 0
\end{vmatrix}$

Second Gate:
${\lambda}_2 = {\lambda}_1 * x \rightarrow {\lambda}_1 * x - {\lambda}_2 = 0$
$a_2 = \begin{vmatrix}
0 & 0 & 0 & 1 & 0 & 0
\end{vmatrix}$
$b_2 = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0
\end{vmatrix}$
$c_2 = \begin{vmatrix}
0 & 0 & 0 & 0 & 1 & 0
\end{vmatrix}$

Third Gate:
The addition gate needs to be converted
${\lambda}_3 = {\lambda}_2 + x \rightarrow (x+{\lambda}_2)*1-{\lambda}_3 = 0$
$a_3 = \begin{vmatrix}
0 & 1 & 0 & 0 & 1 & 0
\end{vmatrix}$
$b_3 = \begin{vmatrix}
1 & 0 & 0 & 0 & 0 & 0
\end{vmatrix}$
$c_3 = \begin{vmatrix}
0 & 0 & 0 & 0 & 0 & 1
\end{vmatrix}$

Fourth Gate:
$\overline{y} = {\lambda}_3 + 5 \rightarrow ({\lambda}_3 + 5)*1 - \overline{y} = 0$
$a_4 = \begin{vmatrix}
5 & 0 & 0 & 0 & 0 & 1
\end{vmatrix}$
$b_4 = \begin{vmatrix}
1 & 0 & 0 & 0 & 0 & 0
\end{vmatrix}$
$c_4 = \begin{vmatrix}
0 & 0 & 1 & 0 & 0 & 0
\end{vmatrix}$

Final
$A = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 \\
5 & 0 & 0 & 0 & 0 & 1 \\
\end{vmatrix}$,

$B = \begin{vmatrix}
0 & 1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 \\
\end{vmatrix}$,

$C = \begin{vmatrix}
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 0 \\
\end{vmatrix}$

R1CS $\rightarrow$ QAP(Quadratic Arithmetic Programs)

Let $(a, b, c)$ pass through $T(x)=(x-1)(x-2)(x-3)(x-4)$

Use Lagrange polynomials Form:

E.g. Transform $A_{i1}$ $\rightarrow (1, 0), (2, 0), (2, 0), (4, 5) \rightarrow 0.833x^3 - 5x^2 + 9.166x - 5 \rightarrow [-5.0, 9.166, -5.0, 0.833]$

  

---

TP Setup:
1. 選擇生成元 $g$ 和加密配對 $e$

2. 將變量總數為 $n$ 其中輸入/輸出變量數位 $m$ 的函數 $f(u) = y$，轉換為階數為 $d$ 大小為$n+1$ 的多項式形式 $QAP \rightarrow [ \{l_i(x), r_i(x), o_i(x)\}_{i \in \{0, ..., n\}}, t(x) ]$

3. 選擇隨機數 $s, \rho_l, \rho_r, \alpha_l, \alpha_r, \alpha_o, \beta, \gamma$

4. 設置 $\rho_o = \rho_l \cdot \rho_r$ 和操作數生成元 $g_l=g^{\rho_l}, g_r = g^{\rho_r}, g_o = g^{\rho_o}$

5. 設置 proving key $p_k$：$(\{g^{s^k}\}_{k \in [d]}, \\
\{g_l^{l_i(s)},g_r^{r_i(s)},g_o^{o_i(s)}\}_{i \in {0,…,n}}\}, \\
\{g_l^{\alpha_ll_i(s)},g_r^{\alpha_rr_i(s)}, g_o^{\alpha_oo_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)},g_o^{\beta o_i(s)}\}_{i \in \{m+1,…,n\}}, \\
\color{magenta}{{g_l^{t(s)}, g_r^{t(s)}, g_o^{t(s)}, g_l^{\alpha_l t(s)}, g_r^{\alpha_r t(s)}, g_o^{\alpha_o t(s)}, g_l^{\beta t(s)},g_r^{\beta t(s)}, g_o^{\beta t(s)}}})$

6. 設置 verification key $v_k$: $(g^1, {g_o}^{t(s)}, \{ {g_l}^{l_i(s)}, {g_r}^{r_i(s)}, {g_o}^{o_i(s)} \}_{i \in \{0, ..., m\}}, g^{\alpha_l}, g^{\alpha_r}, g^{\alpha_o}, g^{\gamma}, g^{\beta})$

Alice Proving:

1. 代入輸入值 $u$，執行 $f(u)$ 計算獲取所有的電路係數 $\{v_i\}_{i \in \{m+1,……，n\}}$

2. 把所有未加密的係數多項式賦值給 $L(x) = l_0(x) + \sum_{i=1}^n {v_i l_i(x)}$
, similarly $R(x), O(x)$

3. 選擇隨機數 $\delta_l, \delta_r, \delta_o$

4. 計算 $h(x) = \frac{L(x)R(x)-O(x)}{t(x)} \color{magenta}{+ \delta_r L(x) + \delta_lR(x) + \delta_l \delta_r t(x) - \delta_o}$

5. 將 prover 的變量值賦值給加密的可變多項式 $\color{magenta}{並進行零知識的\delta-轉換}\quad g_l^{L_p(s)}= \color{magenta}{(g_l^{t(s)})^{\delta_l}} \cdot \prod_{i=m+1}^n{(g_l^{l_i(s)})^{v_i}}$,
similarly $g_r^{R_p(s)}$ 和 $g_o^{O_p(s)}$

6. 為其 $\alpha -$ 變換賦值 $g_l^{L_p'(s)}= \color{magenta}{(g_l^{\alpha _l t(s)})^{\delta_l}} \cdot \prod_{i=m+1}^n{(g_l^{\alpha _l l_i(s)})^{v_i}}$
, similarly $g_r^{R_p'(s)}$ 和 $g_o^{O_p'(s)}$

7. 為變量值一致性多項式賦值
$g^{Z(s) = \color{magenta}{(g_l^{\beta t(s)})^{\delta_l}(g_r^{\beta t(s)})^{\delta_r}(g_o^{\beta t(s)})^{\delta_o}}} \cdot \prod_{i=m+1}^n{(g_l^{\beta l_i(s)}g_r^{\beta r_i(s)}g_o^{\beta o_i(s)})^{v_i}}$

8. 計算證明 $(g_l^{L_p(s)}, g_r^{R_p(s)}, g_o^{O_p(s)}, g^{h(s)}, g_l^{L_p'(s)}, g_r^{R_p'(s)}, g_o^{O_p'(s)}, g^Z)$

Bob Verification:
1. 解析提供的證明為 $(g_l^{L_p},g_r^{R_p},g_o^{O_p},g^h,g_l^{L_p'},g_r^{R_p'},g_o^{O_p'},g^Z)$

2. 將輸入/輸出值賦值給 verifier 的加密多項式並加 1，
$g_l^{L_v(s)} = g_l^{l_o(s)} \cdot \prod_{i=1}^m{(g_l^{l_i(s)})^{v_i}}$, similarly $g_r^{R_v(s)}, g_o^{O_v(s)}$

3. 可變多項式約束檢查，$e(g_l^{L_p}, g^{\alpha_l}) = e(g_l^{L'_p}, g)$, similarly $g_r^{R_p}, g_o^{O_p}$

4. 變量值一致性檢查，$e(g_l^{L_p},g_r^{R_p},g_o^{O_p},g^{\beta \gamma}) = e(g^Z, g^{\gamma})$

5. 有效的計算檢查，$e(g_l^{L_p}g_l^{L_v(s)},g_r^{R_p}g_r^{R_v(s)}) = e(g_o^{t(s)},g^h) \cdot e(g_o^{O_p}g_o^{O_v(s)},g)$

| | 1. 設置 | 2. 證明 | 3. 驗證 |
| -------- | ------------------------------------ | ------------------------------------ | ------- |
| 步驟內容 |  |  |  |