Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE

More Options

• Is this a proxy?
• Similar
• Compare

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

import { Tally } from "./Tally.sol";
import { ITallyFactory } from "./interfaces/ITallyFactory.sol";
import { DomainObjs } from "./utilities/DomainObjs.sol";

/// @title TallyFactory
/// @notice A factory contract which deploys Tally contracts.
contract TallyFactory is ITallyFactory, DomainObjs {
  /// @inheritdoc ITallyFactory
  function deploy(
    address _verifier,
    address _vkRegistry,
    address _poll,
    address _messageProcessor,
    address _owner,
    Mode _mode
  ) public virtual returns (address tallyAddr) {
    // deploy Tally for this Poll
    Tally tally = new Tally(_verifier, _vkRegistry, _poll, _messageProcessor, _owner, _mode);
    tallyAddr = address(tally);
  }
}

// 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;
    }
}

// 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;

/// @title IMessageProcessor
/// @notice MessageProcessor interface
interface IMessageProcessor {
  /// @notice Get the result of whether there are unprocessed messages left
  /// @return Whether there are unprocessed messages left
  function processingComplete() external view returns (bool);

  /// @notice Get the commitment to the state and ballot roots
  /// @return The commitment to the state and ballot roots
  function sbCommitment() external view returns (uint256);

  /// @notice Get public circuit inputs.
  /// @param _currentMessageBatchIndex The current processed batch index
  /// @param _newSbCommitment The new state root and ballot root commitment
  ///                         after all messages are processed
  /// @return publicInputs public circuit inputs
  function getPublicCircuitInputs(
    uint256 _currentMessageBatchIndex,
    uint256 _newSbCommitment
  ) external view returns (uint256[] memory);
}

// 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.10;

import { DomainObjs } from "../utilities/DomainObjs.sol";

/// @title ITallyFactory
/// @notice TallyFactory interface
interface ITallyFactory {
  /// @notice Deploy a new Tally contract and return the address.
  /// @param _verifier Verifier contract
  /// @param _vkRegistry VkRegistry contract
  /// @param _poll Poll contract
  /// @param _messageProcessor MessageProcessor contract
  /// @param _owner Owner of the contract
  /// @param _mode Voting mode
  /// @return The deployed contract
  function deploy(
    address _verifier,
    address _vkRegistry,
    address _poll,
    address _messageProcessor,
    address _owner,
    DomainObjs.Mode _mode
  ) external returns (address);
}

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

import { SnarkCommon } from "../crypto/SnarkCommon.sol";

/// @title IVerifier
/// @notice an interface for a Groth16 verifier contract
interface IVerifier {
  /// @notice Verify a zk-SNARK proof
  /// @param _proof The proof
  /// @param vk The verifying key
  /// @param inputs The public inputs to the circuit
  /// @return Whether the proof is valid given the verifying key and public
  ///          input. Note that this function only supports one public input.
  ///          Refer to the Semaphore source code for a verifier that supports
  ///          multiple public inputs.
  function verify(
    uint256[8] memory _proof,
    SnarkCommon.VerifyingKey memory vk,
    uint256[] memory inputs
  ) external view returns (bool);
}

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

import { SnarkCommon } from "../crypto/SnarkCommon.sol";
import { DomainObjs } from "../utilities/DomainObjs.sol";

/// @title IVkRegistry
/// @notice VkRegistry interface
interface IVkRegistry {
  /// @notice Get the tally verifying key
  /// @param _stateTreeDepth The state tree depth
  /// @param _intStateTreeDepth The intermediate state tree depth
  /// @param _voteOptionTreeDepth The vote option tree depth
  /// @param _mode QV or Non-QV
  /// @return The verifying key
  function getTallyVk(
    uint256 _stateTreeDepth,
    uint256 _intStateTreeDepth,
    uint256 _voteOptionTreeDepth,
    DomainObjs.Mode _mode
  ) external view returns (SnarkCommon.VerifyingKey memory);

  /// @notice Get the process verifying key
  /// @param _stateTreeDepth The state tree depth
  /// @param _messageTreeDepth The message tree depth
  /// @param _voteOptionTreeDepth The vote option tree depth
  /// @param _messageBatchSize The message batch size
  /// @param _mode QV or Non-QV
  /// @return The verifying key
  function getProcessVk(
    uint256 _stateTreeDepth,
    uint256 _messageTreeDepth,
    uint256 _voteOptionTreeDepth,
    uint256 _messageBatchSize,
    DomainObjs.Mode _mode
  ) external view returns (SnarkCommon.VerifyingKey memory);
}

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

import { IMACI } from "./interfaces/IMACI.sol";
import { Hasher } from "./crypto/Hasher.sol";
import { Ownable } from "@openzeppelin/contracts/access/Ownable.sol";
import { IPoll } from "./interfaces/IPoll.sol";
import { IMessageProcessor } from "./interfaces/IMessageProcessor.sol";
import { SnarkCommon } from "./crypto/SnarkCommon.sol";
import { IVerifier } from "./interfaces/IVerifier.sol";
import { IVkRegistry } from "./interfaces/IVkRegistry.sol";
import { CommonUtilities } from "./utilities/CommonUtilities.sol";
import { DomainObjs } from "./utilities/DomainObjs.sol";

/// @title Tally
/// @notice The Tally contract is used during votes tallying
/// and by users to verify the tally results.
contract Tally is Ownable, SnarkCommon, CommonUtilities, Hasher, DomainObjs {
  uint256 internal constant TREE_ARITY = 2;
  uint256 internal constant VOTE_OPTION_TREE_ARITY = 5;

  /// @notice The commitment to the tally results. Its initial value is 0, but after
  /// the tally of each batch is proven on-chain via a zk-SNARK, it should be
  /// updated to:
  ///
  /// QV:
  /// hash3(
  ///   hashLeftRight(merkle root of current results, salt0)
  ///   hashLeftRight(number of spent voice credits, salt1),
  ///   hashLeftRight(merkle root of the no. of spent voice credits per vote option, salt2)
  /// )
  ///
  /// Non-QV:
  /// hash2(
  ///   hashLeftRight(merkle root of current results, salt0)
  ///   hashLeftRight(number of spent voice credits, salt1),
  /// )
  ///
  /// Where each salt is unique and the merkle roots are of arrays of leaves
  /// TREE_ARITY ** voteOptionTreeDepth long.
  uint256 public tallyCommitment;

  uint256 public tallyBatchNum;

  // The final commitment to the state and ballot roots
  uint256 public sbCommitment;

  IVerifier public immutable verifier;
  IVkRegistry public immutable vkRegistry;
  IPoll public immutable poll;
  IMessageProcessor public immutable messageProcessor;
  Mode public immutable mode;

  /// @notice custom errors
  error ProcessingNotComplete();
  error InvalidTallyVotesProof();
  error AllBallotsTallied();
  error NumSignUpsTooLarge();
  error BatchStartIndexTooLarge();
  error TallyBatchSizeTooLarge();
  error NotSupported();

  /// @notice Create a new Tally contract
  /// @param _verifier The Verifier contract
  /// @param _vkRegistry The VkRegistry contract
  /// @param _poll The Poll contract
  /// @param _mp The MessageProcessor contract
  /// @param _tallyOwner The owner of the Tally contract
  /// @param _mode The mode of the poll
  constructor(
    address _verifier,
    address _vkRegistry,
    address _poll,
    address _mp,
    address _tallyOwner,
    Mode _mode
  ) payable Ownable(_tallyOwner) {
    verifier = IVerifier(_verifier);
    vkRegistry = IVkRegistry(_vkRegistry);
    poll = IPoll(_poll);
    messageProcessor = IMessageProcessor(_mp);
    mode = _mode;
  }

  /// @notice Check if all ballots are tallied
  /// @return tallied whether all ballots are tallied
  function isTallied() public view returns (bool tallied) {
    (uint8 intStateTreeDepth, , , ) = poll.treeDepths();
    (uint256 numSignUps, ) = poll.numSignUpsAndMessages();

    // Require that there are untallied ballots left
    tallied = tallyBatchNum * (TREE_ARITY ** intStateTreeDepth) >= numSignUps;
  }

  /// @notice Update the state and ballot root commitment
  function updateSbCommitment() public onlyOwner {
    // Require that all messages have been processed
    if (!messageProcessor.processingComplete()) {
      revert ProcessingNotComplete();
    }

    if (sbCommitment == 0) {
      sbCommitment = messageProcessor.sbCommitment();
    }
  }

  /// @notice Verify the result of a tally batch
  /// @param _newTallyCommitment the new tally commitment to be verified
  /// @param _proof the proof generated after tallying this batch
  function tallyVotes(uint256 _newTallyCommitment, uint256[8] calldata _proof) public onlyOwner {
    _votingPeriodOver(poll);
    updateSbCommitment();

    // get the batch size and start index
    (uint8 intStateTreeDepth, , , ) = poll.treeDepths();
    uint256 tallyBatchSize = TREE_ARITY ** intStateTreeDepth;
    uint256 batchStartIndex = tallyBatchNum * tallyBatchSize;

    (uint256 numSignUps, ) = poll.numSignUpsAndMessages();

    // Require that there are untallied ballots left
    if (batchStartIndex >= numSignUps) {
      revert AllBallotsTallied();
    }

    // save some gas because we won't overflow uint256
    unchecked {
      tallyBatchNum++;
    }

    if (!verifyTallyProof(batchStartIndex, _newTallyCommitment, _proof)) {
      revert InvalidTallyVotesProof();
    }

    // Update the tally commitment and the tally batch num
    tallyCommitment = _newTallyCommitment;
  }

  /// @notice Get public circuit inputs.
  /// @param _batchStartIndex the batch start index
  /// @param _newTallyCommitment the new tally commitment to be verified
  /// @return publicInputs public circuit inputs
  function getPublicCircuitInputs(
    uint256 _batchStartIndex,
    uint256 _newTallyCommitment
  ) public view returns (uint256[] memory publicInputs) {
    (uint256 numSignUps, ) = poll.numSignUpsAndMessages();

    publicInputs = new uint256[](5);
    publicInputs[0] = sbCommitment;
    publicInputs[1] = tallyCommitment;
    publicInputs[2] = _newTallyCommitment;
    publicInputs[3] = _batchStartIndex;
    publicInputs[4] = numSignUps;
  }

  /// @notice Verify the tally proof using the verifying key
  /// @param _batchStartIndex the batch start index
  /// @param _newTallyCommitment the new tally commitment to be verified
  /// @param _proof the proof generated after processing all messages
  /// @return isValid whether the proof is valid
  function verifyTallyProof(
    uint256 _batchStartIndex,
    uint256 _newTallyCommitment,
    uint256[8] calldata _proof
  ) public view returns (bool isValid) {
    (uint8 intStateTreeDepth, , , uint8 voteOptionTreeDepth) = poll.treeDepths();
    (IMACI maci, ) = poll.extContracts();
    uint256[] memory circuitPublicInputs = getPublicCircuitInputs(_batchStartIndex, _newTallyCommitment);

    // Get the verifying key
    VerifyingKey memory vk = vkRegistry.getTallyVk(maci.stateTreeDepth(), intStateTreeDepth, voteOptionTreeDepth, mode);
    // Verify the proof
    isValid = verifier.verify(_proof, vk, circuitPublicInputs);
  }

  /// @notice Compute the merkle root from the path elements
  /// and a leaf
  /// @param _depth the depth of the merkle tree
  /// @param _index the index of the leaf
  /// @param _leaf the leaf
  /// @param _pathElements the path elements to reconstruct the merkle root
  /// @return current The merkle root
  function computeMerkleRootFromPath(
    uint8 _depth,
    uint256 _index,
    uint256 _leaf,
    uint256[][] calldata _pathElements
  ) internal pure returns (uint256 current) {
    uint256 pos = _index % VOTE_OPTION_TREE_ARITY;
    current = _leaf;
    uint8 k;

    uint256[VOTE_OPTION_TREE_ARITY] memory level;

    for (uint8 i = 0; i < _depth; ++i) {
      for (uint8 j = 0; j < VOTE_OPTION_TREE_ARITY; ++j) {
        if (j == pos) {
          level[j] = current;
        } else {
          if (j > pos) {
            k = j - 1;
          } else {
            k = j;
          }
          level[j] = _pathElements[i][k];
        }
      }

      _index /= VOTE_OPTION_TREE_ARITY;
      pos = _index % VOTE_OPTION_TREE_ARITY;
      current = hash5(level);
    }
  }

  /// @notice Verify the number of spent voice credits from the tally.json
  /// @param _totalSpent spent field retrieved in the totalSpentVoiceCredits object
  /// @param _totalSpentSalt the corresponding salt in the totalSpentVoiceCredit object
  /// @param _resultCommitment hashLeftRight(merkle root of the results.tally, results.salt) in tally.json file
  /// @param _perVOSpentVoiceCreditsHash only for QV - hashLeftRight(merkle root of the no spent voice credits, salt)
  /// @return isValid Whether the provided values are valid
  function verifySpentVoiceCredits(
    uint256 _totalSpent,
    uint256 _totalSpentSalt,
    uint256 _resultCommitment,
    uint256 _perVOSpentVoiceCreditsHash
  ) public view returns (bool isValid) {
    if (mode == Mode.QV) {
      isValid = verifyQvSpentVoiceCredits(_totalSpent, _totalSpentSalt, _resultCommitment, _perVOSpentVoiceCreditsHash);
    } else if (mode == Mode.NON_QV) {
      isValid = verifyNonQvSpentVoiceCredits(_totalSpent, _totalSpentSalt, _resultCommitment);
    }
  }

  /// @notice Verify the number of spent voice credits for QV from the tally.json
  /// @param _totalSpent spent field retrieved in the totalSpentVoiceCredits object
  /// @param _totalSpentSalt the corresponding salt in the totalSpentVoiceCredit object
  /// @param _resultCommitment hashLeftRight(merkle root of the results.tally, results.salt) in tally.json file
  /// @param _perVOSpentVoiceCreditsHash hashLeftRight(merkle root of the no spent voice credits per vote option, salt)
  /// @return isValid Whether the provided values are valid
  function verifyQvSpentVoiceCredits(
    uint256 _totalSpent,
    uint256 _totalSpentSalt,
    uint256 _resultCommitment,
    uint256 _perVOSpentVoiceCreditsHash
  ) internal view returns (bool isValid) {
    uint256[3] memory tally;
    tally[0] = _resultCommitment;
    tally[1] = hashLeftRight(_totalSpent, _totalSpentSalt);
    tally[2] = _perVOSpentVoiceCreditsHash;

    isValid = hash3(tally) == tallyCommitment;
  }

  /// @notice Verify the number of spent voice credits for Non-QV from the tally.json
  /// @param _totalSpent spent field retrieved in the totalSpentVoiceCredits object
  /// @param _totalSpentSalt the corresponding salt in the totalSpentVoiceCredit object
  /// @param _resultCommitment hashLeftRight(merkle root of the results.tally, results.salt) in tally.json file
  /// @return isValid Whether the provided values are valid
  function verifyNonQvSpentVoiceCredits(
    uint256 _totalSpent,
    uint256 _totalSpentSalt,
    uint256 _resultCommitment
  ) internal view returns (bool isValid) {
    uint256[2] memory tally;
    tally[0] = _resultCommitment;
    tally[1] = hashLeftRight(_totalSpent, _totalSpentSalt);

    isValid = hash2(tally) == tallyCommitment;
  }

  /// @notice Verify the number of spent voice credits per vote option from the tally.json
  /// @param _voteOptionIndex the index of the vote option where credits were spent
  /// @param _spent the spent voice credits for a given vote option index
  /// @param _spentProof proof generated for the perVOSpentVoiceCredits
  /// @param _spentSalt the corresponding salt given in the tally perVOSpentVoiceCredits object
  /// @param _voteOptionTreeDepth depth of the vote option tree
  /// @param _spentVoiceCreditsHash hashLeftRight(number of spent voice credits, spent salt)
  /// @param _resultCommitment hashLeftRight(merkle root of the results.tally, results.salt)
  // in the tally.json file
  /// @return isValid Whether the provided proof is valid
  function verifyPerVOSpentVoiceCredits(
    uint256 _voteOptionIndex,
    uint256 _spent,
    uint256[][] calldata _spentProof,
    uint256 _spentSalt,
    uint8 _voteOptionTreeDepth,
    uint256 _spentVoiceCreditsHash,
    uint256 _resultCommitment
  ) public view returns (bool isValid) {
    if (mode != Mode.QV) {
      revert NotSupported();
    }

    uint256 computedRoot = computeMerkleRootFromPath(_voteOptionTreeDepth, _voteOptionIndex, _spent, _spentProof);

    uint256[3] memory tally;
    tally[0] = _resultCommitment;
    tally[1] = _spentVoiceCreditsHash;
    tally[2] = hashLeftRight(computedRoot, _spentSalt);

    isValid = hash3(tally) == tallyCommitment;
  }

  /// @notice Verify the result generated from the tally.json
  /// @param _voteOptionIndex the index of the vote option to verify the correctness of the tally
  /// @param _tallyResult Flattened array of the tally
  /// @param _tallyResultProof Corresponding proof of the tally result
  /// @param _tallyResultSalt the respective salt in the results object in the tally.json
  /// @param _voteOptionTreeDepth depth of the vote option tree
  /// @param _spentVoiceCreditsHash hashLeftRight(number of spent voice credits, spent salt)
  /// @param _perVOSpentVoiceCreditsHash hashLeftRight(merkle root of the no spent voice
  /// credits per vote option, perVOSpentVoiceCredits salt)
  /// @return isValid Whether the provided proof is valid
  function verifyTallyResult(
    uint256 _voteOptionIndex,
    uint256 _tallyResult,
    uint256[][] calldata _tallyResultProof,
    uint256 _tallyResultSalt,
    uint8 _voteOptionTreeDepth,
    uint256 _spentVoiceCreditsHash,
    uint256 _perVOSpentVoiceCreditsHash
  ) public view returns (bool isValid) {
    uint256 computedRoot = computeMerkleRootFromPath(
      _voteOptionTreeDepth,
      _voteOptionIndex,
      _tallyResult,
      _tallyResultProof
    );

    if (mode == Mode.QV) {
      uint256[3] memory tally;
      tally[0] = hashLeftRight(computedRoot, _tallyResultSalt);
      tally[1] = _spentVoiceCreditsHash;
      tally[2] = _perVOSpentVoiceCreditsHash;

      isValid = hash3(tally) == tallyCommitment;
    } else if (mode == Mode.NON_QV) {
      uint256[2] memory tally;
      tally[0] = hashLeftRight(computedRoot, _tallyResultSalt);
      tally[1] = _spentVoiceCreditsHash;

      isValid = hash2(tally) == tallyCommitment;
    }
  }
}

// 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;

import { IPoll } from "../interfaces/IPoll.sol";

/// @title CommonUtilities
/// @notice A contract that holds common utilities
/// which are to be used by multiple contracts
/// namely Tally and MessageProcessor
contract CommonUtilities {
  error VotingPeriodNotPassed();

  /// @notice common function for MessageProcessor, and Tally
  /// @param _poll the poll to be checked
  function _votingPeriodOver(IPoll _poll) internal view {
    (uint256 deployTime, uint256 duration) = _poll.getDeployTimeAndDuration();
    // Require that the voting period is over
    uint256 secondsPassed = block.timestamp - deployTime;
    if (secondsPassed <= duration) {
      revert VotingPeriodNotPassed();
    }
  }
}

// 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;
  }
}

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

[{"inputs":[],"name":"MESSAGE_DATA_LENGTH","outputs":[{"internalType":"uint8","name":"","type":"uint8"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"_verifier","type":"address"},{"internalType":"address","name":"_vkRegistry","type":"address"},{"internalType":"address","name":"_poll","type":"address"},{"internalType":"address","name":"_messageProcessor","type":"address"},{"internalType":"address","name":"_owner","type":"address"},{"internalType":"enum DomainObjs.Mode","name":"_mode","type":"uint8"}],"name":"deploy","outputs":[{"internalType":"address","name":"tallyAddr","type":"address"}],"stateMutability":"nonpayable","type":"function"}]

608060405234801561001057600080fd5b50612537806100206000396000f3fe608060405234801561001057600080fd5b50600436106100365760003560e01c8063431a71751461003b578063683f3dc31461006b575b600080fd5b61004e6100493660046100fb565b610085565b6040516001600160a01b0390911681526020015b60405180910390f35b610073600a81565b60405160ff9091168152602001610062565b60008087878787878760405161009a906100d2565b6100a996959493929190610177565b604051809103906000f0801580156100c5573d6000803e3d6000fd5b5098975050505050505050565b61232b806101d783390190565b80356001600160a01b03811681146100f657600080fd5b919050565b60008060008060008060c0878903121561011457600080fd5b61011d876100df565b955061012b602088016100df565b9450610139604088016100df565b9350610147606088016100df565b9250610155608088016100df565b915060a08701356002811061016957600080fd5b809150509295509295509295565b6001600160a01b0387811682528681166020830152858116604083015284811660608301528316608082015260c08101600283106101c557634e487b7160e01b600052602160045260246000fd5b8260a083015297965050505050505056fe6101206040526040516200232b3803806200232b83398101604081905262000027916200012c565b816001600160a01b0381166200005757604051631e4fbdf760e01b81526000600482015260240160405180910390fd5b6200006281620000bf565b506001600160a01b0380871660805285811660a05284811660c052831660e052806001811115620000975762000097620001b4565b610100816001811115620000af57620000af620001b4565b81525050505050505050620001ca565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b80516001600160a01b03811681146200012757600080fd5b919050565b60008060008060008060c087890312156200014657600080fd5b62000151876200010f565b955062000161602088016200010f565b945062000171604088016200010f565b935062000181606088016200010f565b925062000191608088016200010f565b915060a087015160028110620001a657600080fd5b809150509295509295509295565b634e487b7160e01b600052602160045260246000fd5b60805160a05160c05160e0516101005161209e6200028d600039600081816102400152818161055f015281816105ab015281816108fd01528181610b6901528181610bd90152610dfa0152600081816103c00152818161060001526106a90152600081816103570152818161040c0152818161073c0152818161076c0152818161081801528181610c4901528181610cd301528181610f5d0152610fe60152600081816101e40152610d670152600081816102740152610e97015261209e6000f3fe608060405234801561001057600080fd5b506004361061018e5760003560e01c8063683f3dc3116100de578063afb93bd311610097578063d0380fe211610071578063d0380fe2146103bb578063d13181b8146103e2578063e3ff7606146103eb578063f2fde38b146103f357600080fd5b8063afb93bd31461038c578063b904438814610395578063bea140b3146103a857600080fd5b8063683f3dc31461030c578063715018a6146103265780638da5cb5b1461032e5780639cfced971461033f578063a117527914610352578063a21fb5111461037957600080fd5b80632b7ac3f31161014b57806358bfc3791161012557806358bfc379146102ca5780635bb93995146102dd57806361750293146102f057806362a361bb146102f957600080fd5b80632b7ac3f31461026f5780632d966bf4146102965780633dfb88b2146102a957600080fd5b8063023650801461019357806310bc5f51146101bc57806313fb8932146101df57806316425eeb1461021e57806323e3feb114610228578063295a52121461023b575b600080fd5b6101a66101a13660046113e4565b610406565b6040516101b39190611441565b60405180910390f35b6101cf6101ca36600461145b565b61055a565b60405190151581526020016101b3565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6040516001600160a01b0390911681526020016101b3565b6102266105f6565b005b61022661023636600461149f565b61072f565b6102627f000000000000000000000000000000000000000000000000000000000000000081565b6040516101b39190611505565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6101cf6102a4366004611532565b6108f8565b6102bc6102b736600461167b565b610999565b6040519081526020016101b3565b6102bc6102d836600461171d565b610a1a565b6102bc6102eb3660046113e4565b610ab4565b6102bc60015481565b6102bc6103073660046117b3565b610acd565b610314600a81565b60405160ff90911681526020016101b3565b610226610b07565b6000546001600160a01b0316610206565b6102bc61034d366004611813565b610b19565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6101cf610387366004611532565b610b53565b6102bc60025481565b6101cf6103a336600461184e565b610c42565b6102bc6103b6366004611885565b610f1e565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6102bc60035481565b6101cf610f58565b6102266104013660046118f3565b61108a565b606060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015610467573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061048b9190611910565b5060408051600580825260c082019092529192506020820160a080368337019050509150600354826000815181106104c5576104c5611934565b602002602001018181525050600154826001815181106104e7576104e7611934565b602002602001018181525050828260028151811061050757610507611934565b602002602001018181525050838260038151811061052757610527611934565b602002602001018181525050808260048151811061054757610547611934565b6020026020010181815250505092915050565b6000807f0000000000000000000000000000000000000000000000000000000000000000600181111561058f5761058f6114cd565b036105a7576105a0858585856110cd565b90506105ee565b60017f000000000000000000000000000000000000000000000000000000000000000060018111156105db576105db6114cd565b036105ee576105eb858585611107565b90505b949350505050565b6105fe611139565b7f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316638763d0c46040518163ffffffff1660e01b8152600401602060405180830381865afa15801561065c573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610680919061194a565b61069d5760405163f13e1b8560e01b815260040160405180910390fd5b60035460000361072d577f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663d13181b86040518163ffffffff1660e01b8152600401602060405180830381865afa158015610705573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610729919061196c565b6003555b565b610737611139565b6107607f0000000000000000000000000000000000000000000000000000000000000000611166565b6107686105f6565b60007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa1580156107c8573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906107ec9190611985565b505050905060008160026108009190611ade565b90506000816002546108129190611aed565b905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015610873573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906108979190611910565b5090508082106108ba5760405163b3f8c18960e01b815260040160405180910390fd5b6002805460010190556108ce828787610c42565b6108eb576040516341acf34d60e01b815260040160405180910390fd5b5050506001929092555050565b6000807f0000000000000000000000000000000000000000000000000000000000000000600181111561092d5761092d6114cd565b1461094b57604051630280e1e560e61b815260040160405180910390fd5b600061095a858b8b8b8b611203565b905061096461138a565b838152602081018590526109788288610ab4565b604082015260015461098982610f1e565b149b9a5050505050505050505050565b60405163248f667760e01b815260009073e0398f7dfac494c530f6404afeac8669abed26799063248f6677906109d3908590600401611b04565b602060405180830381865af41580156109f0573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610a14919061196c565b92915050565b60007f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001600283604051602001610a509190611b35565b60408051601f1981840301815290829052610a6a91611b6b565b602060405180830381855afa158015610a87573d6000803e3d6000fd5b5050506040513d601f19601f82011682018060405250810190610aaa919061196c565b610a149190611bb0565b6000610abe6113a8565b838152602081018390526105ee815b6040516314d2f97b60e11b81526000907307490eba00dc4aca6721d052fa4c5002aa077233906329a5f2f6906109d3908590600401611bc4565b610b0f611139565b61072d600061133a565b604051630926f44b60e31b815260009073fd77833f10a29c76a6a0ede235eb651d744d0e2f90634937a258906109d3908590600401611bec565b600080610b63858b8b8b8b611203565b905060007f00000000000000000000000000000000000000000000000000000000000000006001811115610b9957610b996114cd565b03610bd557610ba661138a565b610bb08288610ab4565b81526020810185905260408101849052600154610bcc82610f1e565b14925050610c35565b60017f00000000000000000000000000000000000000000000000000000000000000006001811115610c0957610c096114cd565b03610c3557610c166113a8565b610c208288610ab4565b81526020810185905260015461098982610acd565b5098975050505050505050565b60008060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa158015610ca5573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610cc99190611985565b93505050915060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663bc14ee2b6040518163ffffffff1660e01b81526004016040805180830381865afa158015610d2e573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610d529190611c14565b5090506000610d618888610406565b905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b03166310b37e4d846001600160a01b031663652c76e46040518163ffffffff1660e01b8152600401602060405180830381865afa158015610dd2573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610df69190611c4e565b87877f00000000000000000000000000000000000000000000000000000000000000006040518563ffffffff1660e01b8152600401610e389493929190611c6b565b600060405180830381865afa158015610e55573d6000803e3d6000fd5b505050506040513d6000823e601f3d908101601f19168201604052610e7d9190810190611d50565b60405163352a4d1560e01b81529091506001600160a01b037f0000000000000000000000000000000000000000000000000000000000000000169063352a4d1590610ed0908a9085908790600401611eae565b602060405180830381865afa158015610eed573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610f11919061194a565b9998505050505050505050565b6040516304b98e1d60e31b815260009073bb0e724ce02e5e7edd31e632dc6e59f229a1126d906325cc70e8906109d3908590600401611f90565b6000807f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa158015610fb9573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610fdd9190611985565b505050905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015611041573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906110659190611910565b50905080611074836002611ade565b6002546110819190611aed565b10159250505090565b611092611139565b6001600160a01b0381166110c157604051631e4fbdf760e01b8152600060048201526024015b60405180910390fd5b6110ca8161133a565b50565b60006110d761138a565b8381526110e48686610ab4565b6020820152604081018390526001546110fc82610f1e565b149695505050505050565b60006111116113a8565b82815261111e8585610ab4565b602082015260015461112f82610acd565b1495945050505050565b6000546001600160a01b0316331461072d5760405163118cdaa760e01b81523360048201526024016110b8565b600080826001600160a01b0316634909229f6040518163ffffffff1660e01b81526004016040805180830381865afa1580156111a6573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906111ca9190611910565b909250905060006111db8342611fb8565b90508181116111fd57604051635c3017c560e11b815260040160405180910390fd5b50505050565b600080611211600587611bb0565b905084915060006112206113c6565b60005b8960ff168160ff16101561132d5760005b60058160ff1610156112f757848160ff160361126a5785838260ff166005811061126057611260611934565b60200201526112e7565b848160ff16111561128757611280600182611fcb565b935061128b565b8093505b87878360ff168181106112a0576112a0611934565b90506020028101906112b29190611fe4565b8560ff168181106112c5576112c5611934565b90506020020135838260ff16600581106112e1576112e1611934565b60200201525b6112f081612035565b9050611234565b5061130360058a612054565b985061131060058a611bb0565b935061131b82610b19565b945061132681612035565b9050611223565b5050505095945050505050565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b60405180606001604052806003906020820280368337509192915050565b60405180604001604052806002906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b600080604083850312156113f757600080fd5b50508035926020909101359150565b600081518084526020808501945080840160005b838110156114365781518752958201959082019060010161141a565b509495945050505050565b6020815260006114546020830184611406565b9392505050565b6000806000806080858703121561147157600080fd5b5050823594602084013594506040840135936060013592509050565b806101008101831015610a1457600080fd5b60008061012083850312156114b357600080fd5b823591506114c4846020850161148d565b90509250929050565b634e487b7160e01b600052602160045260246000fd5b6002811061150157634e487b7160e01b600052602160045260246000fd5b9052565b60208101610a1482846114e3565b60ff811681146110ca57600080fd5b803561152d81611513565b919050565b60008060008060008060008060e0898b03121561154e57600080fd5b8835975060208901359650604089013567ffffffffffffffff8082111561157457600080fd5b818b0191508b601f83011261158857600080fd5b81358181111561159757600080fd5b8c60208260051b85010111156115ac57600080fd5b602083019850809750505050606089013593506115cb60808a01611522565b925060a0890135915060c089013590509295985092959890939650565b634e487b7160e01b600052604160045260246000fd5b6040805190810167ffffffffffffffff81118282101715611621576116216115e8565b60405290565b60405160a0810167ffffffffffffffff81118282101715611621576116216115e8565b604051601f8201601f1916810167ffffffffffffffff81118282101715611673576116736115e8565b604052919050565b60006080828403121561168d57600080fd5b82601f83011261169c57600080fd5b6040516080810181811067ffffffffffffffff821117156116bf576116bf6115e8565b6040528060808401858111156116d457600080fd5b845b818110156116ee5780358352602092830192016116d6565b509195945050505050565b600067ffffffffffffffff821115611713576117136115e8565b5060051b60200190565b6000602080838503121561173057600080fd5b823567ffffffffffffffff81111561174757600080fd5b8301601f8101851361175857600080fd5b803561176b611766826116f9565b61164a565b81815260059190911b8201830190838101908783111561178a57600080fd5b928401925b828410156117a85783358252928401929084019061178f565b979650505050505050565b6000604082840312156117c557600080fd5b82601f8301126117d457600080fd5b6117dc6115fe565b8060408401858111156117ee57600080fd5b845b818110156118085780358452602093840193016117f0565b509095945050505050565b600060a0828403121561182557600080fd5b82601f83011261183457600080fd5b61183c611627565b8060a08401858111156117ee57600080fd5b6000806000610140848603121561186457600080fd5b833592506020840135915061187c856040860161148d565b90509250925092565b60006060828403121561189757600080fd5b82601f8301126118a657600080fd5b6040516060810181811067ffffffffffffffff821117156118c9576118c96115e8565b6040528060608401858111156116d457600080fd5b6001600160a01b03811681146110ca57600080fd5b60006020828403121561190557600080fd5b8135611454816118de565b6000806040838503121561192357600080fd5b505080516020909101519092909150565b634e487b7160e01b600052603260045260246000fd5b60006020828403121561195c57600080fd5b8151801515811461145457600080fd5b60006020828403121561197e57600080fd5b5051919050565b6000806000806080858703121561199b57600080fd5b84516119a681611513565b60208601519094506119b781611513565b60408601519093506119c881611513565b60608601519092506119d981611513565b939692955090935050565b634e487b7160e01b600052601160045260246000fd5b600181815b80851115611a35578160001904821115611a1b57611a1b6119e4565b80851615611a2857918102915b93841c93908002906119ff565b509250929050565b600082611a4c57506001610a14565b81611a5957506000610a14565b8160018114611a6f5760028114611a7957611a95565b6001915050610a14565b60ff841115611a8a57611a8a6119e4565b50506001821b610a14565b5060208310610133831016604e8410600b8410161715611ab8575081810a610a14565b611ac283836119fa565b8060001904821115611ad657611ad66119e4565b029392505050565b600061145460ff841683611a3d565b8082028115828204841417610a1457610a146119e4565b60808101818360005b6004811015611b2c578151835260209283019290910190600101611b0d565b50505092915050565b815160009082906020808601845b83811015611b5f57815185529382019390820190600101611b43565b50929695505050505050565b6000825160005b81811015611b8c5760208186018101518583015201611b72565b506000920191825250919050565b634e487b7160e01b600052601260045260246000fd5b600082611bbf57611bbf611b9a565b500690565b60408101818360005b6002811015611b2c578151835260209283019290910190600101611bcd565b60a08101818360005b6005811015611b2c578151835260209283019290910190600101611bf5565b60008060408385031215611c2757600080fd5b8251611c32816118de565b6020840151909250611c43816118de565b809150509250929050565b600060208284031215611c6057600080fd5b815161145481611513565b60ff858116825284811660208301528316604082015260808101611c9260608301846114e3565b95945050505050565b600060408284031215611cad57600080fd5b611cb56115fe565b9050815181526020820151602082015292915050565b600082601f830112611cdc57600080fd5b611ce46115fe565b806040840185811115611cf657600080fd5b845b81811015611808578051845260209384019301611cf8565b600060808284031215611d2257600080fd5b611d2a6115fe565b9050611d368383611ccb565b8152611d458360408401611ccb565b602082015292915050565b60006020808385031215611d6357600080fd5b825167ffffffffffffffff80821115611d7b57600080fd5b908401906101e08287031215611d9057600080fd5b611d98611627565b611da28784611c9b565b81526040611db288828601611d10565b85830152611dc38860c08601611d10565b81830152611dd5886101408601611d10565b60608301526101c084015183811115611ded57600080fd5b80850194505087601f850112611e0257600080fd5b83519250611e12611766846116f9565b83815260069390931b84018501928581019089851115611e3157600080fd5b948601945b84861015611e5757611e488a87611c9b565b82529482019490860190611e36565b60808401525090979650505050505050565b8060005b60028110156111fd578151845260209384019390910190600101611e6d565b611e97828251611e69565b6020810151611ea96040840182611e69565b505050565b6000610140610100808785378181850152506103208301611edc828501875180518252602090810151910152565b6020915081860151611ef2610180860182611e8c565b50604080870151611f07610200870182611e8c565b506060870151611f1b610280870182611e8c565b5060808701516101e06103008701528051928390528301916000906103408701905b80831015611f6e57611f5a82865180518252602090810151910152565b938501936001929092019190830190611f3d565b50868103610120880152611f828189611406565b9a9950505050505050505050565b60608101818360005b6003811015611b2c578151835260209283019290910190600101611f99565b81810381811115610a1457610a146119e4565b60ff8281168282160390811115610a1457610a146119e4565b6000808335601e19843603018112611ffb57600080fd5b83018035915067ffffffffffffffff82111561201657600080fd5b6020019150600581901b360382131561202e57600080fd5b9250929050565b600060ff821660ff810361204b5761204b6119e4565b60010192915050565b60008261206357612063611b9a565b50049056fea2646970667358221220244464250cea5ddc4c07dec2f9655787632948ec5cafcdca7b9fcac6fb838ccc64736f6c63430008140033a264697066735822122093627fb321c89ef8059995d44cd21b6e0d726a750120691bac51903310f4d5f164736f6c63430008140033

0x608060405234801561001057600080fd5b50600436106100365760003560e01c8063431a71751461003b578063683f3dc31461006b575b600080fd5b61004e6100493660046100fb565b610085565b6040516001600160a01b0390911681526020015b60405180910390f35b610073600a81565b60405160ff9091168152602001610062565b60008087878787878760405161009a906100d2565b6100a996959493929190610177565b604051809103906000f0801580156100c5573d6000803e3d6000fd5b5098975050505050505050565b61232b806101d783390190565b80356001600160a01b03811681146100f657600080fd5b919050565b60008060008060008060c0878903121561011457600080fd5b61011d876100df565b955061012b602088016100df565b9450610139604088016100df565b9350610147606088016100df565b9250610155608088016100df565b915060a08701356002811061016957600080fd5b809150509295509295509295565b6001600160a01b0387811682528681166020830152858116604083015284811660608301528316608082015260c08101600283106101c557634e487b7160e01b600052602160045260246000fd5b8260a083015297965050505050505056fe6101206040526040516200232b3803806200232b83398101604081905262000027916200012c565b816001600160a01b0381166200005757604051631e4fbdf760e01b81526000600482015260240160405180910390fd5b6200006281620000bf565b506001600160a01b0380871660805285811660a05284811660c052831660e052806001811115620000975762000097620001b4565b610100816001811115620000af57620000af620001b4565b81525050505050505050620001ca565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b80516001600160a01b03811681146200012757600080fd5b919050565b60008060008060008060c087890312156200014657600080fd5b62000151876200010f565b955062000161602088016200010f565b945062000171604088016200010f565b935062000181606088016200010f565b925062000191608088016200010f565b915060a087015160028110620001a657600080fd5b809150509295509295509295565b634e487b7160e01b600052602160045260246000fd5b60805160a05160c05160e0516101005161209e6200028d600039600081816102400152818161055f015281816105ab015281816108fd01528181610b6901528181610bd90152610dfa0152600081816103c00152818161060001526106a90152600081816103570152818161040c0152818161073c0152818161076c0152818161081801528181610c4901528181610cd301528181610f5d0152610fe60152600081816101e40152610d670152600081816102740152610e97015261209e6000f3fe608060405234801561001057600080fd5b506004361061018e5760003560e01c8063683f3dc3116100de578063afb93bd311610097578063d0380fe211610071578063d0380fe2146103bb578063d13181b8146103e2578063e3ff7606146103eb578063f2fde38b146103f357600080fd5b8063afb93bd31461038c578063b904438814610395578063bea140b3146103a857600080fd5b8063683f3dc31461030c578063715018a6146103265780638da5cb5b1461032e5780639cfced971461033f578063a117527914610352578063a21fb5111461037957600080fd5b80632b7ac3f31161014b57806358bfc3791161012557806358bfc379146102ca5780635bb93995146102dd57806361750293146102f057806362a361bb146102f957600080fd5b80632b7ac3f31461026f5780632d966bf4146102965780633dfb88b2146102a957600080fd5b8063023650801461019357806310bc5f51146101bc57806313fb8932146101df57806316425eeb1461021e57806323e3feb114610228578063295a52121461023b575b600080fd5b6101a66101a13660046113e4565b610406565b6040516101b39190611441565b60405180910390f35b6101cf6101ca36600461145b565b61055a565b60405190151581526020016101b3565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6040516001600160a01b0390911681526020016101b3565b6102266105f6565b005b61022661023636600461149f565b61072f565b6102627f000000000000000000000000000000000000000000000000000000000000000081565b6040516101b39190611505565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6101cf6102a4366004611532565b6108f8565b6102bc6102b736600461167b565b610999565b6040519081526020016101b3565b6102bc6102d836600461171d565b610a1a565b6102bc6102eb3660046113e4565b610ab4565b6102bc60015481565b6102bc6103073660046117b3565b610acd565b610314600a81565b60405160ff90911681526020016101b3565b610226610b07565b6000546001600160a01b0316610206565b6102bc61034d366004611813565b610b19565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6101cf610387366004611532565b610b53565b6102bc60025481565b6101cf6103a336600461184e565b610c42565b6102bc6103b6366004611885565b610f1e565b6102067f000000000000000000000000000000000000000000000000000000000000000081565b6102bc60035481565b6101cf610f58565b6102266104013660046118f3565b61108a565b606060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015610467573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061048b9190611910565b5060408051600580825260c082019092529192506020820160a080368337019050509150600354826000815181106104c5576104c5611934565b602002602001018181525050600154826001815181106104e7576104e7611934565b602002602001018181525050828260028151811061050757610507611934565b602002602001018181525050838260038151811061052757610527611934565b602002602001018181525050808260048151811061054757610547611934565b6020026020010181815250505092915050565b6000807f0000000000000000000000000000000000000000000000000000000000000000600181111561058f5761058f6114cd565b036105a7576105a0858585856110cd565b90506105ee565b60017f000000000000000000000000000000000000000000000000000000000000000060018111156105db576105db6114cd565b036105ee576105eb858585611107565b90505b949350505050565b6105fe611139565b7f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316638763d0c46040518163ffffffff1660e01b8152600401602060405180830381865afa15801561065c573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610680919061194a565b61069d5760405163f13e1b8560e01b815260040160405180910390fd5b60035460000361072d577f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663d13181b86040518163ffffffff1660e01b8152600401602060405180830381865afa158015610705573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610729919061196c565b6003555b565b610737611139565b6107607f0000000000000000000000000000000000000000000000000000000000000000611166565b6107686105f6565b60007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa1580156107c8573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906107ec9190611985565b505050905060008160026108009190611ade565b90506000816002546108129190611aed565b905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015610873573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906108979190611910565b5090508082106108ba5760405163b3f8c18960e01b815260040160405180910390fd5b6002805460010190556108ce828787610c42565b6108eb576040516341acf34d60e01b815260040160405180910390fd5b5050506001929092555050565b6000807f0000000000000000000000000000000000000000000000000000000000000000600181111561092d5761092d6114cd565b1461094b57604051630280e1e560e61b815260040160405180910390fd5b600061095a858b8b8b8b611203565b905061096461138a565b838152602081018590526109788288610ab4565b604082015260015461098982610f1e565b149b9a5050505050505050505050565b60405163248f667760e01b815260009073e0398f7dfac494c530f6404afeac8669abed26799063248f6677906109d3908590600401611b04565b602060405180830381865af41580156109f0573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610a14919061196c565b92915050565b60007f30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001600283604051602001610a509190611b35565b60408051601f1981840301815290829052610a6a91611b6b565b602060405180830381855afa158015610a87573d6000803e3d6000fd5b5050506040513d601f19601f82011682018060405250810190610aaa919061196c565b610a149190611bb0565b6000610abe6113a8565b838152602081018390526105ee815b6040516314d2f97b60e11b81526000907307490eba00dc4aca6721d052fa4c5002aa077233906329a5f2f6906109d3908590600401611bc4565b610b0f611139565b61072d600061133a565b604051630926f44b60e31b815260009073fd77833f10a29c76a6a0ede235eb651d744d0e2f90634937a258906109d3908590600401611bec565b600080610b63858b8b8b8b611203565b905060007f00000000000000000000000000000000000000000000000000000000000000006001811115610b9957610b996114cd565b03610bd557610ba661138a565b610bb08288610ab4565b81526020810185905260408101849052600154610bcc82610f1e565b14925050610c35565b60017f00000000000000000000000000000000000000000000000000000000000000006001811115610c0957610c096114cd565b03610c3557610c166113a8565b610c208288610ab4565b81526020810185905260015461098982610acd565b5098975050505050505050565b60008060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa158015610ca5573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610cc99190611985565b93505050915060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663bc14ee2b6040518163ffffffff1660e01b81526004016040805180830381865afa158015610d2e573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610d529190611c14565b5090506000610d618888610406565b905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b03166310b37e4d846001600160a01b031663652c76e46040518163ffffffff1660e01b8152600401602060405180830381865afa158015610dd2573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610df69190611c4e565b87877f00000000000000000000000000000000000000000000000000000000000000006040518563ffffffff1660e01b8152600401610e389493929190611c6b565b600060405180830381865afa158015610e55573d6000803e3d6000fd5b505050506040513d6000823e601f3d908101601f19168201604052610e7d9190810190611d50565b60405163352a4d1560e01b81529091506001600160a01b037f0000000000000000000000000000000000000000000000000000000000000000169063352a4d1590610ed0908a9085908790600401611eae565b602060405180830381865afa158015610eed573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610f11919061194a565b9998505050505050505050565b6040516304b98e1d60e31b815260009073bb0e724ce02e5e7edd31e632dc6e59f229a1126d906325cc70e8906109d3908590600401611f90565b6000807f00000000000000000000000000000000000000000000000000000000000000006001600160a01b031663ac98e5df6040518163ffffffff1660e01b8152600401608060405180830381865afa158015610fb9573d6000803e3d6000fd5b505050506040513d601f19601f82011682018060405250810190610fdd9190611985565b505050905060007f00000000000000000000000000000000000000000000000000000000000000006001600160a01b0316634f367f0f6040518163ffffffff1660e01b81526004016040805180830381865afa158015611041573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906110659190611910565b50905080611074836002611ade565b6002546110819190611aed565b10159250505090565b611092611139565b6001600160a01b0381166110c157604051631e4fbdf760e01b8152600060048201526024015b60405180910390fd5b6110ca8161133a565b50565b60006110d761138a565b8381526110e48686610ab4565b6020820152604081018390526001546110fc82610f1e565b149695505050505050565b60006111116113a8565b82815261111e8585610ab4565b602082015260015461112f82610acd565b1495945050505050565b6000546001600160a01b0316331461072d5760405163118cdaa760e01b81523360048201526024016110b8565b600080826001600160a01b0316634909229f6040518163ffffffff1660e01b81526004016040805180830381865afa1580156111a6573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906111ca9190611910565b909250905060006111db8342611fb8565b90508181116111fd57604051635c3017c560e11b815260040160405180910390fd5b50505050565b600080611211600587611bb0565b905084915060006112206113c6565b60005b8960ff168160ff16101561132d5760005b60058160ff1610156112f757848160ff160361126a5785838260ff166005811061126057611260611934565b60200201526112e7565b848160ff16111561128757611280600182611fcb565b935061128b565b8093505b87878360ff168181106112a0576112a0611934565b90506020028101906112b29190611fe4565b8560ff168181106112c5576112c5611934565b90506020020135838260ff16600581106112e1576112e1611934565b60200201525b6112f081612035565b9050611234565b5061130360058a612054565b985061131060058a611bb0565b935061131b82610b19565b945061132681612035565b9050611223565b5050505095945050505050565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b60405180606001604052806003906020820280368337509192915050565b60405180604001604052806002906020820280368337509192915050565b6040518060a001604052806005906020820280368337509192915050565b600080604083850312156113f757600080fd5b50508035926020909101359150565b600081518084526020808501945080840160005b838110156114365781518752958201959082019060010161141a565b509495945050505050565b6020815260006114546020830184611406565b9392505050565b6000806000806080858703121561147157600080fd5b5050823594602084013594506040840135936060013592509050565b806101008101831015610a1457600080fd5b60008061012083850312156114b357600080fd5b823591506114c4846020850161148d565b90509250929050565b634e487b7160e01b600052602160045260246000fd5b6002811061150157634e487b7160e01b600052602160045260246000fd5b9052565b60208101610a1482846114e3565b60ff811681146110ca57600080fd5b803561152d81611513565b919050565b60008060008060008060008060e0898b03121561154e57600080fd5b8835975060208901359650604089013567ffffffffffffffff8082111561157457600080fd5b818b0191508b601f83011261158857600080fd5b81358181111561159757600080fd5b8c60208260051b85010111156115ac57600080fd5b602083019850809750505050606089013593506115cb60808a01611522565b925060a0890135915060c089013590509295985092959890939650565b634e487b7160e01b600052604160045260246000fd5b6040805190810167ffffffffffffffff81118282101715611621576116216115e8565b60405290565b60405160a0810167ffffffffffffffff81118282101715611621576116216115e8565b604051601f8201601f1916810167ffffffffffffffff81118282101715611673576116736115e8565b604052919050565b60006080828403121561168d57600080fd5b82601f83011261169c57600080fd5b6040516080810181811067ffffffffffffffff821117156116bf576116bf6115e8565b6040528060808401858111156116d457600080fd5b845b818110156116ee5780358352602092830192016116d6565b509195945050505050565b600067ffffffffffffffff821115611713576117136115e8565b5060051b60200190565b6000602080838503121561173057600080fd5b823567ffffffffffffffff81111561174757600080fd5b8301601f8101851361175857600080fd5b803561176b611766826116f9565b61164a565b81815260059190911b8201830190838101908783111561178a57600080fd5b928401925b828410156117a85783358252928401929084019061178f565b979650505050505050565b6000604082840312156117c557600080fd5b82601f8301126117d457600080fd5b6117dc6115fe565b8060408401858111156117ee57600080fd5b845b818110156118085780358452602093840193016117f0565b509095945050505050565b600060a0828403121561182557600080fd5b82601f83011261183457600080fd5b61183c611627565b8060a08401858111156117ee57600080fd5b6000806000610140848603121561186457600080fd5b833592506020840135915061187c856040860161148d565b90509250925092565b60006060828403121561189757600080fd5b82601f8301126118a657600080fd5b6040516060810181811067ffffffffffffffff821117156118c9576118c96115e8565b6040528060608401858111156116d457600080fd5b6001600160a01b03811681146110ca57600080fd5b60006020828403121561190557600080fd5b8135611454816118de565b6000806040838503121561192357600080fd5b505080516020909101519092909150565b634e487b7160e01b600052603260045260246000fd5b60006020828403121561195c57600080fd5b8151801515811461145457600080fd5b60006020828403121561197e57600080fd5b5051919050565b6000806000806080858703121561199b57600080fd5b84516119a681611513565b60208601519094506119b781611513565b60408601519093506119c881611513565b60608601519092506119d981611513565b939692955090935050565b634e487b7160e01b600052601160045260246000fd5b600181815b80851115611a35578160001904821115611a1b57611a1b6119e4565b80851615611a2857918102915b93841c93908002906119ff565b509250929050565b600082611a4c57506001610a14565b81611a5957506000610a14565b8160018114611a6f5760028114611a7957611a95565b6001915050610a14565b60ff841115611a8a57611a8a6119e4565b50506001821b610a14565b5060208310610133831016604e8410600b8410161715611ab8575081810a610a14565b611ac283836119fa565b8060001904821115611ad657611ad66119e4565b029392505050565b600061145460ff841683611a3d565b8082028115828204841417610a1457610a146119e4565b60808101818360005b6004811015611b2c578151835260209283019290910190600101611b0d565b50505092915050565b815160009082906020808601845b83811015611b5f57815185529382019390820190600101611b43565b50929695505050505050565b6000825160005b81811015611b8c5760208186018101518583015201611b72565b506000920191825250919050565b634e487b7160e01b600052601260045260246000fd5b600082611bbf57611bbf611b9a565b500690565b60408101818360005b6002811015611b2c578151835260209283019290910190600101611bcd565b60a08101818360005b6005811015611b2c578151835260209283019290910190600101611bf5565b60008060408385031215611c2757600080fd5b8251611c32816118de565b6020840151909250611c43816118de565b809150509250929050565b600060208284031215611c6057600080fd5b815161145481611513565b60ff858116825284811660208301528316604082015260808101611c9260608301846114e3565b95945050505050565b600060408284031215611cad57600080fd5b611cb56115fe565b9050815181526020820151602082015292915050565b600082601f830112611cdc57600080fd5b611ce46115fe565b806040840185811115611cf657600080fd5b845b81811015611808578051845260209384019301611cf8565b600060808284031215611d2257600080fd5b611d2a6115fe565b9050611d368383611ccb565b8152611d458360408401611ccb565b602082015292915050565b60006020808385031215611d6357600080fd5b825167ffffffffffffffff80821115611d7b57600080fd5b908401906101e08287031215611d9057600080fd5b611d98611627565b611da28784611c9b565b81526040611db288828601611d10565b85830152611dc38860c08601611d10565b81830152611dd5886101408601611d10565b60608301526101c084015183811115611ded57600080fd5b80850194505087601f850112611e0257600080fd5b83519250611e12611766846116f9565b83815260069390931b84018501928581019089851115611e3157600080fd5b948601945b84861015611e5757611e488a87611c9b565b82529482019490860190611e36565b60808401525090979650505050505050565b8060005b60028110156111fd578151845260209384019390910190600101611e6d565b611e97828251611e69565b6020810151611ea96040840182611e69565b505050565b6000610140610100808785378181850152506103208301611edc828501875180518252602090810151910152565b6020915081860151611ef2610180860182611e8c565b50604080870151611f07610200870182611e8c565b506060870151611f1b610280870182611e8c565b5060808701516101e06103008701528051928390528301916000906103408701905b80831015611f6e57611f5a82865180518252602090810151910152565b938501936001929092019190830190611f3d565b50868103610120880152611f828189611406565b9a9950505050505050505050565b60608101818360005b6003811015611b2c578151835260209283019290910190600101611f99565b81810381811115610a1457610a146119e4565b60ff8281168282160390811115610a1457610a146119e4565b6000808335601e19843603018112611ffb57600080fd5b83018035915067ffffffffffffffff82111561201657600080fd5b6020019150600581901b360382131561202e57600080fd5b9250929050565b600060ff821660ff810361204b5761204b6119e4565b60010192915050565b60008261206357612063611b9a565b50049056fea2646970667358221220244464250cea5ddc4c07dec2f9655787632948ec5cafcdca7b9fcac6fb838ccc64736f6c63430008140033a264697066735822122093627fb321c89ef8059995d44cd21b6e0d726a750120691bac51903310f4d5f164736f6c63430008140033