Đọc thuật toán xáo trộn của Ethereum 2.0 trong một bài viết
Tác giả |Ben Edgington
Giới thiệu
Tác giả |Giới thiệunếu bạn muốn học
bước nhảy ma
(nhảy ngẫu nhiên), thì bạn đang ở sai chỗ. Nhưng tin tôi đi, xáo trộn trong Eth2 cũng thú vị không kém.Xáo trộn danh sách là một hoạt động cơ bản trong Ethereum 2.0. Nó chủ yếu được sử dụng để giả ngẫu nhiên chọn người xác minh để thành lập ủy ban trong mỗi vị trí 12 giây và để chọn người đề xuất cho các khối chuỗi đèn hiệu trong mỗi vị trí.Xáo trộn có vẻ khá đơn giản. mặc dù nó có một sốFisher-Yeats shuffleẨn nguy hiểm
hướng lên. Vậy tại sao chúng ta không sử dụng nó trong Eth2? Tôi sẽ giải thích chi tiết ở cuối bài viết, nhưng ngắn gọn - client nhẹ.giấygiấyTekuở giữa. Gần đây tôi đang sử dụng ứng dụng khách ETH2ở giữa
viết lại
Việc thực hiện của chúng tôi, vì vậy tôi muốn viết nó ra khi nó vẫn còn nóng.
Thuật toán hoán đổi hoặc không xáo trộn
vòng hoạt động
Xáo trộn được thực hiện theo vòng. Quá trình này giống nhau cho mỗi vòng, vì vậy tôi sẽ chỉ trình bày quy trình cho một vòng bên dưới, nó đơn giản hơn nhiều so với vẻ ngoài của nó.
Đầu tiên, chúng tôi chọn một chỉ số trục p, chỉ số này được chọn giả ngẫu nhiên dựa trên các vòng và một số dữ liệu gốc khác. Sau khi trục được chọn, nó được cố định trong vòng.
Dựa trên điểm trục này, chúng tôi chọn chỉ số phản chiếu m1 tại điểm giữa giữa p và 0, nghĩa là m1=p/2. (Để giải thích, chúng tôi sẽ bỏ qua vấn đề làm tròn lỗi từng cái một rắc rối)
Mô tả hình ảnh
Điểm xoay và chỉ số gương đầu tiên
2. Từ chỉ số gương đầu tiên đến điểm trục, thay thế hay không
Đối với mỗi chỉ số giữa chỉ số nhân bản m1 và chỉ số trục p, chúng tôi quyết định ngẫu nhiên có nên thay thế các phần tử đó hay không.
Nếu chúng tôi quyết định thay thế, thì chúng tôi thay thế phần tử danh sách trên i1 bằng phần tử trên i1', hình ảnh của nó trên chỉ mục nhân bản. Nghĩa là, i1 được thay thế bằng i1'=m1-(i1-m1), sao cho khoảng cách từ i1 và i1' đến m1 bằng nhau.
Chúng tôi đưa ra cùng một quyết định hoán đổi hay không cho từng chỉ số giữa m1 và p.
Mô tả hình ảnh
3. Tính chỉ số gương thứ hai
Sau khi đưa ra tất cả các quyết định về chỉ số từ m1 đến p, bây giờ chúng ta tìm chỉ số nhân bản thứ hai với m2 là điểm giữa, tức là điểm cách đều p và điểm cuối của danh sách. Đó là m2=m1+n/2.
Mô tả hình ảnh
4. Từ điểm xoay đến gương thứ hai, thay thế hoặc không
Cuối cùng, chúng tôi lặp lại quy trình hoán đổi hoặc không, xem xét tất cả các quyết định thay thế p từ điểm đến trục, tức là các quyết định từ p sang gương thứ hai m2. Nếu chúng tôi chọn không thay thế, chúng tôi chuyển sang cái tiếp theo. Nếu chúng ta chọn thay thế, thì chúng ta thay thế phần tử trên j1 bằng hình ảnh phản chiếu của nó trên j1' tại chỉ số phản chiếu m2.
Mô tả hình ảnh
quyết định trao đổi hay không từ trục sang chỉ số nhân bản thứ hai
Vào cuối một vòng, chúng tôi đã xem xét tất cả các chỉ số giữa m1 và m2, tức là một nửa của tất cả các chỉ số và mỗi chỉ số có một chỉ số cụ thể trong nửa còn lại, cho dù được thay thế hay không. Vì vậy, liên quan đến việc thay thế hay không, tất cả các chỉ số đã được xem xét một lần.
Vòng tiếp theo bắt đầu bằng các vòng tăng dần (hoặc giảm dần) để chúng ta có chỉ số trục mới, sau đó bắt đầu quay vòng qua quy trình được mô tả ở trên.
Mô tả hình ảnh
Quá trình di chuyển từ gương này sang gương khác trong cùng một vòng
nơi khéo léohoàn thànhKhi quyết định có nên thay thế hay không, thuật toán sẽ thông minh chọn chỉ số ứng cử viên cao hơn hoặc hình ảnh phản chiếu của nó. Có nghĩa là khi nó ở dưới trục, i_1 được chọn thay vì i_1'; khi nó ở trên trục, i_k' được chọn thay vì i_k. Điều này có nghĩa là chúng ta có thể lặp lại các chỉ số trong danh sách một cách linh hoạt: chúng ta có thể tách 0 đến m1 và p đến m2 thành hai vòng lặp riêng biệt hoặc kết hợp cả hai trong cùng một vòng lặp từ m1 đến m2, như tôi đã làm ở trên được mô tả trong văn bản (Và
hoàn thành
)của. Kết quả là giống nhau theo cả hai cách: không quan trọng tôi xem xét i_1 hay mirror i_1'; sự thay thế hay không mang lại kết quả tương tự.vòngTrong Eth2, quá trình trên sẽ được thực hiện 90 lần.bản gốcNgười ta đề cập rằng phải mất 6lgN vòng để "bắt đầu thể hiện mức bảo mật tốt khi tấn công mật khẩu có chọn lọc (CCA)", trong đó N là độ dài của danh sách. tại Vitalik
đặc tả chú thích
Vào năm 2014, ông nói rằng "các chuyên gia về mật mã gợi ý rằng chúng tôi có các vòng 4log2N để cung cấp đủ bảo mật". Số lượng trình xác nhận tối đa tuyệt đối trong Eth2, là số lần tối đa chúng tôi cần xáo trộn danh sách, là khoảng 222 (4,2 triệu). Giá trị ước tính do Vitalik đưa ra là 88 vòng và giá trị ước tính trong bài báo là 92 vòng (giả sử lg là logarit tự nhiên). Vì vậy, chúng tôi hiện đang ở trong một phạm vi gần như chính xác, đặc biệt là vì rất có thể chúng tôi sẽ không kết thúc với nhiều trình xác nhận đang hoạt động như vậy.Issue FViệc điều chỉnh các vòng dựa trên độ dài danh sách có thể mang lại kết quả thú vị, nhưng chúng tôi sẽ không làm điều đó, đó có thể là một tối ưu hóa không cần thiết.
Thật thú vị, khi Least Authority kiểm tra thông số kỹ thuật của Beacon Chain, ban đầu họ phát hiện ra rằng có sự sai lệch trong việc xáo trộn chọn những người đề xuất khối (xem
). Nhưng hóa ra họ đã sử dụng nhầm cấu hình xáo trộn chỉ có 10 vòng. Khi họ tăng cấu hình xáo trộn lên 90 vòng (con số chúng tôi sử dụng trên mạng chính), độ lệch đã biến mất.
(giả)ngẫu nhiên
Thuật toán xáo trộn yêu cầu chúng tôi chọn ngẫu nhiên một điểm trục trong mỗi vòng và chọn ngẫu nhiên xem có thay thế từng phần tử trong mỗi vòng hay không.
Trong Eth2, chúng tôi chắc chắn tạo ra tính ngẫu nhiên từ một giá trị hạt giống, theo đó cùng một hạt giống sẽ luôn tạo ra kết quả xáo trộn giống nhau.
Các chỉ báo trục được tạo bằng cách băm SHA2 8 byte của hạt giống được nối với vòng,
Chỉ số trục được tạo từ tám byte hàm băm SHA2 của giá trị gốc được nối với các vòng, do đó, chỉ số này thường thay đổi sau mỗi vòng.
Các bit quyết định được sử dụng để quyết định có thay thế một phần tử hay không được trích xuất từ các phần tử sau: hàm băm SHA256 của hạt giống, vòng, chỉ mục của phần tử trong danh sách.
hiệu quả
Thuật toán xáo trộn này chậm hơn nhiều so với thuật toán Fisher-Yates. Nếu thuật toán Fisher-Yates yêu cầu N lần xáo trộn, thì thuật toán của chúng tôi yêu cầu trung bình 90N/4 lần xáo trộn. Chúng ta cũng phải xem xét việc tạo ra giả ngẫu nhiên, đây là phần đắt nhất của thuật toán. Fisher-Yates cần độ ngẫu nhiên gần với Nlog2N chữ số và chúng tôi cần 90(log2N+N/2) chữ số Theo phạm vi giá trị N mà chúng tôi cần trong Eth2, các chữ số dư thừa là khá nhiều (khi N là một triệu , Eth2 cần khoảng hai lần N).
Tại sao chọn thuật toán hoán đổi hoặc không?
Nếu nó không hiệu quả, tại sao bạn lại chọn triển khai này?
xáo trộn một yếu tố duy nhất
Vì vậy, nếu chúng ta muốn biết phần tử tại chỉ mục 217 đã được xáo trộn ở đâu, chúng ta chỉ có thể chạy thuật toán cho chỉ mục đó mà không cần xáo trộn toàn bộ danh sách. Ngoài ra, ngược lại, nếu chúng ta muốn biết phần tử nào đã được xáo trộn thành chỉ số 217, chúng ta có thể chạy thuật toán ngược lại để tìm phần tử 217 (nghịch nghĩa là chạy các vòng từ cao xuống thấp, không phải từ thấp đến cao ).
thông số kỹ thuật của ETH2
Nội dung được viết là về cách áp dụng thuật toán để xáo trộn một chỉ mục. Trên thực tế, việc xáo trộn toàn bộ danh sách cùng một lúc chỉ là một cách tối ưu hóa danh sách đó! Nếu muốn, chúng ta chỉ có thể xáo trộn lần lượt một phần tử của danh sách: (đảo ngược) chạy xáo trộn để tìm phần tử kết thúc ở chỉ mục 0, chạy một lần xáo trộn khác để tìm phần tử kết thúc ở chỉ mục 1, v.v. Lý do chúng tôi không làm điều đó đơn giản là do quyết định hoán đổi hay không cần tạo hàm băm 256 bit cùng một lúc và việc loại bỏ 255 bit như vậy sẽ rất lãng phí. Nếu chúng ta sử dụng hàm băm hoặc tiên tri 1 bit, thì việc xáo trộn một phần tử của danh sách cũng hiệu quả như xáo trộn toàn bộ danh sách.
Hãy là một khách hàng "nhẹ nhàng" thực sự
lịch sửđâyđâyđâyKiểm tra cuộc thảo luận về nhiệm vụ ban đầu cho thuật toán xáo trộn cho Eth2,
cuối cùng
cuối cùng
Tuyên bố miễn trừ trách nhiệm: Công việc dịch thuật của ECN nhằm mục đích cung cấp thông tin và tài nguyên học tập chất lượng cao cho cộng đồng Ethereum Trung Quốc. Bản quyền của bài viết thuộc về tác giả gốc. Các bản in lại phải ghi rõ nguồn của văn bản gốc và ethereum.cn. Về lâu dài tái bản, vui lòng liên hệ ethereumcn@gmail.com Ủy quyền.
