比特币与数字加密技术学习笔记week1-scrooge-coin代码分析

摘要：本文对第一周编程作业的代码分析

基础数据结构

类图

类之间的依赖图

在理解整个代码之前，我们需要理解基础的数据结构，并且将代码和课程理论相结合。

Transaction

这个类是核心的业务类，对应于理论部分的 Transaction，这里没有定义类型，作业的研究对象只是针对于 PayCoins，也就是消费交易。

Transaction 中有两个内部类， Input 和 Output。而其本身就是有一个 hash 字节数组，一个 Input 的列表和一个 Output 的列表，以及一个 rawTx 的 getter。

下面我们分别根据理论对这些类进行分析，

Transaction 中的 hash 应该是其 ID，用于唯一标志交易。所以只要是和交易进行链接，都需要使用这个 ID。

Output

我们先看 Output，该内部类很简单，只有两个字段 value 和 address，其中 value 是 double 而 address 是一个 PublicKey。这个 Output 就是理论部分中 PayCoins 类型的交易的 CreatCoins 部分，也就是 Coins 被消费销毁后又重新创建再分配的记录。这里 Output 使用在交易中 ArrayList 的 Index 来表示每一条记录的 ID。这样唯一标志某个交易中的再分配记录需要：Transaction 中的 hash 和 Output 列表的 Index 来标识。

Input

我们再看 Input，有三个字段：

preTxHash：前一个交易的 hash 值
outputIndex：前一个交易的 output 列表的下标
signature：签名

这个 Input 就是理论部分的 PayCoins 类型的交易的消费部分，理论中使用 TransID(num) 的格式标识，这里完全类似，只是增加了一个 Signature 用于验证器合法性。

理解 Input 中的签名

前面理论部分我们知道，一个交易需要有签名，这个签名做什么用呢？为了保证货币持有者对货币交易的授权是真实有效的。通过这个签名能够保证货币持有者和货币价值接受者的利益：

一旦签名，不能抵赖
一旦签名，不能篡改

举个例子，在一个交易中处理了 Alice 和 Bob 两个人每个人各一个 Coin 的消费。那么为了得到两个人的确认，他们确实自己主观要消费各自的 Coin，他们需要使用自己的私钥对指定的内容进行前面，这个过程只能两个人本人持有私钥才能实现，所以他们自己是不能抵赖的。

但是需要对哪些内容进行签名呢？这里还需要防止篡改，比如 Alice 本来只想将一半的价值转移给其他人，但是被别人篡改为将全部转移给其他人。这个签名必须能够检测这种篡改，显然我们需要将所有的不能被篡改的数据提取出来，一起进行签名，这样一旦有人篡改，篡改者没有 Alice 的私钥，所以他无法生成一个能够被公钥正确验证的签名。

这个所需要签字的内容在已有代码中已经提供了，就是 getRawDataToSign(int index)，一个交易有多个 input，每个 Input 分别进行签名：

 public byte[] getRawDataToSign(int index) {
	// ith input and all outputs
	ArrayList<Byte> sigData = new ArrayList<Byte>();
	if (index > inputs.size())
		return null;
	// 取出 Input	
	Input in = inputs.get(index);
	// 获取前一个交易的 ID
	byte[] prevTxHash = in.prevTxHash;
	// input 中保存的 output 的 index
	// 注意这里，我们如果 想把 Integer 转化为 byte，需要做一下这样一组操作
	//     后面在处理 Double 类型的 output value，思路是一样的
	ByteBuffer b = ByteBuffer.allocate(Integer.SIZE / 8);
	b.putInt(in.outputIndex);
	byte[] outputIndex = b.array();
	// 签名数据： 前一个交易的 ID
	if (prevTxHash != null)
		for (int i = 0; i < prevTxHash.length; i++)
			sigData.add(prevTxHash[i]);
	// 签名数据，output index		
	for (int i = 0; i < outputIndex.length; i++)
		sigData.add(outputIndex[i]);
	// 签名数据：所有的 output 的 value 和 address
	for (Output op : outputs) {
		ByteBuffer bo = ByteBuffer.allocate(Double.SIZE / 8);
		bo.putDouble(op.value);
		byte[] value = bo.array();
		byte[] addressBytes = op.address.getEncoded();
		for (int i = 0; i < value.length; i++)
			sigData.add(value[i]);

		for (int i = 0; i < addressBytes.length; i++)
			sigData.add(addressBytes[i]);
	}
	// 将 ArrayList<Byte> 转化为 byte[]
	byte[] sigD = new byte[sigData.size()];
	int i = 0;
	for (Byte sb : sigData)
		sigD[i++] = sb;
	return sigD;
}

有了这个函数，我们就可以获取当前交易对应 input 需要签名的数据，也进而可以使用它反过来验证。

交易处理过程思考

在介绍其他数据结构之前，我们先理解一下程序的目标，也就是怎么处理交易。通过前面的学习，我们知道 Scrooge Coin 主要目标就是解决 Double Spending 问题，所以我们这里的交易处理肯定是要能够避免双花，下面我们来看一下是如何避免的。

理论中我们是把交易动作分解为两步，先消费销毁，再分配价值。通过这两步就能在再分配价值前，对其合法性进行验证。

交易处理的切入点是再分配，也就是 Output，在实际中就是处理将价值分配到指定的人的钱包。但是在处理 Output 的时候会追溯到 Input 来验证这些 Output 是否合法。

由于交易是链状的（input 维护着指向前一个交易的 output），所以交易处理不是孤立的处理某一个交易，而必须有其相关联的所有交易的支持。这样我们必须引入一个交易池。

我们再思考，交易和其他交易关联的重点是什么呢？也就是 Input 是和什么进行关联的呢？答案是 Output。所以我们不需要将交易放到池中，而是将 Output 放到池中，这样处理交易时，Input 就能找到相关联的前一个 Output。

这样就引出了我们即将要介绍的 UTXO 和 UTXOPoll，个人认为这种缩写有点扰乱理解，他们各自的含义是：

UTXO：Unspent Transaction Output，就是我们前面说的还未被处理的 output
UTXOPool: Pool of Unspent Transaction Output：这个就是还未被处理的 output 的交易池

UTXO 和 UTXOPool

UTXO 包含两个字段：交易的ID txHash 和交易中 output 的 index

UTXO，虽然称之为 Unspent Transaction Output，但实际上他只是一个索引，而并不包含 output 内容，需要通过这个索引找到 output。我们可以把交易的 hash 和 output 的索引进行组合看做一个索引，这个索引就是 UTXO。

给出一个 UTXO，实际上就能唯一的确认一个 output，首先通过 txHash 找到交易，在通过 index 找到 output。

这里有引入一个 UTXOPool，实际上就是把前面的 UTXO 和具体的 output 进行组合然后放到一个池中。具体实现就是维护一个 HashMap<UTXO, Transaction.Output> H;， UTXO 是索引，Transaction.Output 是具体内容。实际中，每次有未被处理的交易产生，都需要将所有的 output 放入到这个池中等待处理。

程序结构概述

通过上面的分析，我们可以对该程序进行如下描述：

该系统是处理 Scrooge Coin 系统的交易，其主要功能是验证交易的合法性并对交易进行处理生成账本记录。

作为程序的数据，会有一批交易生成，这些交易生成之后，需要将 Unspent Transaction Output 放到池中来让处理器进行处理。

交易验证过程

课程的代码已经给出验证交易所需要的条件

/**
     * @return true if:
     * (1) all outputs claimed by {@code tx} are in the current ScroogeCore.UTXO pool,
     * (2) the signatures on each input of {@code tx} are valid,
     * (3) no ScroogeCore.UTXO is claimed multiple times by {@code tx},
     * (4) all of {@code tx}s output values are non-negative, and
     * (5) the sum of {@code tx}s input values is greater than or equal to the sum of its output
     * values; and false otherwise.
     */
    public boolean isValidTx(Transaction tx) {}

这里我们将代码和其对应的功能点一起进行说明

(1) all outputs claimed by {@code tx} are in the current ScroogeCore.UTXO pool

在交易 tx 中所有的 output 都必须在等钱的 UTXO pool 中，只有在 Pool，我们才能验证该 output 是否存在 double spending 问题。

 // create unspent transaction output based on input information
UTXO lastUTXO = new UTXO(input.prevTxHash, input.outputIndex);
// check 1 - all output claimed by tx are in current utxopool
if (!pool.contains(lastUTXO)) {
	return false;
}
 // pool contain the utxo, get the output
Transaction.Output prevTx = pool.getTxOutput(lastUTXO);

(2) the signatures on each input of {@code tx} are valid

input 中的 signature 必须是有效的，我们前面介绍了这个 Signature 的意思，这里很简单，使用已经提供验证方法来实现:

 // check 2 - signatures of each input are valid
if (input.signature == null || !Crypto.verifySignature(prevTx.address, tx.getRawDataToSign(i), input.signature)) {
	return false;
}

该方法 Crypto.verifySignature 第一个参数是公钥，第二个参数是签名的数据，第三个就是签名。其过程如下，主要使用JDK 提供的 Sigature 类来完成这个工作。

Signature sig = null;
sig = Signature.getInstance("SHA256withRSA");
sig.initVerify(pubKey);
sig.update(message);
return sig.verify(signature);

(3) no ScroogeCore.UTXO is claimed multiple times by {@code tx},

不能双花，这里使用一个临时的 UTXO 的 HashSet 来保存已经处理的 UTXO，最后通过该值数量和 Input的数量对比来确定是否有多次被花费。我们知道 HashSet 会自动去除重复值，使用该特性来巧妙的判断

// traverse all the input in the transaction,
HashSet<UTXO> utxoSet = new HashSet<>();
for (Transaction.Input input : tx.getInputs()) {
	// create unspent transaction output based on input information
	UTXO lastUTXO = new UTXO(input.prevTxHash, input.outputIndex);
				// signature verify successfully, add it to spend set.
	utxoSet.add(lastUTXO);
}

// check 3 - no utxo is claimed multiple times  ?
if (utxoSet.size() != tx.getInputs().size())
	return false;

(4) all of {@code tx}s output values are non-negative, and

// check 4 - non negative output values
for (Transaction.Output output : tx.getOutputs()) {
	sumOfOutputVals += output.value;
	if (output.value < 0)
		return false;
}

(5) the sum of {@code tx}s input values is greater than or equal to the sum of its output values; and false otherwise.

我们需要从上一个 Transaction 中的 output 获取 input 所对应的 value

// statistic the sum of input value which will be used to check the balance of input and output
sumOfInputVals += prevTx.value;

// check 5 - validating input values >= sum of output values
if (sumOfInputVals < sumOfOutputVals)
	return false;

作业提交单元测试分析

下面我们根据单元测试来确定我们代码的目标是否都满足

Test 1: test isValidTx() with valid transactions
==> passed

Test 2: test isValidTx() with transactions containing signatures of incorrect data
==> passed

Test 3: test isValidTx() with transactions containing signatures using incorrect private keys
==> passed

Test 4: test isValidTx() with transactions whose total output value exceeds total input value
==> passed

Test 5: test isValidTx() with transactions that claim outputs not in the current utxoPool
==> passed

Test 6: test isValidTx() with transactions that claim the same UTXO multiple times
==> passed

Test 7: test isValidTx() with transactions that contain a negative output value
==> passed

至此我们就把如何验证一个 Transaction 介绍完了。下面介绍如何处理一组可能的 Transaction

交易组处理

单元测试

Test 8: test handleTransactions() with simple and valid transactions
Total Transactions = 2
Number of transactions returned valid by student = 2
Total Transactions = 50
Number of transactions returned valid by student = 50
Total Transactions = 100
Number of transactions returned valid by student = 100
==> passed

Test 9: test handleTransactions() with simple but some invalid transactions because of invalid signatures
Total Transactions = 2
Number of transactions returned valid by student = 0
Total Transactions = 50
Number of transactions returned valid by student = 2
Total Transactions = 100
Number of transactions returned valid by student = 1
==> passed

Test 10: test handleTransactions() with simple but some invalid transactions because of inputSum < outputSum
Total Transactions = 2
Number of transactions returned valid by student = 2
Total Transactions = 50
Number of transactions returned valid by student = 25
Total Transactions = 100
Number of transactions returned valid by student = 42
==> passed

Test 11: test handleTransactions() with simple and valid transactions with some double spends
Total Transactions = 2
Number of transactions returned valid by student = 1
Total Transactions = 50
Number of transactions returned valid by student = 21
Total Transactions = 100
Number of transactions returned valid by student = 42
==> passed

Test 12: test handleTransactions() with valid but some transactions are simple, some depend on other transactions
Total Transactions = 2
Number of transactions returned valid by student = 2
Total Transactions = 50
Number of transactions returned valid by student = 29
Total Transactions = 100
Number of transactions returned valid by student = 83
Returned set is not a maximal set of transactions
==> FAILED

Test 13: test handleTransactions() with valid and simple but some transactions take inputs from non-exisiting utxo's
Total Transactions = 2
Number of transactions returned valid by student = 1
Total Transactions = 50
Number of transactions returned valid by student = 12
Total Transactions = 100
Number of transactions returned valid by student = 57
==> passed

Test 14: test handleTransactions() with complex Transactions
Total Transactions = 2
Number of transactions returned valid by student = 2
Total Transactions = 50
Number of transactions returned valid by student = 10
Total Transactions = 100
Number of transactions returned valid by student = 30
==> passed

Test 15: test handleTransactions() with simple, valid transactions being called again to check for changes made in the pool
Total Transactions = 2
Number of transactions returned valid by student = 2
Total Transactions = 50
Number of transactions returned valid by student = 48
Total Transactions = 100
Number of transactions returned valid by student = 52
Returned set is not a maximal set of transactions
==> FAILED

实现过程

目前有两种方法

不动点算法

参考介绍

这一个是给你组乱序的交易 TX[] 让你返回其中有效的交易，注意只检查一遍是不够的，因为新交易的加入 UTXOPool可能会使得后面又有新的合法交易出现。最简单的做法就是不动点算法，每次遍历，看看是否结果有更新，如果有继续遍历，直到没有为止，最终一定会收敛到全部加入，而且每次至少会加入一个交易

checkIfMutuallyValid

参考源码

checkIfMutuallyValid 貌似是检查一下 Map<ComparableTransactionInput, ArrayList<Transaction>> 一个 map 的映射关系是否唯一，这部分代码还需要好好理解一下。

附加题

Extra Credit: Create a second file called MaxFeeTxHandler.java whose handleTxs() method
finds a set of transactions with maximum total transaction fees — i.e. maximize the sum over all
transactions in the set of (sum of input values - sum of output values)).

单元测试

Running 1 tests

Test 1: test handleTransactions() with simple and valid transactions
Total Transactions = 2
Number of transactions returned valid by student = 1
Correct, Returned fees 0.0017396507581575746 = maximum fees 
Total Transactions = 10
Number of transactions returned valid by student = 3
Returned set is not a maximum fees set of transactions
Returned fees 0.010941092961145933, maximum fees 0.011991189987225814
Total Transactions = 30
Number of transactions returned valid by student = 10
Returned set is not a maximum fees set of transactions
Returned fees 0.029151874533288123, maximum fees 0.03345190404025702
==> FAILED


Total:0/1 tests passed!