From Theory to Practice: Multiparty Computation

A Primer on Group Theory

A group can be defined as a set \(G\) together with a binary operation \( * : G \times G \rightarrow G\) with the following properties:

1. There is an identity element \(e \in G\) such that for every \(a \in G\) we have \(a * e = e * a = a\).
2. For every element \(a \in G\), there is an element \(a^{-1} \in G\) such that \(a * a^{-1} = a^{-1} * a = e\).
3. Given elements \(a, b, c \in G\), associativity holds: \(a * (b * c) = (a * b) * c\).

In some groups, there is a fourth property, commutativity, which states that for elements \(a, b \in G\) we have \(a*b = b*a\). These axioms seem deceptively simple. In fact, it is the simplicity of these axioms that makes it so difficult to study groups.

Elliptic Curve Groups

Now that we know what groups are, we can define elliptic curve groups. An elliptic curve group is a set of points on an elliptic curve, along with a special point at "infinity," which forms a group under a unique addition operation. An elliptic curve is defined by an equation of the form:

We also require that \(4a^3 + 27b^2 \neq 0\) so that this curve has no cusps or self-intersections. The elements of the group are defined as the points \((x, y)\) on this curve, where x and y belong to some field (which can be finite). Now, we must define a group operation, which we refer to as the "addition" of points. Let us suppose that we have points P and Q. We want to define their sum. Well, let's just draw a line through P and Q. This line will intersect the elliptic curve at some third point. We can reflect this third point across the x-axis and obtain the "sum" of the points P and Q. Of course, we can only draw a line through P and Q if they are distinct. If \(P=Q\) then it would seem that we are out of luck because you can draw infinitely many points through a single point. Luckily, because we defined our elliptic curve so that it would have no cusps or self-intersections, we know that there must exist a unique tangent line to P. Thus, in order to compute the sum \(P+P\), we simply draw the tangent line to the curve at the point P. This line will intersect the elliptic curve at some other point. Then, we reflect this point across the x-axis to obtain the sum of P and P. It can be shown that this operation ensures that all the group axioms are satisfied.

It can also be shown that elliptic curve groups are abelian, which means that \(P+Q=Q+P\). If we have a point P, it is easy to compute nP, where n is some integer. But if you know that \(Q=nP\) for some integer n, it is very difficult to determine what n is. So far, we have gone through a high-level overview of elliptic curve cryptography. But we have yet to understand how exactly this is used in Multi-Party Computation.

Phase 1: Distributed Key Generation (DKG)

Let's say that we want to implement a \((t,n)\) Threshold ECDSA scheme, where n is the total number of parties and t is the minimum number of parties that must cooperate to generate a signature. We will operate within the context of an elliptic curve group G of prime order q with a generator point G. As expected, we will perform all arithmetic modulo q. First, we will do Distributed Key Generation (we will just refer to this as DKG). The goal of DKG is for n parties to collectively create a single public key P, while each party \(P_i\) only knows a secret share \(x_i\) of the corresponding private key \(x\). The full private key \(x\) will never be assembled in one place in order to ensure security. A brief outline of this process is as follows:

1. Secret Contribution: Each party \(P_i\) independently generates a random secret value \(u_i \in \mathbb{Z}_q\). The final master private key will be the sum of these secrets: \(x = \sum_{i=1}^{n} u_i\).
2. Verifiable Secret Sharing (VSS): Each party \(P_i\) acts as a "dealer" using Feldman's Verifiable Secret Sharing scheme. To do this, \(P_i\) generates a random polynomial \(f_i(z)\) of degree \(t-1\) with its secret \(u_i\) as the constant term. That is, we have: \[f_i(z) = u_i + a_{i,1}z + \dots + a_{i,t-1}z^{t-1} \pmod q\] where the coefficients are chosen randomly from the set \(\mathbb{Z}_q\). After this, the party \(P_i\) computes and broadcasts public commitments to the coefficients of its polynomial by exponentiating them with the generator G: \(C_{i,k} = a_{i,k}G\).
3. Share Distribution and Verification: The party \(P_i\) calculates a secret share \(s_{ij}=f_i(j)\) for each other party \(P_j\) and sends it securely. After receiving its share, party \(P_j\) verifies its validity against the public commitments as follows: \(s_{ij}G = \sum_{k=0}^{t-1}(j^k)C_{i,k}\). This check ensures that \(P_i\) distributes shares from a single, consistent polynomial and is not cheating.
4. Final Key Share and Public Key: Each party \(P_j\) combines the valid shares it received to form its final secret share of the master key: \(x_j = \sum_{i=1}^{n} s_{ij} \pmod q\). The collective public key P can be computed by anyone because the commitments to the initial secrets \(U_i = u_iG\)) were broadcasted: \(P = \sum_{i=1}^{n} U_i = (\sum_{i=1}^{n} u_i)G = xG\).

At the end of this phase, the system has a public key P, and each party \(P_i\) holds a share \(x_i\) of the private key \(x\). The set of points \(\{(i,x_{i})\}_{i=1}^{n}\) uniquely specifies a polynomial of degree \(t-1\) whose constant term is \(x\). Let's prove that the constant term of the polynomial defined by these points is \(x\). First, we claim that this polynomial is actually the sum of all the individual polynomials \(\{f_{i}\}\). We recall that \(f_i(z) = u_i + a_{i,1}z + \dots + a_{i,t-1}z^{t-1}\). Evaluating at 0 shows that the constant term of \(f_i\) is \(u_i\). Now, we claim that each point \((j, x_j)\) lies on the polynomial \(F(z)\) defined as \(F(z) = \sum_{i=1}^{n}f_i(z)\). Notice that since we are summing polynomials of degree \(t-1\), the resulting polynomial will also have a degree of \(t-1\). We recall that \(x_j = \sum_{i=1}^{n}s_{ij} = \sum_{i=1}^{n}f_i(j) = F(j)\). So we see that the point \((j,x_j)\) does lie on the polynomial \(F(z)\). Thus, the polynomial defined by the points \(\{(j,x_j)\}\) is actually \(F(z)\). We know that the constant term of \(F(z)\) is \(F(0)\), so we just compute \(F(0) = \sum_{i=1}^{n}f_i(0) = \sum_{i=1}^{n}u_i = x\), as desired.

Phase 2: Distributed Signing

Now, we move on to the second phase, Distributed ECDSA Signing. The goal is to compute a valid ECDSA signature \((r, s)\) for a message hash \(m' = H(m)\). The message \(m\) represents the actual data you wish to sign, and the hash function \(H\) (like SHA-256) converts it into a unique, compact digital fingerprint, which we denote by \(m'\). We sign the hash instead of the message because it is more secure and efficient. The standard ECDSA signature is defined as:

\(k\) is a secret nonce. In threshold signing, both \(x\) and \(k\) are secrets held in a distributed manner, and the protocol must involve at least t parties. To generate the distributed nonce, each participating party \(P_i\) generates a random nonce share \(k_i\) and a second random value \(\gamma_i\) (to help compute \(k^{-1}\)). The parties then collaboratively compute the point \(R = kG\) without revealing \(k = \sum k_i\). To do this, each party broadcasts the commitment \(R_i = k_iG\), and then every party can compute \(R = \sum R_i\). The signature component \(r\) is the x-coordinate of R. If \(r=0\), the protocol must be restarted. The main challenge is to securely compute \(s = k^{-1}(m' + xr)\) when \(k\) and \(x\) are additively shared. We are not allowed to compute this directly, so we will use homomorphic encryption and zero-knowledge proofs. Since the parties cannot compute s directly, we want to ensure that each party computes a share \(s_i\) such that \(s = \sum s_i\). We apply the distributive property as follows: \(s = m'k^{-1} + r(xk^{-1})\). The two main subprotocols are the secure inversion protocol (to compute \(k^{-1}\)) and the secure multiplication protocol (to compute \(k^{-1}x\)).

• Secure Inversion: The parties use their shares of the nonce (\(k_i\)) and the helper values (\(\gamma_i\)) to engage in a protocol that computes shares of its inverse. The idea is that each party will receive a new share \(\sigma_i\) such that \(\sum \sigma_i = k^{-1}\).
• Secure Multiplication: The parties need to compute shares of the product \(xk^{-1}\). They already have shares of \(x\) and just computed shares of \(k^{-1}\) (\(\sigma_i\) values). The idea is that given shares \(x_i\) and \(\sigma_i\), party \(P_i\) will receive a share \(\delta_i\) such that \(\sum \delta_i = (\sum x_i) \cdot (\sum \sigma_i)\).

We recall that \(m'\) and \(r\) are public values, \(\sigma_i\) is \(P_i\)'s share of \(k^{-1}\), and \(\delta_i\) is its share of \(xk^{-1}\). This formula crucially does not contain \(k\) and \(x\) explicitly. When we sum all the shares \(s_i\), we have \(\sum s_i = \sum (m'\sigma_i + r\delta_i)\). Using distributivity, this becomes \(m'(\sum \sigma_i) + r(\sum \delta_i)\). Since we know \(\sum \sigma_i = k^{-1}\) and \(\sum \delta_i = xk^{-1}\), substitution yields \(m'k^{-1} + r(xk^{-1})\), which is equal to \(k^{-1}(m' + rx) = s\). We get back the correct value without ever needing to compute \(x\) and \(k\) explicitly, and we finally have the signature \((r, s)\).

The Practice: Our Go Implementation

Translating this complex theory into code requires a clear separation of concerns. Our Proof-of-Concept (POC) implementation serves as a demonstration and is organized into two primary layers: the networking layer that allows the parties to communicate and the wallet layer that handles the cryptographic protocols.

The Network Layer: `internal/network/network.go`

Before any cryptography can happen, the parties need a robust way to talk to each other. Our `network.go` file implements a `Router` that manages a peer-to-peer mesh network over TCP. It handles dialing, accepting connections, and multiplexing messages. The `Envelope` struct is our standard message format, wrapping the cryptographic payloads sent between nodes.

The Wallet Layer: `internal/wallet/wallet.go`

This is where the cryptographic theory comes to life. Our `Wallet` struct orchestrates the DKG and signing ceremonies by leveraging the well-regarded `tss-lib/v2` library.

• Implementing DKG: Our `RunKeygen` function directly implements the DKG theory. It creates a `keygen.NewLocalParty` from the library, which manages the polynomial generation and secret sharing. The function uses our network `Router` to send and receive the cryptographic messages between parties, handling the rounds of communication until each party has its final key share, which is then persisted to disk.
• Implementing Signing: Our `Sign` function orchestrates the distributed signing process. It creates a `signing.NewLocalParty`, providing it with the message hash and the previously generated key share. This party then handles the complex MPC sub-protocols for nonce generation and share calculation. Again, our `Router` is used to pass the necessary messages. The function returns the final, valid `(r, s)` signature pair.

By separating the low-level networking from the high-level cryptographic workflow, our demonstration is both modular and directly reflects the theoretical underpinnings of MPC. The result is a practical POC that showcases how a secure tool for decentralized key management can be built, developed right here at Nanar Consulting.