Authenticated data structures (ADS) are a model of computation where untrusted responders answer queries on a data structure on behalf of a trusted client providing also a proof of the validity of the answer.
Merkle Trees Merkle Trees[1] (or hash trees) are one of the most prominent examples of ADS which gain recent popularity because of their ample use in blockchain technologies. Merkle trees are essentially trees with hashes instead of values: nodes are labeled with a single hash computed by hashing a concatenation of the hash of their children. Assuming that the hash of the root of the tree is known, membership can be validated by providing the hashes required along the path to the root. Sparse Indexed Merkle Trees extend Merkle trees with the ability to store and index data, for which simple Merkle trees are not enough.
Different blockchains implement variations of the same Sparse Indexed Merkle Trees. In a project developed at the IMDEA Software Institute, a data type called Setchain requires to provide similar ADT guarantees for membership and non-membership on massive collection of elements. We call there massive trees Large Indexed Merkle Trees (LIMTs). The idea of the project is to implement efficiently LIMTs and stretch the size of the tree that a single machine can handle efficiently.
In this project, the candidate will several variations of Large Indexed Merkle Trees and study their performance stressing different usages.
Applicants should be final year BSc or MSc students in computer science, computer engineering, electric engineering or a related discipline, with proven top programming skills as well as ability to understand programs, executions and deployments. The ideal candidate will have a strong/solid programming skills, (preferably in imperative languages like C/C++ and Go), strong data structures and algorithms knowledge, in particular hashing and trees.
The internship duration is intended to be for 6 months. The ideal starting period is from January 2025.
Applicants interested in the position should submit their application at https://careers.software.imdea.org/ using reference code 2024-11-intern-largeindex. Deadline for applications is November 20th, 2024. Review of applications will begin immediately.
The recruitment process will comply with the IMDEA Software Institute’s OTM-R Policy.
For enquiries about the position, please contact:
