해시넷
우로보로스 비잔틴 장애 허용
우로보로스 비잔틴 장애 허용(OBFT; Ouroboros Byzantine Fault Tolerance)이란 간단한 결정론적 블록체인 기반 프로토콜로, 서버는 그들에게 이용 가능한 가장 긴 체인을 확장하는 거래의 블록을 분산시키는 미리 결정된 라운드 로빈(round-robin) 방식으로 돌아가게 된다. 서버는 거래의 결과로 클라이언트에 즉시 응답할 수 있으므로 거래의 결과를 얻을 수 있다.
목차
개요
카르다노가 가지고 있는 기존 지분 증명 프로토콜의 한계, 그 중에서도 특히 Grinding Attack을 막기 위해 설계된 지분증명(Pos) 기반 합의 프로토콜로 우로보로스(Ouroboros)가 있는데, 이 기존의 우로보로스의 디자인에서 영감을 얻은 새로운 BFT 원장 합의 프로토콜이다. 2018년 11월에 발표된 페이퍼가 존재하며, 프로그래밍 언어 하스켈(Haskell) 과 러스트(Rust) 구현이 있다. 우로보로스 BFT를 사용하면 Shelley로의 구현 및 배포 시간을 단축할 수 있다고한다. 또한 우로보로스 비잔틴 장애 허용은 Byron이 사용하는 우로보로스 클래식과 우로보로스 제네시스 사이의 브리지(연결 다리) 역할을 한다.
구현 언어
- 하스켈 : 순수하고 단순한 함수형 프로그래밍 언어로 함수형 프로그래밍 분야의 학자들이 부작용의 해악에 대한 아이디어를 집어넣어 설계해 20년 이상 개발해왔다. 하스켈은 함수형 프로그래밍의 이상에 대한 순수한 표현 중 하나로 I/O 채널을 다루는 데 있어 신중한 메커니즘을 갖추고 있으며, 또한 불가피한 부작용도 갖고 있다. 그러나 그 부분을 제외한 나머지 부분은 완벽하게 기능한다. 커뮤니티는 매울 활발하여 십여 개의 하스켈 변형 버전이 나와 있다. 그 중에서는 독립형도 있고 자바 도는 파이썬과 같은 주류 프로젝트와 통합되는 형태도 있다.
- 러스트 : 러스트는 시스템 수준의 빠른 소프트웨어를 제작하기 위한 언어이다. 러스트는 빠르고, 안전하며, 무엇보다 합리적인 수준의 프로그래밍 난이도를 보장한다. 러스트는 또한 널리 사용되도록 설계되어 있으며 승자 독식의프로그래밍 언어 경쟁에서 '참가에 의의를 두는' 낙오된 언어가 되지 않도록 신경썻다. 러스트의 장점들은 브라우저뿐만 아니라 모든 소프트웨어에 필요하기 때문에 브라우저 프로젝트로 시작한 러스트는 프로그래밍 언어 프로젝트로 진화했다.
정산증명 방법
가정 1. (t < n/4)
- 레저 보고(Ledger Reporting) : 거래 tx는 원장에 여러번 입력할 수 있다. 또한 원장에는 tx와 상충되는 거래가 포함될 수 있다. 원장에 주어진 tx의 각 입력은 tx에 대한 투표로 간주되며, 원장의 구문 분석은 완료된 트랜잭션만 계산한다. 이것들은 원장의 결산 부분에서 t + 1의 표를 받은 거래들이다. 두 개의 최종 거래가 상충될 경우, 원장에 의해 결정된 순서에서 t + 1 표에 도달하는 첫 번째 거래만 유지된다. 원장의 정착부에는 과거에 3t + 1개 이상의 슬롯이 모두 포함되어 있음을 상기한다.
- 멤풀 업데이트(Mempool Update) : 서버는 이전과 같이 수신된 모든 트랜잭션을 수집한다. 트랜잭션 tx는 유효한 한 업데이트된 멤풀로 들어가고, 멤풀은 원장님 상태에 관해 안전한 상태로 유지된다. 원장의 상태는 완료된 트랜잭션만 기준으로 결정된다는 점을 상기해야한다. 그러므로 어떤 상충되는 거래가 원장에 존재할 수 있따는 사실에도 불구하고 원장의 정산 부분에서 다른 거래가 t + 1표에 도달하지 않은 한 거래가 멤풀로 진입할 수 있다.
위와 같이 개정된 OBFT는 대부분의 t < n/4 비잔틴 단체가 존재한다는 가정 하에 파라미터 n + 3t + 1로 지속성과 즉각적인 결산 증명, 그리고 기초적인 디지털 서명 계획의 보안을 만족한다.
가정 2. (t <n/3)
- 레저 보고(Ledger Reporting) : 거래 tx는 다양한 승인 입력의 일부로 원장에 여러번 입력할 수 있으며, 더욱이 원장에 tx와 상충되는 거래와 함께 승인된 입력을 포함할 수 있다. 원장에 주어진 tx의 각 입력은 tx에 대한 투표로 간주된다. 원장을 구문 분석하는 것은 마무리된 트랜잭션만 계산한다. 이러한 거래들은 원장의 정산 부분에서 t + 1의 표를 받은 거래들이다. 두 개의 최종 거래가 상충될 경우, 원장에 의해 결정된 순서에서 t + 1표에 도달하는 첫 번째 거래만 유지된다. 원장의 정착부에는 과거에 3+ 1개 이상의 슬롯이 모두 모두 포함되어 있음을 상기한다.
- 멤풀 업데이트(Mempool Update) : 서버는 과거 n + 2t + 1개의 슬롯까지 잉전 슬롯의 승인된 입력뿐만 아니라 트랜잭션을 수집한다. 트랜잭션 tx는 유효한 한 업데이트된 멤풀로 들어가고, 멤풀은 원장님 상태에 관해 안전한 상태로 유지된다. 원장의 상태는 완료된 트랜잭션만 기준으로 결정된다는 점을 상기해야한다. 따라서 일부 상충되는 거래는 일부 승인된 투입변수의 일부일 수 있지만 다른 거래가 원장의 정산 부분에서 t + 1표에 도달하지 않는 한 거래가 멤풀로 진입할 수 있다.
- 블록체인 확장(Blockchain Extension) : 각 서버는 거래 집합으로 승인 받은 입력을 먼저 준비하고 n + 2t + 1 슬롯에 대해서도 캐싱하는 것을 제외하고, 원장을 연장할 책임이 있는지 확인한다. 서버가 블록체인 연장을 책임지지 않는 경우, 인가된 입력을 다시 제출해야 하는지 여부를 확인한다. 이것은 지역 블록체인에서 승인된 입력을 포함하지 않는 경우에만 발생한다.
OBFT는 대부분의 t < n/3 비잔틴 단체와 기초적인 디지털 서명 체계의 보안이라는 가정하에 매개변수 n + 5t + 2와의 지속성과 즉작적인 해결 증명을 만족시킨다.
대체 위협 모델에서 작동 방식
- Fail-stop corruptions : Fail-Stop 모델에서 서버는 단순히 실패하여 작동을 멈춘다. 이 모델에서 프로토콜은 많은 수의 장애를허용할 수 있음을 쉽게 알 수 있다. 즉, 하나ㅏ의 서버가 여전히 운영 일관성을 달성하고 매개변수 2n으로 트랜잭션이 계속 처리될 것이다.
- 네트워크 분할(Network splits) : 네트워크 분할의 경우, 네트워크는 슬롯 D의 시퀀드에 대해 각각 n1, ., ., ns 서버를 포함하는 s≥2에 대해 일시적으로 연결된 구성요소로 분할된다. 다른 고장이 없다고 가정하면 연결된 각 구성 요소에서 트랜잭션 처리가 정상적으로 지속된다는 것을 쉽게 알 수 있다. 또한 슬롯 최대 D + n에 의해 모든 서버가 활성화되고 시스템이 고유한 블록체인으로 수령된다. FT는 네트워크 분할에 탄력적이다. 승리한 서버를 가진 최대 구성요소가 아닌 다른 연결된 구성요소 내에서 처리된 트랜잭션이 손실될 수 있으므로 다시 제출해야 한다는 점을 유의해야한다.
- 부분 동기화 : 부분 동기화에는 두 개의 정직한 노드 사이의 메시지 전달의 최대 지연을 결정하는 알려지지 않은 매개변수 ∆가 있으며, 메시지의 스케줄링은 상대적이다. ∆가 여전히 선택된 슬롯 길이 내에 들어맞으면, 프로토콜은 영향을 받지 않는다. 만약 그것이 초과되고 프로토콜의 진보다 허용된다면, 단순한 작성 전략은 두 가지 대안적인 블록 체인을 만들 수 있다. 예를 들어, n이 균등하다고 가정하고 서버를 두 세트로 분할한 다음, 두 개의 슬롯에 해당하는 자연 메시지를 전달하여, 각 수신 서버에 대한 선호 w.r.t. 패리티를 부여한다. s 홀수 패널티 서버에서 먼저 수신하고 짝수 페리티 서버에서도 마찬가지로 수신한다. ∆ 지연이 네트워크 분할 사례에 기술된 것과 유사한 방식으로 프로토콜이 단일 블록체인으로 다시 수렴되는 경우에 네트워크 분할과 유사하게 두 개의 블록체인을 병렬로 전진시킨다
각주
참고자료
- [하마] 이승현, 〈BFT 간략 정리 : PBFT , SimpleBFT, SBFT , BFT-SMaRt〉, 《티스토리》, 2019-03-05
- Alexander Russell, Aggelos Kiayias, 〈BOuroboros-BFT:A Simple Byzantine Fault Tolerant Consensus Protocol〉, 《iohk》, 2018-10
- 〈지금 배울 만한 9가지 최첨단 프로그래밍 언어〉, 《아이티월드》, 2014-11-06
- Serdar Yegulalp, 〈C·C++ 개발자 노린다···‘러스트’ 언어란? 뜨는 이유는?〉, 《CIO코리아》, 2018-12-07
