블록체인에서의 비잔틴 문제(Byzantine Generals Problem)

이해 잘 되게 이미지 하나 뽑으려고 검색을 해 보니 역시 GeeksforGeeks에 글이 있다.

https://www.geeksforgeeks.org/byzantine-generals-problem-in-blockchain/

Byzantine Generals Problem in Blockchain - GeeksforGeeks

난 스택오버플로우보다 긱스포긱스가 좋다.

진짜 완벽하다.

(그런데 글자가 너무 많아서 단 한 번도 아티클을 완독한 적이 없다.)

 

어쨌든... 심플하게 이해를 해 보자.

 

1. 비잔틴 문제가 뭐냐?

비잔틴 문제는 분산 시스템에서 발생할 수 있는 신뢰성 문제를 설명하는 고전적인 문제입니다.

이 문제는 주로 분산 컴퓨팅이나 블록체인 네트워크에서 시스템의 신뢰성과 일관성을 유지하는 방법을 이해하는 데 중요합니다.

비잔틴 장군 문제의 개념

1. 상황 설정:
   • 여러 장군이 서로 떨어진 성을 공격하기 위해 협력해야 합니다.
   • 장군들은 서로 메시지를 주고받아 공격 시간과 계획을 조율해야 합니다.
   • 그러나 일부 장군들은 배신자가 되어 잘못된 정보를 보낼 수 있습니다.
2. 문제:
   • 모든 충성스러운 장군들이 같은 공격 계획을 세우는 것이 목표입니다.
   • 배신자가 있는 상황에서도 충성스러운 장군들이 일관된 계획을 세울 수 있는가?

비잔틴 문제의 핵심

1. 충성스러운 장군: 올바른 정보를 보내고, 같은 계획을 따르려고 하는 장군들.
2. 배신자: 잘못된 정보를 보내서 전체 계획을 혼란시키려는 장군들.
3. 목표: 배신자가 있더라도 모든 충성스러운 장군들이 일관된 계획을 세우고, 같은 행동을 하도록 만드는 것.

 

심플하다.

자, 위와 같은 상황이면 어떻게 해야 하는가?

 

위 문제를 해결하기 위해 고안된 알고리즘이 '비잔틴 장애 허용(Byzantine Fault Tolerance, BFT)'이다.

https://inevitableeth.com/home/concepts/bft

Byzantine Fault Tolerance

영어를 해석할 힘이 있다면 위 '사이트'의 글을 다 보는 걸 적극 추천한다.

 

그럼 비잔틴 장애 허용, BFT가 어떻게 작동하는지 보자.

Practical Byzantine Fault Tolerance (PBFT) 예시

PBFT는 가장 널리 알려진 BFT 알고리즘 중 하나입니다. <- Yes, BFT 알고리즘은 여러 개다. 이 얘기는 PBFT 이야기 끝나고 이어서 할 거다.

PBFT는 다음과 같은 단계를 통해 비잔틴 문제를 해결합니다.

1. 전제 조건:
   • 네트워크에는 3𝑓+13f+1 개의 노드가 있으며, 그 중 최대 𝑓f 개의 노드가 악의적일 수 있습니다.
   • 여기서 𝑓f는 허용 가능한 악의적 노드의 수를 의미합니다.
2. 단계 1: 요청(Request):
   • 클라이언트가 리더(주 노드)에게 요청을 보냅니다.
3. 단계 2: 준비(Prepare):
   • 리더는 요청을 받으면 다른 모든 노드에게 준비(Prepare) 메시지를 보냅니다.
   • 모든 노드는 리더의 메시지를 받고, 다시 준비 메시지를 다른 노드들에게 전송합니다.
4. 단계 3: 준비 완료(Pre-prepare):
   • 각 노드는 2𝑓+12f+1 개의 일치하는 준비 메시지를 받으면 준비 완료 상태가 됩니다.
   • 노드는 준비 완료 상태가 되면, 준비 완료 메시지를 다른 노드들에게 전송합니다.
5. 단계 4: 커밋(Commit):
   • 각 노드는 2𝑓+12f+1 개의 일치하는 준비 완료 메시지를 받으면 커밋 상태가 됩니다.
   • 커밋 상태가 되면, 노드는 커밋 메시지를 다른 노드들에게 전송합니다.
6. 단계 5: 응답(Reply):
   • 각 노드는 2𝑓+12f+1 개의 일치하는 커밋 메시지를 받으면 트랜잭션을 실행하고, 클라이언트에게 응답을 보냅니다.
7. 최종 합의:
   • 클라이언트는 𝑓+1f+1 개의 일치하는 응답을 받으면 트랜잭션이 성공적으로 완료되었음을 확인합니다.

PBFT가 비잔틴 문제를 해결하는 방식

• 다수결: PBFT는 네트워크의 과반수 노드가 일치하는 메시지를 보내야 합의를 도출합니다. 이는 악의적 노드가 일부 있더라도 전체 시스템의 무결성을 유지할 수 있게 합니다.
• 메시지 전파: 모든 노드가 서로 메시지를 주고받으며 상태를 공유합니다. 이를 통해 잘못된 정보가 전파되는 것을 방지합니다.
• 여러 단계의 검증: 준비, 준비 완료, 커밋 등 여러 단계의 검증 과정을 통해 트랜잭션의 유효성을 확인합니다.

다른 BFT 알고리즘 예시: Tendermint

Tendermint는 PBFT와 유사하지만, 좀 더 간단한 구조를 가지고 있으며 블록체인에서 주로 사용됩니다.

1. 제안(Propose):
   • 리더 노드가 새로운 블록을 제안합니다.
2. 프리보트(Pre-vote):
   • 각 노드가 제안된 블록을 검토하고, 문제가 없다고 판단하면 프리보트 메시지를 다른 노드에게 전송합니다.
3. 프리커밋(Pre-commit):
   • 프리보트 메시지를 받은 노드는 이를 검토하고, 문제가 없다고 판단되면 프리커밋 메시지를 다른 노드에게 전송합니다.
4. 커밋(Commit):
   • 일정 수 이상의 프리커밋 메시지를 받은 노드는 블록을 커밋하고, 다른 노드에게 커밋 메시지를 전송합니다.
5. 최종 합의:
   • 모든 노드가 블록을 커밋하면 최종 합의에 도달합니다.

요약

• BFT 알고리즘은 네트워크 내 일부 노드가 악의적으로 행동해도 다수의 노드가 일관된 상태를 유지하도록 설계되었습니다.
• PBFT는 다수결과 여러 단계의 검증 과정을 통해 트랜잭션의 유효성을 확인합니다.
• Tendermint는 PBFT와 유사한 구조를 가지고 있지만, 좀 더 간단한 단계로 블록체인에서 사용됩니다.

---

어? 근데 텐더민트는 블록체인 아닌가??? <- 아님, 블록체인 '플랫폼'임.

 

텐더민트(Tendermint)는 합의 알고리즘이자 블록체인 플랫폼입니다.

텐더민트는 BFT 기반의 합의 알고리즘을 사용하며, 이를 통해 PoS(Proof of Stake) 시스템을 구현합니다.

텐더민트(Tendermint)의 두 가지 역할

1. BFT 합의 알고리즘:
   • 텐더민트는 BFT(비잔틴 장애 허용) 합의 알고리즘을 사용합니다. 이는 분산 네트워크에서 일부 노드가 악의적이거나 비정상적으로 행동하더라도 전체 네트워크의 무결성을 유지하도록 합니다.
   • 텐더민트 BFT 합의 알고리즘은 제안(Propose), 프리보트(Pre-vote), 프리커밋(Pre-commit), 커밋(Commit) 단계를 통해 합의에 도달합니다.
2. 블록체인 플랫폼:
   • 텐더민트는 또한 블록체인 플랫폼으로, 개발자들이 텐더민트 코어를 사용하여 새로운 블록체인을 구축할 수 있게 합니다.
   • 텐더민트 코어는 애플리케이션과 합의 레이어를 분리하여 높은 확장성과 유연성을 제공합니다.

텐더민트의 합의 알고리즘과 PoS

• 합의 알고리즘:
  • 텐더민트는 BFT 합의 알고리즘을 사용하여 네트워크의 일관성과 신뢰성을 보장합니다.
  • 이 알고리즘은 네트워크의 과반수 노드가 올바르게 동작하는 한, 합의에 도달할 수 있도록 설계되었습니다.
• PoS 시스템:
  • 텐더민트는 PoS(Proof of Stake) 메커니즘을 사용하여 블록 생성 권한을 분배합니다.
  • 네트워크 참여자들은 자신이 보유한 지분(Stake)에 따라 블록 생성 권한을 얻습니다.
  • 이 지분 기반의 접근 방식은 텐더민트의 BFT 합의 알고리즘과 결합되어 높은 보안성과 효율성을 제공합니다.

텐더민트의 합의 과정

1. 제안(Propose):
   • 리더 노드가 새로운 블록을 제안합니다.
   • 제안된 블록은 다른 검증자 노드들에게 전송됩니다.
2. 프리보트(Pre-vote):
   • 각 검증자 노드는 제안된 블록을 검토하고, 올바르다고 판단되면 프리보트 메시지를 보냅니다.
3. 프리커밋(Pre-commit):
   • 검증자 노드들이 프리보트 메시지를 받고, 다시 블록의 유효성을 확인한 후 프리커밋 메시지를 보냅니다.
4. 커밋(Commit):
   • 검증자 노드들이 충분한 프리커밋 메시지를 받으면 블록을 커밋하고, 이를 최종 블록체인에 추가합니다.
5. 최종 합의:
   • 모든 검증자 노드가 블록을 커밋하면, 합의에 도달하여 블록이 확정됩니다.

요약

• **텐더민트(Tendermint)**는 BFT 합의 알고리즘을 사용하는 블록체인 플랫폼입니다.
• BFT 기반 PoS: 텐더민트는 BFT 알고리즘을 사용하여 네트워크의 일관성과 신뢰성을 보장하고, PoS 메커니즘을 통해 블록 생성 권한을 분배합니다.
• 합의 과정: 제안(Propose), 프리보트(Pre-vote), 프리커밋(Pre-commit), 커밋(Commit) 단계를 거쳐 최종 합의에 도달합니다.

따라서 텐더민트는 BFT 기반의 PoS 시스템을 사용하는 블록체인 플랫폼입니다.

---

이거는 그렇다 치고...

다시 돌아가서, 위의 PBFT가 작동하는 방식은 대충 아래와 같다.

 

이게 뭔지 '몽가 몽가' 알 것 같은 상태까진 왔으나 여기에 대해 내가 말로 알고리즘 설명을 못 하겠다.

학습해서 기록해 놓을 시간이 없으니 그냥 패스한다.

 

지금까지

비잔틴 문제가 뭔지, 이 알고리즘이 어떤 형태로 도는지를 확인했다.

그럼 이제는 BFT 알고리즘이 여러 개라 했는데 어떤 게 있는지 한 번 보자.

주요 BFT 알고리즘

1. PBFT (Practical Byzantine Fault Tolerance):
   • 개념: 실제 시스템에서 비잔틴 문제를 해결하기 위해 설계된 초기 BFT 알고리즘 중 하나입니다.
   • 특징: 다수결 원칙과 여러 단계의 메시지 교환(Prepare, Pre-prepare, Commit)을 통해 합의에 도달합니다.
   • 적용 사례: Hyperledger Fabric, Zilliqa 등.
2. Tendermint:
   • 개념: PBFT와 유사한 구조를 가지지만, 블록체인 환경에 최적화된 BFT 알고리즘입니다.
   • 특징: 간단한 투표 단계(Propose, Pre-vote, Pre-commit, Commit)를 통해 합의에 도달합니다.
   • 적용 사례: Cosmos 네트워크.
3. HotStuff:
   • 개념: 기존 BFT 알고리즘의 효율성을 개선한 알고리즘입니다.
   • 특징: 직렬화된 합의 단계를 통해 처리 속도를 향상시킵니다.
   • 적용 사례: 페이스북의 Libra(현 Diem) 프로젝트에서 사용.
4. Algorand:
   • 개념: 무작위로 선택된 위원회를 통해 합의에 도달하는 BFT 알고리즘입니다.
   • 특징: 빠른 합의와 높은 확장성을 제공합니다.
   • 적용 사례: Algorand 블록체인.
5. HoneyBadgerBFT:
   • 개념: 네트워크가 비동기적일 때도 합의를 도출할 수 있는 BFT 알고리즘입니다.
   • 특징: 네트워크 지연과 패킷 손실에도 견딜 수 있는 강력한 내구성을 제공합니다.
   • 적용 사례: 일부 비트코인 사이드체인 및 프라이빗 블록체인.

요약

• PBFT (Practical Byzantine Fault Tolerance):
  • 구조: Prepare, Pre-prepare, Commit 단계.
  • 특징: 초기 BFT 알고리즘, Hyperledger Fabric 등에서 사용.
• Tendermint:
  • 구조: Propose, Pre-vote, Pre-commit, Commit 단계.
  • 특징: 블록체인 환경에 최적화, Cosmos 네트워크에서 사용.
• HotStuff:
  • 특징: 직렬화된 합의 단계로 처리 속도 향상, Libra 프로젝트에서 사용.
• Algorand:
  • 특징: 무작위로 선택된 위원회를 통해 빠르고 확장성 높은 합의, Algorand 블록체인에서 사용.
• HoneyBadgerBFT:
  • 특징: 비동기적 네트워크 환경에서도 견딜 수 있는 강력한 내구성.

---

오늘은 여기까지.

하이퍼레저 등을 사용할 일이 있으면 비잔틴 장애 허용 알고리즘을 제대로 알고 있어야 할 것 같으니

이 부분은 나중에 다시 공부하고 정리할 것 같다.