POE 利用区块链挖掘协同执行遗传算法

论文地址
Proof of Evolution: leveraging blockchain mining for a cooperative execution of Genetic Algorithms

带着问题去阅读：

• 什么是进化证明？
• 进化证明有什么优点，从哪些角度去证明该方法的正确性？
• 进化证明有什么缺点，哪些原因被限制住了，有什么方法能解决这些问题？
• 未来的方向

使用部分挖矿组件来执行一些客户可以提交的遗传算法（GA）
PoE实现了矿工之间的一种合作心思。在采矿过程中，矿工必须维护和发展候选解决方案的群体，PoE为他们提供了分享他们当前发现的最佳解决方案的可能性，他们可以将这些解决方案添加到他们的群体中。
PoW的优势，只要诚实的节点集体控制的计算能力超过任何合作的攻击者节点群，该系统就可以被认为是安全的。这种说法建立在矿工必须解决散列难题的属性，以实例化一个区块。
上述属性包括：

• 问题的内在硬度
• 容易解决的公共可验证性
• 所有问题的同质硬度
• 难度可调整性
• 区块敏感性
• 不可重复使用性
• 计算的独立同分布性

PoW的缺点:为了保持区块链运行引起的巨大消耗。

• PoE能在采矿时执行优化问题，并且包含了PoW的所有属性，它通过在采矿过程中消耗的部分计算能力来执行GA，使矿工之间进行合作，提高GA的解决方案的质量。
• 提供来一个关于工作在采矿计算总量中的百分比估计，实验结果表明使用PoE达成的解决方案质量优于用PoS达成的结果。

 - nonce("sol","eval","cmp") 
 - sol：使用中的GA的可能解决方案 
 - eval：精确性
 - cmp：衡量所使用的精确性函数的复杂性 nonce的结构

在 PoE 的 nonce 第三个值与作业的解决方案及其评估一起要求。
每个基本操作都有自己的去权重，而且这些权重不是固定，会被一个伪随机变量所改变，这个偏移量由前一个区块的哈希值和矿工的公钥决定。

矿工应该能够分享他们的解决方案，使其他们无法窃取他们。 在PoS中, 这个问题是可以避免的，因为只有宣布最佳解决方案的矿工才会在比赛结束时公布其解决方案。
PoE中，矿工想分享他们当前的最佳解决方案：

• 检查他们的解决方案所属的工作是否开放
• 检查他们的解决方案是否优于已知的最佳解决方案
• 在交易中提交解决方案时，ID以及通过评估器获得的解决方案的分数连接哈希值
• 等到当前区块被开采出来，这样他们之前的交易就被确认了
• 其他矿工可以将解决方案添加到他们的本地群里中，并使用它进行交叉，如果他们发现了更好的解决方案

PoE有三种不同的独立奖励：

• 对发现有效nonce的第一个矿工的奖励
• 对客户提交的GA最佳解决方案的矿工的奖励
• 以及对激励矿工合作的奖励

挖矿的奖励由系统分配能够像PoW那样实例化一个区块的第一个矿工。
最佳解决方案的奖励是由提交相应GA的客户支付的，就像在PoS中。这样一来，客户就没有兴趣提交一个他已经知道最佳解决方案的作业，无法作弊。
为了建立一个真正的合作系统，应该刺激矿工分享个人解决方案。因此只要他们的解决方案对其他人有用，他们就应该得到一点奖励。这种奖励不能由系统产生，否则客户可能会赚取欺骗的钱。所以这种奖励也必须由客户支付。系统应该制定一些标准来说明一个解决方案是否“有用”，以确定何时必须向矿工付款。

这个模型中并不鼓励客户为自己的工作提交解决方案，特别是提交他已经知道的好解决方案的工作，因为他必须为使用这个系统付费。
这个恶意的客户端可以建立一个假的评估器，它为他所知道的特定输入返回最大的分数，而为输入中的每一个其他值返回常规的分数。如果矿工在区块链中分享他们的解决方案，客户端可以阅读它们，在比赛结束时，他将成为拥有假的最佳解决方案的赢家，获得他支付的奖金。因此，他将从其他人那里读到一些好的解决方案，而不支付他们。为了防止这种不良行为，PoE要求对有用的共享解决方案也要付费，而且这种付费必须由客户来执行。如果一个客户提交了一个假的最佳解决方案，没有其他的解决方案会更好，因此，从那一刻起，没有更好的解决方案会被公布。

拒绝服务攻击，阻止工作的执行或支付。一种方法是为候选解决方案提交一个虚假的高评价。这种攻击可以被检测到与评估者检查解决方案。执行攻击的节点可以被禁止进入网络，最佳解决方案的选择可以重新开始。
PoW的另一个可能的问题是由挖矿的竞争性质引起的，它促使矿工购买应用规格集成电路形式的定制硬件。这种硬件比一般的硬件更有效，因此更容易使用。

作者将POE和POW以及POS进行了比较。
考虑到给定作业的评估者的复杂性，散列问题的硬度也相应进行了调整。POS(Proof of Search)被设计为使用与POW相同数量级的能量。POE也进行了相应的调整，使其消耗相同数量级的能量。POE与POW最大的不同在于，其在运行时会解决相应的优化问题。
挖矿任务的难易程度是由哈希字符串开头所需的零数来决定。在此我们假设哈希值是以十六进制字符串的形势存储在区块中，给定一个硬度k，随机nonce的有效概率为p=16^(-k).
挖矿有很多不走，矿工在其中生成一个新的nonce并检查其哈希值，知道一个有效的nonce被发现。最终操作量是由所有矿工进行尝试的次数乘以每一次尝试所需操作次数得到。
假设一个POW挖矿任务需要一个硬度k，则称之为：

• 可以调整PoE对一个作业说要求采矿任务的硬度，以便需要与PoW相等的总操作量。
• 如果PoE为一个特定的工作选择的硬度是k-1, 那么在每个采矿点花费的93%的操作尝试是有益的工作。
• 如果PoE为某一特定工作选择的硬度为k-2或者更小，则99%的操作都是有用的。

提出的定理：

将一项工作在POE中的硬度与它的复杂性联系起来。

POE中挖矿任务的硬度y可以通过计算y=k-log16((w+x)/w) w是制作区块哈希的计算要求，k是POW的目标硬度。
如果我们有y=k-1,更与上面的公式我们可以算出x~w(16^1 - 1)=15w。因为在每次采矿中尝试所进行的计算都是w+x=w+15w=16w,每次尝试的有用功百分比为x/(w+x)=15/16~93%

1. IV.1 设k是POW中挖矿任务的硬度，y是POE为使用挖矿过程与POW在总量上一致而应该设置的硬度。设w为POW在每次尝试执行散列和检查时花费的操作量，设x为POE在每次尝试通过评估工作的候选解决方案生成新的nonce时花费的额外操作量。
   于是有了下面两条近似结果：
   

2. 在证明IV.1之前，我们还需要证明 IV.2,设Pk为硬度k的采矿过程中哈希有效的概率，a是一个期望的阈值。矿工应该进行多少次尝试N，使得有K>=a的概率发现。一个有效的nonce是
   

以最简单的方式表达就是：给定一个复杂度为x的工作，有可能找到一个使数量相等的硬度y，反之，给定一个硬度y,有可能得到工作必须具有复杂度x,以使得数量相等。

POE相比较于POS(搜索证明)的优势在于：它可以通过促成矿工之间合作来提高最终解决方案的质量。
通过在两种模式(标准和合作)下执行一套GA，在一组用不同种子初始化的矿工身上执行固定代数。
在这些测试中，一共考虑了4个GAs实现的实例：

• TSP problems (最小化问题)
• Knapsack problems (最大化问题)
• Locolmotion problem (一个调用外部程序的复杂fitness任务)
• Symbolic Regression problem(使用GP编程)
  

最终实验结果表明，合作可以提高GA的最佳解决方案的精确性。

如果如果这篇文章对你有所帮助～
欢迎关注我的公众号夏虫不可语冰也
同时也欢迎访问我的个人网站 www.cjl946.com
未来将会出更多区块链相关论文解析哦！