Write the recursive function merkle() that is used in code provided below to create a Merkle tree of sha256 hashed strings. Merkle trees1 are an important data structure used in Bitcoin2, and the sha2563 hash function is the current NIST standard for collision-resistant hashing. Use the sha256 library source. The template already includes the code to read in the text file transactions.txt.

There are 8 quotes in the text file. Your recursive function will hash all 8 lines, resulting in 8 hashes. It will them concatenate the first and second hash, the third and fourth hash. etc., resulting in 4 new text strings of 64 characters (a sha256 hash is 32 characters long). Then hash each of these 4 text strings, resulting in 4 new 32-character hashes. Now concatenate pairs again, hash them, and continue this until only a single 32-character hash results.

The function prototype for hashing is: string sha256(string s);

meaning the function parameter list is a single string, and it returns a single string.

The program must have the following:

A recursive function called merkle that takes a single vector of strings as input, and returns a single string. The function prototype is already in the template file.

Use sha256 library to produce the hash strings.

Correct Output

45806129672d2d1229659be25acc0814f8e0d0e8553db4c3290787b926f419c8

8 quotes from .txt file:

//One has to look out for engineers - they begin with sewing machines and end up with the atomic bomb. ////Engineers like to solve problems. If there are no problems handily available, they will create their own problems. //I'm a good communicator, and I'm a good translator. I can talk to engineers; I can talk to people for whom technology is not remotely interesting or even maybe scary - things like that. //The scientist and engineers who are building the future need the poets to make sense of it. //I would never talk just to be social. Now, to sit down with a bunch of engineers and talk about the latest concrete forming systems, that's really interesting. Talking with animal behaviorists or with someone who likes to sail, that's interesting. Information is interesting to me. But talking for the sake of talking, I find that quite boring. //At its core, bitcoin is a smart currency designed by very forward-thinking engineers. It eliminates the need for banks, gets rid of credit card fees, currency exchange fees, money transfer fees, and reduces the need for lawyers in transitions... all good things. //Scientists dream about doing great things. Engineers do them. //More than ever, the world needs good engineers. However, the pool of talent is shrinking not growing.

int main() file:

#include #include #include #include #include "sha256.h"

using namespace std;

string merkle(vector);

int main() { vector txns; string str; ifstream inFile;

// load transactions inFile.open("transactions.txt",ios::in); if (!inFile){cout<<"No file found ";return 0;} while( getline(inFile, str) ){txns.push_back(str);} inFile.close();

cout << merkle(txns) << endl;

return 0; }