블록체인의 확장성(Scaling Blockchains) — 1

이번 연재물은 Stanford University의 David Tse 교수님께서 2020년 봄학기에 강의하신 수업 EE374 Scaling Blockchains의 내용을 요약하여 소개합니다. 더 자세한 내용을 원하시면 수업 웹사이트를 참고하세요. 이번 포스팅은 비트코인에서 사용되는 작업증명 합의 방식에 대한 독자의 기초적인 이해를 가정하고 작성되었습니다.

신뢰 (trust)

사회가 정상적으로 작동하기 위해서는 구성원간의 신뢰가 필요합니다. 초기 문명은 가족 구성원, 부족 간의 혈연에 기반한 신뢰를 바탕으로 발달했습니다. 이러한 유형의 신뢰 체계는 오늘날과 같은 대규모 사회에 맞춰 확장될 수 없는 문제가 있었습니다. 문명의 발달에 따라 은행이나 정부와 같은 거대한 기관들을 형성하고 이들을 신뢰하는 방식으로 신뢰 체계를 확장해왔습니다. 하지만 이와 같은 체계는 기관들이 신뢰를 저버릴 때 무너집니다. 거대한 은행들의 부주의한 리스크 관리로 인해 발생한 2008년의 경제 위기가 좋은 예시입니다. 이렇게 특정 주체가 신뢰를 저버릴 때 발생하는 문제를 해결하기 위해서 신뢰의 대상이 분산되고 탈중앙화된 체계가 만들어졌습니다.

신뢰 체계의 변화 (http://ee374.stanford.edu/downloads/l1_slides.pdf)

중대한 기술적 도약을 이뤄낸 분산 신뢰 체계로는 비트코인과 이더리움을 들 수 있습니다. 비트코인은 대규모 네트워크에서 개방형(permissionless, 누군가의 허가 없이 아무나 네트워크에 참여하거나 떠날 수 있음) 합의(consensus, 참여자들이 시스템의 현재 상태에 대해서 동의하는 것)를 가능하게 하는 블록체인이라는 개념을 최초로 구현해냈습니다. 신뢰 체계에서 가장 중요한 개념이 바로 합의인데, 참여자들이 시스템의 현재 상태에 대해서 동의할 수 없다면 시스템이 작동할 수 없기 때문입니다. 이더리움은 합의의 대상을 단순한 주소별 잔고 관리에서 임의의 튜링 완전한 프로그램의 실행 내역으로 확장하여 스마트 컨트랙트라는 개념을 도입했습니다.

블록체인의 성능 문제

분산 신뢰 체계의 성능은 보안성, 초당 트랜잭션 수, 트랜잭션 최종성 보장에 걸리는 시간의 3가지 기준으로 평가할 수 있습니다.

비트코인과 이더리움의 성능 비교 (http://ee374.stanford.edu/downloads/l1_notes.pdf)

비트코인과 이더리움 모두 대규모로 다양한 용도에 사용되기에는 초당 트랜잭션 수와 트랜잭션 최종성 보장에 걸리는 시간에 문제가 있습니다.

블록체인 트라일레마에 따른 블록체인 플랫폼 분류 (http://ee374.stanford.edu/downloads/l1_slides.pdf)

안전하고(secure), 확장 가능하며(scalable), 분산된(decentralized) 블록체인 기술을 구현하는 문제를 블록체인 트라일레마(blockchain trilemma)라고 합니다. 우리는 경험적으로 3가지 특성 중 2가지를 충족하는 것이 가능하다는 것을 알고 있습니다. 그렇다면 3가지 모두를 충족하는 것이 가능할까요? EE374 수업은 이 문제를 집중적으로 탐구합니다.

작업증명 방식의 보안성

최장 체인(longest chain) 프로토콜에 기반한 비트코인의 작업증명 방식은 얼마나 안전한 걸까요? 트랜잭션이 채굴된 후 k개의 블록이 생성된 후에 컨펌할 경우 이중 지불 공격으로 부터 얼마나 안전한 것인지를 확률적으로 알아보겠습니다.

블록 생성 빈도를 초당 생성되는 블록 개수라고 한다면,

정직한(honest) 채굴자들의 블록 생성 빈도

공격자(adversary)의 블록 생성 빈도

라고 정의할 때 각각 지수 분포(exponential distribution)를 따릅니다. 블록을 생성하기 위한 해시 시도들이 성공적일 확률이 독립 항등 분포(independently and identically distributed) 되어있기 때문에 블록 생성 빈도는 기하 분포(geometric distribution)를 따르고, 대량의 해시 시도들이 이뤄지기 때문에 기하 분포를 지수 분포로 근사할 수 있기 때문입니다.

(i-1)번째 블록으로부터 i번째 블록을 정직한 채굴자들이 채굴하는데 걸리는 시간

(i-1)번째 블록으로부터 i번째 블록을 공격자가 채굴하는데 걸리는 시간

T_i간의 차이

공격자가 정직한 채굴자들보다 먼저 k개의 블록을 채굴하는 사건

라고 정의하게 되면 공격이 성공하게될 확률은

이 됩니다.

블록 생성에 걸리는 시간 T_i의 기대값은 블록 생성 빈도 λ의 역수이다

따라서 공격자가 전체 해시 레이트의 50% 이상을 차지하지 못할 경우 (λ_h > λ_a일 경우), k를 적절하게 큰 값으로 정한다면 이중 지불 공격이 성공할 확률이 0에 수렴함을 알 수 있습니다.

체르노프 유계(Chernoff bound)에 따르면

가 어떤 양의 상수 c에 대해서 성립하고 c는 λ_h와 λ_a에 대한 함수로부터 구할 수 있습니다. 이를 통해서 확률적으로 안전하다고 판단되는 적절한 k의 값을 정할 수 있고, 어떤 트랜잭션에 대해서 잘못된 컨펌 판단이 이뤄질 확률은 k가 증가함에 따라 지수적으로 감소한다는 것을 알 수 있습니다.

네트워크 지연의 영향

위의 분석에서는 네트워크 지연(network delay)의 영향을 고려하지 않았습니다 (∆ = 0). 현실에서는 데이터 전송 시간에 따라 블록 전파의 지연이 발생합니다. 분산 컴퓨팅의 동기 모델(synchronous model)을 통해서 네트워크 지연의 영향을 알아보겠습니다. 동기 모델에서는 지연 시간이 무한정 길어질 수 없고 지연 시간의 상한선 ∆가 존재한다고 봅니다.

b*가 전파되는데 시간이 걸리기 때문에 정직한 채굴자들이 서로 다른 블록을 생성할 확률이 존재한다 (http://ee374.stanford.edu/downloads/l4_notes.pdf)

∆ > 0이 됨에 따라 발생하는 보안성에 대한 가장 큰 영향은 정직한 채굴자들 사이에서도 자연적으로 포크(fork)가 발생할 수 있다는 것입니다.

[t − ∆, t + ∆] 사이에 정직한 채굴자들이 채굴한 다른 블록이 없을 때, 정직한 채굴자들이 어떤 시점 t에 생성한 블록을 외톨이(loner) 블록이라고 합니다. 따라서 외톨이가 아닌 자연적 포크에 따라 생성된 같은 블록 높이(block height)를 갖는 블록들을 무시할 경우 정직한 채굴자들의 블록 생성 빈도 λ_h를 새롭게 정의할 수 있습니다.

블록 생성 빈도에 대해서 지수 분포를 적용했을 때 어떤 블록이 외톨이일 확률은

이기 때문에 외톨이 블록만을 고려할 경우의 정직한 채굴자들의 새로운 블록 생성 빈도는

이 됩니다. 그래서

이 성립하는데 위에서 살펴본 바와 같이

입니다. 따라서 λ_{h,new} > λ_a일 경우 ∆ >0 이더라도 마찬가지로 k가 증가함에 따라 공격이 성공할 확률은 0에 수렴함을 알 수 있습니다.

∆ = 0이었을 때, 네트워크 전체의 보안성을 보장하는 네트워크 전체 대비 공격자들의 해시 레이트 비율의 최대 임계점은

입니다.

∆ > 0일 때는

이 됩니다. 그래서

일 때 자연적 포크 발생으로 인한 영향이 미미해집니다.

네트워크 전체의 블록 생성 빈도는

이기 때문에

따라서 네트워크 전체의 블록 생성 빈도 λ과 네트워크 지연의 상한선 ∆가 커짐에 따라 자연적 포크 발생의 확률도 증가하고, 네트워크의 보안성을 지키기 위해 필요한 정직한 채굴자들의 해시 레이트도 더 커진다는 것을 알 수 있습니다.

패러미터 조율을 통한 컨펌 지연 시간 줄이기

어떤 트랜잭션이 채굴된 후 k개의 블록이 생성되면 해당 트랜잭션이 최종성(finality)을 갖는다고 보고 컨펌(confirm)할 때, 컨펌 지연(confirmation latency)으로 인해 컨펌 과정에 걸리는 시간의 기대값은

입니다.

이기 때문에

이 성립합니다. 양변을 네트워크 지연의 상한선 ∆로 나누면

으로 나타낼 수 있습니다.

양변간에 선형적인 상관 관계가 존재한다 (http://ee374.stanford.edu/downloads/l5_notes.pdf)

여기서 컨펌 지연 시간을 줄이기 위해 변경될 수 있는 패러미터들은 k와 λ입니다.

k를 작은 값으로 설정하게 되면 ε이 커집니다. 이는 시스템의 안정성이 저하된다는 뜻입니다.
k의 값을 변경하지 않고 더 빠르게 블록이 생성되도록 하여 소요 시간을 줄이기 위해 λ를 늘리게 되면, 공격자들에게 더 취약해지기 때문에 보안성을 유지하기 위해서 정직한 채굴자들의 해시 레이트 비중이 더 높아져야 합니다.

따라서 최장 체인 프로토콜을 따르는 시스템이 패러미터 수정을 통해 컨펌 지연 시간을 줄이게 되면 보안성이 저하된다고 볼 수 있습니다.

패러미터 조율을 통한 처리량 늘리기

처리량(throughput)은 초당 얼마나 많은 작업을 처리할 수 있는가를 뜻합니다. 일반적으로 TPS(transactions per second, 초당 처리 가능한 트랜잭션 수)라는 단위로 알려져 있습니다.

블록의 크기를 B, 블록의 생성 빈도를 λ, 처리량을 σ라고 한다면

입니다. 위에서 살펴보았듯이 λ를 더 큰 값으로 바꾸면 보안성이 저하됩니다. 그렇다면 B의 값을 크게 하면 어떨까요?

연구 결과에 따르면 블록의 크기가 커지면 ∆도 증가한다 (Information propagation in the Bitcoin network by C. Decker and R. Wattenhofer.)

∆이 B에 비례하기 때문에

이 성립합니다. 어느 패러미터를 증가시키더라도 λ∆가 증가하게 됩니다.

따라서 최장 체인 프로토콜을 따르는 시스템이 패러미터 수정을 통해 처리량을 늘리게 되면 보안성이 저하된다고 볼 수 있습니다.

맺음말

이번 포스팅에서는 최장 체인 프로토콜에 기반한 작업증명 방식의 보안성과 왜 블록 생성 빈도 또는 블록의 크기를 무제한적으로 늘려서 확장성을 개선할 수 없는지 알아보았습니다. 다음 포스팅에서는 다양한 합의 방식에 대해서 알아보도록 하겠습니다.

감사합니다.