원작자: Soul Machine
원작자: Soul Machine
Tendermint는 pBFT 알고리즘의 변형인 Tendermint의 오픈 소스 프로젝트입니다.Tendermint와 pBFT의 관계는 Raft와 Paxos의 관계와 유사합니다.Tendermint는 pBFT의 단순화된 버전입니다.
알고리즘 핵심 프로세스
Tendermint 핵심 알고리즘 흐름은 아래 그림과 같습니다.
Tendermint 알고리즘은 먼저 임의로 일부 노드를 Validator로 선택한 다음(검증 노드 선택 방법은 아래 "검증 노드 선택 방법" 참조), 검증자 중 하나를 Proposer 노드로 선택합니다. Proposer 노드는 전체 네트워크의 모든 트랜잭션을 모니터링하고 수집하기 시작하고 몇 분 후에 새로운 블록을 조립하여 전체 네트워크에 브로드캐스트합니다. 이것이 제안 블록입니다. 이 제안 블록을 수신한 후 전체 네트워크의 모든 유효성 검사기 노드는 이 블록의 모든 트랜잭션을 읽고 하나씩 검증하기 시작하며 문제가 없으면 사전 투표 메시지를 보내 이에 동의함을 표시합니다. 블록에 불법 거래가 있는 것으로 밝혀지면 반대 투표를 하고 이 투표 메시지는 모든 검증자 노드에 방송되므로 각 검증자 노드는 투표 메시지뿐만 아니라 다른 사람들의 투표 메시지도 수집합니다.합의된 투표 수가 2/3를 초과하면 투표의 두 번째 단계인 사전 커밋 투표 메시지가 전송되고 각 노드도 모니터링 및 사전 수집됩니다. 투표 메시지를 커밋합니다. 검증자 노드가 수집한 사전 커밋 투표 수가 2/3를 초과하면 블록이 대다수의 사람들에 의해 승인되었음을 의미하며 이 블록을 안전하게 로컬 블록체인에 작성하고 끝에 추가할 수 있습니다. 완전한 커밋. 동시에 블록 높이가 1 증가하고 제안자 노드 인덱스도 1 증가하여 다음 라운드(라운드)에 진입하고 새로운 블록을 제안하기 시작합니다.
위의 설명은 90%의 정상적인 프로세스, 즉 파란색 화살표로 표시된 큰 주기입니다. 다음으로 내부 원의 빨간색 화살표로 표시된 작은 루프에 대해 이야기하겠습니다. 대부분의 경우 블록은 한 라운드만 있으면 확인을 완료하고 합의에 도달할 수 있지만 네트워크 상태가 좋지 않고 타임아웃이 자주 발생하는 경우가 있는데 이 때 내부 원의 빨간색 프로세스에 진입하게 됩니다. 매 라운드마다 한 명의 제안자만이 블록을 생성할 수 있는 권한을 가지므로 이 제안자가 전화를 끊거나 네트워크가 좋지 않아 시간이 초과되면 어떻게 해야 할까요? 모든 사람이 이 제안자를 영원히 기다리는 것은 불가능합니다.알고리즘은 분명히 그렇게 어리석게 설계되지 않았으며 명백한 단일 실패 지점이 있습니다. 제안자 노드의 제안 단계에서 모든 검증자 노드는 타이머를 시작하고 타임아웃 기간을 T로 설정합니다(T 값은 네트워크 조건에 따라 동적으로 계산됨). 이 시간 내에 제안자 노드로부터 새로운 메시지가 수신되지 않으면 시간 블록, 제안자 노드가 중단된 것으로 간주하고 모든 유효성 검사기 노드는 계속 기다리지 않고 제안자 노드에서 빈 블록을 수신한 것처럼 로컬 시스템에 특수 구조로 빈 블록을 즉시 생성합니다. 따라서 시간 T 내에 일반 블록이든 빈 블록이든 제안 블록이 수신됩니다. 그런 다음 이 블록에 대한 사전 투표 및 사전 커밋 투표를 진행합니다. 제안자가 전화를 끊으면 대부분의 유효성 검사기는 빈 블록을 보게 되므로 빈 블록이 다수의 득표를 얻고 커밋 단계에 들어갑니다. 빈 블록을 커밋할 때 실제로 빈 블록을 블록체인에 쓰지 않고 아무 것도 쓰지 않으며 블록 높이도 자동으로 증가하지 않고 변경되지 않은 상태로 유지됩니다. 유휴 상태입니다. 이번 라운드가 끝나고 다음 라운드가 시작되면 검증인이 Proposer로 교체되어 현재 중단된 Proposer가 전체 네트워크에 갇히지 않도록 합니다.
네트워크 통신 복잡성
텐더민트의 네트워크 통신 복잡도는 O(n2)인데, 2개의 투표 단계에서 각 검증자 노드가 2/3 이상의 투표 메시지를 수집해야 하고 네트워크에서 보내는 데이터 패킷의 수가 n2이기 때문에 네트워크 동심 복잡도는 오(n2). 제안 단계에서 새 블록은 모든 검증자에게만 수신되면 되며 네트워크 통신 복잡도는 O(n)입니다. 전체적으로 O(n2)입니다. 네트워크 통신의 복잡성은 O(n2)이며 Tendermint의 노드 수가 너무 많지 않을 것으로 예상되며 너무 많으면 네트워크 통신에 병목 현상이 발생하므로 Private 및 Alliance에 적합한 Tendermint 이것은 또한 논문의 17페이지에 명시되어 있습니다. 한 가지 요점: Tendermint는 컨소시엄 또는 조직 간 논리에 최적화된 솔루션입니다. 그것은 또 다른 이야기입니다.
네트워크 가설
네트워크에 대한 Tendermint의 요구 사항은 네트워크가 반동기화되어야 한다는 것입니다. Tendermint는 Propose 단계에서 타임아웃 메커니즘을 가지고 있는데, 이 타임아웃 기간은 일정하지 않고 동적으로 변경되므로 이 단계에서 네트워크는 반동기화되어야 합니다. 사전 투표 및 사전 커밋 투표 단계에서는 네트워크에 대한 요구 사항이 없습니다. 즉, 네트워크가 비동기적입니다. 따라서 Tendermint의 네트워크 요구 사항은 반 동기식입니다.
pre-vote와 pre-commit 투표 단계에서 네트워크가 비동기화되기 때문에 투표의 2/3 이상이 수집되지 않으면 모든 검증인 노드가 무기한 대기하게 되어 전체 시스템이 정체됩니다. Tendermint는 더 강력한 Finality를 대가로 Liveness를 타협했습니다.
예를 들어 제안자 노드가 특정 라운드에서 새 블록 blockX를 브로드캐스트하고 유효성 검사기 A 노드가 새 블록을 제 시간에 수신하지 않으면 A는 마치 블록에서 받은 것처럼 로컬 시스템에 빈 블록을 구성합니다. 제안자가 도착하여 사전 투표 없음 투표 메시지를 보낸 다음 사전 투표 루프에 진입하고 타임아웃 타이머를 시작한 다음 빨간색 내부 서클 루프에 진입하면 A가 네트워크를 모니터링하고 투표 정보를 수집하기 시작합니다.
빈 블록이든 블록X든 수집된 투표 수가 지정된 시간 내에 2/3를 초과하지 않으면 총 투표 수가 2/3를 초과할 때까지 무기한 대기
총 투표 수의 2/3 이상을 모은 후 빈 블록에 대한 투표 수가 2/3를 초과하면 빈 블록에 투표하기 위해 사전 투표 nil을 발행하고 여전히 빨간색 내부 원에 머물러 있습니다. ; blockX에 대한 투표 수가 2/3를 초과하는 경우 3. blockX에 사전 투표를 보내고 파란색 바깥쪽 원으로 전환하고 빈 블록과 blockX에 대한 투표 수가 2/3를 초과하지 않으면 a를 보냅니다. pre-vote nil 메시지는 빈 블록에 투표하고 여전히 빨간색 내부 원에 있는 사전 커밋 단계에 들어갑니다.
A가 pre-commit nil 투표 메시지를 보내면 A는 여전히 빨간색 내부 원에 머물며 pre-commit 프로세스는 위와 유사합니다. 대체로 빨간색 내부 원의 프로세스는 네트워크가 반동기식이라고 가정해야 합니다.
최종성과 생동감
Tendermint의 Finality는 Deterministic한 반면 Bitcoin의 Finality는 Probabilistic합니다.Tendermint는 Bitcoin보다 Finality가 더 강합니다.
그러나 Liveness 측면에서 예를 들어 네트워크가 분할될 때 Tendermint는 이론적으로 중단될 수 있으며 새로운 트랜잭션을 작성할 수 없는 반면 Bitcoin은 각각 독립적으로 작동하는 두 개의 포크로 분할될 수 있으며 새로운 트랜잭션이 계속될 수 있습니다.
잠금 메커니즘
위의 그림에는 그림에 표시되지 않은 묵시적 잠금 메커니즘이 실제로 있습니다. 예를 들어 특정 R 라운드에 A, B, C, D의 4개의 검증자 노드가 있고,
제안 단계에서 제안자 노드는 새로운 블록 blockX를 방송합니다.
A는 타임아웃 기간 내에 새로운 블록을 받지 못하여 사전투표 nil을 외부에 방송하고, B, C, D 모두 수신하여 사전투표를 blockX에 방송
이제 4개의 노드가 커밋 전 단계에 진입했습니다. A는 빨간색 내부 원에 있고 B, C, D는 파란색 외부 원에 있습니다.
A가 네트워크 상태가 좋지 않고 지정된 시간 내에 blockX에 대해 2/3 이상의 투표를 받지 못했다고 가정하면 빈 블록에 투표하기 위해 사전 커밋 nil 투표 메시지만 보낼 수 있습니다.
D는 B와 C의 사전 투표 메시지와 자신의 사전 투표 메시지를 받았고 2/3를 초과하여 D는 로컬 블록체인에서 blockX를 커밋했습니다.
B와 C의 네트워크에 문제가 있어 D는 pre-commit 메시지를 받을 수 없는데 이는 B와 C가 blockX에 대해 2표, 빈 블록에 대해 1표만 볼 수 있기 때문이다. 2/3, 따라서 B와 C C는 빈 블록만 커밋할 수 있고 높이는 변경되지 않고 R+1 라운드에 들어가며 A는 블록X에 대해 2표, 빈 블록에 대해 1표만 볼 수 있으며 빈 블록만 커밋할 수 있습니다. , 높이는 R+1 라운드로 동일하게 유지됩니다.
R+1 라운드에서는 새로운 사랑 제안자가 새로운 블록 blockY를 제안했기 때문에 A, B, C가 합의에 도달하여 blockY를 제출할 수 있으므로 동일한 높이에서 두 개의 blockX와 blockY 블록이 발생하여 포크가 발생합니다. .
Tendermint는 특히 7단계에서 잠금 메커니즘을 추가했습니다. 제안자가 새로운 블록 blockY를 생성하더라도 A, B 및 C는 6단계에서 자신의 사전 커밋 블록에만 잠글 수 있습니다. 6 1단계에서 빈 블록에 투표하면 R+1 라운드에서 빈 블록에만 계속 투표할 수 있고 6단계에서 B가 blockX에 투표하면 새 라운드에서는 영원히 blockX에만 투표할 수 있습니다. , C도 비슷합니다. 이런 식으로 R+1 라운드에서 빈 블록에 대해 1표, blockX에 대해 2표가 주어지고 최종적으로 blockX에 대한 합의에 도달하면 A, B 및 C가 모두 blockX를 커밋합니다. 이는 D와 일치합니다. , 충돌이 없습니다.
텐더민트 대 pBFT
Tendermint와 pBFT는 매우 유사해 보입니다. 예를 들면 다음과 같습니다.
모두 악성 노드의 1/3 이상을 허용하지 않는 BFT 유형 알고리즘에 속합니다.
텐더민트의 제안->사전 투표->사전 커밋 3단계는 pBFT, 사전 준비, 준비, 커밋의 3단계에 해당합니다.
모두 시간이 초과되면 제안자/기본
Tendermint는 pBFT에 비해 두 가지 단순화가 있습니다.
Tendermint에는 pBFT의 View Change 단계가 없습니다.Tendermint는 시간 초과 상황과 정상 상황을 교묘하게 통합하여 하나의 형태로 통합합니다.그들은 모두 제안->사전 투표->사전 커밋의 3단계이며 새로운 블록만 있습니다. 타임아웃이 발생하면 생성되는 특수 빈 블록입니다. 제안자 전환은 빈 커밋 블록을 제출하여 트리거되는 반면 pBFT에는 기본 회전을 트리거하는 별도의 보기 변경 프로세스가 있습니다.
The state of each replica includes the state of the service, a message log containing messages the replica has accepted, and an integer denoting the replica’s current view.
View Change를 제거하는 것 외에도 Tendermint는 다른 곳에서 단순화되며 모든 Tendermint 정보는 블록체인에 저장됩니다. pBFT가 1999년에 제안되었기 때문에 그 당시에는 블록체인이라는 것이 없었기 때문에(블록체인은 2009년 비트코인이 등장한 이후에만 가능했습니다), pBFT의 모든 노드는 일관된 데이터를 가지지만 데이터는 분산된 방식으로 저장됩니다. pBFT의 각 노드 데이터에는 다음이 포함됩니다.
블록체인은 분산 데이터베이스입니다.예를 들어 MySQL과 같은 DBMS 데이터베이스가 등장하기 전에 사람들은 데이터를 파일에 작성하고 하드 디스크에 저장하여 다양한 이상한 파일 형식과 구성 방법을 발명했습니다. MySQL을 사용하면 데이터 관리가 훨씬 더 편리해집니다. 마찬가지로 텐더민트는 모든 데이터를 블록체인에 저장하고, pBFT는 블록체인과 같은 분산형 데이터베이스가 없으며, 모든 풀노드는 자체적으로 하드디스크에서 데이터를 관리해야 합니다. 하드 디스크 공간 절약, 체크포인트 도입 개념, 데이터 관리에만 번거로운 단계가 많습니다.
Tendermint와 pBFT의 관계는 Raft와 Paxos의 관계와 유사합니다.Tendermint는 블록체인 시나리오를 위한 pBFT의 단순화된 버전인 pBFT의 단순화된 버전입니다.
검증인을 선택하는 방법
첫째, 제네시스 블록에서 검증자 노드 집합을 정적으로 설정할 수 있으며, 둘째, 체인이 시작되면 ValidatorUpdate 메시지를 전송하여 검증자 목록을 업데이트할 수 있습니다. 유효성 검사기 업데이트 보기
문서상에 이 곳에 대한 이야기가 많지 않고 비교적 원시적인 것 같습니다.알고랜드의 암호화 복권과 유사한 랜덤 샘플링 알고리즘은 없습니다. 하지만 이 공간은 언제든지 확장될 수 있어야 합니다.
Proposer를 차례로 변경하는 방법
유효성 검사기 노드 그룹이 선택된 후 전체 네트워크의 모든 유효성 검사기 노드는 예를 들어 원형 배열에 복사본을 저장합니다.
일반적으로 블록은 1회차에 생성되는 경우가 대부분이며, 네트워크 상태가 좋지 않을 경우 여러 회차를 거쳐 블록이 생성될 수 있습니다. 어쨌든 매 라운드마다 새로운 검증인이 Proposer로 나오게 되며 순환 규칙은 단순히 순차적으로 증가하는 것입니다. 첫 번째 유효성 검사기가 선택되고 마지막 유효성 검사기에 도달한 후 0으로 재설정되어 무한 루프됩니다.
그런 다음 합의 알고리즘을 시작합니다. 0차 라운드에서는 포지션이 0인 검증인이 제안자 노드로 선택됩니다. 1차 라운드에서는 포지션이 1인 검증인이 선택됩니다. 두 번째 라운드에서는 포지션이 2인 검증인이 제안자로 선정되고 마지막에 도달하면 0으로 재설정됩니다. 무한 루프.
이 라운드 로빈 전략은 시간 초과 제안자 노드를 효과적으로 건너뛸 수 있습니다. 제안자 노드가 끊기거나 네트워크가 열악한 경우 대부분의 노드는 제 시간에 새 블록을 수신할 수 없으므로 시간 초과 후 각 검증 노드는 로컬에서 빈 블록을 구성하고 투표 메시지를 브로드캐스트합니다. 투표, 투표 및 사전 커밋, 마지막으로 빈 블록을 커밋합니다. 이는 아무것도 하지 않는 것과 동일하며 동일한 높이로 새 라운드를 시작합니다. 각각의 새로운 라운드가 시작되기 때문에 순서대로 다음 Proposer로 교체되기 때문에 끊기는 Proposer 노드는 자연스럽게 건너뛰고 알고리즘은 자동으로 계속될 수 있습니다.
라운드 로빈 전략은 너무 단순하고, 악당들이 다음 검증인이 누구인지 쉽게 예측할 수 있으므로 사전에 계획을 세우고 검증인에 대한 DDoS 공격 또는 기타 공격을 실행할 수 있습니다. Tendermint의 솔루션은 IP 주소를 외부 세계에 노출하지 않고 모든 유효성 검사기 노드를 Sentry Node 뒤에 배치하는 것입니다.
계속하려면
참조
Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
Tendermint: Consensus without mining
