基于Shamir Secret Sharing的各种改进

[AlexiaChen]

基于Shamir Secret Sharing的各种改进

其实Secret Sharing方案出来后，就之后有两篇论文对其作出了改进，也就是后来的Verifiable Secret Sharing(VSS)，然后再到Publicly Verifiable Secret Sharing(PVSS)。

VSS的原始论文是《Verifiable Secret Sharig and achieving simultaneity in the Presence of Faults》 PVSS的原始论文是《Publicly Verifiable Secret Sharing》

PVSS的论文对VSS和Secret Sharing都做了简要介绍，并介绍了PVSS的非形式化描述。下面我们就对论文的具体的方法进行分析。看看这三篇论文是怎样一脉相承的，到最后我们再回过头看看MPVSS，也就是我们DPoS共识算法所基于的那篇论文。

Secret Sharing回顾

Secret Sharing的基本方法我之前已经写过了，就是基于多项式的插值来恢复秘密，详情在这里 https://github.com/AlexiaChen/AlexiaChen.github.io/issues/114

可验证的秘密分片(VSS)

因为Shamir给出的方案是随机选择一个k - 1次的多项式P(x), 任意k个分片都可以重构0次项的秘密，这种方案只是信息理论角度的安全，因为 小于k的分片数量就不可能泄露秘密。然而，这个有个前提就是，发牌者(dealer，也就是生成随机多项式的节点)是无错的，并且要在私有信道里分发(Distribute)秘密分片，因为这些分片没有被加密，所以在公网上不可以公布这些秘密分片，当然也可以对秘密分片做加密，但是安全性也依赖了加密函数了。所以原来的SS方案并没有考虑公有分布式网络这些安全性，而VSS方案就添加了安全原语(Verifiable)。

具体情况是这样的，按照原方案，假设dealer是非诚实的节点，对于它公布的其中任意一个分片bi，那么找不到一个方法来验证这个秘密分片bi对于秘密s是合法的，也就是不知道这个分片bi是不是打散秘密s的那个多项式P(x)上的点，因为多项式是不会公布出来的。再说一句白话，就是你只要收到一个分片是非法的，那么重构出来的秘密也是假的。那就无法分辨秘密，秘密也无从谈起。

所以，Shamir给出的基本方案在具有容错的分布式网络环境下是难以被使用的，所以才提出了VSS方案。VSS就是让参与者确信dealer分发的秘密分片bi是否可以重构出秘密s，带有了安全校验的功能。

VSS的具体SS方案不是多项式插值的方式，是基于概率的，详情可以看论文，这里截个图:

公开的可验证秘密分片(PVSS)

PVSS的重点就是Publicly，意思就是不仅仅是参与者能验证秘密分片，而且在网络上的每个节点都能验证分片。

之前提到过，SS方案中在分布式容错网络下，不能防止参与者和dealer作弊，但是在VSS下解决了，VSS中有个交互式的算法Verify，它允许所有的参与者都能互相校验它们之间的秘密分片是否合法，这就要求，参与者之间有交互。还有非交互式的Verify函数，那就叫非交互式VSS方案。

但是如果是非交互式VSS方案，问题也来了，就是参与者只能校验自己收到(拥有)的秘密分片是否合法，它自己不知道其他参与者收到的分片是否合法，再进一步就是它不知道它们这群参与者是否可以恢复出原始秘密。这就需要分片是公共可校验的，PVSS就这样诞生了。

因为在论文里面提到了两种PVSS方案，先说第一种PVSS。有个公共的加密函数Ei被分配到对应的参与者上Pi， 也就是每个参与者都有自己对应的解密函数Di，dealer现在根据各个参与者公开的函数来加密分片并在网络上公布分片:

Si = Ei(si),  i = 1,2,...,n

Si就是si分片被加密后的分片。si自然就是秘密s被打散后的分片了，Si就是要被在网络上分发公布的。

为了校验所有加密后的分片的合法性，就有一个PubVerify的函数算法，该函数以加密后的分片作为集合输入，然后判断是否合法，如果该Si集合的分片都合法，那么就可以再通过Di解密出对应的Si，在进行秘密恢复。但这里的PubVerify函数要被参与者执行，参与者可能要与dealer有交互（与其他参与者没有交互），那么这就称为交互式PVSS，如果不与之交互，就叫非交互式PVSS。

该论文提出的两种PVSS方案都基于ElGamal公钥加密体系。

这两种PVSS方案分别是PVSS for Sharing Discrete Logarithms和PVSS for Sharing e-th Roots。

具体算法有点长，就不细说了，详情可以看论文，这与最原始的SS方案比较，分片也不是基于多项式拆分的。

一种简单的公开的可验证秘密分片(MPVSS)的构造方法

这小节可能打算长一点，因为毕竟MPVSS是我们DPoS的基础。

原始论文的名字在之前的文章中说过，《A Simple Publicly Verifiable Secret SharingScheme and its Application to Electronic Voting》所以简称MPVSS，但是这个简称不是业内共识，估计说这个简称也没人知道。所以要特别注意一下。

这篇论文提出了一个简单的PVSS方案，运行时间是O(k*n)， n就是参与者数量了，k就是至少k个参与者可以恢复秘密了。 论文中，它把Secret Sharing细化为两部分协议(阶段)：分发阶段(Distribution Protocol)和重构阶段(Reconstruction Protocol)。如果明白我前面讲述的原理，那么就知道这两阶段做的内容了。

此外,MPVSS认为原始的PVSS方案太复杂了，不简单，e-th roots依赖于RAS assumption和DH assumption，这些理论难以驾驭，比较复杂，比如double discrete logarithm。而这个MPVSS从设计上就可以让其在任意素数阶的群（离散对数困难的）上工作，而且其安全性只依赖standard Diffie-Hellman assumption和自己的一些决策性变量，这样依赖这种简单的PVSS方案比原始基于ElGamal公钥体系的PVSS要更安全。本论文不仅提出了MPVSS，还基于MPVSS构造了一个选举投票的系统, 这个电子投票系统比《Multi-Authority Secret Ballot Elections with linear work》，《 A secure and optimallyefficient multi-authority election scheme》所提到的投票选举方案还要强大。

非交互式PVSS的模型

首先有个前提就是，PVSS一个特有的特性就是dealer和参与者之间不是私有信道上交互的，而是用公钥加密在公有的信道上通信交互的。dealer将秘密打散成n个分片，分发给n个参与者。然后选取一个k，k满足 1 <= k <= n， k就是多少个分片能重构出秘密的参数。

好了，有了这几个前提，这里的MPVSS还考虑了以下协议:

1. 初始化协议(Initialization Protocol)

几乎所有的系统参数都是初始化阶段产生的，而且这个阶段dealer和参与者之间，参与者与参与者之间不会有任何交互，参与者可以动态进入或离开这个系统，唯一的要求就是每个参与者必须配置属于自己的一把公钥(public key)。

然后每个参与者Pi有自己对应的一个公钥加密函数Ei，这个Ei是用自己对应的那把公钥进行加密的。实际的参与者数量必须是注册的参与者数量的子集，什么是注册的参与者？就是有自己的公钥就算已注册了，但是注册好，可能离线了，实际参与者就是在线的参与者。这里假设P1到Pn参与者就是实际参与者。

2. 分发协议(Distribution Protocol)

分发阶段分为两个步骤：

• 秘密分片分发

设秘密为s，发牌者dealer为D，D首先为各个参与者Pi，生成对应的秘密分片si，也就是各个参与者都有属于自己的一个分片，参与者有n个，那个就生成n个分片，然后这个n个分片，dealer就用各自参与者Pi对应的公钥加密以后并公布出去，加密后的分片是Ei(si)，显然，各个参与者对应的公钥，dealer是知道的，所以当然能用其公钥加密分片。另外，dealer要公布一项证明Proof(d)，该证明表示每个Ei函数加密了对应的分片si。换句话说，该证明表示了dealer与原始秘密s的证明，证明dealer确实知道秘密s，这就保证了重构阶段得到，恢复的秘密s是与证明中的秘密s的值是一致的。

• 秘密分片校验

网络上的任意一方(不一定是参与者)，只要知道参与者注册的公钥，那么就可以校验其对应的分片。对于每个参与者Pi都会运行一个非交互式算法, 该算法根据Proof(d)来校验Ei(si)属于自己的加密分片是否正确。因为任何人都可以校验每个参与者的秘密分片是否合法，这样就可以排除某个参与者受到正确的秘密分片还耍赖的情形。如果其中一个分片校验失败，就可以认为是dealer失败了，然后Distribution Protocol这个阶段的协议终止。

当然这里可以做容错，可以考虑(k, n - c)门限方案，c就是允许失败的分片数量

3. 重构协议(Reconstruction Protocol)

重构阶段也是分为两个步骤:

• 秘密分片解密

因为在分发阶段，校验是校验加密后的分片，现在需要到重构出秘密了，所以先要对加密后的分片解密。所有参与者要对其属于自己的分片Ei(si)解密，当然，因为是(k,n)门限方案，所以不需要所有参与者都对自己的分片解密成功，解密成功的参与者会生成一份解密的证明Proof(Pi), 表明Pi解密后的分片是正确的。

• 秘密分片收集

解密后的证明Proof(Pi)主要是为了剔除那些失败和不诚实(作弊)的参与者，剩下的就是收集这些解密后的分片对秘密s进行重构了，只要k个分片就可以重构出来了。

这里就是整套MPVSS主体流程了，对于之前的PVSS方案，这里在重构协议多出了一条要求就是参与者们必须提供与之对应的分片解密证明来表明自己是诚实的，这些证明是非交互式的，也就是网络上任意一方都能够收集整理这些秘密分片。

MPVSS的具体构造

设Gq是一个以素数q为阶数的素阶群，设g，G都表示Gq上的两个不同独立的生成元，因此没有任何人知道g关于G的离散对数，然后核心就是在这个Gq群上共享一个随机值。dealer所做的就是在选择一个在有限域Fq上的值s，以这个值s计算出秘密S，S = G^s。

既然上面设定为素阶群了，那么这个群必然是一个循环群，满足这种代数结构的有很多，椭圆曲线的有限循环群就满足这个，所以，这个群的实现完全可以用椭圆曲线来做，我们的工程里用的是Ed25519的爱德华曲线，也是满足这个性质的。

好了，上面说了循环群，主要是为了引出可以用有限域下的椭圆曲线来做。

1. 初始化阶段

群Gq，生成元g，G可以选择恰当合适的大家公认的结构，比如椭圆曲线。然后各个参与者Pi，在有限域Fq下生成一个私钥xi，然后用私钥xi生成对应的公钥yi，yi = G^xi， 用公钥yi注册，使其成为共识网络上的一员。

2. 分发阶段

• 分片的分发

设参与者有n个，为P1到Pn， 然后该门限方案为(t, n)方案

dealer随机选取一个最高次数为t - 1的多项式p(x), p(x)是在有限域Fq下的。

设秘密s = a0 = p(0), 也就是秘密是多项式p(x)的0次方项的系数。 dealer继续保留这个秘密s，并发布多项式p(x)上各项系数的承诺:

因为要把秘密s，打散成多项式上的分片，所以p(i)就为秘密分片，并且秘密分片都需要经过参与者对应的公钥进行加密，加密得到的分片为Yi:

最后，当第i个参与者，收到秘密分片p(i)时，且 1 <= i <= n, 作如下验证:

这样其实就是给各个加密后的秘密分片生成了一个唯一的属于分片自己的知识证明，当然以上公式的Xi和Yi是如下定义（Yi已经作出解释了）：

当然，这个非交互式的知识证明是n个参与者的秘密分片证明的叠加组合，每个加密分片的知识证明我们描述为如下的一个DLEQ函数:

DLEQ的具体实现如下, 其实就是Chaum and Pedersen Scheme:

这个DLEQ应用在Shamir Secret Sharing方案上就是，DLEQ中的挑战c，就是Xi,Yi,a1i, a2i的密码学Hash值，证明就是一个公共挑战c和n个回应(responses) ri的组合。

• 分片的校验

校验者首先根据各个系数承诺校验Xi:

然后将Xi,Yi,yi, ri 和挑战c作为输入计算出a1i, a2i：

最后比对挑战c的值与Xi,Yi,a1i, a2i的密码学Hash值是否相等，相当就校验成功，实现了Verifiable的安全原语。

3. 重构阶段

重构阶段也分两个步骤，一个同态性质的解密和通过拉格朗日插值计算，我就不讲解论文了，基本上很好懂了

• 对加密后的分片进行解密

• 收集秘密分片

看完以上重构阶段的同学，可能会比较奇怪了，哎呀，加密后的秘密分片不是Yi = yi ^ p(i)吗？秘密分片本身是p(i)，怎么我解密的时候只计算出Si 就可以了，Si是G^p(i)啊，并不是p(i)本身，没有解密成功啊？怎么回事呢？还有就是，为什么原始秘密s，通过拉格朗日插值重构出来的秘密基于G^p(i)重构出来的秘密是S = G^s,也不是原始秘密s。这一切的一切是怎么回事啊？

首先是这样的，根据DLEQ可以提供Si就是Yi对应的正确的解密证明，所以参与者根本不需要知道原始的秘密分片p(i)，只需要知道Si就可以了，重构出来的秘密S = G^s ，即使秘密不一样，但是本质是没有区别的，因为是同态的。也就是满足以下性质:

• G^p(1) + G^p(2) + .. + G^p(n) = G^(p(1) + p(2) + ... p(n))
• S = G^s

那么根据以上公式就可以看出来了，G点是大家都知道的，反向计算虽然计算不出来，但是既然是同态性质，那么知不知道p(i)无所谓了，这样有个好处就是参与者不需要暴露自己的私钥，反正都可以重构出秘密，都可以通过拉格朗日插值出来，虽然秘密不一样，但是秘密S却是原始秘密s的一个“镜像”，只不过原始秘密s经过同态这样的性质隐藏起来而已，也就是我可以在利用以G^p(i)加密后的秘密，做计算，然后计算的结果，dealer就可以根据原始秘密s计算出S，所以本质都是一样的。论文也有解释说明:

举个同态的小白例子就是，一个DNA基因公司它不希望自己的DNA基因数据泄露，但又想把基因数据拿给第三方机构计算一些结果，就可以经过同态来办到，基因公司把自己的基因数据经过同态加密后，第三方计算机构在加密数据上进行运算，得到了结果，把这个结果返回给基因公司，基因公司可以解密结果得到一个原始计算结果。这个原始计算结果与自己未加密的原始数据计算出来结果是一致的。当然了，这个是理想状态了，实际真有落地应用吗？因为太复杂了，现实世界是不规整的。

MPVSS如何用在分布式共识当中

先来说不考虑拜占庭的情况下，共识协议无非就是让多个参与者节点在某一时刻对某个值达成一致，也就是大家一致认可这个值，我管你是不是经过民主还是非民主的方式做的，只要是大家一致认可就行了，这个值可以代表并“编码”为一个leader节点，也可以表示其他某件事。所以共识就是某个值某个时刻达成一致的共识，这个是基本点。拜占庭情况下的共识也是一样的，但是要考虑作弊，恶意参与者节点，所以需要引入点密码学的工具而已。

下面来考虑怎样基于MPVSS这个方案来做一个共识方案，也就是所有参与者节点，计算结果（值）一致，这个结果值无法预测。

假设有A,B,C三个参与者节点，我们要选一个参与者节点成为leader节点，这个leader节点就是参与者们一致认可的，这个leader节点在区块链中就是出块节点，在分布式数据库领域叫主节点，所有follower节点会对leader节点的数据做多副本一致性。

三个参与者都确定了，然后就可以做(2,3)的MPVSS门限方案了，各个参与者随机生成自己的多项式，然后根据多项式生成自己的秘密a， 把秘密打散成分片公布出去，然后不出意外，其他两个参与者都会收到分片，这样就可以重构出对应参与者的秘密， 也就是到最后，每个参与者都拿到其他两个参与者的秘密了，加上自己的秘密，那么就是三个秘密a，b，c，那么就可以对这3个秘密加起来，得到一个一致的值，这个一致的结果都是参与者自己节点内部计算出来，当然还可以把这个值做下Hash，然后对Hash后的值取 mod 3，映射到一个节点地址数组的下标，这样最终会映射到一个节点地址上去，由那个地址的节点出块。比如:

std::vector<std::string> participantNodeList = ["Node A address", "Node B address", "Node C address"];
uint32_t result = pConsensus->GetConsensusResult();
std::string selfAddress = GetSelfAddress();
if(selfAddress == vecNode[result % participantNodeList .size()])
{
     // I'm the leader in this group of participant and doing what the leader need
}

当然，以上这个参与者列表可以根据网络投票选举而变化，进行动态增删，都是可以的。