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
Media is too big
VIEW IN TELEGRAM
Запись стрима "ERC4626: проблемы и решения"
Спасибо всем, кто зашел на вчерашний стрим! Я все еще учусь проводить такие мероприятия, и порой тяжело дается быстро сформулировать свою мысль. Пишу я гораздо лучше, чем говорю... Но мы будем практиковаться!
В телеграмме я впервые проводил такую встречу и, вероятнее всего, нажал не ту кнопку записи и в итоге получил только звуковую дорожку без видео. Его пришлось записывать уже сразу после стрима, поэтому некоторые моменты могут отличаться.
Также, как и в прошлый раз, выкладываю видео, презентацию и ссылки на протоколы, где были обнаружены уязвимости из видео, чтобы вы сами могли еще раз пройтись по ним и разобрать.
Презентация в Google Docs
Предложение стандарта EIP4626
Контракт от Open Zeppelin
Проблема первого депозитора
Статья - https://mixbytes.io/blog/overview-of-the-inflation-attack
Статья - https://blog.openzeppelin.com/a-novel-defense-against-erc4626-inflation-attacks
"Депозит 1 wei"
Ссылка на отчет с описанием бага - https://code4rena.com/reports/2023-10-ethena#m-04-malicious-users-can-front-run-to-cause-a-denial-of-service-dos-for-stakedusde-due-to-minshares-checks
Ссылка на контракт - https://github.com/code-423n4/2023-10-ethena/blob/main/contracts/StakedUSDe.sol#L191#L194
Проблема с decimals
Статья - https://blog.rivanorth.com/erc-4626-vulnerabilities-and-how-to-avoid-them-in-your-project
Unchecked блоки
Ссылка на отчет - https://code4rena.com/reports/2024-04-panoptic#h-02-overflow-in-collateraltracker-allows-minting-shares-for-free
Ссылка на контракт - https://github.com/code-423n4/2024-04-panoptic/blob/833312ebd600665b577fbd9c03ffa0daf250ed24/contracts/CollateralTracker.sol
Проверка на slippage
Ссылка на контракт - https://github.com/code-423n4/2024-03-pooltogether/blob/main/pt-v5-vault/src/PrizeVault.sol#L454-L472
Permit + ERC4626
Ссылка на отчет - https://code4rena.com/reports/2023-07-pooltogether#m-11-vaultmintwithpermit-can-be-dosd-
Ссылка на контракт - https://github.com/GenerationSoftware/pt-v5-vault/blob/b1deb5d494c25f885c34c83f014c8a855c5e2749/src/Vault.sol
Деление перед умножением
Ссылка на отчет - https://code4rena.com/reports/2024-04-gondi#h-02-division-before-multiplication-could-lead-to-users-losing-50-in-withdrawalqueue
Ссылка на контракт - https://github.com/code-423n4/2024-04-gondi/blob/b9863d73c08fcdd2337dc80a8b5e0917e18b036c/src/lib/pools/WithdrawalQueue.sol#L137-L144
Буду рад узнать ваши мысли по поводу такого стрима: что добавить, что убрать, что переделать.
Ну, и конечно, буду признателен репостам и лайкам!
Всем еще раз спасибо!
#erc4626
Спасибо всем, кто зашел на вчерашний стрим! Я все еще учусь проводить такие мероприятия, и порой тяжело дается быстро сформулировать свою мысль. Пишу я гораздо лучше, чем говорю... Но мы будем практиковаться!
В телеграмме я впервые проводил такую встречу и, вероятнее всего, нажал не ту кнопку записи и в итоге получил только звуковую дорожку без видео. Его пришлось записывать уже сразу после стрима, поэтому некоторые моменты могут отличаться.
Также, как и в прошлый раз, выкладываю видео, презентацию и ссылки на протоколы, где были обнаружены уязвимости из видео, чтобы вы сами могли еще раз пройтись по ним и разобрать.
Презентация в Google Docs
Предложение стандарта EIP4626
Контракт от Open Zeppelin
Проблема первого депозитора
Статья - https://mixbytes.io/blog/overview-of-the-inflation-attack
Статья - https://blog.openzeppelin.com/a-novel-defense-against-erc4626-inflation-attacks
"Депозит 1 wei"
Ссылка на отчет с описанием бага - https://code4rena.com/reports/2023-10-ethena#m-04-malicious-users-can-front-run-to-cause-a-denial-of-service-dos-for-stakedusde-due-to-minshares-checks
Ссылка на контракт - https://github.com/code-423n4/2023-10-ethena/blob/main/contracts/StakedUSDe.sol#L191#L194
Проблема с decimals
Статья - https://blog.rivanorth.com/erc-4626-vulnerabilities-and-how-to-avoid-them-in-your-project
Unchecked блоки
Ссылка на отчет - https://code4rena.com/reports/2024-04-panoptic#h-02-overflow-in-collateraltracker-allows-minting-shares-for-free
Ссылка на контракт - https://github.com/code-423n4/2024-04-panoptic/blob/833312ebd600665b577fbd9c03ffa0daf250ed24/contracts/CollateralTracker.sol
Проверка на slippage
Ссылка на контракт - https://github.com/code-423n4/2024-03-pooltogether/blob/main/pt-v5-vault/src/PrizeVault.sol#L454-L472
Permit + ERC4626
Ссылка на отчет - https://code4rena.com/reports/2023-07-pooltogether#m-11-vaultmintwithpermit-can-be-dosd-
Ссылка на контракт - https://github.com/GenerationSoftware/pt-v5-vault/blob/b1deb5d494c25f885c34c83f014c8a855c5e2749/src/Vault.sol
Деление перед умножением
Ссылка на отчет - https://code4rena.com/reports/2024-04-gondi#h-02-division-before-multiplication-could-lead-to-users-losing-50-in-withdrawalqueue
Ссылка на контракт - https://github.com/code-423n4/2024-04-gondi/blob/b9863d73c08fcdd2337dc80a8b5e0917e18b036c/src/lib/pools/WithdrawalQueue.sol#L137-L144
Буду рад узнать ваши мысли по поводу такого стрима: что добавить, что убрать, что переделать.
Ну, и конечно, буду признателен репостам и лайкам!
Всем еще раз спасибо!
#erc4626
2🔥10❤4
Что по аудиту? Введение
Ранее я писал, что планирую "заново научиться проводить аудит", чтобы сформировать для себя подход к более быстрому пониманию кодовой базы протокола. Кратко говоря, сейчас моя цель научиться делать письменные заметки, чтобы быстро запоминать function flow в контракте и понимать его суть на более детальном уровне в короткий промежуток времени. А зачем?
Из-за основной работы, я не могу уделять более 1-2 часов в день на конкурсный аудит, а на выходных я вообще стараюсь не подходить к компьютеру и полностью отдыхать от web3. Любой хороший аудитор понимает, что этого времени абсолютно недостаточно для каких-либо результатов.
Я прекрасно знаю и понимаю вопросы безопасности смарт контрактов, понимаю, куда нужно смотреть, и в чем может быть потенциальная проблема. При этом сейчас другое время для "багов".
Сами разработчики контрактов сильно прокачались в работе с уязвимостями и простые ошибки, они видят и отлавливают тестами. Остаются только либо, какие-то интеграционные нишевые особенности, либо логические, когда вам необходимо понимать работу контракта на уровне разработчика, чтобы найти что-то.
Понять простую функцию или геттер - не составляет никакого труда. Но когда появляются множественные условия, assembly и огромное количество переменных состояния, за которыми нужно следить - тут и начинаются проблемы.
Посвящая 6-8 часов в день на разбор кода, можно наконец разобрать в нем и найти максимальное количество багов за весь период конкурса. Но что делать, если находить хочется, а времени нет? Я, по крайней мере, хочу попытаться прокачать навык "быстрого понимания протокола"... А что получится, буду описывать тут в постах.
#audit
Ранее я писал, что планирую "заново научиться проводить аудит", чтобы сформировать для себя подход к более быстрому пониманию кодовой базы протокола. Кратко говоря, сейчас моя цель научиться делать письменные заметки, чтобы быстро запоминать function flow в контракте и понимать его суть на более детальном уровне в короткий промежуток времени. А зачем?
Из-за основной работы, я не могу уделять более 1-2 часов в день на конкурсный аудит, а на выходных я вообще стараюсь не подходить к компьютеру и полностью отдыхать от web3. Любой хороший аудитор понимает, что этого времени абсолютно недостаточно для каких-либо результатов.
Я прекрасно знаю и понимаю вопросы безопасности смарт контрактов, понимаю, куда нужно смотреть, и в чем может быть потенциальная проблема. При этом сейчас другое время для "багов".
Сами разработчики контрактов сильно прокачались в работе с уязвимостями и простые ошибки, они видят и отлавливают тестами. Остаются только либо, какие-то интеграционные нишевые особенности, либо логические, когда вам необходимо понимать работу контракта на уровне разработчика, чтобы найти что-то.
Понять простую функцию или геттер - не составляет никакого труда. Но когда появляются множественные условия, assembly и огромное количество переменных состояния, за которыми нужно следить - тут и начинаются проблемы.
Посвящая 6-8 часов в день на разбор кода, можно наконец разобрать в нем и найти максимальное количество багов за весь период конкурса. Но что делать, если находить хочется, а времени нет? Я, по крайней мере, хочу попытаться прокачать навык "быстрого понимания протокола"... А что получится, буду описывать тут в постах.
#audit
🔥3
Что по аудиту? Sablier
На прошлой неделе, в пятницу, закончился мини конкурс протокола Sablier - всего 699 nsloc.
У меня получилось выделить на него всего около 5-6 часов, т.е. в среднем по часу в день.
На скринах я выложил заметки, что я делал по нему и редактор кода, где разбирал основной контракт.
Я понял, что совсем не умею работать с заметками: не понимаю, что нужно отмечать, как возвращаться к ним и как строить архитектуру.
До этого момента, я использовал теги в редакторах, по типу:
@audit, @audit-issue, @note, @audit-ok
и другие, чтобы акцентировать свое внимание на каких-либо деталях. Это хорошо помогает, когда у тебя достаточно времени, чтобы вникнуть в код. Но когда его мало, я могу отвлекаться на них и терять другую мысль, над которой размышляю в данный момент.
Что для меня хорошо сработало в данный аудит?
1. Залить описательную инфу протокола в переводчик.
Я очень хорошо знаю английский язык и свободно говорю, пишу и читаю на нем. Понять смысл протокола, по докам от разработчиков не составит труда, если сконцентрироваться на тексте. Но родной язык, все таки, родной.
Закинув тот же текст в переводчик и пробежав глазами по тексту, вы тоже сможете зацепиться за какие-то основное идеи документации и быстрее понять суть. Годы тренировок на сторис в инстаграм дают о себе знать...
2. Редактор кода, где можно разложить контракт на сниппеты кода также очень помогает.
Мне не нужно было бегать по контракту туда-сюда, чтобы вспомнить, что делать служебная функция. Достаточно было открыть ее рядом с основным контрактом и подглядывать раз через раз.
Да и отслеживать function flow так гораздо легче.
3. Рисунок if/else.
В низу одного из скринов, я делал разбивку условия и заметки по основным моментам, на которые оно влияет. Это сильно помогло запомнить как изменяется память контракта в зависимости от тех или иных опций. Мне зашел этот способ, буду использовать его и дальше.
4. Движение токенов.
Я старался понять движение токенов в контракте: в функциях и до пользователя. Это также помогло отсеять несколько вопросов, которые возникали у меня в процессе аудита.
В целом, я понял протокол, вероятно, на 90% и отправил два репорта.
Не смотря на какие-либо последующие результаты, я понял для себя комфортный способ работы с заметками и некоторые вещи, которые были бесполезными. Думаю на следующем конкурсе попробовать пару новых идеи.
Если у вас есть предложения или свои способы ведения заметок, буду рад почитать о них в комментариях!
Всем легкой и приятной недели!
#audit
На прошлой неделе, в пятницу, закончился мини конкурс протокола Sablier - всего 699 nsloc.
У меня получилось выделить на него всего около 5-6 часов, т.е. в среднем по часу в день.
На скринах я выложил заметки, что я делал по нему и редактор кода, где разбирал основной контракт.
Я понял, что совсем не умею работать с заметками: не понимаю, что нужно отмечать, как возвращаться к ним и как строить архитектуру.
До этого момента, я использовал теги в редакторах, по типу:
@audit, @audit-issue, @note, @audit-ok
и другие, чтобы акцентировать свое внимание на каких-либо деталях. Это хорошо помогает, когда у тебя достаточно времени, чтобы вникнуть в код. Но когда его мало, я могу отвлекаться на них и терять другую мысль, над которой размышляю в данный момент.
Что для меня хорошо сработало в данный аудит?
1. Залить описательную инфу протокола в переводчик.
Я очень хорошо знаю английский язык и свободно говорю, пишу и читаю на нем. Понять смысл протокола, по докам от разработчиков не составит труда, если сконцентрироваться на тексте. Но родной язык, все таки, родной.
Закинув тот же текст в переводчик и пробежав глазами по тексту, вы тоже сможете зацепиться за какие-то основное идеи документации и быстрее понять суть. Годы тренировок на сторис в инстаграм дают о себе знать...
2. Редактор кода, где можно разложить контракт на сниппеты кода также очень помогает.
Мне не нужно было бегать по контракту туда-сюда, чтобы вспомнить, что делать служебная функция. Достаточно было открыть ее рядом с основным контрактом и подглядывать раз через раз.
Да и отслеживать function flow так гораздо легче.
3. Рисунок if/else.
В низу одного из скринов, я делал разбивку условия и заметки по основным моментам, на которые оно влияет. Это сильно помогло запомнить как изменяется память контракта в зависимости от тех или иных опций. Мне зашел этот способ, буду использовать его и дальше.
4. Движение токенов.
Я старался понять движение токенов в контракте: в функциях и до пользователя. Это также помогло отсеять несколько вопросов, которые возникали у меня в процессе аудита.
В целом, я понял протокол, вероятно, на 90% и отправил два репорта.
Не смотря на какие-либо последующие результаты, я понял для себя комфортный способ работы с заметками и некоторые вещи, которые были бесполезными. Думаю на следующем конкурсе попробовать пару новых идеи.
Если у вас есть предложения или свои способы ведения заметок, буду рад почитать о них в комментариях!
Всем легкой и приятной недели!
#audit
👍10