我在30小时内检查了超过1T的助记符，赢得了一枚比特币

-阿里斯泰尔·米尔恩(Alistair Milne)在推特上表示，他计划在用12个单词助记符生成的钱包中赠送1比特币。+8个已知单词有2个⁴⁰(~1.1万亿)可能的助记符。-要测试单个助记符，我们必须从助记符生成种子，从种子生成主私钥，并从主私钥生成地址。-我用Rust写了一个CPU版本来测试CPU解算器的性能。我的Macbook每秒只能检查~1,250个助记符，这意味着需要大约25年的时间才能检查所有2个⁴⁰可能的助记符。-我将生成和检查助记符(SHA-256、SHA-512、RIPEMD-160、EC加法、EC乘法)所需的所有代码移植到OpenCL C，OpenCL C是在GPU上运行代码的编程语言。-图形处理器版本能够每秒检查约143,000个助记符，这意味着需要大约83天来检查所有2个⁴⁰可能的助记符。-我编写了一个服务器应用程序，将工作编排成大约1600万个助记符的批次分配给GPU工作人员池。每个GPU工作人员都会向服务器请求下一批要做的工作，执行该工作，然后将结果记录回服务器。-我花了大约350美元从astast.ai租用GPU(外加从Azure免费租用大约75美元)。-我担心其他人也会这样做，这就是为什么我包括了0.01 BTC的矿工费用。我认为即使这样也不够，我认为可能会出现一场“零竞赛”，人们会不断提高费用，试图让矿商将他们的交易包括在下一个区块中。-我已经开源了用来做这件事的所有代码。有关各个项目的链接，请参阅文章底部。-创建一场不是由软件赢得的比赛是困难的。我想把它付诸实践，试着自己动手做一件。请在Twitter@johncantrell97上关注我以了解详细信息。

阿里斯泰尔·米尔恩(Alistair Milne)在推特上表示，他计划在一个用12个单词助记符生成的钱包中赠送1比特币。

这很可能意味着它是使用BIP-39助记符生成的，后来当他在一条推文中提供了最初的几个种子单词并最终提供了整个BIP-39单词列表时，它得到了确认。

使用来自2048个潜在单词的固定列表中的单词来生成BIP-39助记符。每个单词由与其在列表中的位置相对应的从0到2047的整数表示。在二进制中，您需要11位来表示直到2047的数字。因此，要表示12个字的助记符，您需要12*11或132位。结果是，BIP-39使用128位随机性，然后使用SHA-256生成4位校验和，该校验和附加到原始128位的末尾，从而得到12个字所需的132位。

这意味着如果我们要迭代所有可能的12字助记符，我们需要从0计数到2²⁸-1，其中每个数字都可以解释为单个助记符，转换成一个地址，然后对照保存1BTC的地址进行检查。乍一看似乎很容易，但我们很快就发现这个数字太大了，无法及时迭代。

幸运的是，我们不需要实际检查所有2²²⁸的可能性，因为阿里斯泰尔将每隔几天发布一个种子字。我们收集的每一个种子字都会将我们需要检查的可能性减少2？或2048倍。

他还提到，他将一次释放最后3到4个词，以防止暴力(或者他是这么认为的)，所以这意味着我最多需要在几天内至少暴力破解最后4个词，这样才能在足够的时间内奏效，才能获奖。

对于8个字，这意味着我们知道128位中的8*11位或88位。这意味着我们需要检查的可能助记符“只有”2^(12888)或2个⁴⁰。这是1,099,511,627,776，或者说大约1.1万亿个可能的助记符。

我不确定尝试1万亿种可能性需要多长时间，所以我写了一个快速程序来获得基准基准，这样我就可以对我正在处理的事情有一些了解，如果我认为它甚至可以做到的话。

我要使用的策略是根据一组已知的输入单词计算需要迭代的开始和结束数字。对于每个数字，我会计算与该数字对应的地址，然后检查该地址是否是保存1BTC的地址。如果是这个地址，我就会创建并签署一项交易，将资金扫入我控制的钱包。

我用Rust编写的第一个版本使用了现有的库(rust-比特币、rust-wallet和ring)来处理所有的散列和椭圆曲线数学运算。通过一些快速基准测试证明，使用CPU来实现这一点是不可行的。

我的笔记本电脑(2.5 GHz双核Intel Corei7)每秒只能执行~1250次助记符寻址检查，或每天大约10800万次。这意味着我的CPU将需要大约25年的时间来生成和检查所需的1万亿种可能性，以便在只知道8个单词的情况下强行拼写助记符。

为了在1天内实现这一点，我需要能够将性能提高约9000倍，目前的速度。

我的下一次尝试是租用一台功能更强大的机器，看看同样的纯CPU版本的潜在运行速度有多快。我从Digital Ocean租了一台32核的CPU优化机，能够记录到每秒约8000次的基准测试，仅比我的笔记本电脑提高了约6倍。

我仍然需要从现在开始将性能提高约1000倍才能做到这一点。我不认为我会通过尝试优化CPU代码来接近这一点，因为它很可能已经在我使用的现有库中进行了很好的优化。

在过去的十年中，利用GPU执行通用编程的情况有所上升。在比特币中，我们在相对较早的时候就看到了这一点，当时人们开始使用GPU来执行挖掘所需的操作。

那么，GPU究竟是如何帮助我们更快地解决这个问题的呢？事实证明，当用于通用编程时，单个GPU内核实际上比它的CPU对应内核慢。当您能够高效地并行化程序时，通常可以看到性能提升。这是因为单个GPU设备通常具有数千个可用于计算的内核。

对我们来说幸运的是，我们的问题可以很好地并行化。我们要检查的两个⁴⁰号中的每一个都运行完全相同的计算(数字->；助记符->；种子->；主私钥->；地址)。这意味着我们可以给每个GPU内核1个数字来尝试，并且可以并行运行数千次尝试。

我很快了解了OpenCL，这是一种标准的开源编程语言，用于编写几乎可以在任何GPU设备上运行的软件。OpenCL C与C编程语言非常相似，只是有一些不同之处。其中一个不同之处在于记忆是如何工作的。在GPU中，您可以使用四种主要类型的内存(全局内存、常量内存、本地内存和专用内存)。全局内存在所有GPU内核之间共享，并且访问速度非常慢，您希望尽可能减少它的使用。常量内存和私有内存速度极快，但空间有限。我相信大多数设备只支持64KB的恒定内存。本地内存由“一组”工作者共享，其速度介于全局和恒定之间。

我的目标是把我需要的所有东西都放入64KB的恒定内存中，而不需要从全局或本地内存中读取，从而最大限度地提高程序的速度。这被证明有点棘手，因为标准的预计算secp256k1乘法表本身正好占用64KB。幸运的是，我能够预先计算出一个较小的表，它只使用了32KB，但比整个表慢了大约75%。BIP-39单词列表又占用了大约20KB，SHA2散列又占用了大约6KB，所以我从一开始就已经使用了64KB中的~58KB。这给我留下了大约6kB的工作回旋余地。

理想情况下，我可以在GPU上完成所有的计算。这意味着数字->；助记符->；种子->；主私钥->；地址全部由GPU计算并以OpenCL编写。

到底需要实现什么来处理这些步骤中的每一个？让我们深入研究从数字到比特币地址需要执行的每一步。如果您不关心这些细节，那么只需跳到本文中的在OpenCL中实现一节。

让我们看一个如何将数字转换为12个单词的种子的示例。

我们可以通过计算该值的SHA-256散列并取结果的前4位来获得后4位(校验和)。在本例中，我们得到的校验和为0101。

现在，我们将校验和附加到末尾，并将132位分成11位一组：

最后，我们使用这些作为索引进入BIP-39英语词表，以查找每个对应的单词：

这就是我们如何将任何数字映射到12个单词的助记符。这一步只需要1次SHA-256计算。

下一步是获取这个132位助记符字符串，并使用它生成一个64字节的二进制种子。如何将132位字符串扩展为64字节？BIP-39使用基于密码的密钥派生函数来实现这一点，其中HMAC-SHA512作为散列函数，字符串“助记符”作为盐，12个单词的助记符作为密码。它还使用2048次迭代，每次迭代需要两次SHA512计算。这意味着此步骤总共需要约4096次SHA-512计算。

这类似于许多网站在其数据库中存储散列密码的方式。其主要思想是在尝试暴力破解某人的密码时，使猜测大量密码的速度变慢。您可以通过增加迭代次数或使用速度较慢的散列函数(如sccrypt或bcrypt)来控制检查单个密码所需的时间。

一旦我们有了种子，我们需要将其转换为BIP-32(HD)钱包。您可以读取所有细节的完整BIP，但在高级别，BIP-32定义了一种从种子生成主私钥，然后使用该主密钥对生成最多2个⁵²²子密钥对的方法。

这是构建钱包软件的一个很好的解决方案，因为它使用户可以轻松地备份单个秘密(他们的助记符)，但能够生成几乎无限的地址(用于所有实际目的)。它还有其他好处，您可以在不需要私钥的情况下生成子公钥(对于需要生成接收地址而不需要在其服务器上有私钥的企业来说非常棒)。

要根据BIP-32将种子转换为主私钥，我们需要计算HMAC-SHA512(“比特币种子”，助记符_SEED)。HMAC-SHA512产生64字节的输出。在生成子密钥对时，我们将前32个字节作为主私钥，其余32个字节作为“链码”来“扩展”密钥。

这一步涉及获取我们的BIP-32主私钥，并根据到达保存比特币的地址所需的派生路径导出子密钥对。如果我们查看资源管理器中的地址，我们可以看到它是使用BIP-49P2WPKH-NESTED-IN-P2SH生成的。

这意味着派生路径的格式为m/49'；/COIN_TYPE‘/ACCOUNT’/CHANGE/ADDRESS_INDEX。

对于这个项目来说，找出派生路径是一个巨大的风险。我假设Alistair只是生成了一个新钱包，唯一进行的交易是存入1BTC。在此假设下，这意味着第一个地址的派生路径将是m/49'；/0'；/0'；/0/0。

这意味着我们需要获取主私钥并生成三个强化私钥，然后生成两个普通私钥。

每个强化私钥需要HMAC-SHA-512计算(2个SHA-512散列)和一个secp256k1标量加法。

每个普通私钥都具有与硬化密钥相同的要求，另外还需要根据私钥计算关联的公钥。要计算公钥，我们需要将私钥表示的标量与secp256k1组生成点G进行椭圆曲线乘法。

最后一步是获取计算出的公钥，并将其转换为P2SHWPKH地址。这包括构建正确的脚本，然后使用hash160(RIPEMD-160和SHA-256)获取地址，然后使用SHA256(两次)计算4字节的校验和。

此步骤总共花费我们10个SHA-512、3个SHA-256和1个RIPEMD-160散列。它还花费我们5个EC标量加法和3个EC乘法。

对于我们想要尝试的每个助记符，我们必须执行所有这些步骤：

地址的私钥-10个SHA-512、3个SHA-256、1个RIPEMD-160、5个EC加法器、3个EC乘法器。

乍一看，种子生成步骤将是最慢的，尽管如果没有一些基准测试，很难知道如何在成本方面将SHA-512哈希与EC操作进行比较。事实证明，与其他步骤相比，它们都相对较慢，但种子生成的成本至少比其他步骤高一个数量级。

因此，为了在OpenCL中实现整个流程，我需要一种方法来执行SHA-256、SHA-512、RIPEMD-160、EC加法和EC乘法。我还需要在某种程度上协调所有这些，以解决我的问题。

我的策略是找到所有算法的开源C实现，并将它们移植到OpenCL C。我从SHA-256和SHA-512开始，因为仅凭这两个就可以计算Number->；助记符->；Seed，我知道生成种子是迄今为止最慢的部分。

最终，我在OpenCL中生成了种子，我使用NVIDIA 2080Ti进行的第一个基准测试表明，我可以每秒生成142,857个种子。哇!。现在我们有进展了。

这意味着一颗NVIDIA 2080Ti每天可以产生约120亿颗种子。这仍然意味着需要83天才能产生所有万亿颗种子。这比我的CPU需要25年的时间要好得多。然而，这仍然只是产生种子，种子不足以知道助记符是否正确。我仍然需要完成将种子一直转换到地址的过程，才能验证它是否是正确的助记符。

然后，我回去对SEED的CPU版本进行基准测试以生成地址，看看这需要多长时间。这台32核的数字海洋机器每秒能够处理约5.2万粒种子。这是相当不错的，但是在OpenCL种子生成改进之后，它现在是瓶颈，仍然需要221天以上的时间才能完成。此外，我还需要协调将GPU生成的种子移回CPU以完成它们的处理。这种协调将需要时间，并且是一个更复杂的程序来编写。

这意味着我需要能够在OpenCL中执行EC数学运算(加法和乘法)。我采用了比特币使用的开源libsecp256k1实现，并将其移植到OpenCL C。它要求我首先了解libsecp256k1库是如何构造的，以及我到底需要移植什么才能从主私钥生成地址。

结果，我需要移植大约2000行代码。幸运的是，OpenCL C和标准C足够相似，不需要太多更改。这些更改涉及我实现OpenCL不支持的一些内存管理函数，如memcpy、memset和memero。我还需要消除执行EC乘法时的盲目操作，并预计算一个32KB的表，而不是缺省的64KB表。

说了这么多，做了这么多之后，我运行了一些健全性测试，惊讶地发现我的OpenCL实现实际上工作正常。

然后，我使用2080Ti重新运行基准测试，发现使用GPU从种子计算地址所需的时间可以忽略不计。它每100万粒种子只增加了几百毫秒。

我现在可以100%地在GPU上运行整个过程，但使用2080Ti枚举1万亿个可能的助记符仍然需要大约80天的时间。

然后我尝试在一系列不同的显卡(1080、1080Ti、2070、2070Ti、Tesla K80、Tesla P100和Tesla V100)上运行它。令我惊讶的是，GPU之间的性能变化并不大。即使是最顶级的特斯拉V100也只快了大约15%，但租金几乎是它的4倍。

在低端，1080/1070大约比2080Ti慢3到4倍，但价格只有2080Ti的一半左右。2080Ti似乎是解决此问题的最具成本效益的卡。我能拿到多少，我该如何安排这一切？

如果我要在24小时内解决这个问题，我需要大约80个2080Ti的能量。

如果我想将这个问题分布在多个GPU上，简单的答案是将我们需要迭代成80个相等部分的2个⁴⁰数字分解，然后在单个GPU上运行每个部分。不幸的是，事情不会这么简单。

我首先需要弄清楚如何访问所有这些机器。我的第一个想法是使用主要的云提供商(AWS、Google Cloud和Microsoft Azure)。我很快了解到，这些公司对您可以配置的GPU数量有严格的配额(有些是零！)。开了个新账户。

幸运的是，我遇到了一个GPU市场(Vast.ai)，它允许拥有未使用的GPU的人将其出租给任何想要访问GPU的人。他们有1080和1080Ti的大量库存，但没有我需要的2080Ti那么多。库存一直在波动，这取决于有多少人租了它们，他们愿意付多少钱，以及当时有多少供应商在线。

这意味着我不能轻易地准确分配80个2080Ti，并在它们之间平均分配我的工作负载。

我最终构建了一个简单的集中式服务器，作为工作的分配器。这与矿池的工作原理非常相似。每个GPU工作人员都会向集中式服务器请求一批要执行的工作，执行该工作，然后将该工作(如果找到解决方案)记录回服务器。每个工人都会继续这样做，直到没有更多的工作要做。

这意味着我可以轻松地以我想要的速度旋转任意数量的卡片，并且中央服务器将能够在请求下一批工作时跟踪下一批工作是什么。每个Worker实例不需要知道它需要执行哪部分工作，它只需盲目地向服务器请求下一批工作即可。

此解决方案确实在网络延迟方面增加了更多时间。我需要使批大小足够大，以便增加的网络延迟只占总时间的一小部分。我最终使用的批大小为16,777,216，这意味着将有65,536批工作来计算所有2个⁴⁰可能的助记符。

16,777,216批2080Ti的计算时间略低于2分钟。这意味着不到1秒的网络延迟增加了不到1%的额外计算时间。

这最终是一个比我最初设想的更复杂的系统，我担心会出现错误，或者当时间到来时，它不会像预期的那样工作。我最终进行了全面的端到端测试，以确保一切正常。

我用一个新的BIP-39助记符创建了一个钱包，并在里面转了0.0001块钱。然后，我用9个已知的种子单词启动了我的系统(这样就不会花那么长时间，也不会花我那么多钱)。我租了几辆2080Ti的在Vavar上，然后就让它裂开了。不到20分钟，它就找到了解决方案，并将0.0001比特币扫到了我控制的一个特雷佐钱包里。我觉得我已经准备好了，尽管我不确定我是否真的能够在需要的时候及时获得足够的计算能力来执行任务。

我觉得仍然有一种方法可以优化我正在使用的SHA-512代码，方法是尝试移植Hashcat正在使用的SHA-512版本，因为他们有一个非常优化的版本。由于S。

..