Currently the Table and related structures are defined in the brng package. These should be moved to their own table subpackage. This will encourage good use of these structures by the brng structures, and better separate the tests.

• Migrate table.go file to table subpackage (might be good to have separate files for each Sharing, Row, etc.
• Unit tests for table subpackage

Random number generation (RNG) is an extension of BRNG that results in each party holding unbiased shares of a random number, unknown to all parties. The implementation should include batching functionality.

Protocol

The protocol will be as in the paper, with the modification that the implementation will instead accept the k shares generated during the k calls to BRNG, as opposed to executing the calls to BRNG within an instance of RNG. The protocol steps for the implementation will therefore be:

1. Upon receiving the input shares (generated from BRNG), perform the local arithmetic to obtain the shares of shares.
2. Perform in parallel n directed opens, one for each of the final shares.

State Machine

RNG will be implemented as a state machine as follows.

States

• Init
• WaitingOpen
• Done

Transitions

• Init: on receiving k shares from BRNG, transition to WaitingOpen and construct the messages for the directed opens as per the protocol.
• WaitingOpen: on receiving k valid shares from the directed open step in the protocol, transition to Done and output the corresponding share (runs the Open state machine as a sub-state machine).

The current Opener only opens one sharing at a time. However, some protocols, such as RNG, will want to process batches of sharings at a time, so we should upgrade the Opener to be able to open batches of sharings so that it can be used in these contexts.

Batch Processing Philosophy

When receiving multiple shares at once, we now have the possibility that some of the shares are valid and others are not. In this case it is theoretically possible to make progress in those batches for which the shares are valid, while not doing so for the batches corresponding to the invalid shares. However, initially we should simply consider validity at a collective level: if one of the shares in any of the batches is invalid, we will treat the state transition as the failure case and not add any of the shares, even the valid ones. The reasons for this are:

• Under the security assumptions, this should not change whether or not an open will eventually be completed successfully.
• This makes the logic much simpler and therefore less error prone.

We can change the approach later if we find it necessary/useful to make progress on a per batch basis.

Outline of Changes Required

The following is a rough outline of the changes that will need to be made to the state machine.

State

The state machine will need to be aware of the batch size b. This can be considered fixed and given at construction time. Additionally, the other state will of course need to be changed to accommodate the fact that there is more than one sharing now: the commitment field will now need to be a list of Commitments and the shareBuffer field will now need to be a list of Shares. This will in turn require that the secret field is also a list.

Transitioning on Shares

The TransitionShare will now need to receive a list of shares based on the batch size. This also introduces new validity checks that need to be made:

• The list of shares received needs to have length equal to the batch size for the state machine.
• Each share has the same index.

Note that in the current case of a single share, the return value of TransitionShare is enough to precisely characterise the nature of the error, if there is any. However, in the batched case this would not be able to tell us which of the shares were invalid. We won't worry about this at the moment, as the caller will still have enough information to identify exactly who behaved maliciously (by e.g. simply iterating through the list of shares and checking for themselves which ones are the culprits). However, we can change the interface at a later date to give more accurate information.

Transitioning on Commitments (Reset)

We will also require consistency among the given list of commitments for a reset transition; each commitment should have the same k (reconstruction threshold) value. Again this is for simplicity and can be made more flexible at a later date if desired.

Tests

Naturally, some changes will also need to be made to the tests. The main ones are:

• Randomising over the number of batches
• In tests that currently test behaviour on receiving an invalid share, this now needs to be replaced with an invalid list of shares. This invalid list of shares must have at least one invalid share but the number of invalid shares should be otherwise random.

Tasks

Given the above, the following tasks should be completed:

• Adjust the state variables of the state machine to be able to handle batches
• Update the transition functions to have the correct interfaces and perform the new validity checks
• Update any auxiliary methods for the state machine as required
• Update any documentation that becomes outdated due to the changes
• Update the tests to adhere to the new changes and add any new test cases that are needed to keep the current code and logical coverage

Currently mpc uses outdated versions of shamir and surge. More recent versions should be used.

• surge updated
• shamir updated

This issue specifies the need of the mpc primitive of opening a shared secret, where the secret is shared using a verifiable secret sharing scheme based on Shamir secret sharing.

State Machine

Open will work like a state machine as follows.

States

• Uninitialised
• Waiting (c, k, i)
• Done (c)

Transitions

• Any state: on receiving a reset message that contains a commitment c and reconstruction threshold k for a specific verifiable sharing, transition to Waiting (c, k, 0).
• Uninitialised: on receiving a share, do nothing.
• Waiting (c, k, i): on receiving a share that is invalid with respect to c, do nothing.
• Waiting (c, k, k - 1): on receiving a share that is valid with respect to c, transition to Done (c) and report the reconstructed secret using the k valid shares that have been received.
• Waiting (c, k, i), i < k - 1: on receiving a share that is valid with respect to c, transition to Waiting (c, k, i+1).
• Done (c): on receiving a share, do nothing, but possibly report the validity of the share with respect to c.

Building on past experience with implementing and debugging mpc systems, we would like to make this process easier. Specifically, we would like to have a testing framework such that when a bug is noticed, it is easy to reproduce and determine the root cause.

Design

A testing framework for mpc will always need to approximate a network to simulate message sending and delivery. To facilitate reproducibility, it should be possible to have the network driven in a deterministic fashion. To achieve this, the network should operate by having a global message buffer containing all messages, and these messages are delivered one after the other. This will enable the running of test cases where players in the mpc network receive messages in a specific predetermined order. Thus if it is thought that a certain sequence of messages is causing a bug, this can be tested explicitly. Additionally, the framework should have the ability to record the history of messages in the order they were consumed, and be able to save this to a file when desired so that in a debugging session a user may load this specific message history and play it over as many times as desired while inspecting the operation of the mpc algorithm. This should enable easier debugging.

Minimum Requirements

• Network functionality that can be loaded with a given specific of messages that determines what messages are delivered to who and in what order.
• The ability to record, save, and load a message history from a given run of the network.
• Debugger that can be loaded with messages and a set of players and has basic debugging functionality; step (send next message), basic break point setting, continue to next break point, etc.

Optional Requirements

• Network functionality is general and can be easily configured to run various kinds of networks, e.g. round based, fully asynchronous, etc.
• Debugger can have complicated break point conditions that may depend on the internals of the state machines in the network.
• Any other features for the debugger that are discovered to be useful during its implementation and use.

Biased random number generation (BRNG) is one of the building blocks for the other mpc protocols. The state machine for this protocol is largely simplified by the fact that an external consensus protocol will do most of the work. We want to build in batching functionality, as it is more efficient to perform consensus on multiple instances of BRNG at once.

Protocol

The rough outline of the BRNG protocol is as follows.

1. Each party generates a random number and shares it for each other party.
2. The consensus algorithm picks a subset of at least t+1 of these sharings.
3. Each party sums up their respective shares from the selected subset.

State Machine

BRNG will work like a state machine as follows.

States

• Init
• Waiting
• Ok
• Error

Transitions

• Init: on receiving a start message that specifies a reconstruction threshold k and batch quantity b, transition to waiting and generate b verifiable k-sharings of b random numbers as output.
• Waiting: on receiving the b sets of verifiable shares from every other party, check the validity of each share using the corresponding commitments. If any of the shares are invalid, transition to Error. Otherwise, transition to Ok and output the share that is the sum of all of the shares received (including its own).

The Pedersen commitment parameter, usually denoted by h, has an assumption that is required for security: no one should know the discrete log of h with respect to g, the base point for the elliptic curve. That is, nobody should know x such that g^x = h. This of course cannot be totally ensured in the code, however it is a good idea to check against some basic bases. For example, it could be checked that h is not the point at infinity, and that it is not equal to g.

This issue describes the inversion primitive for SMPC.

Introduction

Inversion takes a shared secret and produces shares of the multiplicative inverse of that secret. The inputs and outputs are the following.

Inputs

• Verifiable sharing of a secret value a

Outputs

• Verifiable sharing of the multiplicative inverse of a, i.e. a^{-1}

Auxiliary Inputs

• Verifiable sharing of some unknown random number r

Definitions

• Player P_i's share of a is denoted a_i.
• Player P_i's share of r is denoted r_i.

Algorithm

The algorithm proceeds by multiplying and opening a and r, which since r is random doesn't reveal anything about a. This opened value c = a*r is then inverted to get c^{-1} which all players can do locally, and then this is multiplied by the shares of r which will produce shares of r * c^{-1} = r * a^{-1} * r^{-1} = a^{-1}.

1. All players invoke multiply and open on inputs a_i and r_i to obtain the output value c.
2. All players compute their output share as b_i = c^{-1} *r_i.

Currently, the RNG state machine constructor checks to see if the BRNG threshold (i.e. the number of curve points in a given input commitment) of each commitment in the input batch is equal to the RNG threshold (i.e. the number of coefficients in the polynomial that defines the sharing for the output of RNG). This should not be the case in practice, however, as is the case for RZG when being used for multiply and open. This is because we want the RZG shares to have a threshold of 2k-1, whereas we want the BRNG shares used to create the RZG shares to have a threshold of k.

To make the problem more concrete, consider the following simple example. Suppose n = 10 and k = 3 and a batch size of b = 1. During multiply and open, we need to use a random sharing of zero with reconstruction threshold 2k - 1 = 5. This means that we need to run RZG with 5 BRNG outputs, part of which will be 5 commitments c_1, ..., c_5. The current RZG requires that each c_i has threshold 5, whereas we would want to use BRNG outputs commitments that have the usual threshold k = 3.

Could you please add an open-source software license to your code? Check out: https://choosealicense.com/

Without a license, as it is, all your code is under copyright, which means that no one can copy, distribute or modify it. Is that what you intent?

Introduction

The Multiply and Open protocol accepts two sets of shares for two field elements a_0 and b_0, and should generate as output the product of these two secrets a_0 * b_0.

Consider two k-sharing schemes for secrets a_0 and b_0 such that:

a(x) = a_0 + a_1*x + a_2*x^2 + ... + a_{k-1}*x^{k-1}

and

b(x) = b_0 + b_1*x + b_2*x^2 + ... + b_{k-1}*x^{k-1}

are the polynomial representations.

For the product c = a_0 * b_0:

c(x) = a_0*b_0 + (a_1*b_0 + a_0*b_1)*x + ... + (a_{k-1} * b_{k-1})*x^{2k - 2}

As described above, the product polynomial is a 2k-1-sharing scheme. Hence, contrary to the k <= n constraint for Open protocol, here we require 2k - 1 <= n.

Verifiable Secret Sharing

As per Pedersen's verifiable secret sharing scheme (VSS), the commitments published for the above k-sharing schemes are:

[ g^{a_0}.h^{t_0}, g^{a_1}.h^{t_1}, ..., g^{a_{k-1}}.h^{t_{k-1}} ]

and

[ g^{b_0}.h^{r_0}, g^{b_1}.h^{r_1}, ..., g^{b_{k-1}}.h^{r_{k-1}} ]

where,

• g is the generator point of the elliptic curve
• h is a random point, termed the Pedersen parameter
• t_0, t_1, ..., t_{k-1} represents a random k-sharing (as per VSS) for a(x)
• r_0, r_1, ..., r_{k-1} represents a random k-sharing (as per VSS) for b(x)

TODO

Implementation Details

Initialisation

Player P_i's MulOpener is initialised/reset with:

• Batch size batchSize
• Reconstruction threshold k (common for all secret-sharing schemes)
• Verifiable shares [(i, a_i, ρ_i), ] for a batch of secrets [a, ]
• Verifiable shares [(i, b_i, σ_i), ] for a batch of secrets [b, ]
• Commitments [C_a, ] for the secrets [a, ]
• Commitments [C_b, ] for the secrets [b, ]
  • C is of the form:

  C_a = (g^a . h^ρ, g^a_1 . h^ρ_1, ..., g^{a_{k-1}} . h^{ρ{k-1}})
  C_b = (g^b . h^σ, g^b_1 . h^σ_1, ..., g^{b_{k-1}} . h^{σ{k-1}})
  

Algorithm

TODO

Zero Knowledge Proof

Say, prover P holds the secrets a, b, their respective de-commitments ρ, σ, along with the product a * b and the random secret τ generated to commit to the product.

In order to prove that a * b is in fact the product of a and b, prover P:

1. Constructs commitments
   • A such that A = g^a . h^ρ
   • B such that B = g^b . h^σ
   • C such that C = g^(ab) . h^τ
2. Chooses uniformly random d, s, x, s_1, s_2
3. Sends to verifier V the messages
   • M such that M = g^d . h^s
   • M_1 such that M_1 = g^x . h^s_1
   • M_2 such that M_2 = B^x . h^s_2
4. Receives e from verifier V
5. Sends to verifier V the values
   • y such that y = d + eb
   • w such that w = s + eσ
   • z such that z = x + ea
   • w_1 such that w_1 = s_1 + eρ
   • w_2 such that w_2 = s_2 + e(τ - σa)

Verifier V can now verify the proof by checking whether:

(1) g^y . h^w = M . B^e
(2) g^z . h^w_1 = M_1 . A^e
(3) B^z . h^w_2 = M_2 . C^e

The scheme we've described above is an interactive protocol. In order to augment it into a non-interactive protocol, we make use of the Fiat-Shamir transform:

e = H(A, B, C, M, M_1, M_2)

where H is a cryptographically secure hash function.

By making use of a cryptographic hash function, the prover simulates a random oracle access and uses e that can be reconstructed by the verifier. Since it's a secure hash function (one-way function), the prover could not have inverted the hash to maliciously construct the public info (commitments) or messages.

Random KeyPair Generation is the process of generating a batch b of Secp256k1 key pairs.

The RKPGer struct makes use of the RNGer struct for both random number generation as well as random zero generation.

Along with an invocation of RNG, an invocation of RZG is also done.

Protocol

When RNG is done, every player has a verifiable share (x_i, t_i) to the unbiased random number x, where x_i is the share and t_i is the de-commitment (evaluation of the random polynomial for commitment scheme). Every player also has the commitment to x, where, commitment[0] is g^(c_0).h^(t_0) (g is the generator of Secp256k1 curve and h is the random curve point used as the commitment scheme parameter. c_0, c_1... are the co-efficients representing the unbiased random number's sharing hence c_0 = x.

Players will now participate in a share-hiding opening of t_0. Every player i opens t_i + z_i, where t_i is the de-commitment from their verifiable share and z_i is their share of the random zero (Here, z_1, z_2... represent a zero-sharing).

On receiving at least k openings, a player can reconstruct t_0. Hence they can also compute g^(c_0) = commitment[0] . h^(-t_0). Since c_0 was our unbiased random secret, g^(c_0) is in fact the respective public key.

At this stage, every player reveals the pair (x_i, g^(c_0)), and players can then reconstruct x to verify that g^(c_0) does in fact match g^x.

Implementation details

Similar to RNG, RKPG will also receive BRNG outputs. The RKPG struct will have two instances of RNGer, specifically, a random number generator and a random zero generator.

State

• Init
  Init state signifies that the RKPGer is in the initialised state
• WaitingRNG
  WaitingRNG represents the state when the RKPGer is in progress constructing the unbiased random numbers, it also coincides with the RNGer's state of WaitingOpen as it waits for threshold number of openings from other machines
• RNGsReady
  RNGsReady represents the state when the RKPGer has successfully constructed a batch of unbiased random numbers and is now waiting for BRNG outputs to begin the random zero generation
• WaitingRZG
  WaitingRZG represents the state when the RKPGer has received BRNG outputs for its random zero generation and is waiting for threshold number of openings from other machines
• WaitingOpen
  WaitingOpen signifies that the RKPGer has successfully completed random zero generation. It is now participating in the share-hiding opening of the decommitment field for the batch of unbiased random numbers. This coincides with the RKPGer's opener's state of Waiting
• Done
  Done represents the state of RKPGer where it has successfully reconstructed a batch of random Secp256k1 public keys. In this state, the RKPGer can respond with the reconstructed public keys and its own verifiable shares of the corresponding unbiased random numbers

API

New

// New creates a new RKPG state machine for a given batch size
func New(
	ownIndex open.Fn,
	indices []open.Fn,
	b, k uint32,
	h curve.Point,
)

TransitionRNGShares

// TransitionRNGShares accepts the BRNG outputs for RNG, and passes them on to
// the embedded RNGer. The RKPGer transitions to WaitingRNG on success. The machine
// can also transition to a RNGsReady state for the trivial case of reconstruction
// threshold being equal to one
func (rkpger *RKPGer) TransitionRNGShares(
	setsOfShares []shamir.VerifiableShares,
	setsOfCommitments [][]shamir.Commitment,
)

TransitionRNGOpen

// TransitionRNGOpen accepts openings from other machines for reconstructing the
// unbiased random number shares. The RKPGer continues to be in the WaitingRNG
// state until reconstructing its shares, upon which it transitions to RNGsReady
func (rkpger *RKPGer) TransitionRNGOpen(
	fromIndex open.Fn,
	openings shamir.VerifiableShares,
)

TransitionRZGShares

// TransitionRZGShares accepts the BRNG outputs for RZG, and passes them on to
// the embedded RZGer. The RKPGer transitions to WaitingRZG on success. The machine
// can also transition to a WaitingOpen state for the trivial case of reconstruction
// threshold being equal to one
func (rkpger *RKPGer) TransitionRZGShares(
	setsOfShares []shamir.VerifiableShares,
	setsOfCommitments [][]shamir.Commitment,
)

TransitionRZGOpen

// TransitionRZGOpen accepts openings from other machines for reconstructing the
// random shares for zero sharing. The RKPGer continues to be in the WaitingRZG
// state until reconstructing its shares, upon which it transitions to WaitingOpen
func (rkpger *RKPGer) TransitionRZGOpen(
	fromIndex open.Fn,
	openings shamir.VerifiableShares,
)

Reset

// Reset transitions a RKPGer in any state to the Init state
func (rkpger *RKPGer) Reset()