Tiago Martins

Finally the last post! This is where the main novelty resides

Introducing the final installment of our Arithmetization in STARKs series, where we will compare low-degree bounds of AIR and PAIR methods. We explore the computational complexity of both approaches and discuss transition strategies between the two. 1/6 threesigma.xyz/blog/degree-bo…

A general description of PAIR to make the contents available a little less sparse. We tried to make it easy to understand and complete at the same time.

We are excited to share the second part in our Series on Arithmetization Methods for STARKs: Preprocessed AIR. 1/5 threesigma.xyz/blog/preproces…

New blogpost just dropped: threesigma.xyz/blog/an-introd… It used the ideas that were described in our paper eprint.iacr.org/2023/661 @joaoanf_ts @threesigma_xyz

We are thrilled to announce our new Series on Arithmetization Methods for STARKs, where we will dive into AIR and its variant PAIR, exploring their soundness implications for low-degree testing. 1/5 threesigma.xyz/blog/an-introd…

#ePrint Study of Arithmetization Methods for STARKs: T Martins, J Farinha ia.cr/2023/661

@joaoanf_ts and I developed this work (eprint.iacr.org/2023/661.pdf) which might present itself useful in: (1) defining common standards in the development and dissemination of arithmetization research, and (2) inducing new ideas in this area. It is about AIR and Preprocessed AIR.

As DeFi grows in the crypto environment, capital efficiency has emerged as a major concern for L2 solutions. Our most recent research study describes the implementation of a cross-L2 AMM to address the issue of liquidity fragmentation. Read it at threesigma.xyz/blog/damm. 1/6

Making optimistic rollups capital-efficient 💸

We are excited to announce our new two-part series: Challenging Periods Reimagined, which proposes a new dynamic challenging period and decentralization paradigm for Optimistic Rollups. Read Part 1 at threesigma.xyz/blog/optimisti…. 1/4

@realgmhacker @threesigma_xyz Yeah of course!

@0xtiago @threesigma_xyz No I am not familiar with those... 🫣🫠 Hey but perhaps you can explain that stuff over a beer 🍻

1/5 Are you familiar with the concepts of soundness in the context of DEEP-FRI and ethSTARK papers? If so, you may have noticed that they relate acceptance probability with seemingly different things. Reed-Solomon proximity in DEEP-FRI and AIR satisfyability in ethSTARK.

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz Yes I agree that the vanishing polynomial becomes much simpler. But I believe that complexity gets transferred onto the PAIR constraints itself since the selector will have to describe where the original enforcement domains were. The prover complexity will still depend on H_i

@0xtiago @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz Higher degree but low arithmetic complexity as verifier will only use something like Z_H=X^n-1. You're mixing a bit the PAIR and its compilation into a proof system; main point is you can compile PAIR to a proof system like plonk where verifier complexity doesn't depend on |H_i|

1/4 What's P-AIR and how does it affect #ZK proofs @aztecnetwork? Preprocessed Algebraic Intermediate Representation (P-AIR) combines disjoint AIR constraints into larger combined constraints with selectors. Can this damage the soundness of the FRI due to larger rate.

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz This comes from defining the rational constrains. The numerator has degree |Q_i| and the denominator has degree |H_i|. In the case of the PAIR, both the numerator (PAIR polynomial) and denominator (vanishing polynomial of the combined enforcement domain) will have higher degree.

@0xtiago @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz Hmm.. you're right that the dfn of AIR with general enforcement domains captures selectors with 0/1 values..but note that requires verifier complexity potentially linear in the trace size cause of need to compute the vanishing poly of the domain - what they denote by |H_i|

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz ... The composition polynomial is a random combination of the two AIR constraints divided by their respective vanishing polynomial. Using the PAIR selector can surely increase the degree bound of the final "larger" constraint in comparison to the regular composition polynomial.

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz In this example, one could use two AIR constraints: A) Y1-X1-X2=0 with enforcement domain rows 1 and 2 B) Y1-X1*X2=0 with enforcement domain rows 3 and 4 (using the nomenclature of the article) Further in the protocol, the composition polynomial will combine these constraints...

@Paul_Gafni @UHaboeck i.e. the verifier wants to reject proofs is they detect very small distances, but they are more likely to accept faulty proofs. Isn´t that weird?

@Paul_Gafni @UHaboeck So m is a parameter for that influences the tolerance of the FRI protocol, which must be agreed upon before hand. If m is large, then the RS proximity tolerance is lower. However, the acceptance probability is generally higher -> epsilon increases.

1/3 I have been puzzled by a detail in STARKs security. Regarding the paper eprint.iacr.org/2020/654.pdf: how to determine the value of the integer m>2, in the FRI soundness? In this paper, the example sets m=2047. But, in the ethSTARK doc. (eprint.iacr.org/2021/582.pdf), m=3 is chosen.

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz Is the degree bound for the FRI increases,then the number of layers increases, and accordingly the proof size and security risk (if the remaining parameters are kept the same)

@0xtiago @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz Preprocessed columns can be huge, when doing proofs for custom functions like hashes; it probably is worth going from degree 2 to 3 (but I'm not an expert on FRI technicalities so maybe I'm wrong)

@rel_zeta_tech @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz but you can just define where to perform which operations using the enforcement domain. It is as complex as using the selector, no?

@0xtiago @Blulinski @janbenes16 @mike_connor @jaosef @Zac_Aztec @threesigma_xyz It is a night and day difference in efficiency when you have custom functions and not just low-level vm