Ouroboros 해설 1편 - 소개 및 모델 정의

우로보로스(Ouroboros) 논문은 아주 학술적인 형태로 쓰여져 있지는 않다. 그것을 읽어줄 대중들을 고려해서 여러 맥락에 대해 설명하고 그것을 이용해 필요한 증명들을 소개하고 있다. 50 페이지 짜리 글은 크게 5 부분으로 요약할 수 있다.

Introduction - 우로보로스를 개발하게 된 과정을 설명 (1p. )
Model - 우로보로스에서 쓰일 용어들을 정의하고 그것을 설명 (5p.)
Our Protocol : Overview - 우로보로스의 프로토콜 단계에 대한 요약 설명 (8p.)
Our Protocol : Static Stake - 최초 지분 상태에만 갖고 동작하는 프로토콜 설명 (10p.)
Our Protocol : Dynamic Stake - 지분이 계속해서 바뀌는 환경에서 동작하는 프로토콜 설명 (33p.)

그 외 프로토콜에 대한 주제별 논의

익명 통신과 더 강력한 적에 대해 (39p.)
보상 체계 (40p.)
지분 대리 Stake Delegation (43p.)
(해킹과 같은) 공격 논의 (45p.)
실험 결과들 (48p.)

각 포스팅은 분량과 내용의 난이도 및 중요도에 따라 적절히 조절할 것이며 총 5개 정도의 포스팅이 적절할 것으로 보인다.

Introduction + Model 포스팅
Overview + Static Stake 1편
Static Stake 2편
Dynamic Stake
보안 + 보상 + 지분 대리 논의
해킹 공격, 실험 결과 논의

우로보로스는 Static/Dynamic Stake 프로토콜을 설명하는 부분에 수학 증명이 거의 몰려있다. 그리고 앞부분과 뒷부분에는 그들이 프로토콜을 만들며 논의했던 주제들에 대해 아주 잘 정리해놓았다. 기존에 블록체인 커뮤니티 및 학계에서 논의되던 것들을 많이 참조해가면서 써놨기 때문에 한마디로 공짜로 보는 고퀄 자료라고 볼 수 있다.

참고사항

대체로 우로보로스 저자가 쓴 말을 옮긴다는 생각으로 쓸 것이며, 개인적인 부가설명을 하고 싶을 때는 [] 안에 #을 붙여서 쓰겠다.
예시 - 우로보로스는 보안성과 효율성을 갖추고 있어서 쩔어준다 [#저자가 자뻑을 하고 있는 것 같다]
글 중간에 링크가 있다면 적절히 도움될 만한 포스팅을 달아놓은 것이다. 최대한 한국말 포스팅을 찾아 달아놓으려 한다.

이 포스팅에서는 Introduction + Model 부분을 다뤘다. (논문 1-7p.)

소개 (Introduction, 1p.)

비트코인의 프로토콜의 주 문제는 PoW 방식 썼을 때 그것을 실행하기 위해 들어가는 에너지가 엄청나다는 것이다. 이 논문을 쓸 때 비트코인 블록체인은 이미 엄청난 양의 에너지를 소모하며 작은 국가 수준의 소모량에 비교할 만하다. 이 문제를 해결하기 위해 좀 더 에너지가 적게 들되 똑같은 일을 할 수 있는 대안을 찾게 되었다. PoW의 원리가 기본적으로 "리더 선거"를 하며 각 채굴자들의 계산 능력에 비례해서 리더를 무작위로 뽑아낸다는 점이 중요하다. [#여기서 투표라는 말이 나온다고 PoS와 혼동할 이유가 없다. 리더란 블록체인의 블록을 만드는 노드를 말한다. PoW는 모든 노드가 경쟁해서 먼저 계산한 노드의 블록을 다들 자기네 체인에 붙인다. 즉, 리더를 계산능력에 비례해 선출하는 힘의 경쟁이라 보면 된다.]

자연스럽게 대안이 되는 개념은 PoS이다. 계산 능력 높일려고 안간힘을 쓰는 채굴자에 의존해 리더를 뽑는 것이 아니라 현재 블록체인에 있는 장부에서 얼마나 지분을 가졌는지에 비례해 무작위로 리더를 뽑는다는 것이다. 그 결과 블록체인이 일종의 '자기 참조' 규칙을 만들게 된다 : 블록체인을 유지시키는 것이 지분을 가진 자들이며 지분에 따라 할 일(및 보상을)을 자기자신이 다시 받는 것이다. 게다가 이 규칙을 이용하면 "인공적인" 계산을 굳이 지분을 가진 쪽에서 하라고 요구할 필요가 없다. [#오로지 경쟁을 위해 괜히 hash함수를 풀라고 하는 PoW와 다르다는 뜻] 어찌보면 아주 이상적인 것으로 보이지만 PoS는 기술적으로나 그것을 정의하는 부분에서나 여러가지 문제가 많이 있다.

기존 작업

PoS 개념은 비트코인 포럼에서 지속적으로 논의되어왔다. 그리고 이 방식이 나름 여러 공격으로부터 안전하다는 것을 보여준 결과들이 있지만, PoS 프로토콜의 공식적인 모델을 제시하거나 그 모델이 안전하다고 증명하는 정확한 내용은 없었다.
PoS를 다른 몇가지 개념하고 비교해보는 게 흥미로운 작업이었는데, '정해진 수의 권위자'들만 블록체인을 통제하게 하는 PoA (proof of authority)나 사용한 메모리 등을 증명하는 proof of space 등등이 있었다.

PoS 설계의 어려운 점

리더 즉, 블록을 만들 주체를 뽑는 프로세스가 근본적인 문제이다. 공정하게 지분노드 [# 앞으로 지분을 가지고 PoS 프로토콜에 참여하는 이해관계자를 지분노드라 정의하겠다. 논문에서는 stakeholders]들 중에서 리더를 뽑아야한다. 그러기 위해 어떤 형태의 규칙을 정의해야하는데, 그런 규칙은 결국 적에게 조작당하는 데 취약할 수 밖에 없다. 예를 들어 어떤 적은 지분노드들 몇개를 가지고 순서를 바꿔가는 등등 여러 시도를 해서 리더를 뽑는 규칙을 찾아낼 수도 있다. 이것이 적이 사용할 수 있는 "연마" [#돌을 깎아 둥글게 조각하듯 지분노드를 조작해 점점 규칙에 다가감] 하는 방식의 공격이다.

우리의 결과물

우리는 안전성을 증명할 수 있는 PoS 시스템 "우로보로스"를 소개한다. 아마 엄밀한 안전성 분석을 이용해 만든 첫번째 프로토콜일 것이다.

우린 PoS 기반 블록체인의 문제를 구현한 모델을 제시한다. 그 모델은 트랜잭션 장부를 견고하게 만들 두 속성들 - 지속성(persistence)과 유효함(liveness) - 을 소개하고 있다.

지속성 - 하나의 노드에서 어떤 트랜잭션을 "안정되었다"(stable)고 한다면, 그리고 이 내용을 끌어 쓰는 다른 노드가 정직하다는 가정 하에 마찬가지로 그 트랜잭션이 안정되었다고 인정한다. 여기서 안정도(stability)는 k라는 지표가 있어서 그걸 중심으로 판단할 것이다. (예를 들면, "k 블록 만큼 깊다" 라는 표현)
유효함 - 트랜잭션이 정직한 방식으로 만들어졌고 네트워크 노드 사이에서 u 만큼의 시간 동안 살아있었다면 안정한 상태가 된다.

우리는 PoS 프로토콜에 기반한 블록체인을 소개한다. 우리는 리더 선출 과정을 랜덤으로 동전 던지는 것처럼 뽑도록 하기 위해 안전하게 여럿(서버들)에 의해 구현하는 방식을 이용한다. 지금까지의 것들은 블록체인의 현재 상태나 랜덤한 수치를 서버끼리 모아서 동전 던지기를 시도했다. 이런 방식은 이미 얘기했듯이 "연마"로 규칙을 도출하는 공격에 취약하다.
우리는 현재 지분노드들의 상태를 일정한 시간마다 스냅샷으로 찍을 것이며, 이 일정한 시간 간격을 시대(epoch)라고 정의한다. 각 시기마다 그 블록체인 자체를 이용해 여러개의 서버가 안전하게 계산하는 과정이 있다. 그러면 시기마다 랜덤하게 선택된 지분노드들이 일종의 협회가 되어 동전 던지기 프로토콜을 실행한다. 동전 던지기 프로토콜을 이용해서 해당 시대에 블록 생성때마다 리더를 선출하며 또 다음 시대에 협회를 구성할 지분노드를 뽑는다.
우리는 어떤 적도 지속성과 유효성을 망가뜨릴 수 없다는 논증을 보여주려 한다. 우로보로스는 그러기 위해서 몇가지 부담 안되는 가정을 하고 있다. (1) 네트워크가 서로 싱크가 맞아서 정직한 지분노드끼리 대화가 원활히 가능하다. (2) 각 시대에 정직한 대다수 지분노드들은 참여가 가능하다. (3) 그 노드들은 너무 긴 시간 동안 오프라인이 되지않는다 (4) 블록체인에 손상이 일어났을 때 잠시 지연이 되며 적응할 수 있는 능력이 있다.

4,5,6 생략.

모델 (Model, 5p.)

[#모델이라는 표현을 설명하고자 한다. 모델은 뭔가를 닮은 것이라는 뜻에서 아주 많은 분야에 사용되는 용어다. 개발용어로 쓸 때의 모델은 보통 그 엔진이 동작하는 것을 설명하기 위해 일종의 추상적인 도형 등등을 그리는 데 쓰는 등등 엄청나게 다양한 방식으로 사용한다. 여기 카르다노의 논문은 수학에 가까운 공학 논문이므로, "어떤 문제가 있고, 그것을 해결하기 위해 필요한 속성을 미리 정의한다"고 생각하면 된다. 예를 들어 우리가 가볍게 "시간이 지나면 1%씩 이자를 주는 개발을 해줘"라고 말하지만 여기서 시간이라는 것도 공학에서는 컴퓨터의 clock 단위를 통해 계산하는 모델로 정의해서 표현할 수 있을 것이다.]

시간(time), 슬롯(slots), 동시성(synchrony)

일단 시간을 쪼개 슬롯이라는 단위로 나눈다. 장부라는 개념은 각 슬롯과 연관되며 슬롯 하나당 하나의 장부 블록이 만들어지게 된다. 노드들은 서로 대략 비슷하게 맞춰진 시계를 갖고 있어서 그 시계가 지금 어느 슬롯인지 알려준다. 각 슬롯은 다음과 같은 속성을 가지고 있다.

현재 슬롯은 공개적으로 알려져 있고 시간과 함께 늘어남
각 노드는 현재 시간에 접근할 수 있음.
슬롯에 할당되는 시간이 꽤 충분해서 그 사이에 정직한 노드들이 메시지를 보내면 서로 받을 수 있다.

[#시간에 따른 블록 생성을 그림으로 다뤄보았다]

트랜잭션 장부의 속성들

트랜잭션 장부들은 "블록"이라는 단위로 나뉘어있고 다음 속성들을 만족해야한다.

지속성. 노드 하나가 어떤 트랜잭션이 안정되었다고 한다면 그 트랜잭션에 대해 조회하면 안정되었다고 알릴 것이다. 이 때 k라는 지표는 그 장부의 k 깊이에 있는 블록 안에 트랜잭션이 있어야 안정되었다고 인정할 때 사용된다.
유효성. 만약 모든 정직한 노드들이 어떤 트랜잭션을 받아들일려고 할때 u 슬롯의 시간이 지나야만 안정되었다고 하며, 그것이 트랜잭션이 확정되는 시간이라고 말한다.

논문 26-35 페이지 동안에는 지속성과 유효성이 다음의 세 기본적인 속성에서 도출될 수 있다는 것을 설명하고 있다.

선행체인 [#common prefix의 의역]. 어떤 체인1이 어떤 체인2의 마지막 k 블록을 잘라냈을 때 나머지라고 하자. 그러면 체인1이 체인2의 k 만큼의 선행체인이라고 정의한다.
체인 품질. 전체 체인 길이에서 정직한 노드가 만든 블록의 개수 비율
체인 성장률. 체인의 길이가 늘어나는 속도를 슬롯으로 측정

안전성 모델

[#슬슬 수학기호가 범벅이 되어 나타난다. 그 기호를 사용하지 않고 증명은 건너뛰어 결론들을 말로 설명해도 충분하다. 하지만 기호 자체의 표현을 완전히 무시하면 맥락이 틀릴 것이라 판단하였다. 그래서 임의로 기호를 살짝 변형해서 X { A, B, C, D} 이렇게 표현을 하겠다. 이것의 의미는 "X라는 기능/모델이 있는데 A,B,C,D를 참조해서 도출 할 수 있다"고 보면 된다.]

우리는 먼저 이상적인 기능 F를 이용해 만든 프로토콜 II의 안전성을 분석하는 시도를 할 것이다. 이 때 관련있는 표현들은 적(adversary)을 의미하는 A, (네트워크) 환경 Z, 안전성 지표 k, 그리고 이미 말했듯이 이상적인 기능 F가 있다고 한다. 이 이상적인 기능이 무엇을 할 것인지 정의를 해야 분석을 시작할 수 있다.
중요한 기능이 두 가지가 있는데 바로 "(트랜잭션을) 퍼뜨리는 기능" 과 "key와 트랜잭션 기능"이 있다.

퍼뜨리기(diffuse) 기능

퍼뜨리기 기능은 각 서버들에 유입되는 데이터를 유지시킨다. 서버가 실행되기 시작하면 이들은 유입되는 데이터를 마치 이메일 편지함처럼 받아들일 수 있게 된다. 그리고 서버들은 메시지를 퍼뜨릴 수 있는데 그러면 다른 서버들의 유입 데이터에 추가가 된다. 이 기능은 슬롯을 따라 반복되며 모든 서버는 한번의 주기 때 한번만 퍼뜨리기 기능을 사용할 수 있다. 만약 적이 있다고 가정하면, 당연히 이 기능을 사용할 것이고 받은 편지함도 볼 것이고 또 다른 서버들에게 메시지를 원하는 대로 전달할 것이다.
한번의 주기가 끝나면 퍼뜨리기 기능으로 인해 모든 받은 편지함은 퍼뜨려진 모든 메시지를 다들 담고 있게 될 것이다. 이 기능을 안쓰는 서버는 버려지게 된다.

키와 트랜잭션 기능

키 등록 기능은 처음에 n명의 사용자가 각각의 지분을 갖고 등록되었을 때부터 시작된다. 이 기능은 적하고도 상호작용을 하는데 아마 공개키(public key)가 등록 안된 경우 등등의 메시지가 올 것이며 이 때 해당 메시지를 보낸 유저를 "오염"되었다고 표시한다. 정직한 사용자에게는 공개키/개인키 쌍을 만들고 그것을 알고리즘에 의해 저장하게 될 것이다. 다음과 같은 행위들이 순서 없이 일어난다. (1) 어떤 유저가 공개키/개인키 쌍을 요청하고 이 기능이 그것을 제공한다 (2) 전체 공개키 저장소가 있고 사용자가 요청하면 보내준다. (3) "유저생성" 메시지를 환경으로부터 수신하면 위와 같은 과정으로 수행한다. (4) 이미 존재하는 유저들은 적에 의해 언제든 오염이 될 수 있는데, D개의 슬롯이 지난 후 "오염" 메시지로 인해 세팅이 된다.

위의 두개의 기능을 구현하는 F라는 기능성에 의해 프로토콜이 실행된다. 또한 아래의 추가적인 기능도 있다고 볼 수 있다.

각 슬롯마다 네트워크 환경 Z는 지분노드들 중 원하는 자들이 활성화하도록 허락해준다. 각각 지분노드들은 다른 노드에게 보낼 메시지를 만들 수 있다.
각 적들은 슬롯마다 최소한 마지막 노드로서라도 실행될 수 있다. (물론 적이 활성화되는 기간도 있다)

위의 모델을 살펴보면 적에게 강력한 힘을 줘서 이 프로토콜이 안전하다고 보장할 수 없는 상태라는 것을 알 수 있다. 그래서 환경에 적절히 제약을 줘서 안전성을 보장할 수 있게 하는 것이 매우 중요하다. 그것을 위해 다음과 같이 네트워크 환경에 제한을 줄 것이다.

(네트워크)환경에 주어지는 제약조건

환경은 정직한 지분노드들을 각 슬롯 주기마다 활성화 시킬 수 있어야하며 다음과 같은 제한이 있다.

각 슬롯마다 최소한 하나의 정직한 지분노드가 활성화되어야 한다
지표 k가 있어서 그만큼만 정직한 지분노드가 오프라인이 되어도 된다. 만약 정직한 지분노드 하나가 "생성" 메시지를 환경에 던져서 생성되면 그 때 새로운 지분노드에게 주어지는 체인은 반드시 그 전 슬롯에서 활성화 되어있던 지분노드의 것하고 완벽히 일치해야한다.
각 슬롯마다 각 지분노드들의 (공개키:지분) 모음을 정의할 수 있다. 만약 어떤 공개키가 "오염"되었으면 그 지분노드도 오염되었다고 본다. 우리는 적들의 지분의 합이 전체 지분의 50%보다 작으면 '적들의 상대지분이 50%보다 작다'고 표현할 것이며 그게 아닐 경우 나쁜상황1/2이라는 이벤트가 프로토콜에서 발생하게 된다.

포스팅 정리

카르다노의 소개 부분과 모델을 정의하는 부분을 정리해보았다. 막상 시작해보니 눈물나게 어렵다. 일단 정확하게 알기 위해 적당히 읽었던 부분도 한줄 한줄 확인해야하고, 수학적인 표현을 피하니 더욱 어려워진다 :( 핵심만 전달하면 될 것이라 생각했건만, 뭔가 "자명한" 말들만 늘어놓게 될 것 같기도 하다. 실제 읽는 사람들이, 그리고 미래의 내가 봤을 때 어떻게 받아들일 지는 아직 모르겠다 :)

그리고 블록체인에 대해 어느 정도 알고 있는 사람이라면 이번 포스팅 부분은 원래부터 알듯 말듯한 내용들을 설명했다고 느낄 수도 있다. 그것이 맞는 인상이다. 카르다노의 모델을 설정하는 부분은 기존에 논의되던 블록체인의 모델, 그것도 이미 컴퓨터 코드로 구현해놓은 것들의 문제를 추상화해서 정의하는 것이기 때문이다. 하지만 한줄한줄 가볍게 여길 수 없는 것이, 그렇게 수학적인 기호를 이용해 설정한 모델들은 엄밀할 뿐만 아니라 서로 엮여서 정리가 만들어지고 해당 PoS 프로토콜의 안전성을 검증하는 데 사용되기 때문이다. 슬롯, 지분노드, 메시지, 지속성, 유효성, 퍼뜨리기 기능, 키 생성 기능 등등이 모두 하나의 주장을 뒷받침하기 위해 이어진다.

다음 포스팅에서는 각 모델들을 엮어서 어떻게 forkable string이라는 것을 정의했고, 그것으로부터 어떻게 PoS 프로토콜의 흐름이 궤도를 안벗어난다는 것을 보여주는 지 즉, 네트워크가 안전하다는 것을 증명하는지 설명하겠다. 물론 증명은 간단히만 짚고 정의와 정리만 설명할 것이다.

영어 듣기가 어느 정도 된다면 이 영상을 보는 것을 추천한다. 우로보로스를 옥스포드 대학교에서 발표하는 강연이며, 개념만을 간단히 다루고 있다.

다음 포스팅에서는 본격적으로 프로토콜에 대한 개괄 설명 및 지분이 고정되어 있는 모델에서 프로토콜의 안전성을 탐색하는 static stake 모델을 설명하겠다.