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:
- 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.
- 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.
- 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….