본 문서에서는 Arweave 최신 백서의 제3절을 소개합니다. 이 부분은 주로 몇 가지 기본 개념에 대한 설명으로, 이후 메커니즘 소개를 위한 기초를 마련합니다. 원래 이 부분에는 SPoRes의 메커니즘 증명이 포함되어 있었으나, 전부 공식과 수학적 유도 과정으로 이루어져 있어, 저자는 별도로 해석하는 것이 더 합리적일 것이라고 생각했습니다.

Arweave의 채굴 메커니즘은 여러 가지 다른 알고리즘과 데이터 구조를 결합하여 비상호작용적이고 간결한 데이터 복제 저장 증명을 형성합니다. 본 문서에서는 먼저 메커니즘 개념을 추상적으로 이해한 후, 이를 Arweave 채굴 과정에서의 사용에 대해 설명합니다.

백서 주소：https://www.arweave.org/files/arweave-lightpaper.pdf

블록 인덱스

Arweave에서 가장 높은 데이터 구조는 블록 인덱스(Block Index)라고 불립니다. 이는 3원소(3-tuples)로 구성된 머클화 리스트로, 각 원소는 세 가지 차원의 정보를 포함합니다: 블록 해시(A Block Hash), 직조 네트워크 크기(A Weave Size), 거래 루트(A Transaction Root). 이 리스트는 해시 머클 트리 형태로 표현되며, 최상위의 머클 루트는 네트워크의 현재 최신 상태를 나타냅니다. 이 루트는 두 개의 요소의 해시로 구성됩니다 - 최신 원소(최신 블록을 나타냄)와 이전 블록 인덱스의 머클 루트. 블록을 생성할 때, 채굴자는 이전 블록 인덱스의 머클 루트를 새 블록에 삽입합니다.

각 블록에 블록 인덱스의 머클 루트를 구축하고 삽입함으로써, 최신 블록에 대해 SPV 증명을 수행한 Arweave 네트워크 노드는 이전의 블록을 완전히 검증할 수 있습니다. 이는 전통적인 블록체인과 대조적이며, 전통적인 블록체인에서는 이전 블록의 거래를 검증하기 위해 전체 체인을 추적해야 합니다. 그러나 Arweave에서는 네트워크 최상단에 대해 SPV 검증을 수행한 후, 블록 인덱스 검증 메커니즘을 통해 사용자가 네트워크 최상단에 대해 SPV 검증을 수행한 후에도 직조 네트워크의 이전 블록을 검증할 수 있으며, 더 이상 중간 블록 헤드를 다운로드하거나 검증할 필요가 없습니다.

그림 1: 블록 인덱스는 Arweave 네트워크에서 블록의 머클 트리를 나타냅니다.

머클화 데이터

그렇다면 데이터는 네트워크에 어떻게 저장될까요?

정보가 Arweave에 저장되어야 할 때, 데이터는 규격에 따라 256 KB의 데이터 블록(Chunk)으로 나누어집니다. 이러한 데이터 블록이 준비되면, 머클 트리를 구축하고 그 루트(데이터 루트 Data Root라고 함)를 거래에 제출합니다. 해당 거래는 서명되고 업로드자가 네트워크에 전송합니다. 이렇게 구축된 각 거래는 소속 블록의 거래 루트(Transaction Root)에 기록됩니다. 따라서 하나의 블록의 거래 루트는 실제로 거래 데이터 루트의 머클 루트입니다.

그림 2: 거래 루트는 블록 내 각 거래에 존재하는 데이터 루트의 머클 루트입니다.

채굴자는 이러한 거래를 조합하여 하나의 블록을 만들고, 거래 내의 데이터 루트를 사용하여 거래 루트를 계산하고 이 거래 루트를 새 블록에 포함시킵니다. 이 거래 루트는 최종적으로 최상위 블록 인덱스에 나타납니다. 이 과정은 모든 데이터가 순서대로 데이터 블록으로 나누어진 지속적으로 확장되는 머클 트리를 생성합니다.

간결한 접근 증명 SPoA

Arweave 네트워크에서 머클 트리의 노드는 데이터 블록을 "왼쪽" 또는 "오른쪽"의 오프셋 위치로 표시하여 데이터 블록을 태깅합니다. 이러한 노드 태깅 방법은 특정 위치에서 데이터 블록의 존재성을 검증하기 위해 매우 간결한 머클 증명을 생성할 수 있습니다. 이러한 머클 트리는 "불균형 트리"라고 불리며, 한쪽의 리프 노드 수가 다른 쪽과 같지 않을 수 있습니다. 이 구조는 채굴자의 하드 드라이브에 실제로 해당 데이터가 존재함을 검증하기 위한 간결한 비상호작용 증명 게임을 구축하는 데 사용될 수 있습니다.

그림 3: 데이터 루트(data root)는 단일 거래에서 모든 데이터 블록이 해시 처리된 머클 루트입니다.

우리는 Bob과 Alice의 게임을 통해 간결한 접근 증명(Succinct Proof of Access, SPoA)이 무엇인지 이해합니다. Bob은 Alice가 머클화 데이터 세트의 특정 위치에 데이터를 저장했는지 검증하고자 합니다. 게임을 시작하기 위해 Bob과 Alice는 동일한 데이터 세트의 머클 루트를 가져야 합니다. 게임은 세 단계로 나뉩니다: 도전, 증명 구축 및 검증.

• 도전: Bob은 Alice에게 데이터 블록의 오프셋(데이터 블록 위치 좌표로 이해하면 더 명확할 수 있음)을 보내 도전을 시작합니다 ------ Alice는 이 위치 인덱스의 데이터에 접근할 수 있음을 증명해야 합니다.

그림 4: Alice는 오프셋 태그가 있는 머클 트리를 탐색하여 도전 데이터 블록(Chunk)을 검색할 수 있습니다.

• 증명 구축: 이 도전을 받은 후, Alice는 증명을 구축하기 시작합니다. 그녀는 자신의 머클 트리를 검색하여 오프셋에 해당하는 데이터 블록을 찾습니다, 그림 4와 같이. 증명 구축의 첫 번째 단계에서, Alice는 저장소에서 전체 데이터 블록을 검색합니다. 그런 다음, 그녀는 해당 데이터 블록과 머클 트리를 사용하여 머클 증명 경로를 구성합니다. 그녀는 전체 데이터 블록을 해시 처리하여 32바이트 문자열을 얻고, 트리에서 이 리프 노드의 부모 노드를 찾습니다. 부모 노드는 자신의 오프셋과 두 개의 자식 노드의 해시 값을 포함하는 노드로, 각 해시 값은 32바이트 길이입니다. 이 부모 노드는 증명에 추가됩니다. 그런 다음 각 상위 부모 노드를 재귀적으로 증명에 추가하여 머클 루트에 도달할 때까지 진행합니다. 이 일련의 노드는 머클 경로 증명을 형성하며, Alice는 이 증명을 데이터 블록과 함께 Bob에게 전송합니다.

그림 5: 도전 오프셋의 증명은 오프셋에 저장된 데이터 블록과 그 머클 경로를 포함합니다.

• 검증: Bob은 Alice로부터 받은 머클 증명과 데이터 블록을 수신합니다. 그는 트리의 최상단에서 리프까지 해시 값을 하나씩 확인하여 머클 증명의 정확성을 검증합니다. 그런 다음, 그는 Alice가 제공한 증명에서 데이터 블록을 해시 처리하여 이 데이터 블록이 올바른 위치에 있는 데이터 블록인지 확인합니다. 만약 이 해시 값들이 모두 일치하면 증명이 유효하다는 것을 의미합니다. 그러나 검증 과정에서 어떤 해시 값이 일치하지 않으면, Bob은 즉시 검증을 중단하고 Alice의 증명이 무효하다고 판단합니다. 이 검증 결과는 증명이 통과했는지 여부를 나타내는 간단한 예 또는 아니오의 과정입니다.

이 간결한 접근 증명(SPoA)의 구성, 전송 및 검증의 복잡도는 O(logn)이며, 여기서 n은 데이터 세트의 크기를 바이트 단위로 나타냅니다. 실제로 이는 크기가 2의 256제곱 바이트인 데이터 세트에서 단일 바이트 위치와 정확성의 증명이 256 * 96B(최대 경로 크기) + 256 KB(최대 데이터 블록 크기)≈ 280 KB로 전송될 수 있음을 의미합니다.

복제의 유일성

Arweave 네트워크는 채굴 능력을 채굴자(또는 협력하는 채굴자 그룹)가 접근할 수 있는 직조 네트워크 복제 수에 비례하도록 설계했습니다. 복제 유일성 계획이 없는 경우, 데이터의 백업은 내용상 서로 완전히 동일합니다. 단일 데이터의 여러 유일한 복제를 장려하고 측정하기 위해, Arweave는 이 문제를 해결하기 위해 패킹(Packing) 시스템을 사용합니다.

패킹 Packing

패킹 메커니즘은 채굴자가 동일한 데이터 블록으로 여러 SPoA 증명을 위조할 수 없도록 보장합니다. Arweave는 RandomX 패킹 계획을 인용하여 원본 데이터 블록을 "패킹"된 데이터 블록으로 변환하며, 이 과정은 채굴자에게 일정한 계산 비용을 발생시킵니다.

패킹 과정은 다음과 같습니다:

• 데이터 블록 오프셋, 거래 루트 및 채굴 주소가 SHA-256 해시에서 사용되어 패킹 키(Packing Key)를 생성합니다.
• 패킹 키는 알고리즘의 엔트로피로 사용되며, 몇 라운드의 RandomX 실행 후 2 MB의 임시 저장소를 생성합니다. 이 패킹 메커니즘의 구성 요소는 규칙을 준수하지 않는 채굴자에게 상당한 비용을 초래합니다.
• 이 엔트로피의 처음 256 KB는 페이스텔 암호(Feistel cypher)를 통해 블록을 대칭적으로 암호화하는 데 사용됩니다. 이를 통해 패킹 데이터 블록이 생성됩니다.

연속적으로 읽는 시간 주기 내에서 패킹 데이터 블록의 총 비용이 저장된 패킹 데이터 블록의 비용을 초과하면, 채굴자는 고유한 데이터 블록을 저장하도록 유도됩니다. 따라서 이러한 올바른 행동을 장려하기 위해서는 다음 조건을 충족해야 합니다:

여기서:

Cs= 데이터 블록을 저장하는 단위 시간 비용

Cp= 데이터 블록을 패킹하는 비용

t= 데이터 블록 읽기 사이의 평균 시간

여기서 패킹 총 비용은 계산에 필요한 전력 비용, 전용 하드웨어 비용 및 평균 사용 수명을 포함합니다. 저장 비용 또한 하드 드라이브 비용, 하드 드라이브 평균 고장 시간, 하드 드라이브 운영 전력 비용 및 저장 하드웨어 운영과 관련된 기타 비용에서 계산될 수 있습니다. 우리는 "온디맨드" 투기 채굴자와 저장된 패킹 데이터 블록의 정직한 채굴자의 비용 비율을 계산하여 패킹 데이터 블록의 안전 마진을 추정할 수 있습니다. 실제로 Arweave는 안전 비율을 사용합니다 - 즉, 온디맨드 투기 채굴의 비용과 데이터 저장 정직한 채굴의 비용 비율 - 본 문서 작성 시 약 19:1입니다.

RandomX

하드웨어 가속 전략에 저항하기 위해, Arweave는 해시 알고리즘 RandomX를 사용하여 패킹 키를 처리합니다. RandomX는 범용 CPU에 최적화되어 있으며, 해시 과정에서 무작위 코드 실행과 다양한 메모리 집약적 기술을 적용하여 GPU 및 ASIC과 같은 전용 하드웨어의 계산 효율성을 크게 제한합니다.

RandomX는 무작위로 생성된 프로그램을 사용하여 범용 CPU의 하드웨어 특성과 높은 일치를 이루며, 이는 RandomX 해시 속도를 높이기 위한 유일한 방법이 더 빠른 범용 CPU를 개발하는 것임을 의미합니다. 이는 이론적으로 더 빠른 CPU 개발의 동기가 될 수 있지만, 실제로 기존의 CPU 속도 향상 동기에 비해 이 동기가 미치는 영향은 거의 무시할 수 있습니다.

검증 가능한 지연 함수 VDF

검증 가능한 지연 함수(Verifiable Delay Function, VDF)는 검증 가능한 암호화된 디지털 시계와 같으며, 사건 간의 시간 흐름을 계산하여 검증할 수 있게 해줍니다. VDF는 지정된 수의 해시 계산을 순차적으로 비병렬로 수행해야 하며, 이를 통해 독특하고 효율적으로 검증 가능한 출력을 생성합니다. Arweave 프로토콜은 VDF를 생성하기 위해 체인 해시(Hash Chain)라는 기술을 사용하며, 이는 재귀적으로 정의됩니다:

공식 주석: n 번째 VDF 해시는 이전 VDF 해시를 다시 해시 처리한 것입니다.

n = 1일 때:

공식 주석: n=1일 경우, 즉 첫 번째 VDF 해시는 씨드의 해시 계산입니다.

Arweave VDF에서 사용하는 해시 함수는 SHA2-256입니다. 이러한 구조를 통해, 시중에서 가장 빠른 CPU 프로세서가 초당 k개의 SHA2-256 해시 값을 연속적으로 계산할 수 있다면, 씨드(seed)에 대해 V(k,seed) 계산을 수행하는 데 최소 1초가 필요합니다. 이는 연속 해시 과정이며, 위의 공식에서 보듯이 n=1일 때 씨드를 해시 처리하고, n=2일 때 V(2,seed)는 V(1,seed)의 해시 계산입니다. 올바르게 생성된 V(k,seed)는 체크포인트(Checkpoint)라고 하며, 이는 증명자가 씨드를 수신하고 이 체크포인트를 생성하는 데 최소 1초가 경과했음을 의미합니다.

만약 VDF 구조가 O(n) 시간을 필요로 하여 n 단계의 계산을 완료해야 한다면, 검증자는 p개의 병렬 스레드를 사용하여 O(n/p) 시간 내에 VDF 출력을 검증할 수 있습니다. 여기서 주의해야 할 점은, VDF의 생성에는 병렬 스레드 계산을 사용해서는 안 되지만, 검증은 가능하며, 이는 검증 과정을 더욱 빠르고 효율적으로 만들 수 있습니다. 우리는 체인 해시 VDF를 사용하는 이유는 그 간단한 구조와 해시 함수의 강건성에 완전히 의존하기 때문입니다.