블록체인 확장성 솔루션 시리즈 6–2 :: NiPoPoW (Non-Interactive Proofs of Proof-of-Work) — SPV응용

Published in

Decipher Media ｜디사이퍼 미디어

18 min readJun 11, 2019

이규택 (Lee Kyutaek)
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
Reviewed by오영택(Youngtaek (Robbie) OH), 박찬(Chan Park)

서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’에서 블록체인의 스케일링 솔루션에 관한 글들을 시리즈로 연재합니다. 시리즈의 여섯 번째 주인공은 Non-Interactive Proofs of Proof-of-Work 입니다.

이 글은, SPV 시리즈 part 1에 이은 시리즈 글로, 해당 글을 완독 하고 오는 것을 추천한다. part 2에서는 compact SPV와 NiPoPow의 기본 아이디어가 되는 high-value-hash highway(HVHH)에 대해서 알아보고, compact SPV의 구체적인 내용과 가능한 attack vector, 그리고 마지막으로 reorganization proof(이하, Reorg proof)에 대한 내용으로 글을 마무리한다.

[ 배경 지식 ]

1. 사이드 체인

사이드체인에 대한 자세한 설명은 디사이퍼 미디엄의 이전 글을 참조하길 바란다.

2. SPV Proof

기본적인 SPV에 대한 내용은 SPV시리즈 part 1을 참고

[ part2에서 설명할 내용 ]

1. Bitcoin SPV노드

2. High-value-hash-highway

3. compact SPV

Bitcoin SPV 노드

Compact SPV 와 PoPoW를 이해하기 전에, 기존 Bitcoin에서 SPV의 작동 방식을 다시 한번 짚고 넘어가자.

[Bitcoin: A Peer-to-Peer Electronic Cash System]

Bitcoin: A Peer-to-Peer Electronic Cash System에서 서술한 SPV 방식이 기존 Full node 방식과 다른 점은, Full node에서는 모든 트랜잭션을 받아 저장하고 있고, SPV방식은 merkle root 만을 이용하여 트랜잭션을 검증한다는 점이다.(세부 검증방식은 part 1 참고)

part 1에서 논의한 바와 같이, SPV의 경우 interchain 문제, 즉, 블록체인간의 통신, 자산 이동에 사용된다. 하지만 SPV 노드 에서 전체 데이터 사이즈는 N*80 bytes(N은 블록갯수) 가 되는데, 현재(2018년 11월 28일 오후 3시) 기준, 전체 블록 개수는 551793개로, SPV데이터 사이즈는 42Mbytes 가 된다. 따라서, SPV Proof로 사용되는 데이터는 비트코인 Script size의 한계인 10000bytes(≃10kbytes)를 넘고, 하루에 144개의 블록이 채굴된다고 할때, 이 블록들의 SPV Proof 마저도 144*80bytes = 115200bytes 이므로, 하루 채굴되는 블록들의 SPV Proof를 감당 할 수 없을 정도이므로 이를 비트코인과 다른 블록체인을 이어주는 Interchain 솔루션으로 활용된다고 가정하면, 구조적인 한계가 명확하다.

Sidechain[*] 논문에서는, 이런 한계점을 뛰어넘기 위해 Compact SPV라는 방식을 채택하는데, 본 글에선 이 Compact SPV 가 어떻게 skip list의 구조를 통해 SPV를 개선했는지, 그 발상을 시간 순서대로 서술하려고 한다.

High-Value-Hash Highway(HVHH)

HVHH는, 2012년 Andrew Miller의 bitcointalk의 한 토픽 으로 시작한다. 이 토픽은 추후, compact spv, sidechain, PoPoW(Proof of Proof of Work)등의 연구 초석이 되는 토픽이다.

해당 토픽에서 A. Miller는 비트코인 헤더에, 한 개의 data(up link)를 추가 하여 skip-list 와 비슷한 구조의 블록체인 스트럭쳐를 제안했다.

Skip-list 자료구조는 search 방식이 0번 node 에서 뒤 노드로 검색하는 방식이므로 down, forward link 를 가지고 있는 반면에, blockchain에서는 임의의 block height에 해당하는 block이 실제 longest chain rule에 만족하며 genesis 블록까지 연결되어있는지 확인 하는 것 이므로, up link, backward link(prev block hash) 로 이루어져 있는 형식으로 구현 하여 skip list 의 특징을 갖는 블록체인 구조를 제안하였다.

용어 정리

hash-value(B) : 블록(B)의 hash(bitwise)에 prefix로 붙어있는 0의 개수
C : honest node들이 채굴한 블록체인
C[i] : C에서 block height 이 i 인 블록
B.target : 블록(B)의 mining 시 필요한 최소 hash-value
B.back-link : 블록(B)의 back-link에 연결된 블록 (= prev block hash)
B.up-link: 블록(B)의 up-link에 연결된 블록

비트코인에 HVHH를 적용한 블록체인 구조에서는, 기존 비트코인 헤더에 up-link를 추가한 방식으로 헤더를 구성한다. up-link는, 이전 블록(prev block)의 hash-value보다 높은 hash-value를 갖는 블록을 가르키고 있다. 즉, pseudo code로 표현해 보면,

와 같다.

이러한 알고리즘으로 생성된 블록체인의 경우 어떤 블록 height(H)의 블록을 검증 할때, 확률적으로 log2(H)개의 블록만 있으면 검증 가능하다.

hash-value가 target 보다 커야 채굴에 성공하고, hash-value 가 1씩 증가 함에 따라 발견되는 확률이 ½ 가 되므로,

hash-value(B) — B.target = k 인 블록은 확률적으로 전체 블록중에서 12k의 비율로 나타난다.

따라서 확률적으로 C[0:H]의 블록 B 중에서 hash-value(B) — B.target의 최대값 은 log2H근방이 될 것이다. 따라서 proof를 만드는 경우, hash-value(C[H])-C[H].target 부터 최대값 까지 최대 한개씩 채워 질 것 이므로 log2H의 블록으로도 proof를 만들 수 있다.

Fork point

이렇게 구성한 spv proof는 fork point를 찾는데도 활용할 수 있다.

다음과 같은 상황을 가정해 보자.

만약 기존 spv proof를 사용하는 경우, fork 가 이루어진 부분을 찾기위해 genesis block 부터 iterative 하게 검색하거나 tip 에서부터 반대로 iterative 하게 확인 해야 한다. 즉, O(N)의 검색시간이 걸린다.

이 상황에서 high-value-hash highway spv proof를 구성하는 경우 두가지 경우가 있을 수 있다. fork 이전에 highest value hash 가 포함된 경우와 포함되지 않은 경우 이다.

**[fork 이전에 highest가 포함된 경우 — 보라색은 공통된 proof, 파란색,빨간색은 fork 이후 서로 다른 proof]**

fork 이전에 highest가 포함된 경우, spv proof 중에 공통된 proof 가 존재 할 것 이다.

**[fork 이후에 highest가 포함된 경우 — 파란색,빨간색은 fork 이후 서로 다른 proof]**

fork 이후에 highest가 포함된 경우 spv proof 중에 공통된 proof 가 존재 하지 않을 것이다.

따라서 spv proof 중에 가장 높은 highest value 를 비교하면 해당 block 이전, 이후에 fork가 존재하는지 확인 할 수 있다. 따라서, 서로 다른 두 spv proof의 겹치지 않기 시작하는 index와 그전 index의 block height 사이에서 fork가 일어난 것을 확인 할 수 있다.

이 방법을 통해 모든 블록을 확인 하는 것 보다 더 적은 시간으로 fork point를 찾을 수 있다.

실험 결과

High value hash highway 의 비트코인 적용 실험 결과

실제 비트코인에 High value hash highway를 적용하였을때, 예상과 같이 적은 양으로 spv proof를 생성 할 수 있는지 확인하였다.

실험은 high-value-hash값과 high-value-hash의 개수를 알아보기 위해서 진행하였다. 데이터는 실제 비트코인 블록(현재 538090블록) 데이터를 이용하였다.

위 그래프는 hash value 와 채굴 난이도를 비교 하였다. Hash value의 경우 256-log2hash 를 이용하여 나타내었다. 채굴 난이도가 변하더라도, 그보다 k만큼 높은 hash value를 가진 블럭의 비율은 독립적으로 나타나는 것을 확인 할 수 있다.

그래프3–1. Hash value 에서 난이도를 뺀 값을 소수점 단위는 내림 한 값

그래프3–2. Hash value 에서 난이도를 뺀 값을 소수점 단위는 내림 한 값

위 그래프3은 hash value 에서 난이도를 뺀 값인데, target 난이도 보다 얼마나 hash value가 높은 block을 채굴 했는지를 보여주는 그래프 이다. 우측에 해당 그래프에 표시를 한 그림을 보면, 빨간색 원으로 표시된 3개의 점이 있는데, 가장 위에 있는 점이 368527번 블록 이다. 당시에 해당된 난이도 보다 220만큼 채굴하기 힘든 블럭을 채굴 한 것이다. 심지어 가장 최근 블록인 552223블록 보다도 낮은 hash 값을 갖고 있는 것을 확인 할 수 있다.

high value hash highway visualization (코드)

Compact SPV

https://web.archive.org/web/20140226095319/http://download.wpsoftware.net/bitcoin/wizards/2013-12-18.txt

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-March/004727.html

Compact SPV proof는 Mark Firedenbach (blockstream co-founder)가 Bitcoin development mailing list에 남긴 글로 처음 소개되었다.

기본 아이디어

HVHH에서는 채굴하는 과정에서 어떤 uplink를 가지고 있는지 포함하게 되는 반면에, Compact SPV에서 채굴자는 모든 ancestor 블록의 헤더(sidechain 논문 기준)로 구성한 merkle root(transaction merkle root 와 같은 방식으로 구성)를 넣어서 채굴하게 된다. 이 merkle root를 통해 proof 를 만들고자 할 때, prover는 해당 블록의 해시 값이 target에 해당하는 값을 어떤 2 이상의 자연수 k로 나눈 값보다 작다면, 직전에 있는 블록부터 k만큼 앞에 있는 블록까지 proof 할 수 있게 해주는 것이다.

즉, HVHH는 prover가 곧 miner 였다면, Compact SPV 에서 prover 가 채굴자일 필요는 없으며, HVHH에서 어떤 상황에서도 같은 SPV proof 가 나오는 반면에, Compact SPV는 prover의 선택에 따라 다른 SPV proof가 나오게 된다.

이를 간략히 도식화 하면, (이미지 출처 : popeller.io)

B14(hash < T/3)가 proof하고 있는 블록들 : B14보다 3블록 앞에 있는 블록까지

이런 방식으로 proof 하였을때 평균적으로 몇개의 블록이 전체 블록체인을 증명하는데 필요한지 알아 보자.

쉬운 풀이를 위해 N height의 블록체인이 있고, target 난이도가 고정이라고 가정하자. (N-k)~N까지의 블록 중 에 0번 블록(genesis 블록)을 proof 할 수 있는 블록이 있을 확률을 먼저 구해보자. 각각의 블록이 proof에 genesis를 포함 하지 않을 확률을 모두 곱한후 1에서 빼주면 된다.

i 번째 블록의 proof가 genesis를 포함 할 확률이란 hash 값이 target/i 보다 작을 확률 이므로, 1/i 가 된다. 따라서 i 번째 블록의 proof가 genesis를 포함하지 않을 확률은i-1/i이 되고 (N-k)~N까지의 블록중에 genesis를 proof 할 수 있는 블록이 있을 확률은,

이다.

따라서 평균적으로 genesis 를 proof 할 수 있는 블록을 찾기 위해 봐야하는 블록의 개수는,

가 된다.

이를 확인하면, 평균적으로 전체의 약 1/2개를 확인하면 genesis를 proof 할 수 있는 블록을 찾을 수 있고, 그 블록을 proof 할 수 있는 블록을 찾기 위해선 찾은 1/2 중의 1/2 즉 전체의 1/4 을 확인하면 그 블록을 proof 할 수 있다.

이런 식으로 평균적으로 ½ 마다 블록이 한개 씩 있다고 하면, f(N) = f(N/2) +1 의 재귀 함수 형태로 선언 되며, f(N) ≃ log2(N) 으로 수렴한다. 따라서 전체 블록체인을 proof 하기 위한 평균적인 블록의 개수는 log2(N)이 된다.

이 결과를 현재(2018년 12월 2일) 비트코인 기준으로 본다면, 전체 블록 개수는 552223이므로 밑이 2인 log를 취한 값이 19.074이므로 약 19~20개 정도의 블록이 필요 할 것으로 예상된다.

Compact SPV의 Attack Vector

Compact SPV의 attack vector로 lucky block(compact SPV proof를 하기 위해 필요한 블록)들을 빠르게 찾아 공격하는 방법에 대해 생각해볼 수 있다. 아래 설명할 예시는 공격자가 전체 해시 파워의 10%를 갖고 있다는 상황을 가정하였다.

SPV 노드를 사용하는 비트코인 수신자에게 지불 증명을 하는 경우, 발신자는 해당 transaction에 사용된 UTXO가 Full 노드 블록체인 상에 존재함을 증명해야 한다. 공격자는 compact SPV를 만들어 이를 속이려 시도할 수 있다. 모든 블록 헤더를 이용하는 기존 SPV라면 공격자가 모든 블록을 위조해야 하므로 공격이 힘들다.

정직한 노드들이 900개의 블록을 생성하는 시간 동안 공격을 성공 시키기 위한 시나리오를 생각해보자. 논문에서 공격자는 전체 해시 파워의 10%를 가지고 있다고 가정하였기 때문에 정직한 노드들이 900개의 블록을 생성할 동안 공격자는 확률적으로 100개의 블록을 생성한다.

공격자는 자신이 만들어낸 SPV proof가 정직한 노드들이 만든 900개로 이루어진 SPV proof 보다 길다는 것을 주장 할 수 있어야 한다.

정직한 노드들이 만든 SPV proof는 확률적으로 900개의 가치를 가질 것 이므로 이를 공격하는 시나리오를 생각해 보자.

한개의 블록을 이용하여 공격 하는 경우 899개의 fake block을 만든 후(mining 으로 만든 block이 아닌 T(target 해쉬) 값 보다 작은 수를 이용) , 마지막에 T/900 보다 작은 블록을 채굴 하면 공격에 성공한다.

해당 블록을 채굴하는데 성공하는 경우는, 1/900이고, 공격자가 100번의 블록 생성할 시간이 주어졌다고 할 때, T/900보다 작은 해시값을 갖는 lucky block을 찾을 확률은 1- (100번의 시도동안 해당 블록을 못 찾을 확률)로 계산해볼 수 있다.

Compact SPV Attack에 대한 Countermeasure

skip_size 의 상한선 만들기
위에 설명한 바와 같이, spv proof 에 필요한 헤더 개수가 늘어남에 따라 공격 성공 확률이 줄어 든다. 공격이 성공하려면, skip_size가 커야 하므로, compact spv proof에 사용할 수 있는 skip_size에 상한선을 두게 된다면, 필요한 헤더의 개수가 늘어나게 되므로 공격 성공 확률을 줄일 수 있다. (ex. max_skip_size = 100)
skip_size 의 상한선이 length에 따라 달라지는 방식
1번에서 논한 바와 같이, 필요한 헤더 개수가 일정 이상이면 안전성이 올라간다. 따라서, 일정 개수 이상을 필수적으로 요구 하는 방식으로 공격 성공 확률을 줄일 수 있는데, 1번의 방식은 fix된 최대 skip_size가 있다. 만약 이 최대값 보다 적은 길이의 블록 개수를 proof하는 경우 헤더 한개로 증명 가능하다. 따라서 블록길이에 따라 가변적인 방식으로 skip_size 최대값을 정하여 헤더를 항상 일정 개수 이상 제공하도록 할 수 있다.(ex. max_skip_size = proof_length/3 or proof_length/log2(proof_length))
merkle로 구성된 hash 중에 랜덤으로 header 요구
cut-and-choose 와 같이 동작하는 방식으로, non-interactive 한 방식이 아닌 interactive 한 방식이다. merkle로 hash 만 저장되어있는 블록중 하나 이상을 verifier가 랜덤하게 선택하여 실제 블록 헤더를 요구하는 방식이다. Interactive 한 방식으로 prover가 proof를 만들때 fake block을 요구 받으면 공격이 매우 힘들다는 특징이 있다.

정리

SPV는 사이드체인에서 Two way peg를 이용하여 자산을 이동시키는 것과 밀접한 관련이 있다. 따라서 본 글에서는 Two way peg에서 사용되는 SPV proof를 설명하고, 이어지는 part3에서 소개할 Proof of Proof of Work의 Reference가 되는 HVHH의 기본 컨셉과 실제 비트코인 데이터를 이용한 실험 결과도 확인해보았다. 그리고 기존의 SPV proof의 단점을 개선한 Compact SPV에 대해 알아보았다. 이어지는 part 3에서는 NiPoPoW 논문을 중심으로 PoPoW와 NiPoPoW에 대해 자세히 알아보자.