// Source: contracts/governance/BaseWeightedMultisig.sol

pragma solidity ^0.8.0;

// SPDX-License-Identifier: MIT

// File contracts/interfaces/IBaseWeightedMultisig.sol

interface IBaseWeightedMultisig {
    error InvalidSigners();
    error InvalidThreshold();
    error MalformedSignatures();
    error LowSignaturesWeight();
    error InvalidWeights();
    error DuplicateSigners(bytes32 signersHash);
    error RedundantSignaturesProvided(uint256 required, uint256 provided);
    error InsufficientRotationDelay(uint256 minimumRotationDelay, uint256 lastRotationTimestamp, uint256 timeElapsed);

    event SignersRotated(uint256 indexed epoch, bytes32 indexed signersHash, bytes signers);

    /**
     * @dev This function returns the old signers retention period
     * @return uint256 The old signers retention period
     */
    function previousSignersRetention() external view returns (uint256);

    /**
     * @dev This function returns the current signers epoch
     * @return uint256 The current signers epoch
     */
    function epoch() external view returns (uint256);

    /**
     * @dev Returns the hash for a given signers epoch
     * @param signerEpoch The epoch to get the hash for
     * @return The hash for the given epoch
     */
    function signersHashByEpoch(uint256 signerEpoch) external view returns (bytes32);

    /**
     * @dev Returns the epoch for a given hash
     * @param signersHash The hash to get the epoch for
     * @return The epoch for the given hash
     */
    function epochBySignersHash(bytes32 signersHash) external view returns (uint256);

    /**
     * @notice This function returns the timestamp for the last signer rotation
     * @return uint256 The last rotation timestamp
     */
    function lastRotationTimestamp() external view returns (uint256);

    /**
     * @notice This function returns the time elapsed (in secs) since the last rotation
     * @return uint256 The time since the last rotation
     */
    function timeSinceRotation() external view returns (uint256);

    /**
     * @notice Compute the message hash that is signed by the weighted signers
     * @param signersHash The hash of the weighted signers that sign off on the data
     * @param dataHash The hash of the data
     * @return The message hash to be signed
     */
    function messageHashToSign(bytes32 signersHash, bytes32 dataHash) external view returns (bytes32);
}

// File contracts/libs/ECDSA.sol

/**
 * @dev Elliptic Curve Digital Signature Algorithm (ECDSA) operations.
 *
 * These functions can be used to verify that a message was signed by the holder
 * of the private keys of a given address.
 */
library ECDSA {
    error InvalidSignatureLength();
    error InvalidS();
    error InvalidV();
    error InvalidSignature();

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature`. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
     * this function rejects them by requiring the `s` value to be in the lower
     * half order, and the `v` value to be either 27 or 28.
     *
     * IMPORTANT: `hash` _must_ be the result of a hash operation for the
     * verification to be secure: it is possible to craft signatures that
     * recover to arbitrary addresses for non-hashed data. A safe way to ensure
     * this is by receiving a hash of the original message (which may otherwise
     * be too long), and then calling {toEthSignedMessageHash} on it.
     */
    function recover(bytes32 hash, bytes memory signature) internal pure returns (address signer) {
        // Check the signature length
        if (signature.length != 65) revert InvalidSignatureLength();

        // Divide the signature in r, s and v variables
        bytes32 r;
        bytes32 s;
        uint8 v;

        // ecrecover takes the signature parameters, and the only way to get them
        // currently is to use assembly.
        // solhint-disable-next-line no-inline-assembly
        assembly {
            r := mload(add(signature, 0x20))
            s := mload(add(signature, 0x40))
            v := byte(0, mload(add(signature, 0x60)))
        }

        // EIP-2 still allows signature malleability for ecrecover(). Remove this possibility and make the signature
        // unique. Appendix F in the Ethereum Yellow paper (https://ethereum.github.io/yellowpaper/paper.pdf), defines
        // the valid range for s in (281): 0 < s < secp256k1n ÷ 2 + 1, and for v in (282): v ∈ {27, 28}. Most
        // signatures from current libraries generate a unique signature with an s-value in the lower half order.
        //
        // If your library generates malleable signatures, such as s-values in the upper range, calculate a new s-value
        // with 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1 and flip v from 27 to 28 or
        // vice versa. If your library also generates signatures with 0/1 for v instead 27/28, add 27 to v to accept
        // these malleable signatures as well.
        if (uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0) revert InvalidS();

        if (v != 27 && v != 28) revert InvalidV();

        signer = ecrecover(hash, v, r, s);

        // If the signature is valid (and not malleable), return the signer address
        if (signer == address(0)) revert InvalidSignature();
    }
}

// File contracts/types/WeightedMultisigTypes.sol

/**
 * @notice This struct represents the weighted signer
 * @param signer The address of the weighted signer
 * @param weight The weight of the weighted singer
 */
struct WeightedSigner {
    address signer;
    uint128 weight;
}

/**
 * @notice This struct represents the weighted signers payload
 * @param signers The list of weighted signers
 * @param threshold The threshold for the weighted signers
 * @param nonce The nonce to distinguish different weighted signer sets
 */
struct WeightedSigners {
    WeightedSigner[] signers;
    uint128 threshold;
    bytes32 nonce;
}

/**
 * @notice This struct represents a proof for a message from the weighted signers
 * @param signers The weighted signers
 * @param signatures The list of signatures
 */
struct Proof {
    WeightedSigners signers;
    bytes[] signatures;
}

// File contracts/governance/BaseWeightedMultisig.sol

/**
    @title BaseWeightedMultisig Contract
    @notice Base contract to build a weighted multisig verification
*/
abstract contract BaseWeightedMultisig is IBaseWeightedMultisig {
    // keccak256('BaseWeightedMultisig.Slot') - 1;
    bytes32 internal constant BASE_WEIGHTED_MULTISIG_SLOT =
        0x457f3fc26bf430b020fe76358b1bfaba57e1657ace718da6437cda9934eabfe8;

    struct BaseWeightedMultisigStorage {
        uint256 epoch;
        uint256 lastRotationTimestamp;
        mapping(uint256 => bytes32) signersHashByEpoch;
        mapping(bytes32 => uint256) epochBySignersHash;
    }

    /// @dev Previous signers retention. 0 means only the current signers are valid
    uint256 public immutable previousSignersRetention;

    /// @dev The domain separator for the signer proof
    bytes32 public immutable domainSeparator;

    /// @dev The minimum delay required between rotations
    uint256 public immutable minimumRotationDelay;

    /**
     * @dev Initializes the contract.
     * @dev Ownership of this contract should be transferred to the Gateway contract after deployment.
     * @param previousSignersRetention_ The number of previous signers to retain
     * @param domainSeparator_ The domain separator for the signer proof
     * @param minimumRotationDelay_ The minimum delay required between rotations
     */
    constructor(
        uint256 previousSignersRetention_,
        bytes32 domainSeparator_,
        uint256 minimumRotationDelay_
    ) {
        previousSignersRetention = previousSignersRetention_;
        domainSeparator = domainSeparator_;
        minimumRotationDelay = minimumRotationDelay_;
    }

    /**********************\
    |* External Functions *|
    \**********************/

    /**
     * @notice This function returns the current signers epoch
     * @return uint256 The current signers epoch
     */
    function epoch() external view returns (uint256) {
        return _baseWeightedMultisigStorage().epoch;
    }

    /**
     * @notice This function returns the signers hash for a given epoch
     * @param signerEpoch The given epoch
     * @return bytes32 The signers hash for the given epoch
     */
    function signersHashByEpoch(uint256 signerEpoch) external view returns (bytes32) {
        return _baseWeightedMultisigStorage().signersHashByEpoch[signerEpoch];
    }

    /**
     * @notice This function returns the epoch for a given signers hash
     * @param signersHash The signers hash
     * @return uint256 The epoch for the given signers hash
     */
    function epochBySignersHash(bytes32 signersHash) external view returns (uint256) {
        return _baseWeightedMultisigStorage().epochBySignersHash[signersHash];
    }

    /**
     * @notice This function returns the timestamp for the last signer rotation
     * @return uint256 The last rotation timestamp
     */
    function lastRotationTimestamp() external view returns (uint256) {
        return _baseWeightedMultisigStorage().lastRotationTimestamp;
    }

    /**
     * @notice This function returns the time elapsed (in secs) since the last rotation
     * @return uint256 The time since the last rotation
     */
    function timeSinceRotation() external view returns (uint256) {
        return block.timestamp - _baseWeightedMultisigStorage().lastRotationTimestamp;
    }

    /*************************\
    |* Integration Functions *|
    \*************************/

    /**
     * @notice This function takes dataHash and proof data and reverts if proof is invalid
     * @param dataHash The hash of the message that was signed
     * @param proof The multisig proof data
     * @return isLatestSigners True if the proof is from the latest signer set
     * @dev The proof data should have signers, weights, threshold and signatures encoded
     *      The proof is only valid if the signers weight crosses the threshold and there are no redundant signatures
     *      The signers and signatures should be sorted by signer address in ascending order
     *      Example: abi.encode([0x11..., 0x22..., 0x33...], [1, 1, 1], 2, [signature1, signature3])
     */
    function _validateProof(bytes32 dataHash, Proof calldata proof) internal view returns (bool isLatestSigners) {
        BaseWeightedMultisigStorage storage slot = _baseWeightedMultisigStorage();

        WeightedSigners calldata signers = proof.signers;

        bytes32 signersHash = keccak256(abi.encode(signers));
        uint256 signerEpoch = slot.epochBySignersHash[signersHash];
        uint256 currentEpoch = slot.epoch;

        isLatestSigners = signerEpoch == currentEpoch;

        if (signerEpoch == 0 || currentEpoch - signerEpoch > previousSignersRetention) revert InvalidSigners();

        bytes32 messageHash = messageHashToSign(signersHash, dataHash);

        _validateSignatures(messageHash, signers, proof.signatures);
    }

    /**
     * @notice This function rotates the current signers with a new set of signers
     * @dev Rotation to repeated signers is not allowed.
     * While the individual signer addresses and weights can be repeated, the nonce must be different.
     * @param newSigners The new weighted signers data
     * @param enforceRotationDelay If true, the minimum rotation delay will be enforced
     * @dev The signers should be sorted by signer address in ascending order
     */
    function _rotateSigners(WeightedSigners memory newSigners, bool enforceRotationDelay) internal {
        BaseWeightedMultisigStorage storage slot = _baseWeightedMultisigStorage();

        _validateSigners(newSigners);

        _updateRotationTimestamp(enforceRotationDelay);

        bytes memory newSignersData = abi.encode(newSigners);
        bytes32 newSignersHash = keccak256(newSignersData);

        // assign the next epoch to the new signers
        uint256 newEpoch = slot.epoch + 1;
        slot.epoch = newEpoch;
        slot.signersHashByEpoch[newEpoch] = newSignersHash;

        // signers must be distinct, since nonce should guarantee uniqueness even if signers are repeated
        if (slot.epochBySignersHash[newSignersHash] != 0) revert DuplicateSigners(newSignersHash);

        slot.epochBySignersHash[newSignersHash] = newEpoch;

        emit SignersRotated(newEpoch, newSignersHash, newSignersData);
    }

    /**********************\
    |* Internal Functions *|
    \**********************/

    /**
     * @dev Updates the last rotation timestamp, and enforces the minimum rotation delay if specified
     */
    function _updateRotationTimestamp(bool enforceRotationDelay) internal {
        uint256 lastRotationTimestamp_ = _baseWeightedMultisigStorage().lastRotationTimestamp;
        uint256 currentTimestamp = block.timestamp;

        if (enforceRotationDelay && (currentTimestamp - lastRotationTimestamp_) < minimumRotationDelay) {
            revert InsufficientRotationDelay(
                minimumRotationDelay,
                lastRotationTimestamp_,
                currentTimestamp - lastRotationTimestamp_
            );
        }

        _baseWeightedMultisigStorage().lastRotationTimestamp = currentTimestamp;
    }

    /**
     * @notice This function takes messageHash and proof data and reverts if proof is invalid
     * @param messageHash The hash of the message that was signed
     * @param weightedSigners The weighted signers data
     * @param signatures The sorted signatures data
     * @dev The signers and signatures should be sorted by signer address in ascending order
     */
    function _validateSignatures(
        bytes32 messageHash,
        WeightedSigners calldata weightedSigners,
        bytes[] calldata signatures
    ) internal pure {
        WeightedSigner[] calldata signers = weightedSigners.signers;
        uint256 signersLength = signers.length;
        uint256 signaturesLength = signatures.length;
        uint256 signerIndex;
        uint256 totalWeight;

        // looking for signers within signers
        // this requires both signers and signatures to be sorted
        // having it sorted allows us to avoid the full inner loop to find a match
        for (uint256 i; i < signaturesLength; ++i) {
            address recoveredSigner = ECDSA.recover(messageHash, signatures[i]);

            // looping through remaining signers to find a match
            for (; signerIndex < signersLength && recoveredSigner != signers[signerIndex].signer; ++signerIndex) {}

            // checking if we are out of signers
            if (signerIndex == signersLength) revert MalformedSignatures();

            // accumulating signatures weight
            totalWeight = totalWeight + signers[signerIndex].weight;

            // weight needs to reach threshold
            if (totalWeight >= weightedSigners.threshold) {
                // validate the proof if there are no redundant signatures
                if (i + 1 == signaturesLength) return;

                revert RedundantSignaturesProvided(i + 1, signaturesLength);
            }

            // increasing signers index if match was found
            ++signerIndex;
        }

        // if weight sum below threshold
        revert LowSignaturesWeight();
    }

    /**
     * @notice Compute the message hash that is signed by the weighted signers
     * @dev Returns an Ethereum Signed Message, created from `domainSeparator`, `signersHash`, and `dataHash`.
     * This replicates the behavior of the
     * https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_sign[`eth_sign`]
     * JSON-RPC method.
     *
     * See {recover}.
     *
     * @param signersHash The hash of the weighted signers that sign off on the data
     * @param dataHash The hash of the data
     * @return The message hash to be signed
     */
    function messageHashToSign(bytes32 signersHash, bytes32 dataHash) public view returns (bytes32) {
        // 96 is the length of the trailing bytes
        return keccak256(bytes.concat('\x19Ethereum Signed Message:\n96', domainSeparator, signersHash, dataHash));
    }

    /**
     * @notice This function checks if the provided signers are valid, i.e sorted and contain no duplicates, with valid weights and threshold
     * @dev If signers are invalid, the method will revert
     * @param weightedSigners The weighted signers
     */
    function _validateSigners(WeightedSigners memory weightedSigners) internal pure {
        WeightedSigner[] memory signers = weightedSigners.signers;
        uint256 length = signers.length;
        uint256 totalWeight;

        if (length == 0) revert InvalidSigners();

        // since signers need to be in strictly increasing order,
        // this prevents address(0) from being a valid signer
        address prevSigner = address(0);

        for (uint256 i = 0; i < length; ++i) {
            WeightedSigner memory weightedSigner = signers[i];
            address currSigner = weightedSigner.signer;

            if (prevSigner >= currSigner) {
                revert InvalidSigners();
            }

            prevSigner = currSigner;

            uint256 weight = weightedSigner.weight;

            if (weight == 0) revert InvalidWeights();

            totalWeight = totalWeight + weight;
        }

        uint128 threshold = weightedSigners.threshold;
        if (threshold == 0 || totalWeight < threshold) revert InvalidThreshold();
    }

    /**
     * @notice Gets the specific storage location for preventing upgrade collisions
     * @return slot containing the BaseWeightedMultisigStorage struct
     */
    function _baseWeightedMultisigStorage() internal pure returns (BaseWeightedMultisigStorage storage slot) {
        assembly {
            slot.slot := BASE_WEIGHTED_MULTISIG_SLOT
        }
    }
}