本文由Gregory Maxwell和Andrew Poelstra共同撰寫，詳細介紹了Borromean環簽名的演算法、使用方法及現存的一些問題。Borromean環簽名是區塊鏈中最常用的一種環簽名演算法，在Monero等Confidential Assets中都有使用。以下為原文譯文：摘要2002年，Abe， Ohkbo和Suzuki基 於離散對數問題開發了一種新型的環簽名，其使用新穎的承諾結構顯著節省了環簽名的大小和驗證時間。環簽名是一種使用n個金鑰聯合的簽名，簽名者需要知道其中一個金鑰所對應的私鑰。可以將它們視為一種析取表示式的簽名:“ 我知道x1 OR我知道x2 OR ..’..我們對它們的構造進行了概括以處理聯合表示式“我知道{x1,x2,x...}中的一個AND我知道{x4,...中的一個..”，從而有能力表達對簽名金鑰的任何單調布林函式的瞭解。這可以透過使用多個獨立的環簽名來輕鬆完成。透過在各個獨立的環之間共享承諾，我們的結構可以節省儲存空間。我們還用“因果環’'描述了-種關於這些環簽名和普通Schnorr簽名的新思維方式，這可以為進一步歸納提供框架。1. 隨機預言和Schnorr簽名在整個過程中，我們假設正在一個迴圈加性群g中工作,對於該群而言，離散對數問題很難解決，並且G是該群中某個固定的已知生成器。1.1 Schnorr驗證考慮以下由Claus Schnorr在1989年開發的互動式身份驗證協議，該協議允許一個公鑰組元素P=xG的秘密 離散對數x的擁有者，能夠證明他了解x但不揭露任何資訊:1.證明者選擇一個隨機標量k並 將kG提交給驗證者2.驗證者響應回覆一個隨機挑戰標量e。3.證明者回復標量值s←-k+xe驗證者不知道k，因為解決離散對數問題是困難的，但是他可以驗證s是如實計算的，因為s=k+xe等 同於sG=kG+ex-G，並且驗證者知道s, e, kG和xG。從直覺上說，這是零知識，因為如果驗證者不小心洩露給證明者e值是什麼，則證明者可能在他根本不知道x的情況下生成一-個合法的s。(具體來說， 她會隨機選擇s，然後選擇“kG"為“sG -exG")在這種情況下，證明者/驗證者互動的記錄與誠實遊戲中的記錄在統計上是無法區分的;因此，如果不誠實的遊戲沒有透露任何有關x的資訊(甚至沒有使用x)，那麼誠實的遊戲也不會。憑直覺，它證明了證明者知道x，因為e是隨機均勻選擇的。如果無論e是什麼她都能贏，那麼簡單地“分叉”她，併為每個分叉賦予不同的e值，例如e,和e2。 那麼，兩個叉將產生s-=k+xe,和s2=k+Xe2,這將x暴露為x=(s-s2)/(e,-e2)。換句話說，無論e值是什麼均可獲勝的驗證者可用於提取x的值，因此她必須具有x的知識。1.2 隨機預言和Fiat-Shamir上述方案不是公開可驗證的，原因與零知識完全相同。就是說，證明者和驗證者之間的互動記錄與他們勾結在一起以避免有人知道x是無法區分的。因此，在誠實遊戲中，證明者只向驗證者證明x的知識，而不向其他任何人證明。幸運的是，由於驗證方除了產生響應挑戰的隨機值外沒有其他用途，因此它具有非常簡單的數學描述:稱為隨機函式。隨機函式是數學函式，可在每個輸入上返回獨立均勻的隨機值。“評估”這樣的函式在功能上等同於在每個新輸入上提交質詢值並接收新的隨機值。因此，隨機函式通常被稱為隨機預言。隨機函式具有無限的Kolmogorov複雜度，無法在一臺機器中進行例項化，但是我們將其替換成稱為雜湊函式的簡單函式，並沒有已知的方法能將它們與隨機函式區分開。這給了我們所謂的隨機預言模型，其中我們有效地擁有了一個存在於柏拉圖形式世界中的挑戰者，我們將其稱為隨機預言。與傳統的挑戰者模式相比，隨機預言有兩個好處: (a) 預言的行為是公開可驗證的，如果行為不誠實是可以被發現的。因此透過“向預言證明”對離散對數的知識，實際上可以向所有人證明這一-知識; (b) 預言是透過雜湊函式建模的，任何人都可以計算該雜湊函式以重新建立互動記錄,因此無需進行任何實際互動。用隨機預言代替實際挑戰者的想法被稱為Fiat- -Shamir變換，它是第一個使用該想法將互動式方案轉變為非互動式可公開驗證方案的。將Fiat- -Shamir變換應用於上述互動方案，可以得到Schnorr簽名方案，其工作原理如下:1.證明者選擇一個隨機標量k，並計算e=H(kG)。2.證明者計算標量值s←-k+xe並且公開(s,e)。由於H對於不同的輸入返回不同的e，因此可以在其輸入中新增內容。例如，為訊息m計算H(mllkG)。結果是包含m的記錄，如果不知道x則無法更改m。因此，這是m. 上的“知識簽名”。任何人都可以先計算kG=sG- -eP來驗證簽名的合法性，並且檢查這確實是承諾的值，即e馬與H(kG)。驗證過程中使用了P=xG這樣的事實，使得該簽名與x是有聯絡的。2.環簽名2.1 時間旅行和變色龍雜湊上述身份驗證方案的關鍵要素是時間順序。我們觀察到，如果證明者可以預測未來並在選擇kG之前確定e,則他可以在不知道x的情況下成功進行身份驗證。在隨機預言模型中，不再有互動過程，也就不再有時間的先後。但是，隨機預言H提供了自己的時間順序:由於對於任何輸入y，如果不對其進行揭露就不可能知道H(y)(除非猜測它，但成功的可能性很低)，因此我們可以說H(y)在y之後確定。因此，儘管我們對時間的定義已經改變，但我們保留了時間至關重要的思想。時間的這種定義允許透過使用密碼學的一些技巧，使得秘密知識的擁有者可以完成逆轉。它的工作方式是調整我們的雜湊函式H,使其成為變色龍雜湊。變色龍雜湊不僅取一個輸入e，還取一個隨機值s作為輸入。某些秘密“陷門資訊”的擁有者將能夠調整s，從而在不更改雜湊輸出的情況下更改e。但普通人仍受時間定律的約束:一旦計算了e的雜湊，e就已經成為過去了，並且不能更改。如下所示，我們從一個普通的雜湊函式H來定義變色龍雜湊。這裡的G和P是群內的生成器。陷門資訊是x，使得P=xG。我們的雜湊函式是: H' (m,e,s)=H(ml|sG-eP)(這實際上是一個“半變色龍雜湊”:具有陷門資訊的人可以透過適當地更改s來更改e的值，但是沒有人可以在不更改雜湊函式輸出的情況下更改m。)我們注意到如果s=k+xe，s來自Schnorr簽名的值，則可以在不預先知道e的情況下計算e=H’(m,e,s)=H(m||kG)。 因此，我們可以將Schnor簽名描述為一對(s,e)， 其中e既是變色龍雜湊的輸入和輸出，s是其隨機輸入。由於雜湊的輸出是隨機並且獨立於其輸入的，因此強制輸入等於輸出需要陷門資訊，因此證明了簽名者具有此資訊。這個結果稱為知識簽名。換句話說，我們可以認為Schnorr籤 名的工作方式如下:為了在不知道金鑰x的情況下生成Schnorr簽名，必須預測隨機預言H的輸出，從而有效地“時光倒流”。簽名的結構本質上包含其自身的雜湊，從而形成因果迴圈並迫使簽名者知道陷阱門資訊。在下一節中，我們將歸納這種因果迴圈並認識到它們是一種有用的抽象工具。2.2 Abe-Ohkubo- Suzuki環簽名環簽名是數字簽名的- -種變體，其中，驗證金鑰被一組驗證金鑰所代替。每個驗證金鑰都有-個對應的私鑰，只需要一個私鑰即可生成一個環簽名。然而，所有的驗證金鑰在驗證簽名的過程中扮演者同樣的角色，因此被用於簽名的那個驗證金鑰仍然是秘密的。Rivest，Shamir和Tauman在2001年提出 了環簽名。他們建議的運用案例是舉報:一個各方連線良好的組織內，舉報人可以使用其他各方的驗證金鑰來構建環，然後簽名訊息以舉報一些陰謀。驗證者會看到是組織內的人已經簽署了此舉報，以確保其真實性，但他們不知道具體是誰做的，從而避免了對個人的一些不良後果。2002年，Abe、Ohkubo和Suzuki基於離散對數問題開發了一種新型的環簽名，該環使用因果環(儘管他們沒有用這個詞)來達到效果。與早期的環簽名相比，這種因果環的使用使簽名的大小顯著減少了(50%) 。描述如下:
這是非常代數的。我們可以提取承諾的結構，以檢視這些環簽名“真正“發生了什麼。為此，我們將它們繪製為有向圖。圖的頂點由變色龍雜湊輸出進行標記;入邊由盲化的輸入標記。(和Schnoor簽名情況一樣， 盲化的輸入要求知道邊的源點的值，或者需要-些秘密知識;區別在於在Schnorr情況下，只有一條邊的源頂點和目標頂點相同)。
換句話說:和以前一樣，我們有一個時間觀念，它只要求雜湊e僅在其輸入被確定後才能知道。我們可以使用變色龍雜湊為擁有陷門資訊的人改寫這個時間順序。我們可以將此時間順序繪製為有向圖，並進行兩個探討:
1.為了形成一個迴圈，需要透過一個承諾實現“時光倒流”，因此，只需要一個金鑰就夠了。
2.從驗證者的角度來看，用於“時光倒流”的承諾和普通承諾是沒有區別的。此外，他只能看到圖結構:我們在插圖中使用的顏色和箭頭是不可見的。
這兩個觀察結果-起描述了Abe-Ohkubo-Suzuki環簽名的工作原理:這僅僅是一個變色龍雜湊承諾的迴圈。
3.Borromean環簽名
更正式地說，令V為一組驗證金鑰，而f為將V的有限子集對映到{0,1}的函式。我們稱f為容許函式，那麼驗證金鑰的一個容許集V滿足f(V)=1。
Borromean環簽名σ是訊息m上的簽名，它帶有驗證金鑰的一個集合V和一個容許函式f，並且滿足下列條件:
1.σ只能由知道驗證金鑰一個容許集V全部私鑰的一方產生。
2.給出σ，V和m,在統計意義.上是無法分辨哪一個容許集合V被使用了。
3.1 單調函式
我們觀察到如果V是一個容許集，那麼它的超集V"也是容許的。原因是，如果V是允許的，那麼持有V'的簽名私鑰的一方可以透過簡單地忽略在V'而不在V中的金鑰，來生成一個簽名。因此，我們可以對f進行如下的限制:如果f(V)=1,那麼對於所有的V'2V，f(V')=1。 滿足這個限制的函式成為單調函式。
3.2 AND和OR
可以證明，單調函式恰好是那些可以用不取反的析取正規化電路表示的函式;即以下形式的電路:
如果所有輸入為1, A或者AND會輸出1;如果所有輸入為0，V或者OR會輸出0。
我們觀察到Abe-Ohkubo-Suzuki簽名方案可以描述為容許函式f只有一個OR1”]的Borromean環簽名。我們更普遍地觀察到，可以在迴圈之外構造OR門，如前面部分所述。
為了將這些OR門結合在一起，僅建立不相交的圖就足夠了，每個圖都對應於一個AOS簽名。但是，透過建立與AND門相對應的新圖形結構，我們可以做的更好。具體來說，如果我們建立一個具有多個向外邊的頂點e (意味著多個s值，且分別需要秘密知識或者e值)，那麼我們就構造了-個AND門，而不需要多個圖。
可以很容易地看到如何構造簽名，以便其圖具有帶有多條出邊的頂點:標記為(e,x)的頂點的每條邊i由s,表示，該s,值可以是隨機的或是s,=k, -xe。我們需要使每個路徑都成為迴圈的一部分。這迫使我們也具有帶有多條入邊的頂點(參見圖2的邊e。)。這意味我們需要改變承諾的結構。
由此，我們可以繪製描述Borromean簽名的示例圖:
一般來說，如果採用n個環的結合，與使用分離的環簽名相比，我們節省了n-1個承諾。
3.3 具體演算法
以上以圖形的方式對Borromean環簽名進行了描述，並在技術，上提供了實現它們所需的所有資訊。但是，細節決定成敗，並且事實上如何計算這些簽名也不是那麼顯而易見的。因此，我們列出了實際的簽名和驗證演算法。
3.3.1簽名
3.3.2驗證
由於驗證過程不依賴需要知道哪些金鑰被使用，這避免了.兩階段”的簽名結構，因此更加簡單。
3.4 效能比較
最後，我們將我們的方案與現有的環簽名進行比較。我們考慮在n個環上使用N個驗證金鑰進行簽名。
這裡“Size"是用欄位元素或者雜湊來衡量的，擁有128位元安全的32位元組。
4.未解決的問題
在前文中，我們介紹了與析取正規化表示式中的a,的大小成比例的簽名方案。
透過避免析取正規化，可以透過用更小的空間來表示這些電路;但是，還不清楚應如何構造與這些電路相對應的簽名。
類似地，透過使用閾值門而不是僅僅使用ANDI門和OR門，可以節省許多單調函式的空間。不過如何將其轉換到我們的框架中也是未解決的。
