Saat menulis tentang cara mengembangkan aplikasi yang aman, salah satu tip paling umum adalah: jangan menulis kripto sendiri, tetapi gunakan beberapa pustaka tepercaya. Sayangnya, saat mengembangkan blockchain, saran ini sering tidak berfungsi: algoritme yang diperlukan tidak diterapkan sama sekali, atau implementasi yang ada tidak cocok karena banyak kemungkinan alasan - bahkan karena algoritme tersebut tidak cukup aman . Dalam kasus ini, juga , perlu untuk memverifikasi tanda tangan menggunakan Ed25519 - jenis tanda tangan yang sangat populer yang ada banyak penerapannya, namun tidak satupun yang cocok untuk kita. Ini karena verifikasi harus dilakukan dari kontrak pintar yang berjalan di blockchain Ethereum.

Apa masalahnya?

Di Ethereum, kontrak pintar dijalankan di lingkungan khusus - yang disebut mesin virtual Ethereum (EVM).

EVM berbeda secara signifikan baik dari arsitektur prosesor populer maupun dari mesin virtual abstrak yang umum digunakan seperti JVM atau WASM. Meskipun sebagian besar arsitektur berisi operasi 32 dan 64 bit, di EVM, satu-satunya tipe datanya adalah integer 256-bit. Ini sangat nyaman untuk implementasi Ed25519, karena semua kalkulasi yang diperlukan dilakukan pada angka yang sesuai dengan 256 bit.

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 $$$(x, y)$, : $$$x$ $$$y$, . : $$$y$ , , , $$$x$ . $$$p=2^{255}-19$, 32 . , , $$$x$.

$$$x$ $$$x=\pm\sqrt{(y^2-1)/(dy^2+1)}$. $$$-d$ $$$p$, , , $$$y$. . , . $$$\sqrt{u/v}$, $$$v\ne0$. Ed25519 ( , $$$p\equiv5\pmod8$):

• $$$\beta=uv^3(uv^7)^{(p-5)/8}$.
• $$$v\beta^2=u$, $$$\pm\beta$.
• , $$$v\beta^2=-u$, $$$\pm\sqrt{-1}\beta$.
• , .

? , $$$\beta^8=u^8v^{24}(uv^7)^{p-5}=u^{p+3}v^{7p-11}=(u/v)^4$, , $$$\beta^2=\pm u/v$ $$$\beta^2=\pm\sqrt{-1}u/v$. ( $$$u\ne0$), $$$u/v$ , $$$\sqrt{-1}$ . $$$\beta^2=-u/v$, $$$(\sqrt{-1}\beta)^2=u/v$. , , .

, : $$$\beta=uv^3(uv^7)^{(p-5)/8}$ $$$\beta=u(uv)^{(p-5)/8}$. $$$\beta^8=u^8(uv)^{p-5}=u^{p+3}v^{p-5}=(u/v)^4$, . , $$$v$ $$$v^{2^{250}-1}$ $$$v^{11}$ $$$p$, $$$p$ ( ).

, , $$$sG=R+hA$. , ($$$R$ $$$A$), , , -: $$$sG-hA$, $$$R$. , , — $$$sG-hA$.

. $$$sG$ $$$hA$, . — « » (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)

$$$n$ — $$$s$ $$$h$. $$$s$ $$$h$, , $$$G$ ( $$$A$). $$$n$ $$$n$ ( ) , , $$$s$ $$$h$ $$$0$ $$$1$ . . , «» $$$s$ $$$h$, , . , $$$k$ $$$A$ $$$G$ $$$2^k$ $$$2^{k+1}-1$, $$$k+1$ ! :

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)

, , , $$$k$ . «» $$$s$ $$$h$, . , : $$$k$ . :

• $$$s$ $$$G$ , $$$G$ . $$$s$ $$$2^k$, $$$G$ — $$$2^{-k}\bmod l$. , $$$2^k$ $$$k$ $$$s$ .
• $$$h$ $$$A$ . $$$h$ $$$2^{-k}\bmod l$ $$$2^k$, , $$$A$ $$$l$. $$$A$ $$$l$, $$$(h2^{-k}\bmod l)\cdot2^k$ $$$h$, $$$l$ $$$8l$ ( ), $$$2^{-k}$. , : $$$h$ $$$h+8l-2^k$ ( , $$$h-2^k$ $$$8l$), : result := subtract(result, Amul[(1 << k) + h]), , $$$k$ , $$$2^k$ , $$$A$ $$$2^k$ $$$2^{k+1}-1$.

$$$k=3$, , .

: , . , $$$p$ . EVM , . — Explicit-Formulas Database. , Curve25519. , . , EFD, , , , . : , . , , -2 -4 (. ), , ( ). «madd-2008-hwcd-3» «dbl-2008-hwcd» ( ). , .

-, . (extended projective coordinates) — $$$X$, $$$Y$, $$$Z$ $$$T$, $$$x=X/Z$, $$$y=Y/Z$ $$$xy=T/Z$. , $$$T$ , , — . , , $$$X$, $$$U$, $$$Y$ $$$V$, $$$x=X/U$ $$$y=Y/V$, , ( , $$$T$). $$$X$, $$$U$, $$$Y$, $$$V$, - $$$T$.

-, . madd (mixed addition) — , , . : ; , , . : $$$((y+x)/2, (y-x)/2, xyd)$. (, $$$(y+x, y-x, xy\cdot2d)$, 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 ( ). , $$$2^{255}$, ( ), 256- . , , , . , , .

, . : $$$x=X/U$ $$$y=Y/V$, $$$x$ $$$y$. — ( $$$p-2$), , : $$$(UV)^{-1}$, $$$U^{-1}=(UV)^{-1}V$ $$$V^{-1}=(UV)^{-1}U$. $$$R$, . , . .

, NEAR . - Rust AssemblyScript ( TypeScript) .

, NEAR, -IDE .

, .

!