a16z: Xây dựng tính ngẫu nhiên công khai của Web3 thông qua các đèn hiệu ngẫu nhiên phi tập trung

Tiêu đề gốc: " Báo hiệu ngẫu nhiên và ngẫu nhiên công khai 》

Tác giả gốc: Joseph Bonneau, Valeria Nikolaenko, đối tác nghiên cứu tiền điện tử a16z

Bản tổng hợp gốc: Shaun@DAORayaki.org, DoraFactory

Tính đồng ngẫu nhiên là một thành phần quan trọng của nhiều giao thức bảo mật trong thế giới thực. Trong một số ứng dụng, chẳng hạn như cờ bạc và trò chơi nhiều người chơi, tính ngẫu nhiên sẽ làm tăng thêm sự thú vị. Trong số các ứng dụng khác, tính ngẫu nhiên cung cấp một cách công bằng để phân bổ các nguồn lực không thể phân chia, từ thẻ xanh đến phân công vụ việc của các thẩm phán tòa án cho đến hạt giống cho các giải đấu thể thao. Nó cũng được sử dụng để phân bổ các nguồn lực tiêu cực, chẳng hạn như kiểm toán thuế hoặc sàng lọc an ninh thứ cấp tại các sân bay.

Theo truyền thống, chúng tôi dựa vào các cơ quan đáng tin cậy để các Giao thức này tạo ra tính ngẫu nhiên, nhưng trong thế giới web3 chúng ta cần phải làm tốt hơn. Trong bài đăng này, chúng ta sẽ khám phá các cách để xây dựng tính ngẫu nhiên có thể xác minh công khai thông qua các cảnh báo ngẫu nhiên được phân phối và sau đó thảo luận về một số ứng dụng trên chuỗi. (Phần thứ hai sắp tới sẽ tập trung cụ thể vào việc lựa chọn người lãnh đạo đồng thời đưa ra đánh giá về các phương pháp lựa chọn người lãnh đạo thay thế.)

Đặc tính mong đợi

Tạo số ngẫu nhiên là một nhiệm vụ cực kỳ tế nhị. Ví dụ: nhiều khóa mã hóa đã bị xâm phạm do chúng dựa vào một trình tạo số ngẫu nhiên thiếu sót (bức tường đèn dung nham của Cloudflare đóng vai trò như một biện pháp giảm thiểu sáng tạo). Tuy nhiên, đây chỉ là sự ngẫu nhiên riêng tư và chỉ một bên cần tạo và sử dụng nó. Ngược lại, tính ngẫu nhiên công khai là một quá trình có sự tham gia của nhiều bên, điều này làm tăng độ khó lên rất nhiều. Một giao thức tốt tạo ra tính ngẫu nhiên công khai sẽ có các đặc tính bảo mật sau:

Không thiên vị: Không kẻ tấn công hoặc liên minh kẻ tấn công nào có thể thiên vị đầu ra. Đáng tin cậy: Không kẻ tấn công nào có thể ngăn giao thức tạo ra đầu ra.

Có thể kiểm chứng: Bất kỳ ai cũng có thể dễ dàng xác minh đầu ra của giao thức và sẽ thấy đầu ra giống như những người khác.

Không thể đoán trước: Nếu giao thức tạo ra đầu ra tại thời điểm T1 thì không ai có thể dự đoán bất cứ điều gì về đầu ra trước một thời điểm T0<T1, lý tưởng nhất là trong trường hợp này trường hợp T0 rất gần với T1.

Tính không thiên vị là một thuộc tính yếu hơn tính không thể đoán trước, vì bất kỳ giao thức không thể đoán trước nào cũng phải không thiên vị. Các nhà khoa học máy tính sẽ nói rằng tính không thiên vị sẽ giảm xuống mức không thể đoán trước được, bởi vì nếu bạn thiên vị, bạn có thể dự đoán. Nhưng đôi khi chúng ta muốn lý luận về chúng một cách riêng biệt, vì chúng có thể dựa trên những giả định khác nhau—ví dụ, đa số không trung thực có thể dự đoán kết quả nhưng không thiên vị nó.

Ngoài những đặc tính này, giao thức còn có thể hoạt động hiệu quả và tạo ra lượng lớn bit ngẫu nhiên. (Trong thực tế, thông thường một ứng dụng chỉ tạo ra 128 bit ngẫu nhiên là đủ, sử dụng chúng để tạo bộ tạo số giả ngẫu nhiên [PNRG] để xuất ra nhiều bit hơn nếu cần. Tuy nhiên, nó sẽ không khả dụng cho từng bit riêng lẻ của đầu ra. đối với các ứng dụng như xổ số hoặc phân bổ tài nguyên) Lý tưởng nhất là giao thức cũng phải hiệu quả về mặt chi phí truyền thông và tính toán.

Các giao thức khác nhau có thể triển khai các thuộc tính này trong các điều kiện khác nhau. Ví dụ: một số giao thức có thể không bị thiên vị bởi bất kỳ liên minh nào của các nút độc hại f1 và không thể đoán trước được bởi bất kỳ liên minh nào của các nút độc hại f2<f1. Ngoài ra còn có nhiều mức độ thành kiến khác nhau. Ví dụ: trong một số giao thức, người tham gia có thể sai lệch đầu ra theo "một bit" - nghĩa là họ có thể chọn giữa một trong hai đầu ra có thể. Các cuộc tấn công khác có thể cho phép chúng sửa chữa hoàn toàn đầu ra. Tuy nhiên, thông thường, chúng ta không muốn chấp nhận bất kỳ sự thiên vị (hoặc khả năng dự đoán) nào cả.

Mật mã lý tưởng: đèn hiệu ngẫu nhiên

Các nhà nghiên cứu mật mã thường bắt đầu bằng việc nghĩ về một giải pháp lý tưởng cho một vấn đề. Trong bối cảnh ngẫu nhiên công khai, đèn hiệu ngẫu nhiên là một dịch vụ lý tưởng hóa, định kỳ tạo ra các đầu ra ngẫu nhiên đáp ứng tất cả các yêu cầu bảo mật cần thiết.

Đèn hiệu ngẫu nhiên được lý tưởng hóa này, tương tự như các dạng trừu tượng hóa mật mã khác - chẳng hạn như các dự đoán ngẫu nhiên hoặc các mô hình nhóm phổ quát - không tồn tại trong thế giới thực. Nhưng đó là một mục tiêu hữu ích và một mô hình hữu ích để suy luận về các giao thức dựa vào tính ngẫu nhiên công khai.

Chúng ta có thể xem xét một số giá trị gần đúng của một đèn hiệu ngẫu nhiên lý tưởng.

Báo hiệu tập trung: Cách dễ nhất để tạo ra tính ngẫu nhiên tốt là thông qua bên thứ ba tập trung với dịch vụ như NIST Randomness Beacon hoặc Random.org, tạo ra dữ liệu từ tiếng ồn trong khí quyển. Tạo ra tính ngẫu nhiên và được chứng nhận để sử dụng cờ bạc. Sự phụ thuộc vào bên thứ ba này hoàn toàn làm suy yếu ý tưởng phân quyền. Thật vậy, trong ví dụ trên, chúng ta phải tin tưởng rằng tổ chức được đề cập đang tạo ra tính ngẫu nhiên một cách chính xác mà không cần bất kỳ bằng chứng mật mã nào.

Sự thể hiện ngẫu nhiên một cách vật lý: Nhiều xổ số truyền thống dựa vào sự hiển thị công khai, chẳng hạn như có thể bao gồm việc ai đó thò tay vào một thùng chứa các quả bóng bàn chứa đầy các số khác nhau . Thật không may, những thứ này thường dễ vận hành. Ví dụ: một quả bóng nhất định có thể được đặt trong tủ lạnh và sau đó bộ chọn có thể được yêu cầu chọn quả bóng lạnh.

Đèn hiệu tự nhiên: Một ý tưởng phổ biến là sử dụng các hiện tượng tự nhiên ngẫu nhiên, chẳng hạn như thời tiết hoặc bức xạ nền vũ trụ, làm đèn hiệu. Thật không may, không có nguồn nào được đề xuất cung cấp sự đồng thuận mạnh mẽ. Những người quan sát khác nhau sẽ thấy các giá trị hơi khác nhau, điều này đòi hỏi phải có sự tham gia lại của các bên đáng tin cậy để thực hiện các phép đo chính thức, với tất cả những nhược điểm của đèn hiệu tập trung.

Đèn hiệu bán tập trung: Một cách tiếp cận tốt hơn là lấy tính ngẫu nhiên trực tiếp từ tiêu đề khối Bitcoin hoặc giá đóng cửa cổ phiếu, điều này dễ xác minh công khai hơn và khó hơn để hai bên có toàn quyền kiểm soát. Tuy nhiên, các cuộc tấn công tinh vi vào tính ngẫu nhiên của chuỗi khối bằng chứng công việc và tính ngẫu nhiên của giá cổ phiếu vẫn tồn tại. Ví dụ: bằng cách sử dụng tiêu đề blockchain, người khai thác có thể chọn giữ các khối có tiêu đề tạo ra giá trị đèn hiệu mà họ không thích. Ngoài ra, họ có thể chọn phá vỡ mối ràng buộc khi tìm thấy hai khối va chạm dựa trên đầu ra đèn hiệu ưa thích.

Đèn hiệu ngẫu nhiên phi tập trung (DRB)

Một cách tự nhiên để giải quyết vấn đề báo hiệu tập trung là thiết kế một giao thức mật mã phi tập trung để tạo ra tính ngẫu nhiên công khai. Vấn đề này hơi giống việc thiết kế một giao thức đồng thuận phi tập trung, chỉ khó hơn. Không chỉ tất cả những người tham gia cần phải đồng ý về đầu ra (tính ngẫu nhiên), mà các tác nhân độc hại trong giao thức không được thiên vị hoặc dự đoán đầu ra.

Một giao thức được thiết kế để mô phỏng đèn hiệu ngẫu nhiên được gọi là đèn hiệu ngẫu nhiên phân tán (DRB). (Các tên khác bao gồm "lật đồng xu phân tán.") Vấn đề đã được nghiên cứu trong nhiều thập kỷ, nổi tiếng chứng minh những kết quả không thể xảy ra vào những năm 1980, nhưng lại nhận thấy sự quan tâm mới đến kỷ nguyên blockchain. DRB có thể được sử dụng để cung cấp tính ngẫu nhiên trên chuỗi, đây sẽ là yếu tố chính cho các ứng dụng trên chuỗi công bằng, an toàn và minh bạch.

Phương pháp cổ điển: Thỏa thuận cam kết-tiết lộ

Trong một kịch bản lạc quan, một thỏa thuận hai vòng rất đơn giản sẽ đủ để đáp ứng nhu cầu của DRB. Ở vòng 1, mỗi người tham gia i tạo ra một giá trị ngẫu nhiên ri và đưa ra một cam kết mật mã ci=Commit(ri). Trong ứng dụng này, lời hứa có thể đơn giản là hàm băm như SHA-256. Sau khi cam kết của mỗi người tham gia được giải phóng, họ sẽ bị khóa vào RI mà họ lựa chọn, nhưng cam kết không tiết lộ bất kỳ thông tin nào về đóng góp của những người tham gia khác. Ở vòng 2, mỗi người tham gia “mở ra cam kết” bằng cách công bố ri. Sau đó kết hợp tất cả các giá trị ngẫu nhiên, ví dụ bằng cách XOR chúng hoặc (tốt nhất là) băm nối chúng.

Giao thức rất đơn giản, bất cứ khi nào một trong những người tham gia chọn ngẫu nhiên ri của họ, một đầu ra đèn hiệu ngẫu nhiên sẽ được tạo ra. Thật không may, nó mắc phải một lỗ hổng điển hình: khi tất cả người tham gia đã tiết lộ giá trị ngẫu nhiên của họ, người tham gia cuối cùng có thể tính toán đầu ra đèn hiệu giả định. Nếu không thích, họ có thể từ chối đưa ra các giá trị của mình, hủy bỏ thỏa thuận. Bỏ qua sự đóng góp của những người tham gia sai sót không giải quyết được vấn đề, vì điều này vẫn khiến kẻ tấn công phải lựa chọn giữa hai đầu ra đèn hiệu (một đầu ra được tính toán với đóng góp của họ và một đầu ra không).

Blockchain cung cấp một giải pháp tự nhiên cho vấn đề này: mỗi người tham gia có thể được yêu cầu gửi một số tiền vào ký quỹ nếu họ không tiết lộ những khoản đóng góp ngẫu nhiên của mình sẽ dẫn đến số tiền đó bị tịch thu. Đây chính xác là cách tiếp cận được thực hiện bởi đèn hiệu RANDAO cổ điển trên Ethereum. Nhược điểm của phương pháp này là đầu ra vẫn có thể bị sai lệch, điều này có thể có giá trị đối với kẻ tấn công nếu số tiền trong ký quỹ nhỏ hơn số tiền trên kết quả báo hiệu. Bảo mật tốt hơn trước các cuộc tấn công thiên vị đòi hỏi phải đặt nhiều mã thông báo hơn vào ký quỹ.

Thỏa thuận cam kết-tiết lộ-khôi phục

Thay vì cố gắng buộc tất cả các bên tiết lộ những đóng góp ngẫu nhiên của họ, một số giao thức bao gồm cơ chế phục hồi để ngay cả khi một số người tham gia bỏ học, những người tham gia còn lại vẫn có thể hoàn thành giao thức. Điều quan trọng là thỏa thuận tạo ra kết quả như nhau trong cả hai trường hợp, để các bên không thể làm sai lệch kết quả khi chọn có rút lui hay không.

Một cách để đạt được điều này là yêu cầu mỗi người tham gia cung cấp một phần bí mật của mình cho những người tham gia khác để hầu hết họ có thể sử dụng nó. Chẳng hạn như chia sẻ bí mật của Shamir để xây dựng lại nó. Tuy nhiên, một đặc tính quan trọng là những người khác có thể xác minh rằng bí mật được gửi đã được chia sẻ chính xác, điều này đòi hỏi phải sử dụng một phương thức nguyên thủy mạnh mẽ hơn được gọi là Chia sẻ bí mật có thể xác minh công khai (PVSS).

Có thể có một số cơ chế phục hồi khác, nhưng chúng đều có những hạn chế giống nhau. Nếu có N tác nhân và chúng tôi muốn khả năng phục hồi nếu bất kỳ nhóm nào có tối đa f nút thoát ra thì bất kỳ nhóm N-f tác nhân nào cũng phải có khả năng tính toán kết quả cuối cùng. Nhưng điều này cũng có nghĩa là một liên minh độc hại gồm những người tham gia N-f có thể dự đoán trước kết quả bằng cách mô phỏng riêng cơ chế phục hồi, điều này cũng có thể xảy ra ở vòng đầu tiên của giao thức, trong đó liên minh như vậy có thể sửa đổi các lựa chọn ngẫu nhiên của riêng họ và thực hiện The kết quả là sai lệch.

Nói cách khác, điều này có nghĩa là bất kỳ liên minh nào của các nút N-f đều phải chứa ít nhất một nút trung thực. Bằng đại số đơn giản, N-f > f, do đó f < N/2, các giao thức này về cơ bản yêu cầu đa số trung thực. Điều này rất khác với mô hình bảo mật tiết lộ cam kết ban đầu, chỉ yêu cầu f<N (ít nhất một người tham gia trung thực).

Các giao thức này cũng thường yêu cầu chi phí truyền thông đáng kể để chia sẻ thông tin PVSS bổ sung giữa tất cả các nút trong mỗi lần chạy giao thức. Cộng đồng nghiên cứu đã thực hiện khá nhiều công việc về vấn đề này trong vài năm qua, với các đề xuất nghiên cứu bao gồm RandShare, Scrape, SecRand, HERB hoặc Albatross, nhưng dường như chưa có đề xuất nào được triển khai thực tế.

Giao thức dựa trên chức năng ngẫu nhiên có thể kiểm chứng

Nhận thấy rằng một nhóm N-f người tham gia có thể tính toán giá trị đèn hiệu ngẫu nhiên trong giao thức trên đã dẫn đến một cách tiếp cận đơn giản hơn: chia sẻ khóa dài hạn giữa N bên và cho phép họ sử dụng khóa đó để đánh giá các hàm ngẫu nhiên có thể kiểm chứng (VRF). Khóa được chia sẻ thông qua sơ đồ ngưỡng t-of-N, do đó, bất kỳ người tham gia t nào cũng có thể tính toán VRF (nhưng các liên đoàn nhỏ hơn thì không thể). Đối với t=N - việc nhận ra rằng một tập hợp N-f người tham gia có thể tính toán giá trị báo hiệu ngẫu nhiên trong giao thức trên đã dẫn đến một cách tiếp cận đơn giản hơn: chia sẻ khóa dài hạn giữa N bên và cho phép họ sử dụng nó để Đánh giá các Hàm ngẫu nhiên có thể xác minh (VRF) . Khóa được chia sẻ thông qua sơ đồ ngưỡng t-of-N, do đó, bất kỳ người tham gia t nào cũng có thể tính toán VRF (nhưng các liên đoàn nhỏ hơn thì không thể). Đối với t=N-f, điều này mang lại khả năng phục hồi tương tự cho f nút độc hại như giao thức cam kết-tiết lộ-khôi phục đã thảo luận ở trên.

DFINITY đi tiên phong trong cách tiếp cận này như một phần của giao thức đồng thuận, sử dụng chữ ký BLS ngưỡng (được sử dụng làm VRF). Đèn hiệu ngẫu nhiên drand độc lập về cơ bản sử dụng cùng một cách tiếp cận, với một tập hợp các ngưỡng của người tham gia - BLS - ký vào bộ đếm mỗi vòng. Entropy Alliance là một phiên bản drand mã nguồn mở sử dụng 16 nút tham gia (tính đến tháng 9 năm 2022) để tạo ra tính ngẫu nhiên cứ sau 30 giây và được điều hành bởi sự kết hợp giữa các nhóm nghiên cứu của công ty và trường đại học.

Nhược điểm của các phương pháp này là việc khởi tạo khóa ngưỡng tương đối phức tạp, cũng như việc định cấu hình lại khóa khi các nút tham gia hoặc rời đi. Tuy nhiên, trong các tình huống thông thường, giao thức hoạt động rất tốt.

Như đã đề cập ở trên, việc chỉ ký một giá trị đếm sẽ không thêm bất kỳ tính ngẫu nhiên mới nào trong mỗi vòng, vì vậy nếu đủ số lượng khóa của người tham gia bị rò rỉ thì giao thức sẽ sẽ có thể dự đoán được ở mọi vòng đấu trong tương lai.

Chainlink VRF kết hợp phương pháp này (sử dụng NSEC5 VRF) với nguồn ngẫu nhiên bên ngoài được chỉ định bởi bên yêu cầu tính ngẫu nhiên, thường là vùng gần nhất trong tiêu đề Blockchain thực tế. Dữ liệu này sau đó được cung cấp thông qua VRF do một bên điều hành hoặc được phân ngưỡng cho một nhóm.

Chuỗi báo hiệu của Ethereum hiện sử dụng VRF dựa trên BLS: những người đề xuất trong mỗi vòng sẽ thêm giá trị VRF của họ vào hỗn hợp. Điều này giúp tiết kiệm một vòng liên lạc so với mô hình tiết lộ cam kết (giả sử khóa công khai BLS dài hạn được đăng ký một lần), mặc dù thiết kế này kế thừa một số cảnh báo của phương pháp tiết lộ cam kết, bao gồm khả năng làm sai lệch đầu ra đèn hiệu bằng cách giữ lại thuộc tính đầu ra.

Giao thức dựa trên hàm trì hoãn có thể kiểm chứng

Cuối cùng, một hướng đi mới đầy hứa hẹn là việc sử dụng mật mã dựa trên thời gian, cụ thể là Hàm trì hoãn có thể xác minh (VDF). Cách tiếp cận này được kỳ vọng sẽ mang lại hiệu quả liên lạc tốt và mạnh mẽ với khả năng phục hồi chống lại các nút độc hại N-1.

Quay trở lại giao thức tiết lộ cam kết ban đầu, các cam kết truyền thống có thể được thay thế bằng các cam kết đúng thời hạn nhằm loại bỏ vấn đề người tham gia từ chối tiết lộ những đóng góp ngẫu nhiên của họ. Các cam kết theo thời gian có thể được bật một cách hiệu quả bởi người gửi ban đầu hoặc bất kỳ ai sẵn sàng tính toán một hàm chậm (về cơ bản là VDF). Do đó, nếu bất kỳ người tham gia nào thoát khỏi giao thức tiết lộ cam kết, những người khác vẫn có thể mở cam kết của họ. Điều quan trọng là thời gian tối thiểu để mở cam kết phải đủ dài để không thể hoàn thành ở vòng đầu tiên (giai đoạn cam kết) của giao thức, nếu không, những kẻ độc hại có thể mở cam kết của người khác đủ nhanh để sửa đổi đóng góp và kết quả sai lệch của chính họ.

VDF hiện đại cho phép thực hiện một vòng thỏa thuận tinh tế hơn: từ bỏ hoàn toàn các cam kết. Mỗi người tham gia có thể chỉ cần xuất bản ri đóng góp ngẫu nhiên của họ và kết quả cuối cùng là sự kết hợp đóng góp của mỗi người tham gia, chạy qua VDF. Độ trễ thời gian trong việc tính toán VDF đảm bảo rằng không ai có thể lựa chọn cam kết của mình để làm sai lệch kết quả đầu ra cuối cùng.

Phương pháp này được Arjen Lenstra và Benjamin Wesolowski đề xuất với tên gọi UNICORN vào năm 2015 và thực sự là một ứng dụng tạo động lực quan trọng trong việc phát triển VDF. Cách tiếp cận này đã được triển khai trong thế giới thực. Chia đã triển khai một phiên bản như một phần của giao thức đồng thuận sử dụng các VDF bình phương lặp lại trong các nhóm lớp. Starkware đã triển khai đèn hiệu VDF chứng minh khái niệm bằng cách sử dụng VDF dựa trên SNARK. Ethereum cũng có kế hoạch sử dụng phương pháp này, xây dựng một ASIC chuyên dụng để tính toán VDF nhằm tạo ra tính ngẫu nhiên ở lớp đồng thuận.

Tính ngẫu nhiên công khai là một thành phần quan trọng của nhiều giao thức, nhưng chúng tôi vẫn thiếu bất kỳ DRB tiêu chuẩn nào cung cấp tính bảo mật cao. Không gian thiết kế rộng và có thể kết hợp nhiều cách tiếp cận trên. Ví dụ: các giao thức dựa trên VRF có thể được kết hợp với các giao thức dựa trên VDF, bổ sung thêm entropy mới, chẳng hạn như giao thức do RandRunner đề xuất. Chuỗi đèn hiệu của Ethereum hiện sử dụng VRF, nhưng VDF có thể được thêm vào trong tương lai để loại bỏ khả năng sai lệch trong các cuộc tấn công giữ lại khối.

Đây cũng là một câu hỏi mở khi các giao thức đa số trung thực có thể chấp nhận được. Đối với một nhóm người tham gia tương đối nhỏ, đã được kiểm duyệt—chẳng hạn như Liên minh Entropy—một giả định trung thực của đa số là hợp lý. Mặt khác, các giao thức chỉ yêu cầu một người tham gia trung thực có một lợi thế cố hữu - nhiều người tham gia hơn chỉ có thể cải thiện tính bảo mật. Điều này có nghĩa là các giao thức này có thể được triển khai với sự tham gia mở, không cần cấp phép.

Trong phần thứ hai, chúng ta sẽ thảo luận về ứng dụng cụ thể của việc bầu chọn người lãnh đạo ngẫu nhiên trong các giao thức đồng thuận, có mục tiêu thiết kế hơi khác nhau và do đó đề xuất nhiều giao thức và phương pháp hơn.   

Liên kết gốc

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia