{"FactRegistry.sol":{"content":"/*\n  Copyright 2019-2022 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.12;\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 = false;\n\n    /*\n      Checks if a fact has been verified.\n    */\n    function isValid(bytes32 fact) external view override returns (bool) {\n        return _factCheck(fact);\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) internal view returns (bool) {\n        return verifiedFact[fact];\n    }\n\n    function registerFact(bytes32 factHash) internal {\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() external view override returns (bool) {\n        return anyFactRegistered;\n    }\n}\n"},"IFactRegistry.sol":{"content":"/*\n  Copyright 2019-2022 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.12;\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) external view returns (bool);\n}\n"},"IQueryableFactRegistry.sol":{"content":"/*\n  Copyright 2019-2022 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.12;\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      Returns true if at least one fact has been registered.\n    */\n    function hasRegisteredFact() external view returns (bool);\n}\n"},"MemoryPageFactRegistry.sol":{"content":"/*\n  Copyright 2019-2022 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.12;\n\nimport \"FactRegistry.sol\";\n\ncontract MemoryPageFactRegistryConstants {\n    // A page based on a list of pairs (address, value).\n    // In this case, memoryHash = hash(address, value, address, value, address, value, ...).\n    uint256 internal constant REGULAR_PAGE = 0;\n    // A page based on adjacent memory cells, starting from a given address.\n    // In this case, memoryHash = hash(value, value, value, ...).\n    uint256 internal constant CONTINUOUS_PAGE = 1;\n}\n\n/*\n  A fact registry for the claim:\n    I know n pairs (addr, value) for which the hash of the pairs is memoryHash, and the cumulative\n    product: \\prod_i( z - (addr_i + alpha * value_i) ) is prod.\n  The exact format of the hash depends on the type of the page\n  (see MemoryPageFactRegistryConstants).\n  The fact consists of (pageType, prime, n, z, alpha, prod, memoryHash, address).\n  Note that address is only available for CONTINUOUS_PAGE, and otherwise it is 0.\n*/\ncontract MemoryPageFactRegistry is FactRegistry, MemoryPageFactRegistryConstants {\n    event LogMemoryPageFactRegular(bytes32 factHash, uint256 memoryHash, uint256 prod);\n    event LogMemoryPageFactContinuous(bytes32 factHash, uint256 memoryHash, uint256 prod);\n\n    /*\n      Registers a fact based of the given memory (address, value) pairs (REGULAR_PAGE).\n    */\n    function registerRegularMemoryPage(\n        uint256[] calldata memoryPairs,\n        uint256 z,\n        uint256 alpha,\n        uint256 prime\n    )\n        external\n        returns (\n            bytes32 factHash,\n            uint256 memoryHash,\n            uint256 prod\n        )\n    {\n        require(memoryPairs.length \u003c 2**20, \"Too many memory values.\");\n        require(memoryPairs.length % 2 == 0, \"Size of memoryPairs must be even.\");\n        require(z \u003c prime, \"Invalid value of z.\");\n        require(alpha \u003c prime, \"Invalid value of alpha.\");\n        (factHash, memoryHash, prod) = computeFactHash(memoryPairs, z, alpha, prime);\n        emit LogMemoryPageFactRegular(factHash, memoryHash, prod);\n\n        registerFact(factHash);\n    }\n\n    function computeFactHash(\n        uint256[] memory memoryPairs,\n        uint256 z,\n        uint256 alpha,\n        uint256 prime\n    )\n        private\n        pure\n        returns (\n            bytes32 factHash,\n            uint256 memoryHash,\n            uint256 prod\n        )\n    {\n        uint256 memorySize = memoryPairs.length / 2; // NOLINT: divide-before-multiply.\n\n        prod = 1;\n\n        assembly {\n            let memoryPtr := add(memoryPairs, 0x20)\n\n            // Each value of memoryPairs is a pair: (address, value).\n            let lastPtr := add(memoryPtr, mul(memorySize, 0x40))\n            for {\n                let ptr := memoryPtr\n            } lt(ptr, lastPtr) {\n                ptr := add(ptr, 0x40)\n            } {\n                // Compute address + alpha * value.\n                let address_value_lin_comb := addmod(\n                    // address=\n                    mload(ptr),\n                    mulmod(\n                        // value=\n                        mload(add(ptr, 0x20)),\n                        alpha,\n                        prime\n                    ),\n                    prime\n                )\n                prod := mulmod(prod, add(z, sub(prime, address_value_lin_comb)), prime)\n            }\n\n            memoryHash := keccak256(\n                memoryPtr,\n                mul(\n                    // 0x20 * 2.\n                    0x40,\n                    memorySize\n                )\n            )\n        }\n\n        factHash = keccak256(\n            abi.encodePacked(\n                REGULAR_PAGE,\n                prime,\n                memorySize,\n                z,\n                alpha,\n                prod,\n                memoryHash,\n                uint256(0)\n            )\n        );\n    }\n\n    /*\n      Registers a fact based on the given values, assuming continuous addresses.\n      values should be [value at startAddr, value at (startAddr + 1), ...].\n    */\n    function registerContinuousMemoryPage(\n        // NOLINT: external-function.\n        uint256 startAddr,\n        uint256[] memory values,\n        uint256 z,\n        uint256 alpha,\n        uint256 prime\n    )\n        public\n        returns (\n            bytes32 factHash,\n            uint256 memoryHash,\n            uint256 prod\n        )\n    {\n        require(values.length \u003c 2**20, \"Too many memory values.\");\n        require(prime \u003c 2**254, \"prime is too big for the optimizations in this function.\");\n        require(z \u003c prime, \"Invalid value of z.\");\n        require(alpha \u003c prime, \"Invalid value of alpha.\");\n        require(startAddr \u003c 2**64 \u0026\u0026 startAddr \u003c prime, \"Invalid value of startAddr.\");\n\n        uint256 nValues = values.length;\n\n        assembly {\n            // Initialize prod to 1.\n            prod := 1\n            // Initialize valuesPtr to point to the first value in the array.\n            let valuesPtr := add(values, 0x20)\n\n            let minus_z := mod(sub(prime, z), prime)\n\n            // Start by processing full batches of 8 cells, addr represents the last address in each\n            // batch.\n            let addr := add(startAddr, 7)\n            let lastAddr := add(startAddr, nValues)\n            for {\n\n            } lt(addr, lastAddr) {\n                addr := add(addr, 8)\n            } {\n                // Compute the product of (lin_comb - z) instead of (z - lin_comb), since we\u0027re\n                // doing an even number of iterations, the result is the same.\n                prod := mulmod(\n                    prod,\n                    mulmod(\n                        add(add(sub(addr, 7), mulmod(mload(valuesPtr), alpha, prime)), minus_z),\n                        add(\n                            add(sub(addr, 6), mulmod(mload(add(valuesPtr, 0x20)), alpha, prime)),\n                            minus_z\n                        ),\n                        prime\n                    ),\n                    prime\n                )\n\n                prod := mulmod(\n                    prod,\n                    mulmod(\n                        add(\n                            add(sub(addr, 5), mulmod(mload(add(valuesPtr, 0x40)), alpha, prime)),\n                            minus_z\n                        ),\n                        add(\n                            add(sub(addr, 4), mulmod(mload(add(valuesPtr, 0x60)), alpha, prime)),\n                            minus_z\n                        ),\n                        prime\n                    ),\n                    prime\n                )\n\n                prod := mulmod(\n                    prod,\n                    mulmod(\n                        add(\n                            add(sub(addr, 3), mulmod(mload(add(valuesPtr, 0x80)), alpha, prime)),\n                            minus_z\n                        ),\n                        add(\n                            add(sub(addr, 2), mulmod(mload(add(valuesPtr, 0xa0)), alpha, prime)),\n                            minus_z\n                        ),\n                        prime\n                    ),\n                    prime\n                )\n\n                prod := mulmod(\n                    prod,\n                    mulmod(\n                        add(\n                            add(sub(addr, 1), mulmod(mload(add(valuesPtr, 0xc0)), alpha, prime)),\n                            minus_z\n                        ),\n                        add(add(addr, mulmod(mload(add(valuesPtr, 0xe0)), alpha, prime)), minus_z),\n                        prime\n                    ),\n                    prime\n                )\n\n                valuesPtr := add(valuesPtr, 0x100)\n            }\n\n            // Handle leftover.\n            // Translate addr to the beginning of the last incomplete batch.\n            addr := sub(addr, 7)\n            for {\n\n            } lt(addr, lastAddr) {\n                addr := add(addr, 1)\n            } {\n                let address_value_lin_comb := addmod(\n                    addr,\n                    mulmod(mload(valuesPtr), alpha, prime),\n                    prime\n                )\n                prod := mulmod(prod, add(z, sub(prime, address_value_lin_comb)), prime)\n                valuesPtr := add(valuesPtr, 0x20)\n            }\n\n            memoryHash := keccak256(add(values, 0x20), mul(0x20, nValues))\n        }\n\n        factHash = keccak256(\n            abi.encodePacked(CONTINUOUS_PAGE, prime, nValues, z, alpha, prod, memoryHash, startAddr)\n        );\n\n        emit LogMemoryPageFactContinuous(factHash, memoryHash, prod);\n\n        registerFact(factHash);\n    }\n}\n"}}