这篇文章上次修改于 272 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文根据 HD wallets and the Legendrery PRF in MPC 整理

目标

实现 hardened 类型的 MPC HD 钱包

这需要设计一个 PRF，根据 $[K]$ 和 $M$ 算出 $[N]$

• $[K]$ 是旧的共享私钥
• $M$ 是 HD 钱包计算中所需的下标 $i$，是公开的
• $[N]$ 是新的共享私钥

PRF 为：

$$ f_K(M) = ((\frac{K+M}{p}), (\frac{K+M+1}{p}), ...(\frac{K+M+n-1}{p})) $$

• $p$ 是素数
• $n$ 是输出的 bit 数量
• $(\frac{K+M}{p})$ 表示 $K+M$ (mod $p$) 的 Legendre 符号，即 $(K+M)^{(p-1)/2}$ (mod $p$)，取值为 1，-1 或 0，但是取 0 的概率很低，可忽略，或者取 0 时定义为 1

符号说明

假设每方都有一个 $a_i$，可得到共享的 $s=\sum_ia_i$

$[a]$ 表示 $a$ 是 $n$ 个 party 之间的共享秘密，例如 $[c] = [a] \cdot b$ 表示每方都会计算 $c_i = a_i \cdot b$，可得到 $c=\sum_i(b \cdot a_i) = b \cdot \sum_ia_i$

原理

算出共享 bool：

• $[t] = [b] \cdot ([s] - [n]) + [n]$

  $[b]$ 是 0 或 1，是随机的

  $[s]$ 是二次剩余，是随机的

  $[n]$ 是二次非剩余，是随机的

  $[t]$ 的结果是 $[s]$ 或 $[n]$

• $[u] = [t] \cdot ([K] + [M])$

  $[u]$ 包含了被 $[t]$ 盲化后的 $([K] + [M])$

• $u = \sum_iu_i$

  当 $u$ 被打开后，不会暴露 $[K]$ 或 $M$，因为它们被 $[t]$ 盲化了

• $l = (\frac{u}{p})$

  $l$ 是被 $[t]$ 盲化后的 $([K] + [M])$ 的 Legendre 符号，结果为 1 或 -1（0 的概率较低，忽略，或定义为 1）

• $[y] = l \cdot (2 \cdot [b] - 1)$

  $[y]$ 的结果是 $l$ 或 $-l$

• $([y] + 1)/2$

  结果是 0 或 1

交互

• 各自生成 $b_i, s_i, n_i$，进而算出 $t_i$，进而结合 $K_i, M_i$ 算出 $u_i$
• 交互，算出 $u = \sum_iu_i$
• 各方均根据 $u$ 算出 $l$，进而结合 $b_i$ 算出 $y_i$，然后转换为 0 或 1

可并行（以免 bit 的数量影响交互的轮数）计算 $n$ 次，得到 $n$ 个 bit，每次都将 $M$ 加 1

分析

从 PRF 的设计目标上，对于 t / n，可以根据任意 t + 1 方推出共享子私钥，但这 t + 1 方和那 t + 1 方算出来的结果一样吗？

另一种方式

每方各自根据 bip32 方式推导子公/私钥分片，所有的子私钥分片相加即可得到共享子私钥

优点：

• 计算简单
• 计算子私钥分片的时候不需要交互
• 支持 non-hardened，即可根据根公钥分片推导子私钥分片，这样计算子地址的时候也不需要交互
• 不需要存储子私钥分片，需要的时候现推即可

缺点：

• 只支持 n / n
• 共享子私钥无法从共享根私钥推出，只能根据 bip32 先算出各方的子私钥分片，然后相加得到共享子私钥，这样备份的时候需要备份所有的根私钥分片