Có thể tạo số ngẫu nhiên nếu chúng ta không tin tưởng lẫn nhau? Phần 2

Này Habr!

В phần đầu tiên Trong bài viết này, chúng tôi đã thảo luận lý do tại sao cần tạo số ngẫu nhiên cho những người tham gia không tin tưởng lẫn nhau, những yêu cầu nào được đưa ra đối với các trình tạo số ngẫu nhiên như vậy và xem xét hai cách tiếp cận để triển khai chúng.

Trong phần này của bài viết, chúng ta sẽ xem xét kỹ hơn một cách tiếp cận khác sử dụng chữ ký ngưỡng.

Một chút mật mã

Để hiểu cách hoạt động của chữ ký ngưỡng, bạn cần hiểu một chút về mật mã cơ bản. Chúng ta sẽ sử dụng hai khái niệm: vô hướng hoặc đơn giản là số mà chúng ta sẽ biểu thị bằng chữ thường (x, y) và các điểm trên đường cong elip mà chúng ta sẽ ký hiệu bằng chữ in hoa.

Để hiểu những điều cơ bản về chữ ký ngưỡng, bạn không cần phải hiểu cách hoạt động của đường cong elip, ngoài một số điều cơ bản:

1. Các điểm trên đường cong elip có thể được cộng và nhân với một số vô hướng (chúng ta sẽ biểu thị phép nhân với một số vô hướng như sau: xG, mặc dù ký hiệu Gx cũng thường được sử dụng trong văn học). Kết quả của phép cộng và nhân với số vô hướng là một điểm trên đường cong elip.

2. Chỉ biết điểm G và tích của nó với một đại lượng vô hướng xG không thể tính được x.

Chúng ta cũng sẽ sử dụng khái niệm đa thức p (x) độ k-1. Cụ thể, chúng ta sẽ sử dụng tính chất sau của đa thức: nếu chúng ta biết giá trị p (x) bất cứ gì k khác nhau x (và chúng tôi không có thêm thông tin về p (x)), chúng ta có thể tính toán p (x) cho bất cứ ai khác x.

Điều thú vị là với mọi đa thức p (x) và một số điểm trên đường cong Gbiết ý nghĩa p(x)G bất cứ gì k những nghĩa khác nhau x, chúng ta cũng có thể tính toán p(x)G bất cứ gì x.

Đây là thông tin đủ để tìm hiểu chi tiết về cách hoạt động của chữ ký ngưỡng và cách sử dụng chúng để tạo số ngẫu nhiên.

Trình tạo số ngẫu nhiên trên chữ ký ngưỡng

Hãy nói rằng n người tham gia muốn tạo một số ngẫu nhiên và chúng tôi muốn mọi người tham gia k có đủ chúng để tạo ra một con số, nhưng để những kẻ tấn công kiểm soát k-1 người tham gia trở xuống không thể dự đoán hoặc ảnh hưởng đến số lượng được tạo ra.

Giả sử có một đa thức như vậy p (x) độ k-1 những gì người tham gia đầu tiên biết p (1), người thứ hai biết p(2), và như thế (n-th biết p(n)). Chúng tôi cũng giả định rằng đối với một số điểm được xác định trước G mọi người đều biết p(x)G cho tất cả các giá trị x. Chúng tôi sẽ gọi số Pi) “thành phần riêng tư” ingười tham gia (vì chỉ ingười tham gia thứ biết cô ấy), và con lợn “thành phần công cộng” i-người tham gia thứ (vì tất cả những người tham gia đều biết cô ấy). Như bạn còn nhớ, kiến ​​thức con lợn không đủ để khôi phục số Pi).

Tạo một đa thức sao cho chỉ i-Người tham gia thứ ba và không ai khác biết thành phần riêng tư của anh ta - đây là phần phức tạp và thú vị nhất của giao thức và chúng tôi sẽ phân tích nó bên dưới. Bây giờ, hãy giả sử rằng chúng ta có một đa thức như vậy và tất cả những người tham gia đều biết các thành phần riêng tư của họ.

Làm thế nào chúng ta có thể sử dụng đa thức như vậy để tạo ra một số ngẫu nhiên? Để bắt đầu, chúng ta cần một số chuỗi trước đây chưa được sử dụng làm đầu vào cho trình tạo. Trong trường hợp blockchain, hàm băm của khối cuối cùng h là một ứng cử viên tốt cho một dòng như vậy. Cho phép người tham gia muốn tạo một số ngẫu nhiên bằng cách sử dụng h giống như hạt giống. Người tham gia chuyển đổi đầu tiên h đến một điểm trên đường cong bằng cách sử dụng bất kỳ hàm được xác định trước nào:

H = vô hướngToPoint(h)

Sau đó mỗi người tham gia i tính toán và công bố Xin chào = p(i)H, họ có thể làm gì vì họ biết p(i) và H. Tiết lộ Htôi không cho phép những người tham gia khác khôi phục thành phần riêng tư ingười tham gia và do đó một bộ thành phần riêng tư có thể được sử dụng từ khối này sang khối khác. Do đó, thuật toán tạo đa thức đắt tiền được mô tả dưới đây chỉ cần được thực thi một lần.

Khi k những người tham gia đã được khám nghiệm tử thi Xin chào = p(i)H, mọi người đều có thể tính toán Hx = p(x)H cho tất cả x nhờ vào tính chất của đa thức mà chúng ta đã thảo luận ở phần trước. Lúc này, tất cả người tham gia tính toán H0 = p(0)H, và đây là số ngẫu nhiên thu được. Xin lưu ý rằng không ai biết p(0), và do đó cách duy nhất để tính toán p(0)H – đây là phép nội suy p(x)H, điều đó chỉ có thể thực hiện được khi k giá trị p(i)H được biết đến. Mở bất kỳ số lượng nhỏ hơn p(i)H không cung cấp bất kỳ thông tin nào về p(0)H.

Trình tạo ở trên có tất cả các thuộc tính mà chúng tôi mong muốn: kẻ tấn công chỉ kiểm soát k-1 người tham gia hoặc ít hơn không có thông tin hoặc ảnh hưởng đến kết luận, trong khi bất kỳ k người tham gia có thể tính toán số kết quả và bất kỳ tập hợp con nào của k những người tham gia sẽ luôn đạt được kết quả như nhau cho cùng một hạt giống.

Có một vấn đề mà chúng tôi đã cẩn thận tránh ở trên. Để nội suy hoạt động, điều quan trọng là giá trị Htôi được xuất bản bởi mỗi người tham gia i nó thực sự giống nhau p(i)H. Vì không có ai ngoại trừ i-người tham gia thứ 2 không biết số Pi), không ai ngoại trừ i-người tham gia không thể xác minh rằng Hi thực sự được tính toán chính xác và không có bất kỳ bằng chứng mật mã nào về tính chính xác Htôi kẻ tấn công có thể xuất bản bất kỳ giá trị nào Chào, và tùy ý ảnh hưởng đến đầu ra của bộ tạo số ngẫu nhiên:

Các giá trị khác nhau của H_1 do người tham gia đầu tiên gửi dẫn đến kết quả H_0 khác nhau

Có ít nhất hai cách chứng minh tính đúng Hi, chúng ta sẽ xem xét chúng sau khi phân tích việc tạo đa thức.

Thế hệ đa thức

Trong phần trước chúng ta đã giả sử rằng chúng ta có một đa thức như vậy p (x) độ k-1 là người tham gia i biết số Pi)và không ai khác có bất kỳ thông tin nào về giá trị này. Trong phần tiếp theo, chúng ta cũng sẽ cần điều đó đối với một số điểm được xác định trước G mọi người đều biết p(x)G cho tất cả x.

Trong phần này, chúng tôi sẽ giả định rằng mỗi người tham gia cục bộ có một số khóa riêng xi, sao cho mọi người đều biết khóa công khai tương ứng Xi.

Một giao thức tạo đa thức có thể có như sau:

1. Mỗi người tham gia i cục bộ tạo ra một đa thức tùy ý pi(x) độ k-1. Sau đó họ gửi từng người tham gia j giá trị pi(j), được mã hóa bằng khóa chung Xj. Như vậy chỉ i-th и j-th người tham gia biết ptôi (j). Người tham gia i cũng công bố công khai pi(j)G cho tất cả j từ 1 để k bao gồm.

2. Tất cả những người tham gia đều sử dụng sự đồng thuận nhất định để lựa chọn k những người tham gia mà đa thức của họ sẽ được sử dụng. Vì một số người tham gia có thể ngoại tuyến nên chúng tôi không thể đợi cho đến khi mọi người tham gia n người tham gia sẽ công bố đa thức. Kết quả của bước này là một tập hợp Z bao gồm ít nhất k đa thức được tạo ở bước (1).

3. Người tham gia đảm bảo rằng các giá trị họ biết pi(j) tương ứng với công bố công khai pi(j)G. Sau bước này Z chỉ các đa thức được truyền riêng pi(j) tương ứng với công bố công khai pi(j)G.

4. Mỗi người tham gia j tính toán thành phần riêng của nó p(j) như một khoản tiền ptôi (j) cho tất cả i в Z. Mỗi người tham gia cũng tính toán tất cả các giá trị p(x)G như một khoản tiền pi(x)G với mọi thứ i в Z.

Xin lưu ý rằng p(x) – nó thực sự là một đa thức k-1, bởi vì nó là tổng của cá nhân pi(x), mỗi trong số đó là một đa thức bậc k-1. Sau đó, lưu ý rằng trong khi mỗi người tham gia j biết p(j), họ không có thông tin về p (x) cho x ≠ j. Thật vậy, để tính được giá trị này, họ cần phải biết mọi thứ số pi(x), và miễn là người tham gia j không biết ít nhất một trong các đa thức đã chọn, họ không có đủ thông tin về p(x).

Đây là toàn bộ quá trình tạo đa thức cần thiết trong phần trước. Các bước 1, 2 và 4 ở trên có cách thực hiện khá rõ ràng. Nhưng bước 3 không tầm thường như vậy.

Cụ thể, chúng ta cần có khả năng chứng minh rằng pi(j) thực sự tương ứng với những cái đã xuất bản pi(j)G. Nếu chúng ta không thể chứng minh điều đó, kẻ tấn công i thay vào đó có thể gửi rác pi(j) tới người tham gia j, và người tham gia j sẽ không thể có được giá trị thực pi(j), và sẽ không thể tính toán thành phần riêng tư của nó.

Có một giao thức mã hóa cho phép bạn tạo một tin nhắn bổ sung bằng chứngi(j), sao cho bất kỳ người tham gia nào, có giá trị nào đó e, cũng như bằng chứng(j) и pi(j)G, có thể xác minh cục bộ rằng e - nó thực sự pi(j), được mã hóa bằng khóa của người tham gia j. Thật không may, quy mô của bằng chứng như vậy là vô cùng lớn và cần phải công bố O (nk) Bằng chứng như vậy không thể được sử dụng cho mục đích này.

Thay vì chứng minh rằng pi(j) phù hợp với pi(j)G chúng ta có thể phân bổ một khoảng thời gian rất lớn trong giao thức tạo đa thức, trong đó tất cả những người tham gia kiểm tra mã hóa nhận được pi(j), và nếu tin nhắn được giải mã không tương ứng với công chúng pi(j)G, họ công bố bằng chứng mật mã cho thấy tin nhắn mã hóa mà họ nhận được là không chính xác. Chứng minh rằng thông điệp không phù hợp với con lợn) dễ dàng hơn nhiều so với việc chứng minh rằng nó phù hợp. Cần lưu ý rằng điều này yêu cầu mỗi người tham gia phải xuất hiện trực tuyến ít nhất một lần trong thời gian được phân bổ để tạo ra bằng chứng đó và dựa trên giả định rằng nếu họ công bố bằng chứng như vậy, nó sẽ đến tay tất cả những người tham gia khác trong cùng thời gian quy định.

Nếu một người tham gia không xuất hiện trực tuyến trong khoảng thời gian này và anh ta có ít nhất một thành phần không chính xác thì người tham gia cụ thể đó sẽ không thể tham gia vào quá trình tạo số tiếp theo. Tuy nhiên, giao thức sẽ vẫn hoạt động nếu có ít nhất k những người tham gia vừa nhận được đúng thành phần hoặc cố gắng để lại bằng chứng về sự không chính xác trong thời gian quy định.

Chứng minh tính đúng đắn của H_i

Phần cuối cùng còn phải thảo luận là làm thế nào để chứng minh tính đúng đắn của Htôi, cụ thể là cái đó Xin chào = p(i)H, không cần mở số Pi).

Chúng ta hãy nhớ rằng các giá trị H, G, p(i)G công khai và được mọi người biết đến. Nhận hoạt động số Pi) hiểu biết con lợn и G được gọi là logarit rời rạc, hoặc dlog, và chúng tôi muốn chứng minh rằng:

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

không tiết lộ số Pi). Ví dụ, các công trình cho những bằng chứng như vậy tồn tại Giao thức Schnorr.

Với thiết kế này, mỗi người tham gia cùng với Hi gửi bằng chứng về tính đúng đắn theo thiết kế.

Khi một số ngẫu nhiên được tạo ra, nó thường cần được sử dụng bởi những người tham gia không phải là những người đã tạo ra nó. Những người tham gia như vậy, cùng với số lượng, phải gửi tất cả Hi và các bằng chứng liên quan.

Một độc giả tò mò có thể hỏi: vì số ngẫu nhiên cuối cùng là H0 và p(0)G – Đây là thông tin công khai, tại sao chúng ta cần bằng chứng cho từng cá nhân? Htôi, tại sao không gửi bằng chứng thay thế

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

Vấn đề là không thể tạo ra bằng chứng như vậy bằng Giao thức Schnorr vì không ai biết giá trị p (0), cần thiết để tạo ra bằng chứng, và hơn thế nữa, toàn bộ trình tạo số ngẫu nhiên dựa trên thực tế là không ai biết giá trị này. Vì vậy cần phải có tất cả các giá trị Hi và bằng chứng cá nhân của họ để chứng minh tính đúng đắn H0.

Tuy nhiên, nếu có một số phép toán trên các điểm trên đường cong elip tương tự về mặt ngữ nghĩa với phép nhân thì chứng minh tính đúng đắn H0 sẽ là tầm thường, chúng tôi chỉ đơn giản là đảm bảo rằng

H0 × G = p(0)G × H

Nếu đường cong đã chọn hỗ trợ cặp đường cong elip, bằng chứng này hoạt động. Trong trường hợp này H0 không chỉ là đầu ra của bộ tạo số ngẫu nhiên mà bất kỳ người tham gia nào biết G,H и p(0)G. H0 cũng là chữ ký trên tin nhắn được sử dụng làm hạt giống, xác nhận rằng k и n người tham gia đã ký tin nhắn này. Như vậy, nếu hạt giống - là hàm băm của khối trong giao thức blockchain, thì H0 vừa là chữ ký đa năng trên một khối vừa là số ngẫu nhiên rất tốt.

Kết luận

Bài viết này là một phần của loạt blog kỹ thuật NEAR. NEAR là một giao thức và nền tảng blockchain để phát triển các ứng dụng phi tập trung với trọng tâm là tính dễ phát triển và dễ sử dụng cho người dùng cuối.

Mã giao thức mở, việc triển khai của chúng tôi được viết bằng Rust, có thể tìm thấy nó đây.

Bạn có thể xem quá trình phát triển cho NEAR trông như thế nào và thử nghiệm trong IDE trực tuyến đây.

Bạn có thể theo dõi tất cả tin tức bằng tiếng Nga tại nhóm điện tín và nhóm trên VKontakte, và bằng tiếng Anh trong bản chính thức twitter.

Hẹn sớm gặp lại!

Nguồn: www.habr.com