Oak

Delegated NIP-13 Proof of Work - Protocol Spec
Login

Delegated NIP-13 Proof of Work - Protocol Spec

Revisions | Status: early draft

Background

Here we explore an approach to Delegated NIP-13 PoW1, which shows how Nostr clients can outsource the PoW to a service provider in exchange for a fee.

A proof-of-concept implementation is offered in Oak Node v0.3.X.

Definitions

PoW Trade: the exchange of sats for outsourced Nostr PoW mining.

Client: a Nostr user that wishes to outsource NIP-13 PoW for a note.

Provider: a Nostr user who offers to generate NIP-13 PoWs in exchange for sats.

Note stub: the message payload and tags which the Client wants to have mined. The resulting mined note will contain the note stub, a nonce-tag from the Provider and a timestamp also set by the Provider.

Blinded PoW solution: Published, but not yet usable PoW solution. A full PoW solution would consist of PoW hash, nonce and timestamp. The blinded PoW contains only the hash and the timestamp. The nonce is not published, but can be derived once the invoice is paid because the invoice preimage = xor(PoW hash, PoW nonce).

Since the PoW hash is already published by the Provider with the Blinded PoW, the Client can tell if it's invalid without even paying to unblind the nonce.

An invalid Blinded PoW will have a lower difficulty than the Client's target difficulty. In this case, the Client can determine the PoW solution is invalid and not pay to unblind it. In addition, such an invalid PoW can be an input in the Provider's reputation.

Conversely, the Client cannot tell if the PoW is truly valid until the nonce is unblinded and the hash is checked. Network participants can only do this after the preimage for this PoW has been published.

Unblinded PoW solution: A combination of two published messages: the Blinded PoW and the preimage. With them, the Client can derive the nonce, which is the last piece of the puzzle needed to build a fully valid PoW note using the Client's payload and the Provider's hash.

Every preimage is linked to an associated Blinded PoW. So the act of publishing a preimage can be seen as unblinding the PoW.

Valid invoice: Invoice posted by the Provider together with the blinded PoW solution, which:

  • is for the exact amount specified by the Client in the Ask
  • has a timestamp that is within timeframe of the Client's Ask created_at timestamp
  • TODO appropriate expiry

Valid PoW solution: A valid unblinded PoW. In other words, a combination of PoW hash, timestamp and (unblinded) nonce that, combined with the Client's payload, tags and pubkey, result in a valid Nostr message.

Reputation: an indicator of a participant's trustworthiness. It's a metric derived entirely from the participant's behavior in previous past trades. For the Client, it shows whether the Client has paid the trade amount in the past. For the Provider, it shows whether the Provider has published valid PoWs for a certain hashrate or not.

Trade Steps

  1. Client publishes an Ask.

    • I am willing to pay S sats for a valid PoW of difficulty D for my message, if delivered within time T.

  2. Interested Providers start working on a PoW.

  3. When ready, Providers publish their Blinded PoW and an invoice.

    • I have mined such a PoW, here is the blinded version. You can unblind it by paying this invoice.

  4. Client chooses one solution from a Provider, pays the associated invoice and publishes the preimage.

    • I have chosen this solution and paid the LN invoice, here is the preimage as proof.
      • The preimage acts as proof of payment and unblinds the PoW.

  5. Providers who posted PoWs but weren't chosen by the Client can optionally unblind their PoWs by publishing the preimage.

Message Structs

Payloads

Client Ask

{
  target_difficulty: int, // Desired PoW difficulty
  timeframe_sec: int,     // The amount of time the Client is willing to wait for a PoW, from the Ask's created_at
  price_sats: int,        // The amount the Client is willing to pay for a PoW
  payload: string,        // The content of the message to be hashed
}

Provider Blinded PoW

{
  mined_id: string,       // Mined PoW hash (ID of the equivalent Nostr PoW message). The achieved difficulty is obvious even before the nonce is unblinded.
  invoice_base64: string, // Base64 encoded BOLT11, the invoice the Client has to pay to get the preimage with which the nonce can be unblinded
  timestamp: int          // Timestamp used in mined note
}

Client Preimage

{
  preimage: string        // The preimage
                          // Client acted honestly (paid) if it matches the invoice preimage hash.
                          // Provider acted honestly (sent a valid PoW) if a Nostr event with the unblinded nonce, the PoW timestamp and the Client payload hashes to the provided PoW hash. 
}

JSON on the wire

Client Ask

{
  "id": ...,
  "pubkey": ...,
  "created_at": ...,
  "kind": 100,
  "tags": [],
  "content": ...,         // Client Ask payload, as JSON
  "sig": ...
}

Provider Blinded PoW

{
  "id": ...,              // Referenced later as Blinded PoW ID
  "pubkey": ...,
  "created_at": ...,
  "kind": 100,
  "tags": [
    ["e", <t_id>],        // Trade ID
  ],
  "content": ...,         // Blinded PoW payload, as JSON
  "sig": ...
}

Client Preimage

{
  "id": ...,
  "pubkey": ...,
  "created_at": ...,
  "kind": 100,
  "tags": [
    ["e", <t_id>, ""],    // Trade ID = ID of Client Ask nostr message
    ["e", <p_id>, ""],    // Blinded PoW ID for the invoice in which this is a preimage
  ],
  "content": ...,         // Preimage
  "sig": ...
}

The on-wire payloads for a trade:

Client Ask:

{
  "target_difficulty":10,
  "timeframe_sec":5,
  "price_sats":2000,
  "payload":"Hello world, I just bought the PoW for this message"
}

Blinded PoW:

{
  "mined_id":"000bc799b094b3148599850890d9369c55959358defcb0f8bd69b32ed845c04e",
  "invoice_base64": "bG5iY3J0MjB1MXAzc2QyZHpwcDVscngzbWpwbGU4YTVhZ3BqbXR2eHh2bWprY2ZzamhldnR5dWdhM21nYTR3cWY5aHR4aHJzZHFxY3F6cGd4cXl6NXZxc3A1OGZjOXFocHRoemxkbXZxOTc3Z3d4cnQ0bHd1YzZlZzZ1dThycXdsZXk0NTdjeTAwc3h6czlxeXlzc3F6dTd5cnp1a3JkOXRubnRzM2NoaGRsYThreG1xYzZ1NmRwdjQydHRqd3V0d213a2doamxrZ21mZHMwMGo1Yzc2ZDg4dnNseTRyZjJocDBscmYwcDlhenV2aHJ1OWp3ODN6d3hsbjRncXdqdGpscw==",
  "timestamp":1661381026,
  "provider_pubkey":"625445913fc67242ade0dc8cc2d0341093ab83f11caa80cc7e1432b50f451257"
}

Preimage

{
  "preimage":"000bc799b094b3148599850890d9369c55959358defcb0f8bd69b32ed845c06d"
}

Failure Modes

A trade can fail due to

In all cases, it's obvious which party is at fault and what the penalty is. For example, an invalid message means the trade cannot continue and the perpetrator's reputation is tarnished. A PoW being posted too late means the Client does not have to pay for it. And a participant not responding when they should have had (e.g. a Client not paying for a PoW posted on time) again affects that participant's reputation.

  1. Client publishes an Ask.

    • Client may post an invalid Ask (invalid message structure, out of range values, etc.)
      • Providers can choose to ignore it
      • May reflect badly on this Client's reputation

  2. Interested Providers start working on a PoW.

    • No Provider starts working on it
      • Client will know this when no PoW is posted within the desired timeframe. Can react by increasing the price or the timeframe.

  3. When ready, Providers publish their Blinded PoW and an invoice.

    • Provider may post an invalid invoice
    • Provider may post a Blinded PoW and an invoice after the timeframe expired
      • Client may or may not pay the invoice. Not paying would not reflect badly on Client's reputation.
      • Neutral to Provider's reputation.

  4. Client chooses one solution, pays the associated invoice and publishes the preimage.

    • Client doesn't pay invoice
    • Client tries to pay but fails because Provider LN node not reachable, or no path found
      • Provider has an incentive to keep LN node running and well-connected, otherwise risks having found PoW for nothing
        • In a trade where multiple Providers posted PoWs, the Client can choose to pay another invoice for another PoW
        • Client not paying can be part of a more sophisticated reputation model
          • In a trade where only one PoW was posted: Client not having paid the invoice might be due to Provider LN node not reachable, so might not count negatively to Client's reputation
          • In a trade where multiple PoWs were posted: much more unlikely that LN nodes of all Providers were unreachable, so not paying any invoice might well count negatively to Client's reputation
    • Client pays another invoice, not the one posted by the Provider
      • Posted preimage will not match preimage hash posted by Provider.
      • This will count as not paying the trade amount.
      • Visible to any network observer, reflected in Client's reputation.
    • Client received only invalid invoices within timeframe and does not pay any of them
      • Visible to any network observer. Neutral to Client's reputation, but reflected in respective Providers' reputations.
    • Client publishes preimage for a valid invoice, but the Unblinded PoW is invalid
      • Visible to any network observer, reflected in Provider's reputation.

  5. Providers who posted PoWs but weren't chosen by the Client can optionally unblind their PoWs by publishing the preimage.

    • Provider does not unblind own PoW
      • Neutral to Provider's reputation.
    • Provider unblinds own PoW, but results in an invalid PoW.
      • Negative to Provider's reputation.

Risk and Reputation

Both participants face counterparty risk. To mitigate this, a reputation can be inferred from the counterpart's behavior in past trades.

The Client's risk is that paying a Provider's invoice might unblind an invalid PoW. To signal trustworthiness, the Provider's reputation can show whether this Provider:

The Provider faces two risks: first, whether this Client will pay for a PoW delivered on time, and two, whether other Providers will find valid PoWs on time as well and therefore be chosen by the Client.

The first risk can be informed by the Client's past reputation, which can show whether the Client:

The second risk depends on:

A Client will likely choose the fastest delivered PoW. With this in mind, a Provider can choose to prioritise the Client Asks for which it's very likely to find a PoW within the timeframe or even much sooner.

In other words, the second Provider risk can be addressed by Providers choosing to work on Client Asks where they're reasonably sure to over-deliver, or where the risk of under-delivering (and potentially not being paid) is acceptable.

Overall, the protocol provides ways for both Clients and Providers to infer the counterpart's trustworthiness and to minimize the trade risk.

Incentives

Both participants have an incentive to act honestly in a trade in which they entered.

Moreover, Providers have an incentive to work on PoWs even if they're not chosen and paid in a particular trade, because this builds up their reputation with potential future clients.

Good reputations can lead to preferential rates, or even counterparty loyalty. A Client may choose to only select a specific Provider's PoWs despite other Providers over-delivering by posting PoWs faster.

Self-trading to inflate own reputation is dis-incentivised, because a trade involves finding a new valid PoW with a valid LN invoice timestamp.

Timestamping

Reliable timestamps are needed only in step 2, when the Provider posts the blinded PoW.

More specifically, the invoice posted in Step 2 has to be:

A malicious provider could backdate their invoices with the intent of damaging the reputation of a Client. If a Client's Ask received no PoWs within its timeframe and the Client therefore paid no invoice, a later invoice that is backdated to appear within the Client's timeframe could damage the Client's reputation, making it appear that the Client hasn't paid for any valid PoW.

BOLT 72 lists requirements for the timestamp of LN protocol messages, including LN invoices. Backdating an invoice can therefore result in isolating the Provider LN node and making the invoice unpayable. However, a malicious Provider may not care about being isolated from the LN network or about losing the invoice, but may wish to only damage a Client's reputation.

A protocol modification that addresses this would have to use the relative freshness guarantees of LN messages to protect against Providers backdating their invoices. One protocol variant could require Providers to first pay a small invoice to the Client in order to find a secret that is necessary for the final PoW. The Client invoice can only be paid within its expiry timewindow and therefore Providers cannot backdate their messages.

A simpler and more robust solution is NIP-033 which allows Nostr events to include an optional OTS field. The attestation would tell observers that this message is at least as old as the OTS date. When determining reputation, messages without OTS would have a much lower weight than those with OTS.

Price Discovery

Currently, there is no way for the Providers to signal at what price per difficulty they would mine at.

However, a price signal can be deduced from recent successful trades, since all trade data is public, including prices.

Data Persistence

An accurate reputation is built on accurate past trade data. However, there is no guarantee that past trade messages will be available indefinitely. There is also no guarantee of a continuous view of past messages, as relay outages or message propagation issues could cause some periods of trade history to become temporarily or permanently unavailable.

This means that reputation, which is derived from public historical trade data, is a soft approximation and not a hard metric.

Participants can increase its reliability by locally storing trade messages, and not depending entirely on live feeds from relays.

DoS Protection for Miners

Miners may want to implement strategies against DoS. The naive case where a provider indiscriminately accepts and starts mining on Client Asks, exposes the miner to DoS attacks4.

Several strategies are possible. Here are a few examples:

Sample Scripts

Show the latest Client Asks:

echo '["REQ", "a", {"kinds": [100], "limit": 20} ]' | websocat wss://nostr-relay.wlvs.space | jq -s 'map(select(.[2].tags | length == 0)) | .[][2].content ' | jq -r . | jq .

# Latest trade IDs
echo '["REQ", "a", {"kinds": [100], "limit": 20} ]' | websocat wss://nostr-relay.wlvs.space | jq -s 'map(select(.[2].tags | length == 0)) | .[][2].id ' | jq -r .

Show the latest mined PoWs:

echo '["REQ", "a", {"kinds": [100], "limit": 10} ]' | websocat wss://nostr-relay.wlvs.space | jq -s 'map(select(.[2].tags | length == 1)) | .[][2].content ' | jq -r . | jq -r .mined_id

Show the latest published preimages (successfully complete trades) :

echo '["REQ", "a", {"kinds": [100], "limit": 30} ]' | websocat wss://nostr-relay.wlvs.space | jq -s 'map(select(.[2].tags | length == 2)) | .[][2] ' | jq -r .content
  1. ^ See last section of NIP-13: https://github.com/nostr-protocol/nips/blob/master/13.md
  2. ^ https://github.com/lightning/bolts/blob/master/07-routing-gossip.md
  3. ^ https://github.com/nostr-protocol/nips/blob/master/03.md
  4. ^ Credit to k00b for pointing this out