# Ethereum 2.0 STARK session, October 29, 2018 [toc] ## Participants: * Avihu Levy (head of Product, StarkWare), Eli Ben-Sasson (Chief Scientist, StarkWare), Oren Katz (VP Engineering, StarkWare) * Zahary, Nimbus team, core developer of Nim team * Kristian McDonald, from Sigma Prime, working on Whitehouse (Rust) * Vitalik Buterin (Ethereum co-founder) * Justin Drake (Researcher, Ethereum Foundation) * Dima Shmatko, working on Harmony * Blazej Kolad and Olivier Begassat, Pegasus * Adrian, works on Cosmos and Polkadot * Everet, from Huberbrandt (?) * Awa * Fredrik (Parity CTO) ## Recop The meeting started with Vitalik and Justin raising three topics that STARKs could help with. In terms of timing, the goal is to deploy them in phase 2, as a quantum-safe replacement for previous mechanisms, that will be deployed soon (in 2019-2020). So, current timeline for deployment of STARK-based solutions is 3-5 years (things may change with technological developments). The three items discussed during the session were: Signature aggregation Verifiable Delay Functions (VDFs) Proofs of custodies (for the validators) The first two items occupied most of the discussion time, so we focus our report on them. ### Signature aggregation For PoS solutions it is required that ⅔ of the validators sign off on a block, and the number of validators will reach thousands to tens-of-thousands. Current plan is to use BLS signatures in Phase 0 for the Beacon Chain, and in phase 2 to replace it with STARKs, to make the solution post-quantum secure. Additional benefits of moving to STARKs is that instead of signing a single message (which can be done using BLS signatures), STARKs can allow for different validators to sign different statements/messages. For this particular application only scalability, not privacy, is required (i.e., a non-zk STARK suffices). Justin asked whether a batching STARK solution can be used to save proving time and/or verification time. StarkWare looked at this question offline, and the answer seems to be that indeed, batching can reduce prover complexity (time and space) but not by a significant factor. This is due to the high efficiency of the STARK proving time. At the same time, moving to batching will increase communication complexity (i.e., STARK argument size) and, overall, batching for STARKs does not seem desirable at this point. A point raised by a number of participants (including Vitalik Buterin) is that STARKs have an advantage over BLS in that signing different messages during a single round is doable via STARKs but more problematic using BLS. Additionally, the universality of STARKs could be useful for augmenting the messages being signed. ### Verifiable Delay Functions Currently Ethereum plans on using a scheme based on RSA, which is not quantum secure. This requires a trusted setup. [Justin Drake: Still unclear we can get the ceremony to work. If we can, then RSA is the clear winner.] The VDF solution would require 1 proof per epoch, with very low latency. One needs the proof generation time to be shorter than the actual computation of the iterated PRF (pseudorandom function). Ideally, if T denotes the time to compute the latter (iterated PRF) then the proof should be generated with 0.01T lag time afterwards, so that the VDF and proof can be released within 1.01T after starting the computation. The target for T should be around 1 hour, on dedicated custom-built ASIC, which the Ethereum Foundation will be funding and distributing for free to nodes. StarkWare’s position is that currently it seems that STARK are not an optimal VDF solution. Informally, the universality of STARKs comes with a computational price tag that seems, at least superficially, to make them less useful as VDF solutions. Justin Drake constructing a STARK for iterated application of permutation polynomials (of the Gorelnik and Mulner type), this requires more offline research. Justin Drake also suggested running public competitions on finding optimal candidates for iterated PRFs for construction of a STARK based VDF. Ethereum STARK-supporting pre-compiles Towards supporting STARKs efficiently on Ethereum, it would be beneficial to add pre-compiles and explicit gas costs for the following: Finite field operations for prime fields, binary fields (characteristic 2) and field extensions. Ideally, the cost should be roughly the same across all finite fields in which a single field element can be represented using a “small” number of bits (say, at most 256 bits) Popular hash functions like Blake and STARK-friendly hashes like Pedersen, MiMC and Jarvis/Friday. WASM might remove the need for pre-compiles all together. _Summary written by Avihu, Oren and Eli (StarkWare)_