Merkle Trees 및 Merkle Roots 알아보기

머클 트리란?

Merkle 트리의 개념은 80년대 초 공개 키 암호화 작업으로 유명한 컴퓨터 과학자인 Ralph Merkle이 제안했습니다.

머클 트리는 집합에 포함된 데이터의 무결성을 효율적으로 검증하는 데 사용되는 구조입니다. 참가자가 정보를 공유하고 독립적으로 검증해야 하는 P2P 네트워크의 맥락에서 특히 흥미롭습니다.

 

P2P 네트워크(Peer-to-Peer Network)는 중앙 서버를 통하지 않고, 직접적으로 각 컴퓨터나 기기들이 서로 연결되어 정보를 공유하는 네트워크입니다. 각 기기들이 서로 대등한 지위를 가지며, 자유롭게 파일이나 데이터를 공유할 수 있습니다.

P2P 네트워크는 다양한 형태로 존재합니다. 파일 공유를 위한 P2P 네트워크에서는 사용자들이 파일을 공유하고, 다운로드하는 데 사용됩니다. 게임, 음악, 동영상 등의 콘텐츠를 공유하는데 많이 사용되며, BitTorrent 등의 프로토콜이 대표적인 예시입니다.

 

또한, P2P 네트워크는 블록체인 기술에서도 활용됩니다. 블록체인에서는 각 노드들이 서로 독립적으로 거래 정보를 검증하고, 분산된 데이터베이스를 유지하며, 새로운 블록을 생성하는 작업 증명(Proof of Work)을 수행합니다.

P2P 네트워크는 중앙 집중형 서버를 통해 데이터를 전송하는 기존의 클라이언트/서버 모델과 달리, 중앙 집중화가 되지 않기 때문에 더욱 안전하고 자유로운 정보 공유가 가능합니다. 하지만, P2P 네트워크에서는 보안 및 프라이버시 등에 대한 이슈가 존재하므로, 이를 해결하기 위한 다양한 기술 및 방법들이 연구되고 있습니다.

 

머클 트리는 어떻게 작동합니까?

큰 파일을 다운로드하려고 한다고 가정합니다. 오픈 소스 소프트웨어를 사용하면 일반적으로 다운로드한 파일의 해시가 개발자가 공개한 해시와 일치하는지 확인하고 싶을 것입니다. 그렇다면 컴퓨터에 있는 파일이 그들의 파일과 정확히 동일하다는 것을 알 수 있습니다.

 

해시가 일치하지 않으면 문제가 있는 것입니다. 소프트웨어로 가장한 악성 파일을 다운로드했거나 제대로 다운로드되지 않아 작동하지 않습니다. 후자의 경우 파일이 다운로드될 때까지 기다려야 한다면 아마 그리 만족스럽지 않을 것입니다. 이제 프로세스를 다시 시작하고 프로세스가 다시 손상되지 않기를 바랍니다.

 

이것에 대해 더 쉬운 방법이 있다면, 당신은 생각합니다. 다행스럽게도 Merkle 트리가 들어오는 곳입니다. 이 중 하나를 사용하면 파일이 청크로 분할됩니다. 50GB 파일인 경우 각각의 크기가 0.5GB가 되도록 100개의 조각으로 나눌 수 있습니다. 그런 다음 하나씩 다운로드됩니다. 이것은 기본적으로 파일을 토렌트할 때 수행하는 작업입니다. 

 

이 경우 소스에서 Merkle 루트 라는 해시를 제공했을 것입니다. 이 단일 해시는 파일을 구성하는 모든 데이터 청크를 나타냅니다. 그러나 Merkle 루트를 사용하면 데이터를 훨씬 쉽게 확인할 수 있습니다. 

 

간단하게 하기 위해 8GB 파일을 8개 조각으로 나누어 사용하는 예를 들어 보겠습니다. 다른 조각 A 에서 H 까지 호출하십시오. 그런 다음 각 조각은 해시 함수를 통해 전달되어 8개의 다른 해시를 제공합니다.

해시 함수를 통해 8개의 프래그먼트 각각을 전달하여 해시를 얻습니다.

 

자, 좀 더 이해하기 쉬운 것이 있습니다. 우리는 모든 조각의 해시를 가지고 있기 때문에 하나가 잘못되면 소스의 것과 비교하여 알 수 있습니다. 가능하지만 그것은 또한 매우 비효율적입니다. 파일에 수천 개의 조각이 있는 경우 정말 모든 조각을 해시하고 결과를 세심하게 비교할 건가요?

 

아니요. 대신 각 해시 쌍을 가져와 결합한 다음 함께 해시할 것입니다. 따라서 hA + hB, hC + hD, hE + hF 및 hG + hH 를 해시합니다. 우리는 4개의 해시로 끝납니다. 그런 다음 이것들로 또 다른 해싱을 수행하여 2로 끝납니다. 마지막으로 나머지 2개를 해시하여 마스터 해시인 Merkle 루트 (또는 루트 해시)에 도달합니다.

구조는 거꾸로 된 나무처럼 보입니다. 맨 아래 행에는 노드를 생성하기 위해 결합된 리프가 있고 마지막으로 루트가 있습니다.

 

이제 다운로드한 파일을 나타내는 Merkle 루트가 있습니다. 이 루트 해시를 소스에서 제공하는 것과 비교할 수 있습니다. 일치한다면 퍼펙트! 그러나 해시가 다르면 데이터가 수정되었음을 확신할 수 있습니다. 즉, 하나 이상의 조각이 다른 해시를 생성했습니다. 따라서 데이터를 약간 수정하면 완전히 다른 Merkle 루트가 생성됩니다. 

 

다행스럽게도 어떤 조각에 결함이 있는지 확인할 수 있는 편리한 방법이 있습니다. 우리의 경우 hE 라고 해봅시다. Merkle 루트( hABCD 및 hEFGH ) 를 생성한 두 개의 해시에 대해 동료에게 요청하는 것으로 시작합니다. 해당 하위 트리에 실수가 없으므로 값 hABCD 는 그들의 값과 일치해야 합니다. 그러나 hEFGH는 그렇지 않으므로 거기에 체크인해야 합니다. 그런 다음 hEF 및 hGH 를 요청 하고 귀하의 것과 비교합니다. hGH는 괜찮아 보일 것이므로 hEF 가 범인임을 알 수 있습니다. 마지막으로 hE 와 hF 의 해시를 비교합니다. 당신은 이제 hE올바르지 않으므로 해당 청크를 다시 다운로드할 수 있습니다.

 

요약하면 Merkle 트리는 데이터를 여러 조각으로 나눈 다음 반복적으로 해시되어 Merkle 루트를 형성함으로써 생성됩니다. 그런 다음 데이터 조각에 문제가 있는지 효율적으로 확인할 수 있습니다. 다음 섹션에서 살펴보겠지만 다른 흥미로운 응용 프로그램도 있습니다.

 

비트코인에서 Merkle 루트가 사용되는 이유는 무엇입니까?

머클 트리에 대한 몇 가지 사용 사례가 있지만 여기서는 블록체인 에서의 중요성에 초점을 맞출 것입니다. 머클 트리는 비트코인과 다른 많은 암호화폐에서 필수적입니다. 그것들은 블록 헤더 에서 찾을 수 있는 모든 블록의 필수 구성 요소입니다. 트리의 잎을 얻기 위해 블록에 포함된 모든 트랜잭션의 트랜잭션 해시( TXID )를 사용합니다.

 

트랜잭션 해시(Transaction Hash)는 블록체인 기술에서 트랜잭션(Transaction)을 고유하게 식별하는 해시값입니다.

트랜잭션 해시는 트랜잭션에 대한 정보를 암호화하여 생성된 고유한 값으로, 다른 트랜잭션과 중복되지 않습니다. 이를 통해 블록체인에서 트랜잭션을 식별하고, 트랜잭션이 유효한지 검증하는 등의 역할을 수행합니다.

 

트랜잭션 해시는 블록체인에서 블록을 생성할 때마다 새로 생성되며, 이전 블록의 해시 값과 함께 다음 블록의 해시 값 계산에 사용됩니다. 이를 통해 블록체인에서는 이전 블록과 다음 블록이 연결되어 블록체인의 안전성과 무결성이 보장됩니다.

 

또한, 블록체인에서는 모든 노드가 동일한 트랜잭션 해시 값을 가지고 있기 때문에, 트랜잭션의 변조나 위조를 방지할 수 있습니다. 이를 통해 블록체인에서는 안전하고 신뢰성 높은 거래가 이루어질 수 있습니다.

 

Merkle 루트는 이 경우 몇 가지 용도로 사용됩니다. cryptocurrency 마이닝 및 트랜잭션 확인에서 그들의 응용 프로그램을 살펴보겠습니다.

 

채굴

비트코인 블록은 두 부분으로 구성됩니다. 첫 번째 부분은 블록에 대한 메타데이터를 포함하는 고정 크기 세그먼트인 블록 헤더입니다. 두 번째 부분은 크기가 가변적이지만 헤더보다 훨씬 큰 경향이 있는 트랜잭션 목록입니다.

 

메타데이터(Metadata)는 데이터에 대한 설명이나 데이터 자체를 다루는 데이터를 말합니다. 즉, 데이터를 설명하는 데이터로, 데이터의 내용, 형식, 처리 방법, 사용 권한 등을 포함합니다.

메타데이터는 다양한 형태로 존재하며, 문서의 제목, 작성자, 작성일 등과 같은 문서 정보, 이미지의 크기, 촬영 날짜, 촬영 장소 등과 같은 이미지 정보, 음악 파일의 제목, 가수, 작곡가, 앨범 정보 등과 같은 음악 정보 등이 메타데이터의 예시입니다.

 

메타데이터는 정보 검색, 정렬, 분류, 보관, 전송, 공유, 보안 등 다양한 용도로 활용됩니다. 예를 들어, 문서 파일의 메타데이터를 활용하여 검색 엔진에서 특정 문서를 검색하거나, 이미지 파일의 메타데이터를 활용하여 검색 조건을 설정하거나, 음악 파일의 메타데이터를 활용하여 음악 스트리밍 서비스에서 재생 목록을 생성하는 등의 기능이 있습니다.

메타데이터는 개인 정보 보호 등의 이유로 노출되지 않도록 주의해야 하며, 데이터의 종류와 목적에 맞게 적절하게 활용되어야 합니다.

 

채굴자는 유효한 블록을 채굴하기 위해 특정 조건과 일치하는 출력을 생성하기 위해 데이터를 반복적으로 해시해야 합니다. 그들은 하나를 찾기 전에 수조 번의 시도를 할 수 있습니다. 시도할 때마다 블록 헤더의 난수( nonce )를 변경하여 다른 출력을 생성합니다. 그러나 블록의 대부분은 동일하게 유지됩니다. 수천 건의 트랜잭션이 있을 수 있으며 매번 트랜잭션을 해시해야 합니다.

 

난수(Nonce)는 무작위로 생성된 숫자 또는 문자열로, 주로 암호화 기술에서 사용됩니다.

암호화 기술에서는 난수를 주로 암호화 키나 인증서 등의 생성에 사용합니다. 난수는 예측이 불가능하며, 매번 다른 값을 가지므로 보안성을 높이는 데 도움이 됩니다. 예를 들어, 암호화된 데이터의 무결성을 검증하기 위해 사용되는 해시 함수에서는 메시지에 대한 난수를 추가하여 보안성을 강화합니다.

 

특히, 블록체인 기술에서는 난수를 이용하여 새로운 블록의 유효성을 검증하는 작업 증명(Proof of Work) 알고리즘에 사용됩니다. 이때 새로운 블록의 해시 값을 계산하기 위해 이전 블록의 해시 값과 트랜잭션 데이터, 그리고 난수를 입력으로 사용합니다. 이를 통해 블록체인 네트워크의 분산된 참여자들은 난수 값을 계속해서 변경하며, 새로운 블록의 해시 값을 발견하기 위해 경쟁하는 작업 증명을 수행합니다.

 

Merkle 루트는 프로세스를 상당히 간소화합니다. 마이닝을 시작하면 포함하려는 모든 트랜잭션을 정렬하고 Merkle 트리를 구성합니다. 결과 루트 해시(32바이트)를 블록 헤더에 넣습니다. 그런 다음 채굴할 때 전체 블록 대신 블록 헤더만 해시하면 됩니다.

 

변조 방지 기능이 있기 때문에 작동합니다. 블록의 모든 트랜잭션을 간결한 형식으로 효과적으로 요약합니다. 유효한 블록 헤더를 찾고 나중에 트랜잭션 목록을 변경할 수 없습니다. 그렇게 하면 Merkle 루트가 변경되기 때문입니다. 블록을 다른 노드로 보낼 때 트랜잭션 목록에서 루트를 계산합니다. 헤더에 있는 것과 일치하지 않으면 블록을 거부합니다.

 

확인

우리가 활용할 수 있는 Merkle 루트의 또 다른 흥미로운 속성이 있습니다. 이것은 라이트 클라이언트(블록체인의 전체 복사본을 보유하지 않는 노드)와 관련이 있습니다. 리소스가 제한된 장치에서 노드를 실행하는 경우 블록의 모든 트랜잭션을 다운로드하고 해시하고 싶지 않을 것입니다.

 

대신 할 수 있는 일은 거래가 특정 블록에 있음을 증명하는 전체 노드에서 제공하는 증거인 Merkle 증명을 요청하는 것입니다. 이것은 일반적으로 단순화된 지불 확인 또는 SPV라고 하며 비트코인 ​​백서에서 Satoshi Nakamoto 가 자세히 설명했습니다.

hD 를 확인하려면 빨간색으로 표시된 해시만 필요합니다.

 

TXID가 hD 인 트랜잭션에 대한 정보를 알고자 하는 시나리오를 고려하십시오. hC 가 제공 되면 hCD를 해결할 수 있습니다. 그런 다음 hABCD를 계산하려면 hAB가 필요합니다. 마지막으로 hEFGH를 사용하여 결과 Merkle 루트가 블록 헤더의 것과 일치하는지 확인할 수 있습니다. 그렇다면 트랜잭션이 블록에 포함되었다는 증거입니다. 다른 데이터로 동일한 해시를 생성하는 것은 거의 불가능합니다.

 

위의 예에서는 세 번만 해시하면 되었습니다. Merkle 증명이 없었다면 우리는 그것을 7번 해야 했을 것입니다. 오늘날 블록에는 수천 개의 트랜잭션이 포함되어 있기 때문에 Merkle 증명을 사용하면 많은 시간과 컴퓨팅 리소스를 절약할 수 있습니다.

 

마무리 생각

Merkle 트리는 다양한 컴퓨터 과학 응용 프로그램에서 매우 유용하다는 것이 입증되었습니다. 우리가 본 것처럼 블록체인에서 매우 가치가 있습니다. 분산 시스템에서 Merkle 트리를 사용하면 불필요한 데이터로 네트워크를 플러딩하지 않고 정보를 쉽게 확인할 수 있습니다.

 

머클 트리(및 머클 루트)가 없으면 비트코인 ​​및 기타 암호화폐의 블록이 오늘날처럼 작지 않을 것입니다. 또한 라이트 클라이언트는 개인 정보 보호 및 보안 면에서 부족하지만 Merkle 증명을 통해 사용자는 최소한의 오버헤드로 트랜잭션이 블록에 포함되었는지 확인할 수 있습니다.