러스트 학습 - 머클 트리

최근 여가 시간에 Rust를 배우기 시작했고 연습으로 Merkle Tree( Wiki )를 구현하기로 결정했습니다.

쉬울 것 같지만 진짜 모험이었습니다 :) 이 게시물에서 저는 제 경험을 공유하고 있습니다.

1 단계

데이터 구조를 준비하는 것으로 시작했습니다. 다음은 많은 언어에서 작동하는 정말 기본적인 것입니다.

struct MerkelTree {
    leaves: Vec<MerkelNode>
}

struct MerkelNode {
    parent: Option<MerkelNode>,
    hash: String
}

Merkel 트리는 "잎"으로 표시된 노드 목록으로 구성됩니다. 각 리프에는 해당 데이터 블록의 해시와 상위 노드에 대한 링크가 포함됩니다. 상위 노드는 두 개의 리프(이진 트리)를 그룹화하고 해당 해시의 해시를 포함합니다. 또한 상위 수준에서 두 개의 노드를 그룹화하는 상위 노드에 대한 링크도 포함합니다. 이 규칙은 위쪽 루트 노드에서 단일 노드로 끝날 때까지 위쪽으로 반복됩니다. 소위 "루트 해시"를 포함하며 부모가 없습니다.

말할 필요도 없이 내가 디자인한 구조는 작동하지 않았습니다.
오류는 다음과 같이 말했습니다.

struct MerkelNode {
   | ^^^^^^^^^^^^^^^^^ recursive type has infinite size

이것은 Rust에서 꽤 잘 알려진 오류로 판명되었습니다. 컴파일 시간에 유형이 차지하는 공간을 알아야 합니다. 내가 취한 접근 방식으로는 불가능합니다.

여기에 설명된 문제에 대한 쉬운 해결책이 있습니다.
Enabling-recursive-types-with-boxes .
자, 한번 해봅시다.

2 단계

데이터를 힙에 저장할 수 있는 "박스"스마트 포인터를 사용했습니다. 그런 식으로 내 구조는 컴파일 타임에 알려진 고정 크기를 갖습니다.

struct MerkelNode {
    parent: Option<Box<MerkelNode>>,
    hash: String
}

위의 코드는 컴파일되므로 구현을 시작하게 되어 기쁩니다. 그러나 몇 시간이 지난 후에도 여전히 코드를 컴파일할 수 없었습니다...
문제는 논리가 아니었다. 문제는 내가 원하는 것을 Rust가 수용할 수 있는 방식으로 표현하지 못했다는 것입니다.

그런 다음 나에게 왔습니다. 작동하지 않고 문제는 다시 구조에 있습니다.
Rust의 두 가지 핵심 규칙은 다음과 같습니다.

Rust의 각 값에는 소유자가 있습니다.

한 번에 한 명의 소유자만 있을 수 있습니다.

하지만 제 경우에는 예를 들어 같은 부모를 가리키는 두 개의 잎이 있습니다. 그들 중 부모의 소유자는 누구입니까?

3단계

좋아, 두 명의 소유자를 가질 수 없으므로 값을 빌려 참조를 사용해야 함을 의미합니다.

struct MerkelNode {
    parent: Option<Box<&MerkelNode>>,
    hash: String
}

그러나 위 코드는 구조의 참조가 수명을 사용해야 하기 때문에 컴파일되지 않습니다.

struct MerkelNode<'a> {
    parent: Option<Box<&'a MerkelNode<'a>>>,
    hash: String
}

코드가 약간 복잡해 보이지만 적어도 컴파일됩니다. 그런 다음 구현을 계속하겠습니다.

몇 시간 후에 다시 한 번 결론에 도달했습니다. 이 방식으로는 작동할 수 없습니다.
가치를 여러 번 빌릴 수 있습니다. 괜찮아. 하지만 이 규칙은 어떻습니까?

Rust의 각 값에는 소유자가 있습니다.

지금은 주인이 없는 것 같습니다. 내 말은 - 라인을 따라 어딘가에 있지만 프로그램 전체 기간 동안 저장할 전용 장소가 없습니다.

4단계

그 시점에서 저는 제가 근본적으로 잘못된 일을 하고 있다는 결론에 도달했습니다. Rust에는 내가 원하는 것을 할 수 있는 패턴이 있어야 합니다...

인터넷 검색 끝에 마침내 다음을 찾았습니다.
The Reference Counted Smart Pointer

다중 소유권 기능을 제공합니다.

구조의 정의는 다음과 같습니다.

struct MerkelNode {
    parent:Option<Rc<MerkelNode>>,
    hash: String
}

이제 마지막으로 동일한 부모 노드에 대해 두 명의 소유자를 가질 수 있습니다.

여기에는 단 하나의 마지막 문제가 있습니다. Rc는 데이터를 읽기 전용으로 공유할 수 있도록 허용합니다. 제 경우에는 충분하지 않습니다. 일단 노드를 생성하면 생성 시점에 알려지지 않은 부모에 대한 포인터로 수정해야 하기 때문입니다.

1시간 정도 지나면....

5단계

Rust에 interior mutability pattern이 있어 필요한 것을 정확하게 수행할 수 있습니다.

구조의 최종 정의는 다음과 같습니다.

struct MerkelNode {
     parent: Option<Rc<RefCell<MerkelNode>>>,
     hash: String
}

이 구조로 작업 솔루션을 구현할 수 있었습니다. 아직 내 코드에 최적화해야 할 것들이 많이 있다고 확신하지만 오늘은 이 일을 끝내고 축하합니다 :)