암호화 도구 101 - 해시 함수와 머클 트리 해설
이 글에서는 무엇을 다루나요?
블록체인을 사용하면 중개자 없이도 사람들이 합의할 수 있습니다. 블록체인은 신뢰 대신 암호학적 증명에 의존합니다. 이러한 증명을 제공하는 데 암호화 기본 요소가 사용됩니다. 그렇다면 암호화 기본 요소란 무엇일까요?
이 글에서는 블록체인의 암호학적 증명에 필수적인 두 가지 암호화 기본 요소인 해시 함수와 머클 트리를 살펴봅니다. 해시 함수의 핵심 작동 원리를 알아보고, 블록체인에서 해시 함수가 중요한 이유와 해시 포인터를 살펴봅니다. 그런 다음 전통적 머클 트리와 동시성 머클 트리를 분석하고 Solana에서 이들이 왜 중요한지 설명합니다.
암호화 기본 요소란 무엇인가요?
암호화 기본 요소는 암호화 프로토콜과 시스템을 구축하는 데 토대가 되는 연산 또는 알고리즘입니다. 암호화 프로토콜에서 암호화 기본 요소는 분자를 이루는 원자와 같습니다. 더 복잡한 솔루션을 구성하는 요소입니다. 난수 생성기, 커밋먼트 스킴, 공개 키 암호화가 모두 암호화 기본 요소의 예입니다.
암호화 기본 요소는 단독으로 사용할 때는 상당히 제한적입니다. 하지만 여러 요소를 결합하면 인증, 기밀성, 무결성과 같은 기본 보안 기능을 제공할 수 있습니다. 암호화 기본 요소를 결합하는 작업은 매우 섬세한 과정으로, 신중한 계획과 각 요소의 상호작용에 대한 깊은 이해가 필요합니다. 이 과정에서는 달성하려는 보안 목표에 따라 보안 관련 사항을 면밀히 고려해야 합니다. 암호화 기본 요소를 결합하는 방법은 크게 다음과 같이 분류할 수 있습니다.
- 순차적 구성: 기본 요소를 차례로 적용합니다(예: 해시 체이닝)
- 병렬 구성: 기본 요소를 동시에 독립적으로 사용합니다(예: 데이터를 동시에 암호화하고 해싱)
- 계층적 구성: 한 암호화 기본 요소 내부에서 다른 요소를 사용합니다(예: 머클 트리)
암호화 기본 요소의 정의와 작동 방식, 그리고 이를 결합할 때의 미묘한 차이를 이해하면 안전하고 효율적인 시스템을 파악하고 설계하는 데 도움이 됩니다. 가장 널리 사용되고 조합되는 암호화 기본 요소 중 하나가 해시 함수입니다.
해시 함수란 무엇인가요?
해시 함수는 크기에 상관없이 데이터를 입력받아 고정 크기의 값을 반환하는 암호화 함수입니다. 이 함수가 반환하는 값을 다이제스트 또는 해시라고 합니다. 널리 사용되는 해싱 알고리즘으로는 SHA-1, SHA-2, SHA-3, MD5, Argon2가 있습니다. 해시 함수는 블록체인 전반에서 사용되므로 그 개념과 작동 방식을 반드시 이해해야 합니다.
간단한 비유
화려한 초콜릿 케이크를 굽는다고 상상해 보세요. 케이크는 여러 층으로 이루어져 있고, 층마다 서로 다른 재료가 들어갑니다. 케이크를 굽는 동안 친구가 무엇을 하고 있는지 묻는 메시지를 보냅니다. 케이크를 만든 방법과 사용한 모든 재료를 자세히 설명하기는 꽤 번거롭습니다. 대신 친구에게 초콜릿 케이크 사진을 보내기로 합니다.
여기서 케이크 사진은 해시 역할을 합니다. 훨씬 복잡한 대상을 단순하고 간결하게 표현한 것입니다. 친구는 케이크에 들어간 모든 재료를 알 수는 없지만, 방금 무엇을 구웠는지는 충분히 파악할 수 있습니다. 초콜릿 케이크 위에 라즈베리가 올라가 있다고 가정해 보겠습니다. 라즈베리를 빼거나 딸기로 바꾸면 케이크 사진은 완성된 결과물과 완전히 달라집니다. 마찬가지로 해싱된 데이터가 조금이라도 바뀌면 새로운 해시 값이 생성됩니다.
좋은 암호화 해시 함수의 특성
앞서 제시한 해시 함수의 정의는 오해를 불러일으킬 수 있습니다. 해시 함수가 가변 크기의 해시를 반환할 수도 있기 때문입니다. 서로 다른 두 입력에 같은 해시를 반환할 수도 있습니다. 누군가 해시를 매우 쉽게 역으로 분석해 원본 입력을 알아낼 수도 있습니다. 앞의 정의는 좋은 암호화 해시 함수에 대한 것이었습니다. 그렇다면 어떤 조건을 갖춰야 좋은 암호화 해시 함수일까요?
좋은 해시 함수는 결정적입니다. 같은 입력은 언제나 같은 출력을 생성합니다. “baseball”이라는 입력을 해싱하면 어떤 시스템에서든 해당 해시 함수는 매번 같은 해시를 출력합니다. 이는 입력 크기와 관계없이 해시 크기가 같다는 뜻이기도 합니다. 이러한 특성은 처리 효율성과 데이터 저장에 중요합니다. 고유한 입력이 항상 고유한 출력을 생성하고 그 출력이 언제나 고정된 크기라면 좋은 암호화 해시 함수라고 볼 수 있습니다.
좋은 해시 함수는 역상 저항성을 갖습니다. 즉, 해시를 바탕으로 입력 값을 역으로 분석하는 것은 계산상 불가능에 가깝습니다. 누군가 해시를 주더라도 어떤 데이터가 그 해시를 생성했는지 알아낼 수 없어야 합니다. 또한 서로 다른 두 데이터 세트가 같은 해시를 생성해서는 안 됩니다. 어떤 두 입력도 절대 같은 해시를 생성하지 않을 때 좋은 해시 함수가 충돌 저항성을 갖는다고 합니다.
좋은 해시 함수는 눈사태 효과를 따릅니다. 입력을 조금만 변경해도 완전히 다른 해시가 나와야 합니다. 문자 하나만 바꿔도 전혀 다른 해시가 생성되어야 합니다. 따라서 해시 출력은 입력에 관한 정보를 드러내거나 식별 가능한 패턴을 보여서는 안 됩니다. 위 그림에서 해시가 어떻게 달라지는지 확인해 보세요. 붉은 여우가 “달리는” 경우에는 “걷는” 경우와 완전히 다른 해시가 생성됩니다. 두 해시에 거의 동일한 정보가 담겨 있다는 징후도 없습니다.
좋은 해시 함수는 빠르게 계산할 수 있어야 합니다. 느린 해시 함수는 트랜잭션 검증처럼 실시간 또는 준실시간 계산이 필요한 상황에 적합하지 않습니다. 느린 해시 함수는 심각한 병목이 되어 처리량과 네트워크 성능을 모두 제한할 수 있습니다. 블록체인에서 효율적이고 안전한 성능을 구현하려면 빠른 해시 함수가 필요합니다.
블록체인에서 왜 중요한가요?
블록체인은 네트워크 전반의 트랜잭션을 기록하는 탈중앙화 분산 원장입니다. 이러한 트랜잭션은 블록으로 묶이며, 블록은 좋은 해시 함수를 통해 안전하게 연결됩니다. 각 블록에는 트랜잭션 데이터, 타임스탬프, 이전 블록의 해시가 포함됩니다. 각 블록의 해시는 이전 블록의 해시에 의존하므로 블록의 내용을 변경하면 해시도 바뀌고 이후의 모든 블록이 무효화됩니다. 이전 해시를 사용해 새 해시를 생성하는 이 과정을 해시 체이닝이라고 합니다.
블록체인에 새 블록을 추가하는 것을 컨펌이라고 합니다. 컨펌은 새 블록과 이전의 모든 블록에 포함된 트랜잭션을 검증하고 보호합니다. 컨펌이 새로 추가될 때마다 이전 블록을 변경하기가 더 어려워지기 때문입니다. 이전 블록을 변경하려면 공격자가 이전의 모든 해시를 다시 계산해야 합니다. 따라서 블록에 충분한 컨펌이 쌓이면 해시 체이닝 덕분에 블록체인을 변경하는 것이 사실상 불가능해집니다.
간단히 말해 블록체인은 해시 함수로 보호되는 블록의 체인입니다. 그렇다면 한 블록에서 다른 블록을 정확히 어떻게 가리킬까요? 암호화 해시 함수를 사용해 블록을 연결하는 것은 맞지만, 이전 블록의 데이터는 어떻게 확인할 수 있을까요? 좋은 암호화 해시 함수는 역상 저항성을 갖는다고 하지 않았나요?
해시 포인터란 무엇인가요?
포인터는 특정 데이터가 메모리에 저장된 위치를 담는 변수입니다. 포인터가 데이터의 위치를 “가리키므로” 해당 메모리 주소의 데이터에 쉽게 접근할 수 있습니다. 해시 포인터는 포인터와 유사한 데이터 구조이지만, 참조하는 데이터의 암호화 해시도 포함합니다. 따라서 해시 포인터를 사용하면 특정 데이터에 접근할 위치를 파악하고, 접근한 데이터의 무결성을 확인할 수 있습니다.
블록체인의 구조는 해시 포인터를 사용하는 연결 리스트라고 표현하는 편이 더 정확합니다. 이전 블록의 해시는 트랜잭션 집합과 그 모든 트랜잭션의 해시를 가리키는 해시 포인터입니다. 해시 포인터는 블록 간 연결과 각 블록의 무결성을 보장하며, 새로 추가된 블록이 이전 블록을 올바르게 잇는지 검증하는 데 사용됩니다.
해시 포인터를 사용하면 블록을 효율적으로 연결할 수 있습니다. 그렇다면 블록 안의 트랜잭션은 어떻게 처리할까요? 한 블록에 트랜잭션이 1,000개 들어 있다면 이를 하나씩 검증하는 데 큰 비용이 들지 않을까요?
머클 트리란 무엇인가요?
머클 트리는 대규모 데이터 세트를 구성하고 검증하는 데 사용하는 데이터 구조입니다. 데이터는 트리와 같은 구조로 구성되며, 각 리프 또는 노드에는 데이터 세트의 해시가 표시됩니다. 리프가 아닌 각 노드는 자식 노드의 해시입니다. 머클 트리는 블록체인에 전파된 특정 블록에 포함된 트랜잭션을 검증하는 데 사용됩니다. 그렇다면 어떻게 작동할까요?
트랜잭션은 하나의 목록으로 배치 처리되어 블록을 구성합니다. 목록의 각 트랜잭션은 좋은 해시 함수로 해싱됩니다. 이 해시들이 리프 노드 역할을 합니다. 리프 노드를 쌍으로 묶어 함께 해싱하면 새로운 해시 계층이 만들어집니다. 머클 루트라고 하는 하나의 해시만 남을 때까지 이 과정을 반복합니다. 머클 루트는 블록 헤더에 저장되며 해당 블록의 모든 트랜잭션을 나타내는 디지털 지문 역할을 합니다. 머클 루트를 블록의 해시라고 부를 수도 있습니다. 따라서 새 블록이 이전 블록의 blockhash를 사용해 이전 블록과 연결된다고 말할 때는 이전 블록의 머클 루트를 새 블록 해시의 일부로 사용한다는 뜻입니다.
머클 트리를 사용하면 블록 내 개별 트랜잭션을 효율적으로 검증할 수 있습니다. 전통적인 방식에서는 특정 트랜잭션 하나를 검증하기 위해 모든 트랜잭션을 확인해야 하므로 비용과 시간이 많이 듭니다. 머클 트리는 머클 증명이라는 암호학적 “지름길”을 제공해 검증 과정을 지원합니다. 머클 증명은 트랜잭션의 리프 노드에서 머클 루트까지 이어지는 경로입니다. 위 그림에서는 Data A에서 머클 루트까지 이어지는 경로라고 생각하면 됩니다. 이 경로에는 형제 노드도 포함됩니다. 각 형제 노드는 경로에 있는 노드와 인접하지만 경로 자체에는 속하지 않는 리프입니다. 검증자는 증명 경로를 사용해 해시를 계산하고, 계산한 해시가 머클 루트와 일치하는지 확인할 수 있습니다. 결과 해시가 일치하면 해당 트랜잭션이 유효하고 변조되지 않았음을 신뢰할 수 있습니다.
새 리프의 데이터를 해싱하고 머클 루트를 다시 계산하면 리프를 변경할 수 있습니다. 새로운 머클 루트는 변경 사항을 검증하는 데 사용되며 이전 증명을 무효화합니다. Solana처럼 처리량이 높은 네트워크에서는 검증인이 온체인 머클 트리에 대한 변경 요청을 빠르게 연속해서 받을 수 있습니다(예: 동일한 슬롯 내). 각 데이터 변경 사항을 순차적으로 다시 계산해야 합니다. 그렇지 않으면 같은 슬롯에서 먼저 이루어진 변경 요청으로 인해 이후의 각 변경 요청이 무효화됩니다. 리프 데이터를 변경하고 새로운 머클 루트를 계산하는 작업은 블록체인에서 매우 흔합니다. 그렇다면 빠른 변경은 어떻게 처리할까요?
동시성 머클 트리란 무엇인가요?
동시성 머클 트리는 동시 읽기와 쓰기에 최적화된 머클 트리입니다. 최근 변경 사항과 해당 루트 해시, 그리고 이를 도출하는 증명이 포함된 안전한 변경 로그를 저장합니다. 이 변경 로그는 해당 트리 전용 온체인 계정에 저장되며, 머클 루트가 여전히 유효한 상태에서 발생할 수 있는 최대 변경 횟수를 포함합니다. 이 최대 변경 횟수를 maxBufferSize라고 합니다. 따라서 검증인은 온체인 머클 트리에 대한 변경 요청을 빠르게 연속해서 받으면 이 변경 로그를 신뢰할 수 있는 정보 소스로 사용해 동일한 슬롯에서 트리에 최대 maxBufferSize번의 변경을 적용할 수 있습니다.
동시성 머클 트리는 전통적인 머클 트리를 개선해 Solana와 같은 고처리량 환경에 적합하도록 만든 구조입니다. Solana에서 온체인 동시성 머클 트리를 생성할 때는 트리의 크기, 생성 비용, 동시 변경 횟수에 영향을 주는 세 가지 속성이 있습니다.
- 최대 깊이
- 최대 버퍼 크기
- 캐노피 깊이
최대 깊이는 임의의 리프에서 머클 루트까지 도달하는 데 필요한 최대 홉 수를 뜻합니다. maxDepth는 트리 안에 저장할 수 있는 최대 노드 수를 결정하는 데 사용됩니다. 다음 공식으로 계산할 수 있습니다. numberOfNodes = 2 ^ maxDepth. 트리의 깊이는 생성할 때 설정해야 하므로, 이 공식을 사용해 트리에 저장할 데이터 수를 결정하는 것이 중요합니다.
앞서 설명했듯이 최대 버퍼 크기는 머클 루트가 여전히 유효한 상태에서 트리에 적용할 수 있는 최대 변경 횟수를 뜻합니다.
캐노피 깊이는 온체인에 저장되는 머클 트리의 하위 집합을 의미합니다. 캐시된 이 증명은 해시가 온체인 머클 루트와 일치하는지 확인하는 데 사용됩니다. 리프에 쓰기 작업을 수행할 때 원래 소유권을 검증하려면 전체 증명 경로를 사용해야 합니다. 예를 들어 NFT를 전송할 때는 트리에 쓰기 작업을 수행해야 합니다. 캐노피를 사용하면 증명 크기를 줄일 수 있으며, 트리를 검증할 때 maxDepth 크기의 증명을 사용하지 않아도 됩니다. maxDepth이 20인 트리에는 크기가 20인 증명이 필요합니다. 캐노피가 15라면 쓰기 트랜잭션마다 크기가 5인 증명만 제출하면 됩니다. 따라서 캐노피 깊이를 높이면 초기 비용은 증가하지만 이후에 더 작은 증명을 제출할 수 있습니다.
캐노피 깊이는 트리 생성 비용을 결정하는 주요 요인입니다. 캐노피 깊이가 깊을수록 더 큰 계정이 필요하기 때문입니다. 개발자는 @solana/spl-account-compression 패키지를 사용해 주어진 트리 크기에 필요한 공간과 온체인에서 해당 공간을 할당하는 데 드는 비용을 계산할 수 있습니다. getConcurrentMerkleTreeAccountSize 함수를 사용하면 매개변수에 따라 특정 계정에 필요한 공간을 계산할 수 있습니다. 그런 다음 필요한 공간에 getMinimumBalanceForRentExemption을 사용해 최종 비용을 Lamports 단위로 계산할 수 있습니다.
Solana는 상태 압축에 동시성 머클 트리를 사용합니다. 상태 압축은 오프체인 데이터의 해시를 생성하고 이를 온체인에 저장해 안전하게 검증하는 방식입니다. 상태 압축의 가장 널리 알려진 사용 사례는 압축 NFT입니다. 민팅 비용을 크게 줄일 수 있기 때문입니다. 예를 들어 Solana에서 NFT 10억 개를 민팅하는 비용은 507 $SOL이지만, “일반” NFT를 사용하면 12 000 000 $SOL이 듭니다. 이제 해싱과 머클 트리를 확실히 이해했으니 다음 글에서는 압축 NFT를 자세히 살펴보겠습니다!
결론
축하합니다! 이 글에서는 블록체인에 필수적인 두 가지 암호화 기본 요소인 해시 함수와 머클 트리를 분석했습니다. 블록체인을 이해하는 일은 결코 쉽지 않습니다. 블록체인은 폭넓은 기술적 이해가 필요한 복잡한 분산 시스템입니다. 일반 개발자, 사용자 또는 투자자가 이러한 지식을 이미 갖추고 있다고 가정하는 경우가 많습니다. 하지만 이 글은 암호화 기본 요소에 관한 사전 지식을 전제로 하지 않습니다. 기초부터 시작해 전통적 머클 트리와 동시성 머클 트리에 관한 더 복잡한 내용으로 발전해 나갔습니다. 압축 NFT처럼 더 복잡한 주제를 살펴보려면 이러한 기본 개념을 이해하는 것이 매우 중요합니다. 이제 새로 습득한 지식을 바탕으로 암호화 기본 요소와 더 복잡한 암호화 솔루션을 다루는 코드베이스나 논의를 더 능숙하게 탐색할 수 있습니다.
익명의 독자님, 여기까지 읽어주셔서 감사합니다!
추가 자료 / 더 읽어보기
Helius 구독하기
최신 Solana 개발 소식을 확인하고 새 게시물 알림을 받아보세요