Apakah mungkin untuk menghasilkan angka acak jika kita tidak percaya satu sama lain? Bagian 2

Halo, Habr!

Pada bagian pertama artikel, kita membahas mengapa mungkin perlu membuat bilangan acak untuk peserta yang tidak saling percaya, persyaratan apa yang diajukan untuk pembuat bilangan acak tersebut, dan mempertimbangkan dua pendekatan untuk implementasinya.

, .

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

, .

!