安全なアプリケーションを開発する方法について書くとき、最も一般的なヒントの1つは、自分で暗号を作成するのではなく、信頼できるライブラリを使用することです。残念ながら、ブロックチェーンを開発する場合、このアドバイスは機能しないことがよくあります。必要なアルゴリズムがまったく実装されていないか、既存の実装が十分に安全でないために、考えられる多くの理由で適切ではありません。この場合も、Ed25519を使用して署名をチェックする必要がありました。これは非常に人気のあるタイプの署名であり、多くの実装がありますが、どれも私たちには適していません。これは、Ethereumブロックチェーンで実行されているスマートコントラクトから検証を実行する必要があるためです。

何が問題ですか？

Ethereumでは、スマートコントラクトは特別な環境（いわゆるEthereum仮想マシン（EVM））で実行されます。

EVMは、一般的なプロセッサアーキテクチャと、JVMやWASMなどの一般的に使用される抽象仮想マシンの両方とは大きく異なります。ほとんどのアーキテクチャには32ビットと64ビットの数値を処理するための操作が含まれていますが、EVMでは唯一のデータタイプは256ビットの整数です。必要な計算はすべて256ビットに収まる数値で実行されるため、これはEd25519の実装に非常に便利です。

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 .

, .

!