Plasma MVP(7f80bc9)
Smart Contract Audit
정순형(철학자)
<외부자료 활용 시 출처 명시 부탁드립니다.>
발표영상
2
3
발표 방향과 순서
정답을 알려주기보다는 적절한 의문을 던지고 함께 호흡하는 방식
왜냐하면 저도 여러분처럼 그냥 블록체인을 좋아하는 한 명의 미완성된 연구자이기 때문
4
몇 가지 질문
5
What is Audit?
6
What is Audit?
7
복잡도 이론과 스마트 컨트렉트
8
알고리즘 교과서에서 가르치는 계산복잡도이론
9
미니미 토큰의 잔액 조회의 시간복잡도는?
mapping(address => Checkpoint[]) balances;
10
미니미 토큰의 잔액 조회의 시간복잡도는?
11
미니미 토큰의 잔액 조회의 공간복잡도는?
mapping(address => Checkpoint[]) balances;
12
EIP 150이후의 가스비 정리
https://docs.google.com/spreadsheets/d/1n6mRqkBz3iWcOlRem_mO09GtSKEKrAsfO7Frgx18pNU/edit#gid=0
13
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? → SSTORE, MSTORE, MLOAD, MSTORE, PUSH, POP.. (GAS)
14
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? → SSTORE, MSTORE, MLOAD, MSTORE, PUSH, POP.. (GAS)
시간비용과 공간비용이 같다??
15
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? → SSTORE, MSTORE, MLOAD, MSTORE, PUSH, POP.. (GAS)
시간비용과 공간비용이 같다??
그렇다면 공간비용도 고려해서 코딩해야 한다??
16
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? →SSTORE, MSTORE, MLOAD, MSTORE, PUSH, POP.. (GAS)
시간비용과 공간비용이 같다??
그렇다면 공간비용도 고려해서 코딩해야 한다??
아니다. 공간 점유 비용이 상대적으로 싸다, 다만 상태변수(스토지리) 제외!
18
EIP 150이후의 가스비 정리 : SSTORE
https://docs.google.com/spreadsheets/d/1n6mRqkBz3iWcOlRem_mO09GtSKEKrAsfO7Frgx18pNU/edit#gid=0
19
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? → SSTORE, MSTORE.. (GAS)
SSTORE를 쓰는 공간
→ 공간비용을 고려해야 한다.
20
이더리움 블록체인에서 비용이란 무엇일까?
정답 : GAS
→ 그렇다면 시간비용은? → 각 연산당 비용 (GAS)
→ 그렇다면 공간비용은? → SSTORE, MSTORE.. (GAS)
시간비용과 공간비용의 부담이 같다
21
SSTORE + 시간비용
= 시공간비용
복잡도는 어디까지 허용될까?
22
폰노이만 머신의 일반적인 복잡도 허용
이더리움 스마트 컨트렉트의 복잡도 허용
23
폰노이만 머신의 일반적인 복잡도 허용
EVM의 복잡도 허용
플라즈마(Plasma)
24
플라즈마(Plasma)
25
Brief Introduction to Plasma MVP
26
child_chain.py
ganache
client.py
루트체인
차일드체인
명령을 날림
루트체인 상태 변경
차일드체인 상태 변경
blocks = {1,2, .. }
마이닝 된 블록
RootChain.sol
Account0
Account1
Account2
current_block:
마이닝 메모리 풀
디사이퍼에서 쓴 다음 글은 매우 도움됩니다!
27
Plasma MVP의 루트체인의 컨트렉트 구성
28
RootChain.sol
library_SafeMath.sol
library_Merkle.sol
library_PlasmaRLP.sol
library_Math.sol
library_Validate.sol
PriorityQueue.sol
Plasma MVP의 루트체인의 컨트렉트 구성
29
RootChain.sol
library_SafeMath.sol
library_Merkle.sol
library_PlasmaRLP.sol
library_Math.sol
library_Validate.sol
PriorityQueue.sol
RootChain.sol의 주요 함수 구성
30
RootChain.sol의 주요 함수 구성
31
파란색 : 현재 구현되어 있는 부분
exit(출금) 과정 : 전체 요약
32
사용자의 요청(startDepositExit 함수, startExit 함수)에 의해
대기열에 여러 exit들(출금요청)이 쌓여있고,
[exit1, exit2, exit3 … ]
각각의 exit정보들에 대한 priority에 대한 정보들은 PriorityQueue.sol을 통해 관리된다.
(챌린지를 거친) finalizeExit함수는 대기열에 쌓인 exit들을 우선순위를 고려하여 하나씩 꺼내 이더를 보내준다.
exit(출금) 과정 : 사용자 요청(startDepositExit)
33
큐에 저장
exit(출금) 과정 : 사용자 요청(addExitToQueue)
34
우선순위 큐에 <삽입>
exit(출금) 과정 : Finalize
35
3.우선순위 큐에서 <삭제>
1. 우선순위 큐에서 다음 엑싯을 찾고(다음 페이지)
2.이더 보내고
exit(출금) 과정 : getNextExit
36
우선순위 큐에서 최소값이 다음 엑싯 값이 된다
개별 컨트렉 소개2 : PriorityQueue.sol
37
38
엑싯 요청 vs Finalize 시-공간 비용 비교
39
엑싯 요청 | Finalize |
ExitQueue.Insert() - 상태변수 변경, percUp(currentSize) - 상태변수 길이(n)만큼 변경 exits[utxoPos] - 상태변수 변경 | 쌓여있는 exit수를 n이라고 하면 transfer(), - 21,000가스 ExitQueue.delMin(), - 상태변수 변경(2번) ExitQueue.percDown(), - 상태변수 변경 delete exits[utxoPos].owner; - 상태변수 변경 |
5000번의 exit 요청이 있었다는 가정(n=5000) 연산당 시공간비용(t)은 약 5000gas 1000번째 exit의 시공간비용은? t*O(log_2(5000)) → 5000*12 → 60000gas + @ | 5000개를 한꺼번에 exit할 경우(n=5000) t = 60,000gas t*O(log_2(n)) → 60,000*O(log_2(5000)) → 60000 * 12 → 0.72M gas |
엑싯 요청 vs Finalize 시-공간 비용 비교
40
엑싯 요청 | Finalize |
ExitQueue.Insert() - 상태변수 변경, percUp(currentSize) - 상태변수 길이(n)만큼 변경 exits[utxoPos] - 상태변수 변경 | 쌓여있는 exit수를 n이라고 하면 transfer(), - 21,000가스 ExitQueue.delMin(), - 상태변수 변경(2번) ExitQueue.percDown(), - 상태변수 변경 delete exits[utxoPos].owner; - 상태변수 변경 |
5000번의 exit 요청이 있었다는 가정(n=5000) 연산당 시공간비용(t)은 약 5000gas 5000번째 exit의 시공간비용은? t*O(log_2(5000)) → 5000*12 → 60000 gas + @ | 5000개를 한꺼번에 exit할 경우(n=5000) t = 60,000gas t*O(log_2(n)) → 60,000*O(log_2(5000)) → 60000 * 12 → 0.72 M gas |
매우 훌륭함
출금요청과 출금 실행
41
출금요청 시공간복잡도
→ t*O(log_2(n))
...
n번 출금요청
...
출금실행 시공간 복잡도 → t*O(log_2(n))
n개 출금
추가 연구 : Merkle과 PlasmaRLP의 시공간복잡도
42
RootChain.sol
library_SafeMath.sol
library_Merkle.sol
library_PlasmaRLP.sol
library_Math.sol
library_Validate.sol
PriorityQueue.sol
추가연구 : challenge의 경우
require(merkleHash.checkMembership(txindex, root, proof));
43
추가 연구 : 플라즈마 캐시
44
마무리
45
실제 실무에서 겪은일..
4000D : “@kevin 토큰 생성시 정해지는 유효 기간 은, 특정 토큰 수량마다 다른거죠? 만약 그렇다면, 특정 토큰의 (토큰 수량, 유효 기간) 의 tuple 을 배열로 저장해야할거에요. 그런 배열을 `tupleRecords` 라고 부르면, `transfer()` 할 떄, 유효하지 않은 토큰 수량을 계산 / 반영해야하는데, 이 때의 계산복잡도 *(`tupleRecords`의 각 원소를 읽고, 유효 기간이 지난 토큰 수량의 총 합을 계산)* 는 최대 `tupleRecords`의 길이 `n` 에 비례해서 `O(n)` 이 될거에요. 이더리움에서 `O(n)` 의 복잡도를 가지는 함수를 구현하는것은 불가능해요. `O(n)`만큼 반복문을 수행하면 언젠가 out of gas 가 발생할거니까요.”
kevin : 어차피 프라이빗 체인에 올리니 상관 없잖아?
4000D : !!
46
Questions?
47
Thanks
48