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

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

基础数据结构

类图

UML

类之间的依赖图

uml-dependency

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

Transaction

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

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

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

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

Output

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

Input

我们再看 Input,有三个字段:

  1. preTxHash:前一个交易的 hash
  2. outputIndex:前一个交易的 output 列表的下标
  3. signature:签名

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

理解 Input 中的签名

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

  1. 一旦签名,不能抵赖
  2. 一旦签名,不能篡改

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

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

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

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
40
41
 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

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

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

UTXO 和 UTXOPool

UTXO 包含两个字段: 交易的ID txHash 和 交易中 outputindex

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

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

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

程序结构概述

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

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

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

交易验证过程

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

1
2
3
4
5
6
7
8
9
10
/**
* @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 问题。

1
2
3
4
5
6
7
8
 // 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 的意思,这里很简单,使用已经提供验证方法来实现:

1
2
3
4
 // 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 类来完成这个工作。

1
2
3
4
5
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},

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

1
2
3
4
5
6
7
8
9
10
11
12
// 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

1
2
3
4
5
6
// 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

1
2
3
4
5
6
// 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;

作业提交单元测试分析

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

交易组处理

单元测试

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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)).

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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!