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을 설명하면서 자세히 얘기하도록 하겠다.