Repository navigation
Report
This technical challenge has been one of the most engaging challenges I have undertaken in a while. The implementation of a Merkle Tree is something that I have never done in practice, however, I have interacted with Merkle trees extensively through my experience on a current project of mine, Weaver; a decentralized AVM (Algorand Virtual Machine) bridge using state proofs.
If I suddenly ran out of brain memory storage I had to dump all other programming languages and choose just one, I would choose Golang. Whenever I have free reign over a choice of building a server/CLI/tool, without constraints, I choose to use Golang. Golang's static typing, in my opinion, alleviates the need for extensive unit testing and its concurrency is just icing on the cake.
I new choice in this project is to use the web framework Echo. I chose an opinionated framework because it can sometimes save time on boilerplate code it also gave me a chance to learn a new framework.
I have used Next.js professionally for about two years and so I felt somewhat at home using it as the client. However, I am accustomed to v12, so I decided to dive into v14 to get to grips with all the new features, especially the new App Router feature.
Chakra UI has been a long time favorite UI kit for me. Segun and his team do amazing work and I use it across multiple projects.
The choice of using SHA-256 over SHA-512 merely came down to small character count. As a lot of this project is based on experimental and custom implementations, I wanted to balance between output being semi-human-readable and actually using a popular hashing algorithm.
Fig 1.1.: Simple sequence diagram
Navigating to the /upload page on the client presents you with an interface that allows you to select multiple files. Once you have added the files, you can upload them to the server.
Once the server receives the files, the files are added to a subdirectory within the .files/ directory that is given the name of a random 32 byte hashed using SHA-256 and encoded in hexadecimal. Once all the files have been uploaded, each file is hashed, using SHA-256 and encoded in hexadecimal. These hashes are sorted alphabetically and a Merkle Tree root is generated from the list. The directory that stores the files is renamed to the Merkle Tree root hash (this doesn't really have any significance, I just thought it would be helpful in testing).
If everything is successful, the Merkle Tree root is returned to the client.
Once you have this Merkle Tree root, you can navigate to /files where you will find the grouped list of files that have been uploaded. Find the file group of the files that were previously uploaded (the groups are separated by the Merkle root). Here you can download the Merkle Tree proof for each file, or use the UI to verify the proof against a Merkle Tree root, i.e. the Merkle Tree root you received in the previous step.
⚠️ NOTE: The verification process happens on the client.
- The Merkle Tree root and proof generation was fully implemented.
- The project was Dockerized.
- Semi-implemented a brand; there is a logo, a name and some limited theming (font choice and primary color).
- A CI/CD pipeline was setup that allows: pull request checks and a version releases based on commit messages (using the commitlint convention).
- The Docker setup is for development only. While an attempt to create production-ready docker images was made, other aspects took priority.
- [🐛] When uploading files, the files are empty.
- Merkle Tree root generation happens on the server only. However, the specs did mention that the client generates the Merkle Tree root, an oversight on my part, but can be implemented in the next iteration.
- A lot of time was wasted on getting Next.js internationalization. When I create new frontend-facing projects, I ensure several features are made necessary and one of those is internationalization. Next.js makes Internationalization a bit more cumbersome and I spent far to long trying to get this working. However, I abandoned it in favor of actually getting on with the implementation.
- I have only tested uploading multiple files and uploading directories may cause an error; I have not accounted for directories/subdirectories.
Echo serves its purpose well, but this decision came down to experimenting with a new framework. There are a plethora of web frameworks out there for Go and Echo has caused some teething issues (see the aforementioned bug).
The Merkle Tree algorithm has unit tests, but as it is a custom implementation, the computational complexity has not been measured extensively. Adding more tests that use very large data sets would highlight its un-optimization and can help development the algorithm to be more optimized.
I am a big fan of e2e testing and, given more time, I would setup an e2e testing framework.