Instructions Write a recursive function named merkle() that can create a Merkle tree of sha256 hashed strings. A Merkle trees is a fundamental data structure used in Bitcoin, and the sha256 hash function is the current NIST standard for collision resistant hashing The entire main program is in the template. You will only need to complete writing the function named merkle. The main program reads lines of text from user input and builds an array of these text strings. The strings can be any length and contains spaces, punctuation etc. it the creates a (nearly) unique 256-bit hash of this file using a recursive function, and outputs it to the screen as a 64 character hexadecimal value (22 = 1604) The recursive function you complete is called merkle() and will 1. hash each of the elements in the vector of strings individually, resulting in as many 64-character hash strings, also stored as data type string (eg 10 lines of text -- 10 hash strings) 2. concatenate the first with the second hash string the third with the fourth, etc, resulting in one half as many new text strings of 128 hexadecimal characters (concatenation of two 64-character string). 3. hash each of these new text strings, resulting in as many new 64 hexadecimal hashes. 4. concatenate pairs again (returning to step 2. then step 3, then step 2 then step 3. :) This recursion (steps 2 -- 3 - 2 - 3 - 2) continues until the there is only a single 64 character hexadecimal hash remaining. Since there are no pairs left at this point to do step 2 the function will return the value merkleRoot where it is output to the screen. Hashes are created using the sha256 library quite simply as demonstrated in this example an arbitrary length string named s1 can be converted (hashed) into a 64 character string (of hexadecimal values) named s2 via 52 = sha256(1): where both s1 and s2 are of data type string Part A Recall from class lecture, that most recursive functions us an if else structure. Add an if else structure to the function For the test condition, determine whether there is only 1 element in the vector v1. When that is the case (test condition evaluates to true), assign the variable merkleRoot to the sha256 hash of this vector element. Leave the else part of the structure completely empty for now (ust a pair of curly brackets) true), assign the variable merkleRoot to the sha256 hash of this vector element. Leave the else part of the structure completely empty for now just a pair of curly brackets) At this point if the input is A single line of text. the output should be fff9f14639b5a8041759d220120160e95e5c739499287405c4dc8ac8539a45 Be careful when you copy/paste the line of text, there is not a return/enterewline at the end. The period is the final part of the input string Part Now add code to the else condition. A new vector will be used to store the concatenated strings, and it is already declared as a local variable in this function and named V2. Create a for loop that will go through the entire vector of strings two at a time. How many times should this loop occur? Since it works on 1 pair of text strings at a time it will be one-half the size of the vector v2 (Recall you did something similar in the Feistel cipher lab). You will need to declare your own indexing variable for this loop. Within the for loop. generate a sha256 hash of the first two elements of the vector individually (use the for loop counter variable for the index), and then concatenate the strings together. Recall that string concatenation can be done simply with the addition operator + Finally, add this concatenated string to the vector v2 using the vector's push_back() function Make sure you used the for loop index variable so that this loop will continue through all pairs in the vector That's all that goes in the forloop. After the loop is complete (but still within the else condition make the function recursive by calling itself with the variable v2 as the parameter. Assign what is returned to the variable merkleRoot At this point, if the input is single line of text. And then a second one. the output should be 60c81e37bcd2de97dc0b71199b3d1e6cb295fafd36063db2c979045a4e913 Part One final thing to take care of. When the input has an odd-numbered of lines, the instructions say to duplicate the last element to make an even number of elements in the initial vector. Put this part above Part 8. Add code that tests whether the vector vi has an odd number of elements. If it does, add a duplicate of the last element to the end of the vector v1 Now, you are all done. If everything is correct, when the input is A single line of text. And then second one. This is the third line. the output should be EE026688ab93ac352042e620d 182142aa8583308281b62fe8dcca 323812c1da8 fatis, click Submit and have the system run all the tests! LAD ACTIVITY 7.10.1: Week 6 Lab - recursion 0/40 Downloadable files sha256.cpp sha256.h transactions.txt Download main.cpp Lood default molt include 2 include 4 include sha256.h" 5 6 using namespace std; 2 main.cpp > 6 using namespace std; 7 8 17 function prototype, don't put your code here. Add it at the bottom 9 string merkle(vector txns; 13 string str; 14 15 // read stdin until it is empty 16 while(getline(cin, str) txns.push_back(str); // output the Merkle root to the screen cout v2; 25 string merkleRoot = ""; 26 // add your code here 28 29 return merkleRoot; 30 } 31 27 I sha256.CPP #include #include #include "sha256.h" const unsigned int SHA256::sha256_k (64) = //UL = uint32 {@x428a2f98, 0x71374491, Oxb5c0fbcf, exe9b5dba5, @x3956c25b, 0x59f111f1, 0x923f82a4, Oxab1c5ed5, @xd807aa98, 8x12835b81, 8x243185be, Ox550c7dc3, 8x72be5d74, exB@debife, ex9bdc6a7, exc19bf174, @xe49b69c1, exefbe4786, ex@fc19dc6, @x240calcc, 0x2de92c6f, @x4a7484aa, x5cba9dc, x76f988da, 0x983e5152, exa831c66d, Oxb00327c8, @xbf597fc7, exc6e00bf3, exd5a79147, 0x06ca6351, 0x14292967, 8x27b70a85, 8x2e1b2138, 0x4d2c6dfc, @x53380d13, 0x650a7354, 0x766a8abb, 0x81c2c92e, @x92722c85, exa2bfe8a1, Oxa81a664b, exc24b8b70, exc76c51a3, @xd192e819, @xd6990624, exf40e3585, @x106aa87@, @x19a4c116, @x1e376c08, 0x274877499, 0x34b@bcb5, @x391c@cb3, @x4ed8aa4a, @x5b9cca4f, @x682e6ff3, 8x748f82ee, Ox78a5636f, 8x84c87814, 0x8cc70208, @x90befffa, exa4506ceb, exbef9a3f7, exc67178f2}; void SHA256::transform(const unsigned char *message, unsigned int block_nb) { uint32 w(64); uint32 w(8); uint32 ti, t2; const unsigned char *sub_block; int i; int j; for (i = 0; i class SHA256 { protected: typedef unsigned char uint8; typedef unsigned int uint32; typedef unsigned long long uint64; const static uint32 sha256_k(); static const unsigned int SHA224_256_BLOCK_SIZE = (512/8); public: void init(); void update(const unsigned char message, unsigned int len); void final(unsigned char *digest); static const unsigned int DIGEST_SIZE = ( 256 / 8); protected: void transform(const unsigned char *message, unsigned int block. nb): unsigned int m_tot_len; unsigned int m_len; unsigned char_block (2*SHA224_256_BLOCK_SIZE); uint32 m_h[8); }; std::string sha256(std::string input); #define SHA2_SHFR(x, n) (x >> n) #define SHA2_ROTR(x, n) ((x >> n) | (x > ((sizeof(x) 3) - n))) #define SHA2_CH(x, y, z) ((x & y) (x & z)) #define SHA2_MAJ(x, y, z) ((x & y) * (x & 2) * (y & z)) #define SHA256_F1(x) (SHA2_ROTR(X, 2) SHA2_ROTR(X, 13) - SHA2_ROTR(x, 22)) #define SHA256_F2(x) (SHA2_ROTR(x, 6) SHA2_ROTR(X, 11) SHA2_ROTR(X, 25)) #define SHA256_F3(x) (SHA2_ROTR(x, 7) * SHA2_ROTR(X, 18) - SHAZ_SHFR(x, 3)) #define SHA256_F4(x) (SHA2_ROTR(X, 17) SHA2_ROTR(X, 19) * SHAZ_SHFR(x,10)) #define SHA2_UNPACK32(x, str) *((str) + 3) = (uints) ((x) *((str) + 2) = (uints) ((x) >> 8); *((str) + 1) = (uint8) ((x) >> 16); *((str) + C) = (uint8) ((x) >> 24); #define SHA2_PACK32 (str, x) *(x) = ((uint32) *((str) + 3) I ((uint32) *((str) + 2) 8) ((uint32) *((str) + 1) 2 include 4 include sha256.h" 5 6 using namespace std; 2 main.cpp > 6 using namespace std; 7 8 17 function prototype, don't put your code here. Add it at the bottom 9 string merkle(vector txns; 13 string str; 14 15 // read stdin until it is empty 16 while(getline(cin, str) txns.push_back(str); // output the Merkle root to the screen cout v2; 25 string merkleRoot = ""; 26 // add your code here 28 29 return merkleRoot; 30 } 31 27 I sha256.CPP #include #include #include "sha256.h" const unsigned int SHA256::sha256_k (64) = //UL = uint32 {@x428a2f98, 0x71374491, Oxb5c0fbcf, exe9b5dba5, @x3956c25b, 0x59f111f1, 0x923f82a4, Oxab1c5ed5, @xd807aa98, 8x12835b81, 8x243185be, Ox550c7dc3, 8x72be5d74, exB@debife, ex9bdc6a7, exc19bf174, @xe49b69c1, exefbe4786, ex@fc19dc6, @x240calcc, 0x2de92c6f, @x4a7484aa, x5cba9dc, x76f988da, 0x983e5152, exa831c66d, Oxb00327c8, @xbf597fc7, exc6e00bf3, exd5a79147, 0x06ca6351, 0x14292967, 8x27b70a85, 8x2e1b2138, 0x4d2c6dfc, @x53380d13, 0x650a7354, 0x766a8abb, 0x81c2c92e, @x92722c85, exa2bfe8a1, Oxa81a664b, exc24b8b70, exc76c51a3, @xd192e819, @xd6990624, exf40e3585, @x106aa87@, @x19a4c116, @x1e376c08, 0x274877499, 0x34b@bcb5, @x391c@cb3, @x4ed8aa4a, @x5b9cca4f, @x682e6ff3, 8x748f82ee, Ox78a5636f, 8x84c87814, 0x8cc70208, @x90befffa, exa4506ceb, exbef9a3f7, exc67178f2}; void SHA256::transform(const unsigned char *message, unsigned int block_nb) { uint32 w(64); uint32 w(8); uint32 ti, t2; const unsigned char *sub_block; int i; int j; for (i = 0; i class SHA256 { protected: typedef unsigned char uint8; typedef unsigned int uint32; typedef unsigned long long uint64; const static uint32 sha256_k(); static const unsigned int SHA224_256_BLOCK_SIZE = (512/8); public: void init(); void update(const unsigned char message, unsigned int len); void final(unsigned char *digest); static const unsigned int DIGEST_SIZE = ( 256 / 8); protected: void transform(const unsigned char *message, unsigned int block. nb): unsigned int m_tot_len; unsigned int m_len; unsigned char_block (2*SHA224_256_BLOCK_SIZE); uint32 m_h[8); }; std::string sha256(std::string input); #define SHA2_SHFR(x, n) (x >> n) #define SHA2_ROTR(x, n) ((x >> n) | (x > ((sizeof(x) 3) - n))) #define SHA2_CH(x, y, z) ((x & y) (x & z)) #define SHA2_MAJ(x, y, z) ((x & y) * (x & 2) * (y & z)) #define SHA256_F1(x) (SHA2_ROTR(X, 2) SHA2_ROTR(X, 13) - SHA2_ROTR(x, 22)) #define SHA256_F2(x) (SHA2_ROTR(x, 6) SHA2_ROTR(X, 11) SHA2_ROTR(X, 25)) #define SHA256_F3(x) (SHA2_ROTR(x, 7) * SHA2_ROTR(X, 18) - SHAZ_SHFR(x, 3)) #define SHA256_F4(x) (SHA2_ROTR(X, 17) SHA2_ROTR(X, 19) * SHAZ_SHFR(x,10)) #define SHA2_UNPACK32(x, str) *((str) + 3) = (uints) ((x) *((str) + 2) = (uints) ((x) >> 8); *((str) + 1) = (uint8) ((x) >> 16); *((str) + C) = (uint8) ((x) >> 24); #define SHA2_PACK32 (str, x) *(x) = ((uint32) *((str) + 3) I ((uint32) *((str) + 2) 8) ((uint32) *((str) + 1)