ALGO; 기본에 충실하자

해당 글은 Algorand Whitepaper의 일부와 Silvio Micali's Lecture on Algorand을 참고하여 작성한 글입니다.

Blockchain Trilemma

Security

프로토콜의 security는 프로토콜에 의해서 유저들이 메시지를 보내고 코딩하는 것을 말한다. 하지만, 단지 프로토콜을 넘어서 커뮤니케이션 네트워크의 security도 생각해야한다. 현재 많은 블록체인 프로토콜은 네트워크의 security에 대해서는 많은 준비가 안되어 있다.

Scalability

전 세계 사람들이 사용할 수 있는 프로토콜을 만들고 싶다면, scalability는 필수이다. 하지만 비트코인과 같이 1초에 7개의 transaction만 검증된다면, 일상생활에서 사용하기는 힘들다.

Decentralization

분산화는 다음과 같은 장점을 가진다. 첫번째로, 제 3자를 믿을 필요가 없어진다. 두번째로, point-of-failure가 없어진다. 세번째로 어느 기업이 독점하지 않기 떄문에 이유 없는 가격/수수료 상승이 없어진다. 하지만, 대부분의 블록체인 프로토콜은 몇개의 마이닝 풀에 의하여 작동한다.

→ Algorand는 이 Trilemma의 3 꼭짓점을 모두 만족시킨다.(라고 주장하신다.)

---

Algorand의 features

Pure Proof of Stakes

모든 토큰은 같은 힘을 가진다. 이 말은 스테이킹 되는 토큰과 그냥 일반 지갑에 들어 있는 토큰이 같은 힘을 가진다는 말이다.

일반 프로토콜에서는 마이너들만 블록 생성에 관여하는 것과 달리 Algrorand는 모든 유저들이 블록 생성에 참여할 수 있도록, 참여 과정을 간단하고, 낮은 가격으로 할 수 있도록 만들었다. 만약 참여할 수 없다면, 자신의 권리를 다른 사람에게 위임할 수는 있다.

프로토콜에 참여하거나 위임하는 경우에는 인센티브를 얻을 수 있다.

Immediate propose-and-agree

Algorand는 다음 블록 생성을 위한 compuation을 최소화하는 것을 목표로 한다.

또한, 비트코인에서는 각각의 마이너들이 블록을 생성한 뒤에 전파하여서 완전한 합의가 아닌 longest chain rule에 의하여 합의를 한다. 하지만, Algorand는 전체 프로토콜의 구성원 전부가 합의를 한 뒤에 블록체인에 추가하는 형태의 합의 메커니즘을 만들었다. 고로 다른 블록체인 프로토콜에서는 흔히 일어나는 soft fork는 일어날 수 없다.(정말 정말 낮은 확률로 일어날 수 있지만, 이는 불가능에 가깝다.)

Evolvability

다른 블록체인 프로토콜의 경우에 커뮤니티에서 어떤 기능의 추가에 대하여서 의견이 맞지 않을 때 합의를 못하고 하드 포크가 일어나는 경우가 있다. 이와 같은 행위는 확장에 반한다. 대신 Algorand의 합의 메커니즘은 제안과 동의(propose and agree)로 이루어져 있다. 보통 이 메커니즘은 다음 블록을 생성할 때에 사용되지만, 새로운 기능이나 통화정책을 정할 때도 사용 가능하다. 즉 모든 구성원이 동의를 해야만 업데이트를 할 수 있다.

---

Algorand's two-step road to consensus

Step 1: Proposal

하나의 퍼블릭 키(유저)가 랜덤하게 선택되어서 이 유저가 새로운 블록을 제안한다. 이 과정은 매우 빠르게 진행된다.

디테일

r 라운드의 새로운 블록 생성 과정에 대한 디테일을 알아보자.

$B^{r} = (r, PAY^{r}, Q^{r}, H(B^{r-1}))$

• $B$: 블록
• $r$: r라운드
• $PAY$: 해당 라운드의 지불(거래)의 집합
• $Q$: 조작이 불가능한 어떤 상수
• $H$: 해시 함수로 $H(B^{r-1})$는 이전 블록의 해시값을 말한다.

유저는 eligible player -> potential leader -> leader의 과정을 거쳐서 leader가 될 수 있다.

eligible player가 되려면

참여자는 이미 k라운드 전부터 프로토콜에 참여하고 있어야 한다. 이를 나타내면, 현재 r라운드 일때 유저 i는 (r-k)라운드의 퍼블릭 키에 포함되어 있어야 한다.

$i \in PK^{r-k}$

• $i$: 참여자
• $PK$: 퍼블릭 키

potential leader가 되려면

라운드 r의 유저 i가 potential leader가 되리면 다음을 만족하여야 한다.

$.H(SIG_{i} (r, 1, Q^{r-1})) \leq p$

• $SIG_{i}$: 유저 i의 전자서명
• $.$: 소수점으로 해당 값을 0~1 사이의 값으로 만든다.
• $p$: 최소 한명의 potential leader가 honest하게 만드는 확률값

유저들은 각자 cryptographic lottery(해당 수식)을 돌려서 자신이 당첨(potential leader)이 되는지 확인할 수 있다. 자신이 당첨되었는지 아닌지는 자신만 알 수 있기 때문에, 악의적인 이용자가 검증자를 corrupt시키려 해도 누구를 corrupt해야할지 알 수가 없다.

potential leader가 되었을 때

자신이 potential leader라는 것을 알게 된 유저 i는 이제 자신만의 후보 블록(candidate block)을 만들어서 다른 참여자들에게 전파하여야 한다. 유저 i의 후보 블록은 다음과 같다.

$B^{r} = (r, PAY_{i}^{r}, SIG_{i}(Q^{r-1}), H(B^{r-1}))$
주목해야 하는 것은 $PAY_{i}^{r}$에서 i가 붙는 것과 같이 각자의 후보 블록에 포함되는 거래들은 전부 다를 수 밖에 없다.

현재까지는 i가 potential leader라는 사실은 i만 알고 있다. 그리하여, 만약에 i가 해당 후보 블록만 다른 참여자에게 전파한다면, 다른 참여자들은 i가 진정으로 potential leader인지 알 수 없다. 그리하여 $i$가 전파하는 라운드 $r$의 스텝 $1$ 메시지

$m_{i}^{r,1}$

에는 자신이 potential reader의 자격이 있다는 자격 증명서 $\sigma_{i}^{r,1}$을 $B^{r}$와 함께 첨부해서 보낸다.
$\sigma_{i}^{r,1}$은 다음과 같이 구성되어 있다.

$\sigma_{i}^{r,1} = SIG_{i}(r, 1, Q^{r-1})$

악의적인 참여자가 유저 i가 이제 potential leader라는 사실을 알고, corrupt시키려 하여도 이미 메시지는 전파되었기 때문에 의미가 없다.

Step 2: Agreement

이 새로운 블록을 검증할 검증자들을 유저들로부터 랜덤하게 천명 뽑는다. 그리고 이 검증자들은 새로운 블록에 대하여서 합의에 이른다.

디테일

검증자가 되려면

라운드 $r$의 step $S$의 검증자 집합을 $SV^{r,s}$이라 할 때, $SV^{r,s}$는 Step1과 동일하게 라운드 $r-k$에 존재하는 참여자로부터 랜덤하게 뽑는다.

$i \in PK^{r-k}$

해당 참여자 중에 다음과 같은 수식을 만족하면 $SV^{r,s}$의 검증자가 될 수 있다.

$.H(SIG_{i} (r, s, Q^{r-1})) \leq p^{'}$

• $p^{'}$: honest 참여자 수가 malicious 참여자 수보다 threshold보다 크게 만드는 확률값

앞서 언급된 과정과 비슷하게 검증자 i는 자신이 검증자라는 것을 알리기 위하여 자격 증명서 $\sigma_{i}^{r,s}$를 $m_{i}^{r,s}$에 담아 전파시킨다.

leader가 되려면

이제 여러명의 potential leader들 중에 실제로 블럭 생성의 역할을 맡을 leader를 뽑아야 한다. $SV^{r,s}$의 검증자들은 potential leader들로부터 전파받은 작업 증명서 $\sigma_{i_{1}}^{r,1}$, ..., $\sigma_{i_{n}}^{r,1}$를 가지고 각 해시 값을 계산한다.

$H(\sigma_{i_{1}}^{r,1})$, ..., $H(\sigma_{i_{n}}^{r,1})$

이 해시 값들 중에 가장 작은 값을 가지는 $\sigma_{i_{j}}^{r,1}$를 찾고, 해당 j를 leader로 뽑는다.

• $\ell_{j}^{r}$: j가 라운드 r의 리더

Effortless One-by-One Byzantine Agreement

블록체인은 블록이 체인에 따라 하나 하나씩 추가되는 것이다. Algorand는 pure PoS를 사용함으로, effortless, 즉 computational cost가 굉장히 작고, one-by-one, 비트코인과 달리 하나의 블록을 추가할 떄 모든 구성원의 합의가 있으므로, fork가 생기지 않는다.

Byzantine Agreement는 커뮤니케이션 프로토콜로 하나의 프로토콜에 다수의 honest(제시된 메커니즘을 따르는) 유저들이 있을 때 다음과 같은 2개의 조건을 만족한다. 첫번째, 모든 honest 유저들은 같은 값에 합의한다. 두번째, 만약 그들이 같은 값으로 시작하였다면, 그 값으로 다 같이 합의해야 한다.

이 Byzantine Agreement는 블록체인과 어떤 관계가 있을까? 블록체인의 가장 큰 챌린지는 어떻게 다음 블록을 선택하고 합의하느냐이다. 모든 노드들은 각자만의 제시할 다음 블록이 있고, 프로토콜은 하나의 블록으로 노드들이 합의할 필요가 있다. 고로 우리는 모든 블록에 대해 Byzantine Agreement에 도달해야한다.

하지만, Byzantine Agreement에도 문제가 있다. 첫째로, 굉장히 느리다. 두번째로, 실제 premissonless system에서는 참여자(노드)들이 고정되어 있지 않고, 자유롭게 추가될 수 있고 그 참여자들이 누구인지 알 수도 없다.