// File: DepositVerifier.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./InnerProductVerifier.sol";
import "./Utils.sol";

contract DepositVerifier {
    using Utils for uint256;
    using Utils for Utils.Point;

    InnerProductVerifier immutable _ip;

    constructor(address ip_) {
        _ip = InnerProductVerifier(ip_);
    }

    function g() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.gX(), _ip.gY());
    }

    function h() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.hX(), _ip.hY());
    }

    function gs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.gs(i);
        return Utils.Point(x, y);
    }

    function hs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.hs(i);
        return Utils.Point(x, y);
    }

    struct Locals {
        uint256 v;
        uint256 w;
        uint256 vPow;
        uint256 wPow;
        uint256[n][2] f; // could just allocate extra space in the proof?
        uint256[N] r; // each poly is an array of length N. evaluations of prods
        Utils.Point temp;
        Utils.Point C_XR;
        Utils.Point y_XR;

        uint256 c;
        Utils.Point A_D;
        Utils.Point A_X;
    }

    function verify(uint256 amount, Utils.Statement calldata statement, Utils.DepositProof calldata proof) external view {
        Locals memory locals;
        locals.v = uint256(keccak256(abi.encode(amount, statement.Y, statement.C, statement.D, proof.A, proof.B))).mod();
        locals.w = uint256(keccak256(abi.encode(locals.v, proof.C_XG, proof.y_XG))).mod();
        for (uint256 k = 0; k < n; k++) {
            locals.f[1][k] = proof.f[k];
            locals.f[0][k] = locals.w.sub(proof.f[k]);

            locals.temp = locals.temp.add(gs(k).mul(locals.f[1][k]));
            locals.temp = locals.temp.add(hs(k).mul(locals.f[1][k].mul(locals.f[0][k])));
        }
        require(proof.B.mul(locals.w).add(proof.A).eq(locals.temp.add(h().mul(proof.z_A))), "Bit-proof verification failed.");

        locals.r = Utils.assemblePolynomials(locals.f);
        locals.wPow = 1;
        for (uint256 k = 0; k < n; k++) {
            locals.C_XR = locals.C_XR.add(proof.C_XG[k].mul(locals.wPow.neg()));
            locals.y_XR = locals.y_XR.add(proof.y_XG[k].mul(locals.wPow.neg()));

            locals.wPow = locals.wPow.mul(locals.w);
        }
        locals.vPow = locals.v; // used to be 1
        for (uint256 i = 0; i < N; i++) {
            uint256 multiplier = locals.r[i].add(locals.vPow.mul(locals.wPow.sub(locals.r[i]))); // locals. ?
            locals.C_XR = locals.C_XR.add(statement.C[i].mul(multiplier));
            locals.y_XR = locals.y_XR.add(statement.Y[i].mul(multiplier));
            locals.vPow = locals.vPow.mul(locals.v); // used to do this only if (i > 0)
        }
        locals.C_XR = locals.C_XR.add(g().mul(amount.neg().mul(locals.wPow))); // this line is new

        locals.A_D = g().mul(proof.s_r).add(statement.D.mul(proof.c.neg())); // add(mul(locals.gR, proof.s_r), mul(locals.DR, proof.c.neg()));
        locals.A_X = locals.y_XR.mul(proof.s_r).add(locals.C_XR.mul(proof.c.neg()));

        locals.c = uint256(keccak256(abi.encode(locals.v, locals.A_D, locals.A_X))).mod();
        require(locals.c == proof.c, "Sigma protocol failure.");
    }
}
// File: EpochTree.sol



// SPDX-License-Identifier: MIT

pragma solidity 0.8.17;

// ----------------------------------------------------------------------------
// BokkyPooBah's Red-Black Tree Library v1.0-pre-release-a
//
// A Solidity Red-Black Tree binary search library to store and access a sorted
// list of unsigned integer data. The Red-Black algorithm rebalances the binary
// search tree, resulting in O(log n) insert, remove and search time (and ~gas)
//
// https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary
//
//
// Enjoy. (c) BokkyPooBah / Bok Consulting Pty Ltd 2020. The MIT Licence.
// ----------------------------------------------------------------------------
contract EpochTree {
    struct Node {
        uint64 parent;
        uint64 left;
        uint64 right;
        bool red;
    }

    uint64 public root;
    uint64 public blackHeight;
    uint64 constant EMPTY = 0;

    mapping(uint64 => Node) public nodes;

    function exists(uint64 key) public view returns (bool) { // need public for FirnLogic.sol
        return (key != EMPTY) && ((key == root) || (nodes[key].parent != EMPTY));
    }

    function rotateLeft(uint64 key) internal {
        uint64 cursor = nodes[key].right;
        uint64 keyParent = nodes[key].parent;
        uint64 cursorLeft = nodes[cursor].left;
        nodes[key].right = cursorLeft;
        if (cursorLeft != EMPTY) {
            nodes[cursorLeft].parent = key;
        }
        nodes[cursor].parent = keyParent;
        if (keyParent == EMPTY) {
            root = cursor;
        } else if (key == nodes[keyParent].left) {
            nodes[keyParent].left = cursor;
        } else {
            nodes[keyParent].right = cursor;
        }
        nodes[cursor].left = key;
        nodes[key].parent = cursor;
    }

    function rotateRight(uint64 key) internal {
        uint64 cursor = nodes[key].left;
        uint64 keyParent = nodes[key].parent;
        uint64 cursorRight = nodes[cursor].right;
        nodes[key].left = cursorRight;
        if (cursorRight != EMPTY) {
            nodes[cursorRight].parent = key;
        }
        nodes[cursor].parent = keyParent;
        if (keyParent == EMPTY) {
            root = cursor;
        } else if (key == nodes[keyParent].right) {
            nodes[keyParent].right = cursor;
        } else {
            nodes[keyParent].left = cursor;
        }
        nodes[cursor].right = key;
        nodes[key].parent = cursor;
    }

    function insertFixup(uint64 key) internal {
        uint64 cursor;
        while (key != root && nodes[nodes[key].parent].red) {
            uint64 keyParent = nodes[key].parent;
            if (keyParent == nodes[nodes[keyParent].parent].left) {
                cursor = nodes[nodes[keyParent].parent].right;
                if (nodes[cursor].red) {
                    nodes[keyParent].red = false;
                    nodes[cursor].red = false;
                    nodes[nodes[keyParent].parent].red = true;
                    key = nodes[keyParent].parent;
                } else {
                    if (key == nodes[keyParent].right) {
                        key = keyParent;
                        rotateLeft(key);
                    }
                    keyParent = nodes[key].parent;
                    nodes[keyParent].red = false;
                    nodes[nodes[keyParent].parent].red = true;
                    rotateRight(nodes[keyParent].parent);
                }
            } else {
                cursor = nodes[nodes[keyParent].parent].left;
                if (nodes[cursor].red) {
                    nodes[keyParent].red = false;
                    nodes[cursor].red = false;
                    nodes[nodes[keyParent].parent].red = true;
                    key = nodes[keyParent].parent;
                } else {
                    if (key == nodes[keyParent].left) {
                        key = keyParent;
                        rotateRight(key);
                    }
                    keyParent = nodes[key].parent;
                    nodes[keyParent].red = false;
                    nodes[nodes[keyParent].parent].red = true;
                    rotateLeft(nodes[keyParent].parent);
                }
            }
        }
        if (nodes[root].red) {
            nodes[root].red = false;
            blackHeight++;
        }
    }

    function insert(uint64 key) internal {
        uint64 cursor = EMPTY;
        uint64 probe = root;
        while (probe != EMPTY) {
            cursor = probe;
            if (key < probe) {
                probe = nodes[probe].left;
            } else {
                probe = nodes[probe].right;
            }
        }
        nodes[key] = Node({parent : cursor, left : EMPTY, right : EMPTY, red : true});
        if (cursor == EMPTY) {
            root = key;
        } else if (key < cursor) {
            nodes[cursor].left = key;
        } else {
            nodes[cursor].right = key;
        }
        insertFixup(key);
    }

    function replaceParent(uint64 a, uint64 b) internal {
        uint64 bParent = nodes[b].parent;
        nodes[a].parent = bParent;
        if (bParent == EMPTY) {
            root = a;
        } else {
            if (b == nodes[bParent].left) {
                nodes[bParent].left = a;
            } else {
                nodes[bParent].right = a;
            }
        }
    }

    function removeFixup(uint64 key) internal {
        uint64 cursor;
        while (key != root && !nodes[key].red) {
            uint64 keyParent = nodes[key].parent;
            if (key == nodes[keyParent].left) {
                cursor = nodes[keyParent].right;
                if (nodes[cursor].red) {
                    nodes[cursor].red = false;
                    nodes[keyParent].red = true;
                    rotateLeft(keyParent);
                    cursor = nodes[keyParent].right;
                }
                if (!nodes[nodes[cursor].left].red && !nodes[nodes[cursor].right].red) {
                    nodes[cursor].red = true;
                    key = keyParent;
                } else {
                    if (!nodes[nodes[cursor].right].red) {
                        nodes[nodes[cursor].left].red = false;
                        nodes[cursor].red = true;
                        rotateRight(cursor);
                        cursor = nodes[keyParent].right;
                    }
                    nodes[cursor].red = nodes[keyParent].red;
                    nodes[keyParent].red = false;
                    nodes[nodes[cursor].right].red = false;
                    rotateLeft(keyParent);
                    return; // key = root;
                }
            } else {
                cursor = nodes[keyParent].left;
                if (nodes[cursor].red) {
                    nodes[cursor].red = false;
                    nodes[keyParent].red = true;
                    rotateRight(keyParent);
                    cursor = nodes[keyParent].left;
                }
                if (!nodes[nodes[cursor].right].red && !nodes[nodes[cursor].left].red) {
                    nodes[cursor].red = true;
                    key = keyParent;
                } else {
                    if (!nodes[nodes[cursor].left].red) {
                        nodes[nodes[cursor].right].red = false;
                        nodes[cursor].red = true;
                        rotateLeft(cursor);
                        cursor = nodes[keyParent].left;
                    }
                    nodes[cursor].red = nodes[keyParent].red;
                    nodes[keyParent].red = false;
                    nodes[nodes[cursor].left].red = false;
                    rotateRight(keyParent);
                    return; // key = root;
                }
            }
        }
        if (nodes[key].red) nodes[key].red = false;
        else blackHeight--;
    }

    function remove(uint64 key) internal {
        uint64 probe;
        uint64 cursor;
        if (nodes[key].left == EMPTY || nodes[key].right == EMPTY) {
            cursor = key;
        } else {
            cursor = nodes[key].right;
            while (nodes[cursor].left != EMPTY) {
                cursor = nodes[cursor].left;
            }
        }
        if (nodes[cursor].left != EMPTY) {
            probe = nodes[cursor].left;
        } else {
            probe = nodes[cursor].right;
        }
        uint64 yParent = nodes[cursor].parent;
        nodes[probe].parent = yParent;
        if (yParent != EMPTY) {
            if (cursor == nodes[yParent].left) {
                nodes[yParent].left = probe;
            } else {
                nodes[yParent].right = probe;
            }
        } else {
            root = probe;
        }
        bool doFixup = !nodes[cursor].red;
        if (cursor != key) {
            replaceParent(cursor, key);
            nodes[cursor].left = nodes[key].left;
            nodes[nodes[cursor].left].parent = cursor;
            nodes[cursor].right = nodes[key].right;
            nodes[nodes[cursor].right].parent = cursor;
            nodes[cursor].red = nodes[key].red;
            (cursor, key) = (key, cursor);
        }
        if (doFixup) {
            removeFixup(probe);
        }
        delete nodes[cursor];
    }
}
// ----------------------------------------------------------------------------
// End - BokkyPooBah's Red-Black Tree Library
// ----------------------------------------------------------------------------
// File: FirnBase.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./Utils.sol";
import "./EpochTree.sol";

contract FirnBase is EpochTree {
    address _owner;
    address _logic;

    mapping(bytes32 => Utils.Point[2]) public acc; // main account mapping
    mapping(bytes32 => Utils.Point[2]) public pending; // storage for pending transfers

    struct Info { // try to save storage space by using smaller int types here
        uint64 epoch;
        uint64 index; // index in the list
        uint64 amount;
    }
    mapping(bytes32 => Info) public info; // public key --> deposit info
    mapping(uint64 => bytes32[]) public lists; // epoch --> list of depositing accounts

    function lengths(uint64 epoch) external view returns (uint256) { // see https://ethereum.stackexchange.com/a/20838.
        return lists[epoch].length;
    }

    modifier onlyOwner() {
        require(msg.sender == _owner, "Caller is not the owner.");
        _;
    }

    modifier onlyLogic() {
        require(msg.sender == _logic, "Caller is not the logic contract.");
        _;
    }

    constructor() {
        _owner = msg.sender;
    }

    function administrate(address owner_, address logic_) external onlyOwner {
        _owner = owner_;
        _logic = logic_;
    }

    receive() external payable onlyLogic {
        // modifier isn't necessary for security, but will prevent people from wasting funds
    }

    function setAcc(bytes32 pub, Utils.Point[2] calldata value) external onlyLogic {
//        acc[pub] = value; // Copying of type struct Utils.Point calldata[2] calldata to storage not yet supported.
        acc[pub][0] = value[0];
        acc[pub][1] = value[1];
    }

    function setPending(bytes32 pub, Utils.Point[2] calldata value) external onlyLogic {
//        pending[pub] = value; // Copying of type struct Utils.Point calldata[2] calldata to storage not yet supported.
        pending[pub][0] = value[0];
        pending[pub][1] = value[1];
    }

    function setInfo(bytes32 pub, Info calldata value) external onlyLogic {
        info[pub] = value;
    }

    function setList(uint64 epoch, uint256 index, bytes32 value) external onlyLogic {
        lists[epoch][index] = value;
    }

    function popList(uint64 epoch) external onlyLogic {
        lists[epoch].pop();
    }

    function pushList(uint64 epoch, bytes32 value) external onlyLogic {
        lists[epoch].push(value);
    }

    function insertEpoch(uint64 epoch) external onlyLogic {
        insert(epoch);
    }

    function removeEpoch(uint64 epoch) external onlyLogic {
        remove(epoch);
    }

    function pay(address destination, uint256 value, bytes calldata data) external payable onlyLogic {
        (bool success,) = payable(destination).call{value: value}(data);
        require(success, "External call failed.");
    }
}
// File: FirnLogic.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./FirnBase.sol";
import "./DepositVerifier.sol";
import "./TransferVerifier.sol";
import "./WithdrawalVerifier.sol";
import "./Utils.sol";

contract FirnLogic {
    using Utils for uint256;
    using Utils for Utils.Point;

    mapping(bytes32 => uint64) _lastRollOver;
    bytes32[] _nonces; // would be more natural to use a mapping (really a set), but they can't be deleted / reset!
    uint64 _lastGlobalUpdate = 0; // will be also used as a proxy for "current epoch", seeing as rollovers will be anticipated

    uint256 constant EPOCH_LENGTH = 60;

    FirnBase immutable _base;
    DepositVerifier immutable _deposit;
    TransferVerifier immutable _transfer;
    WithdrawalVerifier immutable _withdrawal;

    event RegisterOccurred(address indexed sender, bytes32 indexed account);
    event DepositOccurred(bytes32[N] Y, bytes32[N] C, bytes32 D, address indexed source, uint32 amount); // amount not indexed
    event TransferOccurred(bytes32[N] Y, bytes32[N] C, bytes32 D);
    event WithdrawalOccurred(bytes32[N] Y, bytes32[N] C, bytes32 D, uint32 amount, address indexed destination, bytes data);

    address _owner;
    address _treasury;
    uint32 _fee;

    // some duplication here, but this is less painful than trying to retrieve it from the IP verifier / elsewhere.
    bytes32 immutable _gX;
    bytes32 immutable _gY;

    modifier onlyOwner() {
        require(msg.sender == _owner, "Caller is not the owner.");
        _;
    }

    constructor(address payable base_, address deposit_, address transfer_, address withdrawal_) {
        _owner = msg.sender;
        _base = FirnBase(base_);
        _deposit = DepositVerifier(deposit_);
        _transfer = TransferVerifier(transfer_);
        _withdrawal = WithdrawalVerifier(withdrawal_);

        Utils.Point memory gTemp = Utils.mapInto("g");
        _gX = gTemp.x;
        _gY = gTemp.y;
    }

    function administrate(address owner_, address treasury_, uint32 fee_) external onlyOwner {
        _owner = owner_;
        _treasury = treasury_;
        _fee = fee_;
    }

    function g() internal view returns (Utils.Point memory) {
        return Utils.Point(_gX, _gY);
    }

    function rollOver(bytes32 Y, uint64 epoch) internal {
        if (_lastRollOver[Y] < epoch) {
            Utils.Point[2] memory acc;
            (acc[0].x, acc[0].y) = _base.acc(Y, 0);
            (acc[1].x, acc[1].y) = _base.acc(Y, 1);
            Utils.Point[2] memory pending;
            (pending[0].x, pending[0].y) = _base.pending(Y, 0);
            (pending[1].x, pending[1].y) = _base.pending(Y, 1);
            acc[0] = acc[0].add(pending[0]);
            acc[1] = acc[1].add(pending[1]);
            delete pending;
            _base.setAcc(Y, acc);
            _base.setPending(Y, pending);
            _lastRollOver[Y] = epoch;
        }
    }

    function touch(bytes32 Y, uint32 credit, uint64 epoch) internal {
        // could save a few operations if we check for the special case that current.epoch == epoch.
        FirnBase.Info memory current;
        (current.epoch, current.index, current.amount) = _base.info(Y);
        if (current.epoch > 0) { // will only be false for registration...?
            _base.setList(current.epoch, current.index, _base.lists(current.epoch, _base.lengths(current.epoch) - 1)); // list[current.index] = list[list.length - 1];
            _base.popList(current.epoch); // lists[current.epoch].pop();
            if (_base.lengths(current.epoch) == 0) _base.removeEpoch(current.epoch); // if (lists[current.epoch].length == 0) remove(current.epoch);
            else if (current.index < _base.lengths(current.epoch)) {
                // else if (current.index < lists[current.epoch].length) info[lists[current.epoch][current.index]].index = current.index;
                FirnBase.Info memory other;
                (other.epoch, other.index, other.amount) = _base.info(_base.lists(current.epoch, current.index));
                other.index = current.index;
                _base.setInfo(_base.lists(current.epoch, current.index), other);
            }
        }
        current.epoch = epoch;
        current.amount += credit; // implicit conversion of RHS to uint64?
        if (!_base.exists(epoch)) {
            _base.insertEpoch(epoch);
        }
        current.index = uint64(_base.lengths(epoch)); // uint64(lists[epoch].length);
        _base.setInfo(Y, current);
        _base.pushList(epoch, Y); // lists[epoch].push(Y);
    }

    function simulateAccounts(bytes32[] calldata Y, uint32 epoch) external view returns (bytes32[2][] memory result) {
        // interestingly, we lose no efficiency by accepting compressed, because we never have to decompress.
        result = new bytes32[2][](Y.length);
        for (uint256 i = 0; i < Y.length; i++) {
            Utils.Point[2] memory acc;
            (acc[0].x, acc[0].y) = _base.acc(Y[i], 0);
            (acc[1].x, acc[1].y) = _base.acc(Y[i], 1);
            if (_lastRollOver[Y[i]] < epoch) {
                Utils.Point[2] memory pending;
                (pending[0].x, pending[0].y) = _base.pending(Y[i], 0);
                (pending[1].x, pending[1].y) = _base.pending(Y[i], 1);
                acc[0] = acc[0].add(pending[0]);
                acc[1] = acc[1].add(pending[1]);
            }
            result[i][0] = Utils.compress(acc[0]);
            result[i][1] = Utils.compress(acc[1]);
        }
    }

    function register(bytes32 Y, bytes32[2] calldata signature) external payable {
        require(msg.value == 1e16, "Amount must be 0.010 ETH.");

        uint64 epoch = uint64(block.timestamp / EPOCH_LENGTH);

        uint32 credit = uint32(msg.value / 1e15); // == 10.
        (bool success,) = payable(_base).call{value: msg.value}(""); // forward $ to base
        require(success, "Forwarding funds to base failed.");
        require(address(_base).balance <= 1e15 * 0xFFFFFFFF, "Escrow pool now too large.");
        Utils.Point[2] memory pending;
        (pending[0].x, pending[0].y) = _base.pending(Y, 0);
        (pending[1].x, pending[1].y) = _base.pending(Y, 1);
        pending[0] = pending[0].add(g().mul(credit)); // convert to uint256?
        _base.setPending(Y, pending);

        Utils.Point memory pub = Utils.decompress(Y);
        Utils.Point memory K = g().mul(uint256(signature[1])).add(pub.mul(uint256(signature[0]).neg()));
        uint256 c = uint256(keccak256(abi.encode("Welcome to Firn.", address(this), Y, K))).mod();
        require(bytes32(c) == signature[0], "Signature failed to verify.");
        touch(Y, credit, epoch);

        emit RegisterOccurred(msg.sender, Y);
    }

    function deposit(bytes32[N] calldata Y, bytes32[N] calldata C, bytes32 D, bytes calldata proof) external payable {
        // not doing a minimum amount here... the idea is that this function can't be used to force your way into the tree.
        require(msg.value % 1e15 == 0, "Must be a multiple of 0.001 ETH.");
        uint64 epoch = uint64(block.timestamp / EPOCH_LENGTH);
        uint32 credit = uint32(msg.value / 1e15); // can't overflow, by the above.
        (bool success,) = payable(_base).call{value: msg.value}(""); // forward $ to base
        require(success, "Forwarding funds to base failed.");
        require(address(_base).balance <= 1e15 * 0xFFFFFFFF, "Escrow pool now too large.");

        Utils.Statement memory statement;
        statement.D = Utils.decompress(D);
        for (uint256 i = 0; i < N; i++) {
            rollOver(Y[i], epoch);

            statement.Y[i] = Utils.decompress(Y[i]);
            statement.C[i] = Utils.decompress(C[i]);
            // mutate their pending, in advance of success.
            Utils.Point[2] memory pending;
            (pending[0].x, pending[0].y) = _base.pending(Y[i], 0);
            (pending[1].x, pending[1].y) = _base.pending(Y[i], 1);
            pending[0] = pending[0].add(statement.C[i]);
            pending[1] = pending[1].add(statement.D);
            _base.setPending(Y[i], pending);
            FirnBase.Info memory info;
            (info.epoch,,) = _base.info(Y[i]);
            require(info.epoch > 0, "Only cached accounts allowed.");
            touch(Y[i], credit, epoch); // weird question whether this should be 0 or credit... revisit.
        }

        _deposit.verify(credit, statement, Utils.deserializeDeposit(proof));

        emit DepositOccurred(Y, C, D, msg.sender, credit);
    }

    function transfer(bytes32[N] calldata Y, bytes32[N] calldata C, bytes32 D, bytes32 u, uint64 epoch, uint32 tip, bytes calldata proof) external {
        require(epoch == block.timestamp / EPOCH_LENGTH, "Wrong epoch."); // conversion of RHS to uint64 is unnecessary / redundant

        if (_lastGlobalUpdate < epoch) {
            _lastGlobalUpdate = epoch;
            delete _nonces;
        }
        for (uint256 i = 0; i < _nonces.length; i++) {
            require(_nonces[i] != u, "Nonce already seen.");
        }
        _nonces.push(u);

        Utils.Statement memory statement;
        statement.D = Utils.decompress(D);
        for (uint256 i = 0; i < N; i++) {
            rollOver(Y[i], epoch);

            statement.Y[i] = Utils.decompress(Y[i]);
            statement.C[i] = Utils.decompress(C[i]);
            Utils.Point[2] memory acc;
            (acc[0].x, acc[0].y) = _base.acc(Y[i], 0);
            (acc[1].x, acc[1].y) = _base.acc(Y[i], 1);
            statement.CLn[i] = acc[0].add(statement.C[i]);
            statement.CRn[i] = acc[1].add(statement.D);
            // mutate their pending, in advance of success.
            Utils.Point[2] memory pending;
            (pending[0].x, pending[0].y) = _base.pending(Y[i], 0);
            (pending[1].x, pending[1].y) = _base.pending(Y[i], 1);
            pending[0] = pending[0].add(statement.C[i]);
            pending[1] = pending[1].add(statement.D);
            _base.setPending(Y[i], pending);
            FirnBase.Info memory info;
            (info.epoch,,) = _base.info(Y[i]);
            require(info.epoch > 0, "Only cached accounts allowed.");
            touch(Y[i], 0, epoch);
        }
        statement.epoch = epoch;
        statement.u = Utils.decompress(u);
        statement.fee = tip;

        _transfer.verify(statement, Utils.deserializeTransfer(proof));

        _base.pay(msg.sender, uint256(tip) * 1e15, ""); // use all gas here... no reason not to

        emit TransferOccurred(Y, C, D);
    }

    function withdraw(bytes32[N] calldata Y, bytes32[N] calldata C, bytes32 D, bytes32 u, uint64 epoch, uint32 amount, uint32 tip, bytes calldata proof, address destination, bytes calldata data) external {
        require(epoch == block.timestamp / EPOCH_LENGTH, "Wrong epoch."); // conversion of RHS to uint64 is unnecessary. // could supply epoch ourselves; check early to save gas

        if (_lastGlobalUpdate < epoch) {
            _lastGlobalUpdate = epoch;
            delete _nonces;
        }
        for (uint256 i = 0; i < _nonces.length; i++) {
            require(_nonces[i] != u, "Nonce already seen.");
        }
        _nonces.push(u);

        emit WithdrawalOccurred(Y, C, D, amount, destination, data); // emit here, because of stacktoodeep.

        Utils.Statement memory statement;
        statement.D = Utils.decompress(D);
        for (uint256 i = 0; i < N; i++) {
            bytes32 Y_i = Y[i]; // necessary for stacktoodeep
            rollOver(Y_i, epoch);

            statement.Y[i] = Utils.decompress(Y_i);
            statement.C[i] = Utils.decompress(C[i]);
            Utils.Point[2] memory acc;
            (acc[0].x, acc[0].y) = _base.acc(Y_i, 0);
            (acc[1].x, acc[1].y) = _base.acc(Y_i, 1);
            statement.CLn[i] = acc[0].add(statement.C[i]);
            statement.CRn[i] = acc[1].add(statement.D);
            // mutate their pending, in advance of success.
            Utils.Point[2] memory pending;
            (pending[0].x, pending[0].y) = _base.pending(Y_i, 0);
            (pending[1].x, pending[1].y) = _base.pending(Y_i, 1);
            pending[0] = pending[0].add(statement.C[i]);
            pending[1] = pending[1].add(statement.D);
            _base.setPending(Y_i, pending);
            FirnBase.Info memory info;
            (info.epoch,,) = _base.info(Y_i);
            require(info.epoch > 0, "Only cached accounts allowed.");
        }
        uint32 burn = amount / _fee;
        statement.epoch = epoch; // implicit conversion to uint256
        statement.u = Utils.decompress(u);
        statement.fee = tip + burn; // implicit conversion to uint256

        uint256 salt = uint256(keccak256(abi.encode(destination, data))); // .mod();
        _withdrawal.verify(amount, statement, Utils.deserializeWithdrawal(proof), salt);

        _base.pay{gas: 10000}(msg.sender, uint256(tip) * 1e15, ""); // payable(msg.sender).transfer(uint256(tip) * 1e15);
        _base.pay(_treasury, uint256(burn) * 1e15, ""); // (bool success,) = payable(_treasury).call{value: uint256(burn) * 1e15}("");
        _base.pay(destination, uint256(amount) * 1e15, data);
    }
}

// File: InnerProductVerifier.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./Utils.sol";

contract InnerProductVerifier {
    using Utils for uint256;
    using Utils for Utils.Point;

    bytes32 public immutable gX;
    bytes32 public immutable gY;
    bytes32 public immutable hX;
    bytes32 public immutable hY;
    // above, emulating immutable `Utils.Point`s using raw `bytes32`s. save some sloads later.
    Utils.Point[M << 1] public gs;
    Utils.Point[M << 1] public hs;
    // have to use storage, not immutable, because solidity doesn't support non-primitive immutable types

    constructor() {
        Utils.Point memory gTemp = Utils.mapInto("g");
        gX = gTemp.x;
        gY = gTemp.y;
        Utils.Point memory hTemp = Utils.mapInto("h");
        hX = hTemp.x;
        hY = hTemp.y;
        for (uint256 i = 0; i < M << 1; i++) {
            gs[i] = Utils.mapInto("g", i);
            hs[i] = Utils.mapInto("h", i);
        }
    }

    struct Locals {
        uint256 o;
        Utils.Point P;
        uint256[m + 1] challenges;
        uint256[M << 1] s;
    }

    function verify(Utils.InnerProductStatement calldata statement, Utils.InnerProductProof calldata proof, bool transfer) external view {
        Locals memory locals;
        locals.o = statement.salt;
        locals.P = statement.P;
        uint256 M_ = M << (transfer ? 1 : 0);
        uint256 m_ = m + (transfer ? 1 : 0);

        for (uint256 i = 0; i < m_; i++) {
            locals.o = uint256(keccak256(abi.encode(locals.o, proof.L[i], proof.R[i]))).mod(); // overwrites
            locals.challenges[i] = locals.o;
            uint256 inverse = locals.o.inv();
            locals.P = locals.P.add(proof.L[i].mul(locals.o.mul(locals.o))).add(proof.R[i].mul(inverse.mul(inverse)));
        }

        locals.s[0] = 1;
        for (uint256 i = 0; i < m_; i++) locals.s[0] = locals.s[0].mul(locals.challenges[i]);
        locals.s[0] = locals.s[0].inv();
        for (uint256 i = 0; i < m_; i++) {
            for (uint256 j = 0; j < M_; j += 1 << m_ - i) {
                locals.s[j + (1 << m_ - i - 1)] = locals.s[j].mul(locals.challenges[i]).mul(locals.challenges[i]);
            }
        }

        Utils.Point memory temp = statement.u.mul(proof.a.mul(proof.b));
        for (uint256 i = 0; i < M_; i++) {
            temp = temp.add(gs[i].mul(locals.s[i].mul(proof.a)));
            temp = temp.add(statement.hs[i].mul(locals.s[M_ - 1 - i].mul(proof.b)));
        }
        require(temp.eq(locals.P), "Inner product proof failed.");
    }
}
// File: TransferVerifier.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./InnerProductVerifier.sol";
import "./Utils.sol";

contract TransferVerifier {
    using Utils for uint256;
    using Utils for Utils.Point;

    InnerProductVerifier immutable _ip;

    bytes32 immutable _gSumX; // 0x2fa4d012d8b2496ef27316c1447cd8958b034225a0fad7f9e9b944b7de8c5064 when Utils.m == 5
    bytes32 immutable _gSumY; // 0x0c648fe5b6fbbda8eec3d8ce13a891b005f4228f90638e84041b46a17bff0aae

    constructor(address ip_) {
        _ip = InnerProductVerifier(ip_);
        Utils.Point memory gSumTemp;
        for (uint256 i = 0; i < M << 1; i++) {
            gSumTemp = gSumTemp.add(gs(i));
        }
        _gSumX = gSumTemp.x;
        _gSumY = gSumTemp.y;
    }

    function g() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.gX(), _ip.gY());
    }

    function h() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.hX(), _ip.hY());
    }

    function gs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.gs(i);
        return Utils.Point(x, y);
    }

    function hs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.hs(i);
        return Utils.Point(x, y);
    }

    function gSum() private view returns (Utils.Point memory) {
        return Utils.Point(_gSumX, _gSumY);
    }

    struct Locals {
        uint256 v;
        uint256 w;
        uint256 vPow;
        uint256 wPow;
        uint256[n][2][2] f;
        uint256[N][2] r; // each poly is an array of length N. evaluations of prods
        Utils.Point temp;
        Utils.Point CLnR;
        Utils.Point CRnR;
        Utils.Point CR;
        Utils.Point DR;
        Utils.Point yR;
        Utils.Point gR;
        Utils.Point C_XR;
        Utils.Point y_XR;

        uint256 y;
        uint256[M << 1] ys;
        uint256 z;
        uint256[2] zs; // [z^2, z^3]
        uint256[M << 1] twoTimesZSquared;
        uint256 zSum;
        uint256 x;
        uint256 t;
        uint256 k;
        Utils.Point tEval;

        uint256 c;
        Utils.Point A_y;
        Utils.Point A_D;
        Utils.Point A_b;
        Utils.Point A_X;
        Utils.Point A_t;
        Utils.Point gEpoch;
        Utils.Point A_u;
    }

    function verify(Utils.Statement calldata statement, Utils.TransferProof calldata proof) external view {
        Locals memory locals;
        locals.v = uint256(keccak256(abi.encode(statement.Y, statement.CLn, statement.CRn, statement.C, statement.D, statement.epoch, statement.fee, proof.BA, proof.BS, proof.A, proof.B))).mod();
        locals.w = uint256(keccak256(abi.encode(locals.v, proof.CLnG, proof.CRnG, proof.C_0G, proof.DG, proof.y_0G, proof.gG, proof.C_XG, proof.y_XG))).mod();
        for (uint256 row = 0; row < 2; row++) {
            for (uint256 k = 0; k < n; k++) {
                locals.f[row][1][k] = proof.f[row][k];
                locals.f[row][0][k] = locals.w.sub(proof.f[row][k]);
                locals.temp = locals.temp.add(gs(k + n * row).mul(locals.f[row][1][k]));
                locals.temp = locals.temp.add(hs(k + n * row).mul(locals.f[row][1][k].mul(locals.f[row][0][k])));
            }
        }

        require(proof.B.mul(locals.w).add(proof.A).eq(locals.temp.add(h().mul(proof.z_A))), "Bit-proof verification failed.");

        locals.r[0] = Utils.assemblePolynomials(locals.f[0]);
        locals.r[1] = Utils.assemblePolynomials(locals.f[1]);
        locals.wPow = 1;
        for (uint256 k = 0; k < n; k++) {
            uint256 wNeg = locals.wPow.neg();
            locals.CLnR = locals.CLnR.add(proof.CLnG[k].mul(wNeg));
            locals.CRnR = locals.CRnR.add(proof.CRnG[k].mul(wNeg));
            locals.CR = locals.CR.add(proof.C_0G[k].mul(wNeg));
            locals.DR = locals.DR.add(proof.DG[k].mul(wNeg));
            locals.yR = locals.yR.add(proof.y_0G[k].mul(wNeg));
            locals.gR = locals.gR.add(proof.gG[k].mul(wNeg));
            locals.C_XR = locals.C_XR.add(proof.C_XG[k].mul(wNeg));
            locals.y_XR = locals.y_XR.add(proof.y_XG[k].mul(wNeg));

            locals.wPow = locals.wPow.mul(locals.w);
        }
        locals.vPow = locals.v;
        for (uint256 i = 0; i < N; i++) {
            locals.CLnR = locals.CLnR.add(statement.CLn[i].mul(locals.r[0][i]));
            locals.CRnR = locals.CRnR.add(statement.CRn[i].mul(locals.r[0][i]));
            locals.CR = locals.CR.add(statement.C[i].mul(locals.r[0][i]));
            locals.yR = locals.yR.add(statement.Y[i].mul(locals.r[0][i]));
            uint256 multiplier = locals.r[0][i].add(locals.r[1][i]);
            multiplier = multiplier.add(locals.vPow.mul(locals.wPow.sub(multiplier)));
            locals.C_XR = locals.C_XR.add(statement.C[i].mul(multiplier));
            locals.y_XR = locals.y_XR.add(statement.Y[i].mul(multiplier));

            locals.vPow = locals.vPow.mul(locals.v); // used to do this only if (i > 0)
        }
        locals.DR = locals.DR.add(statement.D.mul(locals.wPow));
        locals.gR = locals.gR.add(g().mul(locals.wPow));
        locals.C_XR = locals.C_XR.add(g().mul(statement.fee.mul(locals.wPow))); // this line is new

        locals.y = uint256(keccak256(abi.encode(locals.w))).mod();
        locals.ys[0] = 1;
        locals.k = 1;
        for (uint256 i = 1; i < M << 1; i++) {
            locals.ys[i] = locals.ys[i - 1].mul(locals.y);
            locals.k = locals.k.add(locals.ys[i]);
        }
        locals.z = uint256(keccak256(abi.encode(locals.y))).mod();
        locals.zs[0] = locals.z.mul(locals.z);
        locals.zs[1] = locals.zs[0].mul(locals.z);
        locals.zSum = locals.zs[0].add(locals.zs[1]).mul(locals.z);
        locals.k = locals.k.mul(locals.z.sub(locals.zs[0])).sub(locals.zSum.mul(1 << M).sub(locals.zSum));
        locals.t = proof.tHat.sub(locals.k); // t = tHat - delta(y, z)
        for (uint256 i = 0; i < M; i++) {
            locals.twoTimesZSquared[i] = locals.zs[0].mul(1 << i);
            locals.twoTimesZSquared[i + M] = locals.zs[1].mul(1 << i);
        }

        locals.x = uint256(keccak256(abi.encode(locals.z, proof.T_1, proof.T_2))).mod();
        locals.tEval = proof.T_1.mul(locals.x).add(proof.T_2.mul(locals.x.mul(locals.x))); // replace with "commit"?

        locals.A_y = locals.gR.mul(proof.s_sk).add(locals.yR.mul(proof.c.neg()));
        locals.A_D = g().mul(proof.s_r).add(statement.D.mul(proof.c.neg())); // add(mul(locals.gR, proof.s_r), mul(locals.DR, proof.c.neg()));
        locals.A_b = g().mul(proof.s_b).add(locals.DR.mul(locals.zs[0].neg()).add(locals.CRnR.mul(locals.zs[1])).mul(proof.s_sk).add(locals.CR.add(g().mul(statement.fee.mul(locals.wPow))).mul(locals.zs[0].neg()).add(locals.CLnR.mul(locals.zs[1])).mul(proof.c.neg())));
        locals.A_X = locals.y_XR.mul(proof.s_r).add(locals.C_XR.mul(proof.c.neg()));
        locals.A_t = g().mul(locals.t).add(locals.tEval.neg()).mul(proof.c.mul(locals.wPow)).add(h().mul(proof.s_tau)).add(g().mul(proof.s_b.neg()));
        locals.gEpoch = Utils.mapInto("Firn Epoch", statement.epoch); // TODO: cast my own address to string as well?
        locals.A_u = locals.gEpoch.mul(proof.s_sk).add(statement.u.mul(proof.c.neg()));

        locals.c = uint256(keccak256(abi.encode(locals.x, locals.A_y, locals.A_D, locals.A_b, locals.A_X, locals.A_t, locals.A_u))).mod();
        require(locals.c == proof.c, "Sigma protocol failure.");

        Utils.InnerProductStatement memory ip; // statement
        ip.salt = uint256(keccak256(abi.encode(locals.c))).mod();
        ip.u = h().mul(ip.salt);
        ip.P = proof.BA.add(proof.BS.mul(locals.x)).add(gSum().mul(locals.z.neg())).add(h().mul(proof.mu.neg())).add(ip.u.mul(proof.tHat));
        for (uint256 i = 0; i < M << 1; i++) {
            ip.hs[i] = hs(i).mul(locals.ys[i].inv());
            ip.P = ip.P.add(ip.hs[i].mul(locals.ys[i].mul(locals.z).add(locals.twoTimesZSquared[i])));
        }

        _ip.verify(ip, proof.ip, true);
    }
}
// File: Utils.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

uint256 constant n = 4;
uint256 constant N = 1 << n;
uint256 constant m = 5;
uint256 constant M = 1 << m;

library Utils {
    uint256 constant GROUP_ORDER = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;
    uint256 constant FIELD_ORDER = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47;
    uint256 constant PPLUS1DIV4 = 0x0c19139cb84c680a6e14116da060561765e05aa45a1c72a34f082305b61f3f52;

    function add(uint256 x, uint256 y) internal pure returns (uint256) {
        return addmod(x, y, GROUP_ORDER);
    }

    function mul(uint256 x, uint256 y) internal pure returns (uint256) {
        return mulmod(x, y, GROUP_ORDER);
    }

    function inv(uint256 x) internal view returns (uint256) {
        return exp(x, GROUP_ORDER - 2);
    }

    function mod(uint256 x) internal pure returns (uint256) {
        return x % GROUP_ORDER;
    }

    function sub(uint256 x, uint256 y) internal pure returns (uint256) {
        return x >= y ? x - y : GROUP_ORDER - y + x;
    }

    function neg(uint256 x) internal pure returns (uint256) {
        return GROUP_ORDER - x;
    }

    function exp(uint256 base, uint256 exponent) internal view returns (uint256 output) {
        uint256 order = GROUP_ORDER;
        assembly {
            let location := mload(0x40)
            mstore(location, 0x20)
            mstore(add(location, 0x20), 0x20)
            mstore(add(location, 0x40), 0x20)
            mstore(add(location, 0x60), base)
            mstore(add(location, 0x80), exponent)
            mstore(add(location, 0xa0), order)
            if iszero(staticcall(gas(), 0x05, location, 0xc0, location, 0x20)) {
                revert(0, 0)
            }
            output := mload(location)
        }
    }

    function fieldExp(uint256 base, uint256 exponent) internal view returns (uint256 output) { // warning: mod p, not q
        uint256 order = FIELD_ORDER;
        assembly {
            let location := mload(0x40)
            mstore(location, 0x20)
            mstore(add(location, 0x20), 0x20)
            mstore(add(location, 0x40), 0x20)
            mstore(add(location, 0x60), base)
            mstore(add(location, 0x80), exponent)
            mstore(add(location, 0xa0), order)
            if iszero(staticcall(gas(), 0x05, location, 0xc0, location, 0x20)) {
                revert(0, 0)
            }
            output := mload(location)
        }
    }

    struct Point {
        bytes32 x;
        bytes32 y;
    }

    function add(Point memory p1, Point memory p2) internal view returns (Point memory r) {
        assembly {
            let location := mload(0x40)
            mstore(location, mload(p1))
            mstore(add(location, 0x20), mload(add(p1, 0x20)))
            mstore(add(location, 0x40), mload(p2))
            mstore(add(location, 0x60), mload(add(p2, 0x20)))
            if iszero(staticcall(gas(), 0x06, location, 0x80, r, 0x40)) {
                revert(0, 0)
            }
        }
    }

    function mul(Point memory p, uint256 s) internal view returns (Point memory r) {
        assembly {
            let location := mload(0x40)
            mstore(location, mload(p))
            mstore(add(location, 0x20), mload(add(p, 0x20)))
            mstore(add(location, 0x40), s)
            if iszero(staticcall(gas(), 0x07, location, 0x60, r, 0x40)) {
                revert(0, 0)
            }
        }
    }

    function neg(Point memory p) internal pure returns (Point memory) {
        return Point(p.x, bytes32(FIELD_ORDER - uint256(p.y))); // p.y should already be reduced mod P?
    }

    function eq(Point memory p1, Point memory p2) internal pure returns (bool) {
        return p1.x == p2.x && p1.y == p2.y;
    }

    function decompress(bytes32 input) internal view returns (Point memory) {
        if (input == 0x00) return Point(0x00, 0x00);
        uint256 x = uint256(input);
        uint256 sign = (x & 0x8000000000000000000000000000000000000000000000000000000000000000) >> 255;
        x &= 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF;
        uint256 ySquared = fieldExp(x, 3) + 3;
        uint256 y = fieldExp(ySquared, PPLUS1DIV4);
        Point memory result = Point(bytes32(x), bytes32(y));
        if (sign != y & 0x01) return neg(result);
        return result;
    }

    function compress(Point memory input) internal pure returns (bytes32) {
        uint256 result = uint256(input.x);
        if (uint256(input.y) & 0x01 == 0x01) result |= 0x8000000000000000000000000000000000000000000000000000000000000000;
        return bytes32(result);
    }

    function mapInto(uint256 seed) internal view returns (Point memory) {
        uint256 y;
        while (true) {
            uint256 ySquared = fieldExp(seed, 3) + 3; // addmod instead of add: waste of gas, plus function overhead cost
            y = fieldExp(ySquared, PPLUS1DIV4);
            if (fieldExp(y, 2) == ySquared) {
                break;
            }
            seed += 1;
        }
        return Point(bytes32(seed), bytes32(y));
    }

    function mapInto(string memory input) internal view returns (Point memory) {
        return mapInto(uint256(keccak256(abi.encodePacked(input))) % FIELD_ORDER);
    }

    function mapInto(string memory input, uint256 i) internal view returns (Point memory) {
        return mapInto(uint256(keccak256(abi.encodePacked(input, i))) % FIELD_ORDER);
    }

    function slice(bytes memory input, uint256 start) internal pure returns (bytes32 result) {
        assembly {
            result := mload(add(add(input, 0x20), start))
        }
    }

    struct Statement {
        Point[N] Y;
        Point[N] CLn;
        Point[N] CRn;
        Point[N] C;
        Point D;
        uint256 epoch;
        Point u;
        uint256 fee;
    }

    struct DepositProof {
        Point A;
        Point B;

        Point[n] C_XG;
        Point[n] y_XG;

        uint256[n] f;
        uint256 z_A;

        uint256 c;
        uint256 s_r;
    }

    function deserializeDeposit(bytes memory arr) internal view returns (DepositProof memory proof) {
        proof.A = decompress(slice(arr, 0));
        proof.B = decompress(slice(arr, 32));

        for (uint256 k = 0; k < n; k++) {
            proof.C_XG[k] = decompress(slice(arr, 64 + k * 32));
            proof.y_XG[k] = decompress(slice(arr, 64 + (k + n) * 32));
            proof.f[k] = uint256(slice(arr, 64 + n * 64 + k * 32));
        }
        uint256 starting = n * 96;
        proof.z_A = uint256(slice(arr, 64 + starting));

        proof.c = uint256(slice(arr, 96 + starting));
        proof.s_r = uint256(slice(arr, 128 + starting));

        return proof;
    }

    struct TransferProof {
        Point BA;
        Point BS;
        Point A;
        Point B;

        Point[n] CLnG;
        Point[n] CRnG;
        Point[n] C_0G;
        Point[n] DG;
        Point[n] y_0G;
        Point[n] gG;
        Point[n] C_XG;
        Point[n] y_XG;

        uint256[n][2] f;
        uint256 z_A;

        Point T_1;
        Point T_2;
        uint256 tHat;
        uint256 mu;

        uint256 c;
        uint256 s_sk;
        uint256 s_r;
        uint256 s_b;
        uint256 s_tau;

        InnerProductProof ip;
    }

    function deserializeTransfer(bytes memory arr) internal view returns (TransferProof memory proof) {
        proof.BA = decompress(slice(arr, 0));
        proof.BS = decompress(slice(arr, 32));
        proof.A = decompress(slice(arr, 64));
        proof.B = decompress(slice(arr, 96));

        for (uint256 k = 0; k < n; k++) {
            proof.CLnG[k] = decompress(slice(arr, 128 + k * 32));
            proof.CRnG[k] = decompress(slice(arr, 128 + (k + n) * 32));
            proof.C_0G[k] = decompress(slice(arr, 128 + n * 64 + k * 32));
            proof.DG[k] = decompress(slice(arr, 128 + n * 96 + k * 32));
            proof.y_0G[k] = decompress(slice(arr, 128 + n * 128 + k * 32));
            proof.gG[k] = decompress(slice(arr, 128 + n * 160 + k * 32));
            proof.C_XG[k] = decompress(slice(arr, 128 + n * 192 + k * 32));
            proof.y_XG[k] = decompress(slice(arr, 128 + n * 224 + k * 32));
            proof.f[0][k] = uint256(slice(arr, 128 + n * 256 + k * 32));
            proof.f[1][k] = uint256(slice(arr, 128 + n * 288 + k * 32));
        }

        uint256 starting = n * 320;
        proof.z_A = uint256(slice(arr, 128 + starting));

        proof.T_1 = decompress(slice(arr, 160 + starting));
        proof.T_2 = decompress(slice(arr, 192 + starting));
        proof.tHat = uint256(slice(arr, 224 + starting));
        proof.mu = uint256(slice(arr, 256 + starting));

        proof.c = uint256(slice(arr, 288 + starting));
        proof.s_sk = uint256(slice(arr, 320 + starting));
        proof.s_r = uint256(slice(arr, 352 + starting));
        proof.s_b = uint256(slice(arr, 384 + starting));
        proof.s_tau = uint256(slice(arr, 416 + starting));

        for (uint256 i = 0; i < m + 1; i++) {
            proof.ip.L[i] = decompress(slice(arr, 448 + starting + i * 32));
            proof.ip.R[i] = decompress(slice(arr, 448 + starting + (i + m + 1) * 32));
        }
        proof.ip.a = uint256(slice(arr, 448 + starting + (m + 1) * 64));
        proof.ip.b = uint256(slice(arr, 480 + starting + (m + 1) * 64));

        return proof;
    }

    struct WithdrawalProof {
        Point BA;
        Point BS;
        Point A;
        Point B;

        Point[n] CLnG;
        Point[n] CRnG;
        Point[n] y_0G;
        Point[n] gG;
        Point[n] C_XG;
        Point[n] y_XG;

        uint256[n] f;
        uint256 z_A;

        Point T_1;
        Point T_2;
        uint256 tHat;
        uint256 mu;

        uint256 c;
        uint256 s_sk;
        uint256 s_r;
        uint256 s_b;
        uint256 s_tau;

        InnerProductProof ip;
    }

    function deserializeWithdrawal(bytes memory arr) internal view returns (WithdrawalProof memory proof) {
        proof.BA = decompress(slice(arr, 0));
        proof.BS = decompress(slice(arr, 32));
        proof.A = decompress(slice(arr, 64));
        proof.B = decompress(slice(arr, 96));

        for (uint256 k = 0; k < n; k++) {
            proof.CLnG[k] = decompress(slice(arr, 128 + k * 32));
            proof.CRnG[k] = decompress(slice(arr, 128 + (k + n) * 32));
            proof.y_0G[k] = decompress(slice(arr, 128 + n * 64 + k * 32));
            proof.gG[k] = decompress(slice(arr, 128 + n * 96 + k * 32));
            proof.C_XG[k] = decompress(slice(arr, 128 + n * 128 + k * 32));
            proof.y_XG[k] = decompress(slice(arr, 128 + n * 160 + k * 32));
            proof.f[k] = uint256(slice(arr, 128 + n * 192 + k * 32));
        }
        uint256 starting = n * 224;
        proof.z_A = uint256(slice(arr, 128 + starting));

        proof.T_1 = decompress(slice(arr, 160 + starting));
        proof.T_2 = decompress(slice(arr, 192 + starting));
        proof.tHat = uint256(slice(arr, 224 + starting));
        proof.mu = uint256(slice(arr, 256 + starting));

        proof.c = uint256(slice(arr, 288 + starting));
        proof.s_sk = uint256(slice(arr, 320 + starting));
        proof.s_r = uint256(slice(arr, 352 + starting));
        proof.s_b = uint256(slice(arr, 384 + starting));
        proof.s_tau = uint256(slice(arr, 416 + starting));

        for (uint256 i = 0; i < m; i++) { // will leave the `m`th element empty
            proof.ip.L[i] = decompress(slice(arr, 448 + starting + i * 32));
            proof.ip.R[i] = decompress(slice(arr, 448 + starting + (i + m) * 32));
        }
        proof.ip.a = uint256(slice(arr, 448 + starting + m * 64));
        proof.ip.b = uint256(slice(arr, 480 + starting + m * 64));

        return proof;
    }

    struct InnerProductStatement {
        uint256 salt;
        Point[M << 1] hs; // "overridden" parameters.
        Point u;
        Point P;
    }

    struct InnerProductProof {
        Point[m + 1] L;
        Point[m + 1] R;
        uint256 a;
        uint256 b;
    }

    function assemblePolynomials(uint256[n][2] memory f) internal pure returns (uint256[N] memory result) {
        // f is a 2m-by-2 array... containing the f's and x - f's, twice (i.e., concatenated).
        // output contains two "rows", each of length N.
        result[0] = 1;
        for (uint256 k = 0; k < n; k++) {
            for (uint256 i = 0; i < N; i += 1 << n - k) {
                result[i + (1 << n - 1 - k)] = mul(result[i], f[1][n - 1 - k]);
                result[i] = mul(result[i], f[0][n - 1 - k]);
            }
        }
    }
}
// File: WithdrawalVerifier.sol



// SPDX-License-Identifier: Apache-2.0

pragma solidity 0.8.17;

import "./InnerProductVerifier.sol";
import "./Utils.sol";

contract WithdrawalVerifier {
    using Utils for uint256;
    using Utils for Utils.Point;

    InnerProductVerifier immutable _ip;

    bytes32 immutable _gSumX; // 0x1bcf9024624aef47656cdbd47d104a1b30efac20504e72d395e7e012727c73a3 when Utils.m == 5
    bytes32 immutable _gSumY; // 0x052d5b8798a0be8c27d47246f021c2e9841837904a92a33dc4f6c755fda097bd

    constructor(address ip_) {
        _ip = InnerProductVerifier(ip_);
        Utils.Point memory gSumTemp;
        for (uint256 i = 0; i < M; i++) {
            gSumTemp = gSumTemp.add(gs(i));
        }
        _gSumX = gSumTemp.x;
        _gSumY = gSumTemp.y;
    }

    function g() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.gX(), _ip.gY());
    }

    function h() internal view returns (Utils.Point memory) {
        return Utils.Point(_ip.hX(), _ip.hY());
    }

    function gs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.gs(i);
        return Utils.Point(x, y);
    }

    function hs(uint256 i) internal view returns (Utils.Point memory) {
        (bytes32 x, bytes32 y) = _ip.hs(i);
        return Utils.Point(x, y);
    }

    function gSum() private view returns (Utils.Point memory) {
        return Utils.Point(_gSumX, _gSumY);
    }

    struct Locals {
        uint256 v;
        uint256 w;
        uint256 vPow;
        uint256 wPow;
        uint256[n][2] f; // could just allocate extra space in the proof?
        uint256[N] r; // each poly is an array of length N. evaluations of prods
        Utils.Point temp;
        Utils.Point CLnR;
        Utils.Point CRnR;
        Utils.Point yR;
        Utils.Point gR;
        Utils.Point C_XR;
        Utils.Point y_XR;

        uint256 y;
        uint256[M] ys;
        uint256 z;
        uint256[1] zs; // silly. just to match zether.
        uint256[M] twoTimesZSquared;
        uint256 zSum;
        uint256 x;
        uint256 t;
        uint256 k;
        Utils.Point tEval;

        uint256 c;
        Utils.Point A_y;
        Utils.Point A_D;
        Utils.Point A_b;
        Utils.Point A_X;
        Utils.Point A_t;
        Utils.Point gEpoch;
        Utils.Point A_u;
    }

    function verify(uint256 amount, Utils.Statement calldata statement, Utils.WithdrawalProof calldata proof, uint256 salt) external view {
        Locals memory locals;
        locals.v = uint256(keccak256(abi.encode(salt, amount, statement.Y, statement.CLn, statement.CRn, statement.C, statement.D, statement.epoch, statement.fee, proof.BA, proof.BS, proof.A, proof.B))).mod();
        locals.w = uint256(keccak256(abi.encode(locals.v, proof.CLnG, proof.CRnG, proof.y_0G, proof.gG, proof.C_XG, proof.y_XG))).mod();
        for (uint256 k = 0; k < n; k++) {
            locals.f[1][k] = proof.f[k];
            locals.f[0][k] = locals.w.sub(proof.f[k]);
            locals.temp = locals.temp.add(gs(k).mul(locals.f[1][k]));
            locals.temp = locals.temp.add(hs(k).mul(locals.f[1][k].mul(locals.f[0][k])));
        }
        require(proof.B.mul(locals.w).add(proof.A).eq(locals.temp.add(h().mul(proof.z_A))), "Bit-proof verification failed.");

        locals.r = Utils.assemblePolynomials(locals.f);
        locals.wPow = 1;
        for (uint256 k = 0; k < n; k++) {
            locals.CLnR = locals.CLnR.add(proof.CLnG[k].mul(locals.wPow.neg()));
            locals.CRnR = locals.CRnR.add(proof.CRnG[k].mul(locals.wPow.neg()));
            locals.yR = locals.yR.add(proof.y_0G[k].mul(locals.wPow.neg()));
            locals.gR = locals.gR.add(proof.gG[k].mul(locals.wPow.neg()));
            locals.C_XR = locals.C_XR.add(proof.C_XG[k].mul(locals.wPow.neg()));
            locals.y_XR = locals.y_XR.add(proof.y_XG[k].mul(locals.wPow.neg()));

            locals.wPow = locals.wPow.mul(locals.w);
        }
        locals.vPow = locals.v; // used to be 1
        for (uint256 i = 0; i < N; i++) {
            locals.CLnR = locals.CLnR.add(statement.CLn[i].mul(locals.r[i]));
            locals.CRnR = locals.CRnR.add(statement.CRn[i].mul(locals.r[i]));
            locals.yR = locals.yR.add(statement.Y[i].mul(locals.r[i]));
            uint256 multiplier = locals.r[i].add(locals.vPow.mul(locals.wPow.sub(locals.r[i]))); // locals. ?
            locals.C_XR = locals.C_XR.add(statement.C[i].mul(multiplier));
            locals.y_XR = locals.y_XR.add(statement.Y[i].mul(multiplier));
            locals.vPow = locals.vPow.mul(locals.v); // used to do this only if (i > 0)
        }
        locals.gR = locals.gR.add(g().mul(locals.wPow));
        locals.C_XR = locals.C_XR.add(g().mul(statement.fee.add(amount).mul(locals.wPow))); // this line is new

        locals.y = uint256(keccak256(abi.encode(locals.w))).mod();
        locals.ys[0] = 1;
        locals.k = 1;
        for (uint256 i = 1; i < M; i++) {
            locals.ys[i] = locals.ys[i - 1].mul(locals.y);
            locals.k = locals.k.add(locals.ys[i]);
        }
        locals.z = uint256(keccak256(abi.encode(locals.y))).mod();
        locals.zs[0] = locals.z.mul(locals.z);
        locals.zSum = locals.zs[0].mul(locals.z); // trivial sum
        locals.k = locals.k.mul(locals.z.sub(locals.zs[0])).sub(locals.zSum.mul(1 << M).sub(locals.zSum));
        locals.t = proof.tHat.sub(locals.k);
        for (uint256 i = 0; i < M; i++) {
            locals.twoTimesZSquared[i] = locals.zs[0].mul(1 << i);
        }

        locals.x = uint256(keccak256(abi.encode(locals.z, proof.T_1, proof.T_2))).mod();
        locals.tEval = proof.T_1.mul(locals.x).add(proof.T_2.mul(locals.x.mul(locals.x))); // replace with "commit"?

        locals.A_y = locals.gR.mul(proof.s_sk).add(locals.yR.mul(proof.c.neg()));
        locals.A_D = g().mul(proof.s_r).add(statement.D.mul(proof.c.neg())); // add(mul(locals.gR, proof.s_r), mul(locals.DR, proof.c.neg()));
        locals.A_b = g().mul(proof.s_b).add(locals.CRnR.mul(locals.zs[0]).mul(proof.s_sk).add(locals.CLnR.mul(locals.zs[0]).mul(proof.c.neg())));
        locals.A_X = locals.y_XR.mul(proof.s_r).add(locals.C_XR.mul(proof.c.neg()));
        locals.A_t = g().mul(locals.t).add(locals.tEval.neg()).mul(proof.c.mul(locals.wPow)).add(h().mul(proof.s_tau)).add(g().mul(proof.s_b.neg()));
        locals.gEpoch = Utils.mapInto("Firn Epoch", statement.epoch); // TODO: cast my own address to string as well?
        locals.A_u = locals.gEpoch.mul(proof.s_sk).add(statement.u.mul(proof.c.neg()));

        locals.c = uint256(keccak256(abi.encode(locals.x, locals.A_y, locals.A_D, locals.A_b, locals.A_X, locals.A_t, locals.A_u))).mod();
        require(locals.c == proof.c, "Sigma protocol failure.");

        Utils.InnerProductStatement memory ip; // statement
        ip.salt = uint256(keccak256(abi.encode(locals.c))).mod();
        ip.u = h().mul(ip.salt);
        ip.P = proof.BA.add(proof.BS.mul(locals.x)).add(gSum().mul(locals.z.neg())).add(h().mul(proof.mu.neg())).add(ip.u.mul(proof.tHat));
        for (uint256 i = 0; i < M; i++) {
            ip.hs[i] = hs(i).mul(locals.ys[i].inv());
            ip.P = ip.P.add(ip.hs[i].mul(locals.ys[i].mul(locals.z).add(locals.twoTimesZSquared[i])));
        }

        _ip.verify(ip, proof.ip, false);
    }
}