Giải thích Sách trắng phiên bản thứ 17 của Arweave (3): Trình diễn các trò chơi SPoRes

Ghi chú công thức:kN có nghĩa là tổng số lần thử giải pháp băm mà Alice có thể thực hiện trong một giây. Số lần thử này tỷ lệ thuận với số lượng bản sao duy nhất được Alice lưu trữ. Để có giải thích cụ thể, bạn có thể đọc phần nội dung của bài viết trước “Arweave 2.6 có thể phù hợp hơn với tầm nhìn của Satoshi Nakamoto”. 1-p là xác suất thất bại trong một lần thử. Giá trị xác suất của p2 bằng 1 trừ đi xác suất thất bại trong kN lần thử.

Bằng cách thay thế và suy ra hai công thức trên, chúng ta có được:

Ghi chú công thức: Thay p vào The kết quả thu được từ công thức P2

Thời gian cần thiết để Alice gửi bằng chứng có thể được mô phỏng bằng biến ngẫu nhiên hình học X ~ geom(p2) , p2 là Xác suất thành công. Biến ngẫu nhiên X này phụ thuộc vào d, k và n. Để xác minh xem Alice có nói dối hay không, Bob gửi độ khó d để Alice có thể gửi bằng chứng cho Bob cứ sau 120 giây với n bản sao. Điều này tương đương với xác suất thành công của Alice trong 120 giây:

Ghi chú công thức:1/120 là xác suất gửi bằng chứng thành công trong vòng 120 giây

Nếu Alice có thể gửi bằng chứng trong thời gian yêu cầu, cô ấy có thể có đúng số lượng bản sao duy nhất. Nhưng một bằng chứng là không đủ để thuyết phục Bob rằng Alice không nói dối. Nếu Alice có thể gửi bằng chứng trung bình cứ sau 120 giây trong một khoảng thời gian dài thì Bob có thể tin tưởng một cách hợp lý rằng Alice đã lưu trữ lượng dữ liệu mong đợi.

Tiếp theo, chúng tôi cố gắng định lượng mức độ chắc chắn về việc Bob lưu trữ Alice.

Giả sử Alice tuyên bố lưu trữ 20 bản sao và gửi bằng chứng một cách nhất quán ở mức trung bình 120 giây trong khoảng thời gian 2 tuần (tổng cộng 10.080 bài gửi chứng minh). Tại thời điểm này, Bob đang tự hỏi xác suất để Alice vẫn có thể gửi những bằng chứng này là bao nhiêu nếu cô ấy chỉ lưu trữ 19 (hoặc ít hơn) bản sao. Điều này tương ứng với xác suất cung cấp bằng chứng ở một giây khác:

Chú thích công thức:19k xuất hiện ở đây có nghĩa là Alice đã lưu được 19 bản và mỗi bản có k lần thử để tìm ra lời giải. số kế hoạch.

Đơn giản hóa quá mức:

Xác suất này có thể được tính bằng cách sử dụng giá trị d do Bob tạo ra cho Alice trung thực. Nếu cô ấy lưu trữ 19 bản sao hoặc ít hơn, xác suất cô ấy sẽ cung cấp bằng chứng trong một giây có thể được tìm thấy thông qua một loạt các dẫn xuất được đưa ra dưới đây. Trong số đó, p2* biểu thị xác suất tạo ra bằng chứng trong vòng một giây khi Alice lưu trữ thành thật 20 bản sao, trong khi p2* biểu thị xác suất cung cấp bằng chứng trong vòng một giây nếu cô ấy nói dối (được lưu trữ ≤ 19 bản):

Quá trình suy luận này có vẻ phức tạp nhưng trên thực tế, bất kỳ ai có khả năng toán học cơ bản đều có thể hiểu được. Quá trình phái sinh là quá trình thay thế của các công ty nêu trên.

Do đó, p2*=0,00791832081, tương ứng với thời gian tạo bằng chứng dự kiến ​​là 126,2894 giây. Gọi X* là thời điểm Alice gửi bằng chứng thu được từ p2*, tức là X*~ geom(p2*). Điều này thể hiện tình huống Alice đang nói dối - chỉ có 19 bản sao được lưu trữ và giá trị dự kiến ​​(trung bình) của thời gian cần thiết để gửi bằng chứng X* là:

Ghi chú công thức:E[ X*] có nghĩa là thời gian trung bình để Alice gửi bằng chứng thành công là 126,2894 giây với lý do chỉ có 19 bản sao được lưu trữ. Nếu cô ấy lưu trữ 20 bản sao thì thời gian chuyển giao thành công trung bình là 120 giây.

Chúng ta có thể sử dụng định lý giới hạn trung tâm để ước tính xác suất trung bình mẫu nhỏ hơn 120, khác với giá trị kỳ vọng E[X*] thu được bên trên. Xác suất này được biểu thị dưới dạng:

Chú thích công thức: Biểu thức ở bên trái của phương trình thể hiện xác suất trong vòng hai tuần, thời gian nộp trung bình của Alice cho mỗi bằng chứng nhỏ hơn hoặc bằng 120 giây. Vế phải của phương trình là một biến thể của biểu thức ở vế trái.

Đối với một số lượng lớn mẫu, vế trái của bất đẳng thức này có xu hướng phân phối chuẩn với giá trị trung bình E[X*] và phương sai σX*^2/n , trong đó σX* là độ lệch chuẩn của Xd và n (ở đây = 10.080) là cỡ mẫu. Do đó, công thức trên có thể trở thành:

Chúng ta có thể chuyển đổi phân phối này sang dạng chuẩn chuẩn hóa để đạt được xác suất tương đương:

Cuối cùng, sử dụng bảng phân phối chuẩn chuẩn hóa, chúng ta có thể nhận được Alice có xác suất nằm trong trường hợp này khoảng thời gian trong tuần:

Vì vậy, trong ví dụ này, Bob có thể xác định với độ chắc chắn khoảng 99,99997416% rằng Alice đã lưu trữ hơn 19 bản sao của tập dữ liệu trong 2 tuần. Chúng tôi lưu ý rằng nếu Alice lưu trữ ít hơn 19 bản sao thì thời gian gửi bằng chứng dự kiến ​​sẽ lớn hơn 126,3 giây. Chúng tôi cũng lưu ý rằng toàn bộ hệ thống bằng chứng chỉ yêu cầu truyền bằng chứng cứ sau 120 giây. Đây là tốc độ truyền dữ liệu trung bình giữa Alice và Bob là 2,389 KB mỗi giây (280 KB/120 giây), tương đương với chi phí đồng bộ hóa của mạng Bitcoin.

Cuối cùng, những xác suất này không thay đổi khi kích thước tập dữ liệu tăng tùy ý, nhưng việc tăng thời gian lấy mẫu sẽ tiếp tục cải thiện bản sao Alice của Bob ở mức siêu tuyến tính Tỷ lệ Độ chắc chắn về mặt định lượng của độ chính xác (Hình 1).

Hình 1: Trong trò chơi Bằng chứng ngắn gọn về sự sao chép (SPoRes), độ chắc chắn tăng siêu tuyến tính theo thời lượng mẫu. Sau hai tuần thu thập mẫu, xác suất duy trì ít hơn 19 bản sao là không đáng kể (P<0,0000002584).

Vì vậy, trò chơi SPoRes được xác định bởi các tham số sau:

Ở đâu:

r= Merkle root của tập dữ liệu được sử dụng cho trò chơi.

k= Số lượng thử thách tối đa được mở khóa mỗi giây trên mỗi bản sao.

d= Thông số độ khó xác định khả năng thành công của mỗi lần thử.

Thông qua những dẫn xuất toán học thú vị này, chúng tôi có thể xác định một cách an toàn rằng điều đó có thể được xác định miễn là người khai thác tiếp tục gửi bằng chứng trong một khoảng thời gian hợp lý . Liệu dữ liệu có được lưu trữ hay không. Điều này tạo thành cốt lõi của cơ chế đồng thuận của Arweave nhắm mục tiêu lưu trữ phi tập trung. Niềm vui toán học mới chỉ bắt đầu, sẽ còn nhiều suy luận, lập luận thú vị hơn ở các bài viết sau.

Liên kết trích dẫn

1. Arweave Eco Twitter:

https://twitter.com/@ArweaveEco

2. #SPoA:

https://twitter.com/search?q=%23SPoA&src= hashtag_click

3. #SPoRes:

https:/ /twitter.com/search?q=%23SPoRes&src=hashtag_click

4. Liên kết gốc:

https://twitter.com/ArweaveOasis/status/1772089247660638417