Borromean环签名是如何实现匿名转账的?

本文由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%) 。描述如下:

Borromean环签名是如何实现匿名转账的?

Borromean环签名是如何实现匿名转账的?

这是非常代数的。我们可以提取承诺的结构,以查看这些环签名“真正“发生了什么。为此,我们将它们绘制为有向图。图的顶点由变色龙哈希输出进行标记;入边由盲化的输入标记。(和Schnoor签名情况一样, 盲化的输入要求知道边的源点的值,或者需要-些秘密知识;区别在于在Schnorr情况下,只有一条边的源顶点和目标顶点相同)。

换句话说:和以前一样,我们有一个时间观念,它只要求哈希e仅在其输入被确定后才能知道。我们可以使用变色龙哈希为拥有陷门信息的人改写这个时间顺序。我们可以将此时间顺序绘制为有向图,并进行两个探讨:

1.为了形成一个循环,需要通过一个承诺实现“时光倒流”,因此,只需要一个密钥就够了。

2.从验证者的角度来看,用于“时光倒流”的承诺和普通承诺是没有区别的。此外,他只能看到图结构:我们在插图中使用的颜色和箭头是不可见的。

这两个观察结果-起描述了Abe-Ohkubo-Suzuki环签名的工作原理:这仅仅是一个变色龙哈希承诺的循环。

3.Borromean环签名

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

可以证明,单调函数恰好是那些可以用不取反的析取范式电路表示的函数;即以下形式的电路:


Borromean环签名是如何实现匿名转账的?

如果所有输入为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环签名是如何实现匿名转账的?

由此,我们可以绘制描述Borromean签名的示例图:

Borromean环签名是如何实现匿名转账的?

Borromean环签名是如何实现匿名转账的?

一般来说,如果采用n个环的结合,与使用分离的环签名相比,我们节省了n-1个承诺。

3.3 具体算法

以上以图形的方式对Borromean环签名进行了描述,并在技术,上提供了实现它们所需的所有信息。但是,细节决定成败,并且事实上如何计算这些签名也不是那么显而易见的。因此,我们列出了实际的签名和验证算法。

3.3.1签名

Borromean环签名是如何实现匿名转账的?

Borromean环签名是如何实现匿名转账的?

3.3.2验证

由于验证过程不依赖需要知道哪些密钥被使用,这避免了.两阶段”的签名结构,因此更加简单。

Borromean环签名是如何实现匿名转账的?

3.4 性能比较

最后,我们将我们的方案与现有的环签名进行比较。我们考虑在n个环上使用N个验证密钥进行签名。

Borromean环签名是如何实现匿名转账的?

这里“Size”是用字段元素或者哈希来衡量的,拥有128比特安全的32字节。

4.未解决的问题

在前文中,我们介绍了与析取范式表达式中的a,的大小成比例的签名方案。


Borromean环签名是如何实现匿名转账的?

通过避免析取范式,可以通过用更小的空间来表示这些电路;但是,还不清楚应如何构造与这些电路相对应的签名。

类似地,通过使用阈值门而不是仅仅使用ANDI门和OR门,可以节省许多单调函数的空间。不过如何将其转换到我们的框架中也是未解决的。

关键词: Borromean  环签名  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28310

联系我们

aliyinhang@gmail.com