Simulation of TrueBit Protocol: Part 1

Published in

DECON

13 min readMay 3, 2019

트루빗(TrueBit)은 연산 성능의 확장을 위해 제시된 프로토콜입니다. 이더리움에서는 연산의 복잡도와 스토리지 사용량 등으로부터 가스(gas)라는 수수료를 지불해야 합니다. 한 블록에 담길 수 있는 가스 총량에는 한계가 존재하므로, 연산 성능에 분명한 한계가 존재합니다.

현재로서는 이더리움상에서 복잡한 연산을 수행할 방법이 없습니다. 가령 얼굴 인식과 같은 머신러닝을 스마트 컨트랙트로 수행한다는 것은 상상도 못 할 일입니다. 엄청난 수수료를 부과해야 함은 물론, 블록 한계로 인해 구동조차 못 할 것입니다. 블록체인이 범용적인 네트워크 구조로 기능하려면 이러한 한계를 극복해야 합니다.

그 솔루션이 바로 트루빗입니다.

이번 디콘 시리즈에서는 ‘강제된 오류’와 ‘잭팟’으로 대표되는 트루빗의 인센티브 메커니즘을 시뮬레이션해 보았습니다. 과연 트루빗은 설계자들의 의도대로 선순환할까요?

트루빗 프로토콜

다음은 트루빗 프로토콜의 요약입니다.

프로그램의 수행을 위탁하는 사람 또는 다른 스마트 컨트랙트를 업무 부여자(Task Giver)로 칭하겠습니다. 업무 부여자는 프로그램 코드와 그 입력을 업무(Task)로서 트루빗 컨트랙트에 등록합니다.
해결자(Solver)는 이 업무를 온체인(ON-chain)이 아닌 블록체인 네트워크와는 관계없는 오프체인(OFF-chain) 웹어셈블리 가상 머신에서 수행하여, 그 결과를 트루빗 컨트랙트에 제출합니다. 이때 보증금을 함께 제출하여 자신이 제출한 답에 대한 책임을 집니다.
해결자가 답을 제출한 시점에서부터 일정 시간 동안 도전(challenge)을 받습니다. 만일 도전자가 없다면 해결자의 답은 정답으로 간주되어 업무 부여자에게 반환됩니다.
만일 어느 검증자(Verifier)가 도전을 건다면 검증 게임(verification game)이 시작됩니다. 이 검증자는 자신의 답과 함께 보증금을 겁니다. 해결자와 검증자 중 검증 게임에서 승리한 자는 보증금을 돌려받고 보상을 취득하게 되며, 패배한 자는 보증금을 몰수당합니다.

상세한 내용은 트루빗 백서를 참고해주시길 바랍니다.[1]

검증 게임은 온체인상에서 프로그램을 직접 구동해 보는 것입니다. 그러나 트루빗의 본래 목적을 떠올려봅시다. 연산의 복잡도가 너무나도 높아 온체인상에서 구동이 불가했으므로 트루빗을 사용했습니다. 그러므로 검증 게임에서도 프로그램 코드의 전체를 다 수행할 수는 없습니다.

사실, 검증 게임에서는 단 한 줄의 명령어만을 수행합니다. 해결자와 검증자가 프로그램을 수행하면서 불일치가 발생한 지점이 있을 것입니다. 이 불일치 지점에서의 명령어만을 수행하여 누구의 결과가 맞는지를 검증하는 것입니다. 이를 위해 트루빗 컨트랙트에는 웹어셈블리 인터프리터가 구현되어 있습니다.

강제된 오류와 잭팟

트루빗 프로토콜이 잘 구동되려면 해결자와 검증자가 적극적으로 네트워크에 참여하고, 올바른 결과를 반환하도록 유도해야 합니다. 그러나 이들 간의 관계는 얼핏 공존할 수 없는 것으로 보입니다.

해결자가 정답을 내면 검증자가 보상을 받을 유인이 없습니다. 이로부터 검증자의 기대 수익이 낮아져 이탈하게 되면, 해결자는 오답을 제출하고서도 보상을 받을 수 있습니다. 해결자 중 오답을 제출하는 비중이 높아지면 검증자의 기대 수익이 다시 올라가므로 검증자가 네트워크에 참여하게 되고, 해결자는 보증금을 지키기 위해 다시 정답을 제출하게 됩니다. 이 사이클의 반복입니다.

이대로라면 사이클에서 오답이 제출되는 시기가 존재하므로 트루빗 네트워크를 신뢰할 수 없습니다. 이에 트루빗은 강제된 오류(forced error)와 잭팟(jackpot) 시스템을 도입했습니다.

강제된 오류는 트루빗 컨트랙트가 임의로 해결자가 오답을 제출하도록 강제하여 검증자의 참여를 유도하기 위한 메커니즘입니다. 만일 이 오답을 검출한 검증자는 잭팟이라 불리는 큰 보상을 받습니다. 이로부터 검증자가 항상 검증을 수행할 요인이 생기고, 그러므로 해결자는 정답을 등록할 요인이 생깁니다. 생태계가 긍정적으로 순환할 수 있는 것입니다.

만일 강제된 오류를 잡아낸 검증자가 여러 명(k)일 경우, 이들은 아래 수식에 따라 잭팟(J)을 나누어 가집니다. 지수적인 분배 방법을 취한 이유는 시빌 공격(sybil attack)이라 불리는 한 사용자가 다수의 검증자를 겸하는 문제를 방지하기 위해서입니다.

시뮬레이션 환경 세팅

다음은 트루빗의 기본 인센티브 메커니즘인 ‘잭팟 메커니즘’의 시뮬레이션을 위해 설정 및 가정한 요소입니다.

에이전트(agent) 수: 트루빗 네트워크에 참여하는 검증자의 수입니다. 기본값은 25입니다.
연산력(capacity): 연산력은 각 에이전트가 가지고 있는 컴퓨팅 파워의 수치입니다. 연산력이 높으면 단위 시간당 더 많은 문제를 해결할 수 있습니다. 혹은 문제 하나를 해결하는 것에 부담이 적다고 해석할 수도 있습니다. 연산력은 최소 1, 최대 10의 정수값을 가지도록 기본 설정됩니다. 연산력의 분포는 최근 7일간 수집한 실제 이더리움 네트워크의 채굴자(miner) 상위 25여명을 참조했습니다.

난이도(difficulty): 난이도는 업무가 가지는 연산의 복잡한 정도입니다. 실제 이더리움 블록체인 중 최신 블록 일부로부터, 각 스마트 컨트랙트가 소요한 수수료(gas)의 분포를 참조했습니다. 연산력이 낮은 에이전트 난이도가 높은 문제를 수행하는 것에 일부 제약(큰 비용, 한 에피소드에서 구동할 수 있는 연산의 총 개수 등)이 발생합니다. 난이도는 최소 1, 최대 10의 정수값을 가지도록 기본 설정됩니다.

강제된 오류 비율: 강제된 오류가 발생할 비율입니다. 트루빗에서는 상수 0.001로 상정하고 있으나, 유연한 시뮬레이션을 위해 변경할 수 있도록 설계하였습니다. 기본 값은 0.01입니다.
잭팟 레포지토리(repository) 초기값: 시뮬레이션 시작 시점에 보관된 잭팟의 양입니다. 이는 에피소드나 스텝(step)이 지남에 따라 수수료나 보증금으로부터 충당됩니다.
해결자 오답 비율: 해결자가 잘못된 답을 제출할 확률입니다. 본 시뮬레이션에서의 주된 관심사는 검증자의 비율 및 행동이므로, 해결자는 환경으로서 주어집니다. 기본값은 0.1입니다.
보증금(deposit)의 양: 검증자 혹은 해결자가 지불해야 하는 보증금의 양입니다.
업무 수수료(task fee): 프로토콜 사용의 대가로 업무 부여자가 지불하는 수수료입니다.
연산 비용: 연산을 수행함에 있어 소요되는 비용입니다. 문제의 난이도가 높으면 연산 비용도 많이 소요됩니다.

Cost

비용은 기본적으로 수행한 연산의 난이도에 비례해 부과됩니다. 그러나 만일 검증자가 부정직한 행위를 수행하였고 이러한 행동이 검거될 경우 보증금이 몰수되므로 추가적인 비용이 발생할 수 있습니다.

Benefit

보상은 기본적으로 업무 부여자의 보상으로부터 받으나, 검증 대결에서 승리할 경우 해결자가 건 보증금의 최대 절반을 받아갈 수 있습니다. 또한 잭팟이 터질 경우에는 많은 양의 보상을 기대할 수 있습니다.

Reward

보상은 이익(Benefit)과 비용(Cost)의 차입니다.

Actions

본 시뮬레이션의 에이전트인 검증자는 어느 업무에 대하여 검증을 위한 연산을 수행하거나, 아무런 검증을 하지 않을 수 있습니다. 만일 검증을 한다면 검증자는 올바른 행동을 취할 수 있습니다. 즉 해결자가 정답을 내놓을 경우 도전을 걸지 않을 것이며, 오답을 내놓을 경우에만 도전을 걸 것입니다. 반면 검증자는 잭팟 기금을 노리고, 검증을 수행하지 않고 도전을 걸 수도 있습니다. 혹은 검증을 하지 않고 도전도 걸지 않을 수도 있습니다.

따라서 검증자의 행동은 크게 세 가지로 분류됩니다.

검증을 하고 올바른 행동을 취함
검증을 하지 않고 해결자에게 도전을 검
검증을 하지 않고 해결자에게 도전을 걸지도 않음으로써 네트워크에 미참여

에피소드가 진행됨에 따라 에이전트들은 자신에게 가장 이득이 되는 행동이 무엇인지 파악해 이득이 되는 행동을 주로 취할 것입니다.

트루빗 네트워크의 올바른 동작을 위해 첫 번째 행동을 취하는 에이전트의 비율이 높아짐이 바람직합니다. 반대로 두 번째 행동을 취하는 에이전트의 비율이 높아지면 네트워크는 신뢰할 수 없으며, 세 번째 행동을 취하는 에이전트의 비율이 높아지면 네트워크가 올바르게 구성되지 못합니다.

시뮬레이션 결과 분석

본 시뮬레이션에서는 100개의 업무를 묶어 한 에피소드를 구성하였습니다. 강제된 오류 비율을 0.01로 설정하였으므로, 에피소드별로 1건 정도의 강제된 오류가 나타날 것으로 기대할 수 있습니다. 또한 해결자 오답 비율이 0.1이므로 에피소드별로 10건 정도의 해결자 오답이 발생할 것으로 기대할 수 있습니다.

다음은 시뮬레이션의 결과입니다.

검증률

좌측의 그래프는 에피소드가 진행됨에 따라 검증을 수행하는 에이전트의 비율을 나타낸 것입니다. 오르락내리락하는 모습을 보이지만 전반적으로 감소하는 추세임을 알 수 있습니다. 이는 검증을 위해 연산을 수행하면 어김없이 비용이 지출되는 반면, 이익(잭팟)은 간헐적으로 발생하기 때문입니다. 달리 말하자면 예측 불가능한 보상으로 인해 에이전트가 검증을 할 요인을 느끼지 못하기 때문입니다.

우측의 그래프는 잭팟 기금을 100배로 키웠을 경우의 그래프입니다. 보상의 예측 불가능성이 원인이므로 잭팟 기금을 키우더라도 문제가 크게 개선되지 않습니다.

실제로 검증을 수행하는 검증자가 줄어드는 것은 네트워크에 바람직하지 못한 현상입니다. 다만 단 한 명의 검증자라도 있다면 해결자의 오답을 잡아낼 수 있으므로, 검증을 수행하는 검증자의 비율이 줄어들더라도 트루빗 네트워크가 금방 붕괴되지는 않습니다. 이는 오답 검거율이라는 수치를 통해 알아볼 수 있습니다.

오답 검거율

위 그래프는 해결자가 오답을 내놓았을 때 이를 잡아내는, 즉 오답 검거율을 나타낸 것입니다. 해당 에피소드에서 모든 해결자의 오답을 검거했을 경우 1.0으로 기록됩니다. 반면 1.0이 아닌 경우에는 해결자의 오답을 검거하지 못한 경우가 발생했다는 의미입니다.

이 역시 예측 불가능한 보상으로부터 에이전트 참여를 유도하지 못했기 때문에, 모든 에이전트가 검증에 참여하지 않는 경우가 발생하게 되고(단 한 명의 에이전트라도 검증을 수행하면 오답을 검거할 수 있습니다), 결국 오답 검거율이 1.0이 아닌 지점이 등장하게 됩니다.

이 또한 단순히 잭팟 기금의 크기를 키우는 것만으로 개선되지 않습니다.

네트워크 참여율

네트워크에 참여하는 에이전트의 비율도 점차 낮아짐을 알 수 있습니다. 네트워크는 점차 죽어가는 것입니다.

공평성

잭팟 메커니즘은 이름에서처럼 복권 같은 특징을 가지고 있습니다. 강제된 오류가 무작위로 등장하기 때문에 검증자는 경우에 따라 한 번도 잭팟을 받지 못할 수 있지만, 단 한 문제만 풀고서도 큰 돈을 벌수도 있습니다.

그러나 기회가 모두에게 균등하게 돌아가는 것은 아닙니다. 연산을 대행하는 특성상 연산량이 큰 참여자가 잭팟을 받을 수 있는 확률이 높아집니다. 이는 비트코인에서 해시파워가 큰 채굴자가 대부분의 채굴 보상을 가져가는 형태와 유사합니다. 본 시뮬레이션에서도 연산력이 높은 에이전트들이 더 많은 오답을 검출해내는 양상을 관찰할 수 있었습니다.

연산력의 차이로부터 보상 분배의 불평등이 심화될 경우 네트워크 참여자의 이탈 및 또다른 중앙화의 문제를 야기할 수 있으므로, 시스템 설계자는 적절한 정도의 공평성(fairness)을 달성해야 합니다.[2] 그러나 이는 본 시뮬레이션의 목적 및 범주를 벗어나기 때문에 깊게 다루지는 않겠습니다.

결론

오답 검거율이 1.0이 아닌 지점이 종종 등장하고 네트워크에 미참여하는 에이전트 비율이 높아지는 것은 예측 불가능한 보상이 원인이었습니다. 이는 단순히 잭팟 기금을 키우는 것으로는 해결할 수 없었습니다.

달리 말하자면, 보상이 어느 정도 예측 가능할 경우 에이전트의 검증률을 높이고 네트워크 참여율을 이끌어낼 수 있을 것으로 기대할 수 있습니다. 실제로 트루빗 백서 제2 저자인 Christian Reitwießner 역시 이러한 문제를 인지하고, 트루빗을 위한 예측 가능한 보상 메커니즘인 ‘다중 해결자(multiple solver) 메커니즘’을 제시하기도 하였습니다.[3]

다음 글에서는 ‘다중 해결자 메커니즘’과 더불어 디콘이 설계한 ‘연금 메커니즘’을 소개하고, 이들의 시뮬레이션 결과를 분석해보겠습니다.