Aug 24, 2022 • 31M
Ok Algebraic Automaton
What exactly counts as a SNARK? Why do some proof systems need structured computation, and what are its limits? Why are boolean circuits so neat? And more!
Musings about cryptography, software, and technology
Topics covered in this episode:
00:50 What exactly counts as a SNARK?
08:12 SNARKs with sublinear verification time
12:34 Algebraic Automatons and structured computation
Linear-Time Probabilistic Proofs Over Every Field: https://eprint.iacr.org/2022/1056
16:59 On the limits of structured computation
Miden VM: https://maticnetwork.github.io/miden/intro/main.html
- Strictly speaking it isn't random access, but linear access. The addresses need to increase within the same context. At least, if the docs are correct.The most significant improvement: Miden VM is now Turing-complete and comes with read-write random access memory. This means the VM can execute any program you can throw at it.Polygon Miden 💜 @0xPolygonMiden
21:17 Why Boolean Circuits are more natural than Arithmetic Circuits
Measuring SNARK performance - Justin Thaler: https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/
If you enjoyed this episode, and want to get notified when the next one arrives, feel free to subscribe:
If you want even more updates, feel free to follow me on Twitter.