Version: v0.0.0-...-75dfb8e Latest Latest

This package is not in the latest version of its module.

Go to latest
Published: Nov 9, 2016 License: BSD-2-Clause Imports: 7 Imported by: 0


Monotone Span Programs

A Monotone Span Program (or MSP) is a cryptographic technique for splitting a secret into several shares that are then distributed to parties or users. (Have you heard of Shamir's Secret Sharing? It's like that.)

Unlike Shamir's Secret Sharing, MSPs allow arbitrary monotone access structures. An access structure is just a boolean predicate on a set of users that tells us whether or not that set is allowed to recover the secret. A monotone access structure is the same thing, but with the invariant that adding a user to a set will never turn the predicate's output from true to false--negations or boolean nots are disallowed.

Example: (Alice or Bob) and Carl is good, but (Alice or Bob) and !Carl is not because excluding people is rude.

MSPs are fundamental and powerful primitives. They're well-suited for distributed commitments (DC), verifiable secret sharing (VSS) and multi-party computation (MPC).

Types of Predicates

An MSP itself is a type of predicate and the reader is probably familiar with raw boolean predicates like in the example above, but another important type is a formatted boolean predicate.

Formatted boolean predicates are isomorphic to all MSPs and therefore all monotone raw boolean predicates. They're built by nesting threshold gates.

Example: Let (2, Alice, Bob, Carl) denote that at least 2 members of the set {Alice, Bob, Carl} must be present to recover the secret. Then, (2, (1, Alice, Bob), Carl) is the formatted version of (Alice or Bob) and Carl.

It is possible to convert between different types of predicates (and its one of the fundamental operations of splitting secrets with an MSP), but circuit minimization is a non-trivial and computationally complex problem. The code can do a small amount of compression, but the onus is on the user to design efficiently computable predicates.

To Do
  1. Anonymous secret generation / secret homomorphisms
  2. Non-interactive verifiable secret sharing / distributed commitments


User Databases
type UserDatabase interface {
	ValidUser(string) bool // Is this the name of an existing user?
	CanGetShare(string) bool // Can I get this user's share?
	GetShare(string) ([][]byte, error) // Retrieves a user's shares.

User databases are an abstraction over the primitive name -> share map that hopefully offer a bit more flexibility in implementing secret sharing schemes. CanGetShare(name) should be faster and less binding than GetShare(name). CanGetShare(name) may be called a large number of times, but GetShare(name) will be called the absolute minimum number of times possible.

Depending on the predicate used, a name may be associated to multiple shares of a secret, hence [][]byte as opposed to one share ([]byte).

For test/play purposes there's a cheaty implementation of UserDatabase in msp_test.go that just wraps the map[string][][]byte returned by DistributeShares(...)

Building Predicates
type Raw struct { ... }

func StringToRaw(string) (Raw, error) { ... }
func (r Raw) String() string { .. .}
func (r Raw) Formatted() Formatted { ... }

type Formatted struct { ... }

func StringToFormatted(string) (Formatted, error)
func (f Formatted) String() string

Building predicates is extremely easy--just write it out in a string and have one of the package methods parse it.

Raw predicates take the & (logical AND) and | (logical OR) operators, but are otherwise the same as discussed above. Formatted predicates are exactly the same as above--just nested threshold gates.

r1, _ := msp.StringToRaw("(Alice | Bob) & Carl")
r2, _ := msp.StringToRaw("Alice & Bob & Carl")

fmt.Printf("%v\n", r1.Formatted()) // (2, (1, Alice, Bob), Carl)
fmt.Printf("%v\n", r2.Formatted()) // (3, Alice, Bob, Carl)
Splitting & Reconstructing Secrets
type MSP Formatted

func (m MSP) DistributeShares(sec []byte, db *UserDatabase) (map[string][][]byte, error) {}
func (m MSP) RecoverSecret(db *UserDatabase) ([]byte, error) {}

To switch from predicate-mode to secret-sharing-mode, just cast your formatted predicate into an MSP something like this:

predicate := msp.StringToFormatted("(3, Alice, Bob, Carl)")
sss := msp.MSP(predicate)

Calling DistributeShares on it returns a map from a party's name to their set of shares which should be given to that party and integrated into the UserDatabase somehow. When you're ready to reconstruct the secret, you call RecoverSecret, which does some prodding about and hopefully gives you back what you put in.



Package msp implements matrix operations for elements in GF(2^128).

Polynomial fields with coefficients in GF(2)



This section is empty.


View Source
var (
	Modulus        FieldElem = []byte{135, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} // x^128 + x^7 + x^2 + x + 1
	ModulusSize    int       = 16
	ModulusBitSize int       = 128

	Zero FieldElem = []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
	One  FieldElem = []byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
View Source
var ErrNotEnoughShares = errors.New("not enough shares to recover")

ErrNotEnoughShares is returned if there aren't enough shares to decrypt the secret.


This section is empty.


type Condition

type Condition interface {
	Ok(UserDatabase) bool

type FieldElem

type FieldElem []byte

func NewFieldElem

func NewFieldElem() FieldElem

NewFieldElem returns a new zero element.

func (FieldElem) Add

func (e FieldElem) Add(f FieldElem) FieldElem

Add returns e+f.

func (FieldElem) AddM

func (e FieldElem) AddM(f FieldElem)

AddM mutates e into e+f.

func (FieldElem) Dup

func (e FieldElem) Dup() FieldElem

Dup returns a duplicate of e.

func (FieldElem) Exp

func (e FieldElem) Exp(i int) FieldElem

Exp returns e^i.

func (FieldElem) Invert

func (e FieldElem) Invert() FieldElem

Invert returns the multiplicative inverse of e.

func (FieldElem) IsOne

func (e FieldElem) IsOne() bool

func (FieldElem) IsZero

func (e FieldElem) IsZero() bool

func (FieldElem) Mul

func (e FieldElem) Mul(f FieldElem) FieldElem

Mul returns e*f.

type Formatted

type Formatted struct {
	Min   int
	Conds []Condition

func StringToFormatted

func StringToFormatted(f string) (out Formatted, err error)

func (*Formatted) Compress

func (f *Formatted) Compress()

func (Formatted) Ok

func (f Formatted) Ok(db UserDatabase) bool

func (Formatted) String

func (f Formatted) String() string

type Layer

type Layer struct {
	Conditions []Condition
	Operators  []NodeType

type MSP

type MSP Formatted

func StringToMSP

func StringToMSP(pred string) (m MSP, err error)

func (MSP) DerivePath

func (m MSP) DerivePath(db UserDatabase) (ok bool, names []string, locs []int, trace []string)

DerivePath returns the cheapest way to satisfy the MSP (the one with the minimal number of delegations).

ok: True if the MSP can be satisfied with current delegations; false if not. names: The names in the top-level threshold gate that need to be delegated. locs: The index in the treshold gate for each name. trace: All names that must be delegated for for this gate to be satisfied.

func (MSP) DistributeShares

func (m MSP) DistributeShares(sec []byte, db UserDatabase) (map[string][][]byte, error)

DistributeShares takes as input a secret and a user database and returns secret shares according to access structure described by the MSP.

func (MSP) RecoverSecret

func (m MSP) RecoverSecret(db UserDatabase) ([]byte, error)

RecoverSecret takes a user database storing secret shares as input and returns the original secret.

type Matrix

type Matrix []Row

func (Matrix) Mul

func (e Matrix) Mul(f Row) Row

Mul right-multiplies a matrix by a row.

func (Matrix) Recovery

func (e Matrix) Recovery() (Row, bool)

Recovery returns the row vector that takes this matrix to the target vector [1 0 0 ... 0].

func (Matrix) Size

func (e Matrix) Size() (int, int)

type Name

type Name struct {
	// contains filtered or unexported fields

func (Name) Ok

func (n Name) Ok(db UserDatabase) bool

type NodeType

type NodeType int // Types of node in the binary expression tree.
const (
	NodeAnd NodeType = iota

func (NodeType) Type

func (t NodeType) Type() NodeType

type Raw

type Raw struct {

	Left  Condition
	Right Condition

func StringToRaw

func StringToRaw(r string) (out Raw, err error)

func (Raw) Formatted

func (r Raw) Formatted() (out Formatted)

func (Raw) Ok

func (r Raw) Ok(db UserDatabase) bool

func (Raw) String

func (r Raw) String() string

type Row

type Row []FieldElem

func NewRow

func NewRow(s int) Row

NewRow returns a row of length s with all zero entries.

func (Row) AddM

func (e Row) AddM(f Row)

AddM adds two vectors.

func (Row) DotProduct

func (e Row) DotProduct(f Row) FieldElem

DotProduct computes the dot product of two vectors.

func (Row) Mul

func (e Row) Mul(f FieldElem) Row

func (Row) MulM

func (e Row) MulM(f FieldElem)

MulM multiplies the row by a scalar.

func (Row) Size

func (e Row) Size() int

type TraceElem

type TraceElem struct {
	// contains filtered or unexported fields

type TraceSlice

type TraceSlice []TraceElem

func (TraceSlice) Compact

func (ts TraceSlice) Compact() (index []int, names []string, trace []string)

Compact takes a trace slice and merges all of its fields.

index: Union of all locations in the slice. names: Union of all names in the slice. trace: Union of all the traces in the slice.

func (TraceSlice) Len

func (ts TraceSlice) Len() int

func (TraceSlice) Less

func (ts TraceSlice) Less(i, j int) bool

func (*TraceSlice) Pop

func (ts *TraceSlice) Pop() interface{}

func (*TraceSlice) Push

func (ts *TraceSlice) Push(te interface{})

func (TraceSlice) Swap

func (ts TraceSlice) Swap(i, j int)

type UserDatabase

type UserDatabase interface {
	ValidUser(name string) bool
	CanGetShare(name string) bool
	GetShare(name string) ([][]byte, error)

A UserDatabase is an abstraction over the name -> share map returned by the secret splitter that allows an application to only decrypt or request shares when needed, rather than re-build a partial map of known data.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL