새로운 Smart Contract 프로그래밍 언어 만들기 — VM(0)

안녕하세요. KOA 프로젝트에서 VM 컴포넌트를 맡고 있는 김성재입니다. VM(1) 글이 먼저 쓰여졌지만 아무래도 기존 Smart Contract언어가 어떤식으로 만들어 지는지를 보아야 이해에 훨씬 도움이 되기 때문에 번외 느낌으로 쓰게 되었습니다.

• koa 프로젝트
• koa-playground
• 이전 포스팅 : 새로운 Smart Contract 프로그래밍 언어 만들기 — koa 소개, 목적
• 이전 포스팅 : 새로운 Smart Contract 프로그래밍 언어 만들기 — Lexer
• 이전 포스팅 : 새로운 Smart Contract 프로그래밍 언어 만들기 — Parser
• 이전 포스팅 : 새로운 Smart Contract 프로그래밍 언어 만들기 — Compiler
• 다음 포스팅 : 새로운 Smart Contract 프로그래밍 언어 만들기 — VM(1)

이번 글에서는 비트코인 스크립트와 EVM에 대해 알아볼 것입니다. 더 정확하게는 solidity 언어 자체가 아닌solidity를 실행가능하게 하는 EVM(Ethereum Virtual Machine)에 대해 알아보겠습니다.

Bitcoin Script

비트코인은 Script 언어를 사용함으로써 UTXO를 확인하거나 Transaction을 가능케 합니다.

UTXO : Unspent Transaction Output, 잔액

스크립트의 종류에는 아래와 같이 여러종류가 있습니다.

• P2PKH : Pay-to-Public-Key-Hash
• P2SH : Pay-to-Script-Hash
• P2PK : Pay-to-Public-Key
• OP-RETURN
• MS : Multi-Signature

대표적으로 위와 같은 종류가 있고 Segwit soft fork가 일어난 이후에는

• P2WPKH : Pay-to-Witness-Public-Key-Hash
• P2WSH : Pay-toWitness-Script-Hash

와 같은 스크립트도 있습니다.

하지만 저 많은 것을 다 다루기에는 이 포스팅의성격과 거리가 멉니다. 그래서 이번 포스팅에서는 비트코인에서 가장 대표적인 스크립트인 P2PKH에 대해서만 알아보도록 하겠습니다.

출처 : mastering bitcoin

위 그림은 비트코인 거래를 간략하게 보여준 그림입니다. 첫번째 트랜잭션에서 Joe는 Alice에게 0.1BTC를 보냅니다. 이 시점에서 Alice의 UTXO는 첫번째 트랜잭션의 Output이 됩니다.

두번째 트랜잭션에서 Alice는 Bob에게 0.015BTC를 보냅니다. 이 시점에서 Alice는 첫 번째 트랜잭션의 Output(Alice의 UTXO)을 가져와서 쓸 만큼 쓰는것이죠. 이 시점에서 Output #0은 Bob의 UTXO입니다.

여기서 이런 생각이 들어야 합니다. “그렇다면 자신의 UTXO라는 것은 어떻게 알지?”, “다른 사람이 자신의 UTXO가 아닌 다른 사람의 UTXO에 접근하면 어떡하지?”

여기서 쓰이게 되는것이 Script입니다. Script에 쓰이게 되는 암호화 방식에는 공개키 암호화 방식이 있습니다. 이 암호화에는 개인키(Private-Key), 공개키(Public-Key)가 쓰입니다. 개인키는 사용자 본인만이 가지고 있어야 하는 키이며 공개키는 본인 외에 다른 사람들도 가지고 있어도 되는 키 입니다.

만약 Alice의 개인키로 트랜잭션을 암호화(서명)하면 그 트랜잭션은 Alice의 공개키로만 복호화할 수 있습니다. 반대로 공개키로 함호화하면 개인키로만 복호화 할 수 있는 메커니즘을 가지고 있습니다.

이 암호화 방식을 이용해서 트랜잭션을 만들게 됩니다. 첫 번째 트랜잭션에서Alice가 Bob의 공개키로 UTXO를 암호화하면 그 UTXO는 Bob의 개인키로만 사용할 수 있게 되는 것이죠. 그런데 Bob의 개인키는 Bob만 가지고 있습니다. 그렇기 때문에 첫 번째 트랜잭션의 Output은 Bob만이 사용할 수 있는 UTXO가 되는겁니다!

즉 Alice가 Bob의 공개키로 UTXO를 암호화 합니다. 여기서 생성되는 것이 Locking Script입니다.

그리고 Bob은 자신의 UTXO를 사용하려 합니다. 여기서 생성되는 것이 Unlocking Script입니다.

비트코인에서 Locking Script는 scriptPubKey, Unlocking Script는 scriptSig라고 칭합니다.

여기서 한 번 정리하자면 이제 첫 번째 트랜잭션의Output에는 Alice가 Bob의 공개키로 암호화 한 Locking Script(scriptPubKey) 정보가 들어 있습니다. 그리고 Bob은 자신의 개인키로Unlocking Script(scriptSig)를 생성해서 해당 UTXO의 Locking Script와 비교합니다. 즉, 자신의 UTXO라는 것을 증명, 검증하게 됩니다. 이 과정이 통과하면 UTXO를 쓸 수 있고 아니면 사용하지 못합니다!

자 그러면 이 Script를 어떤식으로 비교한다는 것일까요? 비트코인 내부적으로 어떤식으로 Script를 실행하는 것일까요? 방식은 아래와 같습니다.

출처 : mastering bitcoin

2 + 3 = 5 라는 간단한 연산으로 예시를 들어보겠습니다. 일반적으로 우리는 위와 같은 infix 수식 표기법을 사용합니다. 하지만 비트코인은 위와같이 postfix 수식 표기법을 사용하여 연산자보다 피연산자들이 우선적으로 위치하게 됩니다. 즉 2 3 + 5 = 이라는 익숙하지 않은 표기를 사용하는 것이죠.

2 3 + 5 = 라는 수식이 있고 이것을 미리 정해놓은 예약어로 바꾸게 되면 위와 같이 2 3 ADD 5 EQUAL 라는 수식이 탄생하게 되는것입니다.

스크립트를 하나씩 읽으면서 Stack에 넣고 연산을 진행합니다. 2, 3을 순차적으로 Stack에 넣고 ADD를 만났습니다. 이 ADD라는 예약어는 Stack의 상위 2개 아이템을 꺼내서 더한 결과값을 Stack에 다시 넣는 에약어입니다. 이후 5를 넣고 EQUAL을 만났습니다. EQUAL은 Stack의 상위 2개 아이템을 꺼내서 비교한 후 같으면 TRUE, 아니면 FALSE를 반환합니다. 5와 5는 같으니까 결과는 TRUE가 되게 됩니다.

스크립트를 실행하는 과정은 위와같이 복잡하지 않습니다. 스크립트에 적힌대로, 하라는대로 연산을 진행시켜주면 되기 때문이죠.

자 이제 우리가 알아보기로 한 P2PKH(Pay-to-Public-Key-Hash)는 어떻게 진행될까요? 위에서 Alice는 Bob의 공개키를 이용해서 Locking Script를 만들었고 Bob은 자신의 개인키를 이용해서 Unlocking Script를 만들것입니다. 그리고 아래와 같이 이어 붙힌 후 스크립트를 실행합니다.

출처 : mastering bitcoin

실행 과정은 mastering bitcoin 그림의 도움을 받도록 하겠습니다.

위의 과정 또한 스크립트의 연산자 또는 피연산자를 하나씩 읽어가면서 실행합니다.<sig>는 자신의 UTXO임을 증명하기위해 자신의 개인키로 만든 서명값입니다. 그리고 <PubK>는 자신의 공개키이며 핵심적으로 이 두 정보를가지고 Locking Script를 해제하는 과정을 볼 수 있습니다.

그렇다면 이 Script들이 Bytecode 상으로는 어떤 형태를 띄고 있는지 알아보겠습니다.

Locking Script
DUP HASH160 <PubKHash> EQUALVERIFY CHECKSIG
76a914df3bd30160e6c6145baaf2c88a8844c13a00d1d588ac

Locking Script는 위와 같은 형태를 띄고 있습니다. 꺽새로 표시된 것은 피연산자들이고 나머지는 비트코인에서 미리 정의된 연산자입니다. 이러한 연산자들을 보통 Opcode라고 부르고 더욱 자세한 내용은 비트코인 위키 에서 확일하실 수 있습니다. 위의 Opcode는 각각 아래와 같은 Hex값을 가지고 있습니다.

• OP_DUP : 0x76
• OP_HASH160 : 0xa9
• OP_EQUALVERIFY : 0x88
• OP_CHECKSIG : 0xac

76 a9 14 df3bd30160e6c6145baaf2c88a8844c13a00d1d5 88 ac

이제 다시 Bytecode를 보면 감이 오실것이라고 생각합니다. 각각의 Opcode와 매칭되고 있습니다! 위의 14라는 것은 피연산자의 길이를 뜻하며 데이터를 Stack에 Push하기 전에 데이터의 Length를 저런식으로 넣어줍니다.

같은 방법으로 Unlocking Script도 살펴보겠습니다.

Unlocking Script
<sig> <PubK>
47304402202aa24365218510b56b8a43e265c6e7f0797d8a7a9c9334ee59b5bbb74d8ea6560220400a82a3a018afadb948aff34daa7a8936a17243600841e6fed874e4aa05fceb012103BF350D2821375158A608B51E3E898E507FE47F2D2E8C774DE4A9A7EDECF74EDA

위는 Opcode는 없고 피연산자밖에 없습니다. 즉 처음 47은 sig의 길이라는 뜻입니다.

47 304402202aa24365218510b56b8a43e265c6e7f0797d8a7a9c9334ee59b5bbb74d8ea6560220400a82a3a018afadb948aff34daa7a8936a17243600841e6fed874e4aa05fceb01
21
03BF350D2821375158A608B51E3E898E507FE47F2D2E8C774DE4A9A7EDECF74EDA

47자리를 끊고 다시 보면 21이 보이는 것을 확인할 수 있습니다. 즉 이런식으로 스크립트의 내용을 확인하고 실행하게 되는것이죠.

꽤 길었지만 VM이 하는 역할은 저런 Bytecode를 보고 알맞게 해석하여 실행시켜 주는 것입니다. 하지만 비트코인 스크립트는 결과값이 True 또는 False 밖에 없습니다. 그리고 위에서 말씀드린 스크립트를 제외하면 할 수 있는 일이 매우 제한적입니다.

Solidity : Ethereum Virtual Machine

비트코인 스크립트와는 다르게 이더리움은 많은것을 응용할 수 있는 Solidity라는 언어를 가지고 있습니다. 아직까지 Killer Application이라 할 만한 것은 없지만 유명한 크립토키티나 도박 어플리케이션 등 많은 분야에서 Dapp(Decentralized Application)이 사용되고 있습니다.

하지만 많은것을 할 수 있다는 것은 그만큼 많은것을 신경쓰고 제어해야 한다는 의미입니다. 대표적인 사례로 DAO 해킹사건이 있습니다. 간략하게 말하면DAO가 작성한 스마트 컨트랙트 코드의 결함을 이용해서 750억원 가량이 해킹당한 유명한 사건입니다. 취약점과 공격방식은 여기를 보면 자세히 설명되어 있습니다.

이런 이더리움의 스마트 컨트랙트 특징은 비트코인 스크립트와 비교해서 크게 아래와 같은 특징을 가집니다.

• 상태(State)가 존재 : input에 따라 output이 다르다.
• 반복문의 존재 : 비트코인이 튜링 불완전했다면 이더리움은 튜링 완전하다.
• Gas 체계 : 스마트 컨트랙트를 사용하려면 수수료를 지불해야 한다.

반복문을 가진다는 것은 해커가 무한루프로 네트워크에 공격을 가할 수 있다는 뜻입니다. 그리고 이더리움은 Gas라는 수수료 체계를 통해 이 문제를 해결했습니다. 이더리움 네트워크에서 어떠한 행위를 하기 위해서는 모두 Gas라는 수수료를 지불해야 합니다. 여기서 행위라는 것은 스마트 컨트랙트를 이더리움 네트워크에 배포하거나 배포된 스마트 컨트랙트를 이용하는 것, 트랜잭션을 생성하는 것 등 모든 행위를 뜻합니다. 그리고 이 모든 행위를 판단하고 Gas를 책정하는 게 바로 EVM입니다. 이 포스팅에서는 EVM이 어떤 체계를 가지고 어떻게 스마트 컨트랙트 코드를 읽는지에 대해서 알아보도록 하겠습니다.

비트코인은 스크립트를 즉시 실행하기 때문에 저장공간이 Stack 하나만 있었습니다. 그에 비해 이더리움은 Stack, Memory, Storage 라는 세 개의 저장공간이 있고 컨트랙트 외부의 데이터가 컨트랙트에 접근할 수 있게 하는 CallData라는 개념이 있습니다.

Stack

기본적으로 Stack 자료구조와 동일합니다. Stack의 한 element는 256bits이며 총 1024개의 element를 가질 수 있습니다. Stack은 memory나 storage같은 저장소가 아니라 연산을 위한 공간이기 때문에 대다수의 Opcode는 stack과 함께 상호작용하게 됩니다. 이더리움의 Opcode는 여기서 확인하실 수 있습니다.

총 사이즈가 1024이기는 하지만 local variable이 16개가 넘어가면 컴파일 에러를 뿜게 됩니다. 이에 대한 이유는 공식 레퍼런스에도 명확하게 설명되어 있지 않지만 과도한 gas비용을 방지하거나 EVM 구현상의 한계라고 생각됩니다. EVM은 변수를 사용할 때 Swap이라는 opcode를 사용합니다. 이는 Stack에 변수가 쌓이게 되면 먼저 들어온 변수를 사용하기 위에 가장 상단의 element와 Swap하기 때문입니다. 이 Swap이라는 opcode는 Swap1, Swap2 … 형식으로 총 16개가 존재합니다. 즉, 1024개의 local variable을 사용하려면 Swap opcode는 1024개 까지 존재해야 합니다.

Memory

메모리는 Stack과 같이 수직적인 자료구조가 아닌 수평적인 자료구조입니다. 흔히 “메모리를 참조한다” 라는 표현을 쓰고는 하는데 그것과 동일하게 생각하면 될 것 같습니다.

type Memory struct {
       store []byte
       lastGasCost uint64
}

위의 코드는 실제 EVM에서 memory를 구현하기 위해 사용하는 구조체입니다. 매우 직관적인 코드이며 byte 단위로 데이터를 저장합니다. Memory에 접근하기 위해서는 MSTORE/MSTORE8/MLOAD라는 Opcode를 사용하게 됩니다.

또 하나 중요한 점은 Memory는 휘발성(volatile)의 공간으로 contract가 종료되면 메모리는 contract와 함께 소멸됩니다. 메모리와 관련된 예시는 이 글의 끝에 준비해 두었습니다!

Storage

Storage는 Memory 와 다르게 영구적(persistent)인 저장소 입니다. SSTORE와 SLOAD 두 개의 Opcode로 접근이 가능하며 이 공간은 블록과 함께 저장되어서 contract가 종료되어도 사라지지 않습니다. 이는 이더리움의 소스를 사용한다는 뜻이기 때문에 Storage를 사용하게 되면 많은 gas비용이 듭니다.

Storage에 저장될 때에는 key-value 형식을 가지며 SSTORE는 Stack에서 key와 value를 꺼내서 Storage에 저장하게 됩니다.

저는 Storage라는 공간이 블록체인 상에 직접적으로 저장이 된다는 사실이 흥미로워서 코드를 간략하게 살펴보았습니다.

func opSstore(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
   loc := common.BigToHash(stack.pop())
   val := stack.pop()
   interpreter.evm.StateDB.SetState(contract.Address(), loc, common.BigToHash(val))

   interpreter.intPool.put(val)
   return nil, nil
}

key( loc )와 value를 evm.StateDB 라는 곳에 사용자의 address와 함께 SetState 하고 있습니다.

SetState 는 SetState(db Database, key, value common.Hash) 라는 구현체를 가지고 있습니다. 첫 번째 인자인 db에 key -value를 저장하는 것을 유추할 수 있습니다. 글의 주제와 벗어나고 있는 것 같지만 조금만 더 들여다 보겠습니다…!

위의 Database 라는 파라미터 타입을 조금 더 들여다 보면 아래와 같이 이더리움이 사용하는 Trie interface를 볼 수 있습니다.

// Trie is a Ethereum Merkle Trie.
type Trie interface {
   TryGet(key []byte) ([]byte, error)
   TryUpdate(key, value []byte) error
   TryDelete(key []byte) error
   Commit(onleaf trie.LeafCallback) (common.Hash, error)
   Hash() common.Hash
   NodeIterator(startKey []byte) trie.NodeIterator
   GetKey([]byte) []byte // TODO(fjl): remove this when SecureTrie is removed
   Prove(key []byte, fromLevel uint, proofDb ethdb.Putter) error
}

이 Trie interface는 odrTrie라는 구현체를 가지고 있습니다.

type odrTrie struct {
   db   *odrDatabase
   id   *TrieID
   trie *trie.Trie
}

또한 odrTrie는 Trie를 직접적으로 가지고 있는 것을 볼 수 있습니다.

// Trie is a Merkle Patricia Trie.
// The zero value is an empty trie with no database.
// Use New to create a trie that sits on top of a database.
//
// Trie is not safe for concurrent use.
type Trie struct {
   db   *Database
   root node

   // Cache generation values.
   // cachegen increases by one with each commit operation.
   // new nodes are tagged with the current generation and unloaded
   // when their generation is older than than cachegen-cachelimit.
   cachegen, cachelimit uint16
}

매우 삼천포로 빠지긴 했지만 이로써 Storage는 블록체인에 직접적으로 접근한다는 것을 알 수 있었습니다.

Calldata

Calldata는 저장소라기 보다는contract 외부에서 contract 내부로 전달하는 데이터입니다. contract 안의 특정 함수를 파라미터와 함께 실행하거나 다른 contract내부에서 다른 contract를 호출할 때 Calldata를 쓰게 됩니다.

Calldata는 Stack, Memory, Storage와 같이 저장공간이라기 보다는 contract에 접근을 하기 위한 데이터 모음집이라고 생각하면 됩니다… 근데 이렇게 애매한 설명일 때에는 코드를 보는게 가장 정확하고 빠른 방법인 것 같습니다. Calldata를 위한 Opcode는 CALLDATALOAD, CALLDATASIZE, CALLDATACOPY 등이 있습니다. 이 중 CALLDATALOAD를 살펴보자면,

func opCallDataLoad(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
   stack.push(interpreter.intPool.get().SetBytes(getDataBig(contract.Input, stack.pop(), big32)))
   return nil, nil
}

위와 같이 구현되어 있습니다. 여기서 주목할 것은 contract 파라미터이고 contract 에서 input 이라는 것을 꺼내 쓰고 있습니다. 그래서 이 파라미터 타입인 Contract 가 무엇인지 살펴 보자면

// Contract represents an ethereum contract in the state database. It contains
// the contract code, calling arguments. Contract implements ContractRef
type Contract struct {
   // CallerAddress is the result of the caller which initialised this
   // contract. However when the "call method" is delegated this value
   // needs to be initialised to that of the caller's caller.
   CallerAddress common.Address
   caller        ContractRef
   self          ContractRef

   jumpdests map[common.Hash]bitvec // Aggregated result of JUMPDEST analysis.
   analysis  bitvec                 // Locally cached result of JUMPDEST analysis

   Code     []byte
   CodeHash common.Hash
   CodeAddr *common.Address
   Input    []byte

   Gas   uint64
   value *big.Int
}

위와 같은 구조체를 가지고 있습니다. Code는 호출하는 contract의 code를 담고 있고 CALLDATALOAD에서 꺼내쓰는 Input은 호출하는 function의 정보와function의 파라미터 정보를 담고 있습니다.

즉, Calldata는 스마트 컨트랙트 호출 정보를 담고 있다고 생각하면 됩니다!

지금까지 EVM에 존재하는 여러 Space에 대해 알아보았습니다. 마지막으로 추가적으로 포스팅 하고싶은 내용을 소개하고 마치도록 하겠습니다.

Free memory pointer

Memory에 대한 예시를 생각하다가 Memory와 관련하여 재미있다고 생각한 부분을 준비해 보았습니다. solidity는 코드를 시작할 때, 메모리의 첫부분을 미래의 사용처를 위해 어느정도 미리 할당해 놓습니다. 그리고 이더리움은 공식문서에서 이 공간을 Free memory pointer라고 부릅니다.

지금 당장 REMIX에 접속해서 아무 코드나 치고 컴파일 결과인 bytecode를 보면 앞자리가 0x608060405로 시작하는걸 보실 수 있습니다. 이것을 조금 더 알아보기 쉽게 Opcode로 바꾸게 되면 다음과 같습니다.

PUSH1 0x80 PUSH1 0x40 MSTORE

solidity 버전에 따라 0x80이 아닌 0x60일 수도 있습니다.

MSTORE는 Stack에 있는 element 두 개를 pop 한 후 하나는 offset, 하나는 value로 사용하게 됩니다. 즉 위의 Opcode는 메모리의 0x40위치에 0x80 를 넣겠다는 뜻입니다. 이것을 한 번 MSTORE를 구현하고 있는 코드로 알아보겠습니다.

func opMstore(pc *uint64, interpreter *EVMInterpreter, contract *Contract, memory *Memory, stack *Stack) ([]byte, error) {
   // pop value of the stack
   mStart, val := stack.pop(), stack.pop()
   memory.Set32(mStart.Uint64(), val)
   interpreter.intPool.put(mStart, val)
   return nil, nil
}

구현체 자체도 매우 심플합니다. Stack에서 mStart(offset), value를 pop 한 후 memory에 mStart부터 32bytes 크기로 value라는 값을 세팅시켜주고 있습니다.

interpreter.intPool.put(mStart, val) 은 evm에서 값을 저장시키는 임시공간이라고 생각하시면 됩니다.지금 설명하는 내용에서는 무시해도 됩니다.

0x40은 10진수로 64입니다. 즉, memory bytes의 64~96 위치에 0x80(128)을 저장하겠다는 것입니다. Memory에 접근하기 위해서는 데이터가 Memory 어디에 저장되어 있는지에 대한 정보(offset)을 알아야 합니다. 이 정보가 바로 Memory의 0x40 부분에 저장되어 있는 것입니다. 정확하게는 다음에 사용할 Memory의 offset 정보가 저장되어 있습니다. 즉 다음에 사용할 Memory는 0x80 위치에 저장되어 있다는 뜻입니다.

이 내용은 여기에서 정리된 문서로 볼 수 있습니다. 이 외에도 메모리의 초기 일부분은 약속된 공간이며 아래와 같이 정리 할 수 있습니다.

0x00 ~ 0x20 : scratch space라고 불립니다. SHA3 operation을 위해 사용되는 공간
0x20 ~ 0x40 : 위와 동일
0x40 ~ 0x60 : 다음에 사용 될(할당 예정인) Memory의 위치 정보
0x60 ~ 0x80 : dynamic memory array의 초기값

EVM은 비트코인에 굉장히 복잡합니다. 그렇기 때문에 이번 글을 쓰면서 느낀점은 글의 범위를 어느정도로 잡을지에 대해 고민이 많았습니다. 처음에는 EVM과 solidity에 대하여 가볍게 포스팅 하려고 했으나 후반부로 갈수록 의도와 다르게 글이 쓰여진 것 같습니다…! 혹시라도 본 포스팅에 대해 틀린내용이 있으면 따끔하게 피드백 해주시면 감사하겠습니다!