Open AlexiaChen opened 3 years ago
写这篇文章的缘由是因为之前我提到过我们链的DPoS共识算法底层所依赖的一种PVSS机制,https://github.com/AlexiaChen/AlexiaChen.github.io/issues/104 ,我看了原论文,发现比较繁琐复杂,于是就往References中一直往上追溯,发现一篇shamir写的一篇引用超多的论文《How to Share a Secret 》,可以算是鼻祖级别的论文了,而且非常短,短短两页道尽了了PVSS的基本核心机制。于是乎,心中有了点货,打算整理一下,其实都是很多secret sharing的核心。感兴趣可以拜读下这篇论文,下面我就不说过多的故事来过渡,直接步入核心。
假设一个秘密D,我们把秘密分散成N份分片,其中拿到任意至少K份秘密分片,你就可以把秘密D重构出来,这个就把秘密泄露的风险降低了(秘密D你可以理解为一段数据)。反之如果拿到的分片是k - 1份,或者更少,那么秘密D就不可能被重构出来。
这种方式就叫(k,n)门限方案(threshhold scheme)。
这种方式需要有一个前提就是 n >= 2*k - 1
好的,下面重点来了,概念懂了,但是要通过什么数学方式可以描述满足这样的需求呢?论文中给出了一个简单的方法,就是通过多项式插值。
随机给出一个次数为k - 1的多项式:
q(x) = a0*x^0 + a1*x^1 + a2*x^2 + ... + ak - 1 * x^(k - 1)
那么我们可以把秘密D当作一个数字, D就是q(0)的时候,其实也就是刚好是a0的值。那么这时候我们就可以把D打散成N份秘密分片:
D1 = q(1), D2 = q(2), ... , Di = q(i), ..., Dn = q(n)
那么知道其中任意k个秘密分片Di,就可以通过插值法计算出q(0)的值,也就是a0的值。
比如我们设计一个(4,7)的方案,那么就可以随机生成一个次数为3的多项式:
q(x) = a0*x^0 + a1*x^1 + a2*x^2 + a3*x^3
设秘密D的数值为10,那么a0就为10,剩下的a1,a2,a3这些系数随便生成:
q(x) = 10 + 2*x + 3*x^2 + 4*x^3
那么秘密分片D1-D7就是:
D1 = q(1) = 10 + 2 + 3 + 4 = 19 D2 = q(2) = 10 + 4 + 12 + 32 = 58 D3 = q(3) = 10 + 6 + 27 + 108 = 151 D4 = q(4) = 10 + 8 + 48 + 256 = 322 D5 = q(5) = 10 + 10 + 75 + 500 = 595 D6 = q(6) = 10 + 12 + 108 + 864 = 994 D7 = q(7) = 10 + 14 + 147 + 1372 = 1543
当然对于上面的D1-D7可以描述为二维平面上的点:
D1(1, 19) D2(2, 58) D3(3, 151) D4(4, 322) D5(5, 595) D6(6, 994) D7(7, 1543)
好了,下面我们用python的scipy库中的插值来计算下,这里用的是拉格朗日插值算法(用牛顿插值法也是可以的):
#!/usr/bin/env python3 # pip install -i https://mirrors.aliyun.com/pypi/simple/ scipy from scipy.interpolate import lagrange def P(x): return 10 + 2*x + 3*(x**2) + 4*(x**3) print (P(1)) print (P(2)) print (P(3)) print (P(4)) print (P(5)) print (P(6)) print (P(7)) # D1(1, 19) # D2(2, 58) # D3(3, 151) # D4(4, 322) # D5(5, 595) # D6(6, 994) # D7(7, 1543) x=[1,2,3,6] y=[19,58,151,994] a=lagrange(x,y) print(a)
结果:
3 2 4 x + 3 x + 2 x + 10
第二行就是插值出来的函数了,看到了最低次的a0的数值为10,那么我们就把秘密D重构出来了。细心的看代码也看到了,用的是D1,D2,D3,D6这4个秘密分片重构出的秘密D,如果再少一个分片,就重构不出来D了,大家可以试试。如果用D8 - D11这4个秘密分片也可以把D重构出来。因为这个k只跟多项式的次数有关,与n无关。就比如这个多项式q(x)。可以打散成至少n个秘密分片,也就是这个方案可以是(4, 11), (4, 8),因为n的取值与多项式无关,只有k和D的值与多项式相关。但是n >= 2*k - 1。
注意这个多项式q(x)是在实数轴上的,用在密码学里面需要用有限域处理下,也就是多项式q(x)是在有限域下的,当然,也可以插值出来秘密D。一样的。
在密码学里面,有限域素数p的选取是有要求的,在这里,p要比n和D都大,并且多项式系数a1到最高次系数ak-1要在[0,p)之间离散均匀分布,秘密分片D1,D2,..., Dn都是在有限域下计算出来的。
原始论文里面还有一些优化,比如秘密D过大,比如比素数p大,那么需要把D切分成更小的二进制块来避免多精度运算问题,块的数值大小也不是任意小,有点要求,感兴趣具体去看原始论文吧。我们的MPVSS论文底层的思路与这个是一样的,这样以来,我就可以再去细读我们的论文到底做了哪些具体的改进了。
EOF
有关于秘密分片
前言
写这篇文章的缘由是因为之前我提到过我们链的DPoS共识算法底层所依赖的一种PVSS机制,https://github.com/AlexiaChen/AlexiaChen.github.io/issues/104 ,我看了原论文,发现比较繁琐复杂,于是就往References中一直往上追溯,发现一篇shamir写的一篇引用超多的论文《How to Share a Secret 》,可以算是鼻祖级别的论文了,而且非常短,短短两页道尽了了PVSS的基本核心机制。于是乎,心中有了点货,打算整理一下,其实都是很多secret sharing的核心。感兴趣可以拜读下这篇论文,下面我就不说过多的故事来过渡,直接步入核心。
正文
假设一个秘密D,我们把秘密分散成N份分片,其中拿到任意至少K份秘密分片,你就可以把秘密D重构出来,这个就把秘密泄露的风险降低了(秘密D你可以理解为一段数据)。反之如果拿到的分片是k - 1份,或者更少,那么秘密D就不可能被重构出来。
这种方式就叫(k,n)门限方案(threshhold scheme)。
这种方式需要有一个前提就是 n >= 2*k - 1
好的,下面重点来了,概念懂了,但是要通过什么数学方式可以描述满足这样的需求呢?论文中给出了一个简单的方法,就是通过多项式插值。
随机给出一个次数为k - 1的多项式:
那么我们可以把秘密D当作一个数字, D就是q(0)的时候,其实也就是刚好是a0的值。那么这时候我们就可以把D打散成N份秘密分片:
那么知道其中任意k个秘密分片Di,就可以通过插值法计算出q(0)的值,也就是a0的值。
比如我们设计一个(4,7)的方案,那么就可以随机生成一个次数为3的多项式:
设秘密D的数值为10,那么a0就为10,剩下的a1,a2,a3这些系数随便生成:
那么秘密分片D1-D7就是:
D1 = q(1) = 10 + 2 + 3 + 4 = 19 D2 = q(2) = 10 + 4 + 12 + 32 = 58 D3 = q(3) = 10 + 6 + 27 + 108 = 151 D4 = q(4) = 10 + 8 + 48 + 256 = 322 D5 = q(5) = 10 + 10 + 75 + 500 = 595 D6 = q(6) = 10 + 12 + 108 + 864 = 994 D7 = q(7) = 10 + 14 + 147 + 1372 = 1543
当然对于上面的D1-D7可以描述为二维平面上的点:
D1(1, 19) D2(2, 58) D3(3, 151) D4(4, 322) D5(5, 595) D6(6, 994) D7(7, 1543)
好了,下面我们用python的scipy库中的插值来计算下,这里用的是拉格朗日插值算法(用牛顿插值法也是可以的):
结果:
第二行就是插值出来的函数了,看到了最低次的a0的数值为10,那么我们就把秘密D重构出来了。细心的看代码也看到了,用的是D1,D2,D3,D6这4个秘密分片重构出的秘密D,如果再少一个分片,就重构不出来D了,大家可以试试。如果用D8 - D11这4个秘密分片也可以把D重构出来。因为这个k只跟多项式的次数有关,与n无关。就比如这个多项式q(x)。可以打散成至少n个秘密分片,也就是这个方案可以是(4, 11), (4, 8),因为n的取值与多项式无关,只有k和D的值与多项式相关。但是n >= 2*k - 1。
注意这个多项式q(x)是在实数轴上的,用在密码学里面需要用有限域处理下,也就是多项式q(x)是在有限域下的,当然,也可以插值出来秘密D。一样的。
在密码学里面,有限域素数p的选取是有要求的,在这里,p要比n和D都大,并且多项式系数a1到最高次系数ak-1要在[0,p)之间离散均匀分布,秘密分片D1,D2,..., Dn都是在有限域下计算出来的。
结语
原始论文里面还有一些优化,比如秘密D过大,比如比素数p大,那么需要把D切分成更小的二进制块来避免多精度运算问题,块的数值大小也不是任意小,有点要求,感兴趣具体去看原始论文吧。我们的MPVSS论文底层的思路与这个是一样的,这样以来,我就可以再去细读我们的论文到底做了哪些具体的改进了。
EOF