Plasma ERC721 implementation (Loomnetwork)
Loom network는 온라인 게임, 소셜 앱 들을 구동시키는 dappchain 을 제공하는 플랫폼 입니다. 기존 이더리움 메인넷의 스케일링 문제를 해결한, 일종의 플라즈마 체인인 dappchain 은 현재 베타버전 SDK 제공을 앞두고 있고, DelegateCall, CryptoZombies, EthFiddle, SolidityX 등 적지 않은 사용자를 확보한 제품들을 이미 선보였습니다.
기존에 제시된 스케일링 솔루션인 Plasma 를 개선한 Plasma Cash 가 발표되었고, 다양한 벤더들이 이를 구현하고 있습니다. 이번 글에서는 Plasma Cash 와 Loomnetwork 가 구현한 Plasma-ERC721 를 설명하고자 합니다.
플라즈마의 문제점
기존의 플라즈마 체인의 참여자들은 블록의 유효성을 검증하기 위하여 블록의 모든 데이터를 받아야 했습니다. TPS를 극도로 높이기 위한 솔루션으로서 플라즈마는 블록, 트랜잭션 정보들이 끊임없이 생산될 것인데 이는 저장 공간도, 통신 대여폭도 많이 잡아먹는 시스템일 것입니다.
사실 참여자들이 블록의 모든 데이터를 가져야하는 full node 여야만 하는 이유는 자신들의 UTXO가 invalid하게 사용되지 않음을 검증해야하기 때문입니다. UTXO가 double spending 되지 않았는지, 서명하지도 않았는데 해당 UTXO 를 사용하는 다른 UTXO 가 생성 되었는지 확인을 하는 과정이 기존 플라즈마에는 필요했습니다. 따라서 네트워크 참여자들은 UTXO를 서명하여 TX를 생성한 후, 해당 TX가 메인넷에 기록 되었다는 것을 확인하는 별도의 서명(Confirm signature)를 만들어야 했습니다. Confirmation 에 관한 자세한 설명은 OmiseGO에서 작성한 문서를 참조하세요.
Sparse Merkle Tree (SMT)
따라서 Plasma cash 는 기존의 Binary Merkle Tree 대신 Sparse Merkle Tree (혹은 Merkle Patricia Trie) 를 이용합니다. Sparse Merkle Tree 는 구글에서 발표한 Revocation Transparency 에서 제안되었습니다. Revocation Transparency(이하 RT)는 Certificate Transparency(이하 CT)와 유사한 Merkle Tree 입니다.
CT는 Certificate Authority 의 행위를 모니터링하는 방법을 제안합니다. 이는 CA 가 도메인 소유주 모르게 인증서를 발행하는 행위를 방지하고 사용자들이 올바른 인증서를 사용할 수 있는 log 를 제공합니다. Append-only merkle tree 를 사용합니다.
RT는 인증서가 취소(revoke)되었음을 증명하는 Sparse Merkle Tree(이하 SMT)를 제안합니다. 기본적인 아이디어는 각 인증서는 CA 별로 unique ID를 가지고 있기 때문에, 이 unique ID를 Merkle Tree의 index로 사용합니다. 즉 마지막 leaf 노드들이 있는 배열은 대부분 null 이고 unique ID가 존재하는 부분만 각 인증서의 정보 — revoked or not — 를 가집니다.
이 때 SMT의 level을 h 이라고 한다면 proof 는 최대 h * 32 bytes 가 됩니다. 하지만 SMT의 대부분의 leaf들이 empty 이다면, 그리고 그들의 parent node의 value를 사전에 계산할 수 있다면, proof 길이를 사전에 계산한 값들을 이용하여 줄일 수 있습니다.
우선 empty leaf node는 Hash(0) 의 값을 가집니다. 이들의 부모는 Hash(Hash(0) | Hash(0)) 을 가지고, 이를 순차적으로 이용해 SMT의 각 level의 default node 의 값들을 사전에 계산할 수 있습니다. default node들의 수는 h 와 동일하기에 Merkle Path의 sibling이 default node라면 32 bytes 대신 1 bit 를 이용하여 sibling 의 값을 표현할 수 있습니다. 이러한 sibling node의 수는 SMT의 level h 과 동일하기 때문에 h bits 이용하여 SMT의 proof를 개선할 수 있습니다. Loomnetwork의 Plasma-ERC721에서는 이 h bits를 proof bits라고 부릅니다.
이로 인해 SMT의 proof 는 worst case일 때 h bits + h * 32 bytes 가 되지만, practical 하게는 h bits + O(log N) * 32 bytes (where N is # of non-default hash values, log N ≤ h) 정도의 길이를 가집니다. RT 에서는 h=256 을 제안하였지만 Loomnetwork Plasma ERC721 에선 h=64 를 사용합니다.
따라서 Plasma Cash 참여자는 t 블록동안 자신의 UTXO가 invalid 하게 블록에 포함되었는지 아닌지 알기 위하여 O(t * h) bytes 정도의 proof 만 알고있으면 충분합니다(non-inclusion / non-membership proof). 이는 토큰의 전송 기록이 SMT의 유일한 txindex(token ID) 에 기록되기 때문에 한 블록 안에서 한 토큰이 두 번 이상 전송될 수 없는 조건 때문입니다.
물론 t 는 선형적으로 증가하기 때문에 플라즈마 블록이 오랫동안 쌓일 경우 proof 의 크기가 커질 수 있습니다. 현실적으로 이더리움이 약 15초의 블록 타임을 가지기 때문에 30일 동안 172,800개의 블록이 쌓입니다. 플라즈마의 블록 타임 또한 이더리움의 블록 타임을 upper bound로 가지기 때문에 30일 동안 non-membership proof는 대략적으로 최대 172,800 * 64 bytes = 10.54 MBytes 의 크기를 가집니다.
ERC721
Loomnetwork의 plasma-erc721는 ERC721 토큰을 플라즈마 체인에 deposit 하여 참가하고, 해당 코인을 전송, withdrawal 하는 플라즈마 컨트랙, 클라이언트를 구현하였습니다. ERC721는 하나의 토큰 컨트랙에서 서로 가치가 동일하지 않은(Non-fungible) 토큰들을 정의합니다. openzeppelin-solidity는 ERC721Basic, ERC721, ERC721BasicToken, ERC721Token, ERC721Receiver 컨트랙들을 구현하였는데 상세 기능은 다음과 같습니다.
- ERC721Basic: 토큰을 전송하기 위한 기본적인 기능들을 정의합니다. ERC20과 유사하게
transfer,approve,transferFrom함수를 가집니다. 뿐만아니라 ERC20에서는 없었던 기능이지만 ERC223 에서 추가된 기능인 컨트랙이 토큰을 받은 후 수행할 로직을 정의할 수 있는 함수(ERC223.tokenFallback)를 동일하게 가지고있습니다. ERC721Receiver 가 토큰을 받았을 때 특정 함수를 호출할 수 있도록 강제하는 기능을 ERC721의safeTransferFrom함수가 제공합니다. - ERC721: ERC721Basic 을 상속하며, 토큰 소유주가 가지고있는 토큰들을 조회하거나, 전체 토큰들을 조회하는 기능을 가지고 있습니다. (enumerable) 또한 각 토큰별로 metadata URI를 가질 수 있습니다.
- ERC721BasicToken, ERC721Token: 각각 ERC721Basic, ERC721 를 구현합니다.
- ERC721Receiver: 컨트랙이
safeTransfer를 통해 토큰을 전달받았을 때onERC721Received함수를 실행합니다.onERC721Received의 반환값은 항상ERC721_RECEIVED이어야합니다.
Plasma ERC721 컨트랙 또한 ERC721Receiver를 상속하였습니다.
Plasma RootChain Contract
RootChain 컨트랙에서 사용하는 자료형들은 다음과 같습니다.
TX: 플라즈마의 토큰은 모두 Unique Token ID를 가지기 때문에 소유주가 변경된 (transfer) 블록만 참조하면 됩니다.Coin: ERC721 토큰을 의미하는 코인 자료형입니다. ERC721 토큰을 deposit 할 때 마다Coin이 생성되며,slot이라는 unique coin ID를 아래와 같이 계산합니다. (token ID는Coin.uid에 저장됩니다.)
uint64 slot = uint64(bytes8(keccak256(abi.encodePacked(numCoins, msg.sender, from))));State:Coin이 가질 수 있는 상태는 plasma chain 내부에Depositted되어 있거나, 소유주가Exitting하여 challenge period 에 들어가거나, challenge period가 끝나 해당 토큰을 메인넷에서 받을 수 있는Exited상태를 가집니다.Challenged상태는challengeBefore함수가 실행된 이후의 값입니다. 이는 Challenge 항목에서 자세히 다룹니다.Challenge: 특정Coin에 대한 Challenge 정보를 가집니다.State.Challenged와 동일하게challengeBefore함수와 함께 사용됩니다. 기존의 OmiseGO 구현체에선 challenge 증거가 올바르다면 곧바로 exitor를 slash하였기에 challenge를 굳이 컨트랙트 상태로 기록할 필요가 없었습니다. 자세한 차이는 Challenge항목에서 다룹니다.Exit:startExit함수를 통해 플라즈마 체인의Coin을 꺼낼 때 사용됩니다.
Deposit
기존의 플라즈마 RootChain 컨트랙에서는 이더가 deposit 되었을 때 deposit block 을 생성합니다. ERC721Receiver 의 onERC721Received 함수가 동일한 기능을 수행합니다.
Bond
Exit 혹은 challenge를 시도하기 위해선 0.1 Ether의 bond를 지불해야합니다. Exit이 올바르게 finalized 된다면 bond는 다시 exitor에게 돌아갑니다. 만약 문제가 있어 challenge가 발생하여 challenge가 성공할 경우 exitor의 bond를 challenger에게 전달합니다. 그 반대로 challenge가 실패할 경우 challenger의 bond를 exitor에게 전달합니다(slashBond(from, to)).
Exit
TX 가 이전 블록만 참조하기 때문에 Exit 또한 단순하게 꺼낼 토큰이 존재하는 블록 넘버와 해당 TX가 참조하는 이전 블록 넘버만 알면 됩니다. 따라서 TX1 ← TX2 일 때, startExit 함수의 인자로 TX1, TX2 를 전달하며, RootChain 컨트랙이 TX2 의 소유주에게 토큰을 전달합니다.
이 때 TX1 을 prevTX, TX2 를 exittingTX 라고 부릅니다. 그리고 해당 Exit에 대해 Challenge 할 때 사용된 증거로서의 TX를 challengeTX라고 부릅니다.
Challenge
Plasma Cash Simple Spec 에서 정의한 Challenge 는 3가지 경우에 따라 나뉩니다. 앞의 두 경우는 challenge 즉시 exitor의 bond를 slash할 수 있지만, 마지막 경우(Exit with invalid history challenge)는 exitor가 증거를 다시 제출하여 challenge에 대한 challenge를 할 수 있습니다. Challenge 성공 여부를 결정하기 위하여 비동기적인 2번의 행위가 필요하기 때문에 RootChain 컨트랙에서 challenge에 관한 정보를 저장합니다.
1.
이 때 3←4 이기 때문에 3 은 이미 사용 되었고(Spent), Exit TX 에서 2←3 을 이용해 Exit 하려고 하기 때문에, 이미 사용된 3 를 Exit 하려는 경우입니다. 3이 사용되었음을 증명하기 위해 3←4 가 필요합니다. 따라서 4를 challengeTX 로 이용하여 RootChain 컨트랙의 challengeAfter 함수를 이용하여 challenge 할 수 있습니다. Challenge가 성공한다면 3의 State는 Depositted가 되고, exit을 위해 지불했던 bond는 challenger에게 돌아갑니다. 함수명이 challengeAfter 인 이유는 challengeTX(4)가 exittingTX (3)이후에 있기 때문입니다.
이 경우 Plasma Operator가 invalid block 을 생성하지 않았습니다. 다만 3←4 proof를 Operator가 전파하지 않았을 경우 (block withholding) 3의 소유주는 3←4 임을 증명하지 못한 상태에서 exit을 실행할 수 있습니다. Simple Spec 에선 위 공격에 대한 명확한 해결책을 제시하지 않습니다. (Recovery mechanism을 도입하자거나 challenge할 때 해당 proof가 이더리움을 통해 전파되기 때문에 block withholding했다는 사실을 숨길 수 없다고는 합니다..)
2.
2←3, 2←4 인 토큰 전송이 모두 블록에 포함된 경우입니다. 이 때 2는 double spent 되었습니다. 만약 2←4를 Exit하려고 한다면, 3 를 challengeTX 로 이용하여 challengeBetween 할 수 있습니다. 이 때 4 를 포함하는 블록은 Plasma Operator가 double spending을 허용하는 invalid block을 만든 경우입니다.
3.
2를 소모하지 않아 2←3이 존재하지 않는 상태에서 Operator가 3←4←5를 만든 경우입니다. 이 경우 3이 담긴 블록은 2←3이 아니기 때문에 invalid 합니다. 갑자기 생긴 3으로 인해 해당 토큰은 2의 소유주에서 5의 소유주에게 넘어갔습니다. exit을 위해선 직전 tx의 정보만 필요하기 때문에 4←5를 이용하여 올바르게 startExit할 수 있습니다.
이 경우 해당 토큰이 2 이후 사용되지 않았음을 증명하기 위하여 1←2을 이용하여 challengeBefore 할 수 있습니다. 는 해당 토큰의 가장 마지막 TX는 2라는 것을 의미합니다. 따라서 exitor가 2←3을 증거로 제시할 수 없다면 해당 challenge는 성공이고, 그렇지 않다면 challenge는 실패하게 됩니다. exitor가 2←3을 증명할 수 있다면, responseChallengeBefore 함수를 실행합니다. 위 두 경우엔 challenge 즉시 exitor의 bond를 삭감하고, 해당 TX의 상태를 Exitting에서 Deposited로 바꾸지만, challengeBefore의 경우 exitor의 대답을 기다리기 위하여 TX는 Challenged 상태를 가집니다.
Merkle Proof in SMT
SMT의 merkle proof는 proof bits(64 bits)와 merkle path에 속하는 node의 hash들로 이루어져있습니다. SMT 컨트랙은 생성자와 2개의 public 함수로 이루어져있습니다.
우선 컨트랙이 생성될 때 SMT의 각 level의 default hash value를 계산합니다. Depth가 64이기 때문에 64번의 반복적인 concatenation — hash 를 수행합니다.
checkMembership함수가 root, proof 를 이용하여 특정 leaf가 해당 SMT에 속하는지 판별합니다. 이를 위해서 getRoot함수를 이용합니다. getRoot는 leaf와 proof로 부터 root를 계산합니다.
8번 라인에서 proof의 앞 8바이트(64비트)를 읽어 proofBits에 저장합니다. 그리고 10번 라인의 반복문에서 가장 먼저 proofBits 의 LSB를 읽어 default node인지 그렇지 않은지 판별합니다. 만약 default node라면 해당 level의 default hash를 생성자 단계에서 계산한 값에서 읽습니다. 그렇지 않다면 proof에서 32 바이트를 읽어읽습니다.
해당 level의 hash를 읽어 proofElement에 저장한 후 기존의 computedHash와 proofElement를 concatenate — hash 합니다. 이 때 해당 leaf의 index를 이용해 left child인지 right child인지 구별하여 좌우를 구분하여 concatenate합니다.
Concatenation에 사용된 abi.encodePacked 는 solidity에서 함수 인자를 인코딩하는 방법입니다. 2개의 bytes32를 abi.encodePacked 하는 것은 두 32 bytes를 붙여 하나의 64 bytes를 생성합니다. (인자가 dynamic type일 경우 복잡하게 인코딩 됩니다. 자세한 내용은 solidity document를 참조하세요.)
트리의 한 level에 대한 계산을 완료한 후 proofBits와 index를 2로 나누어 그 다음 level의 값들로 갱신합니다. proofBits는 오른쪽으로 1bit shift하는 것이고 index는 parent node의 index를 의미합니다.
References
github) ethereum/EIPs: ERC-721 Non-Fungible Token Standard
github) OpenZeppelin/openzeppelin-solidity: ERC721 contracts
github) loomnetwork/plasma-erc721
github) omisego/research: no-confirmations
ethresearch) Plasma Cash: Plasma with much less per-user data checking
ethresearch) Loom Network: Plasma Cash for ERC721 Tokens
medium) Plasma Cash Simple Spec
paper) Revocation Transparency — Ben Laurie
video) Vitalik explains RSA accumulators to Karl
