Skip to content

Devshard: timeout-vote threshold unreachable under skewed slot distribution — stranded nonce cannot be resolved (liveness) #1570

Open @kaileido opened 2026-08-09 16:18 UTC 2 comments Updated 2026-09-30 09:17 UTC

Summary

When a Devshard escrow's slots are distributed unevenly across participants, the timeout-vote path can become structurally unable to reach its weight threshold, leaving a stranded nonce permanently unresolved. This is a liveness issue: the escrow's inference cannot be timed out / resolved, and a single participant holding a large slot share can (deliberately or by going offline) deadlock timeout resolution for nonces it is involved in.

Observed

nonce stranded            nonce=681  role=speculative
timeout_started           nonce=681  reason=refused
timeout_vote_requested    → mtd2v4zr, 9ulzldum
timeout_vote_result       9ulzldum  accept  weight=1  running=1  threshold=8
timeout_vote_result       mtd2v4zr  accept  weight=2  running=3  threshold=8
timeout_vote_tally        accept=2 weight=3 threshold=8 verifiers=2 sufficient=false
timeout_insufficient_votes

Two verifiers responded with combined weight 3; the threshold is 8; the remaining ~13 weight is held by the participant that does not vote → sufficient=false and the nonce stays stranded.

Root cause

  • A participant's timeout-vote weight equals its slot count in the escrow group (devshard/state/machine.go — AddressSlotCount / addressToSlotCount). Slot distribution across participants can be highly skewed (e.g. 1 / 2 / 13 across three participants of a 16-slot group).
  • The timeout threshold is a fixed fraction of the total group slot weight: ComputeVoteThreshold(groupSize, VoteThresholdFactor) with VoteThresholdFactor = 50 → groupSize/2 (for a 16-slot group, threshold = 8). (Finalize quorum separately uses QuorumThreshold() = 2*totalSlots/3 + 1, devshard/state/machine.go:1424.)
  • The tally (devshard/user/session.go, ~L2147) accumulates only the weight of verifiers that actually respond/accept and requires accWeight > voteThreshold; on failure it emits timeout_insufficient_votes (session.go:1904) and the nonce remains stranded.

The structural gap: the denominator is the full group weight, but the participant whose nonce is being timed out (or any absent large-share participant) is exactly the one not contributing votes. If that participant holds a slot share ≥ total − threshold (here 13 ≥ 16 − 8), the honest, reachable remainder holds ≤ threshold weight and can never reach it, regardless of correctness. Timeout resolution is then impossible.

Impact

  • Liveness: a stranded/refused nonce that needs a timeout vote can never be resolved → the escrow's progress stalls on that nonce.
  • Griefing vector: a participant assigned a large slot share can strand nonces it is involved in simply by not voting (or going offline), and the remaining verifiers cannot meet the threshold to time it out.

Suggested direction

  • Compute the timeout threshold relative to the eligible/responsive verifier weight for that specific nonce, excluding the subject (timed-out) participant's slots from the denominator; or
  • add a fallback resolution when the reachable verifier set cannot structurally reach the threshold (so a single large-share or absent participant cannot deadlock timeout resolution); and/or
  • bound slot-share skew at escrow creation so no single participant can hold ≥ total − threshold of the slots.

💬 Comments (2)

@redstartechno commented 2026-08-11 02:24 UTC

I traced this on current main (f040d0a5b). The report holds, and there is one property worth recording before anyone picks a direction.

Confirmed:

  • Per-participant vote weight is the escrow slot count — AddressSlotCount, devshard/state/machine.go:1431-1433, accumulated at devshard/user/session.go:2123.
  • The threshold is ComputeVoteThreshold(groupSize, VoteThresholdFactor) (devshard/types/config.go:77-82) with the default factor 50 (devshard/testenv/config/config.go:285), so it is computed over total group slot weight. The comparison is accWeight > voteThreshold at devshard/user/session.go:2147, while accWeight only ever collects weight from verifiers that actually answered.
  • Finalize quorum is separate: 2*totalSlots/3 + 1 at devshard/state/machine.go:1423-1424.
  • After timeout_insufficient_votes (devshard/user/session.go:1904-1905) the call returns an error with no retry, escalation or operator path, so the nonce stays unresolved.

With a skew such as 1 / 2 / 13 in a 16-slot group, the two smaller holders cannot reach threshold 8 on their own — whether the large holder is offline or simply declines to vote.

The property worth noting: VoteThreshold is frozen into SessionConfig at session creation and pinned by devshard/state/vote_threshold_freeze_test.go ("bind-time freeze … for protocol compatibility"), as part of EscrowState / StateRootAndProtocolVersion. So a change to the threshold formula would only affect sessions created under a new approved version name — it cannot unstick escrows that are already bound, and those would still need a resolution path of their own. That puts this in protocol-version territory rather than a self-contained fix.

For completeness: #1569 (merged) and #1549 (open) both harden how votes are verified before being counted, but neither changes the threshold semantics.

Posting this as reference material rather than a proposal — the tradeoff between liveness and the safety margin (threshold over reachable weight, a per-participant weight cap, or an explicit resolution path for exhausted verifiers) seems like yours to make. If you settle on a direction, I am happy to implement it with regression coverage for the skewed-slot case.

@Ryanchen911 commented 2026-09-30 09:17 UTC

Looked into this after @redstartechno's trace, and spent some time measuring how often the skewed case comes up on mainnet rather than just reasoning about it. Short version: the mechanism is right, and the skew is far more common than the one example in the report suggests.

I sampled a few dozen live escrows from the current epoch and looked at the slot distribution in each (the escrow query returns slots[], so counting addresses gives vote weight directly). Groups where a single participant holds half the slots or more are not rare — they show up in roughly two out of five. A fair number go higher than that, and the two-participant groups ([9,7], [10,6] type splits) are common enough that they look like normal sampling behaviour rather than an anomaly.

That puts it a bit differently than "a large-share participant can strand a nonce" — with 16 slots as the group size, the threshold being computed over the full group, and weights on this network concentrated in relatively few hosts, the geometry for this looks like what a 16-draw sample of those weights tends to produce. Nothing has to go wrong for an escrow to end up in this shape.

Concretely I'm interested in the third direction in the report — bounding slot-share skew at escrow create, or spreading the same weights over finer slots so the sampling tail is smaller. Both stay at create time and avoid touching the frozen session state @redstartechno flagged, which is why they appeal to me over anything on the threshold side. I don't have a strong preference between the two yet, and I'd rather not pick one before knowing whether either is acceptable here.

I also want to avoid stepping on #1844, which looks like it covers the threshold-value half of this. Happy to leave that alone.

Is the skew side something worth pursuing, and if so would you have a preference between capping the share and increasing slot granularity? I'm glad to put up a PR with a skewed-case regression test if it's wanted — but I'd rather check first than assume, and I'd also defer to whoever's closer to the escrow creation path if someone else is already thinking about it.


🔄 Auto-synced from Issue #1570 every hour.