# A proposal for Data availability Solution of Plasma EVM(KR) Carl Park(carl.p@onther.io) Aiden Park(aiden.p@onther.io) *Kevin Jeong(kevin.j@onther.io, corresponding) :::info [English Version Link](https://hackmd.io/s/ByeGtM5D7) ::: ## Abstract 본 글에서는 [Plasma EVM](https://hackmd.io/s/HyZ2ms8EX) 에서 가장 문제가 되었던 Data availability(이하 DA)를 해결하기 위한 모델을 제안한다. 이 모델에서는 DA 문제에 대한 판단을 전적으로 유저 개인에게 맡김과 동시에 유사시에 유저들의 유효한 Exit을 보장하기 위한 장치인 **User Request Block**을 새롭게 두었다. 또한 DA문제를 가장한 악의적인 사용자들의 DoS공격을 방지하기 위해 **동적 수수료 모델**을 도입하였다. <br> ## What were the problems? 기존 모델의 문제점은 크게 두가지로 나누어 볼 수 있다. 첫째는 Confirmation 과정에서 Sybil Attack의 형태를 활용한 손쉬운 DoS공격이 가능하다는 것이다. 둘째는 Confirmation 모델 자체가 DA를 완전히 해결하지 못한다는 점이다. 먼저 첫번째 문제부터 자세히 살펴보자. Confirmation 과정을 두어 해당 블록의 모든 Transactor들의 confirm서명을 모아 블록의 해시와 함께 제출하게 하여 DA 문제를 사전에 해결하는 것이 본래 목적이었다. 하지만 이는 단 한명의 Transactor라도 Confirm을 거부하거나 제 시간에 응답하지 못하는 경우 해당 트랜잭션을 제외한 새로운 블록에 대해 다시 Confirm과정을 거쳐야하는 이슈가 있었다. 예를 들어 공격자가 n개의 어카운트를 동원해 트랜잭션을 발생시킨 후에 n개 중 단 하나의 어카운트만을 이용해 Confirm을 차례차례 거부하게 된다면 n번의 Confirm과정을 거치게 하여 해당 기간 동안 블록이 커밋되는 것을 동안 막을 수 있게 된다. 두번째 문제는 'Confirmation 모델이 DA문제를 해결하지 못한다'는 심각한 결함을 안고 있다는 것을 의미한다. 이는 전체 사용자들이 아닌, 해당 블록에 포함된 트랜잭션을 보낸 사용자들에게만 Confirm을 받기 때문에 발생하는 문제이다. 즉, 트랜잭션을 보내지 않은 사용자들은 Confirmation 과정에서 생략되기 때문에, 오퍼레이터가 Data withholding을 하더라도 해당 사용자들은 이를 방어할 수 있는 방법이 없다. 예를 들어 차일드 체인에 오퍼레이터 O, 사용자 A, 사용자 B가 있다고 해보자. 현재 차일드 블록 #1 에는 사용자 A가 보낸 트랜잭션만 포함된 상태이다. 이 때 A와 O가 담합을 하여 O가 유효하지 않은 블록 #1을 생성하고 이를 루트체인에 제출하려고 한다. 이를 위해 필요한 것은 오직 A의 Confirm 서명 뿐이다. 따라서 이 과정에서 B는 블록 데이터를 전달받지 못하게 되더라도 대처할 수 있는 방법이 없다. 기존 모델은 이러한 문제로 인해 사용자들의 자산에 대한 안전을 보장해주지 못하였다. <br> ## New Exit model : User Request Block ### Glossary * **비요청 블록(Non-Request Block;$NRB$)** : 플라즈마 EVM의 비요청블록과 같다. * **유저 요청 블록(User Request Block;$URB$)** : 사용자에 의해 제출되는 요청 블록(Request Block). 기존의 요청 블록과 달리 본인 혹은 다른 사용자의 탈출 요청(Exit Request for URB) 트랜잭션만 포함된 블록이다. * **오퍼레이터 요청 블록(Operator Request Block;$ORB$)** : 오퍼레이터에 의해 제출된 요청 블록. 플라즈마 EVM의 요청 블록과 같다. * **오퍼레이터를 통한 탈출 요청(Exit Request for ORB;$ERO$)** : 오퍼레이터 요청 블록($ORB$)을 통한 탈출 요청 트랜잭션 * **유저에 의한 탈출 요청(Exit Request for URB;$ERU$)** : 유저 요청 블록($URB$)을 통한 탈출 요청 트랜잭션 * **연산 챌린지 기간($CP_{computation}$)** : 요청 블록(Request Block)의 연산 챌린지를 위한 기간 * **인질 챌린지 기간($CP_{withholding}$)** : 비요청 블록(Non-Request Block)의 인질 챌린지(withholding challenge)를 위한 기간 * **확정(Finalized)** : 요청블록은 연산 챌린지 기간($CP_{computation}$) 이후 확정된(finalized) 상태가 되며, 비요청블록(Non-Request Block)은 인질 챌린지 기간($CP_{withholding}$) 이후 확정된(finalized) 상태가 된다. * **재정렬(Rebase)** : 가장 최근의 확정된 블록을 기준으로 유저 요청 블록($URB$)이 제출될 경우 확정(finalized)되지 않은 모든 플라즈마 블록들은 해당 유저 요청 블록($URB$)의 뒤에 위치하게 되며 유저 요청 블록($URB$)과 상충되는 트랜잭션은 되돌려지게(revert)된다. 이를 재정렬(Rebase)이라 한다. * **유저 요청 블록 비용($C_{URB}$)** : 만들어진 유저 요청 블록($URB$)을 루트체인에 제출(Commit)하는데 제출자(Commiter)에게 부과되는 비용 * **유저 탈출 요청 비용($C_{ERU}$)** : 유저에 의한 탈출 요청($ERU$)이 블록에 포함되어 제출(Commit)될때 각 유저가 부담하는 비용 * **유저 탈출 요청 수($N_{ERU}$)** : 유저 요청 블록($URB$)에 포함된 유저 탈출 요청 트랜잭션($ERU$)의 수 * **총 유저 요청 블록 비용(Total Cost for User Request Block; $C_{URB}^{total}$)** : 유저 요청 블록을 루트체인에 제출(Commit)할 때 발생하는 총 비용. $C_{URB}^{total}$ = $C_{URB}$ + $N_{ERU}$*$C_{ERU}$로 계산된다. ___ <br> 새로운 모델에서는 Confirmation이 완전히 사라지고 해당 블록의 DA에 문제가 없는지에 대한 판단을 블록의 마이닝, 제출, 커밋 과정에서 일체 판단하지 않는다. DA문제에 대한 판단은 사용자 개인의 판단에 맡기게 되며, 문제상황이라고 판단되는 사용자들은 가장 최근의 finalized 블록을 기준으로 자신과 다른 사용자의 ERU가 포함된 URB를 커밋하는 것을 통해 안전하게 exit이 가능하다. URB가 커밋되면 오퍼레이터는 finalized되지 않은 차일드 블록들을 URB의 내용을 반영하여 새롭게 Rebase한다. 사용자의 입장에서 별다른 문제가 없다고 판단될 경우에는 ERU가 아닌 ERO를 이용하여 이전 모델과 같이 오퍼레이터가 다음 request block에 자신의 exit request를 반영하는 것을 기다릴 수 있다. 그림을 통해 더 자세히 살펴보도록 하자. ![](https://i.imgur.com/2NX714c.png) 현재 Block#1 이 finalized 된 상태이고, 루트체인에는 NRB#5까지 제출된 상태이다. ORB는 블록이 제출된 시간으로부터 $CP_{computation}$이 지나야 finalized가 되며, NRB 역시 블록이 제출된 시간으로부터 $CP_{withholding}$이 지나야 finalized된다. 현재 $CP_{computation}$은 1시간, $CP_{withholding}$은 1일로 가정한 상태이다. ![](https://i.imgur.com/5bllVTn.png) ORB#4 의 챌린지 기간 $CP_{computation}$ 이 NRB#3의 챌린지 기간보다 짧기 때문에, 문제가 없는 상황에서 ORB#4는 NRB#3보다 일찍 finalized 될 것이다. 따라서 ORB#4가 finalized되는 순간 NRB#3도 finalized 된다. 즉, 문제가 없을 경우 NRB의 챌린지 기간인 $CP_{withholding}$ 은 다음 ORB 생성 시간 + $CP_{computation}$이다. ![](https://i.imgur.com/OzCwqMX.png) 이번에는 NRB#3가 withhold 된 상태라고 하자. 물론 실제로 withhold되었는지는 누구도 증명할 수 없다. 다만 withholding이 발생했다고 판단되는 사용자들은 누구든지 ERU를 제출할 수 있으며, URB를 제출하는 것을 통해 차일드체인에서 안전하게 exit할 수 있다. 여기서 사용자는 자신의 exit request와 다른 사용자의 ERU를 반영하는 트랜잭션이 포함된 URB#2를 가장 최근의 finalized된 블록인 Block#1을 근거로 하여 제출한다. 이 과정에서 사용자는 이전에 제출된 모든 ORB의 requests를 반영하여야 한다. 단, 새롭게 제출된 ERO는 반영하지 않아야 한다. ![](https://i.imgur.com/5mgithJ.png) URB의 제출은 일종의 사용자에 의한 fork를 의미한다. 즉 사용자는 data withholding이 있었다고 판단된다면, 스스로 포크를 하여 canonical chain을 변경할 수 있는 것이다. 따라서 오퍼레이터는 기존에 제출된 NRB를 URB#2를 기준으로 새롭게 마이닝하여 제출하는 Rebase과정을 거쳐야 한다. 이 때 제출된 NRB#3' 과 NRB#4'는 기존의 NRB#3과 NRB#5와 각각 동일한 $transactionRoot$를 가져야 한다. 즉, 이전의 NRB에 포함되었던 트랜잭션들을 그대로 반영해야 한다. 또한 NRB#3' 과 NRB#4' 는 사용자가 withholding문제가 있었다고 판단한 상황이기 때문에 챌린지 기간이 $CP_{withholding}$ 으로 새롭게 설정된다. <br> ## Fee model against Infinite loop attack ### Infinite loop attack 새로운 모델은 withholding에 대한 판단을 사용자 개인에게 맡기며, 문제상황시 URB를 제출하여 언제든지 안전하게 exit이 가능하게 하였다. 하지만 이 모델에는 치명적인 약점이 존재한다. **Rebase를 이용한 일종의 Infinite loop attack**이 그것으로, 악의적인 사용자는 Withholding의 여부와 관계 없이 지속적으로 URB를 커밋하여 이후의 차일드 블록들의 finalization을 막을 수 있다. URB가 제출되는 순간 이후의 NRB들은 Rebase되어 챌린지 기간이 새로 갱신되기 때문이다. 물론 오퍼레이터의 자원을 낭비시킬 수 있다는 측면도 있지만 가장 심각한 문제는 블록의 finalization을 막아 차일드 체인의 원활한 진행을 방해할 수 있다는 것이다. <br> ### Fee model 우리는 이러한 공격을 막기 위해 URB와 ERU에 대해 수수료를 부과하는 모델을 도입하였다. 수수료 모델의 설계목표는 다음과 같다. **1. URB의 제출이 공격의도일 확률에 가깝다면 수수료를 많이 부과해야 하고, 문제상황에 대한 탈출의 용도일 확률에 가깝다면 수수료는 낮게 책정되어야 한다. 2. Rebase를 발생시키는 URB의 커밋 횟수는 가능한 최소화 되어야 한다.** 거듭 강조하는 내용이지만 우리는 차일드 체인의 DA에 실제로 문제가 있었는지 없었는지를 판단할 수 없다. 따라서 우리는 첫번째 원칙에서 명시한 것처럼 DA문제에 대해 확률의 측면에서 접근해야 한다. URB는 차일드 체인에서 DA문제가 발생했을 경우 사용자들의 안전한 Exit을 위한 최후의 보루이기도 하지만, 만약 공격의 의도로 쓰인다면 차일드 체인의 작동을 심각하게 저해할 수 있는 강력한 무기이기도 하기 때문이다. 또한 설령 다수의 사용자들이 URB를 제출하는 상황, 즉 차일드 체인에 문제가 발생했다고 판단하는 사용자들이 많아지더라도 실제로는 차일드 체인에 문제가 없었을 가능성도 여전히 존재한다. 따라서 두번째 원칙에서 명시한 것처럼 항상 차일드 체인의 원활한 작동을 최대한 보장하기 위해 가급적 적은 횟수의 URB커밋을 통해 사용자들의 ERU를 효율적으로 처리할 수 있어야 한다. <br> ### DA probability 첫번째 원칙은 그 자체로서는 매우 타당한 규칙이지만, 결국 '확률'을 알아야만 적용이 가능하다는 한계가 있다. 이는 달리 말하면 확률을 얼마나 정확하게 계산할 수 있는지가 이 수수료 모델 설계의 key point라고 할 수 있다. 그 확률의 산정에 가장 적합한 재료가 무엇일까? 우리는 앞서 DA문제에 대한 판단을 사용자 개인에게 일임한다고 하였다. 독립적인 개인이 DA문제에 대해 스스로 판단을 한다면, DA문제의 발생확률과 가장 상관관계가 높은 것은 바로 사용자 개인의 판단일 것이다. 즉, DA문제가 있다고 판단하는 사용자들의 수가 많아질수록 DA가 발생했을 가능성 또한 높아지는 것이다. 반대로 DA문제가 있다고 판단하는 사용자들의 수가 적다면 그만큼 차일드 체인에 문제가 없었을 가능성이 크다. 따라서 우리는 DA 문제에 대한 사용자들의 판단, 즉 ERU의 수를 통해 DA문제 발생확률을 추측하고 그에 맞게 URB와 ERU에 대한 수수료를 조정하는 모델을 설계하고자 한다. 물론 ERU를 제출한 어카운트들이 모두 독립적인 개인일 것이라는 가정은 매우 naive하다. 그렇기 때문에 ERU에 대해서도 추가적인 수수료가 부과되어야 하는 것이다. 공격자가 많은 어카운트를 동원해 URB를 제출하기에 유리한 조건을 형성하기 위해서는 ERU에 대한 수수료도 모두 부담해야 할 것이기 때문에 이러한 공격방법은 그 효과를 잃을 것이다. <br> ### Cost function 위에서 제시한 원칙을 최대한 만족하기 위해서는 어떠한 형태의 비용함수를 도출해야 하는지에 대해 논의해보자. 첫번째 원칙을 만족시키기 위해서는 URB에 포함되는 ERU의 수가 많아질수록 URB의 제출비용이 감소하고, ERU에 대한 비용 또한 감소해야 한다. 또한 두번째 원칙을 만족시키기 위해서 ERU의 수가 증가함에 따라 감소하는 비용의 폭이 점점 증가하는 형태가 바람직 할 것이다. **$C_{URB}$ : URB를 제출하는데 소모되는 비용 $C_{ERU}$ : ERU를 통해 Exit하는데 소모되는 비용 $N_{ERU}$ : URB에 포함된 ERU의 수** 위와 같이 정의했을 때, 위에서 제시한 조건을 만족하는 비용함수를 간단하게 도출할 수 있을 것이다. **Cost of submitting the URB** ![](https://i.imgur.com/8IqQNLg.png) URB를 제출하는데 소모되는 비용은 위와 같다. URB에 포함된 ERU의 수, 즉 이 증가함에 따라 곡선의 기울기는 급격하게 감소한다. 또한 $N_{ERU}$가 기준점 S를 초과하면 더 이상 $C_{URB}$는 감소하지 않는다. 아래에서 다시 자세히 논의하겠지만, $C_{URB}$ 일정 수준이하로 감소하지 않게 설정한 이유는 공격자가 다수의 어카운트를 생성하여 일종의 sybil attack을 하는 경우도 고려해야 하기 때문이다. 여기서 $N_{ERU}$이 증가함에 따라 $C_{URB}$ 선형적으로 감소하지 않고, 굳이 곡선의 형태를 설정한 이유는 두번째 원칙을 최대한 만족시키기 위함이다. 비용곡선이 직선의 형태라면 $N_{ERU}$가 증가함에 따라 감소하는 한계비용이 일정하지만, 곡선의 형태라면 한계비용의 감소폭이 체증하는 형태가 된다. 따라서 URB를 커밋하는 입장에서는 가능하면 하나라도 더 ERU를 URB에 포함시키는 것이 유리해진다. 이는 결과적으로 소수의 URB만으로 효율적으로 ERU를 처리하는 것을 권장하게 되는 것이다. **Cost of ERU** ![](https://i.imgur.com/ZKt1sBU.png) ERU를 통해 Exit하는데 소모되는 비용은 위 그림과 같다. $C_{ERU}$또한 $N_{ERU}$가 증가할수록 감소하는 형태를 가진다. 여기서도 $C_{URB}$의 곡선과 마찬가지로 sybil attack 을 막기 위해 일정 수준 이하로 비용이 감소하는 것을 방지하고 있다. 사용자는 ERU를 제출하는 시기에 보증금의 형태로 $N_{ERU}$=0 일 때의 $C_{ERU}$를 deposit하게 된다. 이 보증금에서 URB가 제출될 때의 $N_{ERU}$를 기준으로 공제된 수수료를 제외한 나머지를 추후에 돌려받게 된다. <br> ### The importance of total cost 앞서 Cost function을 설명할 때 잠깐 언급했던 sybil attack에 대한 내용을 기억할 것이다. 공격자가 다수의 어카운트를 생성해서 ERU를 생성할 경우 $C_{URB}$, $C_{ERU}$가 너무 낮은 수준이 되면 공격비용이 지나치게 싸질 위험이 있다. 이를 막기 위해 비용이 일정 수준 이하로 감소하는 것을 방지하였는데, 사실 이는 이러한 공격루트를 완벽하게 막는 형태는 아니다. 편의상 $N_{ERU}$가 모두 공격자에 의해 생성되었다고 가정할 경우, 결국 공격자가 지불해야 할 Total cost는 $C_{URB} + C_{ERU}*N_{ERU}$ 가 될 것이다. 그렇다면 위에서 제시한 비용함수를 근거로 Total cost의 형태를 아래와 같이 간략하게 나타낼 수 있다. **Total cost function** ![](https://i.imgur.com/GfxWtPX.png) 위 곡선을 보면 $N_{ERU}$가 증가함에 따라 Total cost가 감소하는 모습을 보이고 있다. 이는$C_{URB}$와 $C_{ERU}$의 기울기가 모두 감소하는 형태이기 때문에 Total cost의 곡선 또한 기울기가 감소하는 형태가 될 수 밖에 없기 때문이다. 결국 공격자가 공격을 할 경우에는 $N_{ERU}$를 Total cost가 가장 낮아지는 지점까지 생성하게 될 것이다. 만약 그러한 경우에도 Total cost가 충분히 높은 상태라면 큰 문제가 되지 않을 수 있다. 하지만 $N_{ERU}$가 충분히 많은 상황에서도 Total cost를 높게 유지하는 것은 필연적으로 유저들의 exit에 대한 비용부담 또한 증가시키게 되는 문제가 있다. 가장 바람직한 형태는 현재의 비용함수를 변형하거나 혹은 다른 파라미터들을 추가하여 Total cost 곡선의 기울기는 양수로, $C_{URB}$ 와 $C_{ERU}$ 곡선의 기울기는 음수의 형태가 되는 것이다. 하지만 이는 현재 연구가 더 필요한 상황이다. <br> ### Various Cases 앞에서 구체적인 비용함수의 형태에 대해 논의했다면, 여기서는 다양한 케이스들을 가정하여 위 모델에 문제가 없는지 간단하게 살펴보도록 하자. 첫번째 케이스는 공격자가 사용자들을 선동하여 ERU를 제출하게 하는 경우이다. 이 경우 공격자는 차일드 체인의 풀노드가 아닌 사용자들을 대상으로 선동을 시도하게 될 것이다. 풀노드 사용자의 경우 스스로 DA에 대해 판단할 근거가 충분하기 때문이다. 하지만 풀노드가 아닌 사용자들을 대상으로 시도하는 선동 또한 쉽지 않을 가능성이 높다. 공격자는 withholding이 일어났다는 것을 증명하기가 어려운 반면, 정직한 풀노드 사용자들은 withholding이 없었다는 것을 증명하기가 쉽기 때문이다. 만약에 플라즈마 체인과 관련된 커뮤니티가 있다면 누군가 해당 블록 데이터를 업로드하고 이를 바탕으로 도출한 블록해시가 루트체인에 제출된 블록 해시가 같다는 것을 증명하면 되기 때문이다. 물론 여전히 그러한 증명들을 믿지 못하거나, 혹은 공격자가 흘린 정보만을 믿고 exit을 하려는 사용자들도 있을 것이다. 그렇다고 하더라도 이는 사실 큰 문제가 되지 않는다. 우리는 DA에 대한 판단을 전적으로 사용자 개인에게 맡기고 있기 때문이다. 만약 해당 사용자가 문제가 있다고 판단하여 ERU를 통해 Exit을 한다면 그 누구도 막을 수 없다. 두번째 케이스는 공격자가 비용을 감수하고 공격을 감행할 경우이다. 이 경우 또한 크게 문제되지는 않는다. 공격자는 대상 차일드 체인의 블록들이 finalization이 되는 것을 일시적으로 막을 수 있지만, 체인의 진행 자체를 막을 수는 없기 때문이다. 따라서 사용자들이 겪게 될 불편도 미미한 수준일 것이다. <br> ### References - [Joseph Poon and Vitalik Buterin, Plasma: Scalable Autonomous Smart Contracts](https://plasma.io/) - [Plasma EVM](https://ethresear.ch/t/plasma-evm-state-enforceable-construction/3025/11)