Transaction Hash:
Block:
11923521 at Feb-25-2021 01:59:38 AM +UTC
Transaction Fee:
0.023245288 ETH
$58.68
Gas Used:
187,462 Gas / 124 Gwei
Account State Difference:
| Address | Before | After | State Difference | ||
|---|---|---|---|---|---|
|
0x1aD91ee0...dA6B45836
Miner
| (Hiveon Pool) | 3,122.166526703157301855 Eth | 3,122.189771991157301855 Eth | 0.023245288 | |
| 0x8129b737...D0303390a | (dYdX: L2 On-Chain Operator) |
13.200107888096275409 Eth
Nonce: 239
|
13.176862600096275409 Eth
Nonce: 240
| 0.023245288 | |
| 0xf6b83Cca...4FBc5E1B1 | (dydx: FRI Statement) |
Execution Trace
FriStatementContract.verifyFRI( proof=[1224591128107481975789301821256457916167302205157674603398335887874921391939, 170808140175515598367475688007416741465595555154848451959179048674153401907, 23766865911686798781166632678315045852363612327885763873271257325839782124, 1420922568140881015437827248052969213149030084696042875128905905414199364246, 1734768272557517328328470851162796297110794788154911213864836813725572843010, 2229813202091906363565980941072823444077268201324851350570864019753202545853, 893962688670919496234538514884372960777143102302233878171451717900332396354, 498058535161058485846799535009143641195303461875187307049540030653892762370, 3538945592413117019254890594735603853766492286367791238964644896996632314156, 440376840661457647082267448199536974916932165255191382156459073479143671885, 3114581173170332302164163111390352268660351984972694480221467153761106009878, 1751610304243849061711193196137886626248372110313239963098888741850399085119, 3015997851698824587152977089529565051194044922822456107449761492712470932519, 3026160624053729090967140089543739176257419639534400572681936575034546754791, 659270576568862155331895154773883167074508597511233653592953924632481176000, 115269432935360635855443654086812552905581348886756766681103929892149976980, 2369569919884146924282171772133849438548507925125314521898329108859470883351, 1829628960243686713227643100134075288891287179456636141536403418813156791293, 645208418204279148839374641864871532234985943169042127556908421240025402505, 3575974893824683612984889882621345187840792872762765686119172032779468819609, 1736348338060155389769802012552547401748697307732050844538642465960113865961, 2025371137841451757651139056723755507017881373326765926587046726013216775619, 3314033129120364225202806177986789456220458561081017004860568294584054362066, 767980442570170427692917442710219792330467714702580964904027224400223570300, 2087185795847526600894502963478700007646461318312201954099515359436723094339, 89381391907512381044420901554209212954328360382002303643989525990653211807, 1405468884081177109260672786487028379230151776919703799756286055782349040884, 1109130768748531929214660370081607805770857955123991755587474988892828891921, 3548790816876680748062767443511174971478824572933840021299434086565365159092, 2599737664094293945397006334008259906920978472143855568495790055947584100749, 1315045608285832218889149906972716265538967018133643755627269658211767009177, 955326753242314694951773807505221840246844201587184254875470630321179987956, 1116608091978931671552005225740765894068260532015969519074001195012885609702, 3220336065423770424761839162746345722644906587152391679196393662952242546977, 324479859894828424283706635153145318266754172385445035599043059959598283908, 1760883224527251857891260333925561109424405971238658553711439494760321776374, 3248061272508846267291968412496828735997072079409967063407046101914753704657, 1082956158252129906745818241536126864570303670002079136820047154126733873958, 1644503648868344092932585168141659946866994970857616693900101582839172803287, 3108744915128113059305481699094820104724406136215295456609788944286225841366, 1049857866981120565891027967152581063728955560955060778995837344759874618742, 3496731965002438871080241975934041216414482498035145897928887861560258101726, 1948782644476894214029766815549692267851101459310672477486393919229882755134, 695370782081608064607882506648581032958199767627182745921020290035893906318, 39669215140871823239267335091569309844950905570391349140952385825746617901, 953733589575506987028471611233508231537509057917072732864940041507286117175, 3189085578938852538727377313194114168541067303177967855611114091145318421380, 191328580973483573481107595483623375470106720523566638987371073722429463890, 2332696678490713177202092940264519339454096007397045625443396323661771810146, 2280818432512252951445636325794888762862546238605775027781193078589907317896, 2934933256435780593354733001415562031440817286822732881468383888455946737704, 1360999268188904315044685784936736935564476528029965275672883168544734573236, 1883623450402661009346542963511159815689405563114234326300576307120555287827, 504939991204870641155047770727041931821986961545031811759132319873010481005, 896555278171766408362916105464842773209114761313673122021104358034931172205, 1621642666356644520815492018531592093264551517284921664184865162631401651661, 985273661115317789039220094167616890684989679999106186638672934103311823122, 3485299790867468763820719828784592272820002057266736699677887003097284739421, 2314482765298456896887948443185499825606431971755219720473701371279891102179, 2054740734932684672255058858253023915767539632445765660780919224816771535133, 1761528545365386178426357692242892925199692409061951393996064809020516907366, 527683128569809436360160259267215224365739619473144897537770246700535987397, 3530590167877992096748197144177711446525888722341903142393832375859878327630, 1755642554485409186337843885035392110339331345036917368659967067739147975460, 2078929037562266376318199489991840940916700365838922611178123253845006570744, 1078638378977296324693199825142996830048857333238569533020880197677199248364, 638549387895427952295696027246840141776926230707591412115453975385384469558, 1490879824163195639314684104940690627744695207185243483237876031525855525797, 1260917427095352874666648803481419574624220831678743219396416027586505972774, 2902178883618650254972060028349320477439386203574941700405197859871401326051, 45925422772950613654062723226858909829610800201009522119124372420555895209984, 4343884106871263684751575198351782910497119742579104863166707460425990012928, 51565658375034294498358274902461226090438282671820337766197035766452838203392, 9509988284801999460683566847946321392504856007864923070732887417519534505984, 13743788731633866223616078938969355421889529302154257060647933214136538759168, 91277853827637663302264540927851031075964373163614477569548752756788944699392, 104325631163949818036468247608721923711582790261233109860896328979730042716160, 104362723132423578508919115997232030747798257557722665684361147510296766578688, 100695600604035352040113930728850923121890421158356390122548032323744281133056, 104803082412639668797786611138359405039829024939448887228328230004843113086976, 2983505331390005999459169017666298440277012854026177514737137367265012875264, 74038736468258580343708931570503296147221608868543485946407999026697871556608, 88074912473498872300168985367848440607665152991484790690041709685986102870016, 84432556262910586262244984699541585516161984283904215326412213994421481373696, 46013073627422879011944388529297296093966611700792290634010865226654972641280, 104483125115895625613364917696692837689209915775978076778138267512421723668480, 42361158130767286963784933904567409695994241640230445953236886550882608480256, 74478523489539638673513766038455561925152866006021700889719355499828987559936, 67699911431466129502765087830896231673354974865370323523890368042991232221184, 37753347564452752130646973068413326482432307350992812856973766289842310742016, 25747763895222232727871525674395355753509929213868996381029880878823444054016, 3255162316125166484933318026878884306618630238497161142617235525887204524032, 33182339999424599702736597046324510638660155428281121992453112435223132372992, 107446515359042190750199016060741046024541344055254631460715163909651571933184, 113863625310274602830911696715689433569271648066750658535778041513320061599744, 23106509075053526032403991443686014604189140925345067025043667295295248531456, 109642763222065439751207371270302133163312854626579751176251041255640348491776, 74631058182208342613738860703903617925458903797825509849403657393089474985984, 70812063514070579489640616774863897243485115017471684794796112321545645326336, 37219192812629671944437536884098149243838370023100223433713230788365213761536, 19201111907495348384575812509240731713518571790464745968571330321993263218688, 19881408901021437458909199206229315169949014841174739000966609073163382816768, 36204613720244995590109639455120204992588618342516749151563103810765637812224, 47046394822709218409390469273172014897735352355971848272781365049395662290944, 25007262037420119756854331217561595043924732115056794264700094628685949173760, 87094871538024839711570686163628024031399210075510240289343652119833292570624, 5524987524040162774591584576299807783264042140167125723727440341736504688640, 72608767633682971358553403277196456489791960124778615652455369210372407951360, 82626677881467369532234356131845522758656239929614512368732736689414952976384, 21497250766141089931223749684659365949964140132714134422220014795221003927552, 4687122352724602857610046648772671264384354092855996081811272280091840741376, 56504924863165507109485259571270515232891581070072213301608348211363889283072, 110326498481309539114984125701777166986645372103881825493522858687936482770944, 24567895091512408863372093048387324934109995604866045749339417114037691875328, 7166823208567063733669472493324526136535917153202626745606135071154638946304, 14661028646999821030745884478621332115470250893982866458545724091381980332032, 8840128203704046582041210179900365168867977620988181664382472358938047152128, 56241965160848575921768881147464882176292220345811279025410623054196013793280, 7766838253085307534679144090831859885035501801188419102201292718847758958592, 17368177923648995518617414805761768721709286041190303128830292860015801794560, 23041355071122555090268821487007407766876305889631357926840027707847036895232, 18169292114043432696829091317519676908021431433021472847239347947184928587776, 92431994681477626409368229636702363726917596400854343577879517584090002882560, 25537767518840227696943758246379160680556228102811257908690940899886163296256, 2231740632370113898102689356070499744337764694443059478769098502796098928640, 64636304963112575252546468014197201951410736387497072703056499792092529164288, 109630773400222105380584123341747181814514055399466626498732642645925752209408, 17348788576041529887068879115605276887391043000507457130340677629534831378432, 87970415047951950524453398876813845141426649227859764642475319624406990323712, 75466375727493963236429951871256339687117911551005969304659398947155682000896, 2409915850816773171099507466735378168735615679280893062504387842369038319616, 56287041339488021617204201071126522314916949769133184337263884274016668614656, 72034031370007773172546981600846922503741452099760202381039056608101169889280, 97851054538183671332363156268869144797930079053194766250782105826441379708928, 77111201073205497935059253628923390255146128658264714293077376676414604967936, 51042218100289465908064348559174932927448637832946648777978570785996570361856, 4719069677476303874345774643302171702068910585436347467625664840057906790400, 108233160268645433972725906523709905112382663606216960097611491487698250629120, 26217306021177273621903310666101447696576081549677885620444865642335500763136, 23702488685439703626596281737639895966649606302925821142583652925606388039680, 12742673467270170204987971422433300653113638974921331219035493227796562444288, 62591446801522893483675680003120469850481116766176282735272564397862568329216, 44476248402838238642681818549517977098417099433052240539688379105321833988096, 49490050477205202948041551473301470923838869045389608782113325339284030357504, 103891779107490482642489265181502539128152042069504316314960674905622478585856, 86402676936246484452502204295517883095931640294988278797532636111252418985984, 29953456891013181753445483785731013200455862623201470253095612283401088794624, 4671849720596717032963577789385019841067173931221403871325731670779634909184, 73992125559056890854269869135746452300887977181703139284600410848926244012032, 45193018794980715142997118838527558073739772296978817568164964804014462992384, 8303667631412549550638454622831291838924608787698686257954012517274040139776, 85840808910818120714999250066325697199757659790036794069735324807657351544832, 106344845364713750210750697395604554797998615022788481218871780299508348354560, 51326971664949217374865701969499022302608032412465017929148322477338318077952], friQueue=[84204, 2060340691386667243128944221439418574635274849080966476775307437698751998901, 893178173056442169025727489288202473800064176936221123358626935762705173782, 88500, 3324224704865187382566843143123999124034271512961834095528787520197266945989, 656648278423722000573557487270672948944795700136248107988500812663597223808, 89230, 470581858176021270473668278609053672092409140436650345717915157728834818964, 109908101836122249823516400610422880268814033587786481590629600502688896228, 99233, 924189258964959345790379091114514041052943313183718103109033863801996148808, 1169876841056089380417257329815900131588119448195887133923036133059028768833, 111224, 3052774854052646770062927836590376911446772442815860774152614866964841062408, 2066473703825139803491367970309064387039397932606733218627411906923508650904, 116187, 102874306354502756859785646788485768743035548441161053696641741156880823575, 42416730130770635722221860618946084400541055603924685347210546559751025102, 116828, 2070345710032343338367284183488850737989287072578319640678458639132100471689, 659244684112643850093633813695139222694076730758652314787806496275754085197, 121634, 1901840562443491943782251312121206624226060617030369416224738148993998656581, 2787955993453304440511473919613350957143131582558044070075494830314645582518, 130844, 1678248045732835320641024825549022711445425689547452057737293172828390717997, 284000139190436510646886215183424412736885743868115298792997481668427136387, 131037, 2688071783749882282322159813897362177439721036634176151520184896199899234598, 262815560673630111858292370538159392762612131976628942135152013441593243934, 0], evaluationPoint=3578413321680931070441135319312180344715207618754288414829534852495776331519, friStepSize=3, expectedRoot=26442873727315226678641497921213390864535490949218324765635849190784536412160 )
-
Null: 0x000...005.00000000( )
{"FactRegistry.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nimport \"IQueryableFactRegistry.sol\";\n\ncontract FactRegistry is IQueryableFactRegistry {\n // Mapping: fact hash -\u003e true.\n mapping (bytes32 =\u003e bool) private verifiedFact;\n\n // Indicates whether the Fact Registry has at least one fact registered.\n bool anyFactRegistered;\n\n /*\n Checks if a fact has been verified.\n */\n function isValid(bytes32 fact)\n external view override\n returns(bool)\n {\n return _factCheck(fact);\n }\n\n\n /*\n This is an internal method to check if the fact is already registered.\n In current implementation of FactRegistry it\u0027s identical to isValid().\n But the check is against the local fact registry,\n So for a derived referral fact registry, it\u0027s not the same.\n */\n function _factCheck(bytes32 fact)\n internal view\n returns(bool)\n {\n return verifiedFact[fact];\n }\n\n function registerFact(\n bytes32 factHash\n )\n internal\n {\n // This function stores the fact hash in the mapping.\n verifiedFact[factHash] = true;\n\n // Mark first time off.\n if (!anyFactRegistered) {\n anyFactRegistered = true;\n }\n }\n\n /*\n Indicates whether at least one fact was registered.\n */\n function hasRegisteredFact()\n external view override\n returns(bool)\n {\n return anyFactRegistered;\n }\n\n}\n"},"FriLayer.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nimport \"MerkleVerifier.sol\";\nimport \"PrimeFieldElement0.sol\";\n\n/*\n The main component of FRI is the FRI step which takes\n the i-th layer evaluations on a coset c*\u003cg\u003e and produces a single evaluation in layer i+1.\n\n To this end we have a friCtx that holds the following data:\n evaluations: holds the evaluations on the coset we are currently working on.\n group: holds the group \u003cg\u003e in bit reversed order.\n halfInvGroup: holds the group \u003cg^-1\u003e/\u003c-1\u003e in bit reversed order.\n (We only need half of the inverse group)\n\n Note that due to the bit reversed order, a prefix of size 2^k of either group\n or halfInvGroup has the same structure (but for a smaller group).\n*/\ncontract FriLayer is MerkleVerifier, PrimeFieldElement0 {\n event LogGas(string name, uint256 val);\n\n uint256 constant internal FRI_MAX_FRI_STEP = 4;\n uint256 constant internal MAX_COSET_SIZE = 2**FRI_MAX_FRI_STEP;\n // Generator of the group of size MAX_COSET_SIZE: GENERATOR_VAL**((PRIME - 1)/MAX_COSET_SIZE).\n uint256 constant internal FRI_GROUP_GEN =\n 0x5ec467b88826aba4537602d514425f3b0bdf467bbf302458337c45f6021e539;\n\n uint256 constant internal FRI_GROUP_SIZE = 0x20 * MAX_COSET_SIZE;\n uint256 constant internal FRI_CTX_TO_COSET_EVALUATIONS_OFFSET = 0;\n uint256 constant internal FRI_CTX_TO_FRI_GROUP_OFFSET = FRI_GROUP_SIZE;\n uint256 constant internal FRI_CTX_TO_FRI_HALF_INV_GROUP_OFFSET =\n FRI_CTX_TO_FRI_GROUP_OFFSET + FRI_GROUP_SIZE;\n\n uint256 constant internal FRI_CTX_SIZE =\n FRI_CTX_TO_FRI_HALF_INV_GROUP_OFFSET + (FRI_GROUP_SIZE / 2);\n\n function nextLayerElementFromTwoPreviousLayerElements(\n uint256 fX, uint256 fMinusX, uint256 evalPoint, uint256 xInv)\n internal pure\n returns (uint256 res)\n {\n // Folding formula:\n // f(x) = g(x^2) + xh(x^2)\n // f(-x) = g((-x)^2) - xh((-x)^2) = g(x^2) - xh(x^2)\n // =\u003e\n // 2g(x^2) = f(x) + f(-x)\n // 2h(x^2) = (f(x) - f(-x))/x\n // =\u003e The 2*interpolation at evalPoint is:\n // 2*(g(x^2) + evalPoint*h(x^2)) = f(x) + f(-x) + evalPoint*(f(x) - f(-x))*xInv.\n //\n // Note that multiplying by 2 doesn\u0027t affect the degree,\n // so we can just agree to do that on both the prover and verifier.\n assembly {\n // PRIME is PrimeFieldElement0.K_MODULUS.\n let PRIME := 0x800000000000011000000000000000000000000000000000000000000000001\n // Note that whenever we call add(), the result is always less than 2*PRIME,\n // so there are no overflows.\n res := addmod(add(fX, fMinusX),\n mulmod(mulmod(evalPoint, xInv, PRIME),\n add(fX, /*-fMinusX*/sub(PRIME, fMinusX)), PRIME), PRIME)\n }\n }\n\n /*\n Reads 4 elements, and applies 2 + 1 FRI transformations to obtain a single element.\n\n FRI layer n: f0 f1 f2 f3\n ----------------------------------------- \\ / -- \\ / -----------\n FRI layer n+1: f0 f2\n -------------------------------------------- \\ ---/ -------------\n FRI layer n+2: f0\n\n The basic FRI transformation is described in nextLayerElementFromTwoPreviousLayerElements().\n */\n function do2FriSteps(\n uint256 friHalfInvGroupPtr, uint256 evaluationsOnCosetPtr, uint256 cosetOffset_,\n uint256 friEvalPoint)\n internal pure returns (uint256 nextLayerValue, uint256 nextXInv) {\n assembly {\n let PRIME := 0x800000000000011000000000000000000000000000000000000000000000001\n let friEvalPointDivByX := mulmod(friEvalPoint, cosetOffset_, PRIME)\n\n let f0 := mload(evaluationsOnCosetPtr)\n {\n let f1 := mload(add(evaluationsOnCosetPtr, 0x20))\n\n // f0 \u003c 3P ( = 1 + 1 + 1).\n f0 := add(add(f0, f1),\n mulmod(friEvalPointDivByX,\n add(f0, /*-fMinusX*/sub(PRIME, f1)),\n PRIME))\n }\n\n let f2 := mload(add(evaluationsOnCosetPtr, 0x40))\n {\n let f3 := mload(add(evaluationsOnCosetPtr, 0x60))\n f2 := addmod(add(f2, f3),\n mulmod(add(f2, /*-fMinusX*/sub(PRIME, f3)),\n mulmod(mload(add(friHalfInvGroupPtr, 0x20)),\n friEvalPointDivByX,\n PRIME),\n PRIME),\n PRIME)\n }\n\n {\n let newXInv := mulmod(cosetOffset_, cosetOffset_, PRIME)\n nextXInv := mulmod(newXInv, newXInv, PRIME)\n }\n\n // f0 + f2 \u003c 4P ( = 3 + 1).\n nextLayerValue := addmod(add(f0, f2),\n mulmod(mulmod(friEvalPointDivByX, friEvalPointDivByX, PRIME),\n add(f0, /*-fMinusX*/sub(PRIME, f2)),\n PRIME),\n PRIME)\n }\n }\n\n /*\n Reads 8 elements, and applies 4 + 2 + 1 FRI transformation to obtain a single element.\n\n See do2FriSteps for more detailed explanation.\n */\n function do3FriSteps(\n uint256 friHalfInvGroupPtr, uint256 evaluationsOnCosetPtr, uint256 cosetOffset_,\n uint256 friEvalPoint)\n internal pure returns (uint256 nextLayerValue, uint256 nextXInv) {\n assembly {\n let PRIME := 0x800000000000011000000000000000000000000000000000000000000000001\n let MPRIME := 0x8000000000000110000000000000000000000000000000000000000000000010\n let f0 := mload(evaluationsOnCosetPtr)\n\n let friEvalPointDivByX := mulmod(friEvalPoint, cosetOffset_, PRIME)\n let friEvalPointDivByXSquared := mulmod(friEvalPointDivByX, friEvalPointDivByX, PRIME)\n let imaginaryUnit := mload(add(friHalfInvGroupPtr, 0x20))\n\n {\n let f1 := mload(add(evaluationsOnCosetPtr, 0x20))\n\n // f0 \u003c 3P ( = 1 + 1 + 1).\n f0 := add(add(f0, f1),\n mulmod(friEvalPointDivByX,\n add(f0, /*-fMinusX*/sub(PRIME, f1)),\n PRIME))\n }\n {\n let f2 := mload(add(evaluationsOnCosetPtr, 0x40))\n {\n let f3 := mload(add(evaluationsOnCosetPtr, 0x60))\n\n // f2 \u003c 3P ( = 1 + 1 + 1).\n f2 := add(add(f2, f3),\n mulmod(add(f2, /*-fMinusX*/sub(PRIME, f3)),\n mulmod(friEvalPointDivByX, imaginaryUnit, PRIME),\n PRIME))\n }\n\n // f0 \u003c 7P ( = 3 + 3 + 1).\n f0 := add(add(f0, f2),\n mulmod(friEvalPointDivByXSquared,\n add(f0, /*-fMinusX*/sub(MPRIME, f2)),\n PRIME))\n }\n {\n let f4 := mload(add(evaluationsOnCosetPtr, 0x80))\n {\n let friEvalPointDivByX2 := mulmod(friEvalPointDivByX,\n mload(add(friHalfInvGroupPtr, 0x40)), PRIME)\n {\n let f5 := mload(add(evaluationsOnCosetPtr, 0xa0))\n\n // f4 \u003c 3P ( = 1 + 1 + 1).\n f4 := add(add(f4, f5),\n mulmod(friEvalPointDivByX2,\n add(f4, /*-fMinusX*/sub(PRIME, f5)),\n PRIME))\n }\n\n let f6 := mload(add(evaluationsOnCosetPtr, 0xc0))\n {\n let f7 := mload(add(evaluationsOnCosetPtr, 0xe0))\n\n // f6 \u003c 3P ( = 1 + 1 + 1).\n f6 := add(add(f6, f7),\n mulmod(add(f6, /*-fMinusX*/sub(PRIME, f7)),\n // friEvalPointDivByX2 * imaginaryUnit ==\n // friEvalPointDivByX * mload(add(friHalfInvGroupPtr, 0x60)).\n mulmod(friEvalPointDivByX2, imaginaryUnit, PRIME),\n PRIME))\n }\n\n // f4 \u003c 7P ( = 3 + 3 + 1).\n f4 := add(add(f4, f6),\n mulmod(mulmod(friEvalPointDivByX2, friEvalPointDivByX2, PRIME),\n add(f4, /*-fMinusX*/sub(MPRIME, f6)),\n PRIME))\n }\n\n // f0, f4 \u003c 7P -\u003e f0 + f4 \u003c 14P \u0026\u0026 9P \u003c f0 + (MPRIME - f4) \u003c 23P.\n nextLayerValue :=\n addmod(add(f0, f4),\n mulmod(mulmod(friEvalPointDivByXSquared, friEvalPointDivByXSquared, PRIME),\n add(f0, /*-fMinusX*/sub(MPRIME, f4)),\n PRIME),\n PRIME)\n }\n\n {\n let xInv2 := mulmod(cosetOffset_, cosetOffset_, PRIME)\n let xInv4 := mulmod(xInv2, xInv2, PRIME)\n nextXInv := mulmod(xInv4, xInv4, PRIME)\n }\n\n\n }\n }\n\n /*\n This function reads 16 elements, and applies 8 + 4 + 2 + 1 fri transformation\n to obtain a single element.\n\n See do2FriSteps for more detailed explanation.\n */\n function do4FriSteps(\n uint256 friHalfInvGroupPtr, uint256 evaluationsOnCosetPtr, uint256 cosetOffset_,\n uint256 friEvalPoint)\n internal pure returns (uint256 nextLayerValue, uint256 nextXInv) {\n assembly {\n let friEvalPointDivByXTessed\n let PRIME := 0x800000000000011000000000000000000000000000000000000000000000001\n let MPRIME := 0x8000000000000110000000000000000000000000000000000000000000000010\n let f0 := mload(evaluationsOnCosetPtr)\n\n let friEvalPointDivByX := mulmod(friEvalPoint, cosetOffset_, PRIME)\n let imaginaryUnit := mload(add(friHalfInvGroupPtr, 0x20))\n\n {\n let f1 := mload(add(evaluationsOnCosetPtr, 0x20))\n\n // f0 \u003c 3P ( = 1 + 1 + 1).\n f0 := add(add(f0, f1),\n mulmod(friEvalPointDivByX,\n add(f0, /*-fMinusX*/sub(PRIME, f1)),\n PRIME))\n }\n {\n let f2 := mload(add(evaluationsOnCosetPtr, 0x40))\n {\n let f3 := mload(add(evaluationsOnCosetPtr, 0x60))\n\n // f2 \u003c 3P ( = 1 + 1 + 1).\n f2 := add(add(f2, f3),\n mulmod(add(f2, /*-fMinusX*/sub(PRIME, f3)),\n mulmod(friEvalPointDivByX, imaginaryUnit, PRIME),\n PRIME))\n }\n {\n let friEvalPointDivByXSquared := mulmod(friEvalPointDivByX, friEvalPointDivByX, PRIME)\n friEvalPointDivByXTessed := mulmod(friEvalPointDivByXSquared, friEvalPointDivByXSquared, PRIME)\n\n // f0 \u003c 7P ( = 3 + 3 + 1).\n f0 := add(add(f0, f2),\n mulmod(friEvalPointDivByXSquared,\n add(f0, /*-fMinusX*/sub(MPRIME, f2)),\n PRIME))\n }\n }\n {\n let f4 := mload(add(evaluationsOnCosetPtr, 0x80))\n {\n let friEvalPointDivByX2 := mulmod(friEvalPointDivByX,\n mload(add(friHalfInvGroupPtr, 0x40)), PRIME)\n {\n let f5 := mload(add(evaluationsOnCosetPtr, 0xa0))\n\n // f4 \u003c 3P ( = 1 + 1 + 1).\n f4 := add(add(f4, f5),\n mulmod(friEvalPointDivByX2,\n add(f4, /*-fMinusX*/sub(PRIME, f5)),\n PRIME))\n }\n\n let f6 := mload(add(evaluationsOnCosetPtr, 0xc0))\n {\n let f7 := mload(add(evaluationsOnCosetPtr, 0xe0))\n\n // f6 \u003c 3P ( = 1 + 1 + 1).\n f6 := add(add(f6, f7),\n mulmod(add(f6, /*-fMinusX*/sub(PRIME, f7)),\n // friEvalPointDivByX2 * imaginaryUnit ==\n // friEvalPointDivByX * mload(add(friHalfInvGroupPtr, 0x60)).\n mulmod(friEvalPointDivByX2, imaginaryUnit, PRIME),\n PRIME))\n }\n\n // f4 \u003c 7P ( = 3 + 3 + 1).\n f4 := add(add(f4, f6),\n mulmod(mulmod(friEvalPointDivByX2, friEvalPointDivByX2, PRIME),\n add(f4, /*-fMinusX*/sub(MPRIME, f6)),\n PRIME))\n }\n\n // f0 \u003c 15P ( = 7 + 7 + 1).\n f0 := add(add(f0, f4),\n mulmod(friEvalPointDivByXTessed,\n add(f0, /*-fMinusX*/sub(MPRIME, f4)),\n PRIME))\n }\n {\n let f8 := mload(add(evaluationsOnCosetPtr, 0x100))\n {\n let friEvalPointDivByX4 := mulmod(friEvalPointDivByX,\n mload(add(friHalfInvGroupPtr, 0x80)), PRIME)\n {\n let f9 := mload(add(evaluationsOnCosetPtr, 0x120))\n\n // f8 \u003c 3P ( = 1 + 1 + 1).\n f8 := add(add(f8, f9),\n mulmod(friEvalPointDivByX4,\n add(f8, /*-fMinusX*/sub(PRIME, f9)),\n PRIME))\n }\n\n let f10 := mload(add(evaluationsOnCosetPtr, 0x140))\n {\n let f11 := mload(add(evaluationsOnCosetPtr, 0x160))\n // f10 \u003c 3P ( = 1 + 1 + 1).\n f10 := add(add(f10, f11),\n mulmod(add(f10, /*-fMinusX*/sub(PRIME, f11)),\n // friEvalPointDivByX4 * imaginaryUnit ==\n // friEvalPointDivByX * mload(add(friHalfInvGroupPtr, 0xa0)).\n mulmod(friEvalPointDivByX4, imaginaryUnit, PRIME),\n PRIME))\n }\n\n // f8 \u003c 7P ( = 3 + 3 + 1).\n f8 := add(add(f8, f10),\n mulmod(mulmod(friEvalPointDivByX4, friEvalPointDivByX4, PRIME),\n add(f8, /*-fMinusX*/sub(MPRIME, f10)),\n PRIME))\n }\n {\n let f12 := mload(add(evaluationsOnCosetPtr, 0x180))\n {\n let friEvalPointDivByX6 := mulmod(friEvalPointDivByX,\n mload(add(friHalfInvGroupPtr, 0xc0)), PRIME)\n {\n let f13 := mload(add(evaluationsOnCosetPtr, 0x1a0))\n\n // f12 \u003c 3P ( = 1 + 1 + 1).\n f12 := add(add(f12, f13),\n mulmod(friEvalPointDivByX6,\n add(f12, /*-fMinusX*/sub(PRIME, f13)),\n PRIME))\n }\n\n let f14 := mload(add(evaluationsOnCosetPtr, 0x1c0))\n {\n let f15 := mload(add(evaluationsOnCosetPtr, 0x1e0))\n\n // f14 \u003c 3P ( = 1 + 1 + 1).\n f14 := add(add(f14, f15),\n mulmod(add(f14, /*-fMinusX*/sub(PRIME, f15)),\n // friEvalPointDivByX6 * imaginaryUnit ==\n // friEvalPointDivByX * mload(add(friHalfInvGroupPtr, 0xe0)).\n mulmod(friEvalPointDivByX6, imaginaryUnit, PRIME),\n PRIME))\n }\n\n // f12 \u003c 7P ( = 3 + 3 + 1).\n f12 := add(add(f12, f14),\n mulmod(mulmod(friEvalPointDivByX6, friEvalPointDivByX6, PRIME),\n add(f12, /*-fMinusX*/sub(MPRIME, f14)),\n PRIME))\n }\n\n // f8 \u003c 15P ( = 7 + 7 + 1).\n f8 := add(add(f8, f12),\n mulmod(mulmod(friEvalPointDivByXTessed, imaginaryUnit, PRIME),\n add(f8, /*-fMinusX*/sub(MPRIME, f12)),\n PRIME))\n }\n\n // f0, f8 \u003c 15P -\u003e f0 + f8 \u003c 30P \u0026\u0026 16P \u003c f0 + (MPRIME - f8) \u003c 31P.\n nextLayerValue :=\n addmod(add(f0, f8),\n mulmod(mulmod(friEvalPointDivByXTessed, friEvalPointDivByXTessed, PRIME),\n add(f0, /*-fMinusX*/sub(MPRIME, f8)),\n PRIME),\n PRIME)\n }\n\n {\n let xInv2 := mulmod(cosetOffset_, cosetOffset_, PRIME)\n let xInv4 := mulmod(xInv2, xInv2, PRIME)\n let xInv8 := mulmod(xInv4, xInv4, PRIME)\n nextXInv := mulmod(xInv8, xInv8, PRIME)\n }\n }\n }\n\n /*\n Gathers the \"cosetSize\" elements that belong to the same coset\n as the item at the top of the FRI queue and stores them in ctx[MM_FRI_STEP_VALUES:].\n\n Returns\n friQueueHead - friQueueHead_ + 0x60 * (# elements that were taken from the queue).\n cosetIdx - the start index of the coset that was gathered.\n cosetOffset_ - the xInv field element that corresponds to cosetIdx.\n */\n function gatherCosetInputs(\n uint256 channelPtr, uint256 friCtx, uint256 friQueueHead_, uint256 cosetSize)\n internal pure returns (uint256 friQueueHead, uint256 cosetIdx, uint256 cosetOffset_) {\n\n uint256 evaluationsOnCosetPtr = friCtx + FRI_CTX_TO_COSET_EVALUATIONS_OFFSET;\n uint256 friGroupPtr = friCtx + FRI_CTX_TO_FRI_GROUP_OFFSET;\n\n friQueueHead = friQueueHead_;\n assembly {\n let queueItemIdx := mload(friQueueHead)\n // The coset index is represented by the most significant bits of the queue item index.\n cosetIdx := and(queueItemIdx, not(sub(cosetSize, 1)))\n let nextCosetIdx := add(cosetIdx, cosetSize)\n let PRIME := 0x800000000000011000000000000000000000000000000000000000000000001\n\n // Get the algebraic coset offset:\n // I.e. given c*g^(-k) compute c, where\n // g is the generator of the coset group.\n // k is bitReverse(offsetWithinCoset, log2(cosetSize)).\n //\n // To do this we multiply the algebraic coset offset at the top of the queue (c*g^(-k))\n // by the group element that corresponds to the index inside the coset (g^k).\n cosetOffset_ := mulmod(\n /*(c*g^(-k)*/ mload(add(friQueueHead, 0x40)),\n /*(g^k)*/ mload(add(friGroupPtr,\n mul(/*offsetWithinCoset*/sub(queueItemIdx, cosetIdx),\n 0x20))),\n PRIME)\n\n let proofPtr := mload(channelPtr)\n\n for { let index := cosetIdx } lt(index, nextCosetIdx) { index := add(index, 1) } {\n // Inline channel operation:\n // Assume we are going to read the next element from the proof.\n // If this is not the case add(proofPtr, 0x20) will be reverted.\n let fieldElementPtr := proofPtr\n proofPtr := add(proofPtr, 0x20)\n\n // Load the next index from the queue and check if it is our sibling.\n if eq(index, queueItemIdx) {\n // Take element from the queue rather than from the proof\n // and convert it back to Montgomery form for Merkle verification.\n fieldElementPtr := add(friQueueHead, 0x20)\n\n // Revert the read from proof.\n proofPtr := sub(proofPtr, 0x20)\n\n // Reading the next index here is safe due to the\n // delimiter after the queries.\n friQueueHead := add(friQueueHead, 0x60)\n queueItemIdx := mload(friQueueHead)\n }\n\n // Note that we apply the modulo operation to convert the field elements we read\n // from the proof to canonical representation (in the range [0, PRIME - 1]).\n mstore(evaluationsOnCosetPtr, mod(mload(fieldElementPtr), PRIME))\n evaluationsOnCosetPtr := add(evaluationsOnCosetPtr, 0x20)\n }\n\n mstore(channelPtr, proofPtr)\n }\n }\n\n /*\n Returns the bit reversal of num assuming it has the given number of bits.\n For example, if we have numberOfBits = 6 and num = (0b)1101 == (0b)001101,\n the function will return (0b)101100.\n */\n function bitReverse(uint256 num, uint256 numberOfBits)\n internal pure\n returns(uint256 numReversed)\n {\n assert((numberOfBits == 256) || (num \u003c 2 ** numberOfBits));\n uint256 n = num;\n uint256 r = 0;\n for (uint256 k = 0; k \u003c numberOfBits; k++) {\n r = (r * 2) | (n % 2);\n n = n / 2;\n }\n return r;\n }\n\n /*\n Initializes the FRI group and half inv group in the FRI context.\n */\n function initFriGroups(uint256 friCtx) internal view {\n uint256 friGroupPtr = friCtx + FRI_CTX_TO_FRI_GROUP_OFFSET;\n uint256 friHalfInvGroupPtr = friCtx + FRI_CTX_TO_FRI_HALF_INV_GROUP_OFFSET;\n\n // FRI_GROUP_GEN is the coset generator.\n // Raising it to the (MAX_COSET_SIZE - 1) power gives us the inverse.\n uint256 genFriGroup = FRI_GROUP_GEN;\n\n uint256 genFriGroupInv = fpow(genFriGroup, (MAX_COSET_SIZE - 1));\n\n uint256 lastVal = ONE_VAL;\n uint256 lastValInv = ONE_VAL;\n uint256 prime = PrimeFieldElement0.K_MODULUS;\n assembly {\n // ctx[mmHalfFriInvGroup + 0] = ONE_VAL;\n mstore(friHalfInvGroupPtr, lastValInv)\n // ctx[mmFriGroup + 0] = ONE_VAL;\n mstore(friGroupPtr, lastVal)\n // ctx[mmFriGroup + 1] = fsub(0, ONE_VAL);\n mstore(add(friGroupPtr, 0x20), sub(prime, lastVal))\n }\n\n // To compute [1, -1 (== g^n/2), g^n/4, -g^n/4, ...]\n // we compute half the elements and derive the rest using negation.\n uint256 halfCosetSize = MAX_COSET_SIZE / 2;\n for (uint256 i = 1; i \u003c halfCosetSize; i++) {\n lastVal = fmul(lastVal, genFriGroup);\n lastValInv = fmul(lastValInv, genFriGroupInv);\n uint256 idx = bitReverse(i, FRI_MAX_FRI_STEP-1);\n\n assembly {\n // ctx[mmHalfFriInvGroup + idx] = lastValInv;\n mstore(add(friHalfInvGroupPtr, mul(idx, 0x20)), lastValInv)\n // ctx[mmFriGroup + 2*idx] = lastVal;\n mstore(add(friGroupPtr, mul(idx, 0x40)), lastVal)\n // ctx[mmFriGroup + 2*idx + 1] = fsub(0, lastVal);\n mstore(add(friGroupPtr, add(mul(idx, 0x40), 0x20)), sub(prime, lastVal))\n }\n }\n }\n\n /*\n Operates on the coset of size friFoldedCosetSize that start at index.\n\n It produces 3 outputs:\n 1. The field elements that result from doing FRI reductions on the coset.\n 2. The pointInv elements for the location that corresponds to the first output.\n 3. The root of a Merkle tree for the input layer.\n\n The input is read either from the queue or from the proof depending on data availability.\n Since the function reads from the queue it returns an updated head pointer.\n */\n function doFriSteps(\n uint256 friCtx, uint256 friQueueTail, uint256 cosetOffset_, uint256 friEvalPoint,\n uint256 friCosetSize, uint256 index, uint256 merkleQueuePtr)\n internal pure {\n uint256 friValue;\n\n uint256 evaluationsOnCosetPtr = friCtx + FRI_CTX_TO_COSET_EVALUATIONS_OFFSET;\n uint256 friHalfInvGroupPtr = friCtx + FRI_CTX_TO_FRI_HALF_INV_GROUP_OFFSET;\n\n // Compare to expected FRI step sizes in order of likelihood, step size 3 being most common.\n if (friCosetSize == 8) {\n (friValue, cosetOffset_) = do3FriSteps(\n friHalfInvGroupPtr, evaluationsOnCosetPtr, cosetOffset_, friEvalPoint);\n } else if (friCosetSize == 4) {\n (friValue, cosetOffset_) = do2FriSteps(\n friHalfInvGroupPtr, evaluationsOnCosetPtr, cosetOffset_, friEvalPoint);\n } else if (friCosetSize == 16) {\n (friValue, cosetOffset_) = do4FriSteps(\n friHalfInvGroupPtr, evaluationsOnCosetPtr, cosetOffset_, friEvalPoint);\n } else {\n require(false, \"Only step sizes of 2, 3 or 4 are supported.\");\n }\n\n uint256 lhashMask = getHashMask();\n assembly {\n let indexInNextStep := div(index, friCosetSize)\n mstore(merkleQueuePtr, indexInNextStep)\n mstore(add(merkleQueuePtr, 0x20), and(lhashMask, keccak256(evaluationsOnCosetPtr,\n mul(0x20,friCosetSize))))\n\n mstore(friQueueTail, indexInNextStep)\n mstore(add(friQueueTail, 0x20), friValue)\n mstore(add(friQueueTail, 0x40), cosetOffset_)\n }\n }\n\n /*\n Computes the FRI step with eta = log2(friCosetSize) for all the live queries.\n The input and output data is given in array of triplets:\n (query index, FRI value, FRI inversed point)\n in the address friQueuePtr (which is \u0026ctx[mmFriQueue:]).\n\n The function returns the number of live queries remaining after computing the FRI step.\n\n The number of live queries decreases whenever multiple query points in the same\n coset are reduced to a single query in the next FRI layer.\n\n As the function computes the next layer it also collects that data from\n the previous layer for Merkle verification.\n */\n function computeNextLayer(\n uint256 channelPtr, uint256 friQueuePtr, uint256 merkleQueuePtr, uint256 nQueries,\n uint256 friEvalPoint, uint256 friCosetSize, uint256 friCtx)\n internal pure returns (uint256 nLiveQueries) {\n uint256 merkleQueueTail = merkleQueuePtr;\n uint256 friQueueHead = friQueuePtr;\n uint256 friQueueTail = friQueuePtr;\n uint256 friQueueEnd = friQueueHead + (0x60 * nQueries);\n\n do {\n uint256 cosetOffset;\n uint256 index;\n (friQueueHead, index, cosetOffset) = gatherCosetInputs(\n channelPtr, friCtx, friQueueHead, friCosetSize);\n\n doFriSteps(\n friCtx, friQueueTail, cosetOffset, friEvalPoint, friCosetSize, index,\n merkleQueueTail);\n\n merkleQueueTail += 0x40;\n friQueueTail += 0x60;\n } while (friQueueHead \u003c friQueueEnd);\n return (friQueueTail - friQueuePtr) / 0x60;\n }\n\n}\n"},"FriStatementContract.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nimport \"FactRegistry.sol\";\nimport \"FriLayer.sol\";\n\ncontract FriStatementContract is FriLayer, FactRegistry {\n /*\n Compute a single FRI layer of size friStepSize at evaluationPoint starting from input\n friQueue, and the extra witnesses in the \"proof\" channel. Also check that the input and\n witnesses belong to a Merkle tree with root expectedRoot, again using witnesses from \"proof\".\n After verification, register the FRI fact hash, which is:\n keccak256(\n evaluationPoint,\n friStepSize,\n keccak256(friQueue_input),\n keccak256(friQueue_output), // The FRI queue after proccessing the FRI layer\n expectedRoot\n )\n\n Note that this function is used as external, but declared public to avoid copying the arrays.\n */\n function verifyFRI(\n uint256[] memory proof,\n uint256[] memory friQueue,\n uint256 evaluationPoint,\n uint256 friStepSize,\n uint256 expectedRoot) public {\n\n require (friStepSize \u003c= FRI_MAX_FRI_STEP, \"FRI step size too large\");\n /*\n The friQueue should have of 3*nQueries + 1 elements, beginning with nQueries triplets\n of the form (query_index, FRI_value, FRI_inverse_point), and ending with a single buffer\n cell set to 0, which is accessed and read during the computation of the FRI layer.\n */\n require (\n friQueue.length % 3 == 1,\n \"FRI Queue must be composed of triplets plus one delimiter cell\");\n require (friQueue.length \u003e= 4, \"No query to process\");\n\n uint256 mmFriCtxSize = FRI_CTX_SIZE;\n uint256 nQueries = friQueue.length / 3;\n friQueue[3*nQueries] = 0; // NOLINT: divide-before-multiply.\n uint256 merkleQueuePtr;\n uint256 friQueuePtr;\n uint256 channelPtr;\n uint256 friCtx;\n uint256 dataToHash;\n\n // Verify evaluation point within valid range.\n require(evaluationPoint \u003c K_MODULUS, \"INVALID_EVAL_POINT\");\n\n // Queries need to be in the range [2**height .. 2**(height+1)-1] strictly incrementing.\n // i.e. we need to check that Qi+1 \u003e Qi for each i,\n // but regarding the height range - it\u0027s sufficient to check that\n // (Q1 ^ Qn) \u003c Q1 Which affirms that all queries are within the same logarithmic step.\n\n // Verify FRI values and inverses are within valid range.\n // and verify that queries are strictly incrementing.\n uint256 prevQuery = 0; // If we pass height, change to: prevQuery = 1 \u003c\u003c height - 1;\n for (uint256 i = 0; i \u003c nQueries; i++) {\n require(friQueue[3*i] \u003e prevQuery, \"INVALID_QUERY_VALUE\");\n require(friQueue[3*i+1] \u003c K_MODULUS, \"INVALID_FRI_VALUE\");\n require(friQueue[3*i+2] \u003c K_MODULUS, \"INVALID_FRI_INVERSE_POINT\");\n prevQuery = friQueue[3*i];\n }\n\n // Verify all queries are on the same logarithmic step.\n // NOLINTNEXTLINE: divide-before-multiply.\n require((friQueue[0] ^ friQueue[3*nQueries-3]) \u003c friQueue[0], \"INVALID_QUERIES_RANGE\");\n\n // Allocate memory queues: channelPtr, merkleQueue, friCtx, dataToHash.\n assembly {\n friQueuePtr := add(friQueue, 0x20)\n channelPtr := mload(0x40) // Free pointer location.\n mstore(channelPtr, add(proof, 0x20))\n merkleQueuePtr := add(channelPtr, 0x20)\n friCtx := add(merkleQueuePtr, mul(0x40, nQueries))\n dataToHash := add(friCtx, mmFriCtxSize)\n mstore(0x40, add(dataToHash, 0xa0)) // Advance free pointer.\n\n mstore(dataToHash, evaluationPoint)\n mstore(add(dataToHash, 0x20), friStepSize)\n mstore(add(dataToHash, 0x80), expectedRoot)\n\n // Hash FRI inputs and add to dataToHash.\n mstore(add(dataToHash, 0x40), keccak256(friQueuePtr, mul(0x60, nQueries)))\n }\n\n initFriGroups(friCtx);\n\n nQueries = computeNextLayer(\n channelPtr, friQueuePtr, merkleQueuePtr, nQueries, evaluationPoint,\n 2**friStepSize, /* friCosetSize = 2**friStepSize */\n friCtx);\n\n verifyMerkle(channelPtr, merkleQueuePtr, bytes32(expectedRoot), nQueries);\n\n bytes32 factHash;\n assembly {\n // Hash FRI outputs and add to dataToHash.\n mstore(add(dataToHash, 0x60), keccak256(friQueuePtr, mul(0x60, nQueries)))\n factHash := keccak256(dataToHash, 0xa0)\n }\n\n registerFact(factHash);\n }\n}\n"},"IFactRegistry.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\n/*\n The Fact Registry design pattern is a way to separate cryptographic verification from the\n business logic of the contract flow.\n\n A fact registry holds a hash table of verified \"facts\" which are represented by a hash of claims\n that the registry hash check and found valid. This table may be queried by accessing the\n isValid() function of the registry with a given hash.\n\n In addition, each fact registry exposes a registry specific function for submitting new claims\n together with their proofs. The information submitted varies from one registry to the other\n depending of the type of fact requiring verification.\n\n For further reading on the Fact Registry design pattern see this\n `StarkWare blog post \u003chttps://medium.com/starkware/the-fact-registry-a64aafb598b6\u003e`_.\n*/\ninterface IFactRegistry {\n /*\n Returns true if the given fact was previously registered in the contract.\n */\n function isValid(bytes32 fact)\n external view\n returns(bool);\n}\n"},"IMerkleVerifier.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nabstract contract IMerkleVerifier {\n uint256 constant internal MAX_N_MERKLE_VERIFIER_QUERIES = 128;\n\n function verifyMerkle(\n uint256 channelPtr,\n uint256 queuePtr,\n bytes32 root,\n uint256 n)\n internal view virtual\n returns (bytes32 hash);\n}\n"},"IQueryableFactRegistry.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nimport \"IFactRegistry.sol\";\n\n/*\n Extends the IFactRegistry interface with a query method that indicates\n whether the fact registry has successfully registered any fact or is still empty of such facts.\n*/\ninterface IQueryableFactRegistry is IFactRegistry {\n\n /*\n Returns true if at least one fact has been registered.\n */\n function hasRegisteredFact()\n external view\n returns(bool);\n\n}\n"},"MerkleVerifier.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\nimport \"IMerkleVerifier.sol\";\n\ncontract MerkleVerifier is IMerkleVerifier {\n\n function getHashMask() internal pure returns(uint256) {\n // Default implementation.\n return 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000000;\n }\n\n /*\n Verifies a Merkle tree decommitment for n leaves in a Merkle tree with N leaves.\n\n The inputs data sits in the queue at queuePtr.\n Each slot in the queue contains a 32 bytes leaf index and a 32 byte leaf value.\n The indices need to be in the range [N..2*N-1] and strictly incrementing.\n Decommitments are read from the channel in the ctx.\n\n The input data is destroyed during verification.\n */\n function verifyMerkle(\n uint256 channelPtr,\n uint256 queuePtr,\n bytes32 root,\n uint256 n)\n internal view virtual override\n returns (bytes32 hash)\n {\n uint256 lhashMask = getHashMask();\n require(n \u003c= MAX_N_MERKLE_VERIFIER_QUERIES, \"TOO_MANY_MERKLE_QUERIES\");\n\n assembly {\n // queuePtr + i * 0x40 gives the i\u0027th index in the queue.\n // hashesPtr + i * 0x40 gives the i\u0027th hash in the queue.\n let hashesPtr := add(queuePtr, 0x20)\n let queueSize := mul(n, 0x40)\n let slotSize := 0x40\n\n // The items are in slots [0, n-1].\n let rdIdx := 0\n let wrIdx := 0 // = n % n.\n\n // Iterate the queue until we hit the root.\n let index := mload(add(rdIdx, queuePtr))\n let proofPtr := mload(channelPtr)\n\n // while(index \u003e 1).\n for { } gt(index, 1) { } {\n let siblingIndex := xor(index, 1)\n // sibblingOffset := 0x20 * lsb(siblingIndex).\n let sibblingOffset := mulmod(siblingIndex, 0x20, 0x40)\n\n // Store the hash corresponding to index in the correct slot.\n // 0 if index is even and 0x20 if index is odd.\n // The hash of the sibling will be written to the other slot.\n mstore(xor(0x20, sibblingOffset), mload(add(rdIdx, hashesPtr)))\n rdIdx := addmod(rdIdx, slotSize, queueSize)\n\n // Inline channel operation:\n // Assume we are going to read a new hash from the proof.\n // If this is not the case add(proofPtr, 0x20) will be reverted.\n let newHashPtr := proofPtr\n proofPtr := add(proofPtr, 0x20)\n\n // Push index/2 into the queue, before reading the next index.\n // The order is important, as otherwise we may try to read from an empty queue (in\n // the case where we are working on one item).\n // wrIdx will be updated after writing the relevant hash to the queue.\n mstore(add(wrIdx, queuePtr), div(index, 2))\n\n // Load the next index from the queue and check if it is our sibling.\n index := mload(add(rdIdx, queuePtr))\n if eq(index, siblingIndex) {\n // Take sibling from queue rather than from proof.\n newHashPtr := add(rdIdx, hashesPtr)\n // Revert reading from proof.\n proofPtr := sub(proofPtr, 0x20)\n rdIdx := addmod(rdIdx, slotSize, queueSize)\n\n // Index was consumed, read the next one.\n // Note that the queue can\u0027t be empty at this point.\n // The index of the parent of the current node was already pushed into the\n // queue, and the parent is never the sibling.\n index := mload(add(rdIdx, queuePtr))\n }\n\n mstore(sibblingOffset, mload(newHashPtr))\n\n // Push the new hash to the end of the queue.\n mstore(add(wrIdx, hashesPtr), and(lhashMask, keccak256(0x00, 0x40)))\n wrIdx := addmod(wrIdx, slotSize, queueSize)\n }\n hash := mload(add(rdIdx, hashesPtr))\n\n // Update the proof pointer in the context.\n mstore(channelPtr, proofPtr)\n }\n // emit LogBool(hash == root);\n require(hash == root, \"INVALID_MERKLE_PROOF\");\n }\n}\n"},"PrimeFieldElement0.sol":{"content":"/*\n Copyright 2019,2020 StarkWare Industries Ltd.\n\n Licensed under the Apache License, Version 2.0 (the \"License\").\n You may not use this file except in compliance with the License.\n You may obtain a copy of the License at\n\n https://www.starkware.co/open-source-license/\n\n Unless required by applicable law or agreed to in writing,\n software distributed under the License is distributed on an \"AS IS\" BASIS,\n WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n See the License for the specific language governing permissions\n and limitations under the License.\n*/\n// SPDX-License-Identifier: Apache-2.0.\npragma solidity ^0.6.11;\n\n\ncontract PrimeFieldElement0 {\n uint256 constant internal K_MODULUS =\n 0x800000000000011000000000000000000000000000000000000000000000001;\n uint256 constant internal K_MODULUS_MASK =\n 0x0fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;\n uint256 constant internal K_MONTGOMERY_R =\n 0x7fffffffffffdf0ffffffffffffffffffffffffffffffffffffffffffffffe1;\n uint256 constant internal K_MONTGOMERY_R_INV =\n 0x40000000000001100000000000012100000000000000000000000000000000;\n uint256 constant internal GENERATOR_VAL = 3;\n uint256 constant internal ONE_VAL = 1;\n uint256 constant internal GEN1024_VAL =\n 0x659d83946a03edd72406af6711825f5653d9e35dc125289a206c054ec89c4f1;\n\n function fromMontgomery(uint256 val) internal pure returns (uint256 res) {\n // uint256 res = fmul(val, kMontgomeryRInv);\n assembly {\n res := mulmod(val,\n 0x40000000000001100000000000012100000000000000000000000000000000,\n 0x800000000000011000000000000000000000000000000000000000000000001)\n }\n return res;\n }\n\n function fromMontgomeryBytes(bytes32 bs) internal pure returns (uint256) {\n // Assuming bs is a 256bit bytes object, in Montgomery form, it is read into a field\n // element.\n uint256 res = uint256(bs);\n return fromMontgomery(res);\n }\n\n function toMontgomeryInt(uint256 val) internal pure returns (uint256 res) {\n //uint256 res = fmul(val, kMontgomeryR);\n assembly {\n res := mulmod(val,\n 0x7fffffffffffdf0ffffffffffffffffffffffffffffffffffffffffffffffe1,\n 0x800000000000011000000000000000000000000000000000000000000000001)\n }\n return res;\n }\n\n function fmul(uint256 a, uint256 b) internal pure returns (uint256 res) {\n //uint256 res = mulmod(a, b, kModulus);\n assembly {\n res := mulmod(a, b,\n 0x800000000000011000000000000000000000000000000000000000000000001)\n }\n return res;\n }\n\n function fadd(uint256 a, uint256 b) internal pure returns (uint256 res) {\n // uint256 res = addmod(a, b, kModulus);\n assembly {\n res := addmod(a, b,\n 0x800000000000011000000000000000000000000000000000000000000000001)\n }\n return res;\n }\n\n function fsub(uint256 a, uint256 b) internal pure returns (uint256 res) {\n // uint256 res = addmod(a, kModulus - b, kModulus);\n assembly {\n res := addmod(\n a,\n sub(0x800000000000011000000000000000000000000000000000000000000000001, b),\n 0x800000000000011000000000000000000000000000000000000000000000001)\n }\n return res;\n }\n\n function fpow(uint256 val, uint256 exp) internal view returns (uint256) {\n return expmod(val, exp, K_MODULUS);\n }\n\n function expmod(uint256 base, uint256 exponent, uint256 modulus)\n internal view returns (uint256 res)\n {\n assembly {\n let p := mload(0x40)\n mstore(p, 0x20) // Length of Base.\n mstore(add(p, 0x20), 0x20) // Length of Exponent.\n mstore(add(p, 0x40), 0x20) // Length of Modulus.\n mstore(add(p, 0x60), base) // Base.\n mstore(add(p, 0x80), exponent) // Exponent.\n mstore(add(p, 0xa0), modulus) // Modulus.\n // Call modexp precompile.\n if iszero(staticcall(gas(), 0x05, p, 0xc0, p, 0x20)) {\n revert(0, 0)\n }\n res := mload(p)\n }\n }\n\n function inverse(uint256 val) internal view returns (uint256) {\n return expmod(val, K_MODULUS - 2, K_MODULUS);\n }\n}\n"}}