Skewed Merkle Tree

이미지
지난번 글 에서 설명했듯이 이더리움 은 Modified Merkle Patricia Trie 를 4가지 용도로 사용한다. 이 중 State Trie와 Storage Trie는 변경되는 데이터를 효율적으로 저장하고 검증하기 위해서 사용된다. 하지만 Transaction Trie와 Receipts Trie는 변경되는 데이터가 대상이 아니다. 이 두 trie는 하나의 블록에서 사용된 트랜잭션과 그에 의해 생성된 receipt의 검증을 위해서만 사용되는 휘발성 데이터다. 이더리움이 두 가지 목적을 위해 같은 데이터 구조를 사용하는 이유는 같은 구현을 공유하기 위해서였다. 하지만 목적이 다르기 때문에 Transaction Trie나 Receipts Trie를 생성하는데 최적화된 코드는 State Trie나 Storage Trie를 생성하는데 필요한 코드와 다르다. 실제로 Parity 는 각각의 용도로 다른 코드를 사용한다. 그렇다면 Transaction Trie나 Receipts Trie를 위해 애초에 같은 Trie를 사용할 이유가 없지 않았을까? 현재 코드박스에서 개발하고 있는 코드체인의 transactions_root와 invoices_root는 이런 고민이 반영됐다. 그래서 UTXO를 저장하는 Merkle Patricia Trie 와는 다른 구현을 사용하기로 결정했다. 그렇다면 transactions_root와 invoices_root에 필요한 특성은 무엇이 있을까? 최소한의 필요조건은 데이터를 검증할 수 있어야 한다는 것이다. 이 검증은 단순히 데이터셋을 검증할 뿐 아니라 데이터의 순서도 일치하는지 확인해야 한다. 여기까지가 이더리움을 비롯한 일반적인 블록체인에서 필요한 특성이다. 코드체인에서는 여기에 몇 가지 요구사항이 더 들어갔다. 우선 구현이 간단해야 한다. 간단해야 한다는 것은 코드가 단순하다는 것뿐 아니라 메모리 사용량이 적고, 실행하는데 시간이 적게 걸려야 한다는 것을 의미한다. 이는 코드체인이 라이트 클라이언트를 고려하고 있기 때문이다...

2018년 22번재 주 - P2P Network

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 지난주 에 이어 이번 주는 P2P를 주제로 발표 했다. 이번에도 발표자료를 만들면서 참고한 자료를 공유하도록 하겠다. Chord: a scalable peer-to-peer lookup protocol for internet applications Tapestry: A Resilient Global-scale Overlay for Service Deployment Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems A Scalable Content-Addressable Network P2P 네트워크 중에서도 네트워크 토폴로지가 특정한 규칙에 의해서 구성되는 네트워크를 structured 네트워크라고 말한다. Structured network는 unstructured network에 비해 특정 노드에 부하가 걸리거나 의존하는 것을 방지하면서 잘 분산된 네트워크를 구성할 수 있다. 위의 4 논문은 각기 Chord , Tapestry , Pastry , Content Addressable Network (a.k.a. CAN)라는 대표적인 structured 네트워크 오버레이를 제시하는 논문이다. Kademlia: A Peer-to-Peer Information System Based on the XOR Metric Kademlia는 위의 네 논문을 개선하는 네트워크 오버레이를 제시한다. BitTorrent , eDonkey , 이더리움 등 많은 P2P 시스템이 kademl...

2018년 21번째 주 - Consensus algorithm

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 회사에서 이런 거 하느라 바빠서 한동안 다른 글은 읽을 시간이 없네요. 발표는 몇 주 동안 계속할 거라서 당분간은 발표자료 만들면서 참고했던 자료들을 공유할 것 같습니다. 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라는 용어의 어원이 된 논문이다. 이...

Safety & Liveness - FLP impossibility으로 보는 블록체인

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘 이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까? 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는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 ...

2018년 20번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 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...

Byzantine Failure - 블록체인 개발이 어려운 이유

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

2018년 19번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 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를 사용하는 것은 얻는 것에 ...

이 블로그의 인기 게시물

USB 2.0 케이블의 내부 구조

[C++] enum class - 안전하고 쓰기 쉬운 enum

Log Aggregator 비교 - Scribe, Flume, Fluentd, logstash

[Web] SpeechSynthesis - TTS API

[Python] cache 데코레이터로 최적화하기