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

原文作：Louis Singer

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

1. 隐私权：在许多情况下，共享有关货物转移的数据很危险（有时也是非法的）。

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

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

将资产表示为Merkle树

资产模型

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

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

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

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

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

Hash + tree data structure = Merkle tree

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

叶子的值是初始化它们的数据片段的哈希值。

节点的值是这些子项的值的串联的哈希。

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

资产表示为Merkle树

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

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

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

左子节点是使用资产类型构建的Merkle叶。

右子节点是资产内容节点的Merkle根。

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

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

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

algorithmgetRootNodeisinput:assetAwithtypeA.typeandcontentA.assets(sortbytype).functionh:ahashfunction.merkleRoot:afunctionlist_nodes-->merklerootnode.output:R,therootnodeoftheassetA.leafNodeType=Node(A.type)ifA.assetsisnullthenreturnleafNodeTypeelserootsOfAssets=list()foreachainA.assetsdorootsOfAssets.push(merkleRoot(a.content))assetsNode=merkleRoot(rootsOfAssets)returnmerkleRoot(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）：

#createtheprojectfolderandmoveinsidemkdirmerkle-tree-supply-chaincdmerkle-tree-supply-chain#initasanodeprojectwithnpmnpminit#installbabelasdevdependenciesnpmi--save-dev@babel/core@babel/node@babel/preset-env#createbabelrcfilewiththepreset-envecho"{\"presets\":[\"@babel/preset-env\"]}">>.babelrc#createthesrcdirectorymkdirsrc#createtheentrypointfiletouchsrc/index.js

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

"scripts":{"test":"echo\"Error:notestspecified\"&&exit1","start":"npxbabel-nodesrc/index.js"}

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

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

importsha256from'crypto-js/sha256'//randomgeneratedprefix//shouldbeprocess.env.HASH_PREFIXconstprefix='A7!~adx0a)^OpBVvt2e'/***Returnsthehashofanobjectgivenasparameter.*@param{String}datatheobjecttodigest.*/exportdefaultfunctionhash(data){returnsha256(prefix+data)}

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

importhashfrom'../hash.utils'import{isString}from'./utils'exportdefaultclassNode{/***Nodeconstructor.*@param{Node|String}lefttheleftchildrenofthenode.*@param{Node}righttherightchildrenofthenode.*/constructor(left,right=null){if(isString(left)&&!right){this.left=nullthis.right=nullthis.leafData=hash(left)}elseif(leftinstanceofNode&&rightinstanceofNode){this.left=leftthis.right=right}else{thrownewError('MalformedNode!')}}/**getterforthenode'sdata*/getdata(){if(this.isLeaf)returnthis.leafDatareturnhash(this.left.data+this.right.data)}/**getterreturningtrueifthenodeisaleaf*/getisLeaf(){if(!this.right&&!this.left)returntrueif(this.rightinstanceofNode&&this.leftinstanceofNode)returnfalsethrownewError('MalformedNode!')}}

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

exportfunctionisString(value){returntypeofvalue==='string'||valueinstanceofString}

我们还创建了两个getter：

data：如果节点是叶子或哈希（this.left.data + this.right.data），则返回leafData。

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

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

/***Generatethetreestring.*@param{Number}layerlayernumberusingtomanageindentation.*/treeString(layer=0){constindentString=''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)}`}/***Printthetreestringofthenode.*/print(){console.log(this.treeString())}

所以整个类应该是：

importhashfrom'../hash.utils'import{isString}from'./utils'exportdefaultclassNode{/***Nodeconstructor.*@param{Node|String}lefttheleftchildrenofthenode.*@param{Node}righttherightchildrenofthenode.*/constructor(left,right=null){if(isString(left)&&!right){this.left=nullthis.right=nullthis.leafData=hash(left)}elseif(leftinstanceofNode&&rightinstanceofNode){this.left=leftthis.right=right}else{thrownewError('MalformedNode!')}}treeString(layer=0){constindentString=''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())}/**getterforthenode'sdata*/getdata(){if(this.isLeaf)returnthis.leafDatareturnhash(this.left.data+this.right.data)}/**getterreturningtrueifthenodeisaleaf*/getisLeaf(){if(!this.right&&!this.left)returntrueif(this.rightinstanceofNode&&this.leftinstanceofNode)returnfalsethrownewError('MalformedNode!')}}

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

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

/***returntherootnodeofalistofleaves.*@param{Node[]}nodesarrayofnodes.*/exportfunctiongetMerkleRootNode(nodes){//thestopcasesif(nodes.length===0)thrownewError('nodesarraycannotbeempty')if(nodes.length===1)returnnodes[0]if(nodes.length===2)returnnewNode(nodes[0],nodes[1])//thecontinuecasesconstnewNodesArray=[]if(nodes.length%2===1)newNodesArray.push(nodes.pop())//iteratethroughthenodesarrayanreduceitbycreatingnewnodes.for(leti=0;i<nodes.length;i=i+2){newNodesArray.unshift(newNode(nodes[i],nodes[i+1]))}returngetMerkleRootNode(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是节点实例。

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

importNodefrom'./merkleTree/Node.class'import{getMerkleRootNode}from'./merkleTree/utils'//Wehavethreepiecesofdataconstdata=['a','b','c']//Transformthemintoleaves:'A','B'and'C'constleaves=data.map(pieceOfData=>newNode(pieceOfData))//CallthemerklerootfunctionconstmerkleRoot=getMerkleRootNode(leaves)//PrintthetreemerkleRoot.print()

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

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

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

让我们看看整个类代码：

importhashfrom'./hash.utils'importNodefrom'./merkleTree/Node.class'import{getMerkleRootNode}from'./merkleTree/utils'exportdefaultclassAsset{/***Assetconstructor.*@param{Object}typetheassets'characteristics(color,shapeetc...)*@param{Array<Asset>}initialAssetstheinitialassets.*/constructor(type,initialAssets=[]){this.type=hash(JSON.stringify(type)).toString()initialAssets.length>0?this.assets={}:this.assets=nullinitialAssets.forEach((asset)=>{if(this.assets[asset.type])this.assets[asset.type].push(asset)elsethis.assets[asset.type]=[asset]},{})}/***Addanasset.*@param{Asset!}assetanassettoadd.*/add(asset){if(this.assets[asset.type])this.assets[asset.type].push(asset)elsethis.assets[asset.type]=[asset]}/**Getter,returntrueiftheassetdoesnotcontainsothersassets.*/getisItem(){returnthis.assets===null}/**Returnsthemerklerootnodeoftheasset*/getnode(){if(this.isItem)returnnewNode(this.type)constassetsNodes=[]Object.keys(this.assets).forEach(key=>{constroot=getMerkleRootNode(this.assets[key].map(asset=>asset.node))assetsNodes.push(root)})constassetsRootNode=getMerkleRootNode(assetsNodes)returngetMerkleRootNode([newNode(this.type),assetsRootNode])}}

大多数函数都很简单：

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

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

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

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

/**Returnsthemerklerootnodeoftheasset*/getnode(){if(this.isItem)returnnewNode(this.type)constassetsNodes=[]Object.keys(this.assets).forEach(key=>{constroot=getMerkleRootNode(this.assets[key].map(asset=>asset.node))assetsNodes.push(root)})constassetsRootNode=getMerkleRootNode(assetsNodes)returngetMerkleRootNode([newNode(this.type),assetsRootNode])}

这是上述算法的实现，我们使用非常有用的函数。getMerkleRootNode。

如果资产不包含内容，那么我们只返回一个叶子：return new Node(this.type)。另外我们为组成内容的每种资产类型创建一棵树。然后以创建的Merkle root为基础并创建另一棵树：assetRootNode。最后我们使用该节点和根据资产类型创建的叶子来返回实例的根：return getMerkleRootNode（[new Node（this.type），assetRootNode]）。

importAssetfrom'./asset.class'constpill0=newAsset({name:'pill',type:'doliprane500mg'})constpill1=newAsset({name:'pill',type:'doliprane500mg'})constpill2=newAsset({name:'pill',type:'doliprane500mg'})constpill3=newAsset({name:'pill',type:'doliprane1000mg'})constpill4=newAsset({name:'pill',type:'doliprane1000mg'})constpills=[pill0,pill1,pill2,pill3,pill4]constbox=newAsset({name:'box',type:'doliprane'},pills)constbatch=newAsset({name:'batch',serialNumber:'xz2'},[box])console.log('\n---box---')box.node.print()console.log('\n---batch---')batch.node.print()

我得到以下结果：

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

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

时间戳将定义资产的创建顺序。我们需要知道何时创建资产。

签名将定义谁创建资产。当有人创建资产（即树的一部分）时，它会对其进行签名。

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

importcryptofrom'crypto'/***SignadatausingaprivateKey.*@param{String!}dataencodeddata.*@param{crypto.KeyLike!}privateKeytheprivatekeyusingtosigndata.*/exportfunctionsign(data,privateKey){constsign=crypto.createSign('SHA256')sign.update(data)sign.end()constres=sign.sign(privateKey,'hex')returnres}/***CreateanewkeyPairsusingthesect239k1ellipticcurve.*/exportfunctionnewKeyPairs(){const{privateKey,publicKey}=crypto.generateKeyPairSync('ec',{namedCurve:'sect239k1',publicKeyEncoding:{type:'spki',format:'pem'},privateKeyEncoding:{type:'sec1',format:'pem'}})return{privateKey,publicKey}}/***Verifythesignatureusingthepublickey.*@param{String!}dataasigneddata.*@param{String!}signaturethesignaturetoverify.*@param{crypto.KeyLike!}publicKeythepublickeyobject.*/exportfunctionverify(data,signature,publicKey){constverifyObject=crypto.createVerify('SHA256')verifyObject.update(data)verifyObject.end()returnverifyObject.verify(publicKey,signature,'hex')}

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

/***Nodeconstructor.*@param{Node|String}lefttheleftchildrenofthenode.*@param{Node}righttherightchildrenofthenode.*@param{Boolean}signatureDataisasignaturedata.*/constructor(left,right=null,IsSignature=false){if(isString(left)&&!right){this.left=nullthis.right=null/***Iftheleafisasignature,donothashthedata.*/this.leafData=IsSignature?left:hash(left).toString()}elseif(leftinstanceofNode&&rightinstanceofNode){this.left=leftthis.right=right}else{thrownewError('MalformedNode!')}}

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

new Node（leftNode，rightNode）创建一个具有两个子节点的节点。

new Node(data) 创建一个叶子并哈希该数据。

new Node(signature, null, true)创建一个叶子并且不对签名进行哈希处理。

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

constructor(type,timestamp,privateKey,initialAssets=[]){//hashtheassettypethis.type=hash(JSON.stringify(type)).toString()//sorttheinitialassetsbytypeinitialAssets.length>0?this.assets={}:this.assets=nullinitialAssets.forEach((asset)=>{if(this.assets[asset.type])this.assets[asset.type].push(asset)elsethis.assets[asset.type]=[asset]},{})//createthesignatureconstcaracteristicsNode=getMerkleRootNode([newNode(this.type),newNode(hash(timestamp).toString())])constsignature=sign(caracteristicsNode.data.toString(),privateKey)//generatethetypenodethis.definitionNode=newNode(caracteristicsNode,newNode(signature,null,true))}

现在构造函数采用了两个新参数：

定义资产创建时间的时间戳。

用于签署资产的私钥。

我们将创建一个名为caracteristicsNode的新节点，该节点是定义资产的所有叶子的Merkle根。在我们的例子中，资产具有两个特征：type和creationTimestamp。特征节点将是：

然后我们对特征节点数据进行签名以获得资产签名。

最后我们创建了一个新资产的成员：defnitionNode。它是一个节点，其中左子节点是特征节点，右子节点是签名叶。

该节点将替换用作资产节点的左子节点的类型叶。因此我们将所有新的Node（this.type）替换为this.definitionNode。

新的Asset类如下所示：

importhashfrom'./hash.utils'importNodefrom'./merkleTree/Node.class'import{getMerkleRootNode,sign}from'./merkleTree/utils'exportdefaultclassAsset{/***Assetconstructor.*@param{Object!}typetheassets'characteristics(color,shapeetc...)*@param{Number!}timestampthecreationtimestampoftheasset.*@param{crypto.KeyLike!}privateKeyusedtosigntheasset.*@param{Array<Asset>}initialAssetstheinitialassets.*/constructor(type,timestamp,privateKey,initialAssets=[]){//hashtheassettypethis.type=hash(JSON.stringify(type)).toString()//sorttheinitialassetsbytypeinitialAssets.length>0?this.assets={}:this.assets=nullinitialAssets.forEach((asset)=>{if(this.assets[asset.type])this.assets[asset.type].push(asset)elsethis.assets[asset.type]=[asset]},{})//createthesignatureconstcaracteristicsNode=getMerkleRootNode([newNode(this.type),newNode(hash(timestamp).toString())])constsignature=sign(caracteristicsNode.data.toString(),privateKey)//generatethetypenodethis.definitionNode=newNode(caracteristicsNode,newNode(signature,null,true))}/***Addanasset.*@param{Asset!}assetanassettoadd.*/add(asset){if(this.assets[asset.type])this.assets[asset.type].push(asset)elsethis.assets[asset.type]=[asset]}/**Getter,returntrueiftheassetdoesnotcontainsothersassets.*/getisItem(){returnthis.assets===null}/**Returnsthemerklerootnodeoftheasset*/getnode(){if(this.isItem)returnthis.definitionNodeconstassetsNodes=[]Object.keys(this.assets).forEach(key=>{constroot=getMerkleRootNode(this.assets[key].map(asset=>asset.node))assetsNodes.push(root)})constassetsRootNode=getMerkleRootNode(assetsNodes)returngetMerkleRootNode([this.definitionNode,assetsRootNode])}}

这是显示带有和不带有签名的资产节点的图。

然后如果我们用一个简单的例子来测试所有这些：

importAssetfrom'./asset.class'import{newKeyPairs,verify}from'./merkleTree/utils'console.log('creatingobjects...')//auserrepresentedasakeypair.constuser=newKeyPairs()//thetimestampshouldbestoredsomewherebytheuser.constnowTimestamp=Date.now()constpill0=newAsset({name:'pill',type:'doliprane500mg'},nowTimestamp,user.privateKey)constpill1=newAsset({name:'pill',type:'doliprane500mg'},nowTimestamp,user.privateKey)constpill2=newAsset({name:'pill',type:'doliprane500mg'},nowTimestamp,user.privateKey)constpill3=newAsset({name:'pill',type:'doliprane1000mg'},nowTimestamp,user.privateKey)constpill4=newAsset({name:'pill',type:'doliprane1000mg'},nowTimestamp,user.privateKey)constpills=[pill0,pill1,pill2,pill3,pill4]constbox=newAsset({name:'box',type:'doliprane'},nowTimestamp,user.privateKey,pills)constbatch=newAsset({name:'batch',serialNumber:'xz2'},nowTimestamp,user.privateKey,[box])console.log('objectscreated.')console.log('results:')console.log('\n---box---')box.node.print()console.log('\n---batch---')batch.node.print()console.log('\nVerifysignature:')console.log(`publickey:\n${user.publicKey}`)//getsignatureandsigneddataconstbatchDefinitionNode=batch.node.leftconstbatchCaracteristicsNode=batchDefinitionNode.leftconstbatchSignatureNode=batchDefinitionNode.right//verifythesignatureconstisVerified=verify(batchCaracteristicsNode.data,batchSignatureNode.data,user.publicKey)console.log(`Verification:${isVerified}`)

我们得到的结果是：

我们还看到签名已验证：

为什么它可以满足以区块链为动力的供应链需求？

让我们来看一个简单的场景：

在这种情况下，所有资产都可以由批次的Merkle树表示。您可以通过复制存储库并启动自定义npm脚本在控制台上进行输出：

#thesourcecodewillbeclonedontheworkingdirectorygitclonehttps://github.com/louisinger/merkle-tree-supply-chain.gitcdmerkle-tree-supply-chain#createthe.envfileecho"HASH_PREFIX=randomgeneratedprefix">.envnpminstallnpmrunstart-demo

使用Merkle树表示，10个药丸=1个药盒的发送可以用药盒的节点表示。

例如如果以我的默克尔树为例，则框2由以下哈希表示：28f1f0b922421443a8b482e0c9d10d1ddac410bead3d07c3d98c3a55eda173ec。

因此整个药盒的交换只要经过一次交换就行，而不需要10笔交易（每个药丸一个）。因为树提供了框2的根哈希与药丸的哈希之间的链接。

另外这里我们以三级资产构成为例（批处理->药盒->药丸）。但是在供应链环境中，处理和交换的资产通常要复杂得多。

本文来源：陀螺财经
原文标题：供应链用例：Merkle Tree之链下资产交易

—-

编译者/作者：陀螺财经

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。