BTF(Byzantine Fault Tolerance)합의 알고리즘
1. 기존 합의 알고리즘의 문제
- 기존 합의 알고리즘은 (1) 가상화폐의 필요성 / (2) 부분 분기가 일어날 수 있다는 문제가 발생했음.
- 이는, 즉각적인 거래 확장을 요구하는 서비스에는 적용이 어려운 문제점이 있음
2. FLP Impossibility
- 비동기 네트워크 내에서 Safety(Node값의 동일성)와 Liveness(Network의 합의)를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능 하다(1985. 4, 'Impossibility of Distributed Consensus with One Faulty Process')
* 비동기 네트워크 : 동기/비동기의 본 의미는
1) 상대방의 일정 신호에 의해 다음 동작이 이루어지면 동기 네트워크 - 미리 정해진 수만큼의 문자열을 한 블록으로 만들어 일시에 전송
- 가변 길이의 블록단위에 사용
- 원거리 전송
- 전송 효율이 좋음
2) 상대방의 상태와 관계없이 일방적으로 동작하면 비동기 네트워크 - 송/수신 간의 별도 동기없이 데이터 교환
- 단거리 전송
- 느린 전송속도
- 전송 효율이 떨어짐
- 블록체인에서 어떤 합의 알고리즘을 채택한다는 의미는, Safety와 Liveness 중 한개를 포기해야 한다는 것을 의미
3. PBFT(Practical Byzantine Fault Tolerance)
- 네트워크에 배신자 노드가 일부 있다고 해도, 네트워크 내에서 이루어지는 합의의 신뢰(Trust)를 보장하는 알고리즘
- BFT의 방식의 대부분은 PBFT의 방식을 변형해서 사용하고 있음
- 배신자 노드가 f개 있을때, 총 노드의 개수가 3f+1개 이상이면, 해당 네트워크는 신뢰할 수 있음
- 네트워크의 모든 노드는 (1) Perpare Certificate, (2) Commit Certificat 라는 두 번의 절차를 거침
- 합의 수행 절차
1) Primary(Leader)가 클라이언트의 요청을 수집, 정렬하고, 시행결과와 함께 다른 노드들에게 전파
2) Primary의 메시지를 받은 노드들은 다른 노드들에게서 받은 메시지를 다시 한번 나머지 노드들에게 전파
3) 모든 노드는 자신이 다른 노드들에게서 가장 많이 받은 같은 메시지가 무엇인지 다른 노드에게 전파
4) 1,2,3의 과정이 끝나면 모든 노드들은 정족수 이상이 동의(합의)한 데이터를 가지게 됨
- 현재 IBM Fabric 0.6vm 1.0v의 Orderer, R3 Corda와 같은 Private 블록체인에 사용중
- 합의 절차를 두번 걸치는 이유
1) 비동기 네트워크에서 한번의 절차만 진행 할 경우, 배신자 노드가 동의 내용을 알고 알고리즘의 Safety 파괴 가능
Reference
- Byzantine Fault Tolerance - en.wikipedia
- ICONLOOP / BFT 기반 합의 알고리즘
- [케블리] #48. 합의 알고리즘 이해하기
0 개의 댓글