区块链中的Ed25519

1. 引言

比特币和以太坊采用Secp256k1，NEO使用secp256r1，波卡、Cardano、NEAR 和 Solana 等使用Ed25519。

Ed25519相关代码实现有：

• https://github.com/dalek-cryptography/ed25519-dalek
• https://github.com/jpopesculian/ed25519-dalek-bip32
• https://github.com/jedisct1/rust-ed25519-compact
• https://github.com/w3f/hd-ed25519
• https://github.com/ZenGo-X/multi-party-eddsa
• https://github.com/ZcashFoundation/ed25519-zebra
• https://github.com/RustCrypto/signatures

详细可参看：Cryptography behind top 20 cryptocurrencies（统计于2019年4月）

NameTypeSigning algCurveHashAddress encodingAddress hashBitcoinUTXOECDSAsecp256k1SHA-256base58, bech32SHA-256, RIPEMD-160EthereumaccountECDSAsecp256k1Keccak-256 * none (just hex) * last 20B of Keccak-256 *XRPaccountECDSA *secp256k1 *first half of SHA-512base58 with different alphabet *SHA-256, RIPEMD-160LitecoinUTXOECDSAsecp256k1SHA-256 *base58, bech32SHA-256, RIPEMD-160EOSaccountECDSAsecp256k1SHA-256 none * none * Bitcoin Cash Same as Bitcoin * StellaraccountEdDSAed25519SHA-256 and SHA-512 in EdDSA *base32noneBinance CoinEthereum ERC-20 token *TetherBitcoin Omni layer / Ethereum ERC-20 tokenTRONaccountECDSAsecp256k1SHA-256base58last 20 bytes of Keccak-256 *CardanoUTXOEdDSAed25519none and SHA-512 in EdDSA *base58noneMoneroUTXO *it's complicated*ed25519Keccak-256 *base58Keccak-256 * IOTAUTXOWinternitz one time signature scheme-Curl, Kerl *noneKerlDashUTXOECDSAsecp256k1SHA-256 *base58SHA-256, RIPEMD-160MakerEthereum ERC-20 tokenNEOaccountECDSAsecp256r1SHA-256base58SHA-256, RIPEMD-160OntologyaccountECDSAnist256p13x SHA-256base58SHA-256, RIPEMD-160Ethereum ClassicSame as EthereumNEMaccountEdDSAed25519none and Keccak-256 in EdDSA *base32Keccak-256, RIPEMD-160ZcashUTXOECDSA, zk-SNARKs * secp256k1, Jubjub * SHA-256base58, bech32SHA-256, RIPEMD-160TezosaccountEdDSA, ECDSA *ed25519, secp256k1, secp256r1BLAKE2 and SHA-512 in EdDSA *base58BLAKE2 2. EdDSA签名机制

可参看：

• 维基百科 EdDSA
• ECDSA VS Schnorr signature VS BLS signature
• Extended twisted Edwards curve坐标系及相互转换
• Edwards-Curve Digital Signature Algorithm (EdDSA)

Edwards-curve Digital Signature Algorithm (EdDSA) 为Schnorr signature的变种，其基于的是twisted Edwards curves。 EdDSA可在不牺牲安全性的情况下，比现有的数字签名机制更快。

EdDSA机制中涉及的参数有：

• finite field F q \mathbb{F}_q Fq​，其中 q q q为prime。
• 曲线 E E E over F q \mathbb{F}_q Fq​，该曲线的order为 n = # E ( F q ) = 2 c l n=\#E(\mathbb{F}_q)=2^cl n=#E(Fq​)=2cl，其中 l l l为large prime， 2 c 2^c 2c为cofactor。
• 具有order l l l 的base point G ∈ E ( F q ) G\in E(\mathbb{F}_q) G∈E(Fq​)。
• hash函数 H H H，其输出为 2 b 2b 2b bits，其中 2 b − 1 > q 2^{b-1}>q 2b−1>q，使得 F q \mathbb{F}_q Fq​ elements 和 E ( F q ) E(\mathbb{F}_q) E(Fq​) curve points都可以 b b b bits string来表示。

EdDSA签名机制的安全性取决于以上参数的选择：

• Pollard’s rho algorithm for logarithms 解决discrete logarithm近似需要约 l π / 4 \sqrt{l\pi/4} lπ/4 ​次curve addition运算。因此，要求 l l l足够大，通常应大于 2 200 2^{200} 2200。对 l l l的限制会影响 q q q的选择，根据Hasse’s theorem： # E ( F q ) = 2 c l \# E(\mathbb{F}_q)=2^cl #E(Fq​)=2cl cannot differ from q + 1 q+1 q+1 by more than 2 q 2\sqrt{q} 2q ​。
• 在分析EdDSA安全性时，hash函数 H H H通常model为random oracle。

公私钥对 ( p k , P ) (pk,P) (pk,P)，其中公钥 P = p k × G P=pk\times G P=pk×G，椭圆曲线order为 n = 2 c ⋅ l n=2^c\cdot l n=2c⋅l， G G G为所选椭圆曲线order 为 l l l的base point。 EdDSA对消息 m m m的签名过程为：

• 1）选择随机值 k ∈ R [ 1 , l − 1 ] k\in_R [1,l-1] k∈R​[1,l−1]
• 2）计算curve point R = k × G R=k\times G R=k×G
• 3）计算hash值 e = H ( R ∣ ∣ P ∣ ∣ m ) e=H(R||P||m) e=H(R∣∣P∣∣m)
• 4）计算 s = k + H ( R ∣ ∣ P ∣ ∣ m ) ⋅ p k s= k+ H(R||P||m)\cdot pk s=k+H(R∣∣P∣∣m)⋅pk

EdDSA的签名为 ( R , s ) (R,s) (R,s)，其中 R R R为point， s s s为scalar。

EdDSA的验签过程为：

• 验证 [ 2 c ⋅ s ] × G = [ 2 c ⋅ k ] × G + [ 2 c ⋅ H ( R ∣ ∣ P ∣ ∣ m ) ⋅ p k ] × G = 2 c × R + [ 2 c ⋅ H ( R ∣ ∣ P ∣ ∣ m ) ] × P [2^c\cdot s]\times G=[2^c\cdot k]\times G+[2^c\cdot H(R||P||m)\cdot pk]\times G=2^c\times R+[2^c\cdot H(R||P||m)]\times P [2c⋅s]×G=[2c⋅k]×G+[2c⋅H(R∣∣P∣∣m)⋅pk]×G=2c×R+[2c⋅H(R∣∣P∣∣m)]×P

EdDSA具有与Schnorr签名类似的线性特征，从而也支持batch validation和key aggregation。

3. Ed25519

Ed25519是EdDSA的实例化，采用的为Curve25519曲线，hash函数选择的为SHA-512，使得 b = 256 b=256 b=256。

4. ZCash中的Ed25519

由于ZCash要求所有节点对Ed25519达成共识，仍需额外处理 在RFC8032 中未提到的一些边缘情况： 具体的代码实现参见：

• https://github.com/ZcashFoundation/ed25519-zebra

在该代码实现中，VerificationKey对应为验签的公钥，SigningKey对应为签名的私钥。 在该代码库中，除实现了单个验签之外，还实现了batch验签。

参考资料

[1] Solana Issue BIP32 [2] Solana Vanity Address using GPUs [3] Cryptography behind top 20 cryptocurrencies