zk-SNARK：關於私鑰、環簽名、ZKKSP

語言: CN / TW / HK

時間 2022-07-25 12:36:08 去中心化金融社區

私鑰

理論上，對於任何數學問題都可以構造一個零知識證明(ZKP)，而無需公開其解決方案。在實踐中，為一個問題開發ZKP通常需要發明一種全新的密碼算法。它沒有標準的“配方”，需要的是廣泛且深入的密碼學知識。例如，ZK的謎題涉及∑-protocol和ZK key-statement proof Pedersen承諾和Fiat-Shamir啟發式。

zk-SNARK對任意問題的ZKP生成進行標準化。只需用 ZK 格式表達要證明的原始問題，例如利用特定語言Circom或Zokrates。其餘的都由通用的 zk-SNARK 框架處理，它隱藏了底層密碼學的所有複雜性。

在zk-SNARK之前，為新問題構建ZKP就類似於在需要設計新的ZKP應用程序時構建新的ASIC。zk-SNARK允許通過簡單地對通用“ZK CPU”進行編程來構建新的 ZKP。前者需要一個密碼學家，而後者只需要一個程序員，極大地降低了ZKP的進入門檻。

為了展示這種範式轉換的威力，我們使用它構建一個最流行的ZKP：給定公鑰(也就是離散對數)的私鑰知識。

私鑰知識的ZKP

要將比特幣鎖定到公鑰/地址，所有者必須表明他知道相應的私鑰。但他不能公開，否則比特幣可能被竊取。這是通過數字簽名完成的，它是ZKP²的一種形式。我們將展示使用zk-SNARK實現相同目標的另一種方法。

在比特幣中，公鑰Q就是私鑰d乘以生成器G。

下面的Circom代碼實現了比特幣橢圓曲線secp256k1上的標量乘法。我們可以很容易地用它證明Q是d的公鑰：

將第3行的輸入標量設置為d：注意，它是私有的，因此仍然是需要保密的。
將第4行的輸入點設為G。
將第6行的輸出設置為Q。

// encoded with k registers of n bits each
template Secp256k1ScalarMult(n, k) {
    signal private input scalar[k];
    signal public input point[2][k];


    signal output out[2][k];


    component n2b[k];
    for (var i = 0; i < k; i++) {
        n2b[i] = Num2Bits(n);
        n2b[i].in <== scalar[i];
    }


    // has_prev_non_zero[n * i + j] == 1 if there is a nonzero bit in location [i][j] or higher order bit
    component has_prev_non_zero[k * n];
    for (var i = k - 1; i >= 0; i--) {
        for (var j = n - 1; j >= 0; j--) {
            has_prev_non_zero[n * i + j] = OR();
            if (i == k - 1 && j == n - 1) {
                has_prev_non_zero[n * i + j].a <== 0;
                has_prev_non_zero[n * i + j].b <== n2b[i].out[j];
            } else {
                has_prev_non_zero[n * i + j].a <== has_prev_non_zero[n * i + j + 1].out;
                has_prev_non_zero[n * i + j].b <== n2b[i].out[j];
            }
        }
    }


    signal partial[n * k][2][k];
    signal intermed[n * k - 1][2][k];
    component adders[n * k - 1];
    component doublers[n * k - 1];
    for (var i = k - 1; i >= 0; i--) {
        for (var j = n - 1; j >= 0; j--) {
            if (i == k - 1 && j == n - 1) {
                for (var idx = 0; idx < k; idx++) {
                    partial[n * i + j][0][idx] <== point[0][idx];
                    partial[n * i + j][1][idx] <== point[1][idx];
                }
            }
            if (i < k - 1 || j < n - 1) {
                adders[n * i + j] = Secp256k1AddUnequal(n, k);
                doublers[n * i + j] = Secp256k1Double(n, k);
                for (var idx = 0; idx < k; idx++) {
                    doublers[n * i + j].in[0][idx] <== partial[n * i + j + 1][0][idx];
                    doublers[n * i + j].in[1][idx] <== partial[n * i + j + 1][1][idx];
                }
                for (var idx = 0; idx < k; idx++) {
                    adders[n * i + j].a[0][idx] <== doublers[n * i + j].out[0][idx];
                    adders[n * i + j].a[1][idx] <== doublers[n * i + j].out[1][idx];
                    adders[n * i + j].b[0][idx] <== point[0][idx];
                    adders[n * i + j].b[1][idx] <== point[1][idx];
                }
                // partial[n * i + j]
                // = has_prev_non_zero[n * i + j + 1] * ((1 - n2b[i].out[j]) * doublers[n * i + j] + n2b[i].out[j] * adders[n * i + j])
                //   + (1 - has_prev_non_zero[n * i + j + 1]) * point
                for (var idx = 0; idx < k; idx++) {
                    intermed[n * i + j][0][idx] <== n2b[i].out[j] * (adders[n * i + j].out[0][idx] - doublers[n * i + j].out[0][idx]) + doublers[n * i + j].out[0][idx];
                    intermed[n * i + j][1][idx] <== n2b[i].out[j] * (adders[n * i + j].out[1][idx] - doublers[n * i + j].out[1][idx]) + doublers[n * i + j].out[1][idx];
                    partial[n * i + j][0][idx] <== has_prev_non_zero[n * i + j + 1].out * (intermed[n * i + j][0][idx] - point[0][idx]) + point[0][idx];
                    partial[n * i + j][1][idx] <== has_prev_non_zero[n * i + j + 1].out * (intermed[n * i + j][1][idx] - point[1][idx]) + point[1][idx];
                }
            }
        }
    }


    for (var idx = 0; idx < k; idx++) {
        out[0][idx] <== partial[0][0][idx];
        out[1][idx] <== partial[0][1][idx];
    }
}

為了便於解釋，我們使用標準的雙加算法。主循環發生在第33行到第65行。我們在第42行使用 Secp256k1AddUnequal 進行點相加；在43行使用 Secp256k1Double 進行點加倍。在每次迭代中，我們都在第355-358行處加倍。如果設置了當前位，我們還會添加。

一旦我們有了Circom代碼，我們就可以使用通用的zk-SNARK庫來證明對私鑰的知識，同時保持它的機密性。我們已經演示了沒有數字簽名的方法。

證明組織成員身份

下面，我們將展示如何通過簡單地用零知識語言Circom“編程”實現另一個複雜的密碼原語：環簽名。

使用zk-SNARK的環簽名

在環簽名中，組/環的任何成員都可以簽名來證明他們的成員身份，而不需要透露他們的具體身份。基於簽名，驗證者可以確定組中的一個成員簽名，但他不知道是哪個成員籤的名。

由於zk-SNARK的可編程性和可組合性，我們可以在前面的點乘法庫的基礎上簡單地“編碼”環簽名，如下所示。

// `n`: chunk length in bits for a private key
// `k`: chunk count for a private key
// `m`: group member count
template Main(n, k, m) {
  signal private input privkey[k];
  
  signal public input pubKeyGroup[m][2][k];
  signal output existInGroup;


  // get pubkey from privkey
  component privToPub = ECDSAPrivToPub(n, k);
  for (var i = 0; i < k; i++) {
    privToPub.privkey[i] <== privkey[i];
  }


  signal pubkey[2][k];


  // assign pubkey to intermediate var
  for (var i = 0; i < k; i++) {
    pubkey[0][i] <== privToPub.pubkey[0][i];
    pubkey[1][i] <== privToPub.pubkey[1][i];
  }


  // check whether pubkey exists in group
  var exist = 0;
  component eq[2*m];
  var compareResult[m];


  for (var i = 0; i < m; i++) {
    // pubkey `x` comparer
    eq[i] = BigIsEqual(k);


    // pubkey `y` comparer
    eq[i+m] = BigIsEqual(k);


    for(var j = 0; j < k; j++) {
      // compare `x`
      eq[i].in[0][j] <== pubkey[0][j];
      eq[i].in[1][j] <== pubKeyGroup[i][0][j];


      // compare `y`
      eq[i+m].in[0][j] <== pubkey[1][j];
      eq[i+m].in[1][j] <== pubKeyGroup[i][1][j];
    }
    
    compareResult[i] = eq[i].out * eq[i+m].out;
  }


  component checker = InGroupChecker(m);
  for(var i = 0; i < m; i++) {
    checker.in[i] <== compareResult[i];
  }


  existInGroup <== checker.out;
}

從第11行到第22行，我們使用私鑰部分中介紹的ECDSAPrivToPub從第5行中的私鑰派生出第16行中的公鑰。然後，我們將得到的公鑰與第7行中定義的組中的每個公鑰進行比較。當且僅當它匹配組中第54行中的任何一個時，我們返回true。

由於私鑰輸入是私有的並且保持隱藏狀態，因此驗證者不能使用它來識別是哪個成員創建了證明。我們已經創建了一個ZKP的成員在組/環的環簽名，而無需瞭解任何底層密碼學。

ZKKSP

在上面，我們已經展示瞭如何使用稱為ZK Key-Statement proof (ZKKSP)的技術為以下語句構建零知識證明 (ZKP)。

雖然ZKKSP奏效，但它有一個很大的侷限性：它只適用於一種特定形式的語句，即secret是給定公鑰的私鑰，而且它也是給定哈希的原映像。目前還不清楚如何將其擴展到一個稍加修改的語句，例如，除了是私鑰和原映像之外，secret也是一個偶數。此外，提出它需要密碼學的專利級知識，如∑-protocol和承諾方案。

ZKKSP使用zk-SNARK

我們通過利用zk-SNARK的可編程性來重新實現ZKKSP。我們將 證明組織成員身份 部分中使用的橢圓曲線點乘法與散列庫簡單地結合起來。生成的Circom代碼如下所示：

// library circuits from http://github.com/0xPARC/circom-ecdsa
include "lib-circom-ecdsa/ecdsa.circom";
include "../node_modules/circomlib/circuits/sha256/sha256.circom";
include "../node_modules/circomlib/circuits/bitify.circom";


// `n`: chunk length in bits for a private key
// `k`: chunk count for a private key
template Main(n, k) {
  // n * k == 256
  assert(n * k >= 256);
  assert(n * (k-1) < 256);


  // little-endian
  signal private input privkey[k];
  signal public input pubkey[2][k];


  signal public output privkeyHash[k];


  // get pubkey from privkey
  component privToPub = ECDSAPrivToPub(n, k);
  for (var i = 0; i < k; i++) {
    privToPub.privkey[i] <== privkey[i];
  }


  // verify input pubkey
  signal pub_x_diff[k];
  signal pub_y_diff[k];
  for (var i = 0; i < k; i++) {
    pub_x_diff[i] <-- privToPub.pubkey[0][i] - pubkey[0][i];
    pub_x_diff[i] === 0;
    pub_y_diff[i] <-- privToPub.pubkey[1][i] - pubkey[1][i];
    pub_y_diff[i] === 0;
  }


  // calculate sha256 of privkey
  component sha256 = Sha256(256);
  for (var i = 0; i < k; i++) {
    for (var j =0; j < n; j++) {
      // change privkey to big-endian as sha256 input
      sha256.in[i * n + j] <-- (privkey[k-1-i] >> (n-1-j)) & 1;
    }
  }


  // set output
  component b2n[k];
  for (var i = 0; i < k; i++) {
    b2n[i] = Bits2Num(n);
    for(var j = 0; j < n; j++) {
      // `b2n` input is little-endian in bits, `sha256` out is big-endian in bits
      b2n[i].in[n-1-j] <== sha256.out[i * n + j];
    }
    privkeyHash[i] <== b2n[i].out;
  }


}


component main {public [pubkey]} = Main(64, 4);

與前面一樣，我們在第 15 行使用ECDSAPrivToPub 從第 14 行的私鑰派生出一個公鑰。然後我們使用第 3 行導入的sha256庫中的Sha256對相同的私鑰進行哈希處理，以確保結果與第 17 行的給定哈希匹配。我們只是“編程”了ZKKSP，不需要事先了解高級密碼學。此外，由於 zk-SNARK 的可組合性，我們可以輕鬆地對其進行擴展以添加對secret的約束。

Source：

http://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-1-9599deb1db47

http://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-2-890869249291

http://xiaohuiliu.medium.com/programmable-zero-knowledge-proofs-using-zk-snarks-part-3-d707dbfa2b28

關於

ChinaDeFi - ChinaDeFi.com 是一個研究驅動的DeFi創新組織，同時我們也是區塊鏈開發團隊。每天從全球超過500個優質信息源的近900篇內容中，尋找思考更具深度、梳理更為系統的內容，以最快的速度同步到中國市場提供決策輔助材料。

Layer 2道友 - 歡迎對Layer 2感興趣的區塊鏈技術愛好者、研究分析人與Gavin（微信: chinadefi）聯繫，共同探討Layer 2帶來的落地機遇。敬請關注我們的微信公眾號 “去中心化金融社區” 。

「其他文章」