お互いを信頼していなければ、ランダムな数字を生成することは可能ですか？パート2

こんにちは、Habr！

最初の部分、要件は、このような乱数発生器のために提唱し、その実施に二つのアプローチが考えられるもの、お互いを信頼していない参加者のための乱数を生成する必要があるかもしれないなぜ記事、我々は議論しました。

, .

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

, .

!