슭의 개발 블로그

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 회사에서 이런 거 하느라 바빠서 한동안 다른 글은 읽을 시간이 없네요. 발표는 몇 주 동안 계속할 거라서 당분간은 발표자료 만들면서 참고했던 자료들을 공유할 것 같습니다. Impossibility of distributed consensus with one faulty process 분산 환경에서 합의 알고리즘을 말할 때 빼놓을 수 없는 논문이다. 합의 알고리즘에 필요한 기본적인 속성은 크게 safety와 liveness가 있다. Safety는 잘못된 합의가 이루어지지 않는다 는 것이고, liveness는 언젠가는 합의가 반드시 이루어진다 는 것이다. 위 논문은 비동기 네트워크에서 하나의 fail-stop failure 노드만 있어도 이 합의가 이루어질 수 없다는 것을 보였다. 이를 FLP impossibility라고 부른다. Consensus in the presence of partial synchrony 첫 번째 논문이 비동기 네트워크에서 safety와 liveness를 보장하는 합의 알고리즘이 불가능하다는 FLP impossibility를 보였다. 그래서 이 논문은 partial synchronous model을 만들어 특정한 가정 아래서 safety와 liveness를 같이 보장하는 합의 알고리즘을 만들 수 있게 해줬다. Partial synchronous model은 메시지가 언젠가는 도착하는 것을 보장하지만 그 도착하는 시간이 언제인지 알 수 없는 모델이다. The Byzantine generals problem Byzantine failure라는 용어의 어원이 된 논문이다. 이...

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘 이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까? FLP impossibility 우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 consensus의 safety라고 말한다. 또한, 합의가 언젠가는 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 liveness가 보장된다고 말한다. 쉽게 풀어 말하면 safety는 "문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다"라는 것이고, liveness는 "문제없는 노드들은 반드시 합의를 한다"라는 것이다. 문제는 byzantine failure가 아닌 fail-stop failure가 하나만 있어도 safety와 liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다 . 이를 FLP impossibility 혹은 FLP theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 safety와 liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다. Liveness over Safety 비트코인 이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 nakamoto consensus라고도 불린다. Nakamoto consensus는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 ...

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. Polkadot: Vision for a Heterogeneous Multi-chain Framework Cosmos - A Network of Distributed Ledgers 블록체인이 쏟아져 나오면서 다른 블록체인과 통신을 어떻게 할 수 없을까에 대해 고민하는 사람들이 나왔다. 예를 들어 지금은 Alice의 비트코인과 Bob의 이더리움을 교환하기 위해서는 양자가 신용하는 Ted가 필요하다. Alice는 비트코인을 Bob은 이더리움을 Ted에게 보내고, 양쪽에게 받은 트랜잭션을 확인한 Ted는 Alice와 Bob에게 이더리움과 비트코인을 보내주는 식이다. 지금은 거래소가 이 역할을 해주고 있다. 하지만 trustless를 가정하고 설계된 블록체인에서 거래소는 가장 약한 고리가 된다. 그래서 이 거래소에 해당하는 역할을 블록체인으로 구성하자는 제안이 나왔고, Polkadot 과 Cosmos 가 대표적이다. How I targeted the Reddit CEO with Facebook ads to get an interview at Reddit 어떤 사람이 공개된 페이스북 프로필을 이용해서 레딧 CEO를 타겟으로 광고를 했다고 한다. 결국, 10$만에 레딧 CEO에게 광고하는 데 성공했다고 한다. 마케터들은 페이스북이 이렇게 유용하다고 생각할 것이다. 근데 사용자 입장에서 반대로 내 신원이 이 정도로 추적된다는 것인데 이런 것을 감수하고 쓸 정도로 페이스북이 매력적인 서비스인지 이해가 안 된다. 사실 사람들이 개인 정보 보호에 그다지 관심 없는 게 아닌가 싶다. To Type or Not to T...

2017년에 이어 올해 2018년까지 블록체인은 정말 시대의 대세가 됐다. 결국, 개발자 외에도 많은 사람이 블록체인을 이야기하고 있다. 그 사람들에게 블록체인이 어려운 이유를 말하라고 하면 대부분 블록체인은 단순한 기술을 넘어서 화폐이기 때문에 어렵다고 말한다. 하지만 이건 사실이 아니다. 가장 유명한 블록체인 시스템인 비트코인 이 대표적인 암호화폐 이기 때문에 사람들이 흔하게 하는 착각이다. 하지만 기술적으로 블록체인이 화폐일 이유는 없다. 블록체인을 조금 더 공부한 사람에게 물어보면 블록체인은 incentive model을 설계해야 해서 어렵다고 말한다. 블록체인에서는 사용자들의 자발적 참여를 유도하기 위한 incentive model을 설계해야 하고, 이는 결국 사람 심리의 영역이기 때문에 어렵다는 것이다. 하지만 이것도 블록체인이 어려운 근본적인 이유는 아니다. 블록체인이 어려운 이유는 블록체인이 분산환경에서 풀어야 하는 가장 어려운 문제를 풀기 때문이다. 분산 시스템은 여러 개의 노드 사이에서 메시지를 주고받으며 상태를 변화시킨다. 이때 모든 노드가 정상적인 경우만 가정할 수는 없다. 이런 시스템은 단일 노드에서 처리되는 시스템보다 문제가 발생할 확률이 늘어나기 때문이다. 하지만 현실적으로 모든 에러를 처리할 수는 없다. 그래서 일반적으로 분산 시스템은 자신이 감당할 수 있는 에러를 정의하고, 그 이외의 에러가 발생할 경우는 동작을 보장하지 않도록 설계된다. 이때 감당할 수 있는 에러의 종류를 시스템의 Failure Model이라고 부른다. 전통적으로 분산 시스템에서 Failure Model은 6개로 분류된다. 이 6 분류는 계층을 가지고 있기 때문에 더 큰 부류는 작은 부류를 포함한다. 분산 시스템은 목표로 하는 Failure Model을 설정하고 그보다 큰 부류의 failure가 발생했을 때는 처리를 포기한다. 가장 처리하기 쉬운 문제는 Fail-stop Failure Model이다. Fail-stop Failure Model...

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. C Primer Primer를 입문서라고 번역하는 게 맞는지 모르겠지만, 어쨌든 C 입문서라고 이름 붙인 문서 중에서 가장 마음에 든다. 다른 언어는 잘 추상화된 모델을 다루는 것이 중요하지만 C는 아니라고 생각한다. C는 내가 사용한 코드가 어떻게 변환되어 실행되는지 기계 단위로 이해하고 있어야 한다. 그럴 필요가 없는 상황에서는 C가 아닌 다른 언어를 써야 한다. C Is Not a Low-level Language C가 low-level 언어 는 아니라는 글이다. 전통적으로 low-level 언어는 머신에 대한 추상화 없이 기계어와 일대일 대응되는 언어를 의미한다. 당연히 이런 의미에서 C는 low-level 언어가 아니다. C는 나름의 abstract machine 을 가지고 있다. 특히 C11 이후로는 멀티 쓰레드 에 대한 개념도 abstract machine에 들어갔기 때문에 전통적인 의미에서 low-level 언어는 아니다. 그렇다고 해서 C가 다른 high-level 언어 와 같다는 의미는 아니다. 다른 high-level 언어들은 실제 기계어로 어떻게 번역되는지 몰라도 될 정도로 abstract machine을 정의한다. 하지만 C는 아니다. 사실 나는 C의 abstract machine도 기계를 몰라도 사용할 수 있을 정도로 잘 정의돼있다고 생각한다. 문제는 C를 사용하는 사람들이 실제 기계에서 어떻게 돌아가는지 고려하면서 코드를 작성한다. 이건 C언어 커뮤니티의 문제는 아니다. 사실 기계 레벨에서 어떻게 돌아가는지 고려하지 않아도 되는 프로젝트에서 C를 사용하는 것은 얻는 것에 ...

지난번 글 에서 설명했듯이 ethereum의 상태는 modified Merkle Patricia Trie(a.k.a. MPT)에 저장된다. Ethererum에서 값은 nonce, balance 등 account의 상태고, 그 키는 account의 주소다. 이 Account의 주소는 160bit이기 때문에, MPT의 root에서부터 40 nibble 의 경로를 타고 가면 account의 상태가 나와야 한다. 하지만 실제로 ethereum의 상태가 저장된 MPT에서 account의 주소를 키로 가지는 노드를 찾으면, leaf node 가 아닌 branch node 나 extension ndoe 가 나온다. 이는 ethereum이 account를 MPT에 집어넣을 때, account의 주소를 바로 키로 사용하는 것이 아니라, 주소의 keccak-256 hash를 키로 사용하기 때문이다. 즉, 40 nibble의 account 주소를 따라가는 것이 아니라, 64 nibble의 hash를 따라가야 원하는 account를 찾을 수 있다. 이렇게 account의 주소를 바로 경로로 사용하는 것이 아니라, 주소의 hash를 경로로 사용하는 것을 ethereum은 secure tree 라고 부른다. Secure tree 에 대해 자세히 설명하기 전에 ethereum이 사용하는 MPT에 대해서 더 알아야할 것이 있다. Ethereum에 있는 MPT는 state trie만이 아니다. Ethereum은 총 네 종류의 MPT가 있다. 첫 번째는 state trie다. 여기에는 ethereum의 account 정보가 저장된다. 여기서 account 정보는 account의 nonce, balance, storage root의 hash, code의 hash다. 만약 계정이 smart contract라면 storage root에는 smart contract의 state를 가지는 MPT의 root가 저장되고, code에는 evm bytecode의 hash 값이 저장된다. 두 번째는...

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. Why would i use @rustlang over C++? Convince me. until now I don't see any reason for me to switch #rustlang — Moustapha Saad (@MoustaphaSaad) 2018년 5월 1일 3개월 전까지 C++을 쓰다가 최근에 회사를 옮기면서 Rust를 쓰고 있다. 개인적으로 느끼기에 Rust가 C++에 비해 가지는 가장 큰 장점은 cargo 라고 생각한다. Cargo 덕분에 C++에 비해서 의존성 관리를 매우 쉽게 할 수 있다. 물론 최근에 나온 언어들은 대부분 패키지 매니저를 가지고 있다. 하지만 그들은 대부분 C++보다 추상화된 메모리 관리를 가정하고 있기 때문에 C++의 대안이 되지는 못한다고 생각한다. 흔히들 말하는 Rust의 메모리 안전성은 딱히 큰 장점으로 느껴지지 않는다. Modern C++에서 제공하는 기능들을 잘 사용하면 C++에서도 메모리 이슈로 문제가 될 일은 많지 않다. 물론 C++을 쓸 때는 잘 써야 한다는 전제가 있어서 Rust를 쓸 때는 때 걱정을 덜 해도 된다는 것은 큰 장점이다. 하지만 Rust가 메모리 안전성은 보장해도 false alarm을 발생하는 일도 자주 있다. Non-lexical lifetime 같은 것이 구현되면서 false alarm을 줄이고 있지만, 아직은 종종 false alarm 때문에 실제로 안전한 코드를 보기 안 좋게 수정해야 하는 경우도 있기 때문에 어느 쪽이 더 좋은지는 취향의 문제라고 생각한다. Date format by count...

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...

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...