머클 트리: 블록체인은 어떻게 모든 노트를 기억하는가?

원문 출처: Annkkitaaa

수백만 개의 커밋먼트를 하나의 작은 지문으로 요약

시리즈: Zcash의 근본 원칙부터 . 제4편. 머클 트리 대상 독자: 초보자. 제3편 (해싱과 커밋먼트)에 기반하여 작성되었습니다. 지문과 커밋먼트가 무엇인지 아시는 분은 준비가 되셨습니다. 학습 후 습득 내용: 머클 트리에 대한 직관적이고 정확한 그림, 특정 항목을 드러내지 않고 멤버십을 증명하는 방법, 그리고 이것이 Zcash의 노트 커밋먼트 트리가 되는 방식.

제0편에서는 모든 노트를 저장하고 오직 성장만 하는 "공개 게시판"에 대해 설명했습니다. 이제 이 게시판에 고정된 것이 무엇인지 예측할 수 있을 것입니다: 커밋먼트(제3편), 즉 봉투입니다. 하지만 실제 게시판에는 수백만 개의 항목이 존재합니다. 네트워크는 이를 어떻게 저장하고 확인하며, 당신의 봉투가 게시판에 있는 것을 드러내지 않고 증명할 수 있을까요? 이 질문에 대한 답은 컴퓨터 과학에서 가장 우아한 구조 중 하나인 머클 트리(Merkle Tree)입니다.

1. 왜 당신이 관심을 가져야 할까요?

커밋먼트의 거대한 공개 목록이 존재하는 순간 두 가지 문제가 발생합니다.

문제 하나: 대규모에서의 무결성. 목록에 3억 개의 항목이 있다면, 어떻게 아무도 하나도 비밀리에 수정되지 않았는지 확인할 수 있을까요? 매번 모든 항목을 재확인하는 것은 불가능합니다.

문제 두 번째: 개인적인 멤버십. 노트를 사용하려면(제0편), 당신의 커밋먼트가 실제로 게시판에 있는 것을 증명해야 합니다. 하지만 만약 당신이 그것을 가리키며 말한다면("4,201,337번 항목입니다!"), 당신은 익명성을 상실하게 됩니다. 당신은 *"내 봉투는 이 게시판의 어딘가에 있습니다"*라고 증명해야 하되, 어떤 것인지 드러내지 않아야 합니다.

머클 트리는 두 문제를 동시에 해결합니다. 전체 목록을 하나의 지문으로 압축하고, 위치를 숨기는 작은 증명으로 멤버십을 증명할 수 있게 해줍니다.

2. 직관: 지문들의 토너먼트

플레이어들이 진출하는 타이거리그 대회 브래킷을 상상해보세요, 하지만 지문들이 결합됩니다.

• 가장 아래에는 각각의 데이터가 자신의 지문(제3편에서 언급한 해시)을 가집니다. 이들은 잎(leaf)입니다.
• 쌍으로 묶습니다. 각 쌍의 두 지문은 함께 해싱되어 하나의 부모 지문이 됩니다.
• 부모들을 다시 쌍으로 묶고, 그 쌍을 해싱하여 계속 올라갑니다.
• 계속해서 진행하다 보면 하나의 지문만이 최상단에 남게 되며, 이 우승자는 머클 루트(Merkle root)입니다.

avalanche effect(제3편)에서 직접적으로 따르는 가장 중요한 특성은 다음과 같습니다:

루트는 아래 모든 것의 지문입니다. 어떤 잎도 하나의 비트만 바꾸어도 그 지문이 변하고, 이로 인해 부모가 변화하고, 그 부모 역시 계속해서 위로 올라가며 루트가 변경됩니다. 따라서 하나의 작은 루트 값은 전체 목록의 무결성을 보증합니다. 이것이 문제 하나를 해결합니다.

3. 실제 트리: 정확하게 계산된 예제

이제 A, B, C, D라는 잎(leaf)을 사용하여 위에서 언급한 네 잎 트리를 실제로 SHA-256 지문으로 만들어보겠습니다 (해시는 가독성을 위해 일부 생략했습니다):

hA = 559aead08264...     hB = df7e70e50215...
hC = 6b23c0d5f35d...     hD = 3f39d5c348e5...

hAB = H(hA , hB) = 63956f0ce48e...
hCD = H(hC , hD) = 98a2fbfddbc7...

ROOT = H(hAB , hCD) = 1b3faa3fcc5e...

모든 것은 "어떤 것을 해싱하고, 그 다음 해시 쌍을 해싱한다"는 것입니다. 제3편에서 언급한 것보다 더 복잡하지 않으며, 트리 구조로 배열된 것이 전부입니다.

4. 재미있는 부분: 위치를 드러내지 않고 멤버십을 증명하는 방법

이제 문제 두 번째입니다. 당신은 루트만 알고 있는 누군가에게 잎 C가 트리에 포함되어 있음을 증명하고 싶습니다. 하지만 당신은 전체 트리를 제공하지 않습니다. 대신, C에서 루트까지 올라가는 데 필요한 지문들, 즉 인증 경로(authentication path) 또는 머클 증명(Merkle proof)만 제공합니다:

C가 트리에 포함되어 있음을 증명하려면:

• 그 형제 노드 hD, 그리고
• 그 삼촌 노드 hAB를 제공해야 합니다.

검증자는 루트만 알고 있고, 이 경로를 따라 다시 계산합니다:

step 1:  H(hC , hD)        = hCD       (C와 형제 노드 결합)
step 2:  H(hAB , hCD)      = ROOT?     (삼촌 노드와 결합)

실제로 계산하면 1b3faa3fcc5e...가 나오며, 이는 루트와 일치합니다. 따라서 잎이 트리에 포함되어 있음을 증명할 수 있습니다.

두 가지 요소가 이 기능을 강력하게 만듭니다:

• 크기가 작다. 4개의 잎에 대해 2개의 해시를 제공했습니다. n개의 잎이 있는 트리라면 약 log_2(n) 개의 해시만 제공하면 됩니다. 수십억 개의 잎이라면 대략 30개의 해시만 필요합니다, 수십억 개가 아닙니다. 트리가 커질수록 증명은 거의 성장하지 않습니다.
• 프라이버시의 씨앗이다. 이 증명은 당신의 잎이 어딘가에 포함되어 있음을 보여줍니다. 이 동일한 검증이 제로 지식 증명(zero-knowledge proof, 제5편) 내부에서 수행될 때, 경로 자체도 숨겨지므로 "내 노트는 트리에 있습니다"라고 증명하면서 노트나 위치를 드러내지 않게 됩니다. 이는 문제 두 번째를 완전히 해결합니다.

5. 머클 트리에서 Zcash의 노트 커밋먼트 트리로

이제 제0편의 "공개 게시판"이 실제로 무엇인지 정확하게 설명할 수 있습니다:

노트 커밋먼트 트리(note commitment tree)는 잎들이 노트 커밋먼트인 머클 트리입니다. 세계 어디서든 노트가 생성될 때마다, 그 커밋먼트는 다음 잎으로 추가되고 루트는 업데이트됩니다.

실제 구체적인 사항들:

• 오직 성장만 한다. 잎들은 추가되지만 제거되지 않습니다. 이는 점진적 머클 트리(incremental Merkle tree)라고 불립니다. (이것은 제0편의 "게시판은 아무 것도 삭제하지 않는다"와 일치합니다.)
• 루트는 앵커(anchor)라고 불린다. 당신이 노트를 사용할 때, 거래는 최근 앵커를 참조하고, 제로 지식으로 해당 루트에 해당하는 노트의 커밋먼트가 트리에 포함되어 있음을 증명한다.
• 고정된 깊이. Zcash의 보호된 트리는 깊이 32이며, 이는 최대 2^(32) (40억 이상) 개의 노트를 저장할 수 있다.
• 제로 지식에 친화적인 해싱. 트리가 SHA-256으로 만들어지지는 않습니다. Sapling은 Pedersen 해시(Article 3에서 언급됨)로 트리를 해싱하고, Orchard는 Sinsemilla(동일하게 Article 3에서 언급됨)를 사용합니다. 이는 회로 내부에서 멤버십 증명이 저렴해지도록 하기 위함입니다.

트리가 처리하지 않는 한 가지: 중복 지출

트리는 노트가 존재함을 증명합니다. 하지만, 이 자체로는 동일한 노트를 두 번 사용하는 것을 막지는 않습니다. 이 작업은 제0편에서 언급된 널리파이어 집합(nullifier set)에 달려 있습니다: "사라진 토큰"의 별도 모음입니다. 당신이 노트를 사용할 때, 그 노트의 널리파이어를 공개하고, 네트워크는 이전에 본 적 있는 널리파이어를 거부합니다.

따라서 두 개의 공개 구조는 보완적인 역할을 하며, 그들을 분리하는 것이 노트의 생성과 소멸 사이의 연관성을 끊는 것입니다:

6. 정직한 고백

단순화된 설명입니다. 실제 점진적 머클 트리는 "프론티어" 노드를 추적하여 루트가 모든 것을 재구성하지 않고 업데이트할 수 있도록 합니다; 네트워크는 최신 앵커뿐만 아니라 최근 앵커의 윈도우를 유지하여, 모든 새 블록이 지갑을 손상시키지 않도록 합니다; 그리고 비어 있는 잎은 정의된 패딩 값으로 채웁니다. 또한 우리는 2의 제곱 수로 깔끔하게 나뉜 이진 트리를 그렸습니다. 하지만 이는 직관에 영향을 주지 않습니다: 커밋먼트 잎들이 쌍으로 해싱되어 하나의 루트로 올라가며, 짧은 멤버십 증명이 제공됩니다. 정확한 회계는 프로토콜 기사에서 다시 다룹니다.

7. 요약

• 머클 트리(Merkle tree)는 데이터를 잎(leaf)으로 해싱하고, 그 다음은 쌍을 위로 해싱하여 결국 하나의 루트(root)만 남게 합니다.
• 악마 효과 덕분에 루트는 전체 목록의 지문입니다: 하나의 잎만 바꾸어도 루트가 변경됩니다. 하나의 작은 값이 대규모 데이터셋을 인증합니다.
• 멤버십 증명(authentication path)은 단지 루트로 올라가는 과정에서 필요한 형제 해시들, 약 log_2(n) 개의 해시이며, 이는 수십억 개의 잎에도 불구하고 증명이 작게 유지됩니다.
• 제로 지식 증명(zero-knowledge proof) 내부에서 수행될 경우, 멤버십 검증은 당신이 어떤 잎을 의미하는지 숨기며, "내 노트는 트리에 있습니다"라고 증명하면서 노트나 위치를 드러내지 않습니다.
• Zcash의 노트 커밋먼트 트리(note commitment tree)는 점진적(incremental) 머클 트리이며, 깊이 32, 루트는 앵커(anchor), Sapling은 Pedersen으로 해싱하고 Orchard는 Sinsemilla로 해싱합니다.
• 트리는 존재를 증명하며, 별도의 널리파이어 집합(nullifier set)은 중복 지출을 방지합니다. 이들을 분리하는 것이 노트의 생성과 소멸 사이의 연관성을 끊는 것입니다.

용어집

FAQ

왜 트리를 사용하지 않고 단순히 해시 목록만 사용하지 않나요? 평탄한 목록은 멤버십 증명을 위해 모든 항목을 드러내거나 처리해야 하므로, 트리는 로그 크기의 증명과 하나의 루트로 무결성을 보장합니다.

검증자가 전체 트리를 필요로 하나요? 아니요. 검증자는 루트와 짧은 인증 경로만 필요합니다. 이것이 바로 목적입니다.

왜 깊이 32인가요? 이것은 약 40억 개의 노트를 저장할 수 있는 범위를 제한하면서, 멤버십 증명과 그 회로 내부 비용을 고정된 관리 가능한 크기로 유지하기 위함입니다.

루트가 새 노트마다 변경된다면, 이전 증명들은 어떻게 유효하게 유지되나요? 네트워크는 최근 앵커(루트)의 윈도우를 기억하므로, 약간 오래된 앵커에 대한 증명은 여전히 검증됩니다. 프로토콜 기사에서 이 내용을 정확히 설명합니다.

직관 테스트

우리의 4 잎 트리에서, 공격자가 비밀리에 잎 C를 다른 값으로 교체하지만 출판된 루트는 그대로 두었다고 가정해보세요. 이로 인해 어떤 문제가 발생할까요? 왜 그들은 조용히 이를 수정할 수 없을까요? (아래에 답이 있습니다.)

다음 단계

제5편 . 제로 지식 증명: 클라이맥스입니다. 지금까지 노트, 커밋먼트, 트리를 만들었으며, "제로 지식으로 증명한다"고 수차례 말했습니다. 제5편에서는 어떻게 당신이 진술이 참임을 증명하고, 노트가 트리에 포함되어 있음을, 널리파이어가 올바른지를, 자금이 균형 잡혀 있음을 증명할 수 있는지, 이를 드러내지 않고도 설명합니다.

ZecHub의 Zcash from First Principles 시리즈의 일부. CC BY-SA 4.0 라이선스.