손으로 그린 서명은 필압, 속도, 리듬, 글자 기울기 같은 요소가 합쳐져 고유성을 만든다. 하지만 문서가 디지털로 오가는 시대에 이 서명은 치명적인 약점을 드러낸다. 이미지처럼 복사해 다른 문서에 붙여넣을 수 있기 때문이다. 내가 붙여넣을 수 있다면 남도 붙여넣을 수 있고, 어느 날 위조된 서명 한 장으로 내 자산이 사라져도 이상할 게 없다. 전자 서명이 필요한 이유가 바로 여기에 있다.
랄프 머클(Ralph Charles Merkle)은 1979년 박사학위 논문 'Secrecy, Authentication, and Public Key Systems'에서 이 문제에 대한 개선안을 제시했다. 다만 전자 서명 자체를 그가 처음 고안한 것은 아니다. 그는 램포트-디피(Lamport-Diffie) 일회용 서명을 개선했고, 그 서명은 다시 라빈(Rabin)의 서명을 발전시킨 것이었다. 실무자 입장에서 중요한 것은 이 계보 전체를 관통하는 재료가 결국 '일방향 함수', 즉 오늘날의 해시 함수라는 점이다.
일회용 서명과 그 허점
머클이 든 예시는 명료하다. 주식을 가진 앨리스와 중개인 밥이 있다. 앨리스는 주식을 살 때 일방향 함수로 F(x)=y를 계산해 y만 밥에게 넘기고, 나중에 팔고 싶을 때 x를 공개하기로 계약해 둔다. 여러 주를 파는 경우라면 메시지의 각 비트마다 별도의 개인키 x_j와 공개키 y_j를 준비하고, 메시지에서 1에 해당하는 비트의 x_j만 공개해 서명한다.
문제는 밥이 특정 개인키를 '받지 못한 척'하며 1을 0으로 바꿔 '11주'를 '10주'로 조작할 수 있다는 데 있다. 램포트와 디피는 메시지 m 뒤에 그 보수(complement) m'을 덧붙이는 방식으로 이를 막았다. 밥이 어느 비트를 0으로 바꾸려면 보수 쪽에서 0을 1로 만들어야 하는데, 그에 해당하는 개인키는 애초에 받은 적이 없어 불가능하다. 다만 이 방식은 메시지 길이를 두 배로 늘린다는 대가가 따른다.
머클의 압축과 인증 트리
머클은 보수 전체 대신 '0의 개수'만 메시지 끝에 붙였다. 100비트 메시지라면 ⌈log₂100⌉=7비트면 충분하다. 이것이 성립하는 이유는 밥이 오직 1을 0으로만 바꿀 수 있기 때문이다. 본문의 1을 0으로 바꾸면 0의 개수는 늘어나므로 개수 필드에서 0을 1로 만들어야 하는데 그것을 할 수 없다. 반대로 '1의 개수'를 붙였다면 양쪽에서 1을 0으로 함께 줄여 손쉽게 위조가 가능해진다.
그러나 일회용 서명은 공개키 저장 부담이 크다는 근본 한계가 남는다. 여기서 등장하는 것이 트리 인증이다. 이진 트리의 잎에 램포트-디피 공개키 벡터 Y_i를 두고, 내부 노드와 루트는 또 다른 일방향 함수 H로 귀납적으로 계산한다. 앨리스가 여덟 개의 서명 메시지를 준비한다면 잎에서 시작해 쌍을 묶어 올라가 최종적으로 루트값 R을 얻는다. 밥과 앨리스가 사전에 합의하고 저장해야 할 값은 오직 이 R 하나뿐이다.
저장 비용과 블록체인으로의 연결
효과는 극적이다. 예시에서 두 해시 함수는 100비트 출력을 낸다. 밥이 1000개의 메시지를, 그것도 1000명의 고객에게서 받아 모든 공개키를 보관한다면 약 2.5GB가 필요하다. 반면 머클 방식에서 밥이 저장하는 것은 100비트 고정 길이의 루트값 하나다. 검증에 필요한 인증 경로에서 중복을 제거하면 결국 트리 자체의 구조가 남으며, 앨리스는 m1·m2·m3을 서명한 뒤 다시 쓰이지 않을 내부 노드들을 지워 버릴 수도 있다. 나아가 200비트짜리 시드키 하나만 보관하면 여덟 개의 개인키 벡터 전체를 다시 생성할 수 있다. 시드키에서 키를 재계산하는 비용이 전량 저장 비용보다 훨씬 싸다는 것이 머클의 계산이었고, 오늘날 연산이 더 빨라진 만큼 이 교환은 더욱 유리하다.
이 구조는 그대로 블록체인의 뼈대가 됐다. 각 블록은 이전 블록으로의 연결과 함께 수천 건의 트랜잭션을 잎으로 삼는 머클 트리를 담는다. 비트코인 백서 'Bitcoin: A Peer-to-Peer Electronic Cash System'은 머클 트리를 간이 결제 검증(SPV)의 해법으로 명시한다. 전체 블록체인을 내려받지 않고도 관련 인증 경로만으로 단일 트랜잭션을 검증할 수 있는데, 이는 밥이 트리 전체를 보관하지 않고 메시지 하나를 검증하던 것과 정확히 같은 원리다.
실무적으로 기억할 점은 두 가지다. 첫째, 노드에 담기는 값은 결국 해시이며, 해시 함수는 비밀번호 보호를 넘어 거대한 자료 구조 전체를 저장 부담 없이 인증하는 도구라는 사실이다. 둘째, 이 모든 안전성은 사전 합의된 루트값의 신뢰에 달려 있다는 한계다. 만약 적대자가 서명 직전에 스스로 공개키와 개인키를 전부 만들어 악의적 메시지에 서명해 보낸다면, 밥은 그 키가 앨리스의 것인지 알 방법이 없다. 결국 어떤 형태로든 사전 약속, 즉 루트값에 대한 신뢰의 뿌리가 전제되어야 나머지 구조가 의미를 갖는다.