環(huán)簽名的關(guān)鍵技術(shù)以及原理解析

隱私是用戶最關(guān)心的問(wèn)題之一，也是 PPIO 研究的重點(diǎn)。區(qū)塊鏈世界涉及隱私保護(hù)的技術(shù)很多，前不久 PPIO Code Talks 的李星老師 給我們分享的“零知識(shí)證明 zk-SNARKs”技術(shù) 就是 隱私保護(hù)的典型代表，今天我們?cè)賮?lái)分析一下另一個(gè)用于隱私保護(hù)的技術(shù)——環(huán)簽名 Ring Signature。

零知識(shí)證明解決的問(wèn)題是，我有一個(gè)秘密，我需要向你證明我知道這個(gè)秘密，但是我又不能讓你知道這個(gè)秘密。而環(huán)簽名解決的問(wèn)題是，我對(duì)你說(shuō)了一句話，但是你只知道是某一群人中有人對(duì)你說(shuō)了這句話，而不知道這群人里具體哪個(gè)人說(shuō)的。簡(jiǎn)言之就是，我把自己藏進(jìn)了人群里。環(huán)簽名通過(guò)將實(shí)際簽名者的公鑰藏進(jìn)一個(gè)公鑰集合，來(lái)達(dá)到保護(hù)簽名者身份的目的。

環(huán)簽名（Ring Signature）方案由 Rivest，Shamir 和 Tauman 三位密碼學(xué)家 于2001年首次提出。環(huán)簽名也被稱為 CryptoNote，由群簽名演化而來(lái)，典型的應(yīng)用案例是門羅幣。群簽名是利用公開(kāi)的群公鑰和群簽名進(jìn)行驗(yàn)證的方案，其中群公鑰是公開(kāi)的，群成員可以生成群簽名，驗(yàn)證者能利用群公鑰驗(yàn)證所得群簽名的正確性，但不能確定群中的正式簽名者?？墒侨汗芾韱T可以撤銷簽名，揭露真正的簽名者群簽名，這是群簽名的關(guān)鍵問(wèn)題所在。

環(huán)簽名方案則去掉了群組管理員，不需要環(huán)成員之間的合作，簽名者利用自己的私鑰和集合中其他成員的公鑰就能獨(dú)立的進(jìn)行簽名，集合中的其他成員可能不知道自己被包含在了其中。這種方案的優(yōu)勢(shì)除了能夠?qū)灻哌M(jìn)行無(wú)條件的匿名外，環(huán)中的其他成員也不能偽造真實(shí)簽名者簽名。外部攻擊者即使在獲得某個(gè)有效環(huán)簽名的基礎(chǔ)上，也不能偽造一個(gè)簽名。

那么環(huán)簽名是如何做到這點(diǎn)的呢？接下來(lái)我們用橢圓曲線來(lái)舉例說(shuō)明環(huán)簽名的具體技術(shù)關(guān)鍵點(diǎn)和原理。

環(huán)簽名生成過(guò)程

假設(shè)簽名者擁有某私鑰 sk 和公鑰 pk（為表述方便，下文中所有粗體表示橢圓曲線上的點(diǎn)），其中 pk = sk·g，這里 g 是 橢圓曲線上的 基點(diǎn)（base point），也被稱為生成元（generator）。而 “·” 這里是倍乘，sk·g 表示 sk 個(gè) g 點(diǎn)在橢圓曲線上進(jìn)行加法運(yùn)算。更多關(guān)于橢圓曲線密碼學(xué)相關(guān)的知識(shí)，可以參見(jiàn) PPIO 的另一篇文章《橢圓曲線密碼學(xué)》。

· 首先，先定義一個(gè) hash 函數(shù)，這個(gè) hash 函數(shù)的輸入是 待簽名的消息 m 和 橢圓曲線上的一個(gè)點(diǎn) A，即 Hash（m， A）。該 hash 函數(shù)和橢圓曲線一樣，是這個(gè)簽名和驗(yàn)簽體系的前提。

該 hash 函數(shù)的一個(gè)參考實(shí)現(xiàn)為：將 m 和 A 的字節(jié)數(shù)據(jù)拼接，然后用傳統(tǒng)的 hash 函數(shù)（如keccak256），得到的值再對(duì) N 取模（這里的 N 是橢圓曲線上有限群的階）。

· 接下來(lái) ，簽名方想對(duì)一消息 m 進(jìn)行簽名，但是又不想在公開(kāi)簽名的同時(shí)，讓別人知道自己的確切身份，因此 簽名方 決定用環(huán)簽名的方式將自己藏到一群人中。于是 簽名方 找來(lái) n-1 個(gè)其他人的公鑰（這些公鑰最好之前在系統(tǒng)中已經(jīng)出現(xiàn)過(guò)和使用過(guò)，不然 簽名方 藏在一堆新人中，還是會(huì)很容易的被識(shí)別出來(lái)），并編好序號(hào)，并將自己的公鑰隨機(jī)地插入其中，共同組合了一個(gè)包含 n 個(gè)公鑰的集合。不妨假設(shè)這 n 個(gè)公鑰為

pk0， pk1， pk2， …， pki-1， pki， pki+1， …， pkn-1

其中 pki 為簽名方的公鑰。

· 然后，簽名方隨機(jī)生成 n-1 個(gè)隨機(jī)數(shù) s0， s1， …， si-1， si+1， …， sn-1， 分別與除 pki 以外的 n-1 個(gè)公鑰一一對(duì)應(yīng)。

注意：這一步無(wú)需隨機(jī)生成 si，因?yàn)?si 會(huì)在后面通過(guò)計(jì)算得到。

· 接著，簽名方隨機(jī)生成 k， 并計(jì)算 k·g， 這里我們先假設(shè)

k·g = si·g+ci·pki （等式①）

這里 等式① 的用途暫時(shí)可能不太好理解，但可先不用管。但根據(jù) 等式① 我們可以確定的是，如果擁有 pki 的私鑰 ski，且如果已知 ci 和 k，那就可以反向求出 si。

注意：這里的 ci 是根據(jù)上一個(gè)公鑰 pki-1 和消息 m 計(jì)算出的 hash 值

· 接下來(lái)引入第2個(gè)式子，

cx = Hash（m， sx-1·g+cx-1·pkx-1） （等式②）

等式② 是一個(gè)遞推式，且 Hash 函數(shù)的第二個(gè)參數(shù)形式上跟 等式① 的右側(cè)是一樣的。這個(gè)遞推式的意思是：已知第 x-1 個(gè)公鑰對(duì)應(yīng)的 sx-1 和 hash 值 cx-1，求下一個(gè)公鑰對(duì)應(yīng)的 hash 值 cx。注意，當(dāng) x=0 時(shí)，x 的上一個(gè)其實(shí)是 n-1，因?yàn)橄聵?biāo)也要對(duì) n 取模。

· 由于在 等式① 中我們定義了 k·g = si·g+ci·pki 所以 ci+1 可直接由計(jì)算得到

ci+1 = Hash（m， si·g+ci·pki） = Hash（m， k·g）

注意：此時(shí)求 ci+1 過(guò)程中我們暫時(shí)并不知道 si 和 ci，但后面計(jì)算得到 ci 后，可以由 k， ci+1 和 ci 求出 si。

緊接著，依次計(jì)算 ci+2， … ， cn-1， c0， …， ci-1， ci： （如圖 1）

ci+2 = Hash（m， si+1·g+ci+1·pki+1）

。..

cn-1 = Hash（m， sn-2·g+cn-2·pkn-2）

c0 = Hash（m， sn-1·g+cn-1·pkn-1）

c1 = Hash（m， s0·g+c0·pk0）

…

ci = Hash（m， si-1·g+ci-1·pki-1）

圖 1 計(jì)算 ci+1， … ， cn-1， c0， …， ci-1， ci 過(guò)程

· 有了 ci之后，回頭觀察等式① ，由于 pki 的私鑰是已知的，即

pki = ski·g

因此 等式① 可寫(xiě)成

k·g = si·g+ci*ski·g

兩邊約去 g，變?yōu)?/p>

k = si + ci*ski

從而根據(jù) k，ci，ski 可以求出 si （如圖 2）即

si = k - ci*ski

注意：私鑰 ski 在這里發(fā)揮了作用，如果沒(méi)有 ski，si也無(wú)法求出。

圖 2 根據(jù)私鑰 ski， k， ci求解 si 過(guò)程

· si 一旦求出后，環(huán)簽名的環(huán)就形成了。而且此時(shí) k 值的使命也已完成，可以被拋棄掉了。

換句話說(shuō)，正因?yàn)槲覀儞碛兴借€ ski， 所以可以構(gòu)造出一個(gè) si，配合隨機(jī)生成的s0， s1， …， si-1， si+1， …， sn-1，使得以下式子都成立：

c0 = Hash（m， sn-1·g+cn-1·pkn-1）

c1 = Hash（m， s0·g+c0·pk0）

…

cn-1 = Hash（m， sn-2·g+cn-2·pkn-2）

反之，如果這 n 個(gè)公鑰中的任何一把私鑰 簽名者都沒(méi)有，那么他也就無(wú)法求出 si 使得{c0， pk0， …。 pkn-1， s0， …。， sn-1}形成一個(gè) 環(huán)。

因此，如果上述 n 個(gè)等式成立，那么也有意味著，生成這 n 個(gè)等式的人至少擁有這 n 個(gè)公鑰中一把私鑰。

· 最后消息 m 的環(huán)簽名數(shù)據(jù)為：

Signature = {c0， pk0， …。 pkn-1， s0， …。， sn-1}

簽名驗(yàn)證過(guò)程

驗(yàn)證者根據(jù) c0， pk0， …。 pkn-1， s0， …。， sn-1，消息 m 和 等式② 依次求出 c1， c2， …。， cn-1， 最后根據(jù) cn-1 求出 c’0，并判斷

c0 ？= c’0

如果相等則簽名有效，如果不等則簽名無(wú)效。

應(yīng)用場(chǎng)景

目前，使用環(huán)簽名方案的項(xiàng)目包括門羅幣 Moreno、布爾幣 Boolberry、StealthCoin、XCurrency 等，以太坊平臺(tái)也增加了一個(gè)類 CryptoNote 環(huán)簽名。

門羅幣（Monero）：門羅幣是應(yīng)用環(huán)簽名的典型代表，環(huán)簽名技術(shù)使得門羅被公認(rèn)為是一個(gè)私密性強(qiáng)，不可追蹤的加密貨幣。環(huán)簽名幫助門羅幣實(shí)現(xiàn)了交易的隱私性：通過(guò)區(qū)塊鏈系統(tǒng)中無(wú)關(guān)節(jié)點(diǎn)無(wú)法追查交易的發(fā)送方，當(dāng)其它節(jié)點(diǎn)驗(yàn)證交易時(shí)，只能確定簽名是諸多公鑰中的一個(gè)，卻無(wú)從定位到哪個(gè)公鑰才是具體的發(fā)送方。

一票否決場(chǎng)景：例如，某協(xié)會(huì)主席提出一種議案，但如果協(xié)會(huì)成員中有人提出反對(duì)意見(jiàn)則議案需被取消。但投反對(duì)票的會(huì)員又不想暴露自己的身份，因此他可以用環(huán)簽名的技術(shù)，將自己的反對(duì)票用自己的私鑰和其他協(xié)會(huì)成員的公鑰進(jìn)行簽名。簽名之后所有協(xié)會(huì)成員都可以看到協(xié)會(huì)中有人反對(duì)該項(xiàng)議案，但不知道確切的反對(duì)者是誰(shuí)。

總結(jié)

回顧一下簽名的整個(gè)過(guò)程，關(guān)鍵的巧妙點(diǎn)在于，如果知道私鑰 ski，那么就可以反推出 si，使 c1， c2， …。， cn-1 形成一個(gè)環(huán)。就好像簽名者找了一根鐵絲，數(shù)學(xué)保證了只有擁有私鑰的人，才能把鐵絲的兩頭接起來(lái)，形成鐵絲環(huán)。而且一旦成為鐵絲環(huán)之后，環(huán)的接點(diǎn)處也沒(méi)有任何痕跡，這使得驗(yàn)證者無(wú)法判斷鐵環(huán)是在哪個(gè)位置上接起來(lái)的。

環(huán)簽名雖然可以用來(lái)做到一定程度的匿名性，不過(guò)畢竟真實(shí)的簽名者還是會(huì)暴露在環(huán)中。且在目前的公有鏈?zhǔn)袌?chǎng)上，與環(huán)簽名相比，零知識(shí)證明依然是最佳的匿名方案之一。只是在某些場(chǎng)景下，如果對(duì)隱私的要求沒(méi)有那么高，同時(shí)簽名方的計(jì)算能力又很弱，環(huán)簽名不失為一個(gè)不錯(cuò)的選擇。
責(zé)任編輯；zl