Merkle-Patricia Trees. Часть 1
Вот и закончилась неделя продаж курса и мы возвращаемся в свое привычное русло!
Когда я пересматривал уроки модуля, где есть темы Древа Меркла, то вспомнил, что уже давно хотел рассмотреть новую для себя тему: Merkle-Patricia Trees. Именно поэтому на канале мы немного "подушним" и разберем, что это такое, как работает и какие проблемы могут возникнуть! Итак, поехали:
В сфере технологии блокчейн передовая структура данных, известная как дерево Меркл-Патриция, является ключевой частью инфраструктуры. Эта структура сочетает в себе свойства деревьев Меркла и деревьев Патриции, что позволяет создать высокоэффективную и безопасную модель представления и проверки данных. Хотя они ассоциируются в первую очередь с Ethereum, их полезность выходит далеко за рамки только этого блокчейна.
Деревья Меркл-Патриция играют важную роль в различных решениях второго уровня, сайдчейнах и других вопросах масштабируемости. Например, решения второго уровня, такие как Rollups, Plasma chains и state channels, используют эти структуры для создания компактных доказательств доступности данных и переходов между состояниями. Аналогичным образом, побочные цепи, представляющие собой отдельные сети блокчейна, предназначенные для работы рядом с основной цепью, также используют деревья Меркл-Патриция для обеспечения согласованности данных и безопасного взаимодействия.
Но что такое деревья Меркл-Патриция и почему они так важны для этих систем? Для того, чтобы ответить на эти и другие вопросы, давайте разберем эту концепцию по частям, изучим их свойства, применение и значение для поддержания безопасности и целостности экосистем блокчейн.
Кратко вспомним, что такое Древо Меркла
Древо Меркла - это разновидность структуры данных, используемой в вычислительной технике. Структура данных - это просто способ организации и хранения данных, чтобы их можно было эффективно использовать.
Давайте разложим определение дерева Меркла на более простые части:
1. Что такое древо в вычислительной технике? Представьте себе семейное дерево, где «предки» находятся вверху, а «потомки» - внизу. Дерево в вычислительной технике похоже на это. Оно начинается с единственного «корневого» узла наверху, который разветвляется на «дочерние» узлы, а каждый из них может иметь свои «дочерние» узлы, и так далее. Узлы в самом низу, у которых нет дочерних узлов, называются «листьями».
2. Что такое криптографический хэш? Хэш - это способ получить любой объем входных данных (например, предложение, документ или целую книгу) и создать из него строку символов фиксированного размера, которая выглядит случайной. Его особенность заключается в том, что любое небольшое изменение входных данных полностью изменит хэш, и вы не сможете вернуться от хэша к исходным данным.
Криптографические хэш-функции - это особые типы хэш-функций, которые отличаются особой безопасностью, то есть их очень сложно перевернуть или найти коллизии (это когда два разных входа дают один и тот же хэш).
3. Как строится дерево Меркла? Вы начинаете с блоков данных в нижней части дерева в качестве «листьев». Каждый из этих блоков данных превращается в хэш. Затем каждая пара этих хэшей объединяется и снова хэшируется, чтобы получить хэш для узла, расположенного над ними. Этот процесс продолжается вверх по дереву, пока не получится один хэш на вершине, который и является «корнем» дерева.
4. Для чего используется дерево Меркла? Деревья Меркла используются там, где нужно быстро и безопасно проверить данные. Например, они используются в технологии блокчейн (которая лежит в основе таких криптовалют, как Bitcoin), чтобы гарантировать, что все транзакции действительны, без необходимости проверять каждую из них.
По сути, деревья Меркла позволяют очень быстро и с высокой степенью достоверности проверить, является ли небольшой фрагмент данных частью большого набора данных. Если у вас есть верхний хэш и возможность двигаться вниз по дереву, вы можете проверить, входит ли часть данных в исходный набор данных, не имея всего набора данных.rd для реверсирования или поиска коллизий.
#merkle #patricia
Вот и закончилась неделя продаж курса и мы возвращаемся в свое привычное русло!
Когда я пересматривал уроки модуля, где есть темы Древа Меркла, то вспомнил, что уже давно хотел рассмотреть новую для себя тему: Merkle-Patricia Trees. Именно поэтому на канале мы немного "подушним" и разберем, что это такое, как работает и какие проблемы могут возникнуть! Итак, поехали:
В сфере технологии блокчейн передовая структура данных, известная как дерево Меркл-Патриция, является ключевой частью инфраструктуры. Эта структура сочетает в себе свойства деревьев Меркла и деревьев Патриции, что позволяет создать высокоэффективную и безопасную модель представления и проверки данных. Хотя они ассоциируются в первую очередь с Ethereum, их полезность выходит далеко за рамки только этого блокчейна.
Деревья Меркл-Патриция играют важную роль в различных решениях второго уровня, сайдчейнах и других вопросах масштабируемости. Например, решения второго уровня, такие как Rollups, Plasma chains и state channels, используют эти структуры для создания компактных доказательств доступности данных и переходов между состояниями. Аналогичным образом, побочные цепи, представляющие собой отдельные сети блокчейна, предназначенные для работы рядом с основной цепью, также используют деревья Меркл-Патриция для обеспечения согласованности данных и безопасного взаимодействия.
Но что такое деревья Меркл-Патриция и почему они так важны для этих систем? Для того, чтобы ответить на эти и другие вопросы, давайте разберем эту концепцию по частям, изучим их свойства, применение и значение для поддержания безопасности и целостности экосистем блокчейн.
Кратко вспомним, что такое Древо Меркла
Древо Меркла - это разновидность структуры данных, используемой в вычислительной технике. Структура данных - это просто способ организации и хранения данных, чтобы их можно было эффективно использовать.
Давайте разложим определение дерева Меркла на более простые части:
1. Что такое древо в вычислительной технике? Представьте себе семейное дерево, где «предки» находятся вверху, а «потомки» - внизу. Дерево в вычислительной технике похоже на это. Оно начинается с единственного «корневого» узла наверху, который разветвляется на «дочерние» узлы, а каждый из них может иметь свои «дочерние» узлы, и так далее. Узлы в самом низу, у которых нет дочерних узлов, называются «листьями».
2. Что такое криптографический хэш? Хэш - это способ получить любой объем входных данных (например, предложение, документ или целую книгу) и создать из него строку символов фиксированного размера, которая выглядит случайной. Его особенность заключается в том, что любое небольшое изменение входных данных полностью изменит хэш, и вы не сможете вернуться от хэша к исходным данным.
Криптографические хэш-функции - это особые типы хэш-функций, которые отличаются особой безопасностью, то есть их очень сложно перевернуть или найти коллизии (это когда два разных входа дают один и тот же хэш).
3. Как строится дерево Меркла? Вы начинаете с блоков данных в нижней части дерева в качестве «листьев». Каждый из этих блоков данных превращается в хэш. Затем каждая пара этих хэшей объединяется и снова хэшируется, чтобы получить хэш для узла, расположенного над ними. Этот процесс продолжается вверх по дереву, пока не получится один хэш на вершине, который и является «корнем» дерева.
4. Для чего используется дерево Меркла? Деревья Меркла используются там, где нужно быстро и безопасно проверить данные. Например, они используются в технологии блокчейн (которая лежит в основе таких криптовалют, как Bitcoin), чтобы гарантировать, что все транзакции действительны, без необходимости проверять каждую из них.
По сути, деревья Меркла позволяют очень быстро и с высокой степенью достоверности проверить, является ли небольшой фрагмент данных частью большого набора данных. Если у вас есть верхний хэш и возможность двигаться вниз по дереву, вы можете проверить, входит ли часть данных в исходный набор данных, не имея всего набора данных.rd для реверсирования или поиска коллизий.
#merkle #patricia
❤3
Merkle-Patricia Trees. Часть 2
1. Основная терминология в дереве Меркла:
- Листовые узлы являются самыми нижними узлами в дереве (у них нет дочерних узлов) и представляют собой блоки данных.
- Родительские узлы помечены криптографическим хэшем их дочерних узлов.
- Корневой узел (верхний узел дерева) известен как корень Меркла.
2. Построение дерева Меркла:
Пусть у нас есть 4 блока данных - L1, L2, L3 и L4.
Шаг 1: Начнем с получения криптографических хэшей блоков данных.
HL1 = Hash(L1)
HL2 = Hash(L2)
HL3 = Hash(L3)
HL4 = Hash(L4)
Здесь 'Hash' может быть любой криптографической хэш-функцией, например SHA256.
Шаг 2: Хэши объединяются в пары и конкатенируются, после чего вычисляется хэш полученной строки.
HL12 = Hash(HL1 + HL2)
HL34 = Hash(HL3 + HL4)
Здесь '+' означает конкатенацию.
Шаг 3: Эти хэши снова конкатенируются и хэшируются для получения корня.
ROOT = Hash(HL12 + HL34)
Этот ROOT является корнем нашего дерева Меркла.
Как и раньше, вы можете использовать это дерево для эффективной и безопасной проверки содержимого этих блоков данных. Процесс точно такой же, но с обновленными именами блоков.
#merkle #patricia
1. Основная терминология в дереве Меркла:
- Листовые узлы являются самыми нижними узлами в дереве (у них нет дочерних узлов) и представляют собой блоки данных.
- Родительские узлы помечены криптографическим хэшем их дочерних узлов.
- Корневой узел (верхний узел дерева) известен как корень Меркла.
2. Построение дерева Меркла:
Пусть у нас есть 4 блока данных - L1, L2, L3 и L4.
Шаг 1: Начнем с получения криптографических хэшей блоков данных.
HL1 = Hash(L1)
HL2 = Hash(L2)
HL3 = Hash(L3)
HL4 = Hash(L4)
Здесь 'Hash' может быть любой криптографической хэш-функцией, например SHA256.
Шаг 2: Хэши объединяются в пары и конкатенируются, после чего вычисляется хэш полученной строки.
HL12 = Hash(HL1 + HL2)
HL34 = Hash(HL3 + HL4)
Здесь '+' означает конкатенацию.
Шаг 3: Эти хэши снова конкатенируются и хэшируются для получения корня.
ROOT = Hash(HL12 + HL34)
Этот ROOT является корнем нашего дерева Меркла.
Как и раньше, вы можете использовать это дерево для эффективной и безопасной проверки содержимого этих блоков данных. Процесс точно такой же, но с обновленными именами блоков.
#merkle #patricia
❤1
Merkle-Patricia Trees. Часть 3
Что такое Trie?
Говоря простым языком, Trie - это особый тип дерева, используемый для хранения строк. То, что делает Trie интересным, так это то, как они организуют и хранят строки, позволяя быстро искать, вставлять и удалять их.
Как работает Trie?
Представьте, что у нас есть пустой Trie. Корень Trie не содержит никаких букв, но служит отправной точкой для хранения наших строк.
Начнем с первой строки «an».
1. Из корневого узла мы проверим, есть ли ветвь для первой буквы «a». В данном случае ее нет, поэтому мы создаем новый узел для «a».
2. Затем мы проверяем, есть ли ветвь для второй буквы «n», исходящая из узла «a». Поскольку ее нет, мы создаем еще один узел для «n».
Теперь наш Trie представляет слово «an».
Для того, чтобы добавить второе слово «ant», мы снова начинаем с корня:
1. Проверяем, есть ли ветвь для «a». На этот раз она уже существует, поэтому мы идем по ней.
2. Затем мы ищем ветвь для «n» от «a». Она также существует, поэтому мы идем по ней.
3. Наконец, мы ищем ответвление для «t» от «n». Ее не существует, поэтому мы добавляем новый узел для «t».
Теперь наша тройка содержит «an» и «ant».
1. Начиная с «dad», мы не находим ветви для «d» в корне, поэтому добавляем ее.
2. Мы не находим ветви для «a» от «d», поэтому добавляем ее.
3. Мы не находим ветви для «d» из «a», поэтому добавляем ее.
4. Для «do» у нас уже есть «d» в корне, поэтому мы следуем ему.
5. У нас нет ветви «o» от «d», поэтому мы добавляем ее.
Теперь наша тройка содержит «an», «ant», «dad» и «do».
Вот так мы создаем Trie! Если мы хотим проверить, входит ли слово в тройку, мы начинаем с корня и идем по ветвям, соответствующим буквам слова. Если мы можем сделать это, не заходя в тупик, значит, наше слово находится в Trie.
Таким образом, мы можем сделать вывод, что Trie хранит слова, разделяя между ними общие буквы. Эта общая структура позволяет эффективно хранить слова и быстро находить их.
Это базовое объяснение Trie. Продвинутые темы включают добавление маркера в конец каждого слова в Trie, чтобы различать, например, «an» и «ant» как отдельные слова.
#merkle #patricia
Что такое Trie?
Говоря простым языком, Trie - это особый тип дерева, используемый для хранения строк. То, что делает Trie интересным, так это то, как они организуют и хранят строки, позволяя быстро искать, вставлять и удалять их.
Как работает Trie?
Представьте, что у нас есть пустой Trie. Корень Trie не содержит никаких букв, но служит отправной точкой для хранения наших строк.
Начнем с первой строки «an».
1. Из корневого узла мы проверим, есть ли ветвь для первой буквы «a». В данном случае ее нет, поэтому мы создаем новый узел для «a».
2. Затем мы проверяем, есть ли ветвь для второй буквы «n», исходящая из узла «a». Поскольку ее нет, мы создаем еще один узел для «n».
Теперь наш Trie представляет слово «an».
Для того, чтобы добавить второе слово «ant», мы снова начинаем с корня:
1. Проверяем, есть ли ветвь для «a». На этот раз она уже существует, поэтому мы идем по ней.
2. Затем мы ищем ветвь для «n» от «a». Она также существует, поэтому мы идем по ней.
3. Наконец, мы ищем ответвление для «t» от «n». Ее не существует, поэтому мы добавляем новый узел для «t».
Теперь наша тройка содержит «an» и «ant».
1. Начиная с «dad», мы не находим ветви для «d» в корне, поэтому добавляем ее.
2. Мы не находим ветви для «a» от «d», поэтому добавляем ее.
3. Мы не находим ветви для «d» из «a», поэтому добавляем ее.
4. Для «do» у нас уже есть «d» в корне, поэтому мы следуем ему.
5. У нас нет ветви «o» от «d», поэтому мы добавляем ее.
Теперь наша тройка содержит «an», «ant», «dad» и «do».
Вот так мы создаем Trie! Если мы хотим проверить, входит ли слово в тройку, мы начинаем с корня и идем по ветвям, соответствующим буквам слова. Если мы можем сделать это, не заходя в тупик, значит, наше слово находится в Trie.
Таким образом, мы можем сделать вывод, что Trie хранит слова, разделяя между ними общие буквы. Эта общая структура позволяет эффективно хранить слова и быстро находить их.
Это базовое объяснение Trie. Продвинутые темы включают добавление маркера в конец каждого слова в Trie, чтобы различать, например, «an» и «ant» как отдельные слова.
#merkle #patricia
❤1
🔥 Популярный плагин для Solidity опасен?
Вчера в Твиттере встретил этот пост о том, что один из самых популярных плагинов для Solidity кода в VSCode может быть опасен:
https://x.com/LehmannLorenz/status/1841545179825942991
Пока еще отлеживаю информацию об этом, но, если вы вдруг используете его, то лучше отключить сейчас!
#vscode
Вчера в Твиттере встретил этот пост о том, что один из самых популярных плагинов для Solidity кода в VSCode может быть опасен:
https://x.com/LehmannLorenz/status/1841545179825942991
Пока еще отлеживаю информацию об этом, но, если вы вдруг используете его, то лучше отключить сейчас!
#vscode
😱6
Merkle-Patricia Trees. Часть 4
Что такое Patricia Trie?
Patricia Trie (также известная как Radix Tree или Compact Prefix Tree) - это тип Trie, в которую добавлены некоторые оптимизации для экономии места и потенциального повышения эффективности поиска. Название «Patricia» - это аббревиатура от «Практический алгоритм получения информации, закодированной в алфавитно-цифровом виде» (Practical Algorithm to Retrieve Information Coded in Alphanumeric).
Как работает Patricia Trie?
Patricia Trie отличается от стандартной Trie тем, что в ней сворачивается любой узел, имеющий только одного ребенка. Вместо того чтобы хранить в каждом узле один символ, Patricia Trie может хранить целые строки или их части, что значительно сокращает количество узлов.
Давайте посмотрим, как Patricia Trie обрабатывает слова: romane, romanus, romulus, rubens, ruber, rubicon, rubicundus.
Мы начинаем с пустого корневого узла. Затем мы начинаем добавлять слова:
1. Вставка слова «romane»: Trie в данный момент пуста, поэтому мы создаем новый узел, ответвляющийся от корня, который содержит строку «romane».
2. Вставка «romanus»: Мы замечаем, что «romanus» имеет общий префикс, «roman», с «romane». Поэтому мы создаем узел, ответвляющийся от «roman», который содержит суффикс «us». Мы также обновим существующую ветвь «romane», чтобы она теперь начиналась от «roman» и содержала суффикс «e».
3. Вставка «romulus»: Это слово имеет общий префикс «rom» с существующими словами. Поэтому мы добавляем ветвь от «rom», содержащую «ulus».
4. Вставка «rubens»: Это слово не имеет общей приставки с существующими словами, поэтому оно ответвляется непосредственно от корня.
5. Вставка «ruber»: «ruber» имеет общий префикс rub с rubens, поэтому мы создаем узел, ответвляющийся от rub, который содержит er. Ветвь «rubens» теперь также начинается от «rub» и содержит суффикс «ens».
6. Вставка «rubicon»: «rubicon» имеет общий префикс rubi с ruber, поэтому мы создаем узел, ответвляющийся от rubi, который содержит con.
7. Вставка «rubicundus»: Это слово имеет общий префикс «rubi» с остальными. Мы ответвляем от «rubi» и добавляем узел с «cundus».
Теперь наша Patricia Trie содержит все семь слов, каждое из которых имеет свой уникальный путь от корня. Trie эффективна, компактна и, по сравнению с обычной Trie, гораздо проще в обходе. Обратите внимание, что Patricia Trie значительно сокращает количество узлов и, следовательно, делает операции более эффективными, сворачивая узлы, имеющие только одного ребенка.
#merkle #patricia
Что такое Patricia Trie?
Patricia Trie (также известная как Radix Tree или Compact Prefix Tree) - это тип Trie, в которую добавлены некоторые оптимизации для экономии места и потенциального повышения эффективности поиска. Название «Patricia» - это аббревиатура от «Практический алгоритм получения информации, закодированной в алфавитно-цифровом виде» (Practical Algorithm to Retrieve Information Coded in Alphanumeric).
Как работает Patricia Trie?
Patricia Trie отличается от стандартной Trie тем, что в ней сворачивается любой узел, имеющий только одного ребенка. Вместо того чтобы хранить в каждом узле один символ, Patricia Trie может хранить целые строки или их части, что значительно сокращает количество узлов.
Давайте посмотрим, как Patricia Trie обрабатывает слова: romane, romanus, romulus, rubens, ruber, rubicon, rubicundus.
Мы начинаем с пустого корневого узла. Затем мы начинаем добавлять слова:
1. Вставка слова «romane»: Trie в данный момент пуста, поэтому мы создаем новый узел, ответвляющийся от корня, который содержит строку «romane».
2. Вставка «romanus»: Мы замечаем, что «romanus» имеет общий префикс, «roman», с «romane». Поэтому мы создаем узел, ответвляющийся от «roman», который содержит суффикс «us». Мы также обновим существующую ветвь «romane», чтобы она теперь начиналась от «roman» и содержала суффикс «e».
3. Вставка «romulus»: Это слово имеет общий префикс «rom» с существующими словами. Поэтому мы добавляем ветвь от «rom», содержащую «ulus».
4. Вставка «rubens»: Это слово не имеет общей приставки с существующими словами, поэтому оно ответвляется непосредственно от корня.
5. Вставка «ruber»: «ruber» имеет общий префикс rub с rubens, поэтому мы создаем узел, ответвляющийся от rub, который содержит er. Ветвь «rubens» теперь также начинается от «rub» и содержит суффикс «ens».
6. Вставка «rubicon»: «rubicon» имеет общий префикс rubi с ruber, поэтому мы создаем узел, ответвляющийся от rubi, который содержит con.
7. Вставка «rubicundus»: Это слово имеет общий префикс «rubi» с остальными. Мы ответвляем от «rubi» и добавляем узел с «cundus».
Теперь наша Patricia Trie содержит все семь слов, каждое из которых имеет свой уникальный путь от корня. Trie эффективна, компактна и, по сравнению с обычной Trie, гораздо проще в обходе. Обратите внимание, что Patricia Trie значительно сокращает количество узлов и, следовательно, делает операции более эффективными, сворачивая узлы, имеющие только одного ребенка.
#merkle #patricia
👍4❤2
Merkle-Patricia Trees. Часть 5
Новая неделя и новые душные посты про Патрицию!
Понимаю, многим интересны будут, скорее, посты про что-то базовое из Solidity, но я хотел бы на канале порой дальше двигаться с "мясными" темами, которые сложно найти где-либо еще. Поэтому недели на две мы еще продолжим говорить про деревья Меркл-Патриция, захватывая темы верификации и уязвимостей. Итак, продолжим.
На прошлой неделе мы поняли, что Patricia tree (также известное как «Радиксное дерево» или «Trie») - это особый тип структуры данных, которая используется для хранения набора строк. Строки разбиваются на отдельные символы, и дерево строится путем создания пути для каждой строки, где каждый символ образует узел на пути. Patricia tree особенно полезны для наборов данных, в которых префиксы строк значительно пересекаются.
В дереве Меркла-Патриция Ethereum каждый счет с сопутствующей информацией (такой как баланс счета, nonce, код контракта, если это контрактный счет, и хранилище) образует строку, которую необходимо сохранить.
Основными компонентами дерева Патриция являются:
1. Узел: Каждый узел в дереве представляет собой символ строки. В контексте Ethereum узел может быть частью адреса счета или другой информации о счете.
2. Грани: это связь между узлами. Ребро соединяет узел с последующим узлом.
3. Ключ: Это символ (или, в случае Ethereum, ниббл (nibble), то есть половина байта), который представляет узел.
4. Путь/префикс: Это последовательность символов (ключей) от корня дерева до определенного узла.
5. Корневой узел: Это начальная точка дерева. Все пути в дереве начинаются от корневого узла.
6. Листовой узел: Это конечные точки каждого пути. В Ethereum узел листьев обычно содержит состояние счета.
Как работает древо?
В Patricia tree каждый путь от корня до листового узла представляет собой строку из набора строк, которые хранит дерево. Символы строки являются ключами узлов, расположенных вдоль пути.
Для того, чтобы найти определенную строку в дереве, вы начинаете с корня и следуете по пути, который соответствует символам строки.
В Ethereum для хранения состояния используется модифицированная версия дерева Патриция, называемая «деревом Меркл-Патриция». В этом случае каждый путь от корня до узла листа представляет собой адрес аккаунта, а узел листа содержит состояние этого аккаунта.
А дальше переходим к совсем сложным объяснениям...
#merkle #patricia
Новая неделя и новые душные посты про Патрицию!
Понимаю, многим интересны будут, скорее, посты про что-то базовое из Solidity, но я хотел бы на канале порой дальше двигаться с "мясными" темами, которые сложно найти где-либо еще. Поэтому недели на две мы еще продолжим говорить про деревья Меркл-Патриция, захватывая темы верификации и уязвимостей. Итак, продолжим.
На прошлой неделе мы поняли, что Patricia tree (также известное как «Радиксное дерево» или «Trie») - это особый тип структуры данных, которая используется для хранения набора строк. Строки разбиваются на отдельные символы, и дерево строится путем создания пути для каждой строки, где каждый символ образует узел на пути. Patricia tree особенно полезны для наборов данных, в которых префиксы строк значительно пересекаются.
В дереве Меркла-Патриция Ethereum каждый счет с сопутствующей информацией (такой как баланс счета, nonce, код контракта, если это контрактный счет, и хранилище) образует строку, которую необходимо сохранить.
Основными компонентами дерева Патриция являются:
1. Узел: Каждый узел в дереве представляет собой символ строки. В контексте Ethereum узел может быть частью адреса счета или другой информации о счете.
2. Грани: это связь между узлами. Ребро соединяет узел с последующим узлом.
3. Ключ: Это символ (или, в случае Ethereum, ниббл (nibble), то есть половина байта), который представляет узел.
4. Путь/префикс: Это последовательность символов (ключей) от корня дерева до определенного узла.
5. Корневой узел: Это начальная точка дерева. Все пути в дереве начинаются от корневого узла.
6. Листовой узел: Это конечные точки каждого пути. В Ethereum узел листьев обычно содержит состояние счета.
Как работает древо?
В Patricia tree каждый путь от корня до листового узла представляет собой строку из набора строк, которые хранит дерево. Символы строки являются ключами узлов, расположенных вдоль пути.
Для того, чтобы найти определенную строку в дереве, вы начинаете с корня и следуете по пути, который соответствует символам строки.
В Ethereum для хранения состояния используется модифицированная версия дерева Патриция, называемая «деревом Меркл-Патриция». В этом случае каждый путь от корня до узла листа представляет собой адрес аккаунта, а узел листа содержит состояние этого аккаунта.
А дальше переходим к совсем сложным объяснениям...
#merkle #patricia
❤4
Merkle-Patricia Trees. Часть 6
Обход путей в Patricia Tree
Обход Patricia Tree начинается с корневого узла. Каждый путь от корневого узла к узлу листа дерева соответствует адресу учетной записи. Для того, чтобы обойти дерево и найти состояние конкретного счета, вы следуете по пути, который соответствует интересующему вас адресу счета.
Ключи узлов вдоль пути - это отдельные полубайты адреса счета. В случае Ethereum адреса имеют длину 20 байт, то есть их можно разбить на 40 полубайтов.
Например, если вы хотите найти состояние учетной записи с адресом 0xabcdef, вы начнете с корня и сначала перейдете к дочернему элементу, который соответствует полубайту 0xa. Оттуда вы перейдете к дочернему элементу, соответствующему 0xb, затем к 0xc, и так далее, пока не пройдете всю последовательность полубайтов 0xa, 0xb, 0xc, 0xd, 0xe, 0xf.
В конце этого пути вы придете к узлу листа, который содержит состояние счета с адресом 0xabcdef.
Patricia Tree в Ethereum различает два типа узлов: узлы листьев и узлы расширения. Кроме того, в этих узлах может храниться ключ с четным или нечетным количеством разрядов. Для указания типа и длины ключа используется двухбитный префикс. Возможными значениями префикса являются:
0x00: Узел расширения, четное количество полубайтов.
0x10: Узел расширения, нечетное количество полубайтов.
0x20: Листовой узел, четное количество полубайтов.
0x30: Листовой узел, нечетное количество полубайтов.
Расширяющие узлы служат внутренними узлами, которые помогают ориентироваться в дереве, а листовые узлы являются фактическими держателями данных.
Четное и нечетное количество полубайтов связано с тем, как хранится ключ. Ниббл - это четырехбитное объединение, или половина октета (octet или октет - это 8-битный байт). Ключи в Patricia Tree Ethereum представлены в виде шестнадцатеричных строк, где каждый шестнадцатеричный символ представляет собой ниббл (4 бита).
Когда мы говорим о «четном» или «нечетном» количестве нибблов, мы имеем в виду длину пути от корневого узла до конкретного узла. Если число полубайтов в пути четное, узел имеет четный префикс (0x00 для расширения, 0x20 для листа), а если число полубайтов нечетное, узел имеет нечетный префикс (0x10 для расширения, 0x30 для листа).
Эти префиксы играют ключевую роль в обеспечении эффективного обхода и манипулирования древовидной структурой. Например, если у вас есть хэш узла и вы хотите получить его данные из базы данных, вы можете расшифровать префикс, чтобы узнать, является ли узел расширением или узлом листа, а также четное или нечетное количество полубайтов в ключе. Обладая этой информацией, вы можете эффективно расшифровать ключ и значение и продолжить обход или манипулирование данными, как это необходимо.
Фух, это достаточно сложная тема, и, вероятнее всего, потребуется прочитать пост и рассмотреть графику несколько раз, чтобы понять всю суть.
#merkle #patricia
Обход путей в Patricia Tree
Обход Patricia Tree начинается с корневого узла. Каждый путь от корневого узла к узлу листа дерева соответствует адресу учетной записи. Для того, чтобы обойти дерево и найти состояние конкретного счета, вы следуете по пути, который соответствует интересующему вас адресу счета.
Ключи узлов вдоль пути - это отдельные полубайты адреса счета. В случае Ethereum адреса имеют длину 20 байт, то есть их можно разбить на 40 полубайтов.
Например, если вы хотите найти состояние учетной записи с адресом 0xabcdef, вы начнете с корня и сначала перейдете к дочернему элементу, который соответствует полубайту 0xa. Оттуда вы перейдете к дочернему элементу, соответствующему 0xb, затем к 0xc, и так далее, пока не пройдете всю последовательность полубайтов 0xa, 0xb, 0xc, 0xd, 0xe, 0xf.
В конце этого пути вы придете к узлу листа, который содержит состояние счета с адресом 0xabcdef.
Patricia Tree в Ethereum различает два типа узлов: узлы листьев и узлы расширения. Кроме того, в этих узлах может храниться ключ с четным или нечетным количеством разрядов. Для указания типа и длины ключа используется двухбитный префикс. Возможными значениями префикса являются:
0x00: Узел расширения, четное количество полубайтов.
0x10: Узел расширения, нечетное количество полубайтов.
0x20: Листовой узел, четное количество полубайтов.
0x30: Листовой узел, нечетное количество полубайтов.
Расширяющие узлы служат внутренними узлами, которые помогают ориентироваться в дереве, а листовые узлы являются фактическими держателями данных.
Четное и нечетное количество полубайтов связано с тем, как хранится ключ. Ниббл - это четырехбитное объединение, или половина октета (octet или октет - это 8-битный байт). Ключи в Patricia Tree Ethereum представлены в виде шестнадцатеричных строк, где каждый шестнадцатеричный символ представляет собой ниббл (4 бита).
Когда мы говорим о «четном» или «нечетном» количестве нибблов, мы имеем в виду длину пути от корневого узла до конкретного узла. Если число полубайтов в пути четное, узел имеет четный префикс (0x00 для расширения, 0x20 для листа), а если число полубайтов нечетное, узел имеет нечетный префикс (0x10 для расширения, 0x30 для листа).
Эти префиксы играют ключевую роль в обеспечении эффективного обхода и манипулирования древовидной структурой. Например, если у вас есть хэш узла и вы хотите получить его данные из базы данных, вы можете расшифровать префикс, чтобы узнать, является ли узел расширением или узлом листа, а также четное или нечетное количество полубайтов в ключе. Обладая этой информацией, вы можете эффективно расшифровать ключ и значение и продолжить обход или манипулирование данными, как это необходимо.
Фух, это достаточно сложная тема, и, вероятнее всего, потребуется прочитать пост и рассмотреть графику несколько раз, чтобы понять всю суть.
#merkle #patricia
❤4👍3🤯3🥰1
Merkle-Patricia Trees. Часть 7
Значения, хранящиеся в узле
Каждый узел в Patricia tree содержит ключ - символ, который этот узел представляет. В Ethereum такими ключами являются ниблы из адресов счетов. Однако листовые узлы в Merkle-Patricia Trees Ethereum хранят не только ключи, но и состояние соответствующего счета.
Состояние счета Ethereum включает в себя:
1. Nonce: Это число, обозначающее количество транзакций, отправленных с адреса учетной записи. Оно используется для предотвращения атак повторного воспроизведения.
2. Баланс: Это количество Ether, которым располагает аккаунт.
3. Корень хранилища: Для аккаунтов смарт-контрактов это корень другого дерева Меркла-Патриция, в котором хранится содержимое смарт-контракта. Каждый путь в этом дереве соответствует ключу хранения, а соответствующий листовой узел содержит значение хранения для этого ключа.
4. Хэш кода: Для аккаунтов смарт-контрактов это хэш Keccak-256 байткода EVM, составляющего код смарт-контракта. Если аккаунт не является смарт-контрактом, это значение представляет собой хэш пустой строки.
Каждый из этих компонентов состояния счета хранится в листовых узлах Merkle-Patricia Trees в Ethereum.
В результате, если вы знаете адрес счета, вы можете пройти по дереву, чтобы найти узел листа для этого адреса и получить состояние счета. И наоборот, если у вас есть корень состояния (который является корнем дерева), вы можете проверить состояние любого счета в сети Ethereum. Это составляет основу глобального управления состоянием Ethereum.
#merkle #patricia
Значения, хранящиеся в узле
Каждый узел в Patricia tree содержит ключ - символ, который этот узел представляет. В Ethereum такими ключами являются ниблы из адресов счетов. Однако листовые узлы в Merkle-Patricia Trees Ethereum хранят не только ключи, но и состояние соответствующего счета.
Состояние счета Ethereum включает в себя:
1. Nonce: Это число, обозначающее количество транзакций, отправленных с адреса учетной записи. Оно используется для предотвращения атак повторного воспроизведения.
2. Баланс: Это количество Ether, которым располагает аккаунт.
3. Корень хранилища: Для аккаунтов смарт-контрактов это корень другого дерева Меркла-Патриция, в котором хранится содержимое смарт-контракта. Каждый путь в этом дереве соответствует ключу хранения, а соответствующий листовой узел содержит значение хранения для этого ключа.
4. Хэш кода: Для аккаунтов смарт-контрактов это хэш Keccak-256 байткода EVM, составляющего код смарт-контракта. Если аккаунт не является смарт-контрактом, это значение представляет собой хэш пустой строки.
Каждый из этих компонентов состояния счета хранится в листовых узлах Merkle-Patricia Trees в Ethereum.
В результате, если вы знаете адрес счета, вы можете пройти по дереву, чтобы найти узел листа для этого адреса и получить состояние счета. И наоборот, если у вас есть корень состояния (который является корнем дерева), вы можете проверить состояние любого счета в сети Ethereum. Это составляет основу глобального управления состоянием Ethereum.
#merkle #patricia
👍4
Merkle-Patricia Trees. Часть 8
Каждый узел в Merkle-Patricia Trees идентифицируется уникальным хэшем, который представляет собой хэш Keccak-256 кодировки RLP (Recursive Length Prefix) содержимого узла. Различные типы узлов в дереве Меркла-Патриция имеют разное содержимое:
1. Листовые узлы: Листовой узел в дереве Меркла-Патриция представляет собой структуру из двух элементов [ключ, значение]. Ключ - это адрес счета (точнее, его преобразованная в Patricia версия), а значение - это закодированное в RLP состояние счета. Состояние включает в себя nonce, баланс, корень хранилища и хэш кода, как упоминалось ранее.
2. Узлы ветвления: Узел ветвления - это структура из 17 элементов. Первые 16 элементов соответствуют 16 возможным символам (0-9 и a-f). Каждый элемент - это хэш дочернего узла, соответствующего этому узлу, или пустой, если такого дочернего узла нет. 17-й элемент - это значение, которое является состоянием счета, если этот узел представляет полный адрес счета, или пустой в противном случае.
3. Узлы расширения: Узел расширения - это двухэлементная структура [ключ, значение], аналогичная узлу листа. Ключ - это общая часть ключей его дочерних узлов, а значение - это хэш его единственного дочернего узла.
Таким образом, помимо пар ключ-значение (для узлов листьев и расширений) или хэшей дочерних узлов (для узлов ветвей), каждый узел неявно содержит свой собственный хэш, который вычисляется как хэш Keccak-256 кодировки RLP содержимого узла. Этот хэш не хранится в самом узле, но используется в качестве ссылки в его родительском узле.
#merkle #patricia
Каждый узел в Merkle-Patricia Trees идентифицируется уникальным хэшем, который представляет собой хэш Keccak-256 кодировки RLP (Recursive Length Prefix) содержимого узла. Различные типы узлов в дереве Меркла-Патриция имеют разное содержимое:
1. Листовые узлы: Листовой узел в дереве Меркла-Патриция представляет собой структуру из двух элементов [ключ, значение]. Ключ - это адрес счета (точнее, его преобразованная в Patricia версия), а значение - это закодированное в RLP состояние счета. Состояние включает в себя nonce, баланс, корень хранилища и хэш кода, как упоминалось ранее.
2. Узлы ветвления: Узел ветвления - это структура из 17 элементов. Первые 16 элементов соответствуют 16 возможным символам (0-9 и a-f). Каждый элемент - это хэш дочернего узла, соответствующего этому узлу, или пустой, если такого дочернего узла нет. 17-й элемент - это значение, которое является состоянием счета, если этот узел представляет полный адрес счета, или пустой в противном случае.
3. Узлы расширения: Узел расширения - это двухэлементная структура [ключ, значение], аналогичная узлу листа. Ключ - это общая часть ключей его дочерних узлов, а значение - это хэш его единственного дочернего узла.
Таким образом, помимо пар ключ-значение (для узлов листьев и расширений) или хэшей дочерних узлов (для узлов ветвей), каждый узел неявно содержит свой собственный хэш, который вычисляется как хэш Keccak-256 кодировки RLP содержимого узла. Этот хэш не хранится в самом узле, но используется в качестве ссылки в его родительском узле.
#merkle #patricia
👍2❤1
Merkle-Patricia Trees. Часть 9
В контексте дерева Меркла Патриция важным аспектом является то, что структура дерева скрепляется с помощью хэшей. В частности, каждый родительский узел хранит не полное содержимое своих дочерних узлов, а их криптографический хэш. Именно это позволяет связывать и перемещать всю структуру данных.
Допустим, у вас есть родительский узел в дереве, и у него есть два дочерних узла. Когда создаются дочерние узлы, информация в каждом из них хэшируется с помощью криптографической хэш-функции (Keccak-256, в случае Ethereum). В результате получается уникальный результат (хэш) для каждого дочернего узла. Затем эти хэши хранятся в родительском узле.
При навигации по дереву вы начинаете с корневого узла и двигаетесь к листовым узлам в зависимости от пройденного пути. Когда вы достигаете каждого узла, хэши, хранящиеся в этом узле, используются для определения того, в какой дочерний узел спускаться дальше.
Эта схема обеспечивает ряд существенных преимуществ:
1. Эффективность: Хранение только хэша, а не полных данных об узле, позволяет сохранить размер каждого узла, а также обеспечивает эффективную навигацию и обновление дерева.
2. Целостность: Поскольку хэш узла является уникальным отпечатком его содержимого, любое изменение данных узла приведет к изменению его хэша. Это, в свою очередь, приведет к изменению хэша родительского узла и, в конечном счете, корня. Таким образом, любая фальсификация данных может быть обнаружена путем проверки согласованности хэшей.
3. Доказательства: Связывание хэшей также позволяет использовать «доказательства Меркла». Доказательство Меркла позволяет доказать, что определенный листовой узел является частью дерева, не требуя для этого всего дерева. Это делается путем предоставления пути хэшей от корня до этого листа.
Итак, подведем итог: связь каждого узла с его дочерними узлами посредством хранения их хэшей - это критическая особенность, которая позволяет обходить, проверять целостность и доказывать включение в Merkle-Patricia Trees.
#merkle #patricia
В контексте дерева Меркла Патриция важным аспектом является то, что структура дерева скрепляется с помощью хэшей. В частности, каждый родительский узел хранит не полное содержимое своих дочерних узлов, а их криптографический хэш. Именно это позволяет связывать и перемещать всю структуру данных.
Допустим, у вас есть родительский узел в дереве, и у него есть два дочерних узла. Когда создаются дочерние узлы, информация в каждом из них хэшируется с помощью криптографической хэш-функции (Keccak-256, в случае Ethereum). В результате получается уникальный результат (хэш) для каждого дочернего узла. Затем эти хэши хранятся в родительском узле.
При навигации по дереву вы начинаете с корневого узла и двигаетесь к листовым узлам в зависимости от пройденного пути. Когда вы достигаете каждого узла, хэши, хранящиеся в этом узле, используются для определения того, в какой дочерний узел спускаться дальше.
Эта схема обеспечивает ряд существенных преимуществ:
1. Эффективность: Хранение только хэша, а не полных данных об узле, позволяет сохранить размер каждого узла, а также обеспечивает эффективную навигацию и обновление дерева.
2. Целостность: Поскольку хэш узла является уникальным отпечатком его содержимого, любое изменение данных узла приведет к изменению его хэша. Это, в свою очередь, приведет к изменению хэша родительского узла и, в конечном счете, корня. Таким образом, любая фальсификация данных может быть обнаружена путем проверки согласованности хэшей.
3. Доказательства: Связывание хэшей также позволяет использовать «доказательства Меркла». Доказательство Меркла позволяет доказать, что определенный листовой узел является частью дерева, не требуя для этого всего дерева. Это делается путем предоставления пути хэшей от корня до этого листа.
Итак, подведем итог: связь каждого узла с его дочерними узлами посредством хранения их хэшей - это критическая особенность, которая позволяет обходить, проверять целостность и доказывать включение в Merkle-Patricia Trees.
#merkle #patricia
👍5❤1
Merkle-Patricia Trees. Часть 10
Хранение и поиск
Фактическое дерево Patricia Tree по факту хранится в базе данных. Выбор места хранения не обязательно должен быть в одном монолитном блоке; скорее, благодаря хэшированной природе дерева, узлы могут храниться в отдельных местах, будь то в памяти или на диске, или даже распределены по сети.
Такая архитектура известна как распределенная хэш-таблица (DHT), и Ethereum использует эту структуру в своей базовой базе данных (с помощью хранилища ключевых значений, известного как LevelDB).
Основное преимущество такой структуры заключается в том, что она позволяет эффективно выполнять операции поиска, вставки и удаления. Когда вы хотите получить или изменить определенный узел, вы можете использовать его хэш в качестве ключа, чтобы быстро найти его в базе данных. Это гораздо более эффективный процесс, чем поиск по всему блоку данных или неупорядоченной базе данных.
Кроме того, такая система способствует масштабируемости и отказоустойчивости. В распределенной сети даже при сбое или выходе из строя одного узла данные не будут потеряны, поскольку они хранятся не в одном месте. Более того, поскольку данные распределены и связаны между собой с помощью хэшей, система может обрабатывать больше данных, просто добавляя в сеть дополнительные узлы хранения.
Наконец, эта структура поддерживает конфиденциальность и безопасность. Поскольку каждый узел идентифицируется и доступ к нему осуществляется по его хэшу, невозможно вычислить реальные данные, не зная хэша. Кроме того, хэш обеспечивает встроенную контрольную сумму, что позволяет легко обнаружить, если данные узла были подделаны.
Таким образом, тот факт, что узлы дерева Патриции, связанные хэшами, могут храниться отдельно, дает значительные преимущества с точки зрения эффективности, масштабируемости, отказоустойчивости и безопасности.
#merkle #patricia
Хранение и поиск
Фактическое дерево Patricia Tree по факту хранится в базе данных. Выбор места хранения не обязательно должен быть в одном монолитном блоке; скорее, благодаря хэшированной природе дерева, узлы могут храниться в отдельных местах, будь то в памяти или на диске, или даже распределены по сети.
Такая архитектура известна как распределенная хэш-таблица (DHT), и Ethereum использует эту структуру в своей базовой базе данных (с помощью хранилища ключевых значений, известного как LevelDB).
Основное преимущество такой структуры заключается в том, что она позволяет эффективно выполнять операции поиска, вставки и удаления. Когда вы хотите получить или изменить определенный узел, вы можете использовать его хэш в качестве ключа, чтобы быстро найти его в базе данных. Это гораздо более эффективный процесс, чем поиск по всему блоку данных или неупорядоченной базе данных.
Кроме того, такая система способствует масштабируемости и отказоустойчивости. В распределенной сети даже при сбое или выходе из строя одного узла данные не будут потеряны, поскольку они хранятся не в одном месте. Более того, поскольку данные распределены и связаны между собой с помощью хэшей, система может обрабатывать больше данных, просто добавляя в сеть дополнительные узлы хранения.
Наконец, эта структура поддерживает конфиденциальность и безопасность. Поскольку каждый узел идентифицируется и доступ к нему осуществляется по его хэшу, невозможно вычислить реальные данные, не зная хэша. Кроме того, хэш обеспечивает встроенную контрольную сумму, что позволяет легко обнаружить, если данные узла были подделаны.
Таким образом, тот факт, что узлы дерева Патриции, связанные хэшами, могут храниться отдельно, дает значительные преимущества с точки зрения эффективности, масштабируемости, отказоустойчивости и безопасности.
#merkle #patricia
👍2
Merkle-Patricia Trees. Часть 11
Мерклизация (Merklization) Patricia Trie: повышение целостности и верификации
Процесс мерклизации, или преобразования Patricia Trie в Merkle-Patricia Trie, является важным шагом в поддержании целостности и эффективности состояния Ethereum. Это преобразование включает в себя интеграцию криптографических хэшей, в частности, путем добавления этих хэшей в каждый узел Trie.
Понимание процесса мерклизации
Концепция мерклизации подразумевает замену традиционных указателей в Patricia Trie (которые указывают на дочерние узлы) на криптографические хэши. Эти хэши генерируются из содержимого соответствующих дочерних узлов.
Для начала обрабатываются листовые узлы (те, у которых нет дочерних узлов). Содержимое этих узлов пропускается через криптографическую хэш-функцию для создания уникального хэша. Этот хэш фактически становится идентификатором узла. Тот же процесс повторяется для каждого листового узла в древе.
Далее мы рассматриваем родительские узлы этих листов. Для каждого из этих узлов мы объединяем хэши их дочерних узлов и пропускаем эту объединенную строку через ту же криптографическую хэш-функцию. Полученный хэш служит идентификатором родительского узла. Этот процесс повторяется для каждого узла в древе, продвигаясь вверх уровень за уровнем, пока мы не достигнем корневого узла.
Корневой узел следует той же схеме. Он объединяет хэши своих прямых дочерних узлов и хэширует полученную строку, чтобы получить уникальный корневой хэш. Этот корневой хэш, также известный как корень Меркла, очень важен, поскольку он представляет весь набор данных. Если изменится хотя бы крошечная часть набора данных, изменится и корневой хэш, что будет свидетельствовать о модификации данных.
#merkle #patricia
Мерклизация (Merklization) Patricia Trie: повышение целостности и верификации
Процесс мерклизации, или преобразования Patricia Trie в Merkle-Patricia Trie, является важным шагом в поддержании целостности и эффективности состояния Ethereum. Это преобразование включает в себя интеграцию криптографических хэшей, в частности, путем добавления этих хэшей в каждый узел Trie.
Понимание процесса мерклизации
Концепция мерклизации подразумевает замену традиционных указателей в Patricia Trie (которые указывают на дочерние узлы) на криптографические хэши. Эти хэши генерируются из содержимого соответствующих дочерних узлов.
Для начала обрабатываются листовые узлы (те, у которых нет дочерних узлов). Содержимое этих узлов пропускается через криптографическую хэш-функцию для создания уникального хэша. Этот хэш фактически становится идентификатором узла. Тот же процесс повторяется для каждого листового узла в древе.
Далее мы рассматриваем родительские узлы этих листов. Для каждого из этих узлов мы объединяем хэши их дочерних узлов и пропускаем эту объединенную строку через ту же криптографическую хэш-функцию. Полученный хэш служит идентификатором родительского узла. Этот процесс повторяется для каждого узла в древе, продвигаясь вверх уровень за уровнем, пока мы не достигнем корневого узла.
Корневой узел следует той же схеме. Он объединяет хэши своих прямых дочерних узлов и хэширует полученную строку, чтобы получить уникальный корневой хэш. Этот корневой хэш, также известный как корень Меркла, очень важен, поскольку он представляет весь набор данных. Если изменится хотя бы крошечная часть набора данных, изменится и корневой хэш, что будет свидетельствовать о модификации данных.
#merkle #patricia
🔥3👍1
Merkle-Patricia Trees. Часть 12
Значение и преимущества мерклизации
1. Неизменяемая структура данных
Основное преимущество мерклизации заключается в повышении безопасности данных. Связывая каждый узел с хэшем его содержимого, мерклизация превращает Patricia Trie в неизменяемую структуру данных. Любое изменение в данных, каким бы маленьким оно ни было, изменяет хэш узла, содержащего эти данные. Это изменение распространяется до корня тройки, изменяя корневой хэш. Следовательно, мерклизированная Patricia Trie предлагает надежный метод обнаружения изменений данных.
2. Облегчение доказательств Меркла
Мерклизированный Patricia Trie позволяет эффективно проверять данные с помощью доказательств Меркла. В двух словах, доказательство Меркла - это цепочка хэшей, доказывающих включение определенного фрагмента данных в набор данных. Пользователь может проверить существование определенного фрагмента данных, не обращаясь ко всему набору данных, ему нужны только соответствующие хэши от корневого до листового узла, содержащего данные. Этот аспект особенно полезен для легких клиентов Ethereum, которые не хранят полное состояние.
3. Обрезка и эффективность хранения
Мерклизация позволяет эффективно обрезать Patricia Trie. Поскольку узлы соединены хэшами, становится возможным удалять узлы (особенно старые версии состояния), не нарушая общей структуры Trie. Узлы, на которые нет ссылок нигде в trie (то есть их хэши не присутствуют ни в одном из родительских узлов), могут быть безопасно удалены. Этот аспект помогает оптимизировать требования клиентов Ethereum к хранению данных.
Таким образом, мерклизация Patricia Trie - это важнейший аспект работы с состоянием Ethereum, обеспечивающий как высокий уровень целостности данных, так и эффективные средства их проверки.
К настоящему моменту мы рассмотрели большинство фундаментальных концепций, связанных с Merkle-Patricia Trees.
Помните, что понимание Merkle-Patricia Trees может быть сложным из-за их сложной структуры и свойств, но они являются фундаментальным компонентом архитектуры Ethereum и играют важную роль в поддержании целостности и безопасности состояния Ethereum. Ничего страшного, если вы не сразу поймете все детали - продолжайте изучать и пересматривать концепцию, и постепенно она станет более понятной.
На следующей неделе выйдет еще пара постов на эту тему, и мы, наконец, перейдем к более простым постам по Solidity.
#merkle #patricia
Значение и преимущества мерклизации
1. Неизменяемая структура данных
Основное преимущество мерклизации заключается в повышении безопасности данных. Связывая каждый узел с хэшем его содержимого, мерклизация превращает Patricia Trie в неизменяемую структуру данных. Любое изменение в данных, каким бы маленьким оно ни было, изменяет хэш узла, содержащего эти данные. Это изменение распространяется до корня тройки, изменяя корневой хэш. Следовательно, мерклизированная Patricia Trie предлагает надежный метод обнаружения изменений данных.
2. Облегчение доказательств Меркла
Мерклизированный Patricia Trie позволяет эффективно проверять данные с помощью доказательств Меркла. В двух словах, доказательство Меркла - это цепочка хэшей, доказывающих включение определенного фрагмента данных в набор данных. Пользователь может проверить существование определенного фрагмента данных, не обращаясь ко всему набору данных, ему нужны только соответствующие хэши от корневого до листового узла, содержащего данные. Этот аспект особенно полезен для легких клиентов Ethereum, которые не хранят полное состояние.
3. Обрезка и эффективность хранения
Мерклизация позволяет эффективно обрезать Patricia Trie. Поскольку узлы соединены хэшами, становится возможным удалять узлы (особенно старые версии состояния), не нарушая общей структуры Trie. Узлы, на которые нет ссылок нигде в trie (то есть их хэши не присутствуют ни в одном из родительских узлов), могут быть безопасно удалены. Этот аспект помогает оптимизировать требования клиентов Ethereum к хранению данных.
Таким образом, мерклизация Patricia Trie - это важнейший аспект работы с состоянием Ethereum, обеспечивающий как высокий уровень целостности данных, так и эффективные средства их проверки.
К настоящему моменту мы рассмотрели большинство фундаментальных концепций, связанных с Merkle-Patricia Trees.
Помните, что понимание Merkle-Patricia Trees может быть сложным из-за их сложной структуры и свойств, но они являются фундаментальным компонентом архитектуры Ethereum и играют важную роль в поддержании целостности и безопасности состояния Ethereum. Ничего страшного, если вы не сразу поймете все детали - продолжайте изучать и пересматривать концепцию, и постепенно она станет более понятной.
На следующей неделе выйдет еще пара постов на эту тему, и мы, наконец, перейдем к более простым постам по Solidity.
#merkle #patricia
🔥3
Merkle-Patricia Trees. Часть 13
Проверка содержимого Merkle-Patricia Tree
Наиболее привлекательной особенностью Merkle-Patricia Tree (MPT) является его способность быстро и эффективно проверять содержимое блока данных благодаря свойствам криптографической хэш-функции, лежащей в его основе. Фундаментальным принципом, лежащим в основе этого процесса проверки, является концепция «доказательств Меркла», которые могут подтвердить существование определенной точки данных в дереве.
Давайте подробнее рассмотрим, как можно проверить содержимое Merkle-Patricia Tree.
Понимание основ: Узлы и маски ветвей
Прежде чем приступить к процессу проверки, необходимо четко понимать, что такое узлы и как они устроены в MPT. Помните, что каждый узел в MPT связан с уникальным хэшем.
В MPT существует три типа узлов:
1. Листовые узлы: Эти узлы содержат фактические данные (например, состояние счета). Каждый узел листа состоит из ключа (путь от корневого узла к листу) и значения (состояние счета).
2. Узлы расширения: Эти узлы по сути являются узлами «быстрого доступа», которые позволяют нам пропустить те части дерева, где есть длинный ряд узлов, каждый из которых имеет только одного ребенка. Они состоят из общей последовательности нибблов и ссылки на другой узел.
3. Узлы ветвей: Эти узлы - настоящая сила, когда речь идет о ветвлении и связывании внутри дерева. Узел ветвления состоит из 17 элементов; 16 из них представляют все возможные значения nibble (от 0 до 15), а последний 17-й элемент хранит значение, если этот узел является концом ключа.
Каждый узел ветвления в MPT также имеет «битовую маску ветвления» - 16-битное двоичное число, отражающее наличие дочерних узлов. Если у узла ветвления есть дочерний узел, соответствующий определенному значению полубайта, то в битовой маске в соответствующей позиции будет стоять '1'.
В MPT у узла ветвления может быть до 16 дочерних узлов, поскольку он основан на 16-битной (4-битной) системе из-за использования шестнадцатеричных ключей.
Таким образом, в данном контексте «битовая маска ветви» - это 16-битное двоичное число, каждый бит которого соответствует существованию (или несуществованию) дочернего узла. Если для данного значения полубайта существует дочерний узел, соответствующий бит в битовой маске ветвления будет равен '1'; если для данного полубайта дочерний узел не существует, бит будет равен '0'.
Процесс верификации: Прохождение через доказательство Меркла
Процесс проверки содержимого MPT начинается с «доказательства Меркла». Это доказательство представляет собой список сериализованных узлов в том порядке, в котором они встречаются при движении по дереву от корня к рассматриваемому узлу.
Для того, чтобы проверить содержимое дерева, нужно:
1. Начните с корневого узла и хэша всего дерева, которые должны быть известны.
2. Изучите узел, указанный в доказательстве Меркла. Для узлов с ветвями вы будете смотреть на битовую маску ветви и следовать по пути, указанному ключом, который вы пытаетесь доказать. Если битовая маска указывает на дочерний узел, следуйте по этому пути и переходите к следующему узлу в доказательстве. Если дочернего узла нет, это означает, что ключ не существует в дереве.
3. Для узлов листьев и расширений вы будете проверять, соответствует ли пара ключ/значение тому, что вы пытаетесь доказать. Узлы листьев должны содержать точный ключ, который вы ищете. Продлевающие узлы должны соответствовать текущему сегменту ключа, а следующий узел в доказательстве должен быть следующим.
4. Продолжайте двигаться вниз по дереву, повторяя процесс для каждого узла в доказательстве.
5. Процесс завершится, когда вы достигнете узла листа с точным ключом, который вы ищете. Значение в этом узле листа - это данные, которые вы пытались доказать. Если процесс завершается, не найдя соответствия, значит, ключа в дереве нет.
6. Важно отметить, что по мере прохождения доказательства вы также должны вычислять хэш каждого узла и проверять, совпадает ли он с хэшем родительского узла. Это очень важно для гарантии того, что данные не были подделаны.
Проверка содержимого Merkle-Patricia Tree
Наиболее привлекательной особенностью Merkle-Patricia Tree (MPT) является его способность быстро и эффективно проверять содержимое блока данных благодаря свойствам криптографической хэш-функции, лежащей в его основе. Фундаментальным принципом, лежащим в основе этого процесса проверки, является концепция «доказательств Меркла», которые могут подтвердить существование определенной точки данных в дереве.
Давайте подробнее рассмотрим, как можно проверить содержимое Merkle-Patricia Tree.
Понимание основ: Узлы и маски ветвей
Прежде чем приступить к процессу проверки, необходимо четко понимать, что такое узлы и как они устроены в MPT. Помните, что каждый узел в MPT связан с уникальным хэшем.
В MPT существует три типа узлов:
1. Листовые узлы: Эти узлы содержат фактические данные (например, состояние счета). Каждый узел листа состоит из ключа (путь от корневого узла к листу) и значения (состояние счета).
2. Узлы расширения: Эти узлы по сути являются узлами «быстрого доступа», которые позволяют нам пропустить те части дерева, где есть длинный ряд узлов, каждый из которых имеет только одного ребенка. Они состоят из общей последовательности нибблов и ссылки на другой узел.
3. Узлы ветвей: Эти узлы - настоящая сила, когда речь идет о ветвлении и связывании внутри дерева. Узел ветвления состоит из 17 элементов; 16 из них представляют все возможные значения nibble (от 0 до 15), а последний 17-й элемент хранит значение, если этот узел является концом ключа.
Каждый узел ветвления в MPT также имеет «битовую маску ветвления» - 16-битное двоичное число, отражающее наличие дочерних узлов. Если у узла ветвления есть дочерний узел, соответствующий определенному значению полубайта, то в битовой маске в соответствующей позиции будет стоять '1'.
В MPT у узла ветвления может быть до 16 дочерних узлов, поскольку он основан на 16-битной (4-битной) системе из-за использования шестнадцатеричных ключей.
Таким образом, в данном контексте «битовая маска ветви» - это 16-битное двоичное число, каждый бит которого соответствует существованию (или несуществованию) дочернего узла. Если для данного значения полубайта существует дочерний узел, соответствующий бит в битовой маске ветвления будет равен '1'; если для данного полубайта дочерний узел не существует, бит будет равен '0'.
Процесс верификации: Прохождение через доказательство Меркла
Процесс проверки содержимого MPT начинается с «доказательства Меркла». Это доказательство представляет собой список сериализованных узлов в том порядке, в котором они встречаются при движении по дереву от корня к рассматриваемому узлу.
Для того, чтобы проверить содержимое дерева, нужно:
1. Начните с корневого узла и хэша всего дерева, которые должны быть известны.
2. Изучите узел, указанный в доказательстве Меркла. Для узлов с ветвями вы будете смотреть на битовую маску ветви и следовать по пути, указанному ключом, который вы пытаетесь доказать. Если битовая маска указывает на дочерний узел, следуйте по этому пути и переходите к следующему узлу в доказательстве. Если дочернего узла нет, это означает, что ключ не существует в дереве.
3. Для узлов листьев и расширений вы будете проверять, соответствует ли пара ключ/значение тому, что вы пытаетесь доказать. Узлы листьев должны содержать точный ключ, который вы ищете. Продлевающие узлы должны соответствовать текущему сегменту ключа, а следующий узел в доказательстве должен быть следующим.
4. Продолжайте двигаться вниз по дереву, повторяя процесс для каждого узла в доказательстве.
5. Процесс завершится, когда вы достигнете узла листа с точным ключом, который вы ищете. Значение в этом узле листа - это данные, которые вы пытались доказать. Если процесс завершается, не найдя соответствия, значит, ключа в дереве нет.
6. Важно отметить, что по мере прохождения доказательства вы также должны вычислять хэш каждого узла и проверять, совпадает ли он с хэшем родительского узла. Это очень важно для гарантии того, что данные не были подделаны.
Сила доказательств Меркла
Прелесть доказательств Меркла и этого процесса проверки заключается в том, что он позволяет эффективно и безопасно подтверждать данные в больших наборах данных. Учитывая сложность и размер блокчейна Ethereum, такая эффективность имеет решающее значение. Несмотря на кажущуюся сложность процесса, он оптимизирован таким образом, что для подтверждения корректности данных требуется минимальное количество информации, что позволяет Ethereum сохранять свою безопасность и децентрализацию.
Помните, что понимание процесса верификации в Merkle-Patricia Tree требует времени и практического опыта. Но с учетом растущей популярности блокчейна и Ethereum эта концепция заслуживает внимания.
#merkle #patricia
Прелесть доказательств Меркла и этого процесса проверки заключается в том, что он позволяет эффективно и безопасно подтверждать данные в больших наборах данных. Учитывая сложность и размер блокчейна Ethereum, такая эффективность имеет решающее значение. Несмотря на кажущуюся сложность процесса, он оптимизирован таким образом, что для подтверждения корректности данных требуется минимальное количество информации, что позволяет Ethereum сохранять свою безопасность и децентрализацию.
Помните, что понимание процесса верификации в Merkle-Patricia Tree требует времени и практического опыта. Но с учетом растущей популярности блокчейна и Ethereum эта концепция заслуживает внимания.
#merkle #patricia
👍1
Merkle-Patricia Trees. Часть 14
Уязвимости при использовании Merkle-Patricia Trees
Merkle-Patricia Trees являются важной частью архитектуры блокчейна Ethereum, предлагая эффективный способ хранения и проверки данных. Благодаря сочетанию способности Patricia Trie работать с данными переменной длины с защитой от взлома, которую обеспечивает дерево Меркла, MPT служат неотъемлемым компонентом состояния Ethereum.
Однако, как и в случае с любой другой структурой данных, безопасность MPT во многом зависит от ее реализации. Плохо реализованная система MPT может быть уязвима для целого ряда проблем безопасности. Примечательно, что эти уязвимости проистекают не из самой концепции MPT, а из того, как они используются и реализуются. Две распространенные уязвимости, связанные с MPT, включают атаки повторного воспроизведения.
Атаки повторного воспроизведения (Replay Attacks)
Атака повторного воспроизведения, также известная как атака воспроизведения, - это когда легитимная передача данных злонамеренно повторяется или задерживается. В контексте MPT злоумышленник может перехватить доказательство Меркла (доказательство подлинности и целостности данных) и попытаться использовать его повторно.
Например, в блокчейне Ethereum злоумышленник может попытаться воспроизвести доказательство транзакции, чтобы создать проблему двойной траты или повторить определенную операцию. Хотя в Ethereum используется система nonce для предотвращения атак на воспроизведение в разных блоках, если у злоумышленника есть возможность влиять на сетевую связь (например, при распределенной атаке типа «отказ в обслуживании» (DDoS)), он может воспроизвести транзакции в пределах одного блока.
Для защиты от атак повторного воспроизведения часто используются уникальные идентификаторы, временные метки или nonces. Ethereum специально использует nonces для предотвращения атак повторного воспроизведения, увеличивая nonce с каждой транзакцией, чтобы гарантировать уникальность каждой из них.
Если вам интересно, то разобрать одну из таких уязвимостей можно тут:
https://medium.com/immunefi/polygon-double-spend-bug-fix-postmortem-2m-bounty-5a1db09db7f1
Основные уязвимости, связанные с MPT, обусловлены сложностью их конструкции, которая при небрежном подходе может подвергнуть систему значительным рискам. Например, одной из уязвимостей является возможность манипулирования узлами дерева во время его реконструкции, что может привести к расхождениям в состоянии блокчейна.
В заключение следует отметить, что Merkle-Patricia Trees являются важнейшим компонентом инфраструктуры Ethereum, поэтому обеспечение их безопасной и эффективной работы имеет первостепенное значение. По мере развития и становления технологии блокчейн разработчики и исследователи должны помнить об этих уязвимостях и разрабатывать инновационные решения не только для снижения этих рисков, но и для повышения общей устойчивости и целостности систем блокчейн.
#merkle #patricia
Уязвимости при использовании Merkle-Patricia Trees
Merkle-Patricia Trees являются важной частью архитектуры блокчейна Ethereum, предлагая эффективный способ хранения и проверки данных. Благодаря сочетанию способности Patricia Trie работать с данными переменной длины с защитой от взлома, которую обеспечивает дерево Меркла, MPT служат неотъемлемым компонентом состояния Ethereum.
Однако, как и в случае с любой другой структурой данных, безопасность MPT во многом зависит от ее реализации. Плохо реализованная система MPT может быть уязвима для целого ряда проблем безопасности. Примечательно, что эти уязвимости проистекают не из самой концепции MPT, а из того, как они используются и реализуются. Две распространенные уязвимости, связанные с MPT, включают атаки повторного воспроизведения.
Атаки повторного воспроизведения (Replay Attacks)
Атака повторного воспроизведения, также известная как атака воспроизведения, - это когда легитимная передача данных злонамеренно повторяется или задерживается. В контексте MPT злоумышленник может перехватить доказательство Меркла (доказательство подлинности и целостности данных) и попытаться использовать его повторно.
Например, в блокчейне Ethereum злоумышленник может попытаться воспроизвести доказательство транзакции, чтобы создать проблему двойной траты или повторить определенную операцию. Хотя в Ethereum используется система nonce для предотвращения атак на воспроизведение в разных блоках, если у злоумышленника есть возможность влиять на сетевую связь (например, при распределенной атаке типа «отказ в обслуживании» (DDoS)), он может воспроизвести транзакции в пределах одного блока.
Для защиты от атак повторного воспроизведения часто используются уникальные идентификаторы, временные метки или nonces. Ethereum специально использует nonces для предотвращения атак повторного воспроизведения, увеличивая nonce с каждой транзакцией, чтобы гарантировать уникальность каждой из них.
Если вам интересно, то разобрать одну из таких уязвимостей можно тут:
https://medium.com/immunefi/polygon-double-spend-bug-fix-postmortem-2m-bounty-5a1db09db7f1
Основные уязвимости, связанные с MPT, обусловлены сложностью их конструкции, которая при небрежном подходе может подвергнуть систему значительным рискам. Например, одной из уязвимостей является возможность манипулирования узлами дерева во время его реконструкции, что может привести к расхождениям в состоянии блокчейна.
В заключение следует отметить, что Merkle-Patricia Trees являются важнейшим компонентом инфраструктуры Ethereum, поэтому обеспечение их безопасной и эффективной работы имеет первостепенное значение. По мере развития и становления технологии блокчейн разработчики и исследователи должны помнить об этих уязвимостях и разрабатывать инновационные решения не только для снижения этих рисков, но и для повышения общей устойчивости и целостности систем блокчейн.
#merkle #patricia
❤2
Некоторые планы на ближайшее время
На прошлой неделе мы закончили большой цикл разбора работы Merkle-Patricia Trees. Это было сложно, многие нюансы работы я осваиваю до сих пор (сложно найти проекты, где бы это было реализовано в понятном виде), и на усвоение информации уйдет время... Какие же вообще планы на ближайшее время?
Во-первых, в идеале было бы провести несколько стримов по безопасности. Я ранее собирал материал по уязвимостям ERC4626, Uniswap и Chainlink и хотел бы уже в этом году закрыть свой гештальт и рассказать вам, что накопал.
Во-вторых, с февраля я вел отдельный канал, где мы разбирали баги с конкурсных аудитов. За все это время, я осознал, что мне нужно прокачать навык "быстрого понимания кода" для поиска потенциальных проблем.
Я знаю и понимаю более 90% уязвимостей от всех отчетов, что я прочитал за это время (а их уже более 200!), но на разбор нового конкурса у меня уходит много времени. Или, скорее, на каждый конкурс я могу уделить всего пару часов в день, и все это время может занять разбор одной-двух функций. А этого вообще не остаточно для хороших результатов...
Вот я и хочу выработать какую-нибудь практику для более быстрого понимания работы функций и изменения в памяти контракта, чтобы весь процесс аудита шел эффективнее. Некоторые записи я буду выкладывать тут на канале. Возможно, кому-то еще это поможет сделать старт в конкурсных аудитах.
В-третьих, вышли несколько интересных обновлений в фаундри и других программ для тестирования смарт контрактов. Мне было бы интересно разобрать как они работают. Или может даже параллельно запустить небольшой интенсив по работе с foundry с нуля. Посмотрим, как все пойдет.
В-четвертых, я понимаю, что многие пришли на канал за информацией по Solidity, а тут какие-то "душные" темы про деревья и абстракции, поэтому, скорее всего, до конца года будем дальше разбирать пункты из репо Chinmaya, который прекрасно акцентирует внимание на некоторые правила работы EVM и Solidity.
Пока как-то так. Не уверен, что получится реализовать все на 100%, но мы будем стремиться к этому!
Всем приятной рабочей недели и легкого обучения!
#offtop
На прошлой неделе мы закончили большой цикл разбора работы Merkle-Patricia Trees. Это было сложно, многие нюансы работы я осваиваю до сих пор (сложно найти проекты, где бы это было реализовано в понятном виде), и на усвоение информации уйдет время... Какие же вообще планы на ближайшее время?
Во-первых, в идеале было бы провести несколько стримов по безопасности. Я ранее собирал материал по уязвимостям ERC4626, Uniswap и Chainlink и хотел бы уже в этом году закрыть свой гештальт и рассказать вам, что накопал.
Во-вторых, с февраля я вел отдельный канал, где мы разбирали баги с конкурсных аудитов. За все это время, я осознал, что мне нужно прокачать навык "быстрого понимания кода" для поиска потенциальных проблем.
Я знаю и понимаю более 90% уязвимостей от всех отчетов, что я прочитал за это время (а их уже более 200!), но на разбор нового конкурса у меня уходит много времени. Или, скорее, на каждый конкурс я могу уделить всего пару часов в день, и все это время может занять разбор одной-двух функций. А этого вообще не остаточно для хороших результатов...
Вот я и хочу выработать какую-нибудь практику для более быстрого понимания работы функций и изменения в памяти контракта, чтобы весь процесс аудита шел эффективнее. Некоторые записи я буду выкладывать тут на канале. Возможно, кому-то еще это поможет сделать старт в конкурсных аудитах.
В-третьих, вышли несколько интересных обновлений в фаундри и других программ для тестирования смарт контрактов. Мне было бы интересно разобрать как они работают. Или может даже параллельно запустить небольшой интенсив по работе с foundry с нуля. Посмотрим, как все пойдет.
В-четвертых, я понимаю, что многие пришли на канал за информацией по Solidity, а тут какие-то "душные" темы про деревья и абстракции, поэтому, скорее всего, до конца года будем дальше разбирать пункты из репо Chinmaya, который прекрасно акцентирует внимание на некоторые правила работы EVM и Solidity.
Пока как-то так. Не уверен, что получится реализовать все на 100%, но мы будем стремиться к этому!
Всем приятной рабочей недели и легкого обучения!
#offtop
❤10👍2
Стрим / видео на тему "ERC4626: Проблемы и решения"
Наконец у меня появилось немного свободного времени и я создал небольшую презентацию с разбором проблем, которые у вас могут возникнуть при работе с таким стандартом как ERC4626.
Думаю провести завтра вечерний стрим, часов в 7 по мск, здесь в Телеграме. Если что-то пойдет не так, то уже в пятницу выложу просто записанное видео с лекцией.
По продолжительности планирую потратить минут 40. Приглашаю всех к участию!
Когда: завтра, 31 октября, 19:00 мск
#stream #erc4626
Наконец у меня появилось немного свободного времени и я создал небольшую презентацию с разбором проблем, которые у вас могут возникнуть при работе с таким стандартом как ERC4626.
Думаю провести завтра вечерний стрим, часов в 7 по мск, здесь в Телеграме. Если что-то пойдет не так, то уже в пятницу выложу просто записанное видео с лекцией.
По продолжительности планирую потратить минут 40. Приглашаю всех к участию!
Когда: завтра, 31 октября, 19:00 мск
#stream #erc4626
🔥14❤9