Chapter 12. 블룸 필터
아래 글에서는 “밑바닥부터 시작하는 비트코인(Programming Bitcoin) -한빛미디어(2019)”의 Chapter 12. 블룸 필터에 대한 내용을 다룬다. 블
Reviewed by.
Programming Bitcoin Series
Chapter 1. 유한체
Chapter 2. 타원곡선
Chapter 3. 타원곡선 암호
Chapter 4. 직렬화
Chapter 5. 트랜잭션
Chapter 6. 스크립트
Chapter 7. 트랜잭션 검증과 생성
Chapter 8. p2sh 스크립트
Chapter 9. 블록
Chapter 10. 네트워킹
Chapter 11. 단순 지급 검증
Chapter 12. 블룸 필터
Chapter 13. 세그윗
라이트 노드가 풀 노드로부터 관심 트랜잭션에 대한 포함 증명을 받는다. 이 때, 라이트 노드는 관심 노드의 상위 집합을 풀 노드에게 알려주는데, 이 상위 집합을 알려주기 위해 블룸 필터를 사용한다.
블룸 필터
블룸 필터는 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다. 다음과 같은 특성을 가진다.
- 빠르고 메모리 효율적이다.
- 집합에 속한 원소를 속하지 않았다고 말하는 일(False Nagative)은 없다. 속하지 않은 원소를 속했다고 말하는 일(False Positive)는 있다.
- 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내에 원소의 숫자가 증가할 수록 False Positive의 확률도 증가한다.
집합의 크기가 굉장히 크거나 집합의 속해 있는 원소의 크기가 커서 원소가 집합에 속해 있는지 정확히 판단하는데 시간이 오래 걸리는 경우 이 과정의 전처리 과정으로 블룸 필터를 이용해서 아예 집합에 속할 일이 없는 원소를 미리 걸러 낼 수 있다.
블록체인의 블룸 필터
라이트 노드는 관심 트랜잭션의 정보로 블룸 필터를 만들어서 풀 노드에 등록하고, 풀 노드는 블룸 필터를 통과한 트랜잭션의 정보를 라이트 노드에게 제공한다. 이 과정에서 라이트 노드는 관심 트랜잭션의 정보 대신, 이를 포함한 상위 집합의 정보로 블룸 필터를 만들면 풀 노드에게 관심 트랜잭션 정보를 공개하지 않을 수 있다.
블룸 필터 생성
블룸 필터는 다음과 같은 2개의 구성 요소를 이용해서 만든다.
- 관심 트랜잭션이 포함된 집합. 각 집합의 요소는 스트링이다.
- n개의 해쉬함수. 해쉬함수의 결과는 1~m 사이의 값을 가진다.
- 길이 m의 비트필드
n=3, m=16 일 때, K1, K2, K3을 해쉬함수라고 하고 A를 관심 집합의 엘리먼트라고 가정하면, 다음과 같이 블룸 필터를 만들 수 있다.
- 비트필드의 모든 값을 0으로 설정한다.
- A를 K1에 통과한 결과 3으로 비트필드의 3번 필드를 1로 설정한다.
- A를 K2에 통과한 결과 1로 비트필드의 1번 필드를 1로 설정한다.
- A를 K3에 통과한 결과 14로 비트필드의 14번 필드를 1로 설정한다.
결과적으로 1, 3, 14번 필드가 1인 길이 16의 비트필드가 만들어지게 되고, 이것이 엘리먼트 A의 블룸 필터이다.
같은 집합에 속한 엘리먼트 B를 다음과 같이 블룸 필터에 추가할 수 있다.
- B를 K1에 통과한 결과 16으로 비트필드의 16번 필드를 1로 설정한다.
- B를 K2에 통과한 결과 1로 비트필드의 1번 필드를 1로 설정한다.
- B를 K3에 통과한 결과 7로 비트필드의 7번 필드를 1로 설정한다.
결과적으로 1, 3, 7, 14, 16번 필드가 1인 길이 16의 비트필드가 만들어지게 되고, 이것이 엘리먼트 A, B의 블룸 필터이다.
집합에 속한 모든 엘리먼트로 위의 과정을 반복하면 집합의 블룸 필터를 만들 수 있다.
블룸 필터 검증
이제 만들어진 블룸 필터를 이용해서 X가 집합에 속하는지 검증해 보겠다.
- X를 K1에 통과한 결과 16이 블룸 필터에 1로 설정되어 있는지 확인한다.
- X를 K2에 통과한 결과 1이 블룸 필터에 1로 설정되어 있는지 확인한다.
- X를 K3에 통과한 결과 7이 블룸 필터에 1로 설정되어 있는지 확인한다.
1, 2, 3을 모두 통과했기 때문에, X는 집합에 속한 것이다.
- Y를 K1에 통과한 결과 16이 블룸 필터에 1로 설정되어 있는지 확인한다.
- Y를 K2에 통과한 결과 2가 블룸 필터에 1로 설정되어 있는지 확인한다.
- Y를 K3에 통과한 결과 7이 블룸 필터에 1로 설정되어 있는지 확인한다.
1, 3은 통과했지만, 2를 통과하지 못했기 때문에, Y는 집합에 속하지 않은 것이다.
BIP0037 블룸 필터
Bitcoin 에서 블룸 필터를 설정하기 위한 규약이 BIP0037이 제안되었다. 블룸 필터를 정의하는 정보는 다음과 같다.
- 비트 필드의 길이
- 해시 함수의 개수
- tweak (일반적인 해시 함수의 salt와 같은 기능)
- 비트 필드의 값
해시 함수는 성능이 빠를수록 좋고, 암호학적인 안전성이 높을 필요는 없다. 이런 특성에 따라 murmur3가 사용된다. murmur3에는 해시 대상과 seed가 입력값으로 전달되는데, tweak는 다음과 같이 seed의 랜덤성을 높이기 위해 사용된다.
seed = i * 0xfba4c795 + tweak블룸 필터 설정
라이트 노드가 다음과 같은 2 가지 설정을 하면 풀 노드로부터 관심 트랜잭션 정보만 받을 수 있습니다.
- version의 optional flag for relay를 0으로 설정
- filterload 커맨드를 실행해서 풀 노드로 블룸 필터 정보를 전송
이 때, 관심 트랙잭션의 정보로는 다음과 같은 값을 사용할 수 있다.
- Transaction ID
- Transaction 출력의 locking script의 컴포넌트. 특히 OP_RETURN의 값도 사용할 수 있다.
- Transaction 입력
- Transaction 입력의 signature
블룸 필터의 사용
머클블록의 입수
getdata 커맨드를 이용하면 라이트 노드가 풀 노드에게 관심 트랜잭션이 포함된 머클 블록을 요청할 수 있다. getdata는 풀 노드가 라이트 노드에게 블록이나 트랜잭션을 전송하게 하는 커맨드인데, 요청하는 데이터 유형을 filtered block으로 설정하면 블룸 필터를 통과한 트랜잭션을 머클블록의 형태로 요청할 수 있다.
