Ouroboros Consensus Algorithms(우로보로스 합의 알고리즘)

블록체인 네트워크의 핵심이자, 중요한 기술은 노드 간의 높은 보안과 효율을 보장하는 합의 알고리즘이라고 생각한다.

카르다노는 Ouroboros 합의 알고리즘을 자체 개발했으며, 기술 수준이 아주 뛰어나다고 알려져 있으나 쉽게 기술된 자료가 없어서 정리해보려 한다.

우선 합의 알고리즘의 시작인 비트코인의 PoW(Proof of Work) 합의 알고리즘에서부터 Ouroboros 까지 탄생한 과정과 개념에 대해서 간단히 정리해 보자.

---

Bitcoin Consensus Algorithm

비트코인은 Public Permissionless Distributed Ledger로, 누구나 허가 없이 참여할 수 있는 네트워크다. 이 네트워크가 공유하는 두 가지 펀더멘탈 속성(Fundamental Property)는 Safety와 Liveness다.

• Safety: 지난 트랜잭션은 불변해야 하며, 시간이 지남에 따라 Certainty 정도는 높아진다.
• Liveness: 새로운 트랜잭션은 원장에 추가된다.

우리는 비트코인이 Eventual Consensus를 이뤘다고 한다. 이는 시간이 지나면서 불변하며, 참일 확률이 높아지는 것을 말한다.

https://medium.com/coinmonks/cardano-ouroboros-consensus-protocol-a-novel-innovation-c460713708b6

이를 위해 비트코인은 본질적으로 해시파워(hashing power)를 증가시키는 경쟁에 의존한다. 이 경쟁은 지속가능하지 않기 때문에 많은 사람들은 대안을 찾고 있다.

여기서 PoW는 참여자들이 확률적으로 그들의 해시파워를 통해 선택되는 선거 메커니즘이다. 카르다노의 Outoboros는 이 해시파워를 다른 리소스로 대체하는 것으로 시작된다.

---

Proof of Work와 Randomness

작업 증명에서의 무작위성(Randomness)은 적절한 hash 후보를 찾는 것은 암호학적 난이도에서 온다. hashing function은 주로 '추측'에 대해 저항력이 있도록 설계되었다. 

이 hashing power에 비례하여 공정한 선출 과정이 이뤄질 수 있게 반복해서 시도하는 것 외에는 다른 방법이 없다.

Ouroboros Consensus Algorithm

우로보로스 합의 알고리즘은 Proof of Stake 프로토콜로, Liveness와 Safety를 Byzantine 알고리즘을 기반으로 제공한다. 정직한 노드들이 대부분의 자원을 보유하고 있다는 가정하에 모든 Block Producer로 알려진 리더를 기반으로 작동한다.

Block Producer는 그들의 지분(스테이킹된 수량)에 비례하여 특정 슬롯에 선출된다. Stake delegation은 우로보로스의 핵심적인 지분으로 이는 확장성에도 필수적인 요소다.

모든 Ouroboros 프로토콜은 시간기반이며, 동기적으로 동작하며, Long chain rule을 선택하여 가장 긴 체인이 정당하다고 결정한다.

Provable security

우로보로스는 명시적인 보안 보증(explicit security guarantees)을 제공하며, 수학적으로 증명가능한 프로토콜이다. 이는 프로토콜과 프로토콜이 이뤄야 할 목표를 설명하는 정의된 모델을 말한다.

모델 내에서 허용되는 임의의 적대적 행위를 고려해서 그 목표를 달성하는 것을 수학적 증명이 가능하며, 이전 버전에 이서 더욱 강화되고 개선된 새로운 메커니즘이 필요하기 때문에 여러 버전의 우로보로스 알고리즘이 존재한다.

Fundamental Properties

크게 세 가지의 속성을 통해서 Ouroboros 기반의 블록체인 네트워크는 safety와 liveness를 달성한다.

• Common Prefix: 어떠한 정직한 참여자 간에 공통적인 Prefix가 존재한다. 어떤 숫자 k가 존재하여 만약 두 체인에서 k개의 블록을 제거하면 같은 부분의 체인이 남겨져있다는 속성
• Chain Quality: 어떤 숫자 k가 존재하여, 정직한 참여자가 소유한 체인에 대해서 최근 k개의 블록 중 적어도 하나는 정직하게 생성되었다는 속성
• Chain Growth: 어떤 숫자 k와 t가 있어 정직한 참여자가 소유한 체인에 대해서 t x k개의 블록이 k개의 슬롯에 걸쳐 존재한다는 속성

Common Prefix는 블록체인의 일관성을 유지, Chain Quality는 블록 생성과정의 정당성, Chain Growth는 시스템이 지속적으로 블록을 추가하여 성장하는 것을 보장한다고 보면 된다.

이 세 속성을 통해서 블록체인은 보안 측면에서 더 신뢰할 수 있는 구조를 유지한다.

Ouroboros Classic

최초로 발표된 Ouroboros 프로토콜로, Proof of stake에 대한 증명가능한 보안을 제시하는 기본 프레임워크다.

복잡한 Multi-party Computation이 필요하며, 노드 간 Randomness의 좋은 소스를 제공해야 했으며 Proof of stake의 주요 과제는 좋은 Randomness의 source을 찾고, 편향 없는 리더 선출을 보장하는 것이다.

Ouroboros Classic은 비트코인의 Security Guarantees 수준과 동일한 Proof of Stake 프로토콜을 구성할 수 있음을 보여줬다. 그러나 Peer 간 완전한 동기화 통신과 같은 몇 가지 한계가 있는 가정에 의존하는 단점이 있다.

공격자가 자신의 이익을 위해서 조작할 수 없고, 더 지속가능한 편향 없는 randomness의 source를 찾는 것은 어렵기 때문이다.

Ouroboros Praos

paros는 더욱 강력한 Security Gurantees를 갖춘 Outoboros classic 버전으로, 적에게 더 많은 파워를 부여해도 시스템을 더욱 안전하게 보호할 수 있다. 시스템의 Provable Security를 유지하는 수학적인 증명을 제공한다.

노드는 전체 네트워크를 위험에 빠뜨리지 않아도 짧은 시간 동안 오프라인 상태에 놓일 수 있다. 이것은 VRF(Verifiable Random Functions)와 forward-secure KES(Key-Evoving signature Schemes)를 이용해서 이뤄진다.

Ouroboros Genesis

Praos와 Classic에서 새로운 노드는 네트워크에 참여할 때, 정직한 노드로부터 초기 데이터를 받아야 한다. 만약 악의적인 노드로부터 부트스트랩하게 될 경우, 공격자로부터 잘못된 데이터를 받아 전파하는 리스크가 발생할 수 있다.

즉, 악의적인 노드는 체인을 위조해서 네트워크에 참여하는 새로운 Peer에게 체인 데이터를 전송할 수 있다.

Ouroboros Genesis는 이 신뢰할 수 있는 인프라에 의존해야 할 필요성을 줄여 더 높은 탈중앙화를 실현한다. 가장 긴 체인을 선택하는 것뿐만 아니라 체인의 성장을 고려하여, 체인 선택 규칙(The chain selection rule)을 확장하여 작동한다.

Ouroboros Crypsinous

대부분의 프라이버시 프로토콜(Privacy-preserving Protocol)은 트랜잭션 처리 단계에서 프라이버시 보호에 중점을 둔다. 그러나 Ouroborous Crypsinous는 프로토콜 레벨에서 프라이버시 보호를 처리한다.

Ouroboros Chronos

모든 우로보로스 프로토콜은 노드가 동기화된 시간(Synchronizing clocks)을 공유한다는 것을 가정한다. Synchronizing clocks는 분산된 컴퓨팅 환경에서 오랜 기간 알려진 어려운 문제다.

NTP(Network Time Protocol)과 같은 메커니즘은 이러한 문제를 해결하기 위해 오늘날까지 사용되며, NTP는 인터넷 프로토콜로 몇 가지 작동하는 인프라에 의존한다.

Ouroboros Chronos는 외부 서비스에 의존하지 않고, 프로토콜 내에서 동기화된 시간을 계산한다.

Ouroboros Leios (Input Endorsers)

카르다노는 분산화된 시스템이며, 노드들은 그들의 스케줄에 일치한 블록을 공유하여 합의에 도달한다. 더 많은 지분을 보유할수록, 선택될 확률이 더 높아진다. 블록은 약 20초마다 생성되며 최대한 빨리 네트워크에 전파한다.

여기서 노드는 대부분 시간 동안 일을 하고 있지 않다. 즉, 블록이 생성되는 20초라는 모든 시간에 블록을 검증하고 있지않다.

실제 CPU 사용량은 오직 짧은 시간에 증가하는 것을 확인할 수 있다. 이처럼, 리소스는 현재 노드에서 활용도가 낮은 상태다.

Leios는 내가 이전에 포스팅했던 Input Endorsers를 포함하는 프로토콜로, 유휴 리소스(Idle Resource)를 활용하여 체인의 구축을 더 병렬적으로 만드는 것에 대한 것이다. 여기서 블록은 3가지의 새로운 유형으로 나눈다.

• Ranking Blocks(진정한 합의)
• Endorsement Blocks(높은 신뢰 합의)
• Input Blocks(가장 빈번한)

이 접근 방식은 카르다노가 UTxO 모델기반으로 트랜잭션이 실제 Concurrent를 가지고 있기에 효과적으로 적용할 수 있다. 대부분의 트랜잭션은 원장이 서로 충돌하지 않는 것들을 다루기 때문에 UTxO 모델의 두 트랜잭션의 Concurrent를 재기 쉽다.

Leios는 근본적으로 Optimistic Consensus Algorithm이며, 더 연속적(Sequentail)이며 비관적인(Pessimistic) 모드로 전환하는 방법을 포함하여 Praos와 유사하게 작동한다.

Input Endorsers에 대한 지난 포스팅
https://tigercoin.tistory.com/402

Cardano Input Endorsers 개념 이해하기

 

---

참고

https://academy.cardanofoundation.org/

https://www.youtube.com/watch?v=PF1SW7e137A