블록체인 확장성 솔루션 시리즈 6–1 :: NiPoPoW (Non-Interactive Proofs of Proof-of-Work) — SPV와 SkipList
Seong-Wook HUH (Wook)
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
1st Review: 문건기(Geon-gi Mun), 오영택(Youngtaek (Robbie) OH), 이규택(Lee Kyutaek)
2nd Review: 오영택(Youngtaek (Robbie) OH), 한겨레(Han Geore)
서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’에서 블록체인의 스케일링 솔루션에 관한 글들을 시리즈로 연재합니다. 시리즈의 여섯 번째 주인공은 Non-Interactive Proofs of Proof-of-Work 입니다.
이 글은 블록체인 확장성 솔루션 시리즈 3–1 :: Interchain Overview 에서 더 나아가 상세한 원리와 실제 적용까지 다루는 글이다. 서로 다른 블록체인, 특히 PoW 를 컨센서스로 사용하는 두 체인 간의 자산 교환 등 상호작용 과정에서 상대 체인의 Consistency를 검증하는 것은 필수적이다. 상대 체인의 Consistency를 검증할 수 없다면 근본적으로 해당 체인에 있는 내 자산의 유효성이 보장될 수 없고, 이전 글 등에서 다뤘던 인터체인 솔루션들은 무용지물이 된다. 하지만 전체 체인을 전부 다운로드하여 검증하려면 너무 많은 시간과 비용이 들고, 인터넷 환경이 좋지 않거나 휴대폰 등 저장공간이 적고 컴퓨팅 파워가 약한 기기에서는 애초에 불가능한 일이다. 따라서 더 가볍고 효율적인 검증 방식이 필요한데, 그중 최근에 연구되고 있는 것이 NIPoPoW (Non-Interactive Proofs of Proof-of-Work) 이다.
이 글과 이어지는 글들에서 NIPoPoW를 이해하기 위한 배경지식과 NIPoPoW 가 무엇인지, 그리고 실제 구현 과정을 다룰 것이다. 이전 글인 블록체인 확장성 솔루션 시리즈 3–1 :: Interchain Overview 에서 다룬 Two Way Pegging 개념과 Two Way Pegging에서 SPV Proofs 가 어떻게 쓰이는지를 먼저 배경지식으로 알고 있어야 이 글과 다음 글들을 읽기 수월할 것이다. 이 글에서는 가장 핵심적인 배경지식인 Simplified Payment Verification(SPV)와 더 나아간 기술인 Compact SPV의 기반이 되는 Skip list에 대해 자세히 알아볼 것이다.
글의 전체 구성은 다음과 같다.
- 서론
- SPV 노드
- SPV 노드 매커니즘
- Skip list 와 비트코인의 Block Skip-list Pointer
- 마무리
SPV 노드 (Lightweight 노드)
비트코인을 비롯한 대부분의 블록체인 네트워크상에는 여러 타입의 노드(참여자)들이 존재하는데, 데이터 저장 방식에 있어 이를 크게 2가지로 나눌 수 있다. 하나는 풀 노드(Full nodes)이고 다른 하나는 SPV (Simplified Payment Verification) 노드이다.
풀 노드는 제네시스 블록부터 현재까지의 모든 블록들을 저장한다. 그럼으로써 각 블록의 검증, 블록에 포함된 각 트랜잭션의 검증을 자체적으로 수행할 수 있다. 새로운 블록과 트랜잭션을 검증하는 구체적인 로직은 여기에서 볼 수 있다. 비트코인의 경우 이 모든 데이터의 크기는 현재 (2018.11.20) 약 187GB이고 최근에는 하루에 대략 130MB씩 커지고 있다. 이는 스마트폰이나 태블릿, 그 외 많은 IoT 기기에 담기 힘든 크기이고, 그래서 SPV 노드의 필요성이 대두되었다.
SPV 노드는 풀 노드와 다르게 트랜잭션들은 제외하고 오직 블록의 헤더만을 저장한다. 비트코인의 블록 헤더 크기는 80 bytes이다. 지금까지 550,785 번 째 블록이 채굴되었으니 SPV 노드가 저장해야 하는 전체 크기는 현재 약 42MB이고, 이는 실제로 풀노드가 저장해야 하는 데이터 크기의 약 2.3% 정도이다. 하지만 데이터 일부만을 저장하기 때문에 발생하는 문제가 있다. 바로 SPV 노드 자체적으로는 트랜잭션의 검증이 불가능하고 풀 노드의 도움을 받아야 한다는 것이다. 지금부터 비트코인을 기준으로 SPV 노드가 어떤 매커니즘으로 트랜잭션을 검증하는지 알아보겠다.
SPV 노드 매커니즘
Block Header
먼저 SPV 노드가 저장하는 블록 헤더의 구조는 위와 같다. 이 중에서 SPV를 이해하기 위해 가장 중요한 것은 블록 안의 모든 트랜잭션들을 베이스로 만들어지는 머클 루트이다. 머클 루트란, 블록 안의 모든 트랜잭션들의 해시값들을 리프(leaf)로 하여 만들어지는 머클 트리의 최상위 노드이다. (머클 트리에 대해 너무 자세하게 다루는 것은 본 글의 요지를 흐릴 수 있기에 넘어간다. 간단히 설명하면, 리프들을 2개씩 합쳐서 해시하여 상위 노드 들을 만들고, 이를 반복하여 1개의 해시값(머클 루트)이 만들어지는 트리구조이다) SPV는 트랜잭션 데이터를 저장하지 않기 때문에 특정 트랜잭션이 유효한지 검증해야 하는 상황이 생기면 풀 노드로부터 그 트랜잭션과 연관된 머클 경로(merkle path) (또는 merkle branch) 를 받아와서 머클 루트 해시를 검증하여 그 트랜잭션이 특정 블록에 포함되어 있다는 것을 검증한다.
위 그림에서, HK 트랜잭션에 대한 머클 경로가 파란색으로 표시되어 있다. (HL, HIJ, HMNOP, HABCDEFGH) HK와 HL을 합쳐서 해시 하면 HKL을 알 수 있고, HKL과 HIJ로 HIJKL을, HIJKL과 HMNOP로 HIJKLMNOP를, 마지막으로 HIJKLMNOP와 HABCDEFGH를 통해 머클 루트 값을 알 수 있다. 만약 이렇게 최종적으로 계산된 머클 루트 값이 SPV 노드 스스로 보유한 헤더에 포함된 머클 루트 해시값과 다르다면(악의적인 풀 노드의 데이터 조작, reorg 케이스 등등에 의해 일어날 수 있다) 검증, 즉 해당 트랜잭션을 이용한 SPV Proof 가 실패하게 되고 이를 이용한 two-way pegging 등은 더이상 진행하지 않는다.
그럼 이제부터 위 과정을 정확히 이해하기 위해 SPV 노드가 풀 노드와 통신하는 매커니즘에 대해 알아보겠다.
MerkleBlock Message
SPV 노드는 블록 헤더에서 머클 루트를 얻고 풀 노드 피어로부터 특정 트랜잭션에 대한 머클 경로 해시값들을 얻음으로써 트랜잭션이 블록에 포함되었다는 것을 확인할 수 있다. 하지만 어디까지나 특정 풀 노드로부터 받은 블록에 해당 트랜잭션이 포함되었다는 것을 알 수 있고, 해당 블록이 메인 체인에 포함되는지는 보장되지 않는다. 따라서 트랜잭션의 포함 여부를 검증하고 해당 블록 뒤에 일정 수의 블록이 쌓이는 것을 확인할 필요가 있다. 비트코인의 경우 특정 블록 뒤에 6개의 블록이 쌓이면 그 블록이 확정되었다고 본다.
예를 들어 위 그림에서 트랜잭션 E가 블록에 추가되었는지 확인하기 위해 SPV 노드는 머클 루트 외에 merkle path (F, GG, ABCD) 해시값만 필요하다. SPV 노드는 다른 트랜잭션에 대해서는 전혀 알 필요가 없다.
전체 데이터를 보유하지 않고 풀 노드에 의존하는 특성 때문에 SPV 노드는 크게 2개의 취약점을 가진다.
- 먼저, SPV 노드가 풀 노드에 특정 트랜잭션에 대한 정보만을 요청함으로 인해 풀 노드가 SPV 노드 유저와 관련된 주소들 등 정보를 수집할 수 있고, 풀 노드는 이를 활용해 특정 유저에 대해 DoS 공격을 시도할 수 있다. 이 문제를 해결하기 위해 비트코인 코어에 Bloom Filter가 구현되었다.(BIP-37) Bloom Filter를 사용하면 SPV 노드는 자신이 원하는 트랜잭션을 특정하지 않고 일종의 패턴만을 풀 노드에 제공하여 자신이 원하는 트랜잭션 외에 그 패턴과 일치하는 여러 트랜잭션들을 받을 수 있기 때문에 (간단히 예를 들어, 마지막 3개 문자가 ‘3EF’인 주소가 생성한 트랜잭션) 이런 DoS 공격을 어느 정도 회피할 수 있다.
- 그리고, 풀 노드가 악의적으로 데이터를 누락시킬 수 있다. 풀 노드는 트랜잭션이 없는데 있다고(false positive) 속이는 것은 힘들지만, 있는데 없다고(false negative) 속이기는 쉽다. 원한다면 간단하게 데이터를 누락시킬 수 있기 때문이다. (이는 일종의 DoS 공격이다. 자세한 내용은 위 BIP-37 을 참고.) SPV 노드는 정직하리라 생각되는 풀 노드 피어 다수로부터 데이터를 받아오는 식으로 이 문제를 해결할 수 있지만, 여전히 네트워크 파티셔닝이나 시빌 어택의 가능성이 있기 때문에 네트워크 연결에 있어 신중해야 한다.
매커니즘에 대해 더 자세하게 알기 위해 실제로 비트코인에서 SPV 노드가 풀 노드로부터 받는 데이터를 분석해보겠다. 위에서 예시를 든, 풀 노드가 SPV의 요청에 따라 보내주는 데이터가 merkleblock message 이다. 이 메시지는 아래와 같은 포맷을 가진다.
실제 위 머클트리 예시에서 E 트랜잭션에 대한 merkleblock message의 hexdump 값은 아래와 같은 형태일 것이다.
위의 hexdump에서 볼 수 있듯이 merkleblock message는 트랜잭션 수, 해시 리스트 및 one-bit 플래그 리스트의 세 가지 특수 데이터 형식을 제공한다. 이 데이터들을 사용하여 아래의 규칙으로 파싱하여 트랜잭션을 검증한다.
- 트랜잭션 수를 사용하여 비어있는 머클 트리를 생성한다. 이 트리에서 제일 하단 노드들을 TXID 노드 (이 노드들의 해시는 TXID이다) 라고 하고 나머지 노드 (merkle root 포함)는 TXID가 아닌 노드 라고 하겠다.
- merkleblock message에 표시된 대로 해시 리스트(Hash1, Hash2, Hash3, Hash4) 및 플래그 비트(1 0 1 1 1 0 0 0)의 순서를 유지한 상태에서 순서대로 각 값을 평가하여 처리한다. 다음 플래그 또는 다음 해시 라는 것은 해시 리스트, 플래그 비트 각각의 다음 순서의 값을 의미한다.
- Merkle root 노드와 첫 번째 플래그에서 시작한다. 아래 표는 처리 중인 노드가 TXID 노드인지 TXID가 아닌 노드인지에 따라 플래그를 평가하는 방법이다. 노드에 플래그를 적용한 후에는 동일한 노드에 다른 플래그를 적용하거나 같은 플래그를 다시 사용할 수 없다. 또한, 다음 플래그를 적용하는 경우는 새로운 노드를 처리하기 시작할 때뿐이다.
- 하위 노드를 처리할 때 상위 노드로 돌아가기 전에 하위 노드 (원래 노드의 손자) 또는 그보다 더 하위 노드를 처리해야 할 수도 있다. 플래그가 0 인 TXID 노드 또는 TXID가 아닌 노드에 도달할 때까지 깊이를 우선 (depth first) 한다.
- 플래그가 0 인 TXID 노드 또는 TXID가 아닌 노드를 처리한 후, 플래그 처리를 중지하고 트리를 올라가기 시작한다. 왼쪽 차일드 노드의 해시만 알려진 노드에 도달하면 오른쪽 차일드 노드(존재하는 경우)와 그 후손을 타고 내려간다.
위 그림을 보면 더 쉽게 이해할 수 있다. H1, H2, H3, H4 는 각각 ABCD, E, F, GG 와 매칭된다.
- 맨 처음 플래그는 1이고 시작점은 머클 루트이다. 머클 루트는 TXID 노드가 아니므로 위 표에 의하면 해시를 계산해야 하고, 먼저 왼쪽 자식 노드를 처리해야 한다. (그리고 추후 오른쪽 자식 노드의 해시를 구한 후 둘을 합해 현재 노드(머클 루트)의 해시를 구해야 한다) 이제 머클 루트 왼쪽 자식 노드를 가리킨 상태에서 다음 플래그를 처리한다.
- 다음 플래그는 0이다. 현재 가리키는 노드는 TXID 노드가 아니다. 표에 의하면 다음 해시, 즉 H1을 이 노드의 해시로 사용한다. 그리고 자손 노드들에 대해서는 더 처리하지 않는다고 했으니 위 과정 1의 나머지 작업에 의해 이제 머클 루트의 오른쪽 자식 노드를 가리킨 상태에서 다음 플래그로 넘어간다.
- 다음 플래그는 1이다. 그리고 현재 노드는 TXID 노드가 아니므로 과정 1 처럼 왼쪽 자식 노드의 해시를 구해야 한다. 왼쪽 자식 노드를 가리킨 상태에서 다음 플래그를 처리한다.
- 다음 플래그 또한 1이다. 그리고 가리키는 노드 또한 마찬가지로 TXID 노드가 아니다. 똑같이 왼쪽 자식 노드를 가리키고 다음 플래그로 넘어간다.
- 다음 플래그는 1이다. 이번에 가리키는 노드는 TXID 노드이다. 표에 의해 다음해시인 H2를 이 노드의 TXID로 사용하고, 필터와 일치한다고(우리가 검증을 원하는 트랜잭션이라고) 표시한다. 이제 과정 4 나머지 작업에 의해 오른쪽 노드를 가리키고 다음 플래그로 넘어간다.
- 다음 플래그는 0이다. TXID 노드를 가리키고 있으므로 다음해시인 H3를 이 노드의 TXID로 사용한다. 플래그가 0이므로 필터와 일치하지는 않는다. 이제 과정 4 마지막 단계에 의해 과정 5에서 구한 해시와 지금 구한 해시를 64 raw bytes로 연결하고 이를 다시 해시하여 과정 4 노드의 해시로 사용한다. 그리고 과정 3의 나머지 작업에 의해 오른쪽 노드를 가리킨다.
- 다음 플래그는 0이고 이번에 가리키는 노드는 TXID노드가 아니다. 따라서 다음 해시인 H4를 이 노드의 해시로 사용한다. 그리고 과정 6에서 구한 해시와 지금 구한 해시를 64 raw bytes로 연결하고 이를 해시 하여 과정 3 노드의 해시로 사용한다. 그리고 다시 과정 2에서 구한 해시(H2)와 지금 구한 해시를 연결하고 해시하면 드디어 과정 1의 머클 루트 해시가 된다. 이제 이 계산된 머클 루트 해시와 SPV 노드가 보유한 헤더에 포함된 머클 루트 해시를 비교하여 일치한다면 검증에 성공한다.
아래와 같은 경우 검증이 실패한다.
- 두 차일드 노드의 해시값이 같은 경우 (CVE-2012–2459)
- 해시 리스트에서 사용되지 않은 해시가 있는 경우
- 플래그 리스트에서 사용되지 않은 플래그 비트가 있는 경우
- 계산된 머클 루트 해시가 블록 헤더의 그것과 일치하지 않는 경우
- 블록 헤더가 유효하지 않은 경우 (헤더의 해시가 nBits 헤더 필드로 인코딩 된 target threshold 보다 작거나 같은지 확인)
SPV 노드는 위와 같은 매커니즘으로 특정 트랜잭션을 검증하고, 또한 해당 트랜잭션이 들어있는 블록의 헤더가 유효한지 확인한 후 해당 블록의 Depth가 일정 수 이상일 경우 해당 트랜잭션의 UTXO set과 지갑 밸런스를 확정할 수 있다.
Skip list and Bitcoin
앞에서 SPV가 헤더 데이터만으로 어떻게 트랜잭션을 검증하고, 헤더 데이터만 보유함으로 인해 어떤 취약점을 가지는지 알아보았다. SPV 를 통해 작은 데이터만으로도 트랜잭션의 증명이 가능해졌지만, 비트코인의 scriptSig는 비트코인 코드에 따라 10,000 bytes를 초과할 수 없고, 평범한 SPV Proofs는 트랜잭션에 적합 할 정도로 작지는 않다. 하루의 작업에 대한 SPV Proofs는 약 144 * 80 = 11,520 bytes 이고(하루 1440분, 10분에 1블록) output 및 merkle path까지 포함한다면 12,000 bytes 를 훨씬 넘기 때문이다. 따라서 PoPoW가 가능해지려면 일반 SPV Proofs보다 더 효율적인 방법이 필요한데, 그 중 하나가 Compact SPV Proofs이다.
Compact SPV Proofs는 이전 글에 언급된 Two Way Pegging을 다룬 사이드체인 페이퍼논문의 Appendix B 에서 처음 정의되었는데, 블록들 중에서 헤더 해시 값이 난이도 타겟 값보다 작은 블록들을 연결하여 더 효율적인 Proofs가 가능해질 수 있다는 내용이다. 이를 이해하기 위해서는 Skip list 라는 자료구조 / 알고리즘을 이해해야 한다. 이번 섹션에서는 Skip list에 대해 자세히 알아보고, 현재 비트코인에서 Skip list가 어떻게 사용되고 있는지 알아보겠다.
Skip list
스킵 리스트는 정렬된 형태를 유지하면서 빠른 탐색 및 데이터 추가, 삭제를 할 수 있는 링크드 리스트 형태의 자료구조이다. 스킵 리스트의 창시자인 William Pugh의 논문 을 기준으로 핵심적인 내용만 설명하겠다. 스킵 리스트의 아이디어는 정렬된 링크드 리스트의 단점을 극복하는 방법을 찾는 것으로부터 출발한다.
정렬된 링크드 리스트에서 특정 노드를 찾는데 드는 비용은 최악의 경우 O(n) 이다.
(아래 모든 리스트에 위 그림처럼 맨 앞 헤드와 맨 뒤 널포인터 노드가 존재한다고 가정한다.)
예를 들어 위와 같은 정렬된 링크드 리스트에서 Search(91)을 수행한다고 했을 때, 작은 노드부터 시작한다고 하면 8번의 비교가 필요하다. (10, 25, 27, 42, 67, 72, 84, 91)
하지만 아래와 같이 짝수 번째 노드마다 포인터를 하나씩 더 갖게 한다면 이 횟수를 줄일 수 있다. 상위 레이어에서 비교하여 나가다가 (10, 27, 67, 84) 찾고자 하는 값보다 더 큰 값(이 경우 96), 혹은 Null 포인터를 만나면 하위 레이어로 내려가는 방식이다.
이런 레이어를 계속해서 쌓으면 아래와 같은 형태의 리스트가 만들어진다.
이진 트리를 닮았다. 이렇게 만들어진 스킵 리스트의 탐색 비용은 O(logn)이 된다. (레이어 수 logn, 각 레이어에서 최대 비교 횟수 2번) 위 예시의 경우 최하위 레이어에선 8번 비교해야 하지만, 위 스킵리스트 구조에서는 7번 비교하게 된다. (10, 96, 67, 96, 84, 96, 91) 노드 수가 적어 별로 효율적으로 보이지 않지만 노드 수가 많아질수록 비교 횟수가 기하급수적으로 줄어든다.
하지만 이런 이상적인 형태의 스킵 리스트의 경우, 새로운 데이터를 추가하거나 기존 데이터를 빼는 경우 모든 레이어의 포인터를 수정해야 하는 문제가 있다. (비용이 많이 든다.) 따라서 저자는 새로 추가되는 노드의 레벨을 임의로(probabilistic) 정하게 한다. 예를 들어, 동전을 던져서 연속해서 같은 면이 나온 횟수로 레벨을 정하는 것이다. 다만, 스킵 리스트에서 레벨이 높아짐에 따라 그만큼 메모리 사용량이 늘어난다. 레벨을 결정하는 확률 p에 따른 탐색 속도와 노드당 평균 포인터 수는 다음과 같다.
Block Skip-list Pointer
비트코인에는 이미 스킵 리스트 자료구조를 활용한 코드가 포함되어 있다. 비트코인의 모든 블록 인덱스에는 다음과 같은 속성이 포함되어 있다.
// pointer to the index of some further predecessor of this blockCBlockIndex* pskip;
위 chain.h 코드에서 주어진 블록의 “skip pointer”를 선택하는 알고리즘은 아래와 같다.
/** Turn the lowest '1' bit in the binary representation of a number into a '0'. */
int static inline InvertLowestOne(int n) { return n & (n - 1); }/** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
int static inline GetSkipHeight(int height) {
if (height < 2)
return 0;
// Determine which height to jump back to. Any number strictly lower than height is acceptable,
// but the following expression seems to perform well in simulations (max 110 steps to go back
// up to 2**18 blocks).
return (height & 1) ? InvertLowestOne(InvertLowestOne(height - 1)) + 1 : InvertLowestOne(height);
}
Skip pointer는 블록체인을 탐색하는 시간을 O(n) 에서 O(log n) 으로 줄여준다.
위 구조는 블록체인의 height를 bit 로 표현 하였을 때, 11101001 과 같이 되어 있는 경우,
11101001 -> 11101000 -> 11100000 -> 11000000 -> 10000000 -> 00000000(genesis)과 같이 가장 낮은 1이 있는 bit를 0으로 바꿔 가면서 블록을 다운 받는 형식으로 진행한다. 즉, 블록의 height를 skip list 구조에 넣어 둔 것으로, header에 적용하여 실제 spv proof로 활용한 것은 아니다. 하지만 다음에 나올 Compact SPV Proof, PoPoW등은 실제 header를 변형하여 spv proof로 활용한다.
마치며
지금까지 크게 SPV 노드란 무엇이고 어떻게 동작하는지를 알아보고, 나아가서 일반 SPV Proofs 보다 더 효율적인 Compact SPV Proofs에 대한 간단한 소개와 함께 이를 이해하기 위한 배경지식인 Skip list를 설명하고 Skip list 가 실제 비트코인에서 사용되는 코드를 분석해 보았다.
사토시 나카모토가 작성한 최초의 비트코인 논문 Bitcoin: A Peer-to-Peer Electronic Cash System 의 섹션 8이 SPV에 대한 내용이다. 당시에는 비트코인이 저장공간, 네트워크 속도 등이 제한된 환경에서도 구동될 수 있도록 고안된 시스템이였겠지만 그런 한계의 극복을 위한 노력이 발전하여 이제 인터체인 기술에서 핵심적으로 사용되고 있다. ‘보수’적인 비트코인을 기반으로 수많은 혁신이 이루어 지고 있는 현재를 직접 공부하는 것이 정말 즐거웠다.
다음 글들에서는 Skip list 맨 처음에 잠시 언급된 Compact SPV Proofs, 그리고 이와 함께 Enabling Blockchain Innovations with Pegged Sidechains 논문에 나오는 Reorganisation Proof에 대해 자세히 다루고, 나아가 PoPoW 에 대해서 알아보도록 하겠다.
2편: NiPoPoW (Non-Interactive Proofs of Proof-of-Work) — SPV응용
References
[1] Bitcoin: A Peer-to-Peer Electronic Cash System
[2] https://github.com/bitcoinbook/bitcoinbook/
[3] https://bitcoin.org/en/developer-guide
[4] https://bitcoin.org/en/developer-reference
[5] https://blockstream.com/sidechains.pdf
[6] https://www.epaperpress.com/sortsearch/download/skiplist.pdf
[7] https://en.bitcoin.it/wiki/Bitcoin_Core_0.11_(ch_5):_Initial_Block_Download
[8] https://www.epaperpress.com/sortsearch/download/skiplist.pdf
