Dealing with false submissions - different hashes

[elenadimitrova]

7.5 Dealing with false submissions

7.5.1 The Challenge-Response Protocol

We now consider the more complicated case where two different hashes have been submitted.

1. The Justification Tree
   The first step is for both parties to upload a justification of their submitted hash. This justification consists of a second Merkle root and two Merkle proofs.
   The Merkle root in questions is the JustificationRootHash (JRH); it is the root of the ‘Justification Tree’ – a tree where each leaf represents a complete reputation state i.e. each leaf is a ReputationRootHash.
   The left-most leaf of the Justification Tree (RH0) is the final accepted reputation state from the last update. Both parties must submit a proof that their tree does indeed start at RH0. Note that in a Merkle proof for a left-most leaf, all siblings are hashed on the right.
   The right-most leaf of the Justification Tree (RHn) is the ReputationRootHash they originally submitted. Both parties must submit a Merkle proof that their tree does indeed end with this hash.
   Note that in a Merkle proof for a right-most leaf, all siblings are hashes on the left; furthermore, by noting the steps at which a hash is hashed with itself, we can determine the index of the last leaf.
   This index is required to be n — the number of reputation updates in the log.
   The intermediate leaves of the Justification Tree represent the evolution of the reputation state, with RHi corresponding to the reputation state after the first i reputation updates in this cycle
   have been applied.
   An example of such a tree is shown in Figure 4. Note that in the first stage of the tree, every neighbouring pair of data leaves is hashed, and so any pair has a shared Merkle proof to the root. We do this so that each element in the first row of hashes (indicated by h0;1; h0;2 : : : hn-1;n in Figure 4) represents a transition between two states. It is these transitions that are the subject of the mining dispute resolution process.
   Since any two differing submitted states agree on the first leaf RH0 (which is the ReputationRootHash accepted at the end of the previous iteration of the mining process), and disagree on the last leaf RHn (the hash they submitted), there must be a hash (hi;i+1) that represents the transition from RHi to RHi+1) where they agree on the starting state but disagree on the result. This transition is meant to be the effect of a single reputation update (the i-th - We start counting at zero, i.e. the transition from RH0 to RH1 is the ‘zeroth’.), and this is the reputation update we will calculate on-chain to establish which submission is incorrect.
   First, however, we must establish where the two submissions first differ, see Dealing with false submissions - different hashes - establishing where two submissions differ #48