monero门罗币ringsignatures环签名算法浅解:(2)AdamBack提出的改进算法
发布于 17 天前 作者 xibiren 104 次浏览 来自 比特币

本文来自: http://blog.sina.com.cn/s/blog_18804e3000102xnyh.html

CryptoNote 2.0白皮书提出的Ring signatures算法早已不用,也很难懂。我们直接看Adam Back提出的改进算法。

类比上次的例子,这个算法就是要用多个公钥创建一个方程,只需持有其中一个对应私钥就可个揭开它。这个方程是什么呢?

假设我们是要验证monero区块链上一个transaction,先看已知信息:

transaction给出了用作输入的n个公钥。为了更具体好懂,我们假设n=3。所以有P1,P2,P3

transaction还给了你三个数: m,I和c1,m是付款方要endorse的message,可以看成是任选的一个数,I和c1有特殊意义,先不管这两个数是怎么来的。 transaction还给了另外一组数:s1, s2, s3,分别对应P1, P2, P3。

好,让你验证: 设 L1 = s1G + c1P1, 设 R1 = s1Hp(P1) + c1I,其中Hp()是一个哈希函数。 计算: c2 = Hs(m, L1, R1),Hs()是另一个哈希函数。哈希函数的输入一般是一个数,那么m, L1, R1三个数是怎么做输入的呢?把这三个数拼在一起就行了。 同样的,计算: L2 = s2G + c2P2 R2 = s2Hp(P2) + c2I c3 = Hs(m,L2,R2)

L3 = s3G + c3P3 R3 = s3Hp(P3) + c3I c4 = Hs(m,L3, R3)

根据ring signature,到这个时候,如果发现c4 = c1,则证明付款方持有P1,P2,P3其中一个所对应的私钥,验证成功,区块链接受这笔付款。否则就是扯淡。这里显然,验证方是无法知道哪个私钥是用来生成这个等式的。这个等式就像一个咬自己尾巴的蛇,称之为环签名非常贴切。

如果不知道其中任何私钥,想要解这个方程,就只能暴力破解。密码学上假设,这在现有的算力上做不到。

那么,如果你是付款方,你知到一个私钥。你是怎么解这个方程,生成上述等式的呢?

假设你知道P2对应的私钥x2:

先让 I = x2*Hp(P2) 任选m,你再先随便选一个数a,算出:

L2 = aG R2 = a*Hp(P2) c3 = Hs(m,L2,R2)

选任意s3,无所谓 L3 = s3G + c3P3 R3 = s3Hp(P3) + c3I c1 = c4 = Hs(m,L3, R3)

选任意s1 L1 = s1G + c1P1 R1 = s1Hp(P1) + C1I c2 = Hs(m,L1,R1)

到这里,m, I, c1, (c2和c3不用),s1, s3都有了,还缺s2

让 s2 = a - c2x2,所以 a = s2 + c2x2

则有: L2 = aG = (s2 + c2x2)G = s2G + c2P2 (在ECC椭圆线上x2G = P2)。 R2 = aHp(P2) = (s2 + c2x2)Hp(P2) = s2 + c2x2Hp(P2) = s2 + c2*I

等式成立!

I在这里叫做 key image,他有一个作用。虽然第三方无法知道你花的钱是来自P1, P2, P3中的哪一个,但是P2对应的key image I只能有一个。如果你试图double spend P2,势必会得到重复的I。已经出现过的I会被验证方拒绝。

值得一提的是,这个算法并非Adam Back所创。提出这个算法的是Joseph Liu, Victor Wei and Duncan Wong , 看名字似乎是中国人。

回到顶部