자료 : SoK: Sharding on Blockchain
지난 포스트 - SoK: Sharding on Blockchain 2
2.2 BFT Consensus Scalability 본문
2.2 BFT Consensus Scalability
Reducing the number of nodes. To tolerate f Byzantine nodes that can equivocate in a quorum system like PBFT, quorums must be intersected by at least f + 1 nodes [102]. Consequently, if a BFT protocol requires n = 3f + 1, its quorum size is at least 2f + 1. The smaller n means the lower communication cost incurred in tolerating the same number of faults; it also means that for the same number of nodes n, the network can tolerate more faulty nodes. One way to reduce the number of nodes is to randomly select a small set of consensus nodes, as a committee, to run a consensus process. A smaller consensus committee can lead to better throughput, as a smaller committee attains higher throughput due to lower communication overhead. Sharding technology reduces the consensus process within one shard. However, in this scenario, the security of each shard, e.g., the ratio of the number of faulty nodes to the size of a shard, will be the top concern. It can be mitigated by utilizing some mechanisms, e.g., the epoch randomness, to guarantee the “good majority” for each shard with a high probability [100]. Another way to reduce the number of nodes is to uti- lizetechniquestogetdownthenfrom3f +1to2f +1. Those techniques are mainly based on leveraging external components (e.g., the trusted hardware) or lessening the sys- tem models. For example, BFT-TO [48], a hardware-assisted BFT, with less replicas, shows that it is possible to imple- ment a Byzantine SMR algorithm with only 2f + 1 replicas by expending the system with a simple trusted distributed component. Similarly, there exist a few other algorithms to achieve the consensus with less replicas, such as A2M-BFT- EA [44], MinBFT [133], MinZyzzyva [133], EBAWA [132], CheapBFT [82], and FastBFT [97]. Besides, there also exist some other work to achieve the same purpose by lessening the system models. For example, the work in [1] improves the BFT threshold to 2f + 1 by utilizing a relaxed synchrony assumption.
Reducing communication complexity. PBFT protocol has been perceived to be a communication-heavy protocol. There is a long-standing myth that BFT is not scalable to the num- ber of participants n, since most existing solutions incur the message transmission of O(n2), even under favorable net- work conditions. As a result, existing BFT chains involve very few nodes (e.g., 21 in [75]). Even with a reduced network size, PBFT still has a communication complexity of O(n2). Byz- coin [90] proposed an optimization wherein the leader uses a collective signing protocol (CoSi) [128] to aggregate other node’s messages into a single authenticated message. By do- ing so, each node only needs to forward its messages to the leader and verify the aggregate message from the latter. In this way, by avoiding broadcasting, the communication com- plexity is reduced to O(n). Besides, there is some work [56] on utilizing trusted execution environments (TEEs) (e.g., In- tel SGX [50]) to scale distributed consensus. TEEs provide a protected memory and isolated execution so that the regular operating systems or applications can neither control nor observe the data being stored or processed inside them [64]. Generally, a trusted hardware can only crash but not be Byzantine. However, introducing trusted hardware into con- sensus nodes is expensive, and specific knowledge is needed to implement the protocol. Similarly, the security in this cate- gory can be mitigated by using cryptograhic primitives, such as threshold signatures [23] [125].
By splitting a network into multiple committees, sharding technology reduces the number of consensus nodes within committees and further reduces the communication com- plexity.
2.2 BFT Consensus Scalability
이번 섹션은 BFT (Byzantine Fault Tolerant) 합의의 확장성에 대해 다룬다.
해당 섹션에서는 기존의 BFT 합의 프로토콜이 확장성에 제한이 있는 문제를 다룬다. 일반적으로 BFT 합의는 합의 참여 노드 수가 증가할수록 성능 저하가 발생하며, 이는 네트워크 통신 및 메시지 교환의 복잡성으로 인한 것이다. 이러한 제한으로 인해 BFT 합의가 대규모 블록체인 네트워크에서 적용하기 어렵게 된다.
논문에서는 이러한 확장성 문제를 해결하기 위해 다양한 기술과 접근 방법을 제시한다. 이러한 기술은 프로토콜 디자인, 네트워크 구조, 노드 관리 및 메시지 전달 등 다양한 측면에서 개선될 수 있다. 또한 샤딩(sharding)과 같은 기술을 도입하여 합의 프로세스를 분할하고 병렬로 처리함으로써 확장성을 개선하는 방법도 제시된다.
블록체인의 샤딩에서도 합의가 필요하다. 대부분 BFT 합의 프로토콜에 의존하여 합의에 도달한다.
각 샤드는 독립적으로 거래를 처리하고 상태를 유지한다. 이 샤드가 네트워크의 일관성과 안전성을 유지하기 위해서는 샤드 간에 합의 메커니즘이 필요하다.
- 합의 메커니즘은 각 샤드에서 생성된 블록이 전체 네트워크에 반영되는 순서를 결정하는 역할
- 모든 샤드 간에 동일한 계정 상태 및 거래 내역을 유지
- 불일치와 중복을 방지
그런데, 대부분의 BFT는 확장성에 대한 제한이 있다. 논문에서는 PBFT를 예로 들어 확장성을 설명.
PBFT는 quadratic communication complexity(이차 통신 복잡성)으로 인해 약 12개의 노드 이상에서는 확장이 되지 않을 것. 그래서 일반적으로 BFT 프로토콜은 f 개의 비잔틴 오류를 허용하기 위해 필요한 노드 수를 줄이거나, 프로토콜의 통신 복잡성을 줄여 더 큰 네트워크 크기를 지원한다.
quadratic communication complexity(이차 통신 복잡성) 특정 합의 프로토콜이 노드들 사이의 통신에 소요되는 리소스와 메시지 교환의 양에 관한 개념 아래의 특징으로 인해 합의 프로토콜의 확장성에 직접적인 영향을 미친다.
- 특징 : 노드 수와 관련하여 선형적으로 증가하지 않고, 노드 수의 제곱에 비례하여 증가
1) (BFT 프로토콜에서) 노드 수를 줄이는 방법
작은 합의 위원회(committee)를 무작위로 선택하여 합의 과정을 실행하는 방법
PBFT와 같은 퀴럼 시스템에서 f개의 비잔틴 노드를 허용하기 위해서는 퀴럼에 적어도 f+1개의 노드가 교차해야(intersected) 한다.
quorum system(퀴럼 시스템)에서 quorum은 “합의에 참여하는 노드들의 그룹”
위에서 “교차한다”는 말은 “f+1개의 노드가 공통적으로 포함되어 있어야 한다.” 퀴럼은 노드들의 집합이기 때문에 어떤 한 퀴럼에 속한 노드 중에는 다른 퀴럼에도 속하는 노드가 있어야 한다.그래서 BFT 프로토콜의 경우,
- 노드 수 n은 3f+1로 요구
- 이에 따라 퀴럼 크기는 최소한 2f+1이 된다.
n이 더 작다면, 더 적은 노드로도 합의를 도달할 수 있어서 통신에 드는 비용을 낮출 수 있다.
반면에 같은 n을 가진 경우, 네트워크는 더 많은 오류 노드를 허용할 수 있다.
이렇게 합의 위원회(committee)를 줄이게 되면 통신 오버헤드(통신 비용)가 낮아져 더 높은 처리량을 얻을 수 있지만, 보안에 문제가 생길수 있다. 그래서 오류 노드 수와 샤드의 크기 비율을 고려해야 한다.
오류 노드 수와 샤드의 크기 비율을 고려하기 위해, “에포크 난수(epoch randomness)”를 활용할 수 있다.
- “에포크 난수(epoch randomness)”는 특정 시간 단위로 생성되는 난수로서, 각 샤드는 자신의 에포크 난수를 갖게 된다. 이 난수를 사용하여 각 샤드 내에서 “좋은 다수(good majority)”를 형성할 수 있는 노드의 비율을 조절한다.
3f+1을 2f+1로 줄이는 기술을 활용하는 방법
주로 외부 구성 요소(예: 신뢰할 수 있는 하드웨어)를 활용하거나, 시스템 모델을 단순화하는 방식으로 구현한다.
- 외부 구성 요소(신뢰할 수 있는 하드웨어)
- BFT-TO: 하드웨어 지원 BFT로서, 적은 복제본을 가지고도 2f+1개의 복제본으로 비잔틴 SMR 알고리즘을 실행할 수 있다.
- 노드(복제본)의 수를 최소화하여 합의를 달성하는 알고리즘
- A2M-BFT-EA, MinBFT, MinZyzzyva, EBAWA, CheapBFT, FastBFT…
- 시스템 모델을 단순화
- 단순화된 동기화 가정을 사용하여 BFT 임계값을 2f+1로 개선
- 일반적으로 BFT 알고리즘에서는 3f+1개의 노드가 동시에 오류를 발생시키는 것을 허용해야 안전한 합의를 달성
- 단순화된 동기화 가정을 사용하여 BFT 임계값을 2f+1로 개선
- 외부 구성 요소(신뢰할 수 있는 하드웨어)
2) 통신 복잡성을 줄이는 방법
PBFT 프로토콜은 통신 비용이 많이 드는 프로토콜이다.
“통신 비용이 많다.”는 뜻은 다음과 같이 해석 될 수 있다.
- 네트워크 대역폭(Bandwidth): 메시지 전송에 필요한 데이터 양은 네트워크 대역폭을 소모합니다. 높은 대역폭 요구사항은 더 많은 데이터를 전송하고 처리해야 함을 의미합니다.
- 네트워크 지연(Latency): 메시지가 발신자에서 수신자로 전달되는 데 걸리는 시간입니다. 지연 시간이 길면 메시지의 전송과 응답 시간이 느려져 전체 통신에 소요되는 시간이 증가합니다.
- 처리량(Throughput): 시스템이 처리할 수 있는 메시지 수의 양입니다. 처리량이 낮으면 메시지의 처리가 지연되거나 병목 현상이 발생할 수 있습니다.
- 계산 리소스(Computational Resources): 메시지를 처리하는 데 필요한 계산 작업과 연산 리소스가 소모됩니다. 암호화, 해시 함수, 서명 검증 등의 작업은 계산 리소스를 요구합니다.
O(n^2) → O(n)
기존의 BFT 프로토콜은 노드 수가 많아지면 통신량이 O(n^2)로 증가하여 확장성이 좋지 않다는 오해가 있었고, 이로 인해 기존의 BFT 체인은 매우 적은 수의 노드만을 포함하고 있었다.
해결책 :
Byzcoin은 기존의 BFT 프로토콜의 통신 복잡도를 개선하기 위해 최적화를 제안했다. 이 최적화는 리더가 다른 노드의 메시지를 한 개의 인증된 메시지로 집계하는 것.
- 각 노드는 자신의 메시지를 리더에게 전달하고 후자로부터 집계된 메시지를 확인하기만 하면 된다.
- 이렇게 하면 브로드캐스팅을 피함으로써 통신 복잡도가 “O(n)”으로 줄어든다
“신뢰할 수 있는 실행 환경(TEE)”을 활용하는 방법
예를 들어, Intel SGX
- 인텔이 개발한 하드웨어 보안 기술
- SGX는 프로그램이 실행되는 동안 메모리 영역을 보호하고 외부로부터의 액세스를 차단하여 프로그램의 기밀성과 무결성을 강화
- 일반적으로 신뢰할 수 있는 하드웨어는 고장만 날 수 있고, 비잔틴 오류를 발생시키지는 않는다.
- 그러나 비용이 많이 든다.
다음에 계속…