Comparing gas consumption for parsing JSON and Amino messages

Relay.sol

//    Copyright (C) 2018 LikeCoin Foundation Limited
//
//    This file is part of LikeCoin Smart Contract.
//
//    LikeCoin Smart Contract is free software: you can redistribute it and/or modify
//    it under the terms of the GNU General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    LikeCoin Smart Contract is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU General Public License for more details.
//
//    You should have received a copy of the GNU General Public License
//    along with LikeCoin Smart Contract.  If not, see <http://www.gnu.org/licenses/>.

pragma solidity ^0.4.24;

contract ERC20Basic {
  function totalSupply() public view returns (uint256);
  function balanceOf(address who) public view returns (uint256);
  function transfer(address to, uint256 value) public returns (bool);
  event Transfer(address indexed from, address indexed to, uint256 value);
}

contract Relay {
    event BlockHash(bytes20 hash);
    event Height(uint height);
    event GasReport(uint id, uint value);
    event Debug(uint id, uint value);
    event DebugBytes(uint id, bytes value);
    
    ERC20Basic public token;
    mapping(address => uint8) public votingPowerIndex;
    uint32[] public votingPower; // Note that votingPower[0] must be 0
    uint256 public totalVotingPower;

    uint public latestBlockHeight;
    bytes20 public latestAppHash;

    mapping(address => mapping(uint64 => bool)) public consumedIds;

    // TODO: mechanism for changing votingPower (may need to record window of total change in votingPower?)
    // TODO: timestamp

    // Sample input:
    // voters: ["0xfd951076dC3b60e304E0059168Fd745e3eb84b6D"]
    // votingPowers: [1]
    // uint32 to prevent overflow
    constructor(address tokenAddr, address[] voters, uint32[] votingPowers) public {
        require(voters.length != 0);
        require(voters.length < 256);
        require(voters.length == votingPowers.length);
        token = ERC20Basic(tokenAddr);
        votingPower.push(0);
        for (uint8 i = 0; i < voters.length; i += 1) {
            votingPowerIndex[voters[i]] = i + 1;
            votingPower.push(votingPowers[i]);
            totalVotingPower += votingPowers[i];
        }
    }

    function verifyAppHash(bytes20 blockHash, bytes appHash, bytes20[] proof) internal pure {
        bytes20 keyHash = ripemd160(abi.encodePacked("App"));
        bytes20 valueHash = ripemd160(abi.encodePacked(byte(appHash.length), appHash));
        bytes20 node = ripemd160(abi.encodePacked(byte(20), keyHash, byte(20), valueHash));
        node = ripemd160(abi.encodePacked(byte(20), node, byte(20), proof[0]));
        node = ripemd160(abi.encodePacked(byte(20), node, byte(20), proof[1]));
        node = ripemd160(abi.encodePacked(byte(20), proof[2], byte(20), node));
        node = ripemd160(abi.encodePacked(byte(20), node, byte(20), proof[3]));
        require(node == blockHash);
    }

    function byteCmp(bytes b1, uint start1, bytes b2) internal pure returns (bool success) {
        uint len = b2.length;
        for (uint i = 0; i < len; i += 1) {
            if (b1[start1 + i] != b2[i]) {
                return false;
            }
        }
        return true;
    }

    function parseUint(bytes bs, uint i) internal pure returns (bool success, uint result) {
        result = 0;
        uint len = bs.length;
        while (i < len) {
            uint8 t = uint8(bs[i]);
            if (t < 0x30 || t > 0x39) { // 0x30 == '0', 0x39 == '9'
                if (t == 0x2c || t == 0x7d) { // ',' or '}'
                    return (true, result);
                }
                return (false, 0);
            }
            result = result * 10 + t - 0x30;
            i += 1;
        }
        return (false, 0);
    }

    function parseHash(bytes bs, uint start) internal pure returns (bool success, bytes20 hash) {
        // A hash field in JSON should have format '"0123456789ABCDEF"'.
        // Requirements:
        //  - the first byte must be a '"'
        //  - the last byte must be a '"'
        //  - the bytes in middle (hex bytes) must be [0-9A-F] (should not have lower case for vote bytes)
        //  - the number of hex bytes must be even number (since 2 hex digit represents 1 byte)
        //  - the length of hex digits must be 40 (votes use 160-bit hash = 40 digit hex)

        // 40 hex digits + 1 '"'
        uint end = start + 41;
        // start with '"', end with '"'
        if (bs.length <= end || bs[start] != 0x22 || bs[end] != 0x22) { // '"'
            return (false, hash);
        }
        uint160 hashUint = 0x0;
        uint i = start + 1;
        // the first byte as a bytes20 needs 19 bytes of zeros after it, 19 * 8 = 152
        uint hashShift = 152;
        while (i < end) {
            // first digit in a byte
            int t = int(bs[i]);
            if (t >= 0x30 && t <= 0x39) { // 0-9
                t -= 0x30;
            } else if (t >= 0x41 && t <= 0x46) { // A-F
                t -= 0x41;
                t += 10;
            } else {
                return (false, hash);
            }
            t *= 16;
            i += 1;
            // second digit in a byte
            int t2 = int(bs[i]);
            if (t2 >= 0x30 && t2 <= 0x39) { // 0-9
                t2 -= 0x30;
            } else if (t2 >= 0x41 && t2 <= 0x46) { // A-F
                t2 -= 0x41;
                t2 += 10;
            } else {
                return (false, hash);
            }
            hashUint |= uint160(t + t2) << hashShift;
            hashShift -= 8;
            i += 1;
        }
        return (true, bytes20(hashUint));
    }

    // TODO: check all indices to prevent overflow
    function parseVoteJson(string jsonStr, uint16 typeIndex, uint16 heightIndex, uint16 blockIndex) internal pure returns (uint height, bytes20 hash) {
        bytes memory TYPE           = '"type":2}';
        bytes memory PREFIX_BLOCKID = '"block_id":{"hash":';
        bytes memory PREFIX_HEIGHT  = '"height":';
        bytes memory json = bytes(jsonStr);
        uint len = json.length;
        require(uint(typeIndex) + TYPE.length <= len);
        require(uint(heightIndex) + PREFIX_BLOCKID.length < len);
        require(uint(blockIndex) + PREFIX_HEIGHT.length < len);
        require(byteCmp(json, typeIndex, TYPE));
        require(byteCmp(json, blockIndex, PREFIX_BLOCKID));
        require(byteCmp(json, heightIndex, PREFIX_HEIGHT));
        bool success;
        (success, hash) = parseHash(json, blockIndex + PREFIX_BLOCKID.length);
        require(success);
        (success, height) = parseUint(json, heightIndex + PREFIX_HEIGHT.length);
        require(success);
        return (height, hash);
    }
    

    function parseAminoVarint(bytes bs, uint start) internal pure returns (uint256 value, uint length) {
        value = 0;
        length = 1;
        uint i = start;
        while (bs[i] >= 0x80) {
            value <<= 7;
            value |= uint256(bs[i]) & 0x7F;
            i += 1;
            length += 1;
        }
        value |= uint256(bs[i]);
        return (value, length);
    }

    function parseAminoFieldAndTyp(bytes bs, uint start) internal pure returns (uint256 field, uint8 typ, uint length) {
        uint256 n;
        (n, length) = parseAminoVarint(bs, start);
        field = n >> 3;
        typ = uint8(n & 0x7);
        return (field, typ, length);
    }
    
    function nextFieldStartingIndex(bytes bs, uint contentStart, uint8 typ) internal pure returns (uint256) {
        if (typ == 0) { // Varint
            uint i = contentStart;
            while (bs[i] >= 0x80) {
                i += 1;
            }
            return i + 1;
        } else if (typ == 1) { // 8Byte
            return contentStart + 8;
        } else if (typ == 2) { // ByteLength
            uint256 contentLength;
            uint varintLength;
            (contentLength, varintLength) = parseAminoVarint(bs, contentStart);
            return contentStart + varintLength + contentLength;
        } else if (typ == 5) { // 4Byte
            return contentStart + 4;
        } else {
            revert();
        }
    }

    function extractBytes20(bytes bs, uint index) internal pure returns (bytes20) {
        bytes20 r;
        assembly {
            r := mload(add(bs, add(index, 32)))
        }
        return r;
    }

    function parseVoteAmino(bytes bs) internal pure returns (uint height, bytes20 hash) {
        uint i = 0;
        uint256 voteType = 0;
        height = 0;
        uint hashIndex = 0;
        while (i < bs.length) {
            uint256 field;
            uint8 typ;
            uint keyLength;
            uint valueLength;
            (field, typ, keyLength) = parseAminoFieldAndTyp(bs, i);
            if (field == 3) { // Height
                if (typ != 0) { // Varint
                    revert();
                }
                if (height != 0) {
                    revert();
                }
                i += keyLength;
                (height, valueLength) = parseAminoVarint(bs, i);
                // height is encoded as signed varint, so need to divide by 2
                if (height % 2 != 0) {
                    revert();
                }
                height /= 2;
                i += valueLength;
            } else if (field == 6) { // Type
                if (typ != 0) { // Varint
                    revert();
                }
                if (voteType != 0) {
                    revert();
                }
                i += keyLength;
                (voteType, valueLength) = parseAminoVarint(bs, i);
                if (voteType != 2) {
                    revert();
                }
                i += valueLength;
            } else if (field == 7) { // BlockID
                if (typ != 2) { // ByteLength
                    revert();
                }
                if (hashIndex != 0) {
                    revert();
                }
                i += keyLength;
                uint valueLengthLength; // Length of the length tag
                (valueLength, valueLengthLength) = parseAminoVarint(bs, i);
                uint j = i + valueLengthLength;
                i = j + valueLength;
                while (j < i) {
                    (field, typ, keyLength) = parseAminoFieldAndTyp(bs, j);
                    if (field == 1) { // BlockID.Hash
                        if (typ != 2) { // ByteLength
                            revert();
                        }
                        j += keyLength;
                        (valueLength, valueLengthLength) = parseAminoVarint(bs, j);
                        if (valueLength != 20) {
                            revert();
                        }
                        hashIndex = j + valueLengthLength;
                        break;
                    } else {
                        j = nextFieldStartingIndex(bs, j + keyLength, typ);
                    }
                }
                if (hashIndex == 0) {
                    revert();
                }
                hash = extractBytes20(bs, hashIndex);
            } else {
                i = nextFieldStartingIndex(bs, i + keyLength, typ);
            }
        }
        return (height, hash);
    }
    
    // Assumed format: 8-byte big-endian height, 8-byte big-endian round, 1-byte vote type, 20-byte block hash, and then the remaining fields
    function parseVotePacked(bytes bs) internal pure returns (uint64 height, bytes20 hash) {
        assembly {
            height := mload(add(bs, 8))
            hash := mload(add(bs, 49))
        }
        byte voteType = bs[16];
        require(voteType == 2);
        return (height, hash);
    }

    function extractSignature(bytes signatures, uint index) internal pure returns (uint8 v, bytes32 r, bytes32 s) {
        assembly {
            r := mload(add(signatures, add(index, 32)))
            s := mload(add(signatures, add(index, 64)))
            v := and(mload(add(signatures, add(index, 65))), 0xFF)
        }
        return (v, r, s);
    }

    function checkVotingPower(bytes32 voteHash, bytes signatures) internal view {
        uint len = signatures.length;
        require(len > 0 && len % 65 == 0);
        uint256 voterSet = 0;
        uint power = 0;
        uint8 v;
        bytes32 r;
        bytes32 s;
        for (uint i = 0; i < len; i += 65) {
            (v, r, s) = extractSignature(signatures, i);
            address voter = ecrecover(voteHash, v, r, s);
            require(voter != address(0x0));
            uint8 voterIndex = votingPowerIndex[voter];
            require(voterIndex != 0);
            uint256 voteBit = 1 << uint(voterIndex);
            require((voterSet & voteBit) == 0);
            voterSet |= voteBit;
            // TODO: should check voting power != 0?
            power += votingPower[voterIndex];
        }
        // Need MORE than 2/3 of totalVotingPower
        // TODO: be careful about overflow?
        require(power * 3 > totalVotingPower * 2);
    }

    // "0x0000000000000003000000000000000002C071F4411882647F12016B6BBB94DDB27EF05AD201234567890123456789012345678901234567890123456789"
    function commitAppHashPackedTest(bytes votePacked) public {
        uint height;
        bytes20 blockHash;
        emit GasReport(400, gasleft());
        (height, blockHash) = parseVotePacked(votePacked);
        emit GasReport(401, gasleft());
        emit GasReport(402, gasleft());
        emit GasReport(403, gasleft());
        emit Height(height);
        emit BlockHash(blockHash);
        emit GasReport(404, gasleft());
        emit GasReport(405, gasleft());
    }

    // "0x18062A0E090337065B000000001500A4781F30023A300A14C071F4411882647F12016B6BBB94DDB27EF05AD212180802121414135A5CEC2F96968398970D2DB20BFE9D7EE293"
    function commitAppHashAminoTest(bytes voteAmino) public {
        uint height;
        bytes20 blockHash;
        emit GasReport(100, gasleft());
        (height, blockHash) = parseVoteAmino(voteAmino);
        emit GasReport(101, gasleft());
        emit Height(height);
        emit BlockHash(blockHash);
    }

    // Sample input: {"@chain_id":"test-chain-dvwvaa","@type":"vote","block_id":{"hash":"C071F4411882647F12016B6BBB94DDB27EF05AD2","parts":{"hash":"14135A5CEC2F96968398970D2DB20BFE9D7EE293","total":1}},"height":3,"round":0,"timestamp":"2018-05-24T03:52:35.528Z","type":2}
    // jsonStr: "{\"@chain_id\":\"test-chain-dvwvaa\",\"@type\":\"vote\",\"block_id\":{\"hash\":\"C071F4411882647F12016B6BBB94DDB27EF05AD2\",\"parts\":{\"hash\":\"14135A5CEC2F96968398970D2DB20BFE9D7EE293\",\"total\":1}},\"height\":3,\"round\":0,\"timestamp\":\"2018-05-24T03:52:35.528Z\",\"type\":2}"
    // typeIndex: 241
    // heightIndex: 181
    // blockIndex: 48
    function commitAppHashJsonTest(
        string voteJson,
        uint16 typeIndex,
        uint16 heightIndex,
        uint16 blockIndex
    ) public {
        uint height;
        bytes20 blockHash;
        emit GasReport(200, gasleft());
        (height, blockHash) = parseVoteJson(voteJson, typeIndex, heightIndex, blockIndex);
        emit GasReport(201, gasleft());
        emit Height(height);
        emit BlockHash(blockHash);
    }

    // Sample input: {"@chain_id":"test-chain-dvwvaa","@type":"vote","block_id":{"hash":"C071F4411882647F12016B6BBB94DDB27EF05AD2","parts":{"hash":"14135A5CEC2F96968398970D2DB20BFE9D7EE293","total":1}},"height":3,"round":0,"timestamp":"2018-05-24T03:52:35.528Z","type":2}
    // jsonStr: "{\"@chain_id\":\"test-chain-dvwvaa\",\"@type\":\"vote\",\"block_id\":{\"hash\":\"C071F4411882647F12016B6BBB94DDB27EF05AD2\",\"parts\":{\"hash\":\"14135A5CEC2F96968398970D2DB20BFE9D7EE293\",\"total\":1}},\"height\":3,\"round\":0,\"timestamp\":\"2018-05-24T03:52:35.528Z\",\"type\":2}"
    // typeIndex: 241
    // heightIndex: 181
    // blockIndex: 48
    // appHash: "0xACB21A217DBE46B3AAC0E508AF3E42628CBA76D8"
    // appHashProof: ["0x263a2b2a6975230091ca1f75254aa67f990c166e", "0x2518991b0459722788cb6f19ebca0ca46ffd2078", "0x617471be53a76299dddbfa3fcf856364f1dadb11", "0x4984658370359ef23dd599bf764284b7b59d8c94"]
    // signatures: "0xf8dbaf0e07d98c5f6bfa1f5ed123b8cda630f340ce016aebb247417a134b81bc17620cf62e9fed4cdd0b77568f93cb55ec97b0db9128f50a44e809e5e016bdfb1c"
    function commitAppHash(
        string voteJson,
        uint16 typeIndex,
        uint16 heightIndex,
        uint16 blockIndex,
        bytes appHash,
        bytes20[] appHashProof,
        bytes signatures
    ) public {
        emit GasReport(300, gasleft());
        bytes32 voteHash = sha256(bytes(voteJson));
        emit GasReport(301, gasleft());
        checkVotingPower(voteHash, signatures);
        emit GasReport(302, gasleft());
        uint height;
        bytes20 blockHash;
        (height, blockHash) = parseVoteJson(voteJson, typeIndex, heightIndex, blockIndex);
        require(height > latestBlockHeight);
        emit GasReport(303, gasleft());
        verifyAppHash(blockHash, appHash, appHashProof);
        emit GasReport(304, gasleft());
        // TODO: Extract useful part from appHash,
        //       e.g. appHash = concat(tree1Hash, tree2Hash), then we may just extract tree2Hash
        //       and store it
        bytes20 extractedAppHash;
        assembly {
            extractedAppHash := mload(add(appHash, 32))
        }
        latestAppHash = extractedAppHash;
        latestBlockHeight = height;
    }

    function sha256Trunc(bytes packed) internal pure returns (bytes20 hash) {
        bytes32 originalHash = sha256(packed);
        return bytes20(originalHash);
    }

    function proveStateInTree(
        bytes key,
        bytes value,
        uint8[] heights,
        uint64[] sizes,
        int64[] versions,
        bool[] innerBranchFirst,
        bytes20[] innerNodes
    ) public view {
        uint length = innerNodes.length;
        require(heights.length == length);
        require(sizes.length == length);
        // versions include 1 more entry than others, since it includes the version of the leaf node
        require(versions.length == length + 1);
        require(innerBranchFirst.length == length);
        bytes20 hash = sha256Trunc(abi.encodePacked(
            int8(0), int64(1), versions[length],
            int8(key.length), key,
            int8(value.length), value
        ));
        for (uint i = 0; i < length; i += 1) {
            // Heights are encoded as int8 (signed), which is encoded using binary.PutVarint in
            // Amino, so there is a sign bit '0' after the number, making the value of the
            // resulting byte doubled
            if (innerBranchFirst[i]) {
                hash = sha256Trunc(abi.encodePacked(
                    uint8(heights[i] * 2), sizes[i], versions[i],
                    int8(20), innerNodes[i],
                    int8(20), hash
                ));
            } else {
                hash = sha256Trunc(abi.encodePacked(
                    uint8(heights[i] * 2), sizes[i], versions[i],
                    int8(20), hash,
                    int8(20), innerNodes[i]
                ));
            }
        }
        require(hash == latestAppHash);
    }

    function withdraw(
        bytes key,
        bytes value,
        uint8[] heights,
        uint64[] sizes,
        int64[] versions,
        bool[] innerBranchFirst,
        bytes20[] innerNodes
    ) public {
        // TODO: Check length of key & value? But invalid key and value should fail Merkle proof checking
        proveStateInTree(key, value, heights, sizes, versions, innerBranchFirst, innerNodes);
        bytes memory PREFIX_KEY = "_ACCOUNT_WITHDRAW_";
        require(byteCmp(key, 0, PREFIX_KEY));
        address from;
        uint64 id;
        uint256 amount;
        assembly {
            // 32 = bytes prefix length
            // 38 = 32 + PREFIX_KEY.length - (32 - sizeof(address))
            from := mload(add(key, 38))
            // 46 = 32 + PREFIX_KEY.length + sizeof(address) - (32 - sizeof(uint8))
            id := and(mload(add(key, 46)), 0xFFFFFFFFFFFFFFFF)
            amount := mload(add(value, 32))
        }
        require(!consumedIds[from][id]);
        consumedIds[from][id] = true;
        require(token.transfer(from, amount));
    }

    // TODO:
    //  - separate different logics into different contracts
    //  - parse params from bytes so the interface won't be fixed
    //  - make contracts upgradable by separating LikeCoin storage address and state storage address
    //    from logic contracts
    //  - an upgrade mechanism
    //  - use libary to reduce gas consumption?
}