Какво е Merkle Tree? Ръководство за начинаещи за този блокчейн компонент

Merkle Trees са основен компонент на блокчейните, които са в основата на тяхната функционалност. Те позволяват ефективна и сигурна проверка на големи структури от данни, а в случай на блокови вериги, потенциално безгранични набори от данни.

Внедряването на Merkle дървета в блокчейни има множество ефекти. Позволява им да мащабират, като същевременно им предоставя базирана на хеш архитектура, за да поддържат целостта на данните и тривиален начин за проверка на целостта на данните.

Криптографските хеш функции са основната технология, която позволява на Merkle дърветата да работят, така че първо е важно да разберете какво представляват криптографските хеш функции.

Бърза присъда: Дърветата на Merkle са структури от данни, съставени от криптографски хешове, които позволяват ефективна проверка на целостта и картографиране на големи набори от данни, което ги прави неразделен компонент на системи като блокчейн и контрол на разпределените версии.

Бързи факти

Криптографски хеш функции

Просто казано, хеш функция е всяка функция, която се използва за съпоставяне на данни с произволен размер (вход) към изход с фиксиран размер. Алгоритъм за хеширане се прилага към входните данни и полученият изход с фиксирана дължина се нарича хеш.

Много хеширащи алгоритми са широко достъпни и могат да бъдат избрани въз основа на вашите нужди.

Полученият хеш от произволния вход е не само с фиксирана дължина, но и напълно уникален за входа, а самата функция е детерминистична. Тоест, без значение колко пъти изпълнявате функцията на един и същ вход, изходът винаги ще бъде същият.

Например, ако имате следните набори от данни по-долу като вход, получените резултати са уникални за всеки вход. Забележете как във втория и третия пример, въпреки че разликата на входовете е само една дума, получените изходи са напълно различни.

Това е много важно, тъй като позволява „пръстови отпечатъци“ на данни.

Криптографска хеш функция, изображение от Wikipedia

Тъй като дължината на изхода (хеш-сумата в примера) винаги е същата, както е определена от използвания алгоритъм за хеширане, огромни количества данни могат да бъдат идентифицирани единствено чрез получения им хеш.

Със системи, които съдържат огромни количества данни, предимствата от възможността за съхраняване и идентифициране на данни с изход с фиксирана дължина могат да създадат огромни спестявания при съхранение и да помогнат за повишаване на ефективността.

В рамките на блокчейните се използват хеширащи алгоритми за определяне на състоянието на блокчейна.

Блоковите вериги са свързани списъци, които съдържат данни и хеш указател, който сочи към предишния блок, създавайки верига от свързани блокове, оттук и името „блокова верига“.

Всеки блок е свързан един с друг чрез хеш указател, който е хешът на данните в предишния блок заедно с адреса на предишния блок. Чрез свързване на блокове от данни в този формат, всеки получен хеш на предишния блок представлява цялото състояние на блокчейна, тъй като всички хеширани данни на предишните блокове се хешират в един хеш.

Това е представено (в случая на алгоритъма SHA-256) чрез изход (хеш), като този:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Хешът по-горе е пръстовият отпечатък на цялото състояние на блокчейна преди него. Състоянието на блокчейна преди новия блок (като хеширани данни) е входът, а полученият хеш е изходът.

Въпреки че е възможно да се използват криптографски хешове без Merkle дървета, това е изключително неефективно и не може да се мащабира. Използването на хешове за съхраняване на данни в блок във формат на серия отнема време и е тромаво.

Както ще видите, дърветата на Merkle позволяват тривиално разрешаване на целостта на данните, както и картографиране на тези данни през цялото дърво с помощта на доказателства на Merkle.

Merkle Trees и Merkle Proofs

Наименувани на Ралф Меркъл, който патентова концепцията през 1979 г., дърветата на Меркъл в основата си са дървета със структура от данни, където всеки възел, който не е лист, е хеш на съответните дъщерни възли.

Листните възли са най-ниското ниво от възли в дървото. В началото може да звучи трудно за разбиране, но ако погледнете често използваната фигура по-долу, ще стане много по-лесно за разбиране.

Пример за двоично хеш дърво, Изображение от Wikipedia

Важно е да забележите как нелистните възли или „клонове“ (представени от хеш 0-0 и хеш 0-1) от лявата страна са хешове на съответните им деца L1 и L2. Освен това забележете как клонът Hash 0 е хешът на неговите свързани деца, клонове Hash 0-0 и Hash 0-1.

Примерът по-горе е най-често срещаната и проста форма на дърво на Merkle, известно като двоично дърво на Merkle. Както можете да видите, има горен хеш, който е хешът на цялото дърво, известен като коренния хеш. По същество дърветата на Merkle са структура от данни, която може да приеме „n“ брой хешове и да ги представи с един хеш.

Структурата на дървото позволява ефективно картографиране на произволно големи количества данни и позволява лесно идентифициране на това къде се случват промени в тези данни. Тази концепция позволява доказателства на Merkle, с които някой може да провери дали хеширането на данни е последователно по целия път нагоре в дървото и в правилната позиция, без да се налага действително да разглежда целия набор от хешове.

Вместо това те могат да проверят дали дадена част от данните е в съответствие с основния хеш, като проверяват само малка част от хешовете, а не целия набор от данни.

Докато основният хеш е публично известен и надежден, е възможно всеки, който иска да направи търсене на ключ-стойност в база данни, да използва доказателство на Merkle, за да провери позицията и целостта на част от данните в база данни, която има определен корен.

Когато основният хеш е наличен, хеш дървото може да бъде получено от всеки ненадежден източник и един клон на дървото може да бъде изтеглен наведнъж с незабавна проверка на целостта на данните, дори ако цялото дърво все още не е налично.

Едно от най-важните предимства на дървовидната структура на Merkle е възможността за удостоверяване на произволно големи набори от данни чрез подобен механизъм за хеширане, който се използва за проверка на много по-малки количества данни.

Дървото е полезно за разпределяне на големи набори от данни в управляеми по-малки части, където бариерата за проверка на целостта е значително намалена въпреки общия по-голям размер на данните.

Основният хеш може да се използва като пръстов отпечатък за цял набор от данни, включително цяла база данни или представяне на цялото състояние на блокова верига. В следващите раздели ще обсъдим как биткойн и други системи внедряват Merkle дървета.

Merkle Trees в биткойн

Криптографската хеш функция, използвана от биткойн, е алгоритъмът SHA-256. Това означава „сигурен хеширащ алгоритъм“, чийто изход е с фиксирана дължина от 256 бита. Основната функция на дърветата Merkle в биткойн е да съхраняват и евентуално да отрязват транзакциите във всеки блок.

Както бе споменато по-рано, блоковете в блокчейн са свързани чрез хешове на предишния блок. В Bitcoin всеки блок съдържа всички транзакции в този блок, както и заглавката на блока, която се състои от:

• Номер на версията на блока
• Предишен блок хеш
• Timestamp
• Цел за трудност при копаене
• дадения случай
• Merkle Root Hash

Изображението по-долу е от бялата книга на Биткойн и илюстрира как дървото Merkle се вписва във всеки блок.

Транзакциите се включват в блокове от миньори и се хешират като част от дърво на Merkle, което води до корена на Merkle, който се съхранява в заглавката на блока. Този дизайн има редица различни предимства.

Най-вече, както е посочено в бялата книга, това позволява съществуването на възли за проста проверка на плащането (SPV), известни също като „леки клиенти“. Тези възли не трябва да изтеглят целия биткойн блокчейн, а само блоковите заглавки на най-дългата верига.

SPV възлите могат да постигнат това, като отправят заявки към своите партньорски възли, докато не се убедят, че съхранените блокови заглавки, върху които работят, са част от най-дългата верига. SPV възел може след това да определи статуса на транзакция, като използва доказателството на Merkle, за да картографира транзакцията към конкретно дърво на Merkle с коренния хеш на съответното дърво на Merkle в заглавката на блока, която е част от най-дългата верига.

Освен това внедряването на Merkle дървета от Биткойн позволява съкращаване на блокчейна, за да се спести място. Това е резултат от това, че само коренният хеш се съхранява в заглавката на блока, следователно старите блокове могат да бъдат отрязани чрез премахване на ненужните клони на дървото на Merkle, като същевременно се запазят само тези, необходими за доказателството на Merkle.

Внедряване на Merkle Trees в други блокчейни и системи

Въпреки че биткойн беше първата блокчейн, която внедри Merkle дървета, много други блокчейни внедряват подобни Merkle дървовидни структури или дори по-сложни версии.

Освен това внедряването на Merkle дърво не е ограничено само до блокчейни и се прилага към различни други системи.

Ethereum, като другата най-разпознаваема криптовалута, също е чудесен пример за внедряване на различно дърво на Merkle. Тъй като Ethereum е завършен като платформа за изграждане на много по-сложни приложения, той използва по-сложна версия на дървото Merkle, наречено Merkle Patricia Tree, което всъщност представлява 3 отделни дървета Merkle, използвани за три вида обекти. Можете да научите повече за тези дървета тук.

И накрая, дърветата на Merkle са важен компонент на разпределените системи за контрол на версиите като Git и IPFS. Способността им лесно да гарантират и проверяват целостта на данните, споделени между компютрите във формат P2P, ги прави безценни за тези системи.

Заключение

Дърветата Merkle са неразделен компонент на блокчейните и ефективно им позволяват да функционират с доказуема неизменност и цялост на транзакциите.

Разбирането на ролята, която те играят в разпределените мрежи и тяхната основна технология на криптографските хеш функции е от решаващо значение за разбирането на основните концепции в рамките на криптовалутите, тъй като те продължават да се развиват в по-големи и по-сложни системи.