1.1 密码学哈希函数

• 要理解的第一个密码学知识是
  • 密码学哈希函数，是个数学函数
• 三特性
  • 输入为任意大小字符串
  • 产生固定大小的输出
    • 为使本章讨论更具体，设输出大小为256位，
    • 但我们的讨论适用于任意规模的输出，只要其足够大。
  • 能有效计算，对输入字符串，合理时间内可算出
    • n位字符串，计算复杂度为$O(n)$O(n)

这些特性定义了一般哈希函数，以此函数为基础，可创建数据结构，如哈希表

• 只专注于加密的哈希函数，要使哈希函数达到密码安全，要有下三特性
  • 碰撞阻力（collision-resistance）
  • 隐秘性（hiding）
  • 谜题友好（puzzle-friendliness）

会研究这些特性，阐释为什么要这样的函数

• 这里对哈希函数的论述与一般密码学不同，特别是谜题友好
• 一般密码学，谜题友好并非加密的哈希函数的要求
  • 却对加密数字货币很有用

1.2 哈希指针及数据结构

• 哈希指针是一种数据结构，它在我们将讨论的很多系统中都有用。
• 哈希指针是
  • 一个指向数据存储位置
  • 及其位置数据的哈希值
  • 的指针
• 哈希指针不但告诉你数据存储的位置
  • 还可以给你一种方式，
  • 让你验证数据没有被篡改过（见图1.4）。

• 可用哈希指针构建各种各样的数据结构
• 可把原来用普通指针实现的数据链表和二叉查找树
  • 通过哈希指针来实现。

区块链

如图1.5

• 用哈希指针构建链表
  • 普通链表有区块，a区块既有数据也有 指向上个区块的指针
  • 区块链中，上一个区块指针被置换为哈希指针
    • so区块不仅能告诉我们上个区块的值在哪，还包含该值摘要，使我们能验证那个值没变
• 存 链表头，即一个哈希指针指向 最近使用的区块

梅克尔树