[BitCoin] 블룸 필터

안녕하세요. 

 

전에 블룸필터에 대해서 게시글을 작성하였으나 그냥 대충 이렇구나 라고 이해하고 글을 써었습니다.

그러기에 좀 더 정확히 왜 쓰이고, 어디다 쓰게 되는지에 대해서 추가적으로 작성하고자 합니다.

 

우선 비트코인에서 블룸필터는 주로 SPV노드에서 사용이 되는데요.

SPV의 노드의 경우 블록헤더만 가지고 있는 노드입니다.

 

어떻게 보면 풀 노드에 붙어서 최소한의 데이터만을 가지고 있는 노드라고 생각하면 될 것 같습니다.

 

이러한 SPV노드는 우선 저장공간의 관점에서 볼때 적은 데이터를 가지고 있을려고 블록헤더만을 가지고 있는 노드인데

즉, 저장공간에 적은 휴대폰와 같은 장치에서 주로 쓰이고 있습니다.

 

그런데 이러한 SPV노드에서 왜 블룸 필터가 사용될까요?

 

블룸 필터의 역할은 우선 필터이기 때문에 필터링을 하는 역할을 합니다.

즉 트랜잭션이 발생하여 자기한테 왔을 때 자기와 상관없는 트랜잭션일 경우 필터링을 해버리는 거죠.

 

그렇게 통신 측면에서 과부하를 줄일 수 있게 될 것입니다.

 

또한 익명성을 보장하는데요. 100프로 보장하는 것은 아닙니다.

필터의 요소가 적으면 적을 수록 유추해내기 쉬우면 많으면 많을 수록 필터링이 제대로 되지 않기 때문에 어느정도

타협점이 필요합니다.

 

현실에서의 예로 맨날 가던길로 갔기 때문에 대충 여기 동네에 살겠구나 정도의 유추가 가능하다는 것입니다.

 

 

위 내용을 좀더 예를 들어 자세히 설명하자면 

A가 B에게 50을 보내는 트랜잭션이 생성되었습니다.

 

블룸필터를 통해 A와 B는 자신에게 해당되는 거래이기 때문에 트랜잭션을 받지만 C나 D같은 경우는 자신과 상관 없는 트랜잭션이기 때문에 블룸필터를 통해 필터링이 된다는 것입니다.

 

여기서 말한 A, B, C, D는 거래주소(Address)입니다.

 

여튼 블룸 필터의 용도는 자신에게 해당하는 트랜잭션인지 필터링을 하고 또한 확률적 필터이기에 자신의 주소가 공개가 되지 않음에 사용한다고 생각이 듭니다. (어디까지나 저의 주관적인 생각입니다.)

 

조금 블룸 필터에 대해서 자세히 알아보겠습니다.

 

SPV노드는 '비어 있는' 상태로 블룸필터를 초기화하고, 이 초기화 상태에서 블룸 필터는 어떠한 패턴과도 일치하지 않으며, 그 후 SPV노드가 자신의 지갑 내에 있는 주소 전부에 대한 목록을 만들고 각 주소에 때응하는 거래 출력값과 일치하는 검색 패턴을 생성하게 됩니다.

 

블룸필터는 2진수 N의 가변적 크기 배열과 M개의 해시 함수로 이루어진 가변수로 구현되어 있습니다.

M개의 해쉬함수는 1에서 N 사이의 출력값을 가지고, 해당 출력값에 해당하는 인덱스의 비트배열을 1로 설정합니다.

이렇게 M개의 해쉬함수에 대한 출력결과로 N비트배열은 M개가 1로 설정되게 되며, 이것이 블룸필터가 됩니다.

 

A패턴이 포함된 필터를 생성하는 과정은 다음과 같습니다.

A 패턴을 3개의 해쉬함수를 통하게 할경우 K1 해쉬함수의 출력값은 인덱스 3이고, 해당 3번 인덱스에 해당하는 배열의 비트를 1로 설정합니다.

K2 해쉬함수의 출력값은 1이고, 해당 인덱스의 배열을 다시 1로 설정합니다.

K3 해쉬함수의 출력값은 14이고, 해당 인덱스의 배열을 1로 설정합니다.

이렇게 최종적으로 1,3,14번 인덱스의 배열이 1로 설정된 배열이 만들어지게 됩니다.

이번에는 B패턴을 추가하도록 하겠습니다.

B패턴의 결과로 1,7,16번 인덱스의 배열이 1로 설정되게 되어, 최종적으로 패턴 A,B 가 포함된 블룸필터가 만들어지게 됩니다.

그럼 이렇게 만들어진 블룸필터를 사용하여 어떤 패턴이 실제 존재하는지 검증하는 방법을 보도록 하겠습니다.

X 패턴이 존재하는지 검증하기 위해 동일 해쉬함수를 통해 출력된 결과값은 16, 1, 7번 인덱스입니다.

블룸필터에 각 인덱스에 해당하는 배열이 다음과 같이 1로 설정되어 있기 때문에 X 패턴은 실제 존재할 가능성이 있습니다. 존재할 가능성이 있다는것이지 반드시 존재한다는것은 아님을 유의하시기 바랍니다. (Maybe Yes)

 

 

Y패턴이 존재하는지 검증하기 위해 다시 동일 해쉬함수를 출력한결과 다음과 같이 16, 2, 7의 결과값을 얻었고, 블룸필터에서는 해당 인덱스의 값은 2번 인덱스가 0으로 일치하지 않습니다.

이와같은 경우 Y 패턴은 절대 존재하지 않는다고 확신할수 있습니다.

즉, 블룸필터를 통해 존재가 확인되는 경우는 확률적으로 존재가능성만을 확인가능하지만, 블룸필터를 통해 존재하지 않는다는것은 절대적으로 존재하지 않음을 확신할수 있는것 입니다.

 

 

이와같이 SPV 노드는 자신이 원하는 거래와 지갑주소를 사용하여 블룸필터를 생성하고, 해당 블룸필터를 인근 풀노드에 전달하여 필요한 거래정보를 요청하게 됩니다.

SPV 노드와 인근의 풀노드는 모두 동일한 해쉬함수를 가지고 있기때문에, 풀노드에서는 해당 블룸필터를 통해서 존재할 가능성이 있는 거래정보를 선별하게 SPV 노드에게 전달하게 됩니다. 이러한 방식은로 SPV 노드는 자신의 주소와 거래정보를 노출시키지 않고, 필요한 정보를 요청하여 거래를 할수 있게 됩니다.