🧐
Bloom Filter만 따로 설명할 수 있지만
비트코인에서 이 기술이 어디에서 사용되고
왜 사용되는지 아는 것이 더 중요하기 때문에 좀 길지만 Bloom Filter를 이해하기 위한 여정을 조금 길게 떠나보자.
🤝 UTXO
UTXO는 Unspent Transaction Outputs의 약자로서, 미사용 트랜잭션 출력값을 말한다.
비트코인은 이더리움의 '계좌 잔고 모델'(Account Balance Model)과 달리 계정이나 잔고가 없고, 블록체인에 기록된 "소비되지 않은 출력값"을 통해 거래의 유효성을 검사하여 코인의 존재 여부를 확인한다.
어떻게 작동하는가?
A,B,C라는 사람이 있다고 가정하고,A가 B에게 10,000원을 전송한다.
이때B는 원래 2,000원을 갖고 있었다고 가정한다. B는 A에게 추가로 만 원을 받게 되면서 B는 12,000원이 생겼지만,실제 데이터 내부의 모습은 2,000원의 객체와 10,000원의 UTXO의 객체가 존재하게 된다.일반적으로 이더리움은 계좌(Account) 방식을 이용하여 잔고를 합쳐 하나의 잔고가 나오게 되지만
비트코인은 굳이 잔고를 합치지 않는다. 현재 B가 소유한 코인들을 모두 모을 뿐이며, 이 때 UTXO 객체를 '금액을 적은 종이'라고 이해할 수 있다.이번에는
B가 C에게 돈을 보낸다. B는 2,000원의 객체와 10,000원의 객체가 있는데 C에게 11,000원을 보내고 1,000원은 B가 다시 소유하게 된다.즉,
B에게 있는 2개의 UTXO 객체를 합치고 나눠서 새로운 UTXO 객체를 만들어낸다. 따라서 비트코인에서 쓰이는 UTXO의 방식은 돈들이 살아 움직이면서 소유자의 금액을 파악하는 방식이고 이더리움의 잔고와 같은 방식은 송신자와 수신자의 잔고를 수정하는 방식을 채용하는 차이점이 있다.
👍 장점
- UTXO를 확인함으로써 이중지불이 방지된다
누군가 트랜잭션을 발생시키면 해당 UTXO는 검증을 받은 후 Transaction Pool(거래처리 대기열)에 들어간다.
그러므로 누간가 악의적으로 이중지불을 발생시키더라도 채굴자들은 UTXO 검사 후 Transacton Pool의 거래를 처리하기 때문에 UTXO의 이중 사용 기록이 있다면 해당 거래를 무효화 할 수 있다.
- 잔고의 증명이 간편하다
UTXO방식을 이용하면 거래에 대한 유효성을 검증하기가 매우 쉽다. 일반적으로 이더리움 같은 경우는 트랜잭션들을 모두 검증 및 확인하여 최종적으로 잔고를 유추하지만 UTXO는 해당 사용자의 UTXO만 확인하면 되기 때문에 그럴 필요가 없다.
이더리움처럼 어느 계좌에 귀속이 된 기록이 아니라 흩어져 있는 UTXO의 객체들로 특정 소유자의 계좌를 유추하는 것이다. 그래서 특정 계좌의 잔고를 알기가 힘들 수 있지만, 수많은 애플리케이션들이 이러한 기능들을 모두 제공하고 있어서(특정 사용자의 UTXO를 모아주는 기능)잔고를 확인하는 데 큰 불편함은 없다.
👎 단점
UTXO의 가장 큰 단점은 UTXO가 너무 과하게 생성이 될 경우이다. 이더리움은 결과적으로 잔고 하나만 점검하면 끝이지만, UTXO 방식을 채용하는 코인들은 흩어져 있는 UTXO를 모두 모아야 되며 소액 결제를 엄청 자주 하거나, 채굴로 이자를 받게 되면 과도한 UTXO로 인해서 불필요한 수수료를 내야 하는 단점이 생긴다.
✅ 채굴을 진행하는 풀노드는 어떻게 UTXO를 검증하는가?
우리가
풀노드(full node)라고 가정하고(풀노드가 무엇인지 밑에서 설명합니다) 블록생성을 위해채굴을 진행 중이며 Node들로부터 transaction을 처리하기 위해transaction pool을 열어놓았다고 생각해보자.누군가가 우리에게
Transaction 4를 우리에게 보냈고, 우리는 해당 거래가 거짓인지 아닌지 판단하기 위해서 보낸사람의UXTO를 검증한다.UXTO를 검증하기 위해
Transaction 4가 어디서부터 나에게 도착했는지 타고타고 올라가며 확인한다.그러다가 결국 나는
100번째 Block에 도착하게 되고Coinbase Transaction(p2p거래가 아닌 채굴을 통해 얻어낸 비트코인 거래)를 확인하게 된다.결국 100번째 블록에서 채굴된 비트코인이 거래되고 또 다시 거래되어 나에게 흘러들어온 것이다. 이 모든 과정을 확인했을 때 누군가가 BTC를 거짓으로 100개 만들어내 거래하는 등의 문제가 없다면 Transaction 4를 통해 전달받은 UTXO가 검증된 것이다.
👾 Light Node, Full Node and SPV Solution
SPV(Simple Payment Verification)란 거래에 대한 모든 블록체인을 저장하지 않고도 트랜잭션을 검증하는 방법이다.
라이트 웨이트 노드(lightweight node)또는경량노드라고도 불린다.
SPV는 비트코인을 받았다는 거래에 대해 모든 블록체인을 다운로드 하지 않고 검증하는 간이 결제 확인 방법이다.
이는 사토시 나카모토의 비트코인 백서에서도 소개되고 있는 부분이다.
블록체인 네트워크 중 일부분의 데이터를 들고 있는 라이트 노드(light node)를 상상해보자.
라이트 노드는 모든 블록 정보를 가지고 있지 않은 Node다.
때문에 새로운 거래 정보를 수신받았을 경우 이 거래가 정상적인지 검증할 수 없다.
반면 풀 노드(full node)는 모든 데이터를 가지고 있는 Node다.
때문에(비트코인의 경우 풀노드는 약 150GB의 데이터를 가지고 있다, 계속 늘어남) 로컬에 있는 블록 정보를 조회하여 전달받은 거래에 대한 유효성을 검증할 수 있다.
이때 라이트 노드에서 거래를 검증하기 위해 풀 노드에게 블록 정보를 요청하여 머클트리를 통해 이 거래가 검증된 거래인지를 확인하는 방법이 바로 SPV이다(블록헤더의 머클트리 root를 통해 검증하고 전체 블록체인 네트워크의 데이터를 저장할 필요 없음).
하지만 주변 라이트 노드는 풀 노드에게 블록헤더에 관한 정보를 요청할 때 프라이버시 문제가 발생한다.
SPV방식은 이러한 프라이버시 문제를 해결하기 위해 Bloom Filter를 사용한다.
🌸 What is Bloom Filter?
블룸필터는확률적 검색 필터다(어떤 물건이 확률적으로 존재하는지 안하는지에 대한 여부를 필터를 통해 알려준다고 생각하면 된다, 어떤 물건이 블룸필터를 통과하면 그 물건이 존재할 확률이 있음, 반드시 존재하는 것은 아님).이 동영상을 시청하면 블룸필터에 대한 명쾌한 이미지를 그릴 수 있을 것이다.
특정 요소를 어떻게 블룸필터에 작성하는지 알아보자.
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와 Y를 통과시켜서 X와 Y가 어떻게 블룸필터를 통해 여과되는지 알아보자.
X 패턴이 존재하는지 검증하기 위해 동일 해쉬함수를 통해 출력된 결과값은 16, 1, 7번 인덱스다.
블룸필터에 각 인덱스에 해당하는 배열이 다음과 같이 1로 설정되어 있기 때문에 X 패턴은 실제 존재할 가능성이 있다. 존재할 가능성이 있다는것이지 반드시 존재한다는것은 아님을 유의한다. (Maybe Yes)
Y패턴이 존재하는지 검증하기 위해 다시 동일 해쉬함수를 출력한결과 다음과 같이 16, 2, 7의 결과값을 얻었고, 블룸필터에서는 해당 인덱스의 값은 2번 인덱스가 0으로 일치하지 않는다.
이와같은 경우 Y 패턴은 절대 존재하지 않는다고 확신할수 있다.
💡
즉, 블룸필터를 통해 존재가 확인되는 경우는 확률적으로 존재가능성만을 확인가능하지만, 블룸필터를 통해 존재하지 않는다는것은 절대적으로 존재하지 않음을 확신할수 있다.
Conclusion
이와같이 SPV Node는 자신이 원하는 거래와 지갑주소를 사용하여 블룸필터를 생성하고, 해당 블룸필터를 인근 풀노드에 전달하여 필요한 거래정보를 요청하게 된다.
풀노드에서는 해당 블룸필터를 통해서 존재할 가능성이 있는 거래정보를 선별하고 SPV 노드에게 전달하게 된다. 이러한 방식으로 SPV 노드는 자신의 주소와 거래정보를 노출시키지 않고(풀노드에게 본인이 무엇을 원하는지 정확하게 말하지 않음), 필요한 정보를 요청하여 거래를 할수 있게 된다.
UTXO
Reference
Coinbase Transaction
Reference
SPV Node
Reference
