Arweave 17판 백서 해석 (3): SPoRes 게임의 증명
이 글은 다소 하드코어합니다. 많은 수학적 유도와 증명이 포함될 것이니, 친구들은 준비를 해주셔야 합니다. 하지만 필자는 수학이 기초 학문으로서 어떤 사물을 논리적으로 설명하는 데 강한 정확성을 가지고 있다고 생각하기 때문에, 간단한 언어로 @ArweaveEco 메커니즘의 수학적 아름다움을 보여주고자 합니다.
백서 해석 (2) 기사에서 우리는 간결한 접근 증명 ( #SPoA ) 게임이 모든 참가자가 데이터 세트의 특정 위치에 실제로 데이터를 저장했음을 증명하는 데 사용될 수 있다고 설명했습니다. 이 패턴은 두 번째 게임을 만드는 데에도 사용될 수 있으며, 우리는 이를 간결한 복제 증명 (Succinct Proofs of Replications #SPoRes )이라고 부릅니다. 이는 증명자가 데이터 세트의 크기에 관계없이 매우 적은 데이터 전송 및 검증 비용으로 자신이 일정량의 데이터 복사본을 저장했음을 검증자에게 증명할 수 있도록 합니다.
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
SPoRes 게임
간결한 복제 증명 (SPoRes) 게임은 다음과 같이 진행됩니다. 앨리스는 자신이 n개의 머클화된 데이터 세트의 유일한 복사본을 저장하고 있다고 주장합니다. 밥은 앨리스가 거짓말을 하고 있는지 확인하고 싶어합니다. 이를 위해 그는 앨리스에게 난이도 매개변수 d와 무작위로 생성된 시드 Seed를 제공합니다. 앨리스는 이 시드를 사용하여 매초 체크포인트를 생성하는 VDF 해시 체인을 생성합니다. 이 체크포인트는 데이터 세트 내에서 최대 k개의 SPoA 도전을 잠금 해제하는 데 사용될 수 있습니다. 그녀가 이러한 도전에 해당하는 패키지 데이터 블록을 가지고 있을 때마다, 앨리스는 해당 SPoA 증명을 구축할 수 있습니다. 그런 다음 이 증명을 해시 처리하고 밥의 난이도 매개변수 d와 비교합니다. 만약 증명 해시 값이 d보다 크면, 앨리스는 유효한 솔루션을 찾았고 해당 증명을 밥에게 보냅니다. 밥은 무작위 시드를 보낸 시간과 앨리스의 유효한 증명을 받은 시간 사이의 시간을 기록합니다.
난이도 d에 기반하여, 유효한 솔루션을 찾기 위한 단일 시도의 성공 확률 p의 표현식은 다음과 같습니다:
공식 주석: SHA 256 기반 알고리즘은 256비트 문자열이므로 최대 해시 수는 2^256 (여기서「^」는 제곱을 의미함)입니다. d보다 큰 유효한 솔루션을 찾으려면 2^256-d의 해시 수가 필요하므로, 이를 통해 단일 시도 성공 확률을 계산할 수 있습니다.
앨리스가 n개의 복사본을 가지고 있고, 각 복사본이 매초 k회의 시도를 할 수 있다면, 그녀가 주어진 1초 내에 솔루션을 찾을 확률은 다음과 같습니다:
공식 주석: kN은 앨리스가 1초 내에 총 수행할 수 있는 해시 솔루션 시도 횟수를 의미하며, 이 시도 횟수는 앨리스가 저장한 유일한 복사본 수에 비례합니다. 구체적인 설명은 이전 기사 《Arweave 2.6은 아마도 사토시의 비전을 더 잘 반영할 것입니다》를 참조하십시오. 1-p는 단일 시도 실패 확률입니다. p2의 확률 값은 kN회의 시도 실패 확률을 뺀 1입니다.
위의 두 공식을 대입하여 유도하면 다음을 얻을 수 있습니다:
공식 주석: p를 P2의 공식에 대입하여 얻은 결과입니다.
앨리스가 증명을 제출하는 데 필요한 시간은 기하학적 랜덤 변수 X ~ geom(p2)로 시뮬레이션할 수 있으며, p2는 성공 확률입니다. 이 랜덤 변수 X는 d, k 및 n에 따라 달라집니다. 앨리스가 거짓말을 하고 있는지 확인하기 위해, 밥은 난이도 d를 전송하여 앨리스가 n개의 복사본을 가지고 있는 조건 하에 매 120초마다 밥에게 증명을 제출할 수 있도록 합니다. 이는 앨리스가 120초 내에 성공할 확률이 다음과 같음을 의미합니다:
공식 주석: 1/120은 120초 내에 한 번 증명을 성공적으로 제출할 확률입니다.
앨리스가 요구된 시간 내에 증명을 제출할 수 있다면, 그녀는 올바른 수량의 유일한 복사본을 가지고 있을 가능성이 높습니다. 그러나 한 번의 증명만으로는 밥이 앨리스가 거짓말을 하지 않았다고 확신하기에는 부족합니다. 앨리스가 오랜 시간 동안 평균적으로 매 120초마다 계속해서 증명을 제출할 수 있다면, 밥은 앨리스가 기대하는 데이터 양을 저장하고 있다고 합리적으로 확신할 수 있습니다.
다음으로 우리는 밥이 앨리스가 저장한 데이터의 확실성을 정량화하려고 합니다.
앨리스가 20개의 복사본을 저장하고 있다고 주장하며, 2주 동안 평균 120초마다 일관되게 증명을 제출했다고 가정합니다 (총 10,080개의 증명을 제출했습니다). 이때, 밥은 앨리스가 19개(또는 그 이하)의 복사본만 저장하고 있다면 여전히 이러한 증명을 제출할 확률이 얼마인지 궁금해합니다. 이는 서로 다른 1초 내에 증명을 제공할 확률에 해당합니다:
공식 주석: 여기서 19k는 앨리스가 19개의 복사본을 저장하고 있으며, 각 복사본이 k회의 시도를 통해 솔루션을 찾는 횟수입니다.
과도한 단순화:
이 확률은 밥이 정직한 앨리스를 위해 생성한 d 값을 사용하여 계산할 수 있습니다. 그녀가 19개 이하의 복사본을 저장하고 있다면, 1초 내에 증명을 제공할 확률은 다음과 같은 일련의 유도를 통해 얻을 수 있습니다. 여기서 p2는 앨리스가 정직하게 20개의 복사본을 저장했을 때 1초 내에 증명을 생성할 확률을 나타내고, p2*는 그녀가 거짓말을 할 경우 (저장 ≤ 19개 복사본) 1초 내에 증명을 제공할 확률을 나타냅니다:
이 유도 과정은 복잡해 보이지만, 기본적인 수학 능력이 있는 친구들은 모두 이해할 수 있습니다. 유도 과정은 위의 회사의 대입 과정입니다.
따라서 p2=0.00791832081로, 예상 증명 생성 시간은 126.2894초입니다. X를 p2에서 얻은 앨리스의 증명 제출 시간으로 설정하면, 즉 X ~ geom(p2)입니다. 이는 앨리스가 거짓말을 하는 경우 ------ 즉, 19개의 복사본만 저장했을 때, 제출 증명의 시간 X의 기대값(평균값)은 다음과 같습니다:
공식 주석: E[X*]는 앨리스가 19개의 복사본만 저장한 경우 성공적으로 증명을 제출하는 평균 시간이 126.2894초임을 나타냅니다. 만약 그녀가 20개의 복사본을 저장했다면, 성공적인 제출 시간은 평균 120초가 됩니다.
우리는 중심 극한 정리를 사용하여 샘플 평균이 120보다 낮을 확률을 추정할 수 있습니다. 이는 위에서 얻은 기대값 E[X*]와 다릅니다. 이 확률은 다음과 같이 표현됩니다:
공식 주석: 등식 왼쪽 표현식은 2주 동안 앨리스가 평균적으로 증명을 제출하는 시간이 120초 이하일 확률을 나타냅니다. 등식 오른쪽은 왼쪽 표현식의 변형입니다.
대량 샘플의 경우, 이 부등식의 왼쪽은 평균 E[X]와 분산 σX^2/n의 정규 분포로 수렴합니다. 여기서 σX*는 Xd의 표준 편차이고, n(여기서는 10,080)은 샘플 크기입니다. 따라서 위의 공식은 다음과 같이 변형될 수 있습니다:
우리는 이 분포를 표준 정규 형태로 변환하여 동등한 확률을 얻을 수 있습니다:
결국, 표준 정규 분포 표를 사용하여 우리는 앨리스가 이 주기 동안 거짓말을 할 확률을 얻을 수 있습니다:
따라서 이 예에서 밥은 약 99.99997416%의 확실성으로 2주 동안 앨리스가 19개 이상의 데이터 세트 복사본을 저장했다고 판단할 수 있습니다. 우리는 앨리스가 저장한 복사본이 19개 미만일 경우 예상 증명 제출 시간이 126.3초를 초과할 것임을 주목합니다. 또한 전체 증명 시스템은 120초마다 한 번의 증명만 전송하면 됩니다. 이는 앨리스와 밥 간의 평균 데이터 전송 속도가 초당 2.389 KB(280 KB/120초)로 비트코인 네트워크의 동기화 비용과 유사하다는 것을 의미합니다.
마지막으로, 이러한 확률은 데이터 세트 크기가 임의로 증가하더라도 변경되지 않으며, 샘플링 주기를 늘리면 밥이 앨리스의 복사본 수에 대한 확실성을 초선형 속도로 지속적으로 향상시킬 수 있습니다 (그림 1).
그림 1: 간결한 복제 증명 (SPoRes) 게임에서 샘플 지속 시간의 증가에 대한 확실성은 초선형적입니다. 2주간의 샘플 수집 후, 19개 미만의 복사본을 유지할 확률은 미미합니다 (P<0.0000002584).
따라서 SPoRes 게임은 다음과 같은 매개변수로 정의됩니다:
여기서:
r= 게임에 사용되는 데이터 세트의 머클 루트.
k= 각 복사본이 매초 잠금을 해제할 수 있는 최대 도전 수.
d= 각 시도 시 성공 확률을 결정하는 난이도 매개변수입니다.
✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨
이러한 흥미로운 수학적 유도를 통해, 우리는 합리적인 시간 내에 광부가 지속적으로 증명을 제출하면 데이터가 저장되었는지 확실히 판단할 수 있다는 것을 안심하고 확신할 수 있습니다. 이는 Arweave가 분산 저장을 목표로 하는 합의 메커니즘의 핵심을 형성합니다. 수학의 재미는 이제 시작에 불과하며, 다음 기사에서는 더 많은 흥미로운 유도와 증명이 있을 것입니다.