You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by sa...@apache.org on 2020/09/28 09:39:16 UTC
[incubator-milagro-MPC] 30/30: Add reshare model
This is an automated email from the ASF dual-hosted git repository.
sandreoli pushed a commit to branch add-resharing
in repository https://gitbox.apache.org/repos/asf/incubator-milagro-MPC.git
commit 5c1ddedca1f092feb6d18e538322d7818c90d727
Author: Samuele Andreoli <sa...@yahoo.it>
AuthorDate: Mon Sep 28 10:37:02 2020 +0100
Add reshare model
TODO Add BC Setup ZKP once it is added
---
model/examples/reshare.py | 398 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 398 insertions(+)
diff --git a/model/examples/reshare.py b/model/examples/reshare.py
new file mode 100755
index 0000000..52e26c8
--- /dev/null
+++ b/model/examples/reshare.py
@@ -0,0 +1,398 @@
+#!/usr/bin/env python3
+
+import sys
+sys.path.append('../')
+
+import json
+import argparse
+
+import sec256k1.big as big
+import sec256k1.curve as curve
+import sec256k1.ecdh as ecdh
+import sec256k1.shamir as shamir
+import sec256k1.paillier as paillier
+import sec256k1.commitments as commitments
+from sec256k1 import factorization_zk as fact
+import sec256k1.mpc as mpc
+
+from Crypto.Util import number
+
+try:
+ import gensafeprime
+ has_gensafeprime = True
+except ModuleNotFoundError:
+ print("WARNING: consider installing libssl-dev and the python module gensafeprime.")
+ print(" The library safe prime generation is very inefficient and not practical for")
+ print(" integers of the size required for the ZKP. Only use low thresholds (2-3)")
+
+ has_gensafeprime = False
+
+
+def prettyvalue(value):
+ if isinstance(value, int):
+ return hex(value)[2:]
+
+ elif isinstance(value, list):
+ prettyvalues = []
+ for el in value:
+ prettyvalues.append(prettyvalue(el))
+
+ return prettyvalues
+
+ elif isinstance(value, dict):
+ prettyvalues = {}
+ for key in value.keys():
+ prettyvalues[key] = prettyvalue(value[key])
+
+ return prettyvalues
+
+ else:
+ return "{}".format(value)
+
+def dumpgame(old_players, new_players, channel):
+ game = {
+ "old_players": old_players,
+ "new_players": new_players,
+ "broadcast_channel": channel
+ }
+
+ json.dump(prettyvalue(game), open("game.json", "w"), indent=2)
+
+if __name__ == "__main__":
+ parser = argparse.ArgumentParser()
+
+ parser.add_argument('-oldn', dest='oldn', type=int, default=2,
+ help='n value for the old (t,n) MPC')
+ parser.add_argument('-oldt', dest='oldt', type=int, default=2,
+ help='t value for the old (t,n) MPC')
+
+ parser.add_argument('-newn', dest='newn', type=int, default=2,
+ help='n value for the new (t,n) MPC')
+ parser.add_argument('-newt', dest='newt', type=int, default=2,
+ help='t value for the new (t,n) MPC')
+
+ args = parser.parse_args()
+
+ oldn = args.oldn
+ oldt = args.oldt
+
+ newn = args.newn
+ newt = args.newt
+
+ print("OLD: MPC players = {}, threshold = {}".format(oldn, oldt))
+
+ # Old Players set
+ old_players = [{} for i in range(oldn)]
+
+ # Old Key Setup
+ #
+ # Simplified for the sake of this demo
+
+ # Setup ECDSA secrets and public keys
+ for player in old_players:
+ player["w_shares"] = [(0, 0) for i in range(oldn)]
+ player["w_checks"] = [[] for i in range(oldn)]
+
+ for i, player in enumerate(old_players):
+ u = big.rand(curve.r)
+
+ # VSS of u
+ u, shares, checks = shamir.make_shares(
+ oldt, oldn, check=True, secret=u)
+
+ # Transmit shares and checks to all other players.
+ #
+ # Remark. Player i MUST get all and only shares i
+ for j, recipient in enumerate(old_players):
+ recipient["w_shares"][i] = shares[j]
+ recipient["w_checks"][i] = checks
+
+ # Each player checks the consistency of all its shares and adds them
+ for i, player in enumerate(old_players):
+ for j in range(oldn):
+ ok = shamir.verify_share(
+ player["w_checks"][j],
+ player["w_shares"][j])
+
+ (x, _) = player["w_shares"][j]
+
+ assert x == i + \
+ 1, "share {} is for the wrong player {} (want {})".format(
+ j, x, i + 1)
+ assert ok, "inconsistent share {} for player {}".format(j, i)
+
+ (x_shares, y_shares) = zip(*player["w_shares"])
+ player["w_shamir"] = (x_shares[0], mpc.combine_fp_shares(y_shares))
+
+ # The Public key is the sum of the free terms in the exponent
+ #
+ # Computed for player_0, same for everyone else
+ pk_shares = [checks[0] for checks in old_players[0]["w_checks"]]
+
+ PK_old = mpc.combine_ecp_shares(pk_shares)
+
+
+ # Resharing
+ #
+ # This is the interesting part
+ print("NEW: MPC players = {}, threshold = {}".format(newn, newt))
+
+ # Preparation
+ #
+ # The old party selects oldt players to come together for the resharing
+ # The new party of newn players is formed and a threshold newt is selected
+
+ # oldt players coming together to reshare
+ resharing_players = [old_players[i] for i in range(oldt)]
+
+ # new Players set
+ new_players = [{} for i in range(newn)]
+
+ # Setup broadcast channel
+ broadcast_channel = {
+ # Old players broadcasts
+ "vss_C" : [None for i in range(oldt)],
+ "vss_r" : [None for i in range(oldt)],
+ "vss_checks": [None for i in range(oldt)],
+ # New players broadcasts
+ "paillier_PK" : [None for i in range(newn)],
+ "paillier_ZKP": [None for i in range(newn)],
+ "bc_sectup" : [None for i in range(newn)]
+ # TODO implement bc_setup ZKP
+ }
+
+ # Setup structs for ECDSA secrets and public keys
+ for player in new_players:
+ player["w_shares"] = [(0, 0) for i in range(oldt)]
+ player["w_checks"] = [[] for i in range(oldt)]
+
+ # Setup x_shares for participants
+ # These might be their index in the player set
+ x_s = []
+ for player in resharing_players:
+ (x, _) = player["w_shares"][0]
+ x_s.append(x)
+
+ # Phase 1.
+ #
+ # The old players convert their SSS shares to additive shares and perform
+ # a VSS(newt, newn) on them.
+ # Then a commitment to the VSS checks is generated and broadcasted to the new players.
+
+ # Old players generate a (newn, newt) sharing of their shares
+ for i, player in enumerate(resharing_players):
+ u = shamir.convert_to_additive_share(
+ x_s, i, player["w_shamir"][1])
+
+ # VSS of u
+ u, shares, checks = shamir.make_shares(
+ newt, newn, check=True, secret=u)
+
+ # Commit to the VSS checks
+ # Committing to all checks in one go, but e could even commit separately
+ # since the commitment and verification are really cheap (few ns)
+ # TODO decide on an encoding. Since these are ECP we could even keep
+ # the points as are in uncompressed form, as long as they validate on
+ # arrival and are the correct amount.
+ checks_bytes = ".".join([str(check) for check in checks]).encode('utf-8')
+ all_checks = big.from_bytes(checks_bytes)
+ r, C = commitments.commit(all_checks, len(checks_bytes))
+
+ # Store r, shares and checks for later
+ player["vss_r"] = r
+ player["vss_checks"] = checks
+ player["vss_shares"] = shares
+
+ # Broadcast commitment
+ broadcast_channel["vss_C"][i] = C
+
+
+ # Phase 2.
+ #
+ # The new players generate Paillier key material and the additional modulus for the
+ # MTA ZKPs. Then ZKP of their well formedness are generated
+ # The Paillier PK and modulus for the ZKPs are broadcasted with the proofs of well formedness
+
+ # Setup Paillier keys for participants
+ for i, player in enumerate(new_players):
+ # Paillier Setup
+ p = number.getStrongPrime(1024)
+ q = number.getStrongPrime(1024)
+
+ n, g, lp, lq, mp, mq = paillier.keys(p, q)
+
+ player["p"] = p
+ player["q"] = q
+ player["n"] = n
+ player["g"] = g
+ player["lp"] = lp
+ player["mp"] = mp
+ player["lq"] = lq
+ player["mq"] = mq
+
+ # ZKP of knowledge of factoring of Paillier PK
+ #
+ # Leaving ID empty for demo. In reality it ill have whatever value
+ # we use for that.
+ ID = b""
+
+ Zi = fact.nizk_setup(n)
+ e,y = fact.nizk_prove(n,p,q,Zi,ID)
+
+ # BC Setup
+
+ # Workaround to avoid using the very slow code from the python library.
+ # This is more in line with openssl and the C library iirc
+ if has_gensafeprime:
+ P = gensafeprime.generate(1024)
+ Q = gensafeprime.generate(1024)
+
+ P, Q, pq, N, alpha, ialpha, b0, b1 = commitments.bc_setup(2048,P=P,Q=Q)
+ player["bc_p"] = P
+ player["bc_q"] = Q
+ player["bc_pq"] = pq
+ player["bc_n"] = N
+ player["bc_alpha"] = alpha
+ player["bc_ialpha"] = ialpha
+ player["bc_b0"] = b0
+ player["bc_b1"] = b1
+
+ # Broadcast paillier PK
+ # Only broadcasting n since g = n+1
+ broadcast_channel["paillier_PK"][i] = n
+
+ # Broadcast paillier ZKP
+ broadcast_channel["paillier_ZKP"][i] = {
+ "e": e,
+ "y": y
+ }
+
+ # Broadcast BC setup
+ broadcast_channel["bc_setup"] = {
+ "bc_n" : N,
+ "bc_b0": b0,
+ "bc_b1": b1
+ }
+
+
+ # Phase 3.
+ #
+ # The old players send the shares to the intended recipients using the point to point
+ # secure channel.
+ # The old players decommit the VSS checks using the broadcast channel
+
+ for i, player in enumerate(resharing_players):
+ # Transmit shares to all other players using the point 2 point channel
+ #
+ # Remark. Player i MUST get all and only shares i
+ for j, recipient in enumerate(new_players):
+ recipient["w_shares"][i] = player["vss_shares"][j]
+
+ # Decommit VSS checks using broadcast channel
+ broadcast_channel["vss_checks"][i] = player["vss_checks"]
+ broadcast_channel["vss_r"][i] = player["vss_r"]
+
+ # Phase 4.
+ #
+ # The new players verify the key material received in Phase 2
+ # The new players verify the decommited VSS checks
+ # The new players verify the received shares with the VSS checks
+ # The new players reconcile the received shares by adding them
+ # The new players reconcile the public key by adding the checks and validate it
+
+ # Common Verification - only done in one pass for demo purposes.
+ # It should be performed by each player, only skipping their own proofs
+ for i in range(newn):
+ # Verify Paillier PK
+ ID = b""
+ paillier_pk = broadcast_channel["paillier_PK"][i]
+ paillier_zkp = broadcast_channel["paillier_ZKP"][i]
+ zi = fact.nizk_setup(paillier_pk)
+ paillier_ok = fact.nizk_verify(zi,paillier_pk,paillier_zkp["e"],paillier_zkp["y"],ID)
+
+ assert paillier_ok, "Paillier PK invalid for player {}".format(i)
+
+ # Verify BC Setup
+ # TODO when BC Setup ZKP is implemented
+
+ for i in range(oldt):
+ # Decommit VSS checks
+ checks = broadcast_channel["vss_checks"][i]
+ C = broadcast_channel["vss_C"][i]
+ r = broadcast_channel["vss_r"][i]
+
+ checks_bytes = ".".join([str(check) for check in checks]).encode('utf-8')
+ all_checks = big.from_bytes(checks_bytes)
+
+ ok_decommit = commitments.decommit(C,r,all_checks, len(checks_bytes))
+
+ assert ok_decommit, "Decommitment invalid for player {}".format(i)
+
+ # End of Common Verification
+
+ # Each player checks the consistency of all its shares and make a shamir reconciliation on them
+ for i, player in enumerate(new_players):
+ for j in range(oldt):
+ ok = shamir.verify_share(
+ broadcast_channel["vss_checks"][j],
+ player["w_shares"][j])
+
+ (x, _) = player["w_shares"][j]
+
+ assert x == i + \
+ 1, "share {} is for the wrong player {} (want {})".format(
+ j, x, i + 1)
+ assert ok, "inconsistent share {} for player {}".format(j, i)
+
+ (x_shares, y_shares) = zip(*player["w_shares"])
+ player["w_shamir"] = (x_shares[0], mpc.combine_fp_shares(y_shares))
+
+ # The Public key is the sum of the free terms in the exponent
+ #
+ # Computed for player_0, same for everyone else
+ pk_shares = [checks[0] for checks in broadcast_channel["vss_checks"]]
+
+ PK_new = mpc.combine_ecp_shares(pk_shares)
+
+ assert PK_new == PK_old
+
+ # At this point the new players should acknowledge the dance went correctly
+
+ # Check that both secrets are the same
+ #
+ # This is only done as an extra check in this demo.
+ # In the actual protocol only the PK is checked
+ old_shares = [player["w_shamir"] for player in resharing_players]
+
+ new_shares = [player["w_shamir"] for player in new_players[:newt]]
+
+ (old_x_shares, old_y_shares) = zip(*old_shares)
+ (new_x_shares, new_y_shares) = zip(*new_shares)
+
+ old_coefs = shamir.lagrange_interpolate1(old_x_shares)
+ old_s, _ = shamir.lagrange_interpolate2(old_coefs, old_y_shares)
+
+ new_coefs = shamir.lagrange_interpolate1(new_x_shares)
+ new_s, _ = shamir.lagrange_interpolate2(new_coefs, new_y_shares)
+
+ assert old_s == new_s, "old_s != new_s\n{} != {}".format(hex(old_s)[2:], hex(new_s)[2:])
+
+ # Phase 5.
+ #
+ # The new players save the shares while the old ones delete theirs.
+
+ for player in resharing_players:
+ player["w_shamir"] = None
+
+ for player in new_players:
+ _ = None
+ # Save Data for persistent storage
+ #
+ # * All Players Paillier PK
+ # * All Players BC Setup
+ # * Own BC Setup with safe primes
+ # * Own Paillier KeyPair
+ # * Own SK Share
+
+ # Dump game for inspection
+ dumpgame(old_players, new_players, broadcast_channel)