저자: 유명한 중국 암호학자인 Wang Yongge 교수, Charlotte에 있는 North Carolina 대학(UNC, Charlotte)의 컴퓨터 과학 종신 교수, Heidelberg 대학의 박사 학위, Sperax의 수석 과학자.
텍스트
Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.
합의 프로토콜의 설계는 항상 매우 어려운 주제였습니다. Turing Award 수상자 Lamport는 분산 컴퓨팅을 위해 설계한 Paxos 합의 프로토콜을 설명하기 위해 1989년에 고대 그리스 Paxos 섬의 아마추어 입법자 그룹을 사용하여 법률을 제정했습니다. Lamport는 그의 기사를 ACM TOCS에 제출했습니다. 아마도 이 저널의 편집자는 기사의 중요성을 인식하지 못했기 때문에 출판에 동의하지 않았을 것입니다. Paxos 합의 프로토콜이 학계에서 널리 논의되고 업계에서 널리 사용되기 전까지는 저널이 1998년에 기사를 발표했습니다.
Lamport는 자신의 기사 중 두 번째로 긴 대기 시간이라고 혼잣말을 했습니다. 지금까지 Paxos 합의 프로토콜은 거의 모든 분산 시스템에서 사용되었습니다. 예를 들어 Google의 Bigtable은 Chubby 잠금 서비스 시스템을 사용하여 각 노드에서 데이터의 일관성을 보장합니다. Chubby 잠금 서비스는 Paxos 프로토콜을 기반으로 합니다. 또한 Microsoft, IBM 및 Amazon의 클라우드 서비스 시스템은 모두 Paxos 프로토콜을 사용하여 시스템 일관성을 제공합니다. 대략적으로 말하면 Paxos 프로토콜은 일련의 ROUND로 구성됩니다. ROUND는 합의에 도달할 때까지 0부터 시작합니다. 각 ROUND는 다음 네 단계로 구성됩니다.
1. 마스터 노드는 일련 번호를 생성하여 모든 노드에 브로드캐스트합니다. 이번 일련번호의 활동에 많은 참여 부탁드립니다.
2. 각 노드는 다음 정보를 마스터 노드로 전송합니다. 자신이 참여한 투표의 일련 번호와 투표한 투표
3. 두 번째 단계에서 대부분의 응답을 받은 후 마스터 노드는 SAFETY를 위반하지 않는 값 v를 선택합니다. 이 값 v를 모든 노드에 브로드캐스트
4. 각 노드는 세 번째 단계에서 마스터 노드로부터 값 v를 받은 후 v에 투표하고 모든 노드에 자신의 투표를 브로드캐스트합니다.
Paxos 프로토콜은 구현하기 어렵기 때문에 Stanford 연구원들은 2014년에 구현하기 쉬운 모듈식 Paxos 프로토콜을 제안하고 Raft 프로토콜이라고 명명했습니다. Paxos/Raft 프로토콜은 더 가벼운 위협 모델에서 작동합니다. 즉, 프로토콜은 비동기 네트워크의 비비잔틴 오류에만 강력합니다. 비비잔틴 위협 모델에서 결함이 있는 노드는 수동적 실수(예: 작업 중지)만 할 수 있으며 능동적 공격을 시작할 수 없습니다. n개의 노드가 있는 시스템이 허용할 수 있는 비비잔틴 결함 노드의 최대 수는 (n-1)/2입니다. Paxos/Raft 프로토콜은 이 최대 내결함성 노드 수를 달성합니다.
Paxos/Raft 프로토콜은 비잔틴 오류에 강하지 않기 때문에 개방형 네트워크 시스템(예: 블록체인 시스템)에서 사용할 수 없습니다. 비잔틴 오류는 거짓말, 메시지 위조, 공모 공격 또는 선택적 DoS 공격 실행과 같은 적극적으로 공격적인 오류입니다. 우리는 이전 기사에서 분산형 블록체인 시스템이 개방형 네트워크 시스템을 기반으로 하므로 비잔틴 위협 모델을 사용해야 한다고 언급했습니다.
시장의 블록체인에서 가장 널리 사용되는 비잔틴 계약은 Turing Award 수상자 Barbara Liskov와 그녀의 학생 Castro가 설계한 실용적인 비잔틴 내결함성 시스템 PBFT(practical BFT)입니다. PBFT는 얼라이언스 체인(예: Hyperledger sawtooth 및 Qulian Technology의 하이퍼체인) 및 많은 퍼블릭 체인에서 널리 사용됩니다. PBFT는 Paxos 프로토콜의 비잔틴 버전으로 볼 수 있습니다. 주요 차이점은 PBFT가 비잔틴 오류를 방지하기 위해 Paxos 프로토콜에 확인 단계를 추가한다는 것입니다. 보안을 분석하기 전에 먼저 프로토콜에 대한 공식적인 설명을 제공합니다.
PBFT 프로토콜에서는 n=3t+1개의 노드 P1, ..., Pn이 있다고 가정합니다. 그 중 최대 t개의 노드가 공격자에 의해 제어됩니다. PBFT는 모든 노드가 공동으로 상태를 유지하고 일관된 조치를 취하도록 요구합니다. PBFT 프로토콜은 일련의 보기를 통해 수행됩니다. 각 뷰에는 메인 노드(리더)라는 노드가 있습니다. PBFT 시스템은 먼저 뷰(v=0)로 시작한 다음 뷰 대체 프로토콜을 통해 뷰 v=1, v=2, …로 이동합니다. 시스템이 마스터 노드가 정상적으로 작동할 수 없다고 판단한 경우에만 보기 교체 프로토콜을 시작하고 다음 보기로 들어갑니다. 우리는 모든 노드가 각 뷰의 마스터 노드가 누구인지 알고 있다고 가정합니다. 클라이언트가 현재 보기의 마스터 노드에 작업을 제출할 때마다 PBFT 프로토콜은 시퀀스 번호 할당(사전 준비), 상호 작용(준비) 및 시퀀스 번호 확인(커밋)의 세 가지 통신 단계를 수행합니다. 일련 번호 할당(사전 준비) 단계에서는 각 작업에 일련 번호를 할당하고 상호 작용(준비) 및 일련 번호 확인(커밋) 단계에서는 모든 작업에 대한 전역 순서를 제공합니다. 현재 뷰 v에 있고 기본 노드가 Pi라고 가정합니다. 그런 다음 전체 계약의 프로세스는 다음과 같습니다.
1. 클라이언트는 마스터 노드의 서비스 작동을 활성화하기 위해 작업 요청 m을 보냅니다.
2. 마스터 노드 Pi가 작업 요청 m을 수신한 후 3단계 프로토콜을 시작합니다.
m,
시퀀스 번호 할당(사전 준비) 단계: 마스터 노드는 작업 요청 m에 대해 고유한 시퀀스 번호 seq를 선택합니다. 그런 다음 마스터 노드는 다음 메시지를 모든 노드에 브로드캐스트합니다.
여기서 H는 해시 함수입니다. 노드 Pj는 다음 조건이 충족되면 위의 메시지를 수락합니다.
i. 디지털 서명 SIGNATURE가 유효합니다.
ii. Pj는 아직 동일한 v, seq를 가진 다른 작업 요청을 수락하지 않았습니다.
iii. 일련 번호 일련 번호가 합리적인 범위 내에 있습니다.
b.상호작용(준비) 단계: 노드 Pj가 마스터 노드로부터 브로드캐스트 메시지를 수락하면 Pj는 상호작용(준비) 단계에 진입하여 다음 메시지를 모든 노드에 브로드캐스트합니다.
Pj에 대한 준비가 된 후 Pj는 모든 노드에 다음 확인 메시지를 브로드캐스트합니다.
노드가 2t+1 확인 메시지를 받으면 노드는 작업 요청 m에 포함된 작업을 실행하고 그 결과를 클라이언트에 직접 보냅니다.
3. 클라이언트는 서로 다른 노드의 응답을 기다리고 t+1개의 응답이 동일하면 응답은 작업의 결과입니다.
Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks
우리는 최근 다음 기사에서 PBFT의 보안을 분석했습니다.
이 기사의 분석은 PBFT 합의 프로토콜이 비동기식 네트워크에서 안전하지 않다는 결론을 내립니다. 이 기사에서는 비동기 네트워크에서 PBFT 프로토콜에 대해 설계한 공격 방법을 간략하게 소개합니다. 설명을 단순화하기 위해 시스템에 n=3+1=4 노드 P1, P2, P3, P4가 있다고 가정합니다. 이 중 노드 P1은 공격자가 제어합니다. 또한 뷰 v의 기본 노드가 P1이라고 가정합니다. 우리의 공격은 v에서 전개됩니다.
, SIGNATURE"를 P1, P2, P3로 전송했습니다. 하지만 P4는 아닙니다.
노드 P1,P2,P3에 대해 준비되었습니다. P4는 최대 2개의 대화형 메시지를 수신했고 배열을 준비하려면 최소한 2+1=3개의 메시지가 필요하므로 P4의 경우 배열이 준비되지 않았습니다.
, SIGNATURE"를 모든 노드에 전송합니다. 물론 가능하다면 공격자는 노드 P4가 노드 P2 및 P3에서 브로드캐스트 메시지를 수신하지 못하도록 DoS 공격을 시작할 수 있습니다(이 DoS 공격은 우리 공격에 그다지 중요하지 않습니다). 이 시점에서 노드 P1과 P2는 작업 m에 대해 3개의 확인 메시지를 받았습니다. 노드 P3 및 P4는 태스크 m에 대해 최대 2개의 확인 메시지를 수신합니다. 따라서 노드 P2는 작업 요청 m에 포함된 작업을 실행하고 그 결과를 클라이언트에 직접 보냅니다. 그러나 P1,P3,P4는 이 작업을 수행하지 않습니다. 따라서 클라이언트는 충분한 응답을 받지 못합니다.
위의 공격을 수행한 후 노드 P1은 더 이상 어떤 보기 v의 메시지에도 응답하지 않습니다. 따라서 시스템은 다음 보기 v+1에 들어가기 위해 보기 교체 프로토콜을 시작합니다. 뷰 v +1에 들어간 후 정직한 노드 P2, P3, P4의 내부 데이터 상태가 다릅니다. 따라서 시스템은 조정되지 않은 상태가 됩니다.
PBFT 프로토콜에서 일부 노드가 특정 메시지를 수신하지 못하는 문제(예: 위의 공격 시나리오)를 해결하기 위해 PBFT 프로토콜은 CHECKPOINT 상태 업데이트 프로세스를 설계했습니다. 특히, 100개의 작업이 실행될 때마다 각 노드 Pj는 현재 상태 메시지를 모든 노드에 브로드캐스트합니다.
노드 Pi가 위와 같이 2t+1개의 상태 업데이트 메시지를 수신하고 그 상태가 상태이면 노드 Pi는 현재 상태를 위 메시지의 상태 상태로 대체합니다. 위의 공격에서 부정직한 노드 P1이 상태 업데이트 메시지를 게시하지 않으면 P2에서 발행된 상태 업데이트 메시지는 P3 및 P4에서 발행된 상태 업데이트 메시지와 다를 것입니다. 노드의 상태를 업데이트하려면 최소한 2+1=3개의 동일한 상태 업데이트 메시지가 필요하기 때문에 P2의 상태를 P3 및 P4의 상태로 업데이트할 수 없습니다. 따라서 시스템은 항상 조정되지 않은 상태에 있게 됩니다.
나중에 보기에서 부정직한 노드 P1은 정직한 노드 P3 및 P4와 협력하여 클라이언트의 다른 작업 요청을 공동으로 실행할 수 있습니다. 따라서 각 노드의 상태는 복구 불가능한 조정되지 않은 상태가 됩니다.
이전 기사에서 우리는 인터넷 기반 블록체인 기술에서 DoS 공격이 시작되기 쉽다고 언급했습니다. 인터넷은 비동기식 네트워크이므로 네트워크 통신을 설명하기 위해 다음 모델을 사용합니다.
메시지가 손실되거나(예: DoS 공격) 재정렬될 수 있는 전역 안정화 시간(GST)이 있습니다. GST 이후 네트워크는 동기식 네트워크가 됩니다. 그러나 언제 GST가 시작될지는 아무도 모릅니다.
