一、区块链(BlockChain)

1. 区块(Block)

  • 区块是组成区块链的基本数据块
  • 区块由区块头区块体组成
  • 区块头一般包含生成的时间戳、上一个区块的hash、当前区块的hash
  • 区块体一般存放数据,如交易记录

区块图示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
//区块代码演示
public class Block {
    
    public long index;//序列
    public long timeStamp;//生成的时间戳
    public String hashSelf;//本区块体的hash
    public String hashPre;//上一个区块的hash
    public long nonce;//随机数,用于生成的hash符合复杂度
    public String data;//数据

    public Block(long index, String hashPre, String data) {
        this.index = index;
        this.hashPre = hashPre;
        this.data = data;
        this.timeStamp = new Date().getTime();
        this.hashSelf = StringUtil.sha256(index + timeStamp + hashPre + data);
    }
}

2. 区块链构成

  • 主要作用是存储信息
  • 区块链由一个个区块构成的链式结构
  • 类似于分布式数据库,每个节点地位平等

区块链图示:

区块链图示

二、消息摘要:哈希算法(hash,散列)

算法解释

  • 对任意内容(原始数据)计算出相同长度的值(hash值),一般区块链中的hash值长度为256位
  • 只要原始数据被修改过,计算出来的hash值一定不同
  • 理论上对原始数据进行修改不可能得到相同的hash值(碰撞计算)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
//hash函数
public class StringUtil {

    /**
     * sha256加密城256位的hash值
     */
    public static String sha256(String input) {
        try {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            byte[] hash = digest.digest(input.getBytes("UTF-8"));
            StringBuilder hexString = new StringBuilder();
            for (byte aHash : hash) {
                String hex = Integer.toHexString(0xff & aHash);
                if (hex.length() == 1) hexString.append('0');
                hexString.append(hex);
            }
            return hexString.toString();
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}

算法应用:挖矿

背景: 由于要保证区块链是链式结构,防止同时产生很多新的区块,中本聪为区块的生成加入了难度,控制全世界生成一个区块的时间为10分钟左右。 比特币采用的共识机制是工作量证明(pow)

在中本聪制定的区块链协议中,使用一个常量A/区块头中包含一个难度系数值X,得到一个目标值Y,计算出来的hash值必须要小于Y。

为了让计算出来的hash值满足条件,在区块头中加入一个随机数,矿工改变随机数,使得生成的hash满足条件。计算出来满足条件的hash之后,广播给其他节点,全网所有节点进行验证,整个过程就是挖矿。矿工成功添加新的区块,就会获得奖励(币)。

三、共识机制

由于区块链是分布式的,每个节点的地位平等,彼此对数据达成一致结果的过程,使数据保持一致性。

  • 拜占庭将军问题

百科-拜占庭将军问题

公式算法分类:

  1. 非拜占庭错误(non-byzantine fault):出现故障但不会伪造信息的情况。也叫故障错误(Crash Fault)。对应的算法为Crash Fault Tolerance(CFT)类算法

    对于非拜占庭错误,常见的算法Paxos、Raft及其变种等。

  2. 拜占庭错误(ByZantine Fault):伪造信息恶意影响其他节点,对应节点为拜占庭节点。 对应的算法为ByZantine Fault Tolerance(BFT)类算法

    对于拜占庭错误,有PBFT,PoW等证明算法。

  • 工作量证明PoW (Proof of Work)

  • 权益证明PoS (Proof of Stake) , 股权证明

  • 代理授权证明 DPoS (Delegated Proof of Stake)

  • 验证池 POOL

    • 实用拜占庭容错 PBFT (Practical Byzantine Fault Tolerance)
    • 授权拜占庭容错算法 dBFT (delegated BFT)

引申:

  • FLP不可能原理
  • CAP原理