블록체인 이해하기 : 장부와 비잔틴 장군문제

블록체인 이해하기 시리즈

들어가기 전 ..

이 글은 연세대학교 블록체인 학회 YBL의 pre track 에서 강연을 하기 전 생각을 정리하기 위해 쓴 글 입니다.
블록체인 이해하기 시리즈는 비트코인의 탄생 배경 과정을 순차적으로 따라가보면서 블록체인에 대한 이해를 돕고자 작성했습니다.

새로운 기술의 대한 열정이, 새로운 세상을 만들어 나가는데 도움이 되길 바랍니다.

글의 목표

1. 블록체인이라는 기술이 왜 분산장부라 불리는지 다른 사람에게 설명할 수 있습니다.
2. 비잔틴 장군 문제에 관해 설명할 수 있으며 합의 알고리즘이 어떤 역할을 하는지 알 수 있습니다.

거래와 장부 그리고 신뢰

블록체인은 공유되는 장부라 이야기 할 수 있습니다. 그렇다면 먼저 장부가 왜 생겨났는지 먼저 알아보고 넘어 가는 것이 좋습니다. 인류에게 장부라는 것은 왜 필요하게 됐을까요?
수렵과 채집 생활에서 벗어난 이후 생산이란 것을 시작한 인류의 선조들은 좋은 기후와 환경을 찾아 살아가게 됩니다. 생산능력이 증대됨에 따라서 잉여 생산물이 발생하면서 생산된 재화를 어떻게 소유하고 저장, 분배를 어떻게 규정해야 할지 고민해야 했습니다.
이를 해결하기 위해서 일종의 행정 통제가 필요했고, 행정 절차를 확립하기 위해 매체 역시 요구되었습니다.
새로운 경제 형태에 적합한 거래를 당사자끼리 합의하고 글자 형태로 기입할 필요가 생겨난 것입니다.
이렇게 해서 장부라는 형태의 문서가 생겨 났습니다.

그렇다면 장부에서 요구되는 사항 중 가장 중요한 것은 무엇일까요? 바로 “신뢰” 입니다.

현대적, 효율적 삶을 위한 수단으로 거래가 발생하지만, 거래가 진실로 이루어지기 위해서는 상호간의 신뢰가 필수적이었습니다. 이는 복식부기라는 개념을 처음 소개한 책의 머리글만 봐도 알 수 있습니다.

“신의 이름으로 기록한다” 복식부기를 처음 소개한 『대수, 기하, 비 및 비례총람』 (Pacioli,1494) 의 첫머리글

신뢰라는 것은 모든 거래에 있어 기초가 됩니다. 하지만 모든 거래 기록들을 어떻게 믿고 서로 합의에 이를 수 있을까요?

• 제 3자를 증인으로 장부를 기록하고 서로 가지고 있으면 될까요? (분산시스템)
• 만약 회계장부의 거래 기록들이 점점 엉망이 되면 어떻게 될까요? (악의적인 사용자 발생)
• 지금까지 거래했던 내역들이 모두 엉망이 되어 돈을 지급해야 할지 말지 알 수 없게되는 상황이 발생한다면? (정상적인 시스템 유지 실패)

사람들은 장부(시스템)에 기록된 거래들이 악의적인 사용자가 등장하더라도 어떻게 지켜질 수 있는가에 대해 고민하기 시작했습니다. (단일화된 결과, 상태의 유지 → 합의 문제) 이에 대한 문제는 비잔틴 장군문제 와도 연관이 있으며 비트코인이 탄생한 배경과 밀접한 관련이 있습니다.

1982 : 비잔틴 장군 문제

이름은 비잔틴 장군 문제이지만 실제로 비잔티움 제국에서 발생한 일은 아닙니다. 이 명칭은 1982년 ‘래슬리 램포트’라는 미국의 컴퓨터 공학자가 동료 2명과 함께 발표한 연구 논문에서 사용한 표현입니다.

지리적으로 떨어져 있는 서로 다른 장군들이 하나의 성을 함락시키기 위해 공격 방법을 합의하는 것에 대한 문제인데요. 장군들은 공격하거나 후퇴하기 위해서 동의를 얻어야 합니다. 모든 장군이 합의에 도달하는 한, 즉, 공격을 하든 후퇴를 하든, 협력적으로 결정에 동의한다면 아무런 문제가 없습니다.

가정된 상황은 다음과 같습니다.

• 각 장군들이 합동하여 과반수 이상이 출병해야만 적에게 승리할 수 있습니다.
• 각 장군들은 전령(messenger)를 통해서 연락을 주고 받습니다.
• 각 장군들은 근처의 장군에게 연락합니다.
• 장군들 중 배신자가 존재할 수도 있고, 배신자는 실제 전파받은 공격계획과 다른 내용을 전파할 수 있습니다. 메시지도 중간에 훼손될 수 있습니다.

여기서 메시지가 늦게 전달되거나, 훼손될 수 있거나, 없어질 수 있다는 사실이 관건입니다.

각 장군들은 열심히 합의에 이르고자 노력할테지만 악의적인 장군이 합의에 이르는 과정에 훼방을 놓을 것이며 이는 전쟁의 승패와도 연결된 문제이기 때문에 장군들은 쉽사리 결정을 할 수 없을 것입니다.

램포트의 논문을 보면 이러한 분산화된 시스템에서 합의를 달성할 수 있는 방법은 최소 2/3 이상의 신뢰할 수 있는 장군을 확보하는 것입니다. 2/3 이상의 장군들이 합의가 되면 퇴각명령이나 공격명령 모두 합의에 이를 수 있으며 (대다수가 같은 결정에 따른다는 행위가 중요합니다.) 어이없이 전쟁에서 패하는 경우는 생기지 않을 것입니다. 반면에 네트워크 참여자 1/3 이상이 악의적으로 행동할 경우 시스템이 실패할 수 있다는 것을 의미하기도 합니다.

비잔틴 장애 허용(BFT, Byzantine Fault Tolerance)

결론적으로 비잔티움 장군 문제는 다양한 산업에서 풀어야 할 사항입니다. 블록체인 산업 외에도, 항공, 우주, 원자력 산업에 비잔티움 장군 문제를 고려하고 있습니다.

비잔틴 장군 문제에 대한 저항성이 있다면 결함이 발생하더라도 전체적인 시스템의 기능이 유지되며 이런 시스템을 비잔틴 장애 허용 시스템이라고 부릅니다. 비잔티움 장애 허용 시스템은 일부 참여자(노드)가 고장나거나 악의적으로 행동하더라도 계속 작동할 수 있습니다.

비잔틴 장애 허용을 만드는 알고리즘은 여러가지가 존재하며 블록체인 산업에서는 이를 합의 알고리즘이라 부릅니다.

프랙티컬 비잔틴 장애 허용(PBFT)

다시 1982년으로 돌아가 래슬리의 비잔틴 장군 문제에 대해 정의한 논문을 좀 더 자세하게 살펴보면서 비잔틴 허용 분산 시스템을 어떻게 구현하는가 살펴보겠습니다.

이 방법은 ‘프랙티컬 비잔틴 장애 허용(PBFT)’이라 불리며 분산시스템이 약속된 행동을 하지 않는 노드가 존재할 수 있는 비동기 시스템(요청을 보낸 후 응답과는 상관없이 다음방식이 동작하는 방식)일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘입니다.

기존의 비잔틴 장애 허용 알고리즘들은 동기식 네트워크에서만 합의가 가능했으나 PBFT의 경우는 비동기 시스템에서도 합의가 가능하도록 만든것에 그 의의가 있습니다.

PBFT를 구현하기 위해 지휘관과 지휘관의 명령을 받은 부관들에 대한 개념이 등장하게 되는데요. 구현하는 방식은 다음과 같습니다.

1. 지휘관이 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들(부관들)에게 전파합니다.
2. 지휘관의 메시지를 받은 노드들(부관들)은 다른 노드들(부관들)에게서 받은 메시지를 다시 한번 나머지 노드들(부관들)에게 전파합니다.
3. 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에 전파합니다.
4. 앞의 과정이 끝나면 모든 노드는 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 됩니다.

이 알고리즘은 결국 대다수의 노드가 가지고 있는 정보가 전체의 상태가 된다 라는 것을 이야기 해줍니다. 이는 각 노드들이 인접한 노드에게만 메시지를 전송할 수 있기때문에 가능한 방법입니다.

여기서 잊지 말아야 할 것은 대다수의 부관들이 특정한 행동을 하게 만드는 것이 목표가 아니라는 것입니다. 대다수의 부관들이 동일한 결정을 하도록 만드는 것이 비잔틴 장애 허용의 핵심입니다. 심지어 지휘관이 배신자여도 전쟁에서는 승리할 수 있습니다. 대다수의 인원이 성 함락에 참여하거나 참여하지 않는다는 사실은 바뀌지 않기 때문입니다.

논문에 있는 그림을 통해 예시를 들면서 다시한번 이야기 해보겠습니다.

먼저 부관 3이 배신자인 경우 입니다. 지휘관은 v라는 명령을 각 부관에게 전파했습니다. 부관 1,2,3은 v라는 명령을 받았고 이를 확인하기 위해서 다른 부관들의 의견을 한 번 더 받아봅니다. 부관1은 지휘관에게 v를 받았고 부관2에게도 v를 받았으니 v를 실행할 것입니다. 부관3은 배신자이기 때문에 x를 실행하기로 마음먹고 x를 하달받았다고 근처에 있는 부관2에게 전파합니다. 그러나 부관2는 지휘관에게 v를 받고 부관1에게 v를 받아 x를 전파받은 것보다 더 많은 v를 전파받은 상태이므로 v를 실행합니다.

따라서 3/4이 v에 대해 합의하고 전체적인 시스템은 유지가 됩니다.

지휘관이 배신자인 경우에는 어떻게 될까요? 우선 지휘관이 x라는 명령을 하달합니다. 부관들도 x라는 명령에 대해 서로에게 전파를 하고 전체적인 시스템은 x에 대해 합의합니다. x라는 명령을 모두가 실행하더라도 전쟁에서는 문제될것이 없습니다. 공격이라면 성을 함락시키는데에 성공할 것이고 후퇴라면 모두가 살아남기 때문입니다.

그렇기에 PBFT를 따르게 되면 전체적인 시스템은 유지되는데에 문제가 생기지 않습니다.

합의 알고리즘

블록체인 시스템은 탈중앙화된 공유장부입니다. 악의적인 노드들은 장부에 저장된 가치를 바꾸기위해 결함을 만들것이며 이를 막기 위해서는 비잔틴 장애 허용 시스템 구축이 필수적입니다.

블록체인 기술에서 비잔틴 장애 허용시스템을 만들어 주는 것은 합의 알고리즘이라 할 수 있습니다. 합의 알고리즘이 없다면 블록체인의 안정성은 무너질 수 밖에 없습니다. 중앙에서 관리하지 않기때문에 다시 복구할 방법 또한 존재하지 않습니다.

비트코인은 PoW라는 합의 알고리즘 방식을 사용합니다. 확률론적으로 비잔틴 장군 문제에 저항성을 갖도록 하는 알고리즘인데 앞서 살펴본 PBFT와는 다른 성질을 지니고 있습니다. 이에 대해서는 다음에 자세히 알아보도록 하겠습니다.

마치며

지금까지 블록체인이 어떠한 기능을 하는지, 합의 알고리즘이 왜 등장했으며 블록체인 시스템에서 왜 쓰이는지 함께 알아보는 시간을 가졌습니다.

블록체인이라는 것이 갑자기 발명된 것이 아니라 여러 기술들의 집합체라는 것을 설명하기 위해 차근차근 개념들을 정리해나갈 생각입니다.

잘못된 내용이 있다면 언제든지 수정요청을 해주시길 바랍니다. 감사합니다.

참고문헌

https://www.microsoft.com/en-us/research/uploads/prod/2016/12/The-Byzantine-Generals-Problem.pdf

https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained

https://en.wikipedia.org/wiki/Byzantine_fault