Multi-Party Computation (MPC) is a mathematical approach used in cryptography that has the ultimate goal of having a cryptographic operation computed by multiple entities while ensuring that their inputs stay private and are not shared with any third party.
MPC has a number of applications, including:
- Privacy-preserving data mining: MPC enables organizations to collaborate on data analysis without disclosing sensitive information, allowing them to identify patterns, trends, and associations while maintaining data privacy.
- Secure auctions: MPC can be used to design sealed-bid auctions where the highest bid is determined without revealing individual bids, ensuring fairness and preventing price manipulation.
- Financial services: Banks and other financial institutions can use MPC for secure trading, credit scoring, and risk assessment without exposing sensitive data.
- Secure multi-party machine learning: MPC can enable multiple organizations to train machine learning models on their combined datasets without revealing individual data points, promoting collaboration and improved model performance.
- Secure password and secret sharing: MPC can be employed to securely share and store sensitive information like passwords and cryptographic keys among multiple parties, ensuring that no single party can access the information without the others.
... and more.
Let’s understand MPC better with an example.
Three people – Karen, Richard and Melanie – share the same position in different companies and want to know the salary average of that position without sharing their salaries.
We know that Karen earns $60,000, Richard earns $70,000 and Melanie earns $80,000. The average is $70,000.
The first step is masking the input with a cryptographic function. In this case, we rewrite each salary as the sum of three values (each member knows he/she has to rewrite it as a sum of exactly three pieces). We can have infinite possibilities, but as an example:
Each participant shares just two of the three salary pieces with the other two participants, meaning none of them will totally reveal their secret to others:
Each participant sums the piece owned with the other pieces received. Thus Karen has -$10,000 , Richard has $250,000 and Melanie has -$30,000. If they share the sum of these numbers among each other, each of them can easily add up the numbers ($210,000) and, by dividing it by 3, they obtain the average salary of $70,000. They got to the required result without the need to share personal details.
Characteristics of Multi-Party Computation
This applies very well in the crypto and blockchain world as it becomes possible, for example, to have transactions signed by multiple entities without each revealing its private key. This is similar to multi-sig wallet setups, but MPC brings with it a lot of improvements and advantages.
How is this possible? Having a secret S, MPC allows to “split” the secret into n “pieces” and distribute them to the n participants of the computation. Applying this concept in the crypto space will result in having the wallet’s private key shared across different members and thus different devices. This adds an extra layer of security to the private key’s custody.
So, what are the advantages of using a wallet that leverages multi-party computation?
- It allows multiple members to manage a common wallet. Each transaction must be approved by all members or by a minimum set of them depending on the chosen configuration. In this case we use the terminology MPC wallet
k/n(kmembers onntotal members have to agree to sign a transaction, e.g2/3,3/4etc.). Having the possibility to sign a transaction when a quorum is reached is something that is already possible with a multi-sig setup, but MPC brings a lot of new possibilities. - The elimination of a single point-of-failure. Each member owns a share of the wallet's private key that he will never have to share with others (it will be seen later that this is true only in certain variants). This eliminates the single point-of-failure problem, well-known in wallets where a single entity manages/custodies the key. Each member therefore guards its key share on the device he owns.
- A high degree of configurability ( the owner can choose the number of wallet members, which cryptographic algorithm to use, etc.).
What are the cons of using an MPC Wallet?
- Members could have their own key share on internet-connected (vulnerable) devices. A possible solution could be that each member use air-gapped or offline custodial devices.
- Members may be subject to phishing and reveal their private key share.
- Performance degrades with a large number of users. Having fewer members means being more prone to risk (e.g. 3 members means an exploiter has to hack “only” 3 devices). Having many members (e.g. 30) degrades speed and performance due to latency in communication.
Multi-Party Computation vs. Multi-Sig Wallets
MPC wallets share some goals with multi-sig wallet setups. However they have some notable advantages, including:
- Key Refresh. All private key pieces shared between members can be refreshed periodically or manually, providing maximum security against attacks over a long term (accordingly to the previous example is possible to split each salary into three other different addends infinitely). In addition, it is possible to have single-use keys or keys with an expiration time (deadline).
- Flexibility. Following on from the previous point, the key refreshing mechanism is useful when the number of members of an MPC wallet change over time. Simply refreshing the key shares is relatively simple to transform an MPC wallet
k/nto an MPC Walletj/mkeeping the same secret (the wallet’s private key) and thus the same wallet address derived from the public key. - Chain-agnostic. Multi-Sig wallets are constructed and deployed to a specific network and their compatibility is limited to a very restricted number of chains. This because the signing process is made on-chain. MPC based wallets instead are designed with the goal of having the entire shared privateKey-construction process off-chain. The specific MPC protocol can implement different cryptographic mechanisms (e.g. ECDSA, EdDSA, Schnorr signatures, etc...) and this means that MPC can be compatible with a large number of blockchains.
- Recovery systems. In case a member loses their key share, recovery mechanisms can be set up in some implementations of MPC wallets. For example, all funds may be transferred to a dedicated address so funds are not lost forever. Alternatively, thanks to Threshold Signature Schemes, it is still possible to sign transactions even with only some of the key "pieces": having all the shares is not mandatory.
- Lower fees. In a multi-sig setup, each member signs and approves an on-chain transaction, whereas in MPC you first put "the pieces" together and then make a single on-chain transaction.
- Anonymous identities. Since the multi-sig works on-chain, the addresses of the wallet’s members are exposed to potential attackers. MPC only exposes a final address on the chain: all the operations that comes before the address construction are not exposed on chain.
- Role and limit management. Some MPC wallet implementations allow the owner to set limit on each wallet member's operations (e.g. limiting the volume of tokens they can transfer).
Threshold Signature Schemes
As said, MPC wallets are based on Multi-Party Computation. This technology is based on a number of different cryptographic concepts that are important to understand.
As with multi-sigs, in MPC-based systems it is possible to to have valid signatures even if not all the “pieces of the key” are retrieved from all the wallet members. Only a minimum set of them is needed, depending on the chosen configuration. This is is possible thanks to certain cryptographic threshold schemes. We will examine:
- Shamir Secret Sharing Scheme (SSSS)
- Verifiable Secret Sharing (VSS)
- Threshold Signature Scheme (TSS)
Shamir Secret Sharing Scheme (SSSS)
Shamir Secret Sharing Scheme (SSSS) is a type of homomorphic secret sharing. Indeed the SSSS uses what is called homomorphic encryption. This type of encryption allows a user to perform operations on encrypted data without decrypting it.
In this scheme there is an entity called Dealer who is responsible for generating the secret (private key) and then distributing the various pieces of the key to the n members of the MPC wallet. When there is the need to sign a transaction, all the necessary pieces must return to the dealer's hands so that the dealer can reconstruct the correct private key and sign.
Such a scheme allows the dealer to sign a transaction, generating a valid signature, from a private key reconstructed with only a minimum set of k pieces out of the total n received from the wallet members, with k < n. This minimum value is called the threshold. If only k-1 pieces (under the threshold) are retrieved from members it is impossible to reveal any secret, even partially.
One of the issues with SSSS becomes apparent: during key generation and signing the entire private key is in the hands of the Dealer, constituting a single point-of-failure.
But how is it possible to reconstruct the private key from just a few pieces?
SSSS is based on Lagrange polynomial interpolation. Therefore given a minimal set of data points (k) it succeeds in creating a polynomial curve (of degree k-1) that traverses those points and reconstructs the value in the gap between two known points.
Let's take an example. Let the secret code be S = 65 and suppose that we want reconstruct the secret with k < n shares with k = 2 and n = 10.
If we imagine S as a point on the y-axis of a plane, its coordinates will be S = (0,65). Thus:
- Introducing a random point
Ron the space we will have only one line that intersectSandR. We call this line secret line. - On that line we will have unlimited points. Let's call those points secret shares and send a secret share, except the point
S, to each of then = 10members. This distribution can happen in different ways depending on the different implementations: the Dealer can create a private channel with each entity or broadcast an encrypted version of the secret to everyone (only the correct recipient will be able to decrypt it and read the secret share). The important thing to notice is that at the end those key shares need to stay private between the dealer and the member who is the receiver. - We can find the secret line (and thus
Sby simply intersecting with the y-axis) with any two of the given secrets (points on that line). In this way we need just anyk = 2of the shares out ofn = 10.
This can be scaled to a k < n system where k = 3,4,5…. For example if k = 3 the secret line will be a secret 2-grade curve (k-1 = 2). If we will be able to retrieve only 2 secrets shares we cannot retrieve the secret curve and thus the secret: we need at least k = 3 points (shares).
With this example we can also understand how simply is the process of refreshing the secret shares keeping the same S full secret.
In conclusion SSSS encodes the "secret" (wallet's private key) as the zero-degree term of a polynomial. Then it creates key shares from the curve and "distributes" it to the various members. As mentioned, to have a correct estimation value in the gap we need minimum set of data points k, with k <= n.
Verifiable Secret Sharing (VSS)
Shamir Secret Sharing has many many variants. For example, VSS (Verifiable Secret Sharing) allows participants to verify that malicious shares are not being distributed by the Dealer thanks to a process where members verify that the piece they received is valid. A common VSS implementation is known as the Feldman VSS algorithm.
Indeed, VSS is used to verify that each member has received a consistent secret share from the Dealer with the other pieces distributed. How?
This protocol has two phases:
- Sharing phase. This phase is a little bit different from SSSS. The Dealer, after distributing the shares to members, will also broadcast commitments to the coefficients. Those are mathematical terms that members can use to verify key share’s validity.
- Validity-check phase. Each member, after receiving the private piece and the broadcasted coefficients, will verify the validity of the private share they received.
This allows recipients who have received a wrong share to issue complaints, which must be answered by the Dealer. In this case a dispute phase begins. Failure to answer complaints results in the Dealer being marked as malicious and removed from the protocol.
Another possible scenario involves an honest Dealer and a dishonest member who raises the complaint. In this phase, each entity has to convince the other parties that they are not lying.
Threshold Signature Scheme (TSS)
We learned that SSSS and VSS have a Dealer entity that knows the full secret when generating the key shares. The Dealer is also able to reconstruct the secret from the key share received in order to sign transactions.
TSS was born as an evolution of SSSS. TSS brings an important improvement with the goal of not ever having the full private key in a single place: there is no longer a single Dealer entity that knows the entire secret or is able to retrieve it when signing. The goal of TSS is accomplished thanks to two important features:
- Key generation is distributed. The total secret is now unknown for all the members, since each of them creates a key share independently. This process is called Distributed Key Generation (DKG). In this process we don’t have a single entity (e.g. the Dealer) that generates the shares for the members. Each participants acts, in turn, like a dealer. This process uses the VSS scheme, allowing each entity to be a dealer for a certain iteration.Entity A creates a secret
S(A)and using VSS splits it into pieces distributingS(AA)to himself,S(AB)to Entity B andS(AC)to Entity C. Each Entity (B and C in this iteration), in order to protect themselves against a possible malicious dealer, verifies the validity of the secret sent by A using VSS and raising complaints if needed.If no complaints are raised, it’s the turn of B. As before, B creates a secret S(B) and distributes S(BB) to himself, S(BA) to A and S(BC) to C. The same for entity C.Each entity will now combine the owned shares resulting in:Entity A knowsS(A)andS(A)'={ S(AA) , S(BA) , S(CA) }Entity B knowsS(B)andS(B)'={ S(BB) , S(AB) , S(CB) }Entity C knowsS(C)andS(C)'={ S(CC) , S(AC) , S(BC) }Each entity owns a new secret that was generated by mixing its initial secret share and other’s initial secret shares. Those new secrets (noted with ' after the symbol) are random even if 2/3 entities generated maliciously non-random polynomials. It will be random since at least one random piece is added to the sum thanks to the work of the single honest entity. - Entity A knows
S(A)andS(A)'={ S(AA) , S(BA) , S(CA) } - Entity B knows
S(B)andS(B)'={ S(BB) , S(AB) , S(CB) } - Entity C knows
S(C)andS(C)'={ S(CC) , S(AC) , S(BC) } - Signing process is distributed. Members do not have to transfer their piece of private key to anyone. In TSS each member creates a signature with the private key by obtaining a Partial Signature. Combining those partial signatures shared across members and devices will form the full signature to approve transactions. Without going too in depth into advanced mathematical topics basically one of the entities that provided a partial signature is chosen to be the aggregator. The aggregator verifies the validity of each partial signature received, since some signers can act maliciously. If all of them are valid he can compute the final signature.Note: The aggregator role is different to the Dealer's in previous schemes. The aggregator will be never able to reveal the full secret key using partial signatures or even the total signature.
Using this method will ensure the total secret will never be in the hands of a single entity at any moment. No key shares are transferred and the full private key is never fully reconstructed.
Security Concerns of Multi-Party Computation (MPC)
There are many aspects to consider regarding security in MPC. First of all, in an MPC network, wallet members may be subject to phishing, where an attacker tricks them into revealing their private key share. This is where the importance of custody of confidential information comes into play. As for wallets, it is necessary to safeguard and never reveal the private key, MPC members should store their private key shares in safe and trusted environments. Storing key shares on a vulnerable device can lead to potentially irreversible failures.
This is particularly important for MPC systems where n / n key shares are required for transaction signing, as the configuration in that case involves a minimum threshold equal to the number of wallet members. This means that the loss of even one key share results in the inability to take control of the funds. For the members, having a backup of sensitive data can be helpful in those situations.
On the other hand, increasing the number of backup copies does not necessarily mean an increase in security. The more copies of sensitive information there are, the greater the possible attack surface.
Another trade-off to consider when dealing with MPC systems is between security and performance. MPC-based wallets verify key shares or partial signatures according to different algorithms and mechanisms. The number of iterations of a specific algorithm increases as the number of members in the MPC network increases, e.g., during key generation or total signature reconstruction. Therefore, having fewer members means being more prone to risk: an MPC wallet with, for example, 3 members allows a bad actor to “only” hack 3 devices/members in order to retrieve key shares. Instead, having a large number of members (e.g. 30) lowers speed and performance due to waiting time for protocols cycles, increasing computational power needed, latency in communication, etc.
The communication channel is another important point to consider. MPC technology is based on a network of signers that are connected to the internet. It may be possible for man-in-the-middle attacks or spoofing attacks to be put in place by malicious entities. Furthermore, for MPC implementations that need all the co-signer members to be active simultaneously, a hacker could find an attack vector to perform a denial of service attack and compromise the entire MPC network.
Let’s think about a scenario where there are 3 members and 3 minimum partial signatures needed to sign a transaction. A hacker can attempt to force one or all of the co-signers to disconnect from the network, making transaction completion impossible.
One last attack vector in some MPC systems is the so-called Forget and Forgive Attack. This type of attack mostly concerns some specific implementations that do not bring sufficient controls into play when refreshing key shares.
MPC allows secret key shares to refresh while keeping the same total private key and, thus, the public key. This process can be repeated infinitely with one condition: after key refresh has been performed, the newly generated key shares must allow the creation of the same previous private key so that the public key matches the old one, otherwise the process is aborted.
The problem is that in some common MPC implementations, the entities involved will not wait for the process to complete before erasing their old key share. They only check the validity of the new share using VSS. This will allow an hacker to send newly-generated key shares to a subset of the MPC members passing their own control mechanisms. The goal is to have (in a j out of n threshold system) j entities reject it and (n - j) entities accept it. This way, the entities who accepted the new share will overwrite the previous key share.
This means that now there is a combination of old and new key shares that are not additive anymore: i.e. a valid signature cannot be issued. A possible solutions for this problem is to ensure that each party waits for the final “result” before deleting its old key share by implementing back-channel communication mechanisms between entities.
Conclusion
In this article we introduced Multi-Party Computation and analyzed the advantages of crypto wallets levering this technology. We compared multi-sig wallets with MPC wallets and briefly analyzed the cryptographic concepts on which the latter are based. We also took an in-depth look at some of the major security concerns that MPC technology entails.
MPC technology is an important development for security in operations that involve secrets shared among multiple parties. In the crypto world this is a pressing need: the growing number of companies and organizations operating in the Web3 world will require asset management shared among multiple entities.
Read more: https://www.certik.com/resources/blog/SlB0bOnxC10TxOgdcYNbJ-what-is-multi-party-computation-mpc
All Comments