1
" M0 P$ e7 L) S- {9 t) m: g) f1 ^$ u5 ^# s# [& _
数字签名算法 - Ed25519
4 z; u9 M/ Q9 ]& v) d& Z7 d. P; D8 V6 r' B: q7 t+ C
一、背景
) h1 V( Z; ]7 y; M+ a9 w
; S  \! b$ G  P, U5 i: E5 r: f数字签名的目的是创造和我们合同上签字一样的不可抵赖性，其核心属性是：通过签名的消息可以明确知道其发起人，因为只有唯一的签名者的私钥才能计算出有效的签名，这也就意味着该消息确实是签名方生成的，这种证明在一些国家具有法律上的意义，比如美国的电子签名法案，德国的签名法等。
4 `3 g/ s/ N, K+ Q. s, j+ O$ K2 {% p+ V+ y
私钥签名，然后公布公钥、消息和签名数据让大家去验证，在这些步骤中公私钥对扮演着最重要的角色，它们总是成对出现，而且就像量子纠缠一样互不分离。公私钥一般是通过一个特殊的单向函数和一个随机数生成，这种单向函数往往正向求解（ f(x) = y） 是多项式难度，而逆向求解（ f-1(y) = x）是指数级难度。
9 Y9 v( D0 s, {- v) d. [# Y# x+ w1 b; y( ^' n: i7 _$ C& k, V
假设x是私钥，y是公钥，那么从私钥推导出公钥在现代计算机体系上需要大到没有任何单位能承受的消耗，所以在目前来看是非常安全的，但是如果量子计算机在未来真的能研究出来的话，那么现在这些广泛基于RSA，DLP（离散对数问题），和从DL上扩展来的ECC（椭圆曲线密码学）的非对称加密机制都是不安全的，如何做到quantum safe，这大约是个和研究量子计算机一样漫长的岁月。! w4 K5 @6 f$ p6 E, E- z

% {) V' G, P5 V, l. y0 u: d签名算法在区块链系统中处于最基础的位置，账户地址、交易的产生都与之紧密相关，所以在签名算法的选择上，我们必须兼顾安全和性能，其中安全是首要的，中本聪当时选择的是ECDSA over secp256k1，secp256k1是SECG定义的一个Koblitz曲线，在他使用前几乎无人问津，它设计透明，而不像NIST选中的secp256r1（也就是现在主流常用的P256）曲线中有一些诡异的参数，这些参数被广泛地认为是NSA植入的后门，后来的一系列事件也确实证明了中本聪的选择是非常具有前瞻性的，于是以太坊、EOS等也都跟进了中本聪的想法，但是随着Ed25519专利期限制解除，包括比特币的核心开发者们和Vitalik Buterin都讨论过是否迁移到Ed25519，链接中可见他们的态度都比较暧昧地倾向于使用Ed25519，但可能由于迁移成本太大所以未能成行，而ripple则是在14年就果断迁移了过去。) r. i' L! K& ?; x/ a2 c' V) @

8 i- x! b  `1 s参考链接：
( n6 g; s) Z' T' s- H4 b2 d/ x* X* o+ Z2 {. J, A# G! x
https://www.ams.org/notices/201402/rnoti-p190.pdf) g; C! ?6 x, D7 n0 E

4 \  Z8 B" i/ H# I$ x# O% Thttps://bitcointalk.org/index.ph ... g1134832#msg1134832
; z! S" i0 P9 r3 L+ C
$ d9 K) }" w/ B/ S0 Y4 Q5 t& D: \% Ohttps://blog.ethereum.org/2015/07/05/on-abstraction/& Q1 l. m' A0 I
; F: t7 s" n  g1 W- P, L' A; T( `
二、安全性考量0 n2 v/ c+ m8 O- @5 w; k$ U1 b

. C; J0 ^" `/ r+ BEd25519在安全性上经过大量独立的知名安全专家评测后被认为是"safe"，而secp256k1是"unsafe"。
' c/ j2 N4 A4 x0 r0 I( t0 V7 S5 D4 o% n* H/ ]0 Y
参考链接：
5 ~/ ~1 H9 o7 [2 [6 v, g+ D: e# ^& S5 h+ ~2 k' L
https://safecurves.cr.yp.to/
. u' N. v& J8 d  f  `5 E( }- B- [1 X0 S- }7 \6 p. ^
三、性能考量- l: X* C$ [+ Y& ~2 r

" D# ~* H) k6 t7 ^  ]- \Vite为了满足了工业级应用对高吞吐、低延迟和扩展性的要求，设计了许多优化的方案，比如提出了"交易分解"这个概念，其含义是会把一个交易拆成类似于"请求"和"响应"这样的一对交易，那么再结合我们如此高的TPS，可以预见在Vite的公链系统中对交易的验证和确认是非常频繁发生的，也就是说整体系统的性能表现对签名和验签算法的速度高低会相当敏感。" L  n6 j; M( @

" B7 C+ K" h' K) `- @根据现在的数据Ed25519的性能数倍快于ECDSA over secp256k1 (参考ripple的benchmark)，我相信这对我们系统的性能提升会带来很大的帮助。不仅如此，Ed25519的签名长度也略小于ECDSA，这给就网络传输和存储系统减轻了不小的压力。
8 ]. p( P! v+ r0 |9 L
' Y: x! m' l( ?* Z! O6 Z6 v* |参考链接：! ]3 y0 H# w% ^6 j
/ Y$ ~3 q7 m+ |) P1 ~- X% D! F
https://ripple.com/dev-blog/curves-with-a-twist/3 E5 O; P' s+ G3 s" O( ~7 J
$ q% P) ]: P* r" z" ?2 k. z
https://bench.cr.yp.to/primitives-sign.html
5 B& k  }& n! L  _. E  I
0 S# x% Q  {! C, i, c% Z) D四、改造( ^/ g7 z3 A( z

: u  O- \# o' {# j2 F5 T我们把标准Ed25519的SHA2替换成了Blake2b。  S" O! D2 O% e0 i& m8 V2 m
' K5 @: ?  g. R
五、不足8 y, i  q$ u  H& c+ n$ M. C
$ Q0 [2 T( o/ H  \! V! _  ?4 c: D
由于密钥空间是非线性的，无法兼容BIP的Hierarchical Deterministic Key Derivation。: k5 y! ~! l: R. ~+ T8 |6 N; G
$ y+ p: A4 K2 a" k; @
参考链接：! `! h. ]: \, [3 u- @$ Y2 H

% |7 I8 p& S# {https://cardanolaunch.com/assets/Ed25519_BIP.pdf7 Q9 ~: [% j0 r, g  G/ O- A* I

" z; R) x* h; r% b. W7 h# E1 Q2+ n* y8 N/ _; v: f% R

' k( l) Q! B+ n  F3 wHash算法 - Blake2b9 N7 l0 z$ P) {* Q7 i  O

8 K  f& b$ {4 \5 a- M+ |一、背景& |2 V0 C+ D% R5 X

/ H& Z4 Q/ t7 P) ^) q哈希算法的作用是对一串任意长的消息生成一个短的固定长的摘要，Hash函数也是一个单向函数，但是和非对称加密系统中的单向函数的差别在于，后者的单向函数往往是追求反向求解在实际操作上不可能，但理论上是可能的，或者换句话说公钥含有推导出私钥的完整信息。但是哈希函数则不一样它理论上不能逆向，而实际上却往往可以，理论上来说，一个哈希值可以有无穷多个原像对应它，给一个简单的证明，假设一个哈希函数的输出是n个bit，那么这个Hash函数的所有输出值只有2n  个，而输入是无限制的。
) G0 r- h3 @. {& u0 x! G/ B1 \$ V( f" I. |
那么根据鸽巢原理，如果输入是m * 2n个bit，每一个Hash的输出至少对应m个原像，那么即使 Hash(X1) = Hash(X2)= Y，也没法得到X1=X2的结论。但实际上受限于存储和计算能力，输入的原文的长度不会很大，意味着m的值域很小，所以一旦有一个X满足Hash(X) = Target，X是真实原像的概率非常大。5 z8 y$ }! ?4 @! V8 n# W8 f1 E

- ?4 X0 x7 u+ m! q参考链接：; y% D! F/ U' P# F4 M& x# Z9 W. f
2 N, [  b! Z: E& x& ?
https://blake2.net/8 v5 m5 E3 Y9 R; Z( O& D2 h) M
& J& P: m. C3 W- x4 d
Hash函数在我们的系统中，担负着挖矿，数据的防篡改等功能，它和签名算法一样是最基础的组件，所以同样我们在技术选型的时候要着重考量其安全和性能。/ r7 q& P1 N; E( F1 {) b* Z# N* d
1 ^( e7 W1 Z" e- ?$ X( z5 c; \4 m
二、安全性考量& V; r: z* F4 x  ?
$ Z; e: o/ j0 t9 T$ |% a6 F
Blake2的前身是Blake，Blake和keccak当时一起竞争SHA3标准的时候失利了，当时失利的原因是Blake和sha2的实现有点相似，而NIST的目标是一个完全不同于SHA2标准的Hash算法。# d. Y( Y4 b5 D2 m

8 U" q# D6 z% `9 X! q“desire for SHA-3 to complement the existing SHA-2 algorithms … BLAKE is rather similar to SHA-2.”2 d5 \9 |  Y1 z+ S

2 u& \  y& h0 p. G/ m6 G, f事实上在安全性评估上NIST给了Blake相当高的评价，其 report形容Blake。# S; ]. [* C! d

& ~. k/ \8 }0 C; m* Z4 i参考链接：
' Z% v( Z+ a1 F% D" h" u
& ~3 v/ f" i( t0 m' u: thttps://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf
7 G8 d. I2 [' u9 W4 e5 Y: z, W4 f: [$ C3 q! q" V
“BLAKE and Keccak have very large security margins.”
. A3 F9 C0 B* y0 f! O1 `1 w
$ Q( X) J9 @( V所以一般而言我们可以认为blake2的安全性和keccak不会有大的区别。: _0 q" K5 p2 b
5 b. s. G8 R4 ]" e
三、性能考量
& h7 y/ r2 a4 K4 ^% C8 Q
4 ]2 f0 d  O3 i( [% _1 ]) F根据大量的数据Blake2的性能表现在现代的通用CPU(X86 ARM等)上的表现远远领先其它任何Hash算法。
$ D; w  ]! ]7 y; L2 k5 k/ w
6 g/ Z6 ^/ A. \7 g具体性能表现参考链接：
: Y' I( B3 W4 R7 ^6 v! M8 z+ }  w0 o! D' m) m# X" J1 [+ v' {$ m) A; d
http://bench.cr.yp.to/results-sha3.html5 ?9 U' I3 G" r& P  n- V

- y, g+ Q; ~1 m! o, DBlake2的另一个特点是用ASIC设计的Blake2算法能达到的峰值并不会很高，这就意味着挖矿的峰值速率相对较低，这也是我们希望的。$ e  P" f7 U( h" r6 J! s6 C& ?. }

+ o5 a9 k2 {2 B6 t- H* i  e$ S9 f3
$ \- k7 S& x0 A+ f5 z* Y' }9 ?, W/ y4 |0 \
密钥派生函数 - scrypt
  g) V" w: R2 w" E/ {
0 Q6 Y3 z, v% L, A4 j- f+ e一、背景! M, ^* y7 L3 Y, `, D$ P
7 d2 S. W8 n( c# Z
密钥派生函数(Key Derivation Function) ，简单而言就是使用一个主密钥派生子密钥的函数，比如把一个短的字符串通过KDF的运算扩展成需要的形式，它和Hash函数很类似，最大不同在于它会引入随机量从而防止黑客进行一些查表攻击等（比如彩虹表 rainbow tables）。我们采用的scrypt是一种内存依赖性的KDF，它每一次计算都要占用大量内存资源，消耗很长时间，所以暴力攻击也几乎是不可能的。
: l. M2 s& |: ?
. o6 @( I8 ~- qKDF在我们的系统中处于非基础性的地位，我们把用户输入的随机短密码经过KDF之后，转换成256bits的密钥，然后使用这个密钥配合AES-256-GCM算法，加密Ed25519私钥，从而安全地在PC上保存我们的私钥。. |. ~3 R8 j$ d) x5 O$ D) C

! A3 z" b2 d: n& h) w4 F$ \1 U5 w二、选择原因' C+ i2 t+ I/ Q, H

; m. X& |( @% I% O+ e# f- u7 N3 E从技术角度来看scrypt相比于获得15年的Password Hashing Competition的argon2来说安全性上并没有大的区别，但是由于其诞生更早使用更广泛所以在实践角度看显得更成熟一点，argon2如果再有两到三年年仍然没有被发现大的问题，我们也有可能会使用它。
/ H/ N  h* L3 Y  p& G+ o4 v# t7 I# t3 E: E$ T2 f; D; o4 a( Y
4
* _3 X0 c, w4 x. w1 ]5 Z
6 ]; ~" x- n+ {% E8 K( n相关名词解释
0 }3 k6 L8 T0 J, t
3 }3 a6 ^* X  l8 M+ ?6 F8 {ECDSA(Elliptic Curve Digital Signature Algorithm)是使用椭圆曲线的数字签名算法) A: Q8 @4 _& C' Y$ Q8 {. ?7 A
4 M4 h& g; `1 t! d) ]
secp256k1是ECDSA算法的一个参数! p9 U- K+ `0 y  w6 W$ U
9 |3 S! ?5 }2 \, t$ C, O
* sec是SECG（Standards for Efficient Cryptography Group）推出的Standards for Efficient Cryptogrpahy
6 O: {3 m9 ?& X% G1 x& j+ f; [% `9 ?" J2 r
* p的意思是这个椭圆曲线使用 prime field，相对应的
7 S. w. D+ b4 q. R" B; q
5 u" k9 L6 l. p+ E& u3 R0 p* 256的意思是 prime的长度是256bits
5 S- Q5 E+ c) S% h1 {' f3 `7 V. l; v1 \7 `' x8 Y" d; X& H2 I' S
* k 是Koblitz曲线/ a6 A& `5 F* x$ E

- ]4 ^2 u& B. B8 E7 b* E- ~* 1 意味着它是第一个(事实上也是唯一)标准曲线的类型0 q, E6 S! Z5 \- F5 c- b' m9 o
( O7 j7 U$ x6 i
Ed25519 是一个使用SHA512/256和Curve25519的EdDSA签名算法