Distributed Proofs of Possession: Proving Key Ownership Without Exposing Keys

At Coinbase, our mission is to increase economic freedom in the world. Central to that mission is the secure custody of customer assets. Our key management infrastructure is rooted in multi-party computation (MPC), where private keys are split into shares held by independent entities such that the full key is never assembled. 

This model works well for signing transactions, but third-party external reviews introduce a different challenge: auditors need cryptographic proof that we control the keys behind customer assets. This post describes how we solved this with Distributed Proofs of Possession (DPoP).

Picture this: an auditor hands you a list of public keys and a challenge message. Your job is to prove, cryptographically, that you control the corresponding private keys. The obvious answer is to sign the message with each private key and hand back the signatures.

In traditional key management systems, this is exactly what happens. The full private key is assembled in a controlled environment (a secure enclave, HSM, or offline workstation) to sign the audit message. This approach is well-established and, when paired with strong operational controls, works reliably. However, each audit cycle requires careful orchestration to preserve the security of those controls.

Our key management architecture eliminates this overhead because it is built on MPC. Private keys are split into shares distributed across multiple entities in independent security domains. The MPC signing protocol allows these entities to collaboratively produce a valid signature without any single party ever holding the complete key.

So why not just use this signing protocol on the audit message? The result would be a standard signature under the full public key, indistinguishable from a real transaction. This creates two problems:

Message Risk: The MPC signing protocol produces a signature that is valid for any purpose, including blockchain transactions. If the audit message were substituted with a real transaction, the resulting signature would be a valid spend. The system has to be trusted not to do this, which is the exact kind of implicit trust we aim to mitigate.

Protocol Misuse: Our production signing flow enforces caller attestations, policy checks, and message validations. These controls are designed specifically for transaction signing. Using the flow for audit purposes means either routing non-transaction messages through that pipeline (requiring special-case handling in production code) or bypassing those controls entirely. Both options weaken the security boundary that the signing protocol was built to enforce.

These risks compound with scale: more keys, more frequent audits, and more complex signing infrastructure all widen the exposure.

So how do we prove key ownership without exposing the full key or trusting a single party? The answer turns out to be surprisingly simple.

Each shareholder signs the auditor's challenge message (m) independently with its own key share, producing a key share signature. The auditor verifies each key share signature and confirms that the public key shares sum to the original public key.

Consider a private key x that is additively shared across n entities:

x = x₁ + x₂ + ... + x_n

Each entity i holds share x_i and can compute the corresponding public key share Q_i = x_i * G, where G is the elliptic curve generator point. The full public key is:

Q = Q₁ + Q₂ + ... + Q_n

For a DPoP proof, each entity signs the auditor's message m using its individual share x_i, producing a signature σ_i. The auditor receives {(Q_i, σ_i)} for all i and performs two checks:

1. Signature Verification: For each i, verify that σ_i is a valid signature on m under Q_i.

2. Key Reconstruction: Verify that Q₁ + Q₂ + ... + Q_n = Q.

If both checks pass, the auditor has cryptographic assurance that the entities collectively possess the private key corresponding to Q, without the key ever being reconstructed.

The soundness of DPoP rests on a well-studied property of Schnorr-family signatures: they are proofs of knowledge of the discrete logarithm. Specifically:

Both signature schemes satisfy:

We prefer Schnorr over ECDSA for the secp256k1 case specifically because ECDSA lacks a formal proof that it constitutes a zero-knowledge proof of knowledge of the private key.

A critical property of this design: key share signatures are useless as transaction signatures. A signature produced by share x_i under public key share Q_i is not a valid signature under the full public key Q. Even if the auditor's challenge message were somehow replaced with a valid transaction, the resulting key share signatures could not be broadcast to any blockchain.

Crucially, an attacker who collects all share signatures still cannot combine them into a valid signature under the full public key. Schnorr signatures produced under different public keys are not aggregatable: there is no operation that takes signatures (σ₁, ..., σ_n) under public keys (Q₁, ..., Q_n) and yields a valid signature under Q = Q₁ + ... + Q_n. The proofs are useful only for verification, not for constructing a valid transaction.

These combined features address the identified problems earlier: key share signatures cannot be leveraged as valid transactions, thereby mitigating "Message Risk," and because the DPoP flow never invokes the production signing protocol, "Protocol Misuse" is also mitigated.

The proof format uses only standard cryptographic primitives (Schnorr, EdDSA, elliptic curve point addition), so auditors can verify it with any implementation of these schemes, not just a provided utility.

At Coinbase, DPoP embodies a wider engineering principle: build systems designed for verification, not trust alone.

This is the same principle behind open-sourcing our MPC cryptography library: security properties should be externally verifiable.

DPoP's purpose is to move beyond mere assurances of key possession ("trust me, I have the key") and instead provide concrete evidence ("here is the proof"): open protocols, open code, and proofs that anyone can verify.

We're building systems that secure billions in digital assets and serve millions of users globally. See what else we're working on at our careers page.