비탈릭 부테린의 99% 장애허용 알고리즘 번역본(3)

Retrofitting onto other consensus algorithms

다른 합의 알고리즘들에 적용

(*참고로 최종화되었다는 것은 새로운 블록이 이전 블록에 붙게되는 과정을 최종화되었다고 표현하였습니다. 어떤분들은 완결시켰다고도 표현하더군요. 블록을 붙이는 일이 끝났으므로 그렇게 표현하는 것이겠죠.)

The above could theoretically be used as a standalone consensus algorithm, and could even be used to run a proof-of-stake blockchain. The validator set of round N+1 of the consensus could itself be decided during round N of the consensus (eg. each round of a consensus could also accept “deposit” and “withdraw” transactions, which if accepted and correctly signed would add or remove validators into the next round).

위의 알고리즘은 이론적으로 합의알고리즘으로 단독으로 사용될 수도 있고, POS 블록체인에 적용되어 사용될 수도 있습니다. 검증자는 N+1 합의의 단계 자체는 합의 N의 단계의 과정에서 정해질 수 있습니다. (예를 들어, 각 단계의 합의과정은 돈을 넣거나 빼는 거래과정을 받아들일 수 있 있습니다. 이 뜻은 각 단계에서 만약 받아들여지거나 사인이 되면 검증자를 다음 단계에서 추가하거나 없어질 수 있다는 것입니다.)

The main additional ingredient that would need to be added is a mechanism for deciding who is allowed to propose blocks (eg. each round could have one designated proposer). It could also be modified to be usable as a proof-of-work blockchain, by allowing consensus-participating nodes to “declare themselves” in real time by publishing a proof of work solution on top of their public key at the same time as signing a message with it.

주요적으로 추가되야하는 사항은 어떤 사람들이 블록들을 추가해야하는 지의 매커니즘입니다. (예를 들어, 매 단계마다 지정된 블록을 추가하는 사람들을 지정하는 방법도 있습니다.) 수정이 되면 POW블록체인에서도 사용될 수 있습니다. 그 방법은 합의에 참여하는 노드들이 실시간으로 스스로 자신을 지정할 수 있도록 만드는 것입니다. 지정을 하는 POW 해결방안은 공공키와 더불어 메세지에 서명을 한 후 공개를 하는 것입니다.

However, the synchrony assumption is very strong, and so we would like to be able to work without it in the case where we don’t need more than 33% or 50% fault tolerance. There is a way to accomplish this. Suppose that we have some other consensus algorithm (eg. PBFT, Casper FFG, chain-based PoS) whose output can be seen by occasionally-online observers (we’ll call this the threshold-dependentconsensus algorithm, as opposed to the algorithm above, which we’ll call the latency-dependentconsensus algorithm).

하지만, 동기화되어있는 네트워크를 가정하는 것은 강력한 보안 방법이지만, 동기화 네트워크 없이도 33%이상이나 50%장애허용 외에는 필요없는 경우에 사용하고 싶다면, 어느 합의 알고리즘이 있다는 것을 가정해봅시다. (예를 들어, PBFT나 Casper FFG, 체인 기반의 PoS) 특히, 알고리즘의 아웃풋이 관찰자들에 의해 가끔 온라인으로 보여지는 알고리즘을 가정해봅시다. (우리는 이것을 기준점-의존 합의 알고리즘이라고 부릅시다. 앞의 알고리즘과는 반대로 지연-의존 합의 알고리즘이라고 부릅시다.)

Suppose that the threshold-dependent consensus algorithm runs continuously, in a mode where it is constantly “finalizing” new blocks onto a chain (ie. each finalized value points to some previous finalized value as a “parent”; if there’s a sequence of pointers A -> … -> B, we’ll call A a descendant of B). We can retrofit the latency-dependent algorithm onto this structure, giving always-online observers access to a kind of “strong finality” on checkpoints, with fault tolerance ~95% (you can push this arbitrarily close to 100% by adding more validators and requiring the process to take longer).

기준점-의존 합의 알고리즘이 지속적으로 새로운 블록을 체인에 추가하는 방식으로 운영되고 있다고 가정해봅시다. (다시말해, 각각의 최종화된 가치들의 포인트들은 그 전 단계에서 최종화 된 가치로써 “부모”라고 부릅니다.) 만약 A 포인터는 B의 이전단계를 말하는 것입니다. A포인터들은 B의 부모라고 할 수 있겠죠. 이러한 구조에 지연-의존 알고리즘을 적용할 수 있습니다. 그 방법은 장애허용 95%까지 도달하는 체크포인트들에서 강력한 최종화에 도달할 수 있도록 상시의 온라인 관찰자들을 접근허용을 하는 것입니다. ( 검증자들을 추가하여 과정을 좀 더 길게 함으로써 언제나 무한히 100%의 최종성에 도달할 수 있도록 할 수 있습니다.)

Every time the time reaches some multiple of 4096 seconds, we run the latency-dependent algorithm, choosing 512 random nodes to participate in the algorithm. A valid proposal is any valid chain of values that were finalized by the threshold-dependent algorithm. If a node sees some finalized value before time T + k * D (D = 8 seconds) with k signatures, it accepts the chain into its set of known chains and rebroadcasts it with its own signature added; observers use a threshold of T + (k — 0.5) * D as before.

매번 시간이 4096초의 배수에 도달할 때마다, 512개의 랜덤의 노드들을 선택하여 알고리즘에 참여하도록 지연-의존 알고리즘을 사용합니다. 유효한 블록추가제안은 기준점-의존 알고리즘에 따라 최종화 된 가치의 유효한 체인이 됩니다. 만약 노드가 k라는 시그니쳐의 시간 ‘T + k * D’ (D = 8 초) 전에 최종화되는 가치를 발견하게 된다면, 체인은 이미 알려진 체인들에 받아들여지고 자신의 시그니쳐가 추가되며 다시 메세지를 전달을 합니다. 전과 같이 관찰자들은. ‘T + (k — 0.5) * D’라는 기준점을 사용합니다.

The “choice” function used at the end is simple:

끝에 있는 “선택”기능은 간단합니다:

● Finalized values that are not descendants of what was already agreed to be a finalized value in the previous round are ignored

이전 단계의 결과물이 아닌 최종화된 가치는 무시됩니다.

● Finalized values that are invalid are ignored

최종화된 가치들은 무효되거나 무시된다.

●To choose between two valid finalized values, pick the one with the lower hash

두 개의 유효한 최종화된 가치에서 고를 때, 해시값이 낮은 것을 선택한다.

If 5% of validators are honest, there is only a roughly 1 in 1 trillion chance that none of the 512 randomly selected nodes will be honest, and so as long as the network latency plus clock disparity is less than D/2 the above algorithm will work, correctly coordinating nodes on some single finalized value, even if multiple conflicting finalized values are presented because the fault tolerance of the threshold-dependent algorithm is broken.

만약 5%의 검증자들이 정직하다면, 오직 1조분의 확률을 가지게 되므로, 512개의 무작위로 선택된 노드들은 정직하지 않을 것입니다. 그리고 네트워크 지연 =시간 불일치가 위의 알고리즘보다 ‘D/2이하인 이상, 다른 노드들과 함께 단일의 최종화된 가치를 통해 다수의 최종화된 가치들이 기준점-알고리즘의 장애허용이 무너져 서로 상충하여 제대로 작동할 것입니다.

If the fault tolerance of the threshold-dependent consensus algorithm is met (usually 50% or 67% honest), then the threshold-dependent consensus algorithm will either not finalize any new checkpoints, or it will finalize new checkpoints that are compatible with each other (eg. a series of checkpoints where each points to the previous as a parent), so even if network latency exceeds D/2 (or even D), and as a result nodes participating in the latency-dependent algorithm disagree on which value they accept, the values they accept are still guaranteed to be part of the same chain and so there is no actual disagreement.

만약 기준점-의존 합의 알고리즘의 장애허용이 (보통 50%나, 67%정도로) 충족된다면, threshold-dependent 합의 알고리즘은 어떤 새로운 체크포인트에서든 최종화를 하던지, 혹은 서로 호환이 되는 새로운 체크포인트들에서 최종화를 하던지 할 것입니다. (예를들어, 체크포인트에서 각각의 포인트들이 그 전의 단계의 부모로써 가르킨다면,) 네트워크 지연이 D/2를 넘는다면, 그리고 그 결과로 노드들이 지연-의존 합의 알고리즘 불일치는 자신들이 인정한 가치들이 여전히 같은 체인에 속하기 때문에 따라서 사실상 불일치는 존재하지 않게 되는 것이빈다.

Once latency recovers back to normal in some future round, the latency-dependent consensus will get back “in sync”. If the assumptions of both the threshold-dependent and latency-dependent consensus algorithms are broken at the same time (or in consecutive rounds), then the algorithm can break down. For example, suppose in one round, the threshold-dependent consensus finalizes Z -> Y -> X and the latency-dependent consensus disagrees between Y and X, and in the next round the threshold-dependent consensus finalizes a descendant W of X which is not a descendant of Y; in the latency-dependent consensus, the nodes who agreed Y will not accept W, but the nodes that agreed X will.

지연이 곧 다가올 다음 단계에서. 원래대로 복구된다면, 지연-독립 합의 알고리즘은 다시 싱크가 맞춰질 것입니다. 만약 여지껏 얘기한 두 가지의 알고리즘 모두가 동시에 무너진다면 알고리즘은 무너질 수 있습니다. 예를 들어 한 단계에서 기준점 의존 합의가 Z -> Y -> X의 순서로 최종화된다면 지연 의존 합의는 Y와 X사이에서 불일치하게 될 것입니다. 그리고 다음 단계에서 기준점 의존 합의알고리즘은 X의 다음 블록인 X(Y의 다음이 아닌) W를 최종화할 것입니다. 지연 의존 합의알고리즘에서는 Y를 인정한 노드들은 W를 받지 않을 것입니다. 하지만 X에 동의한 노드들은 받아들일 것입니다.