> ## Documentation Index > Fetch the complete documentation index at: https://docs.stoffelmpc.com/llms.txt > Use this file to discover all available pages before exploring further. # Protocol costs > Compare preprocessing and online communication stages, computation, and batching costs. Use this page to estimate whether a Stoffel backend fits your latency, throughput, and preprocessing budget. Read it with the [security and fault model](./security-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 1. Measure a run with a prefilled preprocessing pool. 2. Measure a run that generates the same material on demand. 3. Record `n`, `t`, field or curve, batch sizes, secret multiplication count and depth, and input widths. 4. Record the reliable-broadcast variant, message bytes, retries, and network conditions. 5. Test pool exhaustion and delayed-party behavior, not only the all-honest fast path. 6. For AVSS, include group verification and commitment serialization in the budget. 7. 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](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](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](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](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](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](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](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](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](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](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](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](https://doi.org/10.1145/2785953)