We can use Shamir secret shares to perform MPC (Multi-party Computation). In this case, we will compute a multiplication, addition and subtraction, using \(t\) shared secrets of two values (\(a\) and \(b\)) [article]:
MPC (Multi-Party Computation) with Secret Shares |
Method
So let’s see if we can build a model where we can securely distribute value, and then get our nodes to perform the result of a calculation. None of the nodes should be able to compute the result without the help of others, and where Trent is trusted to distribute the inputs, watch the broadcasts, and then gather the results. For this we can use Shamir secret shares, and where a value can be split into t-from-n shares, and where we need \(t\) shares to rebuild our value. So, we could distribute a 2-from-3 to Bob, Alice and Eve, and they Bob and Alice, or Alice and Eve, could rebuild the value back again.
So let’s say we have two values: \(x\) and \(y\), and we want to compute \(x \times y\). We then initially start with \(n\) parties, and where we define a threshold of t (the minimum number of shares required to rebuild any value. Initially, Trent (the trusted dealer) splits the input values of \(x\) and \(y\) into shares:
\(Shares_x = x_1, x_2, ... x_n\)
\(Shares_y = y_1, y_2, ... y_n\)
Next Trent sends one share of each to each of the node, such as \(x_i\) and \(y_i\) to node \(i\). Each node then must gather at least \(t\) shares for the nodes, and then aim to add to its own share. Each node then is able to rebuild the values of \(x\) and \(y\), and then compute \(x \times y\). Trent then receives all the results back and makes a judgement on the consensus. If we have 12 nodes, then if there are at least eight nodes that are fair, the result will be the correct one.
Code
Here is the code:
package main import ( "fmt" "github.com/codahale/sss" "os" "strconv" "encoding/hex" ) func mult(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a*b; return(res) } func add(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a+b; return(res) } func sub(subset1 map[byte][]byte, subset2 map[byte][]byte) int { a_reconstructed := string(sss.Combine(subset1)) b_reconstructed := string(sss.Combine(subset2)) a,_ := strconv.Atoi(a_reconstructed) b,_ := strconv.Atoi(b_reconstructed) res:=a-b; return(res) } func get_shares(shares map[byte][]byte , k byte) map[byte][]byte { subset := make(map[byte][]byte, k) for x, y := range shares { fmt.Printf("Share:\t%d\t%s ",x,hex.EncodeToString(y)) subset[x] = y if len(subset) == int(k) { break } } fmt.Printf("\n") return(subset) } func main() { a:= "10" b:="11" n1:=5 k1:=3 argCount := len(os.Args[1:]) if (argCount>0) {a = (os.Args[1])} if (argCount>1) {b = (os.Args[2])} if (argCount>2) {k1,_ = strconv.Atoi(os.Args[3])} if (argCount>3) {n1,_ = strconv.Atoi(os.Args[4])} n := byte(n1) k := byte(k1) fmt.Printf("a:\t%s\tb: %s\n\n",a,b) fmt.Printf("Policy. Any %d from %d\n\n",k1,n1) if (k1>n1) { fmt.Printf("Cannot do this, as k greater than n") os.Exit(0) } shares1, _:= sss.Split(n, k, []byte(a)) shares2, _:= sss.Split(n, k, []byte(b)) a_subset:=get_shares(shares1,k) b_subset:=get_shares(shares2,k) res1:=mult(a_subset, b_subset) res2:=add(a_subset, b_subset) res3:=sub(a_subset, b_subset) fmt.Printf("\na*b= %d\n",res1) fmt.Printf("a+b= %d\n",res2) fmt.Printf("a-b= %d\n",res3) }
A sample run is:
a: 10 b: 11 Policy. Any 3 from 5 Share: 5 fe87 Share: 1 8bd2 Share: 2 16c7 Share: 2 e47a Share: 3 db58 Share: 4 1a9b a*b= 110 a+b= 21 a-b= -1
and:
a: 9999 b: 9998 Policy. Any 3 from 6 Share: 1 968ada76 Share: 2 44fc9b0c Share: 3 eb4f7843 Share: 4 6d4bf67a Share: 5 1cbaf095 Share: 6 3ef251e3 a*b= 99970002 a+b= 19997 a-b= 1