블록체인 합의 알고리즘의 correctness

블록체인 기술의 핵심이 합의 알고리즘이다 보니 전산 전공자가 아닌 분들도 PoW나 PoS, BFT 같은 합의 알고리즘에 대해 엔지니어들 못지 않은 지식을 자랑하는 걸 많이 볼 수 있습니다. 그리고 신규 블록체인 플랫폼이 저마다의 합의 알고리즘을 하나씩 내놓으면서 유행처럼 많은 합의 알고리즘을 쏟아져 나오고 있습니다.

여러 대의 노드가 트랜잭션의 내용과 순서를 합의하는 방법이야 얼마든지 많으니 수많은 합의 알고리즘이 나오는 것도 이상한 일은 아닙니다. 하지만 합의 알고리즘이 아무리 그럴싸 해도 다음 두 가지 속성을 만족시키지 않으면 아무 소용이 없습니다.

  • Safety: 나쁜 일이 일어나지 않음
  • Liveness: 좋은 일은 언젠가는 일어남

합의 알고리즘이 safe하지 않으면 블록에 포크가 발생하게 되고, 합의 알고리즘이 live하지 않으면 합의를 영원히 못하고 교착 상태에 빠질 수 있습니다.

따라서 합의 알고리즘을 검토하고 공부하실 때 가장 중요하게 보셔야 할 항목은 safety와 liveness에 대한 formal proof입니다. 두 속성을 수학적으로 증명하지 못한 합의 알고리즘은 사실상 이런 식으로 하면 합의가 될 것 같다는 직관 그 이상도 이하도 아닙니다.

한 예로, Raft 합의 알고리즘을 BFT로 수정한 Tangaroa라는 합의 알고리즘이 있습니다. 스탠포드 대학원생 2명이 분산 컴퓨팅 수업 들으면서 과제 보고서로 제출한 합의 알고리즘인데, 어떤 이유인지 유망한 BFT 합의 알고리즘으로 둔갑하여 Kadena Juno나 ScalableBFT 같은 블록체인 프로젝트에도 적용이 되었습니다. 그런데 이 합의 알고리즘은 safety, liveness 두 가지 다 문제가 있습니다.

분산 컴퓨팅은 수많은 가능성을 고려해서 모든 문제를 다 대비해야 하고, 그럴려면 수학적인 증명이 필수입니다. 누가 세상에 없던 고성능 합의 알고리즘을 만들었다고 주장한다면 safety/liveness에 대한 formal proof 먼저 확인하시기 바랍니다.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s