SPV 노드의 거래를 검증하기 위한 블룸필터

풀노드의 경우, 전체 거래정보를 기반으로 UTXO를 검증하여 거래에 유효한지를 판단할수가 있습니다.

즉, 다음과 같이 거래를 위한 UTXO를 유효성을 검증합니다.

거래에 사용하기위한 Transcation 4의 출력, 즉 UTXO를 검증하기위해, 해당거래의 체인을 검색하여 해당 코인이 최초 채굴된 100번 블록까지 거슬러 올라가며 각  블럭의 유효성을 체크합니다.

Coinbase 거래란 채굴을 통해 새로운 코인이 발생하는 것으로 하기의 예는 채굴을 통해 발생한 새로운 코인이, Transaction #1에서 #4까지 사용된것으로 최종 #4번 거래를 통한 출력값이 현재 미사용 출력값인 UTXO 입니다.

즉, Trsaction 4의 UTXO를 거래에 사용하기위해 이전블럭의 유효성을 검증하여 모두 유효한것으로 판단되면 해당 UTXO는 유효한것으로 판단되어 거래에 사용할수가 있는것입니다.

SPV 노드는 전체 블록을 다운로드하지않고, 블록헤더만 다운로드 하기 때문에 전체블록 대비 1000분의 1정도의 작은 용량만 차지합니다.

제한적인 성능의 디바이스나 스마트폰과 같은 환경에서 거래를 하기위한 용도로 사용이 됩니다.

하지만 거래정보가 없이 블록헤더만을 가지고 있기 때문에, 거래를 위해 블록체인상의 블록의 높이 대신 깊이를 잠조해서 거래를 검증합니다.

블록의 헤더에는 거래의 해쉬정보가 포함된 머클트리 루트가 포함되어 있습니다.

다음그림은 사토시 나카모토의 비트코인 논문에 포함된 머클루트입니다.

다음 그림과 같이 각 블록에 포함된 머클루트의 정보를 통해서 특정 거래의 존재여부를 확인할수 있으며, 거래존재가 확인된 블럭이후로 6개의 블록이 쌓인경우, 해당거래는 유효하다고 판단되어 거래에 사용할수 있습니다.

이와같이 SPV 노드는 인근의 풀노드에게 헤더와 거래정보를 요청하여 거래의 유효성을 검증하여 거래를 진행할수 있습니다.  하지만 이렇게 헤더와 거래정보를 요청하는 과정에서 자신의 정보가 노출될수 있습니다.

즉, 자신의 지갑주소가 포함된 거래를 요청하는경우, 해당지갑주소로의 모든 거래정보가 인근노드에 전파되어, 특정주소의 거래가 노출되어 익명성이 위배될수 있습니다.

따라서 SPV 노드는 익명성을 유지하기 위해서 블룸필터를 추가하여 거래에 사용합니다.

블룸필터는 다음과 같이 N개의 해쉬함수와 M개의 1비트 배열로 구성이 됩니다.

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

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

[참조 : Mastering Bitcoin]

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

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

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

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

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

[참조 : Mastering Bitcoin]

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

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

[참조 : Mastering Bitcoin]

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

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

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

[참조 : Mastering Bitcoin]

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

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

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

[참조 : Mastering Bitcoin]

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

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