How much overhead can you expect when executing code as a garbled circuit? Is there a limit to the amount of instructions before using garbled circuits becomes impractical?
Since all programs have to be compiled to boolean gates and these gates have to be encrypted, there is a difference of a few orders of magnitude between running programs natively on a CPU (which can of course use highly optimized arithmetical instructions) and running programs over MPC.
In the end, it all depends on the complexity of the program: For simple programs like the Wordle guess/solution comparison (about 40 lines of code, compiled to < 2k gates) the communication overhead is more significant than the computational overhead. The Garbled Circuits protocol used by Tandem needs 7 rounds of communication, so with a round-trip time of 50ms the whole execution takes 350ms.
For more complicated programs, the computational overhead becomes a bit more significant. For programs of > 100k gates, the time to execute a program can range from a few seconds to about a minute. For example, an AES 256 computation requires ~ 9k AND gates and 40k XOR gates.
Right now I would not use it for programs with more than a couple 100k gates, but the engine has not yet been optimized very much, at the moment the focus is on providing a good UX and an easy way for people to experiment with MPC. I'm pretty sure that with a bit of optimization efforts it will be possible to speed it up significantly.
skoodge|3 years ago
In the end, it all depends on the complexity of the program: For simple programs like the Wordle guess/solution comparison (about 40 lines of code, compiled to < 2k gates) the communication overhead is more significant than the computational overhead. The Garbled Circuits protocol used by Tandem needs 7 rounds of communication, so with a round-trip time of 50ms the whole execution takes 350ms.
For more complicated programs, the computational overhead becomes a bit more significant. For programs of > 100k gates, the time to execute a program can range from a few seconds to about a minute. For example, an AES 256 computation requires ~ 9k AND gates and 40k XOR gates.
Right now I would not use it for programs with more than a couple 100k gates, but the engine has not yet been optimized very much, at the moment the focus is on providing a good UX and an easy way for people to experiment with MPC. I'm pretty sure that with a bit of optimization efforts it will be possible to speed it up significantly.