用js实现一个简单的区块链

in #blockchain7 years ago

用js实现一个简单的区块链

用Javascript实现一个简单的区块链程序。来加深对区块链当中一些基本概念的理解。

区块链

区块链就是一个不断增长的全网总账本,每个完全节点都拥有完整的区块链,并且,节点总是信任最长的区块链,伪造区块链需要拥有超过51%的全网算力。

区块链的一个重要特性就是不可篡改

为什么区块链不可篡改?

区块链是由一个一个区块构成的有序链表,每一个区块都记录了一系列交易,并且,每个区块都指向前一个区块,从而形成一个链条。

每个区块都有一个唯一的哈希标识,被称为区块哈希,同时,区块通过记录上一个区块的哈希来指向上一个区块。

每一个区块还有一个Merkle哈希用来确保该区块的所有交易记录无法被篡改。

区块链中的主要数据就是一系列交易,第一条交易通常是coinbase交易,也就是矿工的挖矿奖励,后续交易都是用户的交易。

区块

一个区块,包含了以下数据

  • 前一个区块hash值
  • 时间戳: 记录了该区块的生成时间
  • 交易数据 (以及根据交易数据生成的Merkles树)
  • 区块hash值
  • nonce 随机数(当前区块工作量证明的参数)

哈希算法

区块链的不可篡改特性是由哈希算法保证的。

哈希算法,又称散列算法,它是一个单向函数,可以把任意长度的输入数据转化为固定长度的输出:

h = H(x)

例如,对morning和bitcoin两个输入进行某种哈希运算,得到的结果是固定长度的数字:

H("morning") = c7c3169c21f1d92e9577871831d067c8
H("bitcoin") = cd5b1e4947e304476c788cd474fb579a

我们通常用十六进制表示哈希输出。

因为哈希算法是一个单向函数,要设计一个安全的哈希算法,就必须满足:通过输入可以很容易地计算输出,但是,反过来,通过输出无法反推输入,只能暴力穷举。

H("???????") = c7c3169c21f1d92e9577871831d067c8
H("???????") = cd5b1e4947e304476c788cd474fb579a

想要根据上述结果反推输入,只能由计算机暴力穷举。...

哈希碰撞

一个安全的哈希算法还需要满足另一个条件:碰撞率低。

碰撞是指,如果两个输入数据不同,却恰好计算出了相同的哈希值,那么我们说发生了碰撞:

H("data-123456") = a76b1fb579a02a476c789d9115d4b201
H("data-ABCDEF") = a76b1fb579a02a476c789d9115d4b201

因为输入数据长度是不固定的,所以输入数据是一个无限大的集合,而输出数据长度是固定的,所以,输出数据是一个有限的集合。把一个无限的集合中的每个元素映射到一个有限的集合,就必然存在某些不同的输入得到了相同的输出。...

哈希碰撞的本质是把无限的集合映射到有限的集合时必然会产生碰撞。我们需要计算的是碰撞的概率。很显然,碰撞的概率和输出的集合大小相关。输出位数越多,输出集合就越大,碰撞率就越低。

安全哈希算法还需要满足一个条件,就是输出无规律。输入数据任意一个bit(某个字节的某一个二进制位)的改动,会导致输出完全不同,从而让攻击者无法逐步猜测输入,只能依赖暴力穷举来破解:

H("hello-1") = 970db54ab8a93b7173cb48f55e67fd2c
H("hello-2") = 8284353b768977f05ac600baad8d3d17

比特币使用的哈希算法有两种:SHA-256和RipeMD160

SHA-256的理论碰撞概率是:尝试2的130次方的随机输入,有99.8%的概率碰撞。
注意2130是一个非常大的数字,大约是1361万亿亿亿亿。以现有的计算机的计算能力,是不可能在短期内破解的。

比特币使用两种哈希算法,一种是对数据进行两次SHA-256计算,这种算法在比特币协议中通常被称为hash256。
另一种算法是先计算SHA-256,再计算RipeMD160,这种算法在比特币协议中通常被称为hash160。

工作量证明

在比特币网络中,矿工的挖矿被称为工作量证明。 挖矿的目的是为了找到一个随机数,使其最终计算出来的区块哈希值 符合当前区块链的难度值。

通过改变区块头部的一个nonce字段的值,计算机可以计算出不同的区块哈希值.

直到计算出某个特定的哈希值的时候,计算结束。这个哈希和其他的哈希相比,它的特点是前面有好几个0:

hash256(block data, nonce=0) = 291656f37cdcf493c4bb7b926e46fee5c14f9b76aff28f9d00f5cca0e54f376f
hash256(block data, nonce=1) = f7b2c15c4de7f482edee9e8db7287a6c5def1c99354108ef33947f34d891ea8d
hash256(block data, nonce=2) = b6eebc5faa4c44d9f5232631f39ddf4211443d819208da110229b644d2a99e12
hash256(block data, nonce=3) = 00aeaaf01166a93a2217fe01021395b066dd3a81daffcd16626c308c644c5246
hash256(block data, nonce=4) = 26d33671119c9180594a91a2f1f0eb08bdd0b595e3724050acb68703dc99f9b5
hash256(block data, nonce=5) = 4e8a3dcab619a7ce5c68e8f4abdc49f98de1a71e58f0ce9a0d95e024cce7c81a
hash256(block data, nonce=6) = 185f634d50b17eba93b260a911ba6dbe9427b72f74f8248774930c0d8588c193
hash256(block data, nonce=7) = 09b19f3d32e3e5771bddc5f0e1ee3c1bac1ba4a85e7b2cc30833a120e41272ed
...
hash256(block data, nonce=124709132) = 00000000fba7277ef31c8ecd1f3fef071cf993485fe5eab08e4f7647f47be95c

比特币挖矿的工作量证明原理就是,不断尝试计算区块的哈希,直到计算出一个特定的哈希值,它比难度值要小。

比特币使用的SHA-256算法可以看作对随机输入产生随机输出,例如,我们对字符串Hello再加上一个数字计算两次SHA-256,根据数字的不同,得到的哈希是完全无规律的256位随机数:

  hash256("Hello?") = ????????????????????????????????????????????????????????????????

大约计算16次,我们可以在得到的哈希中找到首位是0的哈希值,因为首位是0出现的概率是1/16:

如果我们要找出前两位是0的哈希值,理论上需要计算256次,因为00出现的概率是16^2 ,实际计算44次:

hash256("Hello44") = 00e477f95283a544ffac7a8efc7decb887f5c073e0f3b43b3797b5dafabb49b5

如果我们要找出前3位是0的哈希值,理论上需要计算16^3 = 4096次,实际计算6591次:

hash256("Hello6591") = 0008a883dacb7094d6da1a6cefc6e7cbc13635d024ac15152c4eadba7af8d11c

如果我们要找出前4位是0的哈希值,理论上需要计算16^4 = 6万5千多次,实际计算6万7千多次:

hash256("Hello67859") = 00002e4af0b80d706ae749d22247d91d9b1c2e91547d888e5e7a91bcc0982b87

如果我们要找出前5位是0的哈希值,理论上需要计算16^5 = 104万次,实际计算158万次:

hash256("Hello1580969") = 00000ca640d95329f965bde016b866e75a3e29e1971cf55ffd1344cdb457930e

如果我们要找出前6位是0的哈希值,理论上需要计算16^6 =1677万次,实际计算1558万次:

hash256("Hello15583041") = 0000009becc5cf8c9e6ba81b1968575a1d15a93112d3bd67f4546f6172ef7e76

对于给定难度的SHA-256:假设我们用难度1表示必须算出首位1个0,难度2表示必须算出首位两个0,难度N表示必须算出首位N个0,那么,每增加一个难度,计算量将增加16倍。

对于比特币挖矿来说,就是先给定一个难度值,然后不断变换nonce,计算Block Hash,直到找到一个比给定难度值低的Block Hash,就算成功挖矿。

我们用简化的方法来说明难度,例如,必须计算出连续17个0开头的哈希值,矿工先确定Prev Hash,Merkle Hash,Timestamp,bits,然后,不断变化nonce来计算哈希,直到找出连续17个0开头的哈希值。我们可以大致推算一下,17个十六进制的0相当于计算了 16^17 次,大约需要计算2.9万亿亿次。

17个0 =  16**17  = 295147905179352825856 = 2.9万亿亿次

实际的难度是根据bits由一个公式计算出来,比特币协议要求计算出的区块的哈希值比难度值要小,这个区块才算有效:

Difficuly = 402937298
          = 0x18 0455d2
          = 0x0455d2 * 28 * (0x18 - 3)
          = 106299667504289830835845558415962632664710558339861315584
          = 0x00000000000000000455d2000000000000000000000000000000000000000000...

注意,难度值越小,说明哈希值前面的0越多,计算难度越大

比特币网络的难度值是不断变化的,它的难度值保证大约每10分钟产生一个区块,而难度值在每2015个区块调整一次:如果区块平均生成时间小于10分钟,说明全网算力增加,难度值也会增加,如果区块平均生成时间大于10分钟,说明全网算力减少,难度值也会减少。因此,难度值随着全网算力的增减会动态调整。...

代码实现

区块链、区块、哈希算法、哈希碰撞、工作量证明。
该祭出代码了。

区块:

  • sha256算法可以直接从crypto-js中引入
  • 构造器中设好该区块的属性

const SHA256 = require("crypto-js/sha256");

class Block {
    constructor(timestamp, transactions, previousHash = '') {
        this.previousHash = previousHash;
        this.timestamp = timestamp;
        this.transactions = transactions;
        this.hash = this.calculateHash();
        this.nonce = 0;
    }
    ...
    calculateHash() ..
    mineBlock(difficulty) ...
}

  • 计算区块哈希
    计算当前区块的哈希,简单的使用前一个区块哈希值,时间戳,区块交易数据,nonce 来计算。 没有引入Merkle树。
calculateHash() {
   return SHA256(this.previousHash + this.timestamp + JSON.stringify(this.transactions) + this.nonce).toString();
}

  • 区块挖矿

mineBlock(difficulty) {
      while (this.hash.substring(0, difficulty) !== Array(difficulty + 1).join("0")) {
          this.nonce++;
          this.hash = this.calculateHash();
      }
    
      console.log("\nBLOCK MINED: " + this.hash);
}
   
   

交易

一笔交易,包含谁给谁转账多少币。简单表示为:

class Transaction{
    constructor(fromAddress, toAddress, amount){
        this.fromAddress = fromAddress;
        this.toAddress = toAddress;
        this.amount = amount;
    }
}

区块链

  • 构造器设定了 第一个创世区块,难度值,等待确认的交易,以及区块奖励。
class Blockchain{
   constructor() {
       this.chain = [this.createGenesisBlock()];
       this.difficulty = 4;
       this.pendingTransactions = [];
       this.miningReward = 50;
   }
   ...
   createGenesisBlock()...
   getLatestBlock()...
   createTransaction()...
}
    
  • createGenesisBlock: 创建创世区块。
createGenesisBlock() {
   return new Block(Date.now(), [], "0");
}

  • getLatestBlock : 获取最后一个区块,当生成新区块时,需要获取上一个区块
getLatestBlock() {
   return this.chain[this.chain.length - 1];
}

  • 创建交易

生成一笔交易,push到区块链当中的pendingTransactions

createTransaction(transaction){
   console.log(`${transaction.fromAddress} send ${transaction.amount} to ${transaction.toAddress}`)
   this.pendingTransactions.push(transaction);
}

  • 矿工进行挖矿 、 生成新区块 、 奖励矿工
minePendingTransactions(miningRewardAddress){
   let block = new Block(Date.now(), this.pendingTransactions, this.getLatestBlock().hash);
   block.mineBlock(this.difficulty);

   console.log('Block successfully mined! Miner is ' + miningRewardAddress);
   this.chain.push(block);

   this.pendingTransactions = [
       new Transaction(null, miningRewardAddress, this.miningReward)
   ];
}
    
  • 验证区块链是否有效

从创世区块开始,遍历每一个区块,计算出哈希和当前哈希是否相等,验证交易数据有没有被篡改,并验证存储的前一个区块哈希值是否等于上一个区块的哈希值,保证链的有效性。
这保证了,整条链中哪怕有一个区块中的交易数据有微小的改动,都将导致区块链验证失败。

isChainValid() {
   for (let i = 1; i < this.chain.length; i++){
       const currentBlock = this.chain[i];
       const previousBlock = this.chain[i - 1];

       if (currentBlock.hash !== currentBlock.calculateHash()) {
           return false;
       }

       if (currentBlock.previousHash !== previousBlock.hash) {
           return false;
       }
   }

   return true;
}


  • 获取余额
    遍历所有交易数据。把收入和支出做一个累计。
getBalanceOfAddress(address){
        let balance = 0;

        for(const block of this.chain){
            for(const trans of block.transactions){
                if(trans.fromAddress === address){
                    balance -= trans.amount;
                }

                if(trans.toAddress === address){
                    balance += trans.amount;
                }
            }
        }

        return balance;
    }
    

运行!

过程:

  • 创建区块链。
  • Bob挖了第一个区块。此时(Bob奖励50个币,但是需要等待下一个区块确认)
  • Joe挖了第二个区块。(Bob的50个币被确认。Joe奖励的50个币,等待下一个区块确认)
  • Bob向Alice转账50
  • Alice向Bob退还25
  • Joe 挖了三个区块确认了上面两笔交易。
  • Bob 挖了第四个区块。
  • 新来的矿工 Jack 挖了第五个区块。
let codeCoin = new Blockchain();
console.log('Starting the miner...');

codeCoin.minePendingTransactions('Bob');
codeCoin.minePendingTransactions('Joe');

console.log('\nBalance of Bob is', codeCoin.getBalanceOfAddress('Bob'));

console.log("")
codeCoin.createTransaction(new Transaction('Bob', 'Alice', 50));
codeCoin.createTransaction(new Transaction('Alice', 'Bob', 25));

codeCoin.minePendingTransactions('Joe');

console.log('\nBalance of Joe is', codeCoin.getBalanceOfAddress('Joe'));

codeCoin.minePendingTransactions('Bob');

console.log('\nBalance of Joe is', codeCoin.getBalanceOfAddress('Joe'));

codeCoin.minePendingTransactions('Jack');

console.log('\nBalance of Bob is', codeCoin.getBalanceOfAddress('Bob'));
console.log('Balance of Joe is', codeCoin.getBalanceOfAddress('Joe'));
console.log('Balance of Alice is', codeCoin.getBalanceOfAddress('Alice'));
console.log('Balance of Jack is', codeCoin.getBalanceOfAddress('Jack'));

输出结果可以预测下:
每次挖矿的区块奖励50,
Bob挖了两次,奖励100
Joe挖了两次,奖励100
Jack挖了一次。奖励 50 (未确认)
Alice 和 Bob 进行了交易,于是Alice也有25,Bob变成75.

➜  js-blockchain node test.js
Starting the miner...

BLOCK MINED: 0000362f807f2388cd71b83dd1d479cb5b970313dab214d1fda73bc4e6d984a1
Block successfully mined! Miner is Bob

BLOCK MINED: 000023ac01723580e393dfaf4e08119a0a29d8719e0de28521779662da091eb2
Block successfully mined! Miner is Joe

Balance of Bob is 50

Bob send 50 to Alice
Alice send 25 to Bob

BLOCK MINED: 0000224074414014b4b11aedf73d53a22d66d7d5c3b42096de28c59a00ad516d
Block successfully mined! Miner is Joe

Balance of Joe is 50

BLOCK MINED: 0000c3de2e45f316428d412e7b4b7b1ca8b797f8c3878c4eb6ffce6152c7ddda
Block successfully mined! Miner is Bob

Balance of Joe is 100

BLOCK MINED: 00005da59c20889203d88c436aee89b308e550dd9f884d30e4c1bde62bb55832
Block successfully mined! Miner is Jack

Balance of Bob is 75
Balance of Joe is 100
Balance of Alice is 25
Balance of Jack is 0


总结

利用Javascript实现了一个的区块链。加深对一些基本概念的理解。