Compact Sparse Merkle Trees – Efficient Non-Membership Proofs

On Safari/iOS I only get a blank page

You can download the article directly from this link https://osf.io/8mcnh/download

The reason it's slow is because the OSF site loads the pdf in-browser.

It’s more of a paper describing the concept than an actual, production implementation.

CS papers mostly try to explain an idea or an experimental result, describe why it is important, how it relates to existing approaches, what situations it may be useful for, what the drawbacks are, how those might be addressed in future work, etc. Pretty much none of those things are code.

When some algorithm, metric, etc. does need to be presented, it's important to make it as understandable as possible to the reader. This has a few consequences:

- Only the core parts are shown, i.e. the new bits. All of the surrounding infrastructure that would inevitably be required (I/O, error handling, etc.) is omitted, because it's routine stuff for basically any programmer, would distract from understanding the main idea, and probably wouldn't be any good if included (since that's not necessarily what the researchers are good at).

- Programming snippets require a programming language, and these go through fads and fashions over time. I've read papers from many decades ago, with code snippets in MACLISP, Smalltalk72, Algol60, etc. and the ones which remain understandable are those which either limit themselves to a tiny, commonly understood subset of the language (e.g. variables + if/else + loops); or those which have an accompanying description of the language features in English. If we're giving English descriptions anyway, we might as well leave out lots of actual code (especially due to page limits in journals/conference proceedings).

- Since the point of code snippets is to get across the idea, and the notation might also require an accompanying description, it may be better to use a notation specialised to getting across our idea. Usually this is some form of mathematical notation (e.g. superscripts, subscripts, various forms of brackets, bold face, etc.), with an accompanying description of what these things represent.

There is another method to support compact membership proofs and have history-independence. Ethereum uses a Patricia-Merkle tree structure to store its state snapshots. I'm not sure if it supports compact non-membership proofs though.