김성준, Virtual Machine & Optimization Lab in Seoul Nat’l University
본 포스팅에서는 Li, Chenxin, et al. “A decentralized blockchain with high throughput and fast confirmation.” 2020 {USENIX} Annual Technical Conference ({USENIX}{ATC} 20). 2020.[1]을 다룬다.
들어가며
블록체인에 관심을 가진 사람들이라면 확장성(scalability)라는 단어를 심심치 않게 접해봤을 것이다. 확장성이란 사용자 수의 증대에 유연하게 대응할 수 있는 정도를 뜻하며, 블록체인에서는 자원(마이닝 노드, 코어 수) 증가에 따라 트랜잭션의 처리속도(TPS)가 증가하지 않는 문제를 말한다. 대표적인 퍼블릭 블록체인인 비트코인은 7 TPS, 이더리움은 15 TPS라는 낮은 확장성을 지닌다는 한계가 존재한다. 물론 이더리움 2.0에서 샤딩 등의 기법을 도입함으로써 확장성을 대폭 개선할 여지가 있지만, 최근에야 비콘체인 메인넷을 런칭하는 페이즈 0에 진입했으며, 샤드 체인에서 스마트 컨트랙트를 지원하는 페이즈 2에 도달하기까지 상당한 시일이 걸릴 것으로 예상된다.
본 논문에서 소개하는 새로운 합의 알고리즘인 Conflux는 3,480 TPS 및 1분 이내의 트랜잭션 확정 시간을 달성했다고 주장한다. 그렇다면 기존 비트코인 및 이더리움이 낮은 확장성을 지니는 원인이 무엇이며, 이들에서 사용되는 합의 알고리즘을 어떻게 수정하여 높은 확장성을 달성했는지 알아보자.
합의 알고리즘 (Consensus Algorithm)
합의 알고리즘은 다수의 참여자들이 통일된 의사결정을 하기 위해 사용하는 알고리즘으로, 퍼블릭 블록체인의 근간을 이루는 중요한 키워드다. 합의 알고리즘 덕분에, 네트워크에 참여하는 모든 참가자는 결과적으로 단 하나의 블록체인 상태만이 유효하다는 합의를 이끌어낼 수 있다.
비트코인에서는 나카모토 컨센서스(Nakamoto Consensus)라는 합의 알고리즘을 사용한다. 나카모토 컨센서스에서, 채굴자라 불리는 참여자들은 유효한 블록을 생성하기 위하여 작업증명이라는 일종의 수학적 퍼즐을 풀고자 노력한다. 이때 이전 트랜잭션을 번복하는 이중 지불 공격 등을 막기 위하여, 모든 참여자는 가장 긴 체인만을 메인 체인으로 인정하는 longest chain rule을 채택한다.
이러한 나카모토 컨센서스에서 블록 생성 주기가 짧을수록 블록체인의 분기, 즉 포크(fork)의 발생 빈도가 높아지는데, 이는 정직한 채굴자의 컴퓨팅 파워가 분산되어 결과적으로 전체 시스템의 보안성에 악영향을 미친다. 그 결과 나카모토 컨센서스에서는 의도적으로 블록이 천천히 생성되게끔 설계된다. 나카모토 컨센서스를 처음 도입한 비트코인은 블록 생성 간격이 10분으로 유지되게끔 난이도가 조절되며, 트랜잭션 확정에는 1시간이라는 긴 시간이 소요된다는 한계점이 있다.
비트코인과 달리, 이더리움에서는 블록 생성 주기가 15초로 상대적으로 짧은 블록 생성 주기를 가진다. 따라서 필연적으로 포크가 자주 발생할 수밖에 없는데, 이더리움에서는 이를 GHOST 프로토콜을 일부 채용함으로써 포크에 따른 보안성 문제를 해결한다. GHOST 알고리즘에서는 제네시스 블록부터 시작하여, 현재 블록의 자식 블록 중 가장 큰 서브트리 갖는 블록을 재귀적으로 선택함으로써 메인 체인을 결정한다. 예를 들어, 아래 그림에서 블록 X의 서브트리는 6개의 블록을 갖는 반면, 블록 Y의 서브트리는 5개의 블록만을 가지므로 블록 X를 선택하는 식으로 메인 체인을 확장해 나간다. 나카모토 컨센서스의 longest chain rule과는 달리 메인 체인에 포함되지 못한 고아 블록 또한 메인 체인 선택에 영향을 미치므로 정직한 참여자의 컴퓨팅 파워가 분산되지 않고, 블록체인 보안성에 기여할 수 있게끔 설계되었다.
반면 GHOST 프로토콜에 단점이 없는 것은 아니다. GHOST는 liveness attack에 취약하다는 문제점이 있다. 여기서 말하는 Liveness란 “합의 대상(Transaction 또는 블록체인에서 블록)에 문제가 없다면, 네트워크 내에서 반드시 합의가 이루어진다”는 의미이다.
위의 그림에서, 블록 X의 서브트리와 블록 Y의 서브트리가 비슷한 무게를 가진다고 가정해 보자. 블록체인에서는 네트워크 지연으로 인해 생성된 블록 정보가 모든 노드에게 동시에 전파되지 못한다. 따라서 한 그룹은 블록 X가 포함된 서브트리가 메인 체인에 포함된다고 여겨 채굴을 진행할 것이며, 다른 그룹은 블록 Y의 서브트리를 연장하게끔 채굴을 진행할 것이다. 이때 공격자는 네트워크에 공개하지 않은 X’ 및 Y’ 서브트리를 비밀리에 채굴한 뒤 이를 소유하고 있다가, 어느 순간 두 서브트리에 충분한 무게 차이가 생겨 하나로 수렴할 것 같으면 즉시 무게가 부족한 서브트리의 블록을 네트워크에 전파함으로써 두 그룹의 블록체인이 합의를 이루지 못하게끔 공격할 수 있다. 이러한 공격 기법을 liveness attack이라고 부른다.
이외에도 DAG 기반 구조, 계층적 및 평행 체인, 비잔틴 장애 허용, 샤딩 등의 합의 알고리즘이 설계되었으나, 본 포스트에서는 각 합의 알고리즘에 대한 설명은 생략하겠다.
Conflux 자료구조
본 논문에서의 Conflux 합의 알고리즘은 기존의 합의 알고리즘에서 사용되던 자료구조를 약간 변형하여 사용한다. 대표적으로 이더리움의 GHOST는 structured GHOST로, 비트코인 및 이더리움 블록체인의 트리 자료구조는 트리-그래프로 대체된다.
- structured GHOST
일반적인 GHOST에서는 모든 블록이 1만큼의 동일한 무게를 가진다는 전제 하에서 동작하는 반면, structured GHOST에서는 전체 블록의 1/h만이 h만큼의 무게를 가지는 weighted block으로 선택되며 다른 모든 블록의 무게는 0이 된다. 어떤 블록이 weighted block이 될 것인가는 작업증명 결과값에 따라 결정된다(e.g. 작업증명 해시값에서 leading zero의 개수). 이러한 설계 하에서, structured GHOST에서는 weighted block을 가장 많이 포함한 서브트리를 재귀적으로 선택함으로써 메인 체인이 정해진다.
무게가 부여된 블록을 채굴하는 것은 일반적인 블록 채굴 대비 더 높은 난이도를 요구하므로, 공격자는 liveness attack에 필요한 충분한 양의 weighted block을 채굴하기가 어려워진다. 이는 앞서 설명된 liveness attack을 완화시킬 수 있으나, 트랜잭션 확정을 위해 충분한 개수의 weighted block 생성을 기다려야 하기에 트랜잭션 확정 속도가 감소한다는 단점이 있다.
2. Tree-Graph
Conflux에서는 트리-그래프 자료구조를 채택한다. 아래 그림에서, 트리-그래프의 vertex는 블록에, edge는 부모 엣지(parent edge)와 참조 엣지(reference edge)에 각각 대응된다.
부모 엣지는 기존의 합의 알고리즘에서 사용되던 엣지와 동일하며, 각 블록은 자신의 부모 블록을 가리키는 엣지 하나만을 가질 수 있다. 참조 엣지는 자신보다 먼저 생성된 블록을 가리키는 엣지이며, 한 블록이 여러 개의 참조 엣지를 가질 수도 있다. 이렇게 정의된 부모 엣지 및 참조 엣지는 이후 블록 및 트랜잭션 오더링에 사용된다.
Conflux의 합의 알고리즘
Conflux 합의 알고리즘에서, 블록체인 네트워크가 공격받지 않는 일반적인 상황에서는 빠른 트랜잭션 확정을 위해 일반적인 GHOST 프로토콜을 따른다. 즉 모든 블록은 1이라는 동일한 무게를 지닌다. 이때 블록체인 네트워크에 liveness attack 등의 공격이 감지되면, 블록의 무게는 GHOST가 아닌 structured GHOST에 의한 adaptive weight로 변경된다. 이처럼 Conflux 합의 알고리즘은 상황에 따라 유연하게 동작함으로써 GHOST 및 structured GHOST의 장점 모두를 취할 수 있다.
블록 b가 adaptive weight를 가져야 하는지를 판별하기 위해, 제네시스 블록부터 블록 b에 이르기까지 거치는 체인상의 블록 a에 대하여 1) 블록 a가 형제 블록 대비 충분히 무거운 서브트리를 가지고 있지 않은가와 2) 블록 a가 부모 블록 대비 너무 오래되지는 않았는가를 판별한다. 만약 두 조건이 모두 충족된다면 모종의 공격(double spending attack, liveness attack 등)이 행해지고 있음을 의심할 수 있고, 블록 b는 adaptive weight를 부여받게끔 AdaptiveWeight(b) 함수가 설계되어 있다.
최적화
Conflux의 최적화 기법으로, 본 논문에서는 deferred execution과 link-cut tree를 제안한다.
- Deferred execution
기존의 일반적인 블록체인에서는 새 블록을 수신받을 때마다 블록에 담긴 모든 트랜잭션을 수행해본다. 이는 블록 생성 간격이 충분히 길어 블록 오더(block order)가 거의 바뀌지 않는다면 합리적인 방법이다. 하지만 빠른 블록 생성을 통한 높은 확장성을 원한다면, 앞서 설명한 포크 등의 문제로 블록 오더가 수시로 변할 수 있다. 이러한 상황에서는 블록 오더가 변할 때마다 현재 블록체인 상태를 재계산해야 한다는 비효율성을 가진다.
Conflux에서는 이를 해결하기 위해 deferred execution을 도입한다. 블록을 받을 때마다 트랜잭션을 수행해보는 것이 아닌, 특정 블록 개수만큼 지난 뒤에야 이전 블록의 트랜잭션을 순차적으로 실행해보는 것이다. 생성된 뒤 몇 블록이 경과한 블록의 경우에는 그 오더가 바뀔 확률이 매우 낮아지기 때문에, 한번 적용한 트랜잭션이 블록체인 상에서 영구히 유효할 확률을 효과적으로 높일 수 있다.
2. Link-cut Tree
새 블록을 추가할 때마다, 새로 생성된 블록부터 제네시스 블록까지 거슬러 올라가면서 모든 서브트리 무게를 조정하는 naive한 방법은 O(n)의 시간복잡도를 가지며, 블록체인 크기가 증가할수록 그 부담 또한 비례하여 증가할 수밖에 없다. 본 논문에서는 이러한 비효율성을 개선하기 위하여 link-cut tree 자료구조[2]를 도입하였다. Link-cut tree를 활용하면 기존의 O(n) 시간복잡도를 amortized O(logn)으로 감소시킬 수 있다.
평가
본 논문에서는 Conflux의 처리량, 트랜잭션 확정 속도, 확장성을 평가 지표로 삼아 실험을 진행하였다. 그 밖에도 liveness attack이 가해지고 있을 때의 adaptive weight 메커니즘이 원활히 동작하는가를 평가하였으며, 트랜잭션 실행에 있어 최적의 deferred execution을 위한 파라미터를 얻고자 하였다. 시뮬레이션은 800개의 아마존 EC2 m5.2xlarge 가상 머신을 20군데의 도시에서 나눠 사용하였으며, 각 가상머신은 8개의 코어와 1Gbps의 네트워크 처리량, 20Mbps 네트워크 대역폭 제한을 지닌다. 컴퓨팅 자원의 한계로, 각각의 가상 머신이 최대 15개의 풀 노드를 구동하는 환경 하에서 시뮬레이션을 진행하였다고 한다.
아래 그림은 네트워크 지연을 고려했을 때의 Conflux 및 GHOST 프로토콜에서의 트랜잭션 확정에 걸리는 시간을 나타낸 것이다. Conflux에서는 deferred execution 기법을 시용하기 때문에 GHOST 대비 트랜잭션 확정에 약간의 시간이 더 소요됨을 확인할 수 있으나, 극적인 속도 차이는 발생하지 않음을 확인할 수 있다.
그 밖에도, Conflux에서는 최대 9.6Mbps의 트랜잭션 처리량을 얻을 수 있었다고 한다. 이는 동일한 환경 세팅에서의 알고랜드와 비교했을 때 4배 이상의 트랜잭션 처리량이지만, 트랜잭션 확정 속도에는 큰 차이가 없었다고 한다. Conflux와 OHIE와 비교했을 경우, 서로 유사한 트랜잭션 처리량을 가지나 Conflux가 상대적으로 10배 이상 빠른 트랜잭션 확정 속도를 달성했다고 한다.
결론
이번 포스팅에서 다룬 논문에서는 확장 가능하며 중앙 주체 없이 탈중앙화된 블록체인 플랫폼 Conflux를 소개하였다. Conflux는 블록체인에 가해질 수 있는 공격들을 합의 프로토콜 단에서 감지 및 차단할 수 있으며, 기존 퍼블릭 블록체인 대비 빠른 블록 생성 속도를 보여준다.
Conflux network가 중국 정부가 공식 승인 및 지원하는 유일한 퍼블릭 블록체인 프로젝트이며, 한국 아이콘 재단(ICON Foundation)과의 크로스체인 프로토콜 관련 전략적 파트너십을 발표[3]하는 등 어느 정도 입지도 다져나가고 있는 프로젝트로 보인다. 본 포스팅을 읽고 흥미가 생겼다면 Conflux 백서 및 깃헙에 공개된 Rust 기반 구현체를 살펴보는 것도 좋을 것이다.
글을 다 썼을 무렵 Conflux Chain.Kor에서 작성한 미디엄 글을 찾을 수 있었는데, Conflux의 동작 방식을 좀 더 깊게 알아보고 싶다면 도움이 될 것이다.
