mirror of
https://github.com/cloudflare/redoctober.git
synced 2026-02-04 12:02:32 +00:00
7e56983fa6
- Instead of using GF(2^127-1) as one of many options, move to GF(2^128) exclusively. - Don't clear the first two bits of every secret key.
135 lines
4.9 KiB
Markdown
135 lines
4.9 KiB
Markdown
Monotone Span Programs
|
|
======================
|
|
|
|
- [Introduction](#monotone-span-programs)
|
|
- [Types of Predicates](#types-of-predicates)
|
|
- [Documentation](#documentation)
|
|
- [User Databases](#user-databases)
|
|
- [Building Predicates](#building-predicates)
|
|
- [Splitting & Reconstructing Secrets](#splitting--reconstructing-secrets)
|
|
|
|
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](http://en.wikipedia.org/wiki/Shamir%27s_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
|
|
|
|
|
|
Documentation
|
|
-------------
|
|
|
|
### User Databases
|
|
|
|
```go
|
|
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
|
|
|
|
```go
|
|
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.
|
|
|
|
```go
|
|
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
|
|
|
|
```go
|
|
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:
|
|
```go
|
|
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.
|