해싱과 커밋먼트: 마법 같은 봉인된 편지

원문 출처: Annkkitaaa

공개된 장소에서 비밀을 잠그고 거짓말할 수 없게 만드는 방법

시리즈: Zcash의 기본 원리부터 시작하기 . 제3장. 해싱과 커밋먼트 대상 독자: 초보자. 제1장 (유한체)와 제2장 (타원곡선)에 기반하지만, 직관은 그 자체로 이해 가능합니다. 학습 결과: 해시 함수의 개념을 명확히 이해하게 되고, "숨김"과 "결합성"이 실제로 무엇인지 알게 되며, Zcash가 모든 비공개 결제를 고정하는 노트 커밋먼트를 어떻게 구축하는지 배우게 됩니다.

제0장에서는 "마법 같은 봉인된 편지"에 대해 설명했습니다. 이는 공개된 게시판에 붙일 수 있는 것으로, 편지가 존재함을 증명하면서도 내용은 숨길 수 있고, 이후 언제든지 교체할 수 없습니다. 우리는 그러한 것이 가능하다고 약속했으며, 지금이 그 설명입니다. 이를 위해 두 가지 재료가 필요합니다: 해시 함수와 커밋먼트.

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

선거 결과를 예측하고 이후에 그 예측이 정확했다는 것을 증명하고 싶다고 상상해보세요. 단순히 예측을 발표할 수는 없습니다(사람들의 행동에 영향을 줄 수도 있고, 변경했다고 비난받을 수도 있기 때문). 그리고 완전히 비밀로 유지할 수도 없습니다(그렇게 하면 이후 증명이 불가능해지기 때문).

당신이 원하는 것은 현재 공개적으로 값을 잠글 수 있는 방법입니다. 이는 다음과 같은 조건을 충족해야 합니다:

• 아무도 당신이 잠근 값이 무엇인지 알 수 없고(일시적으로 비밀로 유지됨),
• 이후에 이를 드러낼 때, 거짓말할 수 없습니다.

이 "현재 잠금, 나중에 드러내기, 거짓말 불가" 기능은 커밋먼트(commitment)라고 불리며 Zcash 전반에 걸쳐 사용됩니다. 노트의 가치와 소유자는 노트가 생성되는 순간 커밋먼트로 잠겨집니다. 커밋먼트를 만들기 위해 먼저 해시 함수라는 주요 도구가 필요합니다.

2. 직관: 데이터의 지문

해시 함수(hash function)는 어떤 데이터든, 단일 문자나 전체 라이브러리까지도 짧고 고정된 크기의 문자열인 소화물(digest) 또는 해시(hash)로 압축합니다. 이는 데이터의 지문으로 생각할 수 있습니다.

좋은 암호학적 지문은 네 가지 특성을 가지고 있습니다. 방정식이 아닌 직관으로 기억하세요:

또 하나의 특징은 지문이 마치 마법처럼 느껴질 만큼 강력합니다:

악수 효과(verified)

입력을 가장 작은 양만큼 변경하면 지문이 완전히 달라지며, 이전 지문과 전혀 유사하지 않습니다. 한 문자만 다른 두 개의 SHA-256 지문을 보세요:

H("Pay Bob 5 ZEC") = 6e2dc1a954c70cc865f18ea8cb70b7b56eeaf6ca42b380824a55d65dc342f34b
H("Pay Bob 6 ZEC") = 76abc346d8d3053f76a9ae18b617af71f02729a73ec6a51732d2d94934e4217f

64개의 16진수 자릿수 중 59개가 다릅니다. 입력에 하나의 문자만 변경해도 지문이 완전히 달라집니다. 이는 입력을 특정한 지문으로 유도할 수 없다는 이유입니다: "더 따뜻함/차갑음" 같은 신호가 없기 때문입니다.

3. 지문에서 커밋먼트로

다음은 유혹적이지만 결점이 있는 아이디어입니다: 비밀 값 v에 커밋하려면 그 값의 지문 H(v)만 공개하면 됩니다.

이 방법은 결합성(binding) 측면에서는 잘 작동합니다(다른 v를 주장할 수 없음, 충돌이 필요하기 때문). 그러나 숨김(hiding)에는 실패합니다. 가능한 값의 집합이 작다면 공격자는 모든 후보 지문을 계산하고 비교할 수 있습니다. "예" 또는 "아니요"에 커밋하려면 두 값을 해싱해도 즉시 어떤 선택을 했는지 알게 됩니다. 결정성, 이전 직관에서 친구였던 것이 이제 비밀을 유출하게 됩니다.

해결책은 단 한 가지 단어입니다: 난수(randomness).

커밋먼트는 당신의 값과 새로운 난수를 섞은 지문입니다: commitment = H(v, r) 여기서 r은 비밀로 유지되는 난수 "블라인딩" 값입니다.

이제 동일한 v가 매번 다른 r을 사용하기 때문에 커밋먼트도 달라집니다. 우리가 원했던 두 가지 속성이 이제 모두 충족됩니다:

커밋먼트를 열기(드러내기)하려면 v와 r을 공개하면 됩니다. 누구나 다시 H(v, r)을 계산하고 일치하는지 확인할 수 있습니다. 당신은 이제 잠겨 있습니다. 이것이 제0장에서 언급한 마법 같은 봉인된 편지입니다.

영원히 기억해야 할 두 가지: 결합성은 해시가 충돌 방지 특성을 가졌기 때문에, 숨김은 난수 r 덕분에 가능합니다.

4. 봉인된 편지를 만드는 두 가지 방법

두 가지 일반적인 방법이 있으며 Zcash에서는 모두 사용됩니다.

마지막 행이 Zcash에서 페데런 커밋먼트가 중요한 이유입니다. commit(v_1) + commit(v_2)는 commit(v_1 + v_2)와 동일하기 때문에, 프로토콜은 커밋먼트를 더함으로써 들어온 돈이 나간 돈과 같음을 증명할 수 있습니다. 단 하나의 금액도 드러내지 않고요. 이 사실은 제6장에서 다룹니다.

5. Zcash에 영향을 주는 세부 사항: ZK-친화적 해싱

대부분의 소개 자료가 놓치는 중요한 통찰이 있습니다. 바로 "수학과 공학이 만나는 지점"입니다.

SHA-256은 일상적인 컴퓨팅에 탁월한 지문입니다. 그러나 Zcash는 단순히 해시를 계산하는 것만이 아니라, 제로 지식 증명 내에서 해시가 올바르게 계산되었음을 증명해야 합니다(제5장에서 설명). 여기서 문제가 생깁니다: 제로 지식 증명은 유한체 산술(Article 1)의 언어에서 작동하지만, SHA-256은 비트 조작 연산(이동, AND, XOR 등)으로 구성되어 있습니다. 이러한 모든 비트 조작을 유한체 산술로 표현하는 것은 매우 비용이 많이 들며, 증명이 커지고 느려집니다.

그래서 Zcash 암호학자들은 내부가 이미 유한체 산술로 되어 있는 해시 함수를 설계하고 사용했습니다. 이는 증명이 저렴하게 가능하도록 합니다:

이 하나의 공학적 요구사항, "증명이 비용 효율적이어야 한다", 때문에 Zcash는 SHA-256 대신 특별한 해시 함수를 발명하고 채택했습니다.

6. Zcash에서 이 기능은 어디에 사용되나요?

Zcash는 설계에 따라 다른 해시를 사용해왔으며, 각각의 목적에 맞게 선택되었습니다:

인식해야 할 이름은 페데런(commitment-style 해시, 곡선 점으로 구성되어 있으므로 "더해짐" 기능을 가지며 증명이 저렴함)과 Sinsemilla, 그리고 Poseidon(제로 지식 회로를 위해 설계된 유한체 산술 해시). 제0장에서 노트의 내용이 커밋먼트에 봉인되었다고 했을 때, 이 기능이 그 봉인을 담당하고 있습니다.

그래서 제0장에서 언급했던 열린 문제, "봉인된 편지가 내용을 숨길 수 있으면서도 위조 불가능한 이유는 무엇인가?", 이제 해결되었습니다: 난수 r으로부터의 숨김, 충돌 방지 또는 곡선 트랩도어로부터의 결합성.

7. 정직한 경고

이해를 위해 일부 단순화했습니다. 실제 커밋먼트 체계는 v와 r이 어떻게 인코딩되는지, 어떤 생성자가 사용되는지를 명확히 지정합니다; "숨김"과 "결합성"은 각각 완벽한 것과 계산 가능한 것으로 구분되며 정확한 보안 정의가 따릅니다; 또한 페데런, Sinsemilla, Poseidon의 내부 구조는 보여주지 않았습니다. 이 모든 것이 직관을 바꾸지는 않습니다: 커밋먼트는 지문에 난수를 더해 현재는 숨기고 영원히 결합합니다. 세부 사항은 필요할 때 프로토콜 기사에서 다시 다룹니다.

8. 요약

• 해시 함수는 데이터의 지문(digest)으로, 결정적, 빠른 전진, 단방향성, 충돌 방지, 악수 효과(입력의 한 비트 변경으로 지문이 완전히 달라짐)를 갖습니다.
• 커밋먼트는 당신이 현재 공개적으로 값을 잠글 수 있고 나중에 드러낼 때 거짓말할 수 없도록 합니다.
• H(v)만 공개하면 결합성은 있지만 숨김은 없습니다. 난수 r을 더한 H(v, r)으로 해결합니다: r으로부터의 숨김, 충돌 방지로부터의 결합성.
• Zcash는 해시 기반과 페데런 커밋먼트 모두 사용하며, 페데런 커밋먼트는 더해짐(homomorphic)이 가능하여 제6장에서 가치 균형을 비공개로 증명하는 데 활용됩니다.
• 해시가 제로 지식 증명 내부에서 증명되어야 하기 때문에, Zcash는 SHA-256 대신 ZK-친화적(field arithmetic 기반) 해시(페데런, Sinsemilla, Poseidon)를 사용합니다.

용어집

FAQ

값을 암호화하는 대신 커밋먼트를 사용하지 않는 이유는 무엇인가요? 암호화는 나중에 복호화 가능한 비밀을 다룹니다. 커밋먼트는 결합성: 나중에 답을 바꿀 수 없다는 보장입니다. 다른 목적입니다.

커밋먼트가 값의 내용을 숨기면 어떻게 규칙을 확인하나요? 이것은 제로 지식 증명(Article 5)의 역할입니다: 숨겨진 값을 드러내지 않고도 규칙을 준수함을 증명합니다.

SHA-256이 깨졌기 때문에 Zcash가 일부 장소에서 사용하지 않는 건가요? 아니요. SHA-256은 여전히 잘 작동하며, Zcash는 여전히 사용합니다. 다만 회로 내부에서 증명하는 것이 비용이 많이 들기 때문에, 특정 목적에 맞게 ZK-친화적 해시가 존재합니다.

난수 r은 어디서 오고 누가 보관하나요? 노트가 생성될 때 새로 생성되고 노트의 소유자에게 알려져 있습니다. 이는 각 노트가 고유하고 비공개하게 되는 이유입니다.

직관 테스트

당신은 선거 예측을 H(v, r)으로 커밋하고 공개합니다. 친구는 단순히 H(v)만 공개하는 것이 더 간단하다고 주장합니다. 두 가지 가능한 결과가 있을 때, 왜 이 아이디어가 나쁜 것인가요? (아래에 답이 있습니다.)

다음으로 읽을 내용

제4장 . 먀클 트리: 지금까지 수백만 개의 커밋먼트가 쌓였습니다. 제4장에서는 Zcash가 이를 하나의 트리로 정리하고, 그 트리의 작은 루트 지문이 전체 역사 대신 사용되며, 노트가 해당 트리에 포함되어 있음을 증명할 수 있으면서도 어떤 노트인지 드러내지 않는 방법을 보여줍니다. 이것이 바로 제0장에서 언급한 "공개 게시판"의 실제 모습입니다.

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