Bitcoin#5: 풀(Pool)과 머클 루트
블록 구조 (1편)
거래는 노드들을 통해 전파되며 검증(Verification)을 거치게 된다. 몇가지 주요 검증 조건은 다음과 같다.
구문, 데이터 구조 확인
거래크기가 블록 최대 사이즈보다 작은지
이미 사용된 UTXO를 썼는지
이미 사용된 UTXO의 소비를 파악함으로써 이중지불을 방지할 수 있다.
참조 거래가 풀(Pool)이나 메인 체인에 있는지
거래는 이전거래의 출력값을 참조하게 구성되어 있었다. 하지만 참조할 거래가 확인이 되지 않는다면 과연 그 거래는 잘못된 것일까?
고아 거래(Orphan transaction)
네트워크상의 전송 속도 차이로 인해 이전 거래를 전송받지 못할 경우가 있다. 이때 참조하고자 하는 이전 거래를 '부모 거래', 부모거래를 참조하는 이후 거래를 '자식 거래'라고 한다. 부모거래가 도착하기 전 자식거래를 먼저 받을 경우 해당 거래는 '고아 거래'로 간주한다. 고아 거래는 고아거래 풀(Orphan transaction pool)에 보관되기도 한다.
노드들은 중앙화된 데이터에서 조회하는 형식이 아닌 탈중앙화된 환경에서 UTXO를 이용하여 거래를 작
성하거나, 거래들을 모아 블록을 형성한다. 전달 받은 거래는 위와 같은 검증을 마친 후 해당 노드의 거래 풀(Pool)에 추가되고 다시 이웃 노드로 전달이 된다. 그러한 과정에서 풀(pool)이 구성된다. 풀의 종류는 다음과 같다.
풀(Pool)
거래 풀(Transaction Pool, Memory Pool)
노드들은 이웃노드에게 전송받은 거래를 검증 후 거래 풀에 담는다. 채굴자는 블록을 형성할 때, 본인의 거래 풀을 이용하여 블록을 형성하게 된다.
거래 풀외에도 몇몇 노드들은 특별한 풀을 형성하기도 한다.
고아거래 풀(Orphan transaction pool)
거래를 전송받을 때 자식 거래가 있는지 확인 후, 만약 있다면 부모거래와 자식거래 모두 거래풀로 옮긴다.
이는 유효한 거래가 버려지는 것을 방지하며 거래가 유효하게 구성될 수 있도록 한다. 고아거래풀은 서비스공격(Dos)를 예방하기 위해 해당 풀의 거래 보관 갯수를 제한한다.
두가지 풀은 모두 로컬 메모리에 저장되며, 검증은 되었지만 승인이 되지 않은 거래를 담고 있다. 또한 노드가 시작될때 메시지로 직접 채워져 노드간 정보의 차이가 크다.
UTXO 풀(UTXO Pool)
소비되지 않은 출력값(UTXO)들로 구성되어있으며 초기에 비워져 있는 형태가 아닌, 블록체인상의 모든 UTXO데이터를 저장한다. 즉, UTXO 풀은 네트워크의 합의를 의미하기에 노드간 차이가 적다. 이는 로컬 메모리에 저장되거나 데이터베이스 테이블 형태로 영구저장소에 저장되며 승인된 출력값을 담고 있다. 2009년에 생성된 UTXO 또한 포함되어 있다.
채굴자들은 이러한 풀을 통해 거래들을 보관하며 거래 풀을 참고하여 거래를 모아 블록에 담게 된다.
그렇다면 블록은 어떠한 방식으로 거래를 담고, 그 블록은 어떠한 구조를 이루고 있을까?
블록의 구성블록은 그림과 같이 헤더(Header), 거래로 나뉘어 있다.
사실 블록 구조에는 '바디(Body)'라는 필드는 존재하지 않는다. 블록의 구성으로 '블록 헤더'외에 '블록 크기', '거래 개수'도 있으며 '거래'들을 담은 부분을 주로 '바디(Body)'라고 칭하며 실제로 대부분의 크기를 차지한다.
블록체인이 왜 ‘체인’처럼, 즉 암호화되어 있다고 하는지는 헤더를 보면 알 수 있다.
헤더(Header)의 구조
블록 헤더 구조1. 버전(Version)
비트코인의 ‘어떤 버전’을 쓰고 있는지를 표기한다. 이는 소프트웨어/ 프로토콜 업그레이드 추적을 위한 버전 번호이다.
2. 이전 블록 헤더 해시
이는 블록체인을 ‘체인’으로 만드는 중요한 개념이다.
재밌는 사실은 '블록 해시'라고 많이 칭하지만, 실제로 블록 전체가 아닌 '헤더'를 해시하며, '현재' 블록의 해시를 담지 않아 오해를 바로잡기 위해 '이전 블록 헤더 해시'라고 명시했다. 즉, N번째 블록을 채굴하려는 노드가 N-1번째 블록을 전송받았을 때, 바로 이전 블록(N-1번째 블록)에 대한 ‘헤더 해시’를 직접 계산(정확히는 2번 해시를 한다)하여 헤더에 넣는다는 사실이다. 구체적인 채굴의 과정은 이후에 이어서 설명하겠다.
3. 타임스탬프
유닉스 타임 (1970년 1월 1일) 기준으로 초단위 해당 블록 채굴 시각을 기록하게 된다.
4. 머클 루트 (Merkle Root)
머클 루트를 알기 위해서는 머클 트리(Merkle Tree)를 먼저 살펴보자. 머클 트리는 ‘트리구조’를 형성하고 있는 암호화 과정이라고 생각하면 쉽다. 꼭대기에 위치한 최종 값을 '루트', 하부의 값들을 '리프'라고 칭한다.
머클 트리(Merkle Tree)8개 거래에 대한 머클 트리를 예시로 들자. 위 그림과 같이 거래에 대한 해시값이 Hash1부터 Hash8과 같이 '리프'가 이어져 있고, 이를 두 개씩 묶어 더한 후 같은 방식으로 진행하여 최종 값인 머클 루트를 얻는다. (Hash9 값은 (Hash1 + Hash2)의 sha256 해시를 2번 취한 값 )
머클 루트(Merkle Root)란, 단어 속 ‘root’에서 알 수 있듯이 뿌리와 같은 결과로써 하나의 최종 값을 의미하며, 그림상으로는 맨 위에 해당하는 값이 된다.
이 트리를 보면서 ‘거래가 홀수일 경우는 어떻게 되지?’라는 의문이 생길 수 있다. 이러한 경우 맨 마지막 거래를 복사하여 거래를 짝수개로 만들어 사용하는 원칙으로 이용되고 있다. (이러한 경우를 균형 트리(balanced tree))
머클 트리를 보면서 ‘거래의 원본이 그대로 저장이 안 되고 해시값을 이용하는 것이 왜 필요한가?’에 대한 의문이 들 수 있지만, 해시의 쓰임새를 다시 한번 생각해 봤을 때, 위변조를 한 번에 알 수 있다는 장점이 있기에 머클 루트는 매우 중요하다. 즉, 블록 안의 300개의 데이터 중 1개의 데이터, 혹은 그 1개의 데이터 중 글자 하나만 바뀌어도 해시값인 머클 루트는 완전히 다른 값이 나온다는 것을 인지한다면 머클 루트의 효과를 확실히 알 수 있을 것이다. (참고로 이더리움의 경우, 머클 패트리샤 트리(Merkle-Patricia tree(trie))를 이용하여 '상태(state)'의 정보를 저장한다)
머클 트리의 장점은 위변조 가능성을 넘어서, 빠른 탐색을 용이하게 만들어준다. 머클 패스(Merkle Path)를 이용한다면, 머클 루트를 알고 있을 때, ‘어떠한 거래가 들어있다는 확인’을 하는 절차는 매우 용이하다. 검증 과정과 머클 경로가 무엇인지에 대해 살펴보겠다.
예를 들어보자.
머클 트리 예시A는 본인의 거래 Tx1이 블록에 담겨있는지 확인하고자 한다면, 풀 노드(full-node)로부터 블록 헤더와, 머클 패스를 전달받는다. 이때, 블록 헤더 중 머클 루트와 머클 패스를 통해 Tx1의 포함 여부를 확인한다. Tx1이 들어있다는 것을 알려면 어떠한 머클 패스, 즉 어떠한 경로가 필요할까?
Hash2, Hash10, Hash14 만 있으면 머클 루트를 직접 계산하여 도출할 수 있다. 즉, A는 Tx1을 이용하여 Hash1을 만들면, 머클 패스에 포함된 Hash2를 더하며 Hash9를 얻을 수 있다. 이후 Hash9과 머클 패스에 포함되어 있던 Hash10을 통해 Hash13을 얻을 수 있고 같은 방식으로 Hash14를 통해 머클 루트를 직접 구할 수 있다. 이 결괏값을 '전달받은 머클 루트'와 비교하여 일치한다면 본인 거래 Tx1이 블록에 담겨있다는 것을 확인할 수 있을 것이다. 이는 log2(8)=3개의 머클 경로가 포함되어있음을 확인할 수 있다.
이는 SPV(Simplified Payment Verification) 노드가 쉽고 빠르게 특정 거래를 찾을 수 있게 도와준다.
노드(Node)
비트코인 P2P 네트워크에는 여러 종류의 노드가 있다. 모든 노드들은 라우팅 기능을 보유하고 있어 거래와 블록을 검증하고 전파한다.
풀 노드(Full node)
제네시스 블록부터 최신 데이터까지 모두 보관하는 노드이다. 즉, 외부 노드의 도움 및 신뢰 없이 블록체인을 이용할 수 있다. 비트코인은 본래 모든 노드가 풀 노드였다. 현재는 라이트웨이트(Lightweight) 노드의 역할도 생겨났다.
채굴 노드(Mining node)
채굴노드는 반드시 풀노드일 필요 없다. 라이트웨이트 노드로 채굴에 참여하고 싶다면 풀 서버를 이용하여 풀채굴에 참여하면 된다.
SPV(Simplified Payment Verification) 노드
SPV노드는 라이트웨이트(Lightweight)노드와 동일한 개념으로, 말 그대로 '단순 지불 검증 노드'로서 풀 블록체인을 저장하지 않아도 특정 거래를 확인할 수 있는 노드이다. 흔히 오해하는 중요한 사실은 SPV노드는 거래를 '확인'할 수 있지만 '직접 검증'할 수는 없다. 해당 노드는 거래가 담긴 블록의 깊이와 높이를 참고하여 단순 검증(안전하게 보관 되었다는 검증)은 할 수 있지만, 거래 전부에 대한 기록이 없기에 직접 검증(거래 자체가 적합한지)은 불가능하다. UTXO의 소비 여부 또한 검증할 수 없다.
SPV노드는 이웃 노드들에게 지불 검증을 위해 필요한 데이터를 요청하게 된다. 하지만 이러한 과정에서 SPV노드는 자연스레 프라이버시를 노출하게 된다. 즉, 필요하고자 하는 데이터가 무엇인지 그대로 전달해야한다. 이러한 점을 보완하기 위해 '블룸필터(Bloom Filter)'를 사용하여 원하는 데이터를 얻으면서 프라이버시를 유지할 수 있게 된다.
블룸필터(Bloom Filter)
블룸필터는 특정 패턴을 설정하여 조건을 맞추는 데이터를 취합하게 해준다. 쉽게 예를 들면 SPV 노드는 'skkrypto가 보낸 거래'를 찾기 위해 'pto 끝나는 사람이 보내는 거래'를 요청하는것과 같다. 정확성을 높이기 위해서는 '조건'을 구체화시켜야 하지만 그만큼 프라이버시는 노출된다. 여러가지 패턴을 더해 이루어지는 블룸필터는 BIP37에 규정되어 있으며 실제 구동방식은 훨씬 더 구체적이고 복잡하므로 궁금하다면 링크를 통해 확인하면 좋을것 같다.
Bloom Filter이후 채굴의 개념의 핵심인 ‘난이도 목표’, ‘넌스(nonce)’의 설명은 2편이 이어서 설명하겠다.
참고문헌
Antonopoulos, Andreas M. Mastering Bitcoin: Unlocking Digital Crypto-Currencies. OReilly, 2016.
손동하/ sohn@skkrypto.io
