Proposal: Merkle Tree so expensive

[chiro-hiro]

Overview

I've look on MerkleTreeSHA256.sol. This one is an expensive smart contract to operate, so it motivated me to think in another direction.

Reference

• MerkleTreeSHA256.sol

Questions

• If compute/verify proof off-chain cost less than compute it on-chain, why don't we make it easier for on-chain computation?
• Is Merkle tree is the only way to archive that?.

Assumptions

• Actually we only need to store an immutable digest to make sure no one able to change the proof and tracking all state changes.
• Merkle tree is not the only way to resolve this issue

Suggestion

Assume that we have:

• Hash function H()
• Byte array concat operator ++
• Digests need to be used to construct proof: A,B,C (unsorted)

We have: root := H(root, A)

If 0x00...000 is the first root, we have:

0x00...00 <- H(0x00...00 ++ A) <- H(H(0x00...00 ++ A) ++ B) <- H(H(H(0x00...00 ++ A) ++ B) ++ C) ...

These created a immutable chain of digests that only allow us to append to the end of the chain.

Here are my PoC

// SPDX-License-Identifier: MIT
pragma solidity >=0.7.5 <0.8.0;


contract ChainLinkSHA256 {
    event NewDigest(uint256 indexed linkedDigest, bytes32 indexed digest, bytes32 indexed root);
    event NewDigests(uint256 indexed linkedDigest, bytes32[] indexed digest, bytes32 indexed root);

    uint256 public totalLinked = 0;
    bytes32 public chainRoot = 0x0000000000000000000000000000000000000000000000000000000000000000;

    // Append digest to the end of chain of digests by calcualte
    // root := sha256(root ++ digest)
    function appendDigest(bytes32 digest) internal returns (bytes32) {
        chainRoot = sha256(abi.encodePacked(chainRoot, digest));
        totalLinked += 1;
        emit NewDigest(totalLinked, digest, chainRoot);
        return chainRoot;
    }

    // Append digest to the chain one by one
    function appendDigests(bytes32[] memory digests) internal returns (bytes32) {
        bytes32 root = chainRoot;
        for (uint256 i = 0; i < digests.length; i += 1) {
            root = sha256(abi.encodePacked(root, digests[i]));
        }
        chainRoot = root;
        totalLinked += digests.length;
        emit NewDigests(totalLinked, digests, root);
        return root;
    }
}

• What does it cost?
• O(n)

[chiro-hiro]

My demonstration and benchmark result could be found here https://github.com/chiro-hiro/chainlink

[kthomas]

My demonstration and benchmark result could be found here https://github.com/chiro-hiro/chainlink

Awesome 🚀 🎸 💯

[ognjenkurtic]

@Kasshern @skosito @Ybittan @biscuitdey This discussion might be relevant for our work on the SRI. Keeping it open so that we can discuss.