Protocol costs - Stoffel Documentation

Use this page to estimate whether a Stoffel backend fits your latency, throughput, and preprocessing budget. Read it with the security and fault model: a low operation count does not remove a protocol’s security or availability assumptions.

Cost notation

n: computing-party count
t: corruption threshold
B: values processed in a batch
d: polynomial degree
L: broadcast payload bytes
k: AVID data-shard count
h: hash width
q: shares used in an interpolation attempt

A communication stage is a causal dependency, not a wall-clock duration. One reliable broadcast contains several message exchanges. Independent openings can run in parallel, while dependent multiplications add circuit depth. Field operations, group scalar multiplications, encryption, hashing, and Reed–Solomon decoding have different costs. Treat the asymptotic bounds below as planning tools and benchmark the actual field, curve, party topology, batch size, and network used by your application.

HoneyBadgerMPC preprocessing

Component	Communication stages	Computation and communication	Paper
Double sharing	All-party dealing for degree-`t` and degree-`2t` shares	FFT-based polynomial evaluation over the actual domain; `O(n²B)` total scalar delivery across all dealers	^[1]^[9]
RanSha	Deal, mix, verifier reconstruction, verdict broadcast	`O(Bn²)` matrix work plus robust reconstruction by verifier parties	^[1]
RanDouSha	Double-share generation, mixing, degree checks, verdict broadcast	Two matrix transforms plus reconstruction at degrees `t` and `2t`	^[1]
Triple generation	Degree-`2t` reconstruction after random and double shares are available	`O(B)` local products and corrections plus robust reconstruction	^[1]^[12]
Random bits	Secure square, opening, and normalization stages	Multiplication, reconstruction, field square roots or inversions, and candidate handling	^[8]
PRandBitD	Correlated generation, checks, and reconstruction	Work scales with requested bit width and batch size; includes cross-field operations	^[8]
PRandInt	Local weighted assembly after random bits exist	Linear in supplied bit count; generating the bits is additional work	^[8]

These stages produce the material consumed online. They are throughput work rather than application-circuit depth when material is generated ahead of time. If material is generated on demand, the same stages move onto the application’s critical path. Preprocessing can wait indefinitely for a required party. Capacity planning should therefore include a reserve sized for the largest expected burst and a policy for what happens when replenishment stops.

HoneyBadgerMPC online

Operation	Communication stages	Computation	Paper
Add, subtract, public scaling	None	`O(B)` field operations	^[9]
Secret multiplication	Parallel opening of two masked differences, then local Beaver arithmetic	`O(B)` field arithmetic plus robust reconstruction	^[1]^[12]
Input	Private mask delivery to the input client, then reliable broadcast of the masked correction	Client reconstruction plus local party subtraction	^[1]
Output	Direct shares to the output client	Robust reconstruction for each output	^[1]^[9]
Probabilistic truncation	One masked opening, then local adjustment	Mask assembly, decoding, and integer/field operations	^[8]
Fixed-point multiplication	Secret multiplication followed by truncation	Sum of multiplication and truncation work	^[8]^[12]
Division by a public constant	Local reciprocal scaling followed by truncation	Public reciprocal, local scaling, and truncation	^[8]

Multiplication depth usually matters more to latency than multiplication count. Independent products can share an interactive layer and consume more preprocessing without adding the same amount of sequential latency. Comparisons, bit decomposition, and nonlinear operations often expand into several multiplication and bit-oriented steps. Batch reconstruction packs d+1 values and uses two causal exchange stages. Batched wire sessions reduce message overhead, but transmitted bytes and polynomial work still grow with the number of values. Robust error correction may retry decoding as additional shares arrive.^[1]^[6]^[7]

AVSS costs

Phase and operation	Communication stages	Computation	Paper
Preprocessing: encrypted dealing	One reliable-broadcast layer per dealer batch	Dealer: `O(Bnt)` field evaluation, `O(B(t+1))` group commitments, `O(n)` Diffie–Hellman operations, and `O(Bn)` encryption. Each recipient verifies `O(B(t+1))` group work per dealer.	^[9]^[10]
Preprocessing: random shares	`n` concurrent dealings, then local mixing	`O(Bn²)` field work and `O(Bn²(t+1))` group work, plus dealing costs	^[1]^[10]
Preprocessing: triples	`2t+1` selected dealers reshare products	With `m=2t+1`, combining uses `O(Bm(t+1))` group work plus `O(Bm²)` field work	^[12]^[15]
Online: add and subtract	None	`O(t)` commitment additions per scalar plus field arithmetic	^[10]
Online: public scaling	None	`O(t)` group scalar multiplications per scalar plus field arithmetic	^[10]
Online: multiplication	One all-party broadcast layer opens both masked differences	`O(Bt)` commitment work; verification grows with responders and can repeat as shares arrive	^[12]
Online: input	Mask shares to the client, followed by a masked-correction broadcast	Commitment verification, grouping, and interpolation	^[1]^[10]
Online: output	Direct shares to the output client	Commitment verification, grouping, and interpolation	^[9]^[10]

AVSS has higher per-value cryptographic cost than uncommitted field arithmetic because share operations also update or verify curve points. Use it where public commitments or curve compatibility are part of the required output boundary, not as a default replacement for ordinary private application arithmetic. AVSS multiplication additionally assumes correct triples. The supplied product-resharing step does not prove the multiplication relation against an active dealer, so its operation count should not be interpreted as the cost of a complete malicious-secure triple protocol.

Shared distributed primitives

Primitive	Communication	Local work	Paper
Bracha reliable broadcast	INIT, ECHO, READY; `O(n²)` messages and `O(n²L)` total payload bytes	Payload hashing, serialization, and sender tracking	^[13]
AVID-style reliable broadcast	Shard, ECHO, READY; `O(n²)` messages and approximately `O(n²L/k + n² log(n)h)` total bytes	Reed–Solomon encoding/decoding and Merkle proof generation/verification	^[3]
Asynchronous binary agreement	Repeated EST, AUX, and common-coin stages; `O(n²)` control messages per iteration	Signature-share checks, threshold combination, and agreement state	^[4]^[16]
Asynchronous common subset	`n` reliable broadcasts plus `n` binary agreements	Sum of its broadcast/agreement work plus selected-set handling	^[4]
Trusted common-coin setup	`O(n)` dealer-to-party messages	Threshold-key generation and share distribution	^[4]

The standalone binary-agreement and common-subset components are not part of the default preprocessing path. Do not add their costs to every arithmetic operation.

Capacity-planning checklist

Measure a run with a prefilled preprocessing pool.
Measure a run that generates the same material on demand.
Record n, t, field or curve, batch sizes, secret multiplication count and depth, and input widths.
Record the reliable-broadcast variant, message bytes, retries, and network conditions.
Test pool exhaustion and delayed-party behavior, not only the all-honest fast path.
For AVSS, include group verification and commitment serialization in the budget.
For fixed point, include truncation and random-bit generation rather than counting only the underlying multiplication.

These measurements determine deployment capacity. The protocol bounds explain how that capacity changes as party count, batch size, and circuit shape change.

Sources

[1] Lu, Yurek, Kulshreshtha, Govind, Mahadev, Kate and Miller. HoneyBadgerMPC and AsynchroMix: Practical Asynchronous MPC and its Application to Anonymous Communication (2019). https://eprint.iacr.org/2019/883.pdf [3] Cachin and Tessaro. Asynchronous Verifiable Information Dispersal (2004). https://homes.cs.washington.edu/~tessaro/papers/dds.pdf [4] Miller, Xia, Croman, Shi and Song. The Honey Badger of BFT Protocols (2016). https://eprint.iacr.org/2016/199.pdf [6] Gao. A New Algorithm for Decoding Reed-Solomon Codes (2003); DOI 10.1007/978-1-4757-3789-9_5. https://www.math.clemson.edu/~sgao/papers/RS.pdf [7] Choudhury, Hirt and Patra. Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity (ePrint 2012/517). https://eprint.iacr.org/2012/517.pdf [8] Catrina and Saxena. Secure Computation With Fixed-Point Numbers (2010). https://ifca.ai/pub/fc10/31_47.pdf [9] Shamir. How to Share a Secret (1979). https://www.cs.tau.ac.il/~bchor/Shamir.html [10] Feldman. A Practical Scheme for Non-interactive Verifiable Secret Sharing (1987). https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/feldmanVSS.pdf [12] Beaver. Efficient Multiparty Protocols Using Circuit Randomization (CRYPTO 1991). https://doi.org/10.1007/3-540-46766-1_34 [13] Bracha. Asynchronous Byzantine Agreement Protocols (1987). https://doi.org/10.1016/0890-5401(87)90054-X [15] Ben-Or, Goldwasser and Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (1988). https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/GBW88/GBW88.pdf [16] Mostefaoui, Moumen and Raynal. Signature-Free Asynchronous Binary Byzantine Consensus with t < n/3, O(n^2) Messages, and O(1) Expected Time (2015). https://doi.org/10.1145/2785953

​Cost notation

​HoneyBadgerMPC preprocessing

​HoneyBadgerMPC online

​AVSS costs

​Shared distributed primitives

​Capacity-planning checklist

​Sources