레이블이 Byzantine Failure인 게시물을 표시합니다. 모든 게시물 표시
레이블이 Byzantine Failure인 게시물을 표시합니다. 모든 게시물 표시

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-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을 가정하고 나올 것이다. 그래서 설령 블록체인 개발을 하지 않더라도 블록체인에서 어떤 연구가 되고 있는지 아는 것은 분산 시스템 개발자로서도 중요하다고 생각한다.