zk-SNARKs 簡介

本文開源倉庫地址

本文翻譯自 Consensys

翻譯者：@BoxMrChen

在這篇文章中，我們的目標是從實用的角度對 zk-SNARKs 進行概述。我們將把實際的數學問題視為一個黑箱，並試圖圍繞我們如何使用它們來發展一些直覺。我們還將展示一項關於在以太坊中集成 zk-SNARKs 的最近工作的簡單應用。

零知識證明#

零知識證明的目標是讓驗證者能夠确信證明者掌握了一個滿足某種關係的秘密參數，也就是所謂的見證人，而無需向驗證者或任何其他人揭示這個見證人。

我們可以更具體地將其想象為一個程序，標記為 C ，接收兩個輸入： C(x, w)。輸入 x 是公開輸入，而 w 是秘密見證輸入。程序的輸出是布爾值，即 true 或 false 。然後，目標是給定特定的公開輸入 x ，證明證明者知道一個秘密輸入 w ，使得 C(x,w) == true 。

我們將專門討論非交互式零知識證明。這意味著證明本身是一塊可以在無需證明者任何交互的情況下進行驗證的數據。

示例程序#

假設 Bob 得到了某個值的哈希 H ，他希望有證據證明 Alice 知道哈希為 H 的值 s 。通常，Alice 會通過給 Bob s 來證明這一點，然後 Bob 會計算哈希並檢查它是否等於 H 。

然而，假設 Alice 不想向 Bob 透露 s 的值，而只是想證明她知道這個值。她可以使用 zk-SNARK 來實現這一點。

我們可以使用以下程序來描述 Alice 的情況，這裡以 Javascript 函數的形式編寫：

function C(x, w) {  return ( sha256(w) == x );}

這個程序不涉及任何 ZK 內容，他只是用於表示我們想要達到的效果是什麼樣。我們可以將其視為一個黑盒，我們将在下一節中討論如何使用 zk-SNARKs 來構建這樣的程序。

換句話說：該程序接收一個公共哈希 x 和一個秘密值 w ，如果 w 的 SHA-256 哈希等於 x ，則返回 true 。

將 Alice 的問題通過函數 C(x,w)進行翻譯，我們可以看到 Alice 需要創建一個證明，證明她擁有 s ，使得 C(H, s) == true ，而無需揭示 s 。這就是 zk-SNARKs 解決的一般問題。

zk-SNARK 的定義#

一個 zk-SNARK 由三個算法 G, P, V 組成，定義如下：

密鑰生成器 G 由一個秘密參數 lambda 和一個程序 C 組成，並生成兩個公開可用的密鑰，一個 proving key pk（證明密鑰），和一個 verification key vk（驗證密鑰）。這些密鑰是公開參數，只需要使用程序 C 生成一次。

證明者 P 將證明密鑰 pk 、公共輸入 x 和見證 w 作為輸入。該算法生成一個證明 prf = P(pk, x, w) ，證明者知道一個見證 w ，並且該見證滿足程序的要求。

驗證器 V 計算 V(vk, x, prf) ，如果證明是正確的，它將返回 true ，否則返回 false 。因此，如果證明者知道一個滿足 C (x,w) == true 的見證 w ，這個函數就會返回真。

請注意在生成器中使用的秘密參數 lambda 。這個參數有時使得在現實世界的應用中使用 zk-SNARKs 變得棘手。原因在於，任何知道這個參數的人都可以生成假的證明。具體來說，給定任何程序 C 和公開輸入 x ，知道 lambda 的人可以生成一個證明 fake_prf ，使得 V(vk, x, fake_prf) 評估為 true ，而無需知道秘密 w 。

因此，實際運行生成器需要一個非常安全的過程，以確保沒有人了解並保存參數。這就是 Zcash 團隊進行極其複雜的儀式以生成證明密鑰和驗證密鑰的原因，同時確保 “有毒廢料” lambda 在過程中被銷毀。

針對示例程序的 zk-SNARK#

在實際操作中， Alice 和 Bob 如何使用 zk-SNARK，以便 Alice 證明她知道上述示例中的秘密值？首先，如上所述，我們將使用由以下函數定義的程序：

function C(x, w) {
  return sha256(w) == x;
}

首先，Bob 需要運行生成器 G，以創建證明密鑰 pk 和驗證密鑰 vk。首先，隨機生成 lambda，並將其作為輸入：

(pk, vk) = G(C, lambda)

請小心處理參數 lambda，因為如果 Alice 知道 lambda 的值，她將能夠創建假的證明。Bob 將與 Alice 分享 pk 和 vk。

Alice 現在將扮演證明者的角色。她需要證明她知道哈希值為已知哈希 H 的值 s。她運行證明算法 P，使用輸入 pk、H 和 s 來生成證明 prf：

prf = P(pk, H, s)

接下來，Alice 將證明 prf 呈現給 Bob ，Bob 運行驗證函數 V(vk, H, prf)。在這種情況下，由於 Alice 正確地知道了秘密 s，所以會返回真值。Bob 可以确信 Alice 知道這個秘密，但 Alice 並不需要向 Bob 透露這個秘密。

可重用的證明和驗證密鑰#

在我們上述的例子中，如果 Bob 想向 Alice 證明他知道一個秘密，那麼他就不能使用 zk-SNARK，因為 Alice 無法知道 Bob 是否保存了 lambda 參數。Bob 完全有可能偽造證據。

如果一個程序對許多人有用（比如 Zcash 的例子），一個獨立於 Alice 和 Bob 的可信賴的獨立團隊可以運行生成器，創建證明密鑰 pk 和驗證密鑰 vk，而且這樣做沒有人會了解到 lambda。

任何相信該團隊沒有作弊的人，都可以在未來的互動中使用這些密鑰。

以太坊中的 zk-SNARKs#

開發者已經開始將 zk-SNARKs 集成到以太坊中。這看起來是什麼樣子呢？具體來說，你可以將驗證算法的構建模塊以預編譯合約的形式添加到以太坊中。具體操作如下：在鏈下運行生成器，生成證明密鑰和驗證密鑰。然後，任何證明者都可以使用證明密鑰創建證明，這也是在鏈下完成的。然後，你可以在智能合約內部運行通用驗證算法，使用證明、驗證密鑰和公開輸入作為輸入參數。然後，你可以使用驗證算法的結果來觸發其他鏈上活動。

示例：保密交易#

以下是一個簡單的例子，說明了 zk-SNARKs 如何幫助提高以太坊的隱私性。假設我們有一個簡單的代幣合約。通常，一個代幣合約的核心是將地址映射到餘額：

mapping (address => uint256) balances;

我們將保留相同的基本核心，只是將餘額替換為餘額的哈希值：

mapping (address => bytes32) balanceHashes;

我們不會隱藏交易的發送者或接收者。但我們會隱藏餘額和發送的金額。這種屬性有時被稱為保密交易。

我們將使用兩個 zk-SNARKs 來將代幣從一個賬戶發送到另一個賬戶。發送者和接收者各創建一個證明。

通常在一個代幣合約中，為了使大小值的交易有效，我們需要驗證以下內容：

balances[fromAddress] >= value

我們的 zk-SNARKs 需要證明這一點是成立的，以及更新後的哈希值與更新後的餘額相匹配。

主要的思想是，發送者將使用他們的 初始餘額 和值作為私有數據。使用 初始餘額、結束餘額 和 值的哈希 作為公開數據。同樣，接收者將使用 初始餘額 和值作為私有數據。使用 初始餘額 、 結束餘額 和 值的哈希 作為公開數據。

以下是發送者的 zk-SNARK 程序，其中如前所述，x 代表公開數據，w 代表私有數據。

/**
 * @param x 公開數據
 * @param w 私有數據
 */
function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value && // 確保發送者有足夠的餘額
    sha256(w.value) == x.hashValue && // 確保發送的值與公開的哈希值匹配
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore && // 確保發送者的初始餘額與公開的哈希值匹配
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter // 確保發送者的結束餘額與公開的哈希值匹配
  );
}

接收者的 zk-SNARK 程序如下：

/**
 * @param x 公開數據
 * @param w 私有數據
 */
function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  );
}

這些程序會檢查發送餘額是否大於正在發送的值，並檢查所有哈希是否匹配。一組受信任的人员將為我們的 zk-SNARKs 生成證明和驗證密鑰。我們稱它們為 confTxSenderPk、confTxSenderVk、confTxReceiverPk 和 confTxReceiverVk。 confTxSenderPk 和 confTxReceiverPk 將被用於生成證明，而 confTxSenderVk 和 confTxReceiverVk 將被用於驗證證明。

在代幣合約中使用 zk-SNARKs 可能會是這樣的：

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

因此，區塊鏈上唯一更新的只是餘額的哈希值，而不是餘額本身。然而，我們可以知道所有的餘額都被正確地更新了，因為我們可以自己檢查證明已經被驗證過了。

通過上面的例子，我們也可以看到，在區塊鏈上我們只進行了餘額的 Hash 存儲，而沒有暴露真實的餘額，這就對數據進行了保密，我們除了知道兩者之間發生了交易，但是我們不知道具體交易金額，這就保證了交易的隱私性。

詳細信息#

上述的保密交易方案主要是為了給出一個實際的例子，說明我們如何在以太坊上使用 zk-SNARKs。要創建一個健全的保密交易方案，我們需要解決一些問題：

用戶需要在客戶端跟蹤他們的餘額，如果你失去餘額數據，那麼你就失去了這個賬戶的控制權。餘額或許可以用來自簽名密鑰的密鑰加密並存儲在鏈上。
餘額需要使用 32 字節的數據並熵編碼，以防止反向解析哈希以計算餘額。
需要處理向未使用地址發送的邊緣情況。
發件人需要與收件人進行交互才能發送。我們可能會有一個系統，發件人可以使用他們的證明來啟動交易。然後，收件人可以在區塊鏈上看到他們有一個 “待處理的入帳交易”，並可以完成它。