Intro

Some optimizations have already been proposed, see SnapDeals with Reduced Overhead - Adopting alternative Data Commitment. They introduce the use of a different hash function (SNARK friendly) to compute a second commitment tree of the data.

The scenario is the following:

• We have some input data D
• We have a first commitment Comm1 (a MT with SHA) which is efficiently computable by the client but is inefficient to be proven inside a snark
• We have a second commitment Comm2 (a MT with Poseidon) which can be efficiently proven inside a snark but represent a consistent proving overhead for the client (~ 100x)

Question: How do one knows that both Comm1 and Comm2 are commitment to the same (original) D without having a prover to (always) compute a really expensive snark or a client to have a consistent proving overhead in computing Comm2?

Previous solutions:

PoMTT: interactive and off-chain proof of Merkle Tree translation.

That is, before signing the deal offer the Client requires the SP to do probabilistic checks on different random openings of both Comm1 and Comm2.

• client chooses C random positions and send those to SP;
  • how big is C?
  • say we are okay if the translation is wrong in at most 4% of the positions
  • then (1 - 0.04)^C = 2^(-80)
    • C = -80 / log_2(1-0.04) = ~1359
• SP sends the MT paths for both Comm1 and Comm2;
• Client checks the MT paths received;

If the checks does not convince the Client, he will not sign the deal proposal.

PoWMTT: non interactive proof of Wrong Merkle Tree translation.

At a latter time (after the deal is published), anyone retrieving the data D can challenge the SP that the translation was performed wrong at some position. This challenge would be resolved on-chain, by the SP posting a (singe) proof that translation was performed correctly at the given position (i.e. a single MT path in case of commitments done via MT).

Limitations:

• PoMTT:
  • client overhead: handling the challenge-response protocol, computing some Poseidon hash for verification;
  • (minor) not public verifiable proof;
• PoWMTT:
  • client overhead: how to find the position where to challenge the SP?