Scaling Solutions of Monolithic Chain
Disclaimer: 본 글은 서울대학교 블록체인 학회 디사이퍼(Decipher)의 Weekly Session에서 Monolithic Blockchain의 확장 솔루션을 주제로 발표한 내용을 기반으로 작성되었습니다. 해당 글은 Monolithic Blockchain의 확장 솔루션에 대한 전반적인 내용을 바탕으로 작성자의 주관적인 의견을 포함하여 작성하였으며, 본 글에 포함된 어떠한 내용도 투자 조언이 아님을 명시합니다. 이에 따라 본 글의 어떠한 내용도 투자 조언으로 해석되어서도 안 됩니다.
Author
윤정수, 노민섭 of Decipher
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
Reviewed By 신성헌, 박순종, 최재우
Introduction
블록체인의 확장성 문제를 해결하기 위한 다양한 솔루션들이 계속해서 나오고 있습니다. 크게 두 가지로 분류해 보자면 기반이 되는 L1 체인에 rollup, sidechain, data availability layer 등 다양한 모듈러 솔루션을 결합하여 수평적으로 확장성을 높이는 방식이 있고, 기술적인 변형 혹은 개선 등을 통해서 L1 체인 자체의 확장성을 수직적으로 높이는 방식이 있습니다.
전자의 경우, 기존 L1 체인의 보안과 네트워크 효과를 활용하면서도 개별 모듈별로 특화된 기능을 제공할 수 있다는 장점이 있습니다. 이미 이더리움을 중심으로 다양한 L2 솔루션들이 활발하게 개발되고 있으며, Celestia와 같이 모듈러 블록체인에 최적화된 인프라 레이어를 제공하는 프로젝트도 등장하고 있습니다.
반면 후자의 경우에는 모듈화로 인한 복잡성을 피하고 단일 체인으로 높은 성능을 끌어낼 수 있다는 강점이 있습니다. 전통 강자인 Solana가 최근 주목을 받고 있고, 최근 등장한 Aptos, Sui 등도 주목을 받고 있는데요. 이들은 트랜잭션의 병렬 실행, 더욱 효율적인 합의 알고리즘 도입 등을 통해 기존 L1 체인 대비 한층 진화한 확장성을 제공하고 있습니다.
본 글에서는 후자의 방식에 해당되는 최신 블록체인 프로젝트들이 Monolithic한 구조를 유지하면서도 어떻게 L1 체인 자체의 성능을 극대화하는지, 트랜잭션 병렬 실행의 원리와 효율적인 합의 알고리즘을 중심으로 알아보려고 합니다.
트랜잭션 병렬 실행
먼저 블록체인의 실행단(Execution Layer)에서 트랜잭션 처리 속도 향상을 통해 확장성을 증대시키는 방법인 트랜잭션 병렬 실행에 대해 살펴보겠습니다.
트랜잭션 병렬 실행이란?
블록체인의 합의 과정에서 Proposer 혹은 Miner로 선정된 노드가 블록을 생성하여 다른 노드(검증자)들에게 전파하면, 전달받은 노드들은 해당 블록에 속해있는 모든 트랜잭션들을 전부 실행시켜보고 나서 실행 결과가 동일한지 확인합니다.
기존의 EVM 기반 블록체인의 노드들은 해당 과정에서 트랜잭션들을 미리 정해진 순서대로, 한 번에 한 개씩 순차적으로 실행시킵니다. 하지만 한 번에 한 개씩 말고 여러 개의 트랜잭션을 동시에 실행시킨다면, 보다 많은 트랜잭션들을 빠른 시간 안에 처리할 수 있을 것입니다.
트랜잭션 병렬실행은 이렇게 다수의 트랜잭션들을 동시에 병렬적으로 실행시켜서, 블록체인의 실행단(Execution Layer)에서의 확장성을 개선하는 방법입니다.
의존성 문제
그런데 이렇게 다수의 트랜잭션들을 병렬적으로 실행시킬 때 문제가 발생할 수 있습니다.
예를 들어서, NFT 민팅을 진행하는데 NFT 개수가 단 1개라고 가정합니다.
A와 B라는 사람이 해당 NFT를 민팅하는 트랜잭션을 노드에게 제출하였고, 우연히 두 트랜잭션이 한 블록에 동시에 담기게 되었습니다.
만약 두 트랜잭션을 순차적으로 실행시킨다면, 블록 Proposer에 의해 정해진 순서대로(일반적으로 가스비를 높게 제출한 순서대로) 두 트랜잭션 중 하나의 트랜잭션이 먼저 실행되고, 남은 NFT의 개수는 0개로 바뀌어서 나머지 하나의 트랜잭션은 NFT 매진으로 인해 실패 처리될것입니다.
그런데 이 두 트랜잭션을 병렬적으로 동시에 실행시킨다면, 순서가 지켜질 수 없기 때문에 실행 때마다 결괏값이 달라질 수 있습니다. <A가 민팅 성공, B는 민팅 실패> / <B가 민팅 성공, A는 민팅 실패> 두 가지의 결괏값이 나올 수 있는 것입니다. 또한 트랜잭션이 한 번에 한 개씩만(순차적으로) 실행되는 게 아니기 때문에, 한 개의 트랜잭션이 남은 NFT 개수를 먼저 업데이트하기 전에, 두 트랜잭션이 동시에 남은 NFT 개수를 1개로 읽어서 A, B 둘 다 민팅을 성공한 결괏값이 나올 수도 있습니다.(Double Spending과 유사)
이러한 문제점들은 Deterministic 한 실행 결괏값을 내야 하는 블록체인에서 병렬 실행을 더욱 어렵게 합니다.
그렇다면 병렬실행 간에 이러한 문제가 발생하는 이유는 무엇일까요? 두 트랜잭션 모두 같은 NFT와 상호작용하기 때문입니다. 좀더 정확히 말하면 두 트랜잭션 모두 같은 NFT 컨트랙트의 <남은 NFT 개수>라는 storage 상태 값에 접근하기 때문입니다. 결국 같은 storage 상태 값 즉, 같은 자원을 공유하는 트랜잭션은 서로의 실행 결과에 영향을 미치는 상호 의존적인 상태가 되어, 동시 실행 시 처리된 순서에 따라 결괏값이 달라지는 문제가 발생하게 되는 것입니다. (이렇게 두 개 이상의 트랜잭션이 서로 같은 자원에 대한 접근을 경쟁할 때 발생하는 문제를 흔히 Race Condition이라고 합니다)
만약 두 트랜잭션이 서로 다른 NFT를 민팅하는 트랜잭션이면, 서로 의존성이 없기때문에 병렬로 실행시키더라도 아무런 문제가 없었을 것입니다.
그렇다면 이러한 의존성 문제를 해결하여 트랜잭션들을 병렬로 빠르게 처리하면서도, 정해진 순서에 따라 순차적으로 처리한 것과 같은 결괏값을 낼 수 있는 병렬실행 방식에는 뭐가 있을까요?
병렬 실행 방식
앞서 말했듯이, 트랜잭션 병렬 실행에 있어서 제일 핵심적인 과제는 ‘의존성 문제가 있는 트랜잭션들을 어떻게 처리할 것인가?’입니다.
따라서 본 글에서는 의존성 문제를 해결하는 방식을 기준으로 여러 가지 병렬 실행 방식을 분류해서 소개하고자 합니다.
- State Access Method
State Access Method는 트랜잭션들이 어떤 스토리지 상태 값에 접근하는지를 사전에 확인한 뒤 이를 토대로 트랜잭션 간의 의존성을 파악합니다. 그리고 나서 의존성이 없는 트랜잭션들을 병렬로 실행시키고, 의존성이 있는 트랜잭션 끼리는 순서에 따라 순차적으로 실행 시킴으로써 의존성 문제를 해결합니다. 이러한 State Access Method 방식으로 병렬 실행을 하는 대표적인 블록체인으로 Solana와 Sei가 있습니다.
Solana(SVM)
솔라나의 경우엔 프로그램(스마트 컨트랙트) 자체가 stateless 하게 구성되어 있습니다. 이더리움의 스마트 컨트랙트처럼 컨트랙트가 개별적으로 상태 값을 저장하지 않는 구조입니다. 그 대신 솔라나는 개별적인 account를 통해서 상태 값을 분리해서 따로 관리합니다.
유저들은 트랜잭션을 제출할 때 위 그림처럼 트랜잭션에서 접근하게 될 account 리스트를 read-only, writeable account로 구분해서 별도로 제출하게 됩니다.
이렇게 접근할 account가 명시된 트랜잭션들은 위 그림처럼 실행단계에서 배치로 묶여서 병렬로 실행하게 됩니다. 그런데 위 파이프라인과 아래 파이프라인에서 둘 다 C라는 account에 접근하는 트랜잭션이 존재하기 때문에 의존성 문제가 발생할 수 있습니다. 따라서 노드(검증자)는 read-write 락을 사용해서 우선순위가 높은 트랜잭션에게만 해당 account에 대한 접근 권한을 줍니다. 그림의 예시에서는 위 파이프라인이 먼저 C account에 락을 걸고 트랜잭션들을 실행합니다. 이와 동시에 아래 파이프라인도 실행되지만 C account에 쓰기 연산을 하는 트랜잭션은 제외된 뒤, 다음 실행 순서를 위해서 남겨집니다.
솔라나는 이러한 방식을 통해서 의존성이 없는 트랜잭션은 병렬로, 의존성이 있는 트랜잭션은 순차적으로 실행할 수 있게 됩니다.
Sei
Sei의 경우에도 마찬가지로 사전에 파악된 의존성에 대한 정보를 바탕으로 위 그림처럼 리소스 접근에 관한 DAG(Directed Acyclic Graph)를 구성합니다. 그런 다음 모든 트랜잭션 당 하나의 고루틴(경량 스레드)을 할당받게 됩니다. 따라서 모든 트랜잭션이 일단 동시에 실행되기 시작하는데, 이때 트랜잭션을 구성하는 각각의 연산들 중에 DAG를 바탕으로 의존성이 파악된 연산은 해당 의존성이 해소되기 전까지 블록 되었다가 의존성이 해소되고 나면 실행됩니다.
이런 식의 State Access Method는 노드(벨리데이터)입장에서 의존성 파악에 사용되는 오버헤드가 거의 없다는 장점이 있지만, 유저 혹은 개발자 입장에서는 의존성 관련된 정보들을 면밀히 파악하여 제공해야 하는 부담이 있습니다.
2. Optimistic Method — Block-STM
Optimistic Method는 의존성과 관련된 아무런 사전 정보 없이, 말 그대로 낙관적으로 트랜잭션 간의 의존성이 없다는 가정 하에 일단 병렬로 실행 하는 방식입니다. 병렬 실행 후 검증 과정에서 의존성 문제가 발견된 트랜잭션은 성공할 때까지 계속해서 실행 및 검증을 반복합니다.
Optimistic Method 관련해서는 높은 TPS와 Finality를 가진 Aptos가 사용하고, EVM이 호환되는 병렬 VM을 곧 출시할 예정인 SeiV2에서 차용된 Block-STM을 소개하려 합니다.
2.1 Block-STM의 기반이된 기술
Block-STM을 살펴보기에 앞서 Block-STM의 기반이 된 기술을 먼저 알아보겠습니다.
<STM(Software Transactional Memory)>
STM은 이름에서 알 수 있듯이 Block-STM의 기초가 되는 기술입니다. 메모리 접근을 계측하여 충돌을 감지하고 관리하는 방법론을 제시하였는데, OCC(Optimistic Concurency Control)와 결합하여 동시 실행 과정에서 메모리 접근을 기록하고, 실행 이후 모든 트랜잭션을 검증합니다. 검증작업에서 의존성에 의한 충돌이 발견되어 검증 실패하면, 재실행 및 재검증을 검증 성공 때까지 반복하게 됩니다. 이러한 방식은 동시에 실행된 트랜잭션들이 마치 순차적으로 실행된 것과 같은 결과를 만들어 주지만, 트랜잭션의 preset-order를 지켜주지 않기 때문에 deterministic 한 결괏값을 내지 못하게 되고, 결과적으로 블록체인에서 그대로 사용하기 어렵습니다. 또한 필연적인 충돌 기록 유지 및 검증 실패로 인하여 성능적인 부분에 한계가 있기 때문에 Production Level에서 그대로 사용하는 경우는 드뭅니다.
<BOHM(Bounded Ordering with High parallelism in Multicore)>
BOHM은 정적 분석, 사전 실행, 유저가 제공하는 정보 등을 통해서 쓰기 작업에 사용될 메모리 위치를 미리 예상해서 트랜잭션들의 충돌을 방지하는 기술입니다. 뒷부분에서 자세하게 설명을 하겠지만 다중 버전 자료구조(Multi-version data structure)라는 것을 이용해서 의존성 문제를 해결하고, 특히나 preset-order에 따라 트랜잭션의 실행 순서를 보장해 줍니다. BOHM을 단독으로 사용할 경우엔 쓰기 작업에 사용될 위치를 미리 예상하기 위한 사전 제공 정보가 필요하고, 사전 실행을 통한 예상 값이 틀릴 경우에 그 비용이 너무 커서 Block-STM에서는 BOHM의 다중 버전 자료구조의 개념만을 차용해서 사용합니다.
2.2 Block-STM 구성요소
<다중 버전 자료구조(Multi-version data structure)>
‘다중버전 구조’
다중 버전 자료구조는 앞서 설명드린 BOHM에서 차용한 기술로 같은 메모리 위치에 쓰기 작업이 실행될 경우에 쓰기 값을 개별적으로 저장하는 방식입니다. 위 그림은 특정 메모리 위치에 총 4개의 서로 다른 트랜잭션이 쓰기 작업을 하는 예시입니다. 각 트랜잭션의 쓰기 작업이 충돌하지 않게 하기 위해서 각각의 쓰기 값을 분리해서 저장하는 것을 볼 수 있습니다.
또한 읽기 작업 시에는 트랜잭션 자신의 인덱스보다 작거나 같은 값 중에 가장 높은 값의 인덱스를 읽게 됩니다. 위 그림에서 TX5의 읽기 작업 시에는 TX3이 수행한 쓰기 값을 읽게 됩니다. 이를 통해서 쓰기 작업과 읽기 작업 간의 충돌을 방지할 수 있으며, preset-order에 따라 순서대로 트랜잭션을 처리한 결괏값을 낼 수 있습니다.
‘다이나믹한 의존성 관리’
Block-STM 방식은 해당 다중 버전 자료구조를 통해서 트랜잭션 실행 중 다이나믹한 의존성 관리 또한 수행합니다. 만약 트랜잭션이 검증 작업 과정에서 실패를 하게 될 경우에 해당 트랜잭션이 다중 버전 자료구조에서 쓰기 작업을 했던 값에다가 위 그림처럼 ESTIMATE 마크를 달아줍니다. 같은 위치에 읽기 작업을 수행하는 다른 트랜잭션들이 실행 혹은 검증작업 중에 해당 ESTIMATE 마크를 읽게 되면, 의존성 문제가 있다는 것을 빠르게 파악하게 되고 다시 실행 대기 중 상태로 돌아갈 수 있게 됩니다. 위 그림에서 TX5는 TX3의 ESTIMATE 마크를 발견하여 즉시 재실행 상태로 되돌아간 뒤 ,TX3이 재실행되어 ESTIMATE 마크를 지우기 전까지 실행되지 않습니다.
<협업 스케줄러(Collaborative Scheduler)>
협업 스케줄러는 모든 트랜잭션들의 실행(Execution) 및 검증(Validation) 작업의 우선순위를 조정하여 인덱스가 낮은 트랜잭션에 대한 작업들이 우선적으로 실행되도록 스케줄링 합니다. 다중 버전 자료구조에서 ESTIMATE 마크를 읽은 트랜잭션을 의존성이 해소되기 전까지 블록 하는 의존성 관리 또한 협업 스케줄러에서 이루어집니다.
협업 스케줄러는 작업들을 할당하는 과정에서 모든 가용한 스레드를 활용해서 낙관적으로 최대한 많은 작업들을 병렬적으로 실행합니다. 이 과정에서 검증작업에 실패한 트랜잭션은 재실행 필요 상태로 변경되며, 해당 트랜잭션의 인덱스보다 높은 모든 트랜잭션들 중 실행 완료된 트랜잭션들은 의존성으로 인한 재실행 필요 여부를 파악하기 위해서 검증 필요 상태로 다시 되돌립니다. 또한 재실행하는 트랜잭션이 기존 실행 작업 대비 새로운 메모리 위치에 쓰기 작업을 하게 될 경우 해당 트랜잭션 인덱스와 같거나 높은 모든 트랜잭션들 중 실행 완료된 트랜잭션들을 검증 필요 상태로 변경합니다.
2.3 Block-STM 트랜잭션 실행 및 검증 작업
Block-STM의 트랜잭션 실행 및 검증작업 간에 구성요소끼리 어떠한 상호작용을 하는지 살펴보겠습니다.
<실행작업(Execution)>
실행 작업에서는 첫 번째로 실행자(Executor)가 협업 스케줄러(Collaborative Scheduler)에게 작업을 요청하게 되고 협업 스케줄러는 실행 작업을 실행자에게 넘겨줍니다. 실행자는 가상머신(VM)에게 트랜잭션 실행을 요청하게 되고 가상머신은 다중 버전 자료구조(Multi-version data-structure)에서 필요한 값을 읽어가면서 트랜잭션을 실행하게 됩니다. 가상머신은 트랜잭션이 실행 완료되고 나면 실행 과정에서 사용했던 읽기 값과 쓰기 값을 묶어서 실행자에게 전달합니다. 이 읽기 값 쓰기 값 세트는 후에 검증작업에 필요한 값이므로 따로 기록한 뒤에 실행자는 쓰기 값을 다중 버전 자료구조에 적용시키게 됩니다. 마지막으로 작업자는 해당 실행 결과를 협업 스케줄러에게 전달하게 됩니다.
협업 스케줄러는 전달받은 실행 결과에 따라 다음과 같이 스케줄링합니다.
- 실행 작업 실패 (실행 중 ESTIMATE 마크를 읽은 경우): 해당 트랜잭션을 실행 대기 상태로 되돌리고, 해당 ESTIMATE 마크가 사라질 때까지 블록 시킵니다.
- 실행 작업 성공
- 새로운 메모리 위치에 쓰기 작업을 했을 때: 해당 트랜잭션의 인덱스와 같거나 높은 모든 트랜잭션들 중 실행 완료된 트랜잭션들을 검증 필요 상태로 변경합니다.
- 그외: 해당 트랜잭션만 검증 필요 상태로 변경합니다.
<검증작업(Validation)>
실행자가 협업 스케줄러에게 작업을 요청하고 협업 스케줄러는 검증작업을 작업자에게 넘겨줍니다. 실행자는 아까 실행 작업때 기록해놓았던 실행 중 사용한 읽기 값과 다중 버전 자료구조에서 새롭게 읽어온 값을 비교하여 검증합니다. 이때 두 값이 서로 다르거나 다중 버전 자료구조에서 새롭게 읽은 값에 ESTIMATE 마크가 달려있으면 검증 실패로 처리됩니다. 작업자는 해당 검증결과를 협업 스케줄러에게 전달하게 됩니다.
협업 스케줄러는 전달받은 실행 결과에 따라 다음과 같이 스케줄링합니다.
- 검증작업 성공: 다음 작업을 할당합니다
- 검증작업 실패
- 다중 버전 데이터구조에서 해당 트랜잭션의 쓰기 값들에 모두 ESTIMATE 마크를 답니다.
- 해당 트랜잭션의 인덱스보다 높은 모든 트랜잭션들 중 실행 완료된 트랜잭션들을 검증 필요 상태로 변경합니다.
- 해당 트랜잭션의 재실행 횟수 카운터를 증가시킨 후 실행 대기 상태로 되돌립니다.
2.4 Block-STM 성능
해당 그래프는 Block-STM을 통한 병렬 실행 일반적 순차 실행(Sequential Execution)의 tps를 비교한 그래프입니다. 해당 테스트는 모두 만개의 트랜잭션을 포함한 블록들로 수행되었으며, 모든 트랜잭션은 8개의 읽기 연산 5개의 쓰기 연산으로 구성되어 있고, account의 개수를 바탕으로 트랜잭션 간의 충돌 혹은 의존성 수준을 조절했습니다. (Account의 개수가 적을수록 의존성이 있는 트랜잭션이 다수 포함될 가능성이 높다)
32 스레드를 기준으로 계정수 1만 개로(트랜잭션 간의 의존성이 거의 없는 상태로) 트랜잭션을 발생시키면 Block-STM이 순차 실행에 비해 16배 빠른 tps를 보여주고, 계정수 100개로 진행했을 때는 8배 빠른 tps를 보여줍니다.
심지어 계정 2개로 트랜잭션을 발생시켜 대부분의 트랜잭션들이 의존성이 있는 상태로 테스트를 했을 때도 1만 tps 수준으로 순차적 실행과 비슷하게 성능이 나오는 것을 알 수 있습니다.
효율적인 합의 알고리즘
요즘 확장성으로 주목을 받는 모놀리식 체인들은 SOTA(State-of-Art) 합의 알고리즘을 선택해 성능을 많이 끌어올리기도 했습니다. 이를 살펴보기 위해, 블록체인의 합의 알고리즘이 걸어온 길과 학술적으로 정의된 문제 상황 등을 폭넓게 이해할 필요가 있었는데요, 그 공부 과정을 공유하도록 하겠습니다.
분산 환경에서의 노드 간 합의
분산 환경에서 발생할 수 있는 문제
n개의 노드가 있는 분산화된 시스템을 가정해 봅시다. 노드 중 하나라도 고장 나면 시스템이 망가지는 경우를 생각해 봅시다. 노드가 하루 안에 고장 날 확률이 x라고 할 때, x의 값이 아무리 작다고 하더라도 (ex. 0.01%), 노드가 5,000개가 있다면, 시스템이 하루 안에 한 번이라도 고장 날 확률은 60%가 넘습니다. 그렇기 때문에, 분산 환경에서의 장애는 반드시 발생한다는 것을 전제로 시스템을 설계해야 합니다.
분산 시스템은 이러한 장애 상황에서 발생할 수 있는 문제를 해결하기 위해 합의(Consensus) 라는 개념을 이용합니다. 합의는 노드 간의 일관된 상태 유지를 위해 사용되는 기술입니다. 이는 각 노드가 서로 다른 정보나 상태를 가지는 상황에서도 전체 시스템이 동일한 결정을 내리는 것을 목표로 합니다.
그렇다면, 발생할 수 있는 장애의 종류는 어떤 게 있을까요? 이는 크게 Benign Failure(양성 장애)와 Byzantine Failure(비잔틴 장애)로 구분할 수 있습니다.
양성 장애는 흔히 예측 가능한 장애 상황을 의미합니다. 네트워크 이슈로 응답 속도가 저하된다거나, 하드웨어 이슈로 프로세스가 멈추는 등 감지가 쉽고, 예상되는 방식의 실패를 의미합니다. 이는 일반적으로 타임아웃 처리, 재부팅, 서버 교체 등의 알려진 방법으로 대응이 가능한데요, 문제는 비잔틴 장애 상황입니다.
비잔틴 장애는 분산 시스템을 구성하는 요소가 의도적이거나 악의적인 목적을 가지고 시스템에 위해를 가하는 경우를 포함합니다. 이러한 장애 상황은 감지하거나 예측하는 것이 어렵기 때문에 효율적인 합의 알고리즘의 구현이 더 어렵습니다. 블록체인은 Trustless(무신뢰성)이 가장 중요한 특징 중 하나인 분산 시스템으로서, 비잔틴 장애 상황은 필히 가정이 되어야 합니다.
FLP Impossibility
블록체인의 트릴레마와 비슷하게, 합의 알고리즘에도 트릴레마가 있습니다. 이 중, 비잔틴 장애 상황에선 Fault Tolerance는 반드시 달성되어야 하는 문제입니다. 그렇기 때문에, 비잔틴 내결함성 합의 알고리즘은 Safety(안전성)과 Liveness(활동성) 두 가지 성질을 놓고 줄다리기를 하게 됩니다.
<Safety>
Safety는 ‘나쁜 일은 일어나지 않는다’라는 말로 정리할 수 있습니다. 블록체인의 경우를 예시로 들면, 노드 간 합의가 발생해서 블록이 생성된다면 그 결과가 변경(포크)되는 일은 없다는 의미입니다. 그렇기 때문에, 특정 블록이 블록체인에서 컨펌이 되면, 어디에 있는 노드로 접근하던 해당 블록의 데이터는 동일해야 합니다. 그렇다면, Safety가 보장되지 않는 상황은 어떤 상황일까요? 이는 네트워크가 포크가 될 수 있음을 의미합니다.
<Liveness>
Liveness는 합의에서 주로 사용되는 ‘Eventually’ 로 요약될 수 있는데요, ‘좋은 일은 결국 일어난다’라는 말로 정리될 수 있습니다. 이를 블록체인의 관점에서 생각해 보면, 내가 검증한 트랜잭션이 유효하고, 그로부터 만든 블록이 유효하다면, 네트워크 내에서는 반드시 합의가 일어난다는 의미입니다. 그렇다면, Liveness가 보장되지 않는 상황은 어떤 상황일까요? 내가 블록을 만들었고, 그게 암호학적으로 아무 문제가 없다면 언젠가는 해당 블록이 채굴되어야 하지만, 그 블록이 유효함과 상관없이 블록이 채굴되지 않을 수도 있다는 의미입니다.
Proof — of — X
비잔틴 상황에서, Safety를 포기한다는 것은 포크가 발생할 수 있다는 의미이고 이는 네트워크의 불변성과 신뢰성을 훼손한다는 의미이기 때문에, 기존의 연구는 Safety를 최우선적으로 보장하려고 했습니다. 그런데 이런 관념을 깨버리고 Liveness를 Safety보다 우선시 한 합의 알고리즘이 비트코인의 시초인 Nakamoto Consensus 입니다.
이는 당시에 비잔틴 문제를 접근하는 꽤 파격적인 접근 방식이었습니다. Proof-of-Work의 연산력 퀴즈를 이용해 답을 찾아내는 노드는 그 누구라도 즉시 네트워크에 이를 전파하고 유효한 블록으로 인정(합의)을 받을 수 있습니다(Liveness).
다만, 그 대가로 네트워크가 순간적으로는 포크 될 수 있습니다. 위 그림을 예시로 들어봅시다. 노드 사이의 물리적 거리 이슈로 미국과 호주 지역에서 거의 동시에 블록을 채굴하는 것 성공했다고 가정해 봅시다.
Liveness가 우선시 되는 합의 알고리즘이기에, 두 블록 모두 네트워크에서 유효한 블록으로 처리되며 네트워크가 포크 된 상태로 당분간 유지됩니다. 그럼에도 다시 일관된 상태를 결국 유지할 수 있는 이유는 나카모토 합의는 확률적으로 Safety를 보장하기 때문입니다. 이는 여러 개의 체인이 존재할 때, 가장 긴 블록을 가지고 있는 네트워크를 유효한 네트워크로 본다는 룰이 있기 때문입니다.
두 개의 체인이 공존하고 있는 상황에서, 유럽 지역에서 초록색 (호주) 지역의 블록체인을 연장하는 분홍색 체인을 채굴하는 데 성공하는 경우, 빨간색 체인은 자신의 체인을 버리고 가장 긴 체인인 초록-핑크 체인을 Canonical Chain(정격 체인)으로 선택하게 됩니다.
PBFT
반면에, 오늘 알아보게 될 state of art consensus algorithm은 기존 학계의 연구에서처럼 safety를 우선시하는 합의 알고리즘입니다. 블록 생성의 합의가 일어나고 나면 네트워크가 포크 될 가능성은 없습니다. 이는 컨펌된 블록의 결과는 즉각적인 finallity(최종성)이 보장이 되는 알고리즘입니다. 그 중, 현재 SOTA 알고리즘의 기초가 되는 합의 알고리즘은 BFT 계열의 알고리즘인 PBFT (Practical Byzantine Fault Tolerance) 입니다. PBFT의 가장 큰 특징은 1개의 리더 노드와, 여러 개의 Replica (레플리카) 노드로 구성된 합의 알고리즘이란 것입니다. 그렇기 때문에, 블록체인 말고도 여러 분산 데이터베이스와 비슷하게 시스템의 상태 변화, 즉 데이터베이스에서의 쓰기 작업은 리더가 전적으로 담당하게 됩니다.
3-phase commit과 같은 내용을 제외하고, 합의가 이루어지는 과정을 간단하게 따라가보도록 하겠습니다. 위 알고리즘은 다음과 같은 단계로 이루어집니다.
- Request: 클라이언트가 상태 변환을 요청하는 메시지를 리더 노드에 전송합니다. 이 요청은 클라이언트가 시스템의 상태를 어떻게 변환할지에 대한 내용, 블록체인 관점으로는 트랜잭션들에 대한 내용을 포함하고 있습니다.
- Pre-prepare, Prepare: 리더 노드는 클라이언트의 요청을 받아, 이를 기반으로 Prepare 메시지를 만들어 모든 노드에 전송합니다. 각 Replica 노드들은 리더로부터 받은 Prepare 메시지를 검증하고, 만약 메시지가 올바르다고 판단되면 이를 다른 모든 노드에게 전파합니다. 이 과정들을 통해 모든 정상 노드는 동일한 과정을 요청을 처리하게 됩니다.
- Commit: 각 노드는 전체 노드의 2/3 이상, 즉 2f+1 개 이상의 노드로부터 동일한 Prepare 메시지를 받게 되면, 해당 요청이 유효하다고 판단합니다. 그리고 이 사실을 다른 모든 노드에 Commit 메시지를 통해 알립니다.
- Reply: 각 노드는 2f + 1 개 이상의 Commit 메시지를 받으면 클라이언트의 요청을 실제로 실행합니다. 이는 블록체인의 관점에서는 새로운 블록을 생성하고 체인에 연결하는 과정에 해당합니다. 요청 실행이 완료되면, 각 노드는 그 결과를 직접 클라이언트에게 반환합니다.
- 마지막으로, 클라이언트는 f + 1 개의 노드로부터 동일한 결과를 받게 되면, 자신의 요청에 대한 합의가 완료되었다고 판단합니다.
여기서 f는 전체 시스템에서 감내할 수 있는 비잔틴 노드의 개수를 의미하고, f개의 비잔틴 노드가 있다고 가정할 때, 2f + 1 개 (66%) 의 정상 노드가 있어야 시스템은 정상적으로 가동될 수 있습니다.
이 PBFT의 특징 중 가장 큰 장점은 즉결적인 Finality가 보장이 된다는 것입니다. 이는 메시지의 지연 시간에 대한 상한선이 없는 비동기 네트워크 상황에서도 Safety가 보장된다는 것과 같은 말입니다. 메시지의 답변이 언제 올지 모르는 상황에서도, 합의가 이루어졌다는 것은 이미 최소 정족수를 넘는 노드 간에 합의가 일어나서 블록을 생성했다는 의미이기 때문에, 이 값이 변경될 일은 없습니다.
하지만, PBFT는 Liveness를 PoW와 같이 완벽하게 보장할 수는 없습니다. 지연이 아주 큰 상황이거나, 제대로 된 노드의 응답이 도달하지 않는 경우에는 유효한 블록이 있더라도 이를 생성할 수 없는 경우가 생깁니다.
그리고, 오늘 주제인 스케일링 관점에서 PBFT의 가장 큰 단점은, 메시지의 전송 수가 노드의 수에 제곱으로 비례한다는 사실입니다. 위의 그림을 다시 살펴보면, 매 절차가 진행될 때마다, Replica는 모든 노드에 메시지를 전송하는 것을 확인할 수 있습니다. 이는 n개의 노드가 있을 때는 메시지의 수가 n제곱을 필요로 함을 나타내기 때문에 전체 블록체인 시스템에서 노드의 수를 많이 가져가는 것이 불가능하고, 노드의 수가 많아질 수록 성능저하가 일어나게 됩니다.
이제 학술적인 관점이 아닌 PBFT가 블록체인에서 사용되는 사례를 살펴보면, 주로 Permissioned Blockchain (허가형 블록체인)에서 사용되는 것을 확인할 수 있습니다. 가장 대표적인 예시가 클레이튼입니다. 클레이튼은 이더리움보다 더 많은 TPS 달성을 위해 이더리움을 포크해 사용하면서도, 합의 알고리즘은 PBFT를 변형해 사용했는데요, 이 때, PBFT를 사용하면서 이더리움처럼 많은 노드를 네트워크에 사용할 수 없기 때문에, 승인 받은 기업이나 단체만 블록 생성을 할 수 있는 위원회를 구성해, 컨센서스가 네트워크 성능에 병목이 되지 않도록 하였습니다.
코스모스의 경우도 PBFT와 위임형 지분 증명인 DPoS를 결합한 Tendermint를 합의 알고리즘으로 사용했고, 이를 최적화해가며 사용하고 있습니다. 블록체인에서의 탈중앙성은 쉽게 포기할 수 없는 것인데, 밸리데이터의 수를 많이 늘릴 수 없으니 의사 결정 권한을 일반 유저들이 토큰을 위임함으로써 일종의 대의 민주주의처럼 작동할 수 있게 만든 것입니다.
Beyond PBFT
PBFT 이후에도 합의 알고리즘은 특성에 맞게 계속 발전해 나가고 있습니다. 그 중, 블록체인 분야에서 주목을 받은 것은 더 효율적인 합의 알고리즘들 입니다.
그 중 Libra의 전신이면서 AptosBFT, MonadBFT 등에 사용된 HotStuff, 그리고 앱토스가 지향하고 있으면서, Sui는 이미 사용하고 있는 DAG based 합의 알고리즘에 대해 더 상세하게 알아보도록 하겠습니다.
HotStuff
PBFT는 모든 노드 간에 각 단계가 정상적으로 수행되었음을 확인하는 메시지를 보냈기 때문에, 메시지의 수가 노드의 수에 제곱으로 비례하는 메시지 복잡성을 가졌는데요, 이를 선형적으로 줄여 대규모 노드 집합에서 더 효율적으로 작동하도록 만든 것이 HotStuff의 특징입니다. 이를 논문에서는 linear communication 또는 합의의 선형성이라고 부릅니다. 이 메시지 복잡도를 낮추는데 핵심이 된 기술은 Threshold Signature라 불리는 일종의 멀티 시그니쳐 방식입니다.
Threshold Signature(임계값 서명)은 f개의 비잔틴 노드를 감내할 수 있도록 가정된 네트워크에서 2f+1개의 threshold를 넘는 노드가 서명에 참여하면 유효한 값이 나오는 다중서명을 이용하는 것입니다.
오른쪽 그림의 HotStuff의 과정을 PBFT와 비교해서 간략하게만 살펴보면, 리더 노드는 각 노드에게 Prepare 메시지를 보냅니다. 그러면, Prepare 메시지에 포함된 내용을 각 레플리카 노드들은 부분서명을 진행해 다시 리더에게만 돌려줍니다. PBFT와 다른 부분은, PBFT에서는 리더가 보낸 메시지를 Replica가 검증하고, 이를 제대로 검증했음을 서로 모든 노드에게 전달을 했었는데, 여기서는 부분 서명을 진행해 리더에게만 메시지를 전달합니다.
이와 같은 과정을 통해, 메시지의 전달 단계는 PBFT에 비해 조금 더 많아지지만, 메시지의 수는 PBFT와 달리 노드의 수에 선형으로 비례하게 됩니다. 합의 과정을 조금만 더 살펴보면, 리더는 모든 레플리카가 보낸 메시지를 바탕으로 정족수 인증이라 하는 인증서를 생성해서, 프리 커밋 메시지와 함께 모든 레플리카에 전송하고, 이는 다시 전송되기를 반복하며 최종적으로 합의 상태에 도달합니다.
CPU의 연산 시간에 비해 네트워크 IO 대기시간은 그 정도가 상당히 긴 편이고, HotStuff는 노드 간 메시지를 전송하는 단계 수가 더 많아졌기 때문에, 이는 성능에 부정적인 영향을 끼칠 수 있습니다. HotStuff 논문에서는 이런 소통 과정에서 발생하는 비효율을 줄이고자 pipelining 기법이 제안되었습니다. 이를 간단히 요약하면, 일련의 합의 과정을 순차적으로 처리했을 때, 연산 자원을 효율적으로 활용을 하지 못하기 때문에, 이를 CPU 유휴 상태를 최소화하도록 하는 동시성 달성 방법입니다.
아까 각 단계에서 확인할 수 있었던, Prepare, Pre-commit, Commit, Decide 등의 일련의 단계들은 서명 등의 cpu 자원을 사용하는 연산과, 노드 간의 메시지를 주고받는 IO 바운드 작업으로 구분이 됩니다. 이를 하나의 논리적인 묶음, 즉 블록에서 순차적으로 실행을 해버리면, 연산 시간보다 상대적으로 매우 긴 처리 시간을 가진 IO 바운드 시간 동안 리더 노드가 공백 상태에 빠지기 때문에, 이를 막기 위한 방법이라고 이해하시면 됩니다.
AptosBFT 등 다양한 체인들이 이런 파이프라인 기술을 각자만의 방법으로 수정하고 적용해서 처리량을 최적화했다고 하는데, 상세 구현은 다르지만 그 아이디어는 비슷한 것으로 판단했습니다.
DAG-Based Consensus
사실 AptosBFT도 빠른 합의 알고리즘인 편이지만, 최적화의 욕심은 끝이 없습니다. 이 PBFT와 Hotstuff의 그림을 동시에 놓고 보면 개선을 할 수 있는 점을 추가로 발견할 수 있습니다. 둘 다, 합의 과정에서 리더에 가해지는 부하가 크다는 것입니다. View change라는, 일종의 리더를 변경하는 과정에 의해 특정 노드만 계속 리더로서 일하는 일은 막아지긴 하지만, 이러한 방식의 합의 구조는, 리더 노드의 성능이 블록체인 네트워크 전체 성능의 병목이 되게 됩니다. 그래서, 리더의 역할을 이 다른 Replica들에게 조금 떼어내줄 수 없을까 하는 고민이 시작되었습니다.
책임을 분배하기 위해 등장한 아이디어가 DAG 구조를 이용한 합의 알고리즘입니다. DAG는 방향성이 있는 그래프 구조인데, 위에서와 같이 병렬 처리 과정에서의 DAG이 아닌, 합의 과정에서 방향성 그래프 구조를 이용합니다.
DAG를 사용하는 합의 알고리즘에서 분배하는 책임은 메시지, 즉 트랜잭션을 다른 노드에 전파하는 책임을 리더로부터 다른 Replica 노드들이 분배받게 됩니다. 이제, 리더는 합의의 결정과 관련된 책임만 남겨진 상태이기 때문에, 리더 성능이 병목이었던 것을 네트워크 전체의 책임으로 나눠 가질 수 있게 됩니다.
Message Broadcast (메시지 브로드캐스트)의 책임을 분배해서 가져간다는 것을 블록체인과 연계해 생각해 본다면, 싱글 리더가 통합해서 관리하던 Mempool의 역할을 분배하는 문제로 추상화할 수 있을 것 같습니다.
PBFT와 HotStuff 합의 알고리즘을 멤풀 관점에서 다시 생각해 봅시다. 특정 라운드에서의 트랜잭션 정렬 등의 권한은 리더에게 전적으로 있고, 이를 모든 레플리카 노드에 브로드캐스트 하므로, 각 단계에서 모든 노드는 같은 상태의 멤풀을 가지게 됩니다. 실제 분산 데이터베이스에서도 여러 노드들 중 리더를 하나만 사용하고, 데이터베이스 쓰기 작업은 해당 리더를 통해서만 진행한다면 이는 복잡한 충돌의 문제가 발생하지 않기 때문에, 이를 구현하는 것은 복잡하지 않으나, 다중 쓰기가 가능한 데이터베이스의 구현과 충돌 해결은 상당히 도전적인 문제입니다.
다중 노드에, 트랜잭션 브로드캐스팅 권한을 분배한다는 것은 쉽게 표현하면, 진짜 답지라고 표현될 수 있는, 절대적인 특정 시점에 모든 노드에 제출된 트랜잭션의 합인 global state 멤풀을 모두가 동시에 유지하는 것을 포기하고, 각자의 노드가 네트워크 전송 이슈 등으로 상태가 다를 수 있는 멤풀을 가지는 것이 허용되어야 한다는 의미입니다.
이를 더 쉽게 풀어쓰자면, 각각의 노드가 트랜잭션 제출을 받아 멤풀을 구성하고 있고, 인접한 노드들과 제출받은 트랜잭션을 서로 교환을 하긴 하니까, 어느 정도 동기화가 되어 있지만, 특정 시점에 모든 노드가 같은 멤풀 상태를 가지지는 않는다는 의미입니다.
하지만, 합의가 진행, 그러니까, 블록이 컨펌되어 나감에 따라, Eventually 하게만 각자가 가지고 있는 멤풀의 동기화 여부 등을 이용해 절대적인 정답을 맞혀나가면 된다는 것입니다.
DAG based consensus 알고리즘 중 하나인 Tusk를 블록체인에 대응해 쉽게 이해해 보도록 하겠습니다. DAG를 구성하는 꼭짓점 (Vertex)과 간선 (Edge)은 각각의 노드가 특정 추상적인 시점인 라운드(r)에서 가진 멤풀 상태를 꼭짓점, 통신이 이루어져 멤풀 상태가 동기화가 된 경우는 이를 간선으로 잇는 경우로 정의합니다. 이때, 멤풀 상태는 엄밀하게는 트랜잭션들의 모음이라 해서 트랜잭션 블록이라고 부릅니다.
Tusk 합의를 간략하게 표현해 가며 이해해 봅시다. 위의 그림은 노드가 4개가 있는 상황이고, 그리고 Wave 1과 Wave 2 라는 논리적인 시간 단위가 있습니다. 해당 시간을 이해하기 쉽게, 각각의 wave는 1개의 블록이 생성되고 합의되는 시간 구간이라고 이해하시면 됩니다. 그리고 wave 내에는, 추상적인 타임스탬프인 라운드가 있습니다. 이를 바탕으로 위 그림을 다시 보면, 오른쪽으로 갈 수록, 시간이 흐르는 상황이라고 보시면 됩니다.
네모로 표현되어 있는 꼭짓점은 각 라운드에서 각 노드의 멤풀 상태입니다. 시간이 지남에 따라, 각 노드 간에 멤풀 상태를 공유를 하고, 서로의 멤풀 상태에 대해 노드 간 합의를 하고 동기화를 하는데, 그 경우에 다음 라운드에서 간선으로 선을 잇습니다.
<Wave 1>
Wave 1에서는 r=3 시점에, r=1 시점의 리더를 선출합니다. 그림에서는 L1 트랜잭션 블록이 리더로 선출이 되었는데, 이 때, r=2 시점에 L1에 연결된 간선이 몇개가 되는지, 최소 정족수를 만족하는지 확인합니다. 여기서 최소 정족수는 2라고 가정하겠습니다.
빨간 선을 보면, L1에 연결된 간선이 하나밖에 없기 때문에, 최소 정족수를 만족시키지 못해 L1의 상태는 커밋되지 못합니다.
<Wave 2>
Wave 2 시점으로 넘어갑니다. 이번엔 파란색 꼭점이 리더로 선출이 되어있습니다. 라운드 4를 확인해 보면 L2는 최소 정족수인 2개의 간선이 연결되어 있기 때문에, 이는 유효한 것으로 판단되고 그래프상에서 L2와 동기화된 모든 멤풀들의 트랜잭션들은 Wave 2 시점에 블록에 포함되며 합의가 일어납니다. 이 때, L1은 L2와 간선을 통해 연결이 되어 있기 때문에, 이는 동기화가 일어났음을 의미하고, L1에 담겨있는 트랜잭션들은 L2가 합의가 되며 함께 합의가 진행됩니다.
그래프 관점에서 다시 오른쪽 그림을 보면, L1의 멤풀 상태는 연결된 간선이 별로 없기 때문에, 라운드 2에서는 그것(L1에만 들어있는 트랜잭션)을 아는 노드가 하나도 없고, 3이 되어서야 노드 2와 3과 4에 공유가 되었다고 이해할 수 있습니다. 이렇게 매 라운드마다 멤풀 상태의 즉시 동기화는 이뤄지지 못하지만, 오히려 트랜잭션 쓰기 처리를 모든 노드가 처리할 수 있고, 결국에는 DAG 구조를 이용해 동기화가 되고 나중에 컨펌이 되기 때문에, 트랜잭션을 분산으로 처리할 수 있게 되는 것입니다.
다시 한번 정리하면, 리더는 합의 과정에만 참여하고, 트랜잭션 전파는 각 노드가 독립적으로 점진적으로 진행해 나갑니다. 리더는 자신에게 연결된 그래프의 꼭짓점에 포함된 트랜잭션들만 합의에 포함해 나가며, 합의에만 집중하기 때문에, 네트워크 전체의 처리 성능은 증가합니다. 하지만, 유저 입장에서는, 트랜잭션들의 파이프라인이 어떻게 구성되었는지에 따라, 트랜잭션을 제출하고 컨펌되기 까지 레이턴시가 조금 더 길어질 수 있다는 단점이 있을 수 있습니다.
Future Of Consensus
블록체인의 합의 알고리즘은 비잔틴 장애 상황에서 Safety와 Liveness의 trade-off 관계 속에서 발전해 왔습니다. 현재 주목받고 있는 Monolithic Blockchain들은 대중화를 위해 처리 능력 향상에 초점을 맞춘 효율적인 합의 알고리즘들을 채택하고 있습니다. 하지만 블록체인의 발전을 위해서는 효율성뿐만 아니라 Robustness도 함께 고려되어야 할 것입니다. 또한 아직 큰 주목을 받지는 못하고 있지만, 행성 간 결제(Multi-planetary payment)와 관련된 합의 알고리즘 연구도 블록체인의 미래를 위해 중요한 방향이 될 수 있습니다.
블록체인 기술이 진정한 의미의 대중화를 이루기 위해서는 높은 처리 능력, 빠른 트랜잭션 컨펌 시간, Robustness, 그리고 새로운 사용 사례까지 아우르는 합의 알고리즘의 지속적인 발전이 필요할 것입니다. 연구자들과 개발자들의 끊임없는 노력을 통해 블록체인 합의 알고리즘은 더욱 진화하고, 블록체인 기술의 가능성을 넓혀갈 것으로 기대됩니다.
References
- Solana Wiki — Transactions
- Jito Labs — Solana Validator 101: Transaction Processing
- Fyeo — Aptos vs Solana a technical comparison
- Sei Forum — Parallel Transaction Message Processing
- Sei Forum — Optimistic Concurrency Control
- BOHM White paper
- Block-STM White paper
- Block-STM: Scaling Blockchain Execution with Rati Gelashvili | a16z crypto research talks
- Aptos Labs — How We Execute Over 160k Transactions Per Second on the Aptos Blockchain
- Sui Foundation — All About Paralleization
- [케블리] #48. 합의 알고리즘 이해하기 — PBFT Consensus Algorithm
- Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms (2023)
- Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus (2022)
- HotStuff: BFT Consensus in the Lens of Blockchain (2019)
