Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE

More Options

• Similar
• Sol2Uml
• Submit Audit
• Compare

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

import {ECDSA} from "openzeppelin/utils/cryptography/ECDSA.sol";
import {SubstrateMerkleProof} from "./utils/SubstrateMerkleProof.sol";
import {Bitfield} from "./utils/Bitfield.sol";
import {Uint16Array, createUint16Array} from "./utils/Uint16Array.sol";
import {Math} from "./utils/Math.sol";
import {MMRProof} from "./utils/MMRProof.sol";
import {ScaleCodec} from "./utils/ScaleCodec.sol";

/**
 * @title BeefyClient
 * @dev This is a client for verifying BEEFY commitments from the Polkadot network.
 * it contains two ways to verify BEEFY commitments from a Substrate-based chain,
 * one through an interactive protocol, and one through Fiat-Shamir transformation.
 *
 * The interactive protocol is defined in https://eprint.iacr.org/2025/057.pdf. Higher level documentation
 * is available at https://docs.snowbridge.network/architecture/verification/polkadot.
 *
 * To submit new commitments, relayers must call the following methods sequentially:
 * 1. submitInitial: Initializes the session for interactive submission and waits for the Randao delay period
 * 2. commitPrevRandao: Commit to a random seed for generating a validator subsampling
 * 3. createFinalBitfield: Generate the validator subsampling
 * 4. submitFinal: Complete submission after providing the request validator signatures
 *
 *
 * The non-interactive protocol eliminates the need for interaction by applying Fiat-Shamir transform.
 * It is defined in Section 6 of https://eprint.iacr.org/2025/057.pdf, with higher-level documentation
 * available at https://hackmd.io/8Jd7V74iSSeeHOIG76REWw
 *
 * To submit new commitments using the Fiat-Shamir approach, relayers call the following methods sequentially:
 * 1. createFiatShamirFinalBitfield: Generate the validator subsampling using Fiat-Shamir
 * 2. submitFiatShamir: Complete submission after providing the request validator signatures
 */
contract BeefyClient {
    using Math for uint16;
    using Math for uint256;

    /* Events */

    /**
     * @dev Emitted when the MMR root is updated
     * @param mmrRoot the updated MMR root
     * @param blockNumber the beefy block number of the updated MMR root
     */
    event NewMMRRoot(bytes32 mmrRoot, uint64 blockNumber);

    /**
     * @dev Emitted when a new ticket has been created
     * @param relayer The relayer who created the ticket
     * @param blockNumber the parent block number of the candidate MMR root
     */
    event NewTicket(address relayer, uint64 blockNumber);

    /**
     * @dev Interactive session has expired
     */
    event TicketExpired();

    /* Types */

    /**
     * @dev The Commitment, with its payload, is the core thing we are trying to verify with
     * this contract. It contains an MMR root that commits to the polkadot history, including
     * past blocks and parachain blocks and can be used to verify both polkadot and parachain blocks.
     */
    struct Commitment {
        // Relay chain block number
        uint32 blockNumber;
        // ID of the validator set that signed the commitment
        uint64 validatorSetID;
        // The payload of the new commitment in beefy justifications (in
        // our case, this is a new MMR root for all past polkadot blocks)
        PayloadItem[] payload;
    }

    /**
     * @dev Each PayloadItem is a piece of data signed by validators at a particular block.
     */
    struct PayloadItem {
        // An ID that references a description of the data in the payload item.
        // Known payload ids can be found [upstream](https://github.com/paritytech/substrate/blob/fe1f8ba1c4f23931ae89c1ada35efb3d908b50f5/primitives/consensus/beefy/src/payload.rs#L27).
        bytes2 payloadID;
        // The contents of the payload item
        bytes data;
    }

    /**
     * @dev The ValidatorProof is a proof used to verify a commitment signature
     */
    struct ValidatorProof {
        // The parity bit to specify the intended solution
        uint8 v;
        // The x component on the secp256k1 curve
        bytes32 r;
        // The challenge solution
        bytes32 s;
        // Leaf index of the validator address in the merkle tree
        uint256 index;
        // Validator address
        address account;
        // Merkle proof for the validator
        bytes32[] proof;
    }

    /**
     * @dev A ticket tracks working state for the interactive submission of new commitments
     */
    struct Ticket {
        // The block number this ticket was issued
        uint64 blockNumber;
        // Length of the validator set that signed the commitment
        uint32 validatorSetLen;
        // The number of signatures required
        uint32 numRequiredSignatures;
        // The PREVRANDAO seed selected for this ticket session
        uint256 prevRandao;
        // Hash of a bitfield claiming which validators have signed
        bytes32 bitfieldHash;
    }

    /// @dev The MMRLeaf describes the leaf structure of the MMR
    struct MMRLeaf {
        // Version of the leaf type
        uint8 version;
        // Parent number of the block this leaf describes
        uint32 parentNumber;
        // Parent hash of the block this leaf describes
        bytes32 parentHash;
        // Validator set id that will be part of consensus for the next block
        uint64 nextAuthoritySetID;
        // Length of that validator set
        uint32 nextAuthoritySetLen;
        // Merkle root of all public keys in that validator set
        bytes32 nextAuthoritySetRoot;
        // Merkle root of all parachain headers in this block
        bytes32 parachainHeadsRoot;
    }

    /**
     * @dev The ValidatorSet describes a BEEFY validator set
     */
    struct ValidatorSet {
        // Identifier for the set
        uint128 id;
        // Number of validators in the set
        uint128 length;
        // Merkle root of BEEFY validator addresses
        bytes32 root;
    }

    /**
     * @dev The ValidatorSetState describes a BEEFY validator set along with signature usage counters
     */
    struct ValidatorSetState {
        // Identifier for the set
        uint128 id;
        // Number of validators in the set
        uint128 length;
        // Merkle root of BEEFY validator addresses
        bytes32 root;
        // Number of times a validator signature has been used
        Uint16Array usageCounters;
    }

    /* State */

    /// @dev The latest verified MMR root
    bytes32 public latestMMRRoot;

    /// @dev The block number in the relay chain in which the latest MMR root was emitted
    uint64 public latestBeefyBlock;

    /// @dev State of the current validator set
    ValidatorSetState public currentValidatorSet;

    /// @dev State of the next validator set
    ValidatorSetState public nextValidatorSet;

    /// @dev Pending tickets for commitment submission
    mapping(bytes32 ticketID => Ticket) public tickets;

    /* Constants */

    /**
     * @dev Fiat-Shamir domain separator ID
     */
    bytes public constant FIAT_SHAMIR_DOMAIN_ID = bytes("SNOWBRIDGE-FIAT-SHAMIR-v1");

    /**
     * @dev Beefy payload id for MMR Root payload items:
     * https://github.com/paritytech/substrate/blob/fe1f8ba1c4f23931ae89c1ada35efb3d908b50f5/primitives/consensus/beefy/src/payload.rs#L33
     */
    bytes2 public constant MMR_ROOT_ID = bytes2("mh");

    /**
     * @dev Minimum delay in number of blocks that a relayer must wait between calling
     * submitInitial and commitPrevRandao. In production this should be set to MAX_SEED_LOOKAHEAD:
     * https://eth2book.info/altair/part3/config/preset#max_seed_lookahead
     */
    uint256 public immutable randaoCommitDelay;

    /**
     * @dev after randaoCommitDelay is reached, relayer must
     * call commitPrevRandao within this number of blocks.
     * Without this expiration, relayers can roll the dice infinitely to get the subsampling
     * they desire.
     */
    uint256 public immutable randaoCommitExpiration;

    /**
     * @dev The lower bound on the number of signatures required to validate a new commitment. Note
     * that the final number of signatures is calculated dynamically with Randao randomness.
     */
    uint256 public immutable minNumRequiredSignatures;

    /**
     * @dev The signatures required to validate a new commitment using Fiat-Shamir transform. Note
     * that Fiat-shamir comes from the assumption on the hash-power of adversary
     * and its not a crypto-economic argument.
     */
    uint256 public immutable fiatShamirRequiredSignatures;

    /* Errors */
    error InvalidBitfield();
    error InvalidBitfieldLength();
    error InvalidCommitment();
    error InvalidMMRLeaf();
    error InvalidMMRLeafProof();
    error InvalidMMRRootLength();
    error InvalidSignature();
    error InvalidTicket();
    error InvalidValidatorProof();
    error InvalidValidatorProofLength();
    error CommitmentNotRelevant();
    error PrevRandaoAlreadyCaptured();
    error PrevRandaoNotCaptured();
    error StaleCommitment();
    error WaitPeriodNotOver();

    constructor(
        uint256 _randaoCommitDelay,
        uint256 _randaoCommitExpiration,
        uint256 _minNumRequiredSignatures,
        uint256 _fiatShamirRequiredSignatures,
        uint64 _initialBeefyBlock,
        ValidatorSet memory _initialValidatorSet,
        ValidatorSet memory _nextValidatorSet
    ) {
        if (_nextValidatorSet.id != _initialValidatorSet.id + 1) {
            revert("invalid-constructor-params");
        }
        randaoCommitDelay = _randaoCommitDelay;
        randaoCommitExpiration = _randaoCommitExpiration;
        minNumRequiredSignatures = _minNumRequiredSignatures;
        fiatShamirRequiredSignatures = _fiatShamirRequiredSignatures;
        latestBeefyBlock = _initialBeefyBlock;
        currentValidatorSet.id = _initialValidatorSet.id;
        currentValidatorSet.length = _initialValidatorSet.length;
        currentValidatorSet.root = _initialValidatorSet.root;
        currentValidatorSet.usageCounters = createUint16Array(currentValidatorSet.length);
        nextValidatorSet.id = _nextValidatorSet.id;
        nextValidatorSet.length = _nextValidatorSet.length;
        nextValidatorSet.root = _nextValidatorSet.root;
        nextValidatorSet.usageCounters = createUint16Array(nextValidatorSet.length);
    }

    /* External Functions */

    /**
     * @dev Begin submission of commitment
     * @param commitment contains the commitment signed by the validators
     * @param bitfield a bitfield claiming which validators have signed the commitment
     * @param proof a proof that a single validator from currentValidatorSet has signed the commitment
     */
    function submitInitial(
        Commitment calldata commitment,
        uint256[] calldata bitfield,
        ValidatorProof calldata proof
    ) external {
        if (commitment.blockNumber <= latestBeefyBlock) {
            revert StaleCommitment();
        }

        ValidatorSetState storage vset = currentValidatorSet;
        uint16 signatureUsageCount;
        if (commitment.validatorSetID == currentValidatorSet.id) {
            signatureUsageCount = currentValidatorSet.usageCounters.get(proof.index);
            currentValidatorSet.usageCounters
                .set(proof.index, signatureUsageCount.saturatingAdd(1));
        } else if (commitment.validatorSetID == nextValidatorSet.id) {
            signatureUsageCount = nextValidatorSet.usageCounters.get(proof.index);
            nextValidatorSet.usageCounters.set(proof.index, signatureUsageCount.saturatingAdd(1));
            vset = nextValidatorSet;
        } else {
            revert InvalidCommitment();
        }

        // Check if merkle proof is valid based on the validatorSetRoot and if proof is included in bitfield
        if (
            !isValidatorInSet(vset, proof.account, proof.index, proof.proof)
                || !Bitfield.isSet(bitfield, proof.index)
        ) {
            revert InvalidValidatorProof();
        }

        // Check if validatorSignature is correct, ie. check if it matches
        // the signature of senderPublicKey on the commitmentHash
        bytes32 commitmentHash = keccak256(encodeCommitment(commitment));
        if (ECDSA.recover(commitmentHash, proof.v, proof.r, proof.s) != proof.account) {
            revert InvalidSignature();
        }

        // For the initial submission, the supplied bitfield should claim that more than
        // two thirds of the validator set have sign the commitment
        if (
            bitfield.length != Bitfield.containerLength(vset.length)
                || Bitfield.countSetBits(bitfield, vset.length) < computeQuorum(vset.length)
        ) {
            revert InvalidBitfield();
        }

        // Validate that all padding bits (beyond vset.length) are zero
        // This ensures the bitfield was created by createInitialBitfield or equivalent
        Bitfield.validatePadding(bitfield, vset.length);

        tickets[createTicketID(msg.sender, commitmentHash)] = Ticket({
            blockNumber: uint64(block.number),
            validatorSetLen: uint32(vset.length),
            numRequiredSignatures: uint32(
                computeNumRequiredSignatures(
                    vset.length, signatureUsageCount, minNumRequiredSignatures
                )
            ),
            prevRandao: 0,
            bitfieldHash: keccak256(abi.encodePacked(bitfield))
        });

        emit NewTicket(msg.sender, commitment.blockNumber);
    }

    /**
     * @dev Capture PREVRANDAO
     * @param commitmentHash contains the commitmentHash signed by the validators
     */
    function commitPrevRandao(bytes32 commitmentHash) external {
        bytes32 ticketID = createTicketID(msg.sender, commitmentHash);
        Ticket storage ticket = tickets[ticketID];

        if (ticket.blockNumber == 0) {
            revert InvalidTicket();
        }

        if (ticket.prevRandao != 0) {
            revert PrevRandaoAlreadyCaptured();
        }

        // relayer must wait `randaoCommitDelay` blocks
        if (block.number < ticket.blockNumber + randaoCommitDelay) {
            revert WaitPeriodNotOver();
        }

        // relayer can capture within `randaoCommitExpiration` blocks
        if (block.number > ticket.blockNumber + randaoCommitDelay + randaoCommitExpiration) {
            delete tickets[ticketID];
            emit TicketExpired();
            return;
        }

        // Post-merge, the difficulty opcode now returns PREVRANDAO
        ticket.prevRandao = block.prevrandao;
    }

    /**
     * @dev Submit a commitment and leaf for final verification
     * @param commitment contains the full commitment that was used for the commitmentHash
     * @param bitfield claiming which validators have signed the commitment
     * @param proofs a struct containing the data needed to verify all validator signatures
     * @param leaf an MMR leaf provable using the MMR root in the commitment payload
     * @param leafProof an MMR leaf proof
     * @param leafProofOrder a bitfield describing the order of each item (left vs right)
     */
    function submitFinal(
        Commitment calldata commitment,
        uint256[] calldata bitfield,
        ValidatorProof[] calldata proofs,
        MMRLeaf calldata leaf,
        bytes32[] calldata leafProof,
        uint256 leafProofOrder
    ) external {
        bytes32 commitmentHash = keccak256(encodeCommitment(commitment));
        bytes32 ticketID = createTicketID(msg.sender, commitmentHash);
        validateTicket(ticketID, commitment, bitfield);

        bool is_next_session = false;
        ValidatorSetState storage vset = currentValidatorSet;
        if (commitment.validatorSetID == nextValidatorSet.id) {
            is_next_session = true;
            vset = nextValidatorSet;
        } else if (commitment.validatorSetID != currentValidatorSet.id) {
            revert InvalidCommitment();
        }

        // Validate that all padding bits (beyond vset.length) are zero
        // This ensures the bitfield was created by createInitialBitfield or equivalent
        Bitfield.validatePadding(bitfield, vset.length);

        verifyCommitment(commitmentHash, ticketID, bitfield, vset, proofs);

        bytes32 newMMRRoot = ensureProvidesMMRRoot(commitment);

        if (is_next_session) {
            if (leaf.nextAuthoritySetID != nextValidatorSet.id + 1) {
                revert InvalidMMRLeaf();
            }
            bool leafIsValid = MMRProof.verifyLeafProof(
                newMMRRoot, keccak256(encodeMMRLeaf(leaf)), leafProof, leafProofOrder
            );
            if (!leafIsValid) {
                revert InvalidMMRLeafProof();
            }
            currentValidatorSet = nextValidatorSet;
            nextValidatorSet.id = leaf.nextAuthoritySetID;
            nextValidatorSet.length = leaf.nextAuthoritySetLen;
            nextValidatorSet.root = leaf.nextAuthoritySetRoot;
            nextValidatorSet.usageCounters = createUint16Array(leaf.nextAuthoritySetLen);
        }

        latestMMRRoot = newMMRRoot;
        latestBeefyBlock = commitment.blockNumber;
        delete tickets[ticketID];

        emit NewMMRRoot(newMMRRoot, commitment.blockNumber);
    }

    /**
     * @dev Verify that the supplied MMR leaf is included in the latest verified MMR root.
     * @param leafHash contains the merkle leaf to be verified
     * @param proof contains simplified mmr proof
     * @param proofOrder a bitfield describing the order of each item (left vs right)
     */
    function verifyMMRLeafProof(bytes32 leafHash, bytes32[] calldata proof, uint256 proofOrder)
        external
        view
        returns (bool)
    {
        return MMRProof.verifyLeafProof(latestMMRRoot, leafHash, proof, proofOrder);
    }

    /**
     * @dev Helper to create an initial validator bitfield.
     * @param bitsToSet contains indexes of all signed validators, should be deduplicated
     * @param length of validator set
     */
    function createInitialBitfield(uint256[] calldata bitsToSet, uint256 length)
        external
        pure
        returns (uint256[] memory)
    {
        if (length < bitsToSet.length) {
            revert InvalidBitfieldLength();
        }
        return Bitfield.createBitfield(bitsToSet, length);
    }

    /**
     * @dev Helper to create a final bitfield, with subsampled validator selections
     * @param commitmentHash contains the commitmentHash signed by the validators
     * @param bitfield claiming which validators have signed the commitment
     */
    function createFinalBitfield(bytes32 commitmentHash, uint256[] calldata bitfield)
        external
        view
        returns (uint256[] memory)
    {
        Ticket storage ticket = tickets[createTicketID(msg.sender, commitmentHash)];
        if (ticket.bitfieldHash != keccak256(abi.encodePacked(bitfield))) {
            revert InvalidBitfield();
        }
        return Bitfield.subsample(
            ticket.prevRandao, bitfield, ticket.validatorSetLen, ticket.numRequiredSignatures
        );
    }

    /**
     * @dev Helper to create a final bitfield with subsampled validator selections using the Fiat-Shamir approach
     * @param commitment contains the full commitment that was used for the commitmentHash
     * @param bitfield claiming which validators have signed the commitment
     */
    function createFiatShamirFinalBitfield(
        Commitment calldata commitment,
        uint256[] calldata bitfield
    ) external view returns (uint256[] memory) {
        ValidatorSetState storage vset = currentValidatorSet;
        if (commitment.validatorSetID == nextValidatorSet.id) {
            vset = nextValidatorSet;
        } else if (commitment.validatorSetID != currentValidatorSet.id) {
            revert InvalidCommitment();
        }

        if (
            bitfield.length != Bitfield.containerLength(vset.length)
                || Bitfield.countSetBits(bitfield, vset.length) < computeQuorum(vset.length)
        ) {
            revert InvalidBitfield();
        }

        bytes32 commitmentHash = keccak256(encodeCommitment(commitment));

        return fiatShamirFinalBitfield(commitmentHash, bitfield, vset);
    }

    /**
     * @dev Submit a commitment and leaf using the Fiat-Shamir approach
     * @param commitment contains the full commitment that was used for the commitmentHash
     * @param bitfield claiming which validators have signed the commitment
     * @param proofs a struct containing the data needed to verify all validator signatures
     * @param leaf an MMR leaf provable using the MMR root in the commitment payload
     * @param leafProof an MMR leaf proof
     * @param leafProofOrder a bitfield describing the order of each item (left vs right)
     */
    function submitFiatShamir(
        Commitment calldata commitment,
        uint256[] calldata bitfield,
        ValidatorProof[] calldata proofs,
        MMRLeaf calldata leaf,
        bytes32[] calldata leafProof,
        uint256 leafProofOrder
    ) external {
        if (commitment.blockNumber <= latestBeefyBlock) {
            revert StaleCommitment();
        }

        bool is_next_session = false;
        ValidatorSetState storage vset = currentValidatorSet;
        if (commitment.validatorSetID == nextValidatorSet.id) {
            is_next_session = true;
            vset = nextValidatorSet;
        } else if (commitment.validatorSetID != currentValidatorSet.id) {
            revert InvalidCommitment();
        }

        if (
            bitfield.length != Bitfield.containerLength(vset.length)
                || Bitfield.countSetBits(bitfield, vset.length) < computeQuorum(vset.length)
        ) {
            revert InvalidBitfield();
        }
        // Validate that all padding bits (beyond vset.length) are zero
        // This ensures the bitfield was created by createInitialBitfield or equivalent
        Bitfield.validatePadding(bitfield, vset.length);

        bytes32 newMMRRoot = ensureProvidesMMRRoot(commitment);

        bytes32 commitmentHash = keccak256(encodeCommitment(commitment));
        verifyFiatShamirCommitment(commitmentHash, bitfield, vset, proofs);

        if (is_next_session) {
            if (leaf.nextAuthoritySetID != nextValidatorSet.id + 1) {
                revert InvalidMMRLeaf();
            }
            bool leafIsValid = MMRProof.verifyLeafProof(
                newMMRRoot, keccak256(encodeMMRLeaf(leaf)), leafProof, leafProofOrder
            );
            if (!leafIsValid) {
                revert InvalidMMRLeafProof();
            }
            currentValidatorSet = nextValidatorSet;
            nextValidatorSet.id = leaf.nextAuthoritySetID;
            nextValidatorSet.length = leaf.nextAuthoritySetLen;
            nextValidatorSet.root = leaf.nextAuthoritySetRoot;
            nextValidatorSet.usageCounters = createUint16Array(leaf.nextAuthoritySetLen);
        }

        latestMMRRoot = newMMRRoot;
        latestBeefyBlock = commitment.blockNumber;

        emit NewMMRRoot(newMMRRoot, commitment.blockNumber);
    }

    /* Internal Functions */

    // Creates a unique ticket ID for a new interactive prover-verifier session
    function createTicketID(address account, bytes32 commitmentHash)
        internal
        pure
        returns (bytes32 value)
    {
        assembly {
            mstore(0x00, account)
            mstore(0x20, commitmentHash)
            value := keccak256(0x0, 0x40)
        }
    }

    /**
     * @dev Calculates the number of required signatures for `submitFinal`.
     * @param validatorSetLen The length of the validator set
     * @param signatureUsageCount A counter of the number of times the validator signature was previously used in a call to `submitInitial` within the session.
     * @param minRequiredSignatures The minimum amount of signatures to verify
     */
    // For more details on the calculation, read the following:
    // 1. https://docs.snowbridge.network/architecture/verification/polkadot#signature-sampling
    // 2. https://hackmd.io/9OedC7icR5m-in_moUZ_WQ
    function computeNumRequiredSignatures(
        uint256 validatorSetLen,
        uint256 signatureUsageCount,
        uint256 minRequiredSignatures
    ) internal pure returns (uint256) {
        // Start with the minimum number of signatures.
        uint256 numRequiredSignatures = minRequiredSignatures;
        // Add signatures based on the number of validators in the validator set.
        numRequiredSignatures += Math.log2(validatorSetLen, Math.Rounding.Ceil);
        // Add signatures based on the signature usage count.
        numRequiredSignatures += 1 + (2 * Math.log2(signatureUsageCount, Math.Rounding.Ceil));
        // Never require more signatures than a 1/3 + 1 which is sufficient to ensure at least one honest validator.
        return Math.min(numRequiredSignatures, computeMaxRequiredSignatures(validatorSetLen));
    }

    /**
     * @dev Calculates 2/3 majority required for quorum for a given number of validators.
     * @param numValidators The number of validators in the validator set.
     */
    function computeQuorum(uint256 numValidators) internal pure returns (uint256) {
        return numValidators - (numValidators - 1) / 3;
    }

    /**
     * @dev We have 2/3rd +1 honesty assumption on polkadot validators. Hence it is sufficient (for both random sampling and Fiat Shamir) to check 1/3rd +1 validator signatures to ensure at least 1 honest validator signed the payload.
     * @param numValidators The number of validators in the validator set.
     */
    function computeMaxRequiredSignatures(uint256 numValidators) internal pure returns (uint256) {
        return numValidators / 3 + 1;
    }

    /**
     * @dev Verify commitment using the supplied signature proofs
     */
    function verifyCommitment(
        bytes32 commitmentHash,
        bytes32 ticketID,
        uint256[] calldata bitfield,
        ValidatorSetState storage vset,
        ValidatorProof[] calldata proofs
    ) internal view {
        Ticket storage ticket = tickets[ticketID];
        // Verify that enough signature proofs have been supplied
        uint256 numRequiredSignatures = ticket.numRequiredSignatures;
        if (proofs.length != numRequiredSignatures) {
            revert InvalidValidatorProofLength();
        }

        // Generate final bitfield indicating which validators need to be included in the proofs.
        uint256[] memory finalbitfield =
            Bitfield.subsample(ticket.prevRandao, bitfield, vset.length, numRequiredSignatures);

        for (uint256 i = 0; i < proofs.length; i++) {
            ValidatorProof calldata proof = proofs[i];

            // Check that validator is actually in a validator set
            if (!isValidatorInSet(vset, proof.account, proof.index, proof.proof)) {
                revert InvalidValidatorProof();
            }

            // Check that validator is in bitfield
            if (!Bitfield.isSet(finalbitfield, proof.index)) {
                revert InvalidValidatorProof();
            }

            // Check that validator signed the commitment
            if (ECDSA.recover(commitmentHash, proof.v, proof.r, proof.s) != proof.account) {
                revert InvalidSignature();
            }

            // Ensure no validator can appear more than once in bitfield
            Bitfield.unset(finalbitfield, proof.index);
        }
    }

    /**
     * @dev Verify commitment with the sampled signatures using the Fiat-Shamir hash
     */
    function verifyFiatShamirCommitment(
        bytes32 commitmentHash,
        uint256[] calldata bitfield,
        ValidatorSetState storage vset,
        ValidatorProof[] calldata proofs
    ) internal view {
        uint256 requiredSignatures = Math.min(
            fiatShamirRequiredSignatures, computeMaxRequiredSignatures(vset.length)
        );
        if (proofs.length != requiredSignatures) {
            revert InvalidValidatorProofLength();
        }

        uint256[] memory finalbitfield = fiatShamirFinalBitfield(commitmentHash, bitfield, vset);

        for (uint256 i = 0; i < proofs.length; i++) {
            ValidatorProof calldata proof = proofs[i];

            // Check that validator is in bitfield
            if (!Bitfield.isSet(finalbitfield, proof.index)) {
                revert InvalidValidatorProof();
            }

            // Check that validator is actually in a validator set
            if (!isValidatorInSet(vset, proof.account, proof.index, proof.proof)) {
                revert InvalidValidatorProof();
            }

            // Check that validator signed the commitment
            if (ECDSA.recover(commitmentHash, proof.v, proof.r, proof.s) != proof.account) {
                revert InvalidSignature();
            }

            // Ensure no validator can appear more than once in bitfield
            Bitfield.unset(finalbitfield, proof.index);
        }
    }

    function createFiatShamirHash(
        bytes32 commitmentHash,
        bytes32 bitFieldHash,
        ValidatorSetState storage vset
    ) internal view returns (bytes32) {
        return sha256(
            bytes.concat(
                FIAT_SHAMIR_DOMAIN_ID,
                sha256(
                    bytes.concat(
                        commitmentHash,
                        bitFieldHash,
                        vset.root,
                        bytes32(uint256(vset.id)),
                        bytes32(uint256(vset.length))
                    )
                )
            )
        );
    }

    /**
     * @dev Helper to create a final bitfield with subsampled validator selections using the Fiat-Shamir approach
     * @param commitmentHash the hash of the full commitment that was used for the commitmentHash
     * @param bitfield claiming which validators have signed the commitment
     * @param vset the validator set state
     */
    function fiatShamirFinalBitfield(
        bytes32 commitmentHash,
        uint256[] calldata bitfield,
        ValidatorSetState storage vset
    ) internal view returns (uint256[] memory) {
        bytes32 bitFieldHash = keccak256(abi.encodePacked(bitfield));
        bytes32 fiatShamirHash = createFiatShamirHash(commitmentHash, bitFieldHash, vset);
        uint256 requiredSignatures =
            Math.min(fiatShamirRequiredSignatures, computeMaxRequiredSignatures(vset.length));
        return
            Bitfield.subsample(uint256(fiatShamirHash), bitfield, vset.length, requiredSignatures);
    }

    // Ensure that the commitment provides a new MMR root
    function ensureProvidesMMRRoot(Commitment calldata commitment)
        internal
        pure
        returns (bytes32)
    {
        if (commitment.payload.length != 1) {
            revert CommitmentNotRelevant();
        }
        PayloadItem memory payload = commitment.payload[0];
        if (payload.payloadID != MMR_ROOT_ID || payload.data.length != 32) {
            revert CommitmentNotRelevant();
        }
        return bytes32(payload.data);
    }

    function encodeCommitment(Commitment calldata commitment)
        internal
        pure
        returns (bytes memory)
    {
        return bytes.concat(
            encodeCommitmentPayload(commitment.payload),
            ScaleCodec.encodeU32(commitment.blockNumber),
            ScaleCodec.encodeU64(commitment.validatorSetID)
        );
    }

    function encodeCommitmentPayload(PayloadItem[] calldata items)
        internal
        pure
        returns (bytes memory)
    {
        bytes memory payload = ScaleCodec.checkedEncodeCompactU32(items.length);
        for (uint256 i = 0; i < items.length; i++) {
            payload = bytes.concat(
                payload,
                items[i].payloadID,
                ScaleCodec.checkedEncodeCompactU32(items[i].data.length),
                items[i].data
            );
        }

        return payload;
    }

    function encodeMMRLeaf(MMRLeaf calldata leaf) internal pure returns (bytes memory) {
        return bytes.concat(
            ScaleCodec.encodeU8(leaf.version),
            ScaleCodec.encodeU32(leaf.parentNumber),
            leaf.parentHash,
            ScaleCodec.encodeU64(leaf.nextAuthoritySetID),
            ScaleCodec.encodeU32(leaf.nextAuthoritySetLen),
            leaf.nextAuthoritySetRoot,
            leaf.parachainHeadsRoot
        );
    }

    /**
     * @dev Checks if a validators address is a member of the merkle tree
     * @param vset The validator set
     * @param account The address of the validator to check for inclusion in `vset`.
     * @param index The leaf index of the account in the merkle tree of validator set addresses.
     * @param proof Merkle proof required for validation of the address
     * @return true if the validator is in the set
     */
    function isValidatorInSet(
        ValidatorSetState storage vset,
        address account,
        uint256 index,
        bytes32[] calldata proof
    ) internal view returns (bool) {
        bytes32 hashedLeaf = keccak256(abi.encodePacked(account));
        return SubstrateMerkleProof.verify(vset.root, hashedLeaf, index, vset.length, proof);
    }

    /**
     * @dev Basic validation of a ticket for submitFinal
     */
    function validateTicket(
        bytes32 ticketID,
        Commitment calldata commitment,
        uint256[] calldata bitfield
    ) internal view {
        Ticket storage ticket = tickets[ticketID];

        if (ticket.blockNumber == 0) {
            // submitInitial hasn't been called yet
            revert InvalidTicket();
        }

        if (ticket.prevRandao == 0) {
            // commitPrevRandao hasn't been called yet
            revert PrevRandaoNotCaptured();
        }

        if (commitment.blockNumber <= latestBeefyBlock) {
            // ticket is obsolete
            revert StaleCommitment();
        }

        if (ticket.bitfieldHash != keccak256(abi.encodePacked(bitfield))) {
            // The provided claims bitfield isn't the same one that was
            // passed to submitInitial
            revert InvalidBitfield();
        }
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.5.0) (utils/cryptography/ECDSA.sol)

pragma solidity ^0.8.20;

/**
 * @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 {
    enum RecoverError {
        NoError,
        InvalidSignature,
        InvalidSignatureLength,
        InvalidSignatureS
    }

    /**
     * @dev The signature is invalid.
     */
    error ECDSAInvalidSignature();

    /**
     * @dev The signature has an invalid length.
     */
    error ECDSAInvalidSignatureLength(uint256 length);

    /**
     * @dev The signature has an S value that is in the upper half order.
     */
    error ECDSAInvalidSignatureS(bytes32 s);

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with `signature` or an error. This will not
     * return address(0) without also returning an error description. Errors are documented using an enum (error type)
     * and a bytes32 providing additional information about the error.
     *
     * If no error is returned, then the address can be used for verification purposes.
     *
     * The `ecrecover` EVM precompile 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.
     *
     * NOTE: This function only supports 65-byte signatures. ERC-2098 short signatures are rejected. This restriction
     * is DEPRECATED and will be removed in v6.0. Developers SHOULD NOT use signatures as unique identifiers; use hash
     * invalidation or nonces for replay protection.
     *
     * 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 {MessageHashUtils-toEthSignedMessageHash} on it.
     *
     * Documentation for signature generation:
     *
     * - with https://web3js.readthedocs.io/en/v1.3.4/web3-eth-accounts.html#sign[Web3.js]
     * - with https://docs.ethers.io/v5/api/signer/#Signer-signMessage[ethers]
     */
    function tryRecover(
        bytes32 hash,
        bytes memory signature
    ) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
        if (signature.length == 65) {
            bytes32 r;
            bytes32 s;
            uint8 v;
            // ecrecover takes the signature parameters, and the only way to get them
            // currently is to use assembly.
            assembly ("memory-safe") {
                r := mload(add(signature, 0x20))
                s := mload(add(signature, 0x40))
                v := byte(0, mload(add(signature, 0x60)))
            }
            return tryRecover(hash, v, r, s);
        } else {
            return (address(0), RecoverError.InvalidSignatureLength, bytes32(signature.length));
        }
    }

    /**
     * @dev Variant of {tryRecover} that takes a signature in calldata
     */
    function tryRecoverCalldata(
        bytes32 hash,
        bytes calldata signature
    ) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
        if (signature.length == 65) {
            bytes32 r;
            bytes32 s;
            uint8 v;
            // ecrecover takes the signature parameters, calldata slices would work here, but are
            // significantly more expensive (length check) than using calldataload in assembly.
            assembly ("memory-safe") {
                r := calldataload(signature.offset)
                s := calldataload(add(signature.offset, 0x20))
                v := byte(0, calldataload(add(signature.offset, 0x40)))
            }
            return tryRecover(hash, v, r, s);
        } else {
            return (address(0), RecoverError.InvalidSignatureLength, bytes32(signature.length));
        }
    }

    /**
     * @dev Returns the address that signed a hashed message (`hash`) with
     * `signature`. This address can then be used for verification purposes.
     *
     * The `ecrecover` EVM precompile 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.
     *
     * NOTE: This function only supports 65-byte signatures. ERC-2098 short signatures are rejected. This restriction
     * is DEPRECATED and will be removed in v6.0. Developers SHOULD NOT use signatures as unique identifiers; use hash
     * invalidation or nonces for replay protection.
     *
     * 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 {MessageHashUtils-toEthSignedMessageHash} on it.
     */
    function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, signature);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Variant of {recover} that takes a signature in calldata
     */
    function recoverCalldata(bytes32 hash, bytes calldata signature) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecoverCalldata(hash, signature);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `r` and `vs` short-signature fields separately.
     *
     * See https://eips.ethereum.org/EIPS/eip-2098[ERC-2098 short signatures]
     */
    function tryRecover(
        bytes32 hash,
        bytes32 r,
        bytes32 vs
    ) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
        unchecked {
            bytes32 s = vs & bytes32(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
            // We do not check for an overflow here since the shift operation results in 0 or 1.
            uint8 v = uint8((uint256(vs) >> 255) + 27);
            return tryRecover(hash, v, r, s);
        }
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `r` and `vs` short-signature fields separately.
     */
    function recover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, r, vs);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Overload of {ECDSA-tryRecover} that receives the `v`,
     * `r` and `s` signature fields separately.
     */
    function tryRecover(
        bytes32 hash,
        uint8 v,
        bytes32 r,
        bytes32 s
    ) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
        // 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 (301): 0 < s < secp256k1n ÷ 2 + 1, and for v in (302): 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) {
            return (address(0), RecoverError.InvalidSignatureS, s);
        }

        // If the signature is valid (and not malleable), return the signer address
        address signer = ecrecover(hash, v, r, s);
        if (signer == address(0)) {
            return (address(0), RecoverError.InvalidSignature, bytes32(0));
        }

        return (signer, RecoverError.NoError, bytes32(0));
    }

    /**
     * @dev Overload of {ECDSA-recover} that receives the `v`,
     * `r` and `s` signature fields separately.
     */
    function recover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) internal pure returns (address) {
        (address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, v, r, s);
        _throwError(error, errorArg);
        return recovered;
    }

    /**
     * @dev Parse a signature into its `v`, `r` and `s` components. Supports 65-byte and 64-byte (ERC-2098)
     * formats. Returns (0,0,0) for invalid signatures.
     *
     * For 64-byte signatures, `v` is automatically normalized to 27 or 28.
     * For 65-byte signatures, `v` is returned as-is and MUST already be 27 or 28 for use with ecrecover.
     *
     * Consider validating the result before use, or use {tryRecover}/{recover} which perform full validation.
     */
    function parse(bytes memory signature) internal pure returns (uint8 v, bytes32 r, bytes32 s) {
        assembly ("memory-safe") {
            // Check the signature length
            switch mload(signature)
            // - case 65: r,s,v signature (standard)
            case 65 {
                r := mload(add(signature, 0x20))
                s := mload(add(signature, 0x40))
                v := byte(0, mload(add(signature, 0x60)))
            }
            // - case 64: r,vs signature (cf https://eips.ethereum.org/EIPS/eip-2098)
            case 64 {
                let vs := mload(add(signature, 0x40))
                r := mload(add(signature, 0x20))
                s := and(vs, shr(1, not(0)))
                v := add(shr(255, vs), 27)
            }
            default {
                r := 0
                s := 0
                v := 0
            }
        }
    }

    /**
     * @dev Variant of {parse} that takes a signature in calldata
     */
    function parseCalldata(bytes calldata signature) internal pure returns (uint8 v, bytes32 r, bytes32 s) {
        assembly ("memory-safe") {
            // Check the signature length
            switch signature.length
            // - case 65: r,s,v signature (standard)
            case 65 {
                r := calldataload(signature.offset)
                s := calldataload(add(signature.offset, 0x20))
                v := byte(0, calldataload(add(signature.offset, 0x40)))
            }
            // - case 64: r,vs signature (cf https://eips.ethereum.org/EIPS/eip-2098)
            case 64 {
                let vs := calldataload(add(signature.offset, 0x20))
                r := calldataload(signature.offset)
                s := and(vs, shr(1, not(0)))
                v := add(shr(255, vs), 27)
            }
            default {
                r := 0
                s := 0
                v := 0
            }
        }
    }

    /**
     * @dev Optionally reverts with the corresponding custom error according to the `error` argument provided.
     */
    function _throwError(RecoverError error, bytes32 errorArg) private pure {
        if (error == RecoverError.NoError) {
            return; // no error: do nothing
        } else if (error == RecoverError.InvalidSignature) {
            revert ECDSAInvalidSignature();
        } else if (error == RecoverError.InvalidSignatureLength) {
            revert ECDSAInvalidSignatureLength(uint256(errorArg));
        } else if (error == RecoverError.InvalidSignatureS) {
            revert ECDSAInvalidSignatureS(errorArg);
        }
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

// Used to verify merkle proofs generated by https://github.com/paritytech/substrate/tree/master/utils/binary-merkle-tree
library SubstrateMerkleProof {
    /**
     * @notice Verify that a specific leaf element is part of the Merkle Tree at a specific position in the tree
     *
     * The tree would have been constructed using
     * https://paritytech.github.io/substrate/master/binary_merkle_tree/fn.merkle_root.html
     *
     * This implementation adapted from
     * https://paritytech.github.io/substrate/master/binary_merkle_tree/fn.verify_proof.html
     *
     * @param root the root of the merkle tree
     * @param leaf the leaf which needs to be proven
     * @param position the position of the leaf, index starting with 0
     * @param width the width or number of leaves in the tree
     * @param proof the array of proofs to help verify the leaf's membership, ordered from leaf to root
     * @return a boolean value representing the success or failure of the operation
     */
    function verify(
        bytes32 root,
        bytes32 leaf,
        uint256 position,
        uint256 width,
        bytes32[] calldata proof
    ) internal pure returns (bool) {
        if (position >= width) {
            return false;
        }
        return root == computeRoot(leaf, position, width, proof);
    }

    function computeRoot(bytes32 leaf, uint256 position, uint256 width, bytes32[] calldata proof)
        internal
        pure
        returns (bytes32)
    {
        bytes32 node = leaf;
        unchecked {
            for (uint256 i = 0; i < proof.length; i++) {
                if (position & 1 == 1 || position + 1 == width) {
                    node = efficientHash(proof[i], node);
                } else {
                    node = efficientHash(node, proof[i]);
                }
                position = position >> 1;
                width = ((width - 1) >> 1) + 1;
            }
            return node;
        }
    }

    function efficientHash(bytes32 a, bytes32 b) internal pure returns (bytes32 value) {
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, a)
            mstore(0x20, b)
            value := keccak256(0x00, 0x40)
        }
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

import {Bits} from "./Bits.sol";

library Bitfield {
    using Bits for uint256;

    error InvalidSamplingParams();
    error InvalidBitfieldPadding();

    /**
     * @dev Constants used to efficiently calculate the hamming weight of a bitfield. See
     * https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation for an explanation of those constants.
     */
    uint256 internal constant M1 =
        0x5555555555555555555555555555555555555555555555555555555555555555;
    uint256 internal constant M2 =
        0x3333333333333333333333333333333333333333333333333333333333333333;
    uint256 internal constant M4 =
        0x0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f;
    uint256 internal constant M8 =
        0x00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff;
    uint256 internal constant M16 =
        0x0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff;
    uint256 internal constant M32 =
        0x00000000ffffffff00000000ffffffff00000000ffffffff00000000ffffffff;
    uint256 internal constant M64 =
        0x0000000000000000ffffffffffffffff0000000000000000ffffffffffffffff;
    uint256 internal constant M128 =
        0x00000000000000000000000000000000ffffffffffffffffffffffffffffffff;

    uint256 internal constant ONE = uint256(1);

    /**
     * @dev Core subsampling algorithm. Draws a random number, derives an index in the bitfield,
     * and sets the bit if it is in the `priorBitfield` and not yet set. Repeats that `n` times.
     * @param seed Source of randomness for selecting validator signatures.
     * @param priorBitfield Bitfield indicating which validators claim to have signed the commitment.
     * @param priorBitfieldSize Number of bits in priorBitfield Must be <= priorBitfield.length * 256.
     * @param n Number of unique bits in priorBitfield that must be set in the output.
     *          Must be <= number of set bits in priorBitfield.
     */
    function subsample(
        uint256 seed,
        uint256[] memory priorBitfield,
        uint256 priorBitfieldSize,
        uint256 n
    ) internal pure returns (uint256[] memory outputBitfield) {
        if (
            priorBitfield.length != Bitfield.containerLength(priorBitfieldSize)
                || n > countSetBits(priorBitfield, priorBitfieldSize)
        ) {
            revert InvalidSamplingParams();
        }

        outputBitfield = new uint256[](priorBitfield.length);
        uint256 found = 0;

        for (uint256 i = 0; found < n;) {
            uint256 index = makeIndex(seed, i, priorBitfieldSize);

            // require randomly selected bit to be set in priorBitfield and not yet set in bitfield
            if (!isSet(priorBitfield, index) || isSet(outputBitfield, index)) {
                unchecked {
                    i++;
                }
                continue;
            }

            set(outputBitfield, index);

            unchecked {
                found++;
                i++;
            }
        }
    }

    /**
     * @dev Helper to create a bitfield.
     */
    function createBitfield(uint256[] calldata bitsToSet, uint256 length)
        internal
        pure
        returns (uint256[] memory bitfield)
    {
        bitfield = new uint256[](containerLength(length));

        for (uint256 i = 0; i < bitsToSet.length; i++) {
            set(bitfield, bitsToSet[i]);
        }

        return bitfield;
    }

    /**
     * @notice Calculates the number of set bits by using the hamming weight of the bitfield.
     * The algorithm below is implemented after https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
     * Further improvements are possible, see the article above.
     */
    function countSetBits(uint256[] memory self) internal pure returns (uint256) {
        unchecked {
            uint256 count = 0;
            for (uint256 i = 0; i < self.length; i++) {
                uint256 x = self[i];
                x = (x & M1) + ((x >> 1) & M1); //put count of each  2 bits into those  2 bits
                x = (x & M2) + ((x >> 2) & M2); //put count of each  4 bits into those  4 bits
                x = (x & M4) + ((x >> 4) & M4); //put count of each  8 bits into those  8 bits
                x = (x & M8) + ((x >> 8) & M8); //put count of each 16 bits into those 16 bits
                x = (x & M16) + ((x >> 16) & M16); //put count of each 32 bits into those 32 bits
                x = (x & M32) + ((x >> 32) & M32); //put count of each 64 bits into those 64 bits
                x = (x & M64) + ((x >> 64) & M64); //put count of each 128 bits into those 128 bits
                x = (x & M128) + ((x >> 128) & M128); //put count of each 256 bits into those 256 bits
                count += x;
            }
            return count;
        }
    }

    /**
     * @notice Calculates the number of set bits in the first `maxBits` bits of the bitfield.
     * This is a bounded variant of `countSetBits` that only counts bits within the specified range.
     *
     * @dev Example usage:
     * If a bitfield has bits set at positions [0, 5, 10, 256, 300]:
     * - countSetBits(bitfield, 11) returns 3 (bits 0, 5, 10)
     * - countSetBits(bitfield, 257) returns 4 (bits 0, 5, 10, 256)
     * - countSetBits(bitfield, 1000) returns 5 (all bits)
     *
     * @param self The bitfield to count bits in
     * @param maxBits The maximum number of bits to count (counting from bit 0)
     * @return count The number of set bits in the first `maxBits` positions
     */
    function countSetBits(uint256[] memory self, uint256 maxBits) internal pure returns (uint256) {
        if (maxBits == 0 || self.length == 0) {
            return 0;
        }

        unchecked {
            uint256 count = 0;
            uint256 fullElements = maxBits / 256;
            uint256 remainingBits = maxBits % 256;

            // Count bits in full 256-bit elements
            for (uint256 i = 0; i < fullElements && i < self.length; i++) {
                uint256 x = self[i];
                x = (x & M1) + ((x >> 1) & M1); //put count of each  2 bits into those  2 bits
                x = (x & M2) + ((x >> 2) & M2); //put count of each  4 bits into those  4 bits
                x = (x & M4) + ((x >> 4) & M4); //put count of each  8 bits into those  8 bits
                x = (x & M8) + ((x >> 8) & M8); //put count of each 16 bits into those 16 bits
                x = (x & M16) + ((x >> 16) & M16); //put count of each 32 bits into those 32 bits
                x = (x & M32) + ((x >> 32) & M32); //put count of each 64 bits into those 64 bits
                x = (x & M64) + ((x >> 64) & M64); //put count of each 128 bits into those 128 bits
                x = (x & M128) + ((x >> 128) & M128); //put count of each 256 bits into those 256 bits
                count += x;
            }

            // Count bits in the partial element (if any)
            if (remainingBits > 0 && fullElements < self.length) {
                uint256 mask = (ONE << remainingBits) - 1;
                uint256 x = self[fullElements] & mask;
                x = (x & M1) + ((x >> 1) & M1);
                x = (x & M2) + ((x >> 2) & M2);
                x = (x & M4) + ((x >> 4) & M4);
                x = (x & M8) + ((x >> 8) & M8);
                x = (x & M16) + ((x >> 16) & M16);
                x = (x & M32) + ((x >> 32) & M32);
                x = (x & M64) + ((x >> 64) & M64);
                x = (x & M128) + ((x >> 128) & M128);
                count += x;
            }

            return count;
        }
    }

    function isSet(uint256[] memory self, uint256 index) internal pure returns (bool) {
        uint256 element = index >> 8;
        return self[element].bit(uint8(index)) == 1;
    }

    function set(uint256[] memory self, uint256 index) internal pure {
        uint256 element = index >> 8;
        self[element] = self[element].setBit(uint8(index));
    }

    function unset(uint256[] memory self, uint256 index) internal pure {
        uint256 element = index >> 8;
        self[element] = self[element].clearBit(uint8(index));
    }

    function makeIndex(uint256 seed, uint256 iteration, uint256 length)
        internal
        pure
        returns (uint256 index)
    {
        // Handle case where length is 0 to prevent infinite loop in subsample
        if (length == 0) {
            return 0;
        }

        assembly {
            mstore(0x00, seed)
            mstore(0x20, iteration)
            index := mod(keccak256(0x00, 0x40), length)
        }
    }

    // Calculate length of uint256 bitfield array based on rounding up to number of uint256 needed
    function containerLength(uint256 bitfieldSize) internal pure returns (uint256) {
        return (bitfieldSize + 255) / 256;
    }

    /**
     * @dev Validate that all padding bits in the bitfield (beyond length) are zero.
     * @param bitfield The bitfield to validate
     * @param length The number of valid bits (padding starts after this)
     */
    function validatePadding(uint256[] memory bitfield, uint256 length) internal pure {
        uint256 containerLen = containerLength(length);
        if (containerLen == 0 || bitfield.length == 0) {
            return;
        }

        // Check if there are padding bits in the last element
        uint256 validBitsInLastElement = length % 256;
        if (validBitsInLastElement == 0) {
            // All bits in last element are valid, no padding
            return;
        }

        // Create a mask for padding bits: all bits from validBitsInLastElement to 255
        uint256 paddingMask = type(uint256).max << validBitsInLastElement;
        uint256 lastElement = bitfield[containerLen - 1];
        if ((lastElement & paddingMask) != 0) {
            revert InvalidBitfieldPadding();
        }
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

/**
 * @title A utility library for 16 bit counters packed in 256 bit array.
 * @dev The BeefyClient needs to store a count of how many times a validators signature is used. In solidity
 * a uint16 would take up as much space as a uin256 in storage, making storing counters for 1000 validators
 * expensive in terms of gas. The BeefyClient only needs 16 bits per counter. This library allows us to pack
 * 16 uint16 into a single uint256 and save 16x storage.
 *
 * Layout of 32 counters (2 uint256)
 * We store all counts in a single large uint256 array and convert from index from the logical uint16 array
 * to the physical uint256 array.
 *
 *           0                                               1                                               2
 * uint256[] |-- -- -- -- -- -- -- -- -- -- -- -- YY -- -- --|-- -- -- -- -- -- XX -- -- -- -- -- -- -- -- --|
 * uint16[]  |--|--|--|--|--|--|--|--|--|--|--|--|YY|--|--|--|--|--|--|--|--|--|XX|--|--|--|--|--|--|--|--|--|
 *           0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 *
 * Logical Index Layout
 * We use the first 4
 * |-------...---------|----|
 * 256                 4    0
 *        ^index          ^bit-index
 *
 * In the above table counter YY is at logical index 12 in the uint16 array. It will convert to a physical
 * index of 0 in the physical uint256 array and then to bit-index of 192 to 207 of that uint256. In the
 * above table counter XX is at logical index 22. It will convert to a physical index of 1 in the array and
 * then to bit-index 96 to 111 of uint256[1].
 */
using {get, set} for Uint16Array global;

error IndexOutOfBounds();

/**
 * @dev stores the backing array and the length.
 */
struct Uint16Array {
    uint256[] data;
    uint256 length;
}

/**
 * @dev Creates a new counter which can store at least `length` counters.
 * @param length The amount of counters.
 */
function createUint16Array(uint256 length) pure returns (Uint16Array memory) {
    // create space for `length` elements and round up if needed.
    uint256 bufferLength = length / 16 + (length % 16 == 0 ? 0 : 1);
    return Uint16Array({data: new uint256[](bufferLength), length: length});
}

/**
 * @dev Gets the counter at the logical index
 * @param self The array.
 * @param index The logical index.
 */
function get(Uint16Array storage self, uint256 index) view returns (uint16) {
    if (index >= self.length) {
        revert IndexOutOfBounds();
    }
    // Right-shift the index by 4. This truncates the first 4 bits (bit-index) leaving us with the index
    // into the array.
    uint256 element = index >> 4;
    // Mask out the first 4 bits of the logical index to give us the bit-index.
    uint8 inside = uint8(index) & 0x0F;
    // find the element in the array, shift until its bit index and mask to only take the first 16 bits.
    return uint16((self.data[element] >> (16 * inside)) & 0xFFFF);
}

/**
 * @dev Sets the counter at the logical index.
 * @param self The array.
 * @param index The logical index of the counter in the array.
 * @param value The value to set the counter to.
 */
function set(Uint16Array storage self, uint256 index, uint16 value) {
    if (index >= self.length) {
        revert IndexOutOfBounds();
    }
    // Right-shift the index by 4. This truncates the first 4 bits (bit-index) leaving us with the index
    // into the array.
    uint256 element = index >> 4;
    // Mask out the first 4 bytes of the logical index to give us the bit-index.
    uint8 inside = uint8(index) & 0x0F;
    // Create a zero mask which will clear the existing value at the bit-index.
    uint256 zero = ~(uint256(0xFFFF) << (16 * inside));
    // Shift the value to the bit index.
    uint256 shiftedValue = uint256(value) << (16 * inside);
    // Take the element, apply the zero mask to clear the existing value, and then apply the shifted value with bitwise or.
    self.data[element] = self.data[element] & zero | shiftedValue;
}

// SPDX-License-Identifier: MIT
// SPDX-FileCopyrightText: 2023 OpenZeppelin
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
// Code from https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/utils/math/Math.sol
pragma solidity 0.8.28;

/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library Math {
    enum Rounding {
        Floor, // Toward negative infinity
        Ceil, // Toward positive infinity
        Trunc, // Toward zero
        Expand // Away from zero

    }

    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }

    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }

    /**
     * @dev Return the log in base 2 of a positive value rounded towards zero.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }

    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (unsignedRoundsUp(rounding) && 1 << result < value ? 1 : 0);
        }
    }

    /**
     * @dev Returns whether a provided rounding mode is considered rounding up for unsigned integers.
     */
    function unsignedRoundsUp(Rounding rounding) internal pure returns (bool) {
        return uint8(rounding) % 2 == 1;
    }

    /**
     * @dev Safely adds two unsigned 16-bit integers, preventing overflow by saturating to max uint16.
     */
    function saturatingAdd(uint16 a, uint16 b) internal pure returns (uint16) {
        unchecked {
            uint16 c = a + b;
            if (c < a) {
                return 0xFFFF;
            }
            return c;
        }
    }

    /**
     * @dev Safely subtracts two unsigned 256-bit integers, preventing overflow by saturating to min uint256.
     */
    function saturatingSub(uint256 a, uint256 b) internal pure returns (uint256) {
        unchecked {
            if (b >= a) {
                return 0;
            }
            return a - b;
        }
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

library MMRProof {
    error ProofSizeExceeded();

    uint256 internal constant MAXIMUM_PROOF_SIZE = 256;

    /**
     * @dev Verify inclusion of a leaf in an MMR
     * @param root MMR root hash
     * @param leafHash leaf hash
     * @param proof an array of hashes
     * @param proofOrder a bitfield describing the order of each item (left vs right)
     */
    function verifyLeafProof(
        bytes32 root,
        bytes32 leafHash,
        bytes32[] calldata proof,
        uint256 proofOrder
    ) internal pure returns (bool) {
        // Size of the proof is bounded, since `proofOrder` can only contain `MAXIMUM_PROOF_SIZE` orderings.
        if (proof.length > MAXIMUM_PROOF_SIZE) {
            revert ProofSizeExceeded();
        }

        bytes32 acc = leafHash;
        for (uint256 i = 0; i < proof.length; i++) {
            acc = hashPairs(acc, proof[i], (proofOrder >> i) & 1);
        }
        return root == acc;
    }

    function hashPairs(bytes32 x, bytes32 y, uint256 order)
        internal
        pure
        returns (bytes32 value)
    {
        assembly {
            switch order
            case 0 {
                mstore(0x00, x)
                mstore(0x20, y)
            }
            default {
                mstore(0x00, y)
                mstore(0x20, x)
            }
            value := keccak256(0x0, 0x40)
        }
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
pragma solidity 0.8.28;

library ScaleCodec {
    error UnsupportedCompactEncoding();

    uint256 internal constant MAX_COMPACT_ENCODABLE_UINT = 2 ** 30 - 1;

    // Sources:
    //   * https://ethereum.stackexchange.com/questions/15350/how-to-convert-an-bytes-to-address-in-solidity/50528
    //   * https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

    function reverse256(uint256 input) internal pure returns (uint256 v) {
        v = input;

        // swap bytes
        v = ((v & 0xFF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00) >> 8)
            | ((v & 0x00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF) << 8);

        // swap 2-byte long pairs
        v = ((v & 0xFFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000) >> 16)
            | ((v & 0x0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF) << 16);

        // swap 4-byte long pairs
        v = ((v & 0xFFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000) >> 32)
            | ((v & 0x00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF) << 32);

        // swap 8-byte long pairs
        v = ((v & 0xFFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000) >> 64)
            | ((v & 0x0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF) << 64);

        // swap 16-byte long pairs
        v = (v >> 128) | (v << 128);
    }

    function reverse128(uint128 input) internal pure returns (uint128 v) {
        v = input;

        // swap bytes
        v = ((v & 0xFF00FF00FF00FF00FF00FF00FF00FF00) >> 8)
            | ((v & 0x00FF00FF00FF00FF00FF00FF00FF00FF) << 8);

        // swap 2-byte long pairs
        v = ((v & 0xFFFF0000FFFF0000FFFF0000FFFF0000) >> 16)
            | ((v & 0x0000FFFF0000FFFF0000FFFF0000FFFF) << 16);

        // swap 4-byte long pairs
        v = ((v & 0xFFFFFFFF00000000FFFFFFFF00000000) >> 32)
            | ((v & 0x00000000FFFFFFFF00000000FFFFFFFF) << 32);

        // swap 8-byte long pairs
        v = (v >> 64) | (v << 64);
    }

    function reverse64(uint64 input) internal pure returns (uint64 v) {
        v = input;

        // swap bytes
        v = ((v & 0xFF00FF00FF00FF00) >> 8) | ((v & 0x00FF00FF00FF00FF) << 8);

        // swap 2-byte long pairs
        v = ((v & 0xFFFF0000FFFF0000) >> 16) | ((v & 0x0000FFFF0000FFFF) << 16);

        // swap 4-byte long pairs
        v = (v >> 32) | (v << 32);
    }

    function reverse32(uint32 input) internal pure returns (uint32 v) {
        v = input;

        // swap bytes
        v = ((v & 0xFF00FF00) >> 8) | ((v & 0x00FF00FF) << 8);

        // swap 2-byte long pairs
        v = (v >> 16) | (v << 16);
    }

    function reverse16(uint16 input) internal pure returns (uint16 v) {
        v = input;

        // swap bytes
        v = (v >> 8) | (v << 8);
    }

    function encodeU256(uint256 input) internal pure returns (bytes32) {
        return bytes32(reverse256(input));
    }

    function encodeU128(uint128 input) internal pure returns (bytes16) {
        return bytes16(reverse128(input));
    }

    function encodeU64(uint64 input) internal pure returns (bytes8) {
        return bytes8(reverse64(input));
    }

    function encodeU32(uint32 input) internal pure returns (bytes4) {
        return bytes4(reverse32(input));
    }

    function encodeU16(uint16 input) internal pure returns (bytes2) {
        return bytes2(reverse16(input));
    }

    function encodeU8(uint8 input) internal pure returns (bytes1) {
        return bytes1(input);
    }

    // Supports compact encoding of integers in [0, uint32.MAX]
    function encodeCompactU32(uint32 value) internal pure returns (bytes memory) {
        if (value <= 2 ** 6 - 1) {
            // add single byte flag
            return abi.encodePacked(uint8(value << 2));
        } else if (value <= 2 ** 14 - 1) {
            // add two byte flag and create little endian encoding
            return abi.encodePacked(ScaleCodec.reverse16(uint16(((value << 2) + 1))));
        } else if (value <= 2 ** 30 - 1) {
            // add four byte flag and create little endian encoding
            return abi.encodePacked(ScaleCodec.reverse32(uint32((value << 2)) + 2));
        } else {
            return abi.encodePacked(uint8(3), ScaleCodec.reverse32(value));
        }
    }

    function encodeCompactU128(uint128 value) internal pure returns (bytes memory) {
        // 1) up to 2^6 - 1
        if (value <= 63) {
            // single byte = (value << 2)
            // (lowest two bits = 00)
            return abi.encodePacked(uint8(value << 2));
        }

        // 2) up to 2^14 - 1
        if (value <= 0x3FFF) {
            // two bytes = (value << 2) + 0x01
            // (lowest two bits = 01)
            uint16 encoded = uint16(value << 2) | 0x01;
            // We must store it in little-endian
            return abi.encodePacked(reverse16(encoded));
        }

        // 3) up to 2^30 - 1
        if (value <= 0x3FFF_FFFF) {
            // four bytes = (value << 2) + 0x02
            // (lowest two bits = 10)
            uint32 encoded = (uint32(value) << 2) | 0x02;
            return abi.encodePacked(reverse32(encoded));
        }

        // 4) otherwise
        // big integer => prefix + little-endian bytes (no leading zeros)
        // prefix = 0x03 + ((numValueBytes - 4) << 2)
        //   where numValueBytes is how many bytes needed to represent `value`.
        bytes memory littleEndian = _toLittleEndianNoLeadingZeros(value);
        uint8 len = uint8(littleEndian.length); // # of bytes needed

        // Substrate: prefix's lower 2 bits = 0b11,
        // the remaining upper bits = (len - 4).
        // Combined: prefix = 0x03 + ((len - 4) << 2).
        uint8 prefix = ((len - 4) << 2) | 0x03;

        // Concatenate prefix + actual bytes
        return abi.encodePacked(prefix, littleEndian);
    }

    // Convert `value` into a little-endian byte array with no leading zeros.
    // (Leading zeros in LE = trailing zeros in big-endian.)
    function _toLittleEndianNoLeadingZeros(uint128 value) private pure returns (bytes memory) {
        // Even if value=0, that case is handled above in smaller branches,
        // but let's just handle it gracefully anyway:
        if (value == 0) {
            return hex"00";
        }
        // Temporarily build up to 16 bytes in a buffer.
        bytes memory buf = new bytes(16);
        uint128 current = value;
        uint8 i = 0;
        while (current != 0) {
            buf[i] = bytes1(uint8(current & 0xFF));
            current >>= 8;
            unchecked {
                i++;
            }
        }
        // i is now the actual number of bytes used
        // Copy them into a new array of the correct size
        bytes memory out = new bytes(i);
        for (uint8 j = 0; j < i; j++) {
            out[j] = buf[j];
        }
        return out;
    }

    function checkedEncodeCompactU32(uint256 value) internal pure returns (bytes memory) {
        if (value > type(uint32).max) {
            revert UnsupportedCompactEncoding();
        }
        return encodeCompactU32(uint32(value));
    }
}

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: 2023 Snowfork <[email protected]>
// Code from https://github.com/ethereum/solidity-examples
pragma solidity 0.8.28;

library Bits {
    uint256 internal constant ONE = uint256(1);
    uint256 internal constant ONES = type(uint256).max;

    // Sets the bit at the given 'index' in 'self' to '1'.
    // Returns the modified value.
    function setBit(uint256 self, uint8 index) internal pure returns (uint256) {
        return self | (ONE << index);
    }

    // Sets the bit at the given 'index' in 'self' to '0'.
    // Returns the modified value.
    function clearBit(uint256 self, uint8 index) internal pure returns (uint256) {
        return self & ~(ONE << index);
    }

    // Sets the bit at the given 'index' in 'self' to:
    //  '1' - if the bit is '0'
    //  '0' - if the bit is '1'
    // Returns the modified value.
    function toggleBit(uint256 self, uint8 index) internal pure returns (uint256) {
        return self ^ (ONE << index);
    }

    // Get the value of the bit at the given 'index' in 'self'.
    function bit(uint256 self, uint8 index) internal pure returns (uint8) {
        return uint8((self >> index) & 1);
    }

    // Check if the bit at the given 'index' in 'self' is set.
    // Returns:
    //  'true' - if the value of the bit is '1'
    //  'false' - if the value of the bit is '0'
    function bitSet(uint256 self, uint8 index) internal pure returns (bool) {
        return (self >> index) & 1 == 1;
    }

    // Checks if the bit at the given 'index' in 'self' is equal to the corresponding
    // bit in 'other'.
    // Returns:
    //  'true' - if both bits are '0' or both bits are '1'
    //  'false' - otherwise
    function bitEqual(uint256 self, uint256 other, uint8 index) internal pure returns (bool) {
        return ((self ^ other) >> index) & 1 == 0;
    }

    // Get the bitwise NOT of the bit at the given 'index' in 'self'.
    function bitNot(uint256 self, uint8 index) internal pure returns (uint8) {
        return uint8(1 - ((self >> index) & 1));
    }

    // Computes the bitwise AND of the bit at the given 'index' in 'self', and the
    // corresponding bit in 'other', and returns the value.
    function bitAnd(uint256 self, uint256 other, uint8 index) internal pure returns (uint8) {
        return uint8(((self & other) >> index) & 1);
    }

    // Computes the bitwise OR of the bit at the given 'index' in 'self', and the
    // corresponding bit in 'other', and returns the value.
    function bitOr(uint256 self, uint256 other, uint8 index) internal pure returns (uint8) {
        return uint8(((self | other) >> index) & 1);
    }

    // Computes the bitwise XOR of the bit at the given 'index' in 'self', and the
    // corresponding bit in 'other', and returns the value.
    function bitXor(uint256 self, uint256 other, uint8 index) internal pure returns (uint8) {
        return uint8(((self ^ other) >> index) & 1);
    }

    // Gets 'numBits' consecutive bits from 'self', starting from the bit at 'startIndex'.
    // Returns the bits as a 'uint'.
    // Requires that:
    //  - '0 < numBits <= 256'
    //  - 'startIndex < 256'
    //  - 'numBits + startIndex <= 256'
    function bits(uint256 self, uint8 startIndex, uint16 numBits)
        internal
        pure
        returns (uint256)
    {
        require(0 < numBits && startIndex < 256 && startIndex + numBits <= 256, "out of bounds");
        return (self >> startIndex) & (ONES >> (256 - numBits));
    }

    // Computes the index of the highest bit set in 'self'.
    // Returns the highest bit set as an 'uint8'.
    // Requires that 'self != 0'.
    function highestBitSet(uint256 self) internal pure returns (uint8 highest) {
        require(self != 0, "should not be zero");
        uint256 val = self;
        for (uint8 i = 128; i >= 1; i >>= 1) {
            if (val & (((ONE << i) - 1) << i) != 0) {
                highest += i;
                val >>= i;
            }
        }
    }

    // Computes the index of the lowest bit set in 'self'.
    // Returns the lowest bit set as an 'uint8'.
    // Requires that 'self != 0'.
    function lowestBitSet(uint256 self) internal pure returns (uint8 lowest) {
        require(self != 0, "should not be zero");
        uint256 val = self;
        for (uint8 i = 128; i >= 1; i >>= 1) {
            if (val & ((ONE << i) - 1) == 0) {
                lowest += i;
                val >>= i;
            }
        }
    }
}

{
  "remappings": [
    "canonical-weth/=lib/canonical-weth/contracts/",
    "ds-test/=lib/ds-test/src/",
    "forge-std/=lib/forge-std/src/",
    "openzeppelin-contracts/=lib/openzeppelin-contracts/",
    "openzeppelin/=lib/openzeppelin-contracts/contracts/",
    "prb/math/=lib/prb-math/",
    "@openzeppelin/contracts/=lib/openzeppelin-contracts/contracts/",
    "erc4626-tests/=lib/openzeppelin-contracts/lib/erc4626-tests/",
    "halmos-cheatcodes/=lib/openzeppelin-contracts/lib/halmos-cheatcodes/src/",
    "prb-math/=lib/prb-math/src/",
    "v3-core/=lib/v3-core/",
    "v3-periphery/=lib/v3-periphery/contracts/"
  ],
  "optimizer": {
    "enabled": true,
    "runs": 20000
  },
  "metadata": {
    "useLiteralContent": false,
    "bytecodeHash": "ipfs",
    "appendCBOR": true
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "evmVersion": "prague",
  "viaIR": false
}

[{"inputs":[{"internalType":"uint256","name":"_randaoCommitDelay","type":"uint256"},{"internalType":"uint256","name":"_randaoCommitExpiration","type":"uint256"},{"internalType":"uint256","name":"_minNumRequiredSignatures","type":"uint256"},{"internalType":"uint256","name":"_fiatShamirRequiredSignatures","type":"uint256"},{"internalType":"uint64","name":"_initialBeefyBlock","type":"uint64"},{"components":[{"internalType":"uint128","name":"id","type":"uint128"},{"internalType":"uint128","name":"length","type":"uint128"},{"internalType":"bytes32","name":"root","type":"bytes32"}],"internalType":"struct BeefyClient.ValidatorSet","name":"_initialValidatorSet","type":"tuple"},{"components":[{"internalType":"uint128","name":"id","type":"uint128"},{"internalType":"uint128","name":"length","type":"uint128"},{"internalType":"bytes32","name":"root","type":"bytes32"}],"internalType":"struct BeefyClient.ValidatorSet","name":"_nextValidatorSet","type":"tuple"}],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"CommitmentNotRelevant","type":"error"},{"inputs":[],"name":"ECDSAInvalidSignature","type":"error"},{"inputs":[{"internalType":"uint256","name":"length","type":"uint256"}],"name":"ECDSAInvalidSignatureLength","type":"error"},{"inputs":[{"internalType":"bytes32","name":"s","type":"bytes32"}],"name":"ECDSAInvalidSignatureS","type":"error"},{"inputs":[],"name":"IndexOutOfBounds","type":"error"},{"inputs":[],"name":"InvalidBitfield","type":"error"},{"inputs":[],"name":"InvalidBitfieldLength","type":"error"},{"inputs":[],"name":"InvalidBitfieldPadding","type":"error"},{"inputs":[],"name":"InvalidCommitment","type":"error"},{"inputs":[],"name":"InvalidMMRLeaf","type":"error"},{"inputs":[],"name":"InvalidMMRLeafProof","type":"error"},{"inputs":[],"name":"InvalidMMRRootLength","type":"error"},{"inputs":[],"name":"InvalidSamplingParams","type":"error"},{"inputs":[],"name":"InvalidSignature","type":"error"},{"inputs":[],"name":"InvalidTicket","type":"error"},{"inputs":[],"name":"InvalidValidatorProof","type":"error"},{"inputs":[],"name":"InvalidValidatorProofLength","type":"error"},{"inputs":[],"name":"PrevRandaoAlreadyCaptured","type":"error"},{"inputs":[],"name":"PrevRandaoNotCaptured","type":"error"},{"inputs":[],"name":"ProofSizeExceeded","type":"error"},{"inputs":[],"name":"StaleCommitment","type":"error"},{"inputs":[],"name":"UnsupportedCompactEncoding","type":"error"},{"inputs":[],"name":"WaitPeriodNotOver","type":"error"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"bytes32","name":"mmrRoot","type":"bytes32"},{"indexed":false,"internalType":"uint64","name":"blockNumber","type":"uint64"}],"name":"NewMMRRoot","type":"event"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"address","name":"relayer","type":"address"},{"indexed":false,"internalType":"uint64","name":"blockNumber","type":"uint64"}],"name":"NewTicket","type":"event"},{"anonymous":false,"inputs":[],"name":"TicketExpired","type":"event"},{"inputs":[],"name":"FIAT_SHAMIR_DOMAIN_ID","outputs":[{"internalType":"bytes","name":"","type":"bytes"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"MMR_ROOT_ID","outputs":[{"internalType":"bytes2","name":"","type":"bytes2"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"commitmentHash","type":"bytes32"}],"name":"commitPrevRandao","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"uint32","name":"blockNumber","type":"uint32"},{"internalType":"uint64","name":"validatorSetID","type":"uint64"},{"components":[{"internalType":"bytes2","name":"payloadID","type":"bytes2"},{"internalType":"bytes","name":"data","type":"bytes"}],"internalType":"struct BeefyClient.PayloadItem[]","name":"payload","type":"tuple[]"}],"internalType":"struct BeefyClient.Commitment","name":"commitment","type":"tuple"},{"internalType":"uint256[]","name":"bitfield","type":"uint256[]"}],"name":"createFiatShamirFinalBitfield","outputs":[{"internalType":"uint256[]","name":"","type":"uint256[]"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"commitmentHash","type":"bytes32"},{"internalType":"uint256[]","name":"bitfield","type":"uint256[]"}],"name":"createFinalBitfield","outputs":[{"internalType":"uint256[]","name":"","type":"uint256[]"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256[]","name":"bitsToSet","type":"uint256[]"},{"internalType":"uint256","name":"length","type":"uint256"}],"name":"createInitialBitfield","outputs":[{"internalType":"uint256[]","name":"","type":"uint256[]"}],"stateMutability":"pure","type":"function"},{"inputs":[],"name":"currentValidatorSet","outputs":[{"internalType":"uint128","name":"id","type":"uint128"},{"internalType":"uint128","name":"length","type":"uint128"},{"internalType":"bytes32","name":"root","type":"bytes32"},{"components":[{"internalType":"uint256[]","name":"data","type":"uint256[]"},{"internalType":"uint256","name":"length","type":"uint256"}],"internalType":"struct Uint16Array","name":"usageCounters","type":"tuple"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"fiatShamirRequiredSignatures","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"latestBeefyBlock","outputs":[{"internalType":"uint64","name":"","type":"uint64"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"latestMMRRoot","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"minNumRequiredSignatures","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"nextValidatorSet","outputs":[{"internalType":"uint128","name":"id","type":"uint128"},{"internalType":"uint128","name":"length","type":"uint128"},{"internalType":"bytes32","name":"root","type":"bytes32"},{"components":[{"internalType":"uint256[]","name":"data","type":"uint256[]"},{"internalType":"uint256","name":"length","type":"uint256"}],"internalType":"struct Uint16Array","name":"usageCounters","type":"tuple"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"randaoCommitDelay","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"randaoCommitExpiration","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"components":[{"internalType":"uint32","name":"blockNumber","type":"uint32"},{"internalType":"uint64","name":"validatorSetID","type":"uint64"},{"components":[{"internalType":"bytes2","name":"payloadID","type":"bytes2"},{"internalType":"bytes","name":"data","type":"bytes"}],"internalType":"struct BeefyClient.PayloadItem[]","name":"payload","type":"tuple[]"}],"internalType":"struct BeefyClient.Commitment","name":"commitment","type":"tuple"},{"internalType":"uint256[]","name":"bitfield","type":"uint256[]"},{"components":[{"internalType":"uint8","name":"v","type":"uint8"},{"internalType":"bytes32","name":"r","type":"bytes32"},{"internalType":"bytes32","name":"s","type":"bytes32"},{"internalType":"uint256","name":"index","type":"uint256"},{"internalType":"address","name":"account","type":"address"},{"internalType":"bytes32[]","name":"proof","type":"bytes32[]"}],"internalType":"struct BeefyClient.ValidatorProof[]","name":"proofs","type":"tuple[]"},{"components":[{"internalType":"uint8","name":"version","type":"uint8"},{"internalType":"uint32","name":"parentNumber","type":"uint32"},{"internalType":"bytes32","name":"parentHash","type":"bytes32"},{"internalType":"uint64","name":"nextAuthoritySetID","type":"uint64"},{"internalType":"uint32","name":"nextAuthoritySetLen","type":"uint32"},{"internalType":"bytes32","name":"nextAuthoritySetRoot","type":"bytes32"},{"internalType":"bytes32","name":"parachainHeadsRoot","type":"bytes32"}],"internalType":"struct BeefyClient.MMRLeaf","name":"leaf","type":"tuple"},{"internalType":"bytes32[]","name":"leafProof","type":"bytes32[]"},{"internalType":"uint256","name":"leafProofOrder","type":"uint256"}],"name":"submitFiatShamir","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"uint32","name":"blockNumber","type":"uint32"},{"internalType":"uint64","name":"validatorSetID","type":"uint64"},{"components":[{"internalType":"bytes2","name":"payloadID","type":"bytes2"},{"internalType":"bytes","name":"data","type":"bytes"}],"internalType":"struct BeefyClient.PayloadItem[]","name":"payload","type":"tuple[]"}],"internalType":"struct BeefyClient.Commitment","name":"commitment","type":"tuple"},{"internalType":"uint256[]","name":"bitfield","type":"uint256[]"},{"components":[{"internalType":"uint8","name":"v","type":"uint8"},{"internalType":"bytes32","name":"r","type":"bytes32"},{"internalType":"bytes32","name":"s","type":"bytes32"},{"internalType":"uint256","name":"index","type":"uint256"},{"internalType":"address","name":"account","type":"address"},{"internalType":"bytes32[]","name":"proof","type":"bytes32[]"}],"internalType":"struct BeefyClient.ValidatorProof[]","name":"proofs","type":"tuple[]"},{"components":[{"internalType":"uint8","name":"version","type":"uint8"},{"internalType":"uint32","name":"parentNumber","type":"uint32"},{"internalType":"bytes32","name":"parentHash","type":"bytes32"},{"internalType":"uint64","name":"nextAuthoritySetID","type":"uint64"},{"internalType":"uint32","name":"nextAuthoritySetLen","type":"uint32"},{"internalType":"bytes32","name":"nextAuthoritySetRoot","type":"bytes32"},{"internalType":"bytes32","name":"parachainHeadsRoot","type":"bytes32"}],"internalType":"struct BeefyClient.MMRLeaf","name":"leaf","type":"tuple"},{"internalType":"bytes32[]","name":"leafProof","type":"bytes32[]"},{"internalType":"uint256","name":"leafProofOrder","type":"uint256"}],"name":"submitFinal","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"uint32","name":"blockNumber","type":"uint32"},{"internalType":"uint64","name":"validatorSetID","type":"uint64"},{"components":[{"internalType":"bytes2","name":"payloadID","type":"bytes2"},{"internalType":"bytes","name":"data","type":"bytes"}],"internalType":"struct BeefyClient.PayloadItem[]","name":"payload","type":"tuple[]"}],"internalType":"struct BeefyClient.Commitment","name":"commitment","type":"tuple"},{"internalType":"uint256[]","name":"bitfield","type":"uint256[]"},{"components":[{"internalType":"uint8","name":"v","type":"uint8"},{"internalType":"bytes32","name":"r","type":"bytes32"},{"internalType":"bytes32","name":"s","type":"bytes32"},{"internalType":"uint256","name":"index","type":"uint256"},{"internalType":"address","name":"account","type":"address"},{"internalType":"bytes32[]","name":"proof","type":"bytes32[]"}],"internalType":"struct BeefyClient.ValidatorProof","name":"proof","type":"tuple"}],"name":"submitInitial","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"bytes32","name":"ticketID","type":"bytes32"}],"name":"tickets","outputs":[{"internalType":"uint64","name":"blockNumber","type":"uint64"},{"internalType":"uint32","name":"validatorSetLen","type":"uint32"},{"internalType":"uint32","name":"numRequiredSignatures","type":"uint32"},{"internalType":"uint256","name":"prevRandao","type":"uint256"},{"internalType":"bytes32","name":"bitfieldHash","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"bytes32","name":"leafHash","type":"bytes32"},{"internalType":"bytes32[]","name":"proof","type":"bytes32[]"},{"internalType":"uint256","name":"proofOrder","type":"uint256"}],"name":"verifyMMRLeafProof","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"}]

610100604052348015610010575f5ffd5b50604051614a61380380614a6183398101604081905261002f91610335565b815161003c9060016103c1565b6001600160801b0316815f01516001600160801b0316146100a35760405162461bcd60e51b815260206004820152601a60248201527f696e76616c69642d636f6e7374727563746f722d706172616d73000000000000604482015260640160405180910390fd5b608087905260a086905260c085905260e0849052600180546001600160401b0319166001600160401b038516179055815160208301516001600160801b03918216600160801b918316820217600281905560408501516003556101099291900416610193565b8051805160049161011f91839160200190610238565b50602091820151600191909101558151908201516001600160801b03918216600160801b918316820217600681905560408401516007556101639291900416610193565b8051805160089161017991839160200190610238565b506020820151816001015590505050505050505050610433565b60408051808201909152606081525f60208201525f6101b36010846103fa565b156101bf5760016101c1565b5f5b60ff166101cf60108561040d565b6101d99190610420565b90506040518060400160405280826001600160401b038111156101fe576101fe610295565b604051908082528060200260200182016040528015610227578160200160208202803683370190505b508152602001939093525090919050565b828054828255905f5260205f20908101928215610271579160200282015b82811115610271578251825591602001919060010190610256565b5061027d929150610281565b5090565b5b8082111561027d575f8155600101610282565b634e487b7160e01b5f52604160045260245ffd5b80516001600160801b03811681146102bf575f5ffd5b919050565b5f606082840312156102d4575f5ffd5b604051606081016001600160401b038111828210171561030257634e487b7160e01b5f52604160045260245ffd5b604052905080610311836102a9565b815261031f602084016102a9565b6020820152604083015160408201525092915050565b5f5f5f5f5f5f5f610160888a03121561034c575f5ffd5b8751602089015160408a015160608b015160808c0151939a50919850965094506001600160401b0381168114610380575f5ffd5b925061038f8960a08a016102c4565b915061039f896101008a016102c4565b905092959891949750929550565b634e487b7160e01b5f52601160045260245ffd5b6001600160801b0381811683821601908111156103e0576103e06103ad565b92915050565b634e487b7160e01b5f52601260045260245ffd5b5f82610408576104086103e6565b500690565b5f8261041b5761041b6103e6565b500490565b808201808211156103e0576103e06103ad565b60805160a05160c05160e0516145d16104905f395f81816102f1015281816121420152612e3b01525f81816102ca01526113d401525f81816103610152610e7c01525f818161024e01528181610e100152610ea201526145d15ff3fe608060405234801561000f575f5ffd5b5060043610610149575f3560e01c806366ae69a0116100c7578063a77cf3d21161007d578063bb51f1eb11610063578063bb51f1eb14610383578063c7d6e93d14610396578063df0dd0d5146103a9575f5ffd5b8063a77cf3d214610349578063ad209a9b1461035c575f5ffd5b806383fe0ea0116100ad57806383fe0ea0146102ec5780638ab81d1314610313578063a401662b14610326575f5ffd5b806366ae69a0146102985780636f55bd32146102c5575f5ffd5b806341c9634e1161011c578063591d99ee11610102578063591d99ee146102495780635da57fe914610270578063623b223d14610283575f5ffd5b806341c9634e146102135780634b4cfb2814610229575f5ffd5b80630a7c8faa1461014d57806315fac8c6146101aa5780632cdea717146101f3578063366675131461020b575b5f5ffd5b6101747f6d6800000000000000000000000000000000000000000000000000000000000081565b6040517fffff00000000000000000000000000000000000000000000000000000000000090911681526020015b60405180910390f35b6101e66040518060400160405280601981526020017f534e4f574252494447452d464941542d5348414d49522d76310000000000000081525081565b6040516101a19190613a8b565b6101fb610443565b6040516101a19493929190613ade565b6101fb6104da565b61021b5f5481565b6040519081526020016101a1565b61023c610237366004613bd7565b61056f565b6040516101a19190613c40565b61021b7f000000000000000000000000000000000000000000000000000000000000000081565b61023c61027e366004613c82565b61074a565b610296610291366004613cda565b610799565b005b6001546102ac9067ffffffffffffffff1681565b60405167ffffffffffffffff90911681526020016101a1565b61021b7f000000000000000000000000000000000000000000000000000000000000000081565b61021b7f000000000000000000000000000000000000000000000000000000000000000081565b61023c610321366004613dbf565b610c5c565b610339610334366004613dee565b610d5a565b60405190151581526020016101a1565b610296610357366004613e3d565b610d69565b61021b7f000000000000000000000000000000000000000000000000000000000000000081565b610296610391366004613e54565b610f58565b6102966103a4366004613cda565b611572565b6104066103b7366004613e3d565b600a6020525f908152604090208054600182015460029092015467ffffffffffffffff82169263ffffffff6801000000000000000084048116936c010000000000000000000000009004169185565b6040805167ffffffffffffffff96909616865263ffffffff948516602087015292909316918401919091526060830152608082015260a0016101a1565b6002805460035460408051600480546060602082028401810185529383018181526fffffffffffffffffffffffffffffffff80881698700100000000000000000000000000000000909804169694849284918401828280156104c257602002820191905f5260205f20905b8154815260200190600101908083116104ae575b50505050508152602001600182015481525050905084565b6006805460075460408051600880546060602082028401810185529383018181526fffffffffffffffffffffffffffffffff80881698700100000000000000000000000000000000909804169694849284918401828280156104c257602002820191905f5260205f20908154815260200190600101908083116104ae5750505050508152602001600182015481525050905084565b6006546060906002906fffffffffffffffffffffffffffffffff1661059a6040870160208801613eec565b67ffffffffffffffff16036105b157506006610617565b6002546fffffffffffffffffffffffffffffffff166105d66040870160208801613eec565b67ffffffffffffffff1614610617576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80546106489070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b831415806106e8575080546106829070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6106e68585808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b1561071f576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61072986612009565b80519060200120905061073e818686856120fb565b925050505b9392505050565b606082821015610786576040517f5c85a0e700000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61079184848461220c565b949350505050565b5f6107a38a612009565b8051906020012090505f6107c033835f9182526020526040902090565b90506107ce818c8c8c612297565b5f5f90505f6002905060065f015f9054906101000a90046fffffffffffffffffffffffffffffffff166fffffffffffffffffffffffffffffffff168d602001602081019061081c9190613eec565b67ffffffffffffffff160361083757506001905060066108bd565b60025f015f9054906101000a90046fffffffffffffffffffffffffffffffff166fffffffffffffffffffffffffffffffff168d602001602081019061087c9190613eec565b67ffffffffffffffff16146108bd576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6109218c8c808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050845470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b61093084848e8e858f8f6124b7565b5f61093a8e61270a565b90508215610b5657600654610962906fffffffffffffffffffffffffffffffff166001613f40565b6fffffffffffffffffffffffffffffffff1661098460808b0160608c01613eec565b67ffffffffffffffff16146109c5576040517fc72c820000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6109e2826109d38c61282c565b805190602001208b8b8b612928565b905080610a1b576040517f128597bb00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600680547001000000000000000000000000000000008082046fffffffffffffffffffffffffffffffff908116909102911617600290815560075460035560088054600490610a6d90829084906139f2565b5060019182015491015550610a8a905060808b0160608c01613eec565b600680547fffffffffffffffffffffffffffffffff000000000000000000000000000000001667ffffffffffffffff92909216919091179055610ad360a08b0160808c01613f68565b600680546fffffffffffffffffffffffffffffffff1663ffffffff929092167001000000000000000000000000000000000291909117905560a08a018035600755610b3090610b259060808d01613f68565b63ffffffff166129b0565b80518051600891610b4691839160200190613a3e565b5060208201518160010155905050505b5f819055610b6760208f018f613f68565b63ffffffff1660015f6101000a81548167ffffffffffffffff021916908367ffffffffffffffff160217905550600a5f8581526020019081526020015f205f5f82015f6101000a81549067ffffffffffffffff02191690555f820160086101000a81549063ffffffff02191690555f8201600c6101000a81549063ffffffff0219169055600182015f9055600282015f905550507fd95fe1258d152dc91c81b09380498adc76ed36a6079bcb2ed31eff622ae2d0f1818f5f016020810190610c2f9190613f68565b6040805192835263ffffffff90911660208301520160405180910390a15050505050505050505050505050565b60605f600a5f610c7533885f9182526020526040902090565b81526020019081526020015f2090508383604051602001610c97929190613f8b565b60405160208183030381529060405280519060200120816002015414610ce9576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b610d5181600101548585808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855463ffffffff680100000000000000008204811693506c01000000000000000000000000909104169050612a56565b95945050505050565b5f610d515f5486868686612928565b335f9081526020829052604081205f818152600a6020526040812080549293509167ffffffffffffffff169003610dcc576040517f6686db6400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600181015415610e08576040517fe31d900500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8054610e3f907f00000000000000000000000000000000000000000000000000000000000000009067ffffffffffffffff16613fcb565b431015610e78576040517fc77c194900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80547f000000000000000000000000000000000000000000000000000000000000000090610ed1907f00000000000000000000000000000000000000000000000000000000000000009067ffffffffffffffff16613fcb565b610edb9190613fcb565b431115610f4d575f828152600a602052604080822080547fffffffffffffffffffffffffffffffff0000000000000000000000000000000016815560018101839055600201829055517f40d3544771f3c2382030d7a42c371f55cb608ac0eaf54ef2fa846da65af1b9859190a1505050565b446001909101555050565b60015467ffffffffffffffff16610f726020860186613f68565b63ffffffff1611610faf576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600280545f906fffffffffffffffffffffffffffffffff16610fd76040880160208901613eec565b67ffffffffffffffff160361101c57610ff560046060850135612b58565b9050611017606084013561100e61ffff84166001612bda565b60049190612bf8565b6110bc565b6006546fffffffffffffffffffffffffffffffff166110416040880160208901613eec565b67ffffffffffffffff160361108a5761105f60086060850135612b58565b9050611081606084013561107861ffff84166001612bda565b60089190612bf8565b600691506110bc565b6040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6110e7826110d060a0860160808701613fde565b60608601356110e260a0880188614011565b612cb8565b158061112f575061112d8585808060200260200160405190810160405280939291908181526020018383602002808284375f920191909152505050506060850135612d6e565b155b15611166576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61117087612009565b8051602090910120905061118a60a0850160808601613fde565b73ffffffffffffffffffffffffffffffffffffffff166111c0826111b16020880188614075565b87602001358860400135612db2565b73ffffffffffffffffffffffffffffffffffffffff161461120d576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b825461123e9070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b851415806112de575082546112789070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6112dc8787808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050875470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b15611315576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6113798686808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050865470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b6040805160a0810182524367ffffffffffffffff1681528454700100000000000000000000000000000000900463ffffffff8116602083015290918201906113f8906fffffffffffffffffffffffffffffffff1661ffff86167f0000000000000000000000000000000000000000000000000000000000000000612dde565b63ffffffff1681526020015f8152602001878760405160200161141c929190613f8b565b60405160208183030381529060405280519060200120815250600a5f61144b33855f9182526020526040902090565b815260208082019290925260409081015f2083518154858501519386015163ffffffff9081166c01000000000000000000000000027fffffffffffffffffffffffffffffffff00000000ffffffffffffffffffffffff9190951668010000000000000000027fffffffffffffffffffffffffffffffffffffffff00000000000000000000000090921667ffffffffffffffff909316929092171716919091178155606083015160018201556080909201516002909201919091557fbee983fc706c692efb9b0240bddc5666c010a53af55ed5fb42d226e7e4293869903390611535908a018a613f68565b6040805173ffffffffffffffffffffffffffffffffffffffff909316835263ffffffff90911660208301520160405180910390a150505050505050565b60015467ffffffffffffffff1661158c60208b018b613f68565b63ffffffff16116115c9576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6006545f906002906fffffffffffffffffffffffffffffffff166115f360408d0160208e01613eec565b67ffffffffffffffff160361160e5750600190506006611674565b6002546fffffffffffffffffffffffffffffffff1661163360408d0160208e01613eec565b67ffffffffffffffff1614611674576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80546116a59070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b89141580611745575080546116df9070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6117438b8b808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b1561177c576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6117e08a8a808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050845470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b5f6117ea8c61270a565b90505f6117f68d612009565b80519060200120905061180d818d8d868e8e612e31565b8315611a1c57600654611833906fffffffffffffffffffffffffffffffff166001613f40565b6fffffffffffffffffffffffffffffffff1661185560808a0160608b01613eec565b67ffffffffffffffff1614611896576040517fc72c820000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6118b3836118a48b61282c565b805190602001208a8a8a612928565b9050806118ec576040517f128597bb00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600680547001000000000000000000000000000000008082046fffffffffffffffffffffffffffffffff90811690910291161760029081556007546003556008805460049061193e90829084906139f2565b506001918201549101555061195b905060808a0160608b01613eec565b600680547fffffffffffffffffffffffffffffffff000000000000000000000000000000001667ffffffffffffffff929092169190911790556119a460a08a0160808b01613f68565b600680546fffffffffffffffffffffffffffffffff1663ffffffff929092167001000000000000000000000000000000000291909117905560a0890180356007556119f690610b259060808c01613f68565b80518051600891611a0c91839160200190613a3e565b5060208201518160010155905050505b5f829055611a2d60208e018e613f68565b63ffffffff1660015f6101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055507fd95fe1258d152dc91c81b09380498adc76ed36a6079bcb2ed31eff622ae2d0f1828e5f016020810190611a8e9190613f68565b6040805192835263ffffffff90911660208301520160405180910390a150505050505050505050505050565b5f610100611ac98360ff613fcb565b611ad391906140c2565b92915050565b5f6003611ae76001846140d5565b611af191906140c2565b611ad390836140d5565b5f811580611b0857508251155b15611b1457505f611ad3565b5f610100830460ff8416825b8281108015611b2f5750865181105b15611d8e575f878281518110611b4757611b476140e8565b602002602001015190507f5555555555555555555555555555555555555555555555555555555555555555600182901c167f555555555555555555555555555555555555555555555555555555555555555582160190507f3333333333333333333333333333333333333333333333333333333333333333600282901c167f333333333333333333333333333333333333333333333333333333333333333382160190507f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f600482901c167f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82160190507eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff600882901c167eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82160190507dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff601082901c167dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82160190507bffffffff00000000ffffffff00000000ffffffff00000000ffffffff602082901c167bffffffff00000000ffffffff00000000ffffffff00000000ffffffff821601905077ffffffffffffffff0000000000000000ffffffffffffffff604082901c1677ffffffffffffffff0000000000000000ffffffffffffffff82160190506fffffffffffffffffffffffffffffffff608082901c166fffffffffffffffffffffffffffffffff82160190508085019450508080600101915050611b20565b505f81118015611d9e5750855182105b15611fff575f6001826001901b0390505f81888581518110611dc257611dc26140e8565b60200260200101511690507f5555555555555555555555555555555555555555555555555555555555555555600182901c167f555555555555555555555555555555555555555555555555555555555555555582160190507f3333333333333333333333333333333333333333333333333333333333333333600282901c167f333333333333333333333333333333333333333333333333333333333333333382160190507f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f600482901c167f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82160190507eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff600882901c167eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82160190507dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff601082901c167dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82160190507bffffffff00000000ffffffff00000000ffffffff00000000ffffffff602082901c167bffffffff00000000ffffffff00000000ffffffff00000000ffffffff821601905077ffffffffffffffff0000000000000000ffffffffffffffff604082901c1677ffffffffffffffff0000000000000000ffffffffffffffff82160190506fffffffffffffffffffffffffffffffff608082901c166fffffffffffffffffffffffffffffffff8216019050808501945050505b5090949350505050565b606061202061201b6040840184614011565b613039565b6120576120306020850185613f68565b600881811c62ff00ff1663ff00ff009290911b9190911617601081811c91901b1760e01b90565b6120d361206a6040860160208701613eec565b5f65ff000000ff00600883811b91821664ff000000ff9185901c91821617601090811b67ff000000ff0000009390931666ff000000ff00009290921691909117901c17602081811b6bffffffffffffffff000000001691901c63ffffffff161760c01b92915050565b6040516020016120e59392919061412c565b6040516020818303038152906040529050919050565b60605f8484604051602001612111929190613f8b565b6040516020818303038152906040528051906020012090505f61213587838661313e565b84549091505f90612196907f0000000000000000000000000000000000000000000000000000000000000000906121919070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff166132cd565b6132e4565b9050612200825f1c8888808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050895470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150859050612a56565b98975050505050505050565b606061221782611aba565b67ffffffffffffffff81111561222f5761222f61418f565b604051908082528060200260200182016040528015612258578160200160208202803683370190505b5090505f5b8381101561228f576122878286868481811061227b5761227b6140e8565b905060200201356132f9565b60010161225d565b509392505050565b5f848152600a602052604081208054909167ffffffffffffffff90911690036122ec576040517f6686db6400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80600101545f03612329576040517f78ef3a4700000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60015467ffffffffffffffff166123436020860186613f68565b63ffffffff1611612380576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8282604051602001612393929190613f8b565b604051602081830303815290604052805190602001208160020154146123e5576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5050505050565b5f6123f682611aba565b905080158061240457508251155b1561240e57505050565b5f61241b610100846141bc565b9050805f0361242a5750505050565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff811b5f8561245a6001866140d5565b8151811061246a5761246a6140e8565b602002602001015190508181165f146124af576040517f3dc5549600000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b505050505050565b5f868152600a6020526040902080546c01000000000000000000000000900463ffffffff16828114612515576040517f1f1711da00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61258083600101548989808060200260200160405190810160405280939291908181526020018383602002808284375f92019190915250508a5470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150869050612a56565b90505f5b848110156126fd573686868381811061259f5761259f6140e8565b90506020028101906125b191906141cf565b90506125d9886125c760a0840160808501613fde565b60608401356110e260a0860186614011565b61260f576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61261d838260600135612d6e565b612653576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61266360a0820160808301613fde565b73ffffffffffffffffffffffffffffffffffffffff166126998d61268a6020850185614075565b84602001358560400135612db2565b73ffffffffffffffffffffffffffffffffffffffff16146126e6576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6126f4838260600135613350565b50600101612584565b5050505050505050505050565b5f6127186040830183614011565b9050600114612753576040517f484ab7df00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6127616040840184614011565b5f818110612771576127716140e8565b9050602002810190612783919061420b565b61278c906142e4565b80519091507fffff000000000000000000000000000000000000000000000000000000000000167f6d680000000000000000000000000000000000000000000000000000000000001415806127e75750806020015151602014155b1561281e576040517f484ab7df00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8060200151610743906143ad565b606061284461283e6020840184614075565b60f81b90565b6128576120306040850160208601613f68565b604084013561286f61206a6080870160608801613eec565b61288261203060a0880160808901613f68565b6040517fff0000000000000000000000000000000000000000000000000000000000000090951660208601527fffffffff00000000000000000000000000000000000000000000000000000000938416602186015260258501929092527fffffffffffffffff00000000000000000000000000000000000000000000000016604584015216604d82015260a0830135605182015260c083013560718201526091016120e5565b5f610100831115612965576040517f5e862a8a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b845f5b848110156129a35761299982878784818110612986576129866140e8565b905060200201358387901c600116613384565b9150600101612968565b5090951495945050505050565b60408051808201909152606081525f60208201525f6129d06010846141bc565b156129dc5760016129de565b5f5b60ff166129ec6010856140c2565b6129f69190613fcb565b905060405180604001604052808267ffffffffffffffff811115612a1c57612a1c61418f565b604051908082528060200260200182016040528015612a45578160200160208202803683370190505b508152602001939093525090919050565b6060612a6183611aba565b8451141580612a785750612a758484611afb565b82115b15612aaf576040517f5f64a3e000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b835167ffffffffffffffff811115612ac957612ac961418f565b604051908082528060200260200182016040528015612af2578160200160208202803683370190505b5090505f805b83821015612b4e575f612b0c8883886133ad565b9050612b188782612d6e565b1580612b295750612b298482612d6e565b15612b375750600101612af8565b612b4184826132f9565b5060019182019101612af8565b5050949350505050565b5f82600101548210612b96576040517f4e23d03500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600482901c600f8316612baa8160106143ef565b60ff16855f018381548110612bc157612bc16140e8565b905f5260205f200154901c61ffff169250505092915050565b5f82820161ffff80851690821610156107435761ffff915050611ad3565b82600101548210612c35576040517f4e23d03500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600482901c600f83165f612c4a8260106143ef565b60ff1661ffff901b1990505f826010612c6391906143ef565b60ff168561ffff16901b90508082885f018681548110612c8557612c856140e8565b905f5260205f2001541617875f018581548110612ca457612ca46140e8565b5f9182526020909120015550505050505050565b6040517fffffffffffffffffffffffffffffffffffffffff000000000000000000000000606086901b1660208201525f908190603401604080518083037fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0018152919052805160209091012060018801548854919250612d63918390889070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1688886133d0565b979650505050505050565b5f5f600883901c9050612da383858381518110612d8d57612d8d6140e8565b60200260200101516133fb90919063ffffffff16565b60ff1660011491505092915050565b5f5f5f5f612dc288888888613405565b925092509250612dd282826134f8565b50909695505050505050565b5f81612deb856001613604565b612df59082613fcb565b9050612e02846001613604565b612e0d906002614412565b612e18906001613fcb565b612e229082613fcb565b9050610d5181612191876132cd565b82545f90612e8a907f0000000000000000000000000000000000000000000000000000000000000000906121919070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff166132cd565b9050818114612ec5576040517f1f1711da00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f612ed2888888886120fb565b90505f5b8381101561302e5736858583818110612ef157612ef16140e8565b9050602002810190612f0391906141cf565b9050612f13838260600135612d6e565b612f49576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b612f5d876125c760a0840160808501613fde565b612f93576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b612fa360a0820160808301613fde565b73ffffffffffffffffffffffffffffffffffffffff16612fca8b61268a6020850185614075565b73ffffffffffffffffffffffffffffffffffffffff1614613017576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b613025838260600135613350565b50600101612ed6565b505050505050505050565b60605f61304583613641565b90505f5b8381101561228f5781858583818110613064576130646140e8565b9050602002810190613076919061420b565b613084906020810190614429565b6130c0878785818110613099576130996140e8565b90506020028101906130ab919061420b565b6130b9906020810190614442565b9050613641565b8787858181106130d2576130d26140e8565b90506020028101906130e4919061420b565b6130f2906020810190614442565b6040516020016131069594939291906144a3565b604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe08184030181529190529150600101613049565b604080518082018252601981527f534e4f574252494447452d464941542d5348414d49522d76310000000000000060208083019190915260018401548454845192830188905293820186905260608201526fffffffffffffffffffffffffffffffff808416608083015270010000000000000000000000000000000090930490921660a08301525f9160029190829060c001604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe081840301815290829052613208916144f7565b602060405180830381855afa158015613223573d5f5f3e3d5ffd5b5050506040513d601f19601f820116820180604052508101906132469190614502565b604051602001613257929190614519565b604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe08184030181529082905261328f916144f7565b602060405180830381855afa1580156132aa573d5f5f3e3d5ffd5b5050506040513d601f19601f820116820180604052508101906107919190614502565b5f6132d96003836140c2565b611ad3906001613fcb565b5f8183106132f25781610743565b5090919050565b5f600882901c905061332d82848381518110613317576133176140e8565b602002602001015161368a90919063ffffffff16565b83828151811061333f5761333f6140e8565b602002602001018181525050505050565b5f600882901c905061332d8284838151811061336e5761336e6140e8565b602002602001015161369790919063ffffffff16565b5f81801561339857835f52846020526133a0565b845f52836020525b505060405f209392505050565b5f815f036133bc57505f610743565b505f92835260209190915260409091200690565b5f8385106133df57505f6133f1565b6133ec86868686866136a5565b871490505b9695505050505050565b60ff161c60011690565b5f80807f7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a084111561343e57505f915060039050826134ee565b604080515f808252602082018084528a905260ff891692820192909252606081018790526080810186905260019060a0016020604051602081039080840390855afa15801561348f573d5f5f3e3d5ffd5b50506040517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0015191505073ffffffffffffffffffffffffffffffffffffffff81166134e557505f9250600191508290506134ee565b92505f91508190505b9450945094915050565b5f82600381111561350b5761350b614531565b03613514575050565b600182600381111561352857613528614531565b0361355f576040517ff645eedf00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600282600381111561357357613573614531565b036135b2576040517ffce698f7000000000000000000000000000000000000000000000000000000008152600481018290526024015b60405180910390fd5b60038260038111156135c6576135c6614531565b03613600576040517fd78bce0c000000000000000000000000000000000000000000000000000000008152600481018290526024016135a9565b5050565b5f5f61360f8461376a565b905061361a836137fd565b8015613629575083816001901b105b613633575f613636565b60015b60ff16019392505050565b606063ffffffff821115613681576040517fe809999a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b611ad382613829565b600160ff919091161b1790565b600160ff919091161b191690565b5f85815b8381101561375f5786600116600114806136c557508587600101145b156136fc576136f58585838181106136df576136df6140e8565b90506020020135835f9182526020526040902090565b915061372a565b61372782868684818110613712576137126140e8565b905060200201355f9182526020526040902090565b91505b600196871c967fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff909601861c860195016136a9565b509695505050505050565b5f80608083901c1561377e57608092831c92015b604083901c1561379057604092831c92015b602083901c156137a257602092831c92015b601083901c156137b457601092831c92015b600883901c156137c657600892831c92015b600483901c156137d857600492831c92015b600283901c156137ea57600292831c92015b600183901c15611ad35760010192915050565b5f600282600381111561381257613812614531565b61381c919061455e565b60ff166001149050919050565b6060603f8263ffffffff1611613870576040517ffc0000000000000000000000000000000000000000000000000000000000000060fa84901b1660208201526021016120e5565b613fff8263ffffffff16116138e7576138ac6138986403fffffffc600285901b16600161457f565b600881811b62ffff001691901c60ff161790565b6040516020016120e5919060f09190911b7fffff00000000000000000000000000000000000000000000000000000000000016815260020190565b633fffffff8263ffffffff16116139715761393660028363ffffffff16901b6002613912919061457f565b600881811c62ff00ff1663ff00ff009290911b9190911617601081811c91901b1790565b6040516020016120e5919060e09190911b7fffffffff0000000000000000000000000000000000000000000000000000000016815260040190565b6040517f030000000000000000000000000000000000000000000000000000000000000060208201527fffffffff00000000000000000000000000000000000000000000000000000000600884811c62ff00ff1663ff00ff009186901b9190911617601081811c91901b1760e01b1660218201526025016120e5565b919050565b828054828255905f5260205f20908101928215613a2e575f5260205f209182015b82811115613a2e578254825591600101919060010190613a13565b50613a3a929150613a77565b5090565b828054828255905f5260205f20908101928215613a2e579160200282015b82811115613a2e578251825591602001919060010190613a5c565b5b80821115613a3a575f8155600101613a78565b602081525f82518060208401528060208501604085015e5f6040828501015260407fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0601f83011684010191505092915050565b6fffffffffffffffffffffffffffffffff851681526fffffffffffffffffffffffffffffffff84166020820152826040820152608060608201525f60c0820183516040608085015281815180845260e0860191506020830193505f92505b80831015613b5f5783518252602082019150602084019350600183019250613b3c565b50602086015160a086015280935050505095945050505050565b5f60608284031215613b89575f5ffd5b50919050565b5f5f83601f840112613b9f575f5ffd5b50813567ffffffffffffffff811115613bb6575f5ffd5b6020830191508360208260051b8501011115613bd0575f5ffd5b9250929050565b5f5f5f60408486031215613be9575f5ffd5b833567ffffffffffffffff811115613bff575f5ffd5b613c0b86828701613b79565b935050602084013567ffffffffffffffff811115613c27575f5ffd5b613c3386828701613b8f565b9497909650939450505050565b602080825282518282018190525f918401906040840190835b81811015613c77578351835260209384019390920191600101613c59565b509095945050505050565b5f5f5f60408486031215613c94575f5ffd5b833567ffffffffffffffff811115613caa575f5ffd5b613cb686828701613b8f565b909790965060209590950135949350505050565b5f60e08284031215613b89575f5ffd5b5f5f5f5f5f5f5f5f5f6101808a8c031215613cf3575f5ffd5b893567ffffffffffffffff811115613d09575f5ffd5b613d158c828d01613b79565b99505060208a013567ffffffffffffffff811115613d31575f5ffd5b613d3d8c828d01613b8f565b90995097505060408a013567ffffffffffffffff811115613d5c575f5ffd5b613d688c828d01613b8f565b9097509550613d7c90508b60608c01613cca565b93506101408a013567ffffffffffffffff811115613d98575f5ffd5b613da48c828d01613b8f565b9a9d999c50979a969995989497966101600135949350505050565b5f5f5f60408486031215613dd1575f5ffd5b83359250602084013567ffffffffffffffff811115613c27575f5ffd5b5f5f5f5f60608587031215613e01575f5ffd5b84359350602085013567ffffffffffffffff811115613e1e575f5ffd5b613e2a87828801613b8f565b9598909750949560400135949350505050565b5f60208284031215613e4d575f5ffd5b5035919050565b5f5f5f5f60608587031215613e67575f5ffd5b843567ffffffffffffffff811115613e7d575f5ffd5b613e8987828801613b79565b945050602085013567ffffffffffffffff811115613ea5575f5ffd5b613eb187828801613b8f565b909450925050604085013567ffffffffffffffff811115613ed0575f5ffd5b850160c08188031215613ee1575f5ffd5b939692955090935050565b5f60208284031215613efc575f5ffd5b813567ffffffffffffffff81168114610743575f5ffd5b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601160045260245ffd5b6fffffffffffffffffffffffffffffffff8181168382160190811115611ad357611ad3613f13565b5f60208284031215613f78575f5ffd5b813563ffffffff81168114610743575f5ffd5b5f7f07ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff831115613fb8575f5ffd5b8260051b80858437919091019392505050565b80820180821115611ad357611ad3613f13565b5f60208284031215613fee575f5ffd5b813573ffffffffffffffffffffffffffffffffffffffff81168114610743575f5ffd5b5f5f83357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe1843603018112614044575f5ffd5b83018035915067ffffffffffffffff82111561405e575f5ffd5b6020019150600581901b3603821315613bd0575f5ffd5b5f60208284031215614085575f5ffd5b813560ff81168114610743575f5ffd5b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601260045260245ffd5b5f826140d0576140d0614095565b500490565b81810381811115611ad357611ad3613f13565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52603260045260245ffd5b5f81518060208401855e5f93019283525090919050565b5f6141378286614115565b7fffffffff0000000000000000000000000000000000000000000000000000000094909416845250507fffffffffffffffff000000000000000000000000000000000000000000000000166004820152600c01919050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52604160045260245ffd5b5f826141ca576141ca614095565b500690565b5f82357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff41833603018112614201575f5ffd5b9190910192915050565b5f82357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc1833603018112614201575f5ffd5b6040805190810167ffffffffffffffff811182821017156142605761426061418f565b60405290565b604051601f82017fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe016810167ffffffffffffffff811182821017156142ad576142ad61418f565b604052919050565b80357fffff000000000000000000000000000000000000000000000000000000000000811681146139ed575f5ffd5b5f604082360312156142f4575f5ffd5b6142fc61423d565b614305836142b5565b8152602083013567ffffffffffffffff811115614320575f5ffd5b830136601f820112614330575f5ffd5b803567ffffffffffffffff81111561434a5761434a61418f565b61437b60207fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0601f84011601614266565b81815236602083850101111561438f575f5ffd5b816020840160208301375f6020928201830152908301525092915050565b80516020808301519190811015613b89577fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff60209190910360031b1b16919050565b60ff818116838216029081169081811461440b5761440b613f13565b5092915050565b8082028115828204841417611ad357611ad3613f13565b5f60208284031215614439575f5ffd5b610743826142b5565b5f5f83357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe1843603018112614475575f5ffd5b83018035915067ffffffffffffffff82111561448f575f5ffd5b602001915036819003821315613bd0575f5ffd5b5f6144ae8288614115565b7fffff000000000000000000000000000000000000000000000000000000000000871681526144e06002820187614115565b9050838582375f9301928352509095945050505050565b5f6107438284614115565b5f60208284031215614512575f5ffd5b5051919050565b5f6145248285614115565b9283525050602001919050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52602160045260245ffd5b5f60ff83168061457057614570614095565b8060ff84160691505092915050565b63ffffffff8181168382160190811115611ad357611ad3613f1356fea2646970667358221220e6ccdfee5d164c23f5ec1307885b9a5dd2de5dee0f6a141b4ebdd1d708400cca64736f6c634300081c003300000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000000c00000000000000000000000000000000000000000000000000000000000000650000000000000000000000000000000000000000000000000000000001be8c7000000000000000000000000000000000000000000000000000000000000049870000000000000000000000000000000000000000000000000000000000000014ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c00000000000000000000000000000000000000000000000000000000000049880000000000000000000000000000000000000000000000000000000000000014ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c

0x608060405234801561000f575f5ffd5b5060043610610149575f3560e01c806366ae69a0116100c7578063a77cf3d21161007d578063bb51f1eb11610063578063bb51f1eb14610383578063c7d6e93d14610396578063df0dd0d5146103a9575f5ffd5b8063a77cf3d214610349578063ad209a9b1461035c575f5ffd5b806383fe0ea0116100ad57806383fe0ea0146102ec5780638ab81d1314610313578063a401662b14610326575f5ffd5b806366ae69a0146102985780636f55bd32146102c5575f5ffd5b806341c9634e1161011c578063591d99ee11610102578063591d99ee146102495780635da57fe914610270578063623b223d14610283575f5ffd5b806341c9634e146102135780634b4cfb2814610229575f5ffd5b80630a7c8faa1461014d57806315fac8c6146101aa5780632cdea717146101f3578063366675131461020b575b5f5ffd5b6101747f6d6800000000000000000000000000000000000000000000000000000000000081565b6040517fffff00000000000000000000000000000000000000000000000000000000000090911681526020015b60405180910390f35b6101e66040518060400160405280601981526020017f534e4f574252494447452d464941542d5348414d49522d76310000000000000081525081565b6040516101a19190613a8b565b6101fb610443565b6040516101a19493929190613ade565b6101fb6104da565b61021b5f5481565b6040519081526020016101a1565b61023c610237366004613bd7565b61056f565b6040516101a19190613c40565b61021b7f000000000000000000000000000000000000000000000000000000000000000081565b61023c61027e366004613c82565b61074a565b610296610291366004613cda565b610799565b005b6001546102ac9067ffffffffffffffff1681565b60405167ffffffffffffffff90911681526020016101a1565b61021b7f000000000000000000000000000000000000000000000000000000000000000c81565b61021b7f000000000000000000000000000000000000000000000000000000000000006581565b61023c610321366004613dbf565b610c5c565b610339610334366004613dee565b610d5a565b60405190151581526020016101a1565b610296610357366004613e3d565b610d69565b61021b7f000000000000000000000000000000000000000000000000000000000000040081565b610296610391366004613e54565b610f58565b6102966103a4366004613cda565b611572565b6104066103b7366004613e3d565b600a6020525f908152604090208054600182015460029092015467ffffffffffffffff82169263ffffffff6801000000000000000084048116936c010000000000000000000000009004169185565b6040805167ffffffffffffffff96909616865263ffffffff948516602087015292909316918401919091526060830152608082015260a0016101a1565b6002805460035460408051600480546060602082028401810185529383018181526fffffffffffffffffffffffffffffffff80881698700100000000000000000000000000000000909804169694849284918401828280156104c257602002820191905f5260205f20905b8154815260200190600101908083116104ae575b50505050508152602001600182015481525050905084565b6006805460075460408051600880546060602082028401810185529383018181526fffffffffffffffffffffffffffffffff80881698700100000000000000000000000000000000909804169694849284918401828280156104c257602002820191905f5260205f20908154815260200190600101908083116104ae5750505050508152602001600182015481525050905084565b6006546060906002906fffffffffffffffffffffffffffffffff1661059a6040870160208801613eec565b67ffffffffffffffff16036105b157506006610617565b6002546fffffffffffffffffffffffffffffffff166105d66040870160208801613eec565b67ffffffffffffffff1614610617576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80546106489070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b831415806106e8575080546106829070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6106e68585808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b1561071f576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61072986612009565b80519060200120905061073e818686856120fb565b925050505b9392505050565b606082821015610786576040517f5c85a0e700000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61079184848461220c565b949350505050565b5f6107a38a612009565b8051906020012090505f6107c033835f9182526020526040902090565b90506107ce818c8c8c612297565b5f5f90505f6002905060065f015f9054906101000a90046fffffffffffffffffffffffffffffffff166fffffffffffffffffffffffffffffffff168d602001602081019061081c9190613eec565b67ffffffffffffffff160361083757506001905060066108bd565b60025f015f9054906101000a90046fffffffffffffffffffffffffffffffff166fffffffffffffffffffffffffffffffff168d602001602081019061087c9190613eec565b67ffffffffffffffff16146108bd576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6109218c8c808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050845470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b61093084848e8e858f8f6124b7565b5f61093a8e61270a565b90508215610b5657600654610962906fffffffffffffffffffffffffffffffff166001613f40565b6fffffffffffffffffffffffffffffffff1661098460808b0160608c01613eec565b67ffffffffffffffff16146109c5576040517fc72c820000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6109e2826109d38c61282c565b805190602001208b8b8b612928565b905080610a1b576040517f128597bb00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600680547001000000000000000000000000000000008082046fffffffffffffffffffffffffffffffff908116909102911617600290815560075460035560088054600490610a6d90829084906139f2565b5060019182015491015550610a8a905060808b0160608c01613eec565b600680547fffffffffffffffffffffffffffffffff000000000000000000000000000000001667ffffffffffffffff92909216919091179055610ad360a08b0160808c01613f68565b600680546fffffffffffffffffffffffffffffffff1663ffffffff929092167001000000000000000000000000000000000291909117905560a08a018035600755610b3090610b259060808d01613f68565b63ffffffff166129b0565b80518051600891610b4691839160200190613a3e565b5060208201518160010155905050505b5f819055610b6760208f018f613f68565b63ffffffff1660015f6101000a81548167ffffffffffffffff021916908367ffffffffffffffff160217905550600a5f8581526020019081526020015f205f5f82015f6101000a81549067ffffffffffffffff02191690555f820160086101000a81549063ffffffff02191690555f8201600c6101000a81549063ffffffff0219169055600182015f9055600282015f905550507fd95fe1258d152dc91c81b09380498adc76ed36a6079bcb2ed31eff622ae2d0f1818f5f016020810190610c2f9190613f68565b6040805192835263ffffffff90911660208301520160405180910390a15050505050505050505050505050565b60605f600a5f610c7533885f9182526020526040902090565b81526020019081526020015f2090508383604051602001610c97929190613f8b565b60405160208183030381529060405280519060200120816002015414610ce9576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b610d5181600101548585808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855463ffffffff680100000000000000008204811693506c01000000000000000000000000909104169050612a56565b95945050505050565b5f610d515f5486868686612928565b335f9081526020829052604081205f818152600a6020526040812080549293509167ffffffffffffffff169003610dcc576040517f6686db6400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600181015415610e08576040517fe31d900500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8054610e3f907f00000000000000000000000000000000000000000000000000000000000000009067ffffffffffffffff16613fcb565b431015610e78576040517fc77c194900000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80547f000000000000000000000000000000000000000000000000000000000000040090610ed1907f00000000000000000000000000000000000000000000000000000000000000009067ffffffffffffffff16613fcb565b610edb9190613fcb565b431115610f4d575f828152600a602052604080822080547fffffffffffffffffffffffffffffffff0000000000000000000000000000000016815560018101839055600201829055517f40d3544771f3c2382030d7a42c371f55cb608ac0eaf54ef2fa846da65af1b9859190a1505050565b446001909101555050565b60015467ffffffffffffffff16610f726020860186613f68565b63ffffffff1611610faf576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600280545f906fffffffffffffffffffffffffffffffff16610fd76040880160208901613eec565b67ffffffffffffffff160361101c57610ff560046060850135612b58565b9050611017606084013561100e61ffff84166001612bda565b60049190612bf8565b6110bc565b6006546fffffffffffffffffffffffffffffffff166110416040880160208901613eec565b67ffffffffffffffff160361108a5761105f60086060850135612b58565b9050611081606084013561107861ffff84166001612bda565b60089190612bf8565b600691506110bc565b6040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6110e7826110d060a0860160808701613fde565b60608601356110e260a0880188614011565b612cb8565b158061112f575061112d8585808060200260200160405190810160405280939291908181526020018383602002808284375f920191909152505050506060850135612d6e565b155b15611166576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61117087612009565b8051602090910120905061118a60a0850160808601613fde565b73ffffffffffffffffffffffffffffffffffffffff166111c0826111b16020880188614075565b87602001358860400135612db2565b73ffffffffffffffffffffffffffffffffffffffff161461120d576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b825461123e9070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b851415806112de575082546112789070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6112dc8787808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050875470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b15611315576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6113798686808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050865470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b6040805160a0810182524367ffffffffffffffff1681528454700100000000000000000000000000000000900463ffffffff8116602083015290918201906113f8906fffffffffffffffffffffffffffffffff1661ffff86167f000000000000000000000000000000000000000000000000000000000000000c612dde565b63ffffffff1681526020015f8152602001878760405160200161141c929190613f8b565b60405160208183030381529060405280519060200120815250600a5f61144b33855f9182526020526040902090565b815260208082019290925260409081015f2083518154858501519386015163ffffffff9081166c01000000000000000000000000027fffffffffffffffffffffffffffffffff00000000ffffffffffffffffffffffff9190951668010000000000000000027fffffffffffffffffffffffffffffffffffffffff00000000000000000000000090921667ffffffffffffffff909316929092171716919091178155606083015160018201556080909201516002909201919091557fbee983fc706c692efb9b0240bddc5666c010a53af55ed5fb42d226e7e4293869903390611535908a018a613f68565b6040805173ffffffffffffffffffffffffffffffffffffffff909316835263ffffffff90911660208301520160405180910390a150505050505050565b60015467ffffffffffffffff1661158c60208b018b613f68565b63ffffffff16116115c9576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6006545f906002906fffffffffffffffffffffffffffffffff166115f360408d0160208e01613eec565b67ffffffffffffffff160361160e5750600190506006611674565b6002546fffffffffffffffffffffffffffffffff1661163360408d0160208e01613eec565b67ffffffffffffffff1614611674576040517fc06789fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80546116a59070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611aba565b89141580611745575080546116df9070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff16611ad9565b6117438b8b808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050855470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150611afb9050565b105b1561177c576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6117e08a8a808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050845470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1691506123ec9050565b5f6117ea8c61270a565b90505f6117f68d612009565b80519060200120905061180d818d8d868e8e612e31565b8315611a1c57600654611833906fffffffffffffffffffffffffffffffff166001613f40565b6fffffffffffffffffffffffffffffffff1661185560808a0160608b01613eec565b67ffffffffffffffff1614611896576040517fc72c820000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6118b3836118a48b61282c565b805190602001208a8a8a612928565b9050806118ec576040517f128597bb00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600680547001000000000000000000000000000000008082046fffffffffffffffffffffffffffffffff90811690910291161760029081556007546003556008805460049061193e90829084906139f2565b506001918201549101555061195b905060808a0160608b01613eec565b600680547fffffffffffffffffffffffffffffffff000000000000000000000000000000001667ffffffffffffffff929092169190911790556119a460a08a0160808b01613f68565b600680546fffffffffffffffffffffffffffffffff1663ffffffff929092167001000000000000000000000000000000000291909117905560a0890180356007556119f690610b259060808c01613f68565b80518051600891611a0c91839160200190613a3e565b5060208201518160010155905050505b5f829055611a2d60208e018e613f68565b63ffffffff1660015f6101000a81548167ffffffffffffffff021916908367ffffffffffffffff1602179055507fd95fe1258d152dc91c81b09380498adc76ed36a6079bcb2ed31eff622ae2d0f1828e5f016020810190611a8e9190613f68565b6040805192835263ffffffff90911660208301520160405180910390a150505050505050505050505050565b5f610100611ac98360ff613fcb565b611ad391906140c2565b92915050565b5f6003611ae76001846140d5565b611af191906140c2565b611ad390836140d5565b5f811580611b0857508251155b15611b1457505f611ad3565b5f610100830460ff8416825b8281108015611b2f5750865181105b15611d8e575f878281518110611b4757611b476140e8565b602002602001015190507f5555555555555555555555555555555555555555555555555555555555555555600182901c167f555555555555555555555555555555555555555555555555555555555555555582160190507f3333333333333333333333333333333333333333333333333333333333333333600282901c167f333333333333333333333333333333333333333333333333333333333333333382160190507f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f600482901c167f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82160190507eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff600882901c167eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82160190507dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff601082901c167dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82160190507bffffffff00000000ffffffff00000000ffffffff00000000ffffffff602082901c167bffffffff00000000ffffffff00000000ffffffff00000000ffffffff821601905077ffffffffffffffff0000000000000000ffffffffffffffff604082901c1677ffffffffffffffff0000000000000000ffffffffffffffff82160190506fffffffffffffffffffffffffffffffff608082901c166fffffffffffffffffffffffffffffffff82160190508085019450508080600101915050611b20565b505f81118015611d9e5750855182105b15611fff575f6001826001901b0390505f81888581518110611dc257611dc26140e8565b60200260200101511690507f5555555555555555555555555555555555555555555555555555555555555555600182901c167f555555555555555555555555555555555555555555555555555555555555555582160190507f3333333333333333333333333333333333333333333333333333333333333333600282901c167f333333333333333333333333333333333333333333333333333333333333333382160190507f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f600482901c167f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f82160190507eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff600882901c167eff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff00ff82160190507dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff601082901c167dffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff0000ffff82160190507bffffffff00000000ffffffff00000000ffffffff00000000ffffffff602082901c167bffffffff00000000ffffffff00000000ffffffff00000000ffffffff821601905077ffffffffffffffff0000000000000000ffffffffffffffff604082901c1677ffffffffffffffff0000000000000000ffffffffffffffff82160190506fffffffffffffffffffffffffffffffff608082901c166fffffffffffffffffffffffffffffffff8216019050808501945050505b5090949350505050565b606061202061201b6040840184614011565b613039565b6120576120306020850185613f68565b600881811c62ff00ff1663ff00ff009290911b9190911617601081811c91901b1760e01b90565b6120d361206a6040860160208701613eec565b5f65ff000000ff00600883811b91821664ff000000ff9185901c91821617601090811b67ff000000ff0000009390931666ff000000ff00009290921691909117901c17602081811b6bffffffffffffffff000000001691901c63ffffffff161760c01b92915050565b6040516020016120e59392919061412c565b6040516020818303038152906040529050919050565b60605f8484604051602001612111929190613f8b565b6040516020818303038152906040528051906020012090505f61213587838661313e565b84549091505f90612196907f0000000000000000000000000000000000000000000000000000000000000065906121919070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff166132cd565b6132e4565b9050612200825f1c8888808060200260200160405190810160405280939291908181526020018383602002808284375f9201919091525050895470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150859050612a56565b98975050505050505050565b606061221782611aba565b67ffffffffffffffff81111561222f5761222f61418f565b604051908082528060200260200182016040528015612258578160200160208202803683370190505b5090505f5b8381101561228f576122878286868481811061227b5761227b6140e8565b905060200201356132f9565b60010161225d565b509392505050565b5f848152600a602052604081208054909167ffffffffffffffff90911690036122ec576040517f6686db6400000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b80600101545f03612329576040517f78ef3a4700000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b60015467ffffffffffffffff166123436020860186613f68565b63ffffffff1611612380576040517f3d618e5000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8282604051602001612393929190613f8b565b604051602081830303815290604052805190602001208160020154146123e5576040517f6768c0aa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5050505050565b5f6123f682611aba565b905080158061240457508251155b1561240e57505050565b5f61241b610100846141bc565b9050805f0361242a5750505050565b7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff811b5f8561245a6001866140d5565b8151811061246a5761246a6140e8565b602002602001015190508181165f146124af576040517f3dc5549600000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b505050505050565b5f868152600a6020526040902080546c01000000000000000000000000900463ffffffff16828114612515576040517f1f1711da00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f61258083600101548989808060200260200160405190810160405280939291908181526020018383602002808284375f92019190915250508a5470010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff169150869050612a56565b90505f5b848110156126fd573686868381811061259f5761259f6140e8565b90506020028101906125b191906141cf565b90506125d9886125c760a0840160808501613fde565b60608401356110e260a0860186614011565b61260f576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61261d838260600135612d6e565b612653576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b61266360a0820160808301613fde565b73ffffffffffffffffffffffffffffffffffffffff166126998d61268a6020850185614075565b84602001358560400135612db2565b73ffffffffffffffffffffffffffffffffffffffff16146126e6576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b6126f4838260600135613350565b50600101612584565b5050505050505050505050565b5f6127186040830183614011565b9050600114612753576040517f484ab7df00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f6127616040840184614011565b5f818110612771576127716140e8565b9050602002810190612783919061420b565b61278c906142e4565b80519091507fffff000000000000000000000000000000000000000000000000000000000000167f6d680000000000000000000000000000000000000000000000000000000000001415806127e75750806020015151602014155b1561281e576040517f484ab7df00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b8060200151610743906143ad565b606061284461283e6020840184614075565b60f81b90565b6128576120306040850160208601613f68565b604084013561286f61206a6080870160608801613eec565b61288261203060a0880160808901613f68565b6040517fff0000000000000000000000000000000000000000000000000000000000000090951660208601527fffffffff00000000000000000000000000000000000000000000000000000000938416602186015260258501929092527fffffffffffffffff00000000000000000000000000000000000000000000000016604584015216604d82015260a0830135605182015260c083013560718201526091016120e5565b5f610100831115612965576040517f5e862a8a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b845f5b848110156129a35761299982878784818110612986576129866140e8565b905060200201358387901c600116613384565b9150600101612968565b5090951495945050505050565b60408051808201909152606081525f60208201525f6129d06010846141bc565b156129dc5760016129de565b5f5b60ff166129ec6010856140c2565b6129f69190613fcb565b905060405180604001604052808267ffffffffffffffff811115612a1c57612a1c61418f565b604051908082528060200260200182016040528015612a45578160200160208202803683370190505b508152602001939093525090919050565b6060612a6183611aba565b8451141580612a785750612a758484611afb565b82115b15612aaf576040517f5f64a3e000000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b835167ffffffffffffffff811115612ac957612ac961418f565b604051908082528060200260200182016040528015612af2578160200160208202803683370190505b5090505f805b83821015612b4e575f612b0c8883886133ad565b9050612b188782612d6e565b1580612b295750612b298482612d6e565b15612b375750600101612af8565b612b4184826132f9565b5060019182019101612af8565b5050949350505050565b5f82600101548210612b96576040517f4e23d03500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600482901c600f8316612baa8160106143ef565b60ff16855f018381548110612bc157612bc16140e8565b905f5260205f200154901c61ffff169250505092915050565b5f82820161ffff80851690821610156107435761ffff915050611ad3565b82600101548210612c35576040517f4e23d03500000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600482901c600f83165f612c4a8260106143ef565b60ff1661ffff901b1990505f826010612c6391906143ef565b60ff168561ffff16901b90508082885f018681548110612c8557612c856140e8565b905f5260205f2001541617875f018581548110612ca457612ca46140e8565b5f9182526020909120015550505050505050565b6040517fffffffffffffffffffffffffffffffffffffffff000000000000000000000000606086901b1660208201525f908190603401604080518083037fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0018152919052805160209091012060018801548854919250612d63918390889070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff1688886133d0565b979650505050505050565b5f5f600883901c9050612da383858381518110612d8d57612d8d6140e8565b60200260200101516133fb90919063ffffffff16565b60ff1660011491505092915050565b5f5f5f5f612dc288888888613405565b925092509250612dd282826134f8565b50909695505050505050565b5f81612deb856001613604565b612df59082613fcb565b9050612e02846001613604565b612e0d906002614412565b612e18906001613fcb565b612e229082613fcb565b9050610d5181612191876132cd565b82545f90612e8a907f0000000000000000000000000000000000000000000000000000000000000065906121919070010000000000000000000000000000000090046fffffffffffffffffffffffffffffffff166132cd565b9050818114612ec5576040517f1f1711da00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b5f612ed2888888886120fb565b90505f5b8381101561302e5736858583818110612ef157612ef16140e8565b9050602002810190612f0391906141cf565b9050612f13838260600135612d6e565b612f49576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b612f5d876125c760a0840160808501613fde565b612f93576040517fe00153fa00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b612fa360a0820160808301613fde565b73ffffffffffffffffffffffffffffffffffffffff16612fca8b61268a6020850185614075565b73ffffffffffffffffffffffffffffffffffffffff1614613017576040517f8baa579f00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b613025838260600135613350565b50600101612ed6565b505050505050505050565b60605f61304583613641565b90505f5b8381101561228f5781858583818110613064576130646140e8565b9050602002810190613076919061420b565b613084906020810190614429565b6130c0878785818110613099576130996140e8565b90506020028101906130ab919061420b565b6130b9906020810190614442565b9050613641565b8787858181106130d2576130d26140e8565b90506020028101906130e4919061420b565b6130f2906020810190614442565b6040516020016131069594939291906144a3565b604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe08184030181529190529150600101613049565b604080518082018252601981527f534e4f574252494447452d464941542d5348414d49522d76310000000000000060208083019190915260018401548454845192830188905293820186905260608201526fffffffffffffffffffffffffffffffff808416608083015270010000000000000000000000000000000090930490921660a08301525f9160029190829060c001604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe081840301815290829052613208916144f7565b602060405180830381855afa158015613223573d5f5f3e3d5ffd5b5050506040513d601f19601f820116820180604052508101906132469190614502565b604051602001613257929190614519565b604080517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe08184030181529082905261328f916144f7565b602060405180830381855afa1580156132aa573d5f5f3e3d5ffd5b5050506040513d601f19601f820116820180604052508101906107919190614502565b5f6132d96003836140c2565b611ad3906001613fcb565b5f8183106132f25781610743565b5090919050565b5f600882901c905061332d82848381518110613317576133176140e8565b602002602001015161368a90919063ffffffff16565b83828151811061333f5761333f6140e8565b602002602001018181525050505050565b5f600882901c905061332d8284838151811061336e5761336e6140e8565b602002602001015161369790919063ffffffff16565b5f81801561339857835f52846020526133a0565b845f52836020525b505060405f209392505050565b5f815f036133bc57505f610743565b505f92835260209190915260409091200690565b5f8385106133df57505f6133f1565b6133ec86868686866136a5565b871490505b9695505050505050565b60ff161c60011690565b5f80807f7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a084111561343e57505f915060039050826134ee565b604080515f808252602082018084528a905260ff891692820192909252606081018790526080810186905260019060a0016020604051602081039080840390855afa15801561348f573d5f5f3e3d5ffd5b50506040517fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0015191505073ffffffffffffffffffffffffffffffffffffffff81166134e557505f9250600191508290506134ee565b92505f91508190505b9450945094915050565b5f82600381111561350b5761350b614531565b03613514575050565b600182600381111561352857613528614531565b0361355f576040517ff645eedf00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b600282600381111561357357613573614531565b036135b2576040517ffce698f7000000000000000000000000000000000000000000000000000000008152600481018290526024015b60405180910390fd5b60038260038111156135c6576135c6614531565b03613600576040517fd78bce0c000000000000000000000000000000000000000000000000000000008152600481018290526024016135a9565b5050565b5f5f61360f8461376a565b905061361a836137fd565b8015613629575083816001901b105b613633575f613636565b60015b60ff16019392505050565b606063ffffffff821115613681576040517fe809999a00000000000000000000000000000000000000000000000000000000815260040160405180910390fd5b611ad382613829565b600160ff919091161b1790565b600160ff919091161b191690565b5f85815b8381101561375f5786600116600114806136c557508587600101145b156136fc576136f58585838181106136df576136df6140e8565b90506020020135835f9182526020526040902090565b915061372a565b61372782868684818110613712576137126140e8565b905060200201355f9182526020526040902090565b91505b600196871c967fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff909601861c860195016136a9565b509695505050505050565b5f80608083901c1561377e57608092831c92015b604083901c1561379057604092831c92015b602083901c156137a257602092831c92015b601083901c156137b457601092831c92015b600883901c156137c657600892831c92015b600483901c156137d857600492831c92015b600283901c156137ea57600292831c92015b600183901c15611ad35760010192915050565b5f600282600381111561381257613812614531565b61381c919061455e565b60ff166001149050919050565b6060603f8263ffffffff1611613870576040517ffc0000000000000000000000000000000000000000000000000000000000000060fa84901b1660208201526021016120e5565b613fff8263ffffffff16116138e7576138ac6138986403fffffffc600285901b16600161457f565b600881811b62ffff001691901c60ff161790565b6040516020016120e5919060f09190911b7fffff00000000000000000000000000000000000000000000000000000000000016815260020190565b633fffffff8263ffffffff16116139715761393660028363ffffffff16901b6002613912919061457f565b600881811c62ff00ff1663ff00ff009290911b9190911617601081811c91901b1790565b6040516020016120e5919060e09190911b7fffffffff0000000000000000000000000000000000000000000000000000000016815260040190565b6040517f030000000000000000000000000000000000000000000000000000000000000060208201527fffffffff00000000000000000000000000000000000000000000000000000000600884811c62ff00ff1663ff00ff009186901b9190911617601081811c91901b1760e01b1660218201526025016120e5565b919050565b828054828255905f5260205f20908101928215613a2e575f5260205f209182015b82811115613a2e578254825591600101919060010190613a13565b50613a3a929150613a77565b5090565b828054828255905f5260205f20908101928215613a2e579160200282015b82811115613a2e578251825591602001919060010190613a5c565b5b80821115613a3a575f8155600101613a78565b602081525f82518060208401528060208501604085015e5f6040828501015260407fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0601f83011684010191505092915050565b6fffffffffffffffffffffffffffffffff851681526fffffffffffffffffffffffffffffffff84166020820152826040820152608060608201525f60c0820183516040608085015281815180845260e0860191506020830193505f92505b80831015613b5f5783518252602082019150602084019350600183019250613b3c565b50602086015160a086015280935050505095945050505050565b5f60608284031215613b89575f5ffd5b50919050565b5f5f83601f840112613b9f575f5ffd5b50813567ffffffffffffffff811115613bb6575f5ffd5b6020830191508360208260051b8501011115613bd0575f5ffd5b9250929050565b5f5f5f60408486031215613be9575f5ffd5b833567ffffffffffffffff811115613bff575f5ffd5b613c0b86828701613b79565b935050602084013567ffffffffffffffff811115613c27575f5ffd5b613c3386828701613b8f565b9497909650939450505050565b602080825282518282018190525f918401906040840190835b81811015613c77578351835260209384019390920191600101613c59565b509095945050505050565b5f5f5f60408486031215613c94575f5ffd5b833567ffffffffffffffff811115613caa575f5ffd5b613cb686828701613b8f565b909790965060209590950135949350505050565b5f60e08284031215613b89575f5ffd5b5f5f5f5f5f5f5f5f5f6101808a8c031215613cf3575f5ffd5b893567ffffffffffffffff811115613d09575f5ffd5b613d158c828d01613b79565b99505060208a013567ffffffffffffffff811115613d31575f5ffd5b613d3d8c828d01613b8f565b90995097505060408a013567ffffffffffffffff811115613d5c575f5ffd5b613d688c828d01613b8f565b9097509550613d7c90508b60608c01613cca565b93506101408a013567ffffffffffffffff811115613d98575f5ffd5b613da48c828d01613b8f565b9a9d999c50979a969995989497966101600135949350505050565b5f5f5f60408486031215613dd1575f5ffd5b83359250602084013567ffffffffffffffff811115613c27575f5ffd5b5f5f5f5f60608587031215613e01575f5ffd5b84359350602085013567ffffffffffffffff811115613e1e575f5ffd5b613e2a87828801613b8f565b9598909750949560400135949350505050565b5f60208284031215613e4d575f5ffd5b5035919050565b5f5f5f5f60608587031215613e67575f5ffd5b843567ffffffffffffffff811115613e7d575f5ffd5b613e8987828801613b79565b945050602085013567ffffffffffffffff811115613ea5575f5ffd5b613eb187828801613b8f565b909450925050604085013567ffffffffffffffff811115613ed0575f5ffd5b850160c08188031215613ee1575f5ffd5b939692955090935050565b5f60208284031215613efc575f5ffd5b813567ffffffffffffffff81168114610743575f5ffd5b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601160045260245ffd5b6fffffffffffffffffffffffffffffffff8181168382160190811115611ad357611ad3613f13565b5f60208284031215613f78575f5ffd5b813563ffffffff81168114610743575f5ffd5b5f7f07ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff831115613fb8575f5ffd5b8260051b80858437919091019392505050565b80820180821115611ad357611ad3613f13565b5f60208284031215613fee575f5ffd5b813573ffffffffffffffffffffffffffffffffffffffff81168114610743575f5ffd5b5f5f83357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe1843603018112614044575f5ffd5b83018035915067ffffffffffffffff82111561405e575f5ffd5b6020019150600581901b3603821315613bd0575f5ffd5b5f60208284031215614085575f5ffd5b813560ff81168114610743575f5ffd5b7f4e487b71000000000000000000000000000000000000000000000000000000005f52601260045260245ffd5b5f826140d0576140d0614095565b500490565b81810381811115611ad357611ad3613f13565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52603260045260245ffd5b5f81518060208401855e5f93019283525090919050565b5f6141378286614115565b7fffffffff0000000000000000000000000000000000000000000000000000000094909416845250507fffffffffffffffff000000000000000000000000000000000000000000000000166004820152600c01919050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52604160045260245ffd5b5f826141ca576141ca614095565b500690565b5f82357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff41833603018112614201575f5ffd5b9190910192915050565b5f82357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc1833603018112614201575f5ffd5b6040805190810167ffffffffffffffff811182821017156142605761426061418f565b60405290565b604051601f82017fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe016810167ffffffffffffffff811182821017156142ad576142ad61418f565b604052919050565b80357fffff000000000000000000000000000000000000000000000000000000000000811681146139ed575f5ffd5b5f604082360312156142f4575f5ffd5b6142fc61423d565b614305836142b5565b8152602083013567ffffffffffffffff811115614320575f5ffd5b830136601f820112614330575f5ffd5b803567ffffffffffffffff81111561434a5761434a61418f565b61437b60207fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe0601f84011601614266565b81815236602083850101111561438f575f5ffd5b816020840160208301375f6020928201830152908301525092915050565b80516020808301519190811015613b89577fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff60209190910360031b1b16919050565b60ff818116838216029081169081811461440b5761440b613f13565b5092915050565b8082028115828204841417611ad357611ad3613f13565b5f60208284031215614439575f5ffd5b610743826142b5565b5f5f83357fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe1843603018112614475575f5ffd5b83018035915067ffffffffffffffff82111561448f575f5ffd5b602001915036819003821315613bd0575f5ffd5b5f6144ae8288614115565b7fffff000000000000000000000000000000000000000000000000000000000000871681526144e06002820187614115565b9050838582375f9301928352509095945050505050565b5f6107438284614115565b5f60208284031215614512575f5ffd5b5051919050565b5f6145248285614115565b9283525050602001919050565b7f4e487b71000000000000000000000000000000000000000000000000000000005f52602160045260245ffd5b5f60ff83168061457057614570614095565b8060ff84160691505092915050565b63ffffffff8181168382160190811115611ad357611ad3613f1356fea2646970667358221220e6ccdfee5d164c23f5ec1307885b9a5dd2de5dee0f6a141b4ebdd1d708400cca64736f6c634300081c0033

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000000c00000000000000000000000000000000000000000000000000000000000000650000000000000000000000000000000000000000000000000000000001be8c7000000000000000000000000000000000000000000000000000000000000049870000000000000000000000000000000000000000000000000000000000000014ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c00000000000000000000000000000000000000000000000000000000000049880000000000000000000000000000000000000000000000000000000000000014ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c

-----Decoded View---------------
Arg [0] : _randaoCommitDelay (uint256): 0
Arg [1] : _randaoCommitExpiration (uint256): 1024
Arg [2] : _minNumRequiredSignatures (uint256): 12
Arg [3] : _fiatShamirRequiredSignatures (uint256): 101
Arg [4] : _initialBeefyBlock (uint64): 29265008
Arg [5] : _initialValidatorSet (tuple): 
     Arg [1] : id (uint128): 18823
     Arg [2] : length (uint128): 20
     Arg [3] : root (bytes32): 0xff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c

Arg [6] : _nextValidatorSet (tuple): 
     Arg [1] : id (uint128): 18824
     Arg [2] : length (uint128): 20
     Arg [3] : root (bytes32): 0xff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c


-----Encoded View---------------
11 Constructor Arguments found :
Arg [0] : 0000000000000000000000000000000000000000000000000000000000000000
Arg [1] : 0000000000000000000000000000000000000000000000000000000000000400
Arg [2] : 000000000000000000000000000000000000000000000000000000000000000c
Arg [3] : 0000000000000000000000000000000000000000000000000000000000000065
Arg [4] : 0000000000000000000000000000000000000000000000000000000001be8c70
Arg [5] : 0000000000000000000000000000000000000000000000000000000000004987
Arg [6] : 0000000000000000000000000000000000000000000000000000000000000014
Arg [7] : ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c
Arg [8] : 0000000000000000000000000000000000000000000000000000000000004988
Arg [9] : 0000000000000000000000000000000000000000000000000000000000000014
Arg [10] : ff1d13b4dc453f2f88261fbc1ec53922bce47d740489c9022bed06f345395f8c