Tracking issue: narsil design and implementation

[hdevalence]

Because Penumbra uses custom cryptography to achieve privacy, we can't easily make use of existing custody tooling like HSMs or hardware wallets without extending them to add support for our cryptography. However, secure custody is a critical operational requirement. Our plan to address it is to build a threshold signing implementation using FROST, providing off-chain multisignatures indistinguishable from any other transactions.

This tool is Narsil, and it will act as a custodian and audit log for a single Penumbra account, sharing control of that account's spending authority across multiple Narsil shards.

While FROST solves the cryptographic part of threshold signatures, it doesn't solve the engineering problem of building a way for the participants to reliably communicate with each other and agree on what messages they should be signing. That problem is also subtle and difficult to solve, but we realized we already have a tool that allows a set of participants to come to consensus on what messages have occurred: Tendermint consensus.

Using Tendermint internally gives us fault-tolerant state replication with an off-the-shelf tool, but it also has another important advantage. Because the Narsil cluster has fault-tolerant replication of the audit log of every transaction the account has authorized, by implication, it has fault-tolerant replication of the entire account state. This means that users can choose to maintain their account state off-chain, using their Narsil cluster as a personal rollup, and only post state commitments, nullifiers, and proofs to the L1.

This seems particularly useful for active market makers, who can cheaply perform frequent updates to their own state (e.g., updating their liquidity positions potentially every block), while saving on gas and saving other users from scanning irrelevant state updates.

Architecture Overview

Narsil provides implementations of the Custody and View protocols, pluggable into any Penumbra client, to provide threshold signing capability.

Narsil is composed of several discrete parts:

• a Narsil instance is a networked service running narsild and tendermint. Each Narsil instance is either a shard or a replica.
• a Narsil shard is a Narsil instance that holds a keyshare, and thus is able to participate in signing activities.
• a Narsil replica is a Narsil instance that replicates the Narsil ledger, but lacks a keyshare, and therefore cannot participate in signing.
• the Narsil ledger is the verifiable audit log, replicated by Tendermint, of every transaction authorization request, and all messages (Narsil packets) exchanged by shards during signing.
• a Narsil cluster is the entire distributed system replicating the Narsil ledger, made up of multiple Narsil instances. Each Narsil cluster jointly controls one Penumbra account (which may have many public addresses).

Given that Penumbra transaction authorization requests contain complete transaction plans, the Narsil ledger is a complete log of all account activity for a given Penumbra account (and all its associated addresses).

This diagram shows how data flows through the system:

       ┌────────────────────────┐
       │ pcli (or other client) │
       └────────────────────────┘
            ▲               ▲
            │ custody       │ view
            │ protocol      │ protocol
            ▼               ▼
┌──────┬────────┬──────┬────────┬───────────────────────┐     ┌────────┐
│      │Custody │      │  View  │     client protocol   │     │Penumbra│
│      │Service │      │Service │◀──────────────────────┼─────│Fullnode│
│      └────────┘      └────────┘                       │     └────────┘
│         │ ▲               ▲                           │
│         │ │          View │                           │
│    Auth │ │ Auth   Advice │               absent for  │
│ Request │ │ Data          │                replicas   │
│         │ │          ┌────────┐          ┌ ─ ─ ─ ─ ─  │
│         │ │          │ Narsil │ FROST       Narsil  │ │
│         │ └──────────│ Ledger │─────────▶│  Shard     │
│         │            └────────┘           ─ ─ ─ ─ ─ ┘ │
│         │                 ▲     FROST          │      │
│         └─────────────┐   │  ┌─────────────────┘      │
│                       │ ABCI │                        │
│narsild                │   │  │                        │
└───────────────────────┼───┼──┼────────────────────────┘
                        │   │  │
                        ▼   │  ▼
                      ┌──────────┐
                      │Tendermint│
                      └──────────┘

Authorization Flow

A custody client, such as pcli, constructs a TransactionPlan with a complete description of a proposed Penumbra transaction, and signs it with an Ed25519 key used for preauthorization. The TransactionPlan and PreAuthorization are included in an AuthorizeRequest sent to the custody protocol endpoint of a Narsil instance in that account's Narsil cluster. The Narsil instance wraps the AuthorizeRequest in a Narsil packet and submits it to its associated Tendermint instance.

AuthorizeRequests are identified by their transaction's EffectHash, indexing them by content (the effects of the proposed transaction). This provides a number of useful behaviors:

• Multiple users can request authorization of the same TransactionPlan by independently submitting it to the Narsil cluster with their PreAuthorization packet, and the ledger can stack their PreAuthorizations until some policy-based threshold is met.
• Rather than having to hold open a connection, clients can re-request authorization of the same TransactionPlan after it has been signed, and the ledger can immediately return the already-existing authorization data.

When a new AuthorizeRequest is received by the ledger, the ledger initiates a ceremony. Ceremonies are indexed first by EffectHash and then by a sequence number, and represent a particular attempt to threshold-sign the transaction. The state of a ceremony is tracked on-chain by a CeremonyState, whose state transitions are as follows:

┌───────┐   ┌─────────────┐   ┌─────────────┐   ┌────────┐
│Pending│──▶│StartedRound1│──▶│StartedRound2│──▶│Finished│
└───────┘   └─────────────┘   └─────────────┘   ├────────┤
    │              │                 │          │AuthData│
    │              │                 │          └────────┘
    │              │                 │
    │              │                 │          ┌────────┐
    └──────────────┴─────────────────┴─────────▶│ Failed │
                                                └────────┘

Ceremonies start in the Pending state. This corresponds an AuthorizeRequest that has been received by the chain but has not yet met policy requirements (e.g., for a certain number of pre-authorizations). Once policy requirements have been met, the ledger selects a committee of shards to participate in the FROST ceremony. As shards submit their FROST messages, the ledger advances the ceremony to either the Finished or Failed states. The Finished state contains the AuthorizationData necessary to authorize the transaction. Depending on the cause of the failure, a failed ceremony can be restarted. Also, multiple ceremonies can be run in parallel to reduce latency.

As proposed TransactionPlans are observed, each Narsil instance can also records all of the notes and other state fragments that they would create, and forward them to the view service as scanning advice. This allows transactions authorized by Narsil to safely skip inclusion of encrypted payload data, and post only rolled-up state commitments: because transactions from the Narsil-controlled account can only be authorized by threshold signing, and Narsil shards only consider transaction plans posted to the ledger, the Narsil ledger is guaranteed to contain openings of every authorized transaction's state commitments.

Key Generation

A Narsil cluster is initialized with a set of shard operators, the entities responsible for sharing control of the funds it custodies. Shard operators have the following keys:

• ShardIdentityKey: an Ed25519 key representing the root of a shard operator's authority, intended to be used offline.
• ConsensusKey: the (online) Ed25519 key used by Tendermint to sign blocks.
• ShardMessageKey: the (online) Ed25519 key used to sign packets posted by the shard to the ledger.
• ShardKey: the (online) threshold key share itself.

Of these keys, the ShardIdentityKey, ConsensusKey, ShardMessageKey are declared by the shard operator as part of the ShardDescription declared at genesis. At genesis, the shard operators begin a DKG, which results in an AccountGroupInfo describing the jointly-controlled account and the shares of each operator.

Next Steps

This list charts a pathway to an MVP:

• Fill out stub protos for Narsil's ledger
• Extract the tower glue code in pd into a standalone, reusable crate: Implement the crate by extracting code from pd tower-actor#1
• Include generated Narsil code in the penumbra-proto crate #2259
• Add a stub narsil crate to the workspace #2260
• Fill in domain types for the Narsil proto types #2261
• Extract the tendermint proxy code in pd into a standalone workspace crate, so it can be reused by narsild #2253
• Extract the GRPC proxy code in pclientd into the penumbra_proto crate #2254
• Select or write a FROST implementation #2220
  • We need two relatively custom behaviors: decaf377 and randomization. Randomization is also a requirement for using FROST in Zcash, so we should check whether the ZF's implementation would be suitable.
• Implement shard plumbing inside narsild #2264
• Implement Narsil DKG handling on chain spin-up #2262
• Implement AuthorizeRequest packet processing
  • This should identify the request by effect hash, and begin a ceremony. For now, we can skip policy and immediately select a committee.
• Implement AuthorizeCommitment packet processing
  • This has a ledger part (processing the packets) and a shard part (producing them)
• Implement AuthorizeShare packet processing
  • This has a ledger part (processing the packets) and a shard part (producing them)
• Add a CustodyService implementation to Narsil
  • This should forward AuthorizeRequests to the Narsil ledger via an internal Tendermint proxy, then holds the connection open while waiting for the results
• Add a ViewService implementation to Narsil
  • Initially, this should just use the Rust view server, like pclientd, without any custom behavior. This allows narsild to be a drop-in replacement for pclientd.
• Extract the GRPC transaction-creation parts of the pclientd integration test code into something that can be run against narsild
• Refactor pcli to allow specifying a remote custody service
  • This can just be a command-line override to start; later, we can refactor pcli to avoid having spend keys.
• Implement authorization policies

[hdevalence]

Closing as not planned; we shelved this design but could pick it up in the future.