Merkletræer

Merkletræer, eller hash-træer, er datastrukturer som bruges til at verificere integriteten og sammenhængen af store datasæt på en effektiv måde. Bladene i et Merkletræ repræsenterer individuelle dataenheder (for eksempel blokke eller transaktioner), og hvert indre knudpunkt er hash-værdien af dets to underliggende børn. Roden af træet opsummerer hele datasættet i en enkelt hashværdi.

Opbygningen gør det muligt at teste, om en given datapunkt er en del af datasættet ved hjælp af et Merkle-bevis. Beviset består af de hash-værdier, der ligger langs stien fra bladet til roden. Ved at kombinere disse værdier kan man verificere medlemskab uden at skulle hente hele datasættet, hvilket kræver logaritmisk tid og minimal kommunikation.

Konventionelle detaljer kan variere mellem implementeringer. Ved ulige antal blade kan parringen tilpasses ved duplikation af det sidste blad eller gennem en standardiseret policy for håndtering af ulige niveauer, og valgte hash-funktioner påvirker sikkerheden og ydeevnen.

Anvendelser: i kryptografiske blok-kæder som Bitcoin og Ethereum bruges Merkletræer til at gruppere transaktioner i en blok, hvilket gør det muligt at verificere enkelte transaktioner uden at downloade hele blokken. Git og andre versionsstyringssystemer bruger lignende hash-træstrukturer til at spore ændringer og sikre dataintegritet. Merkletræer er også brugt i distribuerede filsystemer og peer-to-peer netværk for effektiv dataverifikation.

Historie: Merkletræet er opkaldt efter Ralph C. Merkle, der beskrev det i 1980’erne. Ideen giver en måde at bevise medlemskab og integritet af store datasæt uden fuld gennemsyn.