Modified Merkle Patricia Trie - ethereum이 상태를 저장하는 방법

이미지
Ethereum 에서 네트워크 부분을 빼고 보면, Ethereum은 하나의 state machine 이고, transaction은 ethereum의 state를 변경시키는 것이다. 이 state는 key-value pair로 표현된다. Key-value pair를 저장하는 방법은 여러 가지 있지만, ethereum에서는 state를 저장하기 위해 Modified Merkle Patricia Trie (a.k.a. MPT)라는 특수화된 방법을 사용하도록 스펙에서 정의하고 있다. MPT는 기본적으로 Patricia trie와 Merkle tree를 합친 것이다. 여기에 추가로 ethereum의 특성에 맞게 몇 가지 최적화를 했다. 따라서 MPT를 쉽게 이해하기 위해서는 Patricia trie와 Merkle tree를 아는 것이 좋다. Patricia Trie Patricia trie는 Prefix tree, radix tree, trie 등 다양한 이름으로 불리는 자료구조다. Trie는 path에 key를 집어넣어 공통된 prefix를 가지는 노드들은 같은 path를 가진다. 공통된 prefix를 찾는데 가장 빠르고, 적은 메모리로 구현할 수 있으며, 구현도 간단하다. 그래서 router 등 낮은 사양의 기계에 들어가는 routing table의 구현체로 많이 사용된다. https://commons.wikimedia.org/wiki/File:Trie_example.svg Merkle Tree Merkle tree 는 hash들의 tree다. Leaf 노드에는 데이터를 보관한다. Leaf의 부모는 leaf의 hash를 가지고, 그 부모는 자식들의 hash의 합을 다시 hash 한 값을 가진다. Merkle tree는 leaf 노드를 제외한 노드들은 전부 hash를 가지고 있기 때문에 hash tree라고도 불린다. https://commons.wikimedia.org/wiki/File:Hash_Tree.svg Merkle tr

2 phase commit

Two Phase Commit (a.k.a. 2PC)은 distributed system에서 atomic commit 을 보장하는 프로토콜이다. 2PC는 나름 많은 에러 상황을 버티고, 괜찮은 성능을 보이기 때문에 많이 사용된다. 2PC에서 노드는 한 개의 coordinator와 여러 개의 cohort로 나누어진다. Coordinator는 commit 할 transaction을 만드는 노드고, cohort들은 coordinator가 보낸 transaction을 commit 하거나 revert 한다. 2PC는 이때 fail 하지 않은 모든 cohort가 같은 상태를 유지하도록 하는 것이다. 즉, fail 하지 않은 모든 노드는 다 같이 commit 하거나 revert 한다. 이때 coordinator를 어떻게 선정할지는 2PC의 영역이 아니다. 고정된 coordinator를 계속 사용할 수도 있고, 차례대로 돌아가면서 coordinator가 될 수도 있고, 별도의 leader election을 사용하여 coordinator를 선정할 수도 있다. 2PC는 어떻게든 coordinator가 선정된 뒤의 일이다. 2PC는 이름 그대로 2가지 phase로 나누어져 있다. 첫 번째 phase는 voting phase라고 부르고, 두 번째 phase는 commit phase라고 불린다. 각 phase의 시작은 coordinator가 보내는 메시지로 시작한다. Voting phase에서 coordinator는 commit 하고 싶은 transaction을 commit 할지 말지 투표하는 요청을 cohort에게 보낸다. VOTE 메시지를 받은 cohort들은 이 transaction을 바로 commit 하지 않는다. 해당 transaction을 커밋할 수 있으면 YES 메시지를, 없으면 NO 메시지를 coordinator에게 보낸다. Voting phase에서 coordinator가 quorum 이상의 YES 메시지나 NO 메시지를 모으면 commi

2018년 17번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. The Configuration Complexity Clock Configuration을 만들다 보면 Rules engine 이나 심할 때는 DSL (Domain Specific Language)까지 만들기도 하는데, 어떨 때는 그냥 하드코딩 하는 것이 가장 적절한 방법일 수 있다는 글이다. Linus's Law given enough eyeballs, all bugs are shallow 리누스의 법칙은 위의 한 줄로 정리된다. 오픈 소스의 근간이 되는 문장이고, peer-review가 필요한 이유로도 많이 언급된다. 문제는 최근의 거대한 소프트웨어서는 버그를 발견하는 데 필요한 enough의 수가 너무 크다는 것이다. 게다가 시스템이 복잡하다면, 그 시스템을 이해하지 못한 개발자는 버그를 발견하기 위한 eyeballs 중 하나가 되지도 못한다. 그렇기 때문에 시스템을 단순하게 유지하는 것이 중요하다. Language Health 각 언어가 오픈 소스에서 얼마나 많이 사용되는지 비교해보는 사이트다. 다만, 어디까지나 오픈소스에서 얼마나 많이 커밋이 있었는지에 대한 비교이지, 얼마나 많은 사람이 사용하는지나, 클로즈드 프로젝트에서 얼마나 많이 사용하는지는 알 수 없다. An introduction to the GNU Core Utilities 리눅스에서 작업하다 보면 필요한 유틸리티 모음. 터미널에서 작업할 때 알면 좋은 것들이다. REST APIs are REST-in-Peace APIs. Long Live GraphQL. GraphQL의 장점에 관해서 쓴 글이다. 근데 여

Ethereum의 state trie pruning

이미지
Ethereum 은 현재 상태를 prefix tree 의 일종인 modified merkle patricia trie (a.k.a. MPT)로 저장한다. MPT는 state root의 hash를 계산하기 위해 state trie 전체를 볼 필요가 없이, 수정된 branch의 hash만 다시 계산하면 되기 때문에 빠르게 root hash를 찾을 수 있다. MPT를 이용하면 새로 추가되는 노드의 수도 최소화할 수 있다. 예를 들어 위의 그림에서 block N 과 block N + 1 의 차이는 A 의 오른쪽 자식의 값이 10에서 20으로 변경된 것뿐이다. 이 경우 10에서 20으로 변경된 노드의 부모 외의 다른 노드는 전부 기존의 노드를 재활용할 수 있다. 따라서 푸른색으로 그려진 3개의 노드만 새로 추가하면 된다. 그렇다면 더는 접근할 필요가 없는 노드들은 어떻게 되는가? 위의 예제에서 붉은색으로 표시된 3개의 노드는 block N + 1 에서는 필요 없는 노드다. 그렇다면 이 3개의 노드는 3개의 푸른색 노드가 추가되고 나면 바로 지워도 될까? 그랬으면 문제가 쉬웠겠지만 아쉽게도 그렇지 않다. Ethereum은 block의 finality를 보장하지 않는다. 다른 말로 언제든지 block N + 1 이 block N 으로 retract 될 수 있다는 것이다. 게다가 Web3 API 를 통해서 과거의 state에 접근하는 것도 가능하기 때문에 현재 상태에서 안 쓰이는 노드를 바로 지울 수는 없다. 그렇다고 영원히 남겨둘 수는 없다. 현재 ethereum에서 최신 state의 크기는 약 25GB 정도지만, 과거 state를 전부 저장하면 300GB를 넘어간다 . 게다가 이 크기는 점점 커질 것이기 때문에 이를 전부 저장하는 것은 현실적이지 않다. Ethereum은 접근할 수 있는 과거 state를 127개로 제한 하여 그보다 오래된 state에만 포함된 노드는 지워도 되도록 하였다. 하지만 지워도 된다는 것과 지울 수 있다는 것은 별개의 문제다.

2018년 16번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다.  보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. ISO week date 오늘이 올해의 몇 번째 주인지 정하는 기준은 말하는 사람마다 다르다. 그래서 이 요약정리 시리즈는 ISO 8601 기준으로 몇 번째 주인지 표기한다. ISO 8601에 따르면 1월 4일이 포함된 주를 그 해의 첫 번째 주로 취급한다. 다른 말로 한 주의 시작을 월요일로 봤을 때 4일 이상 포함된 첫 번째 주가 그 해의 첫 번째 주인 것이다. TextQL 머신 러닝이나 데이터 마이닝을 할 때 데이터의 경향성을 대강 파악하고 싶을 때가 있다. 이럴 때 사용되는 데이터는 보통 매우 큰 데이터이기 때문에 에디터로 열어서 보는 것은 무리가 있고, 간단하게 스크립트를 짜서 실행하게 된다. 근데 이때 하는 일은 대부분 비슷한 일이기 때문에 꽤나 귀찮은 작업이었는데, 스크립트를 짜지 않고 파일을 SQL 을 실행시켜주는 프로젝트가 있었다. 아직 사용해보지는 않아서 직접 스크립트를 짜는 것과 비교하면 어떨지는 모르겠지만 꽤 많은 사람이 쓰고 있는 것 같다. Writing 수학을 배워야 하는 이유가 사고하는 법을 익히기 위해서이듯이, 글쓰기를 배우는 이유는 무엇을 생각했는지 명확하게 하기 위해서다. 사람은 모든 것을 기억할 수 없기 때문에 자신이 생각한 것을 써서 정리해야 한다는 것이다. 게다가 글을 쓰는 것은 내가 글 쓰는 주제에 대해 나보다 모르는 독자를 가정하고 글을 쓰게 된다. 그래서 평소에는 당연하게 생각하고 넘어갔던 것들에 대해서도 한 번 더 생각하고 넘어갈 시간을 가지게 한다. How quantum computing could wreak havoc on cryptocurre

Byzantine Fault Tolerance 시스템에서 N = 3f + 1인 이유

분산환경 시스템에서는 다른 노드가 보낸 메시지가 정상적이라고 보장할 수 없다. 이때 잘못된 노드가 모두에게 틀린 메시지를 보낸다면 문제가 쉽게 풀린다. 틀린 메시지를 보내는 노드를 차단하면 된다. 하지만 일부 노드에게는 잘못된 메시지를 보내고, 일부 노드에게는 제대로 된 메시지를 보내는 경우는 문제 상황을 찾기 힘들다. 분산 시스템에서 각 노드는 다른 노드의 상태를 모르기 때문이다. 이런 식으로 일부 노드에게만 틀린 메시지를 보내는 노드를 가정하는 모델을 byzantine failure model이라고 부른다. Byzantine failure model은 네트워크에서 가장 풀기 어려운 모델임과 동시에 실제 네트워크에서 반드시 해결해야 하는 문제다. 특히 다른 노드를 신뢰할 수 없는 p2p에서는 반드시 Byzantine failure model을 가정하고 예외 상황을 처리해야 한다. 그렇다고 인증된 노드만으로 구성된 분산 시스템이라고 byzantine failure model을 가정하지 않아도 된다는 것은 아니다. 노드 자체는 신뢰할 수 있는 사람이 관리하더라도 해킹당했을 수도 있고, 버그로 잘못된 메시지를 보낼 수도 있고, 하드웨어에 문제가 발생할 수도 있다. Byzantine failure model에서도 정상적으로 돌아가는 시스템을 byzantine fault tolerance (a.k.a. BFT)라고 말한다. 당연히 BFT라고 해도 무한히 많은 faulty 노드에 대해서 동작하지는 않는다. 그래서 보통 어떤 시스템이 BFT라고 말할 때 전체 노드 중 몇 개의 노드에 문제가 있을 때까지 동작하는지를 같이 말한다. 예를 들어 N = 5f라고 말하면, 전체 노드 중 1/5가 byzantine failure일 때 정상 동작하는 시스템이고 N = 3 f + 1이라고 말하면, 전체 노드 중 1/3이 byzantine failure일 때까지는 문제없이 돌아가는 시스템을 말한다. 같은 BFT라고 한다면, 감당할 수 있는 faulty 노드의 비

2018년 15번째 주

이미지
이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 실제로 git 을 사용하면서 단순히 커맨드를 외워서 사용하는 사람들을 많이 봤다. 보통 그 이유로 크게 두 가지를 든다. 첫 번째로 git의 mental model 이 복잡하다는 것이다. git에서 변경된 내용은 크게 다음 상태 중 하나가 된다. 리모트에 존재하는 상태 로컬 브랜치에 있는 상태 브랜치에 머지되지 않았지만 add 돼 있는 상태 변경은 있지만 add 되지는 않은 상태 stash에 들어있는 상태 예전에 커밋했었지만 지금은 브랜치로 따라갈 수 없는 상태 이 중에서 내가 수정했던 내용이 어떤 상태인지 모르는 것이 헷갈리게 하는 첫 번째 이유다. 하지만 반대로 왜 이렇게 많은 상태를 가지게 됐을지 생각해보면 git을 사용하는 데 도움이 된다. 이것들은 전부 그냥 추가된 것이 아니다. 애초에 git을 처음 만든 사람은 Linus Torvalds 다. 그의 성격상 쓸모없는 것은 추가되지 않았다. 전부 제각각의 목적을 가지고 있다. 이 목적을 이해하는 것이 중요한데 아쉽게도 글로 잘 설명할 자신이 없다. 사실 이걸 이해하는 가장 빠르고 확실한 방법은 svn 을 써보는 것이다. 쓰다 보면 불편한 부분들이 자주 생기는데, git에서는 위에서 말한 것들을 이용해 이를 쉽고 빠르게 해결할 수 있다. 사람들이 git을 어려워하는 두 번째 이유는 명령어가 복잡하다는 것이다. 이건 어쩔 수 없다. 사실 git의 명령어는 규칙성 없이 만들어졌다. 그래서 외우는 수밖에 없다. 하지만 어떤 상황에서 어떤 명령어를 써야 한다는 식으로 외우면 끝이 없다. 그보다는 각 명령어가 어떤 상태와 연관이 있는지를 보는