알고리즘 합의 프로토콜 심층 분석

* 면책 조항 :이 기사는 연구원의 개인적인 견해만을 나타내며 Qtum Quantum Chain Foundation의 입장에 대한 개요는 나타내지 않습니다 .

1.1 소개

Algorand는 그것이 "공개 체인 불가능 삼각형"을 뚫었다 고 말했다. 프로젝트 설립자는 MIT CSAIL 연구소의 Silvio Micali 교수 인 Turing Award 수상자이다. Algorand가 제안한 컨센서스 계약은이 프로젝트의 주요 내용으로, Algorand 컨센서스 프로토콜의 작동 원리를 분석하고 그 장점과 단점을 분석합니다.

1.2 Algorand 디자인의 원래 의도

Algorand가 해결하고자하는 핵심 문제는 낮은 대기 시간 (지연 시간)과 분산 네트워크의 높은 신뢰도 사이의 모순입니다 [1].

이 중 지연은 거래 시작부터 거래 확인까지의 시간을 말하며 신뢰는 발행 된 거래가 변경되지 않을 확률을 나타냅니다.

Bitcoin 네트워크에서 거래의 신뢰를 높이려면 사용자는 6 블록 확인 (약 1 시간) 확인 지연을 기다려야합니다 .6 미만의 확인 또는 0 확인과 같은 낮은 대기 시간을 선택한 경우 그것은 필연적으로 낮은 신뢰로 이어지고 "이중화"공격의 가능성을 증가시킬 것이다. 이중 꽃 문제는 대부분의 암호화 된 디지털 통화의 핵심 문제입니다. 비트 코인은 PoW 컨센서스를 사용하여 해결되지만 체인 자체는 여전히 포크 가능성이 있으며 긴 컨센서스 프로세스 및 확인 시간이 필요합니다.

동시에 Algorand는 Bitcoin의 PoW 마이닝 비용이 크고, 거래 확인 시간이 길고, 포크가 포크하기 쉽고, 네트워크가 중앙에 있으며 확장 성이 떨어지는 문제를 해결하려고합니다.

1.3 Algorand 란 무엇입니까?

공식 설명에 따르면, Algorand는 순수한 PoS 컨센서스가 허가없이 공개 된 체인 프로젝트로, 개선 된 비잔틴 컨센서스 프로토콜과 결합하여 빠른 거래 확인을 달성 할 수 있으며 거의 ​​포크없이 거래 수에 영향을 미치지 않고 사용자 수를 무한대로 확장 할 수 있습니다. 속도. 동시에 "확장, 보안, 분산", "공개 체인 불가능 삼각형"[2].

(참고 :“공개 체인 불가능 삼각형”의 정확성과 특정 정의는 더 논란의 여지가 있습니다 [7]. Algorand : 확장 성은 더 큰 사용자 규모에서도 더 높은 처리량을 달성 할 수 있음을 의미합니다 [8], 보안은 악의적 인 공격에 대처할 수있는 능력을 말하며 [9] 분권화는 네트워크가 완전히 개방되고 노드에 대한 임계 값이없는 것을 말합니다 [10].

• 확장 성 : Algorand는 검증 가능한 임의 함수 (VRF)를 통해 블록의 생산자와 검증자를 무작위로 선택합니다 학습자가 선택되면 생산자 나 검증자는 간단히 자신의 신분을 증명하기 위해 짧은 메시지를 방송합니다. 생성 된 각 새 블록에 대해 네트워크에서 교환해야하는 메시지는 사용자 수가 증가해도 변경되지 않으므로 사용자 크기가 증가하더라도 시스템은 더 높은 TPS (초당 처리 된 트랜잭션 수)를 유지할 수 있습니다. 알고리즘의 TPS는 비트 코인의 TPS입니다.

• 보안 : 위의 VRF는 임의로 생산자와 검증자를 선택하는 데 사용되며 선택된 프로세스는 노드에 의해 완전히 완료되므로 Algorand 네트워크의 공격자는 다음 블록 생산자와 검증자를 미리 알 수 없으므로 공격을 완료 할 수 없습니다. 구체적으로, 생산자와 검증 자의 신원은 그들이 선택한 인증 정보를 확인하고 해당 인증 정보를 브로드 캐스트 할 때만 공개됩니다. 현재 공격자가 다양한 공격을 즉시 수행하더라도 새로운 블록의 올바른 수정을 막을 수는 없습니다. 네트워크에서 메시지가 확산되었습니다.

• 탈 중앙화 : Algorand의 각 블록 생산자 및 검증자는 임의로 선택되며 네트워크에 참여하기위한 임계 값이 없으므로 완전히 탈 중앙화됩니다.

Algorand 합의 프로토콜은 아래에 자세히 설명되어 있습니다.

알고리즘 프로토콜 세부 사항

거의 모든 퍼블릭 체인 프로젝트에 대한 블록 생성 및 합의 프로세스는 두 단계로 추상화 할 수 있습니다.

1. 새로운 블록을 생성하려면 블록 생산자를 선택하십시오

2. 다른 노드는 새로운 블록에 대한 합의에 도달

위의 단계가 반복되어 결국 "변조 할 수없는"블록 체인을 형성합니다.

전체 합의 프로세스는 단순하지만 실제 구현에서는 몇 가지 주요 문제를 해결해야합니다.

• 블록 생산자를 선택하고 공정성과 예측 불가능 성을 보장하는 방법은 무엇입니까?

• 새로운 블록에 대한 합의에 도달하는 방법?

• 스플릿 엔드를 피하는 방법?

• 보안을 향상시키는 방법?

• 더 큰 사용자로 확장하는 방법?

Bitcoin은 해시 함수의 임의성을 사용하여 공정성을 보장하고 PoW (Workload Proof)를 사용하여 합의에 도달하며 동시에 전력 공격에 어느 정도 저항합니다. 그러나 Bitcoin은 여전히 ​​컴퓨팅 리소스 소비, 확인 시간이 길고 포크가 쉽고 확장 성이 떨어지는 위의 문제에 직면 해 있습니다. Qtum으로 대표되는 PoS (Pure Proof of Entitlement) 합의 메커니즘을 사용하는 프로젝트도 해시 함수를 사용하며 많은 컴퓨팅 리소스를 소비하지 않지만 여전히 포크, 보안 및 확장 성 문제가 있습니다.

Algorand는 위의 5 가지 문제를 해결하기위한 새로운 합의 메커니즘을 제안했습니다.

2.1 기본 지식

Algorand Consensus Agreement를 공식적으로 도입하기 전에이 기사는 독자가 다음 명사의 의미를 기본적으로 이해하고 있다고 가정합니다.

• 해시 기능

• 공개 / 개인 키

• 디지털 서명

• 거래

• 차단

• 예약

• 컨센서스

• 비잔틴 계약 (BA)

• 정직한 노드

• 공격 노드

• P2P 통신

독자가 위의 개념을 이해하지 못하는 경우 관련 키워드를 검색하여 자세히 알아보고 다음을 읽으십시오.

2.2 Algorand의 기본 프로세스

Algorand 프로토콜은 시간 순서에 따라 다른 라운드로 나눌 수 있으며 각 라운드는 컨센서스에 도달하여 새로운 블록을 생성합니다. 일반적인 일반적인 프로세스는 다음과 같습니다.

1. 각 합의 라운드가 시작될 때 잠재적 인 리더가 무작위로 선택되고 각각 새로운 블록을 생성하며 새로운 블록이 서명되고 방송됩니다.

2. 검증 그룹을 무작위로 선택하여 리더 브로드 캐스트의 새 블록을 확인하고 합의에 도달 한 후 새 블록을 브로드 캐스트하고 다음 라운드에 들어갑니다.

Algorand 합의 프로토콜의 세부 사항은 아래에 자세히 설명되어 있으며이 섹션은 주로 [4]를 참조합니다.

2.3 Algorand의 무작위성 보장 : 검증 가능한 임의 함수

Algorand는 VRF를 사용하여 블록 생산자와 검증자를 선택하여 모든 합의 참가자가 무작위로 공정하게 선택되도록합니다. VRF (Verifiable Random Function)는 Micali 교수가 제안한 의사 난수 (pseudo-random) 기능으로, 일반 난수 기능과 같이 다른 입력 (엄밀히 말하면 "의사 난수")에 대해 무작위로 출력됩니다. ). 호출자가 임의 출력이 실제로 호출자에 의해 생성되었다는 증거를 제공 할 수 있다는 점에서 고유합니다.

VRF는 다양한 방법으로 구현 될 수 있으며 Micali et al.은 원래 논문에서보다 복잡한 구현을 제공합니다 [3]. Algorand는 해시 함수 및 디지털 서명 기능을 사용하여보다 간단한 VRF 구현을 제공합니다. 특정 구현은 호출자 i가 디지털 서명 및 해시 함수를 통해 입력 m을 고정 길이 출력 H [SIGi (m)], 즉 m-> H [SIGi (m)]에 매핑하는 것입니다.

모든 입력 m의 경우, 다른 호출자 i에 의해 생성 된 디지털 서명 SIGi (m)은 고유하며, 다른 입력의 경우 해시 함수 H의 출력은 임의이므로 위의 매핑은 VRF의 "랜덤 성"요구 사항을 준수합니다. 동시에 i의 디지털 서명 SIGi (m)은 공개 키로 인증 할 수 있으므로 VRF "확인 가능"기능도 준수하며 SIGi (m)은 VRF에서 언급 된 "증거"입니다.

이 기능은 아래에 설명 된대로 모든 노드에서 합의 참가자를 임의로 선택하는 데 특히 적합합니다.

2.3.1 각 블록 생산자 (리더)를 무작위로 선택

각 합의 라운드가 시작될 때 각 노드는 다음 VRF를 통해 잠재적 인 리더임을 독립적으로 확인할 수 있습니다.

.H [SIG (r, 1, Q (r-1))] <= 1 / SIZE (PK (rk))

여기서 H는 해시 연산입니다 .SIG는 서명 연산입니다 .r은 현재 라운드입니다 .Q (r-1)은 r-1 라운드의 시드입니다 (다음 2.6에 설명 됨); SIZE (PK (rk) rk 라운드에서 필요한 모든 공개 키의 수입니까 (rk? k가 역 추적 요소 인 이유는 섹션 2.6에서도 설명 됨) 공식이 시작됩니다. 해시 결과가 소수점 이하 자릿수로 변환되므로 결과는 다음과 같습니다. [0,1)의 값입니다.

노드는 위의 서명의 해시 값이 자체 개인 키로 요구 사항을 충족하는지 여부를 계산하여 후보 리더에 속하는지 여부를 알고 프로세스의 다른 노드와 정보를 교환 할 필요가 없습니다. 해시 함수 출력의 임의성으로 인해 요구 사항을 충족하는 후보 노드가 임의로 선택되었다고 간주 할 수 있습니다. 후보 노드는 새로운 블록을 생성하고 전체 네트워크에 서명을 제공하여 그 신원을 확인할 수있다. 후보 리더가 여러 명인 경우 해시 값이 가장 작은 리더가 후속 컨센서스에서 현재 라운드의 최종 리더가됩니다. 리더가 생성 한 블록 Br에는이 라운드의 모든 거래와 위에서 언급 한 증명 정보가 포함되어 있으며 이는 검증 팀 구성원이 확인합니다.

2.3.2 각 라운드의 각 단계에 대한 검증 그룹을 무작위로 선택

검증 그룹 구성원의 선택은 위의 프로세스와 유사하며 각 라운드 및 모든 단계에서 모든 노드가 검증 그룹 구성원에 속하는지 여부를 독립적으로 확인할 수 있습니다.

.H [SIG (r, s, Q (r-1))] <= n / SIZE (PK (rk))

s가 라운드의 다른 단계 인 경우, Algorand는 각 라운드의 각 단계마다 보안을 강화하기 위해 서로 다른 검증 그룹을 가지고 있습니다 .n은 예상되는 검증 그룹 멤버 수이며 수동으로 설정할 수 있습니다. 다른 매개 변수는 의미하지 않습니다 다시 반복하십시오.

후보 리더와 마찬가지로, 검증 그룹 구성원의 각 단계는 무작위로 선택되며, 신원을 확인한 후, 검증 노드는 합의 검증 프로세스에 참여하기 시작하고 서명을 공개하여 신원을 증명할 수 있습니다.

2.3.3 지분 증명 (PoS) 메커니즘 소개

전술 한 랜덤 선택 프로세스는 토큰 보유자의 가중치를 고려하지 않으며, 악의적 인 노드는 큰 확률로 다수의 유효한 개인 키를 생성함으로써 블록의 생산자 및 검증자가 될 수있다. Algorand는 발표 된 구현 제안에서 HMM (Hoest Honor Majority of Money)이라는 조건부 가설을 도입했으며, 기본 아이디어는 위의 무작위 선택 프로세스에서 가중치로 토큰 보유 (Stake)를 도입하는 PoS 컨센서스 메커니즘에서 파생되었습니다. 보유 수가 많은 노드가 선택 될 확률이 높고 토큰 보유자가 네트워크의 보안을 보호하는 경향이 있습니다. 구체적으로는 다음과 같이 표현할 수 있습니다.

.H [SIG (r, 1, Q (r-1))] <= (a (i, r) / M) * (1 / SIZE (PK (rk)))

여기서 a (i, r) / M은 총 토큰 수 M으로 노드가 보유한 코인 수의 가중치입니다. 나머지 프로세스는 이전 설명과 일치했습니다.

2.4 Algorand가 새로운 블록에 동의하는 방법 : 개선 된 비잔틴 계약 BA *

Algorand의 검증자가 새로운 블록에 대한 합의에 도달 한 프로세스는 실제로 Algorand가 BA *라고하는 개선 된 비잔틴 계약이었습니다.

BA *는 개선 된 이진 비잔틴 계약 (BBA)과 등급별 합의 (프로토콜 GC)의 조합입니다 [5].

2.4.1 이진 비잔틴 프로토콜 BBA 개선 *

Algorand가 도입 한 BBA *는 개선 된 이진 비잔틴 프로토콜입니다 (이른바 이진, 즉 0 또는 1 합의 만 달성 할 수 있음). 정직한 노드가 2/3를 초과하면 BBA *가 빠르게 합의에 도달 할 수 있습니다. 특정 프로세스는 3 단계주기이며주기의 각 단계는 합의에 도달 할 확률이 1/3입니다.

노드간에 P2P 통신이 필요합니다. 선택한 검증 노드에 악성 노드가 없다고 가정하고 검증 그룹의 총 노드 수는 n> = 3t + 1이며, 즉 악성 노드가 1/3을 초과하지 않습니다. 프로토콜 프로세스는 다음과 같습니다.

위 계약에서 각 기호의 구체적인 의미는 [4]를 참조하십시오. 모든 검증 노드 i는 초기 값 bi (bi = 0 또는 1)를 가지며, 각 검증 노드는 초기 값을 프로토콜 시작시 다른 검증 노드로 보냅니다.

프로토콜의 첫 번째 단계 (1 단계)는 0 프로세스로 돌아 가기입니다.

• 검증 노드 i에 의해 수신 된 0의 수가 총 검증 노드 수의 2/3를 초과하면, 출력 합의 결과는 0이고, 합의는 종료되며 모든 후속 단계는 실행되지 않습니다.

• 검증 노드 i가 총 검증 노드 수의 2/3를 초과하는 총 1을 수신하면 검증 노드는 자체 bi를 1로 설정합니다.

• 수신 된 0 또는 1이 2/3를 초과하지 않으면 검증 노드는 자체 bi를 0으로 설정합니다.

• 첫 번째 단계는 각 bi를 다른 노드로 다시 보내는 노드를 종료합니다.

두 번째 단계 (2 단계)는 1 프로세스로 돌아가는 것입니다.

• 검증 노드 i에 의해 수신 된 총 1의 수가 검증 노드의 총 수의 2/3를 초과하면, 출력 합의 결과는 1이됩니다. 합의가 종료되고 모든 후속 단계가 실행되지 않습니다.

• 검증 노드 i가 총 검증 된 노드 수의 2/3를 초과하는 총 0을 수신하면, 검증 노드는 자체 bi를 0으로 설정합니다.

• 수신 된 0 또는 1이 2/3를 초과하지 않으면 검증 노드는 자체 bi를 1로 설정합니다.

• 제 2 단계는 각각의 bi를 다른 노드로 다시 보내는 노드를 종료한다.

세 번째 단계 (3 단계)는 초기 값을 재설정하는 프로세스입니다.

• 검증 노드 i가 총 검증 노드 수의 2/3를 초과하는 총 0을 수신하는 경우 bi = 0으로 설정하십시오.

• 검증 노드 i가 총 검증 노드 수의 2/3를 초과하는 총 1을 수신하는 경우 bi = 1로 설정하십시오.

• 수신 된 0 또는 1이 2/3를 초과하지 않으면, 각 검증 노드는 현재 라운드의이 단계와 관련된 메시지에 서명하고 서명을 해시합니다. Bi는 이러한 해시 중 가장 작은 해시의 최하위 비트로 설정됩니다 (여전히 0 또는 1).

• 그런 다음 합의에 도달 할 때까지 첫 번째 단계로 돌아갑니다.

Algorand에서 BBA *의 결과는 블록 수락 여부에 대한 합의이며, 합의 결과는 수락 (0) 또는 거부 (1)입니다.

2.4.2 계층 적 합의 프로토콜 GC

위의 BBA *는 이진 경우에만 적용 할 수 있으며 임의의 값에 대한 합의에 도달해야하는 경우 임의의 값 문제를 이진 문제로 변환하기 위해 계층 적 합의 프로토콜을 도입해야합니다.

Algorand에서 사용하는 GC는 두 단계로 나뉩니다 (위의 그림은 Algorand 백서 [4]에 있습니다. 나머지 텍스트에 해당하기 위해 두 단계는 2 단계와 3 단계로 명명됩니다). 프로토콜의 시작 부분에서 각 검증 노드 i는 초기 값 vi (Algorand에서 후보 새 블록의 해시) :

제 1 단계 (단계 2)에서, 모든 검증 노드는 그들 각각의 vi를 다른 모든 검증 노드에 전송한다;

두 번째 단계 (3 단계)는 특정 값의 x에 대해, 노드가 다른 검증 노드에 의해 x 값이 전송 된 총 횟수를받는 경우에만 (여러 번 동일한 노드에 의해 전송 된 x 값을 한 번만 수신) 총계를 초과하는 경우 노드 수의 2/3를 확인할 때이 노드는 x 값을 다른 노드로 보냅니다.

GC 후에 각 노드는 출력 규칙에 따라 값 쌍 (vi, gi)을 출력합니다.

• 수신 된 x의 총 수가 검증 된 총 노드 수의 2/3를 초과하는 경우 vi = x, gi = 2로 설정하십시오.

• 수신 된 x의 총 수가 검증 된 총 노드 수의 1/3을 초과하면 vi = x, gi = 1로 설정하십시오.

• 그렇지 않으면 vi = 비어 있음, gi = 0으로 설정하십시오.

간단히 말해서, 계층 적 합의의 역할은 가능한 많은 후보 새로운 블록에서 가장 잘 알려진 후보 블록을 선택하고 마지막으로 위의 BBA를 통해 합의에 도달하는 것입니다.

2.4.3 BA * = GC + BBA *

개선 된 비잔틴 프로토콜 BA *는 위의 GC와 BBA *를 결합하여 먼저 임의의 값 문제 (여러 블록에서 한 후보 선택)를 이진 문제 (새 블록 수신 또는 거부?)로 변환 한 다음 BBA *를 사용합니다. 빠른 이진 비잔틴 합의 달성, 어떤 가치에서든 합의에 신속하게 도달 할 수 있으며 합의 과정은 다음과 같습니다 [4] :

BA *의 첫 번째 단계와 두 번째 단계의 모든 검증 노드 i는 2.4.2에서 계층 적 합의 GC를 수행하며, 각각 새로운 블록에 대한 값 쌍 (vi, gi)을 얻습니다. 여기서 vi는 검증 노드 i에 의해 고려되는 후보 영역입니다. 해시 차단 (비어있을 수 있음), gi = 0 또는 1 또는 2

세 번째 단계에서 모든 검증 노드는 각각의 (vi, gi)에 따라 BBA *의 초기 값을 설정합니다 gi = 2 인 경우 초기 값은 0으로 설정됩니다. gi = 0 또는 1 인 경우 초기 값은 1로 설정됩니다. . 그런 다음 2.4.1의 BBA * 합의 프로세스로 진행하십시오.

• 합의 결과가 0이면 최종 출력은 vi입니다 (빈 블록이 아님).

• 합의 결과가 1이면 최종 출력이 비어 있습니다 (즉, 새 블록이 비어 있음)

두 경우 모두 BA *는 검증 노드에서 컨센서스에 도달하여 새 블록과 블록을 포함하는 트랜잭션 (비어있을 수 있음)을 확인할 수 있습니다.

2.5 알고리즘 블록 체인 포크 가능성

Algorand는 실제로 고전적인 비잔틴 컨센서스 BA *의 업그레이드 버전을 사용하는데, 비트 코인으로 대표되는 나카 모토 컨센서스와 가장 큰 차이점은 분기 가능성입니다. 후자는 완전히 분산되어 있기 때문에 노드는 완전히 통신 할 수 없으므로 일부 노드 사이에서만 합의에 도달 할 수 있으며 분기가 발생하기 쉽습니다.

Algorand는 최대 허용 오차 확률 F를 설정하여 포크의 확률을 조정할 수 있습니다. Algorand가 제공하는 두 가지 구현에서 분기 확률은 각각 10 ^ -12와 10 ^ -18이지만 이론적으로는 분기가 가능합니다. 독자에게 직관적 인 개념을 제공하기 위해 Algorand가 초당 블록을 생성한다고 가정하면 10 ^ -18의 확률은 빅뱅 시간부터 현재까지 가능한 분기 만 발생할 수 있으며 확률이 매우 낮다는 것을 의미합니다.

포크가 발생하더라도 Algorand는 여전히 포크에서 복구 할 수 있습니다.

• Algorand는 Nakamoto 컨센서스에서 가장 긴 체인 규칙을 따릅니다.

• 가장 긴 체인이 여러 개인 경우 비어 있지 않은 블록이 포함 된 가장 긴 체인을 선택하십시오.

• 여전히 동일한 경우 블록 해시 값에 따라 정렬 할 수 있습니다.

2.6 Algorand는 어떻게 안전을 보장합니까?

위에서 언급 한 합의 알고리즘은 이상적인 조건에서 분산 환경에서 더 빠른 비잔틴 합의를 실현할 수 있으며 디지털 서명 및 VRF 자체의 보안은 시스템 보안을위한 기본 보안을 제공합니다. 또한 Algorand는 보안을 강화하기 위해 다음과 같은 메커니즘을 도입했습니다.

시드 Q (r)

Algorand의 무작위성은 주로 VRF에 의해 보장되며 리더와 검증 그룹은 각 라운드에서 무작위로 선택됩니다. 보다 간단한 아이디어는 이전 블록 B (r-1)을 랜덤 함수의 입력으로 사용하는 것입니다. 그러나이 방법은 악의적 인 노드에 특정 이점을 제공합니다. 블록은 블록에 포함 된 트랜잭션과 밀접한 관련이 있기 때문에 악의적 인 노드는 블록에 포함 된 트랜잭션 세트를 조정하여 여러 출력을 얻을 수 있으며 가장 유리한 것을 선택할 수 있습니다. 트랜잭션 세트는 새로운 블록을 생성하여 다음 라운드에서 리더 또는 검증 그룹이 될 가능성을 높입니다.

이 문제를 해결하기 위해 Algorand는 트랜잭션 세트 자체와 독립적 인 무작위로 지속적으로 업데이트되는 시드 매개 변수 Q (r)을 도입하여 악의적 인 노드가 트랜잭션 세트를 조정하여 이익을 얻을 수 없습니다.

블록이 비어 있지 않으면 Q (r) = H (SIG (Q (r-1), r) (SIG는 현재 리더의 서명 임)

블록이 비어 있으면 Q (r) = H (Q (r-1), r)

Q (r)는 매 라운드마다 바뀌며 거래 자체와 무관하다는 것을 알 수 있습니다. Q (r-1)이 랜덤 일 때 Q (r)도 랜덤임을 알 수있다. 따라서 악의적 인 노드는 트랜잭션 세트를 변경하여 다음 시드 생성에 영향을 줄 수 없습니다. 그 중에서도 Q (1)의 정의는 관련 문헌에서 찾을 수 없습니다.

역 추적 계수 k

seed 매개 변수는 악의적 인 노드가 리더를 예측할 가능성을 줄여 주지만 여러 개의 잠재적 인 리더가있는 악의적 인 노드는 여전히 일반 노드보다 다음 블록의 리더가 될 가능성이 높지만이 확률은 블록과 함께 증가합니다. 점점 작아지고 있습니다. 따라서 Algorand는 역 추적 계수 k를 도입합니다. r 번째 라운드의 후보 그룹은 rk 라운드에 이미 존재하는 후보 그룹에서만 선택되며 악의적 인 노드가 rk 라운드에서 r 번째 라운드의 후보 그룹에 영향을 줄 가능성은 매우 낮습니다.

일회성 공개 키

이전 섹션에서 언급했듯이 프로토콜 수준의 Algorand 포크는 이론적으로 만 발생할 수 있습니다. 실제로 악의적 인 노드가 다른 노드를 보유 할 수있는 경우에도 검증 그룹이 노출되는 즉시 노드가 새 블록을 다시 서명하도록하여 포크가 짧아 질 수 있습니다. Algorand는 이러한 가능성을 없애기 위해 일회성 공개 키 메커니즘을 도입했습니다.

구체적인 원칙은 모든 노드가 충분한 일회성 공개 키를 생성하고 Algorand 네트워크에 가입 할 때 (즉, 첫 번째 트랜잭션이 발생할 때) 공개 키를 생성한다는 것입니다. 이 공개 키는 이후의 모든 라운드에서 서명을 확인하는 데 사용되며 각 공개 키는 한 번만 사용되며 사용되면 폐기됩니다. 일회성 공개 키 생성 프로세스에는 일정 시간이 걸리지 만 Algorand의 일반적인 구현에서 각 새 노드는 다음 10 ^ 6 라운드에 대한 모든 공개 키 (약 180MB의 데이터)를 생성하는 데 약 1 시간이 걸립니다. 이렇게하면 노드 조인의 임계 값이 증가하지만 위에서 언급 한 포크 공격을 근본적으로 제거 할 수 있습니다. 서명이 완료되면 공개 키가 손상되고 악의적 인 노드에 의해 하이재킹 된 경우에도 포크를 생성하기 위해 다시 서명 할 수 없습니다.

2.7 Algorand의 확장 성

Bitcoin, Ethereum 및 Qtum과 같은 현재의 분산 블록 체인의 경우 확장 성의 주요 병목 현상은 체인의 모든 계산을 전체 네트워크에서 확인해야하며 전체 네트워크의 합의에 도달하는 데 특정 시간이 걸린다는 것입니다. Algorand는 PoS + VRF 메커니즘을 사용하여 블록 생산자와 검증자를 무작위로 선택합니다. 네트워크의 노드 수에 관계없이 각 라운드는 몇 개의 노드에서만 확인하면되므로 합의 속도가 크게 향상되고 확장 성이 향상됩니다. 동시에 Algorand는 개선 된 비잔틴 컨센서스 BA *를 채택하여 컨센서스 노드 간의 통신량을 줄임으로써 컨센서스 속도를 더욱 향상 시켰습니다.

이전에 Algorand는 성능 테스트 데이터를 공개했으며 그 결과 1000 EC2 서버 (AWS 가상 클라우드 서버)와 500,000 명의 사용자 시나리오에서 Algorand 네트워크는 1 분까지 시간을 확인했으며 처리량은 비트 코인 네트워크의 125 배에 달하는 것으로 나타났습니다. (비트 코인은 약 7 TPS) 노드 수가 증가함에 따라 처리량이 크게 감소하지 않습니다 [1].

 Algorand의 장단점

위의 분석을 통해 Algorand는 기본적으로 섹션 2의 시작 부분에서 제기 된 일련의 문제를 해결했습니다.

• PoS 및 검증 가능한 임의 함수 (VRF)를 통한 생산자 및 검증 자 선택 차단

• 개선 된 비잔틴 컨센서스 BA *를 통한 새로 생성 된 블록에 대한 컨센서스

• 특정 매개 변수 설계를 통해 분기 확률을 매우 낮은 값으로 수학적으로 줄입니다.

• 보안 강화를 위해 시드 매개 변수, 역 추적 계수 및 일회성 공개 키를 도입합니다

• 각 라운드에서 부분 검증 만 수행되며, 노드 간의 통신량을 줄임으로써 시스템의 처리량이 더욱 향상되어 확장 성이 향상됩니다.

Algorand는 확장 성, 보안 및 분산화 측면에서 균형이 잘 잡힌다고해서 이것이 "불가능한 삼각형"이라는 것을 깨뜨린 것은 아닙니다.

확장 성 : 본질적으로 모든 트랜잭션은 더 적은 검증 노드로 검증됩니다. 네트워크에 더 많은 노드가 있으면 성능 만 크게 저하되지 않으며 실제로 확장 할 수 없습니다. 또한 각 검증 노드 간의 통신은 네트워크 상태에 따라 달라지며 네트워크의 불안정성은 합의 시간을 길게하여 TPS에 영향을 미칩니다. 관계자는 Algorand가 Permissinoed 환경에서 더 나은 성능을 보일 것이라고 말했다 [4]. 아마도 Permissionless 환경의 노드 환경에 너무 많은 불확실성이 있기 때문에 확장성에 어느 정도 영향을 줄 수 있기 때문일 것입니다.

보안 : Algorand는 본질적으로 비잔틴 합의를 사용하고 악의적 인 노드는 1/3을 초과 할 수 없으며 악의적 인 노드의 수가 1⁄2 미만인 경우 Bitcoin은 보안을 보장 할 수 있습니다.

탈 중앙화 : Algorand는 PoS 컨센서스 및 VRF를 사용하여 블록 생산자와 검증자를 결정합니다 .PoS 프로세스에서 토큰이 더 많은 노드가 선택 될 가능성이 높으며 특정 중앙 집중화로 스태킹 보상이 대가족에 집중됩니다. 추세는 VRF 선택 메커니즘의 도입으로 일부 노드에서만 체인 계산을 검증 할 수 있으며, 이는 네트워크 전체 검증의 분산 시스템을 박탈합니다.

또한 Algorand의 주요 네트워크가 막 출시되었습니다 [6]. 이전의 모든 결과는 이상적인 환경에있는 데이터이며 일부 코드는 오픈 소스가 아니며 가상 시스템 관련 설계는 아직 언급되지 않았지만 구현 복잡성, 안정성 및 실제 성능 아직 테스트 할 시간입니다.

요약

Algorand는 혁신적인 합의 계약을 통해 설계되었으며 높은 확장 성, 우수한 보안 및 어느 정도의 탈 중앙화를 달성했으며 모든 결론에는 엄격한 수학적 증거가 있으며 이는보다 혁신적이고 엄격한 합의입니다. 이 메커니즘은 현재 특정 진입 장벽이있는 분산 된 고 처리량 암호화 디지털 통화 프로젝트에 더 적합합니다.

참고 문헌

[1] https://algorandcom.cdn.prismic.io/algorandcom%2Fa26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf

[2] https://www.algorand.com/what-we-do/technology/core-blockchain-innovation

[3] S. Micali, M. Rabin 및 S. Vadhan. 검증 가능한 임의 함수 40 번째 컴퓨터 과학 기초 (FOCS), 뉴욕, 1999 년 10 월. 

[4] https://algorandcom.cdn.prismic.io/algorandcom%2Fece77f38-75b3-44de-bc7f-805f0e53a8d9_theoretical.pdf

[5] https://algorandcom.cdn.prismic.io/algorandcom%2F218ddd09-8d6f-42f7-9db9-5cfbc0aedbe5_algorand_agreement.pdf

[6] https://www.algorand.com/resources/blog/the-borderless-economy-is-here

[7] https://www.odaily.com/post/5134308

[8] https://www.algorand.com/what-we-do/technology/scalability/

[9] https://www.algorand.com/what-we-do/technology/security/

[10] https://www.algorand.com/what-we-do/technology/permissionless-blockchain/