PANDAS: Một cách tiếp cận thực tế cho việc lấy mẫu dữ liệu khả dụng thế hệ tiếp theo trong Ethereum
Tác giả: Onur Ascigil1, Michał Król2, Matthieu Pigaglio3, Sergi Reñé4, Etienne Rivière3, Ramin Sadre3
Tóm tắt
- PANDAS là giao thức lớp mạng hỗ trợ Danksharding với blob 32 MB trở lên.
- PANDAS đặt mục tiêu đạt được thời hạn 4 giây cho việc lấy mẫu ngẫu nhiên (theo mô hình lựa chọn Fork chặt chẽ ).
- Sau khi tách người đề xuất-người xây dựng (PBS) , những người xây dựng tháo vát sẽ thực hiện việc phân phối ban đầu (tức là gieo hạt) các mẫu tới các nút.
- PANDAS tiến hành theo hai giai đoạn trong mỗi khe: 1) Giai đoạn gieo hạt, trong đó người xây dựng khe được chọn sẽ phân phối các tập hợp con các hàng và cột của một blob được mã hóa 2 chiều cho các nút xác thực và 2) Giai đoạn hợp nhất và lấy mẫu hàng/cột, trong đó các nút lấy mẫu các ô ngẫu nhiên và đồng thời truy xuất và tái tạo các hàng/cột được chỉ định để tăng cường tính khả dụng của dữ liệu các ô.
- PANDAS sử dụng phương pháp truyền thông trực tiếp , nghĩa là truyền thông 1 bước, tức là truyền thông điểm-đến-điểm, cho cả giai đoạn gieo hạt và lấy mẫu thay vì phương pháp truyền tin đồn, truyền thông nhiều bước hoặc DHT.
Chúng tôi đưa ra những giả định sau khi thiết kế PANDAS:
Giả định 1) Người xây dựng tháo vát: Theo sơ đồ Phân tách người đề xuất-người xây dựng (PBS) , trong PANDAS, một tập hợp những người xây dựng tháo vát — ví dụ, các phiên bản đám mây có băng thông tải lên đủ cao như 500 Mbps trở lên — thực hiện việc phân phối các mẫu hạt giống cho mạng. [1]
Giả định 2) Động lực của người xây dựng: Người xây dựng có động lực để dữ liệu blob có sẵn vì Block sẽ chỉ được chấp nhận nếu DAS thành công. Tuy nhiên, những người xây dựng khác nhau có thể có lượng tài nguyên khác nhau. Mối quan tâm của những người xây dựng hợp lý là đảm bảo rằng dữ liệu sẽ được coi là có sẵn trong khi chi tiêu một lượng tài nguyên tối thiểu.
Giả định 3) Các nút xác thực (VN) là các thực thể chính của giao thức DAS: Một nút xác thực (VN) duy nhất chỉ thực hiện một hoạt động lấy mẫu duy nhất (như một thực thể), không phụ thuộc vào số lượng trình xác thực mà nó lưu trữ.
Giả định 4) Phần lớn không trung thực: Phần lớn (hoặc thậm chí là đại đa số) các VN và người xây dựng có thể có ác ý và do đó có thể không tuân thủ đúng giao thức.
Giả định 5) VN kháng Sybil : Một VN trung thực có thể sử dụng một chương trình Proof-of-Validator để chứng minh rằng nó lưu trữ ít nhất một trình xác thực. Nếu nhiều nút cố gắng sử dụng lại cùng một bằng chứng, chúng có thể bị các nút và trình xây dựng trung thực khác đưa vào danh sách chặn.
Dưới đây là các mục tiêu của PANDAS:
Mục tiêu 1) Lựa chọn Fork chặt chẽ: Các nút xác thực trung thực (VN) hoàn tất việc lấy mẫu ngẫu nhiên trước khi bỏ phiếu cho một Block, ngay cả khi phần lớn các VN là độc hại *.* Do đó, chúng tôi nhắm mục tiêu vào mô hình lựa chọn Fork chặt chẽ , nghĩa là các VN trung thực trong ủy ban của một vị trí phải hoàn tất việc lấy mẫu ngẫu nhiên trước khi bỏ phiếu trong vòng bốn giây vào vị trí đó.
Mục tiêu 2) Chiến lược gieo hạt linh hoạt của trình xây dựng: Với việc các trình xây dựng khác nhau có thể có các tài nguyên khác nhau, thiết kế của chúng tôi cho phép trình xây dựng Block có sự linh hoạt để triển khai các chiến lược phân phối blob khác nhau, mỗi chiến lược có sự đánh đổi khác nhau giữa bảo mật và việc sử dụng tài nguyên. Để có tính bảo mật cao hơn, trình xây dựng có thể gửi nhiều bản sao của các ô blob đến các nút xác thực, đảm bảo tính khả dụng cao hơn. Ngược lại, để giảm thiểu việc sử dụng tài nguyên, trình xây dựng có thể phân phối tối đa một bản sao của mỗi ô, giảm mức sử dụng băng thông với cái giá phải trả là tính bảo mật thấp hơn. Cách tiếp cận linh hoạt này cho phép trình xây dựng điều hướng sự đánh đổi giữa việc đảm bảo tính khả dụng của dữ liệu và tối ưu hóa băng thông trong khi vẫn có động lực để Block được các nút xác thực coi là khả dụng để chấp nhận.
Mục tiêu 3) Cho phép các chế độ xem nút không nhất quán: Mục tiêu của chúng tôi là đảm bảo rằng các VN và người xây dựng không bắt buộc phải đạt được Consensus về danh sách các VN. Mặc dù chúng tôi hướng đến việc các VN và người xây dựng thống nhất chung về tập hợp các VN trong hệ thống, nhưng các VN không nhất thiết phải duy trì chế độ xem nhất quán nghiêm ngặt hoặc chế độ xem của người xây dựng và VN phải được đồng bộ hóa hoàn toàn.
Thiết kế PANDAS
Khám phá ngang hàng liên tục: Để đạt được Mục tiêu 3, các nút trong hệ thống thực hiện khám phá ngang hàng liên tục song song với các giai đoạn giao thức bên dưới để duy trì “chế độ xem” cập nhật chứa các ngang hàng khác. Người xây dựng và các VN có mục tiêu khám phá tất cả các VN có Proof-of-Validator hợp lệ. Chúng tôi mong đợi cả người xây dựng và các VN đều có chế độ xem gần nhưng không hoàn hảo về tất cả các VN trong hệ thống.
Dịch vụ thành viên chạy giao thức khám phá ngang hàng sẽ chèn các VN mới (đã xác minh) vào chế độ xem và cuối cùng hội tụ thành một bộ VN hoàn chỉnh. Các thông báo khám phá ngang hàng được liên kết với các thông báo yêu cầu mẫu để giảm chi phí khám phá.
Giao thức PANDAS có hai giai đoạn (không phối hợp), lặp lại trong mỗi khe:
Giai đoạn 1 ) Gieo hạt,
Giai đoạn 2) Củng cố hàng/cột và lấy mẫu
Trong giai đoạn gieo hạt, trình xây dựng đẩy các tập hợp con của hàng/cột trực tiếp đến các VN, nơi việc gán hàng/cột dựa trên một hàm xác định. Khi một VN nhận được các mẫu của mình từ trình xây dựng, nó sẽ hợp nhất toàn bộ hàng/cột mà nó được gán (bằng cách yêu cầu các ô bị thiếu từ các VN khác được gán cho hàng/cột tương ứng) và đồng thời thực hiện lấy mẫu ngẫu nhiên.
Các VN không phối hợp để bắt đầu hợp nhất và lấy mẫu. Do đó, một nút hoàn thành giai đoạn 1 có thể bắt đầu giai đoạn 2 ngay lập tức mà không cần phối hợp với các nút khác. Các VN là thành viên ủy ban của một khe phải hoàn thành việc gieo hạt và lấy mẫu ngẫu nhiên trong vòng 4 giây vào khe.
Dưới đây, chúng tôi giải thích chi tiết hai giai đoạn của giao thức.
Giai đoạn 1- Gieo hạt : Trình xây dựng gán VN cho từng hàng/cột bằng hàm xác định sử dụng không gian băm như chúng tôi giải thích bên dưới. Việc ánh xạ VN này vào từng hàng/cột là động và thay đổi trong từng khe. Việc ánh xạ cho phép các nút ánh xạ cục bộ và xác định các nút vào các hàng/cột mà không cần biết số lượng hoặc danh sách đầy đủ các nút.
Người xây dựng chuẩn bị và phân phối các mẫu hạt giống cho các VN như sau:
1.a) Ánh xạ các Hàng/Cột vào các vùng tĩnh trong không gian băm: Các hàng và cột riêng lẻ được gán các vùng tĩnh trong không gian băm như thể hiện ở phần trên của Hình 1.
1.b) Ánh xạ VN vào một không gian băm : Trình xây dựng sử dụng hàm sắp xếp FNODE(NodeID, epoch, slot, R) để gán mỗi VN cho một khóa trong không gian băm. Hàm này lấy các tham số như NodeID, là định danh của nút (tức là, ID ngang hàng), số epoch và slot, và một giá trị ngẫu nhiên R lấy từ tiêu đề của Block Header từ slot trước đó.
Hình 1: Gán mẫu hàng cho VN. Các mẫu cột được ánh xạ tương tự.
Một VN được gán cho vùng của một hàng sẽ nhận được một tập hợp con các ô thuộc về hàng đó từ trình xây dựng. Khi các VN được ánh xạ lại vào không gian băm trong mỗi khe bằng FNODE, các chỉ định hàng/cột của chúng cũng có thể thay đổi.
LƯU Ý: Không thể gán động các hàng và cột cho VN theo từng khe trong phương pháp gieo hạt dựa trên tin đồn, trong đó các kênh tin đồn theo từng hàng và từng cột phải tương đối ổn định theo thời gian.
1.c) Phân phối mẫu hàng/cột: Đối với mỗi hàng và cột, trình xây dựng áp dụng chiến lược phân phối nỗ lực tốt nhất để đẩy các tập hợp con của mỗi hàng/cột đến các VN được ánh xạ đến vùng hàng/cột tương ứng. Trình xây dựng sử dụng phương pháp truyền thông trực tiếp, đặc biệt là giao thức dựa trên UDP, để phân phối các ô cho mỗi hàng/cột trực tiếp đến các VN.
Cơ sở cho việc giao tiếp trực tiếp *:* Chúng tôi đặt mục tiêu hoàn tất giai đoạn gieo hạt giống nhanh nhất có thể để các thành viên ủy ban có thời gian hoàn thành việc lấy mẫu ngẫu nhiên trước khi bỏ phiếu (Mục tiêu 1).
Chiến lược phân phối hàng/cột: Chúng tôi cho phép các nhà xây dựng lựa chọn các chiến lược phân phối dựa trên tính khả dụng của tài nguyên theo Mục tiêu 2. Có sự đánh đổi giữa việc sử dụng tài nguyên và tính khả dụng của dữ liệu đối với các chiến lược phân phối khác nhau. Hãy xem xét ví dụ trong Hình 2 để phân phối hai hàng. Trong một trường hợp cực đoan (bên trái), nhà xây dựng phân phối toàn bộ hàng 1 cho mỗi VN trong vùng của hàng đó để cải thiện tính khả dụng của dữ liệu với cái giá phải trả là mức sử dụng tài nguyên cao hơn. Trong một trường hợp cực đoan khác, nhà xây dựng gửi các phần hàng không chồng lấn của hàng 6 đến mỗi VN trong vùng của hàng đó, điều này đòi hỏi ít tài nguyên hơn nhưng dẫn đến tính khả dụng của từng ô ít hơn.
Hiện chúng tôi đang đánh giá các chiến lược phân phối khác nhau, bao gồm các chiến lược có thể ánh xạ xác định từng ô riêng lẻ của hàng/cột thành từng VN riêng lẻ trong vùng hàng/cột đó.
LƯU Ý : Người xây dựng chỉ tham gia vào giai đoạn Gieo hạt.
Hình 2: Hai chiến lược (cực đoan) để phân phối các mẫu hàng cho các VN trong vùng hàng tương ứng.
Giai đoạn 2 - Hợp nhất hàng/cột và lấy mẫu : Các VN là một phần của ủy ban khe hiện tại có mục tiêu hoàn thành việc lấy mẫu ngẫu nhiên trong vòng bốn giây đầu tiên của khe (tức là thời hạn bỏ phiếu). Để tăng tính khả dụng của các ô, đặc biệt là đối với các thành viên ủy ban của khe phải thực hiện lấy mẫu (ngẫu nhiên) trong vòng bốn giây, các VN cũng hợp nhất, tức là, truy xuất toàn bộ hàng và cột mà chúng được chỉ định dựa trên ánh xạ FNODE như một phần của việc lấy mẫu hàng/cột.
2.a) Lấy mẫu ngẫu nhiên VN: Các VN trong ủy ban của vị trí hiện tại sẽ cố gắng lấy 73 tế bào được chọn ngẫu nhiên ngay khi nhận được mẫu hạt giống từ người xây dựng.
Bằng cách sử dụng phép gán xác định FNODE, VN có thể xác định cục bộ các nút dự kiến sẽ quản lý một hàng hoặc cột nhất định.
Thuật toán lấy mẫu: Một số nút này có thể ngoại tuyến hoặc không phản hồi. Việc gửi yêu cầu tuần tự cho các ô có nguy cơ bỏ lỡ thời hạn 4 giây cho các thành viên ủy ban.
Hình 3: Ví dụ về việc lấy mẫu: Các hàng và cột được gán cho mỗi VN được hiển thị ở đầu VN tương ứng. VN14 biết gửi yêu cầu đến VN78 để lấy ô một dựa trên kiến thức về FNODE ánh xạ.
Đồng thời, việc gửi yêu cầu đến tất cả các đồng cấp đang giữ bản sao sẽ dẫn đến sự bùng nổ của các tin nhắn trong mạng và chịu rủi ro tắc nghẽn. Do đó, việc lấy dữ liệu phải tìm kiếm sự cân bằng giữa việc sử dụng các yêu cầu song song và dự phòng một mặt và các ràng buộc về độ trễ mặt khác. Phương pháp của chúng tôi sử dụng chiến lược lấy dữ liệu tế bào thích ứng bằng cách sử dụng giao tiếp trực tiếp giữa các nút thông qua giao thức dựa trên UDP (không kết nối). Thuật toán lấy dữ liệu có thể chịu được các mất mát và các nút ngoại tuyến.
2.b) Hợp nhất hàng/cột VN: Nếu một VN nhận được ít hơn một nửa số ô của hàng hoặc cột được chỉ định từ trình xây dựng (do chiến lược phân phối được trình xây dựng lựa chọn), nó sẽ yêu cầu các ô bị thiếu từ các VN khác. Một VN chỉ yêu cầu các ô từ các VN được chỉ định cho cùng một vùng hàng/cột trong quá trình hợp nhất hàng/cột. Khi một VN có một nửa số ô của một hàng hoặc cột, nó có thể tái tạo cục bộ toàn bộ hàng hoặc cột.
Cơ sở hợp nhất hàng/cột:
- Tái tạo các tế bào bị mất : trong khi thực hiện lấy mẫu theo hàng/cột, VN sẽ tái tạo các tế bào bị mất.
- Để tăng cường tính khả dụng của các ô : Với ánh xạ xác định (FNODE), trình xây dựng có thể chọn bất kỳ chiến lược phân phối nào để gửi các tập hợp con của các hàng và cột đến các VN. Hợp nhất hàng/cột nhằm mục đích cải thiện tính khả dụng của các mẫu để có thể hoàn thành việc lấy mẫu ngẫu nhiên đúng thời hạn.
Về mặt lý tưởng, người xây dựng nên chọn một chiến lược phân phối mẫu hạt giống cho phép các VN hợp nhất các hàng và cột một cách hiệu quả. Để tạo điều kiện thuận lợi cho việc này, người xây dựng có thể đẩy mỗi VN một bản đồ (cùng với các mẫu hạt giống) nêu chi tiết cách các ô riêng lẻ của một hàng/cột được chỉ định cho các VN trong vùng của hàng/cột đó như một phần của chiến lược phân phối của người xây dựng. Với bản đồ này, các VN có thể nhanh chóng xác định và truy xuất các ô bị thiếu để tái tạo một hàng hoàn chỉnh, do đó cải thiện tính khả dụng của dữ liệu.
LƯU Ý: Trong một số phương pháp tiếp cận DAS, thuật ngữ 'lấy mẫu hàng/cột' ám chỉ các nút truy xuất nhiều hàng và cột trước khi bỏ phiếu về tính khả dụng của blob. Trong phương pháp tiếp cận của chúng tôi, các nút truy xuất các hàng và cột để tăng cường tính khả dụng của dữ liệu, hỗ trợ các trình xác thực phải thực hiện lấy mẫu ngẫu nhiên trước khi bỏ phiếu.
Chúng tôi gọi đây là 'hợp nhất hàng/cột' thay vì 'lấy mẫu hàng/cột' vì trong PANDAS, các thành viên ủy ban bỏ phiếu dựa trên lấy mẫu ngẫu nhiên và họ không trực tiếp lấy mẫu toàn bộ hàng hoặc cột.
Còn các nút thông thường (RN) thì sao?
Không giống như VN, RN không lấy mẫu hàng/cột hạt giống từ người xây dựng. Người xây dựng gửi mẫu hạt giống ban đầu đến nhóm VN kháng Sybil sử dụng chương trình Proof-of-Validator . Hiện tại không có cơ chế nào để RN chứng minh rằng họ không phải là Sybil; do đó, việc phân phối mẫu ban đầu từ người xây dựng chỉ sử dụng VN.
Sử dụng hàm xác định công khai FNODE, RN có thể được ánh xạ tương tự đến các vùng hàng/cột riêng lẻ. Sau khi được ánh xạ đến một vùng, RN có thể (tùy chọn) thực hiện hợp nhất hàng/cột để truy xuất toàn bộ hàng và cột và phản hồi các truy vấn cho các ô trong vùng được chỉ định của chúng.
Giống như các nút khác, RN phải thực hiện khám phá ngang hàng. Nhìn chung, RN hướng đến khám phá tất cả các VN và cũng có thể tìm cách khám phá các RN khác. Với kiến thức về các ngang hàng khác thông qua khám phá ngang hàng, RN có thể thực hiện lấy mẫu ngẫu nhiên thông qua giao tiếp trực tiếp. Không giống như VN, RN không bị ràng buộc nghiêm ngặt về thời gian để hoàn thành việc lấy mẫu — chúng có thể bắt đầu lấy mẫu sau các VN, ví dụ, sau khi nhận được Block Header cho khe hiện tại.
Thảo luận & Công việc đang diễn ra
Chúng tôi cho rằng những người xây dựng hợp lý có động cơ cắt giảm chi phí (và cung cấp dưới mức cần thiết) nhưng đồng thời, hướng đến mục tiêu tạo ra các khối khả dụng (để được thưởng). Điều này ngụ ý rằng những người xây dựng sẽ hướng đến việc hợp nhất hàng/cột sao cho hiệu quả nhất có thể, tức là với việc hợp nhất hiệu quả, giúp tăng tính khả dụng của các ô, người xây dựng có thể gửi ít bản sao hơn của mỗi ô trong giai đoạn gieo hạt để cắt giảm chi phí.
Hiện tại chúng tôi đang thử nghiệm các chiến lược phân phối khác nhau với các VN độc hại giữ lại các mẫu và cố gắng phá vỡ quá trình khám phá ngang hàng. Mã mô phỏng DAS của chúng tôi có sẵn trên kho lưu trữ GitHub của DataHop .
[1] Đại học Lancaster, Vương quốc Anh
2 City, Đại học London, Vương quốc Anh
3 Đại học Công giáo Louvain (UCLouvain)
4 Phòng thí nghiệm DataHop
