<aside> 🏎️ Formula Zero 는 Nonce Open Source Lab 소속으로, Tezos Foundation 의 지원을 받아 PoS 기반 블록체인의 Light Client를 연구하는 프로젝트입니다.
</aside>
스마트폰 같은 연산 자원이 제한적인 환경을 가진 IoT 모바일 기기에서 블록체인 네트워크를 접근하기 위해서는 블록체인의 모든 데이터를 보유한 Full Node가 제공하는 API를 통해 최신 블록을 가져온다. Full Node를 전적으로 신뢰하지 않는다면 수신한 블록에 대한 검증을 위해 기기 자체적으로 데이터를 유지하고 있어야 한다. 연산 자원이 제한적이므로 1) 해당 데이터를 얼마나 최소한으로 유지할 수 있는지, 2) 해당 데이터를 기반으로 한 검증 연산이 얼마나 빨리 수행할 수 있는지가 매우 중요하다. 이 두가지 사항은 연결된 블록체인 네트워크의 합의 알고리즘(ex. Proof of Work, Proof of Stake)에 따라 달리 접근해야한다.
Proof of Work (PoW)는 확률에 기반한 합의 알고리즘이다. 블록에 대해 합의할 때 투입된 연산량이 충분하다면 추후 공격자에 의해 re-org 될 가능성이 거의 없다고 믿는 것이다. 합의된 블록체인의 신뢰는 0번째 블록인 제네시스 블록과의 연결성에서 비롯되기에, 이 연결고리를 최소한의 데이터로 어떻게 효율적으로 증명해 내는 것이 PoW Light Client의 핵심이다. 비트코인에서는 제네시스 블록부터 최신 블록까지 블록의 헤더만 유지하는 것으로 이 연결고리 검증이 가능하다. 다만 블록체인의 길이에 따라 보유해야할 헤더 데이터 크기 또한 선형적으로 증가하기에 이를 최소 sub-linear 크기의 subgroup만 유지하는 방향으로 연구가 진행되었다. 대표적으로 NiPoPoW 와 FlyClient 가 있다. NiPoPoW 는 블록의 난이도(Difficulty) 와 논스(Nonce) 에 기반하여 re-org 될 확률이 매우 희박한 블록들을 Supernode로 지정한다. 제네시스 블록부터 Supernode들의 체인만Lightweight Client 에서 유지하고 있는 방식으로 제안했으며 해당 데이터 크기는 log(N) 정도이다. FlyClient 는 확률 기반의 블록 샘플링 프로토콜과 Merkle Mountain Range(MMR) commitment 를 블록 헤더 관리에 적용하여 데이터 크기를 최소화한다.
Proof of Stake (PoS)는 정해진 검증인 집합(Committee)의 2/3 이상의 합의에 기반한 알고리즘이다. 검증인은 합의 과정에 참여하기 위해 일정의 stake 를 Deposit 해두고 악의적인 행동에 대한 Penalty를 갖는다. 확률 기반의 PoW 와는 다르게 블록은 완결성(Finality) 100%를 갖는다. 즉 Light Client는 제네시스 블록에서의 연결고리보다는 블록에 포함된 검증인 서명의 유효성을 검증하고 검증인 집합의 변경사항을 추적하는 데 필요한 데이터를 자체적으로 유지해야 한다. 즉, NiPoPoW 나 FlyClient 와는 전혀 다른 접근법이 필요하다. 이번 아티클에서는 PoS 기반인 Celo 블록체인이 제안한 Light Client 인 Plumo 를 분석하고 PoS 에서의 Light Client 설계시 고려할 사항을 정리해본다. (아래 사용한 여러 용어들은 Plumo 에서 제안한 것을 그대로 차용하였다.)
Light client 가 유지해야하는 데이터를 생성하는 함수를 Summary Function $S$ 라고 하자. $S$ 를 통해 전체 블록체인을 검증하고 최소한으로 요약된 데이터는 추후 전달받은 최신 블록에 대한 유효성을 검증하는데 기반이 된다. 이 데이터의 크기와 검증 시간이 블록체인의 길이와 상관없이 Constant 하다면 Light client 입장에서 최적이다. 이를 구현하는 방식으로 영지식(Zero Knowledge, ZK)을 활용한 SNARK (Succint Non-interactive ARgument of Knowledge)가 있다. Light Client 가 유지할 데이터는 세가지 1) 제네시스 블록, 2) 동기화된 마지막 블록, 3) ZK Proof 이다. ZK Proof 는제네시스부터 마지막 블록사이의 중간블록들의 연결고리에 대한 유효성을 증명한다. 블록체인의 길이와 상관없이 Constant 한 데이터 크기를 유지할 수 있으나, 최종 블록이 갱신될 때 마다 전체 블록체인에 대한 ZK Proof를 새로이 생성해야 하고 블록체인 길이와 quasi-linear 한 시간이 소모되기에 실용적이지 않다. 그렇다면, 전체 블록체인에 대한 증명이 아닌 동기화되어 검증된 마지막 블록에서부터 최신 블록까지 증명하는 방식을 고려할 수 있다. 이를 Summary Update Function $U$ 이라고 하자.
Summary Update Function $U$ 는 업데이트를 통해서 데이터 요약을 갱신하는 방식이다. 제네시스 블록에서 블록 $a$ 까지 검증했다면, 추후 최신 블록 $b$ 까지 늘어난 블록체인의 Summary Function $S$ 은 $a,b,$ ZK Proof$_{a\rightarrow b}$가 될 것이다. 전체 블록체인에 대해 요약된 데이터의 크기를 Constant 하게 유지하지 못하지만 데이터 크기가 작아지므로 Zk Proof 생성시간과 동기화 속도에 대해 이점을 얻는다. Update Function 수행시 필요한 데이터는 기본적으로 블록 $a$ 부터 블록 $b$ 까지 발생한 모든 블록들이다. 이 블록들 전부를 다운로드받아 검증하는 것은 데이터 비용 뿐만 아니라 검증시 중간에 포함된 블록들의 크기만큼 시간이 소요된다. 그렇기에 해당 Update 를 Constant 한 비용으로 처리할 수 있는 방안이 필요하다. SNARK를 적용하여 블록 $a$ 부터 블록 $b$ 까지의 상태전이를 Constant size의 증명 ZK Proof 로 대체하는 것이다. PoS 에 따르면 각 블록을 검증할 때 해당 블록에 대해 서명한 검증인 집합의 2/3 에 대해서 서명을 검증해야 하므로 $|b-a|$에 따른 시간 비용이 소모된다. 이를 Constant 또는 sub-linear 하게 바꿔줄 함수를 Update Advice Function $A$ 이라고 하자.
Update Advice Function $A$ 은 Summary Update 를 동기화가 필요한 sub-블록체인 길이에 상관없이 SNARK를 적용하여 constant 하게 만들어주는 함수이다. 실용적이기 위해서는 블록 검증에 필요한 연산을 최소화해야 하여 SNARK의 ZK Proof 생성시간을 줄여야 한다.. 블록에 포함된 검증인 집합의 서명을 각각 검증하는 것이 아닌 Aggregate 하여 검증할 수 있다면 비용을 줄일 수 있다. 또한 블록 a 에서 b까지 각 블록에 포함된 Aggregate 서명을 다시한번 Aggregate 해서 검증할 수있다면 near-constant 하게 줄일 수 있다. 이렇게 서명을 Aggregate 하는데 주목받는 알고리즘이 BLS 서명 알고리즘이다.
Plumo Architecture Overview (from Plumo paper)
위에서 설명한 Summary - Summary Update - Update Advice Function을 정리하면 다음과 같다. $s \rightarrow s'$ 의 블록체인 상태 전이를 증명하기 위해서 다음과 같은 단계를 거친다.
Full Node 는 Prove 역할을 하고, Light Client는 Verify 를 수행하면 상태전이의 유효성을 검증할 수 있기에 업데이터 대상인 sub-블록체인의 길이와 상관없이 $s,s',\pi$ 의 tuple만 유지하면 된다. (전체 블록체인을 구성하는 sub-블록체인의 개수에 따라 해당 tuple 이 여러 개 필요하다.) Aggregate 가 연산 최적화의 핵심이기에 BLS 서명 알고리즘에 대해서 알아보자. SNARK 에 적합한지 여부를 살펴보면 Summary Update Function $U$ 을 최대한 효율화 할 수 있다.