블록체인의 기본 원리 이해, 제 1부:비잔틴 결함 방지

Published in

Loom Network Korean

9 min readJul 14, 2018

이 글은 Georgios Konstantopoulos가 쓴 Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance을 번역한 글입니다. 오역이 있으면 Private Note 기능으로 알려주세요!

블록체인 기본 원리 이해 시리즈에 해당하는 글:

블록체인은 본래 그들의 동기와 그들이 이용할 수 있는 정보에 따라 행동하는 다른 행위자들로 구성되는 탈중앙화 시스템입니다.

새로운 거래가 네트워크에 방송될 때마다, 노드들은 그들의 원장 복사본에 그 거래를 포함시키거나 그것을 무시하는 옵션을 가지죠. 네트워크를 구성하는 대다수의 행위자들이 싱글 상태를 결정할 때 합의가 이루어집니다.

분산 컴퓨팅과 멀티 에이전트 시스템의 근본적인 문제는 다수의 오류가 존재하는 프로세스에서 전반적인 시스템 신뢰성을 달성하는 것입니다. 이를 위해서는 계산을 수행하는 동안 필요한 일부 데이터 값에 대해 합의하는 프로세스가 필요한 경우가 많죠.¹

이러한 과정들은 합의로 묘사됩니다.

행위자가 규칙을 따르지 않고 원장의 상태를 변조하기로 결정하면 어떻게 될까?
이러한 행위자들이 네트워크의 큰 부분을 차지하지만 대다수가 아니면 어떻게 될까?

안전한 합의 프로토콜을 생성하려면 결함 방지 기능이 있어야 하죠.

첫째, 해결할 수 없는 2개의 장군들의 문제들에 대해 간단히 이야기하죠. 그리고 나서 우리는 그것을 비잔틴의 장군들의 문제로 확장하고 분산된 탈중앙화 시스템에서 비잔틴 결함 방지에 대해 논의할 것입니다. 마지막으로, 우리는 이 모든 것이 블록체인 공간과 어떻게 관련되어 있는지에 대해 토론해 보시죠.

두 장군들 문제

이 문제는 (1975년에 처음 출판되어 1978년에 그 이름이 주어짐) 두 장군이 공동의 적을 공격하고 있는 시나리오를 묘사합니다. 장군 1은 리더로 간주되고, 다른 장군은 추종자로 간주됐죠. 각 장군의 군대만으로는 적군을 성공적으로 무찌르기에 부족하기 때문에, 그들은 협력하고 동시에 공격해야 했죠. 이는 단순한 시나리오처럼 보이지만 한가지 경고가 있습니다:

그들이 의사 소통을 하고 시간을 결정하기 위해서는, 장군 1은 적의 캠프를 가로질러 메신저를 보내서 공격 시간을 장군 2에게 전달하도록 해야 하죠. 하지만, 메신저가 적들에게 잡힐 가능성이 있어서, 그 메시지는 전달되지 않을 것입니다. 그것은 장군 1이 공격하는 것을 초래할 것이고 장군 2와 그의 군대는 그들의 기반에서 머무를 것이죠.

첫 번째 메시지가 전달 되더라도, 장군 2는 메세지를 받았다고 인정해야 하고 (ACK, TCP의 3-way 핸드셰이크와 유사하다는 것을 알 수 있음) 그가 메신저를 되돌려 보내, 메신저가 잡히는 이전에 시나리오를 반복 할 것이죠. 이것은 무한 ACK’s를 확장하며, 따라서 장군들은 합의에 도달할 수 없겠죠.

각각의 장군들이 상대방이 공격 계획에 동의했는지 확인하는 두번째 요구 사항을 보장할 방법은 없습니다. 두 장군 항상 모두 그들의 마지막 메신저가 왔는지 궁금해 할 뿐이겠죠.

메세지가 전달되지 않을 가능성이 항상 0보다 크기 때문에, 장군들은 절대 100%자신감으로 동의에 도달할 수 없습니다.

이 두 장군들의 문제는 해결할 수 없는 것으로 증명되었습니다.

비잔틴 장군들의 문제

1982년 Lamport, Shostak그리고 Pease에 의해 널리 묘사된 것처럼, 그것은 두 장군들의 문제의 일반화된 버전을 약간 변형한 것입니다. 이 것은 두 명 이상의 장군들이 그들의 공동의 적을 공격하는 시간에 동의해야 하는 같은 시나리오를 묘사하고 있죠. 여기서 더욱 복잡한 것은 하나 이상의 장군들이 반역자가 될 수 있다는 것인데, 이것은 그들이 자신의 선택에 대해 거짓말을 할 수 있다는 것을 의미하죠. (예를 들면, 그들은 그들이 0900을 공격한다고 동의 했지만, 공격하지 않는 거죠.)

두 장군들의 문제에 설명된 리더-추종자 패러다임은 지휘관-중위 설정으로 변환됩니다. 여기서 합의를 이루기 위해서는 지휘관과 모든 중위가 같은 결정에 동의해야 하는 것이죠 (간단한 공격이나 퇴각을 위함).

IC2에 덧붙여, 여기서 더 빅재미인 것은, 만약 사령관이 반역자라면, 합의는 반드시 이루어져야 한다는 것이죠. 결과적으로, 모든 중위들이 과반수의 표를 얻는 것입니다.

이 경우, 합의에 도달하기 위한 알고리즘은 중위가 관찰하는 결정의 대부분의 가치를 베이스로 하는 거죠.

이론: 모든 m에서, 만약 3m이상의 장군들과 대부분 m의 반역자들이 있다면, 알고리즘 OM(m)는 합의에 도달합니다.

이는, 행위자의 3분의 2가 정직하는 한, 알고리즘이 합의에 도달할 수 있다는 것을 의미합니다. 만약 반역자들이 3분의 1이상이 되면 합의에 이르지 못하면, 군대는 그들의 공격을 조정하지 않을 것이고, 적들이 이기죠.

m = 0 → 반역자는 없고, 각각의 중위는 명령에 따름 | m > 0 → 각각의 중위의 최종 선택은 모든 중위의 선택에서 나옴

이 것은 Lieutentant2의 시각적인 관점에서 좀 더 명확해져야 합니다 — C는 사령관이 되고 L{i}은 중위 i가 되어라:

단계:

사령관은 v를 모든 중위에게 보냄
L1는 v를 L2에게 보냄 | L3는 x L2에게 보냄
L2 ← 다수결(v,v,x) == v

최종 결정은 L1, L2, L3의 다수결이며 결과적으로 합의가 이루어졌죠.

여기서 기억해야 할 중요한 것은 대다수의 중위들이 특정한 결정이 아닌 동일한 결정을 내리는 것이 목표라는 것입니다.

사령관이 반역자인 경우를 살펴 보시죠:

단계:

사령관은 각각 x, y, z를 L1, L2, L3으로 보냄
L1은 x를 L2, L3에게 보냄 |L2은 y를 L1, L3에게 보냄 |L3는 z를 L1, L2로 보냄
L1 ← 다수결(x,y,z) | L2 ← 다수결(x,y,z) | L3 ← 다수결(x,y,z)

그들은 모두 같은 값을 가지고 있어서 합의에 도달합니다. 잠깐 여기 반영하는것을 보시면, 비록 x, y, z가 모두 다르더라도 모든 3명의 중위들에게 다수결의 값(x, y, z)이 동일하다는 거죠. x, y, z가 완전히 다른 사령관들인 경우, 기본 옵션 퇴각에서 동작한다고 가정할 수 있겠죠.

7명의 장군들과 2명의 반역자들에 대한 좀 더 실제적인 접근과 더 복잡한 예를 위해, 이 글을 읽어 보는것도 좋을 것 같아요.

비잔틴 결함 방지

비잔틴 결함 방지는 비잔틴 장군들의 문제에 속하는 실패의 등급을 방지하는 시스템을 정의하는 특징입니다.비잔틴 실패는 실패 모드의 가장 어려운 부류입니다. 이는 어떠한 제한도 내포하지 않으며 노드가 할 수 있는 행동에 대한 가정을 만들려 하지 않죠(예를 들면, 노드는 정직한 행위자처럼 행동하면서 어떠한 임의의 데이터를 생성할 수 있음).

비잔틴 결함은 가장 심각하고 다루기 어렵습니다. 비잔틴 결함 방지는 비행기 엔진 시스템, 원자력 발전소 그리고 많은 양의 센서의 결과에 따라 결정되는 거의 모든 시스템에 필요로 하죠. 스페이스 X도 시스템에 대한 잠재적인 요구 사항으로 고려했었습니다.

이전 섹션에서 언급된 알고리즘은 반역자의 수가 장군들의 3분의 1을 초과하지 않는 한 비잔틴 결함 방지라 합니다. 디지털 서명을 사용이나 네트워크 상에서의 동료 사이에 통신 제한을 부과하는 것을 포함하여, 문제를 쉽게 해결할 수 있는 다른 변형이 존재하죠.

이 모든 것이 블록체인과 어떻게 관련되어 있는거죠?

정의를 내리자면, 블록체인들은 중앙 당국에 의해 통제되지 않는 탈중앙화 ledgers 입니다. 이러한 ledgers들에 저장된 가치 때문에, 나쁜 행위자들은 결점 만들기를 시도하고 일으키는 엄청난 경제적 동기를 가지고 있죠. 그것을 비잔틴 결함 방지라 말하는, 블록체인을 위해 비잔틴 장군들의 문제에 대한 해결책이 필요한 것이죠.

BFT가 없으면, 동료가 블록체인의 안정성을 효과적으로 무효화하는 잘못된 트랜잭션을 전송하고 게시할 수 있습니다. 상황을 더 악화 시키는 것은, 피해를 인수하고 복구할 중앙 당국이 없다는 것이죠.

비트코인이 발명되었을 때 가장 큰 돌파구는 이 이메일에서 사토시 나카모토가 상세히 설명한 비잔틴 장군들의 문제의 확률론적 해결책으로서 작업증명 (PoW)을 사용한 것이었습니다.

결론

이 글에서는 분산 시스템의 합의에 대한 몇 가지 기본적인 개념에 대해 논의했죠.

다음 글에서는 블록체인에서 비잔틴 결함 방지를 달성하기 위해 사용되는 알고리즘에 대해 논하고 비교할 것입니다.

구독 신청을 하시면 라이브가 될 때 알림을 받으실 수 있어요!

Loom Network는 고성능 디앱을 확장하기 위한 멀티체인 상호운용 플랫폼입니다 — 이미 상용 가능한 상태이며, 감사 및 실제 테스트를 거쳤습니다.

Loom 베이스체인에 여러분의 디앱을 한 번 배포하고 나면, 오늘날 모든 주요 블록체인에 걸쳐 가능한 가장 광범위한 사용자 기반에 접근할 수 있습니다.

Loom Network를 처음 접하시나요? 여기서 시작하세요.

LOOM 토큰을 스테이킹해서 베이스체인을 보호하는 데 참여하고 싶으신가요? 여기서 그 방법을 알아보세요.

우리가 하는 일이 마음에 드시나요? 그렇다면 어서 우리의 프라이빗 메일링 리스트에 가입하고, 우리가 계속 전달하는 모든 업데이트를 계속 받아보세요.