A place for talking about the Ethereum Virtual Machine on Farcaster.

How sparse merkle trees work:

Imagine you have a sorted array of integers, and you want to check if 5 is in it.

If I prove to you 4 and 6 are right next to each other, then it’s a proof of the same.

So a non-inclusion proof is a combination of two inclusion proofs.

Working on building zkTLS infra/products. A ruthless empiricist and meme connoisseur.

http://opacity.network

Here is a Typescript and Python implementation: 

https://github.com/cedoor/sparse-merkle-tree

https://github.com/thyeem/compare-sparse-merkle-tries

Sharing these because they’ll be easy to read. The Python one actually compares three implementations.

https://warpcast.com/eulerlagrange.eth/0xdc0f33ba

SMTs are quick to update 1D analogy:

O(N) sorting algo.

You want to sort 0-99 that are in random order.

Initialize array of size 100 that’s empty. Loop through random array, if you see the number 37, put it in the 36th index in empty array.

QED.

Works because each value has one location in the target array.