SUMMER OF BITCOIN CHALLENGE

Task

Checkout resources/ folder for task info.

Approach

• Task is to find the sequence of transaction_ids whose sum of weights is not greater than the block size and whose sum of fees is maximized.
• This sounds like knapsack problem to me. The only thing is that, the transaction should appear in a block iff all of its parents appear and they need to retain their original order.
• To fix todo-4, try to combine all the parent transactions of a transaction into one.

Note

1. A block is valid iff A transaction apprears in a block only if all of its parents appear earlier in the block.
2. All transactions in a block must retain their original order, i.e the order they were listed in mempool.

Installation and Usage

• The system must have python >= 3.6.9 and pipenv installed.
• To install them:

sudo apt-get install python3
sudo python3 -m pip install pipenv

• Install dependencies

  pipenv shell # activates the virtualenv
  pipenv install # installs dependencies from Pipfile.lock

• Edit and run python file

  python3 file.py # inside the virtualenv

• Block generation
  ```bash

  Default block weight of 50000 will be used if block weight is not specified.

  python3 main.py [Optional block weight]

Generate a block with max weight of 40000

python3 main.py 40000

- Check `main.py` for basic usage.
- All the generated blocks are saved in `blocks/` directory in the format `block_{sum_of_fees_of_transactions_in_that_block}.txt` 
### Observations
- Let `f(transaction)` be a the sum of fees generated by the knapsack algorithm for a given total_weight.
```python
    f(all_transactions_in_mempool) > f(transactions_without_parents) > f(transactions_with_parents_combined)

• Blocks generated by all_transactions_in_mempool are not valid most of the time as they do not obey Note-1.
• The best I could do in my system is to generate the block with a max fee of 4094954, with a total weight of 2100000.

Block analysis:

Transactions of block ./blocks/block_4094954.0.txt:
        No. of txs: 1614
        Total Fees: 4094954
        Total weights: 2100000
        is_valid_block: True

• My system resulted in a Segmentation Fault upon execution of the program with total_block_weight > 2100000. Any system with RAM > 16GB should do better than this.

  TODO

  • Create a class Block to handle methods related to blocks.
  • Write a function to verify if a block is valid (Using Note-1).
  • Fix the numba reflected list error.
  • Turns out that some blocks generated by our knapsack are not valid. We need to figure out how to fix it.
    • Follow Note -1 while including the transaction in a
      knapsack.
    • Fixed it combining parent transactions of a transaction.
  • Use only those transactions which do not have parent transactions to avoid the above issue.
  • The transactions in a block are in the reverse order because of knapsack. Due to this, transactions in the block files are in reverse order… Fix it!!
  • Reverse the contents of previously generated block files.
  • Point #3 in Approach.