Devshard: timeout-vote threshold unreachable under skewed slot distribution — stranded nonce cannot be resolved (liveness) #1570
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 / 13across three participants of a 16-slot group). - The timeout threshold is a fixed fraction of the total group slot weight:
ComputeVoteThreshold(groupSize, VoteThresholdFactor)withVoteThresholdFactor = 50→groupSize/2(for a 16-slot group, threshold = 8). (Finalize quorum separately usesQuorumThreshold() = 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 requiresaccWeight > voteThreshold; on failure it emitstimeout_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 − thresholdof the slots.
💬 Comments (2)
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.
I traced this on current
main(f040d0a5b). The report holds, and there is one property worth recording before anyone picks a direction.Confirmed:
AddressSlotCount,devshard/state/machine.go:1431-1433, accumulated atdevshard/user/session.go:2123.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 isaccWeight > voteThresholdatdevshard/user/session.go:2147, whileaccWeightonly ever collects weight from verifiers that actually answered.2*totalSlots/3 + 1atdevshard/state/machine.go:1423-1424.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:
VoteThresholdis frozen intoSessionConfigat session creation and pinned bydevshard/state/vote_threshold_freeze_test.go("bind-time freeze … for protocol compatibility"), as part ofEscrowState/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.