Ao escrever sobre como desenvolver aplicativos seguros, um dos conselhos mais comuns é: não escreva criptografia você mesmo, mas use alguma biblioteca confiável. Infelizmente, ao desenvolver blockchains, esse conselho geralmente não funciona: os algoritmos necessários não são implementados ou as implementações existentes não são adequadas por muitas razões possíveis - até porque não são suficientemente seguras . Também neste caso, foi necessário verificar as assinaturas usando Ed25519 - um tipo de assinatura muito popular para o qual existem muitas implementações, nenhuma das quais, no entanto, nos é adequada. Isso ocorre porque a verificação teve que ser realizada a partir de um contrato inteligente em execução no blockchain Ethereum.
- — , « ». : , , - , , , . - : , , , , - ́ . - - , . , , .
Qual é o problema?
No Ethereum, os contratos inteligentes são executados em um ambiente especial - a chamada máquina virtual Ethereum (EVM).
EVM — , -. : , , — , . , , -, .
EVM , , . , , , , , . - . EVM , , , , EVM. EVM-, - Ed25519 — , , , , . , EVM , — Solidity.
EVM difere significativamente tanto de arquiteturas de processador populares quanto de máquinas virtuais abstratas comumente usadas, como JVM ou WASM. Enquanto a maioria das arquiteturas contém operações de 32 e 64 bits, no EVM o único tipo de dados é um inteiro de 256 bits. Isso é muito conveniente para a implementação do Ed25519, uma vez que todos os cálculos necessários são executados em números que cabem em 256 bits.
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) .
!