Plasma MVP Audit 녹취록 (Script)
계산복잡도 이론을 이용한 효율적인 스마트 컨트랙트 프로그래밍
지난 6월 1일 HAECHI LABS와 함께 현대카드 스튜디오 블랙에서 발표했던 “플라즈마 MVP 오딧” 강연의 녹취록입니다. 이더리움 스케일링 솔루션인 플라즈마와 관련된 내용들을 더 많은 분들이 접할 수 있도록 스크립트를 작성해보았습니다 :)
본 문서는 스크립트를 위주로 작성하였으므로 강의 영상과 발표자료를 병행하여 참고하시길 권장합니다.
Intro
일단은 시작에 앞서서 아이디어의 단초를 제공해준 저희 팀원들, 그리고 엔지니어 4000D에게 감사의 말을 전하고요. 4000D는 이름이 아니고요. Github 아이디입니다. 발표 방향과 순서에 대해 일단 먼저 말씀을 드리도록 하겠습니다. 어떤게 답이다라고 알려주기보다는, 적절한 의문을 던지고 좀 많이 질문도 하시고, 얘기도 하시고 하셨으면 좋겠어요. 그냥 저도 블록체인을 좋아하는 연구자 중 한명이기 때문에 그런식으로 발표를 진행해보면 좋겠다 생각을 하고요.
순서는 일단 플라즈마 오딧이라고 얘기를 했는데, 오딧을 하려면 도구가 필요하잖아요. 그래서 어떤 툴을 쓸지 처음에 설명을 드리고요. 플라즈마 MVP가 어떻게 구성되어있는지 하나하나 보는 방향으로 해보겠습니다.
오신분들 사전정보를 못받아서 몇가지 좀 여쭤볼게요. 혹시 알고리즘과 자료구조를 공부하신 분 계신가요? 계산복잡도 이론 들어보셨죠? 시간복잡도, 공간복잡도.. 그 다음엔 이더리움 황서 읽어보신분 계신가요? EVM의 스토리지, 스택과 메모리 차이에 대해서 좀 확실히 얘기하실 수 있다. 혹시 0x60 옵코드에 대해 알고계신가요? 푸쉬(PUSH).. 왜 제가 꼭 0x60 옵코드에 대해 얘기를 하냐면, EVM 소스코드에 보면 옵코드를 루프문으로 처리하는데 0x60옵코드가 제일 앞에 있어요. 왜? 제일 많이 쓰니까.
플라즈마 관련해서 좀 여쭤보면 플라즈마 백서 보신분 계신가요? 플라즈마 소개글, 디사이퍼에서 연재된 플라즈마 소개글 보신분. 플라즈마 MVP코드를 보셨다? 오미세고에서 만든.. 거기에 커미터다?! 커미터까지는 안계시네요. 네 대충 어느정도 파악이 됐구요. 제가 생각한대로 하면 될 것 같아요. 오늘 발표의 목표는 스마트 컨트랙트를 조금 짜보신 분이 조금 더 잘짜려면 어떻게할까 고민을 하는 과정에서 내용을 준비해 봤습니다.
오딧이라는 과정을 저는 2가지로 보고있어요. 1차적으로 허점을 집어주는 과정이 첫번째일 거고, 두 번째도 저는 사실 굉장히 중요하다고 보거든요? 효율적으로 코드와 프로그램이 동작하도록 도와주는 일, 조언하는 일, 개선하는 일도 굉장히 중요한 일이라고 생각합니다. 특히나 블록체인 같은 리소스가 굉장히 부족한 컴퓨팅 환경에서는 이런 부분들이 더욱 더 중요합니다. 아까보니까 T사의 사례가 있던데, 잠깐 질문 하나 드려볼까요? 아까 그 코드 for문 N번도는거 시간복잡도 몇이죠? O(n)인가요?? O(n)번 코드는 EVM에서 돌리기 힘듭니다. 결론이에요. 오늘 발표내용의 결론인데. 순서대로 말씀을 드리겠습니다. 오늘은 1번보다는 2번에 포커싱을 맞춰진 내용들을 준비를 했습니다.
복잡도 이론과 스마트 컨트랙트
복잡도와 스마트컨트랙과 어떤 관련이 있는지에 대해 얘기를 드리도록 하겠습니다. 알고리즘 교과서에서 계산복잡도 이론이 이렇게 나눠져요.
시간복잡도와 공간복잡도로 나눠진다.
시간복잡도는 보통 연산횟수, 알고리즘 문제 있잖아요? for문 두개 돌리고 몇번 연산되는지 이런 문제들. 공간복잡도는 그렇게 계산되는 과정에서 얼마나 많은 메모리 공간을 차지하나 하는 식으로 접근을 하죠.
그리고 그 안에 시-공간 트레이드 오프(trade-off) 개념이 있습니다. 시간 복잡도가 커지면 공간 복잡도는 줄어드는 경향이 있고, 공간 복잡도를 줄이는 과정에서 시간 복잡도가 커지는 경향이 있고, 이런 이론들이 있습니다.
근데, 제가 질문을 드릴게요. 과연 EVM에서도 그럴까? EVM에서 시간복잡도와 공간복잡도의 개념이 뭘까? 둘은 어떤 관계일까? 궁금하지 않으세요? 진짜 궁금한데..ㅎㅎ 여기에 대해 좀 알아보도록 하겠습니다.
Minime Token
미니미 토큰이라고 있어요. 이 토큰은 특이한게 전송을 할 때마다 잔액을 다 기록합니다. 그래서 모든 특정 블록에 누가 얼마의 잔액을 가지고 있는지 과거 기록이 다 추적이 되요. 근데 “이게 스마트 컨트랙트가 되나?” 이런 생각이 들죠. EVM 성능도 안좋고 용량도 떨어지고 문제도 많다 이러는데 이게 가능한가?
함수는 현재 transfer, generateToken할 때마다 호출되는 function인데요.
getValueAt이라는 함수입니다. 그래서 잔액 상태 변수를 특이하게 정의를 해요. 일반적인 ERC20이랑은 조금 다른 자료구조를 씁니다.
보통 mapping에 address랑 Uint를 붙이죠? 그래서 주소가 얼마의 토큰 balance를 가지고 있나하는 방식으로 코딩을 하는데, 얘는 Checkpoint[]라는 struct를 써요.
Value는 똑같은데, fromBlock을 써요. 내가 전송을 하는 시점에 balance가 얼마인가. 그걸 기록합니다.
Minime Token 시간복잡도
그럼 이제 미니미 토큰 잔액 조회의 시간복잡도를 계산해 볼게요. 굉장히 간단하게 되어있어요. 알고리즘은 바이너리 서치 빅오 표기법으로 했을 때, O(log(n))입니다. 여러가지 숫자는 가정이에요.
현재 이더리움 어카운트 숫자를 좀 볼까요? 보시면, 최신 이더리움 어카운트를 보면 3500만개 정도가 블록체인에 기록되어 있습니다. 현재 데이터입니다.
토큰별 어카운트가 몇 개정도 되는지 살펴볼까요? EOS볼까요? 아직 ERC20이니까, 30만개 정도의 어카운트가 생성됩니다. 만약 미니미 토큰으로 ERC20을 만들었을 때, 내가 시작이 1등이다 하면 몇개 정도의 계정을 처리해야 한다? 잔액 정보를? 한 30에서 50만, 100만개까지 정도는 커버가 어느 정도는 되어야 하고, 멀리까지 바라보면 1000만개, 2000만개 까지도 다룰 수 있어야 한다는 것이겠죠.
그럼 몇가지 가정을 바탕으로 제가 계산을 한번 해볼게요. 이더리움은 연산을 수행할 때 gas 비를 내죠.
gas 비를 t로 가정하면, 가스 소모량은 0.1M이라고 가정.
이렇게 가정한 이유가 뭐냐면, 혹시 보통 ERC20 Mintable 함수 전송할 때 gas 비 얼마나 쓰는지 아시는 분 계신가요? 20만정도 써요. 일반 트랜잭션 보낼 때는 얼마 쓰시는지 아시죠? 2만1천. 미니미 토큰 transfer할 때 얼마 쓰는지 아시나요? 40~50만 정도 씁니다. 그래서 가정을 그냥 한거에요. ¼ 정도 10만정도를 쓸 것이다. 반복문 한번에 10만 정도, 사실 굉장히 넉넉히 준 가정입니다. 실제로는 이것보다는 적을거에요.
n이 0.1M이라고 가정을 해볼게요. 이건 서치니까. 0.1M이 몇개죠? 10만번 정도 서치? 잔액을 자기가 계속 10만번 정도 계정 한개에서 transfer한거에요. 거래소에서 만드는 입금주소가 10만개~20만개 정도 만들어요. nonce값을 확인해 보면 나오잖아요. 어카운트에서 트랜잭션을 몇개 만들었는지. 10만개정도라고 가정했을 때, 최대 가스 소모량은
t*O(log(n))으로 볼 수 있죠? 풀어볼까요? 0.5 M.
블록가스 리밋이 몇인가요? 8M이죠. 얘는 가능하다, 불가능하다? 가능합니다. 그러니까 바이너리 서치 같은 경우는 O(log(n))의 복잡도를 갖고 있기 때문에 이런 연산이 0.9M 정도 쓴다고 가정하면 20개 이상 블록에 담길 수 있습니다. 이런식으로 시간 복잡도를 계산한다는거구요.
Minime Token 공간복잡도
그 다음엔 공간복잡도를 한번 볼까요? 여기 보시면 공간복잡도를 어떻게 알 수 있죠? 보통은 이제 선언된 변수, 선언된 변수가 배열로 커지는 상황을 가정하는데요. 제가 공간복잡도 얘기를 왜 드리냐면, 공간복잡도 입장에서는 공간을 차지 하느냐 마느냐냐, 할당을 했느냐 안했느냐가 기존의 폰노이만 컴퓨터에서 쓰는 가정들이에요. 배열을 크게하면 공간을 많이 쓰게되죠? 그래서 공간복잡도가 커진다고 말을 하는데, 이더리움은 좀 독특하게 있어요. 이더리움의 상태 변수를 변화할 때 몇 가스를 쓰는지 아시는분 계신가요? 최초 0인 것을 새로 할당할 때, 2만 가스를 쓰고요. 일단 할당된 변수들을 바꿀 때, 5000 가스를 씁니다.
근데 볼게요. 알고리즘 이론에서는 시간복잡도와 공간복잡도가 반비례한다고 이야기를 하는데, EVM은 특이한게 있어요.
장소를 차지하는 비용과 장소를 늘리는 비용에 가스를 부과하고 연산이 실행될 때도 가스를 부과해요. 시간복잡도와 공간복잡도가 궁극적으로 비용이라는 측면에서 같아요.
그래서 고정 공간을 변경하는데 소요되는 가스에 대해 질문을 드렸었는데요. EIP150 이후의 현재 EVM의 옵코드가 소모되는 가스 테이블들을 모아놓은 건데, 여기서 SSTORE라는 옵코드(0x55)를 조회해 볼게요. 여기 FORMULA라고 되어있죠. FORMULA가 어떻게 되어있죠?
((value != 0) && (storage_location == 0)) ? 20000 : 5000
“20000 is paid when storage value is set to non-zero from zero. 5000 is paid when the storage value’s zeroness remains unchanged or is set to zero.”
value가 0이 아니거나 storage_location이 0이 아니면 2만, 그렇지 않으면 5천. 최초 할당할 때 2만, 변경할 때 5천. 이 2만이라는 가스는 굉장히 큰 가스에요. 5천이라는 가스도 큰 가스고, 5천이 10번 실행되면 5만이잖아요? 100번 실행되면 몇이죠? 50만이죠. 0.5M인데, 블록가스 리밋이 몇이라고요? 8M. 굉장히 소모되는 양이 많습니다.
반면에 MSTORE 볼까요? 3가스 씁니다. 그러니까 스토리지에 저장하는 것은 비용이 굉장히 큰데, EVM에 있는 메모리나 스택들을 활용할 때는 가스를 거의 쓰지 않습니다. 없는거나 마찬가지에요. 그런데 이건 옐로페이퍼에도 있죠. 스토리지에 저장하는 비용은 크고, 메모리를 이용하는 비용은 적다. 내용으로 다시 돌아가보겠습니다.
그러면, 제가 아까 미리 말씀을 좀 드렸는데요. 시간비용은 각 연산당 비용을 가스로 한 것으로 볼 수 있고, 공간비용은 SSTORE, MSTORE, MLOAD, PUSH, POP 같은 명령어들이 소모될 때 어딘가 공간을 할당합니다. 특히 SSTORE, MSTORE 이런 애들. 공간을 할당할 때 비용을 내게 됩니다. 공간의 절대적인 사이즈도 중요한데, 공간에 뭔가 기록을 할 때 쓰는게 굉장히 의미있다면 분석할만한 가치가 있는 거겠죠. 근데 이렇게 오해할 수 있어요.
시간비용과 공간비용이 같다? 공간비용도 고려해서 코딩을 해야 할까요?
알고리즘 책에 요즘 이렇게 나오잖아요. 요즘 메모리 공간이 굉장히 크기 때문에 시간비용을 고려하는 알고리즘이 좋다. 교과서엔 이렇게 나오잖아요 폰노이만 컴퓨터에서. EVM도 과연 그럴까요?
여기 보시면 Factorial이라는 함수를 솔리디티로 짰는데요. Factorial1은 재귀함수를 쓰고, Factorial2는 for문을 씁니다. 공간복잡도 측면에서는 누가 더 큰가요? 1번이 크죠. 1번은 스택에 계속 쌓아놔야 하잖아요. 기존의 n값을 계속 남겨야하잖아요. 2번은 fac라는 변수 하나만 쓰면되니까 공간복잡도는 작아보이죠. 실제로 이 코드를 돌려보면 누가 더 가스비가 적거나 많을 까요? 별 차이없습니다. 신기하죠? 차이가 조금 나긴 합니다. 한 100번인가 1000번인가 실행하면 2만 정도 차이나는 걸로 알고 있어요.
근데, 아까 SSTORE 얼마 쓴다고 했죠? 5천 쓴다고 했죠? for문 한번이 SSTORE는 5천쓰는데, 이건 백번 천번 돌려도 2만밖에 차이 안나요. 굉장히 적게 차이나는거죠. 그럼에도 불구하고 아래 것이 더 쌀 거에요. 위에는 스택에 저장하고 아래는 메모리에 저장을 하거든요? 하나는 2가스고 하나는 3가슨데, 조금 싸요. 한 30% 정도? 그래서 코드를 짠다면 옵코드에 맞춰진 코드를 짜야한다. 옵코드와 EVM을 이해하는 코드를 짜야되는거죠. 그냥 단순히 폰노이만 컴퓨터 아닙니다 EVM은.
그럼 이더리움 블록체인에서 비용이란 무엇일까? 아까 얘기했듯이 공간비용 차이 되게 많이 났잖아요. 신경쓰지 않아도 된다고 했죠. 근데 하나 신경쓸게 있어요. SSTORE. 스토리지를 쓰는 공간 비용은 신경을 엄청나게 써줘야 해요. 얘는 구조적으로 다르기 때문이에요. 그래서 SSTORE를 쓰는 공간은 공간비용도 고려해야 한다. SSTORE를 쓰는 공간이 뭐 있죠? 컨트랙에 상태 변수들 있죠? 걔 값 바꿀 때 마다 SSTORE 호출합니다. 컨트랙을 배열로 선언하잖아요. 배열의 값을 바꾸잖아요? 그래도 SSTORE 호출해요. 상태변수 변경은 굉장히 신중하게 써야한다. 그리고 최소한으로 해야한다. 이게 굉장히 중요한 거고, 근데 시간과 공간비용을 같이 고려를 해서 저는 이걸 시공간비용이라고 합니다. 무슨 아인슈타인도 아니고 시공간 ㅋㅋㅋ 시공간비용이라는 용어를 쓸게요 앞으로. 왜냐면 두 가지가 다 고려가 되어야하기 때문에.
일반적으로 알고리즘 책에 나오는 복잡도 허용은 O(n^2)정도까지는 그래도 봐줄만 하다고 얘기를 해요 일반적으로. 요즘은 컴퓨터 성능도 많이 좋아졌고 했기 때문에. 하지만 EVM은 훨~씬 적습니다. O(log n)이 제가보기에는 거의 최대 허용치고, 그냥 O(n)도 힘들어요. 아까 T사 사례 나왔죠? 2000개를 줘야해요. 복잡도가 O(n)이거든요? 근데 중간에 Send transaction, transfer 있었죠? ERC20 transfer 함수있었죠? 제가 아까 Mintable 함수 가스 얼마나 쓴다고 그랬나요? 20만? 20만 x 1000하면 어떻게 되죠? 블록가스 리밋에 절대 못담습니다. 아까 for문은 못 돌아가는 구조에요. 그러니까 아키텍처에 대한 이해 없이 소스코드를 짜면, 테스트 환경에서는 돌아가죠. 프라이빗 체인에서는 돌아갑니다. 블록가스 리밋 안주면 되잖아요. 가스 0으로 해도 돌아가잖아요. 퍼블릭 체인에서는 절대 안 돌아가죠.
Plasma
그럼 여기까지 도구를 살펴봤으니, 도구를 가지고 소스코드를 좀 살펴보도록 하겠습니다. 플라즈마에 대한 간단한 소개인데요. 일단 계층형 블록체인을 지향하고 있고, 부모체인 자식체인의 상위 법원의 역할을 수행합니다. 주요 특징으로 Merklize State Commitment, Single Source of Value, Rule with Exit, Map Reduce Computation 여러가지 기능들이 있어요. 플라즈마가 아직 안 만들어 졌는데, MVP를 오미세고에서 만들었어요.
오미세고에서는 n개의 복수의 depth를 가진 체인이 아니라 부모체인과 자식체인 두 가지를 구현을 해놨고, 부모 체인은 EVM 기반으로 동작하는 블록체인이고 ganache로 돌고 있고요. 차일드(자식) 체인은 UTXO모델로 서버에 조그맣게 만들어 놨습니다. 비트코인보다 못한 UTXO모델을 차일드 체인에 집어 넣어요. 어떤 명령어를 주면 루트체인의 상태가 바뀌고, 차일드 체인의 상태가 바뀌는 이런 모델링을 하고 있는거죠. 사실 기능이 완전하지는 않고, 아직 가야할 길이 멀다. 이걸 제가 어떻게 아느냐? 제가 이쪽에 계속 이슈를 올리고 있어요. 커밋도 종종 찍고.
좀 궁금하신 분들은 디사이퍼에서 좋은 글을 써주셨더라고요. 궁금하신 분들은 읽어보고 천천히 생각해보시면 도움이 많이 될 것 같구요.
그래서 제가 좀 살펴보고자하는 것은 메인체인에, 루트체인에 스마트 컨트랙트 구성이 어떻게 구성되어 있나하는 부분입니다. 메인체인의 역할은 사실 별게 없어요. 자식체인에서 발생하는 트랜잭션들이 머클라이즈 되어서 루트해시가 나오죠. 그걸 주기적으로 메인체인에 기록하는 역할을 하는거에요. 아까 Mapreduce라고 개념을 말씀을 드렸었는데, 자식체인에서 100개, 1000개, 5000개, 10000개 이런식의 트랙잭션이 생기면, 머클라이즈해서 대표하는 값을 하나 툭 올립니다. 이런식으로해서 여러개의 트랙잭션들을 단 하나의 트랙잭션으로 대표할 수 있게해서 수직 확장성을 키우는 식의 접근방식을 취하고 있어요.
그럼 루트체인의 컨트랙트 구성을 보면, 일단 루트체인이 있죠? 이 주변에 수많은 라이브러리들이 있습니다. 머클들을 처리해야하기 때문에 머클 관련된 라이브러리들을 컨트랙트로 짯어요. 여기있는건 다 컨트랙트입니다. ERC20으로 짠. Jave, Java Script 라이브러리로 짠게아니라 솔리디티로 짠 코드들이에요. Math, SafeMath 연산 관련된 로직, 이거때문에 얼마 전에 문제가 많았었는데…
그 다음 Validation관련된 코드가 있습니다, 트랙잭션, V, R, S값들 이더리움에서 쓰는 서명 값들. 검증해주는 것을 스마트 컨트랙트로 짰어요. 그다음에 RLP. RLP 인코딩/디코딩을 스마트 컨트랙트로 합니다. RLP하면 코어에서나 쓰는 걸로 알고 계시잖아요. 이것도 스마트 컨트랙트로 짰어요. 재미있는게 Priority Queue(우선순위큐)가 있어요.
Cash 이전의 플라즈마 MVP는 우선순위 큐가 굉장히 중요하죠. 왜냐하면 차일드체인 트랜잭션 혹은 UTXO 세트 중 일부를 내가 메인체인에서 빼서 탈출하고 싶을 때 우선순위 큐를 쓰거든요. 우선순위 큐를 솔리디티 코드로 짰습니다.
오늘 이걸 다 얘기드리긴 힘들 것 같구요. 루트체인이랑 우선순위 큐가 어떻게 구성되어 있는지, 얘네가 과연 현재 퍼블릭 이더리움 블록체인의 limitation 안쪽에서 구현가능한건지 한번 보도록 하겠습니다. 아까 시공간복잡도라는 좋은 툴을 얻었기 때문에 굉장히 분석하기 편해요.
RootChain.sol의 주요 함수 구성들을 좀 보시면,
1. submitblock() : 자식체인의 머클 루트 정보를 부모 체인에 올리는 함수죠.
2. deposit() : 루트 체인에 ETH를 묶고(deposit) 자식 체인으로 들어가는 함수에요. 자식체인에서 이더가, 플라즈마 이더(PETH)죠. 플라즈마 이더로 융통되기 위해서는 부모체인에 이더를 deposit 해야하는 거에요.
3. startDepositExit() / 4. startExit() : 두 함수가 Exit 관련된 로직이에요. 플라즈마 이더가 계속 돌고있으면 메인 체인에서 이거를 exit해서 빠져나와야 하잖아요. 내가 묻은 이더를 꺼내서 들고 나가야 되잖아요. 관련된 함수가 2개가 있고.
5. challengeExit() : 근데 나갈때 더블 스펜딩을 하려는 사람이 있죠. 이 사람들한테 Challenge를 하는 ChallengeExit함수가 있습니다.
6. finalizeExit() : 그리고 챌린지 기간이 다 끝나고, 내가 제출했던 Exit들을 순서대로 처리해주는 FinalizeExit 함수가 있어요.
사실 이렇게만 보시면은 대충 플라즈마가 어떻게 구동하는지 감각이 좀 오실거에요.
어찌 됐든 부모체인이랑 자식체인이 있어서, 부모체인에 ETH를 묶고 자식체인에서 유통하는거에요. 유통을 하다가 내가 나가고 싶으면 자식체인에 있는 토큰 없애고 부모체인에 있는 토큰 deposit 된거 빠져서 나가는 겁니다.
그 사이에있는 트랙잭션 변화? 신경 안쓰겠다는거죠. 주기적으로 묶어서 반영만 하겠다는거죠. 굉장히 간단한 접근방식이구요. 근데 현재 구현되어있는 부분이 1~3번까지에요. MVP 잖아요. 완성된게 아니잖아요 베타버전도 아니고. 뒷부분은 현재 구현중인 상태고.
exit 과정을 좀 요약해서 말씀을 드리면요. 사용자의 요청이 일단 옵니다. startDepositExit이랑 startExit 함수에 의해서 요청이 와서, 이 요청 목록들이 쭉 쌓여요. 배열 형태로 일렬로 쭉 들어옵니다. 각각의 정보들에 대한 priority 정보들은 PriorityQueue.sol을 통해 관리되는 구조에요. 그러니까, 실제 내가 하는 요청과 그 요청에 대한 우선순위를 따로 관리하죠. 근데 이게 전전 버전에서는 이렇게 안했어요. 제가 서울대학교에서 특강할 때만 해도 이렇게 안만들었는데 얘네가 바꿨더라구요.
챌린지를 거친 finalizeExit함수는 대기열에 쌓인 exit들을 우선순위를 고려하여 하나씩 꺼냅니다. 이게 굉장히 중요한데요 플라즈마에서. 제일 마지막 사람이 더블 스펜딩을 한다고 해도, 결과적으로 exit은 UTXO에 쌓인 순서대로 빠져나가기 때문에 마지막 사람의 더블 스펜딩만 잘 판단했다면 사람들이 대량출금을 해서 이 사람의 트랜잭션을 못쓰는 요청을 만들어내겠죠. 이게 핵심이에요. 근데 이 기록들을 어디서 관리한다? 메인 체인의 스마트 컨트랙트에서. 그래서 메인 체인의 RLP라든지 머클이라든지 Priority Queue(우선순위큐)라든지 이런 자료구조들과 컨트랙이 필요한 겁니다.
그래서 제가 이제 이것들을 하나하나 살펴볼텐데요. 이슈는 뭐냐면, 사용자가 exit 요청을 할 때 gas fee를 이더리움이 감당할 수 있을 것인가. 대량출금 요청이 들어왔을 때 퍼블릭 체인이 이 요청들을 감당할 수 있을 것인가. 감당할 수 있도록 컨트랙을 짰나를 한 번 살펴보겠습니다.
일단 그럴려면, 각각의 함수가 어떻게 동작하는지 시공간복잡도를 파악을 해야겠죠 일차적으로.
exit 과정은 사용자 요청으로 이루어져 있고요. 여기보면은 쭉 들어오는데, addExitToQueue에서 일단은 우선순위 큐에 올립니다 요청들을. 출금 요청은 되게 간단해요. 내가 얼마를, 어느 블록으로 deposit했던 ETH를 빠져나가겠다 이런.. 되게 간단한거죠.
근데 Queue에 쌓는데 이렇게 쌓죠. ExitQueue에 insert를 하죠. 우선순위큐에 삽입을 합니다.
그리고 출금할 때, 이건 이제 큐에 쌓아놓은거고 Finalize는 이걸 다 긁어서 빼는거잖아요. 걔는 이제 while문이 도는데, 제일 처음에 우선순위 큐에서 다음 exit을 찾고, 그러니까 우선순위가 제일 높은(제일 옛날에 생긴 사람들) exit을 먼저 찾고, 찾았으면 찾은 사람한테 이더를 보내고. 얘는 메인 체인에서 일어나는 일이에요. 그리고 마지막에 우선순위 큐에서 지우고 그 다음 NextExit을 찾죠.
중요한 건, exit 하나당 뭘 하고 있죠? 우선순위 큐에서 insert를 하고 있죠. 그럼 자료구조를 좀 살펴봐야 할 필요를 느끼지 않을까요? exit이 5000개면 5000개가 얘를 다 돌텐데.
getNextExit 함수 아까 위쪽에 있었는데요. 이 우선순위 큐에서 다음 exit을 찾는 서치 알고리즘인데. 보시면 PriorityQueue에 getMin이라는 함수를 호출합니다. PriorityQueue.sol을 이제 볼 때가 됐네요.
안에 뭐 되게 많은데요. 크게 보면 insert 관련된 로직이랑, delete 관련된 로직 두 가지로 나눌 수 있습니다. 이걸 자세히 설명드린다기보다는, 그냥 이건 알고리즘같은 책보면 우선순위 큐에 대한 구현체들이 많을거에요. 그런거보시면 사실 똑같거든요. 똑같은데, 재밌는건 뭐냐면 우선순위 큐가 구현 방법이 굉장히 다양하다는거에요.
삽입과 삭제 두가지를 봤을 때, 순서없는 배열을 할 경우에 O(1)이 되죠. 삭제를 할 때는 O(n)이 됩니다. 문제는 이게 좋다 나쁘다라기보다는, 이게 맞느냐는거죠. 예를 들어서 볼게요. 삽입이 엄청나게 많고 삭제하는 일이 거의 없어요. 그럼 이걸(순서없는 배열행) 하겠죠. 왜냐, 그게 효율적이니까. 근데, 얘네는 히프라는 자료구조를 씁니다. 제일 마지막(삽입 : O(logn), 삭제: O(logn) ) 두 가지 구현을 씁니다.
엑싯 요청이랑 Finalize의 시공간비용을 비교해볼게요. 안쪽에 실제로 호출된 함수들을 하나하나 꺼내봤어요. 제가 아까 상태변수 변경 몇 쓴다고 했죠 gas? 5000. 상태변수 길이만큼 상태변수 변경하죠. 자, 5000번의 exit 요청이 있다는 가정을 해볼게요. 5000번의 exit 요청이 있었어요. 그리고 5001번째 혹은 5000번째 exit 요청을 하는데에 gas비가 얼마가 드는지 한번 계산을 해보겠습니다.
시공간비용이 약 5000gas라고 봤을 때, 1000번째 exit이라고 되어있는데 5000번째입니다. 5000번째 exit의 시공간 비용은 t*O(log_2(5000))이 될거고 계산하면 60000 gas 쯤 되죠. 근데 물론 앞뒤에 뭐가 막 붙어있을거에요. 스왑도 있고 푸쉬도 있고 팝도 있고 뭣도 있고 기타 해서 한 100000정도 더 붙인다고 하면 16만 가스죠. 블록가스 리밋 몇인가요 아까 제가 말씀드린거? 8M? 얘는 몇이죠? 0.16M. 가능하죠.
Finalize 함수를 한 번 보겠습니다. 이제 얘가 관건인데, 얘는 특징이 뭐냐면 exit 요청이 많이 쌓이면 쌓일수록 마지막 하는 exit의 gas비는 더 많이 지불할 수 밖에 없어요. 구조적으로 그렇게 되어있어요. 왜냐하면 아까 봤듯이, 우선순위 큐에 히프 자료구조를 쓰기 때문에 서치를 해야합니다. 어쩔 수 없이. 왜냐면 나의 우선순위를 스마트 컨트랙이 알아야하잖아요. 내가 한 요청의 우선순위를 알아야 하잖아요. 그렇기 때문에 출금요청이 쌓이면 쌓일수록 마지막 요청에 대한 gas 비는 높아질 수 밖에 없지만, 약 5000개 정도의 요청이 쌓여도 사실은 크게 문제없다. 이거 2~3배까지, 한 2만, 3만 개까지는 문제 없을거에요. 2만개 정도 쌓였으면 exit 하겠죠.
finalize 함수를 볼게요. 얘는 5천개를 한꺼번에 exit하는 경우인데. 시공간비용을 보면 트랜스퍼, 일단 이더를 보내야하기 때문에 21000 gas. ExitQueue.delMin() 함수는 상태변수 변경 2번합니다. ExitQueue.percDown()에서 상태변경, delete exits[utxoPos].owner에서 상태변경해서 상태 변수가 4번. 그 다음에 4번에다 21000가스 하니까 4만에서 5만 가스 정도로 볼게요. 여긴 조금 더 여유있게 6만 가스로 잡았죠. t = 60,000gas에다가 5000번 도니까 60,000*O(log_2(5000))
→ 60000 * 12 하면 0.72M gas죠. 5000개가 한 번에 exit 요청이 들어와도 1M이 안됩니다.
결론은 뭐다? 매우 잘 짰다~
이런 부분들을 생각하고 만들었는지는 사실 잘 모르겠어요. 그런데, 실제로 얘는 퍼블릭 체인에서 구동가능한 컨트랙이다. 플라즈마 체인이 목표하고자 하는 바와 정확히 맞다.
출금 요청이랑 출금 실행들이 어떻게 이루어지는지 볼게요. 화살표의 크기가 gas 비용입니다. 그래서 블록이 지나면 지날수록 내가 출금요청을 할 때마다 소모되는 gas가 커지는데, 어떻게 커지죠? t*O(log_2(n))으로 커지죠. 점점 커지긴 하지만, log 함수로 커지기 때문에 어느 순간(지점) 이상 커지진 않아요. 그리고 출금실행이 한꺼번에 빠져나오는데 얘의 복잡도도 똑같죠. 왜냐, 히프. 우선순위 큐를 히프로 만들었기 때문에. linkedlist나 배열로 만들었으면 어땠을까요? 입금은 무리없이 됐겠지만 출금 때 문제 생겼겠죠.
이게 똑같습니다. 사실, 뭐 플라즈마 컨트랙 복잡한걸로 얘기를 하는데요. ICO도 똑같아요. 이더로 받아가지고 토큰 발행하는데, 마지막에 for문으로 2000개를 돌려요. 미친거죠 완전히. 그러니까 EVM이 뭔지 모르고 짠거죠. 이게 비탈릭이 참 그걸 잘했어요. 손 쉽게 코드를 만들고 이건 되게 잘했는데, 잘 만드는건 다른거죠. 만들기는 쉽습니다. 잘 만드는건 전혀 다른 문제에요. 퍼블릭 체인의 현재 상태가 어떤지, 지금 현재 gas 비가 어떤지, 네트워크 형태가 어떤지. 내가 배포하는 그 시점에. 내가 선언하는 함수의 시공간복잡도가 어떤지. 좀 공학에 대한 깊은, 깊이도 아니죠 사실. 학교에서 다 배우니까요. 3학점 정도 들으면 다 배우잖아요 졸지만 않으면 사실은.. 저도 알고리즘 수업 몇점 못 받았는데..ㅋㅋ
이런 아이디어와 VM에 대한 이해가 없으면 좋은 코드가 나오기 어렵다. 동작하기 않을수도 있다라는 점이 굉장히 중요한 것 같습니다.
Appendix
이제 좀 추가적인 부분이 있는데요. 제가 준비를 못한 부분이고.. 머클에 관련된 구현체가 있어요. 이 부분도 한번 비슷하게 살펴보면 좋을 것 같고. 솔리디티 언어는 RLP 소스코드도 있습니다. 이것도 비슷하게 접근하면 굉장히 좋은 접근이 될 것 같고요.
의도적으로 빠진게 지금 challenge 같은 경우에요. challenge에서 이제 앞에 머클이랑 연결되어 있는데, 머클에서 멤버십 체크하는 함수가 있습니다. 머클의 사이즈가 굉장히 커질 경우에는 이 함수에 대한 부담이 굉장히 커질거에요. 그래서 여기에 대한 분석이 추가로 좀 필요하다.. 플라즈마 Cash가 좀 대표적인 경우죠. challenge를 낼 때, 어떤 데이터를 확인을 해야하나. 그 부담을 줄였다라고 이야기하잖아요. 근데 구현이 아직 없습니다. 직접 만들어보셔도 좋을 것 같아요.
Conclusion
마무리인데, 이건 이제 여기있는 일이 논리적이고 이론적인 일이 아니라 얼마전에 겪은거에요.
요구사항이 이렇게 들어왔습니다.
“ERC20 토큰을 발행/전송하는데 발행일 기준 각각 유효일이 있고, 전송할때, 즉 토큰 컨트랙 한개에서 하는 일이죠. 유효일이 지나면 잔액이 0으로 떨어졌으면 좋겠어요”라고 요구사항이 들어왔어요. 저희팀 엔지니어가 이렇게 이야기합니다.
4000D : 토큰 생성시 정해지는 유효 기간 은, 특정 토큰 수량마다 다른거죠? 만약 그렇다면, 특정 토큰의 (토큰 수량, 유효 기간) 의 tuple 을 배열로 저장해야할거에요. 그런 배열을 `tupleRecords` 라고 부르면, `transfer()` 할 떄, 유효하지 않은 토큰 수량을 계산 / 반영해야하는데, 이 때의 계산복잡도 *(`tupleRecords`의 각 원소를 읽고, 유효 기간이 지난 토큰 수량의 총 합을 계산)* 는 최대 `tupleRecords`의 길이 `n` 에 비례해서 `O(n)` 이 될거에요. 이더리움에서 `O(n)` 의 복잡도를 가지는 함수를 구현하는것은 불가능해요.
따라서 이 요구사항은 받아들여지면 안된다. out of gas난다.라고 이야기를 했는데 제가 이렇게 이야기를 했죠.
어차피 프라이빗 체인에 올리잖아 ? ㅋㅋㅋ
맥락이 이해되시나요? “아 이거 gas비 이런거 부담해야해”라는, 아주 직업적인 컨트랙 엔지니어죠. 짰는데, 결과적으로 우리가 올릴 아키텍쳐는 어디다? 프라이빗 블록체인이다. gas 비 0으로 줘도 올라가잖아요. 소용없죠. DOS 어택을 하든지 말든지, DOS 어택을 하면 그냥 없애버리면 되잖아요. 노드 연결 빼버리면 되잖아요. 이런 대화들이 이제 오고 갔습니다.
아무튼 관련해서 제가 오늘 좀 쉬우면 쉬울수도 있고, 좀 어려우면 어려울 수도 있는 내용들을 말씀드렸는데요. 개발할 때 되게 여러가지들을 고려를 합니다. 특히나 얘가 폰 노이만 컴퓨터가 아니라, 이더리움 가상머신, EVM이기 때문에 고려되는 문제점들이에요. 그리고 개발자나 엔지니어이시라면 이런 부분에 대한 이해와 고려를 하실 필요가 있을 것 같구요.
긴 글 읽느라 고생하셨습니다 :)
