Cryptographic Sortition
블록체인 네트워크에는 공동의 의사결정을 내릴 수 있는 중앙 서버가 존재하지 않는다. 따라서 동일한 정보를 모든 참여자들에 분산하여 저장하고 있다. 여러 참여자가 같은 정보를 저장하기 위해서는 합의 알고리즘이 필요하며, 많은 연구자들에 의해 다양한 알고리즘이 개발되고 있다. 지난 2018년, MIT의 Silvio Micali 교수는 BFT 기반의 순수 지분 증명(PPoS) 합의 알고리즘과 VRF(Verifiable Random Function)를 활용한 블록체인 ‘Algorand’를 선보였다. Algorand는 어떠한 방식으로 위원회(Committee)를 선출하고 있는지, 그 과정에서 VRF를 이용하여 어떻게 Cryptographic Sortition을 해결하고 있는지 알아보도록 하자.
Cryptographic Sortition이란 암호학적 접근을 바탕으로 네트워크 참여자 중 위원회(Committee)를 선출하는 문제를 해결하는 것이다. 텐더민트 합의 알고리즘처럼 미리 정해진 규칙에 따라 선출되는 방식과 달리, 참여자가 각자의 계산 과정을 통해 자신의 선출 여부를 공표하는 방식이다. 이는 참여자가 자신의 선출 여부에 대해 알 수 있어야 하고, 다른 참여자가 공표를 검증할 수 있는 형태로 이루어져야 한다. 또한, 참여자의 Private Key을 모르는 사람은 그 참여자가 위원회로 선출되었는지 미리 알 수 없어야 한다. 따라서 모든 참여자는 자신이 아닌 다른 참여자의 선출 여부가 담긴 결과를 Random 값과 구분할 수 없어야 한다.
이 문제를 전자 서명을 이용하여 해결하고자는 제안이 존재한다. 어떤 메시지와 그것에 대한 서명의 해시한 값이 클수록, 더 많은 투표권을 주자는 것이 이 제안의 핵심 아이디어이다. 이 방식은 1) 각 참여자의 고유한 Identity인 Private Key로부터 해시가 생성되고, 2) Public Key로 다른 참여자가 검증할 수 있으며, 3) 서명의 특성에 따라 출력된 해시들이 Random하게 보일 수 있다는 세 가지 조건을 만족한다. 하지만 한 가지 문제가 존재한다. 많은 전자 서명은 한 가지 메시지에 대응되는 유효한 서명이 여러 개 존재하기 때문에, 만약 참여자의 서명 생성에 제한이 없다면, 하나의 Message에 대해 반복적으로 서명을 생성할 수도 있다. 이 경우, 해당 참여자는 높은 Hash 값을 얻기 위해 자신이 시도할 수 있는 횟수만큼 생성할 것이고, 충분히 큰 Hash 값을 얻었을 때 자신의 Hash값을 공개할 것이다. 이러한 문제 때문에, 위 방법을 실용화하는 현실적으로 불가능하다.
Algorand는 이러한 한계를 VRF(Verifiable Random Function)를 이용하여 극복했다. VRF는 참여자의 Secret Key와 Seed 값을 이용하여, Random Hash와 Proof를 출력한다. 이 Proof는 Secret Key로부터 Hash가 생성되었다는 것을 담고 있다. 역으로, 참여자의 Public Key와 Hash 그리고 Proof를 통해, 이 Hash 값의 타당성을 검증할 수 있다. 또한, Algorand는 참여자가 투표를 통해 당선될 확률을 Chain에서 가지고 있는 지분에 비례하도록 설계했다. Algorand가 이 조건을 추가한 이유는 시빌 공격(Sybil Attack)을 막기 위함이다. 한 명의 공격자가 마치 여러 명인 것처럼 속임으로써, 여러 참여자의 의사 결정을 제어할 수 있다. 결국 참여자들의 의사 결정에 혼란을 야기하는데, 이 공격을 시빌 공격이라 한다.
Algorand는 위 알고리즘을 이용하여 Cryptographic Sortition 문제를 해결한다. 참여자 자신이 선출되었는지 확인하기 위한 Secret Key `sk`와 Seed 값인 `seed`, 추첨 과정에서 추첨될 참여자의 수를 조절하기 위한 임계값 `𝛕`, 추첨을 통해 수행할 특정 역할 `role`, 사용자가 소유하고 있는 지분 ‘w`, 시스템 내의 전체 지분인 ‘W`가 필요하다. 여기서 역할이란 Algorand의 특성 상 Validator와 Block Proposer 등 선정될 수 있는 역할이 많기 때문에 그들을 나타내는 ‘role factor`가 필요하다.
만약 이러한 방식으로 위원회를 선정한다고 했을 때, 어떠한 공격이 발생할 수 있을까? 악의적 참여자는 1) Seed 값을 조절하거나, 2) Role Factor를 변경하거나, 3) 시빌 공격을 취하는 방법으로 공격을 시도할 수 있다. Seed 값은 직전 Block과 Chain에서 결정되는 값을 사용하고 있기 때문에, 참여자가 이를 조절할 수 없으므로 Seed 값 변경을 통한 공격은 불가능하다. 또한, Role Factor는 항상 고정된 상수 값을 사용하고 있기 때문에 공격이 불가능하다.
마지막으로 시빌 공격은 어떻게 대응할까? 앞서 설명한 것처럼, 참여자가 위원회로서 표를 갖게 될 확률은 지분의 비율에 비례한다. 이때, 표를 가질 수 있는 확률변수는 이항분포를 따르게 된다. 마찬가지로 이항분포를 따르는 두 확률변수에 대해, 확률변수의 합 역시 이항분포를 따르게 된다[1]. 따라서 1명의 악의적 참여자가 100명의 참여자로 지분을 나누어 공격하더라도, 당선 확률을 같기 때문에 공격은 불가능하다.
지난 12월, CodeChain 엔지니어 김선표님은 Cryptographic Sortition에 관한 TechTalks를 진행했다. 아래의 영상은 Algorand가 VRF를 이용하여 Cryptographic Sortition을 해결하는 알고리즘의 자세한 설명을 포함하고 있으며, CodeChain에 적용함에 있어 발생하는 문제점에 대해 논한다. 더 궁금한 점이 있으면, 아래의 영상에서 확인해보자.
[CodeChain | Cryptographic sortition] presentation video: https://youtu.be/M4SvmK8G4uo
[1] The example of binomial distribution in VRF
Reference: Gilad, Y., Hemo, R., Micali, S., Vlachos, G., & Zeldovich, N. (2017, October). Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles (pp. 51–68). ACM.
