고급
동시 머클 트리
소개
머클 트리는 각 리프 노드가 일부 데이터를 나타내는 해시로 레이블이 지정된 트리 데이터 구조입니다. 인접한 리프들이 함께 해싱되고, 결과 해시가 해당 리프들의 부모인 노드의 레이블이 됩니다. 같은 레벨의 노드들이 다시 함께 해싱되고, 결과 해시가 해당 노드들의 부모인 노드의 레이블이 됩니다. 이 과정은 루트 노드에 대해 단일 해시가 생성될 때까지 계속됩니다. 이 단일 해시는 전체 트리의 데이터 무결성을 암호학적으로 나타내며 머클 루트라고 합니다.
대부분의 머클 트리는 이진 트리이지만 반드시 그럴 필요는 없습니다. Bubblegum 압축된 NFT(cNFT)에 사용되는 머클 트리는 다이어그램에 표시된 것처럼 이진 트리입니다.
블록체인에 데이터 상태를 저장하는 것에 대해 이야기할 때, 이 머클 루트를 저장하면 루트를 생성하기 위해 이전에 해싱된 모든 것의 데이터 무결성을 나타내는 단일 값을 효과적으로 저장할 수 있습니다. 트리의 어떤 리프 값이 변경되면 기존 머클 루트는 무효가 되고 다시 계산되어야 합니다.
Bubblegum 압축된 NFT의 경우 리프 노드 해시는 리프 스키마의 해시입니다. 리프 스키마는 리프 ID, 소유자/위임자 정보, cNFT의 크리에이터를 나타내는 creator_hash, 그리고 일반적으로 압축된 NFT의 메타데이터를 나타내는 data_hash(크리에이터 배열을 다시 포함)을 포함합니다. 따라서 단일 압축된 NFT를 암호학적으로 확인하는 데 필요한 모든 정보가 해싱된 리프 스키마에 저장됩니다.
리프 경로
이전 섹션에서 배운 것처럼, 머클 트리에서는 리프 노드만이 최종 사용자 데이터를 나타냅니다. 해시로 이어지는 내부 노드들은 모두 머클 루트를 위한 중간 값일 뿐입니다. 리프 노드의 경로를 언급할 때, 리프 노드 해시 자체와 머클 루트로 직접 이어지는 내부 노드들을 의미합니다. 예를 들어, 리프 2의 경로가 아래 다이어그램에 강조 표시되어 있습니다.
리프 증명
압축된 NFT가 머클 트리에 존재하는지 증명하려면 모든 리프 노드를 다시 해싱할 필요가 없습니다. 아래 다이어그램에서 볼 수 있듯이 머클 루트를 계산할 때까지 함께 해싱할 특정 값들만 있으면 됩니다. 이러한 값들을 리프의 증명이라고 합니다. 구체적으로, 리프 노드의 증명은 인접한 리프 노드의 해시와 머클 루트를 계산하는 데 사용할 수 있는 인접한 내부 노드 해시들입니다. 리프 2의 증명이 아래 다이어그램에 강조 표시되어 있습니다.
리프 검증
리프 노드와 그 증명을 사용하여 머클 루트를 계산하는 과정은 다음과 같습니다:
- 원시 리프 스키마로 시작하여 해싱합니다.
- 1단계의 값을 형제 리프 노드의 해시와 해싱하여 리프 경로의 다음 값을 생성합니다.
- 2단계의 경로 값을 증명의 다음 값인 다음 형제 내부 노드와 해싱합니다.
- 머클 루트를 계산할 때까지 형제 내부 노드 값들과 값을 해싱하는 이 과정을 트리 위쪽으로 계속합니다.
우리가 계산한 머클 루트가 해당 트리에 대해 주어진 머클 루트와 일치하면 정확한 리프 노드가 머클 트리에 존재한다는 것을 알 수 있습니다. 또한 리프 노드가 업데이트될 때마다(즉, cNFT가 새 소유자에게 전송될 때) 새로운 머클 루트를 계산하고 온체인에서 업데이트해야 합니다.
동시성
cNFT에 사용되는 온체인 머클 트리는 동일한 블록에서 여러 쓰기를 처리할 수 있어야 합니다. 트리에 새로운 cNFT를 민팅하고, cNFT를 전송하고, cNFT를 위임하고, cNFT를 소각하는 등의 여러 트랜잭션이 있을 수 있기 때문입니다. 문제는 온체인 트리에 대한 첫 번째 쓰기가 동일한 블록 내의 다른 쓰기를 위해 전송된 증명을 무효화한다는 것입니다.
이에 대한 해결책은 spl-account-compression에서 사용하는 머클 트리가 하나의 머클 루트만 저장하는 것이 아니라 이전 루트들과 이전에 수정된 리프들의 경로에 대한 ChangeLog도 저장한다는 것입니다. 새 트랜잭션이 보낸 루트와 증명이 이전 업데이트로 무효화되었더라도 프로그램이 증명을 빨리 감습니다. 사용 가능한 ChangeLog 수는 트리를 생성할 때 사용되는 최대 버퍼 크기에 의해 설정됩니다.
또한 머클 트리의 가장 오른쪽 증명이 온체인에 저장됩니다. 이를 통해 증명을 보낼 필요 없이 트리에 추가할 수 있습니다. 이것이 바로 Bubblegum이 증명 없이 새로운 cNFT를 민팅할 수 있는 방법입니다.