Tiivistepuu
Merkle-puu eli tiivistepuu on tietorakenne, joka sisältää kryptografisia tiivisteitä. Tiivistepuussa jokainen välisolmu on tiiviste sen alisolmuista ja lopullinen lehtisolmu on tiiviste alkuperäisestä tiedosta. Yksittäinen tiiviste koskee vain pientä osaa tiedosta.[1][2][3][4]
Ralph C. Merkle käytti menetelmää digitaalisten allekirjoituksien menetelmässään, jossa yhdellä avaimella allekirjoitetaan useita viestejä, ja patentoi menetelmän. Patentti myönnettiin vuonna 1982 ja se vanheni vuonna 1999.[5][6][7][8][4][9]
Käyttökohteita
[muokkaa | muokkaa wikitekstiä]Merkle-puuta käytetään muun muassa fs-verity -mekanismissa. Tavalliseen tiivisteeseen verrattuna puurakenne on tehokkaampi kun tiedosto on suuri ja siitä käytetään vain pientä osaa.[10][11][12]
Ehdotettu X.509:n uusi muoto Merkle Tree Certificates perustuu Merkle-puun käyttöön.[13]
Merkle-puun käyttäjiä ovat muun muassa lohkoketjut kryptovaluutoissa.[14][15] Myös BitTorrent käyttää tiivistepuuta tiedostojen osien tarkistamiseen.[16]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Graham Cox; Grzegorz Piwowarek: How Do Merkle Trees Work? baeldung.com. 18.3.2024. Viitattu 24.6.2026. (englanniksi)
- ↑ Alin Tomescu: What is a Merkle Tree? decentralizedthoughts.github.io. 22.12.2020. Viitattu 24.6.2026. (englanniksi)
- ↑ Introduction to Merkle Tree geeksforgeeks.org. 3.5.2024. Viitattu 24.6.2026. (englanniksi)
- 1 2 Georg Becker: Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis (PDF) Arkistoitu Viitattu 24.6.2026. (englanniksi)
- ↑ Bibliographic data: US4309569 (A) ― 1982-01-05 worldwide.espacenet.com. Viitattu 24.6.2026. (englanniksi)
- ↑ Method of providing digital signatures patents.google.com. Viitattu 24.6.2026. (englanniksi)
- ↑ Ralph C. Merkle: Protocols for Public Key Cryptosystems ieeexplore.ieee.org. huhtikuu 1980. doi:10.1109/SP.1980.10006 Viitattu 24.6.2026. (englanniksi)
- ↑ Ralph C. Merkle: Protocols for Public Key Cryptosystems researchgate.net. huhtikuu 1980. doi:10.1109/SP.1980.10006 Viitattu 24.6.2026. (englanniksi)
- ↑ Ralph C. Merkle: A Certified Digital Signature (Brassard, G. (eds) Advances in Cryptology — CRYPTO’ 89 Proceedings. CRYPTO 1989. Lecture Notes in Computer Science, vol 435.) link.springer.com. 1990. doi:10.1007/0-387-34805-0_21 Viitattu 24.6.2026. (englanniksi)
- ↑ fs-verity: read-only file-based authenticity protection docs.kernel.org. Viitattu 25.6.2026. (englanniksi)
- ↑ Jonathan Corbet: Protecting files with fs-verity lwn.net. 30.8.2018. Viitattu 25.6.2026. (englanniksi)
- ↑ fs-verity (PDF) events19.linuxfoundation.org. Viitattu 25.6.2026. (englanniksi)
- ↑ Merkle Tree Certificates datatracker.ietf.org. Viitattu 25.6.2026. (englanniksi)
- ↑ Matteo Loporchio; Anna Bernasconi; Damiano Di Francesco Maesa; Laura Ricci: A survey of set accumulators for blockchain systems sciencedirect.com. elokuu 2021. doi:10.1016/j.cosrev.2023.100570 Viitattu 24.6.2026. (englanniksi)
- ↑ Haojun Liu; Xinbo Luo; Hongrui Liu; Xubo Xia: Merkle Tree: A Fundamental Component of Blockchains ieeexplore.ieee.org. syyskuu 2021. doi:10.1109/EIECS53707.2021.9588047 Viitattu 24.6.2026. (englanniksi)
- ↑ What are hash trees and why you should care (PDF) accu.org. Viitattu 25.6.2026. (englanniksi)