Съдържание
Концепцията за дърво на Merkle е предложена в началото на 80-те от Ралф Меркъл – компютърен учен, известен с работата си върху
криптографията с публичен ключ.
Дървото на Merkle е структура, използвана за ефикасна проверка на целостта на данните в набор. Те са особено интересни в контекста на
peer-to-peer мрежи, където участниците трябва да споделят и независимо потвърждават информация.
Хеш функциите са в основата на структурите на дърветата на Merkle, така че ви препоръчваме да разгледате
Какво е хеширане?, преди да продължите.
Да предположим, че искате да изтеглите голям файл. При
софтуер с отворен код обикновено бихте искали да проверите дали хешът на файла, който сте изтеглили, съвпада с този, който е направен публичен от разработчиците. Ако е така, вие знаете, че файлът, който имате на вашия компютър, е точно същият като техния.
Ако хешовете не съвпадат, имате проблем. Или сте изтеглили злонамерен файл, маскиран като софтуер, или той не е изтеглен правилно и следователно няма да работи. Ако е последното, вероятно няма да сте много доволни, ако трябва да изчакате известно време, докато файлът се изтегля. Сега трябва да рестартирате процеса и да се надявате, че няма да се повреди отново.
Само ако имаше по-лесен начин за това, си мислите вие. За щастие, тук идват дърветата на Merkle. С един от тях файлът ви ще бъде раздробен на парчета. Ако е файл от 50 GB, можете да го разделите на сто части, така че всяка да е с размер 0,5 GB. След това ще бъде изтеглен парче по парче. Това по същество правите, когато използвате торент файлове.
В този случай вашият източник ще ви е предоставил хеш, известен като корен на Merkle. Този единичен хеш е представяне на всяка част от данни, която съставя вашия файл. Но коренът на Merkle прави много по-лесно проверката на данните.
За да бъде просто, нека вземем пример, в който използваме 8 GB файл, разбит на осем части. Наречете различните фрагменти от A до H. След това всеки фрагмент се предава през хеш функция, което ни дава осем различни хеша.
Преминаваме всеки от нашите осем фрагмента през хеш функция, за да получим техните хешове.
Добре, значи имаме нещо, което има малко повече смисъл. Имаме хеша на всички фрагменти, така че ако някой е дефектен, ще разберем, като го сравним с този на източника, нали? Възможно е, но това също е невероятно неефективно. Ако вашият файл има хиляди фрагменти, наистина ли ще хеширате всички от тях и щателно ще сравните резултатите?
Не. Вместо това ще вземем всеки чифт хешове, ще ги комбинираме, след което ще ги хешираме заедно. Така че хешираме hA + hB , hC + hD , hE + hF и hG + hH. В крайна сметка получаваме четири хеша. След това правим още един кръг на хеширане с тези, за да завършим с две. Накрая хешираме останалите две, за да стигнем до нашия главен хеш – коренът на Merkle (или коренов хеш).
Структурата прилича на обърнато с главата надолу дърво. В долния ред имаме листата, които се комбинират, за да се получат възлите и накрая коренът.
Вече имаме корен на Merkle, който представлява файла, който изтеглихме. Можем да сравним този коренов хеш с този, предоставен от източника. Ако съвпада, перфектно! Но ако хешовете са различни, можем да сме сигурни, че данните са променени. С други думи, един или повече фрагменти са създали различен хеш. Така че всяка лека промяна на данните ще ни даде напълно различен корен на Merkle.
За щастие има удобен начин да проверим кой фрагмент е дефектен. В нашия случай, нека да кажем, че е hE. Можете да започнете, като попитате peer за двата хеша, които са създали корена на Merkle ( hABCD и hEFGH ). Вашата стойност hABCD трябва да съвпада с тяхната, тъй като няма грешка в това поддърво. Но hEFGH няма, така че знаете да проверите там. След това поисквате hEF и hGH и ги сравнявате с вашите. hGH ще изглежда добре, така че знаете, че hEF е нашият виновник. На последно място, да сравните хешовете на hE и HF. Вече знаете, че hE е неправилен, така че можете да изтеглите отново този фрагмент.
Обобщавайки всичко това, дървото на Merkle се създава чрез разделяне на данни на много части, които след това се хешират многократно, за да образуват корена на Merkle. След това можете ефективно да проверите дали нещо се е объркало с част от данните. Както ще видим в следващия раздел, има и други интересни приложения.
Искате да започнете с криптовалута? Купете биткойн в Binance!
Има няколко случая на използване на дърветата на Merkle, но тук ще се съсредоточим върху тяхното значение в
блокчейните. Дърветата на Merkle са от съществено значение в
биткойн и много други криптовалути. Те са неразделна част от всеки
блок, където могат да бъдат намерени в
хедърите на блока. За да получим листата за нашето дърво, ние използваме хеша на трансакцията (
TXID ) на всяка трансакция, включена в блока.
Коренът на Merkle служи за няколко цели в този случай. Нека да разгледаме неговите приложения при копаене на криптовалута и потвърждение на трансакции.
Копаене
Един биткойн блок се състои от две части. Първата част е хедърът на блока, сегмент с фиксиран размер, съдържащ
метаданни за блока. Втората част е списък с трансакции, чийто размер е променлив, но има тенденция да бъде много по-голям от хедъра.
Копачите трябва многократно да хешират данни, за да произведат изход, който съответства на определени условия, за да копаят валиден блок. Те могат да направят трилиони опити, преди да намерят такъв. При всеки опит те променят произволно число в хедъра на блока (
nonce), за да произведат различен резултат. Но голяма част от блока остава непроменена. Може да има хиляди трансакции и все пак ще трябва да ги хеширате всеки път.
Коренът на Merkle опростява процеса значително. Когато започнете да копаете, вие подреждате всички трансакции, които искате да включите, и изграждате дърво на Merkle. Поставяте получения главен хеш (32 байта) в хедъра на блока. След това, когато копаете, трябва да хеширате само хедъра на блока, вместо целия блок.
Това работи, защото е защитено от подправяне. Вие ефективно обобщавате всички трансакции на блока в компактен формат. Не можете да намерите валиден хедър на блока и по-късно да промените списъка с трансакции, защото това би променило корена на Merkle. Когато блокът се изпраща до други възли, те изчисляват корена от списъка с трансакции. Ако не съвпада с този в хедъра, те отхвърлят блока.
Проверка
Има още едно интересно свойство на корените на Merkle, което можем да използваме. Това се отнася до леките клиенти (възли, които не държат пълно копие на блокчейна). Ако използвате възел на устройство с ограничени ресурси, не искате да изтегляте и хеширате всички трансакции на блок. Това, което можете да направите вместо това, е просто да поискате доказателство за Merkle – доказателство, предоставено от пълния възел, което доказва, че вашата трансакция е в определен блок. Това е по-често наричано опростена проверка на плащането или SPV и е описано подробно от
Сатоши Накамото в бялата книга за биткойн.
За да проверим hD, се нуждаем само от хешовете, показани в червено.
Помислете за сценария, при който искаме да знаем информация за трансакцията, чийто TXID е hD. Ако ни се предостави hC, можем да изчислим hCD. След това се нуждаем от hAB, за да изчислим hABCD. И накрая, с hEFGH можем да проверим дали полученият корен на Merkle съвпада с този от хедъра на блока. Ако е така, това е доказателство, че трансакцията е била включена в блока – би било почти невъзможно да се създаде един и същ хеш с различни данни.
В горния пример трябваше да хешираме само три пъти. Без доказателство за Merkle би трябвало да го направим седем пъти. Тъй като в днешно време блоковете съдържат хиляди трансакции, използването на доказателства на Merkle ни спестява много време и изчислителни ресурси.
Дърветата на Merkle са се доказали като много полезни в редица приложения в областта на компютърните науки – както видяхме, те са невероятно ценни в блокчейна. В разпределените системи дърветата на Merkle позволяват лесна проверка на информацията, без да се наводнява мрежата с ненужни данни.
Без дърветата на Merkle (и корените на Merkle), блоковете на
биткойн и други
криптовалути не биха били толкова компактни, колкото са днес. И докато липсват леки клиенти по отношение на поверителността и сигурността, доказателствата на Merkle позволяват на потребителите да проверят дали техните трансакции са включени в блок с минимални разходи.
