grin/doc/translations/mmr_KR.md

Merkle Mountain Ranges

다른 언어로 되어있는 문서를 읽으려면: English, 简体中文.

MMR의 구조

Merkle Mountain Ranges [1]은 Merkle trees [2]의 대안입니다. 후자는 완벽하게 균형 잡힌 이진 트리를 사용하지만 전자는 완벽하게 균형잡힌 binary tree list 거나 오른쪽 상단에서 잘린 single binary tree로 볼 수 있습니다. Merkle Mountain Range (MMR)는 엄격하게 append 에서만 사용됩니다. 원소는 왼쪽에서 오른쪽으로 추가되고, 두 하위 원소가 있는 즉시 부모를 추가하여 그에 따라 범위를 채웁니다.

다음 그림은 각 노드를 삽입 순서대로 표시한 것입니다. 11 개의 삽입 된 리프와 총크기 19가 있는 range 를 표시합니다.

Height

3              14
             /    \
            /      \
           /        \
          /          \
2        6            13
       /   \        /    \
1     2     5      9     12     17
     / \   / \    / \   /  \   /  \
0   0   1 3   4  7   8 10  11 15  16 18

이 구조는 편평한 리스트로 표시할 수 있습니다. 여기서는 각 노드의 삽입 포지션에서 노드의 높이를 나타냅니다. ( 위의 그림과 아래의 평면 리스트를 비교하면 이해가 쉬움 - 역자 주 )

0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
0  0  1  0  0  1  2  0  0  1  0  0  1  2  3  0  0  1  0

이 구조는 크기(19)에서 간단히 설명 할 수 있습니다. 빠른 binary operation을 사용하기 때문에 MMR 내에서 탐색하는 것도 매우 간단합니다. 주어진 노드의 위치n이라면 이 MMR의 높이, 부모의 위치, 형제 등을 계산할 수 있습니다.

Hashing 과 Bagging

Merkle tree와 마찬가지로 MMR의 부모 노드는 자신의 두 하위 노드의 해시 값을 가지고있습니다. Grin은 전체적으로 Blake2b 해시 함수를 사용하고 충돌을 피하기 위해 해싱하기 전에 항상 노드의 위치를 ​​MMR에 추가합니다. 따라서 데이터 D를 저장하는 인덱스 ​n 에 리프노드 l이 있는 경우엔 (예를 들자면 출력의 경우 해당 데이터는 Pedersen commitment 입니다), 다음과 같이 표시됩니다.

Node(l) = Blake2b(n | D)

인덱스 m에서 어떤 부모 p라면 다음과 같습니다.

Node(p) = Blake2b(m | Node(left_child(p)) | Node(right_child(p)))

Merkle 트리와는 달리 MMR은 일반적으로 하나의 root를 구성하지 않으므로 계산할 방법이 필요합니다. 그렇지 않으면 해시 트리를 사용하는 목적이 무의미 합니다. 이 과정은 [1]에서 설명한 이유 때문에 "bagging the peaks" 라고 합니다.

먼저 MMR의 최고 높이를 확인합니다. (여기서 확인 할 수 있는 한 가지 방법을 정의 할 것입니다.) 일단 다른 작은 예제 MMR을 보여드리겠습니다. 인덱스는 1부터 시작하고 10 진수가 아닌 2 진수로 작성됩니다.

Height

2        111
       /     \
1     11     110       1010
     /  \    / \      /    \
0   1   10 100 101  1000  1001  1011

이 MMR에는 11 개의 노드가 있으며 그 피크는 111(7), 1010(10) 및 1011(11) 입니다. 먼저 이진법으로 표현 될 때 가장 왼쪽 첫번째 피크가 항상 가장 (위치가) 높고 항상 "모두 1"이 되는 것에 주목하세요. 그럼 이 피크는 2^n - 1 형태의 위치를 ​​가질 것이고 항상 MMR 내부에있는 가장 높은 위치 (그 위치는 전체 크기보다 작습니다)입니다. 사이즈 11의 MMR에 대해서도 반복적으로 처리합니다.

2^0 - 1 = 0, and 0 < 11
2^1 - 1 = 1, and 1 < 11
2^2 - 1 = 3, and 3 < 11
2^3 - 1 = 7, and 7 < 11
2^4 - 1 = 15, and 15 is not < 11

Finally, once all the positions of the peaks are known, "bagging" the peaks consists of hashing them iteratively from the right, using the total size of the MMR as prefix. For a MMR of size N with 3 peaks p1, p2 and p3 we get the final top peak:

따라서 첫 번째 피크는 7입니다. 다음 피크를 찾으려면 오른쪽 형제에게 "점프" 해야 합니다. 해당 노드가 MMR에 없다면 왼쪽 하위 노드를 가져옵니다. 만약 그 하위노드도 MMR에 없으면, MMR에 있는 노드를 가져올 때까지 왼쪽에 있는 하위 노드를 계속 가져옵니다. 다음 피크를 찾으면 마지막 노드에 도달 할 때까지 프로세스를 반복합니다.

이 모든 오퍼레이션은 매우 간단합니다. 높이 h에 있는 노드의 오른쪽 형제로 점프하는 것은 2^(h + 1)-1만큼을 높이 h에 추가하는 것입니다. 왼쪽 형제를 가져 가면 2^h만큼 값을 뺍니다.

마지막으로 피크의 모든 위치를 알게되면 피크들을 "bagging"하는 것은 MMR의 전체 크기를 prefix로 사용해서 반복적으로 오른쪽에서부터 해싱하는 것으로 구성됩니다. 3 개의 피크 p1, p2 및 p3을 갖는 크기 N의 MMR에 대해, 다음과 같은 최종 최고 피크를 얻습니다. :

P = Blake2b(N | Blake2b(N | Node(p3) | Node(p2)) | Node(p1))

Pruning

Grin에서는 해시되고 MMR에 저장되는 많은 데이터가 결국 제거 될 수 있습니다. 이런 일이 발생하면 해당 MMR안의 일부 리프 해시가 있는지 여부가 불필요하고 리프의 해시를 제거 될 수 있습니다. 충분한 리프가 제거되면 부모의 존재도 불필요하게 될 수 있습니다. 따라서 우리는 그 리프들의 삭제로 인해 MMR의 상당 부분을 pruning 할 수 있습니다.

MMR의 pruning은 간단한 반복 프로세스에 의존합니다. X는 우선 첫번째 제거할 리프로 초기화됩니다.

1. X를 Pruning 한다.
2. 만약 x가 형제 노드가 있다면 여기서 prunging을 중단한다.
3. 만약 X가 형제 노드가 없다면 X의 부모 노드는 X라고 배정된다.

결과를 시각화하기 위해 첫 번째 MMR 예시에서 시작하여 리프[0, 3, 4, 8, 16]을 제거하면 다음과 같은 pruning MMR이 발생합니다.

Height

3             14
            /    \
           /      \
          /        \
         /          \
2       6            13
       /            /   \
1     2            9     12     17
       \          /     /  \   /
0       1        7     10  11 15     18

[1] Peter Todd, merkle-mountain-range

[2] Wikipedia, Merkle Tree