// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

import { Params } from "./utilities/Params.sol";
import { SnarkCommon } from "./crypto/SnarkCommon.sol";
import { IPoll } from "./interfaces/IPoll.sol";
import { Utilities } from "./utilities/Utilities.sol";
import { CurveBabyJubJub } from "./crypto/BabyJubJub.sol";

/// @title Poll
/// @notice A Poll contract allows voters to submit encrypted messages
/// which can be either votes or key change messages.
/// @dev Do not deploy this directly. Use PollFactory.deploy() which performs some
/// checks on the Poll constructor arguments.
contract Poll is Params, Utilities, SnarkCommon, IPoll {
  /// @notice Whether the Poll has been initialized
  bool internal isInit;

  /// @notice The coordinator's public key
  PubKey public coordinatorPubKey;

  /// @notice Hash of the coordinator's public key
  uint256 public immutable coordinatorPubKeyHash;

  /// @notice the state root of the state merkle tree
  uint256 public mergedStateRoot;

  // The timestamp of the block at which the Poll was deployed
  uint256 internal immutable deployTime;

  // The duration of the polling period, in seconds
  uint256 internal immutable duration;

  /// @notice The root of the empty ballot tree at a given voteOptionTree depth
  uint256 public immutable emptyBallotRoot;

  /// @notice Whether the MACI contract's stateAq has been merged by this contract
  bool public stateMerged;

  /// @notice Get the commitment to the state leaves and the ballots. This is
  /// hash3(stateRoot, ballotRoot, salt).
  /// Its initial value should be
  /// hash(maciStateRootSnapshot, emptyBallotRoot, 0)
  /// Each successful invocation of processMessages() should use a different
  /// salt to update this value, so that an external observer cannot tell in
  /// the case that none of the messages are valid.
  uint256 public currentSbCommitment;

  /// @notice The number of messages that have been published
  uint256 public numMessages;

  /// @notice The number of signups that have been processed
  /// before the Poll ended (stateAq merged)
  uint256 public numSignups;

  /// @notice The actual depth of the state tree
  /// to be used as public input for the circuit
  uint8 public actualStateTreeDepth;

  /// @notice Depths of the merkle trees
  TreeDepths public treeDepths;

  /// @notice The contracts used by the Poll
  ExtContracts public extContracts;

  /// @notice The max number of messages
  uint256 public immutable maxMessages;

  /// @notice The number of children per node in the merkle trees
  uint256 internal constant TREE_ARITY = 5;

  error VotingPeriodOver();
  error VotingPeriodNotOver();
  error PollAlreadyInit();
  error TooManyMessages();
  error InvalidPubKey();
  error StateAlreadyMerged();
  error InvalidBatchLength();

  event PublishMessage(Message _message, PubKey _encPubKey);
  event MergeMaciState(uint256 indexed _stateRoot, uint256 indexed _numSignups);
  event MergeMessageAqSubRoots(uint256 indexed _numSrQueueOps);
  event MergeMessageAq(uint256 indexed _messageRoot);

  /// @notice Each MACI instance can have multiple Polls.
  /// When a Poll is deployed, its voting period starts immediately.
  /// @param _duration The duration of the voting period, in seconds
  /// @param _treeDepths The depths of the merkle trees
  /// @param _coordinatorPubKey The coordinator's public key
  /// @param _extContracts The external contracts
  constructor(
    uint256 _duration,
    TreeDepths memory _treeDepths,
    PubKey memory _coordinatorPubKey,
    ExtContracts memory _extContracts,
    uint256 _emptyBallotRoot
  ) payable {
    // check that the coordinator public key is valid
    if (!CurveBabyJubJub.isOnCurve(_coordinatorPubKey.x, _coordinatorPubKey.y)) {
      revert InvalidPubKey();
    }

    // store the pub key as object then calculate the hash
    coordinatorPubKey = _coordinatorPubKey;
    // we hash it ourselves to ensure we store the correct value
    coordinatorPubKeyHash = hashLeftRight(_coordinatorPubKey.x, _coordinatorPubKey.y);
    // store the external contracts to interact with
    extContracts = _extContracts;
    // store duration of the poll
    duration = _duration;
    // store tree depth
    treeDepths = _treeDepths;
    // Record the current timestamp
    deployTime = block.timestamp;
    // store the empty ballot root
    emptyBallotRoot = _emptyBallotRoot;
    // store max messages
    maxMessages = TREE_ARITY ** _treeDepths.messageTreeDepth;
  }

  /// @notice A modifier that causes the function to revert if the voting period is
  /// not over.
  modifier isAfterVotingDeadline() {
    uint256 secondsPassed = block.timestamp - deployTime;
    if (secondsPassed <= duration) revert VotingPeriodNotOver();
    _;
  }

  /// @notice A modifier that causes the function to revert if the voting period is
  /// over
  modifier isWithinVotingDeadline() {
    uint256 secondsPassed = block.timestamp - deployTime;
    if (secondsPassed >= duration) revert VotingPeriodOver();
    _;
  }

  /// @notice The initialization function.
  /// @dev Should be called immediately after Poll creation
  /// and messageAq ownership transferred
  function init() public {
    if (isInit) revert PollAlreadyInit();
    // set to true so it cannot be called again
    isInit = true;

    unchecked {
      numMessages++;
    }

    // init messageAq here by inserting placeholderLeaf
    uint256[2] memory dat;
    dat[0] = NOTHING_UP_MY_SLEEVE;
    dat[1] = 0;

    (Message memory _message, PubKey memory _padKey, uint256 placeholderLeaf) = padAndHashMessage(dat);
    extContracts.messageAq.enqueue(placeholderLeaf);

    emit PublishMessage(_message, _padKey);
  }

  /// @inheritdoc IPoll
  function publishMessage(Message memory _message, PubKey calldata _encPubKey) public virtual isWithinVotingDeadline {
    // we check that we do not exceed the max number of messages
    if (numMessages >= maxMessages) revert TooManyMessages();

    // check if the public key is on the curve
    if (!CurveBabyJubJub.isOnCurve(_encPubKey.x, _encPubKey.y)) {
      revert InvalidPubKey();
    }

    // cannot realistically overflow
    unchecked {
      numMessages++;
    }

    uint256 messageLeaf = hashMessageAndEncPubKey(_message, _encPubKey);
    extContracts.messageAq.enqueue(messageLeaf);

    emit PublishMessage(_message, _encPubKey);
  }

  /// @notice submit a message batch
  /// @dev Can only be submitted before the voting deadline
  /// @param _messages the messages
  /// @param _encPubKeys the encrypted public keys
  function publishMessageBatch(Message[] calldata _messages, PubKey[] calldata _encPubKeys) external {
    if (_messages.length != _encPubKeys.length) {
      revert InvalidBatchLength();
    }

    uint256 len = _messages.length;
    for (uint256 i = 0; i < len; ) {
      // an event will be published by this function already
      publishMessage(_messages[i], _encPubKeys[i]);

      unchecked {
        i++;
      }
    }
  }

  /// @inheritdoc IPoll
  function mergeMaciState() public isAfterVotingDeadline {
    // This function can only be called once per Poll after the voting
    // deadline
    if (stateMerged) revert StateAlreadyMerged();

    // set merged to true so it cannot be called again
    stateMerged = true;

    uint256 _mergedStateRoot = extContracts.maci.getStateTreeRoot();
    mergedStateRoot = _mergedStateRoot;

    // Set currentSbCommitment
    uint256[3] memory sb;
    sb[0] = _mergedStateRoot;
    sb[1] = emptyBallotRoot;
    sb[2] = uint256(0);

    currentSbCommitment = hash3(sb);

    // get number of signups and cache in a var for later use
    uint256 _numSignups = extContracts.maci.numSignUps();
    numSignups = _numSignups;

    // dynamically determine the actual depth of the state tree
    uint8 depth = 1;
    while (uint40(1 << depth) < _numSignups) {
      depth++;
    }

    actualStateTreeDepth = depth;

    emit MergeMaciState(_mergedStateRoot, _numSignups);
  }

  /// @inheritdoc IPoll
  function mergeMessageAqSubRoots(uint256 _numSrQueueOps) public isAfterVotingDeadline {
    extContracts.messageAq.mergeSubRoots(_numSrQueueOps);
    emit MergeMessageAqSubRoots(_numSrQueueOps);
  }

  /// @inheritdoc IPoll
  function mergeMessageAq() public isAfterVotingDeadline {
    uint256 root = extContracts.messageAq.merge(treeDepths.messageTreeDepth);
    emit MergeMessageAq(root);
  }

  /// @inheritdoc IPoll
  function getDeployTimeAndDuration() public view returns (uint256 pollDeployTime, uint256 pollDuration) {
    pollDeployTime = deployTime;
    pollDuration = duration;
  }

  /// @inheritdoc IPoll
  function numSignUpsAndMessages() public view returns (uint256 numSUps, uint256 numMsgs) {
    numSUps = numSignups;
    numMsgs = numMessages;
  }
}

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

pragma solidity ^0.8.20;

import {Context} from "../utils/Context.sol";

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

    /**
     * @dev The caller account is not authorized to perform an operation.
     */
    error OwnableUnauthorizedAccount(address account);

    /**
     * @dev The owner is not a valid owner account. (eg. `address(0)`)
     */
    error OwnableInvalidOwner(address owner);

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

    /**
     * @dev Initializes the contract setting the address provided by the deployer as the initial owner.
     */
    constructor(address initialOwner) {
        if (initialOwner == address(0)) {
            revert OwnableInvalidOwner(address(0));
        }
        _transferOwnership(initialOwner);
    }

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

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

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        if (owner() != _msgSender()) {
            revert OwnableUnauthorizedAccount(_msgSender());
        }
    }

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

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        if (newOwner == address(0)) {
            revert OwnableInvalidOwner(address(0));
        }
        _transferOwnership(newOwner);
    }

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

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.1) (utils/Context.sol)

pragma solidity ^0.8.20;

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

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

    function _contextSuffixLength() internal view virtual returns (uint256) {
        return 0;
    }
}

// @note This code was taken from
// https://github.com/yondonfu/sol-baby-jubjub/blob/master/contracts/CurveBabyJubJub.sol
// Thanks to yondonfu for the code
// Implementation cited on baby-jubjub's paper
// https://eips.ethereum.org/EIPS/eip-2494#implementation

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

library CurveBabyJubJub {
  // Curve parameters
  // E: 168700x^2 + y^2 = 1 + 168696x^2y^2
  // A = 168700
  uint256 public constant A = 0x292FC;
  // D = 168696
  uint256 public constant D = 0x292F8;
  // Prime Q = 21888242871839275222246405745257275088548364400416034343698204186575808495617
  uint256 public constant Q = 0x30644E72E131A029B85045B68181585D2833E84879B9709143E1F593F0000001;

  /**
   * @dev Add 2 points on baby jubjub curve
   * Formula for adding 2 points on a twisted Edwards curve:
   * x3 = (x1y2 + y1x2) / (1 + dx1x2y1y2)
   * y3 = (y1y2 - ax1x2) / (1 - dx1x2y1y2)
   */
  function pointAdd(uint256 _x1, uint256 _y1, uint256 _x2, uint256 _y2) internal view returns (uint256 x3, uint256 y3) {
    if (_x1 == 0 && _y1 == 0) {
      return (_x2, _y2);
    }

    if (_x2 == 0 && _y1 == 0) {
      return (_x1, _y1);
    }

    uint256 x1x2 = mulmod(_x1, _x2, Q);
    uint256 y1y2 = mulmod(_y1, _y2, Q);
    uint256 dx1x2y1y2 = mulmod(D, mulmod(x1x2, y1y2, Q), Q);
    uint256 x3Num = addmod(mulmod(_x1, _y2, Q), mulmod(_y1, _x2, Q), Q);
    uint256 y3Num = submod(y1y2, mulmod(A, x1x2, Q), Q);

    x3 = mulmod(x3Num, inverse(addmod(1, dx1x2y1y2, Q)), Q);
    y3 = mulmod(y3Num, inverse(submod(1, dx1x2y1y2, Q)), Q);
  }

  /**
   * @dev Double a point on baby jubjub curve
   * Doubling can be performed with the same formula as addition
   */
  function pointDouble(uint256 _x1, uint256 _y1) internal view returns (uint256 x2, uint256 y2) {
    return pointAdd(_x1, _y1, _x1, _y1);
  }

  /**
   * @dev Multiply a point on baby jubjub curve by a scalar
   * Use the double and add algorithm
   */
  function pointMul(uint256 _x1, uint256 _y1, uint256 _d) internal view returns (uint256 x2, uint256 y2) {
    uint256 remaining = _d;

    uint256 px = _x1;
    uint256 py = _y1;
    uint256 ax = 0;
    uint256 ay = 0;

    while (remaining != 0) {
      if ((remaining & 1) != 0) {
        // Binary digit is 1 so add
        (ax, ay) = pointAdd(ax, ay, px, py);
      }

      (px, py) = pointDouble(px, py);

      remaining = remaining / 2;
    }

    x2 = ax;
    y2 = ay;
  }

  /**
   * @dev Check if a given point is on the curve
   * (168700x^2 + y^2) - (1 + 168696x^2y^2) == 0
   */
  function isOnCurve(uint256 _x, uint256 _y) internal pure returns (bool) {
    uint256 xSq = mulmod(_x, _x, Q);
    uint256 ySq = mulmod(_y, _y, Q);
    uint256 lhs = addmod(mulmod(A, xSq, Q), ySq, Q);
    uint256 rhs = addmod(1, mulmod(mulmod(D, xSq, Q), ySq, Q), Q);
    return submod(lhs, rhs, Q) == 0;
  }

  /**
   * @dev Perform modular subtraction
   */
  function submod(uint256 _a, uint256 _b, uint256 _mod) internal pure returns (uint256) {
    uint256 aNN = _a;

    if (_a <= _b) {
      aNN += _mod;
    }

    return addmod(aNN - _b, 0, _mod);
  }

  /**
   * @dev Compute modular inverse of a number
   */
  function inverse(uint256 _a) internal view returns (uint256) {
    // We can use Euler's theorem instead of the extended Euclidean algorithm
    // Since m = Q and Q is prime we have: a^-1 = a^(m - 2) (mod m)
    return expmod(_a, Q - 2, Q);
  }

  /**
   * @dev Helper function to call the bigModExp precompile
   */
  function expmod(uint256 _b, uint256 _e, uint256 _m) internal view returns (uint256 o) {
    assembly {
      let memPtr := mload(0x40)
      mstore(memPtr, 0x20) // Length of base _b
      mstore(add(memPtr, 0x20), 0x20) // Length of exponent _e
      mstore(add(memPtr, 0x40), 0x20) // Length of modulus _m
      mstore(add(memPtr, 0x60), _b) // Base _b
      mstore(add(memPtr, 0x80), _e) // Exponent _e
      mstore(add(memPtr, 0xa0), _m) // Modulus _m

      // The bigModExp precompile is at 0x05
      let success := staticcall(gas(), 0x05, memPtr, 0xc0, memPtr, 0x20)
      switch success
      case 0 {
        revert(0x0, 0x0)
      }
      default {
        o := mload(memPtr)
      }
    }
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

import { SnarkConstants } from "./SnarkConstants.sol";
import { PoseidonT3 } from "./PoseidonT3.sol";
import { PoseidonT4 } from "./PoseidonT4.sol";
import { PoseidonT5 } from "./PoseidonT5.sol";
import { PoseidonT6 } from "./PoseidonT6.sol";

/// @notice A SHA256 hash function for any number of input elements, and Poseidon hash
/// functions for 2, 3, 4, 5, and 12 input elements.
contract Hasher is SnarkConstants {
  /// @notice Computes the SHA256 hash of an array of uint256 elements.
  /// @param array The array of uint256 elements.
  /// @return result The SHA256 hash of the array.
  function sha256Hash(uint256[] memory array) public pure returns (uint256 result) {
    result = uint256(sha256(abi.encodePacked(array))) % SNARK_SCALAR_FIELD;
  }

  /// @notice Computes the Poseidon hash of two uint256 elements.
  /// @param array An array of two uint256 elements.
  /// @return result The Poseidon hash of the two elements.
  function hash2(uint256[2] memory array) public pure returns (uint256 result) {
    result = PoseidonT3.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of three uint256 elements.
  /// @param array An array of three uint256 elements.
  /// @return result The Poseidon hash of the three elements.
  function hash3(uint256[3] memory array) public pure returns (uint256 result) {
    result = PoseidonT4.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of four uint256 elements.
  /// @param array An array of four uint256 elements.
  /// @return result The Poseidon hash of the four elements.
  function hash4(uint256[4] memory array) public pure returns (uint256 result) {
    result = PoseidonT5.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of five uint256 elements.
  /// @param array An array of five uint256 elements.
  /// @return result The Poseidon hash of the five elements.
  function hash5(uint256[5] memory array) public pure returns (uint256 result) {
    result = PoseidonT6.poseidon(array);
  }

  /// @notice Computes the Poseidon hash of two uint256 elements.
  /// @param left the first element to hash.
  /// @param right the second element to hash.
  /// @return result The Poseidon hash of the two elements.
  function hashLeftRight(uint256 left, uint256 right) public pure returns (uint256 result) {
    uint256[2] memory input;
    input[0] = left;
    input[1] = right;
    result = hash2(input);
  }
}

// SPDX-License-Identifier: MIT
// Copyright 2017 Christian Reitwiessner
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to
// deal in the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.

// 2019 OKIMS

pragma solidity ^0.8.20;

/// @title Pairing
/// @notice A library implementing the alt_bn128 elliptic curve operations.
library Pairing {
  uint256 public constant PRIME_Q = 21888242871839275222246405745257275088696311157297823662689037894645226208583;

  struct G1Point {
    uint256 x;
    uint256 y;
  }

  // Encoding of field elements is: X[0] * z + X[1]
  struct G2Point {
    uint256[2] x;
    uint256[2] y;
  }

  /// @notice custom errors
  error PairingAddFailed();
  error PairingMulFailed();
  error PairingOpcodeFailed();

  /// @notice The negation of p, i.e. p.plus(p.negate()) should be zero.
  function negate(G1Point memory p) internal pure returns (G1Point memory) {
    // The prime q in the base field F_q for G1
    if (p.x == 0 && p.y == 0) {
      return G1Point(0, 0);
    } else {
      return G1Point(p.x, PRIME_Q - (p.y % PRIME_Q));
    }
  }

  /// @notice r Returns the sum of two points of G1.
  function plus(G1Point memory p1, G1Point memory p2) internal view returns (G1Point memory r) {
    uint256[4] memory input;
    input[0] = p1.x;
    input[1] = p1.y;
    input[2] = p2.x;
    input[3] = p2.y;
    bool success;

    // solhint-disable-next-line no-inline-assembly
    assembly {
      success := staticcall(sub(gas(), 2000), 6, input, 0xc0, r, 0x60)
      // Use "invalid" to make gas estimation work
      switch success
      case 0 {
        invalid()
      }
    }

    if (!success) {
      revert PairingAddFailed();
    }
  }

  /// @notice r Return the product of a point on G1 and a scalar, i.e.
  ///         p == p.scalarMul(1) and p.plus(p) == p.scalarMul(2) for all
  ///         points p.
  function scalarMul(G1Point memory p, uint256 s) internal view returns (G1Point memory r) {
    uint256[3] memory input;
    input[0] = p.x;
    input[1] = p.y;
    input[2] = s;
    bool success;
    // solhint-disable-next-line no-inline-assembly
    assembly {
      success := staticcall(sub(gas(), 2000), 7, input, 0x80, r, 0x60)
      // Use "invalid" to make gas estimation work
      switch success
      case 0 {
        invalid()
      }
    }

    if (!success) {
      revert PairingMulFailed();
    }
  }

  /// @return isValid The result of computing the pairing check
  ///         e(p1[0], p2[0]) *  .... * e(p1[n], p2[n]) == 1
  ///        For example,
  ///        pairing([P1(), P1().negate()], [P2(), P2()]) should return true.
  function pairing(
    G1Point memory a1,
    G2Point memory a2,
    G1Point memory b1,
    G2Point memory b2,
    G1Point memory c1,
    G2Point memory c2,
    G1Point memory d1,
    G2Point memory d2
  ) internal view returns (bool isValid) {
    G1Point[4] memory p1;
    p1[0] = a1;
    p1[1] = b1;
    p1[2] = c1;
    p1[3] = d1;

    G2Point[4] memory p2;
    p2[0] = a2;
    p2[1] = b2;
    p2[2] = c2;
    p2[3] = d2;

    uint256 inputSize = 24;
    uint256[] memory input = new uint256[](inputSize);

    for (uint8 i = 0; i < 4; ) {
      uint8 j = i * 6;
      input[j + 0] = p1[i].x;
      input[j + 1] = p1[i].y;
      input[j + 2] = p2[i].x[0];
      input[j + 3] = p2[i].x[1];
      input[j + 4] = p2[i].y[0];
      input[j + 5] = p2[i].y[1];

      unchecked {
        i++;
      }
    }

    uint256[1] memory out;
    bool success;

    // solhint-disable-next-line no-inline-assembly
    assembly {
      success := staticcall(sub(gas(), 2000), 8, add(input, 0x20), mul(inputSize, 0x20), out, 0x20)
      // Use "invalid" to make gas estimation work
      switch success
      case 0 {
        invalid()
      }
    }

    if (!success) {
      revert PairingOpcodeFailed();
    }

    isValid = out[0] != 0;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT3 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[2] memory input) public pure returns (uint256) {}
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT4 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[3] memory input) public pure returns (uint256) {}
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT5 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[4] memory input) public pure returns (uint256) {}
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @notice A library which provides functions for computing Pedersen hashes.
library PoseidonT6 {
  // solhint-disable-next-line no-empty-blocks
  function poseidon(uint256[5] memory input) public pure returns (uint256) {}
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;
import { Pairing } from "./Pairing.sol";

/// @title SnarkCommon
/// @notice a Contract which holds a struct
/// representing a Groth16 verifying key
contract SnarkCommon {
  /// @notice a struct representing a Groth16 verifying key
  struct VerifyingKey {
    Pairing.G1Point alpha1;
    Pairing.G2Point beta2;
    Pairing.G2Point gamma2;
    Pairing.G2Point delta2;
    Pairing.G1Point[] ic;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @title SnarkConstants
/// @notice This contract contains constants related to the SNARK
/// components of MACI.
contract SnarkConstants {
  /// @notice The scalar field
  uint256 internal constant SNARK_SCALAR_FIELD =
    21888242871839275222246405745257275088548364400416034343698204186575808495617;

  /// @notice The public key here is the first Pedersen base
  /// point from iden3's circomlib implementation of the Pedersen hash.
  /// Since it is generated using a hash-to-curve function, we are
  /// confident that no-one knows the private key associated with this
  /// public key. See:
  /// https://github.com/iden3/circomlib/blob/d5ed1c3ce4ca137a6b3ca48bec4ac12c1b38957a/src/pedersen_printbases.js
  /// Its hash should equal
  /// 6769006970205099520508948723718471724660867171122235270773600567925038008762.
  uint256 internal constant PAD_PUBKEY_X =
    10457101036533406547632367118273992217979173478358440826365724437999023779287;
  uint256 internal constant PAD_PUBKEY_Y =
    19824078218392094440610104313265183977899662750282163392862422243483260492317;

  /// @notice The Keccack256 hash of 'Maci'
  uint256 internal constant NOTHING_UP_MY_SLEEVE =
    8370432830353022751713833565135785980866757267633941821328460903436894336785;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @title IMACI
/// @notice MACI interface
interface IMACI {
  /// @notice Get the depth of the state tree
  /// @return The depth of the state tree
  function stateTreeDepth() external view returns (uint8);

  /// @notice Return the main root of the StateAq contract
  /// @return The Merkle root
  function getStateTreeRoot() external view returns (uint256);

  /// @notice Get the number of signups
  /// @return numsignUps The number of signups
  function numSignUps() external view returns (uint256);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.10;

import { DomainObjs } from "../utilities/DomainObjs.sol";
import { IMACI } from "./IMACI.sol";
import { AccQueue } from "../trees/AccQueue.sol";

/// @title IPoll
/// @notice Poll interface
interface IPoll {
  /// @notice The number of messages which have been processed and the number of signups
  /// @return numSignups The number of signups
  /// @return numMsgs The number of messages sent by voters
  function numSignUpsAndMessages() external view returns (uint256 numSignups, uint256 numMsgs);

  /// @notice Allows anyone to publish a message (an encrypted command and signature).
  /// This function also enqueues the message.
  /// @param _message The message to publish
  /// @param _encPubKey An ephemeral public key which can be combined with the
  /// coordinator's private key to generate an ECDH shared key with which
  /// to encrypt the message.
  function publishMessage(DomainObjs.Message memory _message, DomainObjs.PubKey calldata _encPubKey) external;

  /// @notice The second step of merging the MACI state AccQueue. This allows the
  /// ProcessMessages circuit to access the latest state tree and ballots via
  /// currentSbCommitment.
  function mergeMaciState() external;

  /// @notice The first step in merging the message AccQueue so that the
  /// ProcessMessages circuit can access the message root.
  /// @param _numSrQueueOps The number of subroot queue operations to perform
  function mergeMessageAqSubRoots(uint256 _numSrQueueOps) external;

  /// @notice The second step in merging the message AccQueue so that the
  /// ProcessMessages circuit can access the message root.
  function mergeMessageAq() external;

  /// @notice Returns the Poll's deploy time and duration
  /// @return _deployTime The deployment timestamp
  /// @return _duration The duration of the poll
  function getDeployTimeAndDuration() external view returns (uint256 _deployTime, uint256 _duration);

  /// @notice Get the result of whether the MACI contract's stateAq has been merged by this contract
  /// @return Whether the MACI contract's stateAq has been merged by this contract
  function stateMerged() external view returns (bool);

  /// @notice Get the depths of the merkle trees
  /// @return intStateTreeDepth The depth of the state tree
  /// @return messageTreeSubDepth The subdepth of the message tree
  /// @return messageTreeDepth The depth of the message tree
  /// @return voteOptionTreeDepth The subdepth of the vote option tree
  function treeDepths()
    external
    view
    returns (uint8 intStateTreeDepth, uint8 messageTreeSubDepth, uint8 messageTreeDepth, uint8 voteOptionTreeDepth);

  /// @notice Get the external contracts
  /// @return maci The IMACI contract
  /// @return messageAq The AccQueue contract
  function extContracts() external view returns (IMACI maci, AccQueue messageAq);

  /// @notice Get the hash of coordinator's public key
  /// @return _coordinatorPubKeyHash the hash of coordinator's public key
  function coordinatorPubKeyHash() external view returns (uint256 _coordinatorPubKeyHash);

  /// @notice Get the commitment to the state leaves and the ballots. This is
  /// hash3(stateRoot, ballotRoot, salt).
  /// Its initial value should be
  /// hash(maciStateRootSnapshot, emptyBallotRoot, 0)
  /// Each successful invocation of processMessages() should use a different
  /// salt to update this value, so that an external observer cannot tell in
  /// the case that none of the messages are valid.
  /// @return The commitment to the state leaves and the ballots
  function currentSbCommitment() external view returns (uint256);

  /// @notice Get the dynamic depth of the state tree at the time of poll
  /// finalization (based on the number of leaves inserted)
  function actualStateTreeDepth() external view returns (uint8);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

import { Ownable } from "@openzeppelin/contracts/access/Ownable.sol";
import { Hasher } from "../crypto/Hasher.sol";

/// @title AccQueue
/// @notice This contract defines a Merkle tree where each leaf insertion only updates a
/// subtree. To obtain the main tree root, the contract owner must merge the
/// subtrees together. Merging subtrees requires at least 2 operations:
/// mergeSubRoots(), and merge(). To get around the gas limit,
/// the mergeSubRoots() can be performed in multiple transactions.
abstract contract AccQueue is Ownable(msg.sender), Hasher {
  // The maximum tree depth
  uint256 public constant MAX_DEPTH = 32;

  /// @notice A Queue is a 2D array of Merkle roots and indices which represents nodes
  /// in a Merkle tree while it is progressively updated.
  struct Queue {
    /// @notice IMPORTANT: the following declares an array of b elements of type T: T[b]
    /// And the following declares an array of b elements of type T[a]: T[a][b]
    /// As such, the following declares an array of MAX_DEPTH+1 arrays of
    /// uint256[4] arrays, **not the other way round**:
    uint256[4][MAX_DEPTH + 1] levels;
    uint256[MAX_DEPTH + 1] indices;
  }

  // The depth of each subtree
  uint256 internal immutable subDepth;

  // The number of elements per hash operation. Should be either 2 (for
  // binary trees) or 5 (quinary trees). The limit is 5 because that is the
  // maximum supported number of inputs for the EVM implementation of the
  // Poseidon hash function
  uint256 internal immutable hashLength;

  // hashLength ** subDepth
  uint256 internal immutable subTreeCapacity;

  // True hashLength == 2, false if hashLength == 5
  bool internal isBinary;

  // The index of the current subtree. e.g. the first subtree has index 0, the
  // second has 1, and so on
  uint256 internal currentSubtreeIndex;

  // Tracks the current subtree.
  Queue internal leafQueue;

  // Tracks the smallest tree of subroots
  Queue internal subRootQueue;

  // Subtree roots
  mapping(uint256 => uint256) internal subRoots;

  // Merged roots
  uint256[MAX_DEPTH + 1] internal mainRoots;

  // Whether the subtrees have been merged
  bool public subTreesMerged;

  // Whether entire merkle tree has been merged
  bool public treeMerged;

  // The root of the shortest possible tree which fits all current subtree
  // roots
  uint256 internal smallSRTroot;

  // Tracks the next subroot to queue
  uint256 internal nextSubRootIndex;

  // The number of leaves inserted across all subtrees so far
  uint256 public numLeaves;

  /// @notice custom errors
  error SubDepthCannotBeZero();
  error SubdepthTooLarge(uint256 _subDepth, uint256 max);
  error InvalidHashLength();
  error DepthCannotBeZero();
  error SubTreesAlreadyMerged();
  error NothingToMerge();
  error SubTreesNotMerged();
  error DepthTooLarge(uint256 _depth, uint256 max);
  error DepthTooSmall(uint256 _depth, uint256 min);
  error InvalidIndex(uint256 _index);
  error InvalidLevel();

  /// @notice Create a new AccQueue
  /// @param _subDepth The depth of each subtree.
  /// @param _hashLength The number of leaves per node (2 or 5).
  constructor(uint256 _subDepth, uint256 _hashLength) payable {
    /// validation
    if (_subDepth == 0) revert SubDepthCannotBeZero();
    if (_subDepth > MAX_DEPTH) revert SubdepthTooLarge(_subDepth, MAX_DEPTH);
    if (_hashLength != 2 && _hashLength != 5) revert InvalidHashLength();

    isBinary = _hashLength == 2;
    subDepth = _subDepth;
    hashLength = _hashLength;
    subTreeCapacity = _hashLength ** _subDepth;
  }

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which require
  /// different input array lengths.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return _hash The hash of the level and leaf.
  // solhint-disable-next-line no-empty-blocks
  function hashLevel(uint256 _level, uint256 _leaf) internal virtual returns (uint256 _hash) {}

  /// @notice Hash the contents of the specified level and the specified leaf.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which require
  /// different input array lengths.
  /// @param _level The level to hash.
  /// @param _leaf The leaf include with the level.
  /// @return _hash The hash of the level and leaf.
  // solhint-disable-next-line no-empty-blocks
  function hashLevelLeaf(uint256 _level, uint256 _leaf) public view virtual returns (uint256 _hash) {}

  /// @notice Returns the zero leaf at a specified level.
  /// This is a virtual function as the hash function which the overriding
  /// contract uses will be either hashLeftRight or hash5, which will produce
  /// different zero values (e.g. hashLeftRight(0, 0) vs
  /// hash5([0, 0, 0, 0, 0]). Moreover, the zero value may be a
  /// nothing-up-my-sleeve value.
  /// @param _level The level at which to return the zero leaf.
  /// @return zero The zero leaf at the specified level.
  // solhint-disable-next-line no-empty-blocks
  function getZero(uint256 _level) internal virtual returns (uint256 zero) {}

  /// @notice Add a leaf to the queue for the current subtree.
  /// @param _leaf The leaf to add.
  /// @return leafIndex The index of the leaf in the queue.
  function enqueue(uint256 _leaf) public onlyOwner returns (uint256 leafIndex) {
    leafIndex = numLeaves;
    // Recursively queue the leaf
    _enqueue(_leaf, 0);

    // Update the leaf counter
    numLeaves = leafIndex + 1;

    // Now that a new leaf has been added, mainRoots and smallSRTroot are
    // obsolete
    delete mainRoots;
    delete smallSRTroot;
    subTreesMerged = false;

    // If a subtree is full
    if (numLeaves % subTreeCapacity == 0) {
      // Store the subroot
      subRoots[currentSubtreeIndex] = leafQueue.levels[subDepth][0];

      // Increment the index
      currentSubtreeIndex++;

      // Delete ancillary data
      delete leafQueue.levels[subDepth][0];
      delete leafQueue.indices;
    }
  }

  /// @notice Updates the queue at a given level and hashes any subroots
  /// that need to be hashed.
  /// @param _leaf The leaf to add.
  /// @param _level The level at which to queue the leaf.
  function _enqueue(uint256 _leaf, uint256 _level) internal {
    if (_level > subDepth) {
      revert InvalidLevel();
    }

    while (true) {
      uint256 n = leafQueue.indices[_level];

      if (n != hashLength - 1) {
        // Just store the leaf
        leafQueue.levels[_level][n] = _leaf;

        if (_level != subDepth) {
          // Update the index
          leafQueue.indices[_level]++;
        }

        return;
      }

      // Hash the leaves to next level
      _leaf = hashLevel(_level, _leaf);

      // Reset the index for this level
      delete leafQueue.indices[_level];

      // Queue the hash of the leaves into to the next level
      _level++;
    }
  }

  /// @notice Fill any empty leaves of the current subtree with zeros and store the
  /// resulting subroot.
  function fill() public onlyOwner {
    if (numLeaves % subTreeCapacity == 0) {
      // If the subtree is completely empty, then the subroot is a
      // precalculated zero value
      subRoots[currentSubtreeIndex] = getZero(subDepth);
    } else {
      // Otherwise, fill the rest of the subtree with zeros
      _fill(0);

      // Store the subroot
      subRoots[currentSubtreeIndex] = leafQueue.levels[subDepth][0];

      // Reset the subtree data
      delete leafQueue.levels;

      // Reset the merged roots
      delete mainRoots;
    }

    // Increment the subtree index
    uint256 curr = currentSubtreeIndex + 1;
    currentSubtreeIndex = curr;

    // Update the number of leaves
    numLeaves = curr * subTreeCapacity;

    // Reset the subroot tree root now that it is obsolete
    delete smallSRTroot;

    subTreesMerged = false;
  }

  /// @notice A function that queues zeros to the specified level, hashes,
  /// the level, and enqueues the hash to the next level.
  /// @param _level The level at which to queue zeros.
  // solhint-disable-next-line no-empty-blocks
  function _fill(uint256 _level) internal virtual {}

  /// Insert a subtree. Used for batch enqueues.
  function insertSubTree(uint256 _subRoot) public onlyOwner {
    subRoots[currentSubtreeIndex] = _subRoot;

    // Increment the subtree index
    currentSubtreeIndex++;

    // Update the number of leaves
    numLeaves += subTreeCapacity;

    // Reset the subroot tree root now that it is obsolete
    delete smallSRTroot;

    subTreesMerged = false;
  }

  /// @notice Calculate the lowest possible height of a tree with
  /// all the subroots merged together.
  /// @return depth The lowest possible height of a tree with all the
  function calcMinHeight() public view returns (uint256 depth) {
    depth = 1;
    while (true) {
      if (hashLength ** depth >= currentSubtreeIndex) {
        break;
      }
      depth++;
    }
  }

  /// @notice Merge all subtrees to form the shortest possible tree.
  /// This function can be called either once to merge all subtrees in a
  /// single transaction, or multiple times to do the same in multiple
  /// transactions.
  /// @param _numSrQueueOps The number of times this function will call
  ///                       queueSubRoot(), up to the maximum number of times
  ///                       necessary. If it is set to 0, it will call
  ///                       queueSubRoot() as many times as is necessary. Set
  ///                       this to a low number and call this function
  ///                       multiple times if there are many subroots to
  ///                       merge, or a single transaction could run out of
  ///                       gas.
  function mergeSubRoots(uint256 _numSrQueueOps) public onlyOwner {
    // This function can only be called once unless a new subtree is created
    if (subTreesMerged) revert SubTreesAlreadyMerged();

    // There must be subtrees to merge
    if (numLeaves == 0) revert NothingToMerge();

    // Fill any empty leaves in the current subtree with zeros only if the
    // current subtree is not full
    if (numLeaves % subTreeCapacity != 0) {
      fill();
    }

    // If there is only 1 subtree, use its root
    if (currentSubtreeIndex == 1) {
      smallSRTroot = getSubRoot(0);
      subTreesMerged = true;
      return;
    }

    uint256 depth = calcMinHeight();

    uint256 queueOpsPerformed = 0;
    for (uint256 i = nextSubRootIndex; i < currentSubtreeIndex; i++) {
      if (_numSrQueueOps != 0 && queueOpsPerformed == _numSrQueueOps) {
        // If the limit is not 0, stop if the limit has been reached
        return;
      }

      // Queue the next subroot
      queueSubRoot(getSubRoot(nextSubRootIndex), 0, depth);

      // Increment the next subroot counter
      nextSubRootIndex++;

      // Increment the ops counter
      queueOpsPerformed++;
    }

    // The height of the tree of subroots
    uint256 m = hashLength ** depth;

    // Queue zeroes to fill out the SRT
    if (nextSubRootIndex == currentSubtreeIndex) {
      uint256 z = getZero(subDepth);
      for (uint256 i = currentSubtreeIndex; i < m; i++) {
        queueSubRoot(z, 0, depth);
      }
    }

    // Store the smallest main root
    smallSRTroot = subRootQueue.levels[depth][0];
    subTreesMerged = true;
  }

  /// @notice Queues a subroot into the subroot tree.
  /// @param _leaf The value to queue.
  /// @param _level The level at which to queue _leaf.
  /// @param _maxDepth The depth of the tree.
  function queueSubRoot(uint256 _leaf, uint256 _level, uint256 _maxDepth) internal {
    if (_level > _maxDepth) {
      return;
    }

    uint256 n = subRootQueue.indices[_level];

    if (n != hashLength - 1) {
      // Just store the leaf
      subRootQueue.levels[_level][n] = _leaf;
      subRootQueue.indices[_level]++;
    } else {
      // Hash the elements in this level and queue it in the next level
      uint256 hashed;
      if (isBinary) {
        uint256[2] memory inputs;
        inputs[0] = subRootQueue.levels[_level][0];
        inputs[1] = _leaf;
        hashed = hash2(inputs);
      } else {
        uint256[5] memory inputs;
        for (uint8 i = 0; i < n; i++) {
          inputs[i] = subRootQueue.levels[_level][i];
        }
        inputs[n] = _leaf;
        hashed = hash5(inputs);
      }

      // TODO: change recursion to a while loop
      // Recurse
      delete subRootQueue.indices[_level];
      queueSubRoot(hashed, _level + 1, _maxDepth);
    }
  }

  /// @notice Merge all subtrees to form a main tree with a desired depth.
  /// @param _depth The depth of the main tree. It must fit all the leaves or
  ///               this function will revert.
  /// @return root The root of the main tree.
  function merge(uint256 _depth) public onlyOwner returns (uint256 root) {
    // The tree depth must be more than 0
    if (_depth == 0) revert DepthCannotBeZero();

    // Ensure that the subtrees have been merged
    if (!subTreesMerged) revert SubTreesNotMerged();

    // Check the depth
    if (_depth > MAX_DEPTH) revert DepthTooLarge(_depth, MAX_DEPTH);

    // Calculate the SRT depth
    uint256 srtDepth = subDepth;
    while (true) {
      if (hashLength ** srtDepth >= numLeaves) {
        break;
      }
      srtDepth++;
    }

    if (_depth < srtDepth) revert DepthTooSmall(_depth, srtDepth);

    // If the depth is the same as the SRT depth, just use the SRT root
    if (_depth == srtDepth) {
      mainRoots[_depth] = smallSRTroot;
      treeMerged = true;
      return smallSRTroot;
    } else {
      root = smallSRTroot;

      // Calculate the main root

      for (uint256 i = srtDepth; i < _depth; i++) {
        uint256 z = getZero(i);

        if (isBinary) {
          uint256[2] memory inputs;
          inputs[0] = root;
          inputs[1] = z;
          root = hash2(inputs);
        } else {
          uint256[5] memory inputs;
          inputs[0] = root;
          inputs[1] = z;
          inputs[2] = z;
          inputs[3] = z;
          inputs[4] = z;
          root = hash5(inputs);
        }
      }

      mainRoots[_depth] = root;
      treeMerged = true;
    }
  }

  /// @notice Returns the subroot at the specified index. Reverts if the index refers
  /// to a subtree which has not been filled yet.
  /// @param _index The subroot index.
  /// @return subRoot The subroot at the specified index.
  function getSubRoot(uint256 _index) public view returns (uint256 subRoot) {
    if (currentSubtreeIndex <= _index) revert InvalidIndex(_index);
    subRoot = subRoots[_index];
  }

  /// @notice Returns the subroot tree (SRT) root. Its value must first be computed
  /// using mergeSubRoots.
  /// @return smallSubTreeRoot The SRT root.
  function getSmallSRTroot() public view returns (uint256 smallSubTreeRoot) {
    if (!subTreesMerged) revert SubTreesNotMerged();
    smallSubTreeRoot = smallSRTroot;
  }

  /// @notice Return the merged Merkle root of all the leaves at a desired depth.
  /// @dev merge() or merged(_depth) must be called first.
  /// @param _depth The depth of the main tree. It must first be computed
  ///               using mergeSubRoots() and merge().
  /// @return mainRoot The root of the main tree.
  function getMainRoot(uint256 _depth) public view returns (uint256 mainRoot) {
    if (hashLength ** _depth < numLeaves) revert DepthTooSmall(_depth, numLeaves);

    mainRoot = mainRoots[_depth];
  }

  /// @notice Get the next subroot index and the current subtree index.
  function getSrIndices() public view returns (uint256 next, uint256 current) {
    next = nextSubRootIndex;
    current = currentSubtreeIndex;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/// @title DomainObjs
/// @notice An utility contract that holds
/// a number of domain objects and functions
contract DomainObjs {
  /// @notice the length of a MACI message
  uint8 public constant MESSAGE_DATA_LENGTH = 10;

  /// @notice voting modes
  enum Mode {
    QV,
    NON_QV
  }

  /// @title Message
  /// @notice this struct represents a MACI message
  /// @dev msgType: 1 for vote message
  struct Message {
    uint256[MESSAGE_DATA_LENGTH] data;
  }

  /// @title PubKey
  /// @notice A MACI public key
  struct PubKey {
    uint256 x;
    uint256 y;
  }

  /// @title StateLeaf
  /// @notice A MACI state leaf
  /// @dev used to represent a user's state
  /// in the state Merkle tree
  struct StateLeaf {
    PubKey pubKey;
    uint256 voiceCreditBalance;
    uint256 timestamp;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

import { IMACI } from "../interfaces/IMACI.sol";
import { AccQueue } from "../trees/AccQueue.sol";

/// @title Params
/// @notice This contracts contains a number of structures
/// which are to be passed as parameters to Poll contracts.
/// This way we can reduce the number of parameters
/// and avoid a stack too deep error during compilation.
contract Params {
  /// @notice A struct holding the depths of the merkle trees
  struct TreeDepths {
    uint8 intStateTreeDepth;
    uint8 messageTreeSubDepth;
    uint8 messageTreeDepth;
    uint8 voteOptionTreeDepth;
  }

  /// @notice A struct holding the external contracts
  /// that are to be passed to a Poll contract on
  /// deployment
  struct ExtContracts {
    IMACI maci;
    AccQueue messageAq;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

import { DomainObjs } from "./DomainObjs.sol";
import { Hasher } from "../crypto/Hasher.sol";
import { SnarkConstants } from "../crypto/SnarkConstants.sol";

/// @title Utilities
/// @notice An utility contract that can be used to:
/// * hash a state leaf
/// * pad and hash a MACI message
/// * hash a MACI message and an encryption public key
contract Utilities is SnarkConstants, DomainObjs, Hasher {
  /// @notice custom errors
  error InvalidMessage();

  /// @notice An utility function used to hash a state leaf
  /// @param _stateLeaf the state leaf to be hashed
  /// @return ciphertext The hash of the state leaf
  function hashStateLeaf(StateLeaf memory _stateLeaf) public pure returns (uint256 ciphertext) {
    uint256[4] memory plaintext;
    plaintext[0] = _stateLeaf.pubKey.x;
    plaintext[1] = _stateLeaf.pubKey.y;
    plaintext[2] = _stateLeaf.voiceCreditBalance;
    plaintext[3] = _stateLeaf.timestamp;

    ciphertext = hash4(plaintext);
  }

  /// @notice An utility function used to pad and hash a MACI message
  /// @param dataToPad the data to be padded
  /// @return message The padded message
  /// @return padKey The padding public key
  /// @return msgHash The hash of the padded message and encryption key
  function padAndHashMessage(
    uint256[2] memory dataToPad
  ) public pure returns (Message memory message, PubKey memory padKey, uint256 msgHash) {
    // add data and pad it to 10 elements (automatically cause it's the default value)
    uint256[10] memory dat;
    dat[0] = dataToPad[0];
    dat[1] = dataToPad[1];

    padKey = PubKey(PAD_PUBKEY_X, PAD_PUBKEY_Y);
    message = Message({ data: dat });
    msgHash = hashMessageAndEncPubKey(message, padKey);
  }

  /// @notice An utility function used to hash a MACI message and an encryption public key
  /// @param _message the message to be hashed
  /// @param _encPubKey the encryption public key to be hashed
  /// @return msgHash The hash of the message and the encryption public key
  function hashMessageAndEncPubKey(
    Message memory _message,
    PubKey memory _encPubKey
  ) public pure returns (uint256 msgHash) {
    if (_message.data.length != 10) {
      revert InvalidMessage();
    }

    uint256[5] memory n;
    n[0] = _message.data[0];
    n[1] = _message.data[1];
    n[2] = _message.data[2];
    n[3] = _message.data[3];
    n[4] = _message.data[4];

    uint256[5] memory m;
    m[0] = _message.data[5];
    m[1] = _message.data[6];
    m[2] = _message.data[7];
    m[3] = _message.data[8];
    m[4] = _message.data[9];

    msgHash = hash4([hash5(n), hash5(m), _encPubKey.x, _encPubKey.y]);
  }
}

{
  "optimizer": {
    "enabled": true,
    "runs": 200
  },
  "evmVersion": "paris",
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "libraries": {
    "contracts/crypto/PoseidonT3.sol": {
      "PoseidonT3": "0x88c2c6a7535463962a34757fe63cc4f296381aba"
    },
    "contracts/crypto/PoseidonT4.sol": {
      "PoseidonT4": "0xf8e637e5c9ec3a8d8fa8843a6df833348e1f1e66"
    },
    "contracts/crypto/PoseidonT5.sol": {
      "PoseidonT5": "0x0a0d66bafda8c8838281084d9c3d68dd9a6fc274"
    },
    "contracts/crypto/PoseidonT6.sol": {
      "PoseidonT6": "0xd2f6c828606ad8e985008cd825012f269b50cd58"
    }
  }
}

[{"inputs":[{"internalType":"uint256","name":"_duration","type":"uint256"},{"components":[{"internalType":"uint8","name":"intStateTreeDepth","type":"uint8"},{"internalType":"uint8","name":"messageTreeSubDepth","type":"uint8"},{"internalType":"uint8","name":"messageTreeDepth","type":"uint8"},{"internalType":"uint8","name":"voteOptionTreeDepth","type":"uint8"}],"internalType":"struct Params.TreeDepths","name":"_treeDepths","type":"tuple"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey","name":"_coordinatorPubKey","type":"tuple"},{"components":[{"internalType":"contract IMACI","name":"maci","type":"address"},{"internalType":"contract AccQueue","name":"messageAq","type":"address"}],"internalType":"struct Params.ExtContracts","name":"_extContracts","type":"tuple"},{"internalType":"uint256","name":"_emptyBallotRoot","type":"uint256"}],"stateMutability":"payable","type":"constructor"},{"inputs":[],"name":"InvalidBatchLength","type":"error"},{"inputs":[],"name":"InvalidMessage","type":"error"},{"inputs":[],"name":"InvalidPubKey","type":"error"},{"inputs":[],"name":"PollAlreadyInit","type":"error"},{"inputs":[],"name":"StateAlreadyMerged","type":"error"},{"inputs":[],"name":"TooManyMessages","type":"error"},{"inputs":[],"name":"VotingPeriodNotOver","type":"error"},{"inputs":[],"name":"VotingPeriodOver","type":"error"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint256","name":"_stateRoot","type":"uint256"},{"indexed":true,"internalType":"uint256","name":"_numSignups","type":"uint256"}],"name":"MergeMaciState","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint256","name":"_messageRoot","type":"uint256"}],"name":"MergeMessageAq","type":"event"},{"anonymous":false,"inputs":[{"indexed":true,"internalType":"uint256","name":"_numSrQueueOps","type":"uint256"}],"name":"MergeMessageAqSubRoots","type":"event"},{"anonymous":false,"inputs":[{"components":[{"internalType":"uint256[10]","name":"data","type":"uint256[10]"}],"indexed":false,"internalType":"struct DomainObjs.Message","name":"_message","type":"tuple"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"indexed":false,"internalType":"struct DomainObjs.PubKey","name":"_encPubKey","type":"tuple"}],"name":"PublishMessage","type":"event"},{"inputs":[],"name":"MESSAGE_DATA_LENGTH","outputs":[{"internalType":"uint8","name":"","type":"uint8"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"actualStateTreeDepth","outputs":[{"internalType":"uint8","name":"","type":"uint8"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"coordinatorPubKey","outputs":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"coordinatorPubKeyHash","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"currentSbCommitment","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"emptyBallotRoot","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"extContracts","outputs":[{"internalType":"contract IMACI","name":"maci","type":"address"},{"internalType":"contract AccQueue","name":"messageAq","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"getDeployTimeAndDuration","outputs":[{"internalType":"uint256","name":"pollDeployTime","type":"uint256"},{"internalType":"uint256","name":"pollDuration","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256[2]","name":"array","type":"uint256[2]"}],"name":"hash2","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[3]","name":"array","type":"uint256[3]"}],"name":"hash3","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[4]","name":"array","type":"uint256[4]"}],"name":"hash4","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256[5]","name":"array","type":"uint256[5]"}],"name":"hash5","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"internalType":"uint256","name":"left","type":"uint256"},{"internalType":"uint256","name":"right","type":"uint256"}],"name":"hashLeftRight","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"components":[{"internalType":"uint256[10]","name":"data","type":"uint256[10]"}],"internalType":"struct DomainObjs.Message","name":"_message","type":"tuple"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey","name":"_encPubKey","type":"tuple"}],"name":"hashMessageAndEncPubKey","outputs":[{"internalType":"uint256","name":"msgHash","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"components":[{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey","name":"pubKey","type":"tuple"},{"internalType":"uint256","name":"voiceCreditBalance","type":"uint256"},{"internalType":"uint256","name":"timestamp","type":"uint256"}],"internalType":"struct DomainObjs.StateLeaf","name":"_stateLeaf","type":"tuple"}],"name":"hashStateLeaf","outputs":[{"internalType":"uint256","name":"ciphertext","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[],"name":"init","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"maxMessages","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"mergeMaciState","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"mergeMessageAq","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256","name":"_numSrQueueOps","type":"uint256"}],"name":"mergeMessageAqSubRoots","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[],"name":"mergedStateRoot","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"numMessages","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"numSignUpsAndMessages","outputs":[{"internalType":"uint256","name":"numSUps","type":"uint256"},{"internalType":"uint256","name":"numMsgs","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"numSignups","outputs":[{"internalType":"uint256","name":"","type":"uint256"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"uint256[2]","name":"dataToPad","type":"uint256[2]"}],"name":"padAndHashMessage","outputs":[{"components":[{"internalType":"uint256[10]","name":"data","type":"uint256[10]"}],"internalType":"struct DomainObjs.Message","name":"message","type":"tuple"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey","name":"padKey","type":"tuple"},{"internalType":"uint256","name":"msgHash","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[{"components":[{"internalType":"uint256[10]","name":"data","type":"uint256[10]"}],"internalType":"struct DomainObjs.Message","name":"_message","type":"tuple"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey","name":"_encPubKey","type":"tuple"}],"name":"publishMessage","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"components":[{"internalType":"uint256[10]","name":"data","type":"uint256[10]"}],"internalType":"struct DomainObjs.Message[]","name":"_messages","type":"tuple[]"},{"components":[{"internalType":"uint256","name":"x","type":"uint256"},{"internalType":"uint256","name":"y","type":"uint256"}],"internalType":"struct DomainObjs.PubKey[]","name":"_encPubKeys","type":"tuple[]"}],"name":"publishMessageBatch","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"uint256[]","name":"array","type":"uint256[]"}],"name":"sha256Hash","outputs":[{"internalType":"uint256","name":"result","type":"uint256"}],"stateMutability":"pure","type":"function"},{"inputs":[],"name":"stateMerged","outputs":[{"internalType":"bool","name":"","type":"bool"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"treeDepths","outputs":[{"internalType":"uint8","name":"intStateTreeDepth","type":"uint8"},{"internalType":"uint8","name":"messageTreeSubDepth","type":"uint8"},{"internalType":"uint8","name":"messageTreeDepth","type":"uint8"},{"internalType":"uint8","name":"voteOptionTreeDepth","type":"uint8"}],"stateMutability":"view","type":"function"}]

0x6101206040526040516200212c3803806200212c8339810160408190526200002791620003da565b825160208401516200003a91906200013a565b62000058576040516379fae7af60e01b815260040160405180910390fd5b8251600181905560208401516002819055620000759190620001ef565b6080528151600a80546001600160a01b039283166001600160a01b031991821617909155602080850151600b80549190941692169190911790915560c08690528451600980549287015160408801805160608a015160ff90811663010000000263ff0000001992821662010000029290921663ffff0000199482166101000261ffff199098169190961617959095179190911692909217929092179091554260a05260e0829052516200012a906005620005c8565b61010052506200066f9350505050565b6000806000805160206200210c833981519152848509905060006000805160206200210c833981519152848509905060006000805160206200210c833981519152826000805160206200210c83398151915285620292fc0908905060006000805160206200210c83398151915280846000805160206200210c83398151915287620292f809096001089050620001e182826000805160206200210c83398151915262000218565b159450505050505b92915050565b6000620001fb620002db565b8381526020810183905262000210816200025b565b949350505050565b60008383811162000232576200022f8382620005f6565b90505b8280620002435762000243620005e0565b60006200025186846200060c565b0895945050505050565b6040516314d2f97b60e11b81526000907388c2c6a7535463962a34757fe63cc4f296381aba906329a5f2f6906200029790859060040162000622565b602060405180830381865af4158015620002b5573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190620001e9919062000655565b60405180604001604052806002906020820280368337509192915050565b604080519081016001600160401b03811182821017156200032a57634e487b7160e01b600052604160045260246000fd5b60405290565b604051608081016001600160401b03811182821017156200032a57634e487b7160e01b600052604160045260246000fd5b805160ff811681146200037357600080fd5b919050565b6001600160a01b03811681146200038e57600080fd5b50565b600060408284031215620003a457600080fd5b620003ae620002f9565b90508151620003bd8162000378565b81526020820151620003cf8162000378565b602082015292915050565b6000806000806000858703610140811215620003f557600080fd5b865195506080601f19820112156200040c57600080fd5b6200041662000330565b620004246020890162000361565b8152620004346040890162000361565b6020820152620004476060890162000361565b60408201526200045a6080890162000361565b606082015294506040609f19820112156200047457600080fd5b506200047f620002f9565b60a0870151815260c087015160208201529250620004a18760e0880162000391565b915061012086015190509295509295909350565b634e487b7160e01b600052601160045260246000fd5b600181815b808511156200050c578160001904821115620004f057620004f0620004b5565b80851615620004fe57918102915b93841c9390800290620004d0565b509250929050565b6000826200052557506001620001e9565b816200053457506000620001e9565b81600181146200054d5760028114620005585762000578565b6001915050620001e9565b60ff8411156200056c576200056c620004b5565b50506001821b620001e9565b5060208310610133831016604e8410600b84101617156200059d575081810a620001e9565b620005a98383620004cb565b8060001904821115620005c057620005c0620004b5565b029392505050565b6000620005d960ff84168362000514565b9392505050565b634e487b7160e01b600052601260045260246000fd5b80820180821115620001e957620001e9620004b5565b81810381811115620001e957620001e9620004b5565b60408101818360005b60028110156200064c5781518352602092830192909101906001016200062b565b50505092915050565b6000602082840312156200066857600080fd5b5051919050565b60805160a05160c05160e05161010051611a12620006fa60003960008181610299015261066b01526000818161033a0152610cf6015260008181610270015281816105100152818161062b01528181610ad00152610c0501526000818161024f015281816104e70152818161060201528181610aa70152610bdc015260006103940152611a126000f3fe608060405234801561001057600080fd5b50600436106101d95760003560e01c80637028bb0e11610104578063ac98e5df116100a2578063e1c7392a11610071578063e1c7392a14610490578063e33b13a014610498578063edbfe83f146104b5578063fba630f2146104d757600080fd5b8063ac98e5df146103e4578063bc14ee2b1461043a578063bea140b314610474578063c17268d91461048757600080fd5b80638aa0ba92116100de5780638aa0ba921461038f5780639c971729146103b65780639cfced97146103c9578063a28bc38c146103dc57600080fd5b80637028bb0e1461035c5780637d0a81c8146103695780638a2a3dfb1461037c57600080fd5b80634f367f0f1161017c578063623f54ac1161014b578063623f54ac146102f557806362a361bb14610308578063683f3dc31461031b5780636d582d341461033557600080fd5b80634f367f0f146102bb57806358bfc379146102c65780635bb93995146102d95780635d5909dd146102ec57600080fd5b806331e766a5116101b857806331e766a5146102175780633dfb88b21461023a5780634909229f1461024d5780634966efd61461029457600080fd5b8062329f2f146101de5780630f4cf692146101e857806327bea0da14610204575b600080fd5b6101e66104e0565b005b6101f160065481565b6040519081526020015b60405180910390f35b6101e66102123660046112aa565b6105fb565b600154600254610225919082565b604080519283526020830191909152016101fb565b6101f16102483660046112ed565b6107a5565b7f00000000000000000000000000000000000000000000000000000000000000007f0000000000000000000000000000000000000000000000000000000000000000610225565b6101f17f000000000000000000000000000000000000000000000000000000000000000081565b600754600654610225565b6101f16102d436600461136b565b610826565b6101f16102e7366004611411565b6108ae565b6101f160075481565b6101e6610303366004611433565b6108d3565b6101f16103163660046114fc565b610958565b610323600a81565b60405160ff90911681526020016101fb565b6101f17f000000000000000000000000000000000000000000000000000000000000000081565b6008546103239060ff1681565b6101f16103773660046115a6565b610992565b6101f161038a366004611608565b6109d2565b6101f17f000000000000000000000000000000000000000000000000000000000000000081565b6101e66103c436600461163f565b610aa0565b6101f16103d7366004611658565b610b9b565b6101e6610bd5565b60095461040d9060ff808216916101008104821691620100008204811691630100000090041684565b6040805160ff958616815293851660208501529184169183019190915290911660608201526080016101fb565b600a54600b54610454916001600160a01b03908116911682565b604080516001600160a01b039384168152929091166020830152016101fb565b6101f16104823660046116b1565b610e10565b6101f160055481565b6101e6610e4a565b6004546104a59060ff1681565b60405190151581526020016101fb565b6104c86104c33660046114fc565b610f6d565b6040516101fb93929190611736565b6101f160035481565b600061050c7f000000000000000000000000000000000000000000000000000000000000000042611779565b90507f0000000000000000000000000000000000000000000000000000000000000000811161054e57604051630931513d60e11b815260040160405180910390fd5b600b546009546040516324a47aeb60e01b81526201000090910460ff1660048201526000916001600160a01b0316906324a47aeb906024016020604051808303816000875af11580156105a5573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906105c9919061178c565b60405190915081907fc5624680ab5d50c84507f9e0dc2032163de2bda906ab8a661a53dd4d43bd5dc790600090a25050565b60006106277f000000000000000000000000000000000000000000000000000000000000000042611779565b90507f000000000000000000000000000000000000000000000000000000000000000081106106695760405163148fb9a960e31b815260040160405180910390fd5b7f0000000000000000000000000000000000000000000000000000000000000000600654106106ab57604051631ec0b2f760e01b815260040160405180910390fd5b6106ba82356020840135611015565b6106d7576040516379fae7af60e01b815260040160405180910390fd5b60068054600101905560006106f58461038a368690038601866117a5565b600b54604051631ffc735d60e01b8152600481018390529192506001600160a01b031690631ffc735d906024016020604051808303816000875af1158015610741573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610765919061178c565b507f4be9ef9ae736055964ead1cf3c83a19c8b662b5df2bd4414776bb64d81f75d1584846040516107979291906117c1565b60405180910390a150505050565b60405163248f667760e01b8152600090730a0d66bafda8c8838281084d9c3d68dd9a6fc2749063248f6677906107df9085906004016117ea565b602060405180830381865af41580156107fc573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610820919061178c565b92915050565b60006000805160206119bd83398151915260028360405160200161084a919061181b565b60408051601f198184030181529082905261086491611851565b602060405180830381855afa158015610881573d6000803e3d6000fd5b5050506040513d601f19601f820116820180604052508101906108a4919061178c565b6108209190611896565b60006108b86110fa565b838152602081018390526108cb81610958565b949350505050565b8281146108f35760405163ca3487f760e01b815260040160405180910390fd5b8260005b8181101561095057610948868683818110610914576109146118b8565b9050610140020180360381019061092b91906118ce565b85858481811061093d5761093d6118b8565b9050604002016105fb565b6001016108f7565b505050505050565b6040516314d2f97b60e11b81526000907388c2c6a7535463962a34757fe63cc4f296381aba906329a5f2f6906107df9085906004016118eb565b600061099c611118565b82515181528251602090810151818301528301518160026020020152604083015160608201526109cb816107a5565b9392505050565b60006109dc611136565b8351518152835160209081015190820152835160409081015190820152835160609081015190820152835160809081015190820152610a19611136565b845160a001518152845160c001516020820152845160e00151604080830191909152855161010001516060830152855161012001516080808401919091528151908101909152610a979080610a6d85610b9b565b8152602001610a7b84610b9b565b81526020018660000151815260200186602001518152506107a5565b95945050505050565b6000610acc7f000000000000000000000000000000000000000000000000000000000000000042611779565b90507f00000000000000000000000000000000000000000000000000000000000000008111610b0e57604051630931513d60e11b815260040160405180910390fd5b600b5460405163c15da65b60e01b8152600481018490526001600160a01b039091169063c15da65b90602401600060405180830381600087803b158015610b5457600080fd5b505af1158015610b68573d6000803e3d6000fd5b50506040518492507f1245b881cb30fdad22b2f9fde2d5c2a3605bbdf272d5e8a2235d8c9e81aba2ce9150600090a25050565b604051630926f44b60e31b815260009073d2f6c828606ad8e985008cd825012f269b50cd5890634937a258906107df908590600401611913565b6000610c017f000000000000000000000000000000000000000000000000000000000000000042611779565b90507f00000000000000000000000000000000000000000000000000000000000000008111610c4357604051630931513d60e11b815260040160405180910390fd5b60045460ff1615610c675760405163b703d3c960e01b815260040160405180910390fd5b6004805460ff19166001178155600a546040805163423f3e1960e01b815290516000936001600160a01b039093169263423f3e19928082019260209290918290030181865afa158015610cbe573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610ce2919061178c565b60038190559050610cf1611154565b8181527f0000000000000000000000000000000000000000000000000000000000000000602082015260006040820152610d2a81610e10565b600555600a546040805163122db15360e01b815290516000926001600160a01b03169163122db1539160048083019260209291908290030181865afa158015610d77573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610d9b919061178c565b6007819055905060015b818160ff166001901b64ffffffffff161015610dcd5780610dc58161193b565b915050610da5565b6008805460ff191660ff8316179055604051829085907f9f5164261ad26064467dc1be8861f75f2e57ae75579ebb4e500894b0ce9a982390600090a35050505050565b6040516304b98e1d60e31b815260009073f8e637e5c9ec3a8d8fa8843a6df833348e1f1e66906325cc70e8906107df90859060040161195a565b60005460ff1615610e6e576040516342a2e18d60e01b815260040160405180910390fd5b6000805460ff19166001908117909155600680549091019055610e8f6110fa565b7f12817f4161f2f5ded33f26c55735a77e80e4f8975483c8c2704745128417f71181526000602082018190528080610ec684610f6d565b600b54604051631ffc735d60e01b81526004810183905293965091945092506001600160a01b031690631ffc735d906024016020604051808303816000875af1158015610f17573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610f3b919061178c565b507f4be9ef9ae736055964ead1cf3c83a19c8b662b5df2bd4414776bb64d81f75d158383604051610797929190611982565b610f75611172565b60408051808201909152600080825260208201526000610f9361118a565b84518152602080860151828201526040805180820182527f171e826ad4a870fd925e0bf0e87884e70e080879c2205ef10114f28a3b6f6dd781527f2bd407d897fbbca9f88adfd2d15252e69de8c1564eb4d3d27162e259172f1a1d818401528151928301909152828252909450925061100c84846109d2565b93959294505050565b6000806000805160206119bd833981519152848509905060006000805160206119bd833981519152848509905060006000805160206119bd833981519152826000805160206119bd83398151915285620292fc0908905060006000805160206119bd83398151915280846000805160206119bd83398151915287620292f8090960010890506110b382826000805160206119bd8339815191526110bf565b15979650505050505050565b6000838381116110d6576110d383826119a9565b90505b82806110e4576110e4611880565b60006110f08684611779565b0895945050505050565b60405180604001604052806002906020820280368337509192915050565b60405180608001604052806004906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b60405180606001604052806003906020820280368337509192915050565b604051806020016040528061118561118a565b905290565b604051806101400160405280600a906020820280368337509192915050565b634e487b7160e01b600052604160045260246000fd5b604051610140810167ffffffffffffffff811182821017156111e3576111e36111a9565b60405290565b604051601f8201601f1916810167ffffffffffffffff81118282101715611212576112126111a9565b604052919050565b600061014080838503121561122e57600080fd5b604051602080820182811067ffffffffffffffff82111715611252576112526111a9565b806040525081935085601f86011261126957600080fd5b6112716111bf565b92850192808785111561128357600080fd5b865b8581101561129c5780358352918301918301611285565b509092525091949350505050565b6000808284036101808112156112bf57600080fd5b6112c9858561121a565b9250604061013f19820112156112de57600080fd5b50610140830190509250929050565b6000608082840312156112ff57600080fd5b82601f83011261130e57600080fd5b6040516080810181811067ffffffffffffffff82111715611331576113316111a9565b60405280608084018581111561134657600080fd5b845b81811015611360578035835260209283019201611348565b509195945050505050565b6000602080838503121561137e57600080fd5b823567ffffffffffffffff8082111561139657600080fd5b818501915085601f8301126113aa57600080fd5b8135818111156113bc576113bc6111a9565b8060051b91506113cd8483016111e9565b81815291830184019184810190888411156113e757600080fd5b938501935b83851015611405578435825293850193908501906113ec565b98975050505050505050565b6000806040838503121561142457600080fd5b50508035926020909101359150565b6000806000806040858703121561144957600080fd5b843567ffffffffffffffff8082111561146157600080fd5b818701915087601f83011261147557600080fd5b81358181111561148457600080fd5b8860206101408302850101111561149a57600080fd5b6020928301965094509086013590808211156114b557600080fd5b818701915087601f8301126114c957600080fd5b8135818111156114d857600080fd5b8860208260061b85010111156114ed57600080fd5b95989497505060200194505050565b60006040828403121561150e57600080fd5b82601f83011261151d57600080fd5b6040516040810181811067ffffffffffffffff82111715611540576115406111a9565b806040525080604084018581111561134657600080fd5b60006040828403121561156957600080fd5b6040516040810181811067ffffffffffffffff8211171561158c5761158c6111a9565b604052823581526020928301359281019290925250919050565b6000608082840312156115b857600080fd5b6040516060810181811067ffffffffffffffff821117156115db576115db6111a9565b6040526115e88484611557565b815260408301356020820152606083013560408201528091505092915050565b600080610180838503121561161c57600080fd5b611626848461121a565b9150611636846101408501611557565b90509250929050565b60006020828403121561165157600080fd5b5035919050565b600060a0828403121561166a57600080fd5b82601f83011261167957600080fd5b60405160a0810181811067ffffffffffffffff8211171561169c5761169c6111a9565b6040528060a084018581111561134657600080fd5b6000606082840312156116c357600080fd5b82601f8301126116d257600080fd5b6040516060810181811067ffffffffffffffff821117156116f5576116f56111a9565b60405280606084018581111561134657600080fd5b80518260005b600a81101561172f578251825260209283019290910190600101611710565b5050505050565b6101a08101611745828661170a565b83516101408301526020909301516101608201526101800152919050565b634e487b7160e01b600052601160045260246000fd5b8181038181111561082057610820611763565b60006020828403121561179e57600080fd5b5051919050565b6000604082840312156117b757600080fd5b6109cb8383611557565b61018081016117d0828561170a565b823561014083015260208301356101608301529392505050565b60808101818360005b60048110156118125781518352602092830192909101906001016117f3565b50505092915050565b815160009082906020808601845b8381101561184557815185529382019390820190600101611829565b50929695505050505050565b6000825160005b818110156118725760208186018101518583015201611858565b506000920191825250919050565b634e487b7160e01b600052601260045260246000fd5b6000826118b357634e487b7160e01b600052601260045260246000fd5b500690565b634e487b7160e01b600052603260045260246000fd5b600061014082840312156118e157600080fd5b6109cb838361121a565b60408101818360005b60028110156118125781518352602092830192909101906001016118f4565b60a08101818360005b600581101561181257815183526020928301929091019060010161191c565b600060ff821660ff810361195157611951611763565b60010192915050565b60608101818360005b6003811015611812578151835260209283019290910190600101611963565b6101808101611991828561170a565b825161014083015260208301516101608301526109cb565b808201808211156108205761082061176356fe30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001a2646970667358221220ee918fd206d19d51e7802d50e33e7d2078dbfa8fe1f17932de0f7d396db34da864736f6c6343000814003330644e72e131a029b85045b68181585d2833e84879b9709143e1f593f00000010000000000000000000000000000000000000000000000000000000000002a3000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000400000000000000000000000000000000000000000000000000000000000000020b05cf4195425c165ae56a244284c7021cbf72bfc567d3a39ce7585b26ff50b40a1ce79a43fa676ee3d2882c79d9164a24d4a22bb6190e3d8fa25d97bffc069a000000000000000000000000fcafb222bd61556e393058f08d6d86bdebcce72c000000000000000000000000db98d5bfa7088044f52a18bff42c4e62e7213f5e005e3dca15d7169ec424d8df83a9e7b4a43ebde4f20bdecc04897779bcd1573b

0x608060405234801561001057600080fd5b50600436106101d95760003560e01c80637028bb0e11610104578063ac98e5df116100a2578063e1c7392a11610071578063e1c7392a14610490578063e33b13a014610498578063edbfe83f146104b5578063fba630f2146104d757600080fd5b8063ac98e5df146103e4578063bc14ee2b1461043a578063bea140b314610474578063c17268d91461048757600080fd5b80638aa0ba92116100de5780638aa0ba921461038f5780639c971729146103b65780639cfced97146103c9578063a28bc38c146103dc57600080fd5b80637028bb0e1461035c5780637d0a81c8146103695780638a2a3dfb1461037c57600080fd5b80634f367f0f1161017c578063623f54ac1161014b578063623f54ac146102f557806362a361bb14610308578063683f3dc31461031b5780636d582d341461033557600080fd5b80634f367f0f146102bb57806358bfc379146102c65780635bb93995146102d95780635d5909dd146102ec57600080fd5b806331e766a5116101b857806331e766a5146102175780633dfb88b21461023a5780634909229f1461024d5780634966efd61461029457600080fd5b8062329f2f146101de5780630f4cf692146101e857806327bea0da14610204575b600080fd5b6101e66104e0565b005b6101f160065481565b6040519081526020015b60405180910390f35b6101e66102123660046112aa565b6105fb565b600154600254610225919082565b604080519283526020830191909152016101fb565b6101f16102483660046112ed565b6107a5565b7f0000000000000000000000000000000000000000000000000000000066b9d3847f0000000000000000000000000000000000000000000000000000000000002a30610225565b6101f17f000000000000000000000000000000000000000000000000000000000000027181565b600754600654610225565b6101f16102d436600461136b565b610826565b6101f16102e7366004611411565b6108ae565b6101f160075481565b6101e6610303366004611433565b6108d3565b6101f16103163660046114fc565b610958565b610323600a81565b60405160ff90911681526020016101fb565b6101f17f005e3dca15d7169ec424d8df83a9e7b4a43ebde4f20bdecc04897779bcd1573b81565b6008546103239060ff1681565b6101f16103773660046115a6565b610992565b6101f161038a366004611608565b6109d2565b6101f17f01285f3034b91c34dc53f459c13c9bd9ab3079772528ca9e868e550d405ffa7e81565b6101e66103c436600461163f565b610aa0565b6101f16103d7366004611658565b610b9b565b6101e6610bd5565b60095461040d9060ff808216916101008104821691620100008204811691630100000090041684565b6040805160ff958616815293851660208501529184169183019190915290911660608201526080016101fb565b600a54600b54610454916001600160a01b03908116911682565b604080516001600160a01b039384168152929091166020830152016101fb565b6101f16104823660046116b1565b610e10565b6101f160055481565b6101e6610e4a565b6004546104a59060ff1681565b60405190151581526020016101fb565b6104c86104c33660046114fc565b610f6d565b6040516101fb93929190611736565b6101f160035481565b600061050c7f0000000000000000000000000000000000000000000000000000000066b9d38442611779565b90507f0000000000000000000000000000000000000000000000000000000000002a30811161054e57604051630931513d60e11b815260040160405180910390fd5b600b546009546040516324a47aeb60e01b81526201000090910460ff1660048201526000916001600160a01b0316906324a47aeb906024016020604051808303816000875af11580156105a5573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906105c9919061178c565b60405190915081907fc5624680ab5d50c84507f9e0dc2032163de2bda906ab8a661a53dd4d43bd5dc790600090a25050565b60006106277f0000000000000000000000000000000000000000000000000000000066b9d38442611779565b90507f0000000000000000000000000000000000000000000000000000000000002a3081106106695760405163148fb9a960e31b815260040160405180910390fd5b7f0000000000000000000000000000000000000000000000000000000000000271600654106106ab57604051631ec0b2f760e01b815260040160405180910390fd5b6106ba82356020840135611015565b6106d7576040516379fae7af60e01b815260040160405180910390fd5b60068054600101905560006106f58461038a368690038601866117a5565b600b54604051631ffc735d60e01b8152600481018390529192506001600160a01b031690631ffc735d906024016020604051808303816000875af1158015610741573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610765919061178c565b507f4be9ef9ae736055964ead1cf3c83a19c8b662b5df2bd4414776bb64d81f75d1584846040516107979291906117c1565b60405180910390a150505050565b60405163248f667760e01b8152600090730a0d66bafda8c8838281084d9c3d68dd9a6fc2749063248f6677906107df9085906004016117ea565b602060405180830381865af41580156107fc573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610820919061178c565b92915050565b60006000805160206119bd83398151915260028360405160200161084a919061181b565b60408051601f198184030181529082905261086491611851565b602060405180830381855afa158015610881573d6000803e3d6000fd5b5050506040513d601f19601f820116820180604052508101906108a4919061178c565b6108209190611896565b60006108b86110fa565b838152602081018390526108cb81610958565b949350505050565b8281146108f35760405163ca3487f760e01b815260040160405180910390fd5b8260005b8181101561095057610948868683818110610914576109146118b8565b9050610140020180360381019061092b91906118ce565b85858481811061093d5761093d6118b8565b9050604002016105fb565b6001016108f7565b505050505050565b6040516314d2f97b60e11b81526000907388c2c6a7535463962a34757fe63cc4f296381aba906329a5f2f6906107df9085906004016118eb565b600061099c611118565b82515181528251602090810151818301528301518160026020020152604083015160608201526109cb816107a5565b9392505050565b60006109dc611136565b8351518152835160209081015190820152835160409081015190820152835160609081015190820152835160809081015190820152610a19611136565b845160a001518152845160c001516020820152845160e00151604080830191909152855161010001516060830152855161012001516080808401919091528151908101909152610a979080610a6d85610b9b565b8152602001610a7b84610b9b565b81526020018660000151815260200186602001518152506107a5565b95945050505050565b6000610acc7f0000000000000000000000000000000000000000000000000000000066b9d38442611779565b90507f0000000000000000000000000000000000000000000000000000000000002a308111610b0e57604051630931513d60e11b815260040160405180910390fd5b600b5460405163c15da65b60e01b8152600481018490526001600160a01b039091169063c15da65b90602401600060405180830381600087803b158015610b5457600080fd5b505af1158015610b68573d6000803e3d6000fd5b50506040518492507f1245b881cb30fdad22b2f9fde2d5c2a3605bbdf272d5e8a2235d8c9e81aba2ce9150600090a25050565b604051630926f44b60e31b815260009073d2f6c828606ad8e985008cd825012f269b50cd5890634937a258906107df908590600401611913565b6000610c017f0000000000000000000000000000000000000000000000000000000066b9d38442611779565b90507f0000000000000000000000000000000000000000000000000000000000002a308111610c4357604051630931513d60e11b815260040160405180910390fd5b60045460ff1615610c675760405163b703d3c960e01b815260040160405180910390fd5b6004805460ff19166001178155600a546040805163423f3e1960e01b815290516000936001600160a01b039093169263423f3e19928082019260209290918290030181865afa158015610cbe573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610ce2919061178c565b60038190559050610cf1611154565b8181527f005e3dca15d7169ec424d8df83a9e7b4a43ebde4f20bdecc04897779bcd1573b602082015260006040820152610d2a81610e10565b600555600a546040805163122db15360e01b815290516000926001600160a01b03169163122db1539160048083019260209291908290030181865afa158015610d77573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610d9b919061178c565b6007819055905060015b818160ff166001901b64ffffffffff161015610dcd5780610dc58161193b565b915050610da5565b6008805460ff191660ff8316179055604051829085907f9f5164261ad26064467dc1be8861f75f2e57ae75579ebb4e500894b0ce9a982390600090a35050505050565b6040516304b98e1d60e31b815260009073f8e637e5c9ec3a8d8fa8843a6df833348e1f1e66906325cc70e8906107df90859060040161195a565b60005460ff1615610e6e576040516342a2e18d60e01b815260040160405180910390fd5b6000805460ff19166001908117909155600680549091019055610e8f6110fa565b7f12817f4161f2f5ded33f26c55735a77e80e4f8975483c8c2704745128417f71181526000602082018190528080610ec684610f6d565b600b54604051631ffc735d60e01b81526004810183905293965091945092506001600160a01b031690631ffc735d906024016020604051808303816000875af1158015610f17573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610f3b919061178c565b507f4be9ef9ae736055964ead1cf3c83a19c8b662b5df2bd4414776bb64d81f75d158383604051610797929190611982565b610f75611172565b60408051808201909152600080825260208201526000610f9361118a565b84518152602080860151828201526040805180820182527f171e826ad4a870fd925e0bf0e87884e70e080879c2205ef10114f28a3b6f6dd781527f2bd407d897fbbca9f88adfd2d15252e69de8c1564eb4d3d27162e259172f1a1d818401528151928301909152828252909450925061100c84846109d2565b93959294505050565b6000806000805160206119bd833981519152848509905060006000805160206119bd833981519152848509905060006000805160206119bd833981519152826000805160206119bd83398151915285620292fc0908905060006000805160206119bd83398151915280846000805160206119bd83398151915287620292f8090960010890506110b382826000805160206119bd8339815191526110bf565b15979650505050505050565b6000838381116110d6576110d383826119a9565b90505b82806110e4576110e4611880565b60006110f08684611779565b0895945050505050565b60405180604001604052806002906020820280368337509192915050565b60405180608001604052806004906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b60405180606001604052806003906020820280368337509192915050565b604051806020016040528061118561118a565b905290565b604051806101400160405280600a906020820280368337509192915050565b634e487b7160e01b600052604160045260246000fd5b604051610140810167ffffffffffffffff811182821017156111e3576111e36111a9565b60405290565b604051601f8201601f1916810167ffffffffffffffff81118282101715611212576112126111a9565b604052919050565b600061014080838503121561122e57600080fd5b604051602080820182811067ffffffffffffffff82111715611252576112526111a9565b806040525081935085601f86011261126957600080fd5b6112716111bf565b92850192808785111561128357600080fd5b865b8581101561129c5780358352918301918301611285565b509092525091949350505050565b6000808284036101808112156112bf57600080fd5b6112c9858561121a565b9250604061013f19820112156112de57600080fd5b50610140830190509250929050565b6000608082840312156112ff57600080fd5b82601f83011261130e57600080fd5b6040516080810181811067ffffffffffffffff82111715611331576113316111a9565b60405280608084018581111561134657600080fd5b845b81811015611360578035835260209283019201611348565b509195945050505050565b6000602080838503121561137e57600080fd5b823567ffffffffffffffff8082111561139657600080fd5b818501915085601f8301126113aa57600080fd5b8135818111156113bc576113bc6111a9565b8060051b91506113cd8483016111e9565b81815291830184019184810190888411156113e757600080fd5b938501935b83851015611405578435825293850193908501906113ec565b98975050505050505050565b6000806040838503121561142457600080fd5b50508035926020909101359150565b6000806000806040858703121561144957600080fd5b843567ffffffffffffffff8082111561146157600080fd5b818701915087601f83011261147557600080fd5b81358181111561148457600080fd5b8860206101408302850101111561149a57600080fd5b6020928301965094509086013590808211156114b557600080fd5b818701915087601f8301126114c957600080fd5b8135818111156114d857600080fd5b8860208260061b85010111156114ed57600080fd5b95989497505060200194505050565b60006040828403121561150e57600080fd5b82601f83011261151d57600080fd5b6040516040810181811067ffffffffffffffff82111715611540576115406111a9565b806040525080604084018581111561134657600080fd5b60006040828403121561156957600080fd5b6040516040810181811067ffffffffffffffff8211171561158c5761158c6111a9565b604052823581526020928301359281019290925250919050565b6000608082840312156115b857600080fd5b6040516060810181811067ffffffffffffffff821117156115db576115db6111a9565b6040526115e88484611557565b815260408301356020820152606083013560408201528091505092915050565b600080610180838503121561161c57600080fd5b611626848461121a565b9150611636846101408501611557565b90509250929050565b60006020828403121561165157600080fd5b5035919050565b600060a0828403121561166a57600080fd5b82601f83011261167957600080fd5b60405160a0810181811067ffffffffffffffff8211171561169c5761169c6111a9565b6040528060a084018581111561134657600080fd5b6000606082840312156116c357600080fd5b82601f8301126116d257600080fd5b6040516060810181811067ffffffffffffffff821117156116f5576116f56111a9565b60405280606084018581111561134657600080fd5b80518260005b600a81101561172f578251825260209283019290910190600101611710565b5050505050565b6101a08101611745828661170a565b83516101408301526020909301516101608201526101800152919050565b634e487b7160e01b600052601160045260246000fd5b8181038181111561082057610820611763565b60006020828403121561179e57600080fd5b5051919050565b6000604082840312156117b757600080fd5b6109cb8383611557565b61018081016117d0828561170a565b823561014083015260208301356101608301529392505050565b60808101818360005b60048110156118125781518352602092830192909101906001016117f3565b50505092915050565b815160009082906020808601845b8381101561184557815185529382019390820190600101611829565b50929695505050505050565b6000825160005b818110156118725760208186018101518583015201611858565b506000920191825250919050565b634e487b7160e01b600052601260045260246000fd5b6000826118b357634e487b7160e01b600052601260045260246000fd5b500690565b634e487b7160e01b600052603260045260246000fd5b600061014082840312156118e157600080fd5b6109cb838361121a565b60408101818360005b60028110156118125781518352602092830192909101906001016118f4565b60a08101818360005b600581101561181257815183526020928301929091019060010161191c565b600060ff821660ff810361195157611951611763565b60010192915050565b60608101818360005b6003811015611812578151835260209283019290910190600101611963565b6101808101611991828561170a565b825161014083015260208301516101608301526109cb565b808201808211156108205761082061176356fe30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001a2646970667358221220ee918fd206d19d51e7802d50e33e7d2078dbfa8fe1f17932de0f7d396db34da864736f6c63430008140033