GregShen

Blockchain Developer 走偏的統計仔 趁著服役期間寫寫文章

輕鬆了解zk-SNARK — 第二篇

運算過程的第一部分 — QAP轉換
Image from Moralis

前言

上一篇 zk-SNARK原理詳解 — 1 中,我大概講了一些零知識證明的概念以及ZCash如何運作的。為什麼使用 ZCash做講解?除了它是一個用零知識證明來處理隱私交易的幣之外,它的文檔對我學習這個知識提供非常多幫助。

另外,我也參考了V神、以及一些大神的文章、論文,整理成一篇我認為大家容易理解的文章(相比於其他文章),希望大家看完後可以跟阿嬤解釋什麼是零知識證明,記得順便帶點靈芝給阿嬤~


抱歉很尬,我們直接開始。

這篇論文中第 25頁,作者整理出零知識證明的過程中會有哪些運算。

當然,這篇文章不會拿上圖做講解,嚇嚇人而已!接下來正式開始進入講解環節~

這邊很重要

回顧一下 zk-SNARK 的意思,全名為 Zero Knowledge Succinct Non-Interactive Arguments of Knowledge,也就是簡潔的、無交互的零知識證明。

其主體是 Argument of Knowledge(知識證明),也就是說,最重要的是驗證者所生成的證明,此證明與挑戰者所提出的問題相對應。

其實這個觀念與其他不同的證明法是一樣的,但困難之處在於

  1. zk(零知識),具體一點就是 — 在交易中,你必須證明你擁有某種未花費的資產,但是不想暴露資產的來源、去向。
  2. Succint(簡潔的),驗證過程中生成的資料大小以及驗證時間都要小於直接暴力運算,因此我們不能讓驗證者每輪都做 hash運算(否則就跟計算量成正比了)。
  3. Non-Interactive(無交互),沒有交互是要驗證啥?

關於這些操作是如何完成的,且聽我娓娓道來~

哦對,為了讓大家知道我們進行到哪個步驟了,我用羊皮紙來追蹤我們的進度,夠誠意了吧!

本文中,我們會一直看到這張圖,看到你做夢都記得…

我們先來取得一個共識…

程式在處理的就是將輸入值運算,zk-SNARK作為一種數學證明,若要能用程式處理,就要有可量化的輸入值,而要進行運算之前,必須先為目標問題建立出一個模型(此模型包含上圖中所有的進行動作),有了模型以及輸入值,才能得到想要的結果。

再說得白話一點,我們在選取問題的特定輸入值後,代入我們所建立的 function後,可以得到一個解,在 zk-SNARK中這個解叫做證明,用來證明驗證者的確知道這個解。

有了這個共識後,再來進行下一步。

進行證明前,先轉換為成適當的格式 — QAP

如前一段所述,我們要建立一個模型以進行零知識證明,既然是模型,就要能涵蓋到大部分的傳入值,不能出現有些可以、有些不行的情況,也因為我們明白:

  1. 並不是任意運算問題都可以進行 zk-SNARK
  2. NP問題的所有實例都可以在 zk中被證明

第一點其實蠻直觀的,關於第二點,在這則論文中解釋了所有NP問題都有零知識證明。

小百科:一般問題可分成兩類: P問題NP問題 。P問題指的是在多項式時間內可的問題。 NP問題(Non-Deterministic Polynomial Problem,非確定性多項式問題),指不能在多項式內可解,但是可以在多項式時間內驗證 的問題。

基於上述兩點,我們應該確保傳入模型執行 zk-SNARK的傳入值是 NP問題,而且是可以在模型中被運算的形式。

在 zk-SNARK中,這個轉換的最終結果是QAP(Quadratic Arithmetic Program),如何轉換以及轉換的邏輯會在稍後說明,現在只需要先了解下面那張圖就好了

總而言之,我們需要輸入值呈現一個正確的格式來執行後續運算,這個格式在zk-SNARK中就是QAP。我們也因此把zk-SNARK拆成兩個部分。

  1. 將初始輸入值轉換為QAP
  2. 進行後續運算

於是現在流程圖長這樣了~

本文主要會講解第一部分 — 轉換為 QAP,第二部分留到之後的文章。

一直說QAP QAP,但它是什麼?又是怎麼轉換的?

QAP轉換過程

我們以V神文章中所提供的範例舉例,這個過程中我們要去證明我們知道 x³+x+5=35 的解,但這個例子可以讓我們理解zk-SNARK的技術原理,同時又不會產生很大的 QAP。

x³+x+5=35如下:

def qeval(x):
    y = x**3
    return x + y + 5
轉換為QAP的主要目的
稍後我們會進行三個步驟將一個函數轉換成 QAP,QAP是以多項式的形式表示,然而為什麼要費盡心思弄出多項式,其實是為了滿足後續以「抽樣」來實現「簡潔」,但這就是下一篇的內容啦,現在做這個聲明只是先跟讀者說明我們要轉換的原因,現在讓我們繼續跑完流程吧!

過程主要分為三個步驟

1.引入變數

將 x³+x+5轉換成幾個簡單算式,例如 x=y, x=y(op)z這種形式,op(operation) 代表加、減、乘、除,這些簡單算式可以視為數位電路中的邏輯閘,也因此被稱為代數電路(Algebraic Circuit)

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

上式中,sym_1, y, sym_2就是我們所引入的變數,將 x=3, sym_1=9, y=27, sym_2=30, ~out=35代入其中,等式成立。

這種轉換的過程有另一個名詞叫做 flattening(拍平),拍平後的每一個式子其實都是一個邏輯閘。

2.定義向量

定義向量s=[~one, x, ~out, sym_1, y, sym_2],其中~one為偽變量,實際上是常數 1,這個偽變量的作用稍後就會看到了。

定義向量s

將每個我們轉換過的簡單算式再轉換為(sa)∗(sb)−(sc)=0,其中 ⋅ 為向量內積運算子,a,b,c為係數向量。

等式左右兩側同為35

要了解找 s與 a, b, c的原因,就要先了解什麼是 R1CS(Rank-1 Constraint System,一階約束系統) 。

R1CS 是由三向量組 (a,b,c) 組成,R1CS 有個解向量 s,s 必須滿足(sa)∗(sb)−(sc)=0。這裡的解向量 s就是 witness。上例中:

s = [1, 3, 35, 9, 27, 30]

a = [5, 0, 0, 0, 0, 1]

b = [1, 0, 0, 0, 0, 0]

c = [0, 0, 1, 0, 0, 0]

複習一下,上面的動作是在將最後一個邏輯閘(“拍平”後的最後一個式子) 轉換成一個約束(即一個三向量組)。

接下來我們再將剩下三個邏輯閘做相同操作找出各自 a,b,c向量

sym_1 = x * x      
y = sym_1 * x      
sym_2 = y + x      
~out = sym_2 + 5   我們已經完成這行
找出各式子 a,b,c向量

將係數向量依順序排列(各行所得到的 a, b, c集合起來),得到A, B, C三矩陣。

集合成 A, B, C

至此第二個步驟完成!

第三個步驟,我們要做的是將 R1CS轉換成 QAP形式

補充:

R1CS與 QAP所要實現的邏輯完全相同,兩者的區別在於 QAP使用多項式來代替內積運算。

在介紹這種轉換之前,我們需要複習拉格朗日差值公式,這個公式的作用是建立一個穿過指定點的多項式,相信各位在國高中也都有學過

圖取自無名PDF

例如通過點 (1,3), (2,2), (3,4) 的多項式為:


前面提到,第三個步驟的目的是把 R1CS轉換為 QAP,使用的就是拉格朗日差值公式。

這個步驟,比較像是在壓縮矩陣,因此我們的第三個步驟就稱作壓縮矩陣。

3. 壓縮矩陣

現在我們要來將 A, B, C三個矩陣分各自轉換為六組多項式。

概念大概是這樣:

矩陣C → C(n)=[C1(n), C2(n), C3(n), C4(n), C5(n), C6(n)]

每組多項式包括三個三階多項式,我們在每個 x點處來評估不同的約束,在這裡,我們共有四個約束,因此我們分別用多項式在 x = 1, 2, 3, 4 評估這四組向量組。

我們先求出四個約束所對應的每個 a 向量的第一個值的多項式,也就是說,使用拉格朗日插值定理求過點 (1,0), (2,0), (3,0), (4,0) 的多項式,類似的我們可以求出其餘的四個約束所對應的每個向量的第 i 個值的多項式。結果如下:

在得到這些多項式後,計算問題就轉換成求 s (s是解向量,一開始有提到),使 (sa)∗(sb)−(sc)=0 在 n = 1,2,3,4,5,6 成立,也等價於:

[s⋅A(n)]∗[s⋅B(n)]−[s⋅C(n)]= H(n)*Z(n),其中Z(n)=(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)

至此,我們終於得到一個涵蓋全部的多項式,也就完成第一部分了!

沒想到光第一部分畫圖就畫這麼久,下一篇我們開始講解後續運算。

歡迎留言或是 email: [email protected] 一起討論
或是追蹤本帳號獲得新文章通知!

參考資料

Zk-SNARKs: Under the Hood

This is the third part of a series of articles explaining how the technology behind zk-SNARKs works; the previous…medium.com

What are zk-SNARKs? | Zcash

Network Upgrade 5 (NU5) in May 2022, Zcash introduced the Orchard shielded payment protocol, which utilizes the Halo 2…z.cash

How Transactions Between Shielded Addresses Work - Electric Coin Company

In 'Anatomy of A Zcash Transaction' we gave a general overview of Zcash Transactions. The purpose of this post is to…electriccoin.co

Introduction to zkSNARKs with Examples

A practical overview of zk-SNARKsmedia.consensys.net

Quadratic Arithmetic Programs: from Zero to Hero

There has been a lot of interest lately in the technology behind zk-SNARKs, and people are increasingly trying to…medium.com

Explaining Quadratic Arithmetic Programs | Xord

This article is greatly inspired by Vitalik explanation on Quadratic arithmetic programs( QAPs). In this article we are…xord.com

零知识证明引论(二)

https://blog.csdn.net/chixiao5404/article/details/100729120

Like my work??
Don't forget to support or like, so I know you are with me..

CC BY-NC-ND 2.0

輕鬆了解 zk-SNARK — 第一篇

Want to read more ?

Login with one click and join the most diverse creator community.