Здравствуйте, уважаемые хабрапользователи! В этой статье речь идет о web 3.0 — интернете с децентрализацией. Web 3.0 вводит понятие децентрализации как основы для современного интернета, многие компьютерные системы и сети нуждаются в свойствах защищенности и децентрализации для своих нужд. Решение для децентрализации называется технологиями распределенного реестра или блокчейн.
Блокчейн — это распределенный реестр. Его можно рассматривать как огромную базу данных которая живет вечно и не изменяется в истории, блокчейн используется как базис для децентрализованных веб-приложений или сервисов.
По сути блокчейн это не только база данных, это возможность повысить доверия между участниками сети с возможностью выполнять бизнес-логику в сети.
Византийский консенсус увеличивает надежность сети решает задачу согласованности
Масштабируемость которые привносит DLT изменяют существующие бизнес-сети.
Блокчейн предлагает новые очень важные преимущества:
Opporty PoE — это проект целью которого является исследование криптографических протоколов и усовершенствование существующих решений DLT и блокчейна.
Большинство публичных систем распределенного реестра не имеют свойства масштабируемости — их пропускная способность довольно низкая. Например ethereum обрабатывает только ~ 20 tx/s.
Множество решений было создано чтобы увеличить свойство масштабируемости и не потерять децентрализацию (как известно может быть только 2 из 3: масштабируемость, защищенность, децентрализация).
Одним с наиболее эффективных является решение с использованием сайдчейнов.
Концепция заключается в том, что root chain обрабатывает небольшое количество коммитов от дочерних цепочек, так что корневая цепочка выступает в качестве наиболее безопасного и окончательного слоя для хранения всех промежуточных состояний. Каждая дочерняя цепочка функционирует как свой блокчейн со своим собственным консенсусным алгоритмом, но есть несколько важных предостережений.
Валидаторы имеют экономические стимулы действовать честно, и отправляют коммитменты в root chain — слой финального settlement транзакции.
В результате пользователи dapp, работающие в child-chain, вообще не должны взаимодействовать с root-chain. Кроме того, они могут вывести свои деньги в root chain, когда захотят, даже если child chain взломан. Эти выходы из child-chain позволяют пользователям безопасно хранить свои средства с помощью Merkle пруфов, подтверждающего право собственности на определенную сумму средств.
Основные преимущества Плазмы связаны с ее способностью существенно облегчать вычисления, которые в настоящее время перегружают основную цепочку. Кроме того, блокчейн Ethereum может обрабатывать более обширные и более параллельные наборы данных. Время, которое снимается с корневой цепочки, также переносится на узлы Ethereum, которые получают более низкие требования к обработке и хранению.
Plasma Cash — это конструкция, которая дает токенам в сети уникальные серийные номера, которые превращают их в уникальные токены. Преимущества этого включают в себя отсутствие необходимости подтверждений, более простую поддержку для всех видов токенов (включая Non-fungible tokens), и смягчение против массовых выходов из child chain.
Проблема плазмы связана с концепцией «массовых выходов» из child chain. В этом сценарии скоординированный одновременный выход из дочерней цепочки потенциально может привести к нехватке вычислительной мощности для вывода всех средств. В результате пользователи могут потерять средства.
Базовая плазма имеет достаточно много вариантов реализации.
Основные различия это:
Основные вариации Плазмы:
Целью этой статьи объяснить структуры данных которые используются в блокчейне Plasma Cash.
Для того чтобы понять, как именно работают commitment’ы необходимо пояснить понятие дерева Меркла.
Деревья Меркла — чрезвычайно важная структура данных в мире blockchain. По сути, деревья Merkle дают нам возможность фиксировать некоторый набор данных таким образом, который скрывает данные, но позволяет пользователям доказать, что некоторая часть информации была в наборе. Например, если у меня есть десять чисел, я могу создать proof для этих чисел, а затем доказать, что одно конкретное число было в этом наборе чисел. Эти proof имеют небольшой постоянный размер, что делает их дешевыми для публикации в Ethereum.
Можно использовать это для набора транзакций. Можно также доказать, что конкретная транзакция находится в этом наборе транзакций. Это именно то, что делает оператор. Каждый блок состоит из набора транзакций, которые превращаются в дерево Меркла. Корень этого дерева — это proof, который публикуется в Ethereum вместе с каждым блоком плазмы.
Пользователи должны иметь возможность выводить свои средства из плазменной цепочки Когда пользователи хотят выйти из плазменной цепочки, они отправляют транзакцию «выхода» в Ethereum.
Plasma Cash используют специальные Merkle Tree которые дают возможно не валидировать весь блок а валидировать только те веточки которые соответствуют токену пользователя.
То есть для передаче токена нужно пройтись историю и просканировать только те токены которые нужны определенному юзеру, при передаче токена юзер просто передает всю историю другому юзеру и тот уже может аутентифицировать всю историю — и главное сделать это очень быстро.
Тем не менее необходимо использовать только некоторые деревья меркла, потому что необходимо получать доказательство включение а также доказательство невключения транзакции в блок, например —
Opporty выполнило свои реализации Sparse Merkle Tree и Patricia Trie
Разреженное дерево Merkle похоже на стандартное дерево Merkle, за исключением того, что содержащиеся в нем данные индексируются, и каждая точка данных размещается на листе, который соответствует индексу этой точки данных
Допустим, у нас есть дерево Меркла с четырьмя листьями. Мы заполним это дерево несколькими буквами (A, D) для демонстрации. Буква А является первой буквой алфавита, поэтому мы должны поставить ее на первый лист. Точно так же мы можем поставить D на четвертом листе.
Так что же происходит во втором и третьем листьях? Мы просто оставляем их пустыми. Точнее, помещается специальное значение (например, ноль) вместо размещения буквы.
Дерево в конечном итоге выглядит так:
Доказательство включения работает точно также как и в обычном дереве меркла Что произойдет, если мы хотим доказать, что C не является частью этого дерева Меркла? Это просто! Мы знаем, что если бы C был частью дерева, он был бы на третьем листе. Если C не является частью дерева, то третий лист должен быть нулевым.
Все, что нужно, это стандартное доказательство вкллючения Меркла, показывающее, что третий лист равен нулю.
Самая лучшая часть разреженного дерева Merkle — это то, что они действительно представляют хранилища ключей-значений внутри дерева Merkle!
Вот часть кода протокола PoE который реализует построение Sparse Merkle Tree
Этот код действует довольно тривиально. Мы имеем key-value хранилище с доказательством включения / невключения.
В каждой итерации заполняется конкретный уровень конечного дерева начиная с самого последнего. В зависимости от того какой ключ текущего листе четный или нечетный мы берем два соседних листа и считаем хеш текущего уровня. Если мы достигли конца мы записываем единый merkleRoot — общий хеш.
Необходимо понимать что это дерево уже заполнено изначально пустыми значениями! И если мы храним огромное количество токен IDS. мы имеем огромный размер дерева и он очень долго генерируется!
Есть множество решений этой неоптимизированности, но Opporty решило сменить это дерево на Patricia Trie.
Patricia Trie — это cоединение из Radix Trie и Merkle Trie.
Radix Trie ключ данных будет хранить сам путь к данным! Это позволяет создать оптимизированную структуру данных для памяти!
То есть мы проходим рекурсивно и строим отдельно левые и правые дочерние поддеревья. При этом строя ключ как путь в этом дереве!
Это решение еще более тривиальное и работает быстрее при этом являясь достаточно оптимизированным! По факту Patricia дерево должно еще можно более оптимизировать путем ввода новых типов узлов — extension node, branch node и т д, как сделано в ethereum протоколе, но эта реализация удовлетворяет всем нашим условиям — мы получили быструю и оптимизированную по памяти структуру данных.
Реализуя эти структуры данных Opporty сделало возможным масштабирование Plasma Cash так как оно дает возможность проверять историю токена и включение невключение токена в дереве! Что позволяет очень сильно ускорить валидацию блоков и самого Plasma Child Chain’a
Блокчейн — это распределенный реестр. Его можно рассматривать как огромную базу данных которая живет вечно и не изменяется в истории, блокчейн используется как базис для децентрализованных веб-приложений или сервисов.
По сути блокчейн это не только база данных, это возможность повысить доверия между участниками сети с возможностью выполнять бизнес-логику в сети.
Византийский консенсус увеличивает надежность сети решает задачу согласованности
Масштабируемость которые привносит DLT изменяют существующие бизнес-сети.
Блокчейн предлагает новые очень важные преимущества:
- Предотвращение дорогостоящих ошибок.
- Прозрачные транзакции.
- Оцифровка для реальных товаров.
- Смарт-контракты.
- Скорость и безопасность платежей.
Opporty PoE — это проект целью которого является исследование криптографических протоколов и усовершенствование существующих решений DLT и блокчейна.
Большинство публичных систем распределенного реестра не имеют свойства масштабируемости — их пропускная способность довольно низкая. Например ethereum обрабатывает только ~ 20 tx/s.
Множество решений было создано чтобы увеличить свойство масштабируемости и не потерять децентрализацию (как известно может быть только 2 из 3: масштабируемость, защищенность, децентрализация).
Одним с наиболее эффективных является решение с использованием сайдчейнов.
Концепция плазма
Концепция заключается в том, что root chain обрабатывает небольшое количество коммитов от дочерних цепочек, так что корневая цепочка выступает в качестве наиболее безопасного и окончательного слоя для хранения всех промежуточных состояний. Каждая дочерняя цепочка функционирует как свой блокчейн со своим собственным консенсусным алгоритмом, но есть несколько важных предостережений.
- Умные контракты создаются в корневой цепочке и действуют как чекпоинт дочерней цепочки в корневой цепочке.
- Создается дочерняя цепочка, которая функционирует как собственный блокчейн с собственным консенсусом. Все состояния в цепочке дочерних процессов защищены fraud proof ами, которые гарантируют, что все переходы между состояниями действительны, и применяют протокол снятия средств.
- Смарт-контракты, специфичные для dapp или child-chain (логика приложения), затем могут быть развернуты в child chain.
- Необходимые средства могут быть переведены из root-chain в child-chain.
Валидаторы имеют экономические стимулы действовать честно, и отправляют коммитменты в root chain — слой финального settlement транзакции.
В результате пользователи dapp, работающие в child-chain, вообще не должны взаимодействовать с root-chain. Кроме того, они могут вывести свои деньги в root chain, когда захотят, даже если child chain взломан. Эти выходы из child-chain позволяют пользователям безопасно хранить свои средства с помощью Merkle пруфов, подтверждающего право собственности на определенную сумму средств.
Основные преимущества Плазмы связаны с ее способностью существенно облегчать вычисления, которые в настоящее время перегружают основную цепочку. Кроме того, блокчейн Ethereum может обрабатывать более обширные и более параллельные наборы данных. Время, которое снимается с корневой цепочки, также переносится на узлы Ethereum, которые получают более низкие требования к обработке и хранению.
Plasma Cash — это конструкция, которая дает токенам в сети уникальные серийные номера, которые превращают их в уникальные токены. Преимущества этого включают в себя отсутствие необходимости подтверждений, более простую поддержку для всех видов токенов (включая Non-fungible tokens), и смягчение против массовых выходов из child chain.
Проблема плазмы связана с концепцией «массовых выходов» из child chain. В этом сценарии скоординированный одновременный выход из дочерней цепочки потенциально может привести к нехватке вычислительной мощности для вывода всех средств. В результате пользователи могут потерять средства.
Варианты реализации Плазмы
Базовая плазма имеет достаточно много вариантов реализации.
Основные различия это:
- хранение информации о способе хранения и представления состояния,
- типы токенов (делимые неделимые),
- защищенность транзакций,
- тип консенсусного алгоритма и т. д.
Основные вариации Плазмы:
- UTXO based — каждая транзакций состоит из входов и выходов: транзакция может быть проведена и потрачена, список не потраченных транзакций является состоянием самого child-chain.
- Account based — просто содержит отражение каждого аккаунта-счета и его баланса, этот тип используется в ethereum так как каждый аккаунт может быть двух типов — пользовательский аккаунта и аккаунт смарт контракта. Преимущество этого типа хранения состояния — его простота, а минус является то что этот вариант не масштабируем (используется специальное свойство nonce чтобы транзакция не была выполнена дважды).
Целью этой статьи объяснить структуры данных которые используются в блокчейне Plasma Cash.
Для того чтобы понять, как именно работают commitment’ы необходимо пояснить понятие дерева Меркла.
Деревья Меркла их использование в Плазме
Деревья Меркла — чрезвычайно важная структура данных в мире blockchain. По сути, деревья Merkle дают нам возможность фиксировать некоторый набор данных таким образом, который скрывает данные, но позволяет пользователям доказать, что некоторая часть информации была в наборе. Например, если у меня есть десять чисел, я могу создать proof для этих чисел, а затем доказать, что одно конкретное число было в этом наборе чисел. Эти proof имеют небольшой постоянный размер, что делает их дешевыми для публикации в Ethereum.
Можно использовать это для набора транзакций. Можно также доказать, что конкретная транзакция находится в этом наборе транзакций. Это именно то, что делает оператор. Каждый блок состоит из набора транзакций, которые превращаются в дерево Меркла. Корень этого дерева — это proof, который публикуется в Ethereum вместе с каждым блоком плазмы.
Пользователи должны иметь возможность выводить свои средства из плазменной цепочки Когда пользователи хотят выйти из плазменной цепочки, они отправляют транзакцию «выхода» в Ethereum.
Plasma Cash используют специальные Merkle Tree которые дают возможно не валидировать весь блок а валидировать только те веточки которые соответствуют токену пользователя.
То есть для передаче токена нужно пройтись историю и просканировать только те токены которые нужны определенному юзеру, при передаче токена юзер просто передает всю историю другому юзеру и тот уже может аутентифицировать всю историю — и главное сделать это очень быстро.
Cтруктуры данных Plasma Cash для хранения состояния и истории
Тем не менее необходимо использовать только некоторые деревья меркла, потому что необходимо получать доказательство включение а также доказательство невключения транзакции в блок, например —
- Sparse Merkle Tree
- Patricia Trie
Opporty выполнило свои реализации Sparse Merkle Tree и Patricia Trie
Разреженное дерево Merkle похоже на стандартное дерево Merkle, за исключением того, что содержащиеся в нем данные индексируются, и каждая точка данных размещается на листе, который соответствует индексу этой точки данных
Допустим, у нас есть дерево Меркла с четырьмя листьями. Мы заполним это дерево несколькими буквами (A, D) для демонстрации. Буква А является первой буквой алфавита, поэтому мы должны поставить ее на первый лист. Точно так же мы можем поставить D на четвертом листе.
Так что же происходит во втором и третьем листьях? Мы просто оставляем их пустыми. Точнее, помещается специальное значение (например, ноль) вместо размещения буквы.
Дерево в конечном итоге выглядит так:
Доказательство включения работает точно также как и в обычном дереве меркла Что произойдет, если мы хотим доказать, что C не является частью этого дерева Меркла? Это просто! Мы знаем, что если бы C был частью дерева, он был бы на третьем листе. Если C не является частью дерева, то третий лист должен быть нулевым.
Все, что нужно, это стандартное доказательство вкллючения Меркла, показывающее, что третий лист равен нулю.
Самая лучшая часть разреженного дерева Merkle — это то, что они действительно представляют хранилища ключей-значений внутри дерева Merkle!
Вот часть кода протокола PoE который реализует построение Sparse Merkle Tree
class SparseTree {
//...
buildTree() {
if (Object.keys(this.leaves).length > 0) {
this.levels = []
this.levels.unshift(this.leaves)
for (let level = 0; level < this.depth; level++) {
let currentLevel = this.levels[0]
let nextLevel = {}
Object.keys(currentLevel).forEach((leafKey) => {
let leafHash = currentLevel[leafKey]
let isEvenLeaf = this.isEvenLeaf(leafKey)
let parentLeafKey = leafKey.slice(0, -1)
let neighborLeafKey = parentLeafKey + (isEvenLeaf ? '1' : '0')
let neighborLeafHash = currentLevel[neighborLeafKey]
if (!neighborLeafHash) {
neighborLeafHash = this.defaultHashes[level]
}
if (!nextLevel[parentLeafKey]) {
let parentLeafHash = isEvenLeaf ?
ethUtil.sha3(Buffer.concat([leafHash, neighborLeafHash])) :
ethUtil.sha3(Buffer.concat([neighborLeafHash, leafHash]))
if (level == this.depth - 1) {
nextLevel['merkleRoot'] = parentLeafHash
} else {
nextLevel[parentLeafKey] = parentLeafHash
}
}
})
this.levels.unshift(nextLevel)
}
}
}
}Этот код действует довольно тривиально. Мы имеем key-value хранилище с доказательством включения / невключения.
В каждой итерации заполняется конкретный уровень конечного дерева начиная с самого последнего. В зависимости от того какой ключ текущего листе четный или нечетный мы берем два соседних листа и считаем хеш текущего уровня. Если мы достигли конца мы записываем единый merkleRoot — общий хеш.
Необходимо понимать что это дерево уже заполнено изначально пустыми значениями! И если мы храним огромное количество токен IDS. мы имеем огромный размер дерева и он очень долго генерируется!
Есть множество решений этой неоптимизированности, но Opporty решило сменить это дерево на Patricia Trie.
Patricia Trie — это cоединение из Radix Trie и Merkle Trie.
Radix Trie ключ данных будет хранить сам путь к данным! Это позволяет создать оптимизированную структуру данных для памяти!
Реализация Opporty
buildNode(childNodes, key = '', level = 0) {
let node = {key}
this.iterations++
if (childNodes.length == 1) {
let nodeKey = level == 0 ?
childNodes[0].key :
childNodes[0].key.slice(level - 1)
node.key = nodeKey
let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(nodeKey)),
childNodes[0].hash])
node.hash = ethUtil.sha3(nodeHashes)
return node
}
let leftChilds = []
let rightChilds = []
childNodes.forEach((node) => {
if (node.key[level] == '1') {
rightChilds.push(node)
} else {
leftChilds.push(node)
}
})
if (leftChilds.length && rightChilds.length) {
node.leftChild = this.buildNode(leftChilds, '0', level + 1)
node.rightChild = this.buildNode(rightChilds, '1', level + 1)
let nodeHashes = Buffer.concat([Buffer.from(ethUtil.sha3(node.key)),
node.leftChild.hash,
node.rightChild.hash])
node.hash = ethUtil.sha3(nodeHashes)
} else if (leftChilds.length && !rightChilds.length) {
node = this.buildNode(leftChilds, key + '0', level + 1)
} else if (!leftChilds.length && rightChilds.length) {
node = this.buildNode(rightChilds, key + '1', level + 1)
} else if (!leftChilds.length && !rightChilds.length) {
throw new Error('invalid tree')
}
return node
}
То есть мы проходим рекурсивно и строим отдельно левые и правые дочерние поддеревья. При этом строя ключ как путь в этом дереве!
Это решение еще более тривиальное и работает быстрее при этом являясь достаточно оптимизированным! По факту Patricia дерево должно еще можно более оптимизировать путем ввода новых типов узлов — extension node, branch node и т д, как сделано в ethereum протоколе, но эта реализация удовлетворяет всем нашим условиям — мы получили быструю и оптимизированную по памяти структуру данных.
Реализуя эти структуры данных Opporty сделало возможным масштабирование Plasma Cash так как оно дает возможность проверять историю токена и включение невключение токена в дереве! Что позволяет очень сильно ускорить валидацию блоков и самого Plasma Child Chain’a