Simulation of TrueBit Protocol: Part 2
트루빗의 ‘잭팟 메커니즘’은 예측 불가능한 보상으로 인해 특정 업무에서 검증자들이 한 명도 실제 연산을 하지 않는 경우가 나타나 해결자의 잘못된 정답을 잡아내지 못하는 문제가 있었습니다. 이를 해결하기 위해서는 예측 가능한 보상을 제공할 수 있는 메커니즘이 필요합니다.
본 게시글에서는 예측 가능한 보상을 제공하는 두 메커니즘을 소개하고 시뮬레이션을 통해 이 메커니즘들이 어떤 결과를 낳는지 비교분석하였습니다. 또한 기존 잭팟 메커니즘에 비해 어떤 장단점이 있는지 알아봅니다. 첫번째 메커니즘은 지난 게시글에서 언급한 바 있는 ‘다중 해결자(multiple solver) 메커니즘’ 입니다. 다른 메커니즘은 디콘에서 직접 고안한 메커니즘인 ‘연금(pension) 메커니즘’ 입니다.
연금 메커니즘
언제 얼마나 보상을 받을 수 있을 지 예측 가능한 메커니즘을 설계하려면 어떻게 해야 할까요? 각 업무 때마다 의뢰자가 지불한 업무 수수료를 분배하면 됩니다. 하지만, 어떤 검증자가 실제로 연산을 수행했을지 알고 업무수수료를 분배할 수 있을까요? 잭팟 메커니즘에서는 검증자의 실제 연산여부를 아는 것이 큰 문제가 아니었습니다. 잭팟에서는 검증자가 평소에 성실히 연산을 해오더라도 즉각 보상을 지급하진 않기 때문입니다. 다만, 해결자의 답이 틀렸다고 도전(challenge) 할 때만 온체인에서 직접 연산을 해 이 답과 검증자의 답이 일치 하는지 확인해 일치하면 검증자에게 보상했습니다. 검증자가 도전을 걸면 온체인이 직접 연산을 해 실제 정답을 알아내는 것인데, 도전의 빈도 수가 많지 않으므로 검증자의 실제 연산 여부를 알아내는 것이 큰 부담이 아니었습니다. 하지만 예측가능한 메커니즘에서는 이 방식을 적용할 수가 없습니다. 잭팟 메커니즘에서는 도전이 일어나는 경우가 거의 없어(Simulation of TrueBit Protocol: Part 1 참고) 온체인이 직접 답을 구해도 부담이 적었으나 예측가능한 메커니즘에서는 온체인이 모든 업무에 대해 직접 답을 구해야 해 큰 부담이 되기 때문입니다. 온체인의 연산력을 아끼는 것이 트루빗의 목표인데 이 목표가 훼손됩니다. 그렇다면 과연 어떤 방법으로 온체인에 부담을 최소화하면서도 효과적으로 연산을 한 노드와 하지 않은 노드를 구별할 수 있을까요?
저희는 해결자가 대부분의 경우 정답을 제출한다는 점에 주목하였습니다. 해결자는 유효한 검증자가 존재하는 한 보증금을 지키기 위해 정답을 제출할 것입니다. 따라서 해결자의 답을 우선적으로 정답으로 간주할 것입니다.
검증자는 자신이 제출한 답이 해결자와 일치하는 경우에 한하여 연금을 받을 자격을 획득합니다. 단, 한 번만 정답이 일치하면 되는 것이 아니라 최근 6번 동안 5회 이상 정답이 일치해야 합니다. 조건에 부합하는 검증자들은 지속적으로 업무 수수료를 분배받습니다. 만일 검증자가 실제로 연산을 통해 검증 과정을 거치지 않으면, 해결자와 답이 달라지고, 연금 자격을 박탈당하게 됩니다. 따라서 실제로 연산을 수행할 유인이 생깁니다.
만일 해결자와 검증자 간 답이 일치하지 않는 경우에는 검증 게임을 통해 정답을 제출한 자를 찾고, 오답을 제출한 자의 보증금을 압류합니다.
시뮬레이션 결과 분석
연금메커니즘 결과
연금 메커니즘에서는 업무 수수료만으로 해결자와 검증자에게 보상합니다. 따라서 업무 수수료가 잭팟 메커니즘에서보다 더욱 중요하게 작용해 수수료가 낮을 경우 검증률과 오답 검거율이 떨어짐을 알 수 있습니다. 현재 세팅은 실제 연산에 드는 비용이 1이라고 했을 때 업무 수수료를 100으로 책정한 결과입니다.
반대로 수수료를 많이 부과한다면 검증률과 오답 검거율이 올라갈 것으로 기대할 수 있습니다. 잭팟 메커니즘에서는 수수료를 많이 부과하더라도 검증률과 오답 검거율에서 큰 개선이 없었습니다. 다음은 수수료를 검증 비용의 500배 정도로 부과했을 때의 그래프입니다.
검증률이 크게 오르고 오답 검거율 역시 1.0을 유지함을 알 수 있습니다. 그러나 이 경우 업무 부여자의 부담이 상당할 것입니다.
한편 수수료 크기를 바꿔가며 시뮬레이션해본 결과, 일정 크기 이상에서는 수수료가 증가하더라도 검증률과 오답 검거율의 변화가 크지 않았음을 알 수 있습니다. 다음은 수수료가 검증에 소요되는 비용의 500배, 1000배, 2000배, 그리고 4000배에서의 검증률 그래프입니다. 그래프가 거의 비슷해 겹치는 양상을 띄고 있습니다.
이는 보상을 2^(n-1)에 따라 분배하기 때문에, 보상이 웬만큼 늘어서는 각 agent들에게 의미 있는 보상으로 환원되지 않아 검증에 참여하지 않던 agent의 행동을 바꾸기에는 부족하기 때문입니다.
잭팟 메커니즘과 연금 메커니즘을 비교해보면, 연금 메커니즘을 사용할 때 네트워크가 더 예측 가능하게 동작하는 것을 알 수 있습니다. 잭팟 메커니즘에서는 잭팟 기금의 양과 업무수수료의 조절만으로는 오답 검거율을 예측할 수 없었습니다. 보상이 간헐적으로 주어지기 때문에 종종 아무도 검증에 참여하지 않는 업무가 발생하기 때문입니다. 반면 연금 메커니즘에서는 수수료만 일정 수준 이상이 되면 모든 오류를 검거함을 관찰할 수 있습니다.
잭팟 메커니즘에서는 업무 수수료를 5로만 해도 훨씬 많은 잘못된 답을 잡아낼 수 있습니다.
다중 해결자 메커니즘
또 다른 예측 가능한 보상을 주는 메커니즘으로 트루빗 contributor 인 Julia Koch와 Christian Reitwießner가 설계한 Multiple-Solver 메커니즘이 있습니다. (Koch, J., & Reitwiessner, C. (2018). A Predictable Incentive Mechanism for TrueBit. arXiv preprint arXiv:1806.11476.) 저자들은 네트워크 참여자들이 보상을 예측하지 못함으로서 실제 연산을 하는게 이득인지 아닌지 판단하지 못하는 문제를 해결하고자 했습니다.
본 메커니즘의 특징은 따로 검증자를 두지 않았다는 점입니다. 모든 참여자들은 해결자가 되어 문제를 푸는데 참여의사를 나타낼 수 있으며, 일단 참여하기로 했으면 시간 안에 무조건 답을 제출해야 하고 제출하지 않으면 보증금을 빼앗기게 됩니다.
답을 낸 이후에 해결자들끼리 답이 다르면 같은 답을 제출한 해결자들이 한 그룹이 되어 토너먼트를 거치는데, 잘못된 답을 제시한 그룹은 올바른 답을 제시한 그룹에게 보증금을 빼앗기게 됩니다.
잭팟은 물론 없고 모든 보상은 업무 수수료와 토너먼트 게임에서 나옵니다.
다중 해결자 메커니즘의 장점은 검증의 의무가 강제되었다는 점입니다. 기존 잭팟 메커니즘에서의 검증자들은 특정 문제를 검증할 의무가 없었습니다. 그래서 한 해결자가 답을 제출했을 때 낮은 확률이지만 단 한명도 이 답을 검증하지 않는 경우가 발생할 수 있었습니다. 이런 경우가 발생해도 검증자들은 손해 보는 것이 없습니다.
하지만 다중 해결자 메커니즘에서는 참여하기로 했음에도 실제 연산을 하지 않으면 보증금을 빼앗기기 때문에, 참여한 해결자들은 올바른 답을 제출할 유인을 갖게 됩니다. 모든 업무에 대해 2명 이상의 해결자가 참여하도록 강제함으로써 누군가 오답을 제출해도 후에 토너먼트 메커니즘을 통해 오답을 잡아낼 수 있도록 합니다.
다중해결자 메커니즘은 잭팟 메커니즘의 일정하지 않은 보상 문제를 해결했습니다. 또한 연금 메커니즘과는 다르게 답을 제출하지 않아도 손해 볼게 없는 검증자를 없애고 답을 제출하지 않으면 보증금을 몰수당하는 해결자만으로 네트워크를 구성해 잘못된 답이 제출될 수 있는 가능성도 최소화하였습니다.
시뮬레이션 결과 분석
다중해결자 메커니즘 결과
연금 메커니즘과 마찬가지로 다중 해결자 메커니즘은 잭팟 메커니즘보다는 더 많은 수수료를 받아야 원하는 결과를 얻을 것임을 예상할 수 있습니다. 다음은 차례대로 업무 수수료가 연산 비용의 1배, 10배, 100배, 그리고 500배일 때의 참여율 및 오답률 그래프입니다. 본 시뮬레이션에서는 검증자가 없으므로 검증률을 대신하여 연산에 참여한 해결자의 수를 살펴보고, 오답 검거율이 아닌 오답을 제출하는 비율을 살펴보았습니다.
수수료를 많이 지불할 수록 연산에 참여하는 에이전트의 비율이 증가하고, 에이전트가 제출한 답 중에 정답이 없는 경우가 줄어든다는 것을 알 수 있습니다.
오답이 아무리 많아도 모든 답이 같지만 않다면 토너먼트가 발생해 온체인에서 결국에는 정답을 알아낼 수 있습니다. 그러나 정답이 없는 경우가 자주 발생한다면 트루빗에 연산을 대행하는 의미가 없으므로 애초에 충분한 수수료를 책정해야 바람직할 것입니다.
비교분석
위의 표는 잭팟, 연금, 다중 해결자 메커니즘의 장단점을 정리한 표입니다. 첫행에는 더 높아져도 더 이상 큰 성능개성이 없는 정도의 업무수수료 수준이 나타나 있습니다. 실제로 네트워크를 구동했을 때 네트워크를 유지할 수준의 수수료입니다. 표에 따르면, 잭팟은 상대적으로 낮은 수수료로도 네트워크를 유지할 수 있으나 검증에 참여하는 에이전트의 수가 적고 오답이 등장할 비율도 상대적으로 다른 두 메커니즘보다는 높습니다. 반면 연금 메커니즘과 다중 해결자 메커니즘은 수수료가 더 많이 높지만 오답률이 낮습니다.
좀 더 자세히 살펴보면, 연금 메커니즘에서 오답이 발생하지 않는 경우의 수수료는 연산 비용의 500배인 반면, 다중 해결자 메커니즘에서는 100배입니다. 이는 각 업무마다 보상을 받을 에이전트의 수가 다중 해결자 메커니즘보다 연금 메커니즘에서 통상 더 많기 때문입니다. 연금 메커니즘에서는 6번 중 한 번은 답이 일치하지 않아도 보상을 분배받았습니다. 이런 유연함으로 인하여 보상을 받을 자격이 있는 에이전트의 수가 많아지는데, 보상은 사람의 수에 따라 지수적으로 빠르게 감소합니다. 결국 연금메커니즘을 사용하면서 다중해결자 만큼의 낮은 오답률을 얻고 싶다면 업무 부여자는 수수료를 더 많이 지불해야 합니다.
결론
잭팟 메커니즘은 적은 돈으로 준수한 오류수준을 얻지만 예측가능한 메커니즘은 돈은 많이 들지만 확실하게 오류를 잡는다
잭팟메커니즘은 업무당 부과되는 수수료는 낮지만 수수료 수준을 아무리 높여도 모든 오답을 잡아낼 수 없는 문제가 있었습니다. 해결자가 잘못된 답을 내놓았지만 보상이 간헐적이기 때문에 그 업무에 단 한명의 검증자도 참여하지 않는 경우가 (작은 확률이지만) 생기기 때문입니다.
이에 대안으로 연금 메커니즘과 다중해결자 메커니즘이 등장했습니다. 이 메커니즘들은 수수료 수준만 높아지면 시뮬레이션 안에서 모든 오답을 잡아낼 수 있었습니다.
결국 잭팟 메커니즘은 낮은 업무수수료에 강점을 가지고 예측가능한 메커니즘은 업무수수료를 더 많이 냈을 때 확실한 결과가 나온다는 점에 강점을 가지는 것입니다. 설계자는 이러한 차이점을 고려하여 네트워크를 설계해야 할 것입니다.
더 나아가서
이번 시뮬레이션을 통해 느낀 것은 잭팟 메커니즘의 한계를 극복하기 위해 예측가능한 보상을 주는 메커니즘이 제안되었지만 잭팟 메커니즘이 여전히 쓸만한 메커니즘이라는 것입니다.
연금, 다중해결자 메커니즘은 잭팟 메커니즘보다 훨씬 더 많은 수수료를 지불해야 하기 때문인데, 이렇게 수수료가 높은 이유는 보상을 2^(n-1)에 따라 지수적으로 분배하는 방식 때문입니다. (잭팟 메커니즘도 이 보상방식을 따르지만, 원금이 큰 잭팟을 2^(n-1) 로 나누는 것보다 원금이 작은 업무수수료를 2^(n-1) 로 나누는 것이 검증을 할 지 말지 의사결정 하는데 더 큰 영향을 끼칩니다)한 사람이 여러개의 주소로 네트워크에 참여하는 시빌 어택(sybil attack)의 가능성을 억제하기 위해 제안된 분배방식이지만 선량한 참여자가 늘어나도 보상이 크게 줄어듭니다. 이 분배방식을 개선하지 않는다면 예측가능 메커니즘은 예측가능하게 보상이 작은 메커니즘에 머무를 것입니다.
또한 느낀 것은, 다음 시뮬레이션에서는 업무 부여자까지 시뮬레이션할 수 있도록 해야한다는 것입니다. 저희 시뮬레이션에서는 업무 부여자가 따로 없어 업무수수료가 높아지면 검증자 / 해결자들 입장에서는 무조건 유리해졌습니다. 하지만, 현실에서는 업무수수료가 높을 경우 업무 부여자들의 참여가 줄어들고 결국 검증자/해결자들의 일감이 줄어들어 검증자/해결자들의 참여 또한 줄어들 수 있습니다. 따라서 다음 시뮬레이션에서는 업무부여자까지 고려하여 업무수수료가 높아졌을 때에도 네트워크가 제 기능을 할 수 있는지 본다면 잭팟 메커니즘과 예측가능한 메커니즘을 비교하는 데 더 도움이 될 것입니다.
About Decon
DECON은 블록체인 프로젝트들을 자문하고 있는 암호경제학 연구소로서, 실제 가치를 만들어낼 수 있는 토큰 모델 설계를 연구하고 있습니다.
토큰 모델 설계와 관련하여, DECON과 함께 연구하고 싶은 분들이나 문의사항이 있으신 분들은 언제든지 contact@deconlab.io로 연락 주시기 바랍니다.
Homepage: https://deconlab.io
Facebook: https://www.facebook.com/deconcryptolab/
