Optimistic Rollup is Not Secure Enough Than You Think — Game Theoretic Approach for More Verifiable Rollup[KR]

Published in

Tokamak Network

66 min readApr 12, 2021

Intro

옵티미스틱 롤업(Optimistic Rollup, 이하 롤업)은 이더리움 커뮤니티가 레이어 2 솔루션인 플라즈마의 문제점을 해결하기 위해 고민하고 있을 때, 이를 해결하기 위해 혜성처럼 등장한 또 다른 레이어 2 솔루션이다. 롤업의 가장 큰 장점은 플라즈마와 달리 위조 증명(Fraud Proof)을 통해 모든 사용자가 롤업을 감시하지 않고, 최소한 단 한명의 정직한 검증자만 있다면 안전성(Security)을 보장할 수 있다는 것이다. 이는 롤업이 플라즈마에 비해 확장성을 대폭 희생한다는 단점에도 불구하고, 이더리움 커뮤니티의 전폭적인 지지를 얻게된 주요 요인이었다.

롤업은 말 그대로 단 한명의 정직한 검증자(Honest Verifier)만 존재해도 안전하게 동작할 수 있는 아주 매력적인 레이어 2 이다. 하지만 블록체인 세계에 살고 있는 우리는 의심이 아주 많은 사람들이기 때문에, 롤업이 정말 안전하게 작동한다고 확신할 수 있는가에 대한 의문이 생긴다. 사실 이런 의문들은 아주 새로운 것은 아니다. 검증자의 딜레마(Verifier’s Dilemma)라는 개념으로 꽤 오랜 기간동안 많은 연구자들은 롤업 뿐 아니라 검증이 필요한 다양한 분야에서 올바르게 검증이 이루어질 수 있는가에 대해 논의해왔다. 롤업 또한 이와 비슷한 논의가 이루어져 왔고, 이에 대한 의견은 크게 두 갈래로 나뉜다. 한 쪽은 롤업에서 검증자의 딜레마를 ‘전혀’ 고려할 필요가 없다고 주장하며, 다른 한 쪽은 롤업이 장기적으로 안전하게 동작하기 위해서는 반드시 검증자의 딜레마를 고려해야 한다고 이야기 한다.

도대체 누구의 말이 맞는 것일까? 설계자가 아닌 사용자의 입장에서 우리는 롤업을 정말 안전하게 사용할 수 있는 것인가? 만약에 확실히 안전한것이 아니라면 우리는 어떻게 해야 하는가? 이 글에서는 이러한 모든 의문들을 모두 해소하고, 롤업의 안전성을 보장하기 위해 장기적으로 어떠한 방향으로 나아가야 할지에 대한 구체적인 방법을 제시할 것이다.

이 글에서 다루는 모든 논의들은 비단 옵티미스틱 롤업뿐만 아니라 위조 증명(Fruad Proof)을 이용하는 모든 확장성 솔루션에 적용 될 수 있다.

Verifier’s Dilemma

롤업의 안전성에 대한 문제를 다루기 전에 반드시 짚고 넘어가야할 개념이 있다. 바로 앞서 소개글에서도 언급 했던 검증자의 딜레마이다. 검증자의 딜레마란 일반적으로 블록체인 세계에서 한 참가자가 어떠한 연산을 수행하고 다른 한 참가자가 해당 작업을 검증하여 네트워크 혹은 프로토콜의 안전성을 유지할 때, 검증에 대한 효용이 명확하지 않은 경우에 발생하는 일련의 문제들을 의미한다.

검증자의 딜레마는 이 글에서 최초로 논의된 개념으로 쉽게 풀어 쓰면 다음과 같이 설명할 수 있다. 비트코인과 이더리움과 같은 블록체인에서는 블록을 최초로 마이닝한 마이너가 네트워크의 다른 노드에게 블록을 전파할 때, 다른 노드들은 모두 블록의 유효성을 검증한다. 이것이 원래 컨센서스가 의도한 바이며, 네트워크의 안전성 측면에서 블록을 전파받은 모든 다른 노드들은 이를 반드시 검증하는것이 바람직하다.

하지만 개별 노드의 연산력은 유한하기 때문에 복잡한 트랜잭션을 검증하는데 사용될 연산력을 다음 블록을 마이닝하는 작업에 할당하는것이 경제적으로 더 유리할 수 있다. 물론, 유효하지 않은 블록을 조상 블록으로 하는 블록은 네트워크에서 인정받을 수 없기 때문에 이러한 위험을 감수해야 한다. 따라서, 개별 노드들은 검증을 수행하는것이 유리한지, 혹은 검증을 하지 않고 마이닝에만 집중하는것이 유리한지 선택해야하는 상황에 끊임 없이 빠지게 된다.

이러한 검증자의 딜레마는 롤업에서도 유사한 방식으로 적용될 수 있다. 롤업에서는 시퀀서가 레이어 2에서 발생한 트랜잭션들을 처리한 후, 해당 상태값들의 요약본과 개별 트랜잭션 데이터만을 레이어 1에 제출한다.

시퀀서 또는 오퍼레이터는 롤업에서 사용자의 트랜잭션의 순서를 결정하고, 이를 레이어 1에 제출하는 역할을 수행한다. 이 글에서는 시퀀서라는 용어를 사용한다.

이 때 시퀀서가 올바르지 않은 상태값을 제출할 수 있기 때문에, 롤업에서는 위조 증명(Fraud Proof)과 DTD(Dispute Time Delay)를 두어 이를 예방한다. 롤업 내외부의 모든 사용자들은 롤업의 검증자가 될 수 있으며, 위조 증명을 통해 DTD내에 유효하지 않은 값이 확정(Finalize)되는 것을 방지할 수 있다.

만약 검증자가 위조 증명에 성공한다면 시퀀서가 예치한 보증금의 일부 혹은 전부를 보상으로 받을 수 있다. 하지만 여기서 한가지 문제가 발생한다. 만약에 시퀀서가 항상 올바른 값만 제출한다면? 검증자는 아무리 검증 작업을 수행해도 위조 증명을 성공하지 못할 것이고, 이는 곧 검증에 대한 유인을 잃게 만든다. 하지만 시퀀서가 계속해서 올바른 값만 제출하는것이 원래 롤업이 의도한 안전성이 아니냐고 반문할 수 있다. 이것이 왜 문제가 되는지 살펴보자.

검증자는 시퀀서가 제출한 상태값이 올바른지 항상 검증한다.
시퀀서는 올바르지 않은 값을 제출하면 위조 증명에 의해 보증금을 몰수 당하므로 계속해서 올바른 상태값만 제출한다.
검증자는 시퀀서가 계속해서 올바른 값만 제출하므로 검증 작업에 대한 보상을 받을 수 없다. 따라서 검증을 포기한다.
검증자가 검증을 포기했으므로 시퀀서는 롤업을 공격하여 사용자들의 자산을 탈취할 강력한 유인을 갖게 된다.

요컨대, 검증에 대한 경제적인 유인은 시퀀서의 공격 행위에 강력하게 의존하기 때문에, 시퀀서가 공격을 하지 않을수록, 다시 말해 롤업이 안전하게 운영 될수록 검증에 대한 유인은 더 감소하게 된다는 것이다. 이는 굉장히 역설적인데, 롤업이 안전해질수록 더 위험해지고, 더 위험해질수록 더 안전해지기 때문이다. 이 논리에 따르면, 한눈에 봐도 검증자의 딜레마는 롤업의 안전성을 심각하게 위해할 수 있는 요소로 보인다. 과연 검증자의 딜레마는 정말 롤업의 위협요소일까? 다음 장에서 더 깊게 파헤쳐보자.

Super-Simple Model

복잡한 개념이나 문제를 이해하고 해결하기 위해서 가장 좋은 방법은 언제나 문제를 단순화하는 것이다. 따라서 우리는 롤업의 검증자의 딜레마에 대해 본격적으로 논의하기에 앞서, 이를 매우 단순화한 Super-Simple Model을 먼저 살펴볼 것이다.

Super-Simple Model은 Ed Felten의 글 The Cheater Checking Problem: Why the Verifier’s Dilemma is Harder Than You Think 을 바탕으로 작성되었다.

가정: 이 글에서 다룰 모든 모델에서 모든 참가자 또는 경기자의 합리성이 주지사실(common knowledge)임을 가정한다. 이는 다음의 두 무한명제가 참(True)임을 뜻한다.

‘당신이 합리적이라는 사실을 나는 알고 있다.

당신이 합리적이라는 사실을 내가 안다는 사실을 당신이 알고 있다.

당신이 합리적이라는 사실을 내가 안다는 사실을 당신이 안다는 사실을 나는 알고 있다. …’

‘내가 합리적이라는 사실을 당신은 알고 있다.

내가 합리적이라는 사실을 당신이 안다는 사실을 나는 알고 있다.

내가 합리적이라는 사실을 당신이 안다는 사실을 내가 안다는 사실을 당신은 알고 있다. …..’

먼저, 아주 단순한 시스템을 생각해보자. 이 시스템에는 두명의 경기자가 존재하는데, 한명은 주장자(Asserter, 이하 A)로 단순히 참 혹은 거짓만 제시한다. 다른 한명은 검증자(Verifier, 이하 V)로 검증에 필요한 비용을 지불하고 A의 주장을 검증하거나 또는 A가 참을 주장했을 것이라 가정하고 검증하지 않는 것을 선택할 수 있다. 만약 A의 주장이 거짓이고 V가 이를 검증하는데 성공했다면 A의 보증금을 보상으로 받게 된다.

반대로 A가 거짓을 주장했음에도 불구하고 V가 이를 고발하지 않는다면 V의 보증금이 A에게 보상으로 주어진다. 즉, 이 시스템의 목적은 A가 거짓 주장을 하더라도 V가 이를 검증하여 항상 참만 주장되도록 유지하는 것이다.

이러한 목적을 달성하기 위해 우리가 고려해야 할 위험요소는 두가지가 있다.

뇌물 수수 공격(Bribery attack)
검증자의 나태(Laziness)

뇌물 수수 공격은 주장자가 검증자를 뇌물로 매수하여 거짓을 주장하더라도 이를 검증하지 않도록 사전에 합의하는 것을 말한다. 이러한 공격 방식은 주장자와 검증자의 담보물의 가치를 높이거나 이해관계자의 수를 늘리는 것으로 비교적 쉽게 해결이 가능하다.

검증자의 나태는 말 그대로 검증자가 검증작업을 수행하지 않아 발생하는 문제를 의미한다. 검증 작업이 수행되지 않는다면, 주장자는 얼마든지 거짓을 계속해서 주장할 수 있게 된다. 검증자의 나태는 뇌물 수수 공격과 달리 담보물의 가치를 높이거나 이해관계자의 수를 단순히 늘리는 것으로는 해결이 쉽지 않다. 그 이유를 아래에서 자세히 살펴보도록 하자.

검증자의 나태를 막기 위해서는 먼저 검증자가 어떠한 기준으로 검증 또는 비검증 전략을 선택하는지 파악할 필요가 있다.

다음과 같은 조건하에 검증자가 각 전략을 선택했을 때의 기대 보수는 아래와 같이 나타낼 수 있다.

R = A의 보증금, A가 거짓을 주장하고 V가 검증에 성공할 경우 V에게 보상으로 주어진다.
L = V의 보증금, A가 거짓을 주장하고 V가 검증에 실패할 경우 A에게 보상으로 주어진다.
X = A가 공격할 확률
C = 검증 비용

검증 기대 보수: R*X-C
비검증 기대 보수: -L*X

이 때, 우리는 V의 검증 보수가 비검증 보수보다 크다면(R*X- C > -L*X) V는 항상 A의 주장을 검증을 할 것이라 쉽게 예측할 수 있다.

즉, X > C/(R+L) 이면 검증자의 나태를 방지할 수 있는 것이다. 반대로 X < C/(R+L)라면 V는 A의 주장을 검증하지 않을 것이다. (두 항이 같은 경우는 어떤 선택을 하더라도 기대 보수가 무차별해지는 지점이다. 즉 V는 A의 주장을 검증할수도 있고, 하지 않을수도 있다.)

그렇다면 우리에게 필요한것은 X를 C/(R+L)보다 더 크게 만드는 것이다. 그러면 V는 항상 A의 주장을 검증하게 될 것이고 이 단순한 시스템은 항상 안전하게 유지될 것이다!

하지만 문제는 X는 A의 공격 확률을 의미하고, 이는 곧 X의 값은 A에 의해 결정된다는 것이다. 만약 X가 충분히 낮도록 A가 공격행위의 빈도수와 시기를 적절하게 조절한다면 V는 검증 효용이 비검증 효용보다 낮기 때문에 검증하지 않는 것을 선택하게 되고, A의 거짓 주장을 효과적으로 방어할 수 없게 된다. 이는 곧 이 단순한 시스템의 안전성이 무너질 수 있다는것을 의미한다.

여기서 누군가는 “R+L을 최대한 높여 효과적인 X의 수치를 충분히 낮추게 되면 시스템은 더 안전해질 수 있다”고 주장할 것이다. 다시 말해, 이 시스템의 참여 조건에 해당하는 자본 제한(Capital Requirement)을 가능한 최대로 늘려 A와 V의 요구 보증금액을 높이자는 것이다. 하지만 이는 다음과 같은 두가지 측면에서 한계가 분명하다.

R과 L이 아무리 높은 수치라도, 그 수치가 사전에 결정되는 순간 A는 효과적인 공격 확률을 계산할 수 있다. 이를 통해 A는 여전히 V의 검증에 대한 유인을 감소시킬 수 있다.
자본 제한을 높이는 것은 참여에 대한 진입장벽을 높여 오직 소수만이 이 시스템에 참여할 수 있게 제한한다. 이는 곧 해당 시스템의 도입과 확장에 매우 부정적인 영향을 끼치게 된다.

또 다른 아이디어는 검증자의 수를 늘리면 이 딜레마를 해결할 수 있다는 것이다. 하지만 검증자의 수를 단순히 늘리는 것은 뇌물수수 공격(Bribery attack)을 예방하는 것에는 큰 도움이 되지만, 검증자의 나태를 해결하는 것에는 오히려 악영향을 끼치게 된다.

뇌물 수수 공격을 예방하는데 도움이 되는 이유는, 주장자가 검증자를 매수하기 위해서는 각 검증자에게 R보다 큰 보상을 지급해야 하기 때문이다. 만약 검증자의 수가 N명이고, 거짓을 주장하여 얻는 총 이익이 M이라고 할 때, M/N > R 일 경우에만 모든 검증자들을 매수할 수 있을 것이다. 따라서 N이 커질수록 주장자는 뇌물 수수 공격을 수행하는것이 어려워진다.

이론적으로 롤업에서 단 한명의 검증자만 있어도 안전하게 동작할 수 있지만, 반대로 이는 시퀀서의 뇌물수수 공격에 취약해질 수 있기 때문에 가능한 다수의 올바른 검증자를 확보하는것이 매우 중요하다고 할 수 있다.

반대로, 검증자의 수를 늘리는 것이 검증자의 나태를 해결하는 것에 별 도움이 안되는 이유는 검증자의 수가 증가할수록 비검증 효용은 그대로인 반면, 검증에 대한 기대 보상은 검증자의 수에 비례하여 감소하기 때문이다. 이는 매우 자명한 사실인데, 예를 들어, 검증자가 두명일 때 두 검증자 모두 검증에 성공한다면 보상 R을 어떠한 비율(K)로든 나누게 될 것이고, 이는 검증자가 단 한명일 때의 보상 R보다 낮은 금액(R/K)일 것이기 때문이다.

이 단순한 모델에 따르면, 검증자의 딜레마란 꽤 복잡한 문제이며 이를 해결하는것은 상당히 어려워 보인다. 하지만 이 모델은 정확히 롤업을 모방한것은 아니다. 롤업에서는 이러한 문제가 해결될수도 있지 않을까? 이에 대해 다음 장에서 더 자세히 살펴보도록 하자.

Super-Simple Model in Optimistic Rollup

앞서 다루었던 단순한 모델을 바탕으로 롤업에서의 Super-Simple Model을 구성하여 롤업에서 검증자의 딜레마와 관련하여 어떠한 문제가 있을지 살펴보자. 사실 앞의 모델에서 변경되는 부분은 많지 않다. 주장자가 시퀀서(Sequencer, S)로, 검증자는 그대로 검증자가 된다. 이 때 검증자는 롤업의 이해관계자라고 가정한다. 즉, 검증자는 롤업에 일정한 경제적/비경제적 자산이 있거나, 롤업을 통해 주기적으로 일정한 경제적/비경제적 수익을 얻는 자이다.

이 때, 다음과 같은 조건하에 검증자 V의 검증 및 비검증 기대보수는 다음과 같다.

R = S의 보증금, V가 검증에 성공할 시 V에게 보상으로 주어진다.
L = V의 롤업에 예치된 자산, V가 검증에 실패할 시 S에게 보상으로 주어질 수 있다.
X = S가 공격할 확률
C = 검증 비용
F = 검증 단위당 V가 얻는 수익(예를 들어, V가 롤업의 트랜잭션 T마다 일정한 수익을 얻을 때, 이를 F라고 한다)

단, R,L > F > C > 0 이다.

또한 편의상 F는 L에 누적해서 포함되지 않는다고 가정하겠다. 이러한 가정은 이후에 다룰 모든 모델에서 동일하게 적용될 것이다.

검증 기대 보수: R*X + F -C
비검증 기대 보수: -L*X + (1-X)F

검증을 하지 않더라도 시퀀서가 공격 행위를 수행하지 않으면 검증자는 여전히 F의 수익을 얻을 수 있다는것에 유의하라.

이 때, Super-Simple Model과 동일하게 검증 보수가 비검증 보수보다 크다면 검증자는 항상 검증할 유인이 있다고 할 수 있다. 즉, 시퀀서의 공격확률이 다음과 같은 경우에 검증자는 검증 전략을 선택하게 된다.

X > C/(R+L+F)

이전의 모델과 달라진 것은 오직 분모에 F가 추가되었다는 것이다. 이는 시퀀서의 공격확률을 소폭 감소시키는 효과를 낼 수 있겠지만, 근본적인 문제점은 동일하게 존재한다.

즉, 검증자의 전략적 선택은 여전히 시퀀서의 공격 확률에 의존하고 있으며, 이는 새로운 변수인 검증 단위당 검증자가 얻는 일정한 수익(F)을 고려하더라도 크게 달라지지 않는다는것을 알 수 있다. 이는 시퀀서의 공격이 매우 간헐적으로 일어나거나 또는 일어나지 않는다면, 검증자는 검증 비용 없이 계속해서 온전한 수익을 얻을 수 있기 때문이다.

우리는 어떻게 이 문제를 해결할 수 있을까? R과 L, 즉 자본 제한을 높이는 방법은 명확한 한계가 있다는 것은 이미 논의가 되었다. 한가지 우리가 생각할 수 있는 것은 롤업이 다수의 검증자들 중 단 한명의 검증자 만이라도 검증을 올바르게 수행하면 시스템의 안전성이 유지될 수 있다는 것이다. 그렇다면 단순한 모델에서 확장된 모델로 변경하여 검증자의 수를 늘리면 이들 중 누군가 한명쯤은 검증을 할 것이라 기대할 수 있지 않을까? 그리하여 롤업의 안전성도 지켜질 수 있지 않을까?

Multiple Verifiers

본격적으로 검증자의 수를 다수(N)로 늘리기 전에 먼저 이를 아주 단순화한 모델로부터 시작해보자. 즉, 검증자는 이제 1명이 아니라 단 2명이다. 두명의 검증자는 V1, V2이고, 시퀀서 S는 여전히 동일하다.

이 때, 다음과 같은 조건하에 각 검증자의 검증 및 비검증 기대 보수는 다음과 같이 나타낼 수 있다.

R = S의 보증금, V가 검증에 성공할 시 V에게 보상으로 주어진다.
L = V(N)의 롤업에 예치된 자산, V가 검증에 실패할 시 S에게 보상으로 주어질 수 있다. (두 검증자의 L은 같다고 가정한다.)
X = S가 공격할 확률
Y = 상대 검증자가 검증할 확률(예를 들어, V1의 관점에서 V2가 항상 검증할것임을 확신한다면 Y = 1이다.)
C = 검증 비용
F = 검증 단위당 V(N)가 얻는 수익 (두 검증자의 F는 같다고 가정한다.)

단, R, L > F > C > 0 이다.

검증 기대 보수: R*X + F-C
비검증 기대 보수: -L*X(1 - Y) + (1 - X(1 - Y))F

검증 및 비검증 보수의 표현식이 상당히 복잡해졌지만, 새롭게 추가된 부분인 (1 - Y)가 의미하는 바가 무엇인지 파악하면 이를 보다 직관적으로 이해할 수 있다. 롤업의 특징은 본인이 검증하지 않아도 다른 누군가가 검증한다면 내 자산또한 안전하게 지켜질 수 있다는 것이었다. 즉, Y가 1 혹은 1에 가깝다는 의미는 상대 검증자가 S를 검증할 것이라는 의미이고, 이는 곧 본인이 직접 검증하지 않아도, 심지어 시퀀서가 항상 공격을 하여 X가 1이 되어도 자신의 모든 자산과 추가적인 경제적 이익은 지켜질 수 있다는 것을 의미한다.

그렇다면 과연 두 검증자중에 어떤 검증자가 검증을 하게 될 것인지, 둘 다 검증을 하게 될지, 또는 아무도 검증을 하지 않게 될지가 궁금해진다. 이를 보다 직관적으로 살펴보기 위해 아주 단순한 게임 이론적 접근 방식을 사용해보자.

두 검증자의 검증 및 비검증 전략 선택에 대한 기대 보수는 다음과 같은 보수행렬표로 나타낼 수 있다.

두 검증자가 모두 검증에 성공했을 때 얻는 보상 R은 동일한 비율로 나누어진다고 가정한다.

이 게임의 내쉬균형은 각 변수의 값에 따라 달라지게 된다. 예를 들어, 시퀀서의 공격 확률이 높아 기대 검증 보상이 매우 높은 경우 모두가 검증(V, V) 하는 것이 균형이 되고, 반대로 공격 확률이 매우 낮아 비검증시 기대 손실이 크지 않다면 모두가 검증을 하지 않는것(NV, NV)이 균형이 된다. 또한, 공격 확률이 매우 높지도 매우 낮지도 않은 경우 두 검증자 중 단 한 명만이 검증을 하는 것(V, NV) (NV, V)이 균형이 된다. 이를 수식으로 나타내면 다음과 같다.

(V, V): X > 2C/R
(V, NV) (NV, V): 2C/R > X > C/(R+L+F)
(NV, NV): X < C/(R+L+F)

구체적인 예시를 통해 각 케이스들을 모두 살펴보도록 하자. 이 예시에서 X를 제외한 나머지 변수들의 값은 아래와 같이 주어졌다고 가정한다.

R = 100
L = 100
F = 5
C = 1

이 때, 시퀀서의 공격확률 X가 2C/R = 0.02 보다 큰 값인 X = 0.05 라고 가정해보자.

이 경우, 두 검증자 모두 검증 전략이 우월 전략이므로, (V, V)가 균형이 된다. 이는 매우 바람직한 상황이지만, 어디까지나 시퀀서의 공격확률이 매우 높은 상황을 가정한 것이므로, 현실적으로 이런 상황은 쉽게 발생하지 않을 것이다.

다음으로, X가 2C/R = 0.02 보다 작고, C/(R+L+F) = 0.0049 보다 큰 값인 X = 0.005 라고 가정해보자.

이 게임은 흥미롭게도 두 검증자가 같은 전략을 선택하는 순간 각자의 이익을 극대화하지 못하게 되고, 서로 다른 전략적 선택을 하는 것이 균형이 된다.

예를 들어, 검증자2가 검증 전략을 선택하게 되면 검증자1은 비검증 전략을 택할 것이고, 반대로 검증자 1이 검증 전략을 선택한다면 검증자 2는 비검증 전략을 선택할 것이다. 이와 비슷한 논리로 검증자2가 비검증 전략을 선택한다면 검증자1은 검증 전략을 선택하는게 가장 합리적이고, 반대로 검증자1이 비검증 전략을 택한다면 검증자2는 검증 전략을 택하게 된다.

즉, 이 게임에서는 두가지 균형이 존재하는데, (NV, V) (V, NV)가 바로 그것이다. 그렇다면 이 게임에서 두가지 균형중 어떠한 균형이 실현되는가? 이는 공약과 신빙성과 같은 요소에 따라 결정되는데, 예를 들면 다음과 같다.

이 게임에서 검증자2가 검증하지 않는 전략을 택했다고 하자. 검증자2는 공공연하게 검증자1에게 “나는 검증에 필요한 요구사항을 갖춘 장비가 없으므로 앞으로 검증을 하지 않겠다”고 엄포한 상황이다. 하지만 검증자1은 현재 검증을 할 수 있는 여건이 모두 마련된 상황이다. 이 때, 검증자1이 택할 수 있는 가장 합리적인 선택은 비검증 전략을 선택해 손해를 보는것보다, 소액의 검증 비용을 지불하더라도 상대적으로 더 높은 기대 보수를 얻을 수 있는 검증 전략일 것이다.

즉, 우리는 X가 충분히 높지도, 낮지도 않은 어떠한 지점에서는 두 검증자 중 단 한명의 검증자만이 검증 전략을 선택할 것임을 알 수 있다.

마지막으로, 시퀀서의 공격확률 X가 C/(R+L+F) = 0.0049 보다 작은 값인 X = 0.0001 라고 가정해보자.

이 게임에서는 두 검증자 모두 비검증 전략이 우월전략이기 때문에, (NV, NV)가 균형이 된다. 계속해서 강조하듯이 롤업의 시퀀서는 사전에 각 변수들에 대한 정보를 미리 알 수 있기 때문에 효과적인 공격 확률을 계산할 수 있다. 따라서 시퀀서는 검증자들이 단 한명이라도 검증 전략을 선택하지 않을 수준의 확률로 공격을 할 것이다. 즉, 만약에 시퀀서가 공격을 한다면 C/(R+L+F)보다 낮은 확률로 공격을 할 것이다.

정리하면, 검증자의 수를 2명으로 늘린 모델에서도 시퀀서의 공격확률에 따라 각 검증자는 검증 또는 비검증 전략을 선택하게 되고, 공격확률이 낮아질수록 검증 전략을 선택하는 검증자의 수가 줄어든다는 것을 알 수 있다. 이는 검증자의 수를 N명으로 늘려도 크게 달라지지 않는다. 검증자의 수가 늘어날수록 기대 검증 보상의 양은 줄어들 것이고, 공격 확률이 아주 낮지 않은 경우에도 다른 한명의 검증자만 검증해도 자신의 이익을 지킬 수 있기 때문에 계속해서 검증 전략을 선택하는 검증자의 수는 줄어들 것이다. 또한 공격 확률이 매우 낮은 경우에는 단 한명의 검증자도 검증 전략을 선택하지 않게 된다.

이는 매우 충격적인 결과인데, 검증자의 수와 관계 없이 롤업이 장기적으로 안전하게 운영 될수록 활성화된 검증자의 수는 계속해서 줄어들어 0에 수렴할 것이라는 사실이다.

There is No Verifier’s Dilemma in Optimistic Rollup?

앞서 논의한바와 같이 롤업이 검증자의 딜레마로 인해 안전성 측면에서 여러 문제점이 있음에도 불구하고, 롤업에서 검증자의 딜레마는 사소한 이슈이며 이를 해결하기 위한 별도의 장치를 둘 필요가 없다는 주장도 존재한다. 결론부터 말하자면, 이러한 주장 중 일부는 타당하고, 일부는 그렇지 않다.

대체로 롤업에서 검증자의 딜레마를 고려할 필요가 없다는 주장의 근거는 크게 네가지로 요약된다.

토큰 소유자(Token Holder)
댑 운영자(Dapp Builder) — 롤업에서 트랜잭션이 발생함에 따라 일정한 수익(예: 이자 농사(Yield Farming))을 거두는 모든 참가자로 치환해도 무방하다.
이타적 검증자(Altruist)
빠른 출금(Fast Withdrawal)

각 근거가 정말로 검증자의 딜레마를 해결할 수 있는지 혹은 그렇지 않은지 차례대로 살펴보도록 하자.

Token Holder

롤업에서 검증자의 딜레마를 고려할 필요가 없다는 주장의 근거로 가장 먼저 등장하는 내용은 바로 레이어 2에 많은 토큰(혹은 자산)을 보유한 사용자의 경우 검증을 할 유인이 높을 것이라는 것이다.

하지만, 많은 토큰을 보유한 사용자는 근본적으로 앞서 논의한 모델에서 L이 상대적으로 높은 검증자에 지나지 않는다. 따라서 이는 시퀀서의 공격확률을 소폭 낮추는것 외에는 어떠한 의미도 없다.

여기서 다시 한번 유의해야 할 점은 단순히 검증자가 롤업에 예치한 자산에 해당하는 L을 늘리거나 시퀀서의 보증금인 R을 늘리는것은 검증자의 딜레마를 해결하는데 큰 도움이 되지 않는다는 것이다.

Dapp Builder

또 다른 근거는 바로 롤업에서 댑을 운영하는 경우, 댑의 운영자는 롤업이 안전하게 운영되어야만 지속적인 수익을 보장받을 수 있으므로 검증에 대한 유인이 클 것이라는 것이다. 하지만 이 또한 앞에서 충분히 논의한 내용이다. 검증단위당 얻는 수익 F가 크더라도, 이는 비검증시에도 시퀀서의 공격만 없다면 보장되는 수익이기 때문에 역시 시퀀서의 공격확률에 따라 검증 또는 비검증 전략을 선택하게 된다. 즉, 큰 규모의 댑을 운영하여 해당 댑의 운영자가 막대한 수익을 거두더라도 이것이 해당 댑의 운영자가 롤업을 항상 검증할 것이라는 보장으로 이어지지는 않는다.

Altruist

다음 근거는 바로 이타주의이다. 이 세상의 모든 사람들은 항상 합리적이고 자신의 이익만을 극대화하는 선택만을 하지는 않는다. 만약 그렇다면, 수 많은 조건 없는 기부와 봉사 등의 행동은 설명되지 않는다. (물론 이 또한 기부 혹은 봉사에 소요되는 경제적 비용보다 비경제적 효용이 더 크다는 것으로 설명될 수 있다.)

요컨대, 검증행위가 경제적으로는 손실일지라도 이 세상의 이타적인 누군가는 검증행위를 수행해줄 것이라는 것이 주장의 요지이다. 한 예로, 비트코인 혹은 이더리움 네트워크에서 일체의 마이닝 보상을 얻지 않지만 모든 일련의 블록 데이터들을 저장하고 이를 다른 노드와 공유하는 사람들이 분명히 존재한다. 이들은 이 행위로 어떠한 경제적 이익을 거두지 못하지만, 어떠한 이유로든 이타적으로 블록을 저장하고 공유하는 것이다.

하지만, 이 또한 문제가 아닌 것은 아니다. 이더리움의 아카이브 노드 수가 적다는 것은 꾸준히 제기되어 온 문제이다. 이더리움의 블록이 늘어남에 따라 상태 데이터는 계속해서 빠른 속도로 증가하고 있고, 이를 어떠한 인센티브도 없이 단순히 이타적인 참가자들이 아키이브 노드를 유지해줄 것이라 기대하는 것은 장기적으로 지속 불가능하다.

이는 일견 일리가 있어보이는 주장이지만, 우리는 검증자의 딜레마를 해결 또는 완화할 이론적 근거를 찾고 있다는 것에 유의해야 한다. 즉, 이타적 검증자는 실제로 롤업이 운영될 때 전체 네트워크의 관점에서 매우 도움이 되는 참가자들 이지만, 네트워크의 안전성을 보장하기 위해 어떠한 메커니즘 혹은 장치를 설계할 때 그 이론적 근거가 되어서도, 또한 될 수도 없는 요소이다.

만약 여러분이 이더리움의 설계자라고 가정해보자. 누군가 블록 데이터를 기록하고 보관할 인센티브가 명확하지 않은데, 이를 어떻게 해결할 생각인지 질문을 한다면 여러분은 어떻게 대답을 할 것인가. 적어도 그 대답이 세상에는 이타적인 사람들이 존재하기 때문에 어떻게든 이 사람들이 그 기록들을 모두 유지시켜 줄 것이라는 내용이라면 크게 설득력이 있다고 보기 힘들것이다.

비탈릭 부테린 또한 자신의 글에서 다음과 같이 롤업의 검증 인센티브를 설계하는데에는 이타주의보다 더 명확한 이론적 근거가 필요하다고 주장하였다.

Auditing incentives — how to maximize the chance that at least one honest node actually will be fully verifying an optimistic rollup so they can publish a fraud proof if something goes wrong? For small-scale rollups (up to a few hundred TPS) this is not a significant issue and one can simply rely on altruism, but for larger-scale rollups more explicit reasoning about this is needed.

Fast Withdrawal

마지막 근거는 바로 빠른 출금이다. 빠른 출금이 검증자의 딜레마를 고려할 필요가 없다는 주장의 근거로 제시되는 이유를 이해하기 위해서는 먼저 빠른 출금이 무엇인지 파악해야 한다.

빠른 출금은 롤업에서 DTD(Dispute Time Delay)로 인해 출금에 필요한 시간이 오래 걸리는 것에 대한 대안으로 제시된 방법이다. 빠른 출금은 일종의 중개인이 레이어 2의 사용자로부터 출금을 원하는 금액의 토큰을 사고, 레이어 1에서 해당 금액에서 수수료를 뺀 금액의 토큰을 사용자에게 바로 전송해주는 방법을 말한다.

앨리스와 이반의 예시를 통해 빠른 출금을 자세히 알아보자.

앨리스는 이반에게 0.1ETH의 수수료를 지불하고 L2에서 L1으로 10ETH를 출금하고자 한다.
앨리스는 빠른 출금 마켓 컨트랙트에 10ETH를 송금한다.
이반은 출금 요청을 확인 및 검증하고 L1에서 앨리스에게 수수료를 제외한 금액 9.9ETH를 송금한다.
출금에 필요한 DTD가 지난 후에 이반은 L2의 컨트랙트에 보관된 10ETH를 취득한다.

여기서 중요한점은 이반은 앨리스의 빠른 출금을 처리하는 과정에서 앨리스의 출금이 올바른 요청인지 아닌지를 검증하게 된다는 것이다. 이는 곧 롤업의 상태가 올바르게 구성되었는지 검증하는 것을 의미한다. 검증자의 딜레마에서 문제가 되는 지점은 검증자의 검증 보상이 시퀀서의 공격 행위가 발생할 확률에 의존한다는 점이었다. 하지만 빠른 출금의 사례에서 이반은 시퀀서의 공격 행위와 무관하게 검증을 할 유인이 있는 것처럼 보인다!

이를 바탕으로 Super-Simple Model에서와 같이 이반의 검증 및 비검증 기대보수를 정의해보자.

이반이 빠른 출금을 처리하여 받는 수수료가 F라고 할 때, 검증작업에 대한 이반의 기대보수는 다음과 같다. 이 때, 이미 롤업에는 이반 이외의 N명의 검증자가 있다고 가정한다.

검증 기대 보수: R*X + F - C
비검증 기대 보수: -L*X + (1-X)F

여기서 재밌는 것은 롤업의 다른 검증자들과 달리 이반은 다른 검증자들의 검증 여부가 자신의 검증 및 비검증 보수에 어떠한 영향도 끼치지 않는다는 것이다. 그 이유는 빠른 출금이 갖는 특수한 성질 때문인데, 이반은 앨리스에게서 출금 요청을 받은 후 가능한 빠른 시간 내에 L1에서 자신의 토큰을 송금하게 된다. 하지만 만약 앨리스의 출금 요청이 실제로는 잘못된 요청이었다는 사실이 DTD내에 다른 검증자에 의해 밝혀지더라도 이반은 자신의 토큰을 돌려받을 수 없게 된다. 이미 L1의 토큰은 엘리스에게 전송되었기 때문이다. 즉, 이반이 빠른 출금을 안전하게 처리하기 위해서는 다른 검증자에 의존하는 것이 아닌 이반 스스로 검증 작업을 수행해야 한다는 것이다.

이는 상당히 흥미로운 사실인데, 만약 롤업에 단 두명의 검증자만이 존재하고 한명은 이반과 같은 빠른 출금의 중개인이고 다른 한명은 평범한 검증자(e.g 토큰 보유자, 댑 운영자 등)라면, 이반은 일반적인 검증자에 비해 검증 전략을 선택할 가능성이 더 높다. 다음 보수행렬표를 통해 이를 자세히 살펴보자.

앞서 언급했듯, 상대 검증자가 검증 전략을 선택하더라도 이반은 빠른 출금을 이용한 시퀀서의 공격 행위를 효과적으로 방어하기 어렵다. 따라서 이반이 비검증 전략을 선택하는 경우의 기대보수는 모두 동일하게 -L*X+(1-F)X 이다. 이것이 시사하는 바는 이반과 검증자 두 참가자 중 누군가 한명은 반드시 검증 전략을 선택해야 하는 상황(두명의 일반적인 검증자가 존재하는 모델에서 시퀀서의 공격확률이 매우 높지도, 낮지도 않은 상황과 유사하다)에서 이반이 상대적으로 검증 전략을 선택할 유인이 더 높다는 것이다.

보다 구체적으로, 2C/R > X > C/(R/2+L+F) 인 경우에 균형은 (V, NV)가 된다. 앞서 두 검증자만을 다룬 모델에서는 동일한 조건하에 균형이 (V, NV) (NV, V) 였다. 즉, 공격 확률이 높지도 낮지도 않은 상황에서 이반은 항상 검증 전략을, 상대 검증자는 항상 비검증 전략을 선택하게 될 것임을 의미한다. 이를 구체적인 예시를 통해 살펴보자.

다음과 같은 조건하에 이반과 검증자의 보수행렬표는 다음과 같이 구성된다.

R = 100
L = 100
F = 5
C = 1
X = 0.007

만약 이반이 일반적인 검증자였다면, 이 경우에 균형은 (V, NV) (NV, V) 이었을 것이다. 하지만 이반은 빠른 출금의 중개인이므로 검증 전략이 우월 전략이 된다. 따라서, 상대 검증자는 항상 비검증 전략을 선택할 것이다. 따라서 (V, NV)가 균형이 된다.

정리하면, 동일한 조건 하에서 빠른 출금의 중개인은 일반적인 검증자에 비해 검증 유인이 더 크다고 볼 수 있다. 즉, 누군가 검증을 하게 된다면 이는 빠른 출금의 중개인일 가능성이 매우 높다는 것이다. 하지만, 이 사실이 이반이 항상 검증 전략을 선택할 것임을 증명하는 것은 아니다.

다시 한번 강조하자면, 이반이 검증 전략을 선택하는 것에 대한 유인이 상대적으로 큰 것은 사실이지만, 실질적으로 이러한 전략적 선택을 할 때는 시퀀서의 공격 확률이 고려된다. 따라서 이제 우리가 중점적으로 보아야 하는 것은 빠른 출금의 중개인은 정확히 어떠한 기준으로 이러한 전략적 선택을 하게 되고, 이 중개인이 가능한 검증 전략을 선택하게 하려면 어떠한 요인이 필요한가를 알아보는 것이다. 이를 다음 장에서 구체적으로 알아보도록 하자.

Fast Withdrawal and Auditing Incentives

이 장에서는 빠른 출금의 중개인인 이반이 롤업에 대한 검증 및 비검증 전략을 어떻게 선택하게 되는지, 그 변인은 무엇인지, 나아가 이반이 항상 롤업을 검증하게 하기 위해서는 어떠한 추가적인 장치가 필요한지 자세히 살펴본다.

Attack-Verify Game

빠른 출금의 중개인인 이반이 어떠한 기준으로 검증 및 비검증 전략을 선택하게 되는지를 알아보기 위해 이반과 시퀀서의 단순한 Attack-Verify Game을 다음과 같이 구성해보자.

이 단순한 게임의 경기자는 이반과 시퀀서 단 두명이다. 시퀀서는 이반에게 빠른 출금을 요청하게 되며, 이 때 위조된 토큰을 이용하여 빠른 출금을 요청할지 또는 올바른 토큰을 이용하여 빠른 출금을 요청할지 선택할 수 있다. 이를 공격과 비공격 전략이라고 부르겠다.

반대로 이반은 시퀀서의 빠른 출금 요청을 받으면 이를 검증하고 처리할 것인지 또는 검증을 하지 않고 처리할 것인지 선택할 수 있다. 이를 검증과 비검증 전략이라고 하겠다.

이 게임에서 이반과 시퀀서는 서로의 전략적 선택에 따라 얻을 수 있는 기대보수가 달라지게 되는데, 이는 구체적으로 다음과 같은 보수행렬표로 나타낼 수 있다.

R: 시퀀서 S의 보증금 / 검증 성공시 이반에게 주어지는 보상
L: 빠른 출금 금액 / 시퀀서의 공격 성공시 이반이 잃는 금액
F: 빠른 출금 수수료
C: 검증 비용

시퀀서의 비공격시의 효용이 0인 이유는 빠른 출금을 이용함으로써 얻는 효용이 지불된 수수료 F와 같다고 간주했기 때문이다. 만약 이를 다른수로 바꾸더라도 시퀀서의 (V,NA), (NV,NA)기대보수는 모두 같을 것이고, (V,A),(NV,A)의 기대보수와 비교했을 때 유의미한 차이를 기대하기는 어렵다.

이 때, R,L > F > C 라는 가정하에 이 게임에서 순수전략 내쉬균형은 존재하지 않는다. 예시를 통해 이를 구체적으로 살펴보자.

R = 100
L = 100
F = 5
C = 1

이 값을 위에서 구성한 보수행렬표에 대입하면 다음과 같다.

이 게임에서 이반과 시퀀서 모두에게 우월전략과 열등전략은 존재하지 않는다. 또한 순수전략 내쉬균형도 존재하지 않는다. 이는 서로의 전략적 선택에 따라 각자의 전략적 선택이 완전히 달라지기 때문이다. 만약 시퀀서가 공격을 하지 않는다면 이반은 검증을 하지 않는 것이 유리하고, 이반이 검증을 하지 않는다면 시퀀서는 공격을 하는 것이 유리하다. 반대로 시퀀서가 공격을 한다면 이반은 검증을 하는 것이 유리하고, 이반이 검증을 한다면 시퀀서는 공격을 하지 않는 것이 유리하다.

이처럼 이반과 시퀀서의 게임에서 단 하나의 전략 벡터를 선택하는 순수전략 균형은 존재하지 않는다. 이는 다시 말해, 이반과 시퀀서 모두 상황에 따라 단 하나의 전략이 아닌 두가지 전략 모두를 사용하게 될 것임을 의미한다.

Mixed Strategy Nash Equilibrium

그렇다면 이반 또는 시퀀서는 두가지 전략을 어떠한 기준으로 선택하게 될까? 이를 알아보기 위해 우리는 혼합전략 내쉬균형이 무엇인지 살펴볼 필요가 있다.

혼합전략을 사용할 때 각 경기자의 최적전략은 상대방이 어떠한 선택을 하더라도 기대보수가 같아지게끔하는 것이다. 즉, 상대방이 어떠한 전략을 취하더라도 기대보수가 무차별해지는 지점을 찾는 것이다.

이반이 검증전략을 선택할 확률을 P라고 하고, 시퀀서가 공격전략을 선택할 확률을 Q라고 한다면, 혼합전략 내쉬균형에 따른 각 확률 P, Q는 다음과 같다.

-R*P + L(1-P) = 0*P + 0*(1-P)
P = L/(R+L)
(R+F-C)Q + (F-C)(1-Q) = -L*Q + F(1-Q)
Q = C/(R+L+F)

이에 앞의 예시에서 사용한 변수값을 할당하면, 혼합전략 내쉬균형은 다음과 같이 계산된다.

P = 1/2
Q = 1/205

즉, 이반은 검증전략과 비검증전략을 각각 2번에 1번꼴로 선택한다. 반대로 시퀀서의 경우 205번에 1번꼴로 공격전략을 205번에 204번꼴로 비공격 전략을 선택하게 된다. 하지만 우리가 원하는 것은 이반이 오직 2번에 1번꼴로 검증전략을 선택하는 것이 아니라 이를 최대한 1에 가깝게 만드는 것이다. 또한 시퀀서의 공격확률을 1/205에서 0에 가깝게 줄이는 것이다. 이 두가지 목적을 모두 달성하기 위해서 우리는 어떠한 조치를 취해야 할까?

가장 효과적인 방법은 L을 늘리는 것이다. L을 높이는 것은 검증자의 검증 전략 선택 확률을 높임과 동시에 시퀀서의 공격 전략 선택 확률을 줄이는 역할을 한다. 반대로, R을 높이는 것은 공격 확률을 줄이는 역할을 할 수는 있지만, 검증 전략 선택 확률은 오히려 줄이는 역할을 한다. 요컨대, 만약 롤업에서 자본 제한을 높여 검증자의 딜레마를 해결하려 한다면 L을 높이는 것이 가장 유효한 방법이라는 것이다. 하지만, 아쉽게도 이러한 자본제한을 높이는 방법은 명백히 한계가 존재한다. 따라서 우리는 이 문제를 해결하기 위해 다른 접근 방법이 필요하다.

Maximin Strategy

우리는 혼합전략 내쉬균형을 통해 이반과 시퀀서가 일정 확률에 따라 검증과 공격에 대한 전략적 결정을 내리게 된다는 것을 알아보았다. 하지만 과연 현실세계에서 이반과 시퀀서는 정확히 이 균형에 부합하는 확률로 각 전략을 선택하게 될것인가에 대해 의문이 생긴다. 두 경기자 모두 이익을 극대화하는 전략을 선택했을 때 추가적으로 얻는 기대 이익은 비교적 낮은 반면에 그 과정에서 잘못된 전략적 선택을 했을 때 발생하는 손실은 그야말로 재앙에 가깝기 때문이다.

예를 들어, 이반은 비검증전략을 선택할 경우 시퀀서가 공격을 하지 않는다면 단 1만큼의 추가 보수를 얻는 반면에, 시퀀서가 공격 전략을 선택했을 경우 -100이라는 큰 손실을 보게 된다. 시퀀서 또한 비공격시 얻는 것도 잃는 것도 없지만, 공격을 선택하고 실패했을 경우의 기대손실이 상대적으로 매우 크다.

이러한 경우 일반적으로 경기자는 이익의 극대화보다는 안전성을 추구하는 경향이 있다. 이 때 경기자가 선택할 수 있는 전략이 바로 최소극대화 전략이다.

이는 비단 이반의 검증 및 비검증 전략 선택에만 해당되는 이야기는 아니다. 예를 들어, 암호화폐를 거래하고 보유하는 사용자들은 리스크를 대하는 성향에 따라 암호화폐를 보관하는 방법에 있어 다양한 전략적 선택을 하게 된다. 암호화폐를 보유하고 거래할 때 일반적으로 가장 편리한 방법은 중앙화된 거래소에 보관하는 것이다. 하지만 이러한 방법은 거래소에 문제가 발생했을 경우 자신이 보유한 암호화폐를 잠재적으로 모두 잃어버릴 위험이 있다. 때문에 위험 회피 성향이 낮은 사용자들은 거래소에 암호화폐를 보관하고 거래하지만, 위험 회피 성향이 다소 높은 사용자들은 거래소에 암호화폐를 보관하지 않고 메타마스크와 같은 지갑 서비스를 이용하거나 혹은 하드웨어 월렛을 사용하게 된다. 이에 더해 위험 회피 성향이 극도로 높은 사용자는 암호화폐 자체에 문제가 생길 수 있으므로 동시에 풀 노드 혹은 아카이브 노드를 운영하게 된다. 이들 모두 암호화폐를 거래소에 보관했을 때 얻는 기대보수는 동일하지만, 위험 회피 성향의 정도, 즉 전략적 안전성을 얼마나 중요시 하느냐에 따라 전략적 선택이 달라지는 것이다.

최소극대화 전략은 경기자가 선택할 수 있는 전략이 각각 최악의 결과를 가져온다고 가정하고, 그 중에 그나마 큰 보수를 택하는 전략을 의미한다. 즉, 다른 경기자가 어떠한 결정을 하더라도 최소한으로 보장받을 수 있는 보수를 극대화하는 것이다.

앞서 예시로 든 보수행렬표에서 이반과 시퀀서가 내쉬균형이 아닌 최소극대화 전략을 따른다고 가정해보자.

이 때, 이반의 최소극대전략은 V가 되고 시퀀서의 최소극대전략은 NA가 된다. 따라서 두 경기자의 최소극대 보수벡터는 (4,0) 이 된다. 다시 말해, 이반과 시퀀서는 최소극대화 전략을 선택할 경우 각각 항상 검증 전략과 비공격 전략을 선택하게 됨을 의미한다.

따라서 우리는 이반과 시퀀서, 혹은 이반만이 전략적 안전성을 최우선으로 두고 있다는 가정하에 빠른 출금이 발생할 때마다 항상 해당 롤업은 검증될 것이라는 결론에 도달할 수 있다.

하지만 모든 경기자가 전략적 안정성(stability)보다 안전성(security)을 우선한다고 가정하는것은 무리가 있다. 경기자의 성향은 각 개인마다 다를 것이기 때문이다. 따라서 최소극대화 전략을 통한 접근은 검증자의 딜레마를 기존보다 다소 완화할 수는 있겠지만 이를 완전히 해결했다고 볼 수 없다.

Fast Withdrawal With Attention Challenge

앞서 우리는 각 경기자가 전략적 안전성을 우선 가치로 둔다는 가정하에 검증자의 딜레마가 해결될 수 있다는 점을 살펴보았다. 하지만 이는 여전히 경기자의 성향에 대한 가정을 요구하므로, 검증자의 딜레마를 다소 완화했을 뿐 완전히 해결한것은 아니라는 점 또한 논의하였다.

만약 이러한 가정도 요구하지 않고 검증자의 딜레마를 해결하려면 어떠한 추가적인 장치가 필요할까? 빠른 출금의 사례에서 이반이 반드시 검증전략을 선택하지 않는 이유는 매우 단순하다. 검증전략이 우월전략이 아니기 때문이다.

반대로 생각해서 검증전략을 우월전략으로 만들기 위해서는 어떻게 해야할까? 이 또한 매우 단순하다. 비검증-비공격 전략에 대한 이반의 보수를 검증-비공격 전략의 보수보다 작거나 같도록 만드는 것이다. 우리는 빠른 출금에 주의 챌린지(Attention Challenge)를 도입하는 것으로 이러한 목적을 달성할 수 있다.

주의 챌린지는 Ed Felten의 글 Cheater Checking: How attention challenges solve the verifier’s dilemma 에서 제시된 개념으로, 랜덤하게 주기적으로 특정 검증자가 올바르게 검증을 수행했는지 확인하는 장치이다. 주의 챌린지가 구체적으로 어떻게 동작하는지에 대해서는 해당 글을 참고하거나 아래의 관련 연구(Related Research)파트를 참고하라.

주의 챌린지를 롤업에 도입할 경우 아래와 같이 동작하게 된다. 이는 매우 단순화한 설명임에 유의하라.

시퀀서는 롤업에서 트랜잭션을 처리한 후의 상태값을 임의의 랜덤값과 함께 해싱(Hashing)하여 다른 검증자들이 알 수 없게 제출한다.
검증자들은 이러한 상태값을 알지 못한 상태로 랜덤한 확률로 주의 챌린지의 대상이 된다.
이 때 대상으로 선정된 경우 검증자는 시퀀서와 동일하게 트랜잭션을 처리한 후의 상태값을 제출한다.
3번 과정에서 선정된 검증자가 정해진 시간 내에 응답하지 않거나, 또는 잘못된 응답을 제출했을 경우 보증금을 몰수당한다.

이러한 방식을 이반과 시퀀서의 게임에 적용하면,아래와 같이 보수행렬표를 재구성할 수 있게 된다.

C = 검증비용 + 주의 챌린지 응답 비용
A = 이반의 주의 챌린지 보증금. 주의 챌린지에 제대로 응답하지 못하는 경우 모두 삭감당한다.
P = 이반이 주의 챌린지의 대상으로 지정될 확률

이 때, 우리는 P*A > C라면, 이반에게 검증 전략이 우월전략이 된다는 것을 쉽게 알 수 있다. 즉, 주의 챌린지에 제대로 응답하지 못했을 경우 발생하는 손실이 검증 비용보다 크다면 이반은 반드시 검증 전략을 선택하게 될 것이다. 이를 구체적인 예시를 통해 확인해보자.

각 변수의 값이 아래와 같을 때, 주의 챌린지를 적용한다면 다음과 같이 보수행렬표를 구성할 수 있다.

R = 100
L = 100
F = 5
C = 2
A = 50
P = 0.1

위 보수행렬표에 따르면 이반은 검증 전략이 비검증 전략보다 모든 경우에서 기대 보수가 더 높으므로, 검증 전략이 우월전략이 된다. 시퀀서는 이반이 항상 검증 전략을 선택할 것이기 때문에 반드시 비공격 전략을 선택하게 된다. 따라서 (V, NA) 전략벡터가 순수전략 내쉬균형이 되며, 이는 곧 롤업의 안전성이 항상 지켜질 수 있음을 의미한다!

주의 챌린지를 일반적인 검증자에게 도입하게 되면, 이 경우 또한 검증 전략이 항상 우월전략이 될 수 있도록 유도할 수 있다. 하지만 주의 챌린지의 특성상 L1과의 상호작용을 요구하기 때문에 주의 챌린지의 대상과 확률을 확대하는 것은 시스템 차원에서 큰 부담이 될 수 있다. 이에 대한 자세한 내용은 Trade-Off of Attention Challenge에서 자세히 다룬다.

Cross-Rollup Transaction

앞서 우리는 빠른 출금의 중개인이 전략적 안정성이 아닌 안전성을 택할 경우나, 혹은 주의 챌린지를 도입했을 경우 반드시 롤업을 검증하는 전략을 선택할 것임을 확인하였다. 재밌는 점은 롤업에서 빠른 출금의 중개인과 완전히 동일한 보수 구조를 갖는 또 다른 참가자가 존재한다는 것이다. 이는 바로 크로스 롤업 트랜잭션(Cross-Rollup Transaction)의 중개인(이하 롤업 중개인)이다.

이 글에서 다루는 크로스 롤업 트랜잭션은 다음 두 글에서 다룬 내용을 바탕으로 한다.

크로스 롤업 중개인은 빠른 출금의 중개인과 유사한 방식으로 롤업과 롤업간의 빠른 토큰 전송 서비스를 제공할 수 있다. 예를 들어, 서로 다른 롤업 A와 B가 있고, 앨리스가 롤업 중개인 이반을 통해 토큰을 A에서 B로 전송하려고 할 때 다음과 같은 방식으로 이를 진행할 수 있다.

앨리스는 이반에게 0.1 ETH의 수수료를 지불하고 롤업 A에서 B로 10 ETH를 전송하고자 한다.
앨리스는 크로스 롤업 마켓 컨트랙트에 10 ETH를 송금한다.
이반은 크로스 롤업 트랜잭션 요청을 확인 및 검증하고 B에서 앨리스에게 수수료를 제외한 금액 9.9 ETH를 송금한다.
출금에 필요한 DTD가 지난 후에 이반은 A의 컨트랙트에 보관된 10 ETH를 취득한다.

이를 통해 알 수 있는 것은 출금과 송금의 목적지만 L1에서 롤업 B로 달라졌을 뿐 다른 요소는 전혀 변경되지 않았다는 것이다. 이는 롤업 중개인 이반도 빠른 출금의 중개인 이반과 동일한 검증 및 비검증 기대보수를 갖는다는 것을 의미한다.

따라서 크로스 롤업 중개인 이반과 시퀀서의 보수 행렬표는 빠른 출금 중개인 이반과 시퀀서의 그것과 동일하게 아래와 같이 나타낼 수 있다.

R: 시퀀서 S의 보증금 / 검증 성공시 이반에게 주어지는 보상
L: 크로스 롤업 송금액 / 시퀀서의 공격 성공시 이반이 잃는 금액
F: 크로스 롤업 송금 수수료
C: 검증 비용

이는 빠른 출금 중개인 이반의 그것과 완전히 동일하다. 따라서 크로스 롤업 중개인 이반 또한 최소 극대화 전략을 선택한다고 가정하거나, 또는 이와 같은 가정 없이 주의 챌린지를 적용하는 경우 항상 검증전략을 선택하게 된다.

이는 매우 고무적인 결과인데, 상대적으로 검증 유인이 높은 검증자의 수가 빠른 출금의 중개인에서 크로스 롤업 중개인까지 확대될 수 있음을 의미하기 때문이다.

Trade-Off of Attention Challenge

앞서 우리는 빠른 출금과 크로스 롤업 트랜잭션의 중개인에게 주의 챌린지를 도입하여 항상 검증 전략을 선택하도록 만들 수 있었다. 주의 챌린지 자체는 비단 이러한 중개인들뿐 아니라 다른 모든 검증자, 즉 롤업의 사용자에게 적용가능한 방법이다. 주의 챌린지를 확대해서 적용하면 모든 검증자들이 검증을 하는 것이 우월전략이 되므로, 이는 롤업의 안전성을 극대화하는 아주 좋은 전략이 될 수 있다.

하지만, 이는 두가지 측면에서 맹점이 존재한다.

첫째, 주의 챌린지에 응답하는 행위는 온체인(on-chain) 트랜잭션을 수반하므로, 주의 챌린지의 대상이 늘어난다는 것은 필요한 온체인 트랜잭션의 수가 많아진다는 것을 의미한다.

둘째, 롤업의 모든 사용자가 주의 챌린지의 대상이 된다면, 이는 롤업의 사용자 경험을 심각하게 저해할 수 있다.

첫번째 이슈부터 자세히 논의해보자. 주의 챌린지의 대상이 늘어난다는 것은 필연적으로 주의 챌린지에 응답하는 대상의 수가 늘어나는 것을 의미한다. 물론 대상이 되는 검증자의 수(N)가 많아질수록 주의 챌린지의 대상으로 선정될 확률 P를 줄이면, 주의 챌린지에 대한 응답 횟수를 적절히 조절할 수 있으므로 문제가 없다고 할 수 있다. 하지만 P를 지나치게 줄이게 될 경우 주의 챌린지에 제대로 응답을 하지 못했을 경우 발생할 수 있는 기대 손실(-P*A)이 낮아지게 되고, 이는 곧 주의 챌린지가 검증전략이 항상 우월전략이 되도록 유도할 수 없게 될 수 있음을 의미한다. 물론 이 경우에도 A를 높여 이를 상쇄할 수 있겠지만, 이는 곧 자본제한을 높이는 것을 의미하기 때문에 바람직한 해결책이라고 보기는 힘들다. 요컨대, 검증자의 수를 늘리는 것은 주의 챌린지로 인해 더 많은 양의 온체인 트랜잭션이 발생할 수 있음을 의미한다.

두번째 이슈는 주의 챌린지의 대상을 무분별하게 확대할 경우 롤업의 사용자 경험을 저해할 수 있다는 것이다. 롤업의 장점은 모든 사용자가 검증자가 되지 않아도, 즉 최소한 한명의 정직한 검증자만 있어도 안전하게 동작할 수 있다는 것에 있다. 물론, 롤업의 정직한 검증자는 다다익선 이지만, 이것이 모든 사용자가 검증자가 되어야 한다는 것을 의미하는 것은 아니다. 극단적으로 표현하면 롤업을 아무도 검증하지 않게 만드는 것만큼 바람직하지 않은 것이 모두가 롤업을 검증하게 만드는 것이다. 이는 이미 이더리움 커뮤니티에서 플라즈마의 단점을 논의할 때 충분히 논의된 것이므로 더 이상의 자세한 설명은 생략하겠다.

요컨대, 우리는 주의 챌린지를 무분별하게 적용해서는 안된다. 가장 바람직한 것은 각 롤업이 달성하고자 하는 안전성 수준에 맞추어 적절한 대상에게 주의 챌린지를 현명하게 적용하는 것이다. 만약 빠른 출금과 크로스 롤업 트랜잭션이 활발하게 발생하고 있다면, 주의 챌린지를 굳이 적용하지 않아도 될 수 있다. (전략적 안전성을 택하는 중개인의 비율이 충분하다고 가정한다면 말이다.) 반대로, 롤업이 배포된 초기에는 빠른 출금이나 크로스 롤업 트랜잭션이 활발하게 발생하지 않을 수 있고, 활성화된 검증자의 수가 매우 적을 수 있다. 이러한 경우에는 주의 챌린지를 적극적으로 도입하는 것이 롤업의 안전성을 지키는데 큰 도움이 될 수 있다.

Additional Reward to Attention Challenge

주의 챌린지는 안전성을 극대화하는데 아주 효과적인 방법이지만, 검증자에게 일종의 부정 피드백(Negative Feedback)인 처벌로 검증을 유도한다. 이 때, 검증자는 주의 챌린지로 인해 검증 전략을 선택하게 되지만, 이러한 검증을 통해 추가적으로 얻는 보상은 없고 오직 비용만 추가적으로 발생할 뿐이다. 따라서 모든 검증자들은 주의 챌린지의 도입에 대해 긍정적인 관점으로 바라볼 수 없게 된다.

하지만, 주의 챌린지의 대상이 되는 검증자들에게 추가적인 보상을 지급할 수 있다면, 개별 검증자가 주의 챌린지로 인해 발생하는 경제적 비용을 완화하거나 이를 상회할 수 있을 것이다. 예를 들어, 특정 롤업에서 자체적으로 발행되는 토큰이 있고, 이 토큰의 일부가 주의 챌린지에 참여하는 검증자에게 보상으로 주어진다고 하자. 이 때, 이 보상의 양이 주의 챌린지의 응답비용보다 높다면 모든 검증자들은 주의 챌린지에 대해 어떠한 부담도 느끼지 않을 것이다.

사용자에게 추가적인 수수료를 징수하여 검증자에게 지급하는 것도 하나의 방법일 수 있다. 하지만 이 경우 사용자에게 추가적인 비용을 부과하는 것이 큰 부담이 되지 않도록 신중하게 비용의 수준을 조정해야 할 것이다.

Repeated Game

지금까지 다루었던 이반과 시퀀서의 검증게임은 모두 일회게임(one-shot game)이었다. 하지만 현실세계의 많은 경제활동은 동일한 주체들간의 반복적 상호작용으로 일어난다. 이와 마찬가지로 롤업 세상에서 일어나는 검증게임 또한 단 1회로 끝나는 것이 아니다. 이반과 시퀀서는 여러번에 걸쳐 진행되는 반복게임(repeated game)을 진행하게 될 것이다. 이들은 반복게임의 각 단계(stage)별로 이전에 각자가 행동했던 결과의 기록(history)에 따라 현재 단계에 대한 전략적 선택을 하게 될 것이다. 우리는 이러한 측면에서 이반과 시퀀서의 검증게임을 단순히 일회게임이 아닌 반복게임의 관점에서 분석해 볼 필요가 있다.

먼저 반복게임이 무한하게 진행되는 무한반복게임에서는 일회게임의 균형과는 다르거나 또는 더 많은 균형이 존재할 수 있다는 사실은 잘 알려져있다. 이는 바로 무한반복게임에서는 일회게임이나 유한반복게임과 달리 협조체제가 달성될 수 있기 때문인데, 현재 상대방을 속여 당장의 이득을 취하더라도 상대방의 보복에 따른 미래의 손실이 크다면 지금 유지되고 있는 협조관계를 깨지 않는 것이 유리하기 때문이다.

반대로 동일한 반복게임에 포함되지만, 반복횟수가 유한한 유한반복게임은 이야기가 전혀 다르다. 유한반복게임에서는 무한반복게임과 달리 반복횟수가 아무리 많아지더라도 협조체제 달성이 불가능하기 때문에, 유일한 내쉬균형을 갖는 일회게임은 아무리 많은 게임이 반복되더라도 경기자들은 매 단계마다 일회게임의 내쉬균형을 선택하게 된다.

여기서 우리가 주목해야할 점은 이반과 시퀀서의 검증게임을 어떠한 범주에서 바라보아야 하는가이다. 반복횟수가 무한할것인지 혹은 유한할것인지에 대해 논의하기 전에 앞서 한가지 질문에 대해 생각해보자.

만약 롤업 체인을 운영하는 시퀀서가 고의여부와 관계없이 트랜잭션을 올바르게 처리하지 않았다면 시퀀서와 이반(이반을 다수의 검증자들로 치환해도 좋다)은 어떻게 되는가?

먼저, 시퀀서의 부정행위가 DTD(Dispute Time Delay)내에 검증되었다고 가정해보자. 이 때 시퀀서는 자신의 보증금의 전부 혹은 일부를 몰수당할것이고, 일체의 시퀀서 권한을 박탈당할 것이다. 반대로 이반은 시퀀서의 보증금의 일부를 보상으로 받게 된다. 그리고 이후의 검증게임은 어떻게 되는가? 종료된다!

이번에는 시퀀서의 부정행위가 DTD이후에 ‘발견’되었다고 가정해보자. 이미 시퀀서에게 속고 빠른 출금을 제공해준 이반은 DTD가 지나서 시퀀서가 자신에게 준 토큰을 확인하지만 이내 그것이 올바르지 않은 값임을 발견할 것이다. 이 때, 시퀀서와 이반에게는 어떤 일들이 일어나는가? 먼저 이반은 이미 레이어 1에서 자신의 토큰을 빼앗긴 후이고, 이는 DTD이내에 검증되지 않았으므로 어떠한 보상도 받을 수 없게 된다. 반대로 시퀀서는 어떻게 되는가? 각 롤업의 사전에 정해진 규칙에 따라 상이할 수 있지만, 비록 DTD이내에 검증이 되지 않아 보증금을 몰수하지 못하고 기존의 상태값 또한 변경이 불가능 해도, 적어도 사후에 시퀀서의 역할 자체는 정지될 것이다. 즉, 이 경우에도 역시 이후의 검증게임은 종료되는 것이다.

여러분은 점원이 횡령을 했다는 것을 오랜 시간이 지난 후에 발견했다면, 이후의 가게 운영을 계속해서 맡기겠는가? 여러분이 천사가 아니라면 당연히 점원을 해고할 것이다. 이미 오랜 시간이 흘러 도둑질에 대한 금전적 책임은 물을 수 없더라도 말이다.

여기서 우리는 시퀀서가 공격을 하는 순간 검증자의 검증 여부와 관계없이 반복되는 검증게임은 종료된다는 것을 알 수 있다. 이를 통해 우리는 검증게임이 무한히 반복될 것이라고 가정하기보다 반복횟수는 사전에 정확히 알 수 없지만 유한한 횟수로 반복될 것이라고 가정하는 것이 보다 합리적이라는 것을 알 수 있다.

따라서 이반과 시퀀서의 검증게임은 무한반복게임이 아닌 유한반복게임이라고 정의하는 것이 보다 합리적이고, 따라서 일회게임에서의 균형이 매 단계마다 반복될 것임을 알 수 있다.

Related Research

앞서 검증자의 딜레마가 근래에 새롭게 제기된 문제가 아니라 이미 다양한 분야에서 제기되고 있는 문제중 하나라는 점을 지적했다. 때문에 이를 해결하려는 연구들 또한 이미 진행되어 왔다.

이 장에서는 다른 다양한 플랫폼에서 검증자의 딜레마를 해결하기 위해 제시한 솔루션들을 다룬다.

Forced Error & Jackpot — Truebit

먼저 잭팟에 대해 자세히 설명하기 전에 트루빗(Truebit)이 무엇인지 간단하게 알아보자. 트루빗은 일종의 오프체인 연산 솔루션으로, 이더리움의 낮은 블록 가스 리밋 제한으로 인해 실행이 불가능한 복잡도가 높은 트랜잭션을 오프체인에서 실행한 후 결과만을 온체인에 기록하는 방식으로 작동한다.

트루빗 프로토콜을 구성하는 구성원은 크게 3가지 타입으로 분류되며, 각 구성원이 수행하는 역할과 책임은 다음과 같다.

1. 의뢰인(Task Giver)

해결자에게 복잡한 트랜잭션에 대한 연산을 의뢰한다.
의뢰시 소정의 수수료를 해결자에게 지급한다.

2. 해결자(Solver)

의뢰인의 작업을 오프체인에서 수행한다.
일정 금액의 보증금을 미리 예치한다.
작업을 올바르지 않게 수행했음이 증명되면 보증금을 몰수당한다.

3. 검증자(Verifier)

해결자의 작업이 올바르게 수행되었는지 검증한다.
문제가 발견되었을 경우 일정 금액을 예치하고 검증게임(Verification Game)을 요청하여 해결자의 연산이 틀렸음을 증명한다.
검증게임에서 승리시 해결자의 보증금을 상금으로 받는다.

여기서 단번에 파악할 수 있는 것은 트루빗 프로토콜이 안전하게 작동하기 위해서는 바로 검증자의 역할이 매우 중요하다는 것이다. 검증자가 해결자의 작업이 올바르게 수행되었는지 제대로 검증하지 않는다면 해결자가 오프체인에서 올바르게 연산한 결과만을 온체인에 제출했는지 확신할 수 없기 때문이다. 따라서 우리가 주목해야 할 것은 트루빗에서 검증자는 항상 검증을 수행할 용의가 있는가일 것이다.

눈치가 빠른 독자들은 트루빗 프로토콜의 검증자의 검증 및 비검증 효용은 앞서 논의한 Super-Simple Game의 그것과 비슷한 구조일 것이라 생각했을 것이다. 이는 실제로 그러하다. 트루빗의 검증 및 비검증 효용을 자세히 살펴보자.

만약 해결자가 올바르지 않은 연산 결과를 제출할 확률이 X라면, 검증자의 기대 보수는 다음과 같이 나타낼 수 있다.

검증 기대 보수: R*X-C
비검증 기대 보수: 0 (여기서 검증자는 해결자를 검증하는데 실패하더라도 어떠한 명시적 페널티도 없다)

이러한 모델에서 검증자의 검증에 대한 유인을 확실하게 보장하기 어렵다는것은 이제 너무나 자명한 사실이다. 물론, 트루빗 프로토콜의 설계자들 또한 이를 정확하게 인지하고 있었다. 이를 해결하기 위해 트루빗은 강제 오류(Forced Error)와 잭팟(Jackpot)을 도입하였다.

트루빗에서 검증자의 딜레마의 가장 큰 원인은 역시 검증자의 보상이 해결자의 공격 확률에 의존하기 때문이다. 이를 해결하는 것이 바로 강제 오류인데, 강제 오류는 해결자의 공격 여부와 관계없이 시스템에 의해 고의적으로 랜덤하게 발생되는 오류를 말한다. 즉, 해결자가 공격을 하지 않더라도 랜덤하게 강제 오류가 발생하므로, 검증자는 이를 검증하여 보상을 받을 수 있게 된다.

강제 오류에 대한 검증 보상은 해결자의 보증금을 이용할 수 없기 때문에 새롭게 보상금을 조달할 필요가 생긴다. 이것이 바로 잭팟이다. 의뢰인은 작업을 요청할 때마다 해결자에게 지급하는 수수료 외에 별도로 세금(Tax)를 지불하는데, 이 세금이 잭팟 보상금의 원천이 된다.

요컨대, 사용자에게서 소정의 수수료를 추가로 받아 보상풀을 형성하고, 이 보상금을 랜덤하게 발생한 강제 오류를 성공적으로 검증한 검증자에게 분배하는 것이다.

잭팟 보상은 정해진 기간 내에 강제 오류를 검증한 검증자 누구에게나 주어진다. 단, 수 많은 복제된 검증자 계정을 동원하여 잭팟 보상을 받는 시빌 공격(Sybil Attack)이 가능하므로, 트루빗은 보상의 분배를 강제 오류를 검증한 계정의 수에 비례하여 지수적으로 감소하도록 설계하였다. 정확한 잭팟 보상 분배 금액은 다음과 같이 계산된다.

J/2^(k-1) (k = 강제 오류를 검증한 검증자 계정의 수)

트루빗의 검증자는 잭팟으로 인한 기대보수가 검증비용보다 높다면 항상 검증을 할 유인이 있다고 볼 수 있다. 다시 말해, 강제 오류가 발생할 확률이 P라고 한다면, P*J/2^(k-1) > C 일 때 트루빗의 검증자는 항상 검증을 할 유인이 있는 것이다. P와 J의 변수값은 해결자의 공격 확률과 달리 시스템적으로 통제 가능한 변수이므로, 검증자들로 하여금 항상 검증을 할 유인이 있도록 유도할 수 있을 것이다.

잭팟 모델은 이러한 장점이 있지만, 반대로 다음과 같은 이슈 또한 존재한다.

보상의 예측 불가능성
사용자에 추가적인 수수료 부과

첫번째 이슈는 강제 오류의 발생 여부는 오직 확률적으로만 예측이 가능하다는 점이다. 운이 따른다면 단 한번의 검증만으로 보상을 받을수도 있고, 수백번의 검증후에도 보상을 받지 못할수도 있다. 기댓값은 예상이 가능하지만 잭팟은 일종의 복권과 같기 때문에 검증자의 꾸준한 참여를 이끌어내기에는 부적합한 측면이 있다. 이에 대한 자세한 내용은 Decon에서 작성한 글을 참고하라.

이와 더불어 강제 오류의 발생 여부는 구조상 특정 해결자가 가장 먼저 이 사실을 알게 된다. 이는 해당 해결자에게 강제 오류에 대한 배타적인 정보를 먼저 제공하므로, 해결자는 이를 활용하여 일체의 검증 행위 없이 잭팟 보상을 차지할 수 있다.

둘째로, 잭팟 모델이 의도한대로 동작하기 위해서는 무엇보다 잭팟 보상금의 확보가 필수적이다. 잭팟 보상금이 충분히 크지 않다면 검증자에게 적절한 인센티브를 제공할 수 없게 된다. 하지만 잭팟 보상금은 작업 의뢰인이 모두 부담하게 되므로, 보상금의 크기를 늘리기 위해서는 필연적으로 의뢰인에게 추가적인 수수료가 부담되어야 한다는 것을 의미한다.

Application to Rollup

잭팟 모델은 여러 이슈가 존재하지만, 강제 오류와 잭팟 보상을 통해 검증자에게 검증 보상에 대한 기댓값을 검증 비용보다 높게 설정하여 검증 유인을 높일 수 있다는 측면에서 여전히 그 가치가 있다.

하지만 이를 롤업의 검증자의 딜레마를 해결하기 위해 활용하는것은 쉽지 않다. 그 이유는 첫째, 잭팟 보상금 기금 구성이 쉽지 않고, 둘째, 롤업은 강제 오류를 발생시키기에 적합한 구조는 아니라는 것이다.

먼저 잭팟 보상금 기금을 구성하기 위해서는 추가적인 재원이 필요한데, 이를 롤업의 사용자에게 추가적으로 부담하는것은 무리가 있다. 이에 대한 대안으로 해당 롤업의 생태계 차원에서 발행되는 별도의 토큰 보상을 지급할 수 있다. 하지만 모든 롤업이 이러한 토큰을 발행할 수는 없을 뿐더러, 잭팟 보상금이 해당 생태계에서 발행되는 토큰의 가치에 온전히 의존하기 때문에 안전성 측면에서 추가적인 위험이 발생할 수 있다.

또한 롤업은 강제 오류를 발생시키기 매우 어려운 구조를 갖고 있다. 트루빗에서는 강제 오류를 위해 작업을 수행한 후 올바른 솔루션과 잘못된 솔루션을 모두 제출한다. 만약 강제 오류가 발생되어야 하는 상황이면 잘못된 솔루션을 지정한 후 강제 오류였음을 밝히게 되고, 반대의 경우 올바른 솔루션을 지정하게 된다. 트루빗은 각 의뢰인의 의뢰하는 작업들이 독립된 고유한 작업들이기 때문에 이러한 방식으로 강제오류를 유도하는 것이 크게 문제가 되지 않는다.

하지만 롤업에서 강제 오류를 발생시킨다면, 올바르지 않은 상태값을 기준으로 이후의 트랜잭션들을 처리해야 한다. 그렇지 않은 경우 누구나 강제 오류가 발생했다는 것을 쉽게 감지할 수 있기 때문이다. 또한 이러한 방식으로 트랜잭션을 처리한다고 하더라도 이는 이미 강제 오류가 발생한 상태를 기준으로 진행된 것이기 때문에 이후의 모든 상태값 또한 유효하지 않은 값이 된다. 요컨대, 롤업은 강제 오류를 발생시키기에 매우 까다로운 구조를 갖고 있는 것이다.

Multiple Solvers — Truebit

트루빗의 다중 해결자 모델은 앞서 제시된 잭팟 모델의 여러 단점을 해결하고, 검증자의 딜레마를 완전히 해소하기 위해 새롭게 제시한 방법이다. 기존 트루빗이 3개의 역할군, 의뢰인, 해결자, 검증자가 명확하게 구분되어 있었다면, 다중 해결자 모델에서는 오직 의뢰인과 해결자만이 존재한다. 단, 하나의 해결자가 아닌 다수의 해결자를 두어 소수의 특정 해결자에 의해 안전성이 위협받는것을 방지한다.

다중 해결자 모델에서는 의뢰인이 작업을 의뢰하면, 해결자 풀(Pool)에서 랜덤하게 선택된 다수의 해결자가 해당 작업에 배정된다. 각 해결자는 작업에 대한 솔루션과 독립 실행 증명(Proof of Independent Execution)을 제출한다. 독립 실행 증명은 말 그대로 각 해결자가 스스로 작업을 해결했는지를 증명하는 과정이다. 독립 실행 증명이 구체적으로 어떻게 구성되는지는 여기서 확인하라. 이를 통해 각 해결자는 다른 해결자의 솔루션을 복제하지 않았음을 증명할 수 있다.

작업에 배정된 모든 해결자들은 스스로 작업을 수행하고 이에 대한 올바른 솔루션을 제출하지 않으면, 다른 해결자나 외부의 검증자(작업에 배정된 해결자가 아니더라도 여전히 누구나 검증은 수행할 수 있다)에 의해 챌린지 되어 자신의 예치금을 몰수당할 수 있다.

단, 각 해결자들은 작업을 올바르게 수행한다면 이에 대한 보상으로 수수료를 받을 수 있고, 이 수수료가 검증 비용보다 높다면 해결자들은 항상 작업을 올바르게 수행할 유인이 있다고 할 수 있다. 즉, 다중 해결자 모델은 검증 작업과 작업을 해결하는 과정이 본질적으로 다르지 않다는 것을 파악하고, 이에 대한 보상을 명시적으로 주어 검증자의 딜레마를 해소한다.

하지만 다중 해결자는 한가지 치명적인 단점이 존재하는데, 바로 많은 비용을 필요로 한다는 것이다. 다중 해결자 모델은 각 작업에 배정되는 해결자의 수가 많으면 많을수록 더 높은 수준의 안전성을 보장할 수 있게 된다. 이는 곧 해결자에게 지불하는 수수료가 필연적으로 높아질 수 밖에 없음을 의미한다.

때문에 트루빗은 의뢰인이 원하는 안전성 수준에 따라 수수료를 지불할 수 있도록 한다. 더 높은 수준의 안전성을 원한다면 수수료를 많이 지불하여 더 많은 해결자들이 작업을 수행하도록 할 수 있고, 그렇지 않은 경우 수수료를 최소한으로 지불하여 소수의 해결자들이 작업을 수행하도록 할 수 있다.

Application to Rollup

다중 해결자 모델의 핵심은 해결자와 검증자를 별도로 분리하지 않고, 이를 하나로 통합하고 작업을 해결(검증)한 행위에 직접적으로 보상을 주는것에 있다. 즉, 롤업에서 이와 유사한 방식을 적용하려면 시퀀서와 검증자를 별도로 분리하는게 아니라 특정 트랜잭션을 처리할 때 하나의 시퀀서가 아니라 다수의 시퀀서가 각자 독립적으로 이를 실행한 후 이에 대한 상태 결과값을 레이어 1에 제출하도록 해야 한다.

중요한 점은 롤업을 가능한 안전하게 유지하기 위해 다수의 시퀀서에게 적절한 보상을 주어야 한다는 것인데, 이는 크게 사용자에게 추가적인 수수료를 받거나 생태계에서 발행되는 토큰 보상으로 방식으로 해결할 수 있다. 다만, 높은 수준의 안전성을 위해서는 더 많은 수수료와 더 많은 토큰 보상이 필요하므로 적절한 수준의 안전성과 비용 기준을 구체적으로 마련할 필요가 있다.

더불어, 기존의 롤업의 경우 레이어 1에 필요한 상호작용이 트랜잭션 데이터를 공유하는 행위와 트랜잭션을 처리한 후의 상태값을 저장하는 행위로 제한되었지만, 다중 시퀀서 모델을 도입할 경우 시퀀서의 수에 비례하여 상태값을 저장하는 행위와 독립 실행 증명에 필요한 트랜잭션 수가 선형적으로 증가한다. 이는 롤업의 본래 목적인 레이어 1의 확장성을 높이는 목적과 상충할 수 있다는 점에 유의해야 한다.

Attention Challenge — Arbitrum

주의 챌린지(Attention Challenge)는 검증자에게 올바르게 검증 작업을 수행하지 않았을 경우 이를 처벌하여 검증자의 딜레마를 해결하고자 한다. 주의 챌린지의 핵심은 검증자에게 추가적인 보상을 주어 검증을 독려하는 것이 아니라, 검증을 하지 않았을 경우 검증자에게 중대한 손실을 입혀 검증을 할 수 밖에 없도록 만드는 것이다.

주의 챌린지가 구체적으로 어떻게 작동하는지 알아보기 위해 앞서 다룬 Super-Simple Model로 돌아가보자. 이 단순한 모델에서는 두 참가자인 주장자, 검증자가 존재했다. 이 때 주장자가 어떠한 값 f(x)를 연산한다고 할 때, 이 값을 그대로 제출하지 않고 오직 x와 암호화된 f(x)만을 제출한다. 이 때 검증자는 x를 확인하고 올바른 f(x)값을 반드시 제출하여야 한다. 만약 검증자가 올바르지 않은 값을 제출하거나 정해진 시간에 응답하지 않을 경우 자신의 보증금을 잃게 된다.

물론, 주의 챌린지에 응답하기 위해서는 온체인(on-chain) 트랜잭션이 필요하므로, 항상 검증자가 주의 챌린지에 응답해야 한다면 이는 레이어 1과 검증자에게 많은 부담이 될 것이다. 따라서, 주의 챌린지는 각 검증자에게 항상 적용되는 것이 아니라 확률적으로 적용된다. 단, 각 검증자가 주의 챌린지의 응답 대상이 되었는지는 오직 스스로 검증 작업을 수행한 후에만 확인할 수 있게 설계된다. 따라서 검증자들은 오프체인(off-chain)에서 f(x)를 연산하여 항상 검증작업을 수행하지만 오직 주의 챌린지의 대상이 되었을 경우에만 이러한 값들을 온체인에 제출하게 된다.

구체적으로 f(x)가 어떻게 암호화되는지, 각 검증자들이 어떻게 챌린지의 응답 대상이 되었는지 확인하는지에 대한 기술적인 사항들은 원 글을 참고하라.

Super-Simple Model에 주의 챌린지를 적용할 경우 검증자의 검증 및 비검증 기대 보수는 다음과 같이 변경된다.

검증 기대 보수: R*X-C
비검증 기대 보수: -L*X -P*A

P는 주의 챌린지의 응답 대상이 될 확률이고, A는 잘못된 응답을 제출했을 때 몰수되는 보증금을 의미한다.

이 때, P*A > C 이면 검증자는 주장자의 공격 확률인 X와 관계 없이 항상 검증을 하는것이 최선의 선택이 된다. P와 A에 대한 적절한 변수값은 시스템에 의해 통제될 수 있으므로, 검증자로 하여금 항상 검증을 하도록 유도할 수 있다.

주의 챌린지는 사용자에게 별도의 추가적인 비용을 발생시키지 않고, 검증자로 하여금 항상 검증을 하도록 유도할 수 있다는 점에서 매우 매력적이다. 하지만 주의 챌린지에는 한가지 맹점이 존재하는데, 만약 검증자가 검증을 수행하면서 주장자가 어떠한 공격도 하지 않아 이에 대한 보상을 얻지 못할 경우, 모든 경우에 대해 손실을 볼 수 있다는 것이다.

예를 들어, 아래와 같은 조건에서 검증자의 기대 보수는 다음과 같이 나타낼 수 있다.

R = 100
L = 10
X = 0
C = 1
P*A = 5

검증 기대 보수 = -1
비검증 기대 보수 = -5

이 때, 검증자는 검증 기대 보수(-1)가 비검증 기대 보수(-5)보다 더 크므로 검증을 하게 될 것이다. 하지만 여기에는 한가지 함정이 존재한다. 바로 어떠한 선택을 하더라도 검증자는 순수하게 손실만 입는다는 것이다! 즉, 검증자는 더 큰 손실을 피하기 위해 작은 손실을 감수하는 상황에 처하게 되는 것이다. 만약 검증자가 강제로 이러한 상황에 놓이게 된다면 별다른 방법이 없겠지만, 이를 시스템적으로 강제할수는 없을 것이다. 즉, 검증자가 원하면 검증자의 역할을 포기하고 보증금을 인출하여 이 시스템을 떠날 수 있다는 것이다.

만약 여러분이 이 검증자라면 어떤 선택을 하겠는가? 기약없는 수익을 기다리며 이 시스템에 남아 검증을 계속하겠는가? 또는 어차피 나에게 주어지는 보상은 아무것도 없고, 비용만 지출되니 검증자를 포기하고 떠나겠는가? 아마 모든 이들은 후자를 선택할 것이다.

이 예시를 통해 알 수 있는 것은 주의 챌린지는 검증자가 항상 비검증이 아닌 검증 전략을 선택하도록 유도할수는 있지만, 검증자가 계속해서 검증자의 역할을 지속적으로 수행하도록 유도하지는 못한다는 것이다.

그렇다면 주의 챌린지는 아무런 효용도 없는 장치인가? 그렇지 않다. 주의 챌린지는 검증자의 딜레마를 해결하는데 매우 효과적인 장치이다. 단, 주의 챌린지의 대상이 되는 검증자들이 검증 작업과 연관된 또는 연관되지 않은 일정한 수익을 얻을 수 있을때만 그 효과를 발휘한다.

예를 들어, 검증자가 검증 단위마다 일정한 수익 F를 얻는다면, F - C > -P*A 일 때, 검증자는 항상 검증 전략을 선택하고 더불어 검증자의 역할을 계속해서 수행하지 않을 이유를 찾기가 어려울 것이다. 우리는 이러한 조건이 적용될 수 있는 모델을 하나 알고 있다. 바로 롤업이다!

Application to Rollup

롤업에서는 검증자의 역할이 명확히 구분되지 않고, 여러 구성원들이 검증자의 역할을 겸하게 된다. 그리고 이러한 구성원 중 일부는 검증 단위인 트랜잭션마다 일정한 수익을 얻는다. 예를 들어, 롤업에서 이자 농사(Yield Farming)를 하고 있는 사용자나 DEX를 운영하는 개발자는 트랜잭션이 처리될 때마다 일정한 수익을 얻을 수 있다. 이러한 경우 주의 챌린지를 적용하면 이들 구성원이 확실하게 롤업을 검증할 수 있도록 유도할 수 있다. 이에 대한 자세한 내용은 이미 앞에서 다루었기 때문에 추가적인 설명은 생략하겠다.

Why do I care so much about Verifier’s Dilemma?

이 글은 지속적으로 롤업의 모든 구성원들에게 안전을 보장하기 위해서는 검증자의 딜레마를 반드시 고려해야하고, 이에 대한 적절한 해결책을 고려할 필요성이 있다고 주장하고 있다. 이에 대한 여러가지 근거를 앞에서 제시했지만, 여전히 이에 동의하지 않는 사람들이 있을 수 있다. 이는 어디까지나 이론적인 측면일 뿐, 실제로 롤업이 활발하게 도입되어 사용될 때, 막상 검증자의 딜레마가 크게 문제가 되지 않을 수 있기 때문이다. 세상에는 자신에게 아무런 이익이 되지 않아도 다른 이들을 도와주는 이타적인 사람들도 있고, 또한 자신의 이익을 극대화하기 보다 이익을 조금 포기하더라도 스스로와 다른 사람들을 위해 차선을 선택하는 이들도 있다. 롤업에서도 이와 비슷한 상황이 전개될수도 있다.

하지만 이 글에서 주장하고 싶은것은 롤업에서 검증자의 딜레마를 고려하지 않는다면 해당 롤업은 ‘반드시’ 위험에 빠지게 될 것이라는 것이 아니다. 다만, 이러한 측면을 사전에 주의 깊게 고려하지 않는다면 매우 낮은 확률이라도 예상치 못한 위기가 닥쳤을 때, 롤업의 안전성이 크게 위협받을 ‘가능성’이 있다는 것이다.

잠시 롤업이 아닌 다른 이야기를 해보자. 예를 들어, 우리가 현대화된 도시에 거주하는 시민을 위한 자동차를 설계한다고 해보자. 이 차는 아마도 잘 정비된 도시의 도로에서만 달리게 될 것이기 때문에, 굳이 어떠한 극한 환경에서도 잘 동작하도록 애를 쓸 필요는 없을 것이다. 4륜구동이 아니어도 될 것이고, 낙차가 높은 곳에서 떨어질 일도 없을 것이기 때문에 값비싼 충격 완화 장치를 추가할 필요도 없다. 사막을 달릴 일도 없을 것이기 때문에 모래 먼지를 고려할 필요도 없고, 폭설과 폭우에도 그렇게 많은 신경을 쓸 필요가 없다. 어차피 그런 일은 잘 일어나지도 않을 뿐더러 도로 또한 항상 잘 정비되어 있을 것이기 때문에 평범한 차도 무리 없이 잘 달릴 수 있을 것이다.

하지만 반대로, 어떤 종류의 극한 환경에서도 항상 문제 없이 잘 달릴 수 있는 차를 설계하고자 한다면 이야기는 완전히 달라진다. 만약 충분한 안전장치가 없다면 이러한 환경에서는 운전자와 승객의 생명을 크게 위협할 수도 있다. 때문에, 추가적인 비용이 발생하고 설계가 다소 복잡해지더라도 가능한 차를 안전하게 설계하는것이 최우선사항이다. 이렇게 설계된 차 또한 물론 대부분의 주행이 도시 환경에서 이루어질 수도 있다. 이런 상황에서는 이 차에 들어간 여러 비용과 설비가 다소 불필요하고 과하게 느껴질 수도 있다. 하지만 이 차는 극한 환경에 처했을 때 그 진가를 발휘할 것이다. 갑자기 폭설이 쏟아져 다른 모든 평범한 차들은 한 치도 움직일 수 없을 때, 이 차는 홀로 문제 없이 잘 달릴 것이다.

다시 롤업과 블록체인의 이야기로 돌아와서, 여러분은 이 두가지 종류의 차 중에 어떤 것이 롤업에 가깝다고 생각하는가? 나는 블록체인을 믿는 사람이라면 누구나 롤업, 아니 나아가 모든 블록체인 기술은 후자의 성격에 더 가깝다는것에 동의할 것이라 믿는다. 블록체인 기술은 탈중앙화를 통해 시스템이 처할 수 있는 모든 극한 환경을 극복(장애 허용, 공격 저항, 담합 저항)하고자 한다. 비록 그것이 매우 드물게 발생하는 상황일지라도 말이다. 롤업 또한 마찬가지다. 롤업은 극한 상황에 대한 대처 능력을 레이어 1과 동일한 수준에 가깝게 구현하되, 레이어 1의 부족한 확장성을 대폭 증가시키기 위한 기술이다. 따라서 우리는 롤업이 이러한 목적대로 모든 극한 환경을 잘 극복할 수 있도록 노력할 필요가 있다.

Conclusion

옵티미스틱 롤업은 당면한 이더리움의 확장성 문제를 중단기적으로, 또한 장기적으로도 획기적으로 해결할 수 있을 것으로 기대되는 레이어 2 솔루션이다. 물론, 현재까지 많은 레이어 2 솔루션이 제시되었고, 특히 유효성 증명(Validity Proof)을 활용하는 zk-롤업(zk-Rollup)은 옵티미스틱 롤업과 다르게 즉시 완결성(Finality)을 부여할 수 있다는 측면에서 각광을 받고 있다. 하지만, 이더리움의 모든 복잡한 트랜잭션들을 zk-롤업으로 처리하기에는 현 시점에서 분명한 한계가 존재하기 때문에, 당분간 이더리움을 위한 현실적인 주요 대안은 옵티미스틱 롤업이 될 것이다.

앞으로 옵티미스틱 롤업은 매우 광범위하게 활용될 것이고, 매우 대중화(Mass Adoption)될 것이다. 롤업의 수가 많아지고, 그 규모가 커질수록 안전성에 대한 이슈는 더욱 더 중요해질 것이다. 계속해서 강조하지만, 롤업은 단 한명의 정직한 검증자만 존재해도 시스템이 안전하게 유지될 수 있다는 점에서 매우 매력적인 레이어 2이다.

하지만 이 글에서 계속해서 논의한 바와 같이, 롤업에서 검증자는 시퀀서의 공격확률이 높지 않다면 검증을 할 유인보다는 그렇지 않을 유인이 더 크다. 때문에 롤업이 안전하게 동작하는 시간이 늘어날수록 활성화된 검증자의 수는 빠르게 줄어들 것이다. 빠른 출금 및 크로스 롤업 트랜잭션의 중개인들 또한 완전한 예외는 아니다. 요컨대, 롤업은 역설적으로 안전해질수록 위험해질것이다. 하지만 우리는 한가지 대안을 알고 있다. 바로 주의 챌린지를 적절하게 적용하는 것이다. 주의 챌린지를 적용할 경우 우리는 롤업의 안전성을 확실하게 보장할 수 있다.

물론, 이 글은 모든 롤업에 주의 챌린지를 반드시 적용해야 한다고 주장하는 것은 아니다. 각 롤업마다 목표로 하는 수준의 안전성이 있을 것이고, 참가자들의 성향에 대한 가정이 있을 것이다. 만약 높은 안전성을 보장하지 않아도 되거나, 이타주의자, 위험을 극도로 회피하는 참가자들의 비율이 충분히 높다고 판단된다면 굳이 주의 챌린지를 적용할 필요는 없다. 중요한것은 각자의 목적에 맞게 필요한 도구를 적절하게 사용하는 것이다. 이 글이 각 롤업의 안전성을 설계할 때 조금이나마 도움이 되었으면 한다.

Glossary

시퀀서: 옵티미스틱 롤업에서 사용자들의 트랜잭션 순서를 결정하고, 해당 트랜잭션들을 처리한 후의 상태값과 트랜잭션 데이터를 레이어 1에 제출하는 역할을 수행한다. 다른 이름으로 오퍼레이터(Operator)라고 부른다.
검증(verify): 다른 참가자가 수행한 연산 결과를 검증하는 행위를 의미한다. 옵티미스틱 롤업에서는 시퀀서가 제출한 상태값이 올바른지 검증하는 행위를 의미한다.
검증자(Verifier): 검증을 수행하는 자이다. 옵티미스틱 롤업에서는 모든 참가자가 검증자가 될 수 있다.
DTD(dispute time delay): 위조 증명 시스템에서 한 결과값이 확정되기 위해 필요한 기간을 말한다.
위조 증명(Fraud Proof): 어떠한 연산을 실행한 결과가 우선 올바르다고 가정한 후, 일정 기간 동안 해당 결과값이 올바른지 검증할 수 있는 기회를 주는 일련의 시스템을 의미한다.
유효성 증명(Validity Proof): 어떠한 연산을 실행한 결과값이 올바르게 구성되었음을 증명하는 시스템을 의미한다. 유효성 증명에는 어떠한 DTD도 요구되지 않는다.
공격(attack): 일반적으로 올바르지 않은 상태나 결과값을 레이어 1에 제출하여 경제적 이익을 취하는 것을 의미한다. 옵티미스틱 롤업에서는 시퀀서가 올바르지 않은 상태값을 제출 및 확정을 유도하여 사용자들의 자산을 탈취할 수 있다.
챌린지(challenge): 위조 증명을 이용하여 올바르지 않은 상태나 결과값을 올바른 것으로 변경하기 위한 일련의 장치를 의미한다. 옵티미스틱 롤업에서는 검증자가 챌린지를 신청하여 시퀀서가 제출한 상태값이 올바르지 않음을 증명할 수 있다.

Optimistic Rollup is Not Secure Enough Than You Think — Game Theoretic Approach for More Verifiable Rollup[KR]

Intro

Verifier’s Dilemma

Super-Simple Model

Super-Simple Model in Optimistic Rollup

Multiple Verifiers

There is No Verifier’s Dilemma in Optimistic Rollup?

Token Holder

Dapp Builder

Altruist

Fast Withdrawal

Fast Withdrawal and Auditing Incentives

Attack-Verify Game

Mixed Strategy Nash Equilibrium

Maximin Strategy

Fast Withdrawal With Attention Challenge

Cross-Rollup Transaction

Trade-Off of Attention Challenge

Additional Reward to Attention Challenge

Repeated Game

Related Research

Forced Error & Jackpot — Truebit

Application to Rollup

Multiple Solvers — Truebit

Application to Rollup

Attention Challenge — Arbitrum

Application to Rollup

Why do I care so much about Verifier’s Dilemma?

Conclusion

Glossary

References

Written by Aiden Park