[비트코인 구조] SPV(Simplified Payment Verification)

미리 알아야 할 내용들

---

[비트코인 구조] 머클 트리(Merkle Tree)

[비트코인 기본 구조] 6. 머클 트리와 SPV(Merkle Tree & SPV)

---

SPV(Simplified Payment Verification)

 

 SPV는 Simplifed Payment Verification 즉, 간소화된 지불 검증의 약자입니다. SPV가 무엇인지에 대해 간단하게 설명하고 넘어가겠습니다.

 

 이전 글에서 머클 트리를 이용하여 머클 루트를 구하고 이 값을 블록의 헤더에 담았습니다.

 

 

 즉, 블록의 헤더는 트랜잭션 전체를 저장하지 않고도 트랜잭션을 포함하게 됩니다. 따라서 블록 헤더들만을 연결해 체인을 만들더라도 하나의 블록체인을 형성할 수 있습니다.

 

 

 이것이 바로 블록의 헤더만을 연결한 체인인 SPV입니다. SPV는 트랜잭션을 포함하지 않고 있기 때문에 용량을 크게 줄일 수 있다는 장점이 있습니다.

 

 만약 SPV 노드가 어떤 트랜잭션이 블록에 포함되어 있는지를 검증하려면 어떻게 해야 할까요? 이 부분에 대해 지금부터 알아보겠습니다.

 

SPV 노드에서의 검증

 어떤 트랜잭션이 블록에 포함되어있는지 확인하려면 머클 트리를 만들어 머클 루트를 구한 후, 이 값을 블록 헤더에 있는 머클 루트의 값과 비교해야 합니다. 하지만 SPV 노드는 검증하고자 하는 트랜잭션 외의 트랜잭션을 가지고 있지 않습니다. 따라서 트랜잭션을 가지고 있는 다른 노드에게 트랜잭션을 요청해야 합니다. 이때 트랜잭션을 요청하게 되는 노드를 풀 노드(Full Node)라고 합니다. 풀 노드는 SPV 노드와는 다르게 모든 트랜잭션의 데이터를 가지고 있습니다.

 

 트랜잭션 데이터를 요청하여 머클 트리를 구성하고 머클 루트를 구해야 한다는 것까지는 알게 되었습니다. 문제는 어떤 방식으로 어떤 트랜잭션을 풀노드에게 요청해야 하는지입니다. 먼저 요청해야 할 트랜잭션에 대한 내용입니다. 만약 전체 트랜잭션이 이루는 머클 트리가 다음과 같고, SPV 노드가 트랜잭션 3을 가지고 검증하려 한다고 가정해 보겠습니다.

 

 

 이 경우 SPV 노드가 트랜잭션 3을 제외한 트랜잭션 0,1,2를 모두 요청해야 할까요? 그렇지 않습니다. 왜 그런지 트랜잭션 3에서부터 올라가 보겠습니다. 현재 SPV 노드가 알고 있는 값은 트랜잭션 3과 이 트랜잭션의 해시값입니다.

 

 

 루트 해시를 구하기 위해서는 트랜잭션 2와 트랜잭션 3의 해시값의 해시값인 해시23이 필요합니다. 즉, 트랜잭션 2를 풀노드에게 요청해야만 해시23을 구할 수 있습니다.

 

 

 이제 해시01과 해시23의 해시값을 이용해 루트 해시를 구해야 합니다. 해시01을 구하기 위해서는 트랜잭션 0과 1이 필요합니다. 하지만 현재 SPV 노드가 검증하고자 하는 트랜잭션은 트랜잭션 3입니다. 트랜잭션 검증을 위해 트랜잭션 0과 1을 요청할 필요는 없습니다. 대신 해시01을 풀노드에게 요청합니다.

 

 

 결론적으로 트랜잭션 2와 해시01만을 요청하여 머클 루트를 구할 수 있었습니다. 이처럼 머클 트리의 특성을 이용하면 꼭 필요한 최소한의 데이터만 요청하여 머클 루트를 구하고 이를 통해 트랜잭션의 포함 여부를 알아볼 수 있습니다.

 

 지금부터는 이러한 요청을 풀노드에게 보내는 방법과 받은 데이터를 이용하여 트리를 구성하는 방법에 대해 알아보겠습니다.

 

깊이 우선 탐색(Depth-first search)

 트리를 구성하기 위해서는 먼저 트리의 탐색 방법에 대해 알아야 합니다. 트리의 탐색 방법에는 크게 '너비 우선 탐색'과 '깊이 우선 탐색'이 있습니다. 이 중 비트코인에서 머클트리를 탐색할 때에 사용하는 방법은 바로 깊이 우선 탐색입니다. 깊이 우선 탐색은 단순하게 설명하면 부모 노드의 왼쪽 자식 노드를 먼저 방문한 뒤 오른쪽 자식 노드를 방문하는 탐색 방법입니다. 예를 들어 다음과 같이 탐색하는 것이 바로 깊이 우선 탐색입니다. 탐색은 해시 값만 진행합니다.

 

 

 트리를 탐색하는 방법을 알게 되었으니 필요한 값을 요청한 후 복원하는 방법에 대해 알아보겠습니다.

 

  트랜잭션 3을 검증하기 위해 필요한 값은 트랜잭션 2와 해시01 값이었습니다. 이 두 값을 이용하면 머클 트리를 구할 수 있었습니다. 따라서 풀 노드는 요청한 두 값을 플래그 비트(Flag bit)과 함께 SPV 노드에게 보내줍니다.

 

 플래그 비트는 해당 위치의 값이 요청하여 보낸 값인지 아니면 SPV가 구할 값인지를 나타내 줍니다. 풀 노드가 보낸 값이면 0을, SPV가 구할 값이면 1을 전송합니다. 예를 들어 위 경우의 플래그 비트는 다음과 같습니다.

 

플래그 비트: 10101

 

 이제 플래그 비트와 깊이 우선 탐색을 이용하여 트리를 어떻게 구성하는지 알아보겠습니다. 모든 트리 탐색의 시작은 루트 해시부터입니다.

 

 

 플래그 비트의 첫 번째 값은 1이므로 루트 해시는 SPV가 구하는 값이 됩니다. 따라서 왼쪽 노드로 탐색을 계속 진행합니다. 그다음 도착하게 되는 위치는 해시01 위치입니다.

 

 

 두 번째 플래그 비트의 값은 0입니다. 따라서 해시01의 값은 풀 노드로 부터 전달받는 값임을 알 수 있습니다. 트리에 해당 값을 넣은 뒤 자식으로의 탐색을 종료합니다. 해당 값보다 아래 위치한 값들의 해시 값이 해당 값이므로 추가적인 탐색을 진행할 필요가 없기 때문입니다. 깊이 우선 탐색 방식에 따라 이제는 오른쪽 방향으로 진행합니다.

 

 

 세 번째 플래그 비트는 1입니다. SPV가 구할 값이므로 탐색을 계속 진행합니다.

 

 

 네 번째 플래그 비트는 0입니다. 따라서 해시2 값(트랜잭션 2의 해시 값)을 받아옵니다. 이후 자식으로의 탐색을 종료하고 부모의 우측 노드로 탐색을 진행합니다.

 

 

 마지막 플래그 비트는 1입니다. 해시3은 SPV 노드가 검증하고자 하는 트랜잭션 3의 해시값이므로 받아올 필요가 없습니다. 모든 플래그 비트를 사용했으므로 탐색을 종료합니다. 풀 노드와 SPV는 이러한 방식으로 필요한 해시 값들을 보내고 얻습니다.

 

 지금까지 SPV에 대해 알아봤습니다. 이어지는 글에서는 이러한 데이터를 실제로는 어떻게 주고받는지에 대해 알아보겠습니다. 감사합니다.

 

 

이어지는 글들

---

[비트코인 구조] 블룸 필터(Bloom Filter)