The Beginning of my Bitcoin Journey and a Knapsack problem variation

Hello Everyone, welcome to my very first blog. I hope you will enjoy reading through this article and, in the end, get some helpful information out of it.

So around a month ago, I started my journey in bitcoin when I saw the application of the Summer of Bitcoin program. I was thrilled but, at the same time, wasn’t very optimistic. Cause till now, I could not get any good results in my search for an opportunity to work on something for the coming summer. But I thought this was not an opportunity to be wasted, so I put my heart and soul into learning about blockchain and bitcoin as much as possible before filling the form.

3 days after coming to know about this opportunity, I filled the form. After some time, I got a mail for the first round of the selection process. It was a problem. A version of 0-1 knapsack problem, to be precise. The problem statement was:

Miners who mine the block has to add transactions to the block they have mined. In return, they get fees for each transaction that they add to the block. But they can’t add an unlimited amount of transactions to a block, as each transaction has its own finite size or weight. The total size of the block is limited. Given a list of transactions with their: Id (aka txid), fees, weight, and their parent transactions. Find a list of transactions such that:

• The combined weight of all the transactions in the final list is not more than the block size, i.e., 4,000,000 units.
• The parents of a single transaction come before it in the final list
• Maximize the total fees that we can obtain with the above two constraints

And so begin my journey with dwelling with the question that could possibly change my life. First, I could not get any idea of how to approach this problem, I went on to think, but it was all in vain. Then I conjured some courage and thought of asking my friend if he has any ideas for a possible way of solving this question. We discuss for more than half an with each other, and finally, I was getting some ideas to approach the problem. I thanked him, got off the phone, and started jotting down some approaches. And then it was a eureka moment I figured out a solution that was decent enough to give some good results. The process I took was:

1. First of all, I added a parameter for each element of the list. The parameter was a bool variable is_selected that kept track of if the transaction is added to the final list or not.
2. Then, along with the given parameters. I added some new parameters, which were combined_weight and combined_fees, which represented the sum of weight and fees of a transaction along with its yet unselected parents.
3. I also defined a new parameter known as combined_efficiency. This ratio of combined_fees and combined_weight kept track of how economically viable it is to add this particular transaction. Then I arranged all the transactions in descending order of their combined_efficieny and added the transaction to the final list. We can only select a transaction if its is_selected bool value is false. Whenever a transaction is selected, I recursively looped over all its parents to check if they are selected or not. If not, then I repeated this process on them also. When recursion reaches a transaction with no unselected parents, it adds the transaction to the final list. Finally, I store that final obtained list in a file named block.txt

Here is the code in python that I wrote in python:

class MempoolTransactions():
    def __init__(self, txid, fee, weight, parents):
        self.txid = txid       #Storing all the atributes of the transaction
        self.fee = int(fee)
        self.weight = int(weight)
        self.parents_txid = [parent for parent in parents.split(';')]
        self.parents = []    #List that would store all parent objects of a transaction
        self.is_selected = False   #Tracks if the transaction has been already added to the selected transactions or not

    def list_of_parents(self, transac_list):  #Function that would iterate over all the transactions in mempool to store parent transactions of a transaction
        for transac in transac_list:
            if transac.txid in self.parents_txid:
                self.parents.append(transac)

    @property
    def combined_weight(self):   #Attribute that stores the combined weight of the transaction as well as all its parents which are not yet selected
        combined_weight = self.weight
        for parent in self.parents:
            if not parent.is_selected:
                combined_weight += parent.combined_weight
        return combined_weight

    @property
    def combined_fees(self):   #Similar as the last function but now storing the combined fees
        combined_fees = self.fee
        for parent in self.parents:
            if not parent.is_selected:
                combined_fees += parent.combined_fees
        return combined_fees

    @property
    def combined_density(self):  #Attribute that would keep track of how high the return of a transaction are, i.e., fees to weight ratio
        return self.combined_fees/self.combined_weight


def selecter(lister, transaction):
    for parent in transaction.parents:  #For all the parents of a transaction
        if not parent.is_selected:  #if a parent is not yet selected
            selecter(lister, parent)  #then recursively call the selecter funtion for the parent of this transaction
    lister.append(transaction)  #add this transaction to the list of selected transactions
    transaction.is_selected = True #Mark the transaction to be selected so as to not select it again later




def transaction_selecter(transaction_list, block_weight):  # Function that would create a list of selected transactions
    sorted_transac_list = sorted(transaction_list, key=lambda x: x.combined_density, reverse=True) #sort the list based on individual transaction's density
    final_list = []  #list that would contain selected transactions
    total_weight = 0 #function to keep track of total accumulated weight of the selected transactions
    block_max_weight = block_weight #Total maximum given weight of a block i.e., 4000000
    for transac in sorted_transac_list:  #iterating over all transactions
        if transac.is_selected:  #if the transaction has been already selected
            continue  #move on
        if(total_weight + transac.combined_weight > block_max_weight): #if by adding this block total weight becomes greater than block's capacity then break
            break
        else:
            total_weight += transac.combined_weight #otherwise add this block's weight to total weight
            selecter(final_list, transac)  #and add this block as well its unselected parents to the final list of selected transactions
    return final_list  #return the final selected list



def parse_mempool_csv():
    with open('mempool.csv') as f:
        next(f)   #skiping the first line which contained the header of each column
        return([MempoolTransactions(*line.strip().split(',')) for line in f.readlines()])

total_block_weight = 4000000   #max possible given weight of block
transac_list = parse_mempool_csv()  #taking the list of all transactions in mempool
for transactions in transac_list:  #for each transaction in list
    transactions.list_of_parents(transac_list)  #Add its parents instance into its list of parents



final_list = transaction_selecter(transac_list, total_block_weight)  #getting the final list of selected transactions

with open('block.txt', 'w') as txtfile:   #Storing the final list of txids of the selected blocks into 
    for e in final_list:
        txtfile.write(str(e.txid) + "\n")

With this approach, I created a valid transaction list and got high enough total fees that I was able to qualify for the next round. The next round was about going through the bitcoin repository issues and giving a solution to one of them. This round also went pretty well. And finally, it was time for the interview. I was pretty nervous for the interview as I had never given a formal interview before this, and also, I was so close to my goal, so the stakes were so high. I prepared for an entire day for the interview. I looked through all the online material I can find related to any interview tips. And then finally the time came.

I was interview by Mr. Adam Jonas, Head of Special Projects at the Chaincode labs. As soon as the interview started, he made sure to get me comfortable as much as possible, to the point it didn’t like an interview and felt like two people discussing. But to be honest, all those preparing for the interview helped me immensely, and I was selected for the program.

I didn’t believe it for quite some time. I never even thought that after not getting any success to get excellent or meaningful summer work, I would be able to work for The Bitcoin itself, with the people at the core of this bitcoin world. It was like a dream come true situation for me.

But the journey had just yet started….