Merkle Trie

← 메인 | English →

API

개요

Sigilaris merkle 패키지는 암호학적으로 검증된 키-값 저장소를 위한 고성능, 타입 안전한 Merkle Trie 구현을 제공합니다. Merkle Trie는 트라이(접두사 트리)의 장점과 머클 트리의 장점을 결합하여, 효율적인 키-값 연산과 함께 전체 트리 상태에 대한 암호학적 검증을 가능하게 합니다.

왜 Merkle Trie가 필요한가? 블록체인과 분산 시스템에서는 데이터 무결성 검증이 매우 중요합니다. Merkle Trie를 사용하면:

주요 특징:

빠른 시작 (30초)

import cats.effect.IO
import cats.effect.unsafe.implicits.global
import cats.data.{EitherT, Kleisli}
import org.sigilaris.core.merkle.*
import org.sigilaris.core.merkle.Nibbles.{given, *}
import scodec.bits.ByteVector

// 간단한 인메모리 노드 저장소 생성
val store = scala.collection.mutable.Map.empty[MerkleTrieNode.MerkleHash, MerkleTrieNode]

given MerkleTrie.NodeStore[IO] =
  Kleisli { hash =>
    EitherT.rightT[IO, String](store.get(hash))
  }

// 노드를 저장소에 저장하는 헬퍼 함수
def saveNodes(state: MerkleTrieState): Unit =
  state.diff.toMap.foreach { case (hash, (node, _)) =>
    store.put(hash, node)
  }

// 빈 트라이 상태로 시작
val initialState = MerkleTrieState.empty

// 키-값 쌍 삽입
val key1 = ByteVector(0x12, 0x34).toNibbles
val value1 = ByteVector.fromValidHex("abcd")

val key2 = ByteVector(0x12, 0x56).toNibbles
val value2 = ByteVector.fromValidHex("ef01")

val program = for
  _ <- MerkleTrie.put[IO](key1, value1)
  _ <- MerkleTrie.put[IO](key2, value2)
  result <- MerkleTrie.get[IO](key1)
yield result

// 프로그램 실행 후 최종 상태 획득
val (finalState, retrievedValue) = program.run(initialState).value.unsafeRunSync() match
  case Right(r) => r
  case Left(e) => throw new Exception(e)

// 향후 쿼리를 위해 노드를 저장소에 저장
saveNodes(finalState)

// 조회한 값이 삽입한 값과 일치
assert(retrievedValue.contains(value1))

// 최종 상태는 전체 트리를 나타내는 루트 해시를 가짐
assert(finalState.root.isDefined)

이게 전부입니다! Merkle Trie가 자동으로:

문서

핵심 개념

주요 타입

MerkleTrieNode

트라이의 노드를 나타내며 세 가지 변형을 가짐:

각 노드는:

Nibbles

4비트 경계에 정렬된 비트 벡터로, 16진수 숫자 (0-F)를 나타냅니다. 트라이의 키 경로에 사용됩니다.

import org.sigilaris.core.merkle.Nibbles
import org.sigilaris.core.merkle.Nibbles.{given, *}
import scodec.bits.ByteVector

val bytes = ByteVector(0x12, 0x34, 0x56)
val nibbles = bytes.toNibbles

nibbles.hex // "123456"
nibbles.nibbleSize // 6

// head와 tail로 분해
val headTail = nibbles.unCons
// headTail = Some((1, "23456"을 나타내는 nibbles))

MerkleTrieState

트라이의 현재 상태를 추적:

효율적인 상태 관리를 가능하게 함:

import org.sigilaris.core.merkle.*
import org.sigilaris.core.crypto.Hash

// 빈 상태로 시작
val state1 = MerkleTrieState.empty

// 또는 기존 루트 해시로부터
val rootHash: MerkleTrieNode.MerkleRoot = ??? // 어딘가로부터
val state2 = MerkleTrieState.fromRoot(rootHash)

MerkleTrie 연산

모든 연산은 이펙트풀하며 StateT[EitherT[F, String, *], MerkleTrieState, A]를 통해 상태를 유지:

활용 사례

1. 기본 키-값 저장소

import cats.effect.IO
import org.sigilaris.core.merkle.*
import scodec.bits.ByteVector

// 노드 저장소 구현 정의
given MerkleTrie.NodeStore[IO] = ???

val key = ByteVector(0x01, 0x02).bits.assumeNibbles
val value = ByteVector.fromValidHex("deadbeef")

val program = for
  _ <- MerkleTrie.put[IO](key, value)
  retrieved <- MerkleTrie.get[IO](key)
yield retrieved

val (state, result) = program.run(MerkleTrieState.empty).value.unsafeRunSync().toOption.get

2. 키-값 쌍 스트리밍

import fs2.Stream
import cats.effect.IO
import org.sigilaris.core.merkle.*

given MerkleTrie.NodeStore[IO] = ???

val startKey = ByteVector(0x00).bits.assumeNibbles

val program = for
  stream <- MerkleTrie.streamFrom[IO](startKey)
  pairs <- stream.compile.toList
yield pairs

// pairs는 사전순으로 모든 키-값 쌍을 포함

3. Merkle 증명 검증

import org.sigilaris.core.merkle.*

// 트라이를 구축한 후, 루트 해시로 무결성 검증 가능
val state: MerkleTrieState = ???
val rootHash = state.root // 이 해시는 전체 트리 상태를 고유하게 식별

// 이 루트 해시를 가진 누구나 트리의 내용에 대한 증명을 검증 가능

4. 변경 추적을 통한 증분 업데이트

import cats.effect.IO
import org.sigilaris.core.merkle.*

given MerkleTrie.NodeStore[IO] = ???

val baseState = MerkleTrieState.fromRoot(???) // 기존 루트

val updates = for
  _ <- MerkleTrie.put[IO](key1, value1)
  _ <- MerkleTrie.put[IO](key2, value2)
  _ <- MerkleTrie.remove[IO](key3)
yield ()

val (newState, _) = updates.run(baseState).value.unsafeRunSync().toOption.get

// newState.diff는 변경된 노드만 포함
// 이를 통해 다른 노드와의 효율적인 동기화 가능

데이터 구조 세부사항

Trie 구조

Merkle Trie는 16진 분기 인수(hexadecimal branching factor)를 사용하며, 각 노드는 니블 0-F에 해당하는 최대 16개의 자식을 가질 수 있습니다.

경로 압축: 노드는 경로를 압축하기 위해 prefix를 저장합니다. 예를 들어, 서브트리에 경로 "abcdef"에 하나의 리프만 있다면, 트라이는 6레벨의 노드를 생성하지 않고 접두사 "abcdef"를 가진 단일 리프를 저장합니다.

트리 예제:

        Root (prefix: "")
         |
    Branch (prefix: "12")
       /    \
  Leaf     Leaf
  (34)     (56)
  val1     val2

해싱 전략

각 노드의 해시는 다음과 같이 계산됩니다:

hash(node) = keccak256(encode(node))

여기서 encode(node)는 다음을 포함:

루트 해시는 전체 트리 상태를 고유하게 식별합니다. 어떤 노드에 대한 변경이라도 위로 전파되어 새로운 루트 해시를 생성합니다.

성능 특성

시간 복잡도

공간 복잡도

메모리 사용

타입 규약

Nibbles 표현

해시 값

Children 배열

다음 단계

제한사항

참고자료

← 메인 | English →