Sparse Merkle tree implemetation in C++
The design document is here: https://docs.google.com/document/d/1d4DggfDmPmNY8UTWFTj-_CE52OuBM6wXfxk0xVwT2ug/edit?tab=t.0#heading=h.1qmhejh2i81g
A few quick notes:
- I assumed that the design doc detailed change log is not needed (as we can easily track changes) so I just made edits directly in the design doc for the following design changes and other notes: -- Changed the leaf key from being the hash of the value to be input data and then updated all relevant places in document. -- Added a few minor clarifications as I found them.
- To compile and run the tests, ensure that the OpenSSL library is installed and just run ./build.sh.
- There are a few comments about TODO mainly relating to exposing methods for testing which should be moved to the private section after the test is done.
- I did only a few commits with relevant comments, but did not use branches/pull requests as I was the only one developing.
- I typically add a lot more comments, however due to time there could a lot more to be desired here, however this depends a lot on the company specifications so I'd be happy to adjust.
- Only the scalability tests for 1,000 and 10,000 key insertions are enabled and for 50k, 100k and 1mil are disabled currently (can be easily enabled in /test/smt_test.cpp). The enabled ones run within 18 secs and need ~280MB RAM (on my laptop with i7 13700 CPU) and they scale linearly so the bigger tests should be similar.
- A potential enhancement in the future is that currently when generating multiple proofs in a batch, first all insertions must be complete and then generate all proofs. This could be improved in the future by changing the structure slightly and will allow better flexibility and usability in real world cases.