Bulletproof Multi-Party Computation in Rust with Session Types
At Chain, we’ve been working on a pure-Rust library for Bulletproofs, which we described in a previous post. Our initial release only proved single ranges, but Bulletproofs allow aggregated range proofs. These harness the logarithmic size of the inner-product protocol to create a proof for m values that is smaller and faster to verify than m individual proofs.
The aggregation is performed by a multi-party computation protocol involving multiple parties and one dealer. Each party has a secret value and wishes to create a range proof aggregated with the others, revealing only a commitment to the secret value and not the secret itself. The dealer is a coordinating party that facilitates this process.
In our implementation, the parties share their commitments with the dealer, and the dealer generates and returns challenge variables. Each party sends its share of the proof to the dealer, and the dealer combines their shares using the inner-product proof to create an aggregated proof.
There are multiple ways to model these party and dealer interactions. One way would be to implement the parties and dealers as mutable objects, with a function that mutates the party or dealer state for each step of the protocol. But it’s possible to use this API incorrectly: to call the functions out of order, or forget to call a function, or to call a function more than once. Ensuring that the API is used correctly is made more difficult when running it asynchronously over a network.
A deviation from the protocol could result in invalid proofs, and opens up the user to potential vulnerabilities that might result in the dealer learning a party’s secret value. For instance, each party constructs a vector polynomial and reveals the result of its evaluation at a single challenge point to construct its proof share. However, if the party could be tricked into revealing multiple evaluation results (a multiple-evaluation attack), it would be possible to cancel out the party’s blinding factors to reveal the party’s secrets.
We wanted a foolproof model that would prevent users from performing any step other than the correct next step of the protocol. With this in mind, we modeled each party and dealer state as a distinct type, and used move semantics to enforce state transitions.
In Rust, objects are either owned or borrowed. While there can be multiple borrows of the same object, each object has a unique owner. When objects are passed by value, ownership is transferred to the new scope, and the old scope can no longer access it. This makes it possible to implement “consuming” methods which take self by value, and therefore can only be called once. In the party and dealer types, such methods consume the previous state and return the next state in the protocol.
Due to the Rust type system, we have a guarantee that a step of the protocol can’t be performed twice. Since the first evaluation consumes the object, rustc guarantees that it can’t be referenced to perform another evaluation. This ensures that the implementation is invulnerable to multiple-evaluation attacks. We also have a guarantee that the user can’t perform steps out of order or skip steps, since it is impossible to call a function on an object that is not of the correct type.
This is an example of an implementation of session types, a type theory formalism that was proposed to structure interactions over communicating processes. An overview of session types can be found here, and details on a more general implementation of a session type library for Rust can be found here.
Our implementation of aggregated range proofs is still at an early stage and will continue in a public GitHub repository. For more details about our implementation, see our aggregation protocol notes; for an explanation of how the range proof algorithm works, see our range proof notes.
Thanks to David Tolnay for pointing us to the Session Types in Rust paper, and to Henry de Valence and Oleg Andreev for all their work on the Bulletproofs implementation. This post was originally published on the Chain blog.
