{"content":{"title":"Merkle trees （Golang实现）","body":"### Merkle trees \r\n---\r\nMerkle树是区块链技术的基本组成部分。它是由不同数据块的散列组成的数学数据结构，用作块中所有交易的摘要。\r\n\r\n\r\n它还允许对大量数据中的内容进行有效和安全的验证。此结构有助于验证数据的一致性和内容。比特币和以太坊都使用Merkle树结构。Merkle树也被称为哈希树。\r\n\r\n\r\n从根本上说，Merkle树是数据结构树，其中每个叶节点都用数据块的哈希标记，非叶节点用加密标记 其子节点标签的哈希值。叶节点是树中的最低节点。\r\n\r\n\r\n\r\n![图片.png](https://img.learnblockchain.cn/attachments/2023/02/R9Yl2Xvj63e26ec555cc7.png)\r\n\r\n###  原理\r\n区块链中每个区块都会有一个 Merkle 树，它从叶子节点（树的底部）开始，一个叶子节点就是一个交易哈希。叶子节点的数量必须是双数，但是并非每个块都包含了双数的交易。如果一个块里面的交易数为单数，那么就将最后一个叶子节点（也就是 Merkle 树的最后一个交易，不是区块的最后一笔交易）复制一份凑成双数。\r\n\r\n\r\n从下往上，两两成对，连接两个节点哈希，将组合哈希作为新的哈希。新的哈希就成为新的树节点。重复该过程，直到仅有一个节点，也就是树根。根哈希然后就会当作是整个块交易的唯一标示，将它保存到区块头，然后用于工作量证明。\r\n\r\n---\r\n### 代码实现\r\n```go\r\npackage main\r\n\r\nimport (\r\n\t\"bufio\"\r\n\t\"crypto/sha256\"\r\n\t\"fmt\"\r\n\t\"os\"\r\n\t\"strconv\"\r\n)\r\n\r\n//默克尔树节点结构体\r\ntype Node struct {\r\n\tIndex    int\r\n\tValue    string\r\n\tRootTree *MHTree\r\n}\r\n\r\n//默克尔树结构体\r\ntype MHTree struct {\r\n\tLength   int\r\n\tNodes    []Node\r\n\trootHash string\r\n}\r\n\r\n//获得默克尔树根节点哈希值\r\nfunc (t *MHTree) GetRootHash() string {\r\n\t//不管是否存储，都重新计算哈希值\r\n\tt.rootHash =   t.Nodes[1].getNodeHash()                            \r\n\treturn t.rootHash\r\n}\r\n\r\n//计算默克尔树中某个节点的哈希值\r\nfunc (n *Node) getNodeHash() string {\r\n\t//叶子节点，则直接计算该节点Value的哈希值\r\n\tif n.Value != \"\" {\r\n\t\treturn calDataHash(n.Value)\r\n\t}\r\n\t//非叶子节点，则递归计算哈希值,其为2个子节点哈希值的哈希值123123123123\r\n    return calDataHash(n.RootTree.Nodes[n.Index*2].getNodeHash() + n.RootTree.Nodes[n.Index*2+1].getNodeHash()\r\n        )                                                         \r\n\r\n//计算数据的哈希值\r\nfunc calDataHash(data string) string {\r\n\thash := sha256.New()\r\n\thash.Write([]byte(data))\r\n\treturn string(hash.Sum(nil))\r\n}\r\n\r\n//从结构化文件创建默克尔树\r\nfunc CreateMHTree(fileName string) MHTree {\r\n\tvar tree MHTree\r\n\t//打开文件\r\n\tfile, err := os.Open(fileName)\r\n\tif err != nil {\r\n\t\tpanic(err)\r\n\t}\r\n\tdefer file.Close()\r\n\t//获取读取器\r\n\tbuf := bufio.NewReader(file)\r\n\t//读取首行，获得叶子节点数目（要求叶子节点数目为2的整数次幂\r\n\tdataCountStr, _, _ := buf.ReadLine()\r\n\tdataCount, _ := strconv.Atoi(string(dataCountStr))\r\n\r\n\t//判断幂次\r\n\tlevel := 0\r\n\tfor i := 1; ; i++ {                                          \r\n\t\tif 2<<i == dataCount {\r\n\t\t\tlevel = i\r\n\t\t\tbreak\r\n\t\t}\r\n\t}\r\n\t//创建默克尔树\r\n\r\n\t//给非叶子节点赋值\r\n\tfor i := 1; i <= 2<<level-1; i++ {                               \r\n\t\ttree.Nodes[i].Index = i\r\n\t\ttree.Nodes[i].RootTree = &tree\r\n\t}\r\n\t//读取文件数据，给叶子节点赋值\r\n\tfor i := 2 << level; i < tree.Length; i++ {                  \r\n\t\tstr, _, _ := buf.ReadLine()\r\n\t\ttree.Nodes[i].Index = i\r\n\t\ttree.Nodes[i].RootTree = &tree\r\n\t\ttree.Nodes[i].Value = string(str)\r\n\t}\r\n\treturn tree\r\n}\r\n\r\nfunc main() {\r\n\tvar fileName string\r\n\r\n\tfmt.Println(\"请输入原始数据文件名称\")\r\n\tfmt.Scanln(&fileName)\r\n\tmhTree1 := CreateMHTree(fileName)\r\n\tfmt.Println(\"请输入比对数据文件名称\")\r\n\tfmt.Scanln(&fileName)\r\n\tmhTree2 := CreateMHTree(fileName)\r\n\r\n\thash1 := mhTree1.GetRootHash()\r\n\thash2 := mhTree2.GetRootHash()\r\n\r\n\tif hash1 == hash2 {\r\n\t\tfmt.Println(\"用户没有改变数据\")\r\n\t} else {\r\n\t\tfmt.Println(\"用户改变了数据\")\r\n\t}\r\n\r\n}\r\n\r\n```"},"author":{"user":"https://learnblockchain.cn/people/10986","address":null},"history":"QmP97k8C4441vFBHCn9sGz8iVHNqAB9bJ4meBCvQMQm7g1","timestamp":1675784586,"version":1}