작업 증명을 사용하지 않고 공정하고 효율적인 방법

Taraxa

特邀专栏作者

2020-07-17 13:06 (UTC+8)

이 기사는 약 3409자로, 전체를 읽는 데 약 5분이 소요됩니다

PoW에 무슨 문제가 있나요?

AI 요약

PoW에 무슨 문제가 있나요?

머리말

보조 제목

POW의 아름다움

Pow는 간단하고 우아한 합의 알고리즘입니다. 각 노드는 간단한 암호화 퍼즐을 풀고 빠른 추측을 통해 솔루션을 얻습니다. 먼저 올바르게 추측하는 사람이 다음 블록을 생성하도록 선택됩니다.

그렇게 간단합니다.

이 간단한 알고리즘은 공정하고 분산된 블록 제안을 위한 진정한 임의성, 특정 지연 - 브로드캐스트에 충분한 시간이 있는지 확인하여 포크 가능성 최소화, 경제적 모기지 - 채굴자들이 정직하게 일하는 것에 대한 기득권.

보조 제목

이미지 설명

나란히 작동하는 초기 조립 라인

간단하고 우아한 PoW 메커니즘의 핵심 문제는 어려운 문제를 높은 수준의 병렬 처리로 처리할 수 있다는 것입니다. 이러한 퍼즐은 일반적으로 노드가 임의의 문자열을 계속 생성하고 해시하고 결과 해시가 특정 기준과 일치하는지 확인하는 해시 함수입니다. 당신이 단지 플레이어(예: 기계, 스레드)라면 평균 N초 후에 정답을 추측할 수 있다고 가정합니다. 하지만 플레이어가 100명이라면 정답을 추측하는 데 걸리는 평균 시간은 N/100초입니다. 작업을 쉽게 분배할 수 있기 때문입니다. 예를 들어 총 M개의 가능한 답변이 있는 경우 플레이어 1이 답변 1을 테스트하여 M/100을 답변하도록 한 다음 플레이어 2가 답변 M/100을 테스트하여 M/200을 답변하도록 할 수 있습니다.

PoW 블록체인 시스템에서 작업하는 채굴자들은 보통 다수의 특수 목적 컴퓨터, 즉 ASIC(Application-Specific Integrated Circuit)를 구입하고 이러한 ASIC의 분업을 조율하는 프로그램을 호출하여 답을 추측하므로 평균 속도는 정답이 더 빠를 것이라고 추측합니다. 시간이 지남에 따라 서로 다른 채굴자들이 팀을 구성하여 ASIC 그룹의 작업을 공유하기로 결정합니다.

비트코인과 같은 네트워크의 경우 채굴자들이 답을 너무 빨리 추측하면 답 추측의 난이도를 높일 수 있는 일련의 내부 알고리즘이 있으며 최종적으로 블록 생성 시간을 평균 10분 정도의 속도로 유지합니다. 따라서 광부들이 추측하는 속도가 빠를수록 퍼즐이 더 어려워지므로 광부들이 속도를 높이거나 ASIC을 통해 더 많은 ASIC을 구축하도록 장려합니다.

채굴기는 점점 더 빨라지고 많아지고 있으며, 네트워크 유지를 위한 에너지 소비가 엄청나게 높아질 때까지 점점 더 많은 에너지를 소비합니다.

보조 제목

설계 목표: 임의 대기 시간

따라서 PoW만큼 리소스를 낭비하지 않으면서 동시에 무작위 지연을 달성할 수 있는 시스템을 설계하려면 다음과 같은 설계 목표를 달성해야 합니다.

공정성과 탈중앙화를 보장하는 진정한 무작위성
대기 시간은 에너지 소비를 최소화하기 위해 병렬 처리를 통해 줄일 수 없습니다.

최적화 방법을 살펴보겠습니다.

이미지 설명

백색 소음은 자연적으로 발생하는 임의성의 원인입니다.

진정한 무작위성은 철학적인 질문에 가깝습니다. "무작위"라고 말할 때 실제로 의미하는 것은 "예측할 수 없음"입니다. 우리 메커니즘의 결과가 네트워크 참여자에 의해 예측할 수 없는 경우, 우리는 그 결과를 무작위적이고 공정한 것으로 간주합니다.

많은 암호화 기능은 해시 기능 및 서명 메커니즘과 같은 임의 출력을 생성하는 것으로 보입니다. 그러나 예측할 수 없는 출력을 생성하도록 특별히 설계되지 않았으며 관찰자는 충분히 많은 수의 샘플이 주어진 패턴을 추론할 수 있습니다.

1999년에 Micali, Rabin 및 Vadhan이 매우 예측할 수 없는 출력을 생성하도록 특별히 설계된 검증 가능한 무작위 함수(VRF)를 설명하는 논문을 발표했습니다. 나중에 Micali 교수가 Algorand 프로젝트를 설립했고, 그 후 프로젝트의 핵심 멤버인 Sergey Gorbunov가 보다 상세하고 이해하기 쉬운 기사를 작성했습니다. VRF의 보다 기술적인 처리에 관심이 있는 경우 위의 기사 및 논문을 참조할 수 있습니다.

Taraxa의 블록 DAG 아키텍처에서 VRF는 임의 지연에 대해 임의성을 제공합니다. VRF의 출력은 다음과 같습니다.

블록 DAG 레벨(L): 제안자가 블록을 패키징할 때 여기서 "레벨"은 앵커 체인의 길이 + 1입니다. 따라서 제안자라면 현재 앵커 체인 L을 계산하고 고스트 포인터(포인터)를 구축할 경계에서 최종 블록을 찾으면 제안하는 블록 수준은 L+1입니다. 여기서 정의는 흔히 말하는 "깊이"와는 다른 개념이라는 점에 유의해야 합니다.
최신 기간 블록의 블록 해시(P): 이것은 블록 DAG에서 가장 최근에 완료된 블록으로, 병렬 PBFT 프로세스를 통해 진정한 최종 확인을 달성할 수 있습니다(자세한 내용은 다음 기사 참조). 제안자가 경계에서 가장 최근에 확인된 기간 블록(P)을 받지 못했다는 점을 고려하면 프로토콜은 특정 허용 오차를 갖게 됩니다. 즉, 최신 기간 블록의 이전 블록 해시도 허용됩니다.
블록 제안자의 비밀 VRF 키(SK): VRF 기능을 구축하는 데 필요합니다. 이는 VRF를 구축하기 위해 각 노드에 대해 특별히 생성되는 트랜잭션 서명 메커니즘과 다릅니다.

VRF 함수의 출력은 두 부분으로 나뉩니다.

v는 지연 길이를 결정하는 데 사용되는 의사 난수 값입니다.
p는 다른 노드가 VRF가 정직하고 올바르게 실행되었는지 확인하는 데 사용할 수 있는 증거입니다. 서명으로 간주할 수 있으며, 제안자의 VRF 공개 키로 다른 어떤 노드도 계산의 정확성을 쉽게 결정할 수 있습니다.
궁극적으로 간단한 방정식을 작성할 수 있습니다.
VRF(L, P, SK) → (v, p)

■ 지연난이도 쉐이핑 기능

VRF(지연 난이도 또는 지연 길이)의 출력을 지연으로 변환하기 전에 특정 분포를 형성해야 합니다. 분포의 특징은 대략 다음과 같습니다.

적절한 네트워크 브로드캐스트를 위한 시간 없이 블록을 즉시 생성할 수 없기 때문에 최소한의 지연이 필요합니다.
전체 네트워크가 정체되는 것을 원하지 않고 블록이 오랫동안 생성되는 것을 원하지 않기 때문에 최대 지연이 필요합니다.
일부 제안자는 빠르고 나머지는 느립니다. 이는 자격을 갖춘 제안자의 수와 전체 네트워크의 직경(즉, 블록이 제안된 노드의 대부분에 도달하는 데 필요한 시간)과 관련이 있습니다.
이미지 설명

성형 기능

유형 함수를 S라고 하면 다음 공식을 얻을 수 있습니다.

S(v) = d

여기서 d는 다음 단계의 난이도 계수입니다.

■ 검증 가능한 지연 지연 기능

토큰은 자체적으로 가치 이전을 생성할 수 있는 버스 카드와 같으며 제휴 체인에는 고유한 가치 이전이 없습니다. 국가는 피라미드 사기를 단속하고 있지만 실제로는 여전히 귀중한 토큰이 많이 있습니다.산업이 발전하고 대중이 어느 정도 인식하면 고품질 퍼블릭 체인은 일률적인 상황을 피할 수 있습니다. . 이때까지 얼라이언스 체인과 퍼블릭 체인 간에 더 많은 협력이 있을 수 있습니다.

혼자 열심히 일하는데 아무도 나란히 싸우지 않는다 =(

이 기사의 시작 부분에서 논의한 바와 같이 PoW는 좋지만 병렬 처리는 "피해"의 주범입니다. 따라서 병렬 처리로 가속할 수 없는 대기 시간을 시뮬레이션하도록 특별히 설계된 VDF(Verifiable Delay Function)가 등장했습니다.

함수는 다음 두 가지 간단한 기준을 충족하는 경우 VDF로 엄격하게 분류될 수 있습니다.

순차적이어야 하며,이 경우 누구도 PoW와 달리 다중 병렬 프로세스를 통해 VDF 함수의 계산 속도를 높일 수 없습니다.
쉽게 확인할 수 있어야 하며,관찰자는 VDF 계산이 정확하고 적절한 지연이 발생하는지 확인하기 위해 간단히 검증(즉, 검증에 걸리는 시간이 함수를 계산하는 시간보다 훨씬 짧음)할 수 있으며 이는 PoW와 유사합니다.

Boneh et al., Pietrzak 및 Wesolowski et al.은 모두 이러한 기준을 만족하는 VDF를 제안했습니다.특히, Pietrzak과 Wesolowski는 병렬 처리에 효과적인 알 수 없는 순서의 그룹에서 반복 제곱의 원리를 기반으로 매우 유사한 방법을 독립적으로 제안했습니다.

수학이 매우 복잡하기 때문에 이러한 함수를 더 높은 수준에서 테스트해 보겠습니다.

이러한 VDF는 각 반복이 이전 반복의 입력을 필요로 하고 지정된 반복에서 향후 반복에 대한 정보를 사용할 수 없기 때문에 병렬로 처리할 수 없는 반복된 제곱 계산을 수행하도록 구성됩니다. 즉, 모든 반복을 거치기 전까지는 답을 알 수 없습니다. 이것은 기능이 순차적임을 보장합니다.

VDF를 검증하기 쉽게 만드는 것은 VDF 중간 입력과 최종 출력의 임의의 선형 조합으로 증명을 구축할 수 있다는 것입니다. 이러한 제한된 선형 조합의 계산은 전체 VDF를 계산하는 것보다 훨씬 적은 단계를 포함하기 때문에 간단합니다. 간단한 유추는 전체 곡선의 모든 값을 계산하는 것(전체 VDF를 계산하는 것)과 화살표를 선택하여 몇 단계 앞으로 나아가는 것(VDF의 효율성을 입증하는 것)의 차이입니다. 화살표가 몇 단계를 진행하는 데 걸리는 시간은 분명히 계산보다 훨씬 적습니다. 이렇게 하면 기능을 쉽게 확인할 수 있습니다.

Taraxa에서는 VDF에 다음 입력 항목을 설정합니다.