김성준, Virtual Machine & Optimization Lab in Seoul Nat’l University
본 포스팅에서는 Huang, Yuming, et al. “Do the Rich Get Richer? Fairness Analysis for Blockchain Incentives.” Proceedings of the 2021 International Conference on Management of Data. 2021. [1]을 다룬다.
들어가며
본 논문의 저자들은 PoW 및 PoS 프로토콜에서 사용되는 인센티브 모델의 공정성이라는 개념에 초점을 맞춘다. 블록체인에서 신뢰할 수 없는 노드들의 자발적이고 정직한 행동을 유도하기 위해서는 적절한 인센티브의 제공이 필수적이다. 인센티브 설계에 문제가 있다면 자칫 공정성이 훼손될 가능성이 있고, 공정성이 깨져버리면 결과적으로 특정 노드의 채굴 파워 독점을 초래한다. 이는 탈중앙화를 전제로 하는 블록체인 정신에 위배되는 매우 부정적으로 작용한다.
본 논문에서는 인센티브 모델의 공정성을 두 가지 관점에서 정의한 뒤, 블록체인에서 널리 사용되는 네 종류의 합의 알고리즘이 공정하게 동작하는가 및 공정성이 확보되는 임계 조건을 수학적으로 분석한다. 또한 이론적인 분석에 그치지 않고 시뮬레이션을 통해 일부 합의 알고리즘의 인센티브 모델이 공정하지 않음을 실험적으로 입증한다.
공정성을 평가하고자 하는 합의 알고리즘은 크게 네 종류이다.
1. Proof-of-Work (PoW)
가장 유명한 합의 알고리즘으로, 채굴자들은 일종의 암호학적 퍼즐을 풀기 위해 컴퓨터 자원을 사용한다. 논스를 포함하는 블록의 해시값이 타겟값 D보다 작도록 하는 논스값을 가장 먼저 찾는 채굴자는 새로운 블록을 생성할 권한을 얻으며, 블록 생성에 따른 보상을 인센티브로 얻는다.
두 채굴자가 각각 H_A 및 H_B의 해시레이트를 가진다면, 채굴자 A가 B보다 먼저 블록 채굴에 성공할 확률이 H_A/(H_A+H_B)로 주어짐을 쉽게 유도할 수 있다.
PoW 합의 알고리즘을 사용하는 대표적인 암호화폐로 비트코인이 있다.
2. Multi-Lottery Proof-of-Stake (ML-PoS)
위의 PoW에서의 채굴 확률이 해시 연산 속도에 비례하기에 단순 연산에만 막대한 에너지를 소비한다는 문제점이 제기되면서, 이러한 에너지 낭비를 막기 위해 지분에 비례하여 블록 채굴 권한을 얻을 확률이 증가하는 지분증명 합의 알고리즘이 발명되었다.
그중에서도 ML-PoS에서는 타겟값이 채굴자의 지분에 비례하며, 해시 연산에 사용하는 파라미터로 논스가 아닌 타임스탬프를 사용함으로써 모든 채굴자가 단위시간당 동일한 회수의 연산만 수행할 수 있도록 설계되었다. PoW와 마찬가지로 아래의 조건식을 가장 먼저 만족한 블록이 새로운 블록으로 채택된다.
두 채굴자가 각각 S_A 및 S_B만큼의 지분을 가질 때, 채굴자 A가 B보다 먼저 블록 채굴에 성공할 확률은 S_A/(S_A+S_B)에 근사된다(정확히 같지는 않음에 유의하자).
ML-PoS 합의 알고리즘을 적용한 암호화폐로 Qtum과 Blackcoin이 있다.
3. Single-Lottery Proof-of-Stake (SL-PoS)
ML-PoS에서 타임스탬프 정보를 가지고 조건에 부합하는 정답을 채굴자가 제시할 때까지 여러 차례 반복하여 수행하는 반면, SL-PoS에서는 각 채굴자들이 시간(time)으로 표현되는 일종의 복권 티켓을 부여받는다. 여기서 말하는 시간은 해당 후보 블록이 유효해지는데 걸리는 시간을 의미하며 아래의 계산식에 의해 주어진다.
각 채굴자의 후보 블록이 유효해지는 시간을 부여받으면, 이들 중 가장 값이 작은, 즉 가장 빨리 유효해진 블록만이 블록체인상에 받아들여지며 이외의 후보 블록들은 버려진다. 계산식에서 알 수 있듯이, 지분이 높은 채굴자가 생성한 블록이 상대적으로 더 빠르게 유효해질 가능성이 높아지도록 설계된 합의 알고리즘이다.
한 가지 주목할만한 점으로, 두 채굴자 A와 B가 각각 S_A와 S_B만큼 비율로 지분을 할당하고 있는 상황에서 채굴자 A가 B보다 먼저 채굴에 성공할 확률은 S_A/2S_B로 계산된다. 눈치가 빠른 독자라면, 그 값이 S_A/(S_A+S_B)로 주어지지 않음에 의아함을 느낄 것이다. 이는 곧 SL-PoS에서 채굴 보상의 기댓값은 채굴자가 보유한 자원에 비례하지 않음을 의미한다.
SL-PoS 합의 알고리즘을 적용한 암호화폐로 NXT가 있다.
4. Compound Proof-of-Stake (C-PoS)
C-PoS에서는 (i) 새로운 블록을 제안하는 블록 제안자(proposer)와 (ii) 새 블록의 유효성을 검증하는 증명자(attester)가 보상을 받는다. 이때 증명자가 받는 보상은 지분에 비례하게 분배되며, 블록 제안자는 지분에 비례한 확률로 무작위로 선출된다.
현재 개발중인 이더리움 2.0에 적용될 예정이다.
그렇다면 어떻게 하면 인센티브 모델의 공정성을 수학적으로 모델링할 수 있을까? 저자들은 본 논문에서 2가지 관점에서의 공정성을 제시한다.
첫번째는 expectational fairness으로, 채굴자가 가지고 있는 자원의 양과 이에 대응되는 채굴 보상의 기댓값이 비례하는가에 대한 공정성이다. 채굴자가 전체 자원의 10%에 해당하는 자원으로 채굴을 수행한다면 채굴 보상의 기댓값 또한 전체 채굴 보상의 10%일 때 인센티브가 주어지는 방식이 공정하다고 말할 수 있을 것이다. 여기서 말하는 자원이란 PoW에서는 해시 파워를, PoS에서는 채굴자의 지분을 의미한다.
두번째로 제시하는 공정성은 robust fairness이다. Robust fairness의 컨셉을 명확히 하기 위해, 아래의 조건식을 만족하면 (𝜀, 𝛿)-fairness를 만족한다고 정의한다.
이를 해석하면, 채굴자가 얻은 채굴 보상의 비율이 채굴자가 가진 자원 비율에 𝜀만큼의 오차를 가감한 범위 내에 들어갈 확률이 1-𝛿 이상이면 (𝜀, 𝛿)-fairness를 만족한다는 의미다.
그렇다면 왜 굳이 직관적으로 명확한 expectational fairness 이외에 robust fairness라는 개념을 추가로 정의하는 것인지 의문이 생길 수 있다. 이를 이해하기 위해서는 expectational fairness 여부가 오직 채굴 보상의 기댓값에만 의존한다는 문제점을 인지하여야 한다. 예를 들어, 전체 채굴 자원의 10%를 가진 채굴자가 N개의 블록이 채굴되는 동안 90% 확률로 아무런 채굴 보상도 얻을 수 없지만, 10% 확률로 N개의 블록에 대한 모든 채굴 보상을 독식하는 극단적인 인센티브 모델을 가정해보자. 분명 채굴 보상의 기댓값은 보유한 채굴 자원과 비례하지만, 이러한 모델 하에서는 인센티브 분배가 너무나 극단적이기 때문에 운좋게 선택된 단 하나의 노드만이 모든 채굴 보상을 독점하게 된다. 따라서 expectational fairness 만으로는 보다 진정한 의미의 공정성을 평가할 수 없기에 robust fairness를 도입한 것이라 이해할 수 있다.
자, 그렇다면 넷 중 어느 인센티브 모델이 expectational fairness 그리고/또는 robust fairness를 달성했을까?
채굴자가 단 둘만 존재한다는 가정 하에 이론적으로 분석했을 때, SL-PoS를 제외한 세 인센티브 모델 모두 expectational fairness를 만족했다. 반면 PoW 만이 충분한 개수의 블록이 채굴된다는 전제 하에 다른 조건 없이 robust fairness를 만족하였다. C-PoS의 경우 조건이 비교적 널널하기에 robust fairness를 만족시켰으며, ML-PoS는 그 조건이 현실적으로 달성하기 어렵기에 robust fairness를 만족시키지 못했다.
저자들은 이론적인 분석에 그치지 않고 추가적인 실험을 수행하였다. 아래 그림은 각 인센티브 모델에 대한 시뮬레이션 결과를 나타낸 것이다. 주황색 선으로 표시된 시뮬레이션 평균값이 a=0.2에 근접한다면 expectational fairness가 달성된 것으로, 하늘색 시뮬레이션 영역이 점선으로 표시된 공정 영역 [(1 − 𝜀)𝑎, (1 + 𝜀)𝑎]에 포함된다면 robust fairness가 달성된 것으로 해석할 수 있다. 𝜀 = 0.1, 𝛿 = 10%가 사용되었다.
위 그림에서 확인할 수 있듯이, PoW 및 C-PoS의 경우 충분히 많은 블록을 채굴한 뒤부터는 안정적으로 공정성이 달성되는 모습을 확인할 수 있다. ML-PoS에서는 expectational fairness는 달성되었으나 채굴 보상의 편차가 너무 커 robust fairness는 달성되지 못한 것을 확인할 수 있으며, SL-PoS의 경우 블록 채굴이 진행될수록 채굴 보상이 0으로 수렴하여 공정성이 확보되지 못함을 알 수 있다.
아래 그림은 채굴자가 보유한 자원 비율에 따른 불공정 확률을 그래프로 표현한 것이다. 초기에 높은 자원을 할당받은 채굴자일수록 기대하는 보상 범위를 벗어난 채굴 보상을 얻게 될 확률이 낮아진다는 공통점을 확인할 수 있다. 이는 지분이 매우 적은 채굴자들에게 있어 일정 수준의 불공정성을 감수해야 한다는 나쁜 소식으로 다가올 수 있다. 네 종류의 합의 알고리즘 중 오직 PoW만이 블록 채굴이 진행됨에 따라 채굴 보상이 완전히 공정하게 분배되게끔 수렴한다는 사실 또한 주목할 만하다.
마지막으로, 초기 자원 할당량을 고정한 뒤 블록 채굴 보상 비율을 조절했을 때의 불공정할 확률 또한 제시하였다. 여기서 채굴 보상 비율이란 전체 지분 대비 주어지는 블록 채굴 보상의 비율이다. 예를 들어, 채굴에 참여하는 지분총량이 100이고, 매 블록마다 1만큼의 보상이 주어진다면 채굴 보상 비율 w=0.01이다. 실험 결과 채굴 보상 비율이 낮을수록 공정성이 높아지는 경향을 보였는데, 이는 블록 채굴 성공 여부가 다음 블록 채굴에 더 적은 영향을 미치기에 보다 공정하다는 직관적인 해석이 가능하다.
C-PoS의 경우, 인플레이션 보상 v을 높이는 것이 공정성 개선에 도움을 주었다. 인플레이션 보상은 모든 채굴자의 지분에 비례하여 고르게 분배되므로 제안자 보상 w에 의한 불공정성을 희석한다고 분석할 수 있다.
결론
블록체인은 기본적으로 탈중앙화를 지향하는 기술이기에 내부 프로토콜을 정교하게 설계하는 것이 무엇보다 중요하다. 본 논문은 공정성을 확보하기 위한 인센티브 설계에 필요한 이론적인 조건들을 제시하였으며, 시뮬레이션을 통한 실험이 이를 뒷받침함을 보였다.
소개된 네 종류의 합의 알고리즘 중 공정성의 관점에서 PoW 합의 알고리즘이 가장 내성이 강하다는 실험 결과를 보면 심플 이즈 베스트라는 말이 떠오른다. 블록체인 또한 필연적으로 지분이 큰 채굴자가 오래 살아남는 등 규모의 경제와 유사한 현상을 피해갈 수 없다는 점에서 소수의 채굴자가 블록 생성을 과독점하는 상황을 타개하기 위한 연구가 필요할 것으로 생각된다.
