# Mina Protocol Multi-Signature Wallets

## Project Background
According to [Mina's documentation](https://docs.minaprotocol.com/zkapps/writing-a-zkapp/feature-overview/permissions#upgrading-after-an-update-to-the-mina-protocol), a zkApp can be designed so that only valid proofs (that is, smart contract logic) can update the smart contract by modifying its verification key. This design enables a deployer to create a smart contract and then renounce ownership by changing the permissions to proof-only – a crucial aspect for decentralised protocols. However, in the event of a hard fork, permissions will revert to being signature-based, thereby restoring upgradeability to the deployer.

This creates a significant centralisation risk within Mina, as there is currently no method to enable hard-fork-proof smart contract deployments.

## Proposal Overview
We propose a multi-signature implementation based on [FROST](https://eprint.iacr.org/2020/852.pdf), which will allow developers to create and sign Mina transactions (or any general message) in a decentralised manner. This will be implemented as a Rust/TypeScript library that enables individual signers to agree on a signature for Mina transaction data. It should integrate with o1js so that developers can interact seamlessly with the Mina blockchain using the agreed signature.

### Impact
A multi-signature implementation is vital for production-ready protocols and will support the decentralisation promise of most blockchains.

## Architecture & Design

### General Overview

Our intended work can be split into two main sections:
1. a Mina-agnostic FROST networking application
2. a FROST integration with o1js

The FROST networking application will be a rust client which allows pre-determined participants to convey and sign arbitrary messages using the FROST protocol. When run correctly, this will produce a Schnorr signature which can then be used to perform transactions on behalf of a decentralised account on Mina. It is worth noting that no-single participant can create signatures on behalf of the decentralised account, this can only be done if a threshold of participants is reached during signing.

The o1js integration will be a typescript library which allows a participant (or anyone else) to copy a signature produced by a FROST signing session and broadcast the corresponding transaction to the Mina blockchain, in similiar syntax o1js currently uses. This in effect allows a user to create a "one-time wallet" which is only able to send a single pre-specified transaction.

### Frost Networking Application Overview
As explained above, this is a rust client which comes with two packages: a `frost-server` and `frost-client`. The `frost-client` is run by each signing participant while the `frost-server` is run by a single signature aggregator (this can be done by a participant in parallel with `frost-client`).

The `frost-server` acts as an aggregator for commitments, partial signatures and encrypted secrets according to the FROST protocol in order to generate a correct final signature for a pre-chosen message. The signature can then be broadcasted to other participants or directly used by the aggregator to send transactions to the Mina blockchain. The server only allows communication from pre-specified public key addresses which signers share with the aggregator beforehand (see [session identification](#Session-Identification)).

Example command with 3/5 threshold scheme:

./frost-server -p 8000 --signers signers.txt -t 3 -n 5

The `frost-client` generates a unique private/public key pair which is used to authenticate with the `frost-server` using TLS. The `frost-client` will perform distributed key generation, commitments and signature sharing to the server to produce a final signature.

Example command with key generation

./frost-client --url 888.888.888:9000 --dkg

If signing is successful then the clients and the aggregator termainal scripts will produce a final pasta-curve signature as output e.g.

Message signature: 0xabc...

This can then be manually copied into our o1js integration which we describe in more detail [below](#O1JS-Integration).

Generally speaking, FROST can be split into key generation and signing. Key generation only needs to be done once when signers first create a session with each other and will be where important information such as the multi-sig wallet public key will be generated. Signing is done repeatedly for any transaction which participants would like to send on behalf of the multi-sig wallet.

### FROST Distributed Key Generation
Please see the FROST paper for detail, but simply put, distributed key generation allows several participants to agree on a secret key without any single participant learning of the key itself. We have outlined how a networking application will build ontop of FROST's key generation algorithm within [Figure 1](#fig:architecture).

<figure id="fig:architecture">
<img src="https://hackmd.io/_uploads/Hk_L7VpCyl.png" alt="System Architecture">
<figcaption>Figure 1. DKG architecture overview.</figcaption>
</figure>

1. Alice and all other participants are responsible for generating a polynomial and publishing commitments to each other. In this case, the aggregator acts as a publishing server and is trusted to give information reliably. All commitments are public and are verified independently by each participant. If any participant receives invalid commitments or does not want to continue, they may abort the process.
2. Every participant must send private key shares unique to each pair, this must be private to the aggregator and all other participants and hence why the session between each participant pair will be private. For example, when Alice plans to send her key share to Charlie, she will encrypt the key share with Charlie's public key, pass the key to the aggregator who forwards it onto Charlie. Charlie can then use her private key to decrypt her key share, ensuring that no middle man can intercept the key share. Public keys are known from the start and is discussed in more detail within [session identification](#Session-Identification).
3. Finally, once everyone receives all their private key shares from all other participants then information is verified against commitments and the participants may abort the process if verification fails.
4. Finally, the aggregator may calculate the public key and each signer's public key share to be displayed publicly.

Note that if participants and aggregators want to perform distributed key generation, then they must call their respective commands with the "--dkg" flag. This will create an entirely new session and hence the corresponding FROST private/public key and will be treated independently of any previous sessions. Whether previous sessions are deleted or can be stored permanently through file session information is yet to be decided.

### FROST Preprocessing and Signing
<figure id="fig:preprocess">
<img src="https://hackmd.io/_uploads/HJk-2sR0Jx.png" alt="Preprocessing Diagram">
<figcaption>Figure 2. Preprocessing Diagram.</figcaption>
</figure>

As described within the FROST paper, preprocessing is the stage before signing where participants generate nonces and their corresponding commitments and publish them. Alice can perform preprocessing for an arbitrary number of messages and publish them all to the aggregator. Whenever the Aggregator runs out of nonces during signing, it will explicitly request more from Alice and will not allow Alice to sign unless Alice responds.

<figure id="fig:sign">
<img src="https://hackmd.io/_uploads/BJZM2iAAyx.png" alt="Signing Diagram">
<figcaption>Figure 3. Signing Diagram.</figcaption>
</figure>

Again, the signing diagram follows the algorithm in the FROST paper with additional logic wherein the Aggregator receives message suggestions from participants. If the queue of messages is non-empty then the aggregator will send the head of the queue to participants to approve. If enough participants accept, they will receive and send their partial signatures to the aggregator which will verify and generate a final signed message.

Note that the FROST scheme is not robust, which extends to our protocol. This means that the protocol does not have an in-built method to remove and locate malicious behaviour, if participants find that signing is constantly failing or being aborted then it is their job to find the cause.

Note that in the diagram timeouts are implicit. A timeout would generally cause a restart. A restart simply puts the message back in the queue.

### Session Identification
One problem that the networking protocol has is session management. FROST provides no guidance to choosing and managing participants or signers. Our solution is to force each participant to generate public/private key pairs. The public key acts as an "account" for each participant and is shared with the aggregator in advance before key generation or signing.

When the aggregator sets up their server, they must explicitly define the public key values that they will accept connections from. If a participant disconnects during key generation or signing then they cannot reconnect and the aggregator/participants must restart if too many participants disconnect.

### Network Design Justification
FROST is a threshold signature scheme with several audited implementations and is comparatively mature relative to other threshold schemes. Furthermore, FROST signing results in a Schnorr signature, which is blockchain agnostic and can be treated as a normal signature within Mina.

The primary rationale for a networking-based implementation is twofold:

1. We can directly utilise the Zcash Foundation's FROST libraries, which will reduce development time and avoid reinventing the wheel.
2. An alternative approach would be to use Mina as a "signature aggregator"; however, this would effectively repurpose Mina for state storage, a role for which it is not suitable for.

## Existing Implementations of FROST and Tech Stack
For the core cryptography implementation of FROST we plan to use the Zcash Foundation's [FROST implementation](https://github.com/ZcashFoundation/frost), specifically the `frost-core` package which implements FROST over arbitrary elliptic curves. Our first step would be to modify the implementation to be compatible with the Pasta curves that Mina uses and hence allow us to test whether signatures are generated correctly and will be accepted by the Mina blockchain.

The Zcash implementation is the most natural choice as it is has been audited and provides the most security.

For the networking application, we plan to use rust's [libp2p](https://libp2p.io/) library as it is one of the most extensive networking libraries and includes implementations for TLS sessions which we will require when participants send secret shares among each other. We plan to use [frostd](https://frost.zfnd.org/zcash/server.html) as inspiration as they have implemented a significant portion of FROST networking logic. We have opted **not** to use their code directly as it is for demonstration purposes and we do not know whether/when their code can be used in an production environment.

## O1JS Integration

Currently, o1js deployment scripts require users to specify private keys in order to sign transactions which is not possible in our use case as the private key is unknown to any single entity. Instead a `SingleUseSigner` interface will allow participants to sign specific transactions from which a signature has been derived from using the FROST networking protocol. An example deployment script will look similiar to the following (modified snippet from [the o1js documentation](https://docs.minaprotocol.com/zkapps/writing-a-zkapp/introduction-to-zkapps/interact-with-mina#signing-transactions-and-explicit-account-updates)).

import { SingleUseSigner } from 'frost-signer';

const senderSignature = '0xabc...'; // This will be copied from a FROST signing session

const tx = await Mina.transaction(sender, async () => {
  await zkapp.deposit(UInt64.from(5 * MINA));
});
await tx.prove();

const wallet = new SingleUserSigner(payment, senderSignature); // Create a client for this specific tx data

wallet.verify(); // Ensure that signature matches with tx data

const signedTx = wallet.signTx();
signedTx.send();

## User Workflow
The user experience should be as follows:

1. Users set up wallets for communication.
- ```frost-client --gen-keys```
3. An aggregator (which may be a centralised entity) configures the signing server with which the users authenticate. Note that if the aggregator misbehaves, no signature can be forged and instead another aggregator can be setup.
- ```frost-server -p 8888 --signers signers.txt```
5. Users agree on a message to sign, for example, zkApp deployment transactions.
- ```frost-client -u example:8888 -m message.json```
- Users receive proposed messages through the terminal and can decide whether to sign or not
7. The aggregator and participants collaborate to create a Mina signature, this will be shown as a hex string within the `frost-client` or `frost-server` terminal output.
8. Any one of the aggregator or participants may copy the signature from the terminal output and use it in their deployment scripts as shown above in the [o1js integration](#O1JS-Integration).

## Risks & Mitigations

**Evolving FROST Scheme**: FROST is not yet a finalised cryptographic scheme. While no changes are anticipated, future modifications to frost-core or other dependencies may render FROST unsuitable as a multi-signature solution.

**Security Concerns**: Although we will attempt to minimise the incorporation of FROST-specific logic, it is necessary to implement FROST over the Pasta curves, which introduces a security risk. This code, along with the remainder of the codebase, will be audited externally to minimise vulnerabilities and bugs.

**Complex Networking Application Logic**: The logic for the networking application can be quite complex, particularly in ensuring that users agree on messages and managing malicious signers. This complexity may potentially extend the production timeline.

**Lack of Asychronous Sessions and Robustness**: Currently, our proposed networking protocol requires participants to abort whenever a technical issue arises e.g. a participant disconnects. Additionally, all signers are required to be online during key generation or signing which can be difficult if participants have unstable internet connections or live in different timezones. The [ROAST paper](https://eprint.iacr.org/2022/550) addresses this issue, however, as we deemed this issue to be not vital to the protocol we have decided to leave this work to later versions.

## Milestones & Timeline
We propose the following milestones and deliverables after 3 months of development:

1. `frost-pasta` rust library which builds on `frost-core` logic implemented on the pasta curves. This should have the same developer interface as all other `frost` curve-specific implementations.
2. An example POC (rust) which allows a user to sign a Mina transaction using `frost-pasta` on a single machine (note this will not be decentralised) and be able to submit that Mina transaction to the Mina blockchain. This ensures that the Mina-specific signing logic is correctly implemented as different implementations can use different prefixes, hashing algorithms, etc. We will use a static transaction message to sign e.g. sending a token amount of MINA.
3. Make significant development gains on [Distributed Key Generation Networking](#FROST-Distributed-Key-Generation) including session identification and authentication with public/private keys. This will include initial p2p networking and a terminal command to allow participants and aggregators to communicate.

### Mid-Way Deliverables
After 6 weeks of development, we expect the `frost-pasta` library to be implemented and unit tested. The POC script should be mostly done but not necessarily finished.