2018-08-09

[Rust] _는 bind하지 않는다

RustRAII 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_for_exit 함수를 실행하는 service_run1.rs와 같은 코드다.

사실 이는 처음부터 의도된 동작은 아니었다. 2013년에 _에 넣은 값이 바로 drop 된다는 것이 버그로 보고됐고, _를 일반적인 변수와 같이 bind 하도록 고치자는 제안도 있었다. 사실, bind 하는 것이 더 직관적이고 일반적인 접근 방법이다. 하지만, Rust 개발자들은 _의 의미를 bind 하지 않는 것으로 스펙에 규정했다. 이는 어떤 값을 받아서 bind 하지 않는 방법이 기존에 존재하지 않았기 때문이다.

값을 bind 하지 않는 _의 특성은 다음과 같은 경우에 유용하게 사용된다. 위 코드는 어떤 tuple을 받아서 Option<A>를 먼저 사용하고, 그 뒤 B를 사용한다. 만약 _가 값을 bind 하였다면, 네 번째 줄과 다섯 번째 줄에서 B가 move 되었을 것이다. 따라서 여덟 번째 줄은 이미 move 된 값을 사용하였다는 경고와 함께 컴파일되지 않았을 것이다. 하지만 _는 값을 bind 하지 않기 때문에 위의 코드는 성공적으로 컴파일된다.

여기서 _로 받은 값을 statement가 끝난 뒤 drop 하는 것이 아닌 값을 bind 하지 않는 것으로 정의했다는 것이 중요하다. 위의 service_run4.rs 예제에서 Service 객체가 drop 된 것은 temporary value를 bind 하지 않았기 때문이지 _가 값을 drop 시키기 때문이 아니다. 만약 _가 값을 drop 한다면, non_bind.rs 예제에서 match 문이 끝난 뒤 B가 drop 되기 때문에 여덟 번째 줄에서 B를 사용할 수 없었을 것이다.

개인적으로 이것 때문에 발생한 버그가 Rust를 사용하면서 겪었던 버그 중 해결에 가장 오랜 시간이 걸린 버그였다. 현재 개발 중인 CodeChain은 멀티스레드 프로그램이기 때문에 main thread에서 여러 개의 서비스를 생성하고 각 서비스는 종료될 때까지 자신이 해야 할 일을 한다. 이때 대부분 서비스는 자기 완결적인 일을 하므로 외부에서 사용하지 않고 객체를 유지하기만 하면 된다. 따라서 변수의 이름을 _로 사용해도, 컴파일러 입장에서는 틀린 코드가 아니기 때문에 성공적으로 컴파일된다. 게다가 다른 언어에서는 _를 변수로 사용하는 것이 아무 문제 없기 때문에 코드를 읽어도 의심 없이 넘어갔었다.

이런 부류의 버그는 모르고 보면 잡기 어려운 문제지만, 알면 매우 쉬운 문제다. 하지만 Rust 공식 문서인 “The Rust Programming Language”에서도 “However, using the underscore by itself doesn’t ever bind to the value. Listing 18-22 will compile without any errors because s doesn’t get moved into _.”라고 단 두 줄 나오고 넘어가기 때문에 Rust의 _는 값을 bind 하지 않는다는 것을 모르기 쉽다. 그래서 앞으로 Rust를 쓰는 사람이 같은 버그를 만나지 않았으면 하는 마음으로 이 글을 쓴다.

2018-06-15

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에 필요한 특성은 무엇이 있을까?

최소한의 필요조건은 데이터를 검증할 수 있어야 한다는 것이다. 이 검증은 단순히 데이터셋을 검증할 뿐 아니라 데이터의 순서도 일치하는지 확인해야 한다. 여기까지가 이더리움을 비롯한 일반적인 블록체인에서 필요한 특성이다. 코드체인에서는 여기에 몇 가지 요구사항이 더 들어갔다.

우선 구현이 간단해야 한다. 간단해야 한다는 것은 코드가 단순하다는 것뿐 아니라 메모리 사용량이 적고, 실행하는데 시간이 적게 걸려야 한다는 것을 의미한다. 이는 코드체인이 라이트 클라이언트를 고려하고 있기 때문이다.

다음으로 전체 트랜잭션을 검증할 수 있어야 한다는 것이다. 이는 다른 블록체인에 없는 코드체인에만 존재하는 특성이다. 코드체인이 동기화를 맞추는 방법에는 Snapshot Sync가 있다. Snapshot Sync는 이력을 다 받을 필요 없이 신뢰할 수 있는 헤더 하나만 있으면 해당 블록을 받은 것과 같은 상태로 동기화되도록 하는 방법이다. 이를 위해서 하나의 헤더만으로 전체 트랜잭션을 검증할 수 있어야 한다.

마지막으로 incremental 하게 만들 수 있어야 한다. 코드체인의 transactions_root는 전체 트랜잭션 목록을 검증할 수 있어야 하기 때문에 incremental 하게 만들 수 없다면 블록이 쌓여갈수록 검증에 필요한 시간이 길어지게 된다. 이를 방지하기 위해 incremental 하게 만들 수 있어야 한다는 것이 필수적이다.

이런 조건들을 만족시키기 위해서 이더리움이 사용하는 Merkle Patricia Trie는 가장 먼저 배제됐다. 이는 전체 데이터에 대해서 incremental하게 만들 수 있지만 Trie를 구성하는데 드는 오버헤드가 컸다.

그다음으로는 전통적인 Merkle Tree를 고려했다. 하지만 이는 위의 특성 중 오버헤드가 적어야 한다는 것과 incremental 하게 만들 수 있어야 한다는 것을 만족시키지 못했다.

그래서 우리는 왼쪽으로 치우친 Skewed Merkle Tree를 사용하기로 결정했다. Skewed Merkle Tree에서는 전 블록의 root위에 현재 블록의 트랜잭션들을 이용해 새 tree를 만들어 지금까지 실행된 전체 트랜잭션 목록을 담는 해시를 빠르고 가볍게 생성할 수 있다. 즉, 전체 트랜잭션 목록을 incremental 하게 만들 수 있고, 만드는데 드는 시간과 메모리는 트랜잭션 수에 선형적으로만 비례한다. 게다가 우리가 관심있는 것은 검증을 위한 root값 뿐이기 때문에 사용하는 메모리는 트랜잭션 개수와 상관없이 상수배만큼 사용하도록 최적화할 수 있다. 실제로 코드체인에서 사용한 코드는 다음과 같이 간단하다.

물론 Skewed Merkle Tree도 만능은 아니다. Skewed Merkle Tree는 Merkle Tree의 기본적인 기능인 Merkle path를 만드는 데 비효율적이다. 따라서 Merkle path를 만들어야 하는 경우 Skewed Merkle Tree보다 고전적인 balanced Merkle Tree가 더 적절하다. 하지만 코드체인이 transactions_root와 invoices_root를 사용하는 용도를 고려해봤을 때, Merkle-proof path를 사용하지 않는다. 오로지 데이터의 검증을 위해서만 사용하기 때문에 Skewed Merkle Tree가 더 적절하다고 판단했다.

2018-06-03

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 시스템이 kademlia 방식을 이용한다. 실질적으로 P2P 네트워크에서 가장 많이 사용되는 방식이다.
Kademlia의 가장 큰 특징은 xor distance를 사용하는 것이다. Xor distance는 노드 아이디의 공통된 prefix가 길수록 가까운 노드로 판단하는 방식이다. 이 방식은 triangle inequality를 만족하며, 각 노드가 작은 라우팅 테이블만으로 전체 네트워크를 효율적으로 연결할 수 있다.
게다가 거리가 대칭적이기 때문에 TCP로 연결해야 하는 시스템에서도 사용하기 좋다.

Understanding churn in peer-to-peer networks

Churn이라는 것은 새 노드가 네트워크에 참여하거나 네트워크에서 노드가 빠져나가는 변동성을 말한다. 위 논문은 다양한 p2p 네트워크에서 네트워크 상태를 조사해서 각 네트워크가 어떤 churn을 가지는지 분석했다.
사실 churn 자체는 서비스의 종류마다 다 다를 것이다. 이 논문에서 주목할 점은 그 churn을 어떻게 분석했는지 그 방법론에 대한 것이라고 생각한다.

Low-Resource Eclipse Attacks on Ethereum’s Peer-to-Peer Network

이더리움에 가할 수 있는 eclipse attack에 관해 정리한 논문이다. 자세한 내용은 전에 쓴 적이 있으니 참고 바란다.

Eclipse Attacks on Bitcoin’s Peer-to-Peer Network

이 논문은 비트코인에서 할 수 있는 eclipse attack에 관해 정리한 논문이다. 이더리움은 2대의 머신으로 공격할 수 있었던 반면 비트코인에서는 약 400개의 머신이 필요하다. 아직 비트코인에서 이보다 적은 수로 공격할 수 있는 방법은 나오지 않았다.

BLAKE2: simpler, smaller, fast as MD5

Cryptographic hash function 중 하나인 BLAKE2를 소개하는 논문이다. SHA-3 finalist였던 blake의 개선판으로 blake보다 더 적은 메모리로 빠르게 돌아간다.

The BLAKE2 Cryptographic Hash and Message Authentication Code (MAC)

Codechain에서는 MD5SHA-1을 이용하는 일반적인 HMAC 대신에 BLAKE2를 HMAC으로 사용한다. 이와 관련하여 이론적 분석이 있을 것이라고 생각하고 보기 시작했는데, HMAC에 관한 내용은 별로 없고, BLAKE2의 알고리즘과 구현에 관한 내용이 대부분이었다.

O(1) Block Propagation

이건 내가 발표한 내용이 아니라 양준모 님의 발표에 있던 비트코인의 Graphene의 아이디어를 줬던 제안이다. 트랜잭션은 언제나 전파하는 비트코인의 특성상 대부분 트랜잭션이 이미 전파돼있을 거라고 가정하고, IBLT라는 자료구조를 이용해서 없는 트랜잭션을 빠르게 확인할 수 있다는 것이 메인 아이디어다.

Invertible Bloom Lookup Tables

이 논문이 위에서 말한 IBLT를 제시하는 논문이다.

2018-05-27

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라는 용어의 어원이 된 논문이다. 이 논문 이전 논문은 기껏해야 메시지가 드랍되는 omission failure 정도밖에 가정하지 않았다. 하지만 이 논문 이후로 악의적인 참여자에 의해 시스템이 공격당하는 경우도 고려하게 됐다.

Reaching Agreement in the Presence of Faults

어떤 시스템이 f개의 byzantine failure node가 있을 때 3f + 1개의 노드로 구성된 네트워크에서 byzantine fault tolerant(a.k.a. BFT)한 합의가 가능하다는 것을 증명한 논문이다. 3f + 1은 BFT 시스템을 구성하기 위한 최소한의 노드 수이기도 하다.

Practical Byzantine fault tolerance

위 논문은 BFT 시스템을 Network File System에서 적용했다. 내가 아는 한은 BFT 알고리즘을 인터넷 규모에서 실제로 사용하는 시스템에 적용한 최초의 논문이고, 여기서 사용된 알고리즘들이 현재 블록체인에 사용되는 BFT 계열 합의 알고리즘들의 근간이 됐다.

Blockchain Consensus Protocols in the Wild

블록체인에서 유명한 합의 알고리즘들을 partial synchronous model에서 safety와 liveness, 그리고 얼마나 많은 byzantine failure node를 버틸 수 있는지 분석했다.

Byzantine Consensus Algorithm

텐더민트에서 사용하는 합의 알고리즘에 대해서 설명한 위키 페이지다. 텐더민트는 BFT에 stake 개념을 섞어 블록체인에서 사용할 수 있도록 만들었다. 특히 여기서 말하는 Proof of Lock Change(a.k.a. PoLC) 개념은 잘 이해해두는 것이 좋다. 보통 BFT 계열 합의 알고리즘을 최적화하려는 사람들이 PoLC에서 문제가 생겨 safety와 liveness에 문제가 생긴다.

Casper the Friendly Finality Gadget

현재 이더리움에서 진행 중인 프로젝트 중 하나로 PoW로 생성된 블록체인에 safety, 블록체인 용어로는 finality를 보장하기 위한 프로토콜이다. 기본적인 방법은 텐더민트에서 사용된 개념과 유사하다. 하지만 충분한 투표를 모으지 못하면 새 블록이 생성되지 않는 텐더민트와는 다르게 캐스퍼는 finality를 보장하지 못 할뿐 블록은 계속 생성된다.

Hot-Stuff the Linear, Optimal-Resilience, One-Message BFT Devil

캐스퍼에 영향을 받아 쓰인 논문으로 캐스퍼를 더 일반화시켰다. 캐스퍼는 블록 생성과 투표와 완전 별개로 진행된다. 하지만 Hot-stuff에서는 블록의 헤더에 투표를 모은다. 다만 이 투표는 반드시 포함해야 하는 것이 아니고 투표가 없어도 블록은 생성된다.

2018-05-24

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는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면 언제든지 현재 합의된 블록을 다른 블록으로 대체할 수 있다. 이런 방식을 블록체인에서는 finality가 보장되지 않는다고 말하고 FLP impossibility에서는 liveness를 위해서 safety를 포기했다고 말한다.

Liveness를 중시하는 nakamoto consensus에서 출발한 합의 알고리즘들은 한정적인 상황에서 safety를 보장할 방법을 추가하는 방식으로 발전해갔다. 이더리움에서 구현되고 있는 Casper the Friendly Finality Gadget이 대표적이다. Casper는 기존의 PoW로 liveness를 보장하며 블록을 생성하지만 50 블록마다 투표하여 safety가 보장되는 지점을 만든다.

Safety over Liveness

이와 반대로 safety를 중시하는 합의 알고리즘도 있다. 전통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다. Cosmos에서 사용하는 Tendermint가 대표적인 safety를 보장하는 BFT 알고리즘이다.

Tendermint는 하나의 라운드가 propose, prevote, precommit 3개의 단계로 나누어진다. 이 중 prevote와 precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어진다. 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다. 하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못 하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있다. 따라서 liveness는 보장되지 않는다.

FLP impossibility가 증명했듯이 safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 liveness를 보장할 수 없다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 liveness가 보장됨을 증명한다.

비동기 네트워크 모델에서는 메시지가 전송되는 것이 보장되는 시간이 없다. 이는 메시지가 무한한 시간 후에 도착하는 것도 가정해야 하고 다시 말해서 전송한 메시지가 도착하지 않는 것을 가정해야 한다. 그렇다고 해서 정해진 시간 안에 메시지 전달이 보장되는 동기 네트워크 모델을 사용할 수는 없다. 이는 인터넷 규모의 네트워크에서는 비현실적인 가정이고, 이런 가정에서 liveness를 증명하는 것은 아무 의미 없기 때문이다. 그래서 tendermint는 정해진 시간 안에 메시지가 도달하는 것이 보장되지만 그 정해진 시간을 알 수 없다는 partial synchronous network model을 사용한다.

Partial synchronous network는 정해진 시간 내에 메시지가 도착하는 것이 보장되는 모델이다. 다만 이 정해진 시간이 무엇인지 노드는 알지 못한다. 이는 꽤나 현실적인 모델이다. 현실의 네트워크도 omission failure가 발생하지 않는 한 언젠가는 메시지가 도착하기 때문이다.

BFT 계열의 합의 알고리즘은 블록 생성을 위해 2번의 투표를 모아야 한다. 비록 partial synchronous network model에서는 언젠가 합의될 것이 보장되지만, 최악의 경우 몇번의 라운드 동안 새 블록이 생성되지 않는 경우도 생긴다. 이는 TPS 저하를 초래한다.

BFT 계열 알고리즘은 이런 문제를 해결하기 위한 방향으로 발전해왔다. 2018년 3월에 발표된 Hot-stuff이라는 프로토콜이 대표적이다. Hot-stuff에서 블록은 validator들의 투표를 포함한다. 이 투표를 commit-certificate(a.k.a. CC)이라고 한다. Hot-stuff은 기존의 BFT 계열의 알고리즘과 다르게 CC가 없는 블록도 생성될 수 있다. 그저 이 블록들은 finality가 보장되지 않을 뿐이다. 이 CC가 없는 블록들은 뒤에 CC가 있는 블록의 finality가 보장되면 그때 finality가 보장된다. 시간 당 블록 생성량을 올리기 위해서 safety를 어느 정도 포기하는 것이다.

마치며

이상으로 liveness의 극단에 있는 nakamoto consensus에서부터 safety에 극단에 있는 tendermint까지 블록체인에서 사용되는 다양한 합의 알고리즘을 알아봤다. 중요한 것은 safety와 liveness는 trade-off이지 둘 중 누군가가 더 우월한 특성은 아니라는 것이다. 자신이 구현하려는 서비스의 종류에 따라 safety와 liveness가 어느 정도 필요한지를 판단하여 알맞은 합의 알고리즘을 사용하는 블록체인을 선택해야 한다.

2018-05-20

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를 가정하고 설계된 블록체인에서 거래소는 가장 약한 고리가 된다. 그래서 이 거래소에 해당하는 역할을 블록체인으로 구성하자는 제안이 나왔고, PolkadotCosmos가 대표적이다.

How I targeted the Reddit CEO with Facebook ads to get an interview at Reddit

어떤 사람이 공개된 페이스북 프로필을 이용해서 레딧 CEO를 타겟으로 광고를 했다고 한다. 결국, 10$만에 레딧 CEO에게 광고하는 데 성공했다고 한다. 마케터들은 페이스북이 이렇게 유용하다고 생각할 것이다. 근데 사용자 입장에서 반대로 내 신원이 이 정도로 추적된다는 것인데 이런 것을 감수하고 쓸 정도로 페이스북이 매력적인 서비스인지 이해가 안 된다. 사실 사람들이 개인 정보 보호에 그다지 관심 없는 게 아닌가 싶다.

To Type or Not to Type:Quantifying Detectable Bugs in JavaScript

JavaScriptTypeScriptflow를 사용하여 정적분석을 하는 것 만으로 15%의 버그를 예방할 수 있다는 연구다.

How a Rust upgrade more than tripled the speed of my code

Parity 팀에서 지난 5월 10일에 발표한 Rust 1.26의 128 bit 정수 타입을 이용해서 실제 성능 향상을 확인했다. 이는 이더리움이 256 bit 정수와 512 bit 정수를 많이 사용하기 때문이고, 이더리움 외의 소프트웨어에서는 128 bit 정수를 쓸 일이 없으니 크게 영향 없을 수도 있다.

Sia: Simple Decentralized Storage

Sia는 블록체인을 이용하여 분산 서비스를 구축하자는 프로젝트이다. 분산 스토리지라고 해도 데이터 전체를 블록체인에 올리는 것은 비현실적이기 때문에 블록체인에는 어떤 데이터를 어떤 노드가 가졌는지에 대한 증명과 그에 대한 보상만 블록체인에 기록한다. 결국, 실제 데이터를 원하는 클라이언트에게 서비스하지 않아도 데이터를 가지고 있다는 증명만 하면 보상을 받는다. 이 문제를 oracle problem이라고 하는데 이 문제를 어떻게 풀었는지 궁금해서 찾아봤는데 아직 못 찾았다.

2018-05-18

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에서는 문제가 발생한 노드는 더 이상 상태가 변하지 않지만, 문제가 발생하기 전 상태를 돌려준다. Fail-stop Failure Model에서는 항상 요청한 메시지가 도착하고, 도착한 메시지는 정상이라고 가정하기 때문에 문제가 쉽게 풀린다. 하지만 메시지가 도착하지 않을 수 있는 현실적인 모델, 간단하게는 서버가 crash나는 상황에 대해서는 고려조차 돼있지 않기 때문에 많이 사용되지 않는다.

그래서 그 다음으로 사용되는 모델은 crash를 고려하는 Crash Failure Model이다. 이 모델에서 요청에 대해 응답을 주지 않는 노드는 언제나 crash 났다고 가정한다. 응답을 주지 않는 노드가 있을 때는 문제가 발생한 노드를 대체하는 새 노드를 실행시키는 것만으로 문제를 해결할 수 있다. 하지만 Crash Failure Model도 인터넷 스케일의 분산 시스템에서는 현실적이지 않다. 인터넷 스케일에서는 노드가 crash나는 것 이외에도 다양한 이유로 메시지가 도착하지 않을 수 있기 때문이다. 그래서 Crash Failure Model은 보통 멀티코어 프로세서에서 프로세서 간 통신이나, 한 데이터 센터 내에서 구성되는 분산 시스템에서 많이 사용된다.

인터넷 스케일에서 사용할 수 있는 가장 간단한 모델은 Omission Failure Model이다. Omission Failure Model은 일정 단위 시간 T를 정의하고 모든 메시지는 전송 후 T 시간 이내에 도착하거나 영원히 도착하지 않을 것이라고 가정한다. 이는 네트워크에서 발생하는 문제를 매우 간단하게 모델링한 것이다.

하지만 실제 네트워크에서는 이보다 복잡한 이슈가 발생한다. 메시지가 도착하는 maximum bound인 T를 정하는 것은 사실상 불가능하다. 현실적으로는 문제가 발생했을 때 메시지는 안 올 수도 있지만, 매우 늦게 도착할 수도 있다. 이런 상황을 고려한 모델을 Performance Failure Model이라고 한다. Performance Failure Model을 가정하는 분산 시스템은 메시지가 안 도착하거나 매우 늦게 도착하는 상황까지 고려해야 한다.

지금까지 설명한 문제는 전부 메시지가 도착했다면 제대로 된 메시지가 도착했다고 가정한다. 다시 말해서 지금까지 설명한 네 개의 failure model. 즉, Fail-stop Failure Model, Crash Failure Model, Omission Failure Model, Performance Failure Model에서는 일단 메시지가 도착하면 그 메시지를 믿는다. 하지만 현실적으로는 믿을 수 없는 경우가 있다. 어떤 노드에 버그가 발생하거나 하드웨어 문제로 메시지가 일부만 전송됐을 수도 있다. 최악의 경우에는 Man-in-the-middle(a.k.a. MITM) 공격 때문에 메시지가 변조될 수도 있다.

일관되게 잘못된 메시지만 보내는 노드만 있는 경우 어렵지 않게 해결된다. 하지만 어떤 메시지는 제대로 보내고 어떤 메시지는 검증 불가능한 잘못된 메시지를 보내는 경우라면 문제가 어려워진다. 이렇게 일관성 없게 잘못된 메시지를 보내는 노드를 byzantine node라고 부르고 이런 failure를 byzantine failure라고 부른다.

일반적으로 모든 byzantine failure를 처리하는 것은 어려운 일이다. 그래서 byzantine failure 중에서 검증할 수 있는 byzantine failure만을 처리겠다는 모델을 Authentication-detectable Byzantine Failure Model이라고 부른다. Authentication-detectable Byzantine Failure Model에서는 error detection scheme을 넣거나 비대칭 암호화를 하는 방식으로 문제를 해결한다. 현재 사용되는 인터넷 규모의 분산 시스템은 대부분 Authentication-detectable Byzantine Failure Model을 가정한다.

하지만 블록체인은 모든 byzantine failure를 고려하는 Byzantine Failure Model을 가정한다. 이는 분산 시스템에서 가정할 수 있는 가장 풀기 어려운 모델이다. 그래서 기존에 있던 분산 시스템은 대부분 byzantine failure를 의도적으로 무시했다. 대부분 노드가 비정상적으로 동작하거나 악의적으로 동작하거나 해킹당하여 이상한 동작을 하는 경우를 고려하지 않았다.

블록체인의 복잡한 개념들은 전부 블록체인이 Byzantine Failure Model을 사용하기 때문이다. 예를 들어 사람들이 어려워하는 incentive model은 참여자들이 자발적으로 byzantine node가 되지 않도록 하기 위한 유인을 주는 것이고, 합의 알고리즘이 복잡해지는 것도 byzantine failure를 가정하기 때문이다. 그렇다면 Byzantine Failure Model을 사용하지 않으면 문제가 단순해지지 않을까?

아쉽게도 이는 불가능하다. 블록체인은 자발적으로 참여하는 탈중앙화된 노드로 구성된 네트워크이기 때문이다. 탈중앙화된 네트워크에서 byzantine node를 발생시키는 이유는 다양하다. 가장 흔한 경우는 악의적인 사용자들이 있다. 단순한 취미로 혹은 경제적인 이유로 혹은 개인적인 원한으로 시스템을 공격하는 사례는 많이 있다. 노드로 참여하는 것이 자유롭지 않은 기존 시스템에서는 보통 DoS 공격을 한다. 하지만 참여가 자유로운 블록체인에서는 byzantine node가 되어 일관성 없는 동작으로 공격하는 것이 더 효과적이다.

악의가 없더라도 게으른 사용자들도 byzantine node가 된다. 중앙화된 분산 시스템에서는 시스템 업그레이드가 빠르고 쉽다. 중앙 관리자가 시스템을 전부 업그레이드하면 끝나기 때문이다. 하지만 탈중앙화된 네트워크에서는 그렇지 않다. 일부 노드는 업그레이드해도 게으른 사용자들은 업그레이드하지 않을 수 있다. 이 경우 업그레이드하지 않은 노드들은 업그레이드된 노드의 메시지를 이해하지 못해 byzantine failure를 발생시킬 수 있다.

이상으로 블록체인이 어려운 이유, Byzantine Failure에 대해서 알아봤다. 블록체인에 관심 없는 엔지니어에게 블록체인에 관해 물어보면 블록체인은 “이력을 저장하는 분산 저장소”라고 대답한다. 하지만 이는 블록체인의 극히 단편적인 모습만을 본 것이다. 오히려 이력을 저장한다는 특징은 byzantine failure를 극복하려는 방법에 불과하다. 블록체인은 근원적으로 이보다 어려운 문제를 풀어야 한다.

개인적으로는 이 어려움이 블록체인 개발의 재미라고 생각한다. 기존에는 이론적으로 연구만 되던 것이 실제로 동작하는 구현체가 나오고 있다. 특히 byzantine failure는 failure model 중 가장 현실에 가까운 모델이다. 따라서 앞으로 나오는 분산 시스템은 Byzantine Failure Model을 가정하고 나올 것이다. 그래서 설령 블록체인 개발을 하지 않더라도 블록체인에서 어떤 연구가 되고 있는지 아는 것은 분산 시스템 개발자로서도 중요하다고 생각한다.

2018-05-13

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를 사용하는 것은 얻는 것에 비해서 비용이 크기 때문이다.

카카오스토리 웹팀의 코드리뷰 경험

코드리뷰 없는 프로젝트는 있을 수 없다고 생각한다. 하지만 발표자가 말하듯이 시스템적으로 반드시 리뷰해야 머지할 수 있는 시스템은 별로라고 생각한다. 경험적으로 이런 시스템은 반드시 문제가 생긴다. 간단한 예로 휴가철에 급하기 hotfix를 넣어야 하는데 휴가 안 간 사람이 한 명밖에 없을 때, 휴가 간 사람이 강제로 업무를 하게 되는 경우가 있다. 굳이 휴가철이 아니더라도 급한 버그를 위해 야근이나 주말 근무를 하는 경우도 마찬가지다. 시스템적으로 머지에 리뷰를 강제하게 되면, 버그를 잡고 머지 하기 위해서 버그 잡는 사람 외에 누군가가 남아있어야 한다. 결코 바람직하지 않은 상황이다.

리뷰를 받을지 말지 패치를 만든 사람의 판단으로 선택해야 한다. 그 패치가 리뷰를 받아야 할지 안 받아도 되는지는 패치를 작성한 사람이 가장 잘 안다. 이건 패치 만드는 사람의 판단을 따라야 한다. 만약 이 정도 판단을 믿지 못한다면, 그 사람에게는 코딩을 맡기면 안 된다. 바람직한 개발 프로세스는 상호 신뢰에서 나온다고 생각한다. 기본적인 신뢰 관계가 없는 팀에서는 아무리 좋은 프로세스를 선택하더라도 유지될 수 없다.

개발 스타일은 툴로 체크해야 한다는 것에도 동의한다. 툴로 체크할 수 있는 걸 사람이 보고 있는 건 시간 낭비다. 다만 윗글에서 나온 대로 수정한 코드에 대해서만 체크할 수 있는 툴은 찾기 어렵다. 그래서 나는 한 번 대대적으로 프로젝트의 스타일을 수정하고 시작하는 것을 더 선호한다. 이렇게 되면 작업하고 있던 사람들과 컨플릭이 나거나 blame으로 찾을 수 있는 이력이 더럽혀진다는 문제가 있다. 하지만 이런 문제가 통일되지 않은 스타일로 프로젝트가 계속 진행되거나, 리뷰마다 스타일을 눈으로 체크하는 것보다는 더 싸게 먹힌다고 생각한다.

By the numbers: Python community trends in 2017/2018

2017, 2018년도 python community를 분석한 글이다. 개인적으로는 Types of Python development 파트에 나오는 파이썬 사용자를 분야별로 나눈 파트다. 보면 파이썬 사용자는 크게 data scientist와 웹 개발자로 나눠진다는 것을 알 수 있다. 특히 data scientist를 다 합치면 웹 개발자보다 많은 비중을 차지한다. 이는 파이썬이 사용하기 편하다는 점도 있지만, numpy, PyTorch, TensorFlow 등 다른 언어에서는 찾기 힘든 좋은 툴들이 많이 있기 때문이라고 생각한다. 당장 나만 해도 개발할 때는 정적 타입 언어를 선호하지만, 자료 분석이나 수치 분석을 할 때 파이썬 외에 다른 언어를 사용하지 않는다.

그 다음으로 눈에 보이는 것은 파이썬과 함께 사용하는 언어로 JavaScript가 1위를 차지했다는 것이다. 개인적으로는 파이썬의 반대되는 컴파일된느 언어나 정적 타입 언어들과 함께 사용할 것이라고 생각했고, 언어적 특성이 비슷한 JavaScript와 함께 사용할 것이라고 생각하지 않았다. 2위가 HTML/CSS인 것을 보면 이는 파이썬 사용자의 절반 정도가 웹 개발을 하기 때문으로 보인다.

다음으로 인상적인 것은 Python 3의 사용자가 Python 2의 3배쯤 사용된다는 것이다. 몇 년 전만해도 많은 Python 2 사용자들이 Python 3로 넘어가지 않고 버티고 있었고, 많은 라이브러리가 Python 2만 지원했었던 것을 생각하면 시대가 많이 좋아진 것 같다.

가장 놀라운 것은 VCS를 안 쓰는 사람이 38%나 된다는 것이다. VCS를 안 쓰고 개발이 관리가 되나 싶은데 안 쓰는 사람이 38%나 된다. 심지어 테스트를 안 짜는 사람(19%)보다 많다.

Quantum resource estimates for computing elliptic curve discrete logarithms

일반적으로 현대 컴퓨터에서 elliptic-curve cryptography(a.k.a. ECC)는 같은 길이의 키를 가지는 RSA 방식보다 더 풀기 어렵다고 말한다. 예를 들어 키 크기가 256 bit인 ECC와 같은 보안 레벨을 가지려면 RSA는 3072 bit 키를 사용해야 한다고 한다. 하지만 양자 컴퓨터가 도입되면 이야기가 달라진다. 양자 컴퓨터로 쇼어 알고리즘을 사용하면 비대칭키 암호화 방식을 깰 수 있는데, 3072 bit RSA를 깨는데 6146 qubit이 필요하지만, 256 bit ECC를 깨는 데는 2330 qubit밖에 필요하지 않다. 여전히 같은 키 크기에서 RSA보다 ECC가 안전하지만, 기존에 안전하다고 여겨지던 것보다는 차이가 많이 줄어든다. 다행이도 아직은 양자컴퓨터가 수십 qubit 수준에서 연구 중이기 때문에 최소한 십 년 운 좋으면 몇십 년 내에서는 별문제 없을 것이라고 생각한다.

Announcing Rust 1.26

Rust 1.26이 나왔다. 일단 눈에 띄는 변화는 다음이 있다.

함수의 인자와 리턴 타입으로 impl Trait 허용

Rust의 trait은 크기가 없기 때문에, 함수의 인자로 받거나 리턴할 수 없었다. 이런 경우 Box로 싸거나, generic을 써야 했다. 이를 impl Trait라는 문법을 추가해서 간단하게 사용할 수 있도록 했다.

레퍼런스 타입 match 할 때, 자동으로 dereference

기존에는 레퍼런스 타입을 매칭하면 패턴 부분에도 전부 레퍼런스라는 것을 명시해야 했다. 이제는 레퍼런스를 자동으로 dereference하기 때문에 &ref를 쓸 필요가 없다.

main 함수가 Result 리턴할 수 있도록 허용

ErrDebug를 구현해야 한다는 제약이 있지만, 이제는 main 함수가 Result를 리턴할 수 있다. 리턴한 값이 Err라면 리턴한 Err를 출력하고 종료한다.

2018-05-12

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 nodeextension 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 값이 저장된다.

두 번째는 storage trie다. etheruem의 smart contract는 내부 상태를 가진다. 따라서 smart contract인 account는 자신의 상태를 간직하는 storage trie를 하나씩 만들어서 가지고 있다.

나머지 두 개는 transactions trie와 receipts trie다. 이들은 각각 블록이 가지고 있는 트랜잭션들과 각 트랜잭션을 실행한 실행 결과를 배열로 했을 때, 배열의 인덱스를 키로 하는 MPT다. Transactions trie와 receipts trie는 merkle proof를 위해 사용된다.

이 네 개의 MPT 중에서 state trie와 storage trie만 secure tree를 사용하고, transactions trie와 receipts trie에는 secure tree를 사용하지 않는다. 즉, state trie와 storage trie는 keccak-256 hash 값인 256 bit 값을 키로 사용하고, transactions trie와 receipts trie의 키는 임의의 길이의 값이다.

Ethereum이 secure tree를 사용하는 이유는 DoS 공격을 막기 위해서다. State trie와 storage trie는 파일에 저장된다. 즉, 이 두 trie에 새 노드가 추가되거나, 수정하거나, 노드를 읽는 것은 disk IO가 있어야 하고, 가능하면 leaf node에 도착할 때까지 최대한 적은 노드를 지나서 가는 것이 좋다. MPT는 이를 위해서 중복되는 1-child branch nodeextension node로 압축할 수 있도록 했다.

하지만 자식이 하나인 branch nodeextension node로 압축된다. 따라서 공격자가 악의적으로 2개의 자식이 생기는 branch node를 만들 수 있다면, 적은 비용으로 공격할 수 있다. 그래서 secure tree는 keccak-256 hash 값을 키로 사용하여 공격자가 자신이 원하는 위치에 노드를 생성할 수 없도록 하였다.

Transactions trie와 receipts trie는 secure tree를 사용하지 않는 이유는 키를 hash 하는 것으로 보호할 수 있는 것이 없다. Transactions trie와 receipts trie에서 키는 트랜잭션과 receipt의 index기 때문에 공격자가 원하는 키를 삽입하는 것이 불가능하기 때문이다.

또한, Secure tree는 키가 256 bit로 고정된다는 장점도 있다. 덕분에 트리의 깊이가 64 이하라는 것이 보장되기 때문에 state trie나 storage trie의 임의의 값을 변경하는데 드는 최대 비용을 계산할 수 있다. 특히 state trie나 storage trie는 트랜잭션에 의해서 읽히거나 수정되는데, 이때 읽히거나 수정되는 값이 어떤 노드에 있는지 상관없이 같은 일을 하는 트랜잭션은 같은 비용을 낸다. 그렇기 때문에 최대 비용이 보장되는 것은 secure tree의 큰 장점이다.

2018-05-06

2018년 18번째 주

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


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

우리나라를 비롯한 중국 일본은 흔히 YYYY-MM-DD 형식을 쓴다. 인도, 동남아, 유럽, 남미, 러시아는 DD-MM-YYYY 형식을 주로 사용한다. 우리나라에서 사용하는 형식을 보통 big endian이라고 부르고, 유럽 등지에서 사용하는 형식을 little endian이라고 부른다. 두 형식의 날짜를 전부 처리해야 하기 때문에 약간 귀찮기는 하지만 여기까지는 그래도 괜찮다.

근데 미국은 MM-DD-YYYY라는 괴랄한 표기법을 사용한다. 거의 인치법 이상으로 제정신이 아닌 표기법 같다. 물론 그들에게도 이유는 있다. 보통 날짜를 말할 때 연도는 중요한 것이 아니다. 오늘이 며칠인지 물어보면 5월 6일이라고 말하지 2018년인지는 말하지 않는다. 중요하지 않은 정보라서 뒤에 적는다는 것이 그들이 말하는 이유다. 근데 그럴 거면 그냥 연도를 적지 말았어야 한다고 생각한다. 내가 연도를 말할지 말지 날짜를 말할 때까지 아무 생각 안 하다가 몇 월 며칠인지 말하고 연도를 말한다는 게 잘 상상이 안 된다. 사실 상상이 되고 말고를 떠나서 middle endian의 날짜 포맷까지 처리하고 나면 짜증이 난다.

참고로 ISO 8601은 우리나라처럼 big endian을 쓰도록 규정한다. 사실 컴퓨터에서 처리하기에는 big endian이 가장 좋다. 그래서 미국이나 유럽에서 개발된 프로그램도 제대로 된 프로그램은 대부분 big endian으로 날짜를 보여준다.

A Taxonomy of Expression Value Categories

C++ 스펙에서 value category가 초안에서 어떻게 바뀌었는지 보여주는 문서다. C++ 11 이전의 lvalue, rvalue에서 xvalue가 추가되면서 어떻게 변했는지 보여준다. 개인적으로 Bjarne Stroustrup이 쓴 "New" Value Terminology와 함께 C++의 value category를 이해하는 데 가장 도움이 되는 문서라고 생각한다.

IMHO를 In My Honest Opinion이라고 받아들이는 사람이 더 많다고 한다. 리뷰나 토론할 때 많이 쓰는 표현인데 앞으로는 약자 쓰는 것도 조심해서 써야겠다.

참고로 buzzfeed가 했다는 설문은 Help Us Solve This Debate About What "IMHO" Stands For로 보인다.

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 tree를 사용하면 서로 다른 두 노드가 같은 데이터를 가졌는지 효율적으로 비교할 수 있다. 예를 들어 위와 같은 L1, L2, L3, L4가 있을 때, 같은 Top Hash를 가졌는지만 비교하면 된다. 만약 Top Hash가 다르고, 어떤 데이터가 다른지 알고 싶으면 Hash0Hash1을 비교하고, 둘 중 다른 브랜치의 hash를 비교해나가면 어떤 데이터가 다른지 알 수 있다.

Merkle Patricia Trie

MPT는 Merkle tree처럼 각 노드가 hash를 가진다. 노드의 hash는 노드 내용의 sha3 hash로 결정된다. 이 hash는 노드를 지칭하는 key로도 사용된다. go-ethereumleveldb를, parityrocksdb라는 key-value storage에 state를 저장한다. 이때 스토리지에 저장되는 key와 value는 ethereum state의 key-value가 아니다. 스토리지에 저장되는 value는 MPT 노드의 내용이고, key는 이 노드의 hash다.

대신 ethereum state의 key는 MPT에서 path로 사용된다. MPT에서 key가 같은지 비교하는 단위는 nibble이기 때문에 하나의 노드에서 최대 16개의 branch를 가질 수 있다. 거기에 노드도 값을 가지기 때문에, 16개의 브랜치와 값을 합쳐 17개의 아이템을 가진 배열이 branch node가 된다.

아래로 자식이 없는 노드는 leaf node라고 불린다. Leaf node는 자신의 path와 value 두 개의 아이템으로 이루어진 배열이다. 예를 들어 "0xBEA"라는 키에 1000이 들어있고, "0xBEE"라는 키에 2000이 들어있는 경우를 생각해보자. 그렇다면 "0xBE"를 path로 가지는 branch node가 있고, 그 아래 "0xA"와 "0xE"를 path로 가지는 두 leaf node가 붙는다.

MPT에는 앞서 설명한 branch nodeleaf node 외에 extension node가 있다. Extension nodebranch node의 최적화다. Ethereum의 state에서는 하나의 branch node가 하나의 자식만 가지는 경우가 많다. 그래서 MPT는 하나의 자식만 가지는 branch node를 경로와 자식의 hash를 가지는 extension node로 압축한다.

여기서 문제가 하나 생긴다. Leaf nodeextension node는 둘 다 2개의 아이템을 가진 배열이다. 따라서 이 두 개의 node를 구분할 방법이 필요하다. MPT는 이를 위해서 경로에 prefix를 붙인다. 만약 노드가 leaf node고 경로가 짝수개의 nibble로 구성돼 있으면 0x20을 붙이고, 홀수개의 nibble로 구성돼 있으면 0x3을 붙인다. 반대로 extension node의 경우 짝수개의 nibble로 구성돼 있으면 0x00을, 홀수개의 nibble로 구성돼 있으면 0x1을 prefix로 붙인다. 홀수개의 nibble로 구성된 경로에는 한 개의 nibble을 prefix로 붙이고, 짝수개의 nibble로 구성된 경로에는 두 개의 nibble을 prefix로 붙이기 때문에 경로는 항상 byte로 표현 된다.

2018-05-02

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 메시지를 모으면 commit phase를 시작한다. 이때 일부 cohort에 문제가 생겨서 더 진행되지 않는 것을 방지하기 위해서 일정 시간 응답을 주지 않는 cohort는 NO 메시지를 보냈다고 가정한다.

이때 quorum을 얼마로 잡는가에 따라서 시스템의 consistency modelresilience가 결정된다. 예를 들어 N개의 coordinator가 있는 시스템에서 N개의 YES 메시지를 모아야 한다면, 하나의 failure도 용납하지 않는 resilient 하지 않지만, strong consistency를 보장하는 시스템이 된다. Quorum이 얼마가 되어야 하는지는 정해지지 않았다. 하지만 non-partition 상황에서 consistency를 보장하기 위해서는 최소 N/2 이상의 YES 메시지를 모아야 한다.

Coordinator가 quorum 이상의 YES 메시지를 받았으면 cohort들에게 COMMIT 메시지를 보내고, quorum 이상의 NO 메시지를 받았으면 cohort 들에게 ROLLBACK 메시지를 보낸다. cohort는 COMMIT 메시지를 받았으면 voting phase에서 받았던 transaction을 커밋하고, ROLLBACK 메시지를 받았으면 그 transaction을 버린다. COMMIT이든 ROLLBACK이든 메시지를 처리하고 나면 cohort는 coordinator에게 처리했다는 메시지를 보낸다. Coordinator가 cohort들에게 처리가 끝났다는 메시지를 받으면 commit phase가 끝난다.

위의 과정을 거쳐 2PC가 진행된다. 앞서 말했듯이 2PC는 괜찮은 resilience를 보이면서, 성능도 나쁘지 않기 때문에 많이 사용된다. 특히 atomic commit을 지원하는 프로토콜 중에서는 가장 적은 메시지 수로 commit 될 수 있는 프로토콜이다.

하지만 2PC에는 심각한 문제가 하나 있다. 2PC는 VOTE 메시지를 보낸 coordinator가 죽어서 COMMIT이나 ROLLBACK 메시지를 보내지 못하면 YES 메시지를 보낸 cohort가 안전하게 상태를 회복할 방법이 없다. 이는 YES 메시지를 보낸 cohort의 상태가 undefined이기 때문이다. 이에 관해서는 다음에 기회가 되면 three phase commit을 설명하면서 자세히 얘기하도록 하겠다.

2018-04-29

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의 장점에 관해서 쓴 글이다. 근데 여전히 GraphQL을 쓸지는 모르겠다. 복잡한 웹 서버를 짤 일이 있으면 모르겠는데 요새는 웹 서버라기보다는 그냥 간단한 툴의 UI를 웹으로 사용하는 정도로만 웹 코딩을 하고 있다. 이 정도 수준의 앱에서는 GraphQL을 사용하는 것이 오버헤드가 더 클 것 같다. 사실 반대로 말하면 뭘 써도 상관 없는 크기라서 GraphQL을 써도 된다. 하지만 다른 라이브러리에 디펜던시 없이 구현할 수 있는 REST에 비해서 GraphQL을 쓰려면 GraphQL을 구현하는 라이브러리를 써야 하므로 의존성을 추가해야 하는데 아직 그만한 필요성을 못 느끼겠다.

GO's New Brand

GO가 새 로고를 발표했다. 드디어 이상한 쥐를 버린 줄 알았는데 Gopher는 마스코트로 여전히 남겨두는 듯 하다.

Flask 1.0 Released

Flask가 드디어 1.0이 됐다. 사실 전에도 0.X인걸 신경 쓰지 않고 썼기 때문에 상관없지만 1.0을 쓰면 괜히 기분이 좋다.

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에만 포함된 노드는 지워도 되도록 하였다. 하지만 지워도 된다는 것과 지울 수 있다는 것은 별개의 문제다. DB에 저장돼있는 노드 중 최근 127개의 노드에서 접근할 수 없는 노드를 찾아 지우는 것은 쉬운 문제가 아니다.

이 문제는 computer science에서 오랫동안 풀어 온 automatic memory management 문제와 비슷하다. 실제로 Vitalik Buterin이 쓴 state tree pruningreference counting을 언급하고 있다. 하지만 ethereum의 state trie pruning은 일반적인 memory management와 다른 점이 하나 있다.

일반적인 automatic memory management는 volatile 한 자원을 다룬다. 따라서 프로그램이 비정상 종료되는 상황을 고려하지 않아도 된다. 프로그램이 종료되면 관리해야 할 자원이 남아 있지 않기 때문이다. 하지만 state trie의 노드는 DB에 저장되는 persistence 메모리다. 프로그램의 비정상 종료로 인해 state trie가 비정상적인 상태가 되면 복구할 방법이 없다. Vitalik이 제시한 state tree pruning이 메인 넷에 들어가지 못한 것도 이런 이유에서다.

Reference counting이 아닌 다른 방법으로 state trie pruning을 구현할 수도 있다. 예를 들어 trace를 이용하는 방법도 tracing garbage collection도 automatic memory management에서 흔히 사용되는 기법이다. 하지만 trace에 필요한 추가적인 메모리나, stop-the-world에 의해 생기는 성능 문제 등이 먼저 해결돼야 한다.

이러한 문제들로 현재 go-ethereum에서는 매우 한정적으로 state trie pruning을 한다. State trie에 대해 cache를 사용하는데, 이 cache에만 저장된 노드에 대해서는 pruning을 하고 DB에 저장된 노드는 pruning을 하지 않는 방식이다. Caching 된 노드는 서버가 정상적으로 종료되거나, 생성된 지 128 block이 지났거나, 캐시 크기를 넘겼거나, 마지막으로 cache된 노드가 DB에 저장된 지 5분이 지나면 DB에 저장한다. 즉, 위의 조건을 만족하기 전에 cache에서 삭제된 노드는 DB에 저장하지 않는다.

하지만 생성된 지 5분이 지나지 않아서 삭제되는 노드는 그리 많지 않다. 따라서 대부분의 삭제됐어야 할 노드는 여전히 DB에 남아 있다. 이에 대해 ethereum에서는 state pruning을 구현하는 것을 계속 시도하고 있다. 하지만, state trie pruning이 실제로 구현되기 전에는 fast sync를 사용하여 다음과 같은 방법을 사용하기를 권장한다.

  1. 새 클라이언트를 띄운다.
  2. 기존 클라이언트에서 새 클라이언트로 fast sync를 받는다.
  3. 기존 클라이언트를 지운다.

위의 과정을 거치면 새 노드에서는 fast sync로 동기화된 상태까지의 garbage node 없이 유효한 노드만 관리할 수 있다. 언뜻 보기에는 주먹구구식 방식으로 보이지만, 위험 부담이 있는 garbage collection을 구현하는 것보다 안전하고 현실적인 해결책이다. Ethereum에 garbage collection이 구현되기 전까지는 계속 위와 같은 방식을 이용해야 할 것으로 보인다.

2018-04-22

2018년 16번째 주

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


ISO week date

오늘이 올해의 몇 번째 주인지 정하는 기준은 말하는 사람마다 다르다. 그래서 이 요약정리 시리즈는 ISO 8601 기준으로 몇 번째 주인지 표기한다. ISO 8601에 따르면 1월 4일이 포함된 주를 그 해의 첫 번째 주로 취급한다. 다른 말로 한 주의 시작을 월요일로 봤을 때 4일 이상 포함된 첫 번째 주가 그 해의 첫 번째 주인 것이다.

TextQL

머신 러닝이나 데이터 마이닝을 할 때 데이터의 경향성을 대강 파악하고 싶을 때가 있다. 이럴 때 사용되는 데이터는 보통 매우 큰 데이터이기 때문에 에디터로 열어서 보는 것은 무리가 있고, 간단하게 스크립트를 짜서 실행하게 된다. 근데 이때 하는 일은 대부분 비슷한 일이기 때문에 꽤나 귀찮은 작업이었는데, 스크립트를 짜지 않고 파일을 SQL을 실행시켜주는 프로젝트가 있었다.

아직 사용해보지는 않아서 직접 스크립트를 짜는 것과 비교하면 어떨지는 모르겠지만 꽤 많은 사람이 쓰고 있는 것 같다.

Writing

수학을 배워야 하는 이유가 사고하는 법을 익히기 위해서이듯이, 글쓰기를 배우는 이유는 무엇을 생각했는지 명확하게 하기 위해서다. 사람은 모든 것을 기억할 수 없기 때문에 자신이 생각한 것을 써서 정리해야 한다는 것이다. 게다가 글을 쓰는 것은 내가 글 쓰는 주제에 대해 나보다 모르는 독자를 가정하고 글을 쓰게 된다. 그래서 평소에는 당연하게 생각하고 넘어갔던 것들에 대해서도 한 번 더 생각하고 넘어갈 시간을 가지게 한다.

How quantum computing could wreak havoc on cryptocurrency

양자 컴퓨터가 상용화되면 현재 사용되는 암호화 기법 중 많은 것들이 쉽게 풀리게 된다. Cryptocurrency들은 이날을 대비해서 post-quantum cryptography로 넘어갈 준비를 해야 한다는 글이다. NSA는 수십 년 안에 양자 컴퓨터가 실제 암호를 해킹할 수 있을 정도로 발전할 것이라는 보고서를 작성한 적이 있다. 하지만 윗글의 글쓴이는 수십 년까지 가지 않고 십수 년 내에 양자 컴퓨터가 암호학에 실질적인 위험이 될 것이니 대비를 해두어야 한다고 주장한다.

OLPC’s $100 laptop was going to change the world — then it all went wrong

10년 전쯤 유행했던 OLPC라는 프로젝트가 있다. One Laptop Per Child라는 이름 그대로 모든 아이에게 노트북을 제공하겠다는 프로젝트였다. XO-1이라는 100$짜리 노트북을 제작하여 개발도상국의 어린이에게 노트북을 하나 더 제공하겠다는 프로젝트였다.

하지만 모든 아이에게 XO-1을 제공하겠다는 프로젝트는 결국 실패했다. XO-1 이후 출시할 계획이었던 XO-2는 나오지도 못했다. 실패한 원인은 여러 가지 있다. 애초에 목표했던 100$ 가격에 도달하지 못하기도 했고, 인텔에서 나온 넷북이 XO-1보다는 비싸지만, 훨씬 훌륭한 성능과 보편성 때문에 더 인기 있었다.

나는 이것을 뜻은 크지만, 기술이 뒤받쳐주지 못해서 생긴 OLPC의 완벽한 실패라고 생각한다. 하지만 윗글의 저자는 OLPC가 넷북의 보급을 가지고 왔고 덕분에 저가형 노트북 시장이 커졌으므로 어느 정도 목표를 이루었다고 보는듯하다.

The latest trend for tech interviews: Days of unpaid homework

최근 유행하고 있는 테크회사들이 인터뷰 시 단순히 면접으로 끝내는 것이 아니라 시간이 오래 걸리는 과제를 내는 것을 비판하는 글이다. 말하고자 하는 바는 이해하지만, 딱히 더 좋은 해결법은 생각나지 않는다. 나는 회사에서 줄 수 있는 가장 큰 복지 중 하나는 좋은 팀을 구성해주는 것이라고 생각한다. 그런 면에서 충분히 검증되지 않은 사람과 일하고 싶지 않다. 물론 검증에 필요한 비용을 구직자에게 전가하는 방식은 옳지 못하다. 개선할 필요가 있다. 하지만 그게 윗글에서 말하는 한 시간 내외의 코딩면접인지는 잘 모르겠다.

Why Is SQLite Coded In C

SQLite가 어째서 C를 사용하는지에 관한 글이다. 개인적으로 C를 좋아하지는 않지만, 이 글에서 주장하는 바는 전부 타당하다고 생각한다.

Conceptual compression means beginners don’t need to know SQL — hallelujah!

Ruby on Rails(a.k.a. RoR)의 제작자, DHH가 쓴 글이다. RoR은 잘 만들어진 ORMActive Record로 유명하다. 사실 지금까지 Active Record 외에는 쓸만한 수준으로 동작하는 ORM을 본 적이 없다. 하지만 여전히 ORM이 SQL을 대체할 수 있는가에 대해서는 회의적이다. 아마 DHH도 완전히 대체할 것으로 생각하지는 않았는지 beginners에 한정시켜 말하기는 했다.

하지만 나는 여기에도 회의적이다. 프로그래머가 쓰는 시간 대부분은 사실 코딩이 아니라 전체적인 구조를 설계하는 것과 문제가 생겼을 때 디버깅하는데 들어간다. SQL을 모른다는 것은 사실 RDBMS(Relational database management system)의 동작을 이해하지 못했다는 것인데 아무리 적절한 수준의 추상화가 문제를 단순화시키는 데 도움을 준다고 해도, 내부 동작을 모른 채로 적절한 설계를 하거나, 문제가 생겼을 때 원인을 찾아낼 수 있다고 생각되지 않는다.

Analysis of the Bitcoin UTXO set

Bitcoin은 Unspent Transaction Output(a.k.a. UTXO) set을 이용해 현재 상태를 표현한다. 위 논문은 bitcoin에서 UTXO를 어떻게 저장하고 UTXO set이 어떻게 변해왔는지를 분석했다.

2018-04-19

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 = 3f + 1이라고 말하면, 전체 노드 중 1/3이 byzantine failure일 때까지는 문제없이 돌아가는 시스템을 말한다.

같은 BFT라고 한다면, 감당할 수 있는 faulty 노드의 비율이 더 큰 시스템이 더 안전한 시스템인 것은 당연하다. 하지만 N = 3f + 1. 즉, 1/3 이상의 byzantine failure를 가정하는 시스템은 없다. 이는 1/3이 이론상으로 가질 수 있는 최대치이기 때문이다.

어떤 노드가 byzantine failure일 때 발생할 수 있는 문제 상황은 크게 두 가지다. 첫 번째 문제 상황은 메시지를 보내지 않는 것이다. 즉, 분산 시스템이 N개의 노드 중 byzantine failure f개가 정상적으로 동작하기 위해서는 N - f개의 메시지만으로 합의가 이루어져야 한다. 이것을 다른 말로 quorum을 위해서 N - f개의 노드가 필요하다고 말한다.

두 번째 문제 상황은 byzantine failure인 노드가 악의적으로 다른 메시지를 보내는 것이다. 극단적으로는 quorum을 이룬 N - f개의 노드 중에서 f개가 byzantine failure가 보낸 메시지인 경우를 생각해볼 수 있다. 이 경우도 정상 동작해야 하므로 (N - f) - f 개의 메시지가 byzantine failure인 노드가 보낸 f개의 메시지보다 많아야 한다.

위의 두 경우를 대비하기 위해서 (N - f) - f > f. 즉, N > 3f이므로 f개의 byzantine failure인 노드가 있을 때 최소 3f개보다 많은 노드가 있어야 byzantine fault tolerance한 시스템이고, 이때 가장 작은 N은 3f + 1이다. 따라서 3f + 1개의 노드로 구성된 시스템에서 견딜 수 있는 faulty 노드의 최대 수는 f다.

2018-04-14

2018년 15번째 주

이 포스팅은 그냥 지난 한 주간 읽었던 것들을 정리하는 포스트입니다. 그냥 예전에 봤던 글 중 나중에 필요한데 뭐였는지 기억 안 나는 글들이 있어서 쓰기 시작했습니다.

보통 하는 일과 관련된 글들이 올라오겠지만 딱히 정해둔 주제는 없고, 그때그때 관심 있었던 것을 읽었기 때문에 지난주에 쓰인 글일 수도 있고 몇 년 전에 쓰인 글일 수도 있습니다.


실제로 git을 사용하면서 단순히 커맨드를 외워서 사용하는 사람들을 많이 봤다. 보통 그 이유로 크게 두 가지를 든다. 첫 번째로 git의 mental model이 복잡하다는 것이다. git에서 변경된 내용은 크게 다음 상태 중 하나가 된다.

  1. 리모트에 존재하는 상태
  2. 로컬 브랜치에 있는 상태
  3. 브랜치에 머지되지 않았지만 add 돼 있는 상태
  4. 변경은 있지만 add 되지는 않은 상태
  5. stash에 들어있는 상태
  6. 예전에 커밋했었지만 지금은 브랜치로 따라갈 수 없는 상태

이 중에서 내가 수정했던 내용이 어떤 상태인지 모르는 것이 헷갈리게 하는 첫 번째 이유다.
하지만 반대로 왜 이렇게 많은 상태를 가지게 됐을지 생각해보면 git을 사용하는 데 도움이 된다. 이것들은 전부 그냥 추가된 것이 아니다. 애초에 git을 처음 만든 사람은 Linus Torvalds다. 그의 성격상 쓸모없는 것은 추가되지 않았다. 전부 제각각의 목적을 가지고 있다. 이 목적을 이해하는 것이 중요한데 아쉽게도 글로 잘 설명할 자신이 없다. 사실 이걸 이해하는 가장 빠르고 확실한 방법은 svn을 써보는 것이다. 쓰다 보면 불편한 부분들이 자주 생기는데, git에서는 위에서 말한 것들을 이용해 이를 쉽고 빠르게 해결할 수 있다.

사람들이 git을 어려워하는 두 번째 이유는 명령어가 복잡하다는 것이다. 이건 어쩔 수 없다. 사실 git의 명령어는 규칙성 없이 만들어졌다. 그래서 외우는 수밖에 없다. 하지만 어떤 상황에서 어떤 명령어를 써야 한다는 식으로 외우면 끝이 없다. 그보다는 각 명령어가 어떤 상태와 연관이 있는지를 보는 것이 좋다. git 명령어는 대부분 변화된 내용을 위의 상태 중 하나로 만들거나, 특정 상태로 로컬에 있는 파일을 변경하는 것이다. 따라서 현재 파일이 어떤 상태에 있고 명령어 이후 어떤 상태로 된다는 것을 인지하고 있으면 조금은 더 쉽게 적응할 수 있다.

News is bad for you – and giving up reading it will make you happier

뉴스가 사람의 정신건강에 해롭다는 기사다. 사람들이 흔히 정보를 얻으려고 뉴스를 읽지만, 실제로는 별 도움도 안 되고 시간만 낭비하게 하고 사람의 창의성을 없애고 수동적으로 만든다는 것이다.

Introduction to zkSNARKs

이더리움의 최근 움직임 중에서 zero-knowledge proof인 zkSNARKs을 도입하고자 하는 움직임이 있다. 위 자료는 이더리움 소속으로, 솔리디티 창시자 중 하나이며 zkSNARKs를 구횬하고 있는 Christian Reitwiessner이 zkSNARKs에 대해 간단히 소개한 발표자료다. 자료 이름은 zkSNARKs이지만 대부분의 내용을 zero-knwledge proof가 무엇인지에 설명하는 데 쓰고 있으므로 zero-knowledge proof가 무엇인지 알고 싶은 사람들이 보기에도 좋은 자료다.

RSS is undead

RSS는 이미 수명이 끝났고, 다시 살아날 리 없다는 글이다. 지난번에 소개했던 It's Time for an RSS Revival이나 Why RSS Still Beats Facebook and Twitter for Tracking News의 반대편에 있는 입장이다.

RSS는 소규모 사이트의 글을 구독하는 데는 적절하지만, 대형 사이트의 특정 카테고리의 글을 구독하는 데는 적당한 UX를 제공하지 못하고, 퍼블리셔 입장에서 사용자의 패턴을 파악할 수 없을뿐더러 광고수익을 얻을 수 없기 때문에 사용자와 퍼블리셔 양쪽에게 손해라는 것이다.

What is a “box model”? (UI Element layout)

Web을 비롯하여 현대의 많은 UI framework들이 box model을 사용하기 때문에 프론트엔드 개발을 하려면 한 번 읽어두는 것이 좋다.

The Science of The Job Search, Part III: 61% of “Entry-Level” Jobs Require 3+ Years of Experience

경력 같은 신입을 원하는 건 우리나라뿐 아니라 전세계 공통인듯하다.

A fork on Github is no fork

Git은 decentralized 된 version control system이기 때문에 fork를 하면 어디서 fork 해왔는지와 완전히 독립적인 repository로 존재할 수 있다. 하지만 Github의 fork는 그 모든 설정과 권한이 원본 repository에 종속적이기 때문에 진짜 fork가 아니라는 글이다.
원칙적으로 맞기는 하지만 Github Enterprise나 private repository 유료 모델을 생각해보면 어쩔 수 없는 선택이었다고 생각한다.

Uninhabited types are ZSTs despite partial initialization being allowed in safe code.

Rust 1.24.0 이후 생긴 memory safety가 깨지는 버그다.

Rust는 무한루프나 내부에서 exit 하기 때문에 return 되지 않는 함수를 표현하기 위해서 uninhabited type을 도입했다. 이 uninhabited type으로 product type을 만들면 이 타입도 uninhabited type이 돼서 크기가 0인 type으로 계산되는데, 이 product type의 다른 field를 접근하는 게 가능해서 주소 계산이 잘못되는 버그가 발생했다. Rust에 zst(zero size type)가 도입됐을 때부터 메모리 주소 계산을 잘못 하는문제가 발생하지 않을까 생각했는데 정말로 터져버렸다.

현재 두 가지 해결 방안 중에서 어느 쪽으로 해결할지 논의 중이라고 하니까 다음 버전인 1.26.0에서는 수정될 것으로 보인다.

Top 10 Bugs in the C++ Projects of 2017

소프트웨어 분석 회사인 viva64에서 2017년 동안 발견했던 버그 중 가장 인상 깊은 버그 10개를 발표하였다. uninitialized memory부터 type error나 단순 실수까지 다양하게 있다.

Don’t Give Away Historic Details About Yourself

자기 정보를 쉽게 제공하지 말라는 글. 특히 우리나라 사람들은 주민등록번호 유출에조차 익숙해져서 그런지 자기 정보를 적는데 아무런 망설임이 없다.

Why Does "=" Mean Assignment?

수학에서는 보통 대입에는 :=를 사용하고 =는 비교에 사용한다. 근데 프로그래밍에서는 왜 =를 대입에 사용하게 됐는지에 관한 글이다. 뭐 지금은 다들 =를 대입연산자로 사용하고, ==를 비교연산자로 사용하는 데 익숙하기 때문에 별 의미는 없지만, 그냥 재미로 읽어봤다.

2018-04-12

이더리움 샤딩

현재 이더리움이 겪고 있는 가장 큰 문제는 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을 실행한다. T1M의 state를 변경할 수 없기 때문에 B에게 바로 입금할 수 없다. 따라서 T1MB에게 돈을 추가하라는 receipt만 남긴다. 그 후 M에서 B에게 입금하는 transaction T2를 실행하고 자신이 입금했다는 것을 다시 receipt에 적는다.

이렇게 하면 기존보다 비효율적이지만 샤드 간 송금은 처리할 수 있다. 하지만 아직 넘어야 할 산이 있다. 이더리움의 consensus 방식은 finality를 확률적으로만 보장한다. 위의 예제에서 T1을 실행됐으면 T2가 실행되고, T1이 실행되지 않았으면 T2도 실행돼서는 안 된다. 따라서 N에 문제가 생겨 reorganization이 발생하여 T1이 사라졌으면, M도 reorganization하여 T2를 지워야 한다. 이를 악용하면, 쉽게 DoS 공격이 가능해진다. 따라서 T2를 실행하기 전의 T1의 finality를 보장해야 하는데, 앞서 말했듯이 현재 이더리움에서는 방법이 없다. 완전히 PoS로 옮겨가거나 최소한 Friendly Finality Gadget이 들어가야 확실하게 finality를 보장할 수있게된다. 그래서 현재 진행중인 sharding phase 1에서는 샤드 간 통신은 구현이 없고 phase 4에서야 구현될 것이라고 한다.

샤드 간 송금은 finalty만 보장되면 위와 같은 방식으로 할 수 있지만, smart contract를 실행하는 것은 이것보다 더 복잡해진다. smart contract에서는 다른 smart contract를 호출할 수 있는데, smart contract도 각자 자신의 state를 가지고 있기 때문에, 모든 smart contract가 같은 shard에 있어야 한다. 이 문제를 해결하기 위해 smart contract를 lock 하여 실행시킬 shard로 가져오는 cross shard lock scheme이 제안은 됐지만, 아직 결정된 것은 아무것도 없다.

이더리움의 성능 문제가 현재 이더리움이 가지는 가장 큰 문제인 것은 확실하다. 이더리움의 트랜잭션 양은 늘어나고 있는데 아직도 이더리움의 초당 트랜잭션 처리 속도는 20tx/s를 넘지 못하고 있다. 하지만 샤딩만으로 얼마나 성능을 향상할 수 있을지는 의문이다. 샤드를 N개 만들었을 때, 최상의 결과는 N배 빨라지는 것이다. 이것도 정말 이상적인 것이고 실제로 이만한 성능 향상을 얻지는 못할 것이다. 따라서 성능을 많이 올리고 싶으면 샤드의 개수를 늘려야 한다.

하지만 위에서 말했듯이 샤드를 도입하면, 샤드 간 transaction은 지금의 이더리움보다 처리 속도가 느려진다. 현재 제안된 casper에서 finality를 보장하기 위해서는 최소 50 block을 기다린다. 샤드 간 통신에서는 두 번째 트랜잭션이 실행되기 전에 finality가 보장돼야 하니, 샤드 간 통신의 finality를 보장하기 위해서는 최소 10분을 더 기다려야 한다는 것이다. 과연 이 overhead를 감수하면서 샤드가 가지고 올 성능 향상이 크지는 않을 것 같다.

2018-04-07

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

회사 생활에 질리고 권태감이 드는 게 생물학적으로 당연하다고 한다. 사람의 뇌는 언제나 새로운 것을 추구하도록 진화됐다고 한다. 이는 사람뿐만 아니라 동물들에게도 마찬가지다. 동물들도 주어진 먹이를 먹는 것보다 숨겨진 음식을 찾아서 먹는 것을 더 좋아한다. 숨겨진 것을 찾아내고 새로운 것을 알아가면 뇌가 자극받아 도파민을 분비하고 이게 기쁨을 느끼게 한다는 것이다.

문제는 현대의 회사 시스템은 이런 도전 정신을 자극할만한 것이 없다는 것이다. 그래서 결국 주기적으로 팀을 옮기거나 조금 더 적극적인 경우 회사를 옮기거나 회사 생활에서 못 받는 자극을 취미에서 찾거나 하는 것 같다.

개인적으로는 이런 권태감을 개인 프로젝트로 푸는 편이다. 특히 회사 일과 같은 것을 하지 않기 위해서 개인 프로젝트를 할 때는 회사에서 쓰는 것과 다른 특성의 언어를 사용하여 회사 일과 상관없는 분야를 한다.

Known-planitext attack

KPA라고 불리는 암호학 공격기법이다. 이름 그대로 공격자가 암호화되기 전의 평문을 알고 있는 암호문이 몇 개 있을 때, 이를 기반으로 어떤 알고리즘으로 암호화된 것인지, 혹은 알고리즘을 이미 알고 있다면, 어떤 키로 암호화됐는지 찾아내는 공격방법이다. 찾아낸 알고리즘이나 키를 이용하여 후에 들어오는 암호문을 복호화하는 것이 목적이다.

It's Time for an RSS Revival

지난번에 소개했던 Why RSS Still Beats Facebook and Twitter for Tracking News와 비슷한 글이다. 최근 페이스북에서 터진 이슈 때문에 많은 사람이 대안을 찾고 있어 RSS에 주목하는 글이 많이 나오고 있는 듯하다.

Metcalfe's law

네트워크의 효용성은 노드 간 컨넥션 수가 높을 수록 높으므로 노드 수의 제곱에 비례하게 된다는 법칙이다. 하지만 현실적으로는 모든 노드가 서로 컨넥션을 갖지 않는다. 따라서 크기가 작은 네트워크에서는 메칼프의 법칙이 성립하지만, 크기가 커지면 성립하지 않는다. 일반적으로 노드 수가 많은 네트워크는 complete graph도 아니고 각 컨넥션이 모두 같은 가치를 갖는것도 아니기 때문이라고 한다.

2018-04-01

2018년 13번째 주

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


정규 표현식에서 \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년경에는 이미 함수의 인자로 객체를 넘기는 패턴이 유행했다. 함수의 인자로 객체를 넘겼을 때의 장점은 두 가지로 정리할 수 있었다.

하나는 default parameter를 구현하기 쉽다는 것이다. EcmaScript 5까지는 default parameter가 없었다. Default parameter를 흉내 내기 위해서 Arguments를 이용해야 했는데, 몇 번째 인자가 무슨 의미를 가지는지 코드에 표현할 방법이 없기에 새 인자를 하나 추가할 때 실수할 확률이 높았다. 이를 object를 이용하면, property 이름이 있기 때문에 Arguments를 이용하는 것보다 읽고 수정하기 쉬운 코드를 만들 수 있었다. 이는 EcmaScript 6에서 default parameter가 추가됐기 때문에 지금은 크게 장점이 아니다.

두 번째 장점은 EcmaScript에 없는 named parameter를 구현할 수 있다는 것이다. EcmaScript에는 named parameter가 없기 때문에 인자 개수 차이에 따라 몇 번째 인자가 무엇을 의미하는지 다르게 해석하는 방법을 많이 사용한다. 하지만 이는 버그를 만들기 쉬운 코드이므로 좋은 방법은 아니다. 이것도 object를 사용하면, 손쉽게 구현할 수 있다.

인자를 객체로 넘기자는 주장은 많이 있었지만, 함수의 리턴 값을 객체로 하자는 주장은 과거에는 그리 흔한 주장이 아니었다. 함수의 종류에 따라 객체를 리턴하는 값이 특정한 객체로 묶기 쉬운 경우도 있었다. 그러나 이 값을 하나의 값이라고 부를지 리턴을 위해 객체로 묶었다고 부를지는 사람마다 다를 것이다.
하지만 EcmaScript 6 이후로는 전혀 관계없는 값을 하나로 묶어서 리턴하는 코드도 자주 보인다. EcmaScript 6에 들어온 destructuring assignment 덕분으로 보인다.


Coding is bad for you

코딩하다 보면 문제가 생길만한 상황이나 너무 사소한 것에 집착하게 되기 때문에 정신 건강에 해롭다는 글.

경험적으로 잘 짠 코드는 예상치 못한 상황에 대비할 수 있도록 짜인 코드였다. 그렇기 때문에 당연히 문제가 생겼을 때를 대비하는 프로그래머가 잘 하는 프로그래머일 것이고, 그들은 사소한 문제가 될만한 상황도 잘 잡아낸다. 이걸 못 하는 사람들은 아무리 빠르게 스펙에 맞게 코드를 짜더라도 절대 잘 한다는 소리를 들을 수 없다.

근데 이게 코딩을 하다 보면 사람이 그렇게 생각하게 되는지 원래 그런 사람들이 코딩을 잘하는 건지는 잘 모르겠다.


Avoid else early return

억지로 single point return을 만들기 위해 if/else를 쓰지 말고, early return이 가능한 지점에서는 최대한 빠르게 return 하자는 글이다. 경험상 single point return이 early return보다 장점을 가지는 경우는 C를 사용할 때밖에 없었다.
Early return이 문제가 되는 경우는 결국 함수 종료 시 특정 로직을 실행해야 하는데, return 문이 많이 있어서 실수로 로직을 빼먹는 경우다. 하지만 요즘 나오는 언어는 대부분 RAII가 되거나, finally block을 지원한다. 따라서 요즘 나온 언어를 사용하면 early return을 사용할 때의 문제점을 언어 차원에서 해결책을 제공하는 것이다.

아쉽게도 C에는 아직 RAII나 finally block에 해당하는 기능이 존재하지 않는다. 그래서 함수가 끝날 때 특정 코드를 실행시킬 방법이 없고, 이런 문제로 C에서는 single point return을 쓰는 게 더 안전할 수 있다. 그래서 지금도 리눅스 커널에서는 예외 처리나 리소스 해제 등을 위해 goto를 이용하여 single point return을 만드는 방법이 권장된다.

하지만 이는 C를 쓸 때의 예외적인 상황이고 대부분의 경우에는 early return이 더 좋다.


LG launches open source version of webOS

LG 스마트 워치나 스마트 티비에 들어가는 webOS의 오픈 소스 버전이 공개됐다는 소식.
webOS는 원래 Palm에서 만든 OS로 리눅스 커널 기반이라는 점에서 안드로이드나 iOS보다 잘 되기를 바랐지만 망한 OS다.
한 5년쯤 전에 LG가 인수했다는 말은 들었는데 LG가 이것저것에 사용해본 듯한데 결과적으로 점유율이 0%인 것을 보면 확실하게 망한 듯하다. 이제 와서 오픈 소스 버전을 공개한다고 하는데 딱히 기대는 안 된다. 오픈 소스라는 게 단순히 소스를 공개한다고 끝나는 것이 아니라 사용자로부터 꾸준한 피드백을 받으며 이루어지는 커뮤니티가 핵심인데, webOS에 피드백을 줄 사용자가 있을지, LG가 그런 커뮤니티를 운영할 능력이 있을지도 의문이다. 솔직히 webOS를 사는데 든 돈이 아까워서 손절하지 못 하고 있는 게 아닐까 싶다.


Key words for use in RFCs to Indicate Requirement Levels

영어를 못 해서 스펙 문서를 작성할 때 어떤 조동사를 써야 할지 헷갈릴 때가 있는데, 그때를 위해 Network Working Group에서 규정한 가이드라인이다.

  • MUST, SHELL, REQUIRED - 반드시 해야 하는 경우
  • MUST NOT, SHELL NOT - 절대 하면 안 되는 경우
  • SHOULD, RECOMMENDED - 근거가 있으면 안 해도 되는 경우
  • SHOULD NOT, NOT RECOMMENDED - 근거가 있으면 해도 되는 경우
  • MAY, OPTIONAL - 하든 안 하든 전체 동작에 문제가 없어야 하는 경우

2018-03-29

[보안] Alice와 Bob

네트워크 프로토콜을 설명하는 글을 읽으면 AliceBob, Carol, Eve, Mallory 등 많은 이름이 등장한다. 보통 이 이름들은 일정한 규칙을 가지고 부여되기 때문에 각 이름이 무슨 의미를 가지는지 안다면 그 프로토콜이 무엇을 어떻게 풀려고 하는지 조금은 더 이해하기 쉬워진다. 이번 글에서는 많이 네트워크 프로토콜에서 많이 사용되는 이름들이 무슨 의미를 가지는지 간략하게 정리해보았다.

네트워크 참여자 - Alice, Bob

보통 AliceBob은 서로 통신하려는 사람을 의미한다. 이때 통신하는 메시지는 보통 암호화하여 통신하는 메시지를 의미하는데 비대칭 키를 사용할지, 대칭 키를 사용할지는 그때그때 다르다.

다자 간 통신 참여자 - Carol, Dave, Erin, Frank, Gray

CarolDaveAliceBob과 함께 통신에 참여하는 경우 사용된다. CarolDave 말고도 CharlieDavid 같은 이름을 사용하기도 하지만 보통 CarolDave를 많이 사용한다.

5명 이상의 참여자가 필요한 프로토콜을 묘사할 때는, E, F, G로 시작하는 이름들을 사용한다. 보통 Erin, Frank, Gray 등의 이름이 사용되는데 어떤 이름을 사용할지는 딱히 정해져 있지 않다. 다른 용도로 사용되는 EveFaythe, Grace 등을 제외하고 아무 이름이나 사용된다.

공격자 - Eve, Mallory, Oscar, Trudy

Eve는 보통 네트워크를 감시하여 패킷을 도청하는 공격자를 의미한다. 다만 Eve는 능동적으로 공격을 하지는 않고 AliceBob이 주고받는 대화를 도청하여 무슨 대화를 주고받는지 알아내는 공격자에게 붙이는 이름이다. 이름의 유래는 eavesdrop에서 나왔다.

Trudy라는 이름은 Eve보다 조금 더 적극적인 공격자를 지칭할 때 사용된다. AliceBob 사이에 끼어들어 AliceBob의 메시지를 가로채 변조하여 보내거나 지우고 자신이 보내고 싶은 메시지를 보내는 공격자를 의미한다. 이름은 intruder에서 유래했다.

조금 더 포괄적인 공격자를 부르는 이름으로 Mallory가 있다. 이름의 유래는 malicious라는 단어에서 나왔다. EveTrudy와 구분 없이 공격자는 전부 합쳐 Mallory라고 부르기도 하므로 Mallory라는 이름이 나오면 이 사람이 어떤 공격을 하는지는 상황에 맞게 해석해야 한다. 이와 비슷한 의미로 사용되는 Oscar라는 이름도 있다.

감시자 - Walter, Wendy

Walter 혹은 Wendy라는 이름은 참여자를 감시하는 합법적인 감시자를 의미한다. 이들이 하는 일은 Mallory를 비롯한 공격자들과 비슷하지만, WendyWalter라는 이름이 나오면 AliceBob이 악의적인 사용자가 된다. 하지만 검열 감시를 피하는 것을 목적으로 하는 프로토콜을 설명할 때도 WalterWendy라는 이름을 사용한다. 예를 들면 검열하는 정부나 기업을 Wendy라고 이름 붙이고 이를 피하기 위한 참여자를 AliceBob이라고 이름하기도 한다.

WalterWendy는 크게 구분 없이 사용되는데 굳이 구분하면 Wendy는 허락되지 않은 정보를 주고받을 때 패킷을 검열하여 보내지 않도록 하는 역할을 하지만 Walter는 패킷을 검열하지는 않고 감시하는 역할만 할 때 사용된다. 보통 메시지를 감시하는 사람이 검열도 하기 때문인지 Wendy라는 이름이 더 많이 사용된다.

신뢰할만한 제삼자 - Trent, Ted

지금까지 설명한 이름들은 AliceBob의 통신을 방해하는 역할에 주어지는 이름이었다. 하지만 지금 설명할 TrentAliceBob의 통신을 도와주는 역할을 한다. 구체적으로 어떤 역할이 있지는 않고, AliceBob의 통신을 도와주는 역할을 한다. AliceBob이 통신할 shared secret을 생성, 관리해주기도 하고, 어떨 때는 AliceBob이 직접 통신하는 것이 아닌 대신 통신할 수 있는 암호화 된 채널을 만들어주기도 한다. 비대칭 키를 사용하는 경우, AliceBob의 public key를 저장하는 저장소를 Trent라고 부르기도 한다. Trent 대신 Ted라고 부르기도 하며 이름의 유래는 trust다.

2018-03-26

이더리움과 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))개의 연결만 유지하면 된다고 말한다.
이더리움이 Eclipse attack에 취약했던 근본적인 원인이 여기에 있다. Kademlia 프로토콜에서는 거리를 노드 아이디를 기반으로 구하는데, 어떤 노드의 아이디가 무엇인지 네트워크 안에 있는 모든 노드가 같은 값으로 알고 있어야 한다. 그래야 Kademlia가 주장하는 효율성을 가져올 수 있다. 문제는 분산 환경에서 각자의 아이디를 동의하는 방법이 없기 때문에 연결을 요청하는 노드가 자신의 public key를 알려주면 그 public key를 노드 아이디를 Keccak hashing 한 값을 노드 아이디로 준다. 즉, 각 노드가 자신의 아이디를 정하여 알려주는 것이다. 따라서 하나의 머신에서 여러 개의 노드 아이디를 생성해낼 수 있고, 악의적인 사용자가 하나의 머신을 여러 개의 노드인 것처럼 꾸미는 Sybil attack이 가능해진다.
이를 막기 위해 IP 주소와 노드 아이디를 기억하여 하나의 주소에서 여러 개의 키를 사용 못 하게 하는 것이 필요하지만, 아직 구현된 솔루션은 존재하지 않는다.

두 번째 공격 방법은 서버의 시간을 조정하는 것이다. 이더리움은 replay-attack을 막기 위해서 메시지에 보낸 시간을 적는다. 그리고 받은 메시지의 시간이 현재 시각과 20초 이상 차이가 나면 replay-attack으로 받은 메시지로 가정하고 무시한다. 문제는 replay-attack인지 판단하기 위해 메시지에 적힌 시간을 사용할 뿐, 메시지를 보낸 실제 시간은 알 수 없다는 것이다. 예를 들어 두 노드 사이에 시간이 20초 이상 난다면, replay-attack이 아닌 정상적인 메시지도 절대 처리되지 않는다.
현대 서버 환경에서 이럴 일은 거의 없다. 보통 서버 시간을 수동으로 설정하지 않고 NTP(Network Time Protocol)를 이용해 주기적으로 동기화하기 때문이다. 따라서 모든 서버의 시간은 길어봐야 몇 초 이내의 오차를 가질 것이라고 가정해도 된다.
하지만 이는 정상적인 상황에서만 가능한 가정이다. 만약 희생자가 될 노드가 사용할 NTP 서버를 해킹하거나 NTP 메시지를 가로채 동기화하지 못 하는 상황을 만들면 어떻게 될까. 아니면 조금 더 적극적으로 NTP 메시지를 가로채 실제 시간과 20초 이상 앞으로 당기면 어떻게 될까.
이 경우 희생자 노드는 네트워크상의 모든 노드와 시간 차이가 나게 될 테니, 다른 노드들은 모두 이 노드에서 보내는 메시지를 무시할 것이다. 그렇게 되면 희생자 노드는 네트워크에서 잊히게 되고 결국 희생자와 통신하는 것은 NTP 서버를 해킹했던 공격자 노드밖에 남지 않게 된다.
이는 메시지에 시간을 적는 방식으로 replay-attack을 막으려고 했던 이더리움 프로토콜의 문제다. 이런 공격을 막기 위해서는 세션별 혹은 메시지 별로 nonce를 사용하여 sign 하는 방법을 이용해야 한다. 하지만 이에 관한 솔루션도 아직 이더리움에는 구현된 것은 없는 것으로 보인다. 따라서 이더리움 노드를 돌리고 있는 서버는 시간이 잘 동기화되고 있는지 주기적으로 확인하는 방법밖에 없다.

마지막 공격 방법은 일종의 타이밍 어택이다. 이더리움은 네트워크에 너무 많은 리소스를 사용하지 않기 위해 통신할 최대 연결 수를 정해놓고 있다. 현재 최대 연결 수는 25개로 25개 이상의 연결이 맺어지면 더는 새 연결을 요청하거나 받아주지 않는다.
반대로 말해서 어떤 노드의 연결을 25개 점유할 수 있으면 이 노드는 더 이상 새 연결을 요청하지도 받아주지도 않을 것이다. 그렇다면 이것은 어떻게 가능할까?
간단하다. 연결이 0개인 순간을 노리면 된다. 어떤 서버라도 서버가 처음 시작했을 때는 연결이 0개인 상태가 된다. 이 타이밍을 노려서 25개의 연결을 먼저 맺으면 된다. 그렇다면 서버가 재시작되는 순간은 어떻게 찾을까.
하드웨어 문제든 OS 업데이트든 이더리움 클라이언트를 업데이트하든 서버가 재시작될 이유는 많이 있다. 하지만 조금 더 공격적으로 DoS 공격을 하여 이더리움 클라이언트를 죽이는 방법도 있다. 보통 이더리움 마이닝 노드는 서버가 종료되면 바로 다시 시작하게 돼 있기 때문에 DoS 공격으로 서버를 죽이고 나면 얼마 지나지 않아 서버가 재시작할 것이고 이때 25개 이상의 연결을 빠르게 요청하면 된다.
이를 막는 방법은 앞에서 설명한 두 방법보다 쉽다. 앞의 두 방법은 프로토콜 자체를 바꿔야 하지만 이 공격은 구현체를 수정하는 것만으로 쉽게 막을 수 있다. 전체 연결 개수 제한과 별개로 외부에서 들어오는 연결의 개수를 제한하는 것이다. 즉, 최소 몇 개의 연결은 내가 요청하는 노드와 연결이 되도록 하면 누군가 다른 사람에 의해 내 연결이 독점 당할 위험은 사라진다. 이 솔루션은 2월에 릴리즈 된 go-ethereum 1.8 버전부터 적용된 것으로 보인다.

2018-03-25

2018년 12번째 주

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

not invented here syndrome

not invented here syndrome이란 말 그대로 자신이 아닌 다른 사람 혹은 다른 팀에서 개발한 물건을 배척하는 태도를 말한다. 너무나 당연하게 이런 태도는 잘못된 것이다. 사람이 필요로 하는 것은 대부분 비슷하기 때문에 이미 그것을 만든 사람이 있을 것이다. 게다가 내가 천재가 아닌 이상 더 오랜 시간 개발되고 테스트해온 다른 라이브러리가 더 안정적으로 돌아갈 것은 당연하다.
하지만 요새는 오히려 반대의 태도. 즉, 모든 라이브러리나 툴을 외부에서 가져와서 해결하려는 태도 때문에 개발이 더 느려지게 되었다. 라이브러리 혹은 프레임웍은 일반적인 문제에 대해서 해결하고자 작성됐기 때문에 간단한 문제를 써드파티 라이브러리로 해결하려고 할 때 오히려 문제가 더 커지기도 한다. 널리 쓰이는 용어는 아니지만 이를 not invented here의 반대된다는 뜻에서 invented here syndrome이라고 부르는 사람도 있다.
결국 엔지니어링은 트레이드오프 사이에서 하나를 선택하는 것이기 때문에 직접 구현할지 써드파티 라이브러리를 사용할지 적절한 수준에서 잘 선택해야 한다.

조직문화와 리더십을 일치시키지 마라

회사 경영에서 추구하는 바를 크게 성과 지향과 관계 지향으로 나눴을 때 어느 쪽을 추구할 것인지에 대해서 조직이 추구하는 방향과 리더가 추구하는 방향을 일치시키지 말라는 글이다.
상식적으로는 리더가 성과 지향일 경우 조직 문화도 성과 지향적이어야 높은 성과를 내기 쉽고, 리더가 관계 지향일 때는 조직도 관계 지향적이어야 회사가 원활하게 돌아간다고 생각하기 쉬운데, 이를 전면적으로 부정하는 연구결과이다. 물론 성과지향인지 관계지향인지는 주관적인 것이기 때문에 단순 설문으로 잘 측정됐을지라거나, 구성원의 행복도 같은 것을 무시하고 재무제표 상에서의 성과만을 측정했다는 점에서 논란의 여지가 있을 수 있겠지만 그래도 조직을 운영할 때, 혹은 일 할 회사나 팀을 선택할 때 한 번 생각해볼 만한 주제라고 생각한다.

EditorConfig

얼마 전까지만 해도 거의 모든 작업을 vim으로만 했기 때문에, vim 설정만 잘해놓으면 됐다. 근데 최근에 Clion을 적극적으로 사용하게 되면서 둘 사이의 스타일이 달라져서 생기는 문제가 발생하게 됐다.
그래서 찾아보니 서로 다른 IDE에서 코딩 스타일을 통일하기 위한 EditorConfig라는 설정이 있다는 것을 알게 됐다. clion을 비롯한 JetBrains 제품들은 별도의 플러그인 없이도 EditorConfig 설정을 읽고 있고, vim을 위해서는 EditorConfig 팀이 제작한 플러그인이 존재한다.

CAP theorem

CAP theorem은 분산 스토리지는 consistency(a.k.a. C), availability(a.k.a A), partition tolerance(a.k.a. P)를 동시에 만족시킬 수 없다는 것이다. 여기서 C, A, P는 각자 일반적으로 사용되는 용어와 다른 용어로 사용되기 때문에 CAP theorem을 이해하려면 각자가 정의하는 것을 이해하는 것이 중요하다.

C는 모든 read operation이 최신 데이터를 받는 것을 보장하는 것이다. C를 보장하는 시스템은 만약 최신 데이터를 돌려줄 것을 보장하지 못한다면 에러를 돌려줘야 한다. 개인적으로 분산 스토리지를 구현할 때 C, A, P 중 가장 구현하기 어려운 특성은 C라고 생각한다.

A는 모든 operation이 에러가 아닌 데이터를 돌려주는 것이다. 이때 돌려주는 값은 최신 값이 아니어도 상관없다. 심지어 eventual consistencyA를 보장하는 시스템에서는 실제로 존재할 수 없는 데이터 조합이 생길 수도 있다.

P는 partition 상황에서도 시스템이 정상 동작해야 한다는 것이다. 여기서 시스템이 정상 동작한다는 것이 언제나 최신 데이터를 보장하거나 에러가 아닌 값을 준다는 것이 아니다. 그것은 CA가 보장하는 것이고 partition 상황에서도 partition이 아닌 상황과 같은 것을 보장하면 P를 보장한다고 할 수 있다.

근데 여기서 partition은 정말 네트워크 레이어에 문제가 생겨 물리적으로 다른 망이 구성되는 상황을 말하는 것이 아니다. partition은 일부 메시지가 전달되지 않는 상황도 포함된다. 이는 분산환경에서 매우 흔히 발생하는 일이고 P를 포기한다는 것은 결국, 분산 환경을 포기한다는 말이 되기 때문에 분산 데이터 스토리지를 만들 때는 결국 CPAP 중 하나를 선택해야 한다.

개인적으로 생각하기에 CPAP 중 구현하기 더 어려운 것은 CP라고 생각된다. 모든 노드가 언제나 같은 상태를 유지하게 하는 것은 생각보다 어렵고 비싸다. 게다가 CP는 근본적으로 AP보다 latency와 throughput이 떨어진다.

하지만 이런 문제에도 불구하고 데이터 스토리지를 사용하는 application을 선택하는 입장에서는 AP보다 CP를 선호해야 한다고 생각한다. CP 대신 AP를 선택하는 이유는 가용성 때문이다. 가용성은 분명 중요하다. 하지만 스토리지의 가용성과 application 전체의 가용성은 다른 말이다. 데이터 스토리지가 정상적으로 동작하고 있다고 하더라도, 데이터의 일관성이 보장되지 못해서 잘못된 값을 돌려주었다면 이 application은 정상적으로 동작했다고 말할 수 있을까.

이런 일을 방지하기 위해서 AP인 스토리지를 사용하는 로직에는 데이터를 체크하는 복잡한 로직이 들어간다. 복잡한 로직은 높은 버그 가능성과 같은 의미이다. application 로직이 복잡해져서 버그가 발생했고 이를 고치기 위해 서비스를 종료했다면 이 application의 가용성은 떨어지게 된다. 게다가 버그로 인해 잘못된 응답을 준 경우는 오히려 처리하기 쉽다. 만약 버그로 인해 잘못된 데이터가 스토리지에 저장됐다면 이는 잡기도 어려울뿐더러, 고치기도 어렵다.

APCP보다 latency와 throughput이 떨어지기 때문에 성능이 필요한 application을 위해서는 AP인 스토리지를 선택해야 주장하는 사람들도 있다. 하지만 성능도 가용성과 마찬가지로 스토리지의 성능은 스토리지를 사용하는 application의 성능과는 별개다. AP인 스토리지를 사용하여 CP인 스토리지를 사용할 때보다 높은 성능을 보여준다는 것을 주장하기 위해서는 데이터 스토리지의 처리 시간이 application 처리 시간의 대부분을 차지한다는 것을 증명해야 한다. 여기서 측정하는 시간은 단순히 데이터 스토리지에 요청한 operation의 처리속도가 아니라, 네트워크 전송 속도를 제외한 데이터 스토리지 내부의 소요 시간이어야 한다.

설령 스토리지가 처리 속도에 충분한 영향을 준다고 하더라도 AP인 데이터 스토리지를 선택하기 전에 중요한 것이 처리 속도인지, 스토리지를 바꾸지 않으면 처리 속도를 올릴 방법이 없는지 고민해봐야 한다.

2018-03-11

2018년 10번째 주

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

Slack Is Shutting Down Its IRC Gateway

 채팅 프로그램들은 누구나 겪는 문제 중 하나가 일부 사용자가 IRC 클라이언트를 포기하지 않는다는 것이다. Slack도 마찬가지였고, 이에 대해서 Slack은 IRC Gateway를 지원하여 IRC 사용자들도 Slack에 포함시키려는 노력을 하였다.

https://xkcd.com/1782/

 하지만 이제는 Slack을 IRC 클라이언트에서 사용할 수 없다. Slack이 IRC 서포트를 중지한다고 발표했다.
 모든 플랫폼에서 같은 사용자 경험을 주고 싶은데 IRC에서 지원하지 않는 기능들이 방해되기 때문이라고 한다. 하지만 이미 Slack에서 IRC Gateway를 사용하는 사람들은 그 한정된 기능에 적응하고 사용하고 있는 사람들일 텐데, 이 사람들을 포기하면서 같은 사용자 경험을 주는 것이 그리 중요한 일일까 싶다. 그보다는 IRC Gateway를 이용하는 사람들을 Slack이 유료로 파는 기능들을 사용하지 않기 때문이 아닐까 싶다.

Why RSS Still Beats Facebook and Twitter for Tracking News

 Facebook이나 Twitter 같은 SNS가 생긴 뒤로 많은 사람이 자신의 포스팅을 SNS에 올리기 시작했고, RSS(Rich Site Summary)는 이제 사용되지 않을 것으로 생각했다. 대표적인 RSS 구독 서비스였던 Google Reader가 2013년 서비스를 종료했던 것이 RSS의 죽음을 나타내는 가장 상징적인 사건이었다.
 하지만 사람들은 여전히 RSS를 포기하지 않았다. 5년이 지난 지금까지 사람들은 여전히 RSS를 사용하고 있다. RSS는 SNS가 가지지 못 하는 장점이 여러 개 있다.
 일단 RSS를 사용하면 내가 구독하고 있는 것을 못 보고 넘어갈 일이 없다. SNS는 기본적으로 최근 포스트를 우선으로 보여준다. 내가 매일 접속하여 꾸준히 보지 않으면, 놓치는 정보가 있을 수 있다.
 게다가 SNS에서 보여주는 정보는 내가 원하는 정보라고 확신할 수 없다. RSS는 내가 RSS Reader에 구독을 원하는 주소를 등록하는 방식이지만, SNS는 자신들이 추천하는 포스트를 나에게 보여준다. 나름대로의 추천 알고리즘을 통해 정보를 뿌려주지만 내가 원하는 글이라고 확신할 수 없다.
 마지막으로 RSS는 하나의 서비스만 사용하면 되는데, SNS는 종류별로 가입해야 한다. 글을 올리는 사람이 모든 SNS에 다 올리면 좋겠지만, 현실은 그렇지 않다. 모든 글을 구독하기 위해서는 모든 SNS에 가입해야 하고, 내가 원하는 글만 보는 것이 아니라 각 SNS가 추천하는 글도 다 보게 된다.
 이런 문제들을 해결할 방법이 나오기 전에는 RSS가 죽을 일은 없을 것 같다.

static local variable


 일단 C++11 이후. 즉, 모던 C++에서는 맞는 말이다. 그 이전에서는 멀티 스레드 프로그램에서는 싱글턴을 사용해야 했는데, 그런 경우가 있으면 2018년에 모던 C++이 아닌 상황에서 이미 망한 프로젝트니까 빠르게 도망치자.
 과거에, 그러니까 C++의 abstract machine이 스레드에 대해 고려를 하지 않았던 시절에는 여러 스레드에서 동시에 static local variable을 사용하는 것이 문제가 될 수 있었다. 하지만 모던 C++에서는 abstract machine에 스레드 개념이 들어갔고, 여러 스레드가 동시에 접근하더라도 static local variable이 단 한 번만 초기화돼야 한다고 명시됐으니 그냥 컴파일러를 믿고 사용하면 된다.

2018-03-04

2018년 9번째 주

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

Lifetime Safety: Preventing Leaks and Dangling

 Herb Sutter와 Neil MacIntosh가 쓴 C++에서 memory leakdangling pointer를 어떻게 없앨 수 있는지에 관한 글이다. 일반적으로 C++의 포인터는 매우 강력하기 때문에, memory leak이나 dangling pointer를 없애기 위해서 C++의 기능을 일부 제한하거나 새로운 문법을 추가하거나 한다. 하지만 이 글에서는 언어를 바꾸지 않으면서 런타임 오버헤드 없이 컴파일 타임에 분석할 수 있는 알고리즘을 제시한다.
 특히 이 알고리즘은 프로그램 전체를 분석하는 것이 아니라 함수 단위, 정확히는 블록 단위로 적용할 수 있고, 변수 재사용 등 많은 스타일 가이드에서 권하지 않지만 실제로는 많이 사용되는 패턴들에 대해서도 고려돼있기 때문에 레거시 코드에 적용하기도 좋다.
 기계적인 작업이기 때문에 툴을 만드는 것이 가장 좋을 것이다. 하지만 툴을 만들 여유가 없더라도 포인터나 레퍼런스를 어떻게 써야 안전한지 보여주는 좋은 글이기 때문에 일단 읽어보는 것을 추천한다.

GitHub DDoS 공격당함

 지난 2018년 2월 28일, GitHubDistributed Denial-of-Service(a.k.a. DDoS) 공격을 당해 약 10분 정도 서비스가 멈췄었다. 이 공격은 memcached를 이용한 공격으로 중국의 0kee team이 찾은 Deluge라는 기법을 이용한 공격이었다.
 Deluge는 다른 서버에 설치된 memcached에 데이터를 요청할 때 source IP를 목표가 되는 서버의 IP로 수정하여 보내, memcached 서버가 목표가 된 서버로 데이터를 보내게 만드는 공격이다.
 이런 부류의 공격을 IP spoofing이라고 하는데, 이는 Internet protocol(a.k.a. IP)OSI 7 layer에서 말하는 session layer에 관한 부분이 없기 때문에 생기는 근본적인 취약점을 이용한 것이기 때문에, 네트워크 프로토콜을 IP 위에 올린다면, 프로토콜을 작성하는 차원에서 세션 처리를 신경 쓰지 않았다면 근본적으로 막을 방법은 없다.
 IP spoofing 자체는 흔하게 사용되는 공격법이지만 memcached를 사용하는 Deluge는 그중에서도 큰 획을 그었다. 단순히 GitHub을 공격했기 때문이 아니라 적은 패킷으로 많은 데이터를 공격하게 할 수 있기 때문이다. 이 비율을 bandwidth amplification factor라고 하는데 Deluge는 지금까지 알려진 IP spoofing 공격 중에서 가장 높다.