作者:Andrew Poelstra. 编译:Cointime.com QDD
我花了相当多的时间思考这个问题,并且现有技术下我可以提供一个相当全面的答案。但不幸的是,目前还没有短时间内完成这个过程的方法,而且核对工作也需要庞大的时间。在本文末尾,有一些笼统的数字能够大致给你一个概念。
“不将私钥暴露给任何硬件”是一个相当普遍且可以理解的目标。而且有一些操作(事实证明)是完全可以手动完成的。特别是,你可以手动进行Shamir秘密共享,并通过计算一些校验和来进行某些计算(有关此类信息,请参阅codex32和BIP 93。有关不包括校验和的更简单方法,请参阅seedxor。对于随机数生成,有多种从掷骰子结果中提取数据的“骰子词”方案。)
根据我的经验,使用一个128位的种子,简单操作(逐字符相加种子,或在秘密共享期间将其乘以固定的拉格朗日乘数)需要花费5-10分钟,而更复杂的操作(计算或验证BCH校验和)需要30-60分钟。
然而,上述方案的共同点是它们能够将种子数据拆分成一系列字符,然后逐字符进行计算。这意味着操作需要反复重复一些易于描述和掌握的步骤,并且可以通过查找表和纸质计算机进行辅助。
codex32/bip93通过校验和允许你通过在结果上填写“校验和工作表”来检查你的手工工作。你甚至可以通过这种方式准确定位到错误的确切位置。 (要检查校验和工作表本身的正确性,你必须重新执行它们。)
好吧,如果你只是想存储种子并验证其完整性,这很“容易”,你可以按照我提供的链接了解如何完成。但是你还想要做两个更困难的事情:
1. 对秘密数据进行哈希或以其他方式“拉伸”,以获得多个秘密密钥,比如BIP32。
2. 根据秘密密钥派生公钥。 (这是你具体的问题,所以很抱歉我给了一个如此笼统的答案,但我认为这个额外的背景信息很有帮助。)这个操作的术语是“椭圆曲线乘法”,我稍后会解释一下这个术语。
对于步骤1,在2014年,Ken Shirrif曾经尝试手工计算sha256,并估计需要连续工作1.5天才能完成用于挖矿的完整双sha256计算。执行BIP32派生的工作量大致相当。幸运的是,如果你只需要HD密钥,我认为可以设计一种基于chacha20的方法,可能需要大约4个小时。但是,如果你跟随该链接,你会发现这里有很多缺失的细节;这只是从一些更简单的计算推断出来的,由于每个密钥大约需要4个小时,已经相当困难了,因此人们希望在花费过多时间进行尝试之前找到更好的方案。
与秘密共享和相关方案不同的是,当执行sha2或chacha20时,没有任何校验和将保留下来。因此,要检查你的工作,你将不得不重新执行整个计算过程。
对于步骤2,从秘密密钥到公钥派生的问题变得有趣。也许你知道,这个单个操作足以派生地址(在Taproot之前,你还需要计算至少一个哈希,但使用Taproot,你几乎可以将密钥直接用作地址)(加上校验和,但这是BCH代码,所以可以使用bip93过程手工计算)。它还足以计算签名(生成Taproot/Schnorr签名的难点是椭圆曲线乘法;还有一个字段乘法和字段加法,但正如我们将看到的,如果你可以进行椭圆曲线乘法,你必然已经弄清楚了如何执行此操作)。
因此,回答你的“如何在执行椭圆曲线乘法时检查我的工作”的问题,答案是:使用派生的公钥对消息进行签名。签名是公开的,因此你可以使用计算机来进行验证。你还将使用计算机计算消息哈希[*]。事实上,当Bitcoin Core派生地址时,它会对每个密钥进行签名,并进行验证,以确保其密钥派生逻辑中没有任何故障。
那么,从秘密密钥到公钥派生涉及什么呢?基本上,你将把你的秘密密钥解释为一个整数n,取一个特殊的椭圆曲线(EC)点称为G,并计算n × G,其中G定义为G加上自身n次。而“相加”意味着椭圆曲线群操作,它是多项式的比率。这些多项式在一个2^256-2^32-977阶的有限域中,因此每个加法和乘法都涉及在大素数模下操作256位数字。
也许你可以用一种不像在这个域上的多项式系列的方式表示椭圆曲线乘法。但是,如果你发现了这样的方法,我怀疑你已经解决了离散对数问题,这样一来,我们整个讨论都没有意义了。因此,在本回答的其余部分中,我将假设我们困在“有限域中的多项式”范式中。我还假设在有限域中的除法速度非常慢,至少是乘法的十倍,因此你希望使用“雅可比坐标”表示你的点,这是一种特殊的坐标系,其中你的点由3个数字而不是2个数字表示,并且你可以始终用(几个)乘法代替除法。我没有雅可比坐标的好引用;它们与Google为你找到的“雅可比坐标”不同。据我所知,它们在计算椭圆曲线数学领域广泛使用,而在其他领域几乎没有使用。
这与电子计算机的工作方式相同,因此我们实际上知道如何对每个EC群操作执行最少数量的域操作。答案是6-16个域乘法,这取决于要组合的点的“兼容性”(它们的第三坐标是否匹配(好),或为1(更好))。
综合起来,有效地执行EC乘法有三个主要策略:
1. 减少需要执行的群操作(EC相加)的数量。
2. 减少每个群操作需要执行的域操作(模素数的加法/乘法)的数量。
3. 更快地执行域操作。
对于步骤1,再次假设没有离散对数破解级别的新颖数学方法,减少群操作的数量的唯一方法是引入查找表。当计算G加上自身n次时,显然我们不会实际上进行n次相加。那将是大约2^255次相加。相反,我们会将n表示为基数-16,这样我们就有了一个更简单的等式,看起来像这样:
n_0 + n_1×(2^4)G + n_2×(2^8)G + n_3×(2^12)G + ... + n_63×(2^252)G
对于每个术语,只有16种可能性;这些不重叠,因此你将从大小为16×64 = 1024的集合中添加。因此,如果你有一个具有1024个条目的查找表,你可以使用64个乘法完成此操作。而不是使用基数16,你可以使用基数1024;然后,你将不得不从大小为26×1024 = 26624的查找表中进行26次相加。
我在2018年左右编写的我的“离散对数表”中每页容纳了18个表项,当时认为它只是一个玩笑;我浪费了很多空间,但你可以看出,很难在一页上放置超过64个条目,这只是一个简单的估计。所以假设每页64个。那么26624个条目就是一个416页的大作。尝试进一步提高效率会出现递减收益,我认为这个分析线路几乎已经完成。
对于步骤2,减少域操作的数量,我们从上面链接的EFD页面中观察到,我们可以通过精心选择要相加的点来减少我们必须执行的操作数。由于即使相加也会有来自查找表的一个点,我们可以确保查找表中的所有点都具有z=1;如果我们需要在傅里叶空间或蒙哥马利形式中工作,我们也可以在查找表中执行这些转换,而无需用户手动执行[**]。仅使用z=1,我们可以将每个EC操作减少到11次乘法。
彼得·德特曼(Peter Dettman)有一种称为“有效仿射”(effective affine)的方案,可以用于将其他点视为具有z=1,即使它们不是,但是这个方案不明显适用于此处。
在我的观点中,第3步有最多的探索空间,因为在这里,手工计算的故事与电子计算的故事真正分道扬镳,我们不能再依赖现有的研究来获得现成的最佳算法。
让我们开始详细地解决问题。我们将假设我们使用基数-32进行工作,而我们的域元素由该基数中的52个bech32“数字”组成。以这个基数工作的好处是,我们可以使用1024元素的volvelle来执行数字乘法和加法,这是一种特别抗错误的查找表形式。如果我们使用较低的基数,我们将做额外的工作,而对于较高的基数,volvelle将会过大。尽管可能存在一些可调整的空间。
对于模256位素数的加法,将涉及52个数字相加,然后再进行52个数字的约简。因为计算机的加法基本上是免费的,我没有简单估计每个点需要执行的加法次数,但让我们以10作为一个粗略的估计。因此,共计1040个操作。
然后我们需要进行11次域乘法。简单地将两个52位数字相乘会涉及到2704个数字操作。但是使用卡拉茨巴乘法,我们可以将其减少到大约1500个操作(如果我记得正确的话)。使用傅里叶变换技术,我们可以将其减少到大约52个操作,但是每几次乘法后,我们需要退出傅里叶空间,这是一个成本高昂的操作,需要执行数万次数字操作。我不知道你需要多久才能执行此操作;可能从“你必须频繁执行此操作,这样就没有用了”到“很少执行此操作,这样会获得巨大的优势”之间。
不幸的是,这些算法是用于整数乘法的,而我们要做的是模乘法。按照传统方法,这将变得非常糟糕,涉及到欧几里德算法和几十个数字除法等。但是,非传统方法中我们可以使用蒙哥马利乘法来实现这一点,该方法大致增加了每个数字乘以一个固定的预计算因子的开销。我们可以预先计算预先计算表中的数字,因此这是免费的。对于其他数字,我们也将假设这是免费的,因为使用查找表可以非常廉价地进行乘以固定常数的乘法,我还没有仔细考虑过细节。
一些人尝试将蒙哥马利乘法与类似卡拉茨巴的技术或甚至傅里叶技术相结合。不幸的是,卡拉茨巴的技术在数字大于256位时不值得付出额外的开销,而傅里叶技术在数字远大于256位时才变得有意义。因此,关于这个问题的文献很少而且分散,用奇怪的术语编写,用于奇怪的特定应用,如数字信号处理芯片或20世纪50年代的计算机等。我可以感觉到这里有一个非常重要的结果(对于试图手工制作比特币钱包的人来说是“重要的”),但是在这里的限制因素是深入学习的时间。我鼓励阅读此内容的任何人动手实践,并在codex32 github仓库上进行讨论,如果他们取得进展。还有其他更具推测性的想法(例如,使用剩余数系统,然后将查找表中的条目表示为它们对各个小素数的剩余数....如果我们可以进行模小素数的乘法/除法,那么数字除法就变得与数字乘法一样廉价,这将打开新的途径),我没有在文献中看到,但可能会找到一些有用的东西。
综上所述,这就是我们目前的状况:使用一个400页的查找表,假设没有任何开销(跟踪进位、将数据从一行复制到另一行等),并且假设每个操作都有volvelle,我们可以执行26个群操作,总共进行286个域乘法和260个域加法,这可以分解为大约78.6万个数字操作(简单地计算)或大约44万个(假设某些类似于卡拉茨巴的技术有效)。假设我们每分钟可以执行5个数字操作。即使在进行所有这些揣摩之后,我们仍然面临2622小时(简单估计)或1475小时(实际应用了某些技巧)的工作。以每周40小时计算,这相当于65周(简单估计)或36周(应用了我们相当确信的技巧)。
在我看来,即使对于非常长期的冷钱包,使用当前的技术也不现实。
[*]如果你真的彻底不相信电子计算机,你可能会对电脑为你生成的哈希进行签名感到不安。毕竟,计算机可能会对哈希进行伪造,从而欺骗你签署你不打算签署的交易。为了解决这个问题,我建议要求多台计算机生成相同的哈希,甚至可以使用TI-84或Gameboy之类的早期设备,这些设备在比特币之前很久就存在了。你可以手工计算哈希,但这需要花费几十个小时的工作量。
[**]也许你担心在查找表中执行的计算可能是错误的或受到破坏。好吧,除非你愿意制作自己的查找表,这将花费你几十年的时间,在一个秘密地点进行苦行僧般的工作,否则你将不得不接受这一点。我还可以对此发表更多意见,但我试图保持这个回答的重点。
所有评论