// File: lib/openzeppelin-contracts/contracts/access/Ownable.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (access/Ownable.sol)

pragma solidity ^0.8.0;

import "../utils/Context.sol";

/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;

    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }

    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }

    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _transferOwnership(newOwner);
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}

// File: lib/openzeppelin-contracts/contracts/utils/Context.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// File: src/AxiomV02.sol



// SPDX-License-Identifier: MIT
// WARNING! This smart contract and the associated zk-SNARK verifiers have not been audited.
// DO NOT USE THIS CONTRACT FOR PRODUCTION
pragma solidity ^0.8.12;

import {IAxiomV0} from "./IAxiomV0.sol";
import {Ownable} from "openzeppelin-contracts/access/Ownable.sol";

uint8 constant TREE_DEPTH = 10;
uint32 constant NUM_LEAVES = 2 ** 10;

// array indices for reading from the ZKP calldata
uint32 constant PUBLIC_BYTES_START_IDX = 4 * 3 * 32;
uint32 constant ROOT_BYTES_START_IDX = PUBLIC_BYTES_START_IDX + 5 * 32;

// constants for batch import of historical block hashes
uint8 constant HISTORICAL_TREE_DEPTH = 17;
uint32 constant HISTORICAL_NUM_LEAVES = 2 ** 17;
uint32 constant HISTORICAL_NUM_ROOTS = 2 ** 7; // HISTORICAL_NUM_LEAVES / NUM_LEAVES

function calcMerkleRoot(bytes32[HISTORICAL_NUM_ROOTS] calldata leaves) pure returns (bytes32) {
    uint256 len = HISTORICAL_NUM_ROOTS >> 1;
    bytes32[] memory roots = new bytes32[](len);
    for (uint256 i = 0; i < len; i++) {
        roots[i] = keccak256(abi.encodePacked(leaves[i << 1], leaves[(i << 1) | 1]));
    }
    while (len > 1) {
        len >>= 1;
        for (uint256 i = 0; i < len; i++) {
            roots[i] = keccak256(abi.encodePacked(roots[i << 1], roots[(i << 1) | 1]));
        }
    }
    return roots[0];
}

contract AxiomV02 is IAxiomV0, Ownable {
    string public constant VERSION = "0.2";

    /// @notice The address of the snark verifier contract.
    address public verifierAddress;
    /// @dev The address of AxiomV0 version "0.1". We will read from the storage of the old contract for old block hashes.
    address public oldAxiomAddress;
    /// @notice The block the contract was created at.
    uint256 public creationBlockNumber;

    // historicalRoots[startBlockNumber] is 0 unless (startBlockNumber % NUM_LEAVES == 0)
    // historicalRoots[startBlockNumber] holds the hash of
    //   prevHash || root || numFinal
    // where
    // - prevHash is the parent hash of block startBlockNumber
    // - root is the partial Merkle root of blockhashes of block numbers
    //   [startBlockNumber, startBlockNumber + NUM_LEAVES)
    //   where unconfirmed block hashes are 0's
    // - numFinal is the number of confirmed consecutive roots in [startBlockNumber, startBlockNumber + NUM_LEAVES)
    mapping(uint32 => bytes32) internal _historicalRoots;

    event UpdateSnarkVerifierAddress(address newAddress);

    /// @dev We do not re-import all historical blockhashes in this v0.2 contract, so we use the old v0.1 contract for older block numbers
    function historicalRoots(uint32 startBlockNumber) public view returns (bytes32) {
        if (startBlockNumber < creationBlockNumber) {
            return IAxiomV0(oldAxiomAddress).historicalRoots(startBlockNumber);
        } else {
            return _historicalRoots[startBlockNumber];
        }
    }

    constructor(address _oldAddress, address _verifierAddress) {
        creationBlockNumber = block.number;
        oldAxiomAddress = _oldAddress;
        verifierAddress = _verifierAddress;
    }

    function updateSnarkVerifierAddress(address _verifierAddress) external onlyOwner {
        verifierAddress = _verifierAddress;
        emit UpdateSnarkVerifierAddress(_verifierAddress);
    }

    function verifyRaw(bytes calldata input) private returns (bool) {
        (bool success,) = verifierAddress.call(input);
        return success;
    }

    function getEmptyHash(uint256 depth) public pure returns (bytes32) {
        // emptyHashes[idx] is the Merkle root of a tree of depth idx with 0's as leaves
        bytes32[TREE_DEPTH] memory emptyHashes = [
            bytes32(0x0000000000000000000000000000000000000000000000000000000000000000),
            bytes32(0xad3228b676f7d3cd4284a5443f17f1962b36e491b30a40b2405849e597ba5fb5),
            bytes32(0xb4c11951957c6f8f642c4af61cd6b24640fec6dc7fc607ee8206a99e92410d30),
            bytes32(0x21ddb9a356815c3fac1026b6dec5df3124afbadb485c9ba5a3e3398a04b7ba85),
            bytes32(0xe58769b32a1beaf1ea27375a44095a0d1fb664ce2dd358e7fcbfb78c26a19344),
            bytes32(0x0eb01ebfc9ed27500cd4dfc979272d1f0913cc9f66540d7e8005811109e1cf2d),
            bytes32(0x887c22bd8750d34016ac3c66b5ff102dacdd73f6b014e710b51e8022af9a1968),
            bytes32(0xffd70157e48063fc33c97a050f7f640233bf646cc98d9524c6b92bcf3ab56f83),
            bytes32(0x9867cc5f7f196b93bae1e27e6320742445d290f2263827498b54fec539f756af),
            bytes32(0xcefad4e508c098b9a7e1d8feb19955fb02ba9675585078710969d3440f5054e0)
        ];
        return emptyHashes[depth];
    }

    // The ZKP has block headers for [startBlockNumber, endBlockNumber] blocks. We extract some common information from the calldata.
    function getBoundaryBlockData(bytes calldata proofData)
        internal
        pure
        returns (bytes32 prevHash, bytes32 endHash, uint32 startBlockNumber, uint32 endBlockNumber, bytes32 root)
    {
        prevHash = bytes32(
            uint256(bytes32(proofData[PUBLIC_BYTES_START_IDX:PUBLIC_BYTES_START_IDX + 32])) << 128
                | uint128(bytes16(proofData[PUBLIC_BYTES_START_IDX + 32 + 16:PUBLIC_BYTES_START_IDX + 2 * 32]))
        );
        endHash = bytes32(
            uint256(bytes32(proofData[PUBLIC_BYTES_START_IDX + 2 * 32:PUBLIC_BYTES_START_IDX + 3 * 32])) << 128
                | uint128(bytes16(proofData[PUBLIC_BYTES_START_IDX + 3 * 32 + 16:PUBLIC_BYTES_START_IDX + 4 * 32]))
        );
        startBlockNumber =
            uint32(bytes4(proofData[PUBLIC_BYTES_START_IDX + 5 * 32 - 8:PUBLIC_BYTES_START_IDX + 5 * 32 - 4]));
        endBlockNumber = uint32(bytes4(proofData[PUBLIC_BYTES_START_IDX + 5 * 32 - 4:PUBLIC_BYTES_START_IDX + 5 * 32]));
        root = bytes32(
            uint256(bytes32(proofData[ROOT_BYTES_START_IDX:ROOT_BYTES_START_IDX + 32])) << 128
                | uint128(bytes16(proofData[ROOT_BYTES_START_IDX + 48:ROOT_BYTES_START_IDX + 64]))
        );
    }

    // update blocks in the "backward" direction, anchoring on a "recent" end blockhash that is within last 256 blocks
    // * startBlockNumber must be a multiple of NUM_LEAVES
    // * roots[idx] is the root of a Merkle tree of height 2**(TREE_DEPTH - idx) in a Merkle mountain
    //   range which stores block hashes in the interval [startBlockNumber, endBlockNumber]
    function updateRecent(bytes calldata proofData) external {
        (bytes32 prevHash, bytes32 endHash, uint32 startBlockNumber, uint32 endBlockNumber, bytes32 root) =
            getBoundaryBlockData(proofData);
        bytes32[TREE_DEPTH] memory roots;
        for (uint256 idx = 1; idx <= TREE_DEPTH; idx++) {
            roots[idx - 1] = bytes32(
                uint256(bytes32(proofData[ROOT_BYTES_START_IDX + idx * 64:ROOT_BYTES_START_IDX + idx * 64 + 32])) << 128
                    | uint128(
                        bytes16(proofData[ROOT_BYTES_START_IDX + idx * 64 + 16 + 32:ROOT_BYTES_START_IDX + idx * 64 + 64])
                    )
            );
        }

        uint32 numFinal = endBlockNumber - startBlockNumber + 1;
        require(numFinal <= NUM_LEAVES); // "Updating too many blocks at once");
        require(startBlockNumber % NUM_LEAVES == 0); // "startBlockNumber not a multiple of NUM_LEAVES");
        require(block.number - endBlockNumber <= 256); // "Not a recent endBlock");
        require(endBlockNumber < block.number); // "Not a recent endBlock");
        require(blockhash(endBlockNumber) == endHash); // "endHash does not match");
        require(verifyRaw(proofData)); // "ZKP does not verify");

        if (root == bytes32(0)) {
            // compute Merkle root of completed Merkle mountain range with 0s for unconfirmed blockhashes
            for (uint256 round = 1; round <= TREE_DEPTH; round++) {
                if (roots[TREE_DEPTH - round] != 0) {
                    root = keccak256(abi.encodePacked(roots[TREE_DEPTH - round], root));
                } else {
                    root = keccak256(abi.encodePacked(root, getEmptyHash(round - 1)));
                }
            }
        }
        _historicalRoots[startBlockNumber] = keccak256(abi.encodePacked(prevHash, root, numFinal));
        emit UpdateEvent(startBlockNumber, prevHash, root, numFinal);
    }

    // update older blocks in "backwards" direction, anchoring on more recent trusted blockhash
    // must be batch of NUM_LEAVES blocks
    function updateOld(bytes32 nextRoot, uint32 nextNumFinal, bytes calldata proofData) external {
        (bytes32 prevHash, bytes32 endHash, uint32 startBlockNumber, uint32 endBlockNumber, bytes32 root) =
            getBoundaryBlockData(proofData);

        require(startBlockNumber % NUM_LEAVES == 0, "aa"); // "startBlockNumber not a multiple of NUM_LEAVES");
        require(endBlockNumber - startBlockNumber == NUM_LEAVES - 1, "bb"); // "Updating with incorrect number of blocks");

        require(
            historicalRoots(endBlockNumber + 1) == keccak256(abi.encodePacked(endHash, nextRoot, nextNumFinal)), "cc"
        );
        // "endHash does not match"
        require(verifyRaw(proofData)); // "ZKP does not verify")

        _historicalRoots[startBlockNumber] = keccak256(abi.encodePacked(prevHash, root, NUM_LEAVES));
        emit UpdateEvent(startBlockNumber, prevHash, root, NUM_LEAVES);
    }

    function isRecentBlockHashValid(uint32 blockNumber, bytes32 claimedBlockHash) public view returns (bool) {
        bytes32 blockHash = blockhash(blockNumber);
        require(blockHash != 0x0); // "Must supply block hash of one of 256 most recent blocks"
        return (blockHash == claimedBlockHash);
    }

    function isBlockHashValid(BlockHashWitness calldata witness) public view returns (bool) {
        require(witness.claimedBlockHash != 0x0); // "Claimed block hash cannot be 0"
        uint32 side = witness.blockNumber % NUM_LEAVES;
        uint32 startBlockNumber = witness.blockNumber - side;
        bytes32 merkleRoot = historicalRoots(startBlockNumber);
        require(merkleRoot != 0); // "Merkle root must be stored already"
        // compute Merkle root of blockhash
        bytes32 root = witness.claimedBlockHash;
        for (uint8 depth = 0; depth < TREE_DEPTH; depth++) {
            // 0 for left, 1 for right
            if ((side >> depth) & 1 == 0) {
                root = keccak256(abi.encodePacked(root, witness.merkleProof[depth]));
            } else {
                root = keccak256(abi.encodePacked(witness.merkleProof[depth], root));
            }
        }
        return (merkleRoot == keccak256(abi.encodePacked(witness.prevHash, root, witness.numFinal)));
    }
}

// File: src/IAxiomV0.sol



// SPDX-License-Identifier: MIT
// WARNING! This smart contract and the associated zk-SNARK verifiers have not been audited.
// DO NOT USE THIS CONTRACT FOR PRODUCTION
pragma solidity ^0.8.12;

interface IAxiomV0 {
    // historicalRoots(startBlockNumber) is 0 unless (startBlockNumber % 1024 == 0)
    // historicalRoots(startBlockNumber) holds the hash of
    //   prevHash || root || numFinal
    // where
    // - prevHash is the parent hash of block startBlockNumber
    // - root is the partial Merkle root of blockhashes of block numbers
    //   [startBlockNumber, startBlockNumber + 1024)
    //   where unconfirmed block hashes are 0's
    // - numFinal is the number of confirmed consecutive roots in [startBlockNumber, startBlockNumber + 1024)
    function historicalRoots(uint32 startBlockNumber) external view returns (bytes32);

    event UpdateEvent(uint32 startBlockNumber, bytes32 prevHash, bytes32 root, uint32 numFinal);

    struct BlockHashWitness {
        uint32 blockNumber;
        bytes32 claimedBlockHash;
        bytes32 prevHash;
        uint32 numFinal;
        bytes32[10] merkleProof;
    }

    // returns Merkle root of a tree of depth `depth` with 0's as leaves
    function getEmptyHash(uint256 depth) external pure returns (bytes32);

    // update blocks in the "backward" direction, anchoring on a "recent" end blockhash that is within last 256 blocks
    // * startBlockNumber must be a multiple of 1024
    // * roots[idx] is the root of a Merkle tree of height 2**(10 - idx) in a Merkle mountain
    //   range which stores block hashes in the interval [startBlockNumber, endBlockNumber]
    function updateRecent(bytes calldata proofData) external;

    // update older blocks in "backwards" direction, anchoring on more recent trusted blockhash
    // must be batch of 1024 blocks
    function updateOld(bytes32 nextRoot, uint32 nextNumFinal, bytes calldata proofData) external;

    function isRecentBlockHashValid(uint32 blockNumber, bytes32 claimedBlockHash) external view returns (bool);
    function isBlockHashValid(BlockHashWitness calldata witness) external view returns (bool);
}