# 해시 함수

{% hint style="warning" %}
**목표 : 해시 함수의 사용 목적을 이해하고, 이를 활용하는 머클 트리(Merkle Tree)의 원리를 파악한다**
{% endhint %}

현대 zkp는 해시 함수 없이는 거의 성립하지 않는다. Fiat-Shamir 변환을 통해 상호작용형 프로토콜을 비상호작용형 zk-SNARK로 바꿀 때 챌린지 값을 만들어주는 핵심 도구가 해시 함수다. 또한, 대규모 상태를 다룰 때 머클 트리를 이용해서  "특정한 어떤 원소를 알고 있다"는 사실을 짧은 해시들만으로 증명한다.

이 글에서는 zkp에서 요구되는 해시 함수의 역할과 원리를 짚고 넘어간다.

### **해시 함수란?**

해시 함수는 ‘임의의 길이의 데이터’를 ‘고정된 길이의 데이터’로 매핑하는 함수이다. 즉, 데이터의 길이에 상관없이 항상 동일한 길이의 출력을 생성한다.

<figure><img src="/files/91sZqlJhFSKZeQpE8lWE" alt=""><figcaption><p>해시 함수의 특징</p></figcaption></figure>

#### **해시함수의 특성**

해시함수는 다음과 같은 특성을 가진다.

1. **Efficiency**

   해시함수는 주어진 입력에 대해서 효율적으로 hash 값을 계산해야 한다.
2. **Pre-image resistance**

   주어진 hash 값으로부터 원래의 입력 데이터를 알아내기 어려워야 한다.
3. **Second pre-image resistance**

   특정 입력 데이터가 주어질 때, 해당 입력 데이터의 hash 값과 동일한 hash 값을 갖는 다른 입력 데이터를 찾아내기 어려워야 한다.
4. **Collision-resistance**

   여기서 Collision(충돌)은 서로 다른 두 입력값(데이터) $$x$$와 $$x'$$가 동일한 해시 값을 생성하는 경우를 말한다$$(H(x) = H(x'))$$. 만약 어떤 해시 함수에서 Collision을 찾는 것이 계산적으로 거의 불가능하다면 Collision-resistance을 가진다 한다.

해시함수의 특성에서 Second Pre-image Resistance와 Collision-resistance가 비슷하다고 생각할 수 있다. 그 차이를 살펴보면 Second Pre-image Resistance는 특정 점 $$x$$가 주어져있고, 그 기준점과 같은 해시 값을 갖는 다른 $$x'$$를 찾기 어려운 특성이다. 반면, Collision-resistance는 기준점 없이, 해시 값이 같은 임의의 두 쌍 $$(x, x')$$을 찾기 어려운 특성이다.

#### **해시함수의 필요성**

해시 함수는 데이터의 **무결성(Integrity)**&#xC744; 검증하는 핵심 도구이다.

해시 함수는 입력 데이터에 아주 작은 변화만 있어도 해시 값이 크게 달라지는 **눈사태 효과(Avalanche Effect)**&#xAC00; 있다. 이 민감한 특성은 해시 함수에 Collision-resistance(충돌 저항성)과 Second Pre-image resistance(제2 역상 저항성)을 부여한다. 그 결과, 공격자가 원본 데이터를 위조하거나 변조하는 것이 사실상 불가능하게 된다.

따라서 파일이나 메시지를 배포하거나 전송할 때 원본 데이터의 해시 값을 함께 제공하면, 수신자는 해당 데이터가 전송 중에 변조되지 않았음을 확신할 수 있다.

#### **해시함수의 예시**

* MD5

  MD5는 1991년에 개발되었으며 128 bit의 해시 출력을 생성한다. 속도가 빨라 한때 널리 사용되었지만, 2004년에 충돌이 실제로 발견되어 현재는 데이터 무결성 검증 용도로는 더 이상 사용되지 않는다.
* SHA-1

  SHA-1은 1995년에 처음 소개되었으며 160 bit의 해시 출력을 가진다. MD5의 대안으로 사용되었으나, 시간이 지나면서 이론적인 보안 약점이 확인되었고 충돌 공격의 위험성이 커져 SHA-2로의 전환이 권고되었다.
* SHA-2

  SHA-2는 현재까지 약점이 발견되지 않은 안전한 해시 함수로 널리 사용되고 있다. 이 계열은 256 bit 또는 512 bit 등 다양한 길이의 출력을 제공하며, 기존 SHA-1과 유사한 Merkle–Damgård 구조를 기반으로 설계되었다.
* SHA-3

  SHA-3는 기존 SHA 계열과는 달리 근본적으로 다른 설계 방식인 스펀지 구조(Sponge Construction)를 사용하여 개발되었다. 이는 기존의 Merkle–Damgård 구조에 대한 잠재적 위협에 대비하기 위함이며, 224, 256, 384, 512 bit 등 여러 출력 길이를 지원한다.

#### **해시함수의 응용 : Merkle Tree**

그렇다면 검증해야 할 데이터가 수십, 수백만 개에 달하는 대규모 집합이라면 어떻게 해야 할까?

이러한 대규모 데이터 집합의 경우, 모든 개별 데이터의 해시 값을 일일이 비교하는 것은 매우 비효율적이다. 이러한 문제를 해결하고 대규모 데이터 집합의 무결성을 효율적으로 검증하기 위해, 해시 함수를 기반으로 하는 **머클 트리(Merkle Tree)**&#xB77C;는 자료구조가 활용된다.

<figure><img src="/files/NQMjeJhf8veIjJrBh3Vr" alt=""><figcaption><p>머클 트리 예시</p></figcaption></figure>

머클 트리는 해시 함수를 기반으로 계층적으로 구성된다. 주요 구성 요소는 다음과 같다.

* **리프 노드 (Leaf Nodes)**: 가장 하위 레벨에 위치한 노드들이다. 각 리프 노드는 원본 데이터 블록(또는 트랜잭션 등)의 개별 해시 값을 저장한다. 예를 들어, 여러 개의 트랜잭션이 있다면 각 트랜잭션의 해시 값이 하나의 리프 노드가 된다.
* **비-리프 노드 (Non-Leaf Nodes)**: 리프 노드 위에 있는 중간 노드들이다. 각 비-리프 노드는 자신이 가진 자식 노드들의 해시 값을 합쳐서 다시 해시(Concatenation & Hashing)한 결과를 저장한다. 예를 들어, 두 자식 노드의 해시 값이 $$H1$$과 $$H2$$라면, 부모 노드는 $$Hash(H1 || H2)$$값을 가지게 된다.
* **머클 루트 (Merkle Root)**: 가장 최상위에 위치한 단일 노드이다. 트리 구조의 꼭대기에 있으며, 모든 하위 데이터 블록의 해시 값이 재귀적으로 결합되어 생성된 최종 해시 값이다. 이 머클 루트 값 하나로 전체 데이터 집합의 무결성을 대표할 수 있다.

데이터 블록들을 해시하여 리프 노드를 만들고, 이웃하는 두 리프 노드의 해시 값을 합쳐서 다시 해시하는 과정을 반복하여 상위 노드를 생성한다. 이 과정을 최종적으로 하나의 머클 루트가 나올 때까지 반복한다.

이처럼 머클 트리는 특정 트랜잭션의 유효성을 검증하기 위해 전체 블록을 확인할 필요 없이, 해당 트랜잭션의 리프 노드부터 머클 루트까지의 **머클 증명(Merkle proof)** 경로와 형제 노드의 해시값만을 사용하여 효율적이고 암호학적으로 안전하게 검증할 수 있도록 돕는다.

### Reference

1. <https://www.helius.dev/blog/cryptographic-tools-101-hash-functions-and-merkle-trees-explained>
2. [https://velog.io/@dohoon8/Cryptography-5.-Hash-function에-대하여](https://velog.io/@dohoon8/Cryptography-5.-Hash-function%EC%97%90-%EB%8C%80%ED%95%98%EC%97%AC)
3. <https://www.coursera.org/learn/cryptography/home/module/4>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-0/prerequisite/undefined.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.