供应链用例:Merkle Tree之链下资产交易

扫码链接5000+新基建产业链上下游从业者,入群请备注“机智地+姓名+公司+岗位

区块链链改项目中,其中供应链是得到大家最关心。但是供应链项目有那几块信息,需要我们特别注意的:

1. 隐私权:在许多情况下,共享有关货物转移的数据很危险(有时也是非法的)。


2. 去中心化:任何人都不应该拥有这些数据,否则会使区块链变得毫无用处。

在本文中,我们提出了一个模型来解决这些问题。

将资产表示为Merkle树

资产模型

供应链是关于资产操纵的。我们需要定义和表示资产。

资产是按类型(一组属性,如颜色,形状,序列号等)描述的商品,并且可以是其他资产的容器。

供应链用例:Merkle Tree之链下资产交易

资产的示例可以是一盒药品:

供应链用例:Merkle Tree之链下资产交易

这些药品盒可以用托盘运输。然后将这些货盘捆绑在一起。因此我们将得到一个复杂的资产组合:

供应链用例:Merkle Tree之链下资产交易

我们所说的供应链实际上是一系列资产交易。由于资产可以是资产的组成部分,因此我们需要一种方法来将它们表示为链值,同时确保不变性和完整性。

Hash + tree data structure = Merkle tree

我们将使用Merkle树来表示我们的资产。Merkle树是一种很棒的加密工具,用于确保复杂数据结构的完整性。Merkle树(通常但不一定)是二叉树,其中:

· 叶子的值是初始化它们的数据片段的哈希值。
· 节点的值是这些子项的值的串联的哈希。


供应链用例:Merkle Tree之链下资产交易

因此如果有人修改了一段用于计算叶子的数据,那么Merkle根就会改变。所以我只能用一个唯一的散列(树的根)来验证大量数据的完整性。

资产表示为Merkle树

我们在上面看到,资产由其类型和(可选)内容组合而成。就Merkle树而言,我们可以表示如下资产:


供应链用例:Merkle Tree之链下资产交易

但是组成资源的资源也可以表示为树。一个重复的结构出现了!

供应链用例:Merkle Tree之链下资产交易

我们可以将资源Merkle根定义为Merkle树节点,其中:

· 左子节点是使用资产类型构建的Merkle叶。
· 右子节点是资产内容节点的Merkle根。

“Root”资产中包含的资产可以具有不同的类型。下面的药盒包含白天的药丸和夜晚的药丸。

供应链用例:Merkle Tree之链下资产交易

我们将修改树模型以按类型对内容进行排序。对于每种类型,我们将计算该类型资产的Merkle根。然后将使用为每种类型计算的根节点列表来计算右子节点。让我们看一个例子,一个盒子的树,其中包含2个晚上的药丸和3个白天的药丸:

供应链用例:Merkle Tree之链下资产交易

让我们用算法将所有这些形式化。

algorithm getRootNode is
  input: asset A with type A.type and content A.assets (sort by type). 
         function h: a hash function. 
         merkleRoot: a function list_nodes –> merkle root node.
  output: R, the root node of the asset A.
  leafNodeType = Node(A.type)
  if A.assets is null then
   return leafNodeType
  else
   rootsOfAssets = list()
   for each a in A.assets do
     rootsOfAssets.push(merkleRoot(a.content))
   assetsNode = merkleRoot(rootsOfAssets)
   return merkleRoot(list(leafNodeType, assetsNode))

用Javascript实现资产Merkle树

首先要做的是实现我们的Merkle树。我们所有的设计都基于Merkle树节点。我们将节点定义为由三个属性描述的对象:

1. data:节点数据。在Merkle树的情况下,如果节点的数据是叶子,则该节点的数据是hash(data_child_left+data_child_right)或hash(data_child_left)。
2. left:左子节点(如果存在)。
3. right:右子节点(如果存在)。

叶子是一个只有一个子节点的节点(在我们的例子中是左边的)。所以当一个节点的右节点为null时,它被认为是一个叶。

我们决定使用javascript,但是您可以使用任何编程语言重新编写代码。重要的是代码背后的逻辑。如果要在javascript中执行此操作,则以下是配置环境的命令列表(假设您已在计算机上安装NodeJS):

# create the project folder and move inside
mkdir merkle-tree-supply-chain
cd merkle-tree-supply-chain
# init as a node project with npm
npm init
# install babel as dev dependencies
npm i –save-dev @babel/core @babel/node @babel/preset-env
# create babelrc file with the preset-env
echo “{   
  “presets”: [
    “@babel/preset-env”
  ]
}” >> .babelrc
# create the src directory
mkdir src
# create the entrypoint file
touch src/index.js

最后使用您喜欢的文本编辑器或IDE编辑package.json文件。然后start脚本添加到scripts对象:

“scripts”: {
  “test”: “echo “Error: no test specified” && exit 1″,
  “start”: “npx babel-node src/index.js”
}

然后,我们可以使用npm run start启动我们的应用程序。现在使用您最喜欢的IDE打开merkle-tree-supply链(我的是vs代码)。我们可以开始编码了!

首先要做的是创建一个哈希函数。我将其写入特定文件:src/hash.utils.js。

import sha256 from ‘crypto-js/sha256’

// random generated prefix
// should be process.env.HASH_PREFIX
const prefix = ‘A7!~adx0a)^OpBVvt2e’

/**
 * Returns the hash of an object given as parameter.
 * @param {String} data the object to digest.
 */
export default function hash (data) {
  return sha256(prefix + data)
}

哈希函数将是用于计算所有哈希值的函数。我们使用crypto-js的SHA256,但您可以使用其他的。prefix用于隐藏data。为什么?因为我们处理容易猜测的数据就像处理一些药片一样。如果没有前缀,很容易猜出一些药丸散列的值(我们可以测试所有值并快速比较)。有了哈希函数后,让我们实现我们的类节点。我将特定于Merkle树的文件放在MerkleTree目录中。让我们在其中创建Node.class.js文件:

import hash from ‘../hash.utils’
import { isString } from ‘./utils’

export default class Node {
  /**
   * Node constructor.
   * @param {Node | String} left the left children of the node.
   * @param {Node} right the right children of the node.
   */
  constructor (left, right = null) {
    if (isString(left) && !right) {
      this.left = null
      this.right = null
      this.leafData = hash(left)
    } else if (left instanceof Node && right instanceof Node) {
      this.left = left
      this.right = right
    } else {
      throw new Error(‘Malformed Node !’)
    }
  }

  /** getter for the node’s data */
  get data () {
    if (this.isLeaf) return this.leafData
    return hash(this.left.data + this.right.data)
  }

  /** getter returning true if the node is a leaf */
  get isLeaf () {
    if (!this.right && !this.left) return true
    if (this.right instanceof Node && this.left instanceof Node) return false
    throw new Error(‘Malformed Node !’)
  }
}

构造函数仅用于测试参数。如果我们仅提供left(作为String!),那么我们将创建一个叶子:这就是为什么我将给定数据的哈希存储在leafData中的原因。如果left和right是Nodes对象,则我们将创建一个常规节点并分配left和right属性。注意我们使用从./utils导入的自定义isString函数:

export function isString (value) {
  return typeof value === ‘string’ || value instanceof String
}

我们还创建了两个getter:

data:如果节点是叶子或哈希(this.left.data + this.right.data),则返回leafData。

isLeaf:如果在其他情况下该节点为假叶子,则返回true。

稍后我们将需要显示链接的节点,因此我添加了两个用于输出给定节点的树的函数:

/**
   * Generate the tree string.
   * @param {Number} layer layer number using to manage indentation.
   */
  treeString (layer = 0) {
    const indentString = ‘ ‘
    if (this.isLeaf) return `n${indentString.repeat(layer)}┗${this.data}`
    return `n${layer === 0 ? ‘.’ : indentString.repeat(layer) + ‘┗’}${this.data}${this.left.treeString(layer + 1)}${this.right.treeString(layer + 1)}`
  }

  /**
   * Print the tree string of the node.
   */
  print () {
    console.log(this.treeString())
  }

所以整个类应该是:

import hash from ‘../hash.utils’
import { isString } from ‘./utils’

export default class Node {
  /**
   * Node constructor.
   * @param {Node | String} left the left children of the node.
   * @param {Node} right the right children of the node.
   */
  constructor (left, right = null) {
    if (isString(left) && !right) {
      this.left = null
      this.right = null
      this.leafData = hash(left)
    } else if (left instanceof Node && right instanceof Node) {
      this.left = left
      this.right = right
    } else {
      throw new Error(‘Malformed Node !’)
    }
  }

  treeString (layer = 0) {
    const indentString = ‘ ‘
    if (this.isLeaf) return `n${indentString.repeat(layer)}┗${this.data}`
    return `n${layer === 0 ? ‘.’ : indentString.repeat(layer) + ‘┗’}${this.data}${this.left.treeString(layer + 1)}${this.right.treeString(layer + 1)}`
  }

  print () {
    console.log(this.treeString())
  }

  /** getter for the node’s data */
  get data () {
    if (this.isLeaf) return this.leafData
    return hash(this.left.data + this.right.data)
  }

  /** getter returning true if the node is a leaf */
  get isLeaf () {
    if (!this.right && !this.left) return true
    if (this.right instanceof Node && this.left instanceof Node) return false
    throw new Error(‘Malformed Node !’)
  }
}

我们有一个树节点的函数表示。我们现在必须编写为我们构建Merkle树的函数。我想给它一个节点列表,函数应该返回Merkle根节点(从而生成初始节点和Merkle根之间的所有节点)。

在文件src/utils中,我创建了一个新的getMerkleRootNode函数:

/**
 * return the root node of a list of leaves.
 * @param {Node[]} nodes array of nodes.
 */
export function getMerkleRootNode (nodes) {
  // the stop cases
  if (nodes.length === 0) throw new Error(‘nodes array cannot be empty’)
  if (nodes.length === 1) return nodes[0]
  if (nodes.length === 2) return new Node(nodes[0], nodes[1])
  // the continue cases
  const newNodesArray = []
  if (nodes.length % 2 === 1) newNodesArray.push(nodes.pop())
  // iterate through the nodes array an reduce it by creating new nodes.
  for (let i = 0; i < nodes.length; i = i + 2) {
    newNodesArray.unshift(new Node(nodes[i], nodes[i + 1]))
  }
  return getMerkleRootNode(newNodesArray)
}

这是一个递归函数。让我们解释一下原因:

MerkleRoot(A, B, C) = MerkleRoot(hash(A + B), C) = hash(hash(A+B)+C)

在上面的例子中,叶子的Merkle根[A,B,C]也是下一层的Merkle根[hash(A+B),C]。因此,如果不能直接进行根计算,我们使用递归函数移动到下一个树层。它允许创建从叶到根的所有中间节点。

递归函数由其stop和continue情况定义。在这里,我们在以下情况下stop函数调用:

node是一个空数组:抛出一个错误。
nodes是一个包含1个元素的数组:我们返回给定的节点(1个叶子的Merkle根=给定的叶子)。
nodes是一个包含2个元素的数组:我们返回一个新节点,该节点是数组中两个节点的父节点。

在其他情况下,我们将继续递归执行。我们需要计算新层,然后使用新的节点数组调用该函数。此类推,直到我们停下来为止。细微之处:在节点数组为奇数的情况下,最后一个从列表中删除。该节点将不参与新节点的计算(树为二进制!)。这是影响结果的任意选择。

这是表示调用函数getMerkleRootNode([A,B,C])的模式,其中A,B和C是节点实例。

供应链用例:Merkle Tree之链下资产交易

下面的代码执行相同的操作:

import Node from ‘./merkleTree/Node.class’
import { getMerkleRootNode } from ‘./merkleTree/utils’

// We have three pieces of data
const data = [‘a’, ‘b’, ‘c’]
// Transform them into leaves: ‘A’, ‘B’ and ‘C’
const leaves = data.map(pieceOfData => new Node(pieceOfData))
// Call the merkle root function
const merkleRoot = getMerkleRootNode(leaves)
// Print the tree
merkleRoot.print()

结果:我们的树共有三层。您的哈希值可能与我的不同(我们可能没有使用相同的前缀)。

.1170bda35de764c0713f31c1aa8256bcd223441f7755f3c838688ed7c7a81f2d
 ┗a1e1b72789a07cc25b0cd3b98e6796b25eda1404b48a4f9c6d35964f63f3e966
  ┗d167e45dad7d508b1095274c288b48ba241370546b0245d9689afb2ba9058f0e
  ┗55850f93f613afcc1a268c5d3d3b085c158be78c550cead28af697ed99c79a1c
 ┗dce9a5ad2bd86dd728b0da1e703eecdf7cf349adc31ac57111a630306277bfdf

现在我们可以处理梅克尔树了。让我们实现一个新的方法,它将允许我们操纵资产。创建名为asset.class.js类. 正如我们之前看到的,资产有两个属性:定义资产的type类型和一组assets=资产的内容。

让我们看看整个类代码:

import hash from ‘./hash.utils’
import Node from ‘./merkleTree/Node.class’
import { getMerkleRootNode } from ‘./merkleTree/utils’

export default class Asset {
  /**
   * Asset constructor.
   * @param {Object} type the assets’ characteristics (color, shape etc…)
   * @param {Array<Asset>} initialAssets the initial assets.
   */
  constructor (type, initialAssets = []) {
    this.type = hash(JSON.stringify(type)).toString()
    initialAssets.length > 0 ? this.assets = {} : this.assets = null
    initialAssets.forEach((asset) => {
      if (this.assets[asset.type]) this.assets[asset.type].push(asset)
      else this.assets[asset.type] = [asset]
    }, {})
  }

  /**
   * Add an asset.
   * @param {Asset!} asset an asset to add.
   */
  add (asset) {
    if (this.assets[asset.type]) this.assets[asset.type].push(asset)
    else this.assets[asset.type] = [asset]
  }

  /** Getter, return true if the asset does not contains others assets. */
  get isItem () {
    return this.assets === null
  }

  /** Returns the merkle root node of the asset */
  get node () {
    if (this.isItem) return new Node(this.type)
    const assetsNodes = []
    Object.keys(this.assets).forEach(key => {
      const root = getMerkleRootNode(this.assets[key].map(asset => asset.node))
      assetsNodes.push(root)
    })
    const assetsRootNode = getMerkleRootNode(assetsNodes)
    return getMerkleRootNode([new Node(this.type), assetsRootNode])
  }
}

大多数函数都很简单:

构造函数将资产类型作为对象获取。请注意我们仅存储类型的哈希值:我们不需要原始数据。资产可以为空,因此initialAssets参数是可选的。构造函数使用type属性按类型的哈希对资产的内容进行排序。

该函数添加正确地将新的资产添加到实例的一个内容。

getter isItem检查内容资产是否为空。如果initialAssets参数为空数组,则constructor将其初始化为null。

最后getter节点返回代表资产的树的Merkle root节点。

/** Returns the merkle root node of the asset */
  get node () {
    if (this.isItem) return new Node(this.type)
    const assetsNodes = []
    Object.keys(this.assets).forEach(key => {
      const root = getMerkleRootNode(this.assets[key].map(asset => asset.node))
      assetsNodes.push(root)
    })
    const assetsRootNode = getMerkleRootNode(assetsNodes)
    return getMerkleRootNode([new Node(this.type), assetsRootNode])
  }

这是上述算法的实现,我们使用非常有用的函数。getMerkleRootNode。
如果资产不包含内容,那么我们只返回一个叶子:return new Node(this.type)。另外我们为组成内容的每种资产类型创建一棵树。然后以创建的Merkle root为基础并创建另一棵树:assetRootNode。最后我们使用该节点和根据资产类型创建的叶子来返回实例的根:return getMerkleRootNode([new Node(this.type),assetRootNode])。

import Asset from ‘./asset.class’

const pill0 = new Asset({ name: ‘pill’, type: ‘doliprane 500mg’ })
const pill1 = new Asset({ name: ‘pill’, type: ‘doliprane 500mg’ })
const pill2 = new Asset({ name: ‘pill’, type: ‘doliprane 500mg’ })

const pill3 = new Asset({ name: ‘pill’, type: ‘doliprane 1000mg’ })
const pill4 = new Asset({ name: ‘pill’, type: ‘doliprane 1000mg’ })

const pills = [pill0, pill1, pill2, pill3, pill4]

const box = new Asset({ name: ‘box’, type: ‘doliprane’ }, pills)
const batch = new Asset({ name: ‘batch’, serialNumber: ‘xz2’ }, [box])

console.log(‘n— box —‘)
box.node.print()
console.log(‘n— batch —‘)
batch.node.print()

我得到以下结果:


供应链用例:Merkle Tree之链下资产交易

如您所见,我在我的批次中找到了我的药盒。

在这个阶段,我们能够代表资产的组成。但是为了尽可能地管理我们的供应链,还需要考虑其他参数:

时间戳将定义资产的创建顺序。我们需要知道何时创建资产。
签名将定义谁创建资产。当有人创建资产(即树的一部分)时,它会对其进行签名。

首先让我们基于Node的加密模块添加以下三个功能。他们将让我们实施签名系统:

import crypto from ‘crypto’

/**
 * Sign a data using a privateKey.
 * @param {String!} data encoded data.
 * @param {crypto.KeyLike!} privateKey the private key using to sign data.
 */
export function sign (data, privateKey) {
  const sign = crypto.createSign(‘SHA256’)
  sign.update(data)
  sign.end()
  const res = sign.sign(privateKey, ‘hex’)
  return res
}

/**
 * Create a new keyPairs using the sect239k1 elliptic curve.
 */
export function newKeyPairs () {
  const { privateKey, publicKey } = crypto.generateKeyPairSync(‘ec’, {
    namedCurve: ‘sect239k1’,
    publicKeyEncoding: { type: ‘spki’, format: ‘pem’ },
    privateKeyEncoding: { type: ‘sec1’, format: ‘pem’ }
  })
  return { privateKey, publicKey }
}

/**
 * Verify the signature using the public key.
 * @param {String!} data a signed data.
 * @param {String!} signature the signature to verify.
 * @param {crypto.KeyLike!} publicKey the public key object.
 */
export function verify (data, signature, publicKey) {
  const verifyObject = crypto.createVerify(‘SHA256’)
  verifyObject.update(data)
  verifyObject.end()
  return verifyObject.verify(publicKey, signature, ‘hex’)
}

另一件事是修改我们的Node构造函数。我们不想对签名进行哈希处理(如果这样做,则以后将无法验证签名)。

/**
   * Node constructor.
   * @param {Node | String} left the left children of the node.
   * @param {Node} right the right children of the node.
   * @param {Boolean} signatureData is a signature data.
   */
  constructor (left, right = null, IsSignature = false) {
    if (isString(left) && !right) {
      this.left = null
      this.right = null
      /**
       * If the leaf is a signature, do not hash the data.
       */
      this.leafData = IsSignature ? left : hash(left).toString()
    } else if (left instanceof Node && right instanceof Node) {
      this.left = left
      this.right = right
    } else {
      throw new Error(‘Malformed Node !’)
    }
  }

我们仅添加一个可选参数:IsSignature。如果等于true,则不使用hash函数来提取叶子的数据。现在我们可以用三种不同的方式创建一个节点:

new Node(leftNode,rightNode)创建一个具有两个子节点的节点。
new Node(data) 创建一个叶子并哈希该数据。
new Node(signature, null, true)创建一个叶子并且不对签名进行哈希处理。

然后让我们修改Asset构造函数以实现时间戳和签名。

声明: 本文由入驻基智地平台的作者撰写,观点仅代表作者本人,不代表基智地立场;基智地发布此信息的目的在于传播更多信息,与本站立场无关。

发表评论

邮箱地址不会被公开。 必填项已用*标注