Introduction to hash-based proof systems by Diego Kingston | Devcon SEA

it's a huge pleasure to to be presenting this it will be kind of a speedrun because five minutes to explain this so that you understand is to few but um we'll try our best to get you excited about this so why are hash based proof systems important okay so they are used right now by many projects and they have helped developed performance CK VMS that make developing provable applications easier because now you have to just write ordinary code and something else is going to take the Gory details of uh generating the proof and all that so what are the properties that hash based proof systems offer first we can work over smaller fields which reduces a lot the overhead that we have in representing the variables then another Advantage is we don't need any kind of trusted setups uh there are like minimal security assumptions depending only on um hash functions and uh it's easier to generate recursive proofs because we don't need to do any kind of field emulation or elliptic curve operations which are uh very expensive operations to to perform okay so what are the main ingredients for hash BAS based proof systems first we need linear codes in general we are going to use read Solomon codes because there are efficient algorithms for um performing the the codification then we need a collision resistant hash function for example Ketch but you can use uh others such as posidon 2 and the idea is that we are going to commit to these um code words and then we need an arithmetization procedure for example an algebraic intermediate representation so the concrete choice of the linear code the hash function and the arithmetization will affect the performance and efficiency determining proof size whether it's easier to do recursion Pro time verifier time okay some examples of these proof systems are Starks with fry Circle Starks which have shown amazing performance being able to prove over um 500,000 hashes per second for posidon 2 liero breakdown vus that works over binary fields and can be an interesting option to build new ckvm and fr Venus which also works over binary Fields but has smaller proof sizes so how do we use for example Rich Solomon codes to build a polinomial commitment scheme which is the main ingredient of many of these proof systems so the idea is that at some point we what we do is we compile the program we want to prove to a set of polinomial equations that have to be fulfilled okay and everything boils down to uh showing that this polinomial has zeros over some set or it evaluates to some value at some point said okay and how we can commit to a polinomial what we can do is we choose some some values a domain and what we do is we evaluate that polinomial over that uh set D and that is what we call the read Solomon encoding typically we choose a nice domain and to show that we are not going to change those evaluations what we do is we build a Merkle tree to commit to those evaluations and one thing that we need to build this uh commitment schemes is to have a way of showing that we evaluated this polinomial correctly and so here the main ingredient is a theorem which is the remainder theorem that says that if a polinomial evaluates to uh given value at the point then uh the polinomial minus the value divided by x minus Z should be a polinomial okay and the idea is that we can commit to this polinomial or this function by evaluating over the domain and committing to the marle tree and we could show show that this is in fact a polinomial just by giving the co efficients but that wouldn't make proof short we want logarithmically short proofs so the idea is that we can use the fry proximity test to do that which has logarithmic size okay that is something you'd like to to look when you are trying to learn these proof systems and uh well here is a basic idea of fry but what you do basically is divide the polinomial between even and odd parts and then you do some random folding to reduce the degree of the polinomial by half this is the same trick you use when you perform the fft and uh here are the two phases of fry you have a commitment where you commit to the code words and then you let the verifier choose some positions where he wants to query and test whether you are cheating or not okay and the interesting thing is you get logarithmically sized proofs and the prover runs really really fast okay and here there are like some cool things you can do to have even faster things by leveraging meren primes but you have to move to a different construction which is circle Starks okay it's more or less the same as this but with some tricks uh well and thank you for listening to me happy to answer any question thank you Diego