在撰写有关如何开发安全应用程序的文章时,最常见的建议之一是:不要自己写加密,而要使用一些受信任的库。不幸的是,在开发区块链时,该建议通常不起作用:所需的算法根本没有实现,或者由于许多可能的原因(即使它们不够安全),现有的实现也不适合。在这种情况下,也有必要使用Ed25519检查签名-Ed25519是一种非常流行的签名类型,其实现方式很多,但是没有一种适合我们。这是因为验证必须从在以太坊区块链上运行的智能合约中执行。
- — , « ». : , , - , , , . - : , , , , - ́ . - - , . , , .
问题是什么?
在以太坊中,智能合约在特殊的环境中执行-所谓的以太坊虚拟机(EVM)。
EVM — , -. : , , — , . , , -, .
EVM , , . , , , , , . - . EVM , , , , EVM. EVM-, - Ed25519 — , , , , . , EVM , — Solidity.
EVM与流行的处理器体系结构和常用的抽象虚拟机(例如JVM或WASM)都存在显着差异。尽管大多数体系结构都包含32位和64位操作,但是在EVM中,唯一的数据类型是256位整数。这对于Ed25519的实现非常方便,因为所有必需的计算都是针对适合256位的数字执行的。
Ed25519 — Curve25519. , , — . , , , — . .
. — , , , — . : — , — ( — , ). , , , , ( ).
Ed25519 . SHA-512 , ( ) : ( — -, , ). — . . , , , , .
, . , . , , , , .
EVM — . «» , EVM , - . , (gas), , , , . : , . , , 256- , , , . EVM . , , , EVM .
EVM : , (storage). , -. . , , , , . Ed25519 . , , . , Solidity - ( Solidity «» , ). , Solidity (, ), . Solidity JavaScript.
, , JavaScript-, Solidity, Solidity.
: - SHA-512
, Ed25519 — - SHA-512. . EVM -: SHA-256, Keccak-256 ( SHA-3-256), RIPEMD-160, SHA-512 . SHA-512 . EVM — , Solidity . 1024 , 16 . , 16, — , , , .
SHA-512 — :
w[0..15] :=
for i in 16 .. 79:
s0 := (w[i-15] ror 1) ^ (w[i-15] ror 8) ^ (w[i-15] >> 7)
s1 := (w[i-2] ror 19) ^ (w[i-2] ror 61) ^ (w[i-2] >> 6)
w[i] := w[i-16] + s0 + w[i-7] + s1
a, b, c, d, e, f, g, h := h0, h1, h2, h3, h4, h5, h6, h7
for i in 0 .. 79:
S0 := (a ror 28) ^ (a ror 34) ^ (a ror 39)
S1 := (e ror 14) ^ (e ror 18) ^ (e ror 41)
ch := (e & f) ^ (~e & g)
maj := (a & b) ^ (a & c) ^ (b & c)
temp1 := h + S1 + ch + k[i] + w[i]
temp2 := S0 + maj
a, b, c, d, e, f, g, h := temp1 + temp2, a, b, c, d + temp1, e, f, g
h0, h1, h2, h3 := h0 + a, h1 + b, h2 + c, h3 + d
h4, h5, h6, h7 := h4 + e, h5 + f, h6 + g, h7 + h
, 16 , , . , : , , , , . : (e & f) ^ (~e & g)
(e & (f ^ g)) ^ g
, (a & b) ^ (a & c) ^ (b & c)
— (a & (b | c)) | (b & c)
( (a & (b ^ c)) ^ (b & c)
). : x
, x | (x << 64)
( x
, 64). , x | (x << 64)
.
w[i]
w[i-2]
(. . w[i-1]
), w
( 256- SIMD). , .
: 16 w
, 16 , , . w
, , . ( 16 ) , , 4,5 .
: . Curve25519 , : , . : , , , . , 32 . , , .
. , , , . . , . , . Ed25519 ( , ):
- .
- , .
- , , .
- , .
? , , , . ( ), , . , . , , .
, : . , . , , ( ).
, , . , ( ), , , -: , . , , — .
. , . — « » (double-and-add), :
result := 0
for bit_index in n-1 .. 0:
result := double(result)
if s & (1<<bit_index) != 0:
result := add(result, G)
if h & (1<<bit_index) != 0:
result := subtract(result, A)
— . , , ( ). ( ) , , . . , «» , , . , , ! :
result := 0
for bit_index in n-1 .. k:
result := double(result)
if s & (1<<bit_index) != 0:
result := add(result, Gmul[s >> (bit_index-k)])
s := s & ((1 << (bit_index-k)) - 1)
if h & (1<<bit_index) != 0:
result := subtract(result, Amul[h >> (bit_index-k)])
h := h & ((1 << (bit_index-k)) - 1)
, , , . «» , . , : . :
- , . , — . , .
- . , , . , , ( ), . , : ( , ), :
result := subtract(result, Amul[(1 << k) + h])
, , , , .
, , .
: , . , . EVM , . — Explicit-Formulas Database. , Curve25519. , . , EFD, , , , . : , . , , -2 -4 (. ), , ( ). «madd-2008-hwcd-3» «dbl-2008-hwcd» ( ). , .
-, . (extended projective coordinates) — , , , , . , , , — . , , , , , , , ( , ). , , , , - .
-, . madd (mixed addition) — , , . : ; , , . : . (, , libsodium) 2, EVM , . :
// :
// 1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
// 2: (s2, d2, t2), s2=(y+x)/2, d2=(y-x)/2, t2=x*y*d.
// :
// 3: (x3, u3, y3, v3), x=x3/u3, y=y3/v3.
// (x4, y4, z4, t4) - , 1, .
x4 := x1 * v1
y4 := y1 * u1
z4 := u1 * v1
t4 := x1 * y1
// . madd-2008-hwcd-3.
s4 := y4 + x4
d4 := y4 - x4
a := d4 * d2 // (y4-x4)*(y2-x2)/2, A/2.
b := s4 * s2 // (y4+x4)*(y2+x2)/2, B/2.
c := t4 * t2 // C/2.
// D/2 - z4, .
x3 := b - a // E/2.
u3 := z4 + c // G/2.
y3 := b + a // H/2.
v3 := z4 - c // F/2.
// x3, u3, y3, v3 E, G, H, F 1/2, , x3/u3 y3/v3 .
:
// :
// 1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
// :
// 2: (x2, u2, y2, v2), x=x2/u2, y=y2/v2.
// (x3, y3, z3) - , 1, . t3 .
x3 := x1 * v1
y3 := y1 * u1
z3 := u1 * v1
// . dbl-2008-hwcd.
xx := x3 * x3 // A.
yy := y3 * y3 // B.
xy := x3 * y3 // E 2xy, , .
zz := z3 * z3
x2 := xy + xy // E.
u2 := yy - xx // G.
y2 := yy + xx // -H.
v2 := zz + zz - u2 // -F.
// , -1 y2 v2 .
: addmod
( ). , , ( ), 256- . , , , . , , .
, . : , . — ( ), , : , . , . , . .
, NEAR . - Rust AssemblyScript ( TypeScript) .
!