비트코인의 Bloom Filters

Bloom Filters는 SPV 노드들이 transactions의 집합을 받을 때 그들이 어느 주소에 관심이 있는지 노출되지 않게 하는 기법입니다.
위 말이 조금 이해가 안될 수 있으므로 예를 들어서 설명해보겠습니다. 

만약 어떤 사람이 서울의 모든 지리를 안다고 가정해봅시다. 이 사람은 누구의 도움없이도 서울안에서 자기가 가고싶은 장소를 알아서 잘 
찾아갈 것입니다. 이 사람은 Full node에 해당합니다. 그러나 많은 사람들은 서울지리를 다 알지 못하기 때문에 누군가에게 물어보면서 자기가 가고싶은 곳을 가야합니다. 이는 SPV node에 해당합니다.

여기서 약간의 문제가 발생합니다. 예를 들어 롯데월드를 가고싶어서 어떤 사람에게 롯데월드를 어떻게 가는지 물어보면 그 사람의 목적지가 롯데월드라는 것을 노출하게 되는셈입니다. 그럼 어떻게 자신의 목적지를 노출하지 않을 수 있을까요?

이런식으로 생각해볼 수 있습니다. 서울에서 "드"로 끝나는 장소를 어떻게 가나요? 라고 물어본다면 롯데월드말고도 다른 장소로 가는 방법도 많이 알게 되겠지만 자신이 롯데월드를 간다는 사실을 어느정도 숨길 수 있습니다. Bloom Filters는 이런 원리에 기반합니다. 

 

Bloom Filters는 특정 패턴을 찾는 search filter로 N개의 비트와 M개의 해쉬함수로 이루어져 있습니다.
3개의 해시함수와 10개의 비트로 이루어졌다고 가정해보겠습니다.

초기에는 10개의 비트가 모두 0으로 세팅이 됩니다.
0 0 0 0 0 0 0 0 0 0

Bloom Filters의 해쉬함수는 input값을 1과 N사이의 값으로 바꾸어줍니다. 즉 여기서는 어떤 값을 넣으면 1~10사이의 값으로 바뀌게 됩니다. 이제 3개의 해쉬함수를 f1, f2, f3라고 가정하고 A라는 패턴을 추가한다고 가정해보겠습니다.

f1(A) = 1
f2(A) = 3
f3(A) = 8
위와 같이 결과값이 나왔다고 가정하면 
0 0 0 0 0 0 0 0 0 0 
-> 1 0 1 0 0 0 0 1 0 0 
즉, 결과값에 해당하는 비트를 1로 바꾸어줍니다.

여기에 B라는 패턴을 더 추가해보겠습니다.

f1(B) = 1
f2(B) = 4
f3(B) = 7
위와 같이 결과값이 나왔다면
1 0 1 0 0 0 0 1 0 0 
-> 1 0 1 1 0 0 1 1 0 0
즉, 이미 1로 세팅되어있는 값은 그대로 1로 내버려둡니다.

이렇게 A, B패턴을 추가한 Bloom Filters가 완성되었습니다.

그럼 어떤 패턴이 Bloom Filters에 있는지 어떻게 확인할까요?
Y라는 패턴이 존재하는지 검증해보겠습니다.

f1(Y) = 1
f1(Y) = 2
f1(Y) = 10
위와 같이 나왔다면 
1 0 1 1 0 0 1 1 0 0 에서 결과값에 해당하는 1은 비트가 1로 되어있지만 2와 10은 비트가 0입니다.
Bloom Filters안에 패턴이 들어있기 위해서는 결과값에 해당하는 비트가 모두 1이어야 합니다.
그러므로 Y패턴은 이 Bloom Filters에 들어있지 않습니다.

 

그래서 이 Bloom Filters는 SPV 노드가 어떻게 사용할까요?

SPV 노드는 Bloom Filters를 이용해 peer들과 통신합니다. 그러면 Bloom Filters를 이용하였으니 SPV 노드가 관심있는 주소 또는 keys가 정확히 어떤건지는 노출되지 않습니다.

과정을 간략히 설명하자면 SPV 노드가 초기에는 Bloom Filters를 모두 0으로 설정합니다. 그리고나서 자기가 관심있는 주소, 키, 해쉬 등을 Bloom Filters에 추가하고 만들어진 Bloom Filters를 peer들에게 보내면 peer들은 Bloom Filters에 매칭되는 정보들만 SPV 노드에게 전달해줍니다.

참고로 Bloom Filters에서 패턴을 제거하는 것은 불가능하기 때문에 패턴을 추가하는 것이 아닌 수정이 필요한 경우는 다시 0으로 초기화 후에 패턴을 추가해야합니다.