The Journey of a Program

In this section, we will demonstrate the life cycle of a high-level program in MP-SPDZ.

Consider the following program:

print_ln('%s', sint(123).reveal())

It entails three steps: creating a constant secret sharing, revealing it to cleartext, and outputting it. The compilation will not execute any of this. Instead, it will create a description in a format specific to MP-SPDZ. For example, reveal() triggers a call to the constructor of asm_open, which will add an object thereof to a list of instructions.

Run the following to retrieve the human-readable representation of the computation:

echo print_ln('%s', sint(123).reveal()) > Programs/Source/journey.py
./compile.py -a debug journey

This will create debug-journey-0 with the following content:

# journey-0--0
ldsi s0, 123 # 0
asm_open 3, True, c0, s0 # 1
print_reg_plain c0 # 2
print_char 10 # 3
use 0, 7, 1 # 4
# journey-0-memory-usage-1
ldmc c0, 8191 # 5
gldmc cg0, 8191 # 6
ldmint ci0, 8191 # 7
ldms s0, 8191 # 8
gldms sg0, 8191 # 9
active True # 10

The first block corresponds mostly to the program whereas the second block is more generic. More specifically:

ldsi s0, 123 # 0

ldsi loads constant values to secret registers, in this case 123 to the register s0.

asm_open 3, True, c0, s0 # 1

asm_open reveals values in secret registers to be stored in cleartext registers, in this case the content of s0 to c0. The True argument triggers a correctness check in protocols where it is available, and the 3 indicates the number of arguments to follow as the instruction is batchable, that is, it can execute any number of

print_reg_plain c0 # 2

print_reg_plain outputs constant values to the console or a file, in this case the register c0.

print_char 10 # 3

print_char outputs a character to the console or a file, in this case the ASCII code for a new line.

use 0, 7, 1 # 4

use indicates the usage of preprocessing information or similar. This allows the virtual machine to account for resources before actually executing the program. This particular call indicates 1 opening (7) of sint (0). You can see the codes in data_type and field_types at the beginning of Compiler/program.py.

ldmc c0, 8191 # 5
gldmc cg0, 8191 # 6
ldmint ci0, 8191 # 7
ldms s0, 8191 # 8
gldms sg0, 8191 # 9

These instructions read memory cells to registers, for example ldms. In this context, the purpose is to indicate the memory usage. The addresses are all 8191 because 8192 is the default size for user memory given in Compiler/config.py. If you use Array or similar data-structures, these numbers will increase accordingly.

active True # 10

active indicates whether the program is compatible with active security.

The compilation above also creates Programs/Bytecode/journey-0.bc, the hexdump output of which looks as follows:

00000000  00 00 00 00 00 00 00 02  00 00 00 00 00 00 00 7b  |...............{|
00000010  00 00 00 00 00 00 00 a5  00 00 00 03 00 00 00 01  |................|
00000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 b3  |................|
00000030  00 00 00 00 00 00 00 00  00 00 00 b4 00 00 00 0a  |................|
00000040  00 00 00 00 00 00 00 17  00 00 00 00 00 00 00 07  |................|
00000050  00 00 00 00 00 00 00 01  00 00 00 00 00 00 00 03  |................|
00000060  00 00 00 00 00 00 00 00  00 00 1f ff 00 00 00 00  |................|
00000070  00 00 01 03 00 00 00 00  00 00 00 00 00 00 1f ff  |................|
00000080  00 00 00 00 00 00 00 ca  00 00 00 00 00 00 00 00  |................|
00000090  00 00 1f ff 00 00 00 00  00 00 00 04 00 00 00 00  |................|
000000a0  00 00 00 00 00 00 1f ff  00 00 00 00 00 00 01 04  |................|
000000b0  00 00 00 00 00 00 00 00  00 00 1f ff 00 00 00 00  |................|
000000c0  00 00 00 e9 00 00 00 01                           |........|
000000c8

It consist of the instructions codes and the arguments in big-endian order. For example, 0x2 is the code for lsdi, 0xa5 is the code for asm_open, 0xb3 is the code for print_reg_plain, etc. You can also spot repeated occurrences of 1f ff, which is the hexadecimal representation of 8191.

Finally, the compilation creates Programs/Schedules/journey.sch, which is a text file:

1
1
journey-0:11
1 0
0
./compile.py journey
lgp:0
opts:
sec:40

The first two lines indicate the number of threads and bytecode files, followed by the names of bytecode files (and the number of instructions in each one). The fourth and fifth line are legacy, and the sixth indicates the compilation command line. The remaining lines indicate further options used during compilation.

Execution

We will now walk through what happens when executing the program above with Rep3 modulo \(2^{64}\). The main function in Machines/replicated-ring-party.cpp indirectly calls Machine<sint, sgf2n>::run() in Processor/Machine.hpp with sint being Rep3Share2<64>. Then, the following happens:

  1. Programs/Schedules/journey.sch is parsed load_schedule().

  2. Programs/Bytecode/journey-0.bc is parsed in Machine<sint, sgf2n>::load_program() where Program::parse(). This creates an internal representation of the code in Program::p where an Instruction object describes every instruction.

  3. Machine<sint, sgf2n>::prepare() creates a computation thread using pthread_create(), which runs thread_info<sint, sgf2n>::Main_Func() in Processor/Online-Thread.hpp.

  4. Machine<sint, sgf2n>::run() calls Machine<sint, sgf2n>::run_tape(), which signals the thread which code to run.

  5. The computation thread waits for a signal in thread_info<sint, sgf2n>::Sub_Main_Func(). Once received, it calls Program::execute() in Processor/Instruction.hpp.

  6. Program::execute() runs the main loop over the instructions. There is a switch statement acting on the instruction codes.

  7. LDSI is defined in ARITHMETIC_INSTRUCTIONS in Processor/instructions.h. It calls sint::constant(), which is defined in Protocols/Rep3Share.h for Rep3Share2<64>. This is in turn calls Replicated::assign() in Protocols/Replicated.h, which creates a constant replicated secret sharing of 123, that is (123, 0) for party 0, (0, 123) for party 1, and (0, 0) for party 2.

  8. OPEN is defined in another switch statement in Instruction::execute() in Processor/Instruction.hpp, where SubProcessor::POpen() in Processor/Processor.hpp is called. This is turn uses the four-step interface of MAC_Check_Base with an instance of ReplicatedMC. The communication happens in ReplicatedMC::exchange(), and the reconstruction (summation) happens ReplicatedMC::finalize(), both in Protocols/ReplicatedMC.hpp. The remaining functions mainly handle copying data and serialization.

  9. PRINTREGPLAIN is also defined in the second switch statement, where Instruction::print() in Processor/Instruction.hpp is called. This function uses SwitchableOutput, which is used to output to console, to file, or not at all depending on the settings.

  10. PRINTCHR is defined in REGINT_INSTRUCTIONS in Processor/instructions.h, which means that it’s called via a switch statement in Instruction::execute_regint() in Processor/Instruction.cpp. It also uses SwitchableOutput.

  11. The remaining instructions are executed similarly but not do have a relevant effect.

  12. When Program::execute() is done, control returns to thread_info<sint, sgf2n>::Sub_Main_Func(), which signals completion to the main thread.

  13. After receiving the signal, Machine<sint, sgf2n>::run() completes and outputs the various statistics and exits