Equihash：基于广义生日问题的非对称工作量证明

"这篇论文是Equihash算法的原创作者Alex Biryukov和Dmitry Khovratovich的作品，他们提出了一种基于广义生日问题的不对称工作量证明（Proof-of-Work, PoW）算法，名为Equihash。该算法着重于解决在加密货币和拒绝服务防御工具中，工作量证明对于GPU、ASIC和僵尸网络用户过于易攻的问题。Equihash的主要创新在于其对内存的大量需求，使得生成证明的过程变得困难，但验证过程却非常快速。此外，论文还介绍了防止成本摊销的新技术——算法绑定，并展示了并行实现受到内存带宽约束的情况。" Equihash是一种针对现代加密货币和抵御拒绝服务攻击的重要算法，它主要解决了工作量证明中的一个关键问题，即如何设计一种对于生成证明而言计算复杂且对内存要求高的算法，但验证过程却能瞬间完成。这一特性被称为“内存硬性”（memory-hardness），旨在阻止那些拥有高性能硬件（如GPU或ASIC）的用户占据优势，以保持网络的公平性和安全性。 论文提出的Equihash算法基于广义生日问题，这是一个在计算上具有挑战性的数学问题。它利用了Wagner's算法的一种增强版本，该算法通常用于解决生日悖论在更大空间中的应用。通过这种方式，Equihash使得攻击者必须投入大量的内存资源才能有效地进行攻击，从而提高了攻击的成本。 为了解决攻击者可能通过多次尝试来分摊成本的问题，论文中提出了“算法绑定”的新策略。这种技术可以防止攻击者将计算成本分散到多个独立的证明生成过程中，确保每次生成证明时的成本不可忽视。 此外，论文还探讨了Equihash并行实现的局限性。由于内存带宽的限制，即使是并行计算，其效率也会受到显著影响。这意味着即使攻击者拥有大量的计算资源，也不能无限制地提高解决Equihash问题的速度，进一步增强了算法的抵抗能力。 Equihash算法为加密货币的安全性和去中心化提供了一个重要的基础，它通过巧妙地结合了计算难度和内存需求，成功地创建了一个既难以破解又易于验证的工作量证明机制。这篇论文对于理解区块链系统中的安全性和抗攻击性具有深远的理论与实践价值。