Message complexity poorly predicts latency in async verifiable secret sharing
The claim
Message complexity alone does not reliably predict latency, and optimistic paths can be outweighed by recovery costs while batching only helps when verification is off the critical path
Published as: “Asynchronous Verifiable and Complete Secret Sharing: From Design Patterns to System-Level Trade-offs”
So what
The results give practitioners concrete guidance for selecting an AVSS/ACSS protocol that matches their latency, throughput, and fault-tolerance requirements.
The five-minute version
Message complexity alone poorly predicts latency; optimistic execution paths can be dominated by recovery cost; and batching or packing only helps when verification stays off the critical path. The paper empirically shows these effects across seven AVSS/ACSS protocols on Grid'5000.
What they found 3
- Message count is a poor predictor of latency; recovery cost dominates optimistic paths.
“The results show that message complexity alone poorly predicts latency, that optimistic paths can be dominated by recovery cost, and that batching or packing helps only when verification stays off the critical path.”
- LIGHTAVSS excels when the dealer is honest but suffers large performance loss under faulty-dealer stress.
“Optimistic execution explains LIGHTAVSS’s honest-dealer advantage and its large faulty-dealer penalty;”
- GOSSAMER achieves the highest sustained throughput (≈1000 secrets/s) with low latency by keeping CPU work off the critical path.
“GOSSAMER sustains around one thousand secrets per second with sub-200 ms average latency at the knee in both honest-dealer and faulty-dealer peak experiments because its batched path keeps CPU-time low and avoids commitment-heavy recovery.”
What undercuts it the paper’s own results
- LIGHTAVSS’s low latency in the honest-dealer case is offset by a dramatic drop in throughput and higher latency when the dealer is faulty, contradicting any claim that it is uniformly the best choice.
Stated limits 2
- Our faulty-dealer experiment is a controlled stress scenario that activates detection, complaint, or recovery paths; it is not an exhaustive Byzantine worst case and does not cover all equivocation patterns, message schedules, or adaptive corruptions.
- Grid’5000 provides a homogeneous, lowlatency environment that helps isolate intrinsic protocol costs but does not reproduce geo-distributed WAN conditions or heterogeneous deployments.
What’s new here 4
- First corpus-backed design-space analysis of modern asynchronous verifiable and complete secret sharing.
- Common Rust implementation of seven representative protocols enabling apples-to-apples evaluation.
- Systematic measurement of both honest-dealer and faulty-dealer stress scenarios across latency, throughput, message count, bandwidth, and CPU.
- Derivation of practical deployment guidelines based on observed design-to-cost trade-offs.
Artifacts & methods 3
- Rust framework implementation of seven protocolssystem
- Grid'5000 experimental platformevaluation
- Representative protocol set (HAVEN, HBACSS, LIGHTAVSS, SIMPLAVSS, GOSSAMER, BINGO, HONEYB)primitive