Skip to content

Writing a Program

Jump to bottom
Sam Kumar edited this page Mar 28, 2021 · 1 revision

This document contains a tutorial walking you through writing programs in MAGE.

Yao's Millionaires' Problem

We'll start by writing a program that uses the HalfGates (garbled circuit) protocol to solve Yao's Millionaires' problem. We'll use the existing DSL for the HalfGates protocol to write the program.

Writing the Program

A single build of MAGE has a set of built-in programs. For example, if you run ./planner, you'll see a list of programs, each followed by a short description, printed out. The easiest way to write a new program for MAGE is to build your program into MAGE, adding it to the list of programs.

The source code for programs goes in the programs/ directory. Create the file millionaire.cpp in this directory, and type (or copy and paste) the following source code:

#include "dsl/integer.hpp"
#include "dsl/util.hpp"
#include "programs/registry.hpp"
#include "programs/util.hpp"

using namespace mage::dsl;

namespace mage::programs::millionaire {
    void create_millionaire_circuit(const ProgramOptions& args) {
        Integer<32> alice_wealth;
        alice_wealth.mark_input(Party::Garbler);

        Integer<32> bob_wealth;
        bob_wealth.mark_input(Party::Evaluator);

        Bit result = (alice_wealth >= bob_wealth);
        result.mark_output();
    }

    RegisterProgram millionaire("millionaire", "Solve Yao's Millionaire's problem", create_millionaire_circuit);
}

Notice that this is the example in Figure 5 of the OSDI 2021 paper.

Explanation of the Program

The program begins the prerequisite #include statements and a using namespace statement so that we can simply write Integer instead of mage::dsl::Integer. As a convention, each program is written in its own namespace in mage::programs to avoid symbol conflicts; in this case, our chosen namespace is mage::programs::millionaire.

The create_millionaire_circuit function contains the DSL code to solve Yao's Millionaires' problem. Let's discuss how it works:

  • The Integer type represents a two's complement integer. The template argument is the length of the integer, in bits. Thus, the Integer<32> type represents a 32-bit integer. The integer itself could be signed or unsigned; the type does not specify the interpretation of those bits.

  • An Integer, regardless of its length in bits, contains only a single MAGE-virtual pointer (a single MAGE-virtual address) during the planning phase. (It is for reasons such as this that we made the length a template parameter.) Thus, while having many Integer objects in a program may take up a lot of memory during runtime, the memory overhead is significantly less while planning.

  • When an Integer object is created, it is initially in the so-called invalid state. In the invalid state, it has no runtime memory footprint. When it is initialized with a value, it enters the valid state and it begins to occupy runtime memory.

  • An Integer may be initialized by assigning it a value. This can be done via an assignment operation, or by calling a function like mark_input(). The mark_input() function reads one party's input (perhaps reading the result of oblivious transfer) and assigns the Integer to the value of the input.

  • The Bit type is simply an alias for Integer<1>.

  • The >= operator compares two integers of the same width as unsigned integers, resulting in a single bit.

  • The mark_output() function writes the value of the Integer it is called on to the program's output.

Finally, we declare a variable of type RegisterProgram. Declaring this variable adds the program to the list of programs that the planner executable knows about. The planner executable, as a result of this variable, knows that the millionaire problem, when specified on the command line, corresponds to the create_millionaire_circuit function. For example, if you run ./planner (with no command-line arguments), you will see millionaire - Solve Yao's Millionaires' problem as one line of the output. Note that the problems are listed in alphabetical order.

Running the Program

The example_input program doesn't know about the millionaire problem, so you'll have to generate input files ourself. We used Integer<32> variables in the program as each party's input, so each party's input should consist of four bytes encoding each party's wealth in little-endian two's complement form.

For example, if Alice's wealth is $1,080,000 and Bob's wealth is $1,008,000, then we should create files with the following contents (see the following examples based on the output):

$ hexdump -C millionaire_0_0_garbler.input
00000000  c0 7a 10 00                                       |.z..|
00000004
$ hexdump -C millionaire_0_0_evaluator.input
00000000  80 61 0f 00                                       |.a..|
00000004

You can use a specialized text editor, such as ghex or hexedit, to compose these files.

Once you have prepared the input files, you can run the planner by running ./planner millionaire halfgates ../config.yaml 0 0 0 and then execute the program by running ./mage halfgates ../config.yaml 0 0 millionaire_0 and ./mage halfgates ../config.yaml 1 0 millionaire_0. You can use the same config.yaml file as you used in the "Running a Program" tutorial.

In the above commands, we set the "problem size" to 0. In reality, any problem size would work, since the DSL code never uses the problem size (args.problem_size). If you use a problem size other than 0, you'll have to rename the input files to millionaire_<size>_0_garbler.input and millionaire_<size>_0_evaluator.input.

Dot Product

The above example, based on Yao's Millionaires' problem is demonstrative but simple. Now, let's move on to a more complex example: computing the dot-product of two vectors. In this case, the problem size is the dimension of the vectors.

We'll write multiple different versions of this program, in order to demonstrate different features of the DSL.

Writing the Program (First Try)

Here is the source code for the program (first cut):

#include <cstdint>
#include <vector>
#include "dsl/integer.hpp"
#include "programs/registry.hpp"
#include "programs/util.hpp"

using namespace mage::dsl;

namespace mage::programs::dot_product {
    void create_dot_product_circuit(const ProgramOptions& args) {
        std::uint64_t n = args.problem_size;
        std::vector<Integer<8>> garbler_vector(n);
        std::vector<Integer<8>> evaluator_vector(n);

        for (std::uint64_t i = 0; i != n; i++) {
            garbler_vector[i].mark_input(Party::Garbler);
            evaluator_vector[i].mark_input(Party::Evaluator);
        }

        Integer<16> result(0);
        for (std::uint64_t i = 0; i != n; i++) {
            result = result + (garbler_vector[i] * evaluator_vector[i]);
        }

        result.mark_output();
    }

    RegisterProgram dot_product("dot_product", "Compute the dot product of two vectors", create_dot_product_circuit);
}

This program is written in the simplest possible way. However, note that:

  • Because the DSL is internal to C++, you can use C++ STL data structures like std::vector.
  • For addition, the sum of two integers has the same width as those two integers; the integers wrap and the carry bit is discarded. But for multiplication, the product of two integers has double the width. So, although garbler_vector[i] and evaluator_vector[i] each have type Integer<8>, the expression garbler_vector[i] * evaluator_vector[i] has type Integer<16>.
  • In cases where the carry bit needs to be preserved even for addition, the add_with_carry method is provided. For example, if a and b have type Integer<8>, one can do Integer<9> c = a.add_with_carry(b).

If you try to run the program, the problem_size argument will determine the number of elements in each vector. So instead of choosing 0, like we did for Yao's Millionaires' problem, choose a value and make sure the input files are the appropriate length.

Writing the Program to Avoid Overflow (Second Try)

A potential issue with the program above is that the result variable may overflow. To fix this problem, we can use a larger integer width for result, and convert (garbler_vector[i] * evaluator_vector[i]) to the same (larger) integer width before adding it to result.

We can replace the create_dot_product_circuit function with the following:

void create_dot_product_circuit(const ProgramOptions& args) {
    std::uint64_t n = args.problem_size;
    std::vector<Integer<8>> garbler_vector(n);
    std::vector<Integer<8>> evaluator_vector(n);

    for (std::uint64_t i = 0; i != n; i++) {
        garbler_vector[i].mark_input(Party::Garbler);
        evaluator_vector[i].mark_input(Party::Evaluator);
    }

    Integer<64> result(0);
    for (std::uint64_t i = 0; i != n; i++) {
        Integer<64> product;
        product.mutate(garbler_vector[i] * evaluator_vector[i]);
        result = result + product;
    }

    result.mark_output();
}

The mutate function stores the same value of garbler_vector[i] * evaluator_vector[i] into the integer it is invoked on, converting the value to an Integer<64>. With this version of the function, we will get 64 bits of output, and the result won't overflow unless the input is very large.

Writing the Program to Avoid Overflow Efficiently (Third Try)

The above solution is inefficient. It performs a 64-bit addition for each element, four times the work as a 16-bit addition. We can optimize this further by adding the elements in a tree, using 16-bit addition for the bottom layer, 17-bit addition for the next layer, and so on.

Fortunately, there is a library function to help with this, as we demonstrate below:

void create_dot_product_circuit(const ProgramOptions& args) {
    std::uint64_t n = args.problem_size;
    std::vector<Integer<16>> products(n);

    for (std::uint64_t i = 0; i != n; i++) {
        Integer<8> garbler_elem;
        garbler_elem.mark_input(Party::Garbler);

        Integer<8> evaluator_elem;
        evaluator_elem.mark_input(Party::Evaluator);

        products[i] = garbler_elem * evaluator_elem;
    }

    Integer<64> result = reduce<64>(products.data(), products.size());
    result.mark_output();
}

Here, reduce is a library function provided to efficiently aggregate Integers in MAGE's DSL. This program has also made an additional optimization; rather than materializing the garbler's and evaluator's inputs in separate arrays, it computes their products as it reads their input.

It's worth mentioning that one could use the tree-based strategy to aggregate the products efficiently without materializing all of the products in memory at once. While this would likely be an improvement, it's arguably not necessary, given that MAGE will swap to storage very efficiently if the physical memory is exhausted.

Clone this wiki locally