[비트코인 구조] 블룸 필터(Bloom Filter)

미리 알아야 할 내용들

---

[비트코인 구조] SPV(Simplified Payment Verification)

---

블룸 필터(Bloom Filter)

 

 SPV와 머클 트리에 대해 다시 한번 알아보겠습니다. 다음과 같은 머클 트리가 존재하고 SPV 노드가 트랜잭션 3을 검증하고 싶다고 가정해 보겠습니다.

 

 

 이 경우 모든 트랜잭션의 해시값을 풀 노드에 요청할 필요가 없었습니다. 다음과 같이 해시01과 해시2만 요청한다면 트랜잭션 3을 검증할 수 있었습니다.

 

 

 따라서 SPV 노드는 트랜잭션 3을 검증하기 위해 해시01과 해시2 두 값을 풀 노드에게 요청해야 합니다. 문제는 풀 노드가 두 값을 이용하면 트랜잭션 3을 검증할 수 있다는 점을 알게 된다는 것입니다. 즉, SPV가 풀 노드에게 해시01과 해시2를 요청한다면, 풀 노드는 SPV 노드가 트랜잭션 3과 연관성이 있을 가능성이 높다는 것을 쉽게 파악할 수 있습니다. 이러한 보안 문제를 해결하기 위해 비트코인에 블룸 필터를 도입하기로 결정했습니다.

 

BIP0037, 블룸 필터

 블룸 필터는 여러 개의 해시 함수를 사용합니다. 예를 들어 다음과 같이 나머지 연산을 사용하는 간단한 3개의 해시 함수가 있다고 가정해 보겠습니다. 또한 이 해시 함수는 다른 해시 함수 처럼 역연산이 불가능하다고 가정해보겠습니다.

 

 

 그리고 x값에 해당하는 값은 다음과 같이 깊이 우선 탐색 순서를 사용하겠습니다.

 

 

 이제 블룸 필터를 만들어보겠습니다. 먼저 증명하고자 하는 트랜잭션을 확인합니다. 여기에서는 트랜잭션 3 이므로 이 값의 해시 값인 해시 3의 순서 7을 x값으로 사용하겠습니다.

 

 

 최종적으로 순서 7의 해시값 [1, 3, 1]을 얻을 수 있었습니다. 이제 이 값을 비트로 표현해 보겠습니다. 그 결과는 다음과 같습니다.

 

 

 해시값이 1 또는 3이기 때문에 해당 값을 1로, 나머지 값은 0으로 처리합니다. 그리고 이 결과 값(블룸 필터)을 풀 노드에 전달합니다.

 

 

 풀 노드는 전달 전달받은 해시 함수를 이용해 모든 트랜잭션의 해시값 순서의 해시를 구합니다. 그 결과는 다음과 같습니다.

 

 

 그리고 이 값을 블룸 필터에 통과시킵니다. 예를 들어 순서가 3인 트랜잭션 0의 경우 해시값이 1또는 3임을 알 수 있습니다. 그리고 이 값은 블룸 필터를 통과합니다.

 

 

 하지만 순서가 4인 트랜잭션 1의 경우 해시값이 0또는 4이므로 블룸 필터를 통과하지 못합니다.

 

 

 결론적으로 풀 노드는 순서가 3과 7인 트랜잭션 0 또는 트랜잭션 3 혹은 둘 다의 트랜잭션을 SPV가 검증하고자 한다는 점을 알 수 있습니다. 하지만 정확히 어떤 트랜잭션을 검증하고자 하는 것인지는 알 수 없습니다. 따라서 SPV 노드의 보안이 어느 정도 유지될 수 있음을 알 수 있습니다.

 

 풀 노드는 블룸 필터를 통과한 두 트랜잭션의 해시값과 해당 트랜잭션 검증을 위한 해시값을 반환합니다. 여기에서는 트랜잭션의 개수가 4개이므로 모든 트랜잭션의 해시값을 반환하게 됩니다. 하지만 보유 해시값과 요청 해시값의 차이 때문에 플래그 비트가 다른 값을 가집니다.

 

 

 최종적으로 풀 노드가 반환하는 값은 다음과 같습니다.

 

 해시값: 해시0, 1, 2, 3

 플래그비트: 1110101

 

 지금까지 SPV 노드가 풀 노드와 데이터를 주고받기 위해 사용하는 블룸 필터에 대해 알아봤습니다. 감사합니다.

 

이어지는 글들

---

[비트코인 구조] 작업증명(Proof-of-Work)과 난이도