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

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.

working on @tableland | co-hosting /zk | avichalp.me

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

love it. In university they were all about in memory search being O(n)*log(n) at best and O(n^2) at worst. but if you have the memory (in theory, with sparse it doesn't even need to be there fully) you can do naive O(n) haha

dind't even think of it. thanks for sharing