#programming-language #secure-computation #smpc #garbled-circuits #circuit-description

bin+lib garble_lang

Turing-Incomplete Programming Language for Multi-Party Computation with Garbled Circuits

4 releases

Uses new Rust 2021

0.1.3 Aug 2, 2022
0.1.2 Jul 27, 2022
0.1.1 Jul 26, 2022
0.1.0 Jul 26, 2022

#19 in Programming languages

Download history 73/week @ 2022-07-24 56/week @ 2022-07-31 14/week @ 2022-08-07

143 downloads per month

MIT license

330KB
7K SLoC

Garble Language

Garble is a simple programming language for Secure Multi-Party Computation with Garbled Circuits. The circuits generated by Garble specify a function, with each input coming from a different party and the output computed collaboratively by all parties in a way that no party learns another party's input. Garble is statically typed, low-level, purely functional and uses a syntax heavily inspired by Rust.

All programs written in Garble are deliberately Turing-incomplete (only supporting bounded recursion), guaranteeing that they can be compiled to circuits using only AND, XOR and NOT gates (without any kind of stateful latches or registers). Here's an example of solving the Millionaire's Problem in Garble:

// A function for solving Yao's Millionaires' problem:

enum Richest {
    IsA,
    IsB,
    Tie,
}

pub fn main(a: u64, b: u64) -> Richest {
    if a > b {
        Richest::IsA
    } else if b > a {
        Richest::IsB
    } else {
        Richest::Tie
    }
}

For more examples, see the Language Tour.

How to Use Garble

The circuits generated by Garble are meant to be executed using a cryptographically secure MPC engine, which is not provided by this crate. Garble is agnostic about the details of the MPC engine and assumes only that the engine executes Garbled Circuits with support for AND, XOR and NOT gates. For local development and testing, Garble supports a direct and unencrypted evaluation of a generated circuit, with all inputs supplied by the local user.

To execute the Millionaire's problem example, first install the garble utility, then run the function:

$ cargo install --git https://github.com/sine-fdn/garble
$ garble garble_examples/millionaires.garble.rs main 10000000u64 10000u64
Richest::IsA
$ garble garble_examples/millionaires.garble.rs main 100u64 5000000u64
Richest::IsB
$ garble garble_examples/millionaires.garble.rs main 1000u64 1000u64
Richest::Tie

Architecture of this Repository

The Garble compiler is relatively straightforward and turns a program &str into a circuit::Circuit (or aborts with a scan/parse/type error). The different steps and their modules are as follows (with steps 1-4 happening during compile time, step 5 during run time):

  1. scan.rs splits a program &str into a token::Token sequence.
  2. parse.rs parses a token::Token sequence into an untyped ast::Program.
  3. check.rs type-checks an untyped ast::Program, returning a typed ast::Program.
  4. compile.rs converts a well-typed ast::Program into a circuit::Circuit.
  5. eval.rs executes a circuit::Circuit with locally supplied inputs.

Dependencies