原文来自IOHK Olga Hryniuk，由卡尔达诺大使陈哲Anson翻译
IOG 研究引入了一种新的、可证明安全的共识协议，以最大程度地减少工作量证明区块链的能源浪费
工作量证明 (PoW) 能源成本和碳足迹的最小化是加密领域最热门的话题之一。长期以来，用有用工作量证明 (PoUW) 代替 Nakamoto 最长链协议中的 PoW 原语在许多方面都被认为是一种理想的解决方案，但时至今日，这一概念仍缺乏令人信服的安全实现。
今天，在领先的国际密码学会议-Crypto-上，Input Output Global, Inc (IOG) 介绍了 Ofelimos，这是一种基于 PoUW 的新型区块链协议，其共识机制同时实现了去中心化的优化问题求解器。共识机制利用工作来解决实际的计算问题来维护区块链。
工作量证明与有用工作量证明
基于 PoW 的区块链协议利用协议参与者（称为矿工）执行的工作。 PoW 通过鼓励矿工竞争解决计算问题以获得生产新区块的资格来确保账本的安全性。这种计算工作维护了协议的安全性，但需要大量的电力和资源使用。在撰写本文时，比特币的年度能源支出与许多中小型国家相当。
有用工作量证明通过重新利用维护协议安全所需的计算工作来解决能源效率问题，以解决复杂的现实世界问题，例如优化公司物流或事件调度。
PoUW 的挑战之一是解决以下困境：如果要解决的问题确实有用（来自现实世界），攻击者可能会指示系统提出易于解决（或已经被攻击者解决）的问题实例.这将利用攻击者的资源比具有相同资源量的诚实参与者产生更多的块，从而降低区块链的安全性。另一方面，最小化攻击者利用其区块生产的能力可能需要提出随机问题实例，从而使系统的计算在实践中无用。
Ofelimos 通过正式的安全性和有用性分析解决了这个难题。
Ofelimos 概述
客户发布要解决的问题和要支付给成功矿工的奖励。就像在 PoW 中一样，矿工解决这些问题以参与决定是否有资格创建区块的抽奖活动。
在纯 PoW 中，这种抽奖通常包括针对给定目标值重复地对挑战（连同计数器）进行散列。如果哈希值低于目标值，则中奖。请注意，在纯 PoW 中，单个查询很快，而到达目标的概率非常小。
出于多种原因，在 PoUW 中，还建议保持单个查询（相对）快速，例如，这可以最大限度地减少同时发布多个块的可能性。另一方面，客户端问题的实例应该是非平凡的，因此外包计算是有吸引力的。对于 PoUW，因此很自然地针对整体上复杂但又可分为小的“统一”步骤的计算类别。每个步骤都应该需要相同的工作量（在预期中），并且对应于纯 PoW 的单个查询。
随机局部搜索 (SLS) 是此类计算的明显类别。 SLS 算法适用于没有已知有效确定性算法的优化问题。相反，SLS 在解决方案空间中执行随机游走，尝试使用某些启发式方法逐步优化解决方案。由于随机游走中的每个探索步骤都是同一计算的不同实例，因此根据上述要求，SLS 是 PoUW 的绝佳候选者。此外，SLS 与物流规划、事件调度等领域的实体经济应用具有高度的实际相关性。
从 PoW 到 PoUW 的逐步转换
矿工拾取并解决发布在区块链上的客户问题实例。问题更新不断地存储在区块链中，直到某些终止标准出现，例如，在固定数量的探索步骤之后，或者如果找到了合适的解决方案。
我们现在重构如何在这种情况下将纯 PoW 转换为 PoUW。
在纯粹的 PoW 中，矿工必须通过一个新区块来扩展他们最长的链，并针对给定目标重复地对新区块进行散列（通过改变区块中包含的计数器）。作为第一步，我们用重复计算的 SLS 探索步骤 M 代替重复散列或存储在链上的探索状态，其中块确定探索步骤的随机种子。参见图 1（右侧）：先前的探索状态 s 通过随机探索步骤 M 扩展，使用将块与状态 s 一起散列得到的种子，产生新的（可能更好的）探索状态 s’。重复此过程，直到满足尚未指定的条件“？”，允许矿工发布块。在此过程中，矿工跟踪在此重复过程中找到的最佳状态 sbest。
图 1：针对目标 T（PoW，左）的散列。重复探索步骤 M（PoUW，右）。
我们现在修复缺少的成功条件“？”。为了获得不受具体计算偏差的良好随机属性，通过在探索步骤之后将“后散列”附加到探索步骤（重用初始种子）——参见图 2——如果这个哈希值低于某个目标 T3，则该块有资格发布。除了目前最好的解决方案 sbest 之外，这还引入了一个必须与块一起发布的新状态 sT，该状态导致哈希值低于 T3——以证明有资格发布块。请注意，只有 sbest 用作状态更新（由矿工进一步探索），而 sT 仅用作发布区块资格的见证人。
图 2：随机发布区块的资格
考虑到 M 比 H 更难计算，并且并非所有 M 实例可能需要相同数量的工作，与诚实的矿工相比，攻击者可能会寻找种子，使他们能够加快 M 计算，从而获得更快地生成块并降低系统安全性的优势。我们通过要求初始哈希值低于目标 T1 来减轻这种磨削。例如，在执行探索步骤 M 之前，矿工必须通过沿着纯 PoW 的路线改变块计数器来找到一个低哈希值。参见图 3。具体而言，选择 T1 使得找到低于目标 T1 的哈希值的预期工作成本至少与计算 M 的最坏情况时间复杂度一样多——强制执行简单实例的磨削与计算成本一样高M 的“不方便”实例。满足上述条件的三元组 (Bctr, sbest, sT) 因此构成 PoUW。
图 3：通过针对目标 T1 的预散列来防御磨削
与纯 PoW 相比，我们不能让节点通过重复矿工的 M 计算来验证 PoUW，因为这将意味着大量的复制计算，从而大大减少了系统中真正有用的计算部分。为了避免这种情况，在“找到”一个可发布的块时，矿工需要创建一个简洁的非交互式参数（SNARG）来证明这种成功——其好处是验证复杂性变得独立于计算 M 的复杂性。此外，证明了最佳解 sbest 的正确计算。参见图 4。
图 4：通过添加非交互式证明来最小化分布式验证
为了利用分布式并发挖掘，SLS 实例是并行化的（例如，通过维护多个探索路径），否则，所有矿工将同时探索相同的状态，从而引入大量（本质上）冗余探索步骤。请注意，出于安全原因，标准“Nakamoto”PoW 中的块生成速度很慢，并且状态更新与块相关联。另一方面，状态更新应该快速进行，以避免矿工探索“过时”的状态。因此，我们引入了两种类型的块，具有与 Nakamoto 共识相同功能的“难以找到”排名块，以及功能类似于最终被排名块引用的交易的“容易找到”输入块。这样，可以相对快速地传播矿工的最佳解决方案，从而使所有矿工保持最新状态。具体而言，这是通过首先针对“简单”目标 T3 评估最终哈希来实现的。如果它低于，则它有资格作为可发布块，但只有当目标低于“更难”目标 T2 时，该块才有资格作为“共识相关”排名块 - 否则它被定义为输入块。请参见图 5。
图 5：低于 T2 的 post-hash 将该块限定为排名块。 T2 和 T3 之间的后散列将块限定为输入块
协议属性
对协议进行彻底的安全性和有用性分析超出了本文的范围。我们重申为什么协议是安全的，然后通过检查协议效率得出结论可能仍然有用。
区块链安全：
磨削：对手对易于计算的 M 实例进行磨削没有优势。这是通过调整预散列阈值 T1 来实现的，这样在任何实例上计算 M 最多与在下面找到新的预散列一样困难T1（预期中）。
**对抗敌手优势：**敌手在计算 PoUW 的速度比诚实方更快的优势是有限的。这是通过将块成功与实际计算解耦，并通过在目标 T1 以下进行预散列来实现的。特别是，遵循 [GKL14, PSS16] 中的标准模型，并假设对手在计算 M 方面没有比诚实方更快的优势，该协议允许对手控制任何少数专用于网络的计算能力——就像比特币一样。相比之下，即使攻击者应该能够在每个实例上免费计算 M，该协议仍然允许攻击者控制多达三分之一的计算资源——因为它们仍然会以“一半”的成本运行，因为预- 对 T1 进行散列。
**可变难度：**在 PoW/PoUW 共识协议中，寻找区块的难度必须不断适应当前系统专用的计算能力水平。在 Ofelimos 中，这很容易通过将目标 T2 调整为在探索步骤之后执行的（单个）后散列 - 这有资格发布排名块。
效率：
频繁更新：排名块和输入块之间的分离确保了状态更新的快速传播。
有用性：通过有用性，我们定义了用于 SLS 问题的整体计算工作的比率（这是一种简化——可以在本文中找到更仔细的定义和分析）。系统中“无用”工作的主要来源是针对 T1 的重复预散列以及 SNARG 的计算。注意：
-
每次调用 M 时仅执行一次后散列，并且与 M 的复杂性相比，出于实际原因可以忽略。
-
SNARG 只需针对许多 M 调用中的两个计算，即产生 sT（暗示块成功）和 sbest（最佳解决方案）的一个。因此，可以通过降低确定块成功的阈值 T3 来最小化 SNARG 计算引起的开销——以权衡较慢的状态更新。
有用性取决于 M 的特性。如果 M 的运行时间足够集中，则可以将 pre-hash 硬度设置为接近 M 的平均情况复杂度。考虑到上述观察，大约 1/2 的有用性可实现为矿工花费大约一半的时间来计算 M。许多经典的 SLS 问题似乎都属于这一类。但是，如果 M 不是“表现良好”，则有用性可能接近于零。因此，具体 SLS 算法及其探索步骤 M 的选择对于实现具有合理有用性的 PoUW 至关重要。
结论
Ofelimos 只是迈向可证明安全和有用的 PoUW 的第一步。尽管目前的工作很容易为高腐败水平提供可证明的安全性，但仍然需要在算法方面进行更多的研究，以提供可以证明其高度有用性的合适类别的优化问题。
“Ofelimos：通过有用工作量证明进行组合优化”研究论文于 2021 年 10 月首次发表。
我要感谢 Matthias Fitzi 在准备这篇博文时的投入和支持。
原文链接：Introducing Ofelimos: a proof-of-useful-work consensus protocol - IOHK Blog