Monotone Span Programs

Introduction
- Types of Predicates
Documentation

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

Anonymous secret generation / secret homomorphisms
Non-interactive verifiable secret sharing / distributed commitments

Documentation

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.