Giới thiệu
“Việc tạo số ngẫu nhiên quá quan trọng nên không thể phó mặc cho may rủi được.”
Robert Cavue, 1970
Bài viết này dành cho ứng dụng thực tế của các giải pháp sử dụng việc tạo số ngẫu nhiên tập thể trong môi trường không đáng tin cậy. Nói tóm lại, cách thức và lý do ngẫu nhiên được sử dụng trong blockchain và một chút về cách phân biệt ngẫu nhiên “tốt” với ngẫu nhiên “xấu”. Tạo ra một số thực sự ngẫu nhiên là một vấn đề cực kỳ khó khăn ngay cả trên một máy tính duy nhất và đã được các nhà mật mã học nghiên cứu từ lâu. Chà, trong các mạng phi tập trung, việc tạo ra các số ngẫu nhiên thậm chí còn phức tạp và quan trọng hơn.
Chính trong các mạng mà những người tham gia không tin tưởng lẫn nhau, khả năng tạo số ngẫu nhiên không thể chối cãi cho phép chúng tôi giải quyết hiệu quả nhiều vấn đề quan trọng và cải thiện đáng kể các kế hoạch hiện có. Hơn nữa, cờ bạc và xổ số không phải là mục tiêu số một ở đây, vì thoạt đầu người đọc thiếu kinh nghiệm có vẻ như vậy.
Tạo số ngẫu nhiên
Máy tính không thể tự tạo ra các số ngẫu nhiên; chúng cần có sự trợ giúp từ bên ngoài để làm điều đó. Máy tính có thể thu được một số giá trị ngẫu nhiên, ví dụ như chuyển động của chuột, dung lượng bộ nhớ được sử dụng, dòng điện rò rỉ trên các chân của bộ xử lý và nhiều nguồn khác được gọi là nguồn entropy. Bản thân các giá trị này không hoàn toàn ngẫu nhiên vì chúng nằm trong một phạm vi nhất định hoặc có kiểu thay đổi có thể dự đoán được. Để biến những số như vậy thành một số thực sự ngẫu nhiên trong một phạm vi nhất định, các phép biến đổi mật mã được áp dụng cho chúng để tạo ra các giá trị giả ngẫu nhiên được phân phối đồng đều từ các giá trị phân bố không đều của nguồn entropy. Các giá trị kết quả được gọi là giả ngẫu nhiên vì chúng không thực sự ngẫu nhiên mà có nguồn gốc xác định từ entropy. Bất kỳ thuật toán mã hóa tốt nào, khi mã hóa dữ liệu, đều tạo ra các bản mã không thể phân biệt được về mặt thống kê với một chuỗi ngẫu nhiên, do đó, để tạo ra tính ngẫu nhiên, bạn có thể lấy một nguồn entropy, chỉ cung cấp khả năng lặp lại tốt và không thể đoán trước các giá trị ngay cả trong phạm vi nhỏ, Công việc còn lại là phân tán và trộn các bit trong. Giá trị thu được sẽ được thuật toán mã hóa đảm nhiệm.
Để hoàn thành chương trình giáo dục ngắn gọn, tôi sẽ nói thêm rằng việc tạo số ngẫu nhiên ngay cả trên một thiết bị là một trong những trụ cột đảm bảo tính bảo mật cho dữ liệu của chúng tôi. Các số giả ngẫu nhiên được tạo được sử dụng khi thiết lập kết nối an toàn trong các mạng khác nhau, để tạo khóa mật mã, để cân bằng tải, giám sát tính toàn vẹn và cho nhiều ứng dụng khác. Tính bảo mật của nhiều giao thức phụ thuộc vào khả năng tạo ngẫu nhiên đáng tin cậy, không thể đoán trước từ bên ngoài, lưu trữ và không tiết lộ cho đến bước tiếp theo của giao thức, nếu không tính bảo mật sẽ bị xâm phạm. Một cuộc tấn công vào trình tạo giá trị giả ngẫu nhiên là cực kỳ nguy hiểm và ngay lập tức đe dọa tất cả các phần mềm sử dụng tính năng tạo ngẫu nhiên.
Bạn nên biết tất cả những điều này nếu bạn tham gia một khóa học cơ bản về mật mã, vì vậy hãy tiếp tục về mạng phi tập trung.
Ngẫu nhiên trong blockchain
Trước hết, tôi sẽ nói về các blockchain hỗ trợ hợp đồng thông minh; chúng là những blockchain có thể tận dụng tối đa các cơ hội được mang lại bởi tính ngẫu nhiên chất lượng cao, không thể phủ nhận. Hơn nữa, để cho ngắn gọn, tôi sẽ gọi công nghệ này là “Beacons ngẫu nhiên có thể xác minh công khai” hoặc PVRB. Vì chuỗi khối là mạng trong đó thông tin có thể được xác minh bởi bất kỳ người tham gia nào, nên phần quan trọng của tên là “Có thể xác minh công khai”, tức là. Bất cứ ai cũng có thể sử dụng các phép tính để có được bằng chứng cho thấy số kết quả được đăng trên blockchain có các thuộc tính sau:
- Kết quả phải có sự phân bố thống nhất có thể chứng minh được, tức là dựa trên mật mã mạnh có thể chứng minh được.
- Không thể kiểm soát bất kỳ bit nào của kết quả. Kết quả là không thể đoán trước được kết quả.
- Bạn không thể phá hoại giao thức tạo bằng cách không tham gia vào giao thức hoặc làm mạng quá tải với các thông báo tấn công
- Tất cả những điều trên phải chống lại sự thông đồng của một số lượng người tham gia giao thức không trung thực cho phép (ví dụ: 1/3 số người tham gia).
Bất kỳ khả năng nào về việc một nhóm nhỏ những người tham gia thông đồng để tạo ra ngẫu nhiên chẵn/lẻ được kiểm soát đều là lỗ hổng bảo mật. Bất kỳ khả năng nào của nhóm nhằm ngăn chặn việc phát hành ngẫu nhiên đều là lỗ hổng bảo mật. Nói chung là có rất nhiều vấn đề và nhiệm vụ này không hề dễ dàng...
Có vẻ như ứng dụng quan trọng nhất của PVRB là nhiều trò chơi, xổ số và nói chung là bất kỳ loại hình cờ bạc nào trên blockchain. Quả thực, đây là một hướng quan trọng, nhưng tính ngẫu nhiên trong blockchain thậm chí còn có những ứng dụng quan trọng hơn. Hãy nhìn vào chúng.
Thuật toán đồng thuận
PVRB đóng một vai trò rất lớn trong việc tổ chức sự đồng thuận của mạng lưới. Các giao dịch trong chuỗi khối được bảo vệ bằng chữ ký điện tử, do đó, một “cuộc tấn công vào giao dịch” luôn là việc bao gồm/loại trừ một giao dịch trong một khối (hoặc một số khối). Và nhiệm vụ chính của thuật toán đồng thuận là thống nhất thứ tự của các giao dịch này và thứ tự của các khối bao gồm các giao dịch này. Ngoài ra, một thuộc tính cần thiết cho các chuỗi khối thực sự là tính hữu hạn - khả năng mạng đồng ý rằng chuỗi cho đến khối cuối cùng là cuối cùng và sẽ không bao giờ bị loại trừ do sự xuất hiện của một nhánh mới. Thông thường, để đồng ý rằng một khối là hợp lệ và quan trọng nhất là cuối cùng, cần phải thu thập chữ ký từ phần lớn các nhà sản xuất khối (sau đây gọi là BP - nhà sản xuất khối), điều này đòi hỏi ít nhất phải cung cấp chuỗi khối. tới tất cả các BP và phân phối chữ ký giữa tất cả các BP. Khi số lượng BP tăng lên, số lượng tin nhắn cần thiết trong mạng tăng theo cấp số nhân, do đó, các thuật toán đồng thuận yêu cầu tính hữu hạn, ví dụ được sử dụng trong đồng thuận Hyperledger pBFT, không hoạt động ở tốc độ yêu cầu, bắt đầu từ vài chục BP, yêu cầu một số lượng lớn các kết nối.
Nếu có một PVRB trung thực và không thể phủ nhận trong mạng, thì ngay cả trong phép tính gần đúng đơn giản nhất, người ta có thể chọn một trong những nhà sản xuất khối dựa trên nó và chỉ định anh ta làm “người lãnh đạo” trong một vòng của giao thức. Nếu chúng ta có N nhà sản xuất khối, trong đó M: M > 1/2 N trung thực, không kiểm duyệt các giao dịch và không phân nhánh chuỗi để thực hiện cuộc tấn công “chi tiêu gấp đôi”, khi đó việc sử dụng PVRB được phân phối đồng đều không bị thách thức sẽ cho phép chọn được một nhà lãnh đạo trung thực với xác suất M / N (M / N > 1/2). Nếu mỗi nhà lãnh đạo được chỉ định khoảng thời gian riêng trong đó anh ta có thể tạo một khối và xác thực chuỗi và các khoảng thời gian này bằng nhau thì chuỗi khối của các BP trung thực sẽ dài hơn chuỗi được hình thành bởi các BP độc hại và sự đồng thuận. thuật toán dựa vào độ dài của chuỗi sẽ đơn giản loại bỏ chuỗi "xấu". Nguyên tắc phân bổ các khoảng thời gian bằng nhau cho mỗi BP lần đầu tiên được áp dụng trong Graphene (tiền thân của EOS) và cho phép hầu hết các khối được đóng bằng một chữ ký duy nhất, giúp giảm đáng kể tải mạng và cho phép sự đồng thuận này hoạt động cực kỳ nhanh chóng và đều đặn. Tuy nhiên, mạng EOS hiện phải sử dụng các khối đặc biệt (Khối không thể đảo ngược cuối cùng), được xác nhận bằng chữ ký của 2/3 BP. Các khối này phục vụ để đảm bảo tính hữu hạn (không thể có một chuỗi phân nhánh bắt đầu trước Khối không thể đảo ngược cuối cùng).
Ngoài ra, trong triển khai thực tế, sơ đồ giao thức phức tạp hơn - việc bỏ phiếu cho các khối được đề xuất được thực hiện theo nhiều giai đoạn để duy trì mạng trong trường hợp thiếu khối và sự cố với mạng, nhưng ngay cả khi tính đến điều này, các thuật toán đồng thuận sử dụng PVRB cũng yêu cầu ít tin nhắn hơn đáng kể giữa các BP, điều này giúp chúng có thể thực hiện nhanh hơn PVFT truyền thống hoặc các sửa đổi khác nhau của nó.
Đại diện nổi bật nhất của các thuật toán như vậy: từ nhóm Cardano, được cho là có thể chứng minh được về mặt toán học chống lại sự thông đồng của BP.
Trong Ouroboros, PVRB được sử dụng để xác định cái gọi là “lịch trình BP” - một lịch trình theo đó mỗi BP được chỉ định khoảng thời gian riêng để xuất bản một khối. Ưu điểm lớn của việc sử dụng PVRB là sự “bình đẳng” hoàn toàn của các BP (theo quy mô bảng cân đối kế toán của họ). Tính toàn vẹn của PVRB đảm bảo rằng các BP độc hại không thể kiểm soát việc lập lịch các khe thời gian và do đó không thể thao túng chuỗi bằng cách chuẩn bị và phân tích trước các nhánh của chuỗi và để chọn một nhánh, chỉ cần dựa vào độ dài của chuỗi là đủ. chuỗi mà không cần sử dụng những cách phức tạp để tính toán “tiện ích” của BP và “trọng lượng” của các khối của nó.
Nói chung, trong mọi trường hợp cần chọn một người tham gia ngẫu nhiên trong mạng phi tập trung, PVRB hầu như luôn là lựa chọn tốt nhất, thay vì một tùy chọn xác định dựa trên, chẳng hạn như hàm băm khối. Nếu không có PVRB, khả năng tác động đến sự lựa chọn của người tham gia sẽ dẫn đến các cuộc tấn công trong đó kẻ tấn công có thể chọn từ nhiều tương lai để chọn người tham gia tham nhũng tiếp theo hoặc nhiều người cùng một lúc để đảm bảo chia sẻ nhiều hơn trong quyết định. Việc sử dụng PVRB làm mất uy tín của các kiểu tấn công này.
Cân bằng tải và mở rộng quy mô
PVRB cũng có thể mang lại lợi ích lớn trong các nhiệm vụ như giảm tải và mở rộng quy mô thanh toán. Để bắt đầu, sẽ rất hợp lý nếu bạn làm quen với Rivesta “Vé xổ số điện tử dưới dạng thanh toán vi mô”. Ý tưởng chung là thay vì thực hiện 100 khoản thanh toán 1c từ người trả đến người nhận, bạn có thể chơi xổ số trung thực với giải thưởng 1$ = 100c, trong đó người trả tiền đưa cho ngân hàng một trong 1 “vé số” của mình cho mỗi lần thanh toán 100c. Một trong những tấm vé này giành được một lọ trị giá 1 đô la và chính tấm vé này mà người nhận có thể ghi lại vào chuỗi khối. Điều quan trọng nhất là 99 vé còn lại được chuyển giữa người nhận và người trả tiền mà không có sự tham gia từ bên ngoài, thông qua kênh riêng và với bất kỳ tốc độ mong muốn nào. Có thể đọc mô tả hay về giao thức dựa trên sơ đồ này trên mạng Emercoin .
Kế hoạch này có một số vấn đề, chẳng hạn như người nhận có thể ngừng phục vụ người trả tiền ngay sau khi nhận được vé trúng thưởng, nhưng đối với nhiều ứng dụng đặc biệt, chẳng hạn như thanh toán theo phút hoặc đăng ký dịch vụ điện tử, những điều này có thể bị bỏ qua. Tất nhiên, yêu cầu chính là tính công bằng của xổ số và để thực hiện nó, PVRB là hoàn toàn cần thiết.
Việc lựa chọn người tham gia ngẫu nhiên cũng cực kỳ quan trọng đối với các giao thức sharding, mục đích của nó là mở rộng quy mô chuỗi khối theo chiều ngang, cho phép các BP khác nhau chỉ xử lý phạm vi giao dịch của họ. Đây là một nhiệm vụ cực kỳ khó khăn, đặc biệt là về mặt bảo mật khi hợp nhất các phân đoạn. Lựa chọn hợp lý một BP ngẫu nhiên nhằm mục đích chỉ định những người chịu trách nhiệm cho một phân đoạn cụ thể, như trong các thuật toán đồng thuận, cũng là nhiệm vụ của PVRB. Trong các hệ thống tập trung, các phân đoạn được chỉ định bởi một bộ cân bằng; nó chỉ đơn giản tính toán hàm băm từ yêu cầu và gửi nó đến người thực thi được yêu cầu. Trong blockchain, khả năng ảnh hưởng đến nhiệm vụ này có thể dẫn đến sự tấn công vào sự đồng thuận. Ví dụ: kẻ tấn công có thể kiểm soát nội dung của các giao dịch, hắn có thể kiểm soát giao dịch nào đi đến phân đoạn mà hắn kiểm soát và thao túng chuỗi khối trong đó. Bạn có thể đọc phần thảo luận về vấn đề sử dụng số ngẫu nhiên cho các tác vụ phân chia trong Ethereum
Sharding là một trong những vấn đề đầy tham vọng và nghiêm túc nhất trong lĩnh vực blockchain; giải pháp của nó sẽ cho phép xây dựng các mạng phi tập trung có hiệu suất và khối lượng tuyệt vời. PVRB chỉ là một trong những khối quan trọng để giải quyết nó.
Trò chơi, giao thức kinh tế, trọng tài
Rất khó để đánh giá quá cao vai trò của các con số ngẫu nhiên trong ngành công nghiệp game. Việc sử dụng rõ ràng trong sòng bạc trực tuyến và sử dụng ngầm khi tính toán tác động của hành động của người chơi đều là những vấn đề cực kỳ khó khăn đối với các mạng phi tập trung, nơi không có cách nào để dựa vào nguồn ngẫu nhiên trung tâm. Nhưng lựa chọn ngẫu nhiên cũng có thể giải quyết được nhiều vấn đề kinh tế và giúp xây dựng các giao thức đơn giản và hiệu quả hơn. Giả sử trong giao thức của chúng tôi có tranh chấp về việc thanh toán cho một số dịch vụ rẻ tiền và những tranh chấp này khá hiếm khi xảy ra. Trong trường hợp này, nếu có PVRB không thể tranh chấp, khách hàng và người bán có thể đồng ý giải quyết tranh chấp một cách ngẫu nhiên nhưng với xác suất nhất định. Ví dụ: với xác suất 60% thì khách hàng thắng và với xác suất 40% là người bán thắng. Cách tiếp cận này, theo quan điểm đầu tiên là vô lý, cho phép bạn tự động giải quyết tranh chấp với tỷ lệ thắng/thua có thể dự đoán chính xác, phù hợp với cả hai bên mà không cần bất kỳ sự tham gia nào của bên thứ ba và lãng phí thời gian không cần thiết. Hơn nữa, tỷ lệ xác suất có thể thay đổi và phụ thuộc vào một số biến toàn cục. Ví dụ: nếu một công ty đang hoạt động tốt, ít tranh chấp và có lợi nhuận cao, công ty có thể tự động chuyển xác suất giải quyết tranh chấp theo hướng lấy khách hàng làm trung tâm, ví dụ 70/30 hoặc 80/20 và ngược lại, nếu tranh chấp tốn nhiều tiền và mang tính gian lận hoặc không thỏa đáng, bạn có thể chuyển xác suất sang hướng khác.
Một số lượng lớn các giao thức phi tập trung thú vị, chẳng hạn như cơ quan đăng ký mã thông báo được quản lý, thị trường dự đoán, đường cong liên kết và nhiều giao thức khác, là những trò chơi kinh tế trong đó hành vi tốt sẽ được khen thưởng và hành vi xấu sẽ bị phạt. Chúng thường chứa các vấn đề bảo mật mà các biện pháp bảo vệ xung đột với nhau. Những gì được bảo vệ khỏi cuộc tấn công của “cá voi” với hàng tỷ token (“cổ phần lớn”) sẽ dễ bị tấn công bởi hàng nghìn tài khoản có số dư nhỏ (“sybil stake”) và các biện pháp được thực hiện để chống lại một cuộc tấn công duy nhất, chẳng hạn như không các khoản phí tuyến tính được tạo ra để làm cho việc giao dịch với số tiền đặt cược lớn không mang lại lợi nhuận thường bị mất uy tín bởi một cuộc tấn công khác. Vì chúng ta đang nói về một trò chơi kinh tế, nên các trọng số thống kê tương ứng có thể được tính toán trước và chỉ cần thay thế hoa hồng bằng hoa hồng ngẫu nhiên với mức phân bổ phù hợp. Các khoản hoa hồng xác suất như vậy được thực hiện cực kỳ đơn giản nếu blockchain có nguồn ngẫu nhiên đáng tin cậy và không yêu cầu bất kỳ phép tính phức tạp nào, gây khó khăn cho cuộc sống của cả cá voi và cá heo.
Đồng thời, cần tiếp tục nhớ rằng việc kiểm soát từng bit trong tính ngẫu nhiên này cho phép bạn gian lận, giảm và tăng xác suất lên một nửa, vì vậy một PVRB trung thực là thành phần quan trọng nhất của các giao thức đó.
Tìm đâu ra sự ngẫu nhiên phù hợp?
Về lý thuyết, việc lựa chọn ngẫu nhiên công bằng trong các mạng phi tập trung làm cho hầu hết mọi giao thức đều được chứng minh là an toàn trước sự thông đồng. Lý do khá đơn giản - nếu mạng đồng ý trên một bit 0 hoặc 1 và ít hơn một nửa số người tham gia không trung thực, thì với đủ số lần lặp, mạng được đảm bảo đạt được sự đồng thuận về bit đó với xác suất cố định. Đơn giản vì một người ngẫu nhiên trung thực sẽ chọn 51 trong số 100 người tham gia với tỷ lệ 51%. Nhưng đây là trên lý thuyết, bởi vì... trong các mạng thực, để đảm bảo mức độ bảo mật như trong bài viết, cần có nhiều tin nhắn giữa các máy chủ, mật mã nhiều đường phức tạp và bất kỳ sự phức tạp nào của giao thức sẽ ngay lập tức bổ sung thêm các vectơ tấn công mới.
Đó là lý do tại sao chúng ta vẫn chưa thấy PVRB có khả năng kháng cự đã được chứng minh trong các chuỗi khối, vốn đã được sử dụng trong thời gian đủ để được kiểm tra bởi các ứng dụng thực, nhiều lần kiểm tra, tải và tất nhiên là các cuộc tấn công thực, nếu không có thì khó gọi là một cuộc tấn công thực sự. sản phẩm thực sự an toàn.
Tuy nhiên, có một số cách tiếp cận đầy hứa hẹn, chúng khác nhau ở nhiều chi tiết và một trong số chúng chắc chắn sẽ giải quyết được vấn đề. Với các tài nguyên máy tính hiện đại, lý thuyết mật mã có thể được chuyển hóa khá khéo léo sang các ứng dụng thực tế. Trong tương lai, chúng ta sẽ rất vui khi nói về việc triển khai PVRB: hiện có một vài trong số đó, mỗi cái có một tập hợp các thuộc tính và tính năng triển khai quan trọng riêng và đằng sau mỗi cái đều có một ý tưởng hay. Không có nhiều đội tham gia vào việc ngẫu nhiên hóa và kinh nghiệm của mỗi người trong số họ là cực kỳ quan trọng đối với những người còn lại. Chúng tôi hy vọng rằng thông tin của chúng tôi sẽ cho phép các nhóm khác tiến nhanh hơn, có tính đến kinh nghiệm của những người đi trước.
Nguồn: www.habr.com