희소 머클 트리 다중 값 증명이란 무엇입니까?

以太坊爱好者

特邀专栏作者

2020-03-11 10:00 (UTC+8)

이 기사는 약 2352자로, 전체를 읽는 데 약 4분이 소요됩니다

이 글은 동일한 머클 트리에 여러 값이 존재함을 증명할 수 있는 방법을 설명합니다.

AI 요약

이 글은 동일한 머클 트리에 여러 값이 존재함을 증명할 수 있는 방법을 설명합니다.

편집자 주: 이 기사의 출처:이더리움 애호가(ID: ethfans)편집자 주: 이 기사의 출처:

이더리움 애호가(ID: ethfans)

, 저자: Jim McDonald, 번역 및 교정: Pei Qi & A Jian, Odai의 승인을 받아 재인쇄됨.

첫 번째 레벨 제목

대중 과학 | 메르켈 잘림이란 무엇입니까

Sparse Merkle multiproofs(Sparse Merkle multiproofs)는 Merkle tree truncation(Merkle pollard)의 대안으로, Merkle 트리에 여러 값의 존재를 증명할 수 있는 공간을 제공할 수 있어 비용 절감의 증거입니다. Merkle proof와 Merkle tree truncated가 무엇인지는 이전 글에서 설명하였으니, 이 글을 읽기 전에 이러한 개념을 읽고 이해하는 것이 좋습니다. 다음으로 텍스트는 아래 그림의 Merkle 트리를 사용하여 다중 값 증명을 설명합니다.

이미지 설명

스파스 다중 값 증명은 Vitalik Buterin이 처음 제안했습니다.

다중 값 증명

이미지 설명

-그림 2, 3, 4: 각각 Banana, Peach, Kumquat에 해당하는 Merkel 증명-

위의 그림에서 알 수 있듯이 3개의 증명에는 중간 분기(즉, 녹색으로 표시된 부분)의 총 9개의 해시 값이 포함되어 있습니다. 각 증명에는 3개의 해시 값이 있습니다. 이 세 가지 증명을 아래 그림에 표시된 구조로 결합하면 다중 값 증명이 됩니다.

이미지 설명

-그림 5: Banana, Peach 및 Kumquat에 해당하는 Merkle 다중 값 증명-

희소 다중값 증명

Merkle 트리의 다중 값 증명은 일부 저장 공간을 절약하지만 일부 데이터는 다른 방법으로 얻을 수 있으므로 이러한 데이터를 제거하면 저장 공간을 추가로 절약할 수 있습니다. (번역자 주: 다른 방법으로 얻을 수 있는 데이터는 필요할 때 얻을 수 있는 한 증명에 저장할 필요가 없습니다)

이미지 설명

-그림 6: Merkle 트리 다중 값 증명에서 제거할 수 있는 해시 값(노란색 표시 참조)-

이러한 해시 값을 제거한 후 다음 그림과 같이 Merkle 트리의 희소 다중 값 증명을 얻을 수 있습니다.

이미지 설명

-그림 7: 희소 머클 트리 다중 값 증명-

Sparse Merkle 다중 값 증명은 포함해야 하는 해시 수를 9에서 3으로 줄입니다. 희소한 다중값 증명은 동일한 증명에 대해 6개의 해시가 필요한 Merkle 잘린 증명보다 더 효율적입니다.
검증자가 희소 다중 값 증명을 얻은 후 해당 값이 머클 트리의 일부인지 확인하려면 다음 단계를 수행해야 합니다(머클 트리에서 왼쪽에서 오른쪽으로, 위에서부터 순서대로) 맨 아래):
(번역자 주: "값 해시"는 값을 해시 함수의 입력으로 사용하고 임의의 출력 문자열을 얻는다는 의미입니다.)
바나나를 해시하여 bc4f...8d3f를 얻습니다.
해시 피치는 59a0…421d를 얻습니다.
2aab를 얻기 위해 해시 금귤…6f791
bc4f...8d3f 및 59a0...421d를 해시하여 9c15...5dec을 얻습니다.
2aab…6f79 및 45cf…14d9를 해시하여 a6e4…87df를 얻습니다.

d596…66ef 및 9c15…5dec을 해시하여 c0b7…da30을 얻습니다.

e336…ed14 및 a6e4…87df를 해시하여 6ff9…8e3d를 얻습니다.

c0b7...da30 및 6ff9...8e3d를 해시하여 d576...ffd9를 얻습니다.

이때 최종 해시 값은 머클 트리의 루트 해시 값과 비교할 수 있는데, 두 값이 일치하면 모든 값이 머클 트리에 있는 것으로 판단된다.

다음 그림은 Merkle tree의 값과 증명의 수가 변경될 때 Merkle 증명을 저장할 때 Merkle tree truncated와 sparse multi-value proofs가 절약할 수 있는 저장 공간의 양을 비교한 것입니다.

Merkle 트리에서 입증된 값의 위치와 제거할 수 있는 중간 분기 해시의 수에 따라 절감액이 달라지기 때문에 다중 값 증명의 절감액은 근사치라는 점에 주목할 가치가 있습니다.
Sparse Multivalued Proofs와 Merkle Truncated 비교
위의 표에서 볼 수 있듯이 희소 다중 값 증명은 Merkle tree truncation보다 더 많은 저장 공간을 절약하는데 Merkle tree truncation을 사용하는 이유는 무엇입니까? 희소한 다중 값 증명은 Merkle tree truncated와 비교하여 몇 가지 다른 특성을 가지므로 주요 사항은 다음과 같습니다.
다중값 증명 방식에서는 모든 값에 대한 증명을 함께 생성하여 검증하고, truncated 방식에서는 각 값에 대한 증명을 별도로 생성하여 검증합니다. 및 관련 증명이 필요합니다. 다중 값 증명의 경우 여러 값을 확인하고 해당하는 여러 값의 증명을 꺼내야 함)
희소한 다중값 증명에는 증명을 생성하고 확인하기 위해 더 많은 메모리와 CPU 주기가 필요합니다.

희소한 다중값 증명은 병렬로 생성하고 확인하기 어렵습니다.