Ý tưởng về BAF được lấy cảm hứng từ nghiên cứu tuyệt vời của Tony về BAL, thực tế là tôi đã đăng nó lần đầu tiên để phản hồi bài đăng của anh ấy . Dưới đây tôi cố gắng giải thích ý tưởng này rõ hơn.
Hãy coi bài đăng này như một bản tóm tắt ý tưởng hơn là một bản thiết kế hoàn thiện.
Thời gian khe rõ ràng bị giới hạn bởi thời gian cần thiết để khuếch tán thay đổi trạng thái trong mạng, vì thông tin về thay đổi được yêu cầu bởi trình xây dựng Block tiếp theo. Cho dù ở dạng Block (danh sách các giao dịch sẽ được thực hiện) hay ở dạng BAL (tập hợp các thay đổi trạng thái), điều này có nghĩa là gửi khá nhiều dữ liệu trên toàn thế giới.
Sự phụ thuộc này thường được mô hình hóa một cách tao nhã bằng giới hạn trên giả định \Delta Δ về độ trễ mạng. Tuy nhiên, trên thực tế, độ trễ mạng phụ thuộc vào kích thước của thông tin cần truyền bá.
Sẽ thế nào nếu chúng ta có thể đẩy nhanh một lượng thông tin nhỏ , đủ để bắt đầu chuẩn bị Block tiếp theo trước khi Block thực tế xuất hiện?
BAF hướng đến mục đích chính xác này. BAF là bộ lọc Bloom nhỏ xác định phần S' của trạng thái S mà Block i không truy cập được. Do đó, bất kỳ thao tác nào trên S' đều an toàn khi thực hiện trong Block i+1, ngay cả khi không biết Block i.
Nhưng bộ lọc Bloom lại “lỏng lẻo”, làm sao điều này có thể xảy ra?
Chúng tôi lấy BAL (sẽ có thêm thông tin chi tiết về loại BAL mà chúng tôi sử dụng sau) và nén nó bằng bộ lọc Bloom để có được BAF. Sau đó, chúng tôi sử dụng e của trạng thái "chưa được chạm tới" (chưa được truy cập) bởi Block i.
Chúng ta có thể thấy bộ lọc bloom như một nén mất mát. Nó có kích thước nhỏ cố định và nó:
- có Kết quả dương tính giả (FP): chúng tôi nghĩ rằng một số
eđã được truy cập, trong khi nó không phải - không có Kết quả âm tính giả (FN): chúng tôi nghĩ rằng một số trạng thái
ekhông được truy cập nhưng thực tế đã được truy cập.
Vì vậy, mặc dù bộ lọc bloom không chính xác, nhưng đây không phải là vấn đề đối với chúng ta khi chúng ta sử dụng nó theo cách phủ định. Chúng ta có thể loại trừ quá nhiều phần tử (vì FP), nhưng chúng ta không bao giờ bao gồm thứ gì đó đã được Block i sửa đổi (vì đó sẽ là FN).
Bộ lọc này có thể nhỏ được không?
Hiện tại, kích thước BAL trung bình chưa nén là 55 KB với mỗi mục dài 32 + 20 = 52 byte . Tương đương với khoảng 1000 mục.
Giả sử chúng ta sử dụng bộ lọc bloom 1KB, dễ dàng phù hợp với một gói IP. Tức là 8196 Bits, khá nhiều không gian cho một bộ lọc bloom. Bộ lọc bloom được định nghĩa bởi k hàm Hash , mỗi hàm ánh xạ một phần tử tới một vị trí duy nhất trong số 8196. Khi thêm một phần tử vào bộ lọc bloom, mỗi bit trong số Bits này sẽ được bật (nếu nó chưa được bật). Khi kiểm tra một phần tử, chúng ta có thể chắc chắn rằng nó không được thêm vào nếu ít nhất một trong Bits này là 0.
Số lượng lý tưởng của hàm Hash được xác định bởi
Xác suất FP của chúng ta sau đó có thể được ước tính như sau:
Người sử dụng BAF này sau đó có thể kiểm tra xem một giao dịch nhất định có khả năng gây nhiễu đến Block khác hay không, ngay cả khi không có Block hoặc BAL, và có thể biết chắc chắn liệu nó có thể gây nhiễu hay không.
Nội dung và mức độ chi tiết của BAF nên như thế nào?
Có nhiều lựa chọn thiết kế khác nhau ở đây:
- mức độ chi tiết cấp tài khoản so với mức độ chi tiết cấp khe cắm
- truy cập trạng thái so với sửa đổi trạng thái
Tài khoản so với mức độ chi tiết của khe cắm
Đối với quyền truy cập của tiểu bang, cả mức độ chi tiết của tài khoản và mức độ khe cắm đều có thể có ý nghĩa. Mức độ tài khoản có nghĩa là bộ lọc trống hơn nhưng loại trừ có cấu trúc nhiều hơn; mức độ khe cắm có nghĩa là loại trừ ít hơn nhưng bộ lọc bão hòa hơn, nghĩa là tỷ lệ FP cao hơn. Ước tính 2% ở trên là với mức sau này.
Người gửi giao dịch cũng cần loại trừ ở cấp độ tài khoản để tránh xung đột Nonce .
Điều thú vị là, nếu cần, chúng ta có thể dễ dàng kết hợp hai mức độ chi tiết khác nhau trong cùng một bộ lọc bằng cách sử dụng phép toán OR nhị phân, thêm cả người gửi giao dịch cấp tài khoản và thông tin truy cập trạng thái cấp khe trong cùng một bitmap.
Truy cập trạng thái so với sửa đổi trạng thái
Lưu ý rằng theo định nghĩa, bộ lọc mức truy cập trạng thái BAF bão hòa hơn (có nhiều số 1 hơn) so với bộ lọc mức sửa đổi trạng thái (từ giờ chúng ta gọi là BMF).
BMF
Chúng ta có thể sử dụng BMF để giúp người xây dựng bắt đầu chuẩn bị khối của họ. Giả sử BMF có thể tiếp cận người xây dựng Block tiếp theo trong một phần nhỏ thời gian khe cắm (ví dụ 300ms), nó có thể được sử dụng để bắt đầu chuẩn bị một phần Block không phụ thuộc vào khối trước đó.
BMF có thể hữu ích để tăng tốc thời gian khe cắm, đảm bảo chuỗi khối không bị xung đột. Bằng cách biết BMF của Block i, người xây dựng Block i+1 có thể bắt đầu xây dựng trên trạng thái không thay đổi giữa Block i-1 và Block i. Trên thực tế, điều này cho phép nó quyết định vào phút cuối xem có nên dựa Block của mình vào Block i hay Block i-1 không.
BAF
Thay vào đó, BAF cuối cùng có thể hữu ích cho việc xây dựng Block song song. Nếu một người xây dựng tôn trọng BAF của một Block khác, thì hai khối trở nên song song hóa được, hay nói cách khác là độc lập về thứ tự, khi cuối cùng được sắp xếp thành một chuỗi.
Bảo vệ BAF (hoặc BMF)
Signinig: BAF có thể được Block Producer ký và thực thi
Nghiêm ngặt: nếu được ký và thực thi, chúng ta có thể đưa ra yêu cầu rằng BAF phải chính xác, không phải nhiều hơn bộ lọc được tạo ra trong quá trình thực hiện lại
Định giá BAF
Có những giao dịch chỉ đơn giản là truy cập vào nhiều trạng thái, dẫn đến BAL lớn và BAF bão hòa. Những điều này rõ ràng làm giảm khả năng song song hóa dựa trên BMF và BAF.
Có hợp lý không khi làm cho việc sở hữu một BAF đầy đủ trở nên tốn kém? Tôi không chắc đây có phải là ý tưởng đúng đắn không, nhưng nó có thể là một phần của không gian thiết kế.
Combo không may mắn
Là một bộ lọc xác suất, có thể xảy ra trường hợp một số kết hợp tạo ra BAF bão hòa ngay cả khi trạng thái được truy cập (hoặc sửa đổi) không lớn như vậy. Đây là sự kết hợp không may của các hàm Hash tạo thành Bits của bộ lọc bloom.
Chúng ta có thể giảm thiểu tác động này bằng cách sử dụng cấu trúc bộ lọc bloom "xoay", bằng cách làm cho các hàm Hash phụ thuộc vào số khe (hoặc chiều cao chuỗi ). Chúng ta thậm chí có thể thực hiện thay đổi này dần dần, dịch chuyển vào/ra các hàm Hash từng cái một khi Block Height tăng lên.
