零点课堂 | 自然常数e与Filecoin预期共识有什么关系?(2)

预期共识的实现是一个不断发现的过程

开发网出现的空块率过高的情况,我们做了模拟,并与Filecoin研究开发团队进行了讨论。显然,这么高的空块轮次比例是不好的,这是的区块时间不固定,交易时间预测起来也比较困难。

那么,一个简单的改动是什么呢?那就是增加每一轮的区块预期数量。因为预期共识本来一轮就可能出现多个区块,在实现中采用tipset的方式进行组合,那么增加区块的预期数量,对于设计实现而言非常简单。

在测试网之前,Filecoin实现引入了预期每轮区块数这个概念,这个被定义为 E (ExpectedBlocksPerEpoch)。当前默认:E = 5

既然,预期区块数提高了,最简单的方法就是把每个矿工的出块概率提高5倍。但是,矿工出块的计算采用掷骰子的方式。也就是产生一个 256 位空间中的一个数,来比较自己的算力占比,从而判断是否拥有出块权。这里就有一个数据越界的问题。Filecoin的实现在这个判断上走过三个阶段:

阶段一:每个矿工按照自己的算力再进行切分,分别按照更小的份额进行选举,如果赢得选举就获得一票。相同默认算力都按照每 25 个 sector来进行统一切分(剩余部分单独算)。这个办法的好处是每一个选举人算力都基本一样,进行公平选举。但是,由于每25个sector都要进行单独计算,每一个部分都需要I/O访问,时间消耗较大。Filecoin团队的最初目的是把这个出块权和时空证明放在一起。但是,最后从安全的角度来考虑,由于计算相对复杂,还是放弃了。

阶段二:直接极致简化,不考虑越界的问题,直接乘以5进行比较计算。这个是在时空证明已经通过WindowedPoSt替代 SurprisedPoSt的情况下的一个简化措施。但是,这样做有两个问题:1)对于算力大于 20% 的矿工肯定是吃亏的;2)当矿工算力足够大时,一定能够赢得选举。这第二个问题比较严重。我们慎重提出,这是一个安全问题,应该改。

阶段三:采用密码抽签的方式,借鉴Algorand采用的算法。逐渐走向完善。

让每一个字节都参与投票

Algorand的密码抽签是一个非常好的概率分布在选举上的应用,对于区块链POS网络而言,非常棒。实现起来比较简单直接。其具体算法如下:

这里不做详细解释,需要的人可以查询相关资料。简单地说,就是在POS选举过程中,当你凭借自己产生的可验证随机数进行抽签的时候,可以通过你自己的份额和相应二项式分布来看你落在哪一个区间,从而判断你获得了多少选票。

二项式分布是 n 个相同概率的独立时间单独计算而后相加的一个分布,而且整个分布正好切分整个概率空间。因此只需要看你的可验证随机数在那个空间就可以了(这个部分比较难说清楚,有意者线下探讨)。

那么对于Filecoin而言,参与选举的份额就是你的算力。如果按照前文中说的阶段二的方式,可以再进行细分,那么可以考虑为每一个字节都参与投票。这样一来,参与投票的选举人数量非常大,整个计算不用采用二项式分布,完全可以采用泊松分布来进行计算。泊松分布的计算公式如下:

这里 λ 是自己的份额与预期总选举票数的乘积。在Filecoin中,它就是

E * mPow/totPow;k 是获得选举权的数量。

看一下上式,是不是很神奇?自然常数 e 再一次用到了 Filecoin 的选举的计算之中。采用泊松分布进行计算是 Filecoin 的一个改进,非常符合Filecoin的特点,同时计算也非常简单。

采用密码抽签之后,就不能保证每一轮都一定会有矿工拿到出块权了,这很正常,因为每个人都自己掷骰子,出块权的计算是独立的。这样的话,实际上每一轮赢得不同的出块选票的概率有多大呢?简单做一个模拟可以得出下表:

这里空轮的概率是 e^-5。

也就是说,预期大约不到200个高度就会出现一个空轮。看起来还好。而每轮选票数为 3,4,5,6,7分布较多也比较均匀。选票数高达15张的情况也不少,大概万分之1.6。

看到这里(如果你真的有耐心看到这里),您可能会想,e是不是与概率的关系比较大,其实我可以告诉你,π在有些时候也会用到概率计算之中。因为这两个常数就是有牵扯不清的关系。

Filecoin中自然常数不仅仅用于选举

自然常数 e 在选举之中的使用,至此显得非常自然,而且也比较优雅。

同时,Filecoin在Token释放上,也利用 e 进行计算。这个与概率无关,而是与衰减有关。Filecoin 不采用周期性减半的方式进行Token释放,而是模仿放射性衰减,也就是指数衰减。白皮书设计为6年减半。而一般说来,衰减的公式可以写为:

上式可以理解为:初始Token为 N0,随时间推移,系统通过释放,在 t 时间点系统中还应该保留的Token量N(t)的计算公式。

看这里,再一次出现了自然常数 e。当然这里不一定非要用 e 的。但是由于 e 的使用非常广泛了,用起来方便顺手。所以基本上现在这是一种统一的用法。

本文由 零点财经 作者:tao 发表,其版权均为 零点财经 所有,文章内容系作者个人观点,不代表 零点财经 对观点赞同或支持。如需转载,请注明文章来源。
分享生成图片
33

发表回复

零点课堂 | 自然常数e与Filecoin预期共识有什么关系?(2)

2021-06-28 10:24:40

预期共识的实现是一个不断发现的过程

开发网出现的空块率过高的情况,我们做了模拟,并与Filecoin研究开发团队进行了讨论。显然,这么高的空块轮次比例是不好的,这是的区块时间不固定,交易时间预测起来也比较困难。

那么,一个简单的改动是什么呢?那就是增加每一轮的区块预期数量。因为预期共识本来一轮就可能出现多个区块,在实现中采用tipset的方式进行组合,那么增加区块的预期数量,对于设计实现而言非常简单。

在测试网之前,Filecoin实现引入了预期每轮区块数这个概念,这个被定义为 E (ExpectedBlocksPerEpoch)。当前默认:E = 5

既然,预期区块数提高了,最简单的方法就是把每个矿工的出块概率提高5倍。但是,矿工出块的计算采用掷骰子的方式。也就是产生一个 256 位空间中的一个数,来比较自己的算力占比,从而判断是否拥有出块权。这里就有一个数据越界的问题。Filecoin的实现在这个判断上走过三个阶段:

阶段一:每个矿工按照自己的算力再进行切分,分别按照更小的份额进行选举,如果赢得选举就获得一票。相同默认算力都按照每 25 个 sector来进行统一切分(剩余部分单独算)。这个办法的好处是每一个选举人算力都基本一样,进行公平选举。但是,由于每25个sector都要进行单独计算,每一个部分都需要I/O访问,时间消耗较大。Filecoin团队的最初目的是把这个出块权和时空证明放在一起。但是,最后从安全的角度来考虑,由于计算相对复杂,还是放弃了。

阶段二:直接极致简化,不考虑越界的问题,直接乘以5进行比较计算。这个是在时空证明已经通过WindowedPoSt替代 SurprisedPoSt的情况下的一个简化措施。但是,这样做有两个问题:1)对于算力大于 20% 的矿工肯定是吃亏的;2)当矿工算力足够大时,一定能够赢得选举。这第二个问题比较严重。我们慎重提出,这是一个安全问题,应该改。

阶段三:采用密码抽签的方式,借鉴Algorand采用的算法。逐渐走向完善。

让每一个字节都参与投票

Algorand的密码抽签是一个非常好的概率分布在选举上的应用,对于区块链POS网络而言,非常棒。实现起来比较简单直接。其具体算法如下:

这里不做详细解释,需要的人可以查询相关资料。简单地说,就是在POS选举过程中,当你凭借自己产生的可验证随机数进行抽签的时候,可以通过你自己的份额和相应二项式分布来看你落在哪一个区间,从而判断你获得了多少选票。

二项式分布是 n 个相同概率的独立时间单独计算而后相加的一个分布,而且整个分布正好切分整个概率空间。因此只需要看你的可验证随机数在那个空间就可以了(这个部分比较难说清楚,有意者线下探讨)。

那么对于Filecoin而言,参与选举的份额就是你的算力。如果按照前文中说的阶段二的方式,可以再进行细分,那么可以考虑为每一个字节都参与投票。这样一来,参与投票的选举人数量非常大,整个计算不用采用二项式分布,完全可以采用泊松分布来进行计算。泊松分布的计算公式如下:

这里 λ 是自己的份额与预期总选举票数的乘积。在Filecoin中,它就是

E * mPow/totPow;k 是获得选举权的数量。

看一下上式,是不是很神奇?自然常数 e 再一次用到了 Filecoin 的选举的计算之中。采用泊松分布进行计算是 Filecoin 的一个改进,非常符合Filecoin的特点,同时计算也非常简单。

采用密码抽签之后,就不能保证每一轮都一定会有矿工拿到出块权了,这很正常,因为每个人都自己掷骰子,出块权的计算是独立的。这样的话,实际上每一轮赢得不同的出块选票的概率有多大呢?简单做一个模拟可以得出下表:

这里空轮的概率是 e^-5。

也就是说,预期大约不到200个高度就会出现一个空轮。看起来还好。而每轮选票数为 3,4,5,6,7分布较多也比较均匀。选票数高达15张的情况也不少,大概万分之1.6。

看到这里(如果你真的有耐心看到这里),您可能会想,e是不是与概率的关系比较大,其实我可以告诉你,π在有些时候也会用到概率计算之中。因为这两个常数就是有牵扯不清的关系。

Filecoin中自然常数不仅仅用于选举

自然常数 e 在选举之中的使用,至此显得非常自然,而且也比较优雅。

同时,Filecoin在Token释放上,也利用 e 进行计算。这个与概率无关,而是与衰减有关。Filecoin 不采用周期性减半的方式进行Token释放,而是模仿放射性衰减,也就是指数衰减。白皮书设计为6年减半。而一般说来,衰减的公式可以写为:

上式可以理解为:初始Token为 N0,随时间推移,系统通过释放,在 t 时间点系统中还应该保留的Token量N(t)的计算公式。

看这里,再一次出现了自然常数 e。当然这里不一定非要用 e 的。但是由于 e 的使用非常广泛了,用起来方便顺手。所以基本上现在这是一种统一的用法。