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不需要

作者：crystal Ye

bitcoin