Zkouška C++ 3. 2. 2026

Blockchain is a distributed database containing transactions. For our exam, we will simplify those transactions and try to create a manager that allows an easy work with the transactions. Transactions

A transaction is an entity that contains any number of inputs and outputs. Outputs are connected to inputs and form a DAG that can look similar as shown at the next picture.

API

In out exam, transactions look as follows:

struct TransactionIn {
    // An identifier of the previous output transaction
    txid_t txid;
    // An index of the previous output transaction
    txindex_t vout;
};

// Transaction output descriptor
struct TransactionOut {
    // A new owner of the receiving BTCs
    pubkey_t pubkey;
    // Number of BTC sent to this specific output
    value_t value;
};

struct Transaction {
    // Input transactions
    std::vector<TransactionIn> ins;
    // Output transactions
    std::vector<TransactionOut> outs;
    // Transaction ID
    txid_t txid;
};

A transaction consists of three fields:

  1. ins - a vector of input transactions. There can be any non-empty number of inputs.

  2. outs - a vector of output transactions. There can be any non-empty number of outputs.

  3. txid - a unique identifier of the transaction used for referencing it in other transactions.

Transaction outputs (TransactionOut) consist of:

  1. pubkey - a public key of the new owner of the BTCs sent to this output. It can be seen as a unique identifier (=address) of the owner.

  2. value - a number of BTCs sent to this output. It must be a positive integer, i.e., value > 0.

Transaction inputs (TransactionIn) consist of:

  1. txid - an identifier of the previous transaction that created the output being used as input.

  2. vout - an index (starting from 0) of the output in the previous transaction that is being used as the input. This pair (txid, vout) uniquely identifies the output being used as input and can be seen as a link to the previous transaction output.

Invariants

All the transactions must satisfy the following invariants. If they do not, they are considered invalid and will be rejected during validation:

  • All inputs must reference already existing outputs from previous transactions. Transactions cannot reference themselves or future transactions.

  • Sum of all input values must be equal to the sum of all output values.

  • No output can be used as input more than once (no double spending)

Holding these invariants implies that there are no cycles in the transaction graph, as each output can be used only once as input. Exam Instructions

Create a transaction manager that manages transactions in memory. It should provide the following functionalities with the specified API:

class TransactionManager {
public:
    // Default ctor
    TransactionManager();

    // Adds a new transaction
    void add_transaction(const Transaction &tx);

    // Returns an iterator to the n-th funding transaction in blockchain
    TransactionIterator begin(txindex_t n) const;

    txindex_t num_funding_transactions() const noexcept;

    // Returns a sentinel iterator that points. Can be used to iterate over the transactions using condition it != end(). 
    TransactionIterator end() const;

    // Returns a balance for a specific publickey
    value_t get_balance(pubkey_t pk);
};b

  1. Create and maintain a materialized DAG of transactions in the memory.

  • For efficient traversal, represent the links between transactions using any form of pointers (smart-points/observers/...) or references.

  • Everything is stored in memory exactly once

  1. Allow to add new transactions

    Implement the add_transaction method that adds a new transaction to the manager. Before adding a transaction, validate it against the invariants mentioned above. If the transaction is invalid, reject it and do not add it to the manager. When successfully added, output: Transaction <txid> added successfully.\n, E.g., Transaction 123 added successfully. If rejected, output: Transaction <txid> is invalid and was rejected. Error: <error_message>.\n, E.g., Transaction 123 is invalid and was rejected. Error: Double spending.

Validation details and error messages

  • Invalid txid - if Transaction::txid is not unique.

  • Invalid input reference - if TransactionIn::txid and TransactionIn::vout do not reference together an already existing output. Self-references and future references are invalid.

  • Input output sum mismatch - if the sum of input values does not equal the sum of output values.

  • Double spending - if any output is used more than once as input.

  • Non-positive output value - if TransactionOut::value is not a positive integer.

Funding transactions

Funding transactions are transactions that have no inputs, i.e., Transaction::ins.empty(). They are the starting points of the transaction DAG and can be used to fund new transactions.

  • The TransactionManager::begin(txindex_t n) method returns an iterator pointing to the n-th (starting from 0) funding transaction added to the manager. (Notice that funding transactions have no counterpart element, i.e., once new BTCs are put into the system, they cannot be removed.)

  • Adjust the validation process for funding transactions accordingly.

  1. Print the balance of a public key

Implement the get_balance method that returns the balance of a specific public key. Balance is defined as the sum of all unspent outputs associated with the public key, i.e., A difference bettwen sum of all outputs and sum of all inputs associated with the public key. (Notice that if the above invariants are held, the balance is always non-negative.)

Validation details and error messages

  • If the public key has no associated transactions, throw a std::invalid_argument with the message Public key <pk> has no associated transactions., e.g., Public key 123 has no associated transactions.

  1. Implement an iterator over transactions

Allow iterating over all added transactions with the following API:

// An iterator that allows to iterate over transactions.
class TransactionIterator {
public:
    // Move to the next transaction connected to the n-th output 
    TransactionIterator &next(txindex_t n);
    
    // Move to the previous transaction from the n-th input
    TransactionIterator &prev(txindex_t n);

    // Returns a number of transaction inputs.
    size_t num_txin() const noexcept;
    // Returns a n-the transaction input. 
    TransactionIn &get_txin(txindex_t n);

    // Returns a number of transaction outputs.
    size_t num_txout() const noexcept;
    // Returns a n-the transaction output. 
    TransactionOut &get_txout(txindex_t n);

    // Returns a current txid.
    txid_t get_txid() const noexcept;

    // Additional operators

    bool operator==(const TransactionIterator &txit) const noexcept;
    bool operator!=(const TransactionIterator &txit) const noexcept;

    TransactionIterator(const TransactionIterator &txit);
    TransactionIterator& operator=(const TransactionIterator &txit);

    TransactionIterator(TransactionIterator &&txit) noexcept;
    TransactionIterator& operator=(TransactionIterator &&txit) noexcept;
};

The iterator allows to traverse the transaction DAG both forward and backward using the next and prev methods.

The starting point of the iterator is defined by the begin(txindex_t n) method of the TransactionManager, which returns an iterator pointing to the n-th funding transaction (a transaction with no inputs - described later).

The end of the iteration is defined by the TransactionManager::end() method, which returns a sentinel iterator that represents the end of the iteration. Given that we do not track unspend outputs directly, TransactionManager::end() - 1 has no meaning and cannot be used to access the last transaction.

The iterator also provides set of some standard operators:

comparision operators == and != for checking equality between two iterators.
copy constructor and assignment operator.
move constructor and move-assignment operator.

Validation and error handling

When calling a iterator-related method with an invalid argument (e.g., next with n greater than the number of outputs), throw a std::invalid_argument with the message Invalid transaction iterator argument..

Example - Test 1 Input

TransactionManager tm;
    
// Funding tx1
Transaction tx1{
    .ins = {},
    .outs = {{ .pubkey = 2, .value = 1000, }},
    .txid = 1
};

// tx1 --> tx2[0|1]
Transaction tx2{
    .ins = {{ .txid = 1, .vout = 0 }},
    .outs = {{ .pubkey = 3, .value = 500 }, { .pubkey = 4, .value = 500 }},
    .txid = 2
};

// tx2[0] --> tx3
Transaction tx3{
    .ins = {{ .txid = 2, .vout = 0 }},
    .outs = {{ .pubkey = 5, .value = 250 }, { .pubkey = 6, .value = 250 }},
    .txid = 3
};

tm.add_transaction(tx1);
tm.add_transaction(tx2);
tm.add_transaction(tx3);

Output

Transaction 1 added successfully.
Transaction 2 added successfully.
Transaction 3 added successfully.
Transaction 4 added successfully.

Example 2

void dfs(TransactionIterator it, TransactionIterator end, auto &&fn) {
    if (it == end) return;  
    fn(it);
    auto it_orig = it;
    for (size_t i = 0; i < it.num_txout(); ++i) {
        dfs(it.next(i), end, fn);
        it = it_orig;
    }
}

dfs(tm.begin(0), tm.end(), [](auto &&it){ std::cout << it.get_txid() << std::endl; });

Files

transactions.hpp - do not edit
    contains the definitions of Transaction, TransactionIn, and TransactionOut structures
transaction_manager.hpp - implement and submit
    contains the definition of TransactionManager and TransactionIterator classes.
    Implement these classes according to the instructions above.
    Do not change the already created methods and their signatures, but you can add/change anything else.

Final hints and notes

  • wrap the original structures into your own structures

  • on purpose, the API does NOT return Transaction from the iterator. The original Transaction is used just for passing the arguments, nothing else

  • for simplicity, we sometimes avoid some const-correctness in the API