您的位置: 首页  >  文章  >  环签名技术 AOS/Borromean

环签名技术 AOS/Borromean

分类: 文章 • 2025-03-06 15:28:17

环签名技术

环签名是一种签名技术，直白来说，通常是有一组公钥，签名方知道一组公钥中某一公钥所对应的私钥(只需知道一个即可)。这样，他就可以使用这一组公钥和那个对应的私钥生成一个环签名。验证者可以验证确实是这组公钥中某个私钥的拥有者生成的环签名，但是却不知道是哪个公钥对应的私钥。

环签名的一个典型的应用场景是匿名举报。在一个组织内，组织内的举报人可以使用其他成员的公钥联合自己的公私钥对一次举报进行签名，管理人(验证者)会看到确实是组织内的人发起了这样的举报，但管理人不会知道具体是哪一个成员发起的举报。如此，在确保了举报的真实性的情况，隐藏了举报人，以避免了对举报人的一些不良后果，如恶意报复等。

有很多实现环签名的技术，如今在区块链隐私领域比较常见的两个环签名算法是AOS和Borromean环签名。

AOS(Abe-Ohkubo-Suzuki)环签名

2002年，Abe、Oh????ub????和Suzu????i基于离散对数问题开发了一种新型的环签名，他们使用因果环(尽管他们没有用这个词)来达到效果。与早期的环签名相比，这种因果环的使用使签名的大小显著减少了(50%)。

理解AOS环签名之前需要理解Schnorr签名的过程，前文已经介绍，这里用到的是非交互的Schnorr签名过程。值得一提的是，前文说到非交互式的Schnorr签名使用哈希函数，并计算e = HASH(R||message)来保证签名者无法构造R来作弊。但是我们接下来可以看到，如果对哈希函数的输入结构进行一定的构造，就可以通过指定的输入数据来提前计算e的值。

变色龙哈希(chameleon hashes)

简单提一下在AOS中使用到的Schnorr签名的过程。

  • 证明者拥有私钥x，并且计算其公钥P = x * G
  • 证明者选择一个随机标量k，并对消息message签名并计算e = HASH(message||k * G)
  • 证明者计算标量值s = k + e * x并且公开(s,e,P)

验证方通过计算s * G - e * P得到理论的k * G值，再验证e ?== HASH(message||k * G)判断验证签名是否合法。

接下来介绍变色龙哈希(chameleon hashes)，在讲解AOS的论文中，对这一部分叙述的很累赘，提出了很多的概念，例如时间旅行(Time Travel)、因果循环(causal loops)等，我觉得是把简单的问题复杂化了。

简而言之，变色龙哈希是一种输入为特定结构的哈希函数，而这种输入的结构允许有陷门(Trapdoor)存在，这个陷门也可以称作后门，知道陷门信息的一方可以通过构造输入数据使得在改变输入的情况使得哈希函数的输出不变。这就造成了这种哈希函数不具有抗碰撞性，即给定一个m和Hc(m)，可以迅速找到m'，使得Hc(m) == Hc(m')。当然在AOS环签名中，使用变色龙哈希是为了通过陷门信息构造一个输入，以匹配已经提前计算好的e值，后面可以看到这种实现的过程和原因。

如下构造一个变色龙哈希函数，式中的G和P是群内的两个点，陷门信息是x，使得P = x * G成立。

Hc(message,e,s) = HASH(message||s*G-e*P)

注意到，如果

s = k + x * e

则可以在不预先知道e的情况下计算

e=Hc(message,e,s)=HASH(message||k*G+x*e*G-e*P)

即

e=Hc(m,e,s)=HASH(message||k*G)

可以看到，通过使用变色龙哈希函数对Schnorr签名的过程进行修改，可以使得拥有陷门信息的人可以无视Schnorr签名的规则，进行逆转，这是我们生成AOS环签名最关键的理念和步骤

签名和验证过程

在详细讲解签名过程之前，先放一张AOS环签名的逻辑图

环签名技术 AOS/Borromean

左边是Schnorr签名的过程，右边是AOS环签名的过程。接下来的阐述会以最直观地方式呈现，不会有一大段的公式和推导，就是一步步完成签名所需要的计算步骤。

首先签名者有一组公钥集合{Pi}，其中0<=i<=n-1，签名者知道其中一个公钥所对应的私钥xj，使得Pj = xj * G，生成签名的步骤如下(为了简洁，下述过程没有写入要签名的信息message)：

  • 均匀随机生成k*G，并计算 ej+1 = H(k*G)
  • 均匀随机生成sj+1，并结算ej+2 = HASH(sj+1G - ej+1Pj+1)
  • 均匀随机生成sj+2，并结算ej+3 = HASH(sj+2G - ej+2Pj+2)
  • …
  • 均匀随机生成sj-2，并结算ej-1 = HASH(sj-2G - ej-2Pj-2)
  • 均匀随机生成sj-1，并结算ej = HASH(sj-1G - ej-1Pj-1)

稍微解释一下，对一组公钥集合{Pi}，其中i是下标。签名从下标j之后开始计算，如果计算到了最后一个(下标为n-1)，则回到第一个(下标为0)进行计算，直到计算到j。这时候，所有的e已经算完了，s已经就算到了sj-1，在此之前的s都是随机生成的。到了这一步的时候，我们需要制定一个sj值，以使得可以和ej+1进行匹配，如下进行计算

  • 设sj = k + xj*ej

此时，可以看到，由于签名者拥有陷门信息xj，使得Pj = xj * G，那么如果接着计算ej+1，则有

ej+1 = HASH(sjG - ejPj) = HASH(kG + xjejG - ejPj) = H(k*G)

正好和最初计算的ej+1进行了匹配，可以直观地感受到，这形成了一个闭环，至于为什么要计算sj来进行匹配，通过看后面验证者进行验证的过程则会加深理解。

  • 最后签名者提交的签名是(si,e0)，其中0<=i<=n-1

现在来说验证方验证的过程，验证方拿到(si,e0)之后，结合已有的公钥组{Pi}。验证的工作就是从e0开始，不断地进行判断

ei+1 ?== HASH(siG-eiPi)

直到最后一组数据en-1和sn-1也判断完毕，则说明该签名是合法有效的。

透过验证方的验证过程可以看出，上述使用陷门信息的目的就是构造输入，使得哈希函数的输出能够匹配一个已经计算好的值，这样就可以通过验证方的验证。并且，值得一提的是，由于这个过程不牵涉到签名方使用的私钥的下标即j，故签名方的私钥可以被完美地隐藏起来。

这就是AOS环签名！

Borromean环签名

Borromean环签名其实是AOS的多环实现，如果能彻底理解AOS的逻辑图和算法过程，那么通过看Borromean的逻辑图就能理解Borromean在做一件什么事情了。

环签名技术 AOS/Borromean

说白了，其实就是通过构造多个环来实现环签名，只要在每一个环中都拥有一个陷门信息就可以做到。

Borromean环签名算法被用于现在最有名的rangeproof算法bulletproof中，所以地位还是相当高的。由于本文不会介绍bulletproof，所以对于Borromean的具体算法细节不做过多的讨论.

markdown对公式的支持太不友好了，这里放出Borromean算法签名和验证的算法过程。如果能完全理解AOS的算法过程的话，那么理解Borromean也不会是难事，无非是构造了多个环，进行多轮的验证。

签名过程

环签名技术 AOS/Borromean

验证过程

环签名技术 AOS/Borromean

环签名技术会在通过使用Mimble-Wimble实现的隐私资产中得到应用，由于在一笔交易中可能存在多种不同的资产转移，则需要使用环签名来证明一笔交易的某个输出资产是输入资产中的一种。具体的实际应用，可以看我的另一篇文章区块链上的隐私技术——Mimble-Wimble。

Tips : 文章同步更新至我的Github : Kingsley-Sun的Github

相关推荐