README
¶
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
- 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.
Documentation
¶
Overview ¶
Package msp implements matrix operations for elements in GF(2^128).
Polynomial fields with coefficients in GF(2)
Index ¶
- Variables
- type Condition
- type FieldElem
- func (e FieldElem) Add(f FieldElem) FieldElem
- func (e FieldElem) AddM(f FieldElem)
- func (e FieldElem) Dup() FieldElem
- func (e FieldElem) Exp(i int) FieldElem
- func (e FieldElem) Invert() FieldElem
- func (e FieldElem) IsOne() bool
- func (e FieldElem) IsZero() bool
- func (e FieldElem) Mul(f FieldElem) FieldElem
- type Formatted
- type Layer
- type MSP
- type Matrix
- type Name
- type NodeType
- type Raw
- type Row
- type TraceElem
- type TraceSlice
- type UserDatabase
Constants ¶
This section is empty.
Variables ¶
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} )
ErrNotEnoughShares is returned if there aren't enough shares to decrypt the secret.
Functions ¶
This section is empty.
Types ¶
type Condition ¶
type Condition interface {
Ok(UserDatabase) bool
}
type FieldElem ¶
type FieldElem []byte
type Formatted ¶
func StringToFormatted ¶
func (Formatted) Ok ¶
func (f Formatted) Ok(db UserDatabase) bool
type MSP ¶
type MSP Formatted
func StringToMSP ¶
func (MSP) DerivePath ¶
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 ¶
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
type Name ¶
type Name struct {
// contains filtered or unexported fields
}
func (Name) Ok ¶
func (n Name) Ok(db UserDatabase) bool
type Row ¶
type Row []FieldElem
func (Row) DotProduct ¶
DotProduct computes the dot product of two vectors.
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 ¶
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.
Source Files