Bloom filtresi, kullanıcıya belirli bir öğenin, bir setin parçası olup olmadığını bildiren bir veri yapısıdır. Her ne kadar bir öğenin setin içinde olduğunu kesin olarak söyleyemese de bu öğe eğer setin içinde bulunmuyorsa bunu kesin olarak bildirebilmektedir.
Bloom Filtresi, Burton Howard Bloom tarafından 1970 yılında bulunmuş olan olasılık temelli bir veri yapısıdır. Bu veri yapısı ile bir elemanın bir küme içinde yer alıp almadığı düşük maliyetle sorgulanabilmektedir. Burton Howard Bloom tarafından 1970 yılında yaratılan Bloom filtresi, depolama alanı kullanımındaki verimliliği sayesinde çoğu uygulamada kullanılmaktadır. Bazı kripto para birimlerinin (özellikle Bitcoin), Basitleştirilmiş Ödeme Doğrulaması veya SPV ( Simplified Payment Verification ) uygulamalarında Bloom filtreleri olmazsa olmazdır. Bir SPV yazılımı kullanırken, kullanıcılar full node (tam düğüm) çalıştırmadan Bitcoin ağı ile etkileşime girebilirler.
Full nodelar, akıllı telefonlar gibi düşük güçlü cihazlarda çalıştırılmalarını zorlaştıran belirli depolama ve hesaplama gereksinimleri ile birlikte gelmektedir. Öte yandan SPV yazılımları, kullanıcının cüzdanları ile ilgili bilgiler için full nodelara soru sormaktadır. Bu verileri kullanıcıya iletmenin en basit çözümü, full nodeları müşterinin anahtarlarından haberdar ederek onlara yalnızca takas ile ilgili işlemlerin gönderilmesini sağlamaktan geçmektedir. Ancak bu durumda, müşterinin mahremiyetinden ödün verileceği için bu yöntem oldukça kötü bir çözümdür. Öte yandan, tüm takas işlemleri daha sonra çoğunu silmek üzere indirilirse bu durumda da fazla veri kullanımına yol açılmaktadır ve verimsiz bir işlem olmaktadır. Bloom filtrelerinin kullanılmasının sebebi budur.
Bloom filtresi veri yapısına olasılıksal adı veri verilmesinin nedeni verdiği yanıtlar arasında false positive sonuçların olabilmesinden kaynaklanmaktadır. Bloom filtresi "Evet, eleman bu kümede bulunuyor." yanıtını verirse eleman bu kümede olma olasılığını yüzde elli oranında taşır. Ancak bunun tam tersi, yani false negative yanıtlar bloom filtresi için geçerli olmamaktadır. Diğer bir deyişle eğer bloom filtresi "Hayır, eleman bu kümede bulunmuyor." derse mutlaka doğru cevabı vermektedir. Doğru veri yapılandırması ile false positive oranı %1'in altında tutulabilmektedir. Böylece bloom filtresi özellikle veritabanı analizinden önce kullanıldığında gereksiz disk erişiminin önüne geçebilmektedir. Yani bloom filtreleri, diğer dizeler için yapılandırılabilir bir yanlış pozitif eşleşme oranıyla belirli, bir dizeyle eşleşmesi garanti edilen kompakt bir filtre oluşturma yeteneği sağlamaktadır.
Örnek olarak, ehemmiyeti olmayan bir istemci, tüm cüzdan adresleri için bir bloom filtresi oluşturabilir, bu filtreyi BIP37'de tanımlanan P2P protokol mesajlarını kullanarak bir düğüme gönderebilir ve ardından düğümden özel bir blok formu (merkle blokları) talep edebilir. BIP37 popüler olduğunda, onu kullanan çoğu ehemmiyetsiz istemci, sınırlı bant genişliğine sahip mobil cihazlarda çalışması sebebiyle bant genişliği kullanımlarını en aza indirmek için düşük yanlış pozitif oranları seçmiştir. Bu seçim, iletişim kurdukları herhangi bir düğüm baz alındığında, o düğüme adres listelerinin verildiği anlamına gelmekteydi. Gizlilik odaklı kullanıcıların daha yüksek bir yanlış pozitif oran ayarlayarak bu gizlilik kaybını hafifletmeleri beklenirken, araştırmalar makul bir inkar edilebilirlik sağlamak için oranın oldukça yüksek olması gerektiğini göstermektedir.
Ek bir sorun olarak, BIP37 filtrelerine hizmet eden düğümler, her istemci için bağımsız olarak filtreleme yapmalıdır ayrıca filtrelerin, düğümlerin her bloğu filtrelemek için yoğun miktarda CPU işleme yapmasını gerektirecek şekilde oluşturulması mümkün olmaktadır. Bu durum, düğümlere karşı bir dizi bilinen DoS vektörü olarak sonuçlanmıştır. Pratikte BIP37, istemcilerin oldukça az miktarda bant genişliği kullanmasına izin verse de, daha yavaştır ve büyük işlem veritabanlarına dayalı diğer uzaktan işlem tarama yöntemlerinden daha fazla bant genişliği kullanmıştır. Günümüzde birçok popüler ama ehemmiyetsiz olan istemci, işlem bloom filtreleri kullanmak yerine bu tür veritabanlarını sorgulamaktadır.
Bloom Filter Örneği
Görseller aracılığı ile oluşturulmuş bu örnekte bloom filtrelerinin nasıl çalıştığı aşağıdaki örnekle anlaşılabilir. Ali adındaki bir müşterinin, full node çalıştıran Ayşe’nin farkında olmasını istemediği yüksek değerli bir işlemi olduğu varsayılsın. Bu durumda 10x1'lik bir şerit olarak gösterilecek bir Bloom filtresi oluşturulacaktır:
Ali istediği verileri 2 farklı hash fonksiyonundan geçirerek, bunun sonucunda ise 0 ve 9 arasında iki rakam elde etmektedir. Bu rakamların 4 ve 7 olduğunu varsayıldıktan sonra Ali bu filtreyi Ayşe’ye göndermektedir.
Yukarıdaki şeride bakıldığında, Ali’nin filtreye hangi verileri aktardığı ile ilgili hiçbir şey öğrenilmemektedir. Ancak elde bir veri seti olsaydı bu verileri aynı filtreden geçirip kıyaslama yapılabilirdi. Eğer doğru set bulunursa filtrenin sonuçları eşleşecektir bu sayede Ali’nin sahip olduğu bilgiye elde veri setini tutan da ulaşabilmektedir. Öte yandan 4 ve 7 sonucuna ulaşacak bir çok farklı girdi olabilmektedir. O nedenle Ayşe, Ali’nin hangi verilerle ilgilendiğini bilememektedir. Yani Ayşe sadece Ali’nin hangi veri filtrelerini kullandığını bilebilmektedir. Ve aynı işlemi tekrar eder.
Tabii ki de bu örnek aşırı basitleştirilmiş bir örnektir. Ancak konsepti anlamak açısından yeterlidir. Bir başka deyişle, Bloom filtreleri müşterilerin niyetini gizlemelesine yardımcı olmaktadır. Her ne kadar mükemmel bir güvenlik tedbiri olmasa da (gizlilik konusu hala tartışılıyor), Bloom filtreleri olumlu bir girişim olarak kabul edilmektedir.