MMR(merkle mountain ranges)

MMR에 대해 언급한 글들(읽어보기)

Merkle Mountain Ranges

MimbleWimble grin과 beam은 MMR을 transaction accumulator 로 사용한다.

Merkle tree와의 비교

MMR는 완벽하게 균형잡힌 이진 트리, root가 하나가 아님

merkle tree 는 완벽하게 균형잡힌 binary 트리거나, 오른쪽 상단에서 잘린(더 짧은) single binary 트리

위쪽은 배열의 인덱스, 아래쪽은 height 을 나타냄

11개의 leaf와 총 19개 range → 19크기의 배열로 표현가능

빠른 binary operation을 사용하기 때문에 MMR 내에서 탐색하는 것도 매우 간단합니다.

노드의 위치가 n이라면 이 MMR의 높이, 부모의 위치, 형제 등을 계산할 수 있습니다.

*Blacke2b는 grin에서 사용하는 해시함수

grin은 충돌을 피하기 위해 해싱하기 전에 항상 노드의 위치를 MMR에 추가함

데이터 D를 저장하는 인덱스 n 에 리프노드 l이 있는 경우 :

Node(l) = Blake2b(n | D)

→ 위의 MMR에서 리프노드 I가 데이터 D를 저장하고, 인덱스 3에 위치한다면,

Node(I) = Blake2b(3| D)

인덱스 m에서 어떤 부모노드 p :

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

→ 부모노드 p가 인덱스 5에 위치한다면,

Node(p) = Blake2b(5 | Node(left_child(p)) | Node(right_child(p))),

Node(left_child(p)) = Blake2b(3 | Dl),

Node(left_child(p)) = Blake2b(4 | Dr)

(Dl: left_child(p)의 저장 데이터, Dr: right_child(p)의 저장 데이터)

Bagging the peaks(final top peak구하기)


Height

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

하나의 MMR이다.

인덱스가 이진수로 표현, 1부터 시작

가장 왼쪽 첫번째 피크가 항상 가장 (위치가) 높고 인덱스의 자리값이 항상 "모두 1"이 되는 것에 주목

→ 여기서 111, 11, 1

이 피크는 2^n - 1 형태의 위치.(n:높이)

→ 111= 7(2^3-1) 의 위치를 가짐, 11은 3, 1은 1

항상 MMR 내부에있는 가장 높은 위치가 된다.

→ 현재 111라는 위치를 가진 노드는 트리에 다른 노드가 추가되거나 제거되어도, 1111이나 11 등에 위치할것이다.?

또한 그 위치는 전체 크기보다 작다.

→ 7(111) < 11(전체크기)

MMR의 최고 높이를 확인하기위해

가장 왼쪽 첫번째 피크(111, 11, 1)에 대해 다음과같이 처리함


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(=111), and 7 < 11
2^4 - 1 = 15, and 15 is not < 11

따라서 최고높이는 3

높이 1,2,3인 각 peak이 있을것이므로

따라서 크기 11인 MMR은 3개의 peak을 가짐

p1,p2,p3일때

p1=7입니다. 다음 피크를 찾으려면 오른쪽 형제에게 "점프" 해야 합니다.

(아마, 그 다음 피크는 현재피크의 높이-1 에 있으므로 이렇게 하는듯)

해당 노드가 MMR에 없다면 왼쪽 하위 노드를 가져옵니다.

(첫번째 MMR예제에서 인덱스14노드는 오른쪽 형제를 갖고있지않아 대신 인덱스13에게)

만약 그 하위노드도 MMR에 없으면, MMR에 있는 노드를 가져올 때까지 왼쪽에 있는 하위 노드를 계속 가져옵니다.

다음 피크를 찾으면 마지막 노드에 도달 할 때까지 프로세스를 반복합니다.

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

→ p1의 높이는 3이므로 오른쪽형제에게 가기위해서 2^(3+1)-1 = 15 개 를 추가?

왼쪽 sibling은 2^3 =8개 뺌? (다시확인)

모든 peak을 알게되면 오른쪽에 있는 peak부터

차례로 해싱, final top peak(P)얻게됨

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

Pruning-mimblewimble

충분한 리프가 제거되면 부모의 존재도 불필요하게 될 수 있습니다. 따라서 우리는 그 리프들의 삭제로 인해 MMR의 상당 부분을 pruning 할 수 있습니다.

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

X를 Pruning 한다.

만약 x가 형제 노드가 있다면 여기서 pruning을 중단한다.

If x have not sibling, X=parent(X)

(만약 X가 형제 노드가 없다면 X의 부모 노드는 X라고 배정된다.)


Height

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

첫 번째 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

0제거: 0은 형제노드1이 있어 0만 프루닝후 중단

3,4제거+5제거: 3은 형제노드4가 있으나 3만 프루닝 후 중단. 4도 프루닝 대상이므로 프루닝 했더니, 둘의 부모노드였던 5는 더이상 리프노드가 없으므로 5도 제거.

8제거: 8은 형제노드7이 있어 8만 프루닝후 중단

16제거: 16은 형제노드15가 있어 16만 프루닝후 중단

다음은 노드가 점차 추가될때를 나타냄

각 값은 높이를 의미(0부터)


0
00
001 <- indexes 0 and 1 are hashed to form index 2
0010
0010012 <- another tree, which leads to the two subtrees being merged (height 2)
00100120
0010012001 <- now we have two trees, one of height 2, one of height 1

마지막 0010012001은

다음과 같은 MMR이다


 /\
/\/\/\

log2(n)

현재 이더리움은 Patricia-Merkle trie accumulator를 사용한다. 상태 이외의 정보는 transaction에서 읽을 수 없기 때문에 중요하게 생각하지 않았다. 그러나 stateless client model에서는 history (receipt 같은 읽기전용 혹은 contract code) 전용 accumulator를 더한 dual accumulator VM 방식이 유용할 수 있다. transaction sender가 off-chain 계산하여 history를 보내주기 때문에 history 접근이 상태 보다 쉬워진다. 그래서 contract가 storage 대신 history를 많이 사용하도록 유도할 수 있다. history-driven application은 SNARK(STARK)나 TrueBit을 사용하여 history의 해시 혹은 임시 상태만 storage에 저장하는 식으로 구현할 수 있다.

https://github.com/mimblewimble/grin/blob/master/doc/mmr_KR.md

https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md

MMR에 대해 언급한 글들(읽어보기)

Fly client, MMR

https://medium.com/blockchain-research-newsletter/blockchain-research-newsletter-3-nipopow-and-flyclient-ac202f7624a7

https://scalingbitcoin.org/transcript/stanford2017/flyclient-super-light-clients-for-cryptocurrencies

https://ethresear.ch/t/batching-and-cyclic-partitioning-of-logs/536

https://ethresear.ch/t/history-state-and-asynchronous-accumulators-in-the-stateless-model/287/2

https://gist.github.com/maczniak/a3f9884e8beaa38c343ea4379f378324

https://petertodd.org/2016/delayed-txo-commitments#txo-mmr-implementation-details

https://medium.com/@jimpo/next-generation-light-clients-block-commitments-e532ba3dfaa