区块链中的Ed25519

1. 引言

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

Ed25519相关代码实现有:

详细可参看: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 ECDSA secp256k1 Keccak-256 * none (just hex) * last 20B of Keccak-256 *
XRP ECDSA * secp256k1 * first half of SHA-512 base58 with different alphabet * SHA-256, RIPEMD-160
Litecoin ECDSA secp256k1 SHA-256 * base58, bech32 SHA-256, RIPEMD-160
EOS ECDSA secp256k1 SHA-256 none * none *
Bitcoin Cash Same as Bitcoin *
Stellar 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 ECDSA secp256k1 SHA-256 base58 last 20 bytes of Keccak-256 *
Cardano EdDSA ed25519 none and SHA-512 in EdDSA * base58 none
Monero it's complicated* ed25519 Keccak-256 * base58 Keccak-256 *
IOTA Winternitz one time signature scheme - Curl, Kerl * none Kerl
Dash ECDSA secp256k1 SHA-256 * base58 SHA-256, RIPEMD-160
Maker Ethereum ERC-20 token
NEO ECDSA secp256r1 SHA-256 base58 SHA-256, RIPEMD-160
Ontology ECDSA nist256p1 3x SHA-256 base58 SHA-256, RIPEMD-160
Ethereum Classic Same as Ethereum
NEM EdDSA ed25519 none and Keccak-256 in EdDSA * base32 Keccak-256, RIPEMD-160
Zcash ECDSA, zk-SNARKs * secp256k1, Jubjub * SHA-256 base58, bech32 SHA-256, RIPEMD-160
Tezos EdDSA, ECDSA * ed25519, secp256k1, secp256r1 BLAKE2 and SHA-512 in EdDSA * base58 BLAKE2

2. 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

    )

    Gin E(mathbb{F}_q)

    GE(Fq)

  • hash函数

    H

    H

    H,其输出为

    2

    b

    2b

    2b bits,其中

    2

    b

    1

    >

    q

    2^{b-1}>q

    2b1>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{lpi/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

    2sqrt{q}

    2q

  • 在分析EdDSA安全性时,hash函数

    H

    H

    H通常model为random oracle。

公私钥对

(

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=2cl

G

G

G为所选椭圆曲线order 为

l

l

l的base point。
EdDSA对消息

m

m

m的签名过程为:

  • 1)选择随机值

    k

    R

    [

    1

    ,

    l

    1

    ]

    kin_R [1,l-1]

    kR[1,l1]

  • 2)计算curve point

    R

    =

    k

    ×

    G

    R=ktimes G

    R=k×G

  • 3)计算hash值

    e

    =

    H

    (

    R

    P

    m

    )

    e=H(R||P||m)

    e=H(RPm)

  • 4)计算

    s

    =

    k

    +

    H

    (

    R

    P

    m

    )

    p

    k

    s= k+ H(R||P||m)cdot pk

    s=k+H(RPm)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

    [2cs]×G=[2ck]×G+[2cH(RPm)pk]×G=2c×R+[2cH(RPm)]×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

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>