⚖️ Challenge-Response Timeline Parameterization

Historical note: this pre-release bridge-spec page describes earlier challenge-response parameters and should not be used as current bridge architecture. Alpen's current bridge direction is Strata using Glock / garbled locks.

The Setup

Let's assume that the operator initiates the kickoff event at block height k. The kickoff starts the timer for T weeks, after which the operator gets reimbursed from the bridge unless challenged. The implicit claim by the operator is that they have appropriately paid a user whose withdrawal request was assigned to them. Any other operator is now allowed to issue a challenge against that claim.

This challenge needs to be issued and confirmed in the bitcoin blockchain within (p + d) blocks, where

• p is the minimum number of blocks that it may take a functional challenger to produce a Challenge, and
• d is the maximum number of blocks within which the challenge kickoff transaction needs to be confirmed.

Similarly, once the challenge kickoff transaction has been confirmed, the operator who is being challenged (the responder) is allowed to produce a defense within q + d blocks, where

• q is the minimum number of blocks that it may take a functional responder to produce a valid Defense, and
• d is the maximum number of blocks within which the Defense needs to be confirmed.

A faulty operator can also start a competing fork instead of working on the current canonical chain. This fork may begin at any block height f and may or may not contain a valid transaction where the operator compensated the user (depending on who the functional party is).

Now, we need to determine the relationship between these parameters in such a way that it is nearly impossible for a faulty party to win even if they are able to amass 50\% of bitcoin's hash rate.

In reality, there may be two cases, namely:

Case I: Functional Operator vs Faulty Challenger

In this case, a functional operator starts a kickoff event and a faulty operator issues an invalid challenge.

The total proof of work accumulated by the functional operator (now acting as the responder) up to the point where the defense is issued can be calculated by:

PoW_{functional\space responder} = PoW_{f \rightarrow q} = f + r + k + (p + d) + q

Note that p and d are inside parentheses since our setup defines an upper bound on their combined value.

Assuming that the faulty challenger, who has x\% of the total hashpower of the bitcoin network, starts the fork at f, they will have accumulated some proof of work. This can be represented in terms of the proof of work of the canonical chain as:

PoW_{faulty\space challenger} = PoW_{f \rightarrow q\prime} = f + (r + k + p + d)\cdot x

Now, the difference in their proof of work can be computed thus:

PoW_{functional\space responder} - PoW_{faulty\space challenger}\newline = f + r + k +(p + d) + q - \{ f + r \cdot x + k \cdot x + (p + d) \cdot x \}\newline = (1 - x) \cdot (r + k) + (1 - x) \cdot (p + d) + q

In the worst case, the withdrawal fulfillment transaction and the kickoff are both confirmed in the same block and the challenger starts working on their fork right from the kickoff point so that r = k = 0. Then, the difference in proof of work reduces to:

(1 - x) \cdot (p + d) + q

To further reduce this deficit, the faulty challenger may choose to issue a challenge exactly after the kickoff point instead of waiting for the (p+d) limit. This further reduces the deficit to:

\Delta_{functional \space responder} = q

This means that if the responder has accumulated at least q amount of work, we can trust that the responder is functional.

Case II: Faulty Operator and Functional Challenger

The second case we need to consider is where the operator is the one making an invalid claim i.e. claiming a payment to a user that they have not actually paid. In this scenario, if the operator is able to accumulate more proof of work than that of the canonical chain, the other operators will see that the user's withdrawal request has been fulfilled.

In this scenario, the total proof of work accumulated by the functional challenger can be computed as:

PoW_{functional\space challenger} = PoW_{f \rightarrow p} = f + r + k + p

The faulty responder tries to provide an invalid defense once the challenge kickoff transaction has been confirmed. During the process, the total proof of work that they can accumulate can be computed as:

PoW_{faulty \space responder} = PoW_{f \rightarrow q \rightarrow d} = f + (r + k + p + d + q + d) \cdot x

Now, the difference between the respective proofs of work can be obtained as:

PoW_{faulty\space responder} - PoW_{functional\space challenger}\newline = f + (r + k + p + d + q + d) \cdot x - (f + k + r + p)\newline = -(1 - x) \cdot (r + k) + (p + 2 \cdot d + q) \cdot x - p

The final expression has been re-arranged to simplify further analysis. From this final expression, we can see that the faulty responder would want this expression to evaluate to as high a value as possible. It is, therefore, in their best interest to have both r and k to fall on the same block and start a fork from that point on. Then, the above express reduces to:

\Delta_{faulty\space responder} = (p+2\cdot d + q)\cdot x - p

Now, if the above value is positive, the faulty responder will have more proof of work than the functional challenger, and vice versa.

Putting it all together

So, we need to formulate the relationship between the various parameters in such a way that given a responder's chain, say C_l and a challenger-chain, say C_h we always select the chain with the functional party i.e. we select the functional responder in the first case and the functional challenger in the second case, given that the bridge operator is only privy to the total proof of work on the individual chains i.e. PoW_{C_l} and PoW_{C_h}.

Let the difference in the proof of work between the two chains be \Delta. We know that from the first case,

\Delta \ge \Delta_{functional\space responder}

However, this is not sufficient because \Delta may still be greater than \Delta_{faulty\space responder} as well, in which case we would actually be letting a faulty responder win.

So, to accommodate both the above cases, \Delta must be at least equal to \Delta_{functional\space responder} but not greater than \Delta_{faulty\space responder} which means we need to enforce the following:

\Delta_{functional\space responder} > \Delta_{faulty\space responder} \newline \implies q > (p + 2\cdot d + q) \cdot x - p \newline \implies (1 - x)\cdot q > 2\cdot d \cdot x - (1 -x)p\newline \implies q > \frac{2\cdot d \cdot x}{1-x} - p

This is the condition required for the functional operator to win over the faulty one. This means that the faulty operator will have a higher chance to win if:

• they have a very high hash rate (x)
• the challenge/response transaction takes too long to confirm (d)
• the time to issue the challenge is too low (p)

If we assume that the faulty operator’s has 50\% of the bitcoin hashpower, then we get:

q > 2d - p \newline \implies p + q > 2d \newline \implies d < \frac{p + q}{2}

So, the values of p, q, and d should be selected in such a way that the above constraint is satisfied. In practice, the values will be scaled even further so as to provide some margin for errors.