search

HarryR / panautomata

Cross-chain proofs and atomic transactions
GNU General Public License v3.0
18 stars 2 forks source link

Trustless Link for Ethereum blocks #12

Open HarryR opened 6 years ago

HarryR commented 6 years ago

Following along similarly to the trustless nature of the Grid+ contract, what we want to do is make it easy for somebody to prove that the Merkle tree uploaded by somebody has been falsified. However I'm unsure if the complexities this introduces will be worth it.

For the negative proofs there are two things which need to be proven:

1) The most recent Ethereum block is the correct successor 2) The uploaded merkle root for that block (which is different from the blocks transaction root) contains all transactions and events

The simpler way to do this would be to just use Ethereum blocks, because then the transaction root of the previous block would be proven by the successive block (although the transactions in a block cannot be trusted until a successive block has been confirmed). But that means you don't get condensed proofs for transactions and events.

Every transaction and every event can be mapped 1:1 to an entry in the ordered merkle tree. So as an example of a negative proof if you provide the transaction receipt for the first transaction, the receipt proof for the ethereum block, then the 'short' merkle proofs for the transaction and every event it emits - this information could be verified as being incorrect?

e.g. if you provide correct 'short' paths from either side of the effected transaction, then provide the transaction receipt which would generate the merkle leafs for the items in between, then if those items don't result in the same merkle tree you can prove that the submitted tree has falsified data within it.

TODO: proof of concept

         R
       /   \
      A1    A2 
     /  \  
   /      \
  B1      B2
 /  \    /  \
TX1 EV1 TX2 TX3

To proof that the leaves TX1 and EV1 have been falsified you must provide the receipt for TX1 and the full path for TX2 and possibly TX3. Then the on-chain contract re-creates the B1 and B2 nodes. If the re-created leaves don't fit in the tree then the merkle root (R) has been provably falsified.

From a related / inspirational ticket:

@Shirikatsu

If we're thinking trustless, how can the events generated by an off-chain service ever be surely correct? Who would provide this service?

This is a rough draft of how any attempts to falsify merkle roots can be verified on-chain without having to verify all of the data on-chain. The problem is incentivisation and the game theory of how to penalise the merkle root uploader(s)/validators in the event of a false proof - given that the stakes may be higher than anything you could 'slash' the only thing you can do is defer the blocks from being valid until there's been enough time for independent third parties to submit negative proofs of any potentially malicious data.

The only remaining problem is how do you know the next block is valid (which is needed to verify the previous blocks transaction root)? With PoS and PoW consensus algorithms you have protection against that, but with PoA you have the problem that you basically just have to trust them and you can't do anything if the act maliciously or cooperate.

HarryR commented 6 years ago

@Shirikatsu some more background thought

There are a handful of options:

1) Trusted / PoA, short proofs (compacted transactions / events in merkle tree)

2) Trusted / PoA, long proofs (transaction receipts, ethereum block headers, MPT)

3) Trustless, short proofs, negative proofs

4) Trustless, long proofs

Short Proofs vs Long Proofs

The initial premise was to reduce the overhead of proving that an event or transaction occurred, thus the events and transactions were compacted into only the necessary information. So proving a transaction on chain B requires a short merkle path and enough information to reconstruct the leaf.

With long proofs the full transaction receipt must be provided, in addition to the MPT proof that the receipt exists within a transaction block.

Trusted vs Trustless

If you have a validator pool, who must have a majority vote of M / N signatures for a block header to be accepted on-chain then you're deferring everything to the trust relationship of the validator pools (rather than a single validator, as with Kovan). I think this is an acceptable trade-off, as long as you're never relying on a single chosen validator (e.g. the 'selected leader' in Paxos...) to not screw the world.

With trustless you're relying on verifying the PoW for the successive blocks to confirm the transaction MPT root of the previous block, this works well in practice, but means you have to have a delay before you can accept something as valid (e.g. waiting for N confirmations) - this is standard practice too.

However, relying on the security of PoW or PoS and subsequent block confirmations only works with long-proofs.

To rely on the security of PoW/PoS and the condensed merkle trees used for 'short proofs' you then need an additional mechanism for negative proofs to keep the submitters honest.

Therefore, the easiest and smallest route, is to use condensed proofs with a trusted pool of authorities from whom you need a majority sign-off on the condensed merkle root used for short-proofs.

For trustless the trade-off is clear, long-proofs must be used in addition to waiting for block confirmations before the previous blocks are considered 'valid' and can be proven against.

However, with the other options you're making tradeoffs in the wrong direction, you're trusting an authority - but then requiring long proofs which are made unnecessary by trust in that authority.