Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
This is a solution of week 1 for the Bitcoin and Cryptocurrency Technologies course (scrooge coin)
/**
* This is a solution of week 1 for the Bitcoin and Cryptocurrency Technologies course (scrooge coin)
* https://www.coursera.org/learn/cryptocurrency
* Please, try yourself before looking this code
* I was able to get 100/100 score!
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
public class MaxFeeTxHandler {
/**
* Creates a public ledger whose current UTXOPool (collection of unspent transaction outputs) is
* {@code utxoPool}. This should make a copy of utxoPool by using the UTXOPool(UTXOPool uPool)
* constructor.
*/
private UTXOPool currentUtxoPool;
public MaxFeeTxHandler(UTXOPool utxoPool) {
currentUtxoPool = new UTXOPool(utxoPool);
}
private static double getFee(Transaction tx, UTXOPool pool) {
double sumOfInputs = 0.0;
for(int i = 0; i < tx.numInputs(); ++i) {
Transaction.Input input = tx.getInput(i);
UTXO utxo = new UTXO(input.prevTxHash, input.outputIndex);
Transaction.Output output = pool.getTxOutput(utxo);
sumOfInputs += output.value;
}
double sumOfOutputs = 0.0;
for(int i = 0; i < tx.numOutputs(); ++i) {
sumOfOutputs += tx.getOutput(i).value;
}
return sumOfInputs - sumOfOutputs;
}
private static UTXO getUtxo(Transaction tx, int inputIndex, UTXOPool pool) {
Transaction.Input input = tx.getInput(inputIndex);
return new UTXO(input.prevTxHash, input.outputIndex);
}
/**
* @return true if:
* (1) all outputs claimed by {@code tx} are in the current UTXO pool,
* (2) the signatures on each input of {@code tx} are valid,
* (3) no 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.
*/
private static boolean isValidTx(Transaction tx, UTXOPool pool) {
// (1)
for(int i = 0; i < tx.numInputs(); ++i) {
if(!pool.contains(getUtxo(tx, i, pool))) {
return false;
}
}
// (2)
for(int i = 0; i < tx.numInputs(); ++i) {
UTXO utxo = getUtxo(tx, i, pool);
Transaction.Output output = pool.getTxOutput(utxo);
if(!Crypto.verifySignature(output.address,
tx.getRawDataToSign(i),
tx.getInput(i).signature)) {
return false;
}
}
// (3)
HashSet<UTXO> claimedSet = new HashSet<UTXO>();
for(int i = 0; i < tx.numInputs(); ++i) {
UTXO utxo = getUtxo(tx, i, pool);
if(claimedSet.contains(utxo)) {
return false;
}
claimedSet.add(utxo);
}
// (4)
for(int i = 0; i < tx.numOutputs(); ++i) {
if(tx.getOutput(i).value < 0.0) {
return false;
}
}
// (5)
return getFee(tx, pool) >= 0.0;
}
public boolean isValidTx(Transaction tx) {
return isValidTx(tx, currentUtxoPool);
}
private static void updatePool(Transaction possibleTx, UTXOPool pool) {
// 1. remove used utxo
for(int inputIdx = 0; inputIdx < possibleTx.numInputs(); ++inputIdx) {
Transaction.Input input = possibleTx.getInput(inputIdx);
UTXO utxo = new UTXO(input.prevTxHash, input.outputIndex);
pool.removeUTXO(utxo);
}
// 2. add new utxo
for(int outputIdx = 0; outputIdx < possibleTx.numOutputs(); ++outputIdx) {
Transaction.Output ouput = possibleTx.getOutput(outputIdx);
pool.addUTXO(new UTXO(possibleTx.getHash(), outputIdx), ouput);
}
}
private Transaction[] _possibleTxs;
private double _maxFee = 0.0;
private int[] _bestTxIdList = null;
private static int[] addElement(int[] a, int e) {
a = Arrays.copyOf(a, a.length + 1);
a[a.length - 1] = e;
return a;
}
private void handleTxsRecursive(UTXOPool pool, int indexStart, int[] seletectedTxIds, Double totalFee) {
if(totalFee > _maxFee) {
_maxFee = totalFee;
_bestTxIdList = seletectedTxIds;
}
for(int i = indexStart; i < _possibleTxs.length; ++i) {
Transaction tx = _possibleTxs[i];
if(isValidTx(tx, pool)) {
UTXOPool copyPool = new UTXOPool(pool);
updatePool(_possibleTxs[i], copyPool);
int [] extendedList = addElement(seletectedTxIds, i);
double fee = getFee(tx, pool);
handleTxsRecursive(copyPool, i + 1, extendedList, totalFee + fee);
}
}
}
/**
* Handles each epoch by receiving an unordered array of proposed transactions, checking each
* transaction for correctness, returning a mutually valid array of accepted transactions, and
* updating the current UTXO pool as appropriate.
*/
public Transaction[] handleTxs(Transaction[] possibleTxs) {
_possibleTxs = possibleTxs;
_maxFee = -1.0;
_bestTxIdList = new int[0];
handleTxsRecursive(currentUtxoPool, 0, _bestTxIdList, 0.0);
ArrayList<Transaction> results = new ArrayList<Transaction>();
if(_bestTxIdList != null) {
for(int i = 0; i < _bestTxIdList.length; ++i) {
results.add(_possibleTxs[_bestTxIdList[i]]);
}
}
Transaction[] r = new Transaction[results.size()];
results.toArray(r);
return r;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment