Before the birth of computer science, trees were used for storing carbon. Now, they can also store hierarchically ordered data, and take up much less space.
Merkle trees -- ones that don’t need ID’ing -- were created by Ralph Merkle in 1988 in an attempt to construct better digital signatures, and are now commonly used as a fast and efficient way to encode blockchain data. The underlying concept is something called data structure trees, where each non-leaf node is a hash of its respective child nodes.
In 2018, John Kuszmaul, a student in MIT’s PRIMES high school research program, which stands for Program for Research in Mathematics, Engineering and Science, along with his mentor Alin Tomescu, came up with an idea to improve Merkle trees: “Verkle trees,” which are much more efficient in proof size.
“Verkle trees are shaping up to be an important part of Ethereum's upcoming scaling upgrades,” Ethereum founder Vitalik Buterin, who recently wrote a blog post on Verkle trees and Kuszmaul’s involvement. “They serve the same function as Merkle trees: you can put a large amount of data into a Verkle tree, and make a short proof ("witness") of any single piece, or set of pieces, of that data that can be verified by someone who only has the root of the tree. If a tree contains a billion pieces of data, making a proof in a traditional binary Merkle tree would require about 1 kilobyte, but in a Verkle tree the proof would be less than 150 bytes - a reduction sufficient to make stateless clients finally viable in practice.”
Buterin noted in his post that Verkle trees are still new, and acknowledged that they were first introduced by Kuszmaul in his 2018 work. Kuszmaul was mentored by Tomescu, an MIT PhD student at the time, who has since graduated with a PhD and currently works at VMware Research Group.
PRIMES, which is a free year-long after-school program, offers research projects and guided reading to high school students. Participants work with MIT researchers on unsolved problems in mathematics, computer science, and computational biology. PRIMES was started in 2010 by Professor Pavel Etingof and Dr. Slava Gerovitch (Math).
“We aim to inspire the next generation of great computer science researchers who will invent, design and program intelligent computers that we can only dream of today,” says MIT professor Srini Devadas, who runs the computer science section of PRIMES that began in 2012. “You will often be baffled as to why your software doesn't do what you think it does, but will be delighted when you diagnose the problem, ecstatic when your code finally works, proud to demonstrate it to everyone, and immensely gratified when someone makes use of it.”
The Computer Science Section of PRIMES has been partially funded by the National Science Foundation for the past several years.