Listen to this article

머클나무

Merkle tree
이진 해시 트리의 예입니다.해시 0-0과 0-1은 각각 데이터 블록 L1과 L2의 해시 값이며, 해시 0은 해시 0-0과 0-1의 연결 해시입니다.

암호화 및 컴퓨터 과학에서 해시 트리 또는 Merkle 트리(Merkle tree)는 모든 "리프"(노드)에 데이터 블록의 암호화 해시를, 리프(브랜치, 내부 노드 또는 inode라고 함)가 아닌 모든 노드는 하위 노드의 라벨의 암호화 해시를 사용하여 라벨링되는 트리입니다.해시 트리는 대규모 데이터 구조의 내용을 효율적이고 안전하게 검증할 수 있도록 합니다.해시 트리는 해시 목록과 해시 체인을 일반화한 것입니다.

리프 노드가 주어진 바이너리 해시 트리의 일부임을 증명하려면 트리 [1]내의 리프 노드 수의 대수에 비례하는 해시 수를 계산해야 합니다.반대로 해시 리스트에서는 리프 노드 수에 비례합니다.따라서 Merkle 트리는 암호화 커밋 스킴의 효율적인 예입니다.이 스킴에서는 트리의 뿌리가 커밋으로 간주되어 리프 노드가 원래의 커밋의[citation needed] 일부임을 밝혀낼 수 있습니다.

해시 트리의 개념은 [2][3]1979년에 특허를 취득한 랄프 머클의 이름을 따서 붙여졌다.

사용하다

해시 트리를 사용하여 컴퓨터 내 및 컴퓨터 간에 저장, 처리 및 전송되는 모든 종류의 데이터를 확인할 수 있습니다.피어 투 피어 네트워크내의 다른 피어로부터 수신한 데이터 블록이 파손되지 않고 변경되지 않은 상태로 수신되는 것을 확인할 수 있습니다.또, 다른 피어가 거짓말을 하지 않고 가짜 블록을 송신하지 않는 것을 확인할 수도 있습니다.

해시 트리는 해시 기반 암호화에 사용됩니다.해시 트리는 IPFS, Btrfs 및 ZFS 파일[4] 시스템에서도 사용됩니다(데이터[5] 열화에 대응).Dat 프로토콜, 아파치 웨이브 프로토콜,[6]Git과 머큐리얼, Tahoe-LAFS 백업 시스템 버전 관리 시스템 분산, Zeronet, 비트 코인과 Ethereum 피어 투 피어 네트워크,[7]은 인증서 투명성 체계;GNUGuix 같은 닉스 패키지 매니저와 자손이다.[8]과 아파치 카산드라, Riak, D 같은 NoSQL 시스템을 많이ynamo.[9]신뢰할 수 있는 컴퓨팅 [10]시스템에서 해시 트리를 사용하는 것이 제안되었습니다.

나카모토 사토시의 초기 Merkle 트리 실장은 해시 함수의 압축 단계를 과도하게 적용하여 Fast Merkle [11]Tree를 사용함으로써 완화합니다.

개요

해시 트리는 예를 들어 파일 또는 파일 집합의 데이터 블록의 해시가 되는 리프(리프 노드, "리프"라고도 합니다.트리의 더 위쪽에 있는 노드는 각각의 자녀의 해시입니다.예를 들어 위 그림에서 해시 0은 해시 0-0과 해시 0-1을 연결한 결과입니다.즉, 해시 0 = 해시(hash(0-0) + hash(0-1))입니다.+는 연결을 나타냅니다.

대부분의 해시 트리 구현은 바이너리(각 노드 아래에 2개의 하위 노드)이지만 각 노드 아래에 더 많은 하위 노드를 사용할 수 있습니다.

보통 해시에는 SHA-2 등의 암호화 해시 함수가 사용됩니다.해시 트리가 의도하지 않은 손상을 방지하기 위해서만 필요한 경우 CRC 등의 안전하지 않은 체크섬을 사용할 수 있습니다.

해시 트리의 맨 위에는 상위 해시(또는 루트 해시 또는 마스터 해시)가 있습니다.대부분의 경우 p2p 네트워크에서 파일을 다운로드하기 전에 top 해시를 신뢰할 수 있는 소스(예를 들어 다운로드해야 할 파일의 권장 사항이 있는 친구나 웹 사이트)에서 가져옵니다.상위 해시를 사용할 수 있는 경우 해시 트리는 p2p 네트워크 내의 피어처럼 신뢰할 수 없는 소스로부터 수신할 수 있습니다.그런 다음 수신된 해시 트리가 신뢰할 수 있는 상위 해시에 대해 확인되며, 해시 트리가 손상되거나 가짜일 경우 프로그램이 상위 [12]해시와 일치하는 해시 트리를 찾을 때까지 다른 소스로부터의 다른 해시 트리가 시도됩니다.

해시 리스트와의 주요 차이점은 해시 트리의 브랜치를 한 번에 하나씩 다운로드할 수 있으며 트리 전체를 아직 사용할 수 없는 경우에도 각 브랜치의 무결성을 즉시 확인할 수 있다는 것입니다.예를 들어 그림에서 데이터 블록에 해시 0-0과 해시 1이 이미 포함되어 있으면 즉시 데이터 블록 L2의 무결성을 검증할 수 있으며, 그 결과를 해시 0-0과 해시 1로 반복 조합하여 최종적으로 상위 해시 1과 비교한다.마찬가지로 데이터 블록 L3의 무결성은 트리에 해시 1-1과 해시 0이 이미 있는 경우 검증할 수 있습니다.이는 파일을 매우 작은 데이터 블록으로 분할하는 것이 효율적이기 때문에 손상 시 작은 블록만 다시 다운로드해야 하기 때문에 이점이 될 수 있습니다.해시 파일이 매우 크면 이러한 해시 트리 또는 해시 목록이 상당히 커집니다.그러나 트리의 경우 작은 브랜치 하나를 빠르게 다운로드하고 브랜치의 무결성을 체크한 후 데이터 블록 [citation needed]다운로드를 시작할 수 있습니다.

두 번째 프리이미지 공격

Merkle 해시 루트는 트리 깊이를 나타내지 않으므로 공격자가 동일한 Merkle 해시 루트를 가진 원본이 아닌 다른 문서를 만드는 두 번째 미리 이미지 공격을 사용할 수 있습니다.위의 예에서 공격자는 두 개의 데이터 블록을 포함하는 새 문서를 만들 수 있습니다. 첫 번째 데이터 블록은 해시 0-0 + 해시 0-1이고 두 번째 데이터 블록은 해시 1-0 + 해시 1-1입니다.[13][14]

Certificate Transparency에는 간단한 수정이 정의되어 있습니다.리프 노드 해시를 계산할 때는 해시 데이터 앞에 0x00 바이트가 추가되고 내부 노드 [12]해시를 계산할 때는 0x01 바이트가 추가됩니다.해시 트리 크기를 제한하는 것은 일부 정식 보안 증명의 전제 조건이며, 일부 증빙을 강화하는 데 도움이 됩니다.일부 구현에서는 해시 전에 해시 트리 깊이 프리픽스를 사용하여 트리 깊이를 제한하기 때문에 추출된 해시 체인은 각 단계에서 프리픽스가 감소하고 리프 도달 시에도 유효한 것으로 정의됩니다.

호랑이나무해시

타이거 트리 해시는 널리 사용되는 해시 트리입니다.바이너리 해시 트리(각 노드 아래에 2개의 하위 노드)를 사용하며 일반적으로 1024바이트의 데이터 블록 크기를 가지며 Tiger [15]해시를 사용합니다.

Tiger 트리 해시는 [16]Gnutella, Gnutella2, Direct Connect P2P[17] 파일 공유 프로토콜 및 Pex,[18] BearShare, LimeWire, Shareaza, DC++[19][20] 및 gtk-gnutella와 같은 파일 공유 애플리케이션에서 사용됩니다.

예

베이스32:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

URN:urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

자석:magnet:?xt=urn:tree:tiger:R5T6Y8UYRYO5SUXGER5NMUOEZ5O6E4BHPP2MRFQ

「 」를 참조해 주세요.

레퍼런스

  1. ^ Becker, Georg (2008-07-18). "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis" (PDF). Ruhr-Universität Bochum. p. 16. Retrieved 2013-11-20.
  2. ^ Merkle, R. C. (1988). "A Digital Signature Based on a Conventional Encryption Function". Advances in Cryptology — CRYPTO '87. Lecture Notes in Computer Science. Vol. 293. pp. 369–378. doi:10.1007/3-540-48184-2_32. ISBN 978-3-540-18796-7.
  3. ^ 미국 특허 4309569 Ralph Merkle, 1982년 1월 5일 발행, Leland Stanford Junior University 이사회에 할당
  4. ^ Bonwick, Jeff. "ZFS End-to-End Data Integrity". Jeff Bonwick's Blog.
  5. ^ Likai Liu. "Bitrot Resistance on a Single Drive". likai.org.
  6. ^ "General Verifiable Federation". Google Wave Protocol. Archived from the original on 2018-04-08. Retrieved 2017-03-09.
  7. ^ Koblitz, Neal; Menezes, Alfred J. (January 2016). "Cryptocash, cryptocurrencies, and cryptocontracts". Designs, Codes and Cryptography. 78 (1): 87–102. CiteSeerX 10.1.1.701.8721. doi:10.1007/s10623-015-0148-5. S2CID 16594958.
  8. ^ 돌스트라, E순수하게 기능하는 소프트웨어 도입 모델.네덜란드 위트레흐트, 과학부 박사 학위 논문.2006년 1월 페이지 21 ISBN 90-393-4130-3.
  9. ^ Adam Marcus. "The NoSQL Ecosystem". aosabook.org. When a replica is down for an extended period of time, or the machine storing hinted handoffs for an unavailable replica goes down as well, replicas must synchronize from one another. In this case, Cassandra and Riak implement a Dynamo-inspired process called anti-entropy. In anti-entropy, replicas exchange Merkle trees to identify parts of their replicated key ranges which are out of sync. A Merkle tree is a hierarchical hash verification: if the hash over the entire keyspace is not the same between two replicas, they will exchange hashes of smaller and smaller portions of the replicated keyspace until the out-of-sync keys are identified. This approach reduces unnecessary data transfer between replicas which contain mostly similar data.
  10. ^ Kilian, J. (1995). "Improved efficient arguments (preliminary version)" (PDF). CRYPTO. doi:10.1007/3-540-44750-4_25.
  11. ^ 마크 프리든바흐: 패스트 머클 트리
  12. ^ a b Laurie, B.; Langley, A.; Kasper, E. (June 2013). "Certificate Transparency". IETF: RFC6962. doi:10.17487/rfc6962.
  13. ^ Elena Andreeva; Charles Bouillaguet; Orr Dunkelman; John Kelsey (January 2009). "Herding, Second Preimage and Trojan Message Attacks beyond Merkle–Damgård". Selected Areas in Cryptography. Lecture Notes in Computer Science. Vol. 5867. SAC. pp. 393–414. doi:10.1007/978-3-642-05445-7_25. ISBN 978-3-642-05443-3.
  14. ^ Elena Andreeva; Charles Bouillaguet; Pierre-Alain Fouque; Jonathan J. Hoch; John Kelsey; Adi Shamir; Sebastien Zimmer (2008). "Second Preimage Attacks on Dithered Hash Functions". In Smart, Nigel (ed.). Advances in Cryptology – EUROCRYPT 2008. Lecture Notes in Computer Science. Vol. 4965. Istanbul, Turkey. pp. 270–288. doi:10.1007/978-3-540-78967-3_16. ISBN 978-3-540-78966-6.
  15. ^ Chapweske, J.; Mohr, G. (March 4, 2003). "Tree Hash EXchange format (THEX)". Archived from the original on 2009-08-03.
  16. ^ "tigertree.c File Reference". Gtk-Gnutella. Retrieved 23 September 2018.
  17. ^ "Audit: P2P DirectConnect Application". Symantec. Retrieved 23 September 2018.
  18. ^ Arne Babenhauserheide (7 Jan 2007). "Phex 3.0.0 released". Phex. Retrieved 23 September 2018.
  19. ^ "DC++'s feature list". dcplusplus.sourceforge.net.
  20. ^ "Development". GTK-Gnutella. Retrieved 23 September 2018.

추가 정보

외부 링크

이 기사 듣기 (5분)
Spoken Wikipedia icon
이 오디오 파일은 2013년 9월 17일(2013-09-17) 본 문서의 개정판에서 작성되었으며 이후 편집 내용은 반영되지 않습니다.
(오디오 도움말, 기타 음성 기사)