É possível gerar números aleatórios se não confiarmos uns nos outros? Parte 2

Olá, Habr!

Na primeira parte do artigo, discutimos por que pode ser necessário gerar números aleatórios para participantes que não confiam uns nos outros, quais requisitos são apresentados para esses geradores de números aleatórios e consideramos duas abordagens para sua implementação.

, .

, , , . : , , (x, y) , .

, :

1. ( xG, G^x ). -- .

2. G xG x.

p(x) k-1. , : p(x) k x ( p(x)), p(x) x.

, p(x) G, p(x)G k x, p(x)G x.

, , , .

n , , k , , k-1 , .

p(x) k-1, p(1), p(2), (n- p(n)). , G p(x)G x. p(i) “ ” i- ( i- ), p(i)G “ ” i- ( ). , p(i)G p(i).

, i- – , . , , .

, ? , . h -- . , h seed. h :

H = scalarToPoint(h)

i H_i = p(i)H, , p(i) H. H_i i- , . , , , .

k H_i = p(i)H, H_x = p(x)H x , . H₀ = p(0)H, . , p(0), p(0)H – p(x)H, k p(i)H . p(i)H p(0)H.

, : , k-1 , , , k , k seed.

, . , H_i i p(i)H. i- p(i), i- H_i , - H_i H_i, :

H_i, , .

, p(x) k-1 i p(i), . G p(x)G x.

, x_i, X_i.

:

1. i p_i(x) k-1. j p_i(j), X_j. i- j- p_i(j). i p_i(j)G j 1 k .

2. k , . , n . – Z k , (1).

3. , p_i(j) p_i(j)G. Z , p_i(j) p_i(j)G.

4. j p(j) p_i(j) i Z. p(x)G p_i(x)G i Z.

, p(x) – k-1, p_i(x), – k-1. , , j p(j), p(x) x ≠ j. , , p_i(x), j , p(x).

, . 1, 2 4 . 3 .

, , p_i(j) p_i(j)G. , i p_i(j) j, j p_i(j), .

, proof_i(j), , e, proof_i(j) p_i(j)G, , e – p_i(j), j. , , O(nk) , .

, , p_i(j) p_i(j)G , p_i(j), p_i(j)G, , . , p_i(G) , , . , , , , , , .

, , . , , , k , , .

H_i

, , H_i, H_i = p(i)H, p(i).

, H, G, p(i)G . p(i) p(i)G G , dlog, , :

dlog(p(i)G, G) = dlog(H_i, H)

p(i). , Schnorr Protocol.

, H_i .

, , , . H_i .

: – H₀, p(0)G – , Hi, ,

dlog(p(0)G, G) = dlog(H₀, H)

, Schnorr Protocol , p(0), , , , . H_i , H₀.

, - , , H₀ , ,

H₀ × G = p(0)G × H

elliptic curve pairings, . H₀ – , , G, H p(0)G. H₀ – , seed, , k n . , seed – , H₀ – - , .

– NEAR. NEAR – , .

, Rust, .

NEAR, -IDE .

, .

!