PoW Pub

Background

Nostr public keys are Schnorr public keys.

A private key on secp256k1 is a scalar k. Multiplying it by G gives the public key K:

kG = K

This means there is a linear relation between the private and the public keys:

(k+x)G = kG + xG = K + X

Alice wants a vanity public key V, but doesn't have the time or the hardware to mine it herself. Bob offers to mine her such a pubkey, but she doesn't want him to know the resulting private key.

Bob offers to trustlessly mine her vanity key, in exchange for a fee, as follows:

• Alice generates a new private key k
• Alice give Bob her public key K and tell him how her desired vanity pubkey V should look like
• Bob iterates through scalars x until a matching V is found:

K + xG = K + X = V

• With knowing x and her secret key k, Alice can find the private key v which has the vanity pubkey V:

kG + xG = (k+x)G = vG = V

The protocol is not fully trustless, because Bob cannot reveal the scalar x without trusting that Alice will pay. Similarly, Alice cannot know for sure Bob will mine and deliver the scalar after she pays.

To mitigate Bob's risk, in the protocol described below Bob will only start mining once Alice pays.

Alice's risk is addressed by allowing multiple providers to bid for the trade, while at the same time giving Alice a way to determine the provider's reputation based on past trades.

Protocol

Clients can purchase the mining of a scalar x for a specific type of vanity pubkey V. The simplest example is that V has a chosen prefix, but it can also have a chosen suffix, or match a pattern.

Knowing the conditions for V, Providers can find the mining difficulty and therefore quote a price and an estimated time to find x.

The steps are as follows:

• Client posts baseline public key K and a desired prefix for vanity pubkey V.
• Interested Providers reply with a BOLT11 LN invoice.
• Client may choose one offer and pay the invoice. Client posts the preimage as proof of payment.
• The Provider who issued the invoice starts mining x and, when ready, posts it.

Each of these steps happen as a Nostr event and is linked to the previous through an e tag. This means all steps of a trade can pe publicly audited, especially whether the Provider:

• got paid and
  • delivered a valid x, or
  • delivered an invalid x, or
• didn't deliver a scalar x (yet)

Providers don't have to trust that Clients will pay, because they get paid upfront. If a Client doesn't pay an invoice, it means he's not interested in that offer.

Clients can choose which Providers to trust based on the Provider's reputation. As part of the Nostr message format, each trade step is signed. Therefore a Client can check the past trade activity of a Provider's pubkey and see in how many trades this Provider was paid and delivered, or was paid and didn't deliver, or was paid and delivered an invalid x.

Example trade

Provider output:

Received Ask for prefix 12345
Posting invoice for 1 sats
Received preimage
Starting to mine for pubkey prefix 12345
Found matching scalar
client_pk  : 20ea67796d2fdfd6fe79cd329eddbbad7eae6119ffa363d2922331296d4d92db
scalar     : 2446df556947ec1130c63c4f6f87a313624fc68e3df2790718748b73969e9295
scalar_pk  : 8e49ae23101c87ee0c4563b7d8631a15a6ec66b06389c45b26d2ccc73431fecd
result_pk  : 123455b733e3baa77bea932bbe83eaa2eef8ded9db7aa05da0d1a1b1c45d3ea8
iterations : 769501 in 22.712 sec @ hashrate ~33880.81 h/s
Sending scalar response

Client output:

Sending PoW Ask for prefix 12345
Received offer and invoice for 1 sats, trying to pay it
Posting proof of payment (preimage)
Received mined scalar       : 2446df556947ec1130c63c4f6f87a313624fc68e3df2790718748b73969e9295
Local secret key            : 85929d88abc62fb211abe13cb21af1b0293631d1cf7a2b846c0449dd2b473b2b
Combined (final) secret key : a9d97cde150e1bc342721d8c21a294c38b85f8600d6ca48b8478d550c1e5cdc0
Combined (final) public key : 123455b733e3baa77bea932bbe83eaa2eef8ded9db7aa05da0d1a1b1c45d3ea8

Querying provider reputation with view-provider-reputations.sh:

==============================================================================
PoW Pub Provider pubkey                                          | +Rep | -Rep
------------------------------------------------------------------------------
6a13a4646c2b24dc998642da236b18b8bc89a72db8c6fb1ac9eb0a04e0a663e1 |    3 |    0
302d426b0df5b6375b3b2a0ea882e726c589f2780f43cec381e7352ef1169693 |    1 |    0
==============================================================================
+Rep = Positive reputation (trades this provider got paid and delivered)
-Rep = Negative reputation (trades this provider got paid but did not deliver)
------------------------------------------------------------------------------

Known issues and Open Questions

• When there are only Providers with little or no trade history (reputation), a Client has to trust that chosen Provider will deliver
• The Client cannot know when the Provider will deliver, or even if the Provider started mining.
  • A variant of this protocol could ask Providers to post intermediary solutions as they are found. These would be x' scalars for vanity pubkeys V' with lower (but non-zero) difficulty than V. This would show the Provider is actually mining and could even give hints as to the hashrate in use and ETA for finding x. However, mining is probabilistic and the absence of such intermediary solutions isn't necessarily proof that the Provider isn't mining.
• Nostr message timestamps are not checked, therefore how long a Provider took to deliver on a past trade cannot be checked.
  • A future version could explore more reliable timestamping options, like an optional OTS tag
  • The BOLT11 invoice already provides somewhat reliable timestamping, because for an invoice to be payable, it has to have an accurate created_at timestamp. LN nodes will ignore peers who backdate their messages, so a backdated invoice would not be payable. However, the invoice is issued and paid before the mining begins, so the invoice's timestamp cannot be used to tell when the mining was finished and x was posted.
• Reputation relies on past trade messages being publicly available. Nostr relays can have different policies around which messages to store and for how long, so a full accurate view of past trades (and therefore of Provider reputation) cannot be guaranteed.
  • If a market develops around this, specialized Nostr relays can offer to store trade messages, and therefore offer reliable reputation, for a fee.
• The protocol is not fully trustless
  • The client has to trust the provider will deliver. This risk is minimized via the provider reputation, but never fully eliminated.
  • A future variant could aim to combine the revealing of the preimage (proof of payment) with the revealing of x in one step. However, the question remains of how would a Provider know that it's worth it to start mining before being paid. This opens the door for DoS attacks on the Providers. A HOLD invoice could be asked for in the first step, that could be cancelled when the Client pays the actual invoice, but AFAIK there is no way for the Provider to prove the HOLD invoice wasn't settled. The Client therefore runs the risk of paying twice. This remains an open topic.
    • One way to solve this could involve Providers requiring a minimum level of PoW in Client requests. This could show Client are not spamming and indeed intent to see the trade through, meaning the Provider can start mining even before being paid.