Node ids and short channel ids blinding

decoys.md

Route Blinding

Notations

• Alice's real node_id is P_a = k_a * G
• Bob's real node_id is P_b = k_b * G
• Alice's blinded node_id is D_a = d_a * G
• Bob's blinded node_id is D_b = d_b * G
• Alice <-> Bob real short_channel_id is scid_ab
• Alice <-> Bob blinded short_channel_id is blinded_scid_ab

Single-hop blinding

Alice is connected to Bob via an unannounced channel scid_ab. Alice wants to be paid by Mallory without revealing her node_id and scid_ab.

Alice <-> Bob <- ... -> Mallory

Requirements

• Bob MUST NOT learn payment_secret.
• Mallory MUST NOT learn P_a.
• Mallory MUST NOT learn scid_ab.
• If Mallory has two invoices, she MUST NOT be able to tell both invoices come from the same node.
• Bob MAY learn D_a.

Proposal

This proposal doesn't require Bob to keep any state and doesn't require any communication between Alice and Bob. However it does require Mallory to apply some custom logic when paying the invoice.

Generate invoice (Alice)

• r <- {0;1}^256 (payment_preimage)
• s <- {0;1}^256 (payment_secret)
• d_a = HMAC256(k_a || "blinded_node_id", r)
• D_a = d_a * G
• E_b = s * d_a * G
• ss_ab = H1(s * d_a * P_b)
• blind_b = H2(ss_ab || E_b)
• blinded_scid_ab = blind_b xor scid_ab
• sign invoice with d_a

Pay invoice (Mallory)

• D_a <- signature recovery
• E_b = s * D_a
• Include E_b in onion payload for Bob

Relay HTLC (Bob)

• outgoing_scid <- onion payload
• E_b <- onion payload
• ss_ab = H1(k_b * E_b)
• blind_b = H2(ss_ab || E_b)
• scid = blind_b xor outgoing_scid
• Relay HTLC via scid
• Include E_a = blind_b * E_b in update_add_htlc to Alice

Receive payment (Alice)

• invoice info <- db.getInvoice(payment_hash)
• Recompute d_a
• Recompute E_a and verify it matches the one from update_add_htlc
• Decrypt onion with d_a
• Apply normal payment validation

Multi-hop blinding (route blinding)

Alice wants to be paid by Mallory without revealing anything else than an upper bound on her distance to a blinding node Roger.

Note that all channels used here may be either unannouced or public.

Alice <-> Bob <-> Carol <-> Roger <- ... -> Mallory

Requirements

• Bob, Carol, Roger MUST NOT learn payment_secret.
• Carol MUST NOT learn P_a.
• Carol MUST NOT learn scid_ab.
• Roger MUST NOT learn P_b, P_a.
• Roger MUST NOT learn scid_ac, scid_bc.
• Mallory MUST NOT learn P_a, P_b, P_c.
• Mallory MUST NOT learn scid_ab, scid_bc, scid_cr.
• If Mallory has two invoices, she MUST NOT be able to tell both invoices come from the same node.

Proposal

This proposal doesn't require any node to keep any state and doesn't require any communication between nodes. However it does require all nodes to apply some custom logic when paying the invoice and relaying HTLCs. This only works once enough nodes have activated this feature.

Generate invoice (Alice)

• r <- {0;1}^256 (payment_preimage)
• s <- {0;1}^256 (payment_secret)
• d_a = HMAC256(k_a || "blinded_node_id", r)
• D_a = d_a * G
• E_r = s * d_a * G
• ss_ar = H1(s * d_a * P_r) = H1(k_r * E_r)
• blind_r = H2(ss_ar || E_r)
• blinded_scid_cr = blind_r xor scid_cr
• E_c = blind_r * E_r
• ss_ac = H1(blind_r * s * d_a * P_c) = H1(k_c * E_c)
• D_c = ss_ac * P_c
• blind_c = H2(ss_ac || E_c)
• blinded_scid_bc = blind_c xor scid_bc
• E_b = blind_c * E_c
• ss_ab = H1(blind_c * blind_r * s * d_a * P_b) = H1(k_b * E_b)
• D_b = ss_ab * P_b
• blind_b = H2(ss_ab || E_b)
• blinded_scid_ab = blind_b xor scid_ab
• E_a = blind_b * E_b
• Store E_a with invoice
• Sign invoice with d_a
• Add the following routing hints to invoice (51 bytes per blinded hop):
  • (blinded_scid_ab, fee/cltv, D_b)
  • (blinded_scid_bc, fee/cltv, D_c)
  • (blinded_scid_cr, fee/cltv, P_r)
  • Note that fee/cltv must be chosen to avoid trivial matching with known public channels
  • Will probably need to overpay fees along the blinded path to be safe (have all possible channels in the anonymity set)
  • Can also add dummy hops to trick the upper bound

Pay invoice (Mallory)

• D_a <- signature recovery
• E_r = s * D_a
• Include E_r in onion payload for Roger

Relay HTLC (Roger)

• Decrypt onion with P_r
• Discovers E_r
• Compute ss_ar, unblinds scid_cr
• Forwards onion to Carol with E_c in update_add_htlc tlv

Relay HTLC (Carol, Bob)

• Find E_x in update_add_htlc tlv -> hint that a blinded node_id has been used
• Compute ss_ax and D_x
• Decrypt onion with D_x
• Unblinds scid
• Forward onion to next node with update E_x

Receive payment (Alice)

• invoice info <- db.getInvoice(payment_hash)
• Verify E_a from update_add_htlc matches stored one
• Recompute d_a
• Decrypt onion with d_a
• Apply normal payment validation

Unblinding channels via fee probing

This route blinding allows more probing than a full rendezvous scheme. With a full rendezvous scheme, Mallory would be given a pre-encrypted onion and can't probe much. With route blinding, Mallory can try different amounts since she is building the whole onion. If nodes along the blinded path act normally, it's easy for Mallory to probe and find the real channels used.

Mallory simply has to create onions with increasing fees for scid_cr, starting with a very low fee. While the fee is below the real fee of scid_cr, Mallory will get an error from Roger. Once the fee she proposed actually satisfies scid_cr, the error will come from Carol.

She can then unblind channels one-by-one by discovering their real feerate.

To mitigate this, when nodes along the blinded path are offered a fee that's too low, they should:

• return a dummy error encrypted with a throw-away key: Mallory will receive an error she can't decrypt and doesn't know which node generated it
• hold the HTLC for a random amount of time before sending the error (otherwise Mallory can still use timing to guess what node errored out)

Even with those mitigations Mallory can discover the real feerate of one of the blinded channels. She uses the correct feerate for all but one channel, and for the target one she tries feerates until the payment succeeds. Once the payment succeeds she knows the approximate of the target channel (but since the payment succeeded, she can't continue probing).

Maybe nodes along the blinded path could use a slightly different feerate than the one they publicly advertize? Add a small fuzzing to it to blind them more?

Are those mitigations enough? Or can a clever attacker still work around them?

Notes

Once we use payment points instead of preimages (post-Schnorr), Mallory doesn't need to do anything special. Instead Alice can create her payment preimage as r = s * d_a. In that case payment_hash = E_b. When Bob receives an HTLC to forward with an unknown scid, he tries recovering the real scid with:

scid = H2(H1(k_b * payment_hash) || payment_hash) xor scid

Once the preimage is revealed, Mallory learns d_a. But it's probably ok as it's a one-time key.

Questions

• Do we need to be careful with blinded_scid_ab collisions (only 64 bits)?
  • Doesn't seem to be an issue: may just allow attackers to learn a few bytes of the blinding factor
• What hash function do we choose for H2:
  • Truncate SHA256/Blake3/Keccak to first 8 bytes?
  • Blake2s?

References

• Mailing list post

Sounds good, I'm available any time tomorrow morning (CET), can you send me an invite with a time slot that works for you?

Done!