Garbled Circuits on the Blockchain for the Very First Time!

First theorized back in 1982, garbled circuits represent one of the best techniques within multi-party computation (MPC) for preserving private information. Although incredibly powerful, they were never considered for use on the blockchain due to their heavy resource requirements and relative slow speed. After years of extensive research, we’ve achieved a revolutionary breakthrough in garbled circuits, allowing the technology to be used on the blockchain for the very first time.

Today, we are very excited to share this achievement with you, the first of many proof of concepts in our endeavor to put Garbling Circuits on the blockchain. Watch below as we demonstrate a working MPC endpoint utilizing garbled circuits to interact with Alice and Bob.

How do Garbled Circuits Preserve Privacy?

As a privacy-preserving cryptographic technique, garbled circuits were essentially designed to solve one problem: The Millionaires problem created by Andrew Yao. In this theoretical scenario, two millionaires, Alice and Bob, want to work out which one of them is richer without disclosing their actual net worth.

To do this, they can use a garbled circuit which can be simplified into the following steps:

• Step 1 — The problem or “function” (i.e. who is richer) is written as a type of program that uses logical gates, (aka a Boolean circuit). In the Millionaires Problem, suppose that the millionaires’ wealth can fit into 8-bit integers (recall that such integers can accommodate numbers between 0 and 2⁸-1=255). Then the Boolean circuit has 2x8=16 input wires (first set of 8 input wires `belong’ to Alice and the second set `belongs’ to Bob). The circuit structure is such that it takes the first and second sets of input wires, interprets them as numbers X and Y, and computes MAX(X,Y). The result goes to an output wire that encodes a single bit B. If B=0 then we have X > Y and otherwise (B=1) we have X ≤ Y.
• Step 2 — Alice encrypts or “garbles” this Boolean circuit, the result is called Garbled Circuit. Each input wire (recall that there are 16 of them) is associated with two long and random labels L0 and L1 that represent the binary values 0 and 1, respectively. At the time of garbling, Alice has L0 and L1 for all wires. The goal of Alice is to give Bob the garbled circuit, along with only a single label for each input wire, so that Bob will be able to compute the MAX function only once using the labels it obtains. The set of labels associated with the input wires of the garbled circuit (one label per input wire) is called a Garbled Input. In Step 3a, Alice sends the garbled circuit to Bob, including one label for each of the first 8 input wires that belong to her, and in Step 3b, Bob obtains one label per input wire of the second set of 8 input wires (that belong to him).
• Step 3a — Alice sends the garbled circuit to Bob along with the right labels for her 8 input wires.
• Step 3b — Bob “garbles” his own number and obtains 8 labels, one label for each input wire that belongs to him. Now Bob is ready for the actual computation.
• Step 4. Bob computes the garbled circuit on the garbled input (one label per input wire). This process outputs the bit B in the clear, so now Bob knows the result of the computation. In particular, this result does not reveal any dollar amounts, just an answer to the question of who is richer.
• Step 5 — At this point Bob may communicate the result, B, to Alice, so she can learn which of them is richer.

This is obviously a very simplified explanation, make sure to revise this article for a more detailed walkthrough of the process.

Modern Optimizations

For the longest time, garbled circuits were little more than a theoretical computer model due to their significant resource requirement. They certainly weren’t suitable for use on the blockchain which relies on lightweight resource overheads and fast settlement times. However, after years of research, Dr. Avishay Yanai and his team at Soda Labs developed a breakthrough that revolutionizes the speed and power of this technology. This optimization has been so profound, it provides an increase that is faster and more efficient than other solutions on the market.

This includes a computation speed that is up to 1000 times faster than FHE based systems, latency that is up to 100 times lower than current solutions and storage requirements that are up to 250 times smaller than those needed by fully homomorphic encryption. Additionally, garbled circuits can handle transactions that affect a private state shared among multiple parties (unlike ZK-based solutions) and aren’t affected by single-point-of-failure vulnerabilities like those discovered in TEE solutions. We will discuss this optimization at length in the upcoming COTI V2 whitepaper.

For the first time in history, garbled circuits have the speed and computational power to run efficiently on the blockchain, making it the perfect choice for the COTI V2 privacy-preserving solution.

But way more than just theoretical transaction speeds and storage requirements, we’ve already managed to implement the first part of this revolutionary technology.

COTI V2 First Milestone Demo

We recently announced the completion of COTI V2’s first development milestone. This included:

• The design and algorithms of the MPC protocol
• The implementation of the MPC protocol
• Demonstration of the successful input and output of secret data by users.

As part of this milestone, we have recorded a live demonstration of a newly-created MPC endpoint interacting with Alice and Bob via garbled circuits. Watch below as we successfully demonstrate how private transactions will work on COTI V2.

For those who want an abridged solution, we’ve summarized the steps shown in the demonstration.

Step 1 — Alice onboards by requesting a key to be generated by the MPC node. This key is then secret-shared and stored by the system.

Step 2 — Bob also onboards to the system using the same method.

Step 3 — Both Alice and Bob encrypt their inputs (for this demonstration, this is represented by text files containing “private” variables) using their previously shared keys. This encrypted input is contained within a stored file on the MPC node. When inspecting this file, instead of the private information, all you see is a cipher text and random string.

Step 4 — The MPC node contains a list of Ethereum operation codes containing logical programming conditions (IF, OR, NOT, EQUALS etc). When initiated by Alice or Bob, the node assesses the encrypted inputs against these conditions to generate an output. This output not only provides information specific to Alice or Bob, it can also trigger a change to an account balance.

Step 5 — Alice and Bob retrieve this output and use their keys to decrypt the information they are permitted to view.

Our next demonstration will include an even more advanced module with greater functionality and improved integrations into our future ecosystem. There are so many more exciting things to come, from the release of the whitepaper to the launch of the COTI V2 Devnet, so stay tuned for the latest updates on our road to COTI V2.

Stay COTI!

For all of our updates and to join the conversation, be sure to check out our channels:

Website: https://coti.io/

X: https://twitter.com/COTInetwork

YouTube: https://www.youtube.com/channel/UCl-2YzhaPnouvBtotKuM4DA

Telegram: https://t.me/COTInetwork

Discord: https://discord.gg/9tq6CP6XrT

GitHub: https://github.com/coti-io