Shamir Secret Sharing

钱包是接收和发送比特币的应用程序或设备。Anna 希望即使丢失部分记录，仍能恢复备份。她选择五份中取三份：生成五个不同份额，同一组中任意三个有效份额就能恢复秘密。她可以丢失两个，但不能丢失三个。所需数量称为门限；一般写作 n 份中需要 k 份，因此允许丢失 n−k 份。可是，门限无法识别 Anna 是否同意。如果别人拿到三个份额，或者持有人联合起来，也能恢复同一个秘密。降低门限会让恢复更容易，也会减少无需 Anna 就能完成恢复的人数。 [1] [6]

Anna 若把五个文件都放进同一个云端账号，帮助就很有限。账号丢失或被攻破会同时影响全部份额。备份需要合理分散存放，记录所用方法和参数，并在可信设备上检查恢复过程。如果也要供继承人使用，他们必须知道要找什么、如何安全处理。对同一秘密 S 重新随机拆分，会产生新的一组份额；新旧份额不能混用。但足够的旧份额仍能恢复 S。所以重新拆分不能撤销已经泄露且仍可用的备份，也没有改变秘密本身。 [1] [4]

普通恢复会在一台设备上重新组成完整秘密。如果设备已被入侵，攻击者可能就在这一刻取得它。假如秘密是一把 Private Key，也就是用来生成数字签名、授权花费资金的秘密数值，持有人之后无需再凑份额就能签名。Multisig 则按该次支出的条件要求多个签名。另有门限签名：借助额外的 MPC 协议，即多个参与者进行安全的共同计算，份额可以参与生成签名，而不必拼出完整密钥。NIST 区分了这些情形。仅有 Shamir 份额，并不意味着已经具备这样的签名协议。 [3] [5] [6]

两个名称带 Shamir 的程序，未必能读取彼此的份额。恢复时，数学运算、数值编码、份额标识以及所属分组都必须匹配。SLIP-39 是以此方法为基础的具体标准：它添加了记录份额的词表、元数据即辅助信息、分组、加密及错误检查。因此，通用原理并不是让你手动切分已有 Seed Phrase 的指南。在把钱包交给这种备份之前，要了解支持的格式，并确认预定流程确实能够完成恢复。 [2]

五份中需要三份时，丢失两个份额的后果很明确。但损坏或伪造的份额，可能让基本计算返回另一个秘密，而不是提示份额不足。方法本身不验证份额来源，也不证明创建者诚实。错误检测、纠正以及 verifiable secret sharing，也就是验证分享过程是否正确的机制，都是有各自假设的附加层。例如，SLIP-39 增加了校验和与称为 digest 的验证指纹。这不代表所有 Shamir Secret Sharing 应用都有相同检查，也不代表校验和正确就证明备份来源可信。 [2] [5]

在理想方案中，少于 k 个完整份额不会给攻击者增加任何关于 S 的信息，即使其计算能力无限也一样。份额不是能直接看见的三分之一原始单词。这一性质需要正确的随机性：拆分所用的数必须独立、等概率地选择。可预测的数、重复使用这些数，或秘密数据从设备内存中泄露，都会改变情况。附加检查数据也须单独分析，例如 SLIP-39 的 digest。而原始密码如果很弱，不会因为备份被拆分，就无法通过其他途径猜中了。 [1] [2]

取一个很小的秘密 S=5，使用规则 f(x)=5+3*x mod 17。mod 17 表示取除以 17 后的余数。三个份额是数对 (1,8)、(2,11)、(3,14)：第一个数表示位置，第二个数是计算结果。从前两个点可得到增量 3，以及原始秘密 8−3=5。三种可能的点对都能恢复同一个五。可是，仅凭点 (1,8)，S 可以是 0 到 16 中的任意值，只要把增量选为 a=8−S mod 17。这些小数值仅用于说明，不能拿来设计真实钱包的备份。 [1]

一般规则是 f(x)=S+a1*x+…+a(k−1)*x^(k−1)。这个表达式称为多项式；S 是秘密，其余系数是从有限域中独立、均匀随机选出的元素。有限域是一种有严格加法和乘法规则的数学环境。份额为 (x,f(x))，每个 x 必须不同且非零：x=0 会直接泄露 S。从 k 个点出发，拉格朗日插值可以算出 f(0)，也就是秘密。同一点的两份副本不会增加信息。在素域 GF(p) 中，普通除法由乘以模逆元代替；模逆元与除数的乘积为 1。GF(256) 的运算也不同于简单地对 256 取余，不能混淆。 [1]