Java Work

1. COMP 311 Lab03
   1. 1. Purpose

To assess your ability to apply the knowledge and skills developed in Modules 6 and 7. Emphasis will be placed on heaps and priority queues as well as relevant design patterns.

1. 1. 1. Assignment

For this lab, we will be building part of a node in the Bitcoin network. The two main jobs of a node are to keep track of the currently accepted blockchain and any forks, and to validate and track pending transactions and attempt to generate a new valid block containing them. You will only have to build small pieces of the node, the rest of the code is assumed to already exist.

This lab will use different version of the classes from Lab 2 to represent the blockchain, transactions, etc. You’ll be able to copy some of the code from that lab to fill in these classes, but pay attention to which methods are needed – you won’t need all of the code from Lab 2, and there are some new methods that you will need to implement for this one.

Definitions

Transaction Fee - The difference between the total output amount of a transaction and the total input amount. This can be zero or more.

UTXO – Unspent Transaction Output. This is an output in the blockchain that indicates that some amount of bitcoins belong to a certain address. Ownership of some amount of bitcoins means that there is a UTXO with that amount tied to your address.

TransactionManager

public void addPendingTransaction(Transaction tx)

Bitcoin nodes receive transactions from other nodes, and then attempt to create a new valid block containing those transactions. This method would be called when a transaction has been received over the network, and would add the given transaction to the list of potential transactions for the next block that will be generated.

public List<Transaction> getTransactionsForNextBlock()

This method will return the pending transactions that would be included in the next block if this node generated a hash successfully. In this lab, we will be limiting the number of transactions per block to three. If there are more than three pending transactions, this should return the best ones – the transactions with the highest transaction fees.

public List<Transaction> getQueuedTransactions()

This method will return the pending transactions that will not be included in the next block – every pending transaction except for the three with the highest transaction fees.

public int getUTXO(String addr)

As blocks are added to the chain, the TransactionManager will keep track of the UTXO. This method will return the amount of a UTXO for the given address, or zero if there is no matching UTXO.

public void executeBlock(Block block)

A real Bitcoin node would receive accepted blocks over the network from other nodes, and after validating them, add them to the blockchain. This method will assume that the supplied block has been received and validated. It will then update the current list of UTXO – the inputs to this block will be marked as spent, and its outputs will be new UTXO. It will also need to update the pending and queued transactions.

public void undoBlock(Block block)

When there is a fork in the blockchain, a block can be accepted at first, but then be rolled back as some other branch of the chain grows longer and becomes accepted. When this happens, this method would be called to undo the transaction contained within the given block. This method is essentially the reverse of executeBlock(). It will update the same data structures.

public boolean isBlockValid(Block newBlock)

This method will check the given block for validity. A real Bitcoin node would do much more extensive checking, but we will only be checking a few things. This method will return the result of validation, but not modify any data inside the TransactionManager.

• The first transaction in the block must be the coinbase transaction. It will have no inputs, and its total output amount will be the block reward (25) plus the total transaction fees for the block.

• Any outputs that are spent by the block will be checked against the current list of UTXO.

• The amounts of the UTXO that are being spent by the block must match the amounts the block is using in its inputs – you can’t spend part of a UTXO, the whole amount must be spent at once.

• The sum of the input amounts for every transaction in the block except for the coinbase transaction must match or exceed the sum of the output amounts.

1. 1. 1. Examples

TransactionManager tm = new TransactionManager();

Block b = new Block("hash1");

Transaction tx = new Transaction("cb1");

tx.addOutput(new TxOutput("addr1", 100));

b.addTransaction(tx);

tm.executeBlock(b);

assertEquals(100, tm.getUTXO("addr1"));

b = new Block("hash2");

tx = new Transaction("cb2");

tx.addOutput(new TxOutput("addr2", 50));

b.addTransaction(tx);

tx = new Transaction("transfer");

tx.addInput(new TxInput("addr1", 100));

tx.addOutput(new TxOutput("addr3", 75));

tx.addOutput(new TxOutput("addr4", 25));

b.addTransaction(tx);

tm.executeBlock(b);

assertEquals(50, tm.getUTXO("addr2"));

assertEquals(0, tm.getUTXO("addr1"));

assertEquals(75, tm.getUTXO("addr3"));

assertEquals(25, tm.getUTXO("addr4"));

In the example test case above, a block is created with only one transaction that sends 100 bitcoins to addr1. Once this block is executed, getUTXO(“addr1”) returns 100. A second block is then created that sends 50 bitcoins to addr2, and transfers the 100 original bitcoins from addr1 to addr3 and addr4. Calling getUTXO() on the addresses now returns their new balances.

1. 1. 1. Hints

The following hints should help you design and implement your solution.

1. The most natural way to handle pending transactions is with a priority queue. For this lab, you are not allowed to use the PriorityQueue class that is supplied with the JDK – you must write your own heap-based priority queue. The PQ class in the starter project will get you started. Your priority queue should behave as a max-heap if the supplied comparator uses the compareTo() method of its elements.

2. executeBlock() doesn’t do any validation of the block. Other code would call validateBlock() before calling executeBlock(). This also gives you a little more flexibility in writing your tests for executeBlock().

3. The TxInput class has a new member that can be used to keep track of the TxOutput that this input is spending. This could be useful in undoBlock().

4. Use a test-driven approach! Start with a simple test case, and work your way up to a more complicated example. It's also a good idea to write tests for your priority queue before attempting to use it in your other code.

1. 1. 1. Design

Your design is important. Though a starter project is provided, you should consider what other classes or interfaces are appropriate in your solution. A substantial portion of your score will be based on the design of your solution.

1. 1. 1. Deliverables

Submit your program via the Eclipse submitter to the Web-CAT server on or before the due date given in your syllabus.