[Lightning-dev] Towards a gridlike Lightning Network

[ZmnSCPxj via Lightning-dev]

Good morning list,

As my award-winning and supremely notable and 
talked-about-by-the-man-on-the-street article "Cyclic Superhubs as Solution 
Towards Reasonable Lightning Network Topography" points out, cycles are a good 
way to organize the LN in order to allow easier accessibility to the network 
for all participants of all kinds.

An issue here is the need for coordination in order to set up cyclic superhubs. 
 A node acting by itself cannot form cyclic superhubs.

However, one can consider that coordination is needed only to identify peers 
with which one forms superhubs.  But we already have a system that identifies 
peers: the node gossip.

So let us assume: All nodes have similar-enough views of the publicly-visible 
peers on the node graph, as built by node gossip.

I now present an algorithm, which given a set of nodes extracted from node 
gossip, returns a peer to try connecting and funding a channel to.

--

First, start with a 32-bit number i = 0.

For each node, get hash = H(i || pubkey), where H is some standard hash 
algorithm, and pubkey is the public key of the node.  Also get our_hash = H(i 
|| our_pubkey)

Perform successive filtering.  While the set is larger than 2 nodes, 
successively compare high bits.  If the highest bit of hash does not match the 
highest bit of our_hash, remove it from the set.  If the resulting set is still 
larger than 2, match the next bit.  When the set is now 2 or 1 node, back off 
by one bit and add back the most recently removed nodes.  This yields a set 
that is at least 3 or more nodes.

Sort the nodes according to hash.

Identify where our node is in the sorted list.  Then our candidate is the next 
node in the list, or if we are the last node, then the first node in the list.

If the candidate already has a channel with us, or has no address info and 
cannot be found by DNS seed or so on, or cannot be contacted, or refuses 
incoming channels or some other error, then increment i and try finding again.

---

Even if nodes have some divergence in their own local maps of the network, 
there is the chance that the difference will be filtered away and the nodes 
that are "destined" to form a superhub can still find each other in the same 
superhub.

Assuming all nodes have the same routemap, then all nodes will form their own, 
non-overlapping superhubs for each i.  However if some nodes get to increment 
i, hopefully because it already has a channel with its destined candidate peer 
at one value of i, it can then potentially form superhubs with other nodes that 
have also reached higher i.

Regards,
ZmnSCPxj___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] AMP via HD, BN+SS, and TR

[ZmnSCPxj via Lightning-dev]

Good morning Andrew,

> Hi ZmnSCPxj,
> 
> Yep, I'm pretty sure this works the way you describe -- essentially replace
> 
> the hash challenges with adaptor signatures which are reblinded at each layer.


Thank you very much your confirmation.

> For example, with adaptor signatures + Graftroot \[1\], one party can make 
> their
> 
> commit-tx signature atomic with a delegation to a timelock script; the other
> 
> party does the same but for a different timelock script. Then maybe both 
> parties
> 
> can share the same commit tx rather than doing the symmetric thing, which 
> would
> 
> save space and simplify the protocol a bit.

Possibly not?  On each pair of symmetric commitments, an output that is 
timelocked on one commitment transaction is not timelocked on the other 
commitment transaction, and that output is signable by the same party.  E.g. in 
the simple case with a single output controlled by a single party A, A has a 
commitment transaction whose output is timelocked and unlockable by A, B has a 
commitment transaction whose output is only unlockable by A (and in particular 
not timelocked).  Each side still needs its own commitment transaction I think.

(unless Graftroot is even more magical than how I understand it: my skills 
already strain trying to understand Scriptless Script and Taproot, so possibly 
I just do not understand Graftroot well enough)

Symmetry in commitment transactions is not particularly space-heavy.  
Well-behaved nodes will never bother storing old commitments and can delete 
those from disk, and you only need to store your own commitment --- the other 
commitment is the responsibility of the counterparty to store.

> And more generally, this "output
> 
> has different spend conditions depending on who publishes to the chain" 
> primitive
> 
> seems like a really powerful thing, and AFAIK nobody has noticed this feature 
> of
> 
> Graftroot until very recently.

Ah, this is indeed very interesting!

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] AMP via HD, BN+SS, and TR

[Andrew Poelstra]

Hi ZmnSCPxj,


Yep, I'm pretty sure this works the way you describe -- essentially replace
the hash challenges with adaptor signatures which are reblinded at each layer.
Because adaptor signatures can make arbitrary sets of signatures atomic (and
don't require any precommitments in the blockchain) it's easy to do multipath
stuff this way. And using discrete logs as challenges makes reblinding and
transferrable proof-of-payment easy.

It's also true that you can use BIP32 hardened keys for the challenges. You
might as well use HMAC rather than a hash for the sake of standardness, but
I don't think there's any particular reason to do this for key derivation.

Then Taproot can hide the non-cooperative cases as you mention.


I've been working on understanding Lightning and figuring out best way to
use the full power of scriptless scripts. I think we can do better than just
dropping TR+SS into the existing architecture. (Some of AJ's recent emails
to the list have been one-sided commentary on ideas I floated to him in
person recently, but I haven't had time to get everything straight enough
in my mind to reply.)

For example, with adaptor signatures + Graftroot [1], one party can make their
commit-tx signature atomic with a delegation to a timelock script; the other
party does the same but for a different timelock script. Then maybe both parties
can share the same commit tx rather than doing the symmetric thing, which would
save space and simplify the protocol a bit. And more generally, this "output
has different spend conditions depending on who publishes to the chain" 
primitive
seems like a really powerful thing, and AFAIK nobody has noticed this feature of
Graftroot until very recently.


Cheers

Andrew

[1] 
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html


On Sun, Mar 18, 2018 at 08:25:13PM -0400, ZmnSCPxj via Lightning-dev wrote:
> Good morning list,
> 
> I sketch here the idea, of making atomic multipath payment (AMP), with the 
> properties:
> 
> 1.  Has a proof-of-payment.
> 2.  Multipath decorrelation.
> 
> Note: I am not a mathematician.  Thus, it is likely, that there is a mistake 
> here, and we cannot make this work.
> 
> First, we look at BIP32 hierarchically derived (HD) keys by Wuille.  Roughly, 
> given a parent private key k_par, we can do derive k_i child keys for integer 
> i by:
> 
> k_i = H(i || k_par * G) + k_par
> 
> where H(x) is a hash function and G is the generator point. (this it not 
> quite how BIP32 does it, it uses HMAC, maybe that is safer for some reason 
> that my non-mathematician self is unaware of...)
> 
> The parent public key K_par = k_par * G.  We can derive K_i public child keys 
> for integer i by:
> 
> K_i = H(i || K_par) * G + K_par
> 
> (I think)
> 
> Note that K_i = k_i * G still, as is usual for elliptic curve asymmetric 
> cryptography:
> 
> K_i = k_i * G = (H(i || k_par * G) + k_par) * G = H(i || k_par * G) * G + 
> k_par * G = H(i || K_par) * G + K_par
> 
> Of note is that if we know an i, a private child key k_i corresponding to 
> that i, and the public parent key K_par, we can derive the private parent key 
> k_par:
> 
> k_i = H(i || K_par) + k_par
> 
> k_par = k_i - H(i || K_par)
> 
> Now all we need is to have a conditional payment, which can only be performed 
> if the payee provides a private key which matches a public key, i.e. given x 
> * G, the payee must provide x.
> 
> Fortunately Poelstra has done this work beforehand in the Scriptless Script 
> (SS) concept, where the payee provides a T = t * G, and the Scriptless Script 
> construction requires that the payee reveal the t in order to claim the 
> payment.  I will not go into the math since there is a good chance I shall 
> make a mistake; look up discussions by better mathematicians by me.  
> Scriptless Script requires Bellare-Neven (BN) signatures to work.
> 
> Note that Scriptless Script handles only the equivalent of hashlocking.  We 
> still need a timelock in case the payee refuses to reveal the 
> proof-of-payment t.
> 
> Fortunately, Maxwell has provided a construction, taproot (TR).  This 
> construction has two top-level branches: a Bellare-Neven n-of-n, or a Bitcoin 
> Script.  We know that Scriptless Script can make an equivalent to a hashlock 
> from a Bellare-Neven n-of-n.  The other branch of a taproot construction can 
> now be a simple OP_CLTV+OP_CHECKSIG script, forming the timelock half of an 
> HTLC.
> 
> How would a multipath payment work?  The invoice would contain the parent 
> public key K_par.  From this, the payer derives as many K_i, as it needs to 
> split the payment to.  It sets up conditional payments that require 
> revelation of the private child key k_i for each K_i it derives.
> 
> When the payee receives a partial payment, it is not incentivized to claim it 
> immediately yet.  This is because revelation of even one child key k_i will, 
> in combination with the parent public key K_par, reveal the parent private 
> key 

Re: [Lightning-dev] A protocol for requesting invoices

[Corné Plooy via Lightning-dev]

> It is a public key hash, yes.  But what I refer to is that the 
> payee-determined route section, which starts from an introduction point, 
> protects the payee from being located by the payer, but how did the payer 
> contact the payee in the first place anyway?  If it was by IP or non-.onion 
> hostname, then the payee has been already located and there is no point in 
> hiding from the payer.  If it was by .onion hostname, then the payee security 
> is bounded by the security of TOR, so it is no more secure for the payee to 
> simply run its LN node on the same .onion address (which LN spec supports) 
> and provide the public key of its LN node.
>
> Note that onion routing on LN in general protects the payer and the payee 
> from being known easily by intermediate hop nodes, and this is the sole 
> intent of onion routing for now.  Presumably the payer knows how to contact 
> the payee (else how would it form a connection to the payee in order to make 
> an interactive request for invoice?).  Presumably if the payee is a merchant, 
> it knows how to send its product to the payer (and thus would know details 
> like the physical address of the payer).  And so on.  The payee-determined 
> route that starts from the introduction point protects the payee from the 
> payer, but does it indeed increase the security or is there some other way to 
> locate the payee anyway?
If that payee has a LN node that is 100% a TOR hidden service, and you
don't use a (partially) payee-determined route, the payee has to reveal
its node ID to the payer. This is not the same as revealing the physical
identity of the payee, and having a hidden service may help to keep the
two identities separated, but a LN node is a relatively long-lived
entity. Over time, the risk increases that knowledge about the node ID
(e.g. what kinds of transactions are linked to this ID) leaks out and
gets combined, revealing things you don't want to be revealed.

It may, for instance, be that some of your incoming transactions are
inherently linked to your physical identity (e.g. salary), and some
other you don't want linked to yourself. If you have to reveal your node
ID to all payers, you risk those transactions being linked to you,
either now or in the future. Running a node as a TOR hidden service is
not sufficient. However, if you manage to hide your node ID from payers,
this becomes much more difficult; you really gain some privacy.

In fact, using a TOR hidden service may not always be necessary. In some
cases, you could alternatively set up payer/payee communication over a
more-or-less anonymous physical medium; maybe using a burner phone, WiFi
with a randomized MAC address, NFC, or some other kind of radio
communication.

The alternative approach to partially payee-determined routes would be
to run different nodes for different identities and to regularly shut
down nodes and set up new ones. This requires expensive on-chain actions
though (more expensive than setting up a new TOR hidden service), and I
don't think it's good for the rest of the network either if channels are
regularly shut down. I prefer if people can have lots of privacy, even
when running only a single node.

You could roughly say that TOR is necessary because your IP address can
often be linked to you, and partially payee-determined routes are
necessary because your node ID can often be linked to you.

CJP


___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] DNS Seed query semantics clarification

[Christian Decker]

Thomas Steenholdt  writes:
> Thanks for the explanation - This was exactly the the piece of the
> puzzle I was missing. 
>
> I'd be happy to help clarify this in the BOLT10 specification, if that
> makes any type of sense? I can make a pull request for revie

Absolutely, improvements are always welcome :-)
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] High level fee mechanics

[Thomas Steenholdt]

Hi ZmnSCPxj,


Thank you so much - Exactly what I needed! 


/Thomas


From: ZmnSCPxj 
Sent: Sunday, March 18, 2018 8:48:57 PM
To: Thomas Steenholdt
Cc: lightning-dev@lists.linuxfoundation.org
Subject: Re: [Lightning-dev] High level fee mechanics

Good morning Thomas,


Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On March 19, 2018 6:24 AM, Thomas Steenholdt 
 wrote:


Hi,


I've been trying to figure out the mechanics of Lightning fees, especially in 
the case of routed payments. Unfortunately, I haven't had any success in 
finding a high level description on the topic.



I'm hoping somebody is able to point me in the right direction?

BOLT spec https://github.com/lightningnetwork/lightning-rfc contains 
everything, but is very detailed and contains the topic in multiple places.



Example:

A multi-hop routed payment where A needs to pay D through B and C. Established 
channels are A -> B -> C -> D.



What I'm looking for is a high level explanation of how fees are established, 
announced and ultimately claimed in a payment like this. Some of the questions 
that come to mind are:


- Does A know ahead of time the fees on B and C, or only when trying to set up 
the payment? And how?

Yes.  Node gossip, the `channel_update` message in BOLT#7.  This message, 
contains `fee_base_msat` and `fee_proportional_millionths`.  For each channel, 
there are two `channel_update` messages, one from each direction.  For example 
B<->C channel, B announces its fee for B->C transfers while C announnces its 
fee for C->B transfers.

The A may have obsolete information about fees (e.g. B or C change their fee 
but their `channel_update` has not propagated to A yet).  In this case, payment 
routing will fail, but the `channel_update` will also be sent as part of the 
error message returned by payment routing failure.


- How does A know the amount of fees that need to be added to the payment to 
cover all fees?

It computes it.  If D is to be given a payment with value `msatoshi` then it 
computes first the C->D fee, which is the C->D `fee_base_msat` +  (C->D 
`fee_proportion_millionts` * `msatoshi` / 1,000,000).  Add that to `msatoshi` 
and that is the payment that needs to reach C, so A computes the payment from 
B->C similarly, except the `msatoshi` is replaced with the payment that should 
reach C.  Then A knows how much it has to give to B.


- Is D aware of the full amount including fees or is that somehow hidden?

No.  D is only aware of how much C offers it.


- How are the fees actually claimed (who ends up paying whom)?

A offer B a value that is higher than what A instruct B to forward to C.  The 
difference is the fee.  Since the highest value is at the source A, A is the 
one, who ends up paying the entire fee.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev