Go의 머클 트리: 제네릭과 증명

Go에서의 머클 트리: 제네릭과 포함 증명 구현

블록체인과 같이 수백만 개의 레코드를 가진 시스템에서 특정 요소의 존재를 검증하려면 일반적으로 전체 데이터셋을 전송해야 합니다. 머클 트리는 이 문제를 해결합니다: 백만 개의 트랜잭션 대신 O(log N)개의 해시만 필요합니다—백만 개 요소에 대해 약 20개 정도입니다. 이 구조는 이진 트리로 구성되며, 각 노드는 자식 노드들을 해시하고, 루트는 전체 집합을 요약합니다.

예시: 트랜잭션 A, B, C, D. 전체 집합을 직접 해시하면 클라이언트가 검증을 위해 모든 데이터를 가져야 합니다. 트리에서는 클라이언트가 인접 해시들: H(B), H(CD)를 받고—리프 A부터 루트까지 독립적으로 루트 해시를 재구성합니다.

기본 인터페이스와 노드 타입

모든 트리 노드를 위한 인터페이스로 시작하며, 제네릭을 지원합니다:

type Node[T any] interface {
    String() string
    StringIndent(level int) string
    AddChild(Node[T])
    GetBytes() []byte
    GetChildren() []Node[T]
}

리프는 값과 그 해시를 저장합니다. 어떤 타입의 값이든 직렬화하려면 CBOR를 사용하세요—맵에서 키 순서가 불안정한 JSON과 달리 결정론적 형식(RFC 8949)입니다.

type Leaf[T any] struct {
    Value     T
    ValueHash []byte
}

func NewLeaf[T any](value T, hash hash.Hash) (*Leaf[T], error) {
    hashedValue, err := valueToHash(value, hash)
    if err != nil {
        return nil, err
    }
    return &Leaf[T]{Value: value, ValueHash: hashedValue}, nil
}

func valueToHash(value any, hash hash.Hash) ([]byte, error) {
    encoded, err := cbor.Marshal(value)
    if err != nil {
        return nil, err
    }
    hash.Reset()
    hash.Write(encoded)
    return hash.Sum(nil), nil
}

이진 노드는 왼쪽과 오른쪽 자식을 집계합니다:

type BinaryNode[T any] struct {
    Value []byte
    Right Node[T]
    Left  Node[T]
}

해시 함수 팩토리로 트리 구축하기

트리는 깨끗한 해시 인스턴스를 생성하는 팩토리가 있는 구조로 관리됩니다—hash.Hash는 상태를 가지므로 함수를 전달하세요:

type BinaryTree[T any] struct {
    newHash func() hash.Hash
}

func NewBinaryTree[T any](newHash func() hash.Hash) *BinaryTree[T] {
    return &BinaryTree[T]{newHash: newHash}
}

// 사용법
tree := NewBinaryTree[string](sha256.New)

구성: 리프는 값을 해시하고, 내부 노드는 자식 해시들의 연결을 해시합니다. H(AB) = SHA256(H(A) + H(B)). 루트는 전체 트리의 최종 해시입니다.

머클 증명: 생성과 검증

포함 증명은 핵심 메커니즘입니다. 클라이언트는 대상 해시(H(A))와 루트 해시를 알고 있습니다. 서버는 리프에서 루트까지의 경로를 따라 인접 해시들을 제공합니다.

생성 알고리즘

• 루트에서 대상 리프로 내려갑니다.
• 각 레벨에서 형제 노드(경로의 일부가 아닌 왼쪽 또는 오른쪽)의 해시를 저장합니다.
• 증명은 이러한 해시들의 목록입니다.

아래에서 위로 검증:

• H(A)로 시작합니다.
• 순차적으로 인접 해시들과 해시하며, 측면(왼쪽/오른쪽)을 번갈아 가며 합니다.
• 루트에 도달—일치하면 포함이 확인됩니다.

2^20 요소(백만 개)의 경우, 증명은 각각 32바이트인 20개의 해시로, 약 640바이트입니다.

장점과 응용

• 로그 복잡도: 증명에 O(log N), SPV 클라이언트에 이상적입니다.
• 최소 트래픽: 비트코인 SPV는 전체 블록(500+ GB) 없이 트랜잭션을 검증합니다.

응용:

• 비트코인: 블록 헤더의 트랜잭션 루트.
• 이더리움: 상태 트라이, 트랜잭션 트라이, 영수증 트라이.
• Git: 커밋의 트리 객체.
• IPFS: 청크의 루트로서의 콘텐츠 해시.
• 인증서 투명성: SSL 인증서 로그 감사.

핵심 요약

• 머클 트리는 다른 데이터를 노출하지 않고 O(log N)으로 포함을 증명합니다.
• Go에서 타입 안전성을 위해 제네릭 사용; 어떤 타입이든 결정론적 해싱을 위해 CBOR 사용.
• 해시 함수 팩토리는 hash.Hash 상태로 인한 경쟁 조건을 방지합니다.
• 증명은 리프에서 루트까지의 경로를 따라 형제 해시들로 생성됩니다.
• 분산 시스템에 효율적: 블록체인, P2P 저장소.

— Editorial Team