¿Es posible generar números aleatorios si no confiamos el uno en el otro? Parte 2

¡Hola, Habr!

En la primera parte del artículo, discutimos por qué podría ser necesario generar números aleatorios para participantes que no confían entre sí, qué requisitos se proponen para tales generadores de números aleatorios y consideramos dos enfoques para su implementación.

, .

, , , . : , , (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 .

, .

!