18.06.2019
Структуры данных состояния блокчейна Plasma Cash

Здравствуйте, уважаемые хабрапользователи! В этой статье речь идет о web 3.0 — интернете с децентрализацией. Web 3.0 вводит понятие децентрализации как основы для современного интернета, многие компьютерные системы и сети нуждаются в свойствах защищенности и децентрализации для своих нужд. Решение для децентрализации называется технологиями распределенного реестра или блокчейн.

Блокчейн — это распределенный реестр. Его можно рассматривать как огромную базу данных которая живет вечно и не изменяется в истории, блокчейн используется как базис для децентрализованных веб-приложений или сервисов.

По сути блокчейн это не только база данных, это возможность повысить доверия между участниками сети с возможностью выполнять бизнес-логику в сети.

Византийский консенсус увеличивает надежность сети решает задачу согласованности
Масштабируемость которые привносит DLT изменяют существующие бизнес-сети.

Блокчейн предлагает новые очень важные преимущества:

  1. Предотвращение дорогостоящих ошибок.
  2. Прозрачные транзакции.
  3. Оцифровка для реальных товаров.
  4. Смарт-контракты.
  5. Скорость и безопасность платежей.


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 которые дают возможно не валидировать весь блок а валидировать только те веточки которые соответствуют токену пользователя.

То есть для передаче токена нужно пройтись историю и просканировать только те токены которые нужны определенному юзеру, при передаче токена юзер просто передает всю историю другому юзеру и тот уже может аутентифицировать всю историю — и главное сделать это очень быстро.

Cтруктуры данных Plasma Cash для хранения состояния и истории

Тем не менее необходимо использовать только некоторые деревья меркла, потому что необходимо получать доказательство включение а также доказательство невключения транзакции в блок, например —

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.


Оригинал статьи

Структуры данных состояния блокчейна Plasma Cash

Здравствуйте, уважаемые хабрапользователи! В этой статье речь идет о web 3.0 — интернете с децентрализацией. Web 3.0 вводит понятие децентрализации как основы для современного интернета, многие компьютерные системы и сети нуждаются в свойствах защищенности и децентрализации для своих нужд. Решение для децентрализации называется технологиями распределенного реестра или блокчейн.

Блокчейн — это распределенный реестр. Его можно рассматривать как огромную базу данных которая живет вечно и не изменяется в истории, блокчейн используется как базис для децентрализованных веб-приложений или сервисов.

По сути блокчейн это не только база данных, это возможность повысить доверия между участниками сети с возможностью выполнять бизнес-логику в сети.

Византийский консенсус увеличивает надежность сети решает задачу согласованности
Масштабируемость которые привносит DLT изменяют существующие бизнес-сети.

Блокчейн предлагает новые очень важные преимущества:

  1. Предотвращение дорогостоящих ошибок.
  2. Прозрачные транзакции.
  3. Оцифровка для реальных товаров.
  4. Смарт-контракты.
  5. Скорость и безопасность платежей.


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 которые дают возможно не валидировать весь блок а валидировать только те веточки которые соответствуют токену пользователя.

То есть для передаче токена нужно пройтись историю и просканировать только те токены которые нужны определенному юзеру, при передаче токена юзер просто передает всю историю другому юзеру и тот уже может аутентифицировать всю историю — и главное сделать это очень быстро.

Cтруктуры данных Plasma Cash для хранения состояния и истории

Тем не менее необходимо использовать только некоторые деревья меркла, потому что необходимо получать доказательство включение а также доказательство невключения транзакции в блок, например —

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.


Оригинал статьи

Всё из мира криптовалют: