HD钱包学习小结

在比特币/以太坊等公链上都会用到钱包。钱包主要用来管理用户的私钥，及用户在链上的数字货币，即用私钥对交易进行签名。私钥可用于生成特定消息的签名，此签名可以在不泄露私钥的情况下使用公钥进行验证。

因为私钥极其重要，一旦泄漏就意味着数字资产的所有权就掌握在别人手里。理论上私钥可以是任意的一串随机数字串，不仅难以记忆也没有规律可循，有必要利用一些 密码学方法 来管理秘钥对（一个秘钥对包括一个私钥和对应的公钥），既方便管理又足够安全。

1. 非确定性钱包

如果只是完全随机生成一个数字串作为私钥，可以使用密码学安全的伪随机数生成器（ CSPRNG, Cryptographically secure pseudorandom number generator,密码学安全伪随机数生成器）。这些私钥之间完全独立，相应的公钥也毫无关联，管理这样的秘钥对的钱包叫做 非确定性钱包 （nondeterministic wallet）。早期比特币地址非确定性钱包. 非确定性钱包最大的麻烦是秘钥对导入导出时，必须逐个操作钱包中的所有秘钥对。

2. 确定性钱包

为了方便应用, 针对非确定性钱包的这些问题，提出了一种密钥对的生成方法：密钥对由一个原始的种子主密钥推导而来。最常见的推导方式是树状层级推导 (hierarchical deterministic) 简称 HD。 这种方法生成的钱包秘钥对也叫 确定性钱包 （deterministic wallet）。

通过一个 共同的种子可以推导出n 多私钥 ，种子推导私钥采用不可逆哈希算法。在需要备份钱包私钥时，只备份这个种子即可（大多数情况下为了方便抄写，种子由12个的助记词生成），钱包只需导入助记词即可导入全部的私钥。HD 钱包能够在不需知道私钥的前提下生成大量的公钥，这个特性非常适用于只负责收款的服务。

我们从HD钱包的生成关系来分别介绍：

熵(128位)→助记词(12个)→种子(512位)→私钥→公钥→地址。

2.1 助记词和熵

顾名思义, 助记词是为了方便记录一长串无规律的数字串而映射为方便抄写和记忆的助记词。因为助记词库中一共有 2048 个助记词，因此 11位长度(2^11=2048)的索引 就可以定位到全部的助记词. 记住这n个助记词以及他们的顺序，就可以将它们的 索引值组合成(n 11)位长度 *的数字串。

反过来说，将(n*11)位长度的数字串切割成n份，每份长度11位，分别作为助记词的索引，根据索引从助记词库中获得助记词并永久记录。

下面是生成这个n*11的数字串，并转换为助记词的过程:

image.png

生成一个长度为128/160/192/224/256位 (bits) 的随机序列数字串，称为熵；
对熵进行hash，取hash后数据串的 前4/5/6/7/8位 作为校验和 (长度=熵长度/32)；
将熵和校验和进行组合，即总长度是132/165/198/231/264位；
将上述结果进行每 11 位切割，得到12/15/18/21/24个助记词索引；
根据助记词索引匹配助记词库的词，得到完整的一串助记词；

下图以长度为128位的熵为例表示上面的过程：

[图片上传失败...(image-4d4e04-1532831639402)]

2.2 种子

通过助记词可以推导出长度为128至256位的熵。通过 PBKDF2函数 可以将熵导出较长的（512位）种子。

注: PBKDF2(Password-Based Key Derivation Function 2)是常用的 key stretching 算法中的一种。在密码学中，Key stretching 技术被用来增强弱密钥的安全性，增加了暴力破解 (Brute-force attack) 对每个可能密钥尝试攻破的时间，增强了攻击难度。其基本原理是通过一个为随机函数(例如 HMAC 函数)，把明文和盐值作为输入参数，然后重复进行运算最终产生密钥。如下图所示:

image.png

PBKDF2函数的实现如下：

DK = PBKDF2(PRF, Password, Salt, c, dkLen)
实现：
DK = T1 || T2 || ... || Tdklen/hlen
Ti = F(Password, Salt, c, i) = U1 ^ U2 ^ ... ^ Uc
U1 = PRF(Password, Salt || INT_32_BE(i))
U2 = PRF(Password, U1)
...
Uc = PRF(Password, Uc-1)

该函数有几个输入参数：

PRF：是一个伪随机函数，例如 HMAC-SHA512 函数，它会输出长度为hLen的结果。
Password：用来生产秘钥的原文，即 助记词组成的字符串 。
"mnemonic" + 用户输入的密码passphrase作为 salt ，密码是可选的。
c: 重复计算的次数，比如2048
dkLen：输出秘钥长度

2.3 主私钥和主链码

从根种子可以生成 主密钥 (master key) 和 主链码 (master chain code)。计算方法很简单，根种子通过HMAC-SHA512函数计算一次, 左256位就是主私钥，右256位就是主链码，主私钥通过椭圆曲线算法推到出主公钥，主公钥和主私钥组成主秘钥对。主链码作为推导下级密钥的熵。

image.png

私钥生成公钥的算法参见下面的椭圆曲线算法小节。这里主公钥长度是264位，是因为格式是 压缩格式公钥 （前缀(8位)+x轴方向坐标(256位)），见下面小节介绍。

2.4 子密钥

从父密钥(parent keys)可以推导子密钥(child keys)，CKD 函数对下面三个输入做 单向散列哈希 。

父密钥(父私钥或父公钥), 如果输入父私钥,也会转换为父公钥
链码作为熵
索引序号

计算方法见下面以太坊hd钱包中的介绍.

image.png

索引号个数为2^32，每个父级密钥能推导出该数目一半的子密钥 (索引号从 0x00 到 0x7fffffff (0~2^31-1) 会生成正常的密钥；索引号从 0x80000000 到 0xffffffff 会生成 增强密钥 ）。

推导采用不可逆的 HMAC-SHA512 不可逆加密算法，子密钥不能向上推导出父密钥、同时也不能水平推导出同一级的密钥。生成的512位数据的左256位作为 子私钥 ，右256位作为 子链码 。

2.5 扩展密钥

CKD 推导子密钥的三个元素中，其中父密钥和链码结合统称为 扩展密钥 (Extended keys)。

包含私钥的扩展密钥用以推导 子私钥 ，从子私钥又可推导对应的公钥和比特币地址；
包含公钥的扩展密钥用以推导 子公钥 ；

扩展密钥使用 Base58Check 编码时会加上特定的前缀编码：

包含私钥的前缀为 xprv
包含公钥的扩展密钥前缀为 xpub

相比比特币的公私钥，扩展密钥编码之后得到的长度为 512 或 513 位。

2.6 子公钥

HD 钱包非常好用的特征之一就是在隐藏私钥的前提下通过 公钥推导出子公钥 ，极大加强安全性。在只需要生成地址接受比特币而无需消费的场景下非常有用，通过公钥扩展密钥能生成无穷尽的公钥和比特币地址。子公钥推导流程如下：

image.png

这种方式可以用来创造非常保密的public-key-only公钥。可以用来接收比特币但不可以花这个地址里的任何比特币。与此同时，在另一种更保险的服务器上，扩展私钥可以衍生出所有的对应的可签署交易以及花钱的私钥。

注：分别推导出的子公钥和子私钥是一对秘钥. 在算法实现中, 子公钥的推导需要先计算子私钥, 再算出子公钥.

2.7 增强扩展密钥

密钥需加强保管以免泄漏，泄漏私钥意味着对应的地址上的币可被转走、泄漏公钥意味着 HD 钱包的隐私被泄漏。增强密钥推导 (Hardened child key derivation) 解决下述两个问题：

虽然泄漏公钥并不会导致丢币，但含有公钥的扩展密钥泄漏会导致以此为根节点推导出来的扩展公钥全部泄漏，一定程度上破坏了隐私性。
如果泄漏扩展公钥（包含有链码）和子私钥，就可以被用来衍生所有的其他子私钥，因为可以通过遍历索引获得子链码。更糟糕的是，子私钥与母链码可以用来推断母私钥。

于此，BIP32 协议把 CKD 函数改为 HKD (hardened key derivation formula) 生成增强密钥推导函数。“打破”了父公钥以及子链码之间的关系。HKD几乎与一般的衍生的子私钥相同，不同的是父私钥被用作输入而不是父公钥。

CKD 函数是从扩展密钥的序列号 ( 0x00 到 0x7fffffff)、父链码和 父公钥 生推导出子链码和子公钥，子私钥从父私钥推导；而 HKD 通过 父私钥 、父链码和增强扩展密钥的序列号 (0x80000000 到 0xffffffff) 推导增强子私钥和增强子链码。

image.png

3. 椭圆曲线算法

通过椭圆曲线算法可以从私钥计算得到公钥，这是不可逆转的过程, 公式如下： K = k * G 。其中k是私钥，G是被称为 生成点 的常数点， 所有比特币用户的生成点是相同的 ，而K是所得公钥。其反向运算，被称为“寻找离散对数”——已知公钥K来求出私钥k——是非常困难的，就像去试验所有可能的k值，即暴力搜索。

使用的 secp256k1 标准所定义的一条特殊的椭圆曲线如下：

image.png

对应的公式是

y^2 mod p = (x^3 + 7) mod p
其中 p = 2^256 – 2^32 – 2^9– 2^8 – 2^7 – 2^6 – 2^4 – 1

上图的x，y是定义在实数范围内的，如果x,y全部取整数,那只有一些离散的坐标值才符合secp256k1椭圆曲线，例如当p=17时，x,y的离散坐标图如下：

image.png

定义椭圆曲线坐标的加法：给定椭圆曲线上的两个点 P1(x1,y1) 和 P2(x2,y2)，则椭圆曲线上 必定有第三点 P3(x3,y3) = P1 + P2。几何图形中，该第三点 P3 可以在 P1 和 P2 之间画一条线来确定。这条直线恰好与椭圆曲线上的 一点相交 。此点记为 P3'=(x，y)。然后，在 x 轴做映射获得 P3=(x，-y)。 椭圆曲线坐标的乘法很好理解，分解为多个加法即可。

image.png

4. 公钥

公钥是在椭圆曲线上的一个点，由一对坐标（x，y）组成。

公钥通常表示为前缀04紧接着两个256比特的数字。其中一个256比特数字是公钥的x坐标，另一个256比特数字是y坐标。例如：

K = 04F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A07CF33DA18BD734C600B96A72BBC4749D5141C90EC8AC328AE52DDFE2E505BDB

为什么在坐标地址前有前缀04？因为前缀04是用来表示非压缩格式公钥，即具有完整的x,y坐标, 而压缩格式公钥是以02或者03开头。

4.1压缩格式公钥

引入压缩格式公钥是为了减少比特币交易的字节数，从而可以节省那些运行区块链数据库的节点磁盘空间。椭圆曲线上的点实际是数学方程的一个解。因此，如果我们知道了公钥的x坐标，就可以通过解方程 y2 mod p = (x3 + 7) mod p 得到y坐标。这种方案可以让我们只存储公钥的x坐标，略去y坐标，从而将公钥的大小和存储空间减少了256比特，大大节省了很多数据传输和存储。

压缩格式公钥为什么有02或03两个前缀？因为y的解是来自于一个平方根，有正负。而y坐标可能是奇数或者偶数，分别对应正负。所以在生成压缩格式公钥时，如果y是偶数，则使用02作为前缀；如果y是奇数，则使用03作为前缀。上面的K如果用压缩格式表示就是：

K = 03F028892BAD7ED57D2FB57BF33081D5CFCF6F9ED3D3D7F159C2E2FFF579DC341A

但是存在一个问题：一个私钥可以生成两种不同格式的公钥——压缩格式和非压缩格式，生成两个不同的比特币地址。目前较新的比特币客户端的默认格式采用压缩格式公钥.

从钱包中导出私钥时,有2种WIF格式（Wallet Import Format）：

新版比特币客户端只能导出为以K或L为前缀的Base58编码的 WIF压缩格式的 的私钥。
较老的没有实现压缩格式公钥的钱包，导出为以5为前缀的Base58编码的 WIF格式 的私钥。
对于私钥的16进制原文,上面2种导出格式区别是WIF压缩格式的私钥被加了后缀01。

举例如下：

私钥hex：1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD
对应WIF格式：5J3mBbAH58CpQ3Y5RNJpUKPE62SQ5tfcvU2JpbnkeyhfsYB1Jcn

私钥Hex-compressed：
1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD01
对应WIF-compressed：KxFC1jmwwCoACiCAWZ3eXa96mBM6tb3TYzGmf6YwgdGWZgawvrtJ

base58编码见下面小节的介绍。

5. 账户地址

5.1 比特币地址

比特币地址是一个由数字和字母组成的字符串，以数字“1”开头。例如：

1J7mdg5rbQyUHENYdx39WVWK7fsLpEoXZy

通过公钥生成地址的算法如下:

ADDR = RIPEMD160(SHA256(PUBKEY))  //双hash

为了提高了可读性、避免歧义并有效防止了在地址转录和输入中产生的错误。比特币地址还要经过“Base58Check”编码。

ACCOUNT_ADDR = Base58Check(ADDR)

5.2 编码

Base64使用了26个小写字母、26个大写字母、10个数字以及2个符号（例如“+”和“/”），通常用于编码邮件中的附件。Base58是Base64编码格式的子集，同样使用大小写字母和10个数字，但不包含不含Base64中的0（数字0）、O（大写字母o）、l（小写字母L）、I（大写字母i），以及“+”和“/”两个字符。Base58的字母表是：

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Base58Check是一种常用在比特币中的Base58编码格式，增加了 错误校验码 来检查数据在转录中出现的错误。校验码长4个字节，添加到需要编码的数据之后。校验码是从需要编码的数据的哈希值中得到，所以可以用来检测并避免输入中产生的错误。

在编码之前，首先我们要对数据添加一个称作“版本字节”的前缀，这个前缀用来明确需要编码的数据的类型。前缀如下：

image.png

注意：

同一个密钥被不同的格式编码后，虽然结果看起来可能不同，但是密钥所编码数字原文并没有改变。
添加前缀的数字串不限于比特币地址, 例如私钥/公钥。

校验码的计算方法如下：

checksum = SHA256(SHA256(prefix+data))

取结果的前4个字节作为校验码。这样得到3个部分：前缀、数据和校验码，再采用之前描述的Base58字母表编码：

image.png

至此，完成了比特币地址的全部生成过程。

6.多币种和多帐户

让同一个 seed 可以支援 多币种、多帐户 等。各层定义如下：

m / purpose' / coin_type' / account' / change / address_index

其中的 purporse' 固定是 44' ，代表使用 BIP44。而 coin_type' 用来表示不同币种，例如 Bitcoin 就是 0' ，Ethereum 是 60' 。

7. 以太坊确定性钱包

有一个golang实现的以太坊确定性钱包的项目: https://github.com/shiqinfeng1/go-ethereum-hdwallet .

该项目提供钱包相关的接口有:

NewMnemonic(bits): 通过熵生成BIP-39助记词,bits一般等于128位NewSeedFromMnemonic(mnemonic):使用助记词生成BIP-39种子,不带密码
NewSeed(): 不使用助记词,通过rand包直接生成512位长度的BIP-39种子
NewSeedFromMnemonic(mnemonic): 助记词转换为种子

NewFromSeed(seed): 通过种子创建一个新的钱包
NewFromMnemonic(mnemonic): 通过助记词创建一个新的钱包

钱包结构的定义:

type Wallet struct {
    mnemonic  string   //助记词(可选)
    masterKey *hdkeychain.ExtendedKey   //主秘钥,包含主私钥和主链码
    seed      []byte  //种子
    url       accounts.URL //HD钱包的生成路径
    paths     map[common.Address]accounts.DerivationPath //每个账户的派生路径
    accounts  []accounts.Account  //保存所有当前钱包的账户
    stateLock sync.RWMutex   //钱包操作锁
}

7.1 生成钱包

首先生成种子, 可以直接生成,或者根据熵和助记词生成.

根据种子通过hdkeychain.NewMaster(seed)生成 主私钥和主链码 , 对种子进行一次hash操作:

HMAC-SHA512(Key = "Bitcoin seed", Data = Seed)

账户派生路径DerivationPath的格式是这样的:

m / purpose' / coin_type' / account' / change / address_index

其中:

purpose=44或0x8000002C(表示数字加密货币)
coin_type=60或0x8000003C*(表示是以太坊)

所以以太坊的根路径是 m/44'/60'/0'/0

7.2 钱包接口

Wallet钱包提供的接口如下:

Accounts(): 返回当前钱包所有账户列表
Contains(account): 检查指定账户是否在本钱包里
Unpin(account): 取消固定指定的账户: 从钱包中删除该账户
Derive(path, pin): 根据path派生一个账户地址: path->派生私钥->公钥->地址

PrivateKey(account): 获取账户私钥
PublicKey(account): 获取账户公钥
Address(account): 获取账户地址
Path(account): 账户路径

SignHash(account, hash): 签名hash
SignTx(account, tx, chainID): 签名交易

钱包接口中,最重要的是派生 Derive.

派生子私钥和子公钥的算法使用同一个接口: ExtendedKey.Child(i) , 派生出指定索引的子key. 如果输入的索引大于0x80000000, 说明派生增强的key, 否则就是派生普通的key.

只有私钥可以派生增强的子私钥; 公钥不可以派生增强的子公钥; 子公钥的派生不需要知道母私钥, 直接从母公钥就可以派生;

子秘钥也是通过下面HMAC-SHA512函数获得:

HMAC-SHA512(Key = chainCode, Data = data)

chainCode即为父key的链码
强化子私钥的data格式是: 0x00 || ser256(parentKey) || ser32(i) ;
普通子私钥/子公钥的data格式是: serP(parentPubKey) || ser32(i) ;

注意: 这里子私钥也是采用的母公钥作为参数.
计算结果是512位长度的数字串 I , 其中:
- 通过左256位 Il 计算子私钥: childKey = parse256(Il) + parentKey ,
- 通过左256位 Il 计算子公钥: childKey = serP(point(parse256(Il)) + parentKey) . 其实就是将IL作为私钥,计算了公钥坐标代入.
- 右256位 Ir 作为子链码 .

附:

image.png

1. 非确定性钱包

2. 确定性钱包

2.1 助记词和熵

2.2 种子

2.3 主私钥和主链码

2.4 子密钥

2.5 扩展密钥

2.6 子公钥

2.7 增强扩展密钥

3. 椭圆曲线算法

4. 公钥

4.1压缩格式公钥

5. 账户地址

5.1 比特币地址

5.2 编码

6.多币种和多帐户

7. 以太坊确定性钱包

7.1 生成钱包

7.2 钱包接口

Recommend

Features to Avoid Null Reference Exceptions in Java and Swift

golang 开发环境配置

使用 SpringAOP 获取一次请求流经方法的调用次数和调用耗时

SQL Server 与 MySQL 中排序规则与字符集相关知识的一点总结

如何设置自己的Dionaea蜜罐来收集恶意软件样本

XXE漏洞利用技巧：从XML到远程代码执行

在Cloud ML Engine的TPU上从头训练ResNet

The DevOps Toolchain per Anders Wallgren, Electric Cloud

诺基亚首席科学家范力欣：用模糊逻辑实现可解释的深度神经网络

ECCV 2018 | 旷视科技提出新型轻量架构ShuffleNet V2：从理论复杂度到实用设计准则

About Joyk