Экзотические структуры данных: Modified Merkle Patricia Trie

[Xop]

Ну, эта структура данных используется не только Etherium и не только в криптовалютах. Один из примеров — Hyperledger Indy.

[Jigglypuff]

Справедливо. Однако, я, вроде бы, не указывал, что кроме как в Ethereum эта структура данных не используется нигде. Ethereum — насколько мне известно — источник, не более. Просто так вышло, что лично я познакомился с ней благодаря данному проекту. Именно поэтому в повествовании упоминается Ethereum.

В exonum, например, Merkle Patricia Trie тоже используется — однако там оно несколько видоизменено. В частности, ветвление там именно бинарное, а также не используется RLP.

Тем не менее, идея в основе лежит та же: бинарное KV-хранилище, имеющее возможность подтвердить наличие тех или иных данных.

В итоге именно тот факт, что это не one-shot структура, целиком и полностью направленная на нужды сугубо одного проекта, и побудил меня написать эту статью. Кто знает — возможно в будущем кто-то решит, что и для его проекта нужно нечто подобное, и моя статья станет ему подспорьем в этом нелегком деле :)

[Xop]

Учитывая хайп вокруг криптовалют у неподготовленного читателя после упоминания Etherium и не упоминания других проектов вообще может сложиться впечатление, что «аа, опять эти криптовалюты», хотя сфера применения этой структуры данных гораздо шире, поэтому и решил все-таки оставить комментарий. А заодно порадовать автора (ну, классная статья же, и ни одного комментария), и попутно чуть попиарить свой любимый проект.

[Jigglypuff]

Мне всё же хочется надеяться, что на Хабре среднестатистический читать достаточно подготовлен. В любом случае, спасибо на добром слове!

[yleo]

IMHO никакой экзотики. Хотя для blockchain-поколения возможно так и выглядит )

Кстати, RLP — это MessagePack сломанный в духе «назло бабушке уши отморожу».
А первый blockchain — это git, буквально.

[Jigglypuff]

По поводу RLP и git — всё так :)

А по поводу наличия или отстутствия экзотики — это ж всё относительно. Мне показалось, что раз информации на хабре о MPT нет, то это достаточно экзотично.

[ratijas]

Для тех, кто только сейчас заметил, что "trie" это не «tier» и не «tree»:

Tries were first described by René de la Briandais in 1959. The term trie was coined two years later by Edward Fredkin, who pronounces it /ˈtriː/ (as «tree»), after the middle syllable of retrieval. However, other authors pronounce it /ˈtraɪ/ (as «try»), in an attempt to distinguish it verbally from «tree».