区块链中的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月)
Name | Type | Signing alg | Curve | Hash | Address encoding | Address hash |
---|---|---|---|---|---|---|
Bitcoin | UTXO | ECDSA | secp256k1 | SHA-256 | base58, bech32 | SHA-256, RIPEMD-160 |
Ethereum | account | ECDSA | secp256k1 | Keccak-256 * | none (just hex) * | last 20B of Keccak-256 * |
XRP | account | ECDSA * | secp256k1 * | first half of SHA-512 | base58 with different alphabet * | SHA-256, RIPEMD-160 |
Litecoin | UTXO | ECDSA | secp256k1 | SHA-256 * | base58, bech32 | SHA-256, RIPEMD-160 |
EOS | account | ECDSA | secp256k1 | SHA-256 | none * | none * |
Bitcoin Cash | Same as Bitcoin * | |||||
Stellar | account | EdDSA | ed25519 | SHA-256 and SHA-512 in EdDSA * | base32 | none |
Binance Coin | Ethereum ERC-20 token * | |||||
Tether | Bitcoin Omni layer / Ethereum ERC-20 token | |||||
TRON | account | ECDSA | secp256k1 | SHA-256 | base58 | last 20 bytes of Keccak-256 * |
Cardano | UTXO | EdDSA | ed25519 | none and SHA-512 in EdDSA * | base58 | none |
Monero | UTXO * | it's complicated* | ed25519 | Keccak-256 * | base58 | Keccak-256 * |
IOTA | UTXO | Winternitz one time signature scheme | - | Curl, Kerl * | none | Kerl |
Dash | UTXO | ECDSA | secp256k1 | SHA-256 * | base58 | SHA-256, RIPEMD-160 |
Maker | Ethereum ERC-20 token | |||||
NEO | account | ECDSA | secp256r1 | SHA-256 | base58 | SHA-256, RIPEMD-160 |
Ontology | account | ECDSA | nist256p1 | 3x SHA-256 | base58 | SHA-256, RIPEMD-160 |
Ethereum Classic | Same as Ethereum | |||||
NEM | account | EdDSA | ed25519 | none and Keccak-256 in EdDSA * | base32 | Keccak-256, RIPEMD-160 |
Zcash | UTXO | ECDSA, zk-SNARKs * | secp256k1, Jubjub * | SHA-256 | base58, bech32 | SHA-256, RIPEMD-160 |
Tezos | account | EdDSA, ECDSA * | ed25519, secp256k1, secp256r1 | BLAKE2 and SHA-512 in EdDSA * | base58 | BLAKE2 |
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
q
q
- 曲线
E
E
F
q
mathbb{F}_q
n
=
#
E
(
F
q
)
=
2
c
l
n=#E(mathbb{F}_q)=2^cl
l
l
2
c
2^c
- 具有order
l
l
G
∈
E
(
F
q
)
Gin E(mathbb{F}_q)
- hash函数
H
H
2
b
2b
2
b
−
1
>
q
2^{b-1}>q
F
q
mathbb{F}_q
E
(
F
q
)
E(mathbb{F}_q)
b
b
EdDSA签名机制的安全性取决于以上参数的选择:
-
Pollard’s rho algorithm for logarithms 解决discrete logarithm近似需要约
l
π
/
4
sqrt{lpi/4}
l
l
2
200
2^{200}
l
l
q
q
#
E
(
F
q
)
=
2
c
l
# E(mathbb{F}_q)=2^cl
q
+
1
q+1
2
q
2sqrt{q}
- 在分析EdDSA安全性时,hash函数
H
H
公私钥对
(
p
k
,
P
)
(pk,P)
(pk,P),其中公钥
P
=
p
k
×
G
P=pktimes G
P=pk×G,椭圆曲线order为
n
=
2
c
⋅
l
n=2^ccdot l
n=2c⋅l,
G
G
G为所选椭圆曲线order 为
l
l
l的base point。
EdDSA对消息
m
m
m的签名过程为:
- 1)选择随机值
k
∈
R
[
1
,
l
−
1
]
kin_R [1,l-1]
- 2)计算curve point
R
=
k
×
G
R=ktimes G
- 3)计算hash值
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
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^ccdot s]times G=[2^ccdot k]times G+[2^ccdot H(R||P||m)cdot pk]times G=2^ctimes R+[2^ccdot H(R||P||m)]times 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 中未提到的一些边缘情况:
具体的代码实现参见:
在该代码实现中,VerificationKey对应为验签的公钥,SigningKey对应为签名的私钥。
在该代码库中,除实现了单个验签之外,还实现了batch验签。
参考资料
[1] Solana Issue BIP32
[2] Solana Vanity Address using GPUs
[3] Cryptography behind top 20 cryptocurrencies