Ralph Merkle

암호화한 메시지를 보내려 합니다. 받는 사람이 읽으려면 비밀 키가 필요한데, 누군가 모든 통신을 지켜본다면 그 키를 어떻게 전달할까요? Ralph Merkle는 1978년 논문에서 뜻밖의 방법을 설명했습니다. 발신자가 암호화한 퍼즐을 많이 준비하면 수신자는 무작위로 고른 퍼즐을 풀고, 그 안에 숨겨진 식별자를 공개적으로 돌려보냅니다. 이제 두 사람은 공통 키를 압니다. 도청자도 식별자는 보지만 어느 퍼즐에 들어 있었는지 모릅니다. 논문의 모델에서 도청자의 작업량은 문제 크기의 제곱에 비례해 늘고, 참여자의 작업량은 선형으로 늘어납니다. 격차는 제곱 수준이지 지수적이지 않습니다. 역사적인 돌파구였지만 오늘날 메시지 암호화에 권장되는 절차라는 뜻은 아닙니다. [1]

1978년 논문에서는 공격자가 무엇을 할 수 있는지 살펴봐야 합니다. 도청은 허용하지만 변경이나 위조는 탐지할 수 있다는 가정이 남아 있습니다. 편지를 읽는 사람과, 편지를 고쳐 쓰고 당신 이름으로 서명까지 하는 사람을 생각해 보세요. 후자는 실제 상대방이 누구인지 확인하는 추가 보호가 필요합니다. 계산 작업량의 차이만으로 그 문제를 해결할 수는 없습니다. 따라서 퍼즐이 능동적으로 개입하는 중개자를 거치는 모든 통신의 안전을 보장하지는 않습니다. 미리 공유한 비밀 키가 없어도 명시된 가정 아래에서는 합의할 수 있음을 보여 준 것이 핵심입니다. [1]

Merkle Tree는 다른 문제를 다룹니다. 이 인증 트리는 Merkle의 1979년 박사학위 논문에 나옵니다. 계약서 보관소에서 전체를 내려받지 않고 특정 계약서만 확인하고 싶다고 해 봅시다. 각 항목에서 짧은 디지털 지문인 해시를 계산합니다. 지문을 쌍으로 합쳐 다시 해시하는 과정을 반복하면 공통 루트가 남습니다. 해싱은 내용을 암호화하는 것이 아니라 일치를 확인하는 수단입니다. 의미 있는 검증을 위해서는 올바른 보관소의 지문이라고 미리 인증된 루트가 필요합니다. 사기꾼이 자기 문서와 임의의 루트를 함께 줄 수 있다면 둘이 일치해도 원래 보관소에 관해서는 아무것도 증명하지 못합니다. [2]

항목 8개가 있는 균형 이진 트리를 예로 들어 보겠습니다. 선택한 리프를 검증하려면 각 단계의 이웃 가지 지문인 형제 해시 3개가 필요합니다. 자신의 리프와 이 지문들로 루트를 계산해 인증된 루트와 비교합니다. 리프 자체와 루트는 이 보조 해시의 개수에 포함되지 않습니다. 트리 구조와 결합 순서, 즉 이웃 값을 왼쪽에 둘지 오른쪽에 둘지도 알아야 합니다. 데이터 절약은 숨겨진 정보를 이용하는 마술이 아닙니다. 멀리 있는 보관소 부분을 지문이 대표하므로, 이 특정 검증에는 다른 문서의 전체 내용이 필요하지 않은 것입니다. [2]

Merkle Tree는 항목과 특정 데이터 집합의 관계를 증명합니다. 잘못된 정보가 참이 되도록 만들지는 않습니다. 예시 보관소에는 이름이 틀린 계약서도 들어갈 수 있습니다. 증명은 그 계약서가 포함되었다는 사실을 정확히 확인하면서도 이름의 오류는 발견하지 못할 수 있습니다. 지문은 문서 작성자에게 권한이 있었는지도 증명하지 않습니다. 항목이 이 루트와 맞는지, 루트를 어디서 알았는지, 어떤 규칙으로 내용을 받아들이는지를 구분해야 합니다. 그러면 같은 기술이 Bitcoin에서 하는 일과 다른 구성 요소가 맡아야 하는 일이 분명해집니다. [2]

Bitcoin은 Merkle Tree를 이용해 거래를 블록의 간략한 기록인 블록 헤더에 연결합니다. 루트는 헤더에 포함되며, 수록된 거래가 바뀌면 공동 지문에 영향을 줍니다. Satoshi Nakamoto는 whitepaper의 7절에서 이 구조를 설명하고 Merkle의 연구를 참고문헌으로 제시합니다. 이는 기술적 영향의 근거이지 Merkle가 Bitcoin을 만들었다는 근거는 아닙니다. 트리는 유효한 이력을 고르거나 노드 대신 거래 서명을 검사하지 않습니다. Bitcoin은 거래 검증과 계산 작업의 증거인 Proof of Work 등 다른 규칙을 함께 사용합니다. 한 구성 요소에 전체 시스템의 능력을 돌리기보다 그 역할을 이해하는 편이 유용합니다. [3]

whitepaper의 8절은 SPV, 간소화된 결제 검증을 설명합니다. 경량 클라이언트는 블록 헤더와 거래를 선택한 블록에 연결하는 트리 가지를 사용합니다. 데이터는 절약하지만 누적 작업량이 가장 큰 체인과 채굴자의 행동에 관한 가정에 의존합니다. 포함 증명만으로는 완전한 검증을 수행하는 Full Node처럼 거래의 모든 규칙을 확인하지 못합니다. 특정 출력이 나중에 사용되었는지도 보여 주지 않습니다. 그러려면 이후의 사건을 알아야 합니다. 처음 배우는 사람에게 중요한 점은 “이 결제가 이 블록에 있다”를 “지금 사용 가능한 자금을 완전히 확인했다”와 혼동하지 않는 것입니다. [3]

1979년 박사학위 논문은 인증 트리를 유한한 일회용 디지털 서명 집합에도 사용합니다. 디지털 서명은 특정 비밀 키의 소유자가 메시지를 승인했는지 확인하는 수단이며, 종이에 쓴 서명의 이미지가 아닙니다. 트리는 여러 검증 값을 하나의 알려진 루트에 연결할 수 있습니다. 다만 이 구조에서는 사용할 수 있는 서명 수가 한정되어 있으므로 결국 루트를 갱신해야 합니다. 같은 일회용 키를 무제한 재사용해도 된다는 뜻이 아닙니다. 이 심화 주제에도 공통된 생각이 있습니다. 필요한 부분을 작은 증명으로 검증하되, 검증이 어떤 조건에 의존하는지 정확히 이해해야 합니다. [2]