합의 알고리즘 개요

이전 포스팅에서는 loopchain의 스마트 컨트랙트인 SCORE(Smart Contract On Reliable Environments)에 대해서 알아보았습니다.

블록체인 기술 연재 시리즈
블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment)

이전 포스팅 들에서 설명한 스마트 컨트랙트(Smart Contract)의 경우 라이트닝 네트워크(Lighting Network)와 함께 블록체인을 응용한 서비스를 하는데 꼭 필요한  대표적인 기술입니다.  이번 포스팅에서는 블록체인을 지탱하는 핵심 기술분산합의 알고리즘에 대해 알아보도록 하겠습니다.

합의 문제(Consensus Problem) 

블록체인은 기본적으로 분산 시스템입니다. 합의 문제는 분산 시스템의 신뢰도를 보장하기 위해 나온 개념으로 블록체인이 나오기 전부터 존재하던 개념입니다. 이를 한 줄로 요약한다면 모든 분산 시스템에 참여하고 있는 모든 프로세스가 같은 결과 값을 결정해야 한다는 것입니다.  이것이 왜 필요할까요?

분산 컴퓨팅으로 이루어진 비행기 예매 시스템에 합의 알고리즘이 없다고 가정해봅시다. 손님 A와 손님 B가 같은 자리a를 동시에 예매 하였을 때 합의 알고리즘이 없다면 들어온 시스템에 따라 자리 a를 예매한 사람이 달라집니다. 이런 시스템 오류와 무결성을 보장하기 위하여 합의 문제를 해결하는 합의 알고리즘이 생겨났습니다.

스크린샷 2017-05-23 오전 8.56.04
합의 알고리즘이 없는 비행기 예매 시스템

합의 문제를 해결하는 합의 알고리즘은 3가지 조건을 만족해야 합니다.

  • 모든 Process가 같은 값을 결정
  • 결정된 데이터는 특정 Process에 의해 제안된 것이어야 함
  • 모든 시스템의 상태는 0이나 1로 결정 되어야 함(모두 1인지 0인지 판단 할 수 있어야 함)

대표적인 합의 알고리즘으로는 Paxos와 Raft가 있습니다. 블록체인에서도 합의 문제는 매우 중요합니다. 전재산 1000원을 가지고 있는 A가 1000원을 B에게 송금하는 메세지를 보내면서 C에게 송금한다는 메세지를 동시에 보냈을때 블록체인 시스템에서 합의를 하지 못하면 큰 문제가 생길 수 있습니다.

비잔틴 장군 문제(Byzantine General Problem)

블록체인은 합의 문제 말고도 비잔틴 장군 문제라는 분산 네트워크 문제를 해결하는 시스템입니다. 비잔틴 장군 문제는 분산 컴퓨팅의 아버지 레슬리 램포트(L. LAMPORT)가 논문을 통해 처음 으로 악의적인 노드가 분산 시스템에 참여한 상황을 모델링한 문제입니다. 비잔틴 장군 문제를 해결한 시스템은 악의적인 노드가 분산 시스템에 참여한 상황에서도 전체 시스템은 신뢰도 있는 서비스를 제공할 수 있다는 것을 보장합니다.

비잔틴 장군 문제

  • 흩어져 있는 비잔틴의 장군들이 성을 공격하려 합니다. 모든 장군들이 같이 공격을 한다면 이길 수 있는 상황
  • 장군들은 흩어져 있기 때문에 같은 시간에 공격하기 위해 메세지를 공유
  • 하지만 비잔틴 장군 들 중 첩자가 있어 중간에 메세지를 교체할 수 있음
  • 이때 모든 장군들이 같은 시간에 공격을 할 방법은?
0--xCD-El4LZ48dji1.png
비잔틴 장군 문제(출처 : https://goo.gl/OKSivi)

문제에서는 장군들로 표현하였지만 네트워크에 있는 악의적인 노드와 오작동 하는 노드를 첩자라고 생각하면 됩니다. 비잔틴 장군 문제를 해결하는 분산 시스템은 특정 노드가 해킹이나 오작동이 발생해 문제가 생겨도 네트워크는 여전히 신뢰도 있는 서비스를 제공할 수 있습니다. 대표적인 비잔틴 장애 허용(Byzantine Fault Tolerance)알고리즘으론 PBFT(Practical Byzantine Fault Tolerance)가 있습니다.

블록체인의 경우 하나의 주체가 네트워크를 구성하는 것이 아닌 신뢰관계가 아닌 노드들이 모여서 네트워크를 구성합니다. 또한 각각의 노드들은 네트워크 조작을 통해 부당한 이득을 취하는 게 가능합니다. 따라서 블록체인 시스템은 비잔틴 장군 문제를 해결해야만 합니다. 비잔틴 장군 문제를 해결함으로써 네트워크에 악의적인 노드가 존재하더라도 신뢰도 있는 시스템을 제공하는 것을 보장할 수 있습니다.

오늘 포스트에서는 합의 문제와 비잔틴 장군문제가 무엇인지에 대해 알아보았습니다. 다음 포스트에서는 공개 블록체인에서 위의 문제를 해결하기 위해 사용하는 대표적인 알고리즘인 작업증명(Proof of Work)과 지분증명(Proof of Stake)에 대해 알아보겠습니다.

1 thought on “합의 알고리즘 개요”

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중