assignment1 snippet

txhandler.java

    /**
     * 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) {
        // The side effect is to advance the state of the pool.
        // Convert the unordered list into a graph, and perform topological sort

        /** Mapping from hash to corresponding transaction. */
        HashMap<byte[], Transaction> T = new HashMap<byte[], Transaction>();

        /** Mapping from txHash to all the claimed transaction. */
        HashMap<byte[], ArrayList<byte[]>> M = new HashMap<byte[], ArrayList<byte[]>>();

        ArrayList<Transaction> validTxs = new ArrayList<Transaction>();

        for (Transaction tx: possibleTxs) {
            byte[] hash = tx.getHash();
            T.put(hash, tx);
            for (Transaction.Input in : tx.getInputs()) {
                if (!M.containsKey(hash)) {
                    M.put(tx.getHash(), new ArrayList<byte[]>());
                }

                // NOTE: only add txHash within possibleTxs
                if (T.containsKey(in.prevTxHash)) {
                    M.get(hash).add(in.prevTxHash);
                }
            }
        }

        // NOTE: This won't return the maximal number of transactions.
        // Process transaction in topological order, when there are two choices, pick one
        // according to the incoming order.
        while (M.size() != 0) {
            // TODO: This is just to mute compiler warnings for uninitialized variable.
            byte[] selectedHash = possibleTxs[0].getHash();
            Transaction selectedTx = possibleTxs[0];

            for (byte[] hash : M.keySet()) {
                // Found the first hash with no reference in this transaction batch.
                if (M.get(hash).size() == 0) {
                    selectedHash = hash;
                    selectedTx = T.get(hash);
                    break;
                }
            }

            if (isValidTx(selectedTx)) {
                validTxs.add(selectedTx);
                pool = nextPool(selectedTx);
            }

            // remove selectedrent hash
            M.remove(selectedHash);
            // remove all the reference to selectedrent hash
            for (byte[] hash : M.keySet()) {
                M.get(hash).remove(hash);
            }
        }

        return validTxs.toArray(new Transaction[validTxs.size()]);
    }

    private UTXOPool nextPool(Transaction tx) {
        UTXOPool newpool = new UTXOPool(pool);

        for (int i = 0; i < tx.numInputs(); i++) {
            Transaction.Input in = tx.getInput(i);
            newpool.removeUTXO(new UTXO(in.prevTxHash, in.outputIndex));
        }

        for (int i = 0; i < tx.numOutputs(); i++) {
            Transaction.Output out = tx.getOutput(i);
            newpool.addUTXO(new UTXO(tx.getHash(), i), out);
        }

        return newpool;
    }