미디엄에 재발행 하였습니다.
블록체인의 확장성을 이야기할 때 빠지지 않는 것이 속도에 대한 것이다.
블록체인의 TPS가 빠르다고 반드시 좋은 것만은 아니지만 그럼에도 블록전파속도에 개선이 필요한 이유는 무엇일까?
이번 글에서는 블록체인에서 블록의 전달속도가 미치는 영향과 전파기술 발전의 중요성에 관해 이야기하고,
블록전파시간 개선을 위해 제안된 방법들을 전반적으로 살펴보고자한다.
블록체인의 동기화
먼저 블록체인이 만들어지는 과정을 간단히 살펴보자. 노드에 의해 새로 발견된 블록은 P2P 방식으로 전체 노드에 전달되며 점차 네트워크 전체로 확산된다. 각 노드는 전달된 최신 블록의 유효성을 검증하고 자신의 체인에 포함시킨다. 채굴 보상을 받기 위해서는 채굴자가 생성한 블록이 네트워크 전체가 인정하는 캐노니컬(canonical)체인에 포함되어야 하므로 이것이 네트워크 전체에 자신이 가진 블록을 전파하게 하는 요인이된다.
이때 캐노니컬체인에 포함되지 못한 블록을 스테일블록(Stale Block, 고아블록)이라 한다. 스테일블록이 생성되는 원인은 기존의 캐노니컬체인에서 서로 다른 블록이 동시에 생성되었을 때 한 블록을 선택해 이어나가야하기 때문이다.
노드 간 블록체인의 동기화는 블록체인의 신뢰와 보안을 위해 매우 중요하다. 노드가 가진 체인이 캐노니컬체인과 동일하지 않아 분기가 발생하면 스테일블록의 비율이 높아지는데, 비트코인에서는 스테일블록에 대한 채굴 보상을 받지 못하므로 많은 분기가 일어날수록 해시파워를 낭비한것이 된다. 해시파워를 낭비한만큼 블록생성속도가 느려지므로 이를 일정하게 유지하기 위해 채굴 난이도가 낮아진다는점에서 네트워크의 보안에 영향을 미친다. 채굴 난이도가 낮을 때는 블록생성시간이 짧아져 여러 노드에서 비슷한 시기에 블록을 생성할 확률이 높고 이 중 네트워크에 더 빨리 전파되는 블록이 캐노니컬체인에 포함되기에 유리하다.
따라서 블록전파(Block Propagation)시간은 블록체인의 동기화에 영향을준다. 블록의 전파시간이 오래걸린다면 동시에 여러개의 블록이 전파되고 있을 확률이 높아지므로 마찬가지로 스테일블록의 비율이 높아질 가능성이 크다. 더불어, 트랜잭션 전파 속도가 늦어지고 더블스펜딩 어택의 성공 가능성이 높아지기 때문에 위험하기도하다.
덧붙이자면, 비트코인의 경우 가장 긴 체인을 캐노니컬 체인으로 선택하기때문에 많은 채굴노드가 참여하는 체인일수록 빠른 채굴로 캐노니컬 체인이 될 확률이 높다.
따라서, 채굴풀 하나가 대부분의 해시율을 차지하게된다면 블록의 생성과 포함여부를 좌지우지할수있게 된다. 즉, 블록체인에서 분권화(Decentralization, 탈중앙화)와 검열저항성이란 의미가 사라진다.
이러한 이유때문에 블록생성시간이 비트코인보다 짧은 이더리움은 채굴자들의 참여를 독려하기위해서 수정된 고스트 프로토콜을 적용하여 엉클블록 채굴자에게도 채굴 보상을 준다.
이렇게 블록생성속도와 전파시간, 스테일블록의 비율, 난이도와 탈중앙성은 서로에 영향을 미친다.
블록전파기술 연구가 필요한 이유는
앞서 이야기한 것 처럼 블록체인을 안전하게 유지시키기위해 블록과 트랜잭션을 빠르게 전달하는것이 중요하다는 점을 첫째로 들 수 있다. 실제로 비트코인에서는 스테일블록 비율이 낮은 풀로 대거 이동하는 일이 있었으며, BIP66을 통해 네트워크 해시율의 대다수가 채굴시 검증을 하지않는다는 것을 알게되었다. 블록체인이 유지되기 위해서는 참여자들이 시스템을 파괴하지않고 암묵적인 룰을 잘 지키며 이용할 수 있도록 블록의 전파속도를 개선해야 한다.
블록이 생성되고 확인(confirm)되는 시간은 줄이기 어렵다. 충분한 유효성 검증 과정을 거쳐야하기 때문이다. 그러나 블록 전파시간의 개선에는 가능성이 있다. 블록전파시 지연이 일어나는 원인은 노드간 프로토콜 라운드트립과 TCP 자체의 라운드트립 외에도 블록템플릿 생성시간, 유효성 검증 시간, 채굴자와 채굴풀간의 통신 대기시간 등으로 다양하다. 따라서 여러 방향으로 접근해볼수 있고 블록체인의 유효성을 파괴하지않는 개선 방안을 고민해볼 수 있을것이다.
이외에도, 전파기술의 개선을 통해 데이터 전달시의 대역폭을 줄이거나 다양한 통신 방법과 네트워크를 사용자가 선택할 수 있도록 하는 등의 이점을 얻을 수 있다.
블록전파시 지연 개선방안
블록전파기술의 발전과정을 살펴보기위해, 비트코인 코어 개발자인 Gmaxwell의 Advances in block propagation(2017) 발표자료와 각 솔루션의 논문 및 공식 사이트를 참고 하였다.
먼저 가장 잘 알려진 Relay Network와 Compact Blocks에 대해 알아보도록 하자.
Relay Network
블록전파속도를 개선하기위해 최초로 널리 보급된 프로토콜은 비트코인 개발자인 Matt Corallo가 개발한 fast block relay network였다. 전 세계에 분산된 9개의 허브중 가까운 곳에 연결하여 연결된 다른 노드간 트랜잭션, 블록을 송수신하여 P2P방식보다 대기시간을 감소시킬 수 있었다.
또 다른 릴레이 네트워크인 Falcon은 컷 스루(cut-through) 라우팅을 적용하여 블록을 여러 패킷으로 나누어 전송한다. 패킷이 전송 될 때마다 다른 노드에게 바로 스트리밍 하며, 나머지 패킷이 도착할 때까지 계속해서 블록을 재구성한다. 때문에 처음에는 헤더만 검사 하고, 모든 데이터를 받은 후에야 유효성을 검사할수 있지만 전파 시간을 줄일수 있다는 장점이있다. 노드는 총 10개이며, IC3에서 관리한다.
초기의 릴레이 네트워크를 초석으로하여 개발한 FIBRE(Fast Internet Bitcoin Relay Engine)는 컷 스루 라우팅과 함께 사용하던 TCP 대신 UDP와 순방향 오류정정 기법(FEC, Forward Error Correction)을 사용하였다. TCP는 손실된 패킷을 재전송하므로 안정적이지만 추가적인 라운드트립이 발생한다. 따라서 지연시간을 줄이기 위해 좀 더 빠른 UDP를 사용하였고 손실된 패킷을 복구하기위해 FEC를 함께 전송하게 했다. 이렇게 하면 데이터 일부가 손실된 경우에도 재구성이 가능하다.
현재 비트코인에서 사용되는 Compact Blocks 릴레이 방식이 FIBRE와 함께 설계되었기 때문에 cmpctblock 메시지의 형식이 UDP-FEC 기반 릴레이 구조에 맞도록 설계되었는데, 메모리 풀에서 누락된 트랜잭션을 라운드트립을 통해 요청하는 대신 FEC를 함께 전송하는 방법으로 복구한다. 블록데이터의 8배를 보내게되지만, UDP전송을 사용하여 지연정도가 크지 않았다. 컴팩트 블록에 대해선 잠시후 추가적으로 설명할 것이다.
일반적으로 FIBRE와 Falcon을 통틀어 릴레이 네트워크라고 부른다. 최근 연구된 릴레이 네트워크를 좀 더 살펴보자면, bloXroute는 릴레이 네트워크의 단점으로 여겨지는 중앙화로 인한 검열가능성 문제를 방지하기위해 블록을 암호화하여 내용을 기반으로한 선택적인 검열을 불가능하게 하였다. 블록의 내용은 전파가 이뤄진 후에 표시된다. 비트코인 캐시에서의 테스트를 완료하였고 현재(2019년 8월) 이더리움에서의 테스트를 준비 중이다.
한편, 릴레이 네트워크에서 보안성을 개선하기위한 연구도 있다. SABRE는 라우팅 공격중 하나인 BGP(Border Gateway Protocol) 하이재킹으로부터 비트코인을 보호하기 위해 제안된 릴레이 네트워크이다. 인터넷을 기반으로하는 비트코인을 비롯한 블록체인에는 BGP의 취약점으로 인한 위험성이 존재한다. 간단히 말하자면, 공격자가 IP 접두사를 가로채 트래픽을 차단함으로써 두 노드간의 모든 연결을 끊으면 블록체인을 병렬로 분할시킬수있다. 분할은 두개의 체인이 생기는 분기(fork)로 이어진다.
이를 네트워크 파티셔닝 문제라하는데, 이를 해결하기위해 SABRE는 노드를 다양하게 배치하여 공격자가 네트워크를 혼란시키기 어렵도록 만든다. FIBRE, Falcon과 비교하여 실험한결과 이전의 릴레이 네트워크들은 공격에 훨씬 취약하다. 이미 비트코인 노드들이 긴밀하게연결되어 있으므로 대규모 라우팅공격에 대응하기엔 부족하다는 의견도 있지만 위험성이 크므로 인터넷 기술의 발전과 함께 앞으로 계속되어야하는 연구임은 분명하다.
앞서 블록체인에서의 전파 시간지연을 줄이기 위한 솔루션 중 릴레이 네트워크의 종류와 특징에 대해 간단히 알아보았다. 현재로서는 비트코인의경우 릴레이 네트워크가 통신 방식의 다양성에 기여하며, 블록전파시간을 개선하는 효과가 가장 크다. 그러나 릴레이서버에서 마음만 먹으면 블록을 선택적으로 전송할 검열가능성이 있기 때문에 중립성을 유지할수 없다는 단점이 있으므로 릴레이 네트워크에 의존하기보다는 P2P를 사용하면서 블록 전파 시간을 줄일수 있는 방법을 연구하는것이 블록체인의 신뢰성과 사용가치를 높이기 위해서 더욱 중요할 것이다.
Compact Blocks Relay
FIBRE와 함께 설계된 컴팩트 블록 릴레이는 현재도 비트코인 노드의 대부분이 사용하는 블록 전달 방식이다.
아래 다이어그램은 초기 비트코인 블록 프로토콜과 현재 사용되고 있는 컴팩트 블록의 전파 방식을 나타낸 것이다.
그림에서 알 수 있듯이, 초기의 비트코인 프로토콜(A)은 단순했지만 데이터 전송에는 비효율적이었다. 새로운 블록을 가지고 있다는 INV 메시지를 보내면, 블록 전송을 요구하는 getdata 응답을 받은 후에 블록을 전송했다. 이는 불필요한 과정으로, 프로토콜상에서 1.5 RTT(Round Trip Time)을 갖게된다. 뿐만아니라, 트랜잭션은 전체 네트워크에 먼저 전파되어 각 노드의 메모리 풀에 저장되는데, 트랜잭션이 포함된 블록을 전파하여 이미 보유한 데이터를 중복해서 전파하면서 대역폭을 낭비하는 비효율적인 방법이었다. 따라서 컴팩트 블록은 필요없는 과정을 줄이고 트랜잭션을 중복 전송 하지 않게 하는것이 목적이었다.
컴팩트 블록은 짧은 트랜잭션 ID를 포함하는데 충돌을 막기위해 salt를 사용한 6바이트의 ID를 사용한다. 또한, 수신노드에게 없을거라 예상되는 트랜잭션을 함께 전송하는데, 송신자는 수신자의 트랜잭션풀을 확인하지 않았고, 자신이 몰랐던 트랜잭션이면 피어들도 모르는 트랜잭션일 것이라고 추론한 휴리스틱한 방법임에도 효과가 좋았다. 이를 수신한 노드는 받은 정보와 트랜잭션풀을 비교하여 블록을 재 구성하고, 누락된 트랜잭션을 요청할 수 있다.
컴팩트 블록은 대역폭에 따라 두가지 모드를 제공하는데, 피어의 sendcmpct 메시지에 따라 모드가 결정된다.
고대역폭 모드에서는 이전에 sendcmpct 메시지를 받았으면 해당 피어에게 허가를 먼저 요청하지 않고도 블록이 준비된 후 바로 전송할 수 있게하여, 유효성검증이 끝나기전에 블록 전송을 함께 시작한다. 위의 다이어그램에서 각 회색 막대는 블록의 유효성검증 기간을 의미하는데, 각 A, B, C에서 막대의 위치를 보면 쉽게 이해할 수 있을것이다. 동시에 여러 노드에게 블록을 전송하므로 이름처럼 대역폭 인바운드가 충분한 노드를 위한 모드이다. 비트코인에서는 동시에 최대 3명까지 가능하도록 권장하고 있다.
반면, 저대역폭 모드에서는 블록을 요청하는 sendcmpct이후 유효성 검증을 먼저 진행하기 때문에 블록 전송 전까지 대기시간이 여전히 존재하지만, 여러 피어가 동시에 블록을 전송하면 대역폭이 낭비되는 경우를 막기위해 INV 메시지로 블록을 전송해도 되는지 한번 더 확인한다.
앞서 말했듯 블록 전파 지연에는 다양한 원인이 존재한다. 그 중 노드가 사용하는 전체 대역폭의 12%를 블록 전파가 차지했고, 트랜잭션 전파에도 10%이상을 사용했다. 따라서 컴팩트 블록을 이용하는것이 대역폭을 크게 개선하는것은 아닐수 있다.
또한, 기존 프로토콜에서 일정하게 1.5 RTT가 걸리던것을 컴팩트 블록을 이용하면 고대역폭 모드에서는 0.5 ~ 1.5 RTT, 저대역폭 모드에서는 1.5 ~ 2.5 RTT까지 걸릴수 있으므로 전파 속도가 반드시 개선된다고 보기 어렵고, TCP전송을 사용하거나 패킷 손실이 발생할 경우 추가적인 지연이 발생할 것이다. 효과를 극대화 하기 위해서는 앞서 보았던 FIBRE에서 UDP와 오류정정기법을함께 사용해야한다.
하지만 컴팩트 블록은 비트코인에서 채택되어 현재도 대부분의 노드에서 사용하는 릴레이 프로토콜이 되었다.
컴팩트 블록 이후에도 트랜잭션을 중복 전송하지 않기위해 다양한 방법이 시도되었는데, set reconciliation이나 데이터 압축 등의 방법이 사용되었다.
이제 Set reconciliation을 통해 전파 문제를 해결하고자 한 연구의 원리를 살펴볼 것이다.
Set reconciliation
set reconciliation이란 서로 다른 두개이상의 집합(set)이 있을때 그 차이를 비교하거나 둘을 일치시키는 것을 의미한다. 필터링과 동기화라고 생각하면 더 쉬운데, 두 집합의 요소를 비교해 필터링하거나 동기화할 때 얼마나 효율적으로 하는지가 중요하다.
앞서 릴레이 네트워크와 컴팩트블록을 소개했지만 블록전파 개선을 위해 가장 먼저 연구되었던 것은 2013년 블룸필터를 통한 reconciliation이었다. SPV노드를 위해 BIP37에서 블룸필터가 구현되었는데, 이를 이용해 이미 알려진 트랜잭션을 필터링한 후 전송하는 방법을 실험했지만 이 방법은 필터링으로인한 오버헤드가 더 크다는것이 밝혀졌다.
이후 컴팩트 블록과 비슷한 시기에 연구된 Xthin Blocks(Xtreme Thin Blocks)도 블룸필터를 사용하고자 했는데 비효율적이며 성능이 컴팩트 블록보다 좋지 않았다.
그러나 비트코인 코어와 비트코인 캐시에서 블룸필터 같은 확률적 자료구조를 이용하려는 연구가 최근까지도 꾸준히 진행되어왔다. 그중 대표적인것은 비트코인 언리미티드가 개발한 Graphene이다. (같은 이름의 블록체인 엔진과 다른것이니 혼동하지 말자.) 버전1은 이미 비트코인 캐시에 적용되었고, 성능 개선을 위해 버전2를 연구중이다.
Graphene에 대해 알아보기 전에 불름필터, 그리고 IBLT라는 자료구조에 대한 이해가 먼저 필요하다.
Bloom Filter와 IBLT
Bloom Filter
블룸필터는 대표적인 확률적 자료구조 중 하나이다. 특징을 정리하자면 다음과 같다.
- membership query시 사용
- 어떤 원소가 특정 집합에 포함되어있는지 확인할 때 사용
- 검색 시간과 메모리 절약.
- 길이가 x인 bit 배열과 k개의 hash함수를 이용, 삽입할 원소n개 에 대한 hash의 결과를 배열의 인덱스로 함
- 배열의 원소 삭제 불가. 삽입만 가능
- false positive 특성을 가짐
false positive는 한국어로 해석하면 부정오류 또는 거짓 긍정으로 해석되는데, 말 그대로 거짓을 사실인 것 처럼 보여준다는 이야기다. 따라서 어떤 집합을 이용해서 만든 블룸필터에 멤버쉽쿼리를 진행하면 실제로는 집합에 포함되지 않는 원소지만 포함하고있다고 거짓증언을 할 수 있다는 뜻이다.
그래서 거짓긍정률(이하 FPR, False Positive Rate)을 높게하는것이 좋긴하지만, 블룸필터에서 FPR은 블룸필터의 길이와 해시함수의 수, 삽입할 원소의 수에 영향을 미친다.
아래는 FPR과, 최적의 해시함수 개수를 구하는 식이다.
위의 식에 따르면 FPR은 크기가 크고(x), 사용된 해시 함수의 수(k)가 많을수록, 삽입할 원소의 수(n)가 작을수록 낮아진다.
하지만, 해시함수의 수를 늘리면 cpu 사용량이 증가하고, 크기가 클수록 메모리 사용량이 증가하므로, 위의 식에따라 에러율(FPR)과 k, x, n 을 조절하여 적절한 값을 유지해야하며, False Positive 확률(FPR)을 줄이기 위해서는 블룸필터의 크기를 키워야하지만 일반적으로 데이터량을 줄이기 위해 블룸필터를 사용한다는 점을 고려해야한다.
위의 식을 정리해서 최적의 블룸필터 크기를 구하면
bits이다.
IBLTs(Invertible Bloom Lookup Tables)
IBLT는 블룸필터와 유사한 방법으로 해시함수를 이용하여 데이터를 삽입하지만 각 셀에 bit값 대신 count와 key-value가 입력된다. 블룸필터와 달리 데이터의 삭제가 가능하고, 두 IBLT간 Subtraction(차 연산)이 가능하다. 차 연산의 결과는 서로 다른 두 집합의 차이인 대칭차(symmetric difference)를 구할때 유용하며, 따라서 set reconciliation에 이용가능하다.
또한, 멤버십 쿼리를 위한 Get과 Listing 함수가 존재하는데, 차 연산 후 대칭차를 구하기 위해 사용할 수 있다. 기억해야할것은, IBLT의 크기는 차 연산 후 예상되는 대칭차의 크기가 클수록 크다.
교집합이 존재하는 집합A, B가 있을 때 집합 A로 IBLT I, 집합 B로 IBLT I'를 생성한후 차연산을 하면 또다른 IBLT가 만들어지고, 해당 IBLT에는 A-B, B-A 의 원소가 함께 존재한다.
이때, Listing, Get 함수를 이용해 새 IBLT에서 A-B 혹은 B-A의 원소를 구할 수 있다.
IBLT의 자세한 연산 방법은 아래에서 설명한다.
IBLT 생성
해시함수 h1, h2를 이용해 A = {x,y,z} 에대한 IBLT를 생성한다면
연산 시작 전에 각 테이블의 값을 모두 0으로 초기화 한 후, 아래의 삽입(Insert) 연산을 이용하여 각 원소를 차례대로 삽입한다.
즉, 각 key의 인덱스는 해시함수 h1와 h2와의 결과값이다.
각 열을 로 나타낼수 있는데, 편의상 T의 인덱스는 1부터 시작한다고 가정하겠다.
는 XOR 연산을 의미한다. 각 keysum과 hashsum에 대해 key와 H(key)를 xor 연산하고, count를 1씩 추가 한다고 생각하면 된다.
차 연산(I''=I-I' 혹은 I''=II')
IBLT끼리의 차 연산 방법은 간단하다. 집합 A,B로부터 만들어진 I, I'라는 두 IBLT가 있을때 count는 I에서 I'의 각 값의 차를 구하고, keysum과 hashsum은 각 자리의 수 끼리 XOR 연산을 하면 된다.
결과인 I''역시 IBLT이며, 우리가 목표로 하는 영역과 같은 왼쪽 그림에서 색칠 된 영역의 원소(I-I') 뿐만 아니라 I'-I 역시 포함한 I와 I'의 대칭차(symmetric difference)인 (I-I')U(I'-I), 즉 (A/B)U(B/A)의 원소를 함께 나타내고 있다.
I와 I'의 대칭차는 Sub연산 후 Listing과정을통해 구할 수 있다.
리스팅(Listing)
IBLT는 Listing 과정을 통해 IBLT가 가진 원소들을 나열할 수 있다. 따라서 위에서 차연산을 통해 얻은 (I-I')U(I'-I)의 원소를 구할수 있다.
위의 알고리즘을 간단히 설명하자면,
count = 1 or -1이면 hashsum == H(keysum)임을 확인한 후, 해당 버킷을 별도의 queue에 저장한다.
(hashsum과 keysum의 해시값이 같은지를 확인하는 이유는 한 버킷에 원소(key)하나만 존재한다는것을 확인하기 위해서이다.)
queue에 저장된 데이터를 차례대로 Pop하여, 해당 key가 있는 모든 버킷에서 XOR연산을 수행한다. 이때 count = -1이면 (I'-I)에 속한 원소이고, count = 1이면 (I-I')에 속한 원소이다.
이제 하나의 상황을 가정해서, 블룸필터와 IBLT를 이용한 reconciliation을 한다고 생각해보자.
Assumptions
- Alice는 자신이 발견한 새로운 블록을 Bob에게 전달하려 한다.
- Bob의 pool에는 이미 많은 트랜잭션들이 있고, Alice가 보내려는 블록이 포함한 트랜잭션들도 대부분 보유하고 있을 것이다.
- 따라서 Alice는 Bob에게 없는 트랜잭션만 알아낸후 보내려한다.
practice 1. xthin blocks (블룸필터 이용)
- Alice가 블록을 갖고있다는 사실을 알리면
- Bob은 자신의 pool에 있는 트랜잭션을 이용한 Bloom filter를 생성하여, getdata요청과 함께 전송한다.
- Alice는 블록의 header와 트랜잭션id 리스트를 전송한다.
이 경우 Compact Blocks 보다도 더 많은 데이터를 전송하게 된다. 컴팩트 블록은 6bytes의 트랜잭션 ID를 사용하므로, 낮은대역폭 모드일경우 n개의 트랜잭션을 전송할때 6n bytes이지만, xThin 블록은 Bob이 가진 트랜잭션으로 블룸필터를 만들어 Alice에게 전송하기 때문에 의 비용이 추가로 더 든다. 여기서 m은 Bob이 가진 트랜잭션량 이다.
Bob이 가진 트랜잭션(m)에 비례하며, 대부분의 트랜잭션을 Bob이 이미 갖고있는 상황이기 때문에, 누락된 트랜잭션이없는 경우엔 대역폭을 쓸데없이 낭비한 상황이 된다.
practice 2. Alice가 블룸필터를 생성하는 경우
xThin에서는 Bob이 자신의 트랜잭션을 가지고 블룸필터를 생성했다면, Alice가 보내려는 블록의 트랜잭션의 수(n)가 훨씬 적을것이므로, Alice가 블룸필터를 생성해서 보내는 방법이 더 효율적일것이라 예상할수 있다
- Alice가 블록을 갖고있다는 사실을 알리면
- Bob이 자신이 가진 트랜잭션(m)을 Alice에게 알려주면서 getdata요청한다.
- Alice는 블록의 모든 트랜잭션(n)으로 블룸필터를 생성하고, 블록 header와 함께 전송한다.
- Bob은 받은 블룸필터로 pool에서 필요한 트랜잭션들을 찾아낸다.
FPR = 1/(m-n)이면 pool에 있는 m만큼의 트랜잭션 중 블록에 포함되는 n을 뺀 나머지, 즉 유효하지 않은 트랜잭션들 중 1개가 false positive된다는 의미이므로, 한 블록당 한 트랜잭션꼴로 잘못 포함하게 되어 Bob은 매번 블록 생성에 실패하게된다.
에러율을 좀더 낮추어 FPR = 1/144(m-n)이라 한다면, 144개블록당 한번씩 블록에 유효하지않은 트랜잭션이 포함될수 있다. 비트코인에서 하루에 약 144개 블록이 생성되므로 하루에 한번씩 유효하지않은 블록이 생성될수 있다는 의미다.
블록에 포함된 트랜잭션이 n이므로 이 방법에서 생성되는 블룸필터의 크기는 이고, 이 때 컴팩트 블록(6n bytes)보다 적은 비용을 사용하려면 m < 71982340 - n, 즉 pool의 크기가 71,982,340 bytes 보다도 더 커야하는데, 최근 1년 기준으로 메모리풀(m)의 최대크기가 약 50,000,000bytes 이다. 따라서 컴팩트 블록보다 적은 비용이 들 것이라 예상할 수 있다.
하지만 m의 크기가 클수록 전송할 데이터량이 증가한다. 블룸필터의 false positive rate를 줄여야하는데, 개선 가능할지라도 여전히 Bob의 pool 크기(m)가 오류율과 블룸필터의 크기에 영향을 미친다
practice 3. IBLT를 이용하는 경우
- Alice가 블록을 갖고있다는 사실을 알리면
- Bob은 getdata메시지를 보낸다.
- Alice는 모든 트랜잭션id로 IBLT를 생성해 블록 header와 함께 전송한다.
- Bob은 자신의 pool에 있던 트랜잭션으로 IBLT를 생성하여, 받은 IBLT와 함께 대칭차를구한다. (sub 연산후 리스팅) (두 IBLT의 차이는 15%이상일 수 없다. 그렇지 않으면 IBLT를 더 크게 만들어야한다.)
IBLT의 크기는 두 집합의 크기와 관계없으며, 차연산 후 복구할수 있다고 예상되는 차이, 즉, 대칭 차가 클수록 크기가 증가하므로, pool이 작을때는 대칭차가 비교적 작아(파란선, 노란선) 효과가 좋지만 pool의 크기가 커지면 대칭차가 더 크기때문에(초록색 선) Compact Blocks(빨간 선) 보다도 전송할 데이터의 양이 매우 많아진다.
practice 4. Graphene (블룸필터와 IBLT를 함께 사용)
practice 1~3까지 블룸필터나 IBLT를 단독으로 사용하여 reconciliation했을 때의 문제점을 정리해 보자면,
- 블룸필터를 사용할 때, Bob의 pool사이즈가 블룸필터의 크기와 FPR에 영향을 미친다.
- IBLT를 사용하면, 블록과 pool의 대칭차가 클수록 IBLT의 크기가 매우 커진다.
이는 두 자료구조의 특성 때문인데, Graphene에서는 이 문제를 해결하기 위해 두가지를 모두 사용했다. 해결 아이디어는 이렇다.
Alice가 Bob에게 블록의 트랜잭션으로 블룸필터와 IBLT 각각을 만들어 전송한다. 둘 중 어느것을 먼저 이용해야할까? IBLT는 대칭차가 클수록 크기가 커지므로, 먼저 블룸필터로 블록과 pool간의 대칭차를 줄인다. 이 때, false positive가 일어나더라도 처음에 받은 IBLT로 오류를 복구할수 있기때문에, 블룸필터의 크기를 줄이고 FPR을 높이기로 한다.
A={x,y,z}, B={y,z,a}
- Alice가 블록을 갖고있다는 사실을 알리면
- Bob은 getdata메시지를 보낸다.
- Alice는 모든 트랜잭션id로 IBLT(I=IBLT(A))와 블룸필터(S=BF(A))를 생성해 블록 header와 함께 전송한다.
- Bob은 Alice에게서 받은 블룸필터(S)로 pool에서 일치하는 트랜잭션을 모두 찾은후에(m'={y,z,a}, {a}는 false positive) IBLT를 생성(I'=IBLT('m))한다.
- Alice에게서 받았던 IBLT(I)와 자신이 생성한 IBLT(I')로 차연산(I을 한후 Bob에게 없는 트랜잭션을 구한다.(I-I')
위의 과정을 실제로 계산해보면, 블룸필터의 false positive로 인해 m'에 잘못 포함된 원소 a가 있었지만, IBLT로 차연산한 후에는 바른 결과(A-B={x})가 나오는 것을 알수있다. (참고: Bloom Filter + IBLT 연산 해보기 )
Graphene에서는 두가지 프로토콜에 대해 실험했는데, 첫번째 프로토콜은, 블록의 모든 트랜잭션과 다른 트랜잭션들을 pool에 가지고 있는경우이고, 두번째는, pool에 블록의 트랜잭션중 일부분만 갖고있는 경우이다.
왼쪽의 그래프는 프로토콜1에 대해 블록에 포함되지않은 pool의 트랜잭션 양에 따라 전송해야할 데이터의 크기를 컴팩트 블록과 함께 비교한것으로, 블록과 관련없는 pool의 트랜잭션이 많아져도 컴팩트 블록에 비해 전송해야할 데이터 크기가 작고, 증가율이 높아져도 전송할 데이터 크기는 크게 증가하지 않는다.
오른쪽의 그래프는 프로토콜2에 대해 블록의 트랜잭션을 pool에 얼마나 포함하고 있는지에 따라 비교한것으로, 왼쪽의 숫자 200, 2000, 10000는 블록의 크기를 의미하고 위의 점선은 컴팩트 블록의 수치를 나타낸것이다
한계점
위의 그래프를 보면 전송할 데이터의 크기를 줄임으로써 대역폭을 줄이는 효과는 있겠지만, 트랜잭션을 디코딩하는 과정, 즉 Bob이 받아야할 트랜잭션을 복구하는 과정에서 실패할 확률이 존재한다. 메모리 풀에 블록의 트랜잭션을 모두 갖고 있다면 첫번째 프로토콜이 올바르게 작동할 확률이 높다. 그러나 더 일반적인 경우, 네트워크 문제, 느린 블록전파 시간 등의 이유로 메모리풀에 모든 트랜잭션을 보유하고 있지 않게 되면, 이 경우 디코딩에 실패할 확률이 매우 높다. 첫번째 프로토콜에서 실험했을때, 트랜잭션의 99퍼센트를 보유하고 있음에도 97%만 디코딩에 성공하였으므로, 이후 누락된 트랜잭션을 다시 요청하는 두번째 프로토콜을 실행해야한다. 3개월전의 graphene 버전2 중간 보고서에 따르면, 복구 실패율이 평균 하루에 한 블록 미만으로 낮아졌다고 한다.
또 한가지 문제점은, Graphene을 적용하기 위해서는 Alice가 트랜잭션 순서를 결정해야한다. Alice가 트랜잭션id로 블룸필터와 IBLT를 생성하기 때문인데, 생성 전에 자체적으로 트랜잭션 정렬에 추가적인 비용이 든다. 이를 피하기 위해서는 프로토콜 자체에 트랜잭션 순서를 정해야하는데, 이 때문에 비트코인 캐시(Unlimited와 ABC)에는 2018년 가을에 CTOR(Canonical Transaction Ordering Rule)을 적용하였다. 트랜잭션 순서가 정해지는것에 대해 여러 장단점이 있는데, 다음번에 다룰 예정이다.
지금까지 블록 전파 개선을 위해 set reconciliation과 그 중 블룸필터와 IBLT를 이용한 graphene대해 알아 보았다. 컴팩트 블록처럼 속도개선보다는 대역폭을 줄이는데에 효과가 있었고, 블록 크기가 클수록 전송할 데이터 크기 감소율이 크다는 장점이 있지만, 대신 추가적인 라운드 트립과 디코딩 실패확률이 비교적 높다는것이 단점이다. 또한 만약 실패한 경우 재요청을 해야하는데, one-round trip만에 가능하지만, 오히려 시간이 지연될것이다. reconciliation를 위해 블룸필터와 IBLT외에도 다른 선택지가 있지만, graphene은 두 가지 자료구조를 사용해 개선하려한 점이 의미있었고 계속 개발중인 프로토콜이기에 얼마나 더 개선될지가 기대된다.
최근에 비트코인을 위해 Erlay라는 새로운 트랜잭션 전파 방법이 제안되었는데, reconciliation을 위해 BlockStream에서 개발한 minisketch라는 자료구조를 이용했으며, 기존의 트랜잭션 전파 방법을 개선했다고 한다. 다음엔 sketch라는 자료구조와 Erlay에 대해 알아보도록 하겠다.
참고할만한 추가 리소스