Our project focuses on creating Bitcoin blocks by selecting transactions in a way that optimizes the transaction fees. By implementing a sophisticated algorithm, we aim to maximize the profitability of each block while ensuring efficient and secure transaction processing. This approach helps miners earn higher rewards and contributes to the overall efficiency of the Bitcoin network.
- amount sent = amount recieved + transaction fee
- Bitcoins design makes it easier for the sender to specify the
transaction fee
than the reciever. This makes sense since, thetransaction fee
is taken from the sender's wallet. - When a miner creates a
block proposal
, the miner is entitled to specify where all the fees paid by the transactions in that block proposal should be sent. If the proposal results in a valid block that becomes a part of the best block chain, the fee income will be sent to the specified recipient. If a valid block does not collect all available fees, the amount not collected are permanently destroyed - To select the set of optimal transaction, miner has to solve two problems
- Problem1: Transaction Fee and Size - Knapsack Problem - NP Hard
- Problem2: Transaction conflicts - Maximum Independent Set Problem - NP Hard
Create a block from the pending transactions (mempool.csv
) that has maximum possible Miner Fee
-
- Block weight should not exceed
4,000,000
- Parent transaction should be included before child transaction
- Block weight should not exceed
-
- sort the mempool data by
feerate
in descenting order - start add transactions to the block till its
weight
is less than4000000
- Improvement: Find a single equivalent block for a block + parents
- sort the mempool data by
-
- If a transaction has any parent then calculate an equivalent block by combining child block with its parent (Now this equivalent block can be compared with any block present in the mempool)
- Sort the mempool by
feerate
in descending order - Improvement Try to make sure that you create a equivalent transaction which has more number of ancestors first. For the Example:
a->b->c
, we must hita
beforeb or c
while creating equivalent transaction
-
- Sort the mempool by number of ancestors present for a transction in descending order
- Follow the same steps from
Intermediate Approach 2
above - Improvement Time complexity of
findTxnIndex()
,findEqTxnIndex()
methods inMempool class
can be improved usingdictionary
(looping through list in current implementation)
-
- Not the most optimal since some transaction requires parents to be added. Blindly adding this parent since, its child has good metric is not optimal
-
- Hopefully none
- Time complexity of few functions like
findTxnIndex()
,findEqTxnIndex()
can be improved
-
- Block fee:
6345335 (Incorrect)
- Block weight:
4000000 (Incorrect)
- The above result are incorrect, the generated
block.txt
was not valid
- Block fee:
-
- Block fee:
5714810
- Block weight:
3999804
- Block fee:
-
- Block fee:
5797979
- Block weight:
3999808
- Block fee:
- Revisited NP Hard, 0/1 Knapsack, Dynamic Programming
- Better understanding of DFS
- Learnt the Miner's Fee concept. Hence, got a good overview of bitcoin mining process
- Better understanding of python function and internals
- Reading CSV files
- variable assignment
- how python passes arguments (It is neither pass by value not pass by reference)
- Debugging python using vscode
- The
mempool.csv
has a column nameparents_
* instead ofparents
. weight
,fee
are of typeint
.*
_
above denotes space