bitcoin（1）
密码学原理- hash 函数
性质
1」collision resistance： 防止篡改
例如：一个m的hash（m），当m发生改变，装不到另一个m‘，使得hash（m’）=hash（m）
【collision free： 无法人为制造hash碰撞】
【brute-force：遍历所有的输入找到发生的hash碰撞】
2」hiding：单向（只可以从输出算出输出，反向不可行）
- 蛮力求解；遍历所有输入找到相同的输出hash（m‘）=hash（x），则找到x=m’， 此时就要求x的范围足够大
- digital commitment（digital equaivalent of sealed envelope）
- —
3」puzzle friendly
我们利用改变不同的nonce，找到使hash（block header）<=target 的nonce。这种需要很多次计算的方法成为 pow(proof of work), 找到合适的nonce很困难，但是我们反向验证十分方便，此为puzzle friendly
SHA256——Bitcoin中使用的hash function
签名
1」bitcoin账户管理
去中心化，每个用户自己决定开户，即自己创建公钥（public key)和私钥(private key)
- 来源于非对称加密体系（asymmetric encryption algorithm):
加密用公钥（相当于银行账号），解密用私钥（保存在本地，相当于银行账号密码）：解决秘钥传输不方便
- 私钥的用途：
用于签名，方便其他账户知道此次转账确实为本人操作（验证签名：用公钥）
2」a good source of randomness??
数据结构 — hash pointer
1」blockchain
- 第一个区块（genesis block)，最近产生的区块（most recent block)
- 每一个block都包含前一个block
2」merkle tree
-
与二叉树（binary tree）类似，用hash pointer 代替普通指针
-
最底层leaf node：数据块（data block），上面的每一层均为hash pointer
—data block的哈希值存在上层的 hash pointer，两个data block（类似于二 叉树）的哈希值的和再去哈希值再存储到上一层的 hash pointer，直到根结点（root）
—根结点的哈希值为root hash
—只要知道root hash，可以检测对任何节点的修改
- 数据块（data block）每个数据块是一个交易（transaction）：分为块头（header） 和块身
—块头（header）：没有交易的具体信息只有root hash value
—块身（body）：储存交易列表
- 用途：merkle proof
又称为proof of membership , proof of inclusion
如何像轻节点证明交易完成：
找到交易的位置，从交易位置到root的路径一路计算hash直到根结点，再与保存的root hash进行比较，称为merkle proof
—全节点：保存 header + body：保存路径中所有用到的hash
—轻节点：只保存 header
—时间复杂度为log（n）；不存在证明时间复杂度为（n）
2.1」sorted merkle tree
对底层（leaf node）的hash value进行排序，可以更好的进行不存在证明，时间复杂度为log（n），bitcoin不需要