circuit.go

package garbled

import (
	"bytes"
	cryptoUtil "crycomp/internal/crypto/util"
	"crycomp/internal/util"
	"crypto/rand"
	"crypto/sha256"
	"errors"
	"fmt"
)

// Table contains the random or encoded strings of bit-length k.
type Table struct {
	// data contains the raw byte data this table holds.
	data []byte
	// rows is the number of rows in data (not length).
	// Normally this is the numbe of wires the table was created for.
	rows int
	// cols is the number of strings in each row. E.g the two input
	// keys (K_0^i, K_1^i)
	cols int
	// valueLen contains the string length (of each value). This is always k/8.
	valueLen int
}

// NewTable returns a new garbled table with n rows and each row containing numValues columns.
// Each value contains k/8 bytes. k must be a multiple of 8.
func NewTable(n, numValues, k int) (t *Table, err error) {
	if k%8 != 0 {
		return nil, errors.New("k must be multiple of 8")
	}
	t = &Table{
		data:     make([]byte, n*numValues*k/8),
		rows:     n,
		cols:     numValues,
		valueLen: k / 8,
	}
	return
}

// index returns the data index for row i and column j.
func (t *Table) index(r, c int) int {
	return r*t.cols*t.valueLen + c*t.valueLen
}

// // SetValue sets the byte string value at row i and column j.
// func (t *Table) SetValue(r, c int, data []byte) error {
// 	if len(data) != t.valueLen {
// 		return errors.New("data have invalid length")
// 	}
// 	index := t.index(r, c)
// 	copy(t.data[index:index+t.valueLen], data)
// 	return nil
// }

// GetValue returns a byte slice containing the value at row i and column j.
func (t *Table) GetValue(r, c int) []byte {
	index := t.index(r, c)
	return t.data[index : index+t.valueLen]
}

func (t *Table) SetRow(r int, data []byte) {
	if len(data) != t.cols*t.valueLen {
		panic("data have invalid length")
	}
	index := t.index(r, 0)
	copy(t.data[index:index+t.cols*t.valueLen], data)
}

func (t *Table) GetRow(r int) []byte {
	index := t.index(r, 0)
	return t.data[index : index+t.cols*t.valueLen]
}

// func (t *Table) SetValueOld(data []byte, i, s int) {
// 	valStart := i*t.valueLen + s*t.valueLen
// 	copy(t.data[valStart:valStart+t.valueLen], data)
// }

// func (t *Table) GetValueOld(i, s int) []byte {
// 	valStart := i*t.valueLen + s*t.valueLen
// 	return t.data[valStart : valStart+t.valueLen]
// }

// func (t *Table) SetRowOld(data [][]byte, i int) {
// 	for j, val := range data {
// 		t.SetValueOld(val, i, j)
// 	}
// }

// func (t *Table) GetRowOld(i int) [][]byte {
// 	values := make([][]byte, 0)
// 	for j := 0; j < t.cols; j++ {
// 		values = append(values, t.GetValueOld(i, j))
// 	}
// 	return values
// }

func (t *Table) getKFirstValues(numInputWire int) [][][]byte {
	values := make([][][]byte, 0)
	for i := 0; i < numInputWire; i++ {
		// values = append(values, t.GetRowOld(i))
	}
	return values
}

func (t *Table) randomizeTable() {
	rand.Read(t.data)
}

type GCircuit struct {
	F *Table
	E [][][]byte
	D [][]byte
}

type Protocol struct {
	G func(a, b []byte, i int) []byte
}

func NewGarbBloodCircuit() (c *GCircuit, err error) {
	p := Protocol{G}

	numInput := 6
	numWires := 11 // Includes numInput
	k_bits := 128

	// 1. Create two random strings for each wire.
	K, err := NewTable(numWires, 2, k_bits)
	if err != nil {
		return
	}
	K.randomizeTable()

	// 2. Create a garbled table for all C values (4 for each gate)
	C, err := NewTable(numWires-numInput, 4, k_bits*2)
	if err != nil {
		return
	}

	// // 1st layer are OR-gates with b input being NOT
	C.SetRow(0, p.garbleGate(K, 0, 3, 6, ORGateWithNot))
	C.SetRow(1, p.garbleGate(K, 1, 4, 7, ORGateWithNot))
	C.SetRow(2, p.garbleGate(K, 2, 5, 8, ORGateWithNot))

	C.SetRow(3, p.garbleGate(K, 6, 7, 9, ANDGate))
	C.SetRow(4, p.garbleGate(K, 8, 9, 10, ANDGate))

	c = &GCircuit{
		F: C,
		E: K.getKFirstValues(numInput),
		// D: K.GetRowOld(numWires),
	}
	return
}

//Creates a row (C_0^i, C_1^i, C_2^i ,C_3^i) for the garbled table, where
func (p *Protocol) garbleGate(K *Table, Li, Ri, out int, c func(a, b int) int) (cRow []byte) {
	cRow = make([]byte, K.valueLen*4)
	// Random permutation
	perm := cryptoUtil.Perm(4)

	// for (a,b) in {0,1} x {0,1}
	for a := 0; a <= 1; a++ {
		for b := 0; b <= 1; b++ {
			left := p.G(K.GetValue(Li, a), K.GetValue(Ri, b), out)
			right := make([]byte, K.valueLen*2)
			copy(right[:K.valueLen], K.GetValue(out, c(a, b)))
			// right = append(right, make([]byte, 16)...)

			// The index to write this value to. This depends in the row permutation.
			rowI := perm[a*2+b] * K.valueLen

			util.XOR(left, left, right) // XOR with left as destination.
			copy(cRow[rowI:rowI+K.valueLen], left)
			// cRow[rowI : rowI+K.valueLen] =
			// cVals[a*2+b] = util.XOR(left, right)
		}
	}
	return
}

func G(A, B []byte, i int) []byte {
	hash := sha256.New()
	hash.Write(A)
	hash.Write(append(B, byte(i)))
	return hash.Sum(nil)
}

func Enc(e [][][]byte, x []bool) (X [][]byte) {
	X = make([][]byte, 0)
	for i, val := range x {
		if val {
			X = append(X, e[i][1])
		} else {
			X = append(X, e[i][0])
		}
	}
	return
}

func Eval(C *Table, X [][]byte) ([]byte, error) {
	var K = X
	var res []byte
	for i := 0; i < 3; i++ {
		for j := 0; j < 4; j++ {
			// res = util.XOR(G(K[i], K[i+3], i), C.GetValueOld(i, j))
			if bytes.Equal(res[16:], make([]byte, 16)) {
				K = append(K, res[:16])
				break
			}
		}
		return nil, fmt.Errorf("Aborted while evaluating the garbled circuit, no match was found")
	}
	return K[len(K)-1], nil
}

func Decode(d [][]byte, Z []byte) bool {
	if bytes.Equal(d[0], Z) {
		return false
	} else if bytes.Equal(d[1], Z) {
		return true
	}
	//TODO: Error handling
	return false
}

////////////////////////////////////////////////////////////////
// Circuit
////////////////////////////////////////////////////////////////

type Circuit struct {
	wires      []int
	gates      []Gate
	outputWire int
	numInput   int
}

func NewCircuit(numInput int) *Circuit {
	return &Circuit{
		wires:    make([]int, numInput),
		gates:    make([]Gate, 0),
		numInput: numInput,
	}
}

func (c *Circuit) getInputWires(i int) (Li, Ri int) {
	return i, c.numInput + i
}

func (c *Circuit) AddGate(Li, Ri int, f func(a, b int) int) *Gate {
	c.wires = append(c.wires, 0)
	g := newGate(Li, Ri, len(c.wires)-1, f)
	c.gates = append(c.gates, *g)
	return g
}

type Gate struct {
	Li, Ri    int
	i         int
	truthfunc func(a, b int) int
}

func newGate(Li, Ri, i int, f func(a, b int) int) (g *Gate) {
	g.Li = Li
	g.Ri = Ri
	g.i = i
	g.truthfunc = f
	return
}

////////////////////////////////////////////////////////////////
// GATES
////////////////////////////////////////////////////////////////

func ORGate(a, b int) int {
	if a+b != 0 {
		return 1
	} else {
		return 0
	}
}

func ORGateWithNot(a, b int) int {
	if ((1 - b) + a) == 0 {
		return 0
	} else {
		return 1
	}
}

func ANDGate(a, b int) int {
	return a * b
}