[Music] [Applause] hi uh I will be presenting on the topic rash gkp and tradeoff my name is utak hasimoto and I'm gkp developer at INX in this presentation I will explain uh rash gkp which is a te uh technology uh from p uh it is excha technology from the perspective of client side validation used in plasma so first uh let's explain what client side validation is so client side validation was introduced by Dan Robinson's Isam research post titled plasma with client validation This was later defined uh Bic Bain uh plas uh plasma cache the basic
idea is to minimize the burden on base layer as much as possible and do what can be done on the client side the verification that utxo has not been double spend is down on client side not on the base layer and it is the send has responsibility uh to prove to the recipient that UD exr has not been dou spend recent State Technologies such as indax and GK coins are based on client side validation so to show that uh utxo has not been double spent we need to prove that utxo has not been included in
blocks before being spent if the blocks have passed since a udx was issued a direct method would require T exclusion proofs the amount of data for this exclusion proof uh increase rapidly and it quickly and manageable and so recash gkp solve this problem so what is recursive gkp ordinary gkp is a cryptographic tool to show that uh to show that uh the statement is true without repeating any information other than statement hold so for example uh let's take example fibon sequence so verifier can verify the 100 term of f sequence start with 28 without re
calculating the Fibonacci sequence so instead of using a gkp to prove statement about C sequence we can also prove that correctness of gkp that prove statement about fibon sequence in other words this means proving the correctness of gkp inside a gkp this is called aive gkp this gkp can be repeated any number of times and by the final verifier checking only the last gkp gkp the correctness of initial statement is verified recursively let's to client side validation utx Source are accompanied by a gkp that proving their history is correct when consuming a utxo and to
create uh new utxo we first need to verify that the all the gkp proof is correct and verify that uh all utxo has a sufficient amount to create the new utxo so recipient uh create a new gkp that proves two two point so this is a deive gkp so and we call this proof a balance proof balance proof is a recar proof every time a participant make a transfer the balance proof is updated and this chain of recur proof continu until the assets were withdrawn and there is another important application of recursive gkp in client
side validation the right client gkp in Balance proofs there are cases where we need to prove that TX included in plasma blocks for this we need to create a mark tree of plasma block hases also in cases like inax where plasma block verification isn't done on chain we need to determine whether each block is correct or incorrect inside gkp so let's call this gkp related to plasma blocks a right cant gkp this is a recash proof because it need to be updated every time a new plasma Brock is posted so next I will explain various
scheme for performing Rive gkp Rive gkp scheme can be broadly divided in accumulation scheme and wholy C gkps har and Nova and protar belong to accumulation scheme and reive stock and recash gross 16 are example of fully recursive gkp let me explain the uh accumulation scheme suppose we are given function f and uh initial value z z let's say that after applying F three times we get Z three to prove this we need to prove uh three statement true so F of z0 equals to Z1 and F of Z1 equals to Z2 and F of
Z2 equal to Z3 to prove this three statement in noral gkp we would need to create three gkp for each statement in in the accumulation scheme by introducing accumulator it become uh it is possible to accumulate statement into the accumulator so by verifying the final accumulator is correct it can be guaranteed that all statement are correct however this Aron is not sufficient it is also necessary to verify that process of updating the accumulator is correct when all verification passes including accumulator verifier and decider which verifies the final accumulator it can be guaranteed that all statement
are correct so in this way by using accumulators verification verification of statement can be transformed into the program of verification of accumulator however the number of accumulator verifier still need to be end times which is still inefficient so we include accumulator verifier of each step in the statement of next jkp and we F the accumulator verifier Itself by devising in this way only last accumulator verifier is needed so har and Har to uses inner product argument as a accumulator so next let's explain the folding scheme all statement can be written as constraint in in the
form of R1 CS here a B and C are matrices and C is a vector consisting of public input X and one which is represent a constant term of the constraint and W which is the private input that is witness relux R1 CS is a R1 CS that add exra scar U and er Vector e to the R1 CS Delux R1 CS can be used as an accumulator let's see this next so now suppose we have a relaxed R1 Cs and another R1 Cs and let's consider taking a random linear combination with two R1 CS
instances so let's call this random value low so we can create new Z by combining Z1 and Z2 by row and in this way by adding extra time U and E we can absorb the cross terms and result become also R1 CS relax R1 CS we call this operation foring so you using relax R1 CS as accumulator this becomes noas foring in This Way Nova realizes the accumulation scheme by explain ex expressing statement as R1 Cs and folding them into a relaxed R1 CS Nova's recy proof is extremely fast and running about 50 millisecond per
step for small circuit so as the latest result result on NOA to client side validation we have hyper NOA and cycle fold hyper NOA enable the foring multiple instances also cycle fold simplified previously complexed uh instantiation of Nova on cycle of eliptic cures these two achievement ment U made made Rashi proof of U Tre structure possible this arrows for example marging multiple utxo into a single utxo however there are also drawbacks when applying accumulation scheme to client side validation in accumulation schemes the nled property is only guaranteed in the final step this means that in
each step the verifier can uh can see the somewhat guess the witness the previous proofer used therefore the proof is not suitable for privacy payment purpose also when verifying accumulator the deci need to verify all type of State statements therefore if the recursive structure become too complex the decider become too large for example in client side validation ban proof need to absorb a right Cent proof to synchronize the latest plasma block or match Balan proofs into into one to receive funds in this case deci needs to verify four types of recursive structures in such situation
the deider becomes twoo cost so next let's look at uh fly reive gkp fly reive gkp verifies gkp completely at each step without using accumulators also it completely verifies zkp stock based prony for example has very good benchmarks it completes proof uh less than 500 milliseconds for nonk config and less than two seconds for ZK config on the other hand uh there is also research on performing a recursive gkp on uh gr 60 circuit this approach requires verifiers of operations on tic cup so this involves nonnative field arithmetic which is result a relatively long time
of about 200 seconds so in this presentation we'll take closer look at stock based recursive gkp stocks at um based on MAR 3 and read Solomon encoding the Boton neck inaside is a fft for leadon encoding and hash calculations of constructing Maru Tre on the other hand most computationally intensive part of verifier is a verification of hash calculations for verifying Market proof recursive stock doesn't use tic cup so nonnative field arithmetic is not necessary also while um most costly part is has calculation we can reduce this cost by using GK friendly hashes like uh poson
hash furthermore it is possible to further reduce the cost of poson hash verification by using custom gate or Ari specially for poson hash verification for example in prony 2 a custom B custom gate uh with 135 columns is used to verify poson has this custom gate allows to verify a POS on has in a single row enabling fast recash proofs however stock based proof size are very large ranging from 100 kilobyte to several megabyte this can be burden in places with uh limited communication resources also unlike accumulation schemes it completely verifies proof at each step
so the cost of verifying um gkp is larger compared to accumulation scheme so another problem is that U after Fiat shamia transformation the security of f is difficult to evaluate and in most cases we have to use the conjecture security level so this is the summary so recash gkp plays a crucial role in client side validation and accumulation scheme and recash stocks are promising candidate for recash proof in client side validation however each has it's to off so accumulation scheme can execute a recash proof extreme extremely quickly taking about 50 millisecond however there is no
gness at each step additionally if the recur structure to complex the cost of deider can be become become too costly on the other hand recur stock fully verify gkp at each step so they don't require deci and can be guaranteed gkess at each step however the proof size um might be large and speed is slower than the uh throw and accumulation scheme nevertheless by utilizing custom Gates such as poson hash recursion can be achieved at practical speed yes that's all thank you [Applause]
