합의는 분산 컴퓨팅에서 가장 근본적인 문제 중 하나이다.
이것은 결정론적 상태 시스템으로 모델링 되는 replicating services를 위한 일반적인 접근 방식인 State Machine Replication(SMR)에서 중요하다.
이 접근 방식의 핵심 아이디어는 서비스 복제본이 동일한 초기 상태에서 시작하고, 그 후에 요청(또는 트랜잭션)을 동일한 순서로 실행함으로써 복제본이 서로 동기화되도록 하는 것이다.
SMR 방식에서 합의의 역할은 모든 복제본이 동일한 순서로 트랜잭션을 수신하도록 보장하는 것이다. 기존 SMR 기반 시스템의 배치는 데이터 센터 설정(지역 네트워크)에서 이루어지며, 소수의 복제본(3~7개)을 가지며 일반적으로 단일 관리 도메인(예: Chubby)에 속한다.
그 결과 일반적인 형태의 실패(특히 악의적이거나 비잔틴 결함과 같은 형태)는 무시할 수 있는 확률로 발생한다고 간주하므로 충돌과 같은 경미한 실패만 처리한다.
최근 암호화폐와 블록체인의 성공으로 SMR 기반 시스템의 설계와 배치에 대한 새로운 도전 과제가 제기되었다. 광범위한 지역 네트워크에서 많은 수의 노드(수백 개 또는 수천 개) 간에 합의를 이끌어내야 하는데, 이들 노드는 같은 관리 도메인에 속하지 않으며, 일부 노드는 악의적으로 행동할 수 있다. (비잔틴 결함)
이전의 데이터 센터 배치와는 달리 블록체인 시스템에서는 노드가 다른 노드의 일부에만 연결되기 때문에 통신은 Gossip 기반의 P2P 프로토콜을 통해 이루어진다.
비잔틴 결함 허용 합의(또는 SMR)에 대한 고전적인 학술 문헌의 주요 초점이 다르기 때문에 이러한 새로운 요구조건은 존재하지 않는 설계와 알고리즘을 요구한다.
본 논문에서는 Tendermint라고 하는 BFT SMR 플랫폼의 핵심인 새로운 비잔틴 결함 허용 합의 알고리즘을 설명한다.
Tendermint 플랫폼은 Go 언어로 작성된 고성능 BFT SMR 구현체, 합의 계층 위에서 독립적이고 결정론적인 응용 프로그램을 구축하기 위한 유연한 인터페이스, 배포 및 관리를 위한 도구 모음으로 구성되어 있다.
Tendermint 합의 알고리즘은 PBFT SMR 알고리즘과 인증된 결함에 대한 DLS 알고리즘에서 영감을 받았다.
DLS 알고리즘과 유사하게 Tendermint는 라운드 단위로 진행되며, 각 라운드에는 전용 제안자(코디네이터 또는 리더)가 있고, 프로세스는 일반적인 과정인 새로운 라운드로 진행된다. (제안자가 PBFT에서와 같이 충분한 프로세스를 통해 결함이 있거나 의심되는 경우가 아닐 때)
각 라운드의 통신 패턴은 PBFT의 "normal" 상황과 매우 유사하다. 바람직한 조건(올바른 제안자, 올바른 프로세스 간 적시성과 신뢰성이 있는 통신)에서 Tendermint는 세 가지 통신 단계(PBFT와 동일)를 통해 결정을 내린다.
Tendermint 합의 알고리즘의 주요 혁신은 새로운 종료 메커니즘이다.
부분 동기 시스템 모델에 대한 기존 BFT 합의(및 SMR) 알고리즘은 일반적으로 종료를 위해 그림 1에 나와있는 통신 패턴에 의존한다.
그림 1은 프로세스가 새로운 라운드를 시작할 때 제안자 변경 중에 교환되는 메시지를 보여준다. 이것은 (Global Stabilization Time <GST> 이후) 시스템을 일원성(configuration)으로 이끌어 나갈 올바른 제안자가 있는 라운드가 존재한다는 것을 보장한다.
직관적으로, 모든 올바른 프로세스가 제안된 값을 수락하고, 올바른 프로세스 간의 통신이 적시성과 신뢰성을 가진다면, 모든 올바른 프로세스가 결정을 내린다.