밑바닥부터 시작하는 비트코인

12

장

블룸 필터

305

12.1.1

다중 해시함수 사용

전체 집합의 원소 개수가

1

백만 개라고 합시다. 한 그룹의 원소 개수가 여전히

5

개인 블룸 필

터를 만들고자 한다면 비트 필드의 길이는

1

,

000

,

000

/

5

=

200

,

000

비트여야 합니다. 각 그

룹은 평균

5

개의 원소로 이루어지고 관심 원소가

1

개라면 그룹에서 관심 원소의 비율은

20%

가 됩니다.

200

,

000

비트는

25

,

000

바이트이고 블룸 필터 설정값으로 전송하기에는 많은 데이

터양입니다. 더 좋은 방안이 없을까요?

해시함수를 여러 개 사용해서 블룸 필터를 구성하면 비트 필드의 길이를 상당히 줄일 수 있습

니다.

32

비트의 비트 필드에서

5

개의 해시함수를 사용하면

32

!/ (

27

!

5

!)~

200

,

000

개의 그룹

을 만들 수 있습니다.

3

1

백만 개의 원소 중에서 평균

5

개의 원소가 동일한

5

비트 조합을 갖게

됩니다. 이런 식으로

25K

바이트를 전송하는 대신

4

바이트 (

32

비트 )만 전송할 수 있습니다.

이를 구현하는 코드는 다음과 같습니다. 간단히 하기 위해 이전 예와 동일한

10

비트 필드를 사

용하지만 관심 원소는 두 가지로 가정했습니다.

>>> from helper import hash256, hash160

>>> bit_field_size = 10

>>> bit_field = [0] * bit_field_size ...