4.比特币的区块 交易“体小量大”,自然而然的想法就是把交易打包成 “块”、对块来操作,从而达到提高效率的目的。 在把交易打包到块的过程中如何组织这些交易? 可以有各种方式 比特币使用的是一种称为 Merkle tree的数据结构 Merkle Tree 用Hash指针建立的二叉树 能够快速地(对数级复杂度)判定一个数据是否在一个集合中 能够快速地判定集合中是否有数据被篡改
◼ 交易“体小量大”，自然而然的想法就是把交易打包成 “块”、对块来操作，从而达到提高效率的目的。 ◼ 在把交易打包到块的过程中如何组织这些交易？ ◼ 可以有各种方式 ◼ 比特币使用的是一种称为Merkle Tree的数据结构 ◼ Merkle Tree ◼ 用Hash指针建立的二叉树 ◼ 能够快速地（对数级复杂度）判定一个数据是否在一个集合中 ◼ 能够快速地判定集合中是否有数据被篡改 3 4. 比特币的区块
4.比特币的区块:Hash指针 ■Hash指针 数据data的hash值H(data)蕴含了data的存储位置信息,即可以通 过 H(data)的值读取到数据。从而,h(data)不仅指明了数据的存 储位置,也提供了对数据是否被篡改过的验证证据。从一个hash 值y处读取数据data,只有当y=H(data)成立,才说明数据没有被 篡改过。例 例如,比特币中每个交易的hash是交易的唯一标识。 H() data
◼ Hash指针 ◼ 数据data的hash值H(data)蕴含了data的存储位置信息，即可以通 过H(data) 的值读取到数据。从而，h(data)不仅指明了数据的存 储位置，也提供了对数据是否被篡改过的验证证据。从一个hash 值y处读取数据data，只有当y=H(data)成立，才说明数据没有被 篡改过。例 ◼ 例如，比特币中每个交易的hash是交易的唯一标识。 4 data 𝐻( ) 4. 比特币的区块：Hash指针
4.比特币的区块:Hash指针 ■Hash链 prev: H( prev HO data data data 只需要记住最后的这个hash值,就能保证整条链的防篡改性 基于的什么密码学原理?
◼ Hash链 5 data prev:H( ) data data H() prev:H( ) prev:H( ) 只需要记住最后的这个hash值，就能保证整条链的防篡改性。 基于的什么密码学原理？ 4. 比特币的区块：Hash指针
4.比特币的区块: Merkle tree ■Merk| e tree 数据放在叶子节点,除了叶子节点之外,每个节点包含两个指向其子节点的Hash指针。(每个 节点的Hash值存在其父节点中) 任何数据被篡改的话,会影响该节点到根节点这个路径上所有节点的Hash值,当然也包含根节 点的Hash值。所以,存储根节点Hash值即可保证数据的不可篡改性 问题:Mrk| e Tree的每个内 部节点需要多大存储空间? H(1) H(1)h H(1)H(1) H(1)H(1) H(/)H
◼ Merkle Tree ◼ 数据放在叶子节点，除了叶子节点之外，每个节点包含两个指向其子节点的Hash指针。（每个 节点的Hash值存在其父节点中） ◼ 任何数据被篡改的话，会影响该节点到根节点这个路径上所有节点的Hash值，当然也包含根节 点的Hash值。所以，存储根节点Hash值即可保证数据的不可篡改性。 6 问题：Merkle Tree的每个内 部节点需要多大存储空间? 4. 比特币的区块：Merkle Tree
4.比特币的区块: Merkle tree ■隶属关系证明 在 Merkle tree中可以高效地证明一个隶属关系:一个数据在一个 Merkle tree的数据集合中 输入:a) Merkle tree根节点的Hash值b)一个数据块,及从该数据块到根节点的路径上所有 节点 对于有n个叶子(数据成员)的 Merkle tre中,需要的空间和时间复杂都是log(n)。 H(1)H(1) H(1)H( H(1)H(1) H(1)H(1) H(/)H(1) H()H( H(1)H() (data) (data) (data) (data)
◼ 隶属关系证明 ◼ 在Merkle Tree中可以高效地证明一个隶属关系：一个数据在一个Merkle Tree的数据集合中 ◼ 输入：a) Merkle Tree 根节点的Hash值 b) 一个数据块，及从该数据块到根节点的路径上所有 节点 ◼ 对于有n个叶子（数据成员）的Merkle Tree中，需要的空间和时间复杂都是log(n)。 7 4. 比特币的区块：Merkle Tree