Code Challenge 2024 Solution

Author - pred695

Design Approach - Steps I took to create a valid block

Code Structure:

All the structs used in the implementation are stored in the Structs package in the file struct.go file. All the functions used throughout the implementation are stored in the Utils package under relevant files stated below. The coinbase.go file contains the generation of the coinbase transaction. The merkle.go file contains the code for the generation of Merkle root for the whole block and as well as the witness merkle. The prioritize.go file contains the code that implements the sorting algorithm which sorts transactions according to their fee/weight ratio. The weight.go file contains the code for calculating the weight of the transactions in the mempool. The util.go file contains the basic utility functions used throughout the implementation. The Validation package contains the address validation implementation for various locking scripts. The Blockchain package contains the code that runs the proof of work for the whole block in pow.go and the block mining code is there in mine.go file. This code generates the output.txt file.

Steps taken for generating the mined block.

a) Serialization:

There are two types of serialization used in my implementation. One is segwit serialization and the other is non segwit serialization.

1. func SerializeTransaction(tx *Structs.Transaction) ([]byte, error)-> Returns the serialized transaction without including the witness data.
2. func SegWitSerialize(tx *Structs.Transaction) ([]byte, error) -> Returns the serialized transaction including the witness data.
3. func SerializeBlockHeader(bh *Structs.BlockHeader) []byte -> Returns the serialized block header.

b) Generation of TxIDs:

1. TxIDs are generated by the non segwit serialized data if the output is double hashed with sha256 algorithm. An example from code: txid := to_sha(to_sha(serialized)) where to_sha function implements sha256 algorithm on a stream of bytes. and the serialized variable is the output of the non segwit serialization. This txid generated is in the big endian format. It is transformed into the little-endian format by using the ReverseBytes function defined in the serialize.go file in Utils package.

   The txids generated are used further for calculation of Merkle Root of the included transactions.

2. WTxIDs are generated by the segwit serialized data if the output is double hashed with sha256 algorithm. An example from code: wtxid := to_sha(to_sha(segserialized)) where segserialized is the segwit serialized data of the transactions. The WTxIDs for a non segwit transaction is same as that of the segwit transaction because of the absence of the witness data. The coinbase transaction in our case is a segwit transaction as the mempool contains many segwit transactions and I am also including many segwit transaction in my block.

c) Construction of Merkle Root and Witness Commitment:

1. The function func NewMerkleTree(leaves []string) *Structs.MerkleNode is used for creating the merklee tree. It returns the merkle root of all the transactions which is of the type MerkleNode defined in the Structs package. The leaves are the TxIDs in string format.
2. The function func CreateWitnessMerkle() string is used for creating the witness merkle of the block to be constructed. It returns the witness commitment which is included in the Coinbase Transaction. Code snippet of witness commitment generation commitment_string := hex.EncodeToString(merkleRoot.Data) + "0000000000000000000000000000000000000000000000000000000000000000".

d) Construction of Blockheader:

1. The blockheader is constructed in the mine.go function in the Blockchain package. It is of the type BlockHeader defined in struct.go file in the Structs package.
2. This blockheader is put in the first line of output.txt in the serialized form. The serialization function of the Blockheader is func SerializeBlockHeader(bh *Structs.BlockHeader) []byte.

e) Proof of Work Algorithm:

This is implemented in the pow.go file in the Blockchain package.

f) Construction of Coinbase Transaction:

The coinbase transaction is constructed in the coinbase.go in the Utils package.

g) Fractional Knapsack Algorithm:

The algorithm to gain the maximum fee by including the transactions which had relatively higher fee/weight ratio is implemented in the prioritize.go file in the Utils package. It sorts the transactions in the decreasing order of the fee to weight ratio and keep including them one by one until the Block weight reaches close to the maximum of 4000000including the coinbase transaction which came out be 660 wu in my case.

Flow:

Serialize transactions -> Generate Transaction IDs -> Perform Address Validation -> Generate Witness Transaction IDs -> Pick up transactions according to the Fractional Knapsack Algorithm in a greedy manner -> Construct the witness commitment for the Coinbase Tx -> Create a Valid Coinbase transaction -> Construct the Merkle Root of the included transactions -> Run the proof of work algorithm -> Generate the output.txt file once the block is mined.