renproject / mpc Goto Github PK
View Code? Open in Web Editor NEWLicense: GNU General Public License v3.0
License: GNU General Public License v3.0
Currently mpc
uses outdated versions of shamir
and surge
. More recent versions should be used.
surge
updatedshamir
updatedCould 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?
This issue describes the inversion primitive for SMPC.
Inversion takes a shared secret and produces shares of the multiplicative inverse of that secret. The inputs and outputs are the following.
a
a
, i.e. a^{-1}
r
P_i
's share of a
is denoted a_i
.P_i
's share of r
is denoted r_i
.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}
.
a_i
and r_i
to obtain the output value c
.b_i = c^{-1} *r_i
.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.
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
.
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.
Init
state signifies that the RKPGer
is in the initialised stateWaitingRNG
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 machinesRNGsReady
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 generationWaitingRZG
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 machinesWaitingOpen
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
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 numbersNew
// 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()
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.
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:
We can change the approach later if we find it necessary/useful to make progress on a per batch basis.
The following is a rough outline of the changes that will need to be made to the state machine.
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 Commitment
s 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.
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:
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.
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.
Naturally, some changes will also need to be made to the tests. The main ones are:
Given the above, the following tasks should be completed:
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.
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:
n
directed opens, one for each of the final shares.RNG will be implemented as a state machine as follows.
k
shares from BRNG, transition to WaitingOpen and construct the messages for the directed opens as per the protocol.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).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
.
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
.
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 curveh
is a random point, termed the Pedersen parametert_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
Player P_i
's MulOpener
is initialised/reset with:
batchSize
k
(common for all secret-sharing schemes)[(i, a_i, ρ_i), ]
for a batch of secrets [a, ]
[(i, b_i, σ_i), ]
for a batch of secrets [b, ]
[C_a, ]
for the secrets [a, ]
[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}})
TODO
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
:
A
such that A = g^a . h^ρ
B
such that B = g^b . h^σ
C
such that C = g^(ab) . h^τ
d
, s
, x
, s_1
, s_2
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
e
from verifier V
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.
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.
Open will work like a state machine as follows.
c
, k
, i
)c
)c
and reconstruction threshold k
for a specific verifiable sharing, transition to Waiting (c
, k
, 0
).c
, k
, i
): on receiving a share that is invalid with respect to c
, do nothing.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.c
, k
, i
), i < k - 1
: on receiving a share that is valid with respect to c
, transition to Waiting (c
, k
, i+1
).c
): on receiving a share, do nothing, but possibly report the validity of the share with respect to c
.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
.
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.
The rough outline of the BRNG protocol is as follows.
t+1
of these sharings.BRNG will work like a state machine as follows.
k
and batch quantity b
, transition to waiting and generate b
verifiable k
-sharings of b
random numbers as output.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).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.
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.
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.
table.go
file to table
subpackage (might be good to have separate files for each Sharing
, Row
, etc.table
subpackageA declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.