Bộ lọc bloom là gì?

Bloom Filter là gì? Bộ lọc Bloom (Filter Bloom), được phát triển vào năm 1970 bởi Burton Howard Bloom, thông báo cho người dùng biết một mục nhất định có thuộc một bộ hay không. Tuy nhiên, bộ lọc chỉ có thể hiển thị hoàn toàn chắc chắn rằng một mục không có trong tập hợp. Nếu nó chỉ ra rằng mục đó nằm trong bộ, trong một số trường hợp, điều này có thể sai.

Bloom Filter là gì? Do hiệu quả tiết kiệm không gian, bộ lọc Bloom hấp dẫn cho nhiều ứng dụng khác nhau. Trong thế giới tiền điện tử, chúng được sử dụng rộng rãi trong Simplified Payment Verification (SPV), đặc biệt là khi nói đến Bitcoin.

Người dùng có thể sử dụng mạng Bitcoin mà không cần vận hành các nút đầy đủ bằng cách sử dụng máy khách SPV. Rất khó để chạy các nút đầy đủ trên các thiết bị có công suất thấp như điện thoại thông minh vì chúng có các yêu cầu lưu trữ và xử lý cụ thể. Do đó, khách hàng SPV chỉ có thể hỏi các nút đầy đủ để biết thông tin về ví của họ.

Cách đơn giản nhất để lấy thông tin này là làm cho các nút đầy đủ nhận biết được các khóa của người dùng. Bằng cách này, chỉ các giao dịch có liên quan mới được chuyển đến họ. Tuy nhiên, đây là một lựa chọn tồi vì quyền riêng tư của người dùng sẽ bị xâm phạm theo cách này.

Mặc dù tải xuống tất cả các giao dịch chỉ để xóa phần lớn trong số đó cũng không phải là một lựa chọn tốt vì nó sẽ lãng phí rất nhiều băng thông. Đó là lúc bộ lọc Bloom ra tay giải cứu.

Bloom Filter là gì? Hãy tưởng tượng rằng Anna là một khách hàng và John là một nút đầy đủ. Anna có một giao dịch tốn kém nhưng cô ấy không muốn John biết về nó. Vì vậy, cô ấy cần phải tìm cách "che đậy" giao dịch của mình. Để làm điều đó, cô ấy tạo một bộ lọc Bloom. Giả sử rằng nó trông như thế:

3 4 2 1 6 8 7 5 0 9

Cô ấy chạy dữ liệu giao dịch thông qua hai hàm băm riêng biệt. Mỗi hàm này kết thúc việc chọn hai giá trị từ chuỗi số bạn có thể thấy ở trên. Giả sử các giá trị này là 2 và 8.

3 4 2 1 6 8 7 5 0 9

Sau đó, Anna gửi bộ lọc cho John. Rõ ràng là không có khả năng biết dữ liệu nào Anna đã gửi đến bộ lọc nếu chỉ dựa trên lưới này.

Mặc dù nếu John có toàn bộ tập hợp chứa dữ liệu của Anna, anh ấy có thể băm nó và tìm kiếm các điểm tương đồng trong bộ lọc. Nếu có sự trùng khớp, có thể đó là dữ liệu mà Anna yêu cầu.

Tuy nhiên, một số đầu vào có thể tham chiếu đến 2 và 8 cùng một lúc. Do đó, John sẽ không thể biết phần dữ liệu nào mà Anna thực sự quan tâm. Vì vậy, anh ta sẽ trả lại tất cả các kết quả phù hợp, sau đó Anna sẽ sắp xếp lại.

Rõ ràng, quá trình này phức tạp hơn thế nhiều. Tuy nhiên, nó minh họa thực tế là bộ lọc Bloom che giấu lợi ích thực tế của khách hàng.

Bloom Filter là gì? Filter Bloom có thể không phải là phương pháp tốt nhất để lấy thông tin mong muốn vì nó cũng có một số lo ngại về quyền riêng tư. Tuy nhiên, đó vẫn là một lựa chọn tốt hơn là chỉ đặt một yêu cầu không được che giấu cho một nút.