The worst case of relayer-only mode seems to be O(N), N is block length.

[hackfisher]

Assuming that we have enough relayer attackers (> N).

And for each round, if on-chain rules find that the sampled(targeted) headers disagree, then define next sampling is always at half of left side.

Here is an example, the relayed block height to latest confirmed is 8, and there are 1 Honest(H) Relayer, and 7 other Lier(L) Relayers, L2 - L8

The header they relayed is as following:

Initial: G = A1

Starting relay from H1(height = 8, Round 1)

1 - 2- 3- 4- 5- 6- 7- 8 (Block Height)
/ - 3- 4- 2- 6- 7- 5- 1 (Onchain Resolving Rounds)
A1-B1-C1-D1-E1-F1-G1-H1 (H Confirmed at 8, H1 Finalized)
A1-B1-C1-D1-E1-F1-G1-H2 (L2 slashed at height = 7, G = H1, round = 1)
A1-B1-C1-D1-E1-F1-G3-H3 (L3 slashed at height = 6, G = G1, round = 5)
A1-B1-C1-D1-E1-F4-G4-H4 (L4 slashed at height = 5, G = F1, round = 7)
A1-B1-C1-D1-F5-F5-G5-H5 (L5 slashed at height = 4, G = E1, round = 6)
A1-B1-C1-D6-E6-F6-G6-H6 (L6 slashed at height = 3, G = D1, round = 2)
A1-B1-C7-D7-E7-F7-G7-H7 (L7 slashed at height = 2, G = C1  round = 4)
A1-B8-C8-D8-E8-F8-G8-H8 (L8 slashed at height = 1, G = B1, round = 3)

Note1: A1, B1, B8, C1, C7, C8 ... H1, H2, H3, H4, H5, H6, H7, H8 etc. are header hash/mmr_root.
Note2: A1...H1 are valid headers, (A-H)# (where # >=2) are invalid headers.

[yanganto]

The worst case of all models are O(N), N is block length.

When the evil second relayer or the evil challenger keep challenge the honest initial relay on all the blocks. The initial relayer need to relay all the blocks on the chain, so the worst case always O(N).

Therefor, it is important to higher the barrier for making a challenge, such as provide a header instead of a 0 flag when challenger. And also, the rule once you lie ignore all your challenge in all round, is also to higher the barrier for an evil challenger.

[yanganto]

By the way, the worst case is the one always challenge everything. This behavior in Chinese term is "杠精".

[hackfisher]

O(N) means the time, not the works.

Relayer-Challenge Model should be O(logN)

[yanganto]

And the variable bond can against the assumption Assuming that we have enough relayer attackers (> N).

For example, the bond with third header should be 1.5 * bond.

• For an evil guy, he wants to provide the third incorrect header, the barrier is 1.5 higher. Because he knows he lies, the bond will not return.
• For an honest guy, he wants to provide the third correct header to against the two incorrect blocks. Because he knows he is honest. The bond is higher, and the reward is also higher much more, such that the motivation is higher. Because the 1.5 bond will return, and the 2 bonds(one from the first lie relayer and one from the second lie relayer) for the two incorrect blocks will reward him. And the reward / bond is greater, so the motivation is higher.