一个极简的区块链实现——财奴币

本文主要介绍了普林斯顿大学公开课《比特币和数字货币技术》中的作业1和作业3中财奴币的实现过程,这里主要整理一下思路,并给出了代码实现。其中有部分代码参考了GitHub上其他人的作业,在此表示感谢。

作业1主要与交易有关。首先来看交易类Transaction,该类有四个成员变量,两个成员内部类Input和Output分别表示交易的输入和输出,以及用于交易相关操作的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Transaction {
...
private byte[] hash; // 交易的哈希值 (后面省略了getter和setter方法)
private ArrayList<Input> inputs; // 交易的输入
private ArrayList<Output> outputs; // 交易的输出
private boolean coinbase; // 是否币基交易
...
/* 重要的成员方法 */
public void addInput(byte[] prevTxHash, int outputIndex); // 添加输入
public void addOutput(double value, PublicKey address); // 添加输出
public void removeInput(int index); // 根据索引删除输入
public void removeInput(UTXO ut); // 根据UTXO删除输入
public Input getInput(int index); // 根据索引获取输入
public Output getOutput(int index); // 根据索引获取输出
public int numInputs(); // 输入数量
public int numOutputs(); // 输出数量
public byte[] getRawDataToSign(int index); // 把交易中第i个输入的相关信息序列化
public byte[] getRawTx(); // 把交易序列化
public void addSignature(byte[] signature, int index); // 对第i个输入签名
...
public class Input {
public byte[] prevTxHash; // 前一交易哈希
public int outputIndex; // 已使用的交易输出在前一交易中的索引
public byte[] signature; // 校验有效性的签名
public Input(byte[] prevHash, int index); // 构造方法需要提供前一交易哈希和交易输出在交易中的索引
public void addSignature(byte[] sig); // 添加签名
}
public class Output {
public double value; // 交易金额
public PublicKey address; // 输出地址(公钥)
}
}

getRawDataToSign()方法得到交易中第i个输入的序列化信息,以便于对其签名。其中序列化的内容包括:第i个Input的prevTxHash,所有Output的value和address。

内容 prevTxHash outputIndex value addr value addr
字节数 var 4 4 var 4 var

getRawTx()方法与getRawDataToSign()方法功能类似,只是序列化内容包括了所有Input的prevTxHash、outputIndex和signature,以及所有Output的value和address。

UTXO类代表了未消费的交易输出。可以看出UTXO相当于交易输出的摘要和索引。

1
2
3
4
5
6
7
8
public class UTXO implements Comparable<UTXO> {
private byte[] txHash; // 该UTXO对应TX的哈希值
private int index; // 输出在TX中对应的索引
public UTXO(byte[] txHash, int index) {
this.txHash = Arrays.copyOf(txHash, txHash.length);
this.index = index;
}

UTXOPool类持有一个键为UTXO,值为Transaction.Output的HashMap对象。

在作业1中要求实现一个TxHandler类,实现以下功能:

1
2
3
4
5
6
public class TxHandler {
public TxHandler (UTXOPool utxoPool); // 根据UTXOPool创建TxHandler
public boolean isValidTx (Transaction tx); // 校验交易有效性
public Transaction[] handleTxs (Transaction[] possibleTxs); // 返回有效交易集合,并更新UTXOPool
}

财奴币规定,如果以下条件为真,交易有效。

  • 交易中声明的所有输出均在当前的UTXOPool中出现
  • 每个输入的签名是有效的
  • 没有UTXO被交易声明多次(即未出现多重支付)
  • 所有输出的值是非负的
  • 交易的所有输入值的和大于等于所有输出值的和

基于以上条件,实现isValidTx()方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public boolean isValidTx(Transaction tx) {
HashSet<UTXO> utxoSeen = new HashSet<>();
ArrayList<Transaction.Output> outputs = tx.getOutputs();
ArrayList<Transaction.Input> inputs = tx.getInputs();
double totalOutput = 0.0;
double totalInput = 0.0;
for (int i = 0; i < tx.getInputs().size(); i++) {
Transaction.Input input = tx.getInput(i);
UTXO ut = new UTXO(input.prevTxHash, input.outputIndex);
if (!utxoSeen.add(ut)) { // 条件3
return false;
}
Transaction.Output output = utxoPool.getTxOutput(ut);
if (output == null) { // verify 条件1
return false;
}
if (!Crypto.verifySignature(output.address, tx.getRawDataToSign(i), input.signature)) { // 条件2
return false;
}
totalInput += output.value;
}
for (Transaction.Output output : outputs) {
if (output.value < 0.0) {
return false; // 条件4
}
totalOutput += output.value;
}
return (totalInput >= totalOutput); // 条件5
}

其中用到的Crypto类是一个工具类,提供一个静态的verifySignature()方法用于验证签名的有效性。作业中不要求根据私钥计算签名。

另一个方法handleTxs()用于处理一系列交易,传入参数为Transaction[],该方法需要对传入的所有交易逐条校验其有效性,返回所有有效的交易,并更新UTXOPool。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public Transaction[] handleTxs(Transaction[] allTx) {
Transaction[] stuckTxs = Arrays.copyOf(allTx, allTx.length);
Transaction[] tempTxs = new Transaction[allTx.length];
Transaction[] successTxs = new Transaction[allTx.length];
int tempCounter = 0, successCounter = 0;
int stuckSize = allTx.length;
while (true) {
boolean change = false;
tempCounter = 0;
for (int i = 0; i < stuckSize; i++) {
if (inPool(stuckTxs[i])) {
if (isValidTx(stuckTxs[i])) {
change = true;
updatePool(stuckTxs[i]);
successTxs[successCounter++] = stuckTxs[i];
}
} else {
tempTxs[tempCounter++] = stuckTxs[i];
}
}
if (change) {
for (int i = 0; i < tempCounter; i++) {
stuckTxs[i] = tempTxs[i];
}
stuckSize = tempCounter;
} else {
break;
}
}
Transaction[] result = new Transaction[successCounter];
for (int i = 0; i < successCounter; i++)
result[i] = successTxs[i];
return result;
}

其中用到了inPool()updatePool()方法,分别用于判断交易是否在UTXOPool中,和根据交易更新UTXOPool。校验交易是否在池中,只需根据交易中的所有Input创建出UTXO对象,检验这些UTXO对象是否在池中即可。

1
2
3
4
5
6
7
8
9
10
11
12
private boolean inPool(Transaction tx) {
ArrayList<Transaction.Input> inputs = tx.getInputs();
Transaction.Input in;
UTXO ut;
for (int i = 0; i < inputs.size(); i++) {
in = inputs.get(i);
ut = new UTXO(in.prevTxHash, in.outputIndex);
if (!utxoPool.contains(ut))
return false;
}
return true;
}

更新UTXOPool,只需根据Transaction中的Input找到池中对应的UTXO并将其删除,根据Output创建一个UTXO并添加到池中即可。

1
2
3
4
5
6
7
8
9
10
private void updatePool(Transaction tx) {
for (int i = 0; i < tx.getInputs().size(); i++) { // 删除原有UTXO
Transaction.Input in = tx.getInput(i);
utxoPool.removeUTXO(new UTXO(in.prevTxHash, in.outputIndex));
}
for (int i = 0; i < tx.getOutputs().size(); i++) { // 添加新UTXO
Transaction.Output out = tx.getOutput(i);
utxoPool.addUTXO(new UTXO(tx.getHash(), i), out);
}
}

UTXO就是未交易输出的一种索引表示,通过交易哈希和输出在交易中的索引唯一确定一个输出。

以上只是实现了UTXO与Transaction之间的交互,还未实现将Transaction存储到区块链中。作业3中提供了BlockBlockHandlerTransactionPool等几个类,用来实现交易信息与区块链的交互。

Block中有本区块的哈希值,前一区块的哈希值,本区块对应的币基交易,区块中的所有交易。构建一个区块需要提供前一区块的哈希,以及公钥地址(以便生成一笔币基交易给矿工,在这里就是财奴)。在finalize()方法中通过SHA-256算法生成本区块的哈希摘要,摘要的内容包括prevBlockHash和区块中除了币基交易的所有交易信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Block {
public static final double COINBASE = 25;
private byte[] hash;
private byte[] prevBlockHash;
private Transaction coinbase;
private ArrayList<Transaction> txs;
public Block(byte[] prevHash, PublicKey address) {
prevBlockHash = prevHash;
coinbase = new Transaction(COINBASE, address);
txs = new ArrayList<Transaction>();
}
// 省略了getter方法
public void addTransaction(Transaction tx); // 向区块中添加一笔交易
public byte[] getRawBlock(); // 获取区块序列化结果,内容包括prevBlockHash和txs
public void finalize() { // 不知道为什么把生成区块hash的操作放在这里?
try {
MessageDigest md = MessageDigest.getInstance("SHA-256");
md.update(getRawBlock());
hash = md.digest();
} catch (NoSuchAlgorithmException x) {
x.printStackTrace(System.err);
}
}
}

BlockHandler持有一个BlockChain对象,并提供了操作区块链的各种方法。该类可以认为是节点操作区块链的代理,而该类内部则通过BlockChain对象进行底层的区块链操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class BlockHandler {
private BlockChain blockChain; // 持有一个本地的区块链
public boolean processBlock(Block block) { // 校验区块,非空即添加到链上
if (block == null)
return false;
return blockChain.addBlock(block);
}
public Block createBlock(PublicKey myAddress) { // 在主链上创建区块
Block parent = blockChain.getMaxHeightBlock();
byte[] parentHash = parent.getHash();
Block current = new Block(parentHash, myAddress);
UTXOPool uPool = blockChain.getMaxHeightUTXOPool();
TransactionPool txPool = blockChain.getTransactionPool();
TxHandler handler = new TxHandler(uPool);
Transaction[] txs = txPool.getTransactions().toArray(new Transaction[0]);
Transaction[] rTxs = handler.handleTxs(txs);
for (int i = 0; i < rTxs.length; i++)
current.addTransaction(rTxs[i]);
current.finalize(); // 显式调用区块的finalize()
if (blockChain.addBlock(current))
return current;
else
return null;
}
public void processTx(Transaction tx) { // 添加交易至区块链交易池
blockChain.addTransaction(tx);
}
}

processBlock()方法可以理解为节点收到一个其他节点广播的新区块后,将该区块添加到本地的区块链上。createBlock()方法可以认为节点”挖到”一个新区块,则首先将其添加到本地区块链,将返回一个Block对象以便进一步向其他节点进行广播(这些都是我猜的)。processTx()方法可以认为是节点收到其他节点广播的交易信息,将其添加到本地的交易池中(注意不是直接添加到链上)。

交易池为TransactionPool类,提供了交易哈希值到交易对象的映射。ByteArrayWrapper为提供了equals()和hashCode()的byte[]的封装类。

1
2
3
4
public class TransactionPool {
private HashMap<ByteArrayWrapper, Transaction> H;
// 省略了add, remove, get, gets方法
}

BlockChain类定义了对区块链的各种底层操作。

1
2
3
4
5
6
7
8
9
10
11
public class BlockChain {
public static final int CUT_OFF_AGE = 10;
/* 待实现的方法 */
public BlockChain(Block genesisBlock); // 根据创世区块创建区块链
public Block getMaxHeightBlock(); // 获取最大高度的区块
public UTXOPool getMaxHeightUTXOPool(); // 获取最大高度的UTXOPool
public TransactionPool getTransactionPool(); // 获取交易池
public boolean addBlock(Block block); // 添加区块
public void addTransaction(Transaction tx); // 添加交易
}

为便于对Block对象进行操作,创建一个内部类Node,用于对Block对象进行封装,以将各个区块按照链接关系组织成链式结构,便于进行操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private class Node {
Node parent;
List<Node> children;
int height;
Block block;
UTXOPool utxoPool;
public Node(Node parent, Block block, UTXOPool up) {
this.parent = parent;
this.block = block;
this.utxoPool = up;
this.children = new ArrayList<>();
if(parent != null){
parent.children.add(this);
this.height = parent.height+1;
} else {
this.height = 1;
}
}
public UTXOPool getUTXOPool() {
return new UTXOPool(utxoPool);
}
}

首先实现addTransaction()方法和getTransactionPool()方法。向该类加入一个TransactionPool对象,并将Transaction添加至池中。

1
2
3
4
5
6
7
8
9
private TransactionPool transactionPool;
public void addTransaction(Transaction tx) {
this.transactionPool.addTransaction(tx);
}
public TransactionPool getTransactionPool() {
return this.transactionPool;
}

在作业3中给出了以下假设:

  • 如果向addBlock(Block b)方法传入一个创世区块,可直接返回false。
  • 如果同一高度存在多个区块,则getMaxHeightBlock()会返回最先加入的一个。
  • 假设区块中的币基交易在下一个区块即可被消费。(比特币协议则要求100个确认后才可消费)
  • 只为区块链维护一个全局交易池,接收到交易则向其添加,接收到或者创建区块则删除区块中的交易。特别地,曾经在主链中的交易但现在在分支中,则该交易会丢失(因为交易池已经在区块接收或创建时删除了)。
  • 币基值保持为25个币(与实际运行的4年减半不同)。
  • 校验一个新接收的区块时,只校验交易的格式是否正确就可以了。不需要保证交易集合是最大可能集合。此外,也不需要进行PoW校验。

要获得最大高度的区块,以及最大高度的UTXOPool,需要获得最大高度的Node。为便捷地查找到Node,在类中添加一个区块哈希值到Node对象的Map。添加一个Node变量指向高度最大的节点,添加一个int变量指示当前区块链的最大高度。考虑到同一高度有可能存在多个区块,添加一个List变量表示目前的头节点列表。

1
2
3
4
private ArrayList<Node> HeadNode;
private HashMap<ByteArrayWrapper,Node> HashBH;
private int maxHeight;
private Node maxHNode;

根据创世区块创建区块链:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public BlockChain(Block genesisBlock) {
Transaction coinbase = genesisBlock.getCoinbase();
UTXOPool uPool = new UTXOPool();
UTXO utxoCoinbase = new UTXO(coinbase.getHash(),0); // 币基交易只有1个输出
uPool.addUTXO(utxoCoinbase, coinbase.getOutput(0));
Node gen = new Node(null,genesisBlock,uPool);
this.HeadNode = new ArrayList<>();
this.HeadNode.add(gen);
this.HashBH = new HashMap<>();
this.HashBH.put(new ByteArrayWrapper(genesisBlock.getHash()), gen);
this.maxHeight = 1; // 创世区块高度为1
maxHNode = gen; // 最大高度Node
this.transactionPool = new TransactionPool();
}

直接从maxHNode中获取block和UTXOPool:

1
2
3
4
5
6
7
public Block getMaxHeightBlock() {
return maxHNode.block;
}
public UTXOPool getMaxHeightUTXOPool() {
return maxHNode.getUTXPool();
}

最后,实现addBlock()方法。首先,根据传入区块的prevBlockHash找到其父区块。随后,通过父区块获取UTXOPool,以此校验区块中的所有交易。然后,向UTXOPool中添加该区块中的币基交易。然后,以该区块创建一个Node。从交易池中移除区块中的交易。更新链的高度和最高的节点。如果新的区块的高度比最高区块的高度小10及以上,则不会添加该Node至Map中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public boolean addBlock(Block block) {
byte[] prevHash = block.getPrevBlockHash();
if (prevHash == null){
return false;
}
Node prevNode = this.HashBH.get(new ByteArrayWrapper(prevHash));
if (prevNode == null){
return false;
}
TxHandler handler = new TxHandler(prevNode.getUTXPool());
ArrayList<Transaction> TXs = block.getTransactions();
Transaction[] validTXs = new Transaction[TXs.size()];
validTXs = handler.handleTxs(TXs.toArray(validTXs));
if (validTXs.length < TXs.size()){
return false;
}
UTXOPool pool = handler.getUTXOPool();
Transaction coinbase = block.getCoinbase();
pool.addUTXO(new UTXO(coinbase.getHash(),0), coinbase.getOutput(0));
Node newNode = new Node(prevNode,block,pool);
this.HashBH.put(new ByteArrayWrapper(block.getHash()), newNode);
for(Transaction tx :block.getTransactions()){
this.transactionPool.removeTransaction(tx.getHash());
}
if( (prevNode.height +1) > this.maxHeight){
this.maxHeight = prevNode.height + 1;
this.maxHNode = newNode;
}
if (newNode.height > this.maxHeight - CUT_OFF_AGE){
return true;
}else{
return false;
}
}

至此,一个”中心化”的财奴币系统就完成了。然而,系统中简化了区块链中交易信息的表现形式,采用链表存储交易信息而非Merkle树,无法通过哈希摘要快速验证交易的有效性。此外,由于系统中定义了一个财奴角色进行中心化记账,因此分布式共识机制在系统中也没有体现。