—— Part1 합의의 분류 ——

초기 분산 합의 알고리즘의 느린 개발부터 오늘날 블록체인 합의의 번성까지 합의 알고리즘의 개발은 약 40년을 거쳤습니다. 서로 다른 합의 알고리즘은 초점이 다르기 때문에 그들이 직면하는 문제와 환경도 다릅니다. 이 기사에서는 다음과 같은 다양한 관점에서 합의 알고리즘을 분류합니다.

▲ 내결함성 유형

비잔틴 오류의 허용 여부에 따라 합의 알고리즘은 두 가지 범주로 나눌 수 있습니다.

1) 비잔틴 내결함성 합의 알고리즘: PBFT, PoW, PoS, DPoS

2) Non-Byzantine 내결함성 합의 알고리즘: Paxos, Raft

비잔티움 허용 여부는 신뢰도가 낮은 네트워크에 알고리즘을 적용할 수 있는지 여부를 나타냅니다. 일반적으로 비잔틴 내결함성 알고리즘은 퍼블릭 체인 환경에서 사용해야 하며, 얼라이언스 체인에서는 얼라이언스 참여자 간의 신뢰 정도에 따라 선택할 수 있습니다.

▲ 알고리즘 결정론

알고리즘의 확실성에 따라 합의 알고리즘은 두 가지 범주로 나눌 수 있습니다.

1) 확정적 합의 알고리즘: Paxos, Raft, PBFT

2) 확률적 합의 알고리즘: PoW, 부분 PoS

결정론적 합의는 일단 합의 결정에 도달하면 롤백 가능성이 없음을 의미하며, 이 범주는 일반적으로 전통적인 분산 합의 알고리즘과 개선된 버전입니다. 확률적(probabilistic)은 도달한 합의 결정이 미래에 일정 확률로 롤백된다는 것을 의미하며, 이 확률은 시간이 지남에 따라 0이 되는 경향이 있지만 이러한 유형의 블록체인은 일반적으로 퍼블릭 체인에 적용됩니다.

▲주요 선발 전략

리더를 선택하는 전략에 따라 합의 알고리즘은 두 가지 범주로 나눌 수 있습니다.

1) 선거 합의 알고리즘: Raft, PBFT

2) 합의 알고리즘 증명: PoW, PoS

선거형 합의는 투표를 통해 블록 생성 노드를 선택하는 것을 말하며, 동일한 노드가 여러 개의 연속 라운드 동안 블록 생성 노드로 존재할 수 있습니다. 이 범주는 일반적으로 전통적인 분산형 합의 알고리즘과 개선된 버전입니다. 증명형 합의 알고리즘은 블록 생성 노드가 블록 생성 권한을 얻기 위해 특정 방식으로 특정 능력이 있음을 증명해야 함을 의미합니다.이 유형의 합의 알고리즘은 일반적으로 블록 생성 노드가 서로 다릅니다. 따라서 블록 권리의 공정성은 일반적으로 퍼블릭 체인에 적용됩니다.

—— Part2 Non-Byzantine 내결함성 합의 알고리즘——

Paxos

Paxos는 비동기 네트워크 모델에서 정확성과 내결함성을 보장할 수 있는 최초의 합의 알고리즘입니다. 이에 앞서 FLP는 비동기 네트워크 모델에서 노드 장애가 있는 한 종료될 수 있는 합의 알고리즘을 가질 수 없다고 명시적으로 지적했습니다. 따라서 Paxos는 일정한 희생을 치렀습니다. Paxos는 시스템의 보안을 보장하기 위해 일정량의 활동을 희생했습니다. 즉, 시스템이 비동기 상태에 있을 때 합의의 진행이 중단되고 노드의 절반이 동기 상태로 돌아가면 합의를 촉진하고 종료를 완료할 수 있습니다.

이미지 설명

그림 1. 기본 Paxos 합의 프로세스

텍스트

Raft

Paxos는 분산형 합의 알고리즘의 기반을 마련했다고 할 수 있는 매우 영향력 있는 합의 알고리즘이지만 이해와 구현의 어려움으로 인해 완전한 Paxos 알고리즘을 구현하는 것은 매우 어렵습니다. 따라서 많은 Paxos 변형이 있으며 그중 가장 유명한 것은 Raft 합의 알고리즘입니다.

Raft는 로그 복제 관리를 위한 합의 알고리즘으로 이해하기 쉽도록 설계되었습니다. Paxos의 내결함성과 성능을 가지고 있지만 차이점은 일관성 문제를 상대적으로 독립적인 세 가지 하위 문제, 즉 리더 선택(리더 선택), 로그 복제(로그 복제) 및 보안(안전)으로 분해한다는 것입니다. 이를 통해 Raft를 더 잘 이해하고 실제 시스템 구축에 쉽게 적용할 수 있습니다.

Raft에서 각 노드는 Leader(마스터 노드), Candidate(후보 노드), Follower(슬레이브 노드)의 세 가지 상태 중 하나에 있어야 합니다. 정상적인 상황에서는 하나의 노드만 리더이고 나머지 노드는 추종자입니다. Leader는 클라이언트의 모든 요청을 처리하고(클라이언트가 Follower와 통신하면 Follower가 정보를 Leader에게 전달함) 로그 데이터(블록체인의 패키징에 해당)를 생성하여 Follower 노드에 브로드캐스트합니다. 팔로워는 수동적입니다. 능동적으로 요청을 보내지 않고 리더로부터 한 방향으로만 로그 데이터를 받을 수 있습니다. Candidate는 차기 Leader를 선출하는 과정에서 발생하는 과도기적 상태로, 어떤 노드라도 Candidate가 될 수 있으며 Primary Node의 장애를 발견한 후 Leader가 될 수 있습니다.

Raft 알고리즘은 시간을 임의 길이의 항(항)으로 나눕니다. 임기는 연속된 숫자로 표시됩니다. 모든 임기는 선거로 시작됩니다. 후보자가 선거에서 승리하면 남은 임기 동안 지도자로 활동합니다. 경우에 따라 표가 나뉘며 지도자가 선출되지 않고 다른 임기가 시작되고 다음 선거가 즉시 시작됩니다.

이미지 설명

텍스트

요약하다

Paxos와 Raft는 비비잔틴 내결함성 기술인 Crash Fault Tolerance 합의입니다. Non-Byzantine은 분산 시스템에 crash fault가 있지만 악의적인(손상된) 노드 시나리오가 없으며(즉, 메시지가 손실되거나 반복될 수 있지만 오류 메시지가 없음) 분산형이라는 의미입니다. 컨센서스 필드 가장 일반적인 질문입니다. Paxos와 비교하여 Raft는 동일한 내결함성과 성능을 보장하면서 더 간결합니다.

텍스트

  PoW

작업 증명(PoW)은 1993년 Cynthia Dwork와 Moni Naor의 학술 논문[3]에서 처음 언급되었으며, 같은 해 Markus Jakobsson과 Ari Juels가 "작업 증명"의 개념을 공식적으로 제안했습니다[ 4] . 처음에 PoW는 주로 스팸 방지에 사용되었습니다. 2008년 PoW는 합의 알고리즘으로 비트코인 ​​시스템에 적용되었습니다. PoW에는 다음 세 가지 기본 속성이 있습니다.

1) 수학 퍼즐: PoW 합의 알고리즘은 수학 퍼즐(Mathematical Puzzle)을 설계하는데, 노드는 새로운 블록을 생성하기 전에 퍼즐에 대한 솔루션을 얻기 위해 특정 컴퓨팅 리소스를 소비하여 블록을 네트워크 및 다른 노드에 브로드캐스팅해야 합니다. 이 솔루션의 유효성을 쉽게 확인할 수 있습니다.

2) 해시 알고리즘: 해시 알고리즘(Hash Algorithm)은 임의의 길이의 입력을 고정된 길이의 출력으로 변환할 수 있는 알고리즘이며, 이는 y = hash(x)로 기록될 수 있으며, 다른 입력 x에 의해 얻어진 출력 y는 달라지다. 또한 y는 x를 알고 있을 때 빠르게 계산할 수 있지만 y를 알고 있는 경우 x는 철저한 방법을 통해서만 역으로 추론할 수 있습니다. 해시 알고리즘은 빨리 감기와 어려운 역방향의 특성을 가지고 있기 때문에 해시 알고리즘은 PoW의 수학적 문제를 설계하는 데 자주 사용됩니다.

3) 블록 생성: 블록 생성 라운드에서 시스템은 출력 값에 조건을 설정하여 수학 문제의 난이도 값을 조정합니다.노드가 문제를 성공적으로 해결하고 체인에서 검증을 통과한 후 해당 보상을 받습니다. .

새 블록을 생성하기 전에 PoW는 목표 값을 미리 설정하고 블록 생성 노드가 계산한 해시 값이 목표 값보다 작아야 PoW의 난이도를 나타냅니다. 블록을 생성하고 보상을 받기 위해 블록 생산자는 먼저 일련의 트랜잭션을 수집하고 블록으로 묶은 다음 블록을 생성하기 위해 수학 문제를 해결하기 시작합니다.

이 기간 동안 블록 생성 노드는 난수를 생성하고 현재 블록 데이터와 이전 블록의 해시로 여러 라운드의 해시 작업을 수행하고 현재 블록의 해시 값을 계산해야 합니다.

현재 블록 해시가 조건을 충족할 때까지:

이미지 설명

텍스트

PoS

앞서 언급한 작업증명합의알고리즘은 컴퓨팅 파워를 이용하여 "리더"의 자격을 놓고 경쟁하지만 작업증명 과정에서 많은 자원이 낭비되어 상대방에게 받아들여지기 어렵다. 대규모 애플리케이션. 이와 관련하여 일부 사람들은 "리더" 자격 선출의 기준으로 "지분"을 직접 사용하려고 시도하기 시작했으며 이후 PoS(Proof of Stake) 합의 알고리즘을 생산했습니다.

PoS의 아이디어는 사회에서 나옵니다. 사람이 더 많은 주식을 소유할수록 더 많은 배당금과 배당금을 받게 됩니다. 블록체인 시스템도 이와 같은 방식으로 유지된다면 과도한 자원 소모가 필요하지 않을 뿐만 아니라 블록체인 자산의 자연스러운 인플레이션도 발생할 수 있습니다. 노드는 일정량의 토큰을 투자하여 합의에 참여하고, 새로운 블록을 패키징할 수 있는 권한을 획득하고 토큰 보유량에 따라 보상을 받습니다. 현재 Ethereum에는 PoS로 전환하려는 Ethereum 2.0 계획도 있습니다.

토큰 보유 상태를 설명하기 위해 PoS 합의 알고리즘은 "코인 시대"라는 개념을 도입합니다. 코인 에이지는 노드가 패스의 일부를 얼마나 오래 보유하고 있는지를 나타냅니다. 노드가 패스를 "공유"로 투자하면 패스의 이 부분이 코인 나이를 축적하기 시작합니다. 코인 나이의 계산 방법은 다음과 같습니다. 다음과 같습니다.

패스의 이 부분을 사용한 후에는 그것이 블록 생성에 사용되든 단순한 거래에 사용되든 관계없이 패스의 이 부분에 해당하는 통화 연령은 소멸됩니다. 기존 PoS 합의 알고리즘에서 코인 나이는 중요한 판단 기준으로, 블록 생성 시 노드가 사용하는 코인 나이가 높을수록 블록 생성이 쉬워져 단기 투기를 어느 정도 제한할 수 있다.

PoS 합의 알고리즘이 블록을 생성할 때 코인 나이와 해시 작업의 난이도를 모두 고려하므로 노드가 블록 생성을 완료하는 데 아주 적은 컴퓨팅 리소스만 소비하면 됩니다.

DPoS

DPoS(Delegated Proof of Stake) 합의 알고리즘[5]에서 선거인은 블록을 직접 생성하는 대표자를 선출하고 선거인은 대표자를 선출함으로써 간접적으로 블록을 놓고 경쟁할 수 있는 권리를 행사한다. 위임 지분 증명 합의 알고리즘은 실제로 일련의 선택 규칙을 통해 후보를 제한하고 일련의 투표 규칙을 공식화합니다. 일반 참가자는 후보자 중에서 투표를 통해 위임자를 선택하고, 위임자는 블록을 생성하며, 요건을 충족하지 못하는 위임자는 자격이 박탈되고 새로운 위임자가 재선출됩니다.

DPoS는 특정 중앙화 기능을 유지하므로 고효율 트랜잭션 처리량을 보장할 수 있으며 속도는 Visa 및 Mastercard와 같은 일반적인 중앙화 기관과 비교할 수 있습니다. 이 알고리즘에서 탈 중앙화의 특성은 주로 블록 생성 권한의 제어 가능성에 반영됩니다. 즉, 주주는 투표를 통해 자신이 신뢰할 수 있는 대표 노드를 선택하고, 대표 노드는 블록체인 데이터를 유지합니다.

——4부 요약——

위에서 언급한 합의 알고리즘은 대부분 비트코인, 이더리움 등과 같은 퍼블릭 체인 시나리오에서 사용됩니다. 퍼블릭 체인 시나리오의 대규모 노드로 인해 결정론적 분산 합의 알고리즘을 채택하기 어렵습니다. PoW는 워크로드 증명을 통해 더 높은 보안과 탈중앙화를 달성합니다.PoW와 비교하여 PoS는 에너지 소비를 줄이기 위해 일정량의 보안을 희생하는 반면 DPoS는 더 적은 노드를 선출하여 합의 효율성을 향상시키는 보다 근본적인 방법을 사용합니다.

저자 소개

저자 소개

참조

FunChain 기술의 기본 플랫폼 부서의 합의 알고리즘 연구 그룹

참조

[1]Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[2] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[3] Dwork C, Naor M. Pricing via processing or combatting junk mail[C]//Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1992: 139-147.

[4] Jakobsson M, Juels A. Proofs of work and bread pudding protocols[M]//Secure Information Networks. Springer, Boston, MA, 1999: 258-272.

[5]Delegated Proof of Stakehttps://github.com/dacplayproject/cpp-play/wiki/Delegated-Proof-of-Stake