Definition
‘임의의 길이의 데이터’를 ‘고정된 길이의 데이터’로 매핑하는 함수 → 데이터의 길이에 상관없이 항상 동일한 길이의 출력을 생성
해시함수의 특성
-
Efficiency
Hash function은 주어진 입력에 대해서 효율적으로 hash 값을 계산해야 한다.
-
Pre-image resistance
주어진 hash 값으로부터 원래의 입력 데이터를 알아내기 어려워야 한다.
-
Second pre-image resistance
특정 입력 데이터가 주어질 때, 해당 입력 데이터의 hash 값과 동일한 hash 값을 갖는 다른 입력 데이터를 찾아내기 어려워야 한다.
-
Collision-resistance
동일한 hash 값을 가지는 입력 데이터 쌍을 찾아내기 어려워야 한다.
- collision : 서로 다른 두 입력값(데이터) x와 x'가 동일한 해시 값을 생성하는 경우 ()
- 만약 어떤 해시 함수에서 충돌을 찾는 것이 계산적으로 거의 불가능하다면 충돌 저항성을 가진다 한다.
- collision : 서로 다른 두 입력값(데이터) x와 x'가 동일한 해시 값을 생성하는 경우 ()
- Second Pre-image Resistance: 특정 x이 주어져 있고, 그 기준점과 같은 해시 값을 갖는 다른 x′를 찾기 어려운 특성 (1대1 공격)
- Collision Resistance: 기준점 없이, 해시 값이 같은 임의의 두 쌍(x, x′)을 찾기 어려운 특성(무작위 2개 찾기)
해시함수의 필요성
해시 함수는 데이터의 무결성을 검증하는 데 핵심적으로 사용된다.
- 이는 입력 데이터의 극히 작은 변화에도 최종 해시 값이 크게 달라지는 Avalanche Effect 덕분이다.
- 이러한 특성으로 인해 Collision-resistance과 Second Pre-image resistance이 보장되어, 데이터의 위조나 변조를 사실상 불가능하게 만든다.
즉, 특정 파일이나 메시지를 배포하거나 전송할 때, 원본 데이터의 해시 값을 함께 제공함으로써 수신자는 해당 데이터가 중간에서 변경되지 않았음을 확신할 수 있다. (Integrity 보장)
Example of Hash function
- MD5
- 1991년에 개발
- 128 bit의 output → collsion이 2004년 발견되어 더 이상 사용되지 않음
- SHA-1
- 1995년 처음 소개
- 160 bit의 Output → 이론적 분석으로 오류가 있음이 확인되었고 SHA-2로 발전
- SHA-2
- 256 bit 또는 512 bit의 output → 약점이 발견되지 않음
- SHA-3
- SHA 계열과는 매우 다른 설계 방식 → 기존의 SHA는 Merkle–Damgård 구조라는 유사한 구조를 가지는데 Keccak은 근본적으로 다른 접근 방식인 sponge construction를 사용
- 224, 256, 384, 512 bit의 output
해시 함수의 응용: Merkle Tree
만약 검증해야 할 데이터가 수십, 수백만 개에 달하는 대규모 집합이라면 어떨까?
모든 개별 데이터의 해시 값을 일일이 비교하는 것은 매우 비효율적일 것이다.
⇒ 이러한 문제를 해결하고 대규모 데이터 집합의 무결성을 효율적으로 검증하기 위해 '머클 트리(Merkle Tree)'라는 자료구조가 해시 함수를 기반으로 활용된다.
머클 트리의 구성 요소 및 작동 원리
머클 트리는 해시 함수를 기반으로 계층적으로 구성된다. 주요 구성 요소는 다음과 같다.
- 리프 노드 (Leaf Nodes): 가장 하위 레벨에 위치한 노드들이다. 각 리프 노드는 원본 데이터 블록(또는 트랜잭션 등)의 개별 해시 값을 저장한다. 예를 들어, 여러 개의 트랜잭션이 있다면 각 트랜잭션의 해시 값이 하나의 리프 노드가 된다.
- 비-리프 노드 (Non-Leaf Nodes): 리프 노드 위에 있는 중간 노드들이다. 각 비-리프 노드는 자신이 가진 자식 노드들의 해시 값을 합쳐서 다시 해시(Concatenation & Hashing)한 결과를 저장한다. 예를 들어, 두 자식 노드의 해시 값이
H1과H2라면, 부모 노드는Hash(H1 + H2)값을 가지게 된다. - 머클 루트 (Merkle Root): 가장 최상위에 위치한 단일 노드이다. 트리 구조의 꼭대기에 있으며, 모든 하위 데이터 블록의 해시 값이 재귀적으로 결합되어 생성된 최종 해시 값이다. 이 머클 루트 값 하나로 전체 데이터 집합의 무결성을 대표할 수 있다.
데이터 블록들을 해시하여 리프 노드를 만들고, 이웃하는 두 리프 노드의 해시 값을 합쳐서 다시 해시하는 과정을 반복하여 상위 노드를 생성한다. 이 과정을 최종적으로 하나의 머클 루트가 나올 때까지 반복한다.
이처럼 머클 트리는 특정 트랜잭션의 유효성을 검증하기 위해 전체 블록을 확인할 필요 없이, 해당 트랜잭션의 리프 노드부터 머클 루트까지의 머클 증명(Merkle proof) 경로와 형제 노드의 해시값만을 사용하여 효율적이고 암호학적으로 안전하게 검증할 수 있도록 돕는다.
