맨위로가기

해시 트리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

해시 트리는 트리 구조의 일종으로, 파일 등의 데이터를 잎 노드에 저장하고, 각 상위 노드는 자식 노드들의 해시 값으로 구성된다. 데이터의 무결성을 검증하기 위해 사용되며, 특히 P2P 네트워크에서 데이터 변조를 방지하는 데 활용된다. 타이거 트리 해시는 널리 사용되는 해시 트리의 한 종류이며, 비트토렌트, ZFS 파일 시스템, 비트코인 등 다양한 분야에서 사용된다. 랄프 머클이 1979년에 발명했으며, 램포트 서명을 효율적으로 관리하기 위해 개발되었다.

더 읽어볼만한 페이지

  • 트리 구조 - 덴드로그램
    덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다.
  • 트리 구조 - 프림 알고리즘
    프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.
  • 오류 검출 정정 - 부호 이론
    부호 이론은 정보를 효율적으로 표현하고 오류를 감지 및 수정하는 기술을 연구하며, 소스 부호화, 채널 부호화, 암호 부호화 등으로 발전하여 CD, 모뎀, 휴대폰 등 다양한 분야에 응용된다.
  • 오류 검출 정정 - 비터비 알고리즘
    비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.
  • 암호화 해시 함수 - RIPEMD
    RIPEMD는 MD4를 기반으로 1992년 설계된 암호화 해시 함수로, 보안 취약점 보완을 위해 RIPEMD-128, RIPEMD-160, RIPEMD-256, RIPEMD-320 등의 변형이 개발되었으며, 특히 RIPEMD-160은 160비트 해시 값을 생성하고 다양한 라이브러리에서 지원되지만 보안성 우려가 제기되고 있다.
  • 암호화 해시 함수 - MD5
    MD5는 로널드 리베스트 교수가 개발한 128비트 해시 값 생성 암호화 해시 함수이나, 보안 취약점으로 인해 현재는 보안이 중요한 분야에서는 사용이 중단되었다.
해시 트리
정의
유형자료 구조
정의각 노드가 자식 노드를 2개 이하로 갖는 트리 자료 구조
특징
활용 분야디지털 서명
데이터 무결성 검증
데이터 동기화
암호화폐 (예: 비트코인)
구조루트 노드 (root node)
리프 노드 (leaf node)
중간 노드 (intermediate node)
생성 과정

보안
장점데이터 위변조 방지, 효율적인 데이터 검증
공격 유형제2원상 공격 (second preimage attack)
구현
예시머클-다미고르드 구조
관련 알고리즘해시 함수

2. 구조

해시 트리는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다. 예를 들어 해시 0은 해시 0-0과 해시 0-1을 연결한 문자열을 다시 해시 함수로 계산한 것이다. 해시 함수는 이진 트리를 사용할 수도 있지만, 임의의 차수를 가진 트리에서도 사용 가능하다.

해시 함수는 어떤 것이든 사용할 수 있지만, 보통 SHA-1, 타이거, 월풀 등의 암호화 해시 함수가 사용된다. 그러나 해시 트리를 사용하는 목적이 악의적인 공격자의 데이터 변조를 막으려는 것이 아니라, 단순히 오류를 찾기 위한 경우, CRC 등의 안전하지 않은 함수를 사용할 수도 있다.

데이터를 검증하고자 하는 사용자는 루트 노드의 해시 값('''루트 해시''' 또는 '''마스터 해시'''라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다.

또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다. 이런 특징 때문에 만약 일부 데이터가 손상될 경우 어떤 데이터가 손상되었는지를 쉽게 찾아내어 손상된 데이터를 다시 전송받을 수 있는 장점이 있다. 예를 들어 데이터 2번이 손상되었다면, 해시 0-1과 해시 0, 그리고 루트 해시가 달라지고 다른 값들은 달라지지 않는다. 따라서 대량의 데이터가 있을 경우에도 손상된 데이터를 빠르게 찾아낼 수 있다.

2. 1. 이진 해시 트리

해시 트리는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다. 예를 들어 해시 0은 해시 0-0과 해시 0-1을 연결한 문자열을 다시 해시 함수로 계산한 것이다. 해시 함수는 이진 트리를 사용할 수도 있지만, 임의의 차수를 가진 트리에서도 사용 가능하다.

해시 함수는 어떤 것이든 사용할 수 있지만, 보통 SHA-1, 타이거, 월풀 등의 암호화 해시 함수가 사용된다. 그러나 해시 트리를 사용하는 목적이 악의적인 공격자의 데이터 변조를 막으려는 것이 아니라, 단순히 오류를 찾기 위한 경우, CRC 등의 안전하지 않은 함수를 사용할 수도 있다.

데이터를 검증하고자 하는 사용자는 루트 노드의 해시 값('''루트 해시''' 또는 '''마스터 해시'''라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다.

또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다. 이런 특징 때문에 만약 일부 데이터가 손상될 경우 어떤 데이터가 손상되었는지를 쉽게 찾아내어 손상된 데이터를 다시 전송받을 수 있는 장점이 있다. 예를 들어 데이터 2번이 손상되었다면, 해시 0-1과 해시 0, 그리고 루트 해시가 달라지고 다른 값들은 달라지지 않는다. 따라서 대량의 데이터가 있을 경우에도 손상된 데이터를 빠르게 찾아낼 수 있다.

타이거 트리 해시는 널리 사용되는 형태의 해시 트리이다. 이진 해시 트리(각 노드 아래에 두 개의 자식 노드)를 사용하며, 일반적으로 데이터 블록 크기는 1024 바이트이고, 타이거 해시를 사용한다.[16]

타이거 트리 해시는 그누텔라,[17] 그누텔라2, 다이렉트 커넥트 P2P 파일 공유 프로토콜[18] 및 파일 공유 애플리케이션인 펙스,[19] 베어쉐어, 라임와이어, 쉐어자, DC++[20] 및 gtk-gnutella에서 사용된다.[21]

2. 2. 일반적인 해시 트리

해시 트리는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다. 예를 들어 해시 0은 해시 0-0과 해시 0-1을 연결한 문자열을 다시 해시 함수로 계산한 것이다. 해시 함수는 이진 트리를 사용할 수도 있지만, 임의의 차수를 가진 트리에서도 사용 가능하다.

해시 함수는 어떤 것이든 사용할 수 있지만, 보통 SHA-1, 타이거, 월풀 등의 암호화 해시 함수가 사용된다. 그러나 해시 트리를 사용하는 목적이 악의적인 공격자의 데이터 변조를 막으려는 것이 아니라, 단순히 오류를 찾기 위한 경우, CRC 등의 안전하지 않은 함수를 사용할 수도 있다.

데이터를 검증하고자 하는 사용자는 루트 노드의 해시 값('''루트 해시''' 또는 '''마스터 해시'''라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다.

또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다. 이런 특징 때문에 만약 일부 데이터가 손상될 경우 어떤 데이터가 손상되었는지를 쉽게 찾아내어 손상된 데이터를 다시 전송받을 수 있는 장점이 있다. 예를 들어 데이터 2번이 손상되었다면, 해시 0-1과 해시 0, 그리고 루트 해시가 달라지고 다른 값들은 달라지지 않을 것이다. 따라서 대량의 데이터가 있을 경우에도 손상된 데이터를 빠르게 찾아낼 수 있다.

2. 3. 해시 함수

해시 트리는 트리 구조의 일종으로, 잎 노드는 파일 등의 데이터를 가리킨다. 상위 노드는 각각 자식 노드들의 해시 값이 된다. 예를 들어 해시 0은 해시 0-0과 해시 0-1을 연결한 문자열을 다시 해시 함수로 계산한 것이다. 해시 함수는 이진 트리를 사용할 수도 있지만, 임의의 차수를 가진 트리에서도 사용 가능하다.

해시 함수는 어떤 것이든 사용할 수 있지만, 보통 SHA-1, 타이거, 월풀 등의 암호화 해시 함수가 사용된다. 그러나 해시 트리를 사용하는 목적이 악의적인 공격자의 데이터 변조를 막으려는 것이 아니라, 단순히 오류를 찾기 위한 경우, CRC 등의 안전하지 않은 함수를 사용할 수도 있다.

데이터를 검증하고자 하는 사용자는 루트 노드의 해시 값('''루트 해시''' 또는 '''마스터 해시'''라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다.

또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다.

2. 4. 루트 해시

해시 트리를 검증하고자 하는 사용자는 루트 노드의 해시 값(루트 해시 또는 마스터 해시라고 부른다)만 알면 데이터가 옳은 데이터인지 검증할 수 있다. 또한 데이터 전체가 아닌 일부만 검증하고자 할 때에도 자식 노드 가운데 하나의 해시 값을 알면 그 노드의 모든 자식 노드에 대해 데이터를 검증할 수 있는 특징이 있다.

3. 동작 원리

해시 트리는 노드에 해시 값을 가진 이진 트리이며, 잎 부분에는 데이터 블록(파일이나 파일을 분할한 것 등)의 해시 값이 들어 있다. 잎보다 상위의 노드에는 각각의 자식 노드의 해시 값이 들어 있다. 예를 들어, ''hash 0''에는, ''hash 0-0''과 ''hash 0-1''을 결합한 결과의 해시 값이 들어 있다. 즉, ''hash 0 = hash(hash 0-0 || hash 0-1)''이 된다(여기서 ||는 문자열 결합의 의미).

많은 해시 트리의 구현은 이진 트리(각 노드가 많아야 2개의 자식 노드를 가짐)이지만, 각 노드가 그보다 많은 자식 노드를 가지도록 할 수도 있다.

일반적으로 해시 함수에는 SHA-1, Whirlpool, Tiger와 같은 암호학적 해시 함수가 사용된다. 또한, 의도하지 않은 데이터 손상에 대한 보호만을 목적으로 해시 트리를 사용하는 경우라면, CRC 등의 더 보안성이 낮은 체크섬을 사용해도 좋다.

해시 트리의 루트에는 ''탑 해시''(top hash)(또는 ''루트 해시''(root hash), ''마스터 해시''(master hash))가 저장된다. P2P 네트워크에서 파일 다운로드를 시작하기 전에는 신뢰할 수 있는 정보원(예를 들어 친구나, 탑 해시 다운로드를 위해 권장되는 웹사이트 등)에서 탑 해시를 얻도록 하는 경우가 많다. 탑 해시만 이용 가능하다면, 해시 트리 자체는 어디에서 얻든 상관없으며, 예를 들어 P2P 네트워크의 피어와 같은 신뢰할 수 없는 정보원으로부터 얻어도 좋다. 다음으로, 신뢰할 수 있는 탑 해시를 사용하여, 얻은 해시 트리의 검사를 수행하고, 해시 트리가 손상되었거나 가짜인 경우에는 다른 정보원에서 해시 트리를 얻는다. 프로그램은 탑 해시에 의한 검사가 통과될 때까지 이를 반복하면 된다.

해시 리스트와의 주요 차이점은, 해시 트리의 일부분의 가지 만을 다운로드할 수 있으며, 또한 해시 트리의 전체를 이용할 수 없더라도 가지의 완전성을 검사할 수 있다는 점에 있다. 예를 들어, ''data block 001''의 완전성을 검사하려면, 해시 트리에 ''hash 0-0''과 ''hash 1''만 포함되어 있으면 된다(''data block 001''의 해시 값과 ''hash 0-0''의 값을 조합하고, 다음으로 ''hash 1''의 값과 조합하면 탑 해시의 값과 비교가 가능하다). 마찬가지로, ''data block 002''의 완전성을 검사하려면 ''hash 1-1''과 ''hash 0''의 값이 있으면 된다. 이 특징을 이용하여, 파일을 매우 작은 블록으로 분할해 두고, 블록이 손상되었으면 재다운로드하도록 하면 효율적으로 처리가 가능하다. 해시화 대상의 파일이 매우 큰 경우, 해시 트리나 해시 리스트의 크기는 그에 따라 커지지만, 해시 트리라면 일부분의 작은 가지 만을 다운로드할 수 있고, 가지의 완전성 체크가 가능하며, 데이터 블록의 다운로드를 즉시 시작할 수 있다.

3. 1. 부분 검증

3. 2. 손상된 데이터 식별

3. 3. Second preimage attack 방지

두 번째 프리이미지 공격은 공격자가 원본과 다른 문서를 생성하여 동일한 머클 해시 루트를 갖도록 하는 공격이다. 머클 해시 루트는 트리 깊이를 나타내지 않기 때문에 이러한 공격이 가능하다. 예를 들어, 공격자는 두 개의 데이터 블록을 포함하는 새로운 문서를 생성할 수 있는데, 첫 번째 블록은 ''해시 0-0'' + ''해시 0-1''이고, 두 번째 블록은 ''해시 1-0'' + ''해시 1-1''이다.

인증 투명성에 정의된 한 가지 간단한 해결 방법은 리프 노드 해시를 계산할 때 해시 데이터 앞에 0x00 바이트를 추가하고, 내부 노드 해시를 계산할 때는 0x01을 추가하는 것이다. 해시 트리 크기를 제한하는 것은 일부 공식 보안 증명의 전제 조건이며, 일부 증명을 더 강력하게 만드는 데 도움이 된다. 일부 구현에서는 해시 앞에 해시 트리 깊이 접두사를 사용하여 트리 깊이를 제한하므로, 추출된 해시 체인은 접두사가 각 단계에서 감소하고 리프에 도달했을 때 여전히 양수일 경우에만 유효한 것으로 정의된다.

4. 용도

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용한다.[27] 또한 구글 웨이브 프로토콜[28] 이나 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,[29] 비트토렌트 프로토콜 등에서도 사용된다.

발명자 랄프 머클은 여러 개의 램포트 서명을 효율적으로 다루기 위해 해시 트리를 개발했다.[30] 램포트 서명은 양자 컴퓨터가 실용화되어도 안전할 것으로 예상되는 디지털 서명 알고리즘이지만, 한개의 메시지마다 새로운 키를 생성해야 하는 단점이 있다. 여러 개의 램포트 키를 해시 트리로 묶으면 보다 효율적으로 다룰 수 있다. 이런 방식을 머클 서명이라고 부른다.

해시 트리는 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는 데 사용될 수 있다. 해시 트리는 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

해시 트리는 다음에서 사용된다.


신뢰 컴퓨팅 시스템에서 해시 트리를 사용할 것을 제안했다.[11]

사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12]

해시 트리는 단독 또는 여러 컴퓨터에서 저장, 처리, 전송되는 임의의 데이터의 검증 처리에 이용할 수 있다. 현재 주요 용도로는, P2P 네트워크에서 다른 피어로부터 수신한 데이터 블록이 손상되거나 변조되지 않았는지, 혹은 다른 피어가 가짜 데이터 블록을 전송하지 않았는지와 같은 검증 처리가 있다. 또한, 해시 트리를 신뢰 컴퓨팅에 사용하는 제안도 이루어지고 있다. 구체적인 사용 예로는, 썬 마이크로시스템즈(Sun Microsystems)가 ZFS에 해시 트리를 사용하고 있다.[22] 이 외에도, 해시 트리는 구글 웨이브(Google Wave)Apache Wave 프로토콜[23], 분산 버전 관리 시스템 Git, 백업 시스템 Tahoe-LAFS, 비트코인의 P2P 네트워크, 아파치 카산드라(Apache Cassandra) 및 Riak와 같은 NoSQL 시스템[24]에서 사용되고 있다.

해시 트리는 1979년에 랄프 머클(Ralph Merkle)에 의해 발명되었다.[25] 원래의 목적은 대량의 람포트 서명을 효율적으로 처리하는 것이었다. 람포트 서명은 양자 컴퓨터가 실현되어도 여전히 안전성을 유지할 수 있다고 여겨지지만, 하나의 키는 하나의 메시지 서명에만 사용할 수 있다는 제약이 있다. 여기서, 람포트 서명을 해시 트리와 결합하면, 하나의 키를 여러 메시지에 사용할 수 있게 되어, 효율적인 디지털 서명 체계를 구축할 수 있다.

4. 1. P2P 네트워크

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용한다.[27] 또한 구글 웨이브 프로토콜[28] 이나 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,[29] 비트토렌트 프로토콜 등에서도 사용된다.

해시 트리는 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는 데 사용될 수 있다. 해시 트리는 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

해시 트리는 IPFS(InterPlanetary File System), 비트토렌트, Btrfs 및 ZFS 파일 시스템[5]( 데이터 열화 방지[6]), Dat 프로토콜, 아파치 웨이브 프로토콜,[7] Git 및 Mercurial 분산 버전 관리 시스템, Tahoe-LAFS 백업 시스템, 제로넷, 비트코인 및 이더리움 P2P 네트워크,[8] 인증 투명성 프레임워크, Nix 패키지 관리자 및 GNU Guix,[9] 아파치 카산드라, Riak, 다이나모와 같은 여러 NoSQL 시스템[10]에서 사용된다. 신뢰 컴퓨팅 시스템에서 해시 트리를 사용할 것을 제안했다.[11]

사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12] 해시 트리는 단독 또는 여러 컴퓨터에서 저장, 처리, 전송되는 임의의 데이터의 검증 처리에 이용할 수 있다. 현재 주요 용도로는, P2P 네트워크에서 다른 피어로부터 수신한 데이터 블록이 손상되거나 변조되지 않았는지, 혹은 다른 피어가 가짜 데이터 블록을 전송하지 않았는지와 같은 검증 처리가 있다. 또한, 해시 트리를 신뢰 컴퓨팅에 사용하는 제안도 이루어지고 있다.

4. 2. 파일 시스템

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 해시 트리는 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는 데 사용될 수 있으며, 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용한다.[27] 데이터 열화 방지를 위해 Btrfs 및 ZFS 파일 시스템에서 사용된다.[5][6] 또한 구글 웨이브 프로토콜[28][7] 이나 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,[29][8] 비트토렌트 프로토콜 등에서도 사용된다. 신뢰 컴퓨팅 시스템에서 해시 트리를 사용할 것을 제안했다.[11]

발명자 랄프 머클은 여러 개의 램포트 서명을 효율적으로 다루기 위해 해시 트리를 개발했다.[30][25] 램포트 서명은 양자 컴퓨터가 실용화되어도 안전할 것으로 예상되는 디지털 서명 알고리즘이지만, 한개의 메시지마다 새로운 키를 생성해야 하는 단점이 있다. 여러 개의 램포트 키를 해시 트리로 묶으면 보다 효율적으로 다룰 수 있다. 이런 방식을 머클 서명이라고 부른다. 사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12]

4. 3. 분산 버전 관리 시스템

해시 트리는 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용하며,[27] 구글 웨이브 프로토콜,[28] 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,[29] 비트토렌트 프로토콜 등에서도 사용된다.

해시 트리는 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는 데 사용될 수 있다. 해시 트리는 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

해시 트리는 IPFS(InterPlanetary File System), 비트토렌트, Btrfs 및 ZFS 파일 시스템[5](데이터 열화 방지[6]), Dat 프로토콜, 아파치 웨이브 프로토콜,[7] Git 및 Mercurial 분산 버전 관리 시스템, Tahoe-LAFS 백업 시스템, 제로넷, 비트코인 및 이더리움 P2P 네트워크,[8] 인증 투명성 프레임워크, Nix 패키지 관리자 및 GNU Guix,[9] 아파치 카산드라, Riak, 다이나모와 같은 여러 NoSQL 시스템[10]에서 사용된다. 신뢰 컴퓨팅 시스템에서 해시 트리를 사용할 것을 제안했다.[11]

사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12]

4. 4. 블록체인

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 데 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용하며,[27] 구글 웨이브 프로토콜[28][7], 깃 버전 관리 시스템, 비트코인 및 이더리움 암호 통화 시스템,[29][8] 비트토렌트 프로토콜 등에서도 사용된다.

해시 트리는 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12] 해시 트리는 P2P 네트워크에서 다른 피어로부터 수신한 데이터 블록이 손상되거나 변조되지 않았는지, 혹은 다른 피어가 가짜 데이터 블록을 전송하지 않았는지와 같은 검증 처리에 사용된다. 또한 신뢰 컴퓨팅에 사용하는 제안도 이루어지고 있다.[11]

4. 5. 기타

해시 트리는 여러 블록으로 나뉜 데이터를 전송할 때 데이터가 변조되지 않았음을 보장하는 용도로 사용된다. 특히 P2P 망에서 전송받은 데이터에 오류가 있거나 악의적인 데이터 변조가 있는지를 검증하는 용도로 사용된다.[27] 썬 마이크로시스템즈에서 개발한 ZFS 파일 시스템에서 해시 트리를 사용하며,[27] 구글 웨이브 프로토콜,[28][7] 깃 버전 관리 시스템, 비트코인 암호 통화 시스템,[29] 비트토렌트 프로토콜 등에서도 사용된다.

해시 트리는 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 검증하는 데 사용될 수 있다. 블록체인에서 P2P 네트워크의 다른 피어로부터 수신된 블록이 손상되지 않고 변경되지 않았는지 확인하고, 다른 피어가 거짓말을 하고 가짜 블록을 보내지 않는지 확인하는 데 도움을 줄 수 있다.

해시 트리는 해시 기반 암호화에 사용된다. 또한, IPFS(InterPlanetary File System), 비트토렌트, Btrfs 및 ZFS 파일 시스템([5] 데이터 열화 방지[6]), Dat 프로토콜, Git 및 Mercurial 분산 버전 관리 시스템(엄밀히 말하면 방향 비순환 그래프를 사용하지만 트리는 아님), Tahoe-LAFS 백업 시스템, 제로넷, 비트코인 및 이더리움 P2P 네트워크,[8] 인증 투명성 프레임워크, Nix 패키지 관리자 및 GNU Guix와 같은 파생 제품,[9] 아파치 카산드라, Riak, 다이나모와 같은 여러 NoSQL 시스템[10]에서 사용된다. 신뢰 컴퓨팅 시스템에서 해시 트리를 사용할 것을 제안했다.[11]

사토시 나카모토가 처음 구현한 비트코인에서 머클 트리는 해시 함수의 압축 단계를 과도하게 적용했는데, 이는 고속 머클 트리를 사용하여 완화된다.[12]

발명자 랄프 머클(Ralph Merkle)은 여러 개의 램포트 서명을 효율적으로 다루기 위해 해시 트리를 개발했다.[30] 램포트 서명은 양자 컴퓨터가 실용화되어도 안전할 것으로 예상되는 디지털 서명 알고리즘이지만, 한개의 메시지마다 새로운 키를 생성해야 하는 단점이 있다. 여러 개의 램포트 키를 해시 트리로 묶으면 보다 효율적으로 다룰 수 있다. 이런 방식을 머클 서명이라고 부른다. 해시 트리는 1979년에 랄프 머클(Ralph Merkle)에 의해 발명되었다.[25]

4. 6. 머클 서명

해시 트리는 1979년에 랄프 머클이 발명했다.[25] 원래 목적은 대량의 람포트 서명을 효율적으로 처리하기 위한 것이었다. 람포트 서명은 양자 컴퓨터가 실현되어도 안전성을 유지할 수 있다고 여겨지지만, 하나의 키는 하나의 메시지 서명에만 사용할 수 있다는 제약이 있다. 람포트 서명을 해시 트리와 결합하면, 하나의 키를 여러 메시지에 사용할 수 있게 되어, 효율적인 디지털 서명 체계를 구축할 수 있다. [https://www.google.com/patents/US4309569 머클 트리에 관한 특허]에서는 여러 개의 일회용 서명을 효율적으로 다루는 방법을 설명한다.

5. Tiger Tree Hash

타이거 트리 해시(Tiger Tree Hash, TTH)는 널리 사용되는 해시 트리의 한 형태이다. 이진 해시 트리(각 노드 아래에 두 개의 자식 노드)를 사용하며, 일반적으로 데이터 블록 크기는 1024 바이트이고, 타이거 해시를 사용한다.[16]

타이거 트리 해시는 그누텔라,[17] 그누텔라2, 다이렉트 커넥트 P2P 파일 공유 프로토콜[18] 및 파일 공유 애플리케이션인 펙스,[19] 베어쉐어, 라임와이어, 쉐어자, DC++[20][26] 및 gtk-gnutella에서 사용된다.[21]

참조

[1] 웹사이트 Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis http://www.emsec.rub[...] Ruhr-Universität Bochum 2008-07-18
[2] 웹사이트 Handbook of Applied Cryptography https://cacr.uwaterl[...] 2024-03-07
[3] 서적 Advances in Cryptology – CRYPTO '87
[4] 특허 Method of providing digital signatures
[5] 웹사이트 ZFS End-to-End Data Integrity https://blogs.oracle[...] 2005-12-08
[6] 웹사이트 Bitrot Resistance on a Single Drive http://lifecs.likai.[...]
[7] 웹사이트 General Verifiable Federation http://www.waveproto[...] 2017-03-09
[8] 간행물 Cryptocash, cryptocurrencies, and cryptocontracts 2016-01
[9] 문서 The Purely Functional Software Deployment Model. https://nixos.org/~e[...] 2006-01
[10] 웹사이트 The NoSQL Ecosystem http://www.aosabook.[...]
[11] 간행물 Improved efficient arguments (preliminary version) https://link.springe[...] 1995
[12] 문서 Fast Merkle Trees https://github.com/b[...]
[13] 간행물 Certificate Transparency https://www.rfc-edit[...] 2013-06
[14] 서적 Selected Areas in Cryptography SAC 2009-01
[15] 서적 Advances in Cryptology – EUROCRYPT 2008 2008
[16] 웹사이트 Tree Hash EXchange format (THEX) http://open-content.[...] 2003-03-04
[17] 웹사이트 tigertree.c File Reference http://gtk-gnutella.[...] 2018-09-23
[18] 웹사이트 Audit: P2P DirectConnect Application https://www.symantec[...] 2018-09-23
[19] 웹사이트 Phex 3.0.0 released http://www.phex.org/[...] 2007-01-07
[20] 웹사이트 DC++'s feature list http://dcplusplus.so[...]
[21] 웹사이트 Development http://gtk-gnutella.[...] 2018-09-23
[22] 문서 ZFS End-to-End Data Integrity http://blogs.sun.com[...]
[23] 문서 Wave Protocol Verification Paper' http://www.waveproto[...]
[24] 문서 http://www.aosabook.[...]
[25] 문서 A digital signature based on a conventional encryption function
[26] 문서 DC++'s feature list http://dcplusplus.so[...]
[27] 웹인용 ZFS End-to-End Data Integrity https://blogs.oracle[...] 2005-12-08
[28] 웹인용 General Verifiable Federation http://www.waveproto[...] 2009-05-27
[29] 웹인용 Bitcoin: A Peer-to-Peer Electronic Cash System http://bitcoin.org/b[...] 2013-08-28
[30] 저널 인용 http://www.cse.mssta[...] 2013-08-28


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com