공부 노트: 비잔틴 장군 문제 6장, 신뢰성 있는 시스템

이번주 토요일 동국대 블록체인 학회 '블리펀트'에서 'The Byzantine Generals Problem' 논문 스터디를 진행했다. 내가 전체적인 스터디 리딩을 맡았고, 6장, 7장 요약 및 정리를 담당했다.
비잔틴 장군 문제는 두 번째 읽는 것이지만, 여전히 개헬이다... 아직도 수식은 외계어처럼 보인다.
그러나 공부하는 과정에서 서로 의견을 교환하고 토론하다 보니 이제 전체적인 윤곽은 그려진다. 비잔틴 장군 문제의 출발점이 되는 논문을 공부함으로써 POW(작업증명)와, PBFT(실용적 비잔틴 장애 허용)라는 비잔틴 장군 문제 솔루션으로 넘어가는 다리는 놓은 듯 하다.

공부하면서 6, 7장을 구글 번역기의 도움을 받아 번역을 해봤다. 요새 구글 번역기가 훌륭해서 어색한 문장 정도만 고쳐도 봐줄 만한 번역문이 되는 듯 하다. 전체 논문 페이지수는 20페이지이며, 1장부터 7장까지 있다. 이번엔 6, 7장만 번역했는데, 논문 난이도가 헬이라 그런지 의외로 시간이 많이 걸렸다. 번역문을 봐도 내용이 어려워서 이해하기 어려운데, 영어 원문은 정말 말이 안나온다...;; 좌절감과 더불어 영어 공부를 더 빡시게 해야겠다는 의욕을 불어넣어준 논문이다. 공부한 내용을 잊지 않기 위해, 그리고 영어 공부도 할 겸 남은 챕터도 시간이 날 때마다 번역하려고 한다.

오늘은 우선 6장 번역본 초안만 올렸다. 초안인지라 가독성은 매끄럽지 못하다. 나중에 전체적으로 번역하고, 문장을 내 언어에 맞게 수정할 계획이다. 이 작업이 언제 끝날 지는? 음, 글쎄 나도 잘 모르겠다. 일단 해보는 거지 뭐.

---

6.신뢰성 있는 시스템

본질적으로 신뢰할 수있는 회로 구성 요소를 사용하는 것 외에 신뢰할 수 있는 컴퓨터 시스템을 구현하는 유일한 방법은 여러 가지 "프로세서"를 사용하여 동일한 결과를 계산 한 다음 결과에 대해 다수결을 수행하여 단일 값을 얻는 것입니다. 투표는 시스템 내에서 수행될 수도 있고 출력 사용자가 외부에서 수행될 수도 있습니다. 이것은 개별 칩의 고장으로부터 보호하기 위해 여분의 회로를 사용하는 안정적인 컴퓨터를 구현하든 아니면 핵 공격으로 개별 사이트를 파괴하지 못하도록 중복 컴퓨팅 사이트를 사용하는 탄도 미사일 방어 시스템을 구현하든 상관 없습니다. 유일한 차이점은 복제된 "프로세서"의 크기입니다.

신뢰성을 높이기 위해 다수결을 사용하는 것은 모든 정상적인 프로세서가 동일한 출력을 생성한다는 가정에 기반합니다. 이것은 모두 동일한 입력을 사용하는 한 사실입니다. 그러나 단일 입력 데이터는 단일 물리적 구성 요소 (예 : 안정적인 컴퓨터의 다른 회로 또는 미사일 방어 시스템의 일부 레이더 사이트)에서 발생하며 오작동한 구성 요소는 다른 프로세서에 다른 값을 줄 수 있습니다. 또한, 다른 프로세서는 값이 변하는 동안 값을 읽으면 결함이 없는 입력 장치에서도 다른 값을 얻을 수 있습니다. 예를 들어, 두 개의 프로세서가 시계를 읽는 중에 시계를 읽으면 이전 시간과 다른 시간을 가져올 수 있습니다. 이것은 시계의 나아감과 읽기를 동기화함으로써만 예방할 수 있습니다.

과반수 투표로 안정적인 시스템을 만들려면 다음 두 가지 조건을 만족해야 합니다:

1. 모든 정상적인 프로세서는 동일한 입력 값을 사용해야합니다 (따라서 동일한 출력을 생성합니다).
2. 입력 장치에 결함이 없으면 모든 결함이 없는 프로세스는 입력으로 제공한 값을 사용하여 올바른 출력을 생성합니다.

이것들은 우리의 대화형 일관성 조건 IC1과 IC2입니다. 여기서 "지휘관"은 입력을 생성하는 단위이고 "중위"는 프로세서이며 "충성도가 높은"은 결함이 없음을 의미합니다.

"하드웨어"솔루션으로 문제를 우회하려고 시도하고 있습니다. 예를 들어, 모든 프로세서가 동일한 입력을 얻도록 하려고 시도 할 수 있습니다. 그들 모두가 같은 전선에서 그것을 읽음으로써 가치를 얻습니다. 그러나 오류가 있는 입력 장치는 일부 프로세서에서 0으로 해석할 수있는 신호와 다른 것으로부터 1로 해석할 수 있는 신호를 따라 주변 신호를 보낼 수 있습니다. 프로세서가 비잔틴 장군 문제를 해결하기 위해 서로 통신하는 것을 제외하고는 서로 다른 프로세서가 오류가있는 입력 장치에서 동일한 값을 얻을 수 있음을 보장할 수있는 방법이 없습니다.

물론, 잘못된 입력 장치는 의미없는 입력 값을 제공 할 수 있습니다.비잔틴 장군 솔루션이 할 수 있는 모든 것은 모든 프로세서가 동일한 입력 값을 사용한다는 것을 보장합니다. 입력이 중요한 경우 중복 값을 제공하는 여러 개의 별도 입력 장치가 있어야합니다. 예를 들어, 미사일 방어 시스템에 여분의 레이더와 중복 처리 사이트가 있어야합니다. 그러나 중복 입력은 안정성을 확보할 수 없습니다. 결함이 없는 프로세서가 동일한 출력을 생성하기 위해 중복 데이터를 사용하는 것을 보장할 필요가 있습니다.

입력 장치에 오류가 없지만 값이 변경되는 동안 읽혀지기 때문에 다른 값을 제공하는 경우에도 오류없는 프로세서가 적절한 입력 값을 얻길 바랍니다. 대다수의 함수와 선택 함수가 중앙 함수로 사용된다면, 우리의 알고리즘은 오류가 없는 프로세서가 얻은 값이 입력 장치가 제공한 값의 범위 내에 있다는 특성을 가지고 있음을 알 수 있습니다. 따라서, 오류가 없는 프로세서는 입력 단위가 적당한 값의 범위를 생성하는한 합리적인 값을 얻을 수 있습니다.

우리는 여러 가지 해결책을 제시해 왔지만 컴퓨팅 시스템이 아닌 비잔틴 장군의 관점에서 언급되었습니다. 이제 이러한 솔루션이 안정적인 컴퓨팅 시스템에 어떻게 적용될 수 있는지 검토합니다. 물론 프로세서와 함께 "장군" 알고리즘을 구현하는 데 문제가 없습니다. 문제는 가정 A1-A3 (알고리즘 SM(m)에 대한 가정 A1-A4)을 충족하는 메시지 전달 시스템을 구현하는 데 있습니다. 이제 이러한 가정을 순서대로 고려합니다.

A1. 가정 A1은 오류가 없는 프로세서가 보낸 모든 메시지가 올바르게 전달된다고 말합니다. 실제 시스템에서는 통신 회선이 실패할 수 있습니다. 구두 메시지 알고리즘 OM (m)과 OM (m, p)의 경우 두 프로세서를 결합하는 통신 회선의 오류는 프로세서 중 하나의 오류와 구별할 수 없습니다. 따라서 우리는 이러한 알고리즘이 현재 상태에서 작동함을 보장 할 수 있습니다. 프로세서 또는 통신 회선 장애가 발생해도 최대 m 개의 장애가 발생할 수 있습니다. (물론 동일한 프로세서에 연결된 여러 통신 회선의 장애는 단일 프로세서 장애와 같습니다.) 실패한 통신 회선이 서명된 메시지의 위변조를 초래할 수 없다고 가정하면 - 아래에서 볼 수 있는 가정은 상당히 합리적입니다. 그러나 서명된 메시지 알고리즘 SM(m)은 통신 회선 실패에 민감하지 않습니다. 보다 정확하게, 정리 4는 통신 회선 장애가 있는 경우에도 유효합니다. 실패한 통신 회선은 단순히 통신 회선을 제거하는 것과 동일한 효과가 있습니다. 이는 프로세서 그래프의 연결성을 낮춥니다.

A2. 가정 A2는 프로세서가 수신한 메시지의 발신자를 프로세서가 결정할 수 있다고 명시합니다. 실제로 필요한 것은 결함 있는 프로세서가 결함이 없는 프로세서를 가장할 수 없다는 것입니다. 실제로 이는 프로세스 간 통신이 일부 메시지 교환 네트워크가 아닌 고정 회선을 통해 이루어짐을 의미합니다. (스위칭 네트워크가 사용되는 경우 결함이있는 네트워크 노드는 고려하고 비잔틴 장군 문제가 다시 나타납니다.) 다른 프로세서의 가장은 메시지를 위조한다는 것을 암시하기 때문에 A4가 가정되고 모든 메시지가 서명된다고 가정하면 A2는 필요하지 않습니다.

A3. 가정 A3는 메시지 부재가 감지될 수 있어야한다. 메시지가 없으면 도착하지 못한 경우에만 메시지를 감지할 수 있습니다. 고정된 시간 길이 - 다른 말로 하면 타임 아웃 규칙을 사용합니다. A3를 만족시키기 위해 타임 아웃을 사용하려면 두 가지 가정이 필요합니다.

1. 메시지의 생성 및 전송에 필요한 고정된 최대 시간이 있습니다.
2. 발신자와 수신자는 고정된 최대 오류 내에서 동기화된 시계를 가지고 있습니다.

수신자가 메시지가 도착할 때까지 얼마나 오래 기다려야 하는지를 알아야하기 때문에 첫 번째 가정에 대한 필요성은 상당히 분명합니다. 생성 시간은 생성에 필요한 모든 입력을 받은 후 프로세서가 메시지를 보내는 데 걸리는 시간입니다. 두 번째 가정에 대한 필요성은 덜 분명합니다. 그러나 이 가정이나 동등한 가정이 비잔틴 장군 문제를 풀기 위해 필요하다는 것을 알 수 있습니다. 더 정확히 말하면 장군이 다음과 같은 상황에서만 행동을 취하는 알고리즘을 허용한다고 가정해보십시오.

1. 고정 초기 시간에 (모든 장군들에게 동일).
2. 메시지를 받으면.
3. 무작위로 선택한 시간이 경과 한 때에.
   (즉, 장군은 타이머를 무작위 값으로 설정할 수 있으며 타이머가 꺼지면 작동합니다.)

(이는 우리가 생각할 수 있는 가장 일반적인 클래스의 알고리즘을 만들어 내는데, 이것은 동기화 된 클럭을 만들지 못하게 합니다.) 메시지 전송 지연에 상한이 있더라도 메시지가 임의로 빨리 전송 될 수 있다면 비잔틴 장군 문제를 해결할 수 있는 알고리즘이 없다는 것을 알 수 있습니다. 더욱이, 반역자에게 허용되는 유일한 잘못된 행동을 메시지를 보내지 못하게 하는 것으로 제한해도, 해결책은 없습니다.이 결과의 증거는 이 백서의 범위를 벗어납니다. 전송 지연에 대한 상한 및 하한을 배치하면 프로세서가 메시지를 앞뒤로 보내서 시계를 구현할 수 있습니다.

위의 두 가지 가정은 보내지 않은 메시지를 쉽게 감지합니다. u를 최대 메시지 생성 및 전송 지연으로 하고, 결함이 없는 프로세서는 언제나 최대 r 만큼 서로 다른 시계를 갖는 것으로 가정한다. 그런 다음 결함이 없는 프로세스의 시계에서 시간 T로부터 생성되기 시작해야 하는 메시지는 수신자의 시계에서 시간 T + u + r까지 목적지에 도착할 것입니다. 따라서, 수신자가 그 시간까지 메시지를 수신하지 않았다면, 수신자는 그것이 발신되지 않았다고 가정할 수 있습니다. 나중에 도착한다면, 발신자가 결함이 있는 것입니다. 나중에 도착하면 발신자가 결함이 있는 것입니다. 그래서 알고리즘의 정확성이 전송되는 메시지에 의존하지 않습니다. 입력 프로세서가 값을 보내는 시간을 고정하여 프로세서가 각 메시지를 언제까지 기다려야 하는지 계산할 수 있습니다. 예를 들어 알고리즘 SM(m)에서 프로세서는 k 개의 서명을 가진 메시지에 대해 시간 T0 + k (u + r)까지 기다려야합니다. 여기서 T0는 사령관이 알고리즘 실행을 시작한 시간입니다.

정확하게 동일한 속도로 실행되는 두 개의 시계는 없으므로, 아무리 정확히 처음에 프로세서의 시계가 정확히 동기화되더라도, 정기적으로 다시 동기화되지 않으면 결국 임의로 멀리 떨어지게 됩니다. 따라서 일부 프로세서에 결함이 있어도 프로세서의 시계를 일정량으로 동기화해야 하는 문제가 있습니다. 이는 비잔틴 장군 문제 자체만큼이나 어려운 문제입니다. 우리의 비잔틴 장군 해결책과 밀접하게 관련된 시계 동기화 문제에 대한 해결책이 존재합니다. 이는 앞으로의 논문에서 설명 될 것입니다.

A4. 가정 A4는 프로세서가 결함이 없는 프로세서의 서명을 위조할 수 없는 방식으로 메시지에 서명할 수 있어야 합니다. 서명은 데이터 항목 M에서 프로세스 i가 생성한 중복 정보 Si(M)입니다. i로 서명된 메시지는 (M, Si(M))쌍으로 구성됩니다. A4의 파트 (a) 및 (b)를 충족시키려면 함수 Si가 다음 두 가지 속성을 가져야 합니다. 서명은 데이터 항목 M에서 프로세스 i가 생성한 중복 정보 Si(M)입니다. A4의 파트 (a) 및 (b)를 충족시키려면 함수 Si가 다음 두 가지 속성을 가져야합니다.

(a) 프로세서 i가 오류가 없으면, 결함이 있는 프로세서가 Si (M)을 생성 할 수 없습니다.
(b) M과 X가 주어지면, 어떤 프로세스가 X가 Si(M)와 같은지를 결정할 수 있습니다.

Si(M)은 단지 하나의 데이터 항목이고 오류가있는 프로세서는 모든 데이터 항목을 생성할 수 있으므로 속성 (a)는 보장할 수 없습니다. 그러나 우리는 위반의 확률을 우리가 원하는 만큼 작게 만들 수 있으므로 시스템을 원하는 대로 신뢰할 수 있습니다. 이것이 어떻게 되는지는 우리가 만날 것으로 예상되는 결함 유형에 달려 있습니다. 관심 있는 두 가지 경우가 있습니다.

1. 무작위 오작동. Si를 적절하게 "무작위 화"하는 기능을 사용함으로써 프로세서의 임의의 오작동이 본질적으로 무작위 선택 절차 (즉, 수의 역수)를 통해 확률과 동일한 올바른 서명을 생성 할 확률을 만들 수 있습니다 가능한 서명. 다음은이를 수행하는 한 가지 방법입니다. 메시지가 P보다 작은 양의 정수로 인코딩된다고 가정합니다. 여기서 P는 2의 거듭 제곱입니다. Si(M)가 M * Ki mod P와 같다고하자. 여기에서 Ki는 P보다 작은 무작위로 선택된 홀수입니다. K [1을 Ki * Ki 1 - 1 mod P와 같은 P보다 작은 고유 번호로 놓으면 프로세스가 확인할 수 있습니다. M = X * K ~ 1 mod P를 테스트하여 X = Si(M)이라고 가정합니다. 다른 프로세서가 Ki를 메모리에 가지고 있지 않으면, 단일 (0이 아닌) 메시지에 대해 올바른 서명 M * Ki를 생성 할 확률 M은 l / P이어야합니다 : 무작위 선택으로 그렇게 할 확률. (프로세서가 몇 가지 간단한 절차로 Ki를 얻을 수 있다면, Sj (M)을 계산하려고 할 때 Ki를 K /로 대체함으로써 결함있는 프로세서 j의 서명이 단조 될 확률이 더 클 수 있음에 유의하십시오.)

2. 악의적인 지능. 결함 있는 프로세서가 악의적인 지능(예 : 그것이 시스템을 방해하려는 인간에 의해 작동되는 완벽하게 우수한 프로세서 인 경우)에 의해 유도되는 경우 서명 기능 Si의 구성이 암호화 문제가 됩니다. 이 문제를 어떻게 해결할 수 있는지에 대한 논의는 독자들에게 [1]과 [4]를 참조하십시오.

프로세스가 이미 서명을 본 경우 서명 Si(M)을 생성하는 것이 쉽다는 점에 유의하십시오. 따라서 동일한 메시지를 두 번 서명하지 않아도 되는 것이 중요합니다. 이것은 SM(m)을 반복적으로 사용하여 일련의 값을 분배할 때 고유성을 보장하기 위해 값에 일련 번호를 추가해야 함을 의미합니다.

(다음 노트에서 계속)

원문 The Byzantine Generals Problem