"비동기" 네트워크의 비잔틴 결함 허용에 대한 임계값이 결정되는 이유는 무엇입니까?(단 하나의 결함이 있는 노드도 허용할 수 없는 경우)

Question

다음 답변에서 (링크: https://bitcoin.stackexchange.com/a/58908/41513)에 대해 다음과 같은 사실이 밝혀졌습니다. 비동기식 비잔틴 계약:

"우리는 1/3 이상의 노드가 부정직 한 것을 견딜 수 없거나 안전이나 무시도를 잃을 수 없습니다."

이 증명을 위해 다음 조건/요구 사항이 고려되었습니다.

1. 우리 시스템은 비동기식.
2. 일부 참가자는 악의적일 수 있습니다.
3. 우리는 안전을 원합니다.
4. 우리는 활력을 원합니다.

근본적인 질문은 다음과 같습니다.

다음과 같은 잘 알려진 논문을 고려하면: "하나의 잘못된 프로세스로 분산 합의 불가능" (링크: https://apps.dtic.mil/dtic/tr/fulltext/u2/a132503.pdf)

다음을 보여줍니다.

완전히 비동기적인 합의 프로토콜은 예고되지 않은 단일 프로세스 종료도 허용할 수 없습니다.,

여전히 네트워크가 비동기적이라고 가정할 수 있습니까?이 경우 네트워크는 결함이 있는 노드 하나도 허용할 수 없습니다.

Answer 1

대답은 이러한 다양한 결과에서 만들어진 정확한 가정을 추적하는 것과 관련이 있습니다.간단히 말해서 두 결과 모두 비동기성을 가정하지만 "하나의 잘못된 프로세스로 분산된 합의가 불가능"하려면 더 강력한 형태의 활력과 결정성이 필요하며 이는 합의를 불가능하게 만듭니다.

1.하나의 잘못된 프로세스로 분산된 합의가 불가능함

Michael Fischer, Nancy Lynch 및 Michael Paterson의 이 중요한 결과는 시스템이 비동기적일 뿐만 아니라 다음을 충족하는 분산 합의에 관한 것입니다.

• 결정론. 합의 알고리즘은 임의성을 사용하지 않습니다.

• 메시지 지연 시 활성 상태. 메시지가 임의로 지연될 수 있을 뿐만 아니라 그러한 지연이 계속되는 경우에도 우리는 활성성을 보장해야 합니다.

왜 이러한 속성이 너무 강력하여 분산 합의가 불가능하게 되는지 살펴보겠습니다.

예를 들어보자:앨리스, 밥, 찰리는 친구이며 어디서 만나 저녁 식사를 할지 결정하고 싶어합니다.그들 중 한 명이 예기치 않게 AWOL(또는 더 이상 친구가 되는 데 관심이 없다고 판단하여) 메시지에 응답하지 않을 수도 있습니다.이 경우에도 나머지 두 사람이 만날 장소를 결정할 수 있습니다.이제 그들은 어떻게 해야 할까요?

분명한 접근 방식은 다음과 같습니다.

앨리스는 어디로 갈지 결정하고 밥과 찰리에게 알려줍니다.

그러나 이것은 앨리스가 무단이탈할 수도 있기 때문에 작동하지 않습니다.따라서 이 문제를 해결하려면 다음으로 가장 확실한 접근 방식은 다음과 같습니다.

Alice와 Bob은 모두 다른 사람들에게 어디로 가야 하는지 알려줍니다.모두가 앨리스의 말을 들으면 앨리스가 말하는 곳으로 갈 것입니다.그렇지 않으면 Bob이 말하는 곳으로 갈 것입니다.

그러나 이것은 새로운 문제를 안고 있다.당신이 찰리라고 가정해 보세요.앨리스의 소식을 들으면 어디로 가야할지 알 수 있습니다.둘 중 누구도 소식을 듣지 못한다면, 여러분은 듣기를 기다립니다.문제는 Bob의 소식을 들었지만 Alice의 소식은 듣지 못한 경우입니다.임의의 메시지 지연이 있기 때문에 Bob이 말한 대로 진행하도록 커밋할 수 없습니다.앨리스가 어디로 가야할지 말했는데 당신은 아직 그것을 받지 못했을 수도 있습니다!그래서 당신은 완전히 갇혀 있고, 만약 앨리스가 AWOL을 떠난다면, 당신은 영원히 기다리게 될 것입니다.

여기서 문제는 거래를 중단할 방법이 없다는 것입니다."좋아요, 이것은 작동하지 않습니다. 너무 길어서 지연을받지 못했습니다. 다시 시도해 봅시다." 실제 합의 알고리즘 (가장 잘 알려진 Paxos)은 네트워크 지연으로 인해 라운드가 실패 할 가능성이 있으며,이 경우 더 짧은 네트워크 지연을 기대하면서 다시 시도합니다.또한, 무작위 프로토콜을 사용하여 문제를 해결할 수도 있습니다. 대개 일하고, 작은(또는 심지어 0) 확률로 영원히 계속됩니다.

2.비동기식 비잔틴 합의 $1/3$ 노드 중 장애가 발생함

당신이 링크한 bitcoinSE 게시물은 생명성 문제에 대해 설명하며 "앞으로 계속해서 발전할 수 있는 능력"이라고만 말했습니다.실제로 위의 결과는 이것의 가장 강력한 형태가 불가능하다는 것을 보여주므로 요구 사항/가정을 완화해야 합니다.

두 가지 예를 고려해 보겠습니다.Miguel Castro와 Barbara Liskov의 "Practical Byzantine Fault Tolerance"에서는 다음과 같은 방법으로 결함이 있는 노드의 1/3 미만으로 실질적인 활성 상태를 달성합니다. 메시지 지연이 계속해서 무한정 증가하지 않는다고 가정.저자는 다음과 같이 말합니다.

우리는 Livenity를 보장합니다. 즉, 고객은 결국 최대 제공되는 요청에 대한 답변을받습니다. $\frac{n-1}{3}$ 복제본에 결함이 있으며 $지연(t)$ 보다 빨리 자라지 않습니다 $t$ 무기한 ... 이것은 네트워크 결함이 결국 수리 된 경우 실제 시스템에서 사실 일 수있는 다소 약한 동기 가정이지만, 우리는 불가능한 결과를 우회 할 수있게 해주었다 [9].

여기서 [9]는 위에서 논의한 불가능 결과이다.우리의 예에 대한 간단한 용어로, 그들은 약한 형태의 동기화를 요구함으로써 Charlie와 관련된 위의 문제를 피합니다.메시지 지연은 무한정이 아니라 일시적으로만 증가할 수 있다는 것을 알고 있기 때문에 Charlie는 단순히 영원히 기다릴 필요가 없습니다.(물론 실제 알고리즘은 훨씬 더 복잡해집니다. 그러나 이는 부분적으로 활성이 가능한 이유에 대한 개념적 아이디어입니다.)

Ran Canetti와 Tal Rabin의 "최적의 복원력을 갖춘 빠른 ​​비동기식 비잔틴 계약"에서는 무작위성을 사용하여 $n/3$ 비잔틴 노드 오류.그들의 논문에서:

이 설정에서는 다음을 설명합니다. $(\lceil\frac{n}{3} ceil- 1)$- 탄력적인 비잔틴 계약 프로토콜.압도적 인 확률로 모든 비 임산 플레이어는 프로토콜의 실행을 완료합니다.모든 비 임산사가 프로토콜의 실행을 완료 한 이벤트에 따라, 그들은 예상 시간에 따라 그렇게합니다.

여기 $(\lceil\frac{n}{3} ceil- 1)$-복원력은 노드의 1/3 미만이 비잔틴임을 의미합니다.핵심 단어를 참고하세요 압도적인 확률로. 따라서 그들은 가능한 많은 "실행"이 가능한 확률적 알고리즘을 가지고 있으며 압도적으로 대부분이 작동합니다.위의 불가능성 결과는 항상 존재해야 함을 의미합니다. 일부 활성이 발생하지 않는 곳에서 실행됩니다.합의가 없습니다:

결정론적 프로토콜에 대한 Fischer, Lynch 및 Paterson의 [FLP] 중대한 불가능성 결과는 BA에 도달하는 모든 (무작위) 프로토콜이 종료되지 않는 실행을 가져야 함을 의미합니다.