Git Product home page Git Product logo

markkurossi / mpc Goto Github PK

View Code? Open in Web Editor NEW
92.0 5.0 22.0 9.84 MB

Secure Multi-Party Computation (MPC) with Go. This project implements secure two-party computation with Garbled circuit protocol.

Home Page: https://www.markkurossi.com/mpcl/index.html

License: MIT License

Go 99.34% Makefile 0.14% C 0.53%
multi-party-computation golang go mpc yao-millionaires garbled-circuit logical-circuits oblivious-transfer sha-256 sha-512

mpc's Introduction

mpc

Secure Multi-Party Computation with Go. This project implements secure two-party computation with Garbled circuit protocol. The main components are:

  • garbled: command-line program for running MPCL programs
  • compiler: Multi-Party Computation Language (MPCL) compiler
  • circuit: garbled circuit parser, garbler, and evaluator
  • ot: oblivious transfer library

Getting started

The easiest way to experiment with the system is to compile the garbled application and use it to evaluate MPCL programs. The garbled application takes the following command line options:

  • -O: optimization level (default 1 enabling all current optimizations).
  • -circ: compile inputs to circuit format.
  • -cpuprofile: write cpu profile to the specified file.
  • -d: enable diagnostics outputs.
  • -dot: generate Graphviz DOT output.
  • -e: specifies circuit evaluator / garbler mode. The circuit evaluator creates a TCP listener and waits for garblers to connect with computation.
  • -format: specifies circuit format for the -circ output file. Possible values are: mpclc (default), bristol.
  • -i: specifies comma-separated input values for the circuit.
  • -memprofile: write memory profile to the specified file.
  • -ssa: compile MPCL input to SSA assembly.
  • -stream: streaming mode.
  • -v: enabled verbose output.

The examples directory contains various MPCL example programs which can be executed with the garbled application. For example, here's how you can run the Yao's Millionaires' Problem which can be found from the millionaire.mpcl file:

package main

func main(a, b int64) bool {
    if a > b {
        return true
    } else {
        return false
    }
}

First, start the evaluator (these examples are run in the apps/garbled directory):

$ ./garbled -e -i 800000 examples/millionaire.mpcl
 - In1: a{1,0}i64:int64
 + In2: b{1,0}i64:int64
 - Out: %_{0,1}b1:bool1
 -  In: [800000]
Listening for connections at :8080

The evaluator's input is 800000 and it is set to the circuit inputs In2. The evaluator is now waiting for garblers to connect to the TCP port :8080.

Next, let's start the garbler:

$ ./garbled -i 750000 examples/millionaire.mpcl
 + In1: a{1,0}i64:int64
 - In2: b{1,0}i64:int64
 - Out: %_{0,1}b1:bool1
 -  In: [750000]
Result[0]: false

The garbler's input is 750000 and it is set to the circuit inputs In1. The garbler connects to the evaluator's TCP port and they run the garbled circuit protocol. At the end, garbler (and evaluator) print the result of the circuit, which is this case is single bool value Result[0]:

Result[0]: false

In our example, the evaluator's argument In2 is bound to the MPCL program's b int64 argument, and garbler's In1 to a int64. Therefore, the result of the computation is false because In1=750000 <= In2=800000. If we increase the garbler's input to 900000, we see that the result is now true since the garbler's input is now bigger than the evaluator's input:

$ ./garbled -i 900000 examples/millionaire.mpcl
 + In1: a{1,0}i64:int64
 - In2: b{1,0}i64:int64
 - Out: %_{0,1}b1:bool1
 -  In: [900000]
Result[0]: true

Ed25519 Key Generation and Signature Computation

The ed25519 directory contains Ed25519 key generation and signature computation examples.

Key Generation

$ ./garbled -stream -e -v -i 0x784db0ec4ca0cf5338249e6a09139109366dca1fac2838e5f0e5a46f0e191bae,0xd0da45d3c99e756da831d1e7d696eae3fa9fe39d3b1b2618c7ff997d17777989b5cf415b114298c8b10bed0f0eff118e43ab606ab01143151dff89171307dffa,0x44bf09357e19b1f96f9cf6d9e7d25a0e8dd62d6e0d4bba2bec4c59983c7dc84d1486677b6d8837746cd948c881913c36faeaee08e8309afac58be4757a1c544e
$ ./garbled -stream -v -i 0x57c0e59c20ac7d75ef7e3188fdd7f5876abee1cab394af8125acaca9760bb54c,0x76b42e6292f4a3dc339d208481abeb9a24e08127c7cd8dbde62abcddc0c0e6f7a0f740e756b44dae137f0e7ff8eae0ceb1a962c130fdcbe8cbee3e31ab55b8dc,0xeb83eb1f5203f5b752c96264a21ff4a27fa60cf2313f5f53c3fa96e0b52a2814b786e43a3af64b66291b5b29f432cb8d5a930e31f4e6f072a6d33b861b5b5f13 examples/ed25519/keygen.mpcl
┏━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━┳━━━━━━━━┳━━━━━━┓
┃ Op          ┃            Time ┃      % ┃ Xfer ┃
┡━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━╇━━━━━━━━╇━━━━━━┩
│ Init        │      2.039289ms │  0.00% │   0B │
│ OT Init     │    248.443521ms │  0.27% │ 21kB │
│ Peer Inputs │   10.330183787s │ 11.10% │  1MB │
│ Eval        │ 1m22.462325965s │ 88.63% │ 14GB │
│ Total       │ 1m33.042992562s │        │ 14GB │
└─────────────┴─────────────────┴────────┴──────┘
Max permanent wires: 52138674, cached circuits: 23
#gates=824319227 (XOR=529672017 XNOR=28633983 AND=265892049 OR=116232 INV=4946 xor=558306000 !xor=266013227) #w=847060405
Result[0]: 8ae64963506002e267a59665e9a2e6f9348cc159be53747894478e182ece9fcb
Result[1]: 4ded80ae09692306c9659307f522f5dba1d96e48cde9f4f6e22fb340629db76aa2bee5867d009e008b6fb85902273acda8910c9a740a788f70c28ca0a3093835
Result[2]: cd5c37f4497fd56e236aa858442b3ff90f7a6401ee2186ea18d074fe93d8f9d18b582fa47a1ee0f0a9083ddd9e262b8f3c642dfad68f667f87dddd4bec80aca3

Signature Computation

$ ./garbled -stream -e -v -i 0x46eb82a021d88960fb13388b0e76ba13b84524ffe114d7f3a728b39efc185eeaa7137132182bab7504daf200d882b787ee8b9b1c9f41be9c38fb4e0ba1aff326
$ ./garbled -stream -v -i 0x4d61726b6b7520526f737369203c6d747240696b692e66693e2068747470733a2f2f7777772e6d61726b6b75726f7373692e636f6d2f,0x5e768ad83640b43d93d6c26b34021d0a0cda6bf5eb962970554d7ab074e2f4cd49bc6fef2fa4dc2f763c1f70b751b7f03d398e8930d837130426454ea52d4449 examples/ed25519/sign.mpcl
┏━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━┳━━━━━━━━┳━━━━━━━┓
┃ Op          ┃            Time ┃      % ┃  Xfer ┃
┡━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━╇━━━━━━━━╇━━━━━━━┩
│ Init        │      1.303611ms │  0.00% │    0B │
│ OT Init     │    131.270606ms │  0.15% │  16kB │
│ Peer Inputs │    4.123998305s │  4.69% │ 667kB │
│ Eval        │ 1m23.745891208s │ 95.16% │  15GB │
│ Total       │  1m28.00246373s │        │  15GB │
└─────────────┴─────────────────┴────────┴───────┘
Max permanent wires: 53913890, cached circuits: 25
#gates=830082709 (XOR=533261481 XNOR=28815787 AND=267491441 OR=494216 INV=19784 xor=562077268 !xor=268005441) #w=853799279
Result[0]: b71a55aece64574bedd94729a9ca95a87b5fe0a587fecf50ff0238805132c1291e08cb871016cb4f3935bd45423626f61dc648a91affda3671b19d7b28e03505

Multi-Party Computation Language (MPCL)

The multi-party computation language is heavily inspired by the Go programming language, however it is not using the Go's compiler or any other related components. The compiler is an independent implementation of the relevant parts of the Go syntax.

Builtin functions

The MPCL runtime defines the following builtin functions:

  • copy(dst, src): copies the content of the array src to dst. The function returns the number of elements copied, which is the minimum of len(src) and len(dst).
  • len(value): returns the length of the value as integer:
    • array: returns the number of array elements
    • string: returns the number of bytes in the string
  • make(type, size): creates an instance of the type type with size bits.
  • native(name, arg...): calls a builtin function name with arguments arg.... The name can specify a circuit file (*.circ) or one of the following builtin functions:
    • hamming(a, b uint) computes the bitwise hamming distance between argument values
  • size(variable): returns the bit size of the argument variable.

TODO

  • Foundation
    • Circuit & garbling:
      • Oblivious transfer extensions
      • SSA variable liveness analysis must be optimized
    • TLS for garbler-evaluator protocol
    • BMR multi-party protocol
  • Compiler
    • Check that types.Rune is used consistently.
    • Incremental compiler
      • Constant folding
        • Implement using AST rewrite
        • binary expressions
        • if-blocks
        • For-loop unrolling
        • Function call and return
      • peephole optimization
        • SSA aliasing is 1:1 but amov has 2:1 relation
        • variable liveness analysis for templates
      • BitShift
    • copy() does not work on arrays which have been make():ed
    • &base[pos][i] returns the address of the first element
    • reading from *[32]int32 returns invalid values
    • Pointer handling
      • Cleanup pointer r-value handling
      • Slices are passed by value instead of by reference
      • Selecting struct members from struct pointer value
  • Streamer
    • Uninitialized variables produce unspecified values in stream mode
  • Ed25519
    • Parsing Ed25519 MPCL files
      • local variables in for-loop unrolling
    • Compound init values must be zero-padded to full size

Benchmarks and tests

Please, see the benchmarks.md file for information about various benchmarks.

mpc's People

Contributors

hextrust-0 avatar markkurossi avatar rozag avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar

mpc's Issues

String Type in mpcl

I am trying to convert a byte array to a hex string in mpcl. Here is the code from Sha256 HMAC. I saw a type defined as type stringSize string but didn't get any tests on this.

In the code below I want to convert the variable key to a string and pass it to HMAC
hmac.SumSHA256([]byte("message"), []byte("abc"))
such that it looks like this:
hmac.SumSHA256([]byte("message"), []byte(string_key))

package main


import (
	"crypto/hmac"
)

type Garbler struct {
	msg      [32]byte
	keyShare [64]byte
}

func main(g Garbler, eKeyShare [64]byte) []byte {
	var key [64]byte

	for i := 0; i < len(key); i++ {
		key[i] = g.keyShare[i] ^ eKeyShare[i]
	}

This was the code I wrote to convert byte array to hex string:
package main


import "fmt"

func main() {
	byteArray := []byte{0x48, 0x65, 0x6C, 0x6C, 0x6F} // Example byte array

	// Convert the byte array to a hexadecimal string
	var hexString string
	for _, b := range byteArray {
		hexString += byteToHexString(b)
	}

	fmt.Println(hexString)
}

func byteToHexString(b byte) string {
	hexChars := "0123456789ABCDEF"
	high := b >> 4
	low := b & 0x0F
	return string(hexChars[high]) + string(hexChars[low])
}
	

but string is not accepted by mpcl. Can we write a package that handles this conversion?

help: Possible to implement 3 party MPC?

Is it possible to implement a solution with a setup of one garbler and two evaluator, where each garbler has a 2-pc connection with each of the two evaluators, with the help of this library?

Can you give some insight on this?

`p2p.Conn.Stats` is not goroutine safe

Issue

I've been inspecting my project with go's race detector and stumbled upon a data race caused by p2p package.

Severity

It seems that the core functionality of the library is not affected by the race, but it makes it a bit harder to inspect apps that use the lib for data races because of a lot of "false positives", so to speak.

How to reproduce

Let's start with the basic garbled example:

  1. Shell 1:
    cd apps/garbled
    go run --race . -e -i 800000 examples/millionaire.mpcl
  2. Shell 2:
    cd apps/garbled
    go run --race . -i 750000 examples/millionaire.mpcl
  3. Output in Shell 1:
     - In1: a{1,0}i64:int64
     + In2: b{1,0}i64:int64
     - Out: %_{0,1}b1:bool1
     -  In: [800000]
    Listening for connections at :8080
    New connection from 127.0.0.1:61520
    p2p.NewConn
    ==================
    WARNING: DATA RACE
    Read at 0x00c00037e0e8 by main goroutine:
      github.com/markkurossi/mpc/circuit.Evaluator()
          /Users/rozag/workspace/mpc/circuit/evaluator.go:115 +0xf44
      main.evaluatorMode()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:359 +0x28d
      main.main()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:311 +0x2ce6
    
    Previous write at 0x00c00037e0e8 by goroutine 14:
      github.com/markkurossi/mpc/p2p.(*Conn).writer()
          /Users/rozag/workspace/mpc/p2p/protocol.go:94 +0x244
      github.com/markkurossi/mpc/p2p.NewConn.func1()
          /Users/rozag/workspace/mpc/p2p/protocol.go:80 +0x39
    
    Goroutine 14 (running) created at:
      github.com/markkurossi/mpc/p2p.NewConn()
          /Users/rozag/workspace/mpc/p2p/protocol.go:80 +0x304
      main.evaluatorMode()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:358 +0x244
      main.main()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:311 +0x2ce6
    ==================
    Result[0]: false
    
  4. Output in Shell 2:
     + In1: a{1,0}i64:int64
     - In2: b{1,0}i64:int64
     - Out: %_{0,1}b1:bool1
     -  In: [750000]
    p2p.NewConn
    ==================
    WARNING: DATA RACE
    Read at 0x00c000424178 by main goroutine:
      github.com/markkurossi/mpc/circuit.Garbler()
          /Users/rozag/workspace/mpc/circuit/garbler.go:139 +0xb24
      main.garblerMode()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:381 +0x13b
      main.main()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:318 +0x2eb5
    
    Previous write at 0x00c000424178 by goroutine 14:
      github.com/markkurossi/mpc/p2p.(*Conn).writer()
          /Users/rozag/workspace/mpc/p2p/protocol.go:94 +0x244
      github.com/markkurossi/mpc/p2p.NewConn.func1()
          /Users/rozag/workspace/mpc/p2p/protocol.go:80 +0x39
    
    Goroutine 14 (running) created at:
      github.com/markkurossi/mpc/p2p.NewConn()
          /Users/rozag/workspace/mpc/p2p/protocol.go:80 +0x304
      main.garblerMode()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:378 +0xb3
      main.main()
          /Users/rozag/workspace/mpc/apps/garbled/main.go:318 +0x2eb5
    ==================
    Result[0]: false
    Found 1 data race(s)
    

The root cause

It seems that the problem is that we read and write to p2p.Conn.Stats.(Sent|Recvd) without any synchronization from multiple goroutines. And one of the goroutines is the one we start in p2p.NewConn.

Proposed solution

Leverage sync/atomic.Uint64 instead of raw uint64 in p2p.IOStats.

Why the evaluator can use the original boolean circuit?

Hello developer,
From my understanding, the garbler only sends the garbled circuit, encoding information, and decoding information to the evaluator.
However, in evaluator.go and eval.go the evaluator directly uses the original circuit to compute the output.
Is there any template I can use to modify the algorithm?

undefined variable 'break'

Hello

I am going to implement modular add function.
I am facing an error regarding undefined variable 'break'
Any idea how to break the loop?

In hmac hmacsha-256.mpcl the generated result is not same as the one genearted online using same credentials

while trying the code.
i used the key given in the example ie - b598163d740b0973b8b312881bfe6601e031d33d9f15be97b0cc8898ae570932fd755ced0af309f7625f531ab01cdc0ba7130ae14b561b905f53777255174170

and the message - Hello, world!...................
the Hmac sha256 output i got online is - 8b8252a526ca8b895cd3d7749124b9d801f654fa8a4a9d515b101468de48edde which does not matches with the one result[0] in the docs
expected result - Result[0]: 60d27dbd14f1e351f20069171fead00ef557d17ac9a41d02baa488ca4b90171a

notes-
site used for computing sha256
https://www.devglan.com/online-tools/hmac-sha256-online

Help: possible to scale?

Is it possible to have potentially thousands of clients garble their shares, send it to 2 nodes to perform the mpc calculations? I would like to create a demo showing 10000 homes provide their occupancy in order to know the city's total occupancy without knowing each individual home's occupancy. Would it be possible for each home to garble their secret (occupancy - unsigned integer - and send it to 2 mpc nodes to perform the aggregation function?

How to run HMAC ?

I am new to this repo. I want to run the HMAC circuit. Can you guide how to run it?

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.