We have been aggressively optimizing our GPU execution to reduce the cost of our polynomial commitments. This is the dominating cost (asymptotically and concretely) of most proof systems. However, as of these most recent benchmarks, the costs of our commitment scheme are now about 40% of our overall proof time (and dropping). What's next? The other 60% 😎

When you're looking at the Proof of SQL benchmarks, note that this graph is deceptive. It's a log-log graph, so it makes it look like performance decreases as the dataset scales. The opposite is true. In fact, performance on this graph is sublinear. We haven't even hit the asymptomatic linear scaling until we reach close to 10 million rows of data.

Super excited to launch Proof of SQL today! Proof of SQL is a ZK protocol that enables scalable data processing beyond anything we’ve seen in Web3. The trick that gives the speed unlock here is that we built the protocol around the data: the commitments are data-driven, the arithmetization is data-driven, and the acceleration is data-driven. For example, let’s think about the commitments. Merkle tree based data structures are not native to ZK: they require a minimum of n hashes to access n items of data. This is a large overhead simply for data access. Instead, we use the proof-native commitment scheme as the data structures holding the data itself. This begs the question: what commitment schemes are conducive to holding data? There are 3 major criteria that we think are critical: 1) It has to scale. In other words, it should be able to support huge amounts of data. A trusted setup of size 2^30 only can support roughly a billion data elements. That's not a lot of data. 2) It has to be succinctly updateable/appendable. In other words, we want a commitment scheme that can be incrementally modified without needing access to the entire dataset, but only needing a small cache to modify it. 3) It needs succinct evaluation proofs and fast proof and verification times. Merkle trees satisfy 1 and 2, but not 3. KZG-style commitments satisfy 2 and 3, but not 1. FRI-style commitments satisfy 1 and 3, but not 2. The Dory commitment scheme satisfies all three. That's what we use today, but stay tuned, because we can do even better. 👀🚀

Brain teaser for y'all. How do you prove that a set of values are unique? 👇

Security, Scalability, Speed. Pick 3.

Why aren’t more DeFi protocols using ZK coprocessors? Here's some guesses: 1. Latency issues. Who wants to wait 20 Eth blocks (or more) for a single result? The reason oracles are so popular in DeFi and coprocessors aren't yet, is because most oracles focus on delivering results back onchain quickly during a transaction (next block). 2. Lack of data. Coprocessors don't really give access to a lot of data. Some give access to historical chain data, but they can't produce proofs that process or aggregate tens of thousands (much less millions/billions) of data points of chain history. This doesn't seem to be the focus of most zkVM teams, but it certainly is our focus. 3. Developer experience can be goofy. Some are decent, but others have a cumbersome learning curve because DeFi calculations must be rewritten to follow the coprocessor's SDK. I may be bit biased because those are the big 3 things that we solve with Proof of SQL @spaceandtime. My vision is a coprocessor pipeline that simply combines a zkVM paired with a specialized zkDB rather than trying to query over entire chain histories in a powerful zkVM like RISC Zero, SP1, Jolt, Nexus, etc.

A ZK-proven database is the key to scaling Web3. Databases are already the bedrock of Web2. Without them, your favorite website wouldn't exist. You wouldn't see this tweet. Now imagine if Web3 not only had secure, fast, and cheap smart contracts—thanks to pioneers like @zksync—but if those smart contracts could also access databases in a lightning fast and verifiable way. This is no longer a pipe dream. Super pumped to partner with zkSync to make this the reality in Web3.

Learn Yul? ✅ Port ZK verifiers? ✅ Cheap SQL on Ethereum? 👀

Here's a solution: Let f be a univariate polynomial who's roots are the claimed unique values. A prover can commit to this polynomial using your favorite PCS. Any scheme will work if you're smart enough. Then, the prover can commit to additional polynomials p and q. Now, all we need is evaluation proofs of f(r), p(r), and q(r). Additionally, the formal derivative f' has an evaluation that can be easily evaluated several different ways (X margins too small). Verifier simply needs to check that f(r)p(r)+f'(r)q(r)=1. Proof: Schwartz-Zippel gives soundness, Bezoit and weak Nullstellensatz give completeness.

As the community contributes to Blitzar, one thing I’m excited to see is support for more curves. Today, Blitzar supports… - BN254 - BLS12-381 - Curve25519 If you need a curve that’s not supported today, add it! Add support for Grumpkin, add support for Pasta curves. We open-sourced Blitzar so that you can improve and customize it for your use case. spaceandtime.io/blitzar What curves do you want to see supported in Blitzar?

In order to understand Blitzar you need to understand multi-scalar multiplication. MSM involves a series of calculations where each one takes a group element and multiplies it by a corresponding data element: group element 1 times data element 1, plus group element 2 times data element 2, etc. This process is repeated for a series of group and data element pairs. What makes MSM particularly powerful is its ability to perform these computations in parallel (processing multiple data points simultaneously). Blitzar executes these parallel computations really efficiently. One of the things we're working on right now is expanding the types of MSM that Blitzar can compute. Inner product argument is built around computing commitments to a really large column of data. Dory is focused on computing commitments to matrices of data - a bunch of smaller columns of data. Blitzar is already extremely performant for the first scenario, and we’re working to make it performant for the second as well. Check it out at spaceandtime.io/blitzar

Let’s talk commitment schemes. When we were building Blitzar, we started with support for a generic inner product argument using Pedersen commitments. This is similar to what bullet proofs and a variety of other protocols do. It doesn't require a trusted setup, can grow arbitrarily large, and it's relatively simple to build… but it has a linear time verifier, which doesn't work for succinct/cheap verification. The second commitment scheme we've added is the Dory commitment scheme, which also has a transparent setup and can grow arbitrarily. Dory has some nice flexibility because it's actually a commitment to a matrix rather than to just a column of data. It's also much cheaper verification, but it's still not quite cheap enough for verification onchain. Now, we're working on an in-house, custom-built, composition-based commitment scheme to support a core function required for Proof of SQL: the ability to update a commitment. This new scheme will deliver succinct verification that can be done onchain and satisfies that property of updatability, which is critical to what we’re building and a powerful primitive for other protocols. Excited to share more soon.

Pros: Asymptotically optimal verifier and can prove uniqueness of arbitrary field elements. Cons: The best way I know how to compute p and q is quasilinear time. Challenge: Do me one better. Make the prover linarithmic, the complexity of the element distinctness problem. End🧵

The standard approach is to sort the values, take the difference between consecutive values and then show that they are all positive. Few problems with this approach. 1) It requires a range proof. While there are good range proofs, afaik, they mostly boil down to decomposition+lookup at some level. This can be a bit costly. 2) It requires bounding the values in order to avoid field wrapping issues. This is problematic if your values are, say, wallet addresses, which is probably the most important use case. 3) It's ugly: there's no obvious reason why uniqueness should require an ordering. In fact, field elements have no ordering and everyone insist on faking one. I'd rather not.

Currently looking into leveraging CUDA's warp-level primitives to make Blitzar even faster. Gotta keep stacking those 2x performance gains! 🔥

👀

🙏