2018의 게시물 표시

read-writers lock - 공유 자원 접근하기

Multithreaded programming에서 공유 자원에 접근할 때는 동시에 두 개 이상의 스레드가 자원을 변경시키지 않기 위해서 mutex 를 사용한다. Mutex를 사용하면 공유자원에 접근하는 스레드를 한 개로 제한하기 때문에 안전하지만, 어떤 경우는 비효율적이다. 예를 들어 여러 스레드가 공유 자원에 동시에 접근해야 하지만 그중 일부 스레드만 값을 변경하는 경우는 어떨까? 이런 경우 값을 읽기만 하는 스레드는 동시에 접근해도 상관없다. 하지만 어떤 스레드가 값을 변경하고 있으면, 다른 스레드는 공유 자원에 접근해서는 안 된다. 반대로 다른 스레드가 공유 자원에 접근하고 있는 중에는 값을 변경하는 스레드는 접근해서는 안 된다. 이때 사용하는 것이 shared-exclusive lock이라고도 하는 readers-writer lock 이다. Readers-writer lock은 여러 개의 reader와 한 개의 writer를 허용한다. 그래서 multiple-readers/single-writer lock(MRSW lock)이라고도 불린다. 즉, 이미 read lock이 잡혀있는 readers-writer lock에 read lock을 잡으면 바로 lock이 잡히고 다음 코드를 실행할 수 있지만, write lock을 잡으면, lock을 잡지 못하고 read lock이 풀릴 때까지 기다린다. 그렇다면 A thread 가 read lock을 잡고, B thread 가 write lock을 잡은 뒤 C thread 가 read lock을 잡으면 어떻게 될까? 단순하게 생각해보면 A thread 가 read lock을 잡고 있으니 B thread 의 write lock은 잡히지 못하고 기다리고, C thread 의 read lock은 잡힐 수 있기 때문에, A thread 와 C thread 의 코드가 실행될 것이다. 하지만 이런 구현의 경우 read lock이 빈번하게 잡히는 코드라면, write lock이 영원히 실행되지 못할 수도 있다. 이

Rust 읽을거리

아무 글도 안 쓴지 벌써 삼 개월이 지났다. 아무래도 너무 오래 논거 같아서 뭐라도 써야 할 것 같다. 사실 쓰고 싶은 주제는 많다. 하지만 대부분 주제가 쓰는 데 시간이 걸릴 주제라서 귀찮고, 이번에는 간단하게 Rust 를 배우는데 읽기 좋은 자료들을 정리해보도록 하겠다. Rust는 배우기 어려운 언어로 소문나 있지만, 그런 만큼 Rust 개발 커뮤니티에서 공식적으로 제공하는 문서가 많이 있다. 그중에서 입문자가 읽기 가장 좋은 문서는 RBE라고 불리는 Rust by Example 다. RBE는 자세한 설명보다는 실제 코드를 어떻게 짜야 하는지를 보여준다. RBE를 읽었으면 Rust를 배우기 위해서 Rust Book이라고 불리는 Rust Programming Language 를 반드시 읽어야 한다. Rust Book은 Second edition 이후로 Live edition으로 관리되고 있는데, 기초적인 내용부터 Rust를 사용하는 데 꼭 필요한 내용을 담고 있다. 사실 일반적으로는 RBE보다 Rust Book을 먼저 읽는 것을 추천하는데 나는 Rust Book과 RBE 중 어느 쪽을 먼저 읽을지는 취향의 문제라고 생각한다. 그다음은 Rust Standard Library 다. Rust 표준 라이브러리를 설명한 문서인데, Rust를 no_std 옵션으로 사용할 것이 아니라면, 반드시 읽어야 하는 문서다. 하지만 라이브러리 매뉴얼이라는 특성상 처음부터 순서대로 읽을 일은 거의 없고 그때그때 필요한 것이 있으면 찾아보는 경우가 대부분이다. 하지만 한 번 처음부터 제대로 읽어보는 것을 추천한다. 특히 표준 라이브러리의 소스로 가는 링크를 제공하는데, 표준 라이브러리는 사실상 Rust를 가장 잘 쓰는 사람들이 짠 코드이기 때문에, 소스코드를 읽으며 배우는 점도 많다. Rust idiom을 배우기 위해서라도 한 번 읽어보는 것이 좋다. 여기까지 읽었으면 Rust에 대한 기본적인 지식은 생겼을 것이다. 여기까지만 해도 Rust로 프로그래밍하는데 별 문제

Chromium OS 설치 후기

이미지
3줄 요약 Chromium OS에서 PlayStore 실행시키는 거 보고 반함 집에서 놀던 노트북에 설치함 포맷 거의 2주 정도 삽질을 했다. 시작은 우연히 보게 된 위의 영상 때문이었다. Chrome OS의 고질적인 문제인 쓸만한 앱이 없다는 문제를 해결하기 위해 ChromeOS에서 안드로이드 앱을 실행할 수 있게 했다는 것이다. 안 그래도 개발용 데스크톱을 새로 장만하면서, 전에 사용하던 리눅스 노트북의 용도가 단순 인터넷 서핑 정도가 됐기 때문에 망설임 없이 노트북을 포맷하고 Chrome OS의 오픈소스 버전인 Chromium OS를 설치했다. Chromium OS를 설치하면서 기대했던 것은 대략 다음과 같다. Play Store를 이용해서 노트북으로 안드로이드 게임 플레이하기 어차피 인터넷밖에 안 할 거 크롬 이외의 UI 부하를 줄여서 조금이라도 저전력으로 만들기 필요하면 개발자 모드로 터미널 사용하기 설치하는 게 쉽지는 않았다. Chromium OS는 공식적으로 바이너리 배포를 하지 않는다. Chromium OS를 사용하는 공식적인 방법은 ChromeOS가 설치된 크롬북을 구매하는 것뿐이다. 그 외의 개인적으로 사용하고 싶은 사람들은 Chromium OS를 소스에서 빌드해서 설치해야 한다. 그래서 소스를 클론 받았는데, 소스만 22GB다. 구글 프로젝트 대부분이 그렇듯이, 내부적으로 의존하고 있는 라이브러리의 소스까지 전부 포함하고 있기 때문인듯하다. 어쨌든 소스 받는 데만 하루가 걸렸다. 그리고 빌드를 시작했는데 빌드 중 중간결과물만 100GB가 넘는 크기가 나왔다. 그래도 어찌어찌 빌드하여 설치했는데, 실행이 안 된다. 찾아보니 기본적으로는 지원되는 하드웨어가 적고, 다양한 하드웨어를 지원하기 위해는 빌드 시 설정을 바꿔야 한다고 한다. 그래서 이것저것 뒤져가면서 빌드를 다시 해봤는데 여전히 실행이 안 된다. 그래서 포기하려던 찰나에 비공식적으로 Chromium OS 이미지를 배포하는 사람 이 있다는 것을 발견하고

[Rust] _는 bind하지 않는다

Rust 는 RAII idiom 을 사용하는 언어로, 객체가 소멸하는 시점에 따라 코드의 의미가 달라진다. 예를 들어 아래 코드를 보자. 이 코드는 Service 의 객체를 생성하고 종료하기를 기다리는 코드다. 이 코드는 문법적으로는 아무 문제가 없다. 하지만 종료할 때까지 Service 가 어떤 동작을 수행하기를 원했다면 이는 틀린 코드다. Service 객체는 아무 변수에도 bind 되지 않았기 때문에 이 객체는 두 번째 줄에 있는 문장이 끝나면 소멸한다. Service 객체가 wait_for_exit 이 수행될 때까지 살아있기를 원한다면, 아래와 같이 변경해야 한다. 위의 코드에서 Service 의 객체는 변수 service 에 bind 된다. 따라서 두 번째 라인이 끝나도 소멸하지 않고 wait_for_exit 이 종료되는 것을 기다리고, run 함수가 종료되면서 stack이 unwind 될 때 소멸한다. 하지만 위의 코드를 컴파일하면 server 가 unused variable이라는 경고가 보일 것이다. Rust 컴파일러는 선언된 변수가 사용되지 않으면 경고를 내기 때문이다. 그렇다면 사용하지 않는 변수의 소유권만 가지고 있고 싶을 때는 어떻게 해야 할까? 이 경우 _(underscore)로 시작하는 변수 이름을 사용하면 된다. Rust 컴파일러는 _로 시작하는 변수를 특별 취급하기 때문에, _로 시작하는 변수는 사용하지 않아도 컴파일러 경고가 나지 않는다. 그렇다면 사용하지 않는 변수에 아무런 이름을 주지 않으면 어떻게 될까? 어차피 사용하는 것이 목적이 아니고, 객체를 bind만 해서 가지고 있는 것이 목적이라면 아래 코드처럼 아무 이름 없이 _ 를 변수로 사용해도 되지 않을까? 아쉽게도 위 코드는 예상대로 동작하지 않는다. 이는 _ 가 객체의 소유권을 가지지 않기 때문이다. 이를 Rust의 용어로는 _ 는 value를 bind 하지 않는다고 말한다. 즉, 위의 코드는 Service 객체를 생성하고 소멸시킨 뒤 wait

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를 사용하는 것은 얻는 것에

Secure Tree - state trie의 키가 256 bit인 이유

지난번 글 에서 설명했듯이 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 값이 저장된다. 두 번째는

2018년 18번째 주

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

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

이미지
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에만 포함된 노드는 지워도 되도록 하였다. 하지만 지워도 된다는 것과 지울 수 있다는 것은 별개의 문제다. DB에 저장돼있는 노드 중 최근 127개의 노드에서 접근할 수 없는 노드를 찾아 지우는 것은 쉬운 문제가 아니다. 이 문제는 computer science에서 오랫동안 풀어 온 automatic memory management 문제와 비슷하다. 실제로 Vitalik Buterin 이 쓴 state tree pruning 은 reference counti

2018년 16번째 주

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

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의 명령어는 규칙성 없이 만들어졌다. 그래서 외우는 수밖에 없다. 하지만 어떤 상황에서 어떤 명령어를 써야 한다는 식으로 외우면 끝이 없다. 그보다는 각 명령어가 어떤 상태와 연관이 있는지를 보는

이더리움 샤딩

현재 이더리움이 겪고 있는 가장 큰 문제는 scalability다. 이더리움이 인기를 끌면서 트랜잭션의 양도 늘어나고 참여하고 있는 노드의 수도 늘고 있는데 PoW를 쓰는 이더리움의 특성상 초당 트랜잭션 처리 수는 늘지 못한다. 그래서 지금 이더리움 코어 개발자들이 초점을 맞춰서 개발하고 있는 것이 ethereum sharding 이다. 이더리움 샤딩을 간단히 설명하면 샤드별로 merkle patricia tree 를 만들고 그 샤드의 root들로 만들어진 merkle partricia tree의 root만을 블록체인에 올리는 것이다. 이렇게 하면 모든 miner가 모든 트랜잭션을 실행할 필요 없이 각 샤드별로 miner를 분산시켜 실행할 수 있기 때문에 전체 실행 속도가 올라간다는 내용이다. 설명은 간단하지만 구현은 간단하지 않다. 이더리움은 replay attack 을 막기 위해서 account nonce라는 것을 도입했다. 현재 state에서 account가 가지는 nonce보다 1 큰 nonce를 가지는 트랜잭션만 유효한 transaction이기 때문에, 같은 account에서 보내는 2개 이상의 트랜잭션은 동시에 처리될 수 없다. 즉, 한 account의 트랜잭션이 두 개 이상의 샤드에서 실행되면 안전하지 못하다는 것이고, account는 샤드에 종속돼야 한다. 또한, 샤드는 독립적으로 실행돼야 한다. 이 말은 한 샤드에서 실행된 트랜잭션이 다른 샤드에 영향을 주지 못 한다는 것이고, 다른 샤드에 존재하는 account 사이에서는 트랜잭션을 주고받을 수 없다는 것이다. 현재 제안된 샤드 간 통신은 receipt tree를 이용하는 것이다. 예를 들어 shard N 의 account A 에서 shard M 의 account B 로 송금하는 상황을 생각해보자. 이때 N 은 account A 의 계좌를 차감하는 transaction T1 을 실행한다. T1 은 M 의 state를 변경할 수 없기 때문에 B 에게 바로 입금할 수 없다. 따라서 T1

2018년 14번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. Why you should pick strong consistency, whenever possible 지난번 글 에서 CP와 AP 중에서 CP를 AP보다 더 선호해야 한다고 썼었다. 이렇게 생각한 사람이 나만 있는 건 아닌 것 같다. 구글 클라우드 플랫폼 팀에서 발표한 Spanner 라는 데이터베이스는 external consistency 를 보장한다. 이 포스트는 Spanner가 external consistency를 사용한 이유에 관한 글인데 제목은 strong consistency 라고 나와 있지만, 이는 strong consistency가 더 일반적으로 사용되는 용어이기 때문에 제목을 이렇게 쓴 것이지 Spanner는 언제나 최신 데이터를 읽을 것을 보장하는 external consistency를 보장한다. MantisTek GK2's Keylogger Is A Warning Against Cheap Gadgets 중국 키보드에서 키로거가 검출됐다고 한다. 개인적으로 전자제품 살 때 알리익스프레스를 많이 사용한다. 같은 사양의 제품을 10분의 1도 안 되는 가격으로 살 수 있기 때문이다. 그때마다 친구들과 이거 전부 해킹당하고 있는거 아닌가라는 농담 하면서 구매하고 몇일은 외부로 나가는 네트워크를 감시하고 그랬는데 실제로 키로거 하는 제품이 있었다. There's a biological reason you're bored at work 회사 생활에 질리고 권태감이 드는 게 생물학적으로 당연하다고 한다. 사람의 뇌는 언제나 새로운 것을 추구하도록 진화됐다고 한다. 이는 사

2018년 13번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. 이때까지 정규식에서 \d는 당연히 [0-9]와 동일하다고 생각했는데 아니였다... c#에서는 \d가 digit이라는 이름에 걸맞게 아라비안 숫자[0-9]뿐이 아닌 페르시안 숫자[۱۲۳۴۵۶۷۸۹] 등 유니코드 평면에 존재하는 모든 숫자 노테이션을 매칭함. 그래서 [0-9]와 \d는 interchangeable 하지 않음... pic.twitter.com/7i4cnzeECU — 전세계 300억개의 장비가 (@devunt) 2018년 3월 28일 정규 표현식 에서 \d 가 의미하는 것이 언어마다 다 다르다고 한다. 언어가 지원하는 문자열이 single byte문자열이면, \d가 [0-9]를 의미하는 것이 맞지만, 유니코드라면 [0-9] 이외의 문자열도 처리할 것을 고려했어야 한다. 그런 의미에서 파이썬 2의 string literal은 유니코드가 아니기 때문에 [0-9]를 처리하는 것이 이상하지 않지만, Java나 JavaScript처럼 유니코드 string literal을 지원하는 언어에서 \d를 [0-9]에만 대응하는 건 조금 안일한 결정이 아니었나 싶다 자바스크립트 디자인 패턴: RORO RORO는 Receive an Object, Return an Object의 약자로, 이름 그대로 함수에 넘기는 인자와 함수가 넘기는 인자를 object로 하자는 것이다. 함수의 인자로 object를 넘기자는 것은 꽤 옛날부터 있었던 주장이다. 최소한 내가 처음 웹 개발을 했던 2009년경에는 이미 함수의 인자로 객체를 넘기는 패턴이 유행했다. 함수의 인자로 객체를 넘겼을 때의 장점은 두 가지로 정리할 수

[보안] Alice와 Bob

네트워크 프로토콜을 설명하는 글을 읽으면 Alice 와 Bob, Carol , Eve , Mallory 등 많은 이름이 등장한다. 보통 이 이름들은 일정한 규칙을 가지고 부여되기 때문에 각 이름이 무슨 의미를 가지는지 안다면 그 프로토콜이 무엇을 어떻게 풀려고 하는지 조금은 더 이해하기 쉬워진다. 이번 글에서는 많이 네트워크 프로토콜에서 많이 사용되는 이름들이 무슨 의미를 가지는지 간략하게 정리해보았다. 네트워크 참여자 - Alice , Bob 보통 Alice 와 Bob 은 서로 통신하려는 사람을 의미한다. 이때 통신하는 메시지는 보통 암호화하여 통신하는 메시지를 의미하는데 비대칭 키를 사용할지, 대칭 키를 사용할지는 그때그때 다르다. 다자 간 통신 참여자 - Carol , Dave , Erin , Frank , Gray Carol 과 Dave 는 Alice 와 Bob 과 함께 통신에 참여하는 경우 사용된다. Carol 과 Dave 말고도 Charlie 나 David 같은 이름을 사용하기도 하지만 보통 Carol 과 Dave 를 많이 사용한다. 5명 이상의 참여자가 필요한 프로토콜을 묘사할 때는, E, F, G로 시작하는 이름들을 사용한다. 보통 Erin , Frank , Gray 등의 이름이 사용되는데 어떤 이름을 사용할지는 딱히 정해져 있지 않다. 다른 용도로 사용되는 Eve 와 Faythe , Grace 등을 제외하고 아무 이름이나 사용된다. 공격자 - Eve , Mallory , Oscar , Trudy Eve 는 보통 네트워크를 감시하여 패킷을 도청하는 공격자를 의미한다. 다만 Eve 는 능동적으로 공격을 하지는 않고 Alice 와 Bob 이 주고받는 대화를 도청하여 무슨 대화를 주고받는지 알아내는 공격자에게 붙이는 이름이다. 이름의 유래는 eavesdrop에서 나왔다. Trudy 라는 이름은 Eve 보다 조금 더 적극적인 공격자를 지칭할 때 사용된다. Alice 와 Bob 사이에 끼어들어 Alice 와 Bob 의

이더리움과 Eclipse attack

p2p 네트워크는 많은 취약점을 가지고 있는데 대표적인 것이 Eclipse attack 이다. Eclipse attack은 네트워크 전체를 공격하는 것이 아니라 목표로 하는 노드의 Routing table을 공격하여 목표로 하는 노드와 전체 네트워크 사이에 악의적인 노드를 집어넣는 공격이다. Routing table을 공격하는 방법이기 때문에 routing-table poisoning이라고도 불린다. 이더리움도 p2p 네트워크를 사용하여 메시지를 주고받기 때문에 eclipse attack이 가능하리라 생각은 했는데 지난 3월 1일 발표 된 페이퍼 에 따르면 단 2개의 노드만으로 하나의 노드를 완전히 고립시키는 것이 가능하다고 한다. 이 페이퍼는 올해 1월 진행됐던 바운티 프로그램에서 나온 문제점들을 정리한 페이퍼로 크게 세 가지 공격방법으로 나눌 수 있다. 우선 첫 번째 문제는 이해하기 위해 이더리움이 p2p 네트워크를 어떻게 관리하는지 이해해야 한다. 네트워크 그래프 구성에 가장 중요한 것은 다른 노드를 어떻게 찾을 것인가 하는 것이다. 이를 흔히 node discovery라고 하는데 이더리움은 node discovery를 위해 DHT( Distributed Hash Table ) 프로토콜 중 하나인 Kademlia 의 일부를 수정해서 사용한다. Kademlia가 다른 DHT와 다른 가장 큰 특징은 노드 간의 거리를 XOR distance로 측정한다는 것이다. XOR distance의 거리는 symmetric 하므로 노드 아이디만 알고 있으면, 노드 A가 생각하는 노드 B까지의 거리나, 노드 B가 생각하는 노드 A까지의 거리나, 노드 C가 생각하는 노드 A와 노드 B 사이의 거리가 같다. 따라서 각 노드는 자신이 알고 있는 노드 중에서 자신과 가까운 노드들과만 통신하면 적은 연결 수로도 큰 네트워크를 구성할 수 있다는 장점이 있다. Kademlia 페이퍼에는 대략 노드의 개수를 N 이라고 할 때 각 노드는 O(log(N)) 개의 연결만 유지하면 된

2018년 12번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다. 보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다. not invented here syndrome not invented here syndrome이란 말 그대로 자신이 아닌 다른 사람 혹은 다른 팀에서 개발한 물건을 배척하는 태도를 말한다. 너무나 당연하게 이런 태도는 잘못된 것이다. 사람이 필요로 하는 것은 대부분 비슷하기 때문에 이미 그것을 만든 사람이 있을 것이다. 게다가 내가 천재가 아닌 이상 더 오랜 시간 개발되고 테스트해온 다른 라이브러리가 더 안정적으로 돌아갈 것은 당연하다. 하지만 요새는 오히려 반대의 태도. 즉, 모든 라이브러리나 툴을 외부에서 가져와서 해결하려는 태도 때문에 개발이 더 느려지게 되었다. 라이브러리 혹은 프레임웍은 일반적인 문제에 대해서 해결하고자 작성됐기 때문에 간단한 문제를 써드파티 라이브러리로 해결하려고 할 때 오히려 문제가 더 커지기도 한다. 널리 쓰이는 용어는 아니지만 이를 not invented here의 반대된다는 뜻에서 invented here syndrome 이라고 부르는 사람도 있다. 결국 엔지니어링은 트레이드오프 사이에서 하나를 선택하는 것이기 때문에 직접 구현할지 써드파티 라이브러리를 사용할지 적절한 수준에서 잘 선택해야 한다. 조직문화와 리더십을 일치시키지 마라 회사 경영에서 추구하는 바를 크게 성과 지향과 관계 지향으로 나눴을 때 어느 쪽을 추구할 것인지에 대해서 조직이 추구하는 방향과 리더가 추구하는 방향을 일치시키지 말라는 글이다. 상식적으로는 리더가 성과 지향일 경우 조직 문화도 성과 지향적이어야 높은 성과를 내기 쉽고, 리더가 관계 지향일 때는 조직도 관계 지향적이어야 회사가 원활하

이 블로그의 인기 게시물

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

RAII는 무엇인가

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

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

[Web] SpeechSynthesis - TTS API