When writing about how to develop secure applications, one of the most common advice is: don't write crypto yourself, but use some trusted library. Unfortunately, when developing blockchains, this advice often does not work: the required algorithms are either not implemented at all, or the existing implementations are not suitable for many possible reasons - even because they are not secure enough . In this case, too , it was necessary to check signatures using Ed25519 - a very popular type of signatures for which there are many implementations, none of which, however, suited us. This is because the verification had to be performed from a smart contract running on the Ethereum blockchain.

What is the problem?

In Ethereum, smart contracts are executed in a special environment - the so-called Ethereum virtual machine (EVM).

EVM differs significantly both from popular processor architectures and from commonly used abstract virtual machines such as JVM or WASM. While most architectures contain 32- and 64-bit operations, in EVM the only data type is a 256-bit integer. This is very convenient for the implementation of Ed25519, since all the necessary calculations are performed on numbers that fit into 256 bits.

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 .

, .

!