Justin Thaler
@SuccinctJT
Followers
5,441
Following
74
Media
3
Statuses
241
Research Partner @ a16z crypto Associate Professor of CS at Georgetown.
Joined January 2022
Don't wanna be here?
Send us removal request.
Explore trending content on Musk Viewer
Macklemore
• 312047 Tweets
連休明け
• 227682 Tweets
WIN Premiere Night TH
• 226486 Tweets
GW明け
• 183439 Tweets
Tyla
• 173278 Tweets
Timberwolves
• 104112 Tweets
#ジブリのうた
• 73382 Tweets
Switch後継機
• 71894 Tweets
休み明け
• 47566 Tweets
OverTheMoon by PerthChimon
• 45792 Tweets
BINGLING ENDGAME
• 44296 Tweets
SB19 GOES INTERNATIONAL
• 38409 Tweets
#Victor_เริ่มก่อน
• 34537 Tweets
竹田くん
• 29940 Tweets
#家庭教師ヒットマンREBORN
• 28153 Tweets
Barnsdall
• 26069 Tweets
PRABOWOingin YangTERBAIK
• 25044 Tweets
MenataNKRI LebihMAJU
• 24258 Tweets
ニンダイ
• 23245 Tweets
次世代機
• 16266 Tweets
2ND LOREAL LIVE X BOOK
• 14205 Tweets
生田斗真
• 14197 Tweets
桃源暗鬼アニメ化
• 12928 Tweets
Khumalo
• 12898 Tweets
退職代行
• 11077 Tweets
#ヒゲダンラジオライブ
• 10057 Tweets
1/ We're excited to share the initial release of Jolt, a new approach to zkVM design. Early benchmarks indicate it outperforms RISC Zero by ~6x and SP1 by up to 2x. Major optimizations are still in the pipeline.
105
121
620
Introducing Lasso and Jolt, two new works that I hope will change how SNARKs are designed and built. You can read about them here: (1/6)
21
373
469
In my latest blog post on SNARKs, I identify, and try to clear up, a variety of misconceptions that have been hindering progress and causing confusion.
I hope this leads to more informed and accurate discourse surrounding this transformative technology!
21
161
470
I have some exciting news to share – I’ll be joining
@a16zcrypto
research as a Research Partner at the conclusion of this semester. (1/7)
38
50
326
After my last post, I had a request from some folks to discuss the security of SNARKs as they are currently deployed. I've done so in this new post here: (1/9)
18
78
255
In my latest blog posts, I delve into work just unveiled by Ben Diamond and Jim Posen (D&P) that, in my view, reshapes the landscape for hashing-based SNARKs. D&P have fine-tuned the Ligero/Brakedown polynomial commitment scheme... (1/5)
4
30
143
A couple of talks I gave during a recent visit to a16z are now up on Youtube.
Part 1:
Part 2: (1/4)
21
24
139
Known attacks on FRI when run non-interactively at 80 bits of security are feasible. This is not an academic question. It's about securing hundreds of millions of dollars of assets and a systemic risk to the rollup ecosystem. (1/3)
@DCbuild3r
@SuccinctJT
An ACCURATE SCIENTIFIC comparison MUST USE SAME SAME CRYPTO assumptions (CRH, or ROM) for both systems. AND UNDER THOSE SAME ASSUMPTIONS SNARKs have 0 bits of security.
6
0
9
5
20
119
I had a great time talking with
@AnnaRRose
! We're starting a fresh reading group for Proofs, Arguments, and Zero-Knowledge sometime next month. If you're interested, join the Discord for scheduling and updates.
This week,
@AnnaRRose
chats with
@SuccinctJT
about his work on interactive proofs + SNARKs. Then discuss the making of his book Proofs, Arguments, and Zero Knowledge + the organic study group that formed around it over on the
@__zkhack__
discord + more!
0
13
53
6
22
117
I enjoyed getting into the weeds of Lasso+Jolt in this Study Club Session and fielding tons of thoughtful questions! It should be a useful resource for anyone looking to learn more about these tools.
Just published the latest ZK Study Club -
@SuccinctJT
hosts a session on Lasso and Jolt, moderated by
@apruden08
and with awesome questions from
@feministPLT
,
@rel_zeta_tech
,
@arantxazapico
& more
Subscribe on youtube for more study club videos!
0
11
64
5
15
100
Thanks to
@samrags_
and
@moodlezoup
, an initial Lasso implementation is now available, and we are looking for contributors to finish building Jolt. Here’s their overview: (5/6)
5
10
99
Nice recent post on hardware acceleration and the sum-check protocol (or more generally any SNARK obtained by applying Fiat-Shamir to a logarithmic-round interactive protocol). Here is some additional context. (1/6)
Are we better off with Plonk and NTT rather than with HyperPlonk and MLE-SumCheck? 🤯
Answers in our latest blog 👀
2
24
113
3
21
96
The third part of my talk series on SNARKs is now up! This final talk covers the main ideas that go into designing "polynomial IOPs", which form the information-theoretic core of most SNARKs. (1/2)
3
20
97
TLDR: A recent comparison of FRI to MSM-based commitments claims FRI is orders of magnitude better but in fact it is worse.
Already,
@Zac_Aztec
provides important context and corrections to this slide in the following thread, but I would add several more: …
6
20
74
I enjoyed talking to
@AnnaRRose
&
@GuilleAngeris
on the
@zeroknowledgefm
podcast about Jolt, the sum-check protocol, and how SNARKs will evolve! I'm excited to see where these innovations take us next.
0
23
93
4/ And for a developer's perspective on Jolt, check out the blog post by
@moodlezoup
and
@samrags_
. As Jolt paves the way for a new era in SNARK design, we're open to collaboration. If you're interested in contributing to its development, we'd love to hear…
6
3
60
2/ Jolt isn't just a leap in speed; it's a paradigm shift. Powered by the sum-check protocol, it instantiates the lookup singularity, yielding the simplest and most extensible zkVM to date. And it shows that what makes VMs good for real hardware also makes them good for SNARKs.
16
1
60
3/ Explore the concepts in my two latest blog posts: a less-technical overview and a comprehensive technical discussion
7
4
59
To the extent that anyone might deem SNARKs that use elliptic curves as having 0 bits of security, StarkEx is also at 0 bits of security today due its use of ECDSA signatures, as is its L1, Ethereum. (3/3)
2
1
47
These are the stakes. I congratulate StarkWare on upping the StarkNet (SHARP) verifier to 96 bits of security earlier this week as promised. However, the dYdX StarkEx verifier remains at 80 bits . I continue to believe that this is too low. (2/3)
3
2
41
@DCbuild3r
@fede_intern
At this point I'm aware of three criticisms/claims (not all from this thread) that haven't yet been addressed. Let me address each.
1) If we could do everything with lookups we would already be doing that. This misses two things. First, Lasso is more than an order of…
2
4
32
Lasso is a new lookup argument with a much faster prover and other attractive properties. Jolt builds on Lasso to offer a new paradigm in zkVM design. Together, we believe they realize
@barrywhitehat
's vision of a "lookup singularity" for simpler/more auditable SNARKs. (2/6)
1
1
31
Our preliminary benchmarks indicate the initial Lasso implementation is about 10x faster than Halo2’s lookup argument, and we expect 30x-40x after optimization. (4/6)
2
4
27
@mitschabaude
In terms of techniques, I do not actually think there is huge novelty in Lasso. The techniques are already there in Spark. Plus, I suspect you could get a lookup argument with similar costs to Lasso with c=1 from Plookup by simply replacing the grand product argument with…
2
5
26
Also check out two new ZK courses if you haven't already! and
1
0
25
I’ve already contributed to their robust content library: a 3-part lecture on SNARK design (), and posts on SNARK security and performance () and measuring SNARK performance () (5/7)
1
5
25
The papers are preliminary, and feedback on them is welcome! (6/6)
1
0
24
My own viewpoint is that sum-check-based SNARKs remain the most promising for minimizing total prover work, and that good hardware implementations will follow. (6/6)
3
1
24
Check out my two posts and , as well as Ben and Jim's post for a hardware-centric angle on these developments: (4/4)
1
7
23
The web3 community's open ethos means that a16z crypto researchers can work with anyone, and contribute to the ecosystem as a whole, not only to the firm. I can't wait to embark on this adventure and look forward to sharing more as I learn and grow with the team (7/7)
5
1
20
The key technical tools underlying Lasso and Jolt are the sum-check protocol and Spark, the sparse polynomial commitment scheme from Spartan (which itself uses sum-check). I'll have more to say about these tools in the coming weeks. (3/6)
1
0
20
I am thrilled to be working with brilliant colleagues, not only in the research group, but throughout the entire firm, including
@eddylazzarin
@Tim_Org
@smc90
@samrags_
(6/7)
1
1
19
@fede_intern
Thanks for the reply.
I agree that in general the community is nowhere near precise enough in cost accounting, as discussed at length in my recent "misconceptions" blog post. However, with a precise accounting it is indeed possible to understand the ballpark concrete costs of…
0
2
18
This space is experiencing an explosion of innovation, and I think this technology can be transformative. But if we prioritize performance over security, we may cause people to lose trust in the technology and potentially see misappropriated funds in the process. (7/9)
1
2
16
@EliBenSasson
At any rate, the protocols we use to secure millions of dollars of assets must not be breakable today. For that reason, FRI should not be run non-interactively at 80 bits of security if it is securing anything of value. (3/3)
0
0
16
None of the above is investment advice, for more info go to
3
0
16
...particularly when it's used to commit to small values. When combined with sum-check-based SNARKs like Lasso and Jolt, this paves the way for much faster SNARKs for standard hash functions like Keccak. The domino effect? (2/5)
1
1
14
The tweet I'm responding to suggests that a protocol using non-hashing cryptography be deemed to have 0 bits of security when compared to a hashing-based one. This immediately leads to nonsensical conclusions, or at least ones that
@EliBenSasson
presumably disagrees with (2/3)
1
0
14
The upshot is that some deployed SNARKs are being run at "80 bits of security" - which is not as well-defined a term as it may seem. My post unpacks this and explains why I think it is not enough. (2/9)
1
0
14
This content is provided for informational purposes only, and should not be relied upon as legal, business, investment, or tax advice. See for more info. (9/9)
1
1
13
These issues mainly arise in post-quantum-secure SNARKs (PQ-SNARKs), which in today's deployments means FRI-based ones. This might be for a combination of reasons. (3/9)
1
0
13
Given the sophisticated nature of these protocols, experts need to feel comfortable candidly discussing their security and that of the contracts that implement them. This post is my attempt to set an example in this regard. (6/9)
1
0
13
@fede_intern
@yezhang1998
FYI there's been some nice improvements to Brakedown:
I'm excited about this approach to polynomial commitments and hopeful we'll see further improvements soon.
0
2
13
I hope the post is informative and sparks a discussion about best practices and norms, both in deploying SNARKs and talking about them. (8/9)
1
0
11
@mitschabaude
I agree that people are already doing decomposition for tables like bitwiseAND. This is explicit in Sam and Michael's post on "Understanding Lookups":
The advantages of Lasso are a matter of performance, generality, and perspective.
An example might…
2
1
12
@dimahledba
@apriori0x
@LoganJastremski
@StarkWareLtd
The dYdX StarkEx verifier remains at 80 bits of security today.
These are the stakes. I congratulate StarkWare on upping the StarkNet (SHARP) verifier to 96 bits of security earlier this week as promised. However, the dYdX StarkEx verifier remains at 80 bits . I continue to believe that this is too low. (2/3)
3
2
41
1
0
12
Amplified recursion capabilities for Ligero/Brakedown, overcoming the hurdles of their somewhat large verification costs. This addresses the primary obstacle keeping them from wide deployment. (3/5)
1
0
12
To achieve scalable SNARK provers, a complete reconfiguration of today’s deployments is needed, from polynomial IOPs and commitment schemes to hash functions and zkVM design. My posts unpack what should change. (4/5)
1
0
11
With FRI, there is a tension between verifier costs and security, and the proofs are on the larger side. So this tension may get resolved in favor of performance over security. (4/9)
1
0
11
@weikengchen
StarkWare already works over the 251-bit prime (see Section 3.1.1 here: ). The prime matches the field used in StarkEx ECDSA signatures . So increasing security here requires increasing number of FRI queries, not the field size.
1
0
10
Also, the security of non-PQ SNARKs is determined by the elliptic curve they choose to use, and the community has largely coalesced around a handful of curves with good security. (5/9)
1
0
11
None of the above should be taken as investment advice; please see for more information.
1
0
11
@rel_zeta_tech
@Zac_Aztec
EC-based schemes are definitely best if working over large fields (either because an application calls for that, or because it simplifies implementation). 6-12 field ops per ~20-bit-committed-value is a tough bar to clear.
To commit to N values, (subsequent improvements to)…
0
0
11
To add to to this, SNARKs that avoid both FRI and sum-check (PlonK, Marlin, Groth16) require FFTs (and multiexps), so the memory locality issues noted above apply to these SNARKs as well. (5/6)
2
0
11
@FlyingNobita
Some extra detail for anyone following along: We saw that Freivalds' algorithm for verifying n x n matrix multiplication has soundness error 1/|F|, while an variant using univariate rather than n-variate polynomials has error (n-1)/|F|.
3
1
11
I believe blockchains will transform society’s mechanisms for establishing trust & privacy, and that they raise deep technical and intellectual questions. And I expect that a16z crypto research will play a central role in shaping this emerging discipline. (2/7)
1
0
11
The breadth and depth of knowledge within the research group and its many visitors is incredible. I have learned a tremendous amount from them directly, as well as from the blog posts, podcasts, and videos produced since the group's inception just 7 months ago. (4/7)
1
1
10
Several have reached out confused about this third tweet. Why do SNARKs using elliptic curves have 0 bits of security, that doesn't make sense? That's the point. (1/3)
1
0
10
The group is uniquely focused on fundamentally understanding blockchains and on benefiting the ecosystem today. I think this two-pronged focus is maximally impactful, and also a lot of fun. (3/7)
1
0
9
@rel_zeta_tech
First, the estimates for GKR are too high by a factor of about 4. Details below.
(Thaler13 didn't optimize constants well. I pay much more attention to them in this new paper: )
>Now we need to estimate the constant in the dynamic programming for all the…
2
0
9
@fede_intern
FRI proofs with MBs of space?
As one example, Polygon zkEVM requires 250+ GBs of space. The zkEVM circuit trace has 2^23 rows, 1164 columns, and RS rate of 1/2. I don't consider that circuit to be large, though this is subjective. (1/2)
1
0
9
I hope it's a useful resource, and coveys some of the magic that gives these protocols their power. (2/2)
1
2
8
There has been work on hardware implementations of sum-check: Zebra () and Giraffe (). These works heavily exploit the essentially perfect memory locality of the sum-check prover in each round. (2/6)
1
2
8
@_bfarmer
@wyatt_benno
@cmpeq
Do you at least agree there should be two FFTs instead of one in the counts for FRI?
*I don't think I understand the claim that a single MSM of length 2^25 is going to increase latency. 2^25 is tiny. There are hardware companies that can do 2^30-length MSMs in under a second…
1
0
8
At some point a third talk will likely be posted, focusing more on how SNARKs work and less on the intricacies of the rollup application. (4/4)
0
0
7
@rel_zeta_tech
@PratyushRT
@0xAlbertG
@mpfzajac
It's the super-constant number of rounds.
Applying Fiat-Shamir to an r-round protocol with lambda bits of security can result in a non-interactive protocol with only lambda/r bits of security. No one had ruled out such a security loss for FRI.
1
1
7
@_bfarmer
It's certainly possible to use curves over extension fields, but it requires a lot of care. The discrete log problem appears to be easier over extension fields at roughly equivalent total bit sizes, see for example this paper: (1/2)
1
1
7
@YupengZhang7
The mix of additive and multiplicative notations doesn't help. But many papers refer to group exponentiations/scalar-multiplications as "group operations" and refer to n exponentiations as "linear time". I don't think additive vs. multiplicative confusion explains that.
1
0
7
Hopefully, the talks will be useful to anyone who, like me, is trying to understand this application space. It was awesome to dive into the details of many innovative projects.
More detailed statements about SNARK performance are in this blog post: (3/4)
1
0
6
@mitschabaude
@o1_labs
Adding to this after reflection, we came upon the notion of decomposable tables because they naturally arise in sparse polynomial evaluation, where the "big table" is all Lagrange basis polynomials evaluated at the evaluation point r, and the subtables are Lagrange basis…
1
0
6
@_bfarmer
Since many FRI-based projects are breaking large circuits into small pieces and applying recursion, the prover bottleneck tends to be Merkle-hashing the result of an FFT. I think hashing 2n 251-bit field elements is about twice as expensive as n 256-bit field elements? (2/2)
1
0
5
@rel_zeta_tech
@PratyushRT
@0xAlbertG
@mpfzajac
Also, even for 2-round protocols, a factor-2 loss in bits of security would be catastrophic. And (ignoring FRI) lots of deployed protocols do use 2 rounds before being Fiat-Shamir-ed. The paper also rules out any loss of security in many such constant-round protocols.
1
1
5
0
0
5
@_bfarmer
@weikengchen
One that I think we'll see soon is neural network training/inference, the bottleneck in which is often repeated matrix multiplication of small integers. I'm working on some others that I hope people will find compelling. (2/7)
2
0
6
@_bfarmer
Which leads some to express sentiments like: .
I agree that small fields are very powerful for simulating native operations on many instruction set architectures (though some new work coming out in a few weeks will offer a counterpoint to that too). (2/2)
1
1
5
In round i of sum-check, the prover can make one streaming pass over the data structure of size N/2^i. I don't believe FFTs have the same degree of memory locality, which is why many distributed FFT algorithms require all-to-all communication. (3/6)
2
0
5
@m_ratsim
@Zac_Aztec
@EliBenSasson
Vectorization of 256-bit ModMult is possible and in fact done in Curve25519-dalek, which uses AVX2 (for x86-64 processors). Note that this is for Crandall-style rather than Montgomery-style reductions (again, not all MSM-based commitments need pairing-friendly curves).
See…
2
0
5
@nanne007
You are right, thanks a lot for the correction!
(We may have originally written this text assuming m=log(N)/c for simplicity, and then later scrapped that. It's clearer to separate the sparsity parameter m and the memory size N^{1/c}, even if it's ultimately optimal to choose c…
1
0
5
@rel_zeta_tech
@DCbuild3r
@fede_intern
No, we don't need to commit to those. Those values are all computed by P via field work in sum-check with no explicit proof that P computed them correctly (sum-check itself implicitly checks this). Here's why this works:
1
0
4
Nothing in the podcast should be taken as investment advice, see for more info.
0
0
4
@rel_zeta_tech
@DCbuild3r
@fede_intern
Yes, the log^2(n) hashes for GKR grand product are concretely and asymptotically fewer than the O(lambda * log^2(n)) hashes in FRI.
2
0
4
As noted in the post's conclusion, FRI (on top of requiring FFTs) has the same logarithmic round folding structure as sum-check, and the post itself presumes that this folding is not the bottleneck in SNARKs that use FRI. (4/6)
1
0
4
@dlubarov
@PapiniShahar
@rel_zeta_tech
@_bfarmer
@wyatt_benno
@cmpeq
Oh I see, thank you!
I was confused by the combination of ambiguous parentheses and the slide ignoring the cost of additions in the FFT, which are ~40% of the multiplication costs according to the reference they are taken from (Table 1, Apple M1, here: ).…
1
0
4
@cmpeq
@_bfarmer
I don't think ECDSA is an isolated example. Outside of SNARKs for VM abstractions, many applications involve proving statements about crypto-systems that inherently involve large fields. It's a mix. I'm trying to add nuance to the conversation, not switch to an opposite extreme.
1
0
4
@weikengchen
Also, recursion brings both overhead and imperfectly-understood security, especially when new SNARK-friendly hash functions are used. Just because people are relying heavily on it today to keep circuit size in check does not mean they always will. (2/2)
1
0
4
@_bfarmer
@weikengchen
Third, I wouldn't totally write off security considerations yet. I hope you're right that the situation with SNARK-friendly hash functions is going to better soon. But while projects are deploying Poseidon with at most 95 bits of security, it's premature to relax on this. (6/7)
2
0
3
@rel_zeta_tech
@samrags_
@moodlezoup
Lasso basically *is* (an optimized variant of) Spark. It's circular to say that the vector of counts for the big table is sparse and we have a sparse poly commit, so no problem, we're done. (5/5)
1
0
3
@weikengchen
If FFT is not the bottleneck (say it's merkle-hashing, or multi-exp, or non-sum-check-related-field-ops), then sum-check shouldn't be either (1/2)
2
0
3
@_bfarmer
@weikengchen
Even with standard hashes, I think there are entities that are conservative w/ security and won't use this tech given the state of our understanding. All implemented composed SNARKs have heuristic security or at least significant loss in concrete security can't be ruled out (7/7)
0
0
3
@_bfarmer
In the sentence quoted in your first tweet, I meant that using two 251 bit field elements to represent a 256-bit data type is roughly twice as expensive as using one 256-bit field element. (1/2)
1
1
3
@zkproofs
@williamborgeaud
@recmo
No. To have P commit to a vector guaranteed to be of the form (z, z), just have P commit to z.
The MLE of (z, z) has one extra variable relative to z itself. The first variable is simply ignored, and the remaining variables are fed into the commitment to z.
2
0
3
@_bfarmer
@wyatt_benno
@cmpeq
Yes, I was referring to Lasso/Jolt, which avoid the need for the prover to commit to large field elements, thereby speeding up MSM-based techniques by an order of magnitude or more.
My views are further elaborated upon in recent tweets: …
@rel_zeta_tech
@Zac_Aztec
EC-based schemes are definitely best if working over large fields (either because an application calls for that, or because it simplifies implementation). 6-12 field ops per ~20-bit-committed-value is a tough bar to clear.
To commit to N values, (subsequent improvements to)…
0
0
11
1
1
3
@rel_Aztec
I agree that concretely lambda can be thought of as log N times a large-ish constant. But I think there are both asymptotic and concrete reasons to treat is as super-logarithmic, especially in research papers. (1/2)
1
0
3
@rel_zeta_tech
@DCbuild3r
@fede_intern
You can view those values as lookups into an MLE-structured table, where we know in advance that the k'th lookup will be to the k'th entry. (continued)
1
0
3
@_bfarmer
@weikengchen
BTW already-pervasive protocols like Bulletproofs/IPA can be viewed as special-purpose monolithic (sum-check-based!) SNARKs if you squint hard enough, see, e.g., Sum-Check Arguments (, Appendix A). (3/7)
1
0
3
@fede_intern
StarkWare is using an RS rate of 1/16. That would presumably 8x the space on a trace of similar size. Even more when the bigger field is taken into account. (2/2)
0
0
3
The talks focus on SNARKs and their applications to blockchain scalability. In preparing these, I learned a lot about validity rollups and their subtleties---I was surprised by just how much there was to learn. (2/4)
1
1
3