t-bast/decoys.md

## decoys.md

      
    Raw
  

              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