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

Này Habr!

Trong bài viết này tôi sẽ nói về việc tạo ra các số giả ngẫu nhiên bởi những người tham gia không tin tưởng lẫn nhau. Như chúng ta sẽ thấy bên dưới, việc triển khai một máy phát điện “gần như” tốt thì khá đơn giản, nhưng để có một máy phát điện tốt thì rất khó.

Tại sao cần tạo số ngẫu nhiên giữa những người tham gia không tin tưởng lẫn nhau? Một lĩnh vực ứng dụng là các ứng dụng phi tập trung. Ví dụ: một ứng dụng chấp nhận đặt cược từ một người tham gia và nhân đôi số tiền với xác suất 49% hoặc loại bỏ với xác suất 51% sẽ chỉ hoạt động nếu nó có thể nhận được một số ngẫu nhiên một cách khách quan. Nếu kẻ tấn công có thể tác động đến kết quả của trình tạo số ngẫu nhiên và thậm chí tăng nhẹ cơ hội nhận được khoản thanh toán trong ứng dụng, hắn sẽ dễ dàng phá hủy nó.

Khi chúng tôi thiết kế một giao thức tạo số ngẫu nhiên phân tán, chúng tôi muốn nó có ba thuộc tính:

1. Anh ta phải khách quan. Nói cách khác, không người tham gia nào được phép gây ảnh hưởng đến kết quả của bộ tạo số ngẫu nhiên theo bất kỳ cách nào.

2. Anh ta hẳn là người không thể đoán trước được. Nói cách khác, không người tham gia nào có thể dự đoán số nào sẽ được tạo (hoặc suy ra bất kỳ thuộc tính nào của nó) trước khi nó được tạo.

3. Giao thức phải khả thi, nghĩa là có khả năng chống lại thực tế là một tỷ lệ phần trăm người tham gia nhất định ngắt kết nối mạng hoặc cố tình dừng giao thức.

Trong bài viết này, chúng ta sẽ xem xét hai phương pháp: RANDAO + VDF và phương pháp mã xóa. Trong phần tiếp theo, chúng ta sẽ xem xét chi tiết cách tiếp cận dựa trên chữ ký ngưỡng.

Nhưng trước tiên, chúng ta hãy xem xét một thuật toán đơn giản và thường được sử dụng, có tính khả thi, không thể đoán trước nhưng có sai số.

RANDAO

RANDAO là một cách tiếp cận rất đơn giản và do đó được sử dụng khá phổ biến để tạo ra tính ngẫu nhiên. Trước tiên, tất cả những người tham gia mạng sẽ chọn cục bộ một số giả ngẫu nhiên, sau đó mỗi người tham gia sẽ gửi hàm băm của số đã chọn. Tiếp theo, những người tham gia lần lượt tiết lộ các số đã chọn và thực hiện thao tác XOR trên các số được tiết lộ và kết quả của thao tác này trở thành kết quả của giao thức.

Bước xuất bản các giá trị băm trước khi tiết lộ các con số là cần thiết để kẻ tấn công không thể chọn số của mình sau khi đã nhìn thấy số của những người tham gia khác. Điều này sẽ cho phép anh ta gần như một mình xác định đầu ra của bộ tạo số ngẫu nhiên.

Trong quá trình thực hiện giao thức, người tham gia cần đi đến quyết định chung (được gọi là đồng thuận) hai lần: khi nào bắt đầu tiết lộ các số đã chọn và do đó ngừng chấp nhận giá trị băm và khi nào nên ngừng chấp nhận các số đã chọn và tính toán ngẫu nhiên kết quả. con số. Việc đưa ra những quyết định như vậy giữa những người tham gia không tin tưởng lẫn nhau bản thân nó không phải là một nhiệm vụ dễ dàng và chúng tôi sẽ quay lại vấn đề đó trong các bài viết sau; trong bài viết này, chúng tôi sẽ giả định rằng chúng tôi có sẵn một thuật toán đồng thuận như vậy.

RANDAO có những thuộc tính nào mà chúng tôi mô tả ở trên? Nó không thể đoán trước được, có sức sống tương tự như giao thức đồng thuận cơ bản, nhưng nó có tính thiên vị. Cụ thể, kẻ tấn công có thể quan sát mạng và sau khi những người tham gia khác tiết lộ số của họ, anh ta có thể tính toán XOR của họ và quyết định có tiết lộ số của mình để ảnh hưởng đến kết quả hay không. Mặc dù điều này ngăn cản kẻ tấn công một mình xác định đầu ra của trình tạo số ngẫu nhiên, nhưng nó vẫn mang lại cho kẻ tấn công một chút ảnh hưởng. Và nếu kẻ tấn công kiểm soát một số người tham gia thì số bit mà chúng kiểm soát sẽ bằng số lượng người tham gia mà chúng kiểm soát.

Ảnh hưởng của những kẻ tấn công có thể giảm đi đáng kể bằng cách yêu cầu người tham gia tiết lộ các con số theo thứ tự. Sau đó, kẻ tấn công sẽ chỉ có thể ảnh hưởng đến kết quả nếu nó được mở lần cuối. Mặc dù mức độ ảnh hưởng ít hơn đáng kể nhưng thuật toán vẫn bị sai lệch.

RANDAO+VDF

Một cách để làm cho RANDAO không thiên vị là: sau khi tất cả các số được tiết lộ và XOR được tính toán, kết quả của nó sẽ được đưa vào đầu vào của một hàm, hàm này mất rất nhiều thời gian để tính toán nhưng cho phép bạn kiểm tra tính chính xác của hàm tính toán rất nhanh.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Chức năng này được gọi là Chức năng trì hoãn có thể xác minh hoặc VDF. Nếu việc tính toán kết quả cuối cùng mất nhiều thời gian hơn giai đoạn tiết lộ số thì kẻ tấn công sẽ không thể dự đoán được tác động của việc hiển thị hoặc ẩn số của mình và do đó sẽ mất cơ hội tác động đến kết quả.

Phát triển VDF tốt là vô cùng khó khăn. Gần đây đã có một số bước đột phá, ví dụ: này и cái này, điều này làm cho VDF trở nên thiết thực hơn trong thực tế và Ethereum 2.0 có kế hoạch sử dụng RANDAO với VDF làm nguồn số ngẫu nhiên trong dài hạn. Ngoài thực tế là cách tiếp cận này không thể đoán trước và không thiên vị, nó còn có thêm lợi ích là khả thi nếu có ít nhất hai người tham gia trên mạng (giả sử giao thức đồng thuận được sử dụng là khả thi khi giao dịch với một số lượng nhỏ người tham gia như vậy).

Thách thức lớn nhất của phương pháp này là thiết lập VDF sao cho ngay cả người tham gia có phần cứng chuyên dụng rất đắt tiền cũng không thể tính toán VDF trước khi kết thúc giai đoạn khám phá. Lý tưởng nhất là thuật toán thậm chí phải có giới hạn an toàn đáng kể, chẳng hạn như 10 lần. Hình bên dưới cho thấy cuộc tấn công của kẻ tấn công có ASIC chuyên dụng cho phép anh ta chạy VDF nhanh hơn thời gian được phân bổ để tiết lộ xác nhận RANDAO. Người tham gia như vậy vẫn có thể tính toán kết quả cuối cùng bằng cách sử dụng hoặc không sử dụng số của mình, sau đó, dựa trên phép tính, chọn có hiển thị kết quả đó hay không.

Đối với dòng VDF được đề cập ở trên, hiệu suất của ASIC chuyên dụng có thể cao hơn 100 lần so với phần cứng thông thường. Vì vậy, nếu giai đoạn tiết lộ kéo dài 10 giây thì VDF được tính toán trên ASIC đó phải mất hơn 100 giây để có giới hạn an toàn gấp 10 lần và do đó, cùng một VDF được tính toán trên phần cứng thông thường phải mất 100x100 giây = ~3 giờ.

Ethereum Foundation có kế hoạch giải quyết vấn đề này bằng cách tạo ra các ASIC miễn phí, có sẵn công khai của riêng mình. Khi điều này xảy ra, tất cả các giao thức khác cũng có thể tận dụng công nghệ này, nhưng cho đến lúc đó, phương pháp RANDAO+VDF sẽ không khả thi đối với các giao thức không thể đầu tư phát triển ASIC của riêng mình.

Nhiều bài viết, video và các thông tin khác về VDF đã được sưu tầm trên trang web này.

Chúng tôi sử dụng mã xóa

Trong phần này, chúng ta sẽ xem xét một giao thức tạo số ngẫu nhiên sử dụng xóa mã. Nó có thể chấp nhận tối đa ⅓ kẻ tấn công trong khi vẫn tồn tại và cho phép tối đa ⅔ kẻ tấn công tồn tại trước khi chúng có thể dự đoán hoặc ảnh hưởng đến kết quả.

Ý tưởng chính của giao thức như sau. Để đơn giản, giả sử có chính xác 100 người tham gia. Chúng ta cũng giả sử rằng tất cả những người tham gia cục bộ đều có một số khóa riêng và khóa chung của tất cả những người tham gia đều được tất cả những người tham gia biết:

1. Mỗi người tham gia cục bộ nghĩ ra một chuỗi dài, chia nó thành 67 phần, tạo mã xóa để lấy 100 lượt chia sẻ sao cho 67 lượt chia sẻ bất kỳ là đủ để khôi phục chuỗi, gán mỗi phần trong số 100 phần chia sẻ cho một trong những người tham gia và mã hóa chúng bằng khóa công khai của cùng một người tham gia. Tất cả các chia sẻ được mã hóa sau đó sẽ được xuất bản.

2. Những người tham gia sử dụng một số loại đồng thuận để đạt được thỏa thuận về các bộ mã hóa từ 67 người tham gia cụ thể.

3. Sau khi đạt được sự đồng thuận, mỗi người tham gia sẽ lấy các chia sẻ được mã hóa trong mỗi bộ trong số 67 bộ được mã hóa bằng khóa chung của họ, giải mã tất cả các chia sẻ đó và xuất bản tất cả các chia sẻ được giải mã đó.

4. Khi 67 người tham gia đã hoàn thành bước (3), tất cả các bộ đã thống nhất có thể được giải mã và xây dựng lại hoàn toàn do đặc tính của mã xóa và số cuối cùng có thể thu được dưới dạng XOR của các hàng ban đầu mà những người tham gia bắt đầu ở (1) .

Giao thức này có thể được chứng minh là không thiên vị và không thể đoán trước. Số ngẫu nhiên thu được được xác định sau khi đạt được sự đồng thuận, nhưng không ai biết cho đến khi ⅔ số người tham gia giải mã các phần được mã hóa bằng khóa chung của họ. Do đó, số ngẫu nhiên được xác định trước khi thông tin đủ để tái tạo lại nó được công bố.

Điều gì sẽ xảy ra nếu ở bước (1) một trong những người tham gia gửi cổ phiếu được mã hóa cho những người tham gia khác mà mã xóa không chính xác cho một chuỗi nào đó? Nếu không có những thay đổi bổ sung, những người tham gia khác nhau sẽ không thể khôi phục chuỗi nào cả hoặc họ sẽ khôi phục các chuỗi khác nhau, điều này sẽ dẫn đến việc những người tham gia khác nhau sẽ nhận được một số ngẫu nhiên khác nhau. Để ngăn chặn điều này, bạn có thể làm như sau: mỗi người tham gia, ngoài số lượt chia sẻ được mã hóa, còn tính toán cây Merkla tất cả các chia sẻ như vậy và gửi cho mỗi người tham gia cả chính chia sẻ được mã hóa và gốc của cây merkle cũng như bằng chứng về việc đưa phần chia sẻ đó vào cây merkle. Trong sự đồng thuận ở bước (2), những người tham gia không chỉ đồng ý về một tập hợp các bộ mà còn về một tập hợp các gốc cụ thể của những cây đó (nếu một số người tham gia đi chệch khỏi giao thức và gửi các rễ cây merkle khác nhau cho những người tham gia khác nhau, và hai gốc như vậy được hiển thị trong quá trình đồng thuận, hàng của anh ta không được đưa vào tập kết quả). Do sự đồng thuận, chúng ta sẽ có 67 dòng được mã hóa và các gốc tương ứng của cây merkle sao cho có ít nhất 67 người tham gia (không nhất thiết phải là những người đã đề xuất các dòng tương ứng), mỗi người trong số 67 dòng có một thông báo có phần chia sẻ của mã bị xóa và bằng chứng cho thấy sự xuất hiện của phần chia sẻ đó trong cây tương ứng bị mờ đi.

Khi ở bước (4), người tham gia giải mã 67 nhịp cho một chuỗi nhất định và cố gắng xây dựng lại chuỗi gốc từ chúng, có thể thực hiện một trong các tùy chọn:

1. Chuỗi được khôi phục và nếu sau đó nó được mã hóa xóa một lần nữa và cây Merkle được tính cho các lượt chia sẻ được tính toán cục bộ thì gốc sẽ trùng khớp với chuỗi đã đạt được sự đồng thuận.

2. Hàng được khôi phục nhưng gốc được tính toán cục bộ không khớp với gốc đã đạt được sự đồng thuận.

3. Hàng không được khôi phục.

Dễ dàng chỉ ra rằng nếu tùy chọn (1) xảy ra với ít nhất một người tham gia ở trên thì tùy chọn (1) xảy ra với tất cả người tham gia và ngược lại, nếu tùy chọn (2) hoặc (3) xảy ra với ít nhất một người tham gia, thì đối với tất cả người tham gia, tùy chọn (2) hoặc (3) sẽ xảy ra. Do đó, đối với mỗi hàng trong tập hợp, tất cả những người tham gia sẽ khôi phục nó thành công hoặc tất cả những người tham gia sẽ không khôi phục được nó. Số ngẫu nhiên thu được sau đó là XOR chỉ của các hàng mà người tham gia có thể khôi phục.

Chữ ký ngưỡng

Một cách tiếp cận khác đối với tính ngẫu nhiên là sử dụng cái được gọi là chữ ký ngưỡng BLS. Trình tạo số ngẫu nhiên dựa trên chữ ký ngưỡng có cùng sự đảm bảo giống như thuật toán dựa trên mã xóa được mô tả ở trên, nhưng có số lượng tin nhắn tiệm cận được gửi qua mạng cho mỗi số được tạo thấp hơn đáng kể.

Chữ ký BLS là một thiết kế cho phép nhiều người tham gia tạo một chữ ký chung cho một tin nhắn. Những chữ ký này thường được sử dụng để tiết kiệm dung lượng và băng thông bằng cách không yêu cầu gửi nhiều chữ ký. 

Một ứng dụng phổ biến cho chữ ký BLS trong giao thức blockchain, ngoài việc tạo số ngẫu nhiên, là đăng nhập khối trong giao thức BFT. Giả sử 100 người tham gia tạo khối và một khối được coi là cuối cùng nếu 67 người trong số họ ký vào đó. Tất cả họ đều có thể gửi các phần chữ ký BLS của mình và sử dụng một số thuật toán đồng thuận để thống nhất 67 phần trong số đó và sau đó hợp nhất chúng thành một chữ ký BLS. Bất kỳ 67 phần (hoặc nhiều hơn) nào cũng có thể được sử dụng để tạo chữ ký cuối cùng, điều này sẽ phụ thuộc vào 67 chữ ký nào được kết hợp và do đó có thể khác nhau, mặc dù các lựa chọn khác nhau của 67 người tham gia sẽ tạo ra một chữ ký khác, mọi chữ ký như vậy sẽ là hợp lệ. chữ ký cho khối. Sau đó, những người tham gia còn lại chỉ cần nhận và xác minh một chữ ký trên mỗi khối, thay vì 67, qua mạng, điều này giúp giảm đáng kể tải trên mạng.

Hóa ra là nếu các khóa riêng mà người tham gia sử dụng được tạo theo một cách nhất định, thì cho dù tổng hợp 67 chữ ký nào (hoặc nhiều hơn, nhưng không ít hơn), thì chữ ký thu được sẽ giống nhau. Điều này có thể được sử dụng như một nguồn ngẫu nhiên: trước tiên, những người tham gia đồng ý về một số thông báo mà họ sẽ ký (đây có thể là đầu ra của RANDAO hoặc chỉ là hàm băm của khối cuối cùng, điều đó không thực sự quan trọng miễn là nó thay đổi mỗi lần và nhất quán) và tạo chữ ký BLS cho nó. Kết quả của việc tạo sẽ không thể đoán trước được cho đến khi 67 người tham gia cung cấp phần của họ và sau đó đầu ra đã được xác định trước và không thể phụ thuộc vào hành động của bất kỳ người tham gia nào.

Cách tiếp cận ngẫu nhiên này có thể thực hiện được miễn là ít nhất ⅔ số người tham gia trực tuyến đều tuân theo giao thức, đồng thời không thiên vị và không thể đoán trước được miễn là ít nhất ⅓ số người tham gia tuân theo giao thức. Điều quan trọng cần lưu ý là kẻ tấn công kiểm soát nhiều hơn ⅓ nhưng ít hơn ⅔ số người tham gia có thể dừng giao thức nhưng không thể dự đoán hoặc ảnh hưởng đến đầu ra của nó.

Bản thân chữ ký ngưỡng là một chủ đề rất thú vị. Trong phần thứ hai của bài viết, chúng tôi sẽ phân tích chi tiết cách chúng hoạt động và mức độ chính xác cần thiết để tạo khóa người tham gia để có thể sử dụng chữ ký ngưỡng làm trình tạo số ngẫu nhiên.

Kết luận

Bài viết này là bài viết đầu tiên trong loạt bài viế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