원작자: Soul Machine
FLP 불가능의 원칙으로 인해,
No completely asynchronous consensus protocol can tolerate even a single unannounced process death
따라서 순전히 비동기 네트워크를 위한 합의 알고리즘을 설계하는 데 시간을 낭비하지 마십시오. 해결책은 네트워크에 대한 요구 사항을 강화하고 네트워크가 동기식 또는 부분 동기식(비동기에서 동기식 또는 반동기식으로, 네트워크 상태가 더 좋아짐)이 되도록 요구하거나 완결성에 대한 요구 사항을 완화하고 결정론적 완결성을 요구하지 않는 것입니다. , Probabilistic Finality만 있으면 됩니다. 두 가지를 동시에 하는 것도 가능합니다.
표 1 다양한 합의 알고리즘 비교
위 표의 내용은 아래에서 자세히 설명합니다.
Finality
Finality는 Safety, Consistency와 비슷해 보이지만 다른 것 같아 매우 혼란스럽습니다.
간단한 이해를 위해 Finality, Safety 및 Consistency는 동의어, 즉 Finality=Safety=Consistency라고 생각할 수 있습니다.
더 깊은 이해를 위해 Finality는 복잡하다고 생각합니다. Finality>Safety>Consistency입니다. 일관성은 Hadoop과 같은 신뢰할 수 있는 환경과 비트코인과 같은 신뢰할 수 없는 환경을 포함한 모든 분산 시스템에 적용 가능합니다. 안전은 비잔틴 환경에 적용됩니다. 최종성은 블록체인 시나리오의 용어이며 블록체인은 비잔틴 시나리오입니다 -블록체인 외에 블록체인 솔루션). 일관성은 CAP 이론의 C로, 최종성보다 더 일반적이고 요구 사항이 적습니다. Finality는 Consistency보다 더 많고 더 강력한 의미를 내포하고 있습니다. 최종성은 다음 의미를 모두 포함합니다.
모든 노드의 데이터는 일관성이 있어야 합니다. 클라이언트는 모든 노드에 읽기 작업을 보내고 결과는 동일해야 합니다. 이것은 CAP에서 언급한 Consistency로 Hadoop과 같은 신뢰할 수 있는 환경과 Bitcoin과 같은 신뢰할 수 없는 환경을 포함한 모든 분산 시스템에 적용되는 용어입니다.
모든 노드는 상호 갈등과 분열의 상태, 즉 안전에 들어가지 않도록 해야 합니다. 이 용어는 Byzantine 내결함성 분야에 적용됩니다.Byzantine과 같은 개방형 환경에서 악의적인 노드는 두 개의 충돌하는 메시지(예: 이중 지출 트랜잭션)를 브로드캐스트하여 전체 네트워크의 모든 노드가 분할 상태에 빠지게 합니다. , 일관된 달성이 불가능하여 안전의 본질을 파괴합니다. 모든 비잔틴 합의 알고리즘은 전체 네트워크의 안전을 보장하기 위해 악의적인 노드의 문제를 처리해야 합니다.
트랜잭션이 블록에 들어가면 취소할 수 없어야 합니다. 즉, 불변성입니다. 블록체인 시나리오에서 안전을 보장하기 위해서는 악의적인 노드가 발행한 이중 지출 거래 문제를 처리해야 할 뿐만 아니라 악의적인 노드가 블록으로 패키징된 거래를 취소하는 것을 방지해야 합니다. 블록체인은 단일 연결 목록과 선형 구조이기 때문에 악의적인 노드는 이론적으로 오래된 블록에서 시작하여 더 긴 새 체인을 포크하고 전송한 모든 트랜잭션을 취소하고 자신의 돈을 다시 보냅니다(또 다른 형태의 이중 지출)
요약하면 최종성=일관성 + 안전성 + 불변성입니다.
Liveness
활성도는 CAP의 가용성과 동일하다고 간주할 수 있습니다. 해저 광케이블이 끊어지는 등 네트워크에 파티션이 발생하고 글로벌 인터넷이 두 부분으로 나뉘면 전체 블록체인 시스템이 정상적으로 새 트랜잭션을 작성할 수 있습니까? 나는 Finality의 합의 알고리즘을 좋아한다. 이때 나는 무한정 기다리는 것을 선택할 것이다. 새로운 거래는 해저 광 케이블이 수리되고 양쪽의 인터넷이 상호 운용될 때까지 쓸 수 없다. 나는 Availabilty의 합의 알고리즘을 좋아한다. 이때 두 사람은 네트워크는 독립적으로 작동하고 데이터는 분리되며 전체 노드의 데이터는 일관성이 없게 됩니다.
예를 들어 Tendermint는 Deterministic Finality를 추구하기 위해 Liveness를 희생하는 유형입니다. 해저 케이블이 끊어지고 네트워크가 두 편으로 나뉜다고 가정하면 각 편에 검증인의 절반이 있으므로 투표 및 커밋 단계에서 각 측의 모든 검증인은 특정 제안 블록에 100% 투표하고 수신만 할 수 있습니다. 제안 블록의 최대 50% 투표는 2/3에 도달할 수 없으므로 전체 블록체인 네트워크는 2/3 투표가 수집될 때까지 무기한 대기합니다. 이 대기 시간 동안 다음 블록을 생성할 수 없고 새로운 트랜잭션을 작성할 수 없으며 전체 네트워크가 마비됩니다.
비트코인이 이런 종류의 네트워크 분할에 직면하면 비트코인 시스템의 두 부분이 계속 앞으로 나아갈 것이며 새로운 트랜잭션을 작성하여 새로운 블록을 생성할 수 있습니다.해저 케이블이 수리되고 양쪽의 인터넷이 연결되면 병합을 선택합니다.
해저 광 케이블이 끊어지기 전에는 다음 그림과 같이 전 세계 모든 전체 노드의 상태가 일관됩니다.
해저 광 케이블이 끊어지면 글로벌 네트워크가 두 부분으로 나뉘고 두 부분이 독립적으로 블록을 생성합니다.이 때 양측은 일관성이 없지만 여전히 선형 블록 체인이라고 생각하여 서로를 인식할 수 없습니다. , 다음 그림과 같이:
왼쪽과 오른쪽에서 여전히 10분마다 새로운 블록이 채굴되지만 왼쪽의 block07과 오른쪽의 block07의 블록 해시는 동일하지 않습니다. 현재 Bitcoin 네트워크는 계속 사용할 수 있지만 Finality는 파괴됩니다.
해저 광 케이블을 수리할 때 이때 양측은 블록을 서로 동기화하고 다음 그림과 같이 포크가 있음을 알게 됩니다.
이제 세상의 모든 풀노드의 상태는 위의 그림이 되고 포크가 있는데 양쪽 높이가 모두 8이므로 어떤 포크가 맞는지 판단할 수 없다. 마이너 지원 및 어느 쪽이 중요한지 Ligao, 어느 쪽이 먼저 새 블록을 가지고 있는지, 어느 쪽이 이기고 더 짧은 체인이 폐기되는지 예를 들어, 오른쪽에 새 블록이 먼저 있으면 오른쪽이 이기고, 왼쪽 포크는 폐기됩니다.모든 전체 노드의 데이터는 다시 선형 블록 체인이 되어 아래 그림과 같이 합의에 도달합니다.
실제로 해저 광케이블이 연속적이고 네트워크에 파티션이 없어도 두 명의 채굴자가 동시에 새로운 블록을 파는 경우가 종종 발생하는데 이때 누가 운이 좋은지 경쟁을 하게 되는데, 그리고 다음 새 블록이 상속하는 포크가 이기게 됩니다. 즉, 비트코인은 이론적으로 결정론적으로 일관된 상태를 갖지 않을 것이며 포크는 언제든지 어떤 높이에서도 나타날 것이므로 비트코인은 더 강한 라이브니스를 위해 약간의 최종성을 희생합니다.
Network Assumption
모든 분산 합의 알고리즘에는 네트워크에 대한 암묵적인 가정이 있습니다.
먼저 네트워크 분류에 대해 이야기하겠습니다.
동기화: 메시지는 특정 시간 T 내에 전달되어야 합니다. 상한 값 T는 알려진 상수이며 모든 노드가 이를 알고 있습니다. 메시지가 T 시간 내에 전달되지 않으면 메시지를 계산하지 않고 노드는 메시지가 손실되었다고 생각하고 계속 기다리지 않습니다. 모든 노드는 질서정연하며 T가 지나갈 때마다 한 걸음 앞으로 나아가는데 매우 깔끔하다.
반 동기: 메시지는 특정 시간 T 내에 전달되어야 하지만 T의 값은 고정된 값이 아니라 동적으로 변경됩니다. 예를 들어 네트워크 상태에 따라 동적으로 계산됩니다. 모든 노드
비동기: 메시지는 언제든지 도착하며 매우 빠르거나 매우 느릴 수 있습니다. 요컨대 명확한 상한(상한) 또는 무한정 지연이 없습니다. 아무리 늦게 도착하더라도 메시지는 노드는 메시지를 수락하고 처리해야 하며 단순히 시간 초과로 인해 메시지를 폐기할 수 없습니다.
네트워크 상의 비트코인은 네트워크가 동기화되어 있고 제한 시간은 약 10분이라는 가정하에 채굴자가 블록을 파낸 후 전체 네트워크에 브로드캐스트합니다. 이때 전체 비트코인 시스템은 이 블록이 모든 풀노드는 10분 안에 모든 풀노드가 그것을 받았는데, 이는 10분마다 모든 풀노드가 깔끔하게 한 걸음씩, 즉 자신의 블록체인 끝에 블록을 추가한다는 것을 의미합니다. 예를 들어 네트워크 속도가 매우 빠르더라도(예: 3분 미만) 이 새 블록은 모든 전체 노드에서 수신되었으며 비트코인은 여전히 10분마다 앞으로 이동합니다(새 블록이 생성됨). 이더리움도 비슷하지만 제한 시간이 15초입니다.
Tendermint는 제안 단계에서 네트워크가 반 동기적이라고 가정합니다.이 단계에는 제한 시간이 있기 때문입니다.시간이 만료 된 후에도 새로운 제안 블록이 수신되지 않으면 다른 유효성 검사기는 제안자 노드가 끊어진 것으로 간주합니다. 따라서 빈 블록이 생성됩니다.다음 제안자로 라운드 로빈이 될 때까지. Tendermint는 prevote와 precommit 모두에서 투표의 2/3 이상을 모아야 하는데, 이는 무한 대기 상태입니다. 즉, 이 두 단계에서는 네트워크가 비동기식이라고 가정합니다. 궁극적으로 네트워크에 대한 Tendermint의 요구 사항은 반 동기식입니다.
pBFT는 pre-prepare-prepare-commit의 3단계에서 비동기식인데, 비동기식이고 타임아웃 메커니즘이 없는데 어떻게 앞으로 나아갈 수 있을까? 2/3 이상 모으면 계속 진행할 수 있습니다. 그러나 모든 노드는 클라이언트로부터 요청을 받으면 타이머를 시작하고 일정 시간 내에 요청이 완료되지 않으면 View Change가 트리거됩니다. 보기 변경 섹션은 반동기식입니다.
여기에서 pBFT에 비해 Tendermint의 단순화를 이해할 수 있습니다. Tendermint는 timeout 메커니즘을 Proposal 단계(pBFT의 사전 준비 단계와 동일)로 이동시켰고, Proposer가 지정된 시간 내에 Proposal 블록을 브로드캐스트하면 다음 단계로 진행합니다. 단, 이것은 Proposal 블록이 빈 블록이라는 것입니다(블록이 비어 있을 때 사전 투표 및 사전 커밋 프로세스가 완전히 진행되지만 블록 높이가 1씩 증가하지 않으므로 이는 동등합니다. 새 제안자 노드가 새 제안 블록을 재방송합니다. 즉, 어쨌든 제안 단계는 다음 단계로 진행됩니다. 그러나 Tendermint의 사전 준비는 비동기식이며 영원히 멈출 수 있습니다. pBFT는 타임아웃 메커니즘을 뷰 변경 부분으로 옮겼기 때문에 pBFT에는 텐더민트보다 조금 더 복잡한 추가 뷰 변경 단계가 있습니다. Tendermint는 빈 블록과 라운드 로빈을 제출하여 제안자 노드를 대체하고 pBFT는 View Change를 통해 기본 노드를 대체합니다. Tendermint는 복잡한 보기 변경 단계를 제거합니다.
View Change를 제거하는 것 외에도 Tendermint는 다른 곳에서 단순화되며 모든 Tendermint 정보는 블록체인에 저장됩니다. 그러나 pBFT는 1999년에 제안되었으며, 그 당시에는 블록체인이라는 것이 없었기 때문에 pBFT의 모든 노드는 일관된 데이터를 가지고 있지만 데이터는 분산된 방식으로 저장됩니다. 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.
블록체인은 분산 데이터베이스입니다.예를 들어 MySQL과 같은 DBMS 데이터베이스가 등장하기 전에 사람들은 데이터를 파일에 작성하고 하드 디스크에 저장하여 다양한 이상한 파일 형식과 구성 방법을 발명했습니다. MySQL을 사용하면 데이터 관리가 훨씬 더 편리해집니다. 마찬가지로 텐더민트는 모든 데이터를 블록체인에 저장하고, pBFT는 블록체인과 같은 분산 데이터베이스가 없으며, 모든 노드가 자체적으로 하드디스크에서 데이터를 관리해야 합니다. 하드 디스크 공간 절약, 체크포인트 개념 도입 .
Tendermint와 pBFT의 관계는 Raft와 Paxos의 관계와 유사합니다.Tendermint는 블록체인 시나리오를 위한 pBFT의 단순화된 버전인 pBFT의 단순화된 버전입니다.
다음 그림은 Tendermint의 알고리즘 흐름도입니다.
다음 그림은 pBFT의 알고리즘 흐름도입니다.
참조
참조
1999.Castro. Practical Byzantine Fault Tolerance
Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
Consensus Compare: Casper vs. Tendermint
A Proof of Stake overview
Compared with traditional PBFT, what advantage does Tendermint algorithm has?
Synchronous, partially synchronous and asynchronous consensus algorithms
GRANDPA Block Finality in Polkadot: An Introduction (Part 1)
Finality in Blockchain Consensus
