This all look intriguing, e.g. that thereās a virtual machine for this (see Risc Zero link), zkVM, just unclear how slow this is, for arbitrary Rust code, unclear to me itās based on RISC-V, but suppose youāre right the VM emulated it).
I knew of zero-knowledge proofs, but not zk-SNARK, or STARK (seemingly what to concentrate on), apparently building of them, and both seemingly related to āverifiable computingā you pointed to, though not exactly the same.
Itās 65 pages, but donāt worry, seems readable, and intriguing (e.g. what I put in bold):
While initially planned as short, the work now spans several dozens of pages, nevertheless it requires very little pre-requisite knowledge, and one can freely skip familiar parts.
[ā¦]
Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) is the truly ingenious method of proving that something is true without revealing any other information, however, why it is useful in the ļ¬rst place?
Zero-knowledge proofs are advantageous in a myriad of application, including:
ā¢ Proving statement on private data:
ā Person A has more than X in his bank account
ā In the last year, a bank did not transact with an entity Y
ā Matching DNA without revealing full DNA
ā One has a credit score higher than Z
ā¢ Anonymous authorization:
ā Proving that requester R has right to access web-siteās restricted area without revealing its identity (e.g., login, password)
ā Prove that one is from the list of allowed countries/states without revealing from which one exactly
ā Prove that one owns a monthly pass to a subway/metro without revealing cardās id
ā¢ Anonymous payments:
ā Payment with full detachment from any kind of identity
ā Paying taxes without revealing oneās earnings [ā¦]
And:
Zk-SNARKs have existed for a while, but the STARK proof system is a relatively new thing. It stands out for several reasons:
- While traditional zk-SNARKs rely on cutting-edge cryptographic hard problems and assumptions, the only cryptographic ingredient in a STARK proof system is a collision-resistant hash function. As a result, the proof system is provably post-quantum under an idealized model of the hash function 1.
In part 6: Speeding things up:
The Number Theoretic Transform and its Applications
The Fast Fourier Transform
The Number Theoretic Transform (NTT) is a powerful mathematical tool that has become increasingly important in developing Post Quantum Cryptography (PQC) and Homomorphic Encryption (HE). Its ability to efficiently calculate polynomial multiplication using the convolution theorem with a quasi-linear complexity O(N log n) instead of O(n^2) when implemented with Fast Fourier Transform-style algorithms has made it a key component in modern cryptography. FFT-style NTT algorithm or fast-NTT is particularly useful in lattice-based cryptography. In this short note, we briefly introduce the basic concepts of linear, cyclic, and negacyclic convolutions via traditional schoolbook algorithms, traditional NTT, its inverse (INTT), and FFT-like versions of NTT/INTT. We then provide consistent toy examples through different concepts and algorithms to understand the basics of NTT concepts.
While āBeginners Guideā, not surprisingly a bit math-heavy, assuming some number-theoretic backgroundā¦:
Example 3.1. In a ring Z7681 and n = 4, the 4-th root of unity which satisfy the condition Ļ4 ā” 1 mod 7681 are {3383, 4298, 7680}.