Bloom filter — 그런데 Eth, Bit를 곁들인
오랜만에 Bloom Filter에 꽂히게 되어 Bloom Filter가 도대체 뭔지
어떻게 동작하는지 적어보고 싶어져서 글을 작성합니다.
Source : My Little Poor knowledge
Bloom Filter는 확률형 자료 구조라고도 불립니다.
다들 아시다시피
빠르고 ( 원소가 없는 경우를 확인하는 데는 O(1)의 시간 복잡도를 가짐 ),
메모리 효율적이라는 장점이 있습니다.
다만 “확률형”이라는 말에 초점을 잡아볼 필요가 있습니다.
보통은 정확하게 답변을 내놓는데에 집중하는 반면
Bloom Filter는 다소 애매한 답변을 내놓습니다.
바로 False Postive입니다.
Bloom Filter가 뱉어내는 결과에는 두가지가 있습니다.
- 속해있을 수도 있다. ( False Postive )
- 속해 있지 않다.
Bloom Filter의 결과로 다들 이런걸 할 수 있다 합니다.
“집합의 크기가 매우 크거나 원소의 크기가 커서 원소가 집합에 속해 있는지 판단하는 데 시간이 오래 걸리는 경우 Bloom Filter를 전처리 과정으로 이용하면 아예 집합에 속하지 않을 원소를 미리 걸러낼 수 있습니다.
이로써 원소의 소속 여부를 효율적으로 판별할 수 있게 됩니다.”
여기까지 왔으면 Bloom Filter가 어떻게 동작하는지 알고 가야할것 같은데요
Bloom Filter는 m 비트 크기의 비트배열 구조와,
서로 다른 K가지의 Hash 함수를 사용하여 구현됩니다.
(표지의 네모박스가 비트배열, 파랑 빨강 박스가 Hash 함수를 나타냅니다.)
여기서 각 Hash 함수는 m 가지의 값을 균등한 확률로 출력해야만 합니다.
제가 본 예시중 가장 이해하기 쉬웠던 예시를 가져와 봤습니다.
비트 배열 크기가 10 비트이고,
하나의 Hash 함수를 가진 Bloom Filter가 있습니다.
이 Hash 함수는 숫자를 10으로 나눈 후 그 나머지 값을 반환하는 함수입니다.
이 필터의 기준이 되는 집합에는 원소가 34 하나뿐입니다.
34를 10으로 나누면 나머지는 4이므로, 네 번째 비트를 1로 변경합니다.
이제 이 기준 집합을 대상 집합과 비교해 봅시다.
대상 집합의 첫 번째 원소는 56입니다.
56에 Hash 함수를 적용하면, 나머지 값인 6을 얻습니다.
여섯 번째 비트를 확인해보면 값은 0입니다.
이 결과로부터, 56이 기준 집합인 34와 일치할 확률은 없다는 것을 알 수 있습니다. 따라서, 이 값은 조인할 필요가 없는 대상이 됩니다.
대상 집합의 두 번째 값은 54입니다. 54에 Hash 함수를 적용하면, 4라는 결과 값을 얻습니다. 네 번째 비트를 확인해보니 값이 1입니다.
이는 34와 54의 Hash 함수 결과가 동일하므로, Bloom Filter 입장에서는 둘 다 참으로 판단됩니다.
하지만, 실제 값인 54는 기준 값인 34와 다르기 때문에,
이 경우는 ‘False Positive’라고 합니다.
이는 Bloom Filter에서 허용되는 오류지만, 이런 경우가 많아질수록 Bloom Filter의 성능은 저하됩니다.
Bloom Filter의 성능을 높이려면 False Postive를 최대한 줄여야 합니다.
이를 위한 방법으로는 비트 배열의 크기를 늘리거나 Hash 함수의 개수를 늘리는 것이 있습니다.
하지만, 비트 배열 크기를 늘리면 메모리 사용량이 증가하고, Hash 함수를 늘리면 CPU 사용량이 증가합니다.
따라서, Bloom Filter의 성능 향상을 위해서는 비트 배열 크기와 Hash 함수의 개수를 적절하게 조절하는 것이 중요합니다.
이러한 예시를 보다보니 실제로는 어떻게 사용될까 궁금하신 분들도 많을것 같아
제 가까운 친구들을 데려와 봤습니다.
제 주변, 그나마 가까운 친구인 이더는 지금까지 정의한 역할과 비슷하게 사용하는것 같습니다.
이더리움에서 Bloom Filter는 로그와 이벤트를 조회하는데 사용됩니다.
이더리움 블록 헤더에는 ‘logsBloom’이라는 필드가 있고,
이 필드는 각 블록에 대한 로그들의 Bloom Filter를 저장합니다.
이더리움에서 Bloom Filter는 주로 두 가지 목적으로 사용됩니다:
로그 및 이벤트 조회: 스마트 컨트랙트에서 발생하는 이벤트는 블록체인에 로그로 저장됩니다. 이 로그들은 Bloom Filter를 통해 검색할 수 있습니다. 특정 이벤트를 찾기 위해 전체 블록체인을 검색할 필요 없이 Bloom Filter를 사용해서 해당 이벤트가 있는 블록을 빠르게 찾을 수 있습니다.
가스 최적화: Bloom Filter를 사용하면 특정 이벤트를 찾기 위한 계산량을 줄일 수 있습니다. 이는 이더리움 네트워크에서 가스를 절약하는데 도움이 됩니다.
그러나 다른 친구 비트는 특이하게도 익명을 보장하기 위해 사용됩니다.
비트코인에서 Bloom Filter는 False Postive이라는 특성을 이용해 사용자가 원하는 프라이버시 수준과 데이터 전송량(대역폭) 사이의 균형을 맞출 수 있게 해줍니다. 이는 사용자가 자신만의 Bloom Filter를 만들어 원하는 데이터를 선택적으로 필터링할 수 있게 해줍니다.
예로 들어, 간소화된 결제 검증(SPV) 클라이언트는 자신의 Bloom Filter를 만들어 필요한 트랜잭션을 선택하고, 이 Bloom Filter를 ‘필터로드’라는 메시지를 통해 전체 노드에 전송할 수 있습니다. 그리고 ‘필터 추가’라는 명령을 통해 새로운 Bloom Filter를 전송하지 않고도 필터에 원하는 데이터를 추가할 수 있습니다. 마지막으로 ‘필터 클리어’라는 명령을 통해 기존의 블록 찾기 방식으로 되돌릴 수 있습니다.
Bloom Filter가 로드되면, 전체 노드는 Bloom Filter와 관련된 머클 브랜치를 가진 블록 헤더인 ‘머클 블록’을 전송하게 됩니다.
SPV 클라이언트는 Bloom Filter에 트랜잭션뿐만 아니라 공개키, 서명 스크립트와 pubkey 스크립트의 데이터 등도 추가할 수 있습니다. 이렇게 되면 P2SH(Pay-to-Script-Hash) 트랜잭션 탐색이 가능해집니다.
또한, 사용자가 더 높은 프라이버시를 원하면 Bloom Filter에 더 많은 거짓 긍정을 포함시키는 방식으로 설정할 수 있습니다.
이렇게 하면 트랜잭션 탐색에 필요한 대역폭은 늘어나지만, 프라이버시 보호 수준이 높아집니다.
반대로, 사용자가 대역폭을 절약하고 싶다면 거짓 긍정률을 낮추는 방식으로 설정할 수 있습니다.
이 경우에는 노드가 사용자의 트랜잭션을 더 명확하게 볼 수 있게 되지만, 대역폭 사용량은 줄어들게 됩니다.
참조 : https://developer.bitcoin.org/devguide/operating_modes.html
여기까지 Bloom Filter — 그런데 Eth, Bit를 곁들인 이었습니다.
감사합니다.
Special Thanks to maczniak
참고한 자료: https://dataonair.or.kr/db-tech-reference/d-lounge/technical-data/?mod=document&uid=235922,
