BoLD: question about number of defender’s stake

1

The BoLD paper is awesome! Permissionlessness is crucial for validation. I was wondering how many stakes the defenders can be forced to submit in the multi-level setting.

From the paper:

3.4.5 Staking. A party who creates a level-zero edge must submit a stake S which they should expect to lose if their edge is incorrect. If there are L level-zero edges, the total stakes will be LS.

When a lower challenge is started, any party can create a level-zero edge in the lower challenge

Within each challenge or sub-challenge, the basic protocol is executed as described in the previous section.

I understand this as meaning that for each sub-challenge a party wishes to create a top-level edge, they’d need to submit another stake. This makes sense to me, otherwise I see the risk of a Sybil attack.

With this in mind, considering a two-level challenge, what would happen if the attackers create X different top-level edges at the first level? Would it force X level-two sub-challenges, in which defenders would have to submit another stake for each sub-challenges, for a total of X new stakes?

Here’s a step by step of what I’m trying to describe.

Defender: creates the honest top-level edge in level-one challenge, submitting 1 stake.

Attacker: creates X dishonest top-level edges in level-one challenge, submitting X stakes.

Defenders and attackers: play the standard game by creating further child edges, “chasing” each other in parallel. My understanding is that both attacker and defender would end up submitting X * log2 (steps) edges. At this point, I believe there’ll be a total of X one-step forks in the challenge, starting X sub-challenges.

Is the next step for the defender to create X honest top-level edges, one in each new sub-challenge, submitting one new stake for each?

5 Likes
2

Hi @GCdePaula!
For each challenge-level, only one honest-party stake is ever required. In your example, this is true on level-2 for the same reason it’s true on level-1; there’s only one valid edge at the start of each level, and the honest defenders can effectively act as a team to use the valid edge to make moves against all invalid edges.

And to be sure: the “defenders” here are anybody who chooses to participate, not just (say) the party who submitted the stake (the top-level edge includes includes a merkle-commitment of the execution trace to the next level, so invalid moves simply revert).

Also, note that only the initial, top-level assertion requires a full stake; the stake required for a sub-challenge (i.e., to transition to a lower level) can be significantly smaller (a “mini-stake”). This is because invalid sub-challenges don’t buy any additional delay, they only slightly grief the honest team.

2 Likes
3

Hello, @DZack23! Thank you for the reply, very clear answer :slight_smile:

I understand! Mind if I ask further questions? I’m still a bit lost on a few details haha.

To simplify my comment, I’ll describe as if there were a single honest validator (the “defender”, who’ll post the single honest top-level edge in each challenge) and a single dishonest validator (the “attacker”, who’ll try to mess things up). Take that to generally mean “the set of honest validators” and “a set of dishonest validators working in tandem” respectively. Alternatively, take that as pessimistic scenario where there’s only a single honest validator defending the rollup against the world.

If I understood it correctly, in a multi-level setup the defender can be forced to “match” the number of stakes submitted by the attacker on the previous challenge level. The mitigating factor is that nested challenges have a smaller stake.

I’m curious about this mini-stake. Can you give more details, or point somewhere I could read more about it? I’m wondering how small it is. Do they get exponentially smaller as nestedness increases? I guess not, otherwise either the confiscated stake wouldn’t be able to reimburse the costs, or the first stake would have to be very high.

This is because invalid sub-challenges don’t buy any additional delay, they only slightly grief the honest team.

I don’t get this :confused:

What buys additional delay, and why sub-challenges don’t? My understanding is that the height of the history can be as large as the parent one, which would grief just as much.

You can see that I’m a bit confused haha, some detail probably went right over my head. Thank you again for the reply.

4

It’s an excellent question–the logic of this protocol is subtle.

The reason why sub-challenges don’t buy additional delay is that in a sub-challenge, the timers are inherited from the parent challenge. So the attacker doesn’t get any additional time cushion for starting a sub-challenge.

Here’s another way to look at it. If the honest parties are moving diligently, then the adversary has a dilemma. When the honest parties bisect, the adversary must either (a) not respond, which lets the honest parties accumulate time toward the fixed time goal that will allow the honest leaf edges to be confirmed, or (b) respond by bisecting, which will allow the honest parties to bisect again and cut the disagreement in half.

Either choice uses a limited “resource” that the adversaries have. If they choose (a) they use up their fixed-size time allowance. If they choose (b) they use up a level of bisection, getting one level closer to the max level where the honest parties will be able to do one-step proofs. If they run out of either resource, the honest parties will be able to confirm their leaf edges and win the challenge.

This dilemma is the same for the adversaries, whether the challenge is all done as a single unit, or divided into multiple levels of challenge. (And the “resource allocations” the adversary has are the same either way.)

In terms of the stake amounts, a top-level assertion starts a challenge, which gives the adversary those two resources, including the time resource which the adversary can use to cause delay. That’s why the top-level assertion stake needs to be larger. But sub-challenges don’t give the adversary more of either resource, so they just need stakes large enough to prevent minor griefing.

5 Likes
5

That’s pretty clever! I was also having trouble understanding the clocks/timers, this explanation made everything clearer. Thank you :slight_smile:

I have more questions haha, I hope that’s ok!

they just need stakes large enough to prevent minor griefing.

I see! However, I think this just shifts my original question to a three-level setup, in which the attacker forces the defender to submit as many stakes in the subsequent level of sub-challenges as the attacker did in the previous level.

Suppose a three-level setup with a given smaller stake for the bottom two challenge levels. If coordinated attackers had enough funds for X stakes, how much funds would the defenders need to have in hand to protect the rollup: O(X), O(X^a), O(log(X)), O(log^2(X)) …?

4 Likes