The Garble Programming Language

Garble is a simple programming language for Multi-Party Computation. Garble programs are compiled to Boolean circuits and always terminate, making them ideal for Garbled Circuits. Garble is statically typed, low-level, purely functional and uses a Rust-like syntax. Garble is much simpler than Rust though, making it easy to learn and simple to integrate into MPC engines.

// A program for solving Yao's Millionaires' problem in Garble:

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
    }
}

Garble is developed by the SINE Foundation and is open source. We developed Garble for our own MPC engine, but you can use Garble in any MPC engine that executes Boolean circuits.

A Guide to Garble

Garble is a programming language for MPC that is quite easy to learn and mostly works like Rust, except that it is much simpler and only implements a subset of Rust (without the borrow checker). The following guide introduces the main features of Garble.

A minimal Garble program is a public function (conventionally called main), with each function argument conceptually belonging to a different party in an MPC protocol based on Boolean circuits, e.g. Garbled Circuits. For example, the following program computes the Boolean and of two parties:

pub fn main(party_a: bool, party_b: bool) -> bool {
    party_a & party_b
}

The above function is a bit contrived, a more interesting example would be to compute the sum of the inputs of three parties:

pub fn main(a: u32, b: u32, c: u32) -> u32 {
    a + b + c
}

Installation

The easiest way to install the Garble compiler is using cargo install:

$ cargo install garble_lang --features="bin"
$ garble
Turing-Incomplete Programming Language for Multi-Party Computation with Garbled Circuits

Usage: garble <COMMAND>

Commands:
  run    Run the Garble program with the specified inputs
  check  Check the Garble program for any type errors
  help   Print this message or the help of the given subcommand(s)

Options:
  -h, --help     Print help
  -V, --version  Print version

If you want to test the Garble compiler with some example programs, the easiest way to do so is to clone the Garble repository and use the programs found in garble_examples:

$ git clone git@github.com:sine-fdn/garble-lang.git
$ cd garble-lang
$ garble run garble_examples/millionaires.garble.rs --function=main 10000000 10000
Richest::IsA
$ garble run garble_examples/millionaires.garble.rs --function=main 100 5000000
Richest::IsB
$ garble run garble_examples/millionaires.garble.rs --function=main 1000 1000
Richest::Tie

If a program cannot be compiled, Garble will report type errors and display the location of the error in the source code:

$ garble run garble_examples/error_examples/simple_type_error.garble.rs --function=main 0 true

Type error on line 2:5.
The operands have incompatible types; u32 vs bool:
       | pub fn main(a: u32, b: bool) -> u32 {
   2 > |     a - b
     > |     ^^^^^
       | }

Functions

Garble programs are a collection of pure functions. There are no side effects such as printing output or doing any other form of IO. Functions that are meant to be invoked as the entry points of multi-party computations must be marked public by using the pub modifier. Non-pub top-level function definitions can be used to split the program into smaller chunks:

pub fn main(x: u16) -> u16 {
    inc(x)
}

fn inc(x: u16) -> u16 {
    add(x, 1)
}

fn add(x: u16, y: u16) -> u16 {
    x + y
}

Garble will abort with an error if any of the non-pub defined functions are unused:

$ garble run garble_examples/error_examples/unused_fn.garble.rs --function=main 0
Type error on line 3:2.
Function 'inc' is declared but never used:

       | pub fn main(x: u16) -> u16 {
       |     x + 1
   3 > | }
     > |
   4 > |
     > |
   5 > | fn inc(x: u16) -> u16 {
     > | ^^^^^^^^^^^^^^^^^^^^^^^
   6 > |     add(x, 1)
     > | ^^^^^^^^^^^^^
   7 > | }
     > | ^
       |

Garble panics if an error occurs, for example if an integer overflows during an addition:

$ garble run garble_examples/calculator.garble.rs --function=main '(200, 200)' Op::Add
Panic due to Overflow on line 17:43.

       | pub fn main(values: (u8, u8), op: Op) -> OpResult {
       |     match (op, values) {
  17 > |         (Op::Add, (x, y)) => OpResult::Ok(x + y),
     > |                                           ^^^^^
       |         (Op::Sub, (x, y)) => OpResult::Ok(x - y),

Garble will also panic on integer overflows caused by other arithmetic operations (such as subtraction and multiplication), divisions by zero, and out-of-bounds array indexing.

Circuit logic for panics is always compiled into the final circuit (and includes the line and column number of the code that caused the panic), it is your responsibility to ensure that no sensitive information can be leaked by causing a panic.

Just like Rust, Garble supports both // and (nested) /* */ comments:

/*
fn unused_fn(x: ...) -> ... {
    /* nested block comment */
    // normal comment within block comment
}
*/
pub fn main(x: u16) -> u16 {
    // comment including '/*'
    x + /* ... */ 1
}

Variables and Mutability

Let bindings can be used to introduce variables, which are immutable by default:

pub fn main(a: u32, b: u32) -> u32 {
    let sum = a + b;
    let result = sum + sum;
    let result = result + result; // this shadows the existing `result` binding
    result
}

The left-hand side of left bindings is not restricted to simple variables, you can also use patterns, as long as they are irrefutable (in other words they always match). Here is an example of how to use let bindings to destructure tuples and structs:

struct FooBar {
    foo: i32,
    bar: (i32, i32),
}

pub fn main(x: (i32, i32)) -> i32 {
    let (a, b) = x;

    let bar = (0, 0);
    let foobar = FooBar { foo: 0, bar };
    let FooBar { bar, .. } = foobar;
    let (y, z) = bar;
    a + y
}

Since Garble is purely functional under the hood, it is not possible to have shared mutable state: mutable bindings (using let mut) are always restricted to the current lexical scope and any values passed to functions are copied by-value, not by-reference:

pub fn main(x: i32) -> i32 {
    let mut y = 0;
    y = x; // `y` will now be equal to `x`
    let z = inc(y);
    z // is equal to `x + 1`, but `y` is still equal to `x`
}

fn inc(mut a: i32) -> i32 {
    a = a + 1; // the value of `a` is changed only inside this function's scope
    a
}

In contrast to let, let mut does not support destructuring using patterns. The left-hand side of a let mut statement must always be a variable name.

Copying a value on every mutation might sound expensive, but this is actually not the case in a language like Garble that compiles to Boolean gates: Previous values (or more specifically, "wires" with specific Boolean values) can be freely reused, entirely or partially, because there are no memory locations, only gates and their connecting wires.

Data Types

Garble supports several primitive types: Booleans (bool), unsigned integers of different bit lengths (u8, u16, u32, u64, usize) and signed integers of different bit lengths (i8, i16, i32, i64). Note that in contrast to Rust, the type suffix of a number must sometimes be specified because Garble only supports a limited form of type inference for numbers. If no type suffix is specified and Garble cannot figure out the type, i32 will be used by default.

Primitive types support the usual logical, bitwise and arithmetic operations:

pub fn main(_a: i32, _b: i32) -> () {
    let add = 0 + 1;
    let sub = 1 - 1;
    let mul = 2 * 1;
    let div = 2 / 1;
    let rem = 5 % 2;

    let bit_xor = 4u32 ^ 6;
    let bit_and = 4u32 & 6;
    let bit_or = 4u32 | 6;
    let bit_shiftl = 4u32 << 1;
    let bit_shiftr = 4u32 >> 1;

    let and = true & false;
    let or = true | false;

    let eq = true == false;
    let neq = true != false;

    let gt = 5 > 4;
    let lt = 4 < 5;
    let gte = 5 >= 4;
    let lte = 4 <= 5;

    let unary_not = !true;
    let unary_minus = -5;
    let unary_bitflip = !5u32;
}

Just like Rust, Garble supports short forms that combine assignment and operators, e.g. a += 1 as a short form for a = a + 1:

pub fn main(_a: i32, _b: i32) -> () {
    let mut x = 0i32;
    x += 5;
    x -= 3;
    x *= 3;
    x /= 2;
    x %= 1;

    let mut x = 0u32;
    x ^= 4;
    x &= 3;
    x |= 2;
    x <<= 1;
    x >>= 1;

    let mut b = true;
    b ^= true;
    b &= true;
    b |= true;
}

Since Garble does not support automatic type coercions, it is often necessary to explicitly cast integers to the desired type:

pub fn main(a: i32, b: u32) -> i64 {
    let c = -500i64;
    a as i64 + b as i64 + c
}

Several collection types are supported: Fixed-size arrays, ranges, tuples, structs and enums. In contrast to Rust, all collection types in Garble support equality comparison (==) out of the box.

Arrays and Ranges

Arrays can be initialized either by explicitly listing all elements (which must have the same type) or by using a 'repeat expression', which repeats a single element a number of times.

pub fn main(a: u32, b: u32) -> [u32; 4] {
    let array1 = [a, b, 0u32, 1u32]; // directly listing all elements
    let array2 = [a; 4]; // `a` repeated 4 times
    array2
}

Arrays are indexed using array[index]. An element can be reassigned if the whole array has been declared as mutable by let mut. Each new let binding, no matter whether immutable or mutable, always copies the full array: As a result, mutating a single index only affects a single variable, never any other "copies" of the array. This might sound inefficient, but does not incur any performance penalty in a purely functional circuit using only Boolean gates. Consequently, there is no shared mutable state in Garble:

pub fn main(replacement: i32) -> [i32; 4] {
    let mut array1 = [10, 20, 30, 40];
    let second_val = array1[1]; // will be `20`
    let mut array2 = array1;
    array2[1] = replacement;
    let second_val1 = array1[1]; // still `20`
    let second_val2 = array2[1]; // equal to the value of `replacement`
    array2
}

Ranges are a more convenient notation for arrays of continuous numbers. They are treated by Garble as arrays and have an array type. The minimum value of a range is inclusive, the maximum value exclusive:

pub fn main(_a: i32) -> [i32; 5] {
    10..15 // equivalent to `[10, 11, 12, 13, 14]`
}

Tuples

Tuples can hold a fixed number of elements of heterogeneous types. Tuple fields are accessed using . followed by an index (without type suffix) or using let-destructuring (tuples are immutable, so it is not possible to reassign a tuple field):

pub fn main(a: i32, b: u64) -> (i32, u64, i64) {
    let sum = (a as i64) + (b as i64);
    let tuple = (a, b, sum);
    let a = tuple.0;
    let b = tuple.1;
    let sum = tuple.2;
    let (a, b, sum) = tuple;
    tuple
}

Structs

Structs must be declared as top-level types before they can be used. Note that unlike in Rust, only record-style structs (with named fields) are supported:

struct FooBar {
    foo: i32,
    bar: i32,
}

pub fn main(x: i32) -> i32 {
    let foobar = FooBar { foo: x, bar: 2 };
    foobar.bar
}

Similar to Rust, Garble offers syntactic sugar for dealing with structs. If the value of a field is a variable with the same name as the field, the value can be omitted (writing Foo { bar } instead of Foo { bar: bar }), both in patterns and in struct literals. Additionally, a subset of the fields of a struct can be matched by ignoring the remaining fields using ..:

struct FooBar {
    foo: i32,
    bar: i32,
}

pub fn main(x: (i32, i32)) -> i32 {
    let (foo, bar) = x;
    let foobar = FooBar { foo, bar };
    match foobar {
        FooBar { foo: 0, .. } => 1,
        FooBar { foo, .. } => foo,
    }
}

Just like tuples, structs are immutable, so it is not possible to reassign a struct field.

Enums

Similar to structs, enums must be declared as top-level types before they can be used and are accessed using pattern matching. Unlike in Rust, patterns must always specify the full enum variant name (e.g. EnumName::VariantName):

enum Op {
    Zero,
    Div(u8, u8),
}

enum OpResult {
    DivByZero,
    Ok(u8),
}

Fields on an enum can be accessed using pattern matching:

pub fn main(op: Op) -> OpResult {
    match op {
        Op::Zero => OpResult::Ok(0),
        Op::Div(x, 0) => OpResult::DivByZero,
        Op::Div(x, y) => OpResult::Ok(x / y),
    }
}

If/Else and Pattern Matching

Garble supports two forms of conditional control flow, if/else and pattern matching, which are both expressions and always return a value. Here's an example of if/else:

pub fn main(x: i32) -> i32 {
    if x < 0 {
        -1
    } else if x == 0 {
        0
    } else {
        1
    }
}

Here is an example of pattern matching on numbers:

pub fn main(x: i32) -> i32 {
    match x {
        0 => 1,
        x => x,
    }
}

Pattern matching is also supported for enums, structs, tuples and range literals (but not for arbitrary arrays), see the description of data types for more details. Here's how to match on an enum:

pub fn main(op: Op) -> OpResult {
    match op {
        Op::Zero => OpResult::Ok(0),
        Op::Div(x, 0) => OpResult::DivByZero,
        Op::Div(x, y) => OpResult::Ok(x / y),
    }
}

As in Rust, patterns can be nested:

fn main(x: (bool, (u8, u8))) -> i32 {
    match x {
        (false, _) => 0,
        (_, (_, 0)) => 1,
        (_, (x, y)) => (x as i32) + (y as i32) + 1,
    }
}

Garble also supports inclusive-end ranges in patterns (but only in patterns, not as array literals), using ..= instead of ..:

pub fn main(x: u8) -> u8 {
    match x {
        0..10 => 1,
        10 => 2,
        11 => 2,
        13 => 2,
        12..100 => 2,
        100..=255 => 3,
    }
}

Garble supports Rust's .. shorthand in structs, to ignore all remaining fields:

struct FooBar {
    foo: i32,
    bar: i32,
}

pub fn main(x: (i32, i32)) -> i32 {
    let (foo, bar) = x;
    let foobar = FooBar { foo, bar };
    match foobar {
        FooBar { foo: 0, .. } => 1,
        FooBar { foo, .. } => foo,
    }
}

If patterns are not exhaustive, Garble will report the missing cases:

$ garble run garble_examples/error_examples/non_exhaustive_patterns.garble.rs --function=main '(true, (0, 0))'
Type error on line 2:5.
The patterns are not exhaustive. Missing cases:

  (true, (1u8..=255u8, 1u8..=255u8))

...in expression:
       | pub fn main(x: (bool, (u8, u8))) -> i32 {
   2 > |     match x {
     > |     ^^^^^^^^^
   3 > |         (false, _) => 0,
     > | ^^^^^^^^^^^^^^^^^^^^^^^^
   4 > |         (_, (_, 0)) => 1,
     > | ^^^^^^^^^^^^^^^^^^^^^^^^^
   5 > |         (_, (0, y)) => 2,
     > | ^^^^^^^^^^^^^^^^^^^^^^^^^
   6 > |     }
     > | ^^^^^
       | }

For Loops and For-Join Loops

Just like Rust, Garble supports for loops that can iterate over a collection of values. In contrast to Rust, Garble also implements a specialized form of these loops to join together sorted collections of records. Let's look at both of these in turn:

For Loops

Garble supports for loops as the only looping / recursion construct in the language. (Calling a function recursively is a type error.) For loops can only loop over arrays:

pub fn main(_x: i32) -> i32 {
    let mut sum = 0;
    for i in [2, 4, 6, 8] {
        sum += i
    }
    sum
}

Instead of a simple loop variable you can also use destructuring:

pub fn main(_x: i32) -> i32 {
    let mut sum = 0i32;
    for (a, b) in [(2, 4), (6, 8)] {
        sum += a + b;
    }
    sum
}

Arrays in Garble always have a fixed size, Garble does not support data structures of a dynamic length. This is by design, as it disallows any form of unbounded recursion and thus enables the Garble compiler to generate fixed circuits consisting only of Boolean gates. Garble programs are thus computationally equivalent to LOOP programs, corresponding precisely to the class of primitive recursive functions.

For-Join Loops

Garble has special support for joining together two sorted arrays of tuples, by comparing their first field for equality, which can be useful to combine two data sources coming from different parties similar to a JOIN in SQL. Syntactically, for-join loops are a special case of for loops, using a built-in join function instead of an array:

let rows1 = [(0u8, 10u16), (1u8, 11u16), (2u8, 12u16)];
let rows2 = [(0u8, 5u32, 5u32), (2u8, 6u32, 6u32)];
// The arrays rows1 and rows2 will be joined based on their first field, which is of type u8.
// The tuple (1u8, 11u16) from rows1 is discarded because it cannot be joined with rows2.
for joined in join(rows1, rows2) {
    let ((id1, x), (id2, y, z)) = joined;
    // ...
}

Garble automatically joins the arrays in a for-join loop using a bitonic sorting network, more concretely implementing the paper Private Set Intersection: Are Garbled Circuits Better than Custom Protocols? without the shuffle step, which has a circuit complexity of O((m + n) * log(m + n)) instead of O(m * n) which would result from joining the arrays using nested loops.

It is your responsibility to ensure that the arrays that are joined in the loop must be sorted in ascending order! Otherwise elements might be discarded or invalid data returned.

For-join loops always join two arrays based on the first field. If you would like to compare more than one field for equality, the easiest way is to transform the sorted array so that the relevant fields are grouped together in a tuple and thus form the first field. Such a transformation will be completely optimized away by the Garble compiler, such as in the following example, which groups together the first two fields, compiled to a circuit with 0 gates:

pub fn main(arr1: [(u16, u16, u32); 8]) -> [((u16, u16), u32); 8] {
    let mut arr2 = [((0u16, 0u16), 0u32); 8];
    let mut i = 0usize;
    for elem in arr1 {
        let (a, b, c) = elem;
        arr2[i] = ((a, b), c);
        i += 1;
    }
    arr2
}

Just like normal for loops, for-join loops support destructuring:

pub fn main(rows1: [(u8, u16); 3], rows2: [(u8, u16); 3]) -> u16 {
    let mut result = 0u16;
    for ((_, a), (_, b)) in join(rows1, rows2) {
        result += a + b;
    }
    result
}

Const Parameters

To be able to generate Boolean circuits, Garble programs cannot contain any data structures with a dynamic size, such as a list whose size is only known at run time. Instead, the size of all data structures needs to be known at compile time, which can be quite limiting in practice. For example, two parties might want to compare their data sets without knowing ahead of time how many records each data set contains.

To make this easier, Garble supports const parameters, whose size is not yet known while type-checking but will only later be supplied when the program is actually compiled. This makes it possible to develop and check Garble programs without knowing the size of these values in advance. Calling these parameters "constants" might be slightly confusing, because their value is left unspecified before compilation and allows Garble to simulate a restricted form of dynamism, but since Garble is syntactically a subset of Rust and the values are indeed constants during compilation, they are declared using the const keyword.

Garble supports Boolean and integer constants, which need to be declared at the top level:

const MY_CONST: usize = PARTY_0::MY_CONST;

pub fn main(x: u16) -> u16 {
    let array = [2u16; MY_CONST];
    x + array[1]
}

Garble also supports taking the min() / max() of several constants as part of the declaration of a constant, which, for instance, can be useful to set the size of a collection to the size of the biggest collection provided by different parties:

const MY_CONST: usize = min(PARTY_0::MY_CONST, PARTY_1::MY_CONST);

pub fn main(x: u16) -> u16 {
    let array = [2; MY_CONST];
    x + array[1]
}

const MY_CONST: usize = max(PARTY_0::MY_CONST, PARTY_1::MY_CONST);

pub fn main(x: u16) -> u16 {
    let array = [2; MY_CONST];
    x + array[1]
}

Garble currently does not support type inference in const declarations, which is why you always have to use type suffixes even for simple number literals, e.g. use 2u16 instead of 2.

Garble programs can be type checked without providing concrete values for the declared constants, but all const values must be provided during compilation, using garble_lang::compile_with_constants. See MPC Engine Integration for more details.

Circuits and Termination

Garble programs are Boolean circuits consisting of a graph of logic gates, not sequentially executed programs of instructions on a von Neumann architecture with main memory and CPU. This has deep consequences for the programming style that leads to efficient Garble programs, with programs that would be efficient in "normal" programming languages resulting in highly inefficient circuits and vice versa.

Copying is Free

One example has already been mentioned in the context of arrays: Copying whole arrays in Garble is essentially free, because arrays (and their elements) are just a collection of output wires from a bunch of Boolean logic gates. Duplicating these wires does not increase the complexity of the circuit, because no additional logic gates are required.

Replacing the element at a constant index in an array with a new value is equally cheap, because the Garble compiler can just duplicate the output wires of all the other elements and only has to use the wires of the replacement element where previously the old element was being used. In contrast, replacing the element at a non-constant index (i.e. an index that depends on a runtime value) is a much more expensive operation in a Boolean circuit than it would be on a normal computer, because the Garble compiler has to generate a nested multiplexer circuit.

The following program seems to do a lot of work, but is actually just re-arranging the bits in an array, turning each element from a tuple of three values into a nested tuple. Garble optimizes the actual loop away, resulting in a program with 0 AND gates:

pub fn main(arr1: [(u16, u16, u32); 8]) -> [((u16, u16), u32); 8] {
    let mut arr2 = [((0u16, 0u16), 0u32); 8];
    let mut i = 0usize;
    for elem in arr1 {
        let (a, b, c) = elem;
        arr2[i] = ((a, b), c);
        i = i + 1usize;
    }
    arr2
}

Branching is Expensive

Here's an additional example: Let's assume that you want to implement an MPC function that on each invocation adds a value into a (fixed-size) collection of values, overwriting previous values if the buffer is full. In most languages, this could be easily done using a ring buffer and the same is possible in Garble:

pub fn main(mut arr: [u16; 500], i: usize, x: u16) -> [u16; 500] {
    arr[i % 500] = x;
    arr
}

However, Garble has no way of knowing that the above function is meant to implement a ring buffer and that the value of i will only be incremented in steps of 1 between each invocation. From the perspective of the compiler, the above code requires an array access at an arbitrary location, which requires the Garble compiler to generate a nested multiplexer circuit.

Instead of passing the parameter i as an input, we could also "shift" the whole array by 1 element, constructing a new array in the process. This would require a lot of copying in other languages, but is much more performant in Garble:

pub fn main(arr: [u16; 500], x: u16) -> [u16; 500] {
    let mut arr2 = [0u16; 500];
    arr2[0] = x;
    for i in 1usize..500usize {
        arr2[i] = arr[i - 1usize]
    }
    arr2
}

The difference in circuit size is extreme: While the first version (with i as an input parameter) is compiled to a circuit with more than 700,000 non-input gates, the second version (which shifts the entire array by one element) uses only 2 non-input gates (because the program is effectively a static transformation from input to output).

Such an example might be a bit contrived, since it is possible to infer the inputs of both parties (except for the element that is dropped from the array) from the output of the above function, defeating the purpose of MPC, which is to keep each party's input private. But it does highlight how unintuitive the computational model of pure Boolean circuits can be from the perspective of a load-and-store architecture with main memory and CPU.

Garble's Computational Model

It can be helpful to think of Garble programs as being executed on a computer with infinite memory, free copying and no garbage collection: Nothing ever goes out of scope, it is therefore trivial to reuse old values. But any form of branching or looping needs to be compiled into a circuit where each possible branch or loop invocation is "unrolled" and requires its own dedicated logic gates. In normal programming languages, looping a few additional times does not increase the program size, but in Garble programs additional gates are necessary. The size of Garble programs therefore reflects the worst case algorithm performance: While normal programming languages can return early and will often require much less time in the best or average case than in the worst case, the evaluation of Garble programs will always take constant time, because the full circuit must always be evaluated.

MPC Engine Integration

Integrating Garble into your own MPC engine is pretty straightforward. You have to know how to compile Garble programs, how to encode inputs as Garble literals, and how to understand the circuit format that the Garble compiler produces. Let's look at all of these in more detail:

Compiling Garble

You can use the garble_lang::compile function to compile source code directly into a circuit, which will return an error if there are any parse or type errors. (Or garble_lang::compile_with_constants in case you are using consts which are only provided after type checking.) It is recommended to prettify potential errors so that their location is highlighted in the source code as part of their error message:

use garble_lang::{compile, literal::Literal, token::UnsignedNumType::U32};

// Compile and type-check a simple program to add the inputs of 3 parties:
let code = "pub fn main(x: u32, y: u32, z: u32) -> u32 { x + y + z }";
let prg = compile(code).map_err(|e| e.prettify(&code)).unwrap();

The result is a garble_lang::GarbleProgram, which can be used to access the circuit field (if you want to execute the circuit using your own engine), but also exposes type information and allows you to execute the circuit directly (useful for debugging purposes):

// We can evaluate the circuit directly, useful for testing purposes:
let mut eval = prg.evaluator();
eval.set_u32(2);
eval.set_u32(4);
eval.set_u32(6);
let output = eval.run().map_err(|e| e.prettify(&code)).unwrap();
assert_eq!(u32::try_from(output).map_err(|e| e.prettify(&code)).unwrap(), 2 + 4 + 6);

Encoding Inputs As Literals

If you want to execute a circuit produced by Garble using your own MPC engine, you first need to convert your input arguments into the bit format that the Garble compiler expects. The easiest way to do this is to call .parse_arg() or .parse_literal_arg() on the garble_lang::GarbleProgram, which expects as its first argument the index of the argument in the main function:

// Inputs arguments can be parsed from strings:
let x = prg.parse_arg(0, "2").unwrap().as_bits();
let y = prg.parse_arg(1, "10").unwrap().as_bits();
let z = prg.parse_arg(2, "100").unwrap().as_bits();
let output = prg.circuit.eval(&[x, y, z]); // use your own MPC engine here instead
let result = prg.parse_output(&output).unwrap();
assert_eq!("112", result.to_string());

// Input arguments can also be constructed directly as literals:
let x = prg.literal_arg(0, Literal::NumUnsigned(2, U32)).unwrap().as_bits();
let y = prg.literal_arg(1, Literal::NumUnsigned(4, U32)).unwrap().as_bits();
let z = prg.literal_arg(2, Literal::NumUnsigned(6, U32)).unwrap().as_bits();
let output = prg.circuit.eval(&[x, y, z]); // use your own MPC engine here instead
let result = prg.parse_output(&output).unwrap();
assert_eq!(Literal::NumUnsigned(12, U32), result);

Garble's Circuit Format

Each garble_lang::circuit::Circuit consists of 3 parts:

1. input_gates, specifying how many input bits each party must provide
2. gates, XOR/AND/NOT intermediate gates (with input gates or intermediate gates as inputs)
3. output_gates, specifying which gates should be exposed as outputs (and in which order)

Conceptually, a circuit is a sequence of input or intermediate (XOR/AND/NOT) gates, with all input gates at the beginning of the sequence, followed by all intermediate gates. The index of a gate in the sequence determines its "wire". For example, in a circuit with two input gates (1 bit for party A, 1 bit for party B), followed by three intermediate gates (an XOR of the two input gates, an AND of the two input gates, and an XOR of these two intermediate XOR/AND gates), the input gates would be the wires 0 and 1, the XOR of these two input gates would be specified as Gate::Xor(0, 1) and have the wire 2, the AND of the two input gates would be specified as Gate::And(0, 1) and have the wire 3, and the XOR of the two intermediate gates would be specified as Gate::Xor(2, 3) and have the wire 4:

Input A (Wire 0) ----+----------+
                     |          |
Input B (Wire 1) ----|-----+----|-----+
                     |     |    |     |
                     +-XOR-+    |     |
        (Wire 2) =====> |       |     |
                        |       +-AND-+
        (Wire 3) =======|========> |
                        +---XOR----+
        (Wire 4) ==========> |

The input gates of different parties cannot be interleaved: Each party must supply all of their inputs before the next party's inputs can start. Consequently, a circuit with 16 input bits from party A, 8 input bits from party B and 1 input bit from party C would be specified as an input_gates field of vec![16, 8, 1].

At least 1 input bit must be specified, not just because a circuit without inputs would not be very useful, but also because the first two intermediate gates of every circuit are constant true and constant false, specified as Gate::Xor(0, 0) with wire n and Gate::Not(n) (and thus depend on the first input bit for their specifications).

(De-)Serializing Garble Values

If the optional "serde" crate feature is enabled, Garble supports serializing literal values to/from formats supported via serde. The following ABNF grammar shows how Garble literals are represented in JSON (using serde_json):

literal = "\"True\"" /
          "\"False\"" /
          "{\"NumUnsigned\":[" uint "," uint-ty "]}" /
          "{\"NumSigned\":[" int "," int-ty "]}" /
          "{\"ArrayRepeat\":[" literal "," uint "]}" /
          "{\"Array\":[" [literal *("," literal)] "]}" /
          "{\"Tuple\":[" [literal *("," literal)] "]}" /
          "{\"Enum\":[\"" string "\",\"" string "\"," variant "]}" /
          "{\"Range\":[" uint "," uint "," uint-type "]}"

uint    = 1*DIGIT

uint-ty = "\"Usize\"" /
          "\"U8\"" /
          "\"U16\"" /
          "\"U32\"" /
          "\"U64\"" /
          "\"Unspecified\""

int     = ["-"] uint

int-ty  = "\"I8\"" /
          "\"I16\"" /
          "\"I32\"" /
          "\"I64\"" /
          "\"Unspecified\""

string  = 1*ALPHA

variant = "\"Unit\"" /
          "{\"Tuple\":[" [literal *("," literal)] "]}"

Here are some example Garble literals and how they would be serialized as JSON:

Contributing

While Garble was developed by us at the SINE Foundation for the use in our MPC engine, we would love to see how you end up using Garble and are happy to accept pull requests. Garble is distributed under the MIT license and hosted on GitHub:

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 is optional and happens 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, not using any MPC or other privacy-preserving techniques.

You can also reach us at vorstand@sine.foundation.