Re: [Lightning-dev] Handling nonzerobasefee when using Pickhard-Richter algo variants

2021-08-30 Thread René Pickhardt via Lightning-dev
Dear ZmnSCPxj,

thank you very much for this mail and in particular the openess to tinker
about a protocol change with respect to the transport layer of HTLCs /
PTLCs! I fully agree that we should think about adopting our onion
transport layer in a way that supports local payment splits and merges to
resemble the flowing nature of payments more closely! While an update for
that might be tricky I think right now is a perfect moment for such
discussions as we kind of need a full upgrade anyway when going to PTLCs
(which in fact might even be helpful with a local splittling / merging
logic as secrets would be additive / linear) Before I elaborate let me
state a few things and correct an error in your mail about the convex
nature of the fee function and the problems of the min-cost flow solver.

I agree with you (and AJ) that there is a problem in the base fee that
comes from overpaying when dissecting a flow into paths which share a
channel. However this is not related to the convexity issue. In a recent
mail [0] I conductd the calculation demonstrating why the current fee
function f(x)=x*r+b is not even linear (every linear function should be
convex). As described in the paper the problem is for the min cost flow
solving algorithms if the cost-function (in that case the fee function) is
neither linear nor convex.

The issue that breaks convexity is really subtle here and comes when going
from 0 flow to some flow. In that sense I apologize that the paper might be
slightly misleading in its presentation. While convexity is often checked
with the second derivative argument our function is in fact defined on
integers and thus not even differentiable which is why the argument with
the second derivative that we use to show the convexity of the negative log
probabilities is not transferable.

Let us better go with the wikipedia definition of convexity [1] that
states:
"In mathematics, a real-valued function is called convex if the line
segment between any two points on the graph of the function lies above the
graph between the two points."

So how you would test convexity is by making sure that for any two values
x_1 and x_2 the line connecting the points (x_1,f(x_1)) and (x_2,f(x_2))
lies above all other points (x,f(x)) for x  \in {x_1, , x_2}. In our
case because f(0)=0 and f(2)=2r+b
The line connecting those two points is defined by l(x)=((2r+b)/2)*x =
(r+b/2)*x which means that l(1)=r+b/2.
however f(1) = r+ b which is larger than l(1) for any positive value of b.
(Note that again with a zerobasefee b=0 we have f(1)=r=l(1) which would be
sufficient)

If you implement the capacity scaling algorithm for a min-cost flow solver
you will see that the algorithm linearizes the convex costs all the time by
switching to a unit cost in each delta-scaling phase (as described in
section 9, 10.2 and 14.1 through 14.5 of the book [2] that we refer to in
the paper and that Stefan already mentioned to you). This seems very
ismilar to the thoughts you seemed to have in your mail (though even after
reading them 3 times I can't verify how you turned the base_fee into a
proportional term by switching to a unisized payment amount). You will also
recognize that the base fee is not linearizable as a unit cost and will
break the reduced cost optimality criterium in the delta phases of the
algorithm. That being said in our mainnet tests we actually used 10k and
100k sats as a fixed min unit size for htlcs in flow computation but more
about that in the already announced and soon to come mail about the mainnet
tests.

Long story short while the base fee yields indeed a problem for a flow to
be dissected into paths the issues seems to be much more severe because of
this non continious jump when going from f(0) to f(1).

All that being said I am very delighted to see that you propose a protocol
change towards "whole flow payments" (Please allow me to still call them
payment flows as our paper title suggested). In my recent mail [0] I said I
would want to write another mail about  our mainnet test results and the
the consequences for the protocol, node operators, users etc... One of the
consequences goes fully along with the idea that you described here and
thus I very much like / appreciate your idea / proposal! As the other mail
was too long anyway let me quickly copy and past the text about the 5
consequences for the protocol that I saw from my draft and note that the
second one goes fully along with your proposal:

Consequences for the Protocol


1.) As we send larger amounts we confirmed what many people already knew:
Stuck and hanging HTLCs are becoming more of a problem. The main reason
that in our experiments we could not deliver the full amount was that we
"lost" htlcs as they did neither arrive at the destination in time nor did
they return as errors to the sender quickly enough before the mpp timeout.
We very very much need a cancable payment mechanism [3]. I know taproot and
PTLCs are coming but I 

[Lightning-dev] Do we really want users to solve an NP-hard problem when they wish to find a cheap way of paying each other on the Lightning Network?

2021-08-26 Thread René Pickhardt via Lightning-dev
Dear fellow lightning developers,

with a mixture of shock and disbelief I have been following the (semi)
public discussions for the last 6 weeks and the reaction of some companies
/ people that reached out to me. I have to say I am really surprised by the
amount of hesitation that - despite obvious and overwhelming mathematical
evidence -  a small group of people demonstrated in response to our
results. While I cannot make any sense of this I decided to post here
despite the fact that I believe everything that needed to be said is
already written and explained clearly in our paper [0] about optimally
reliable and cheap payment flows on the Lightning Network. My hope is that
this mail can help us to

* clarify a few misunderstandings
* stop having opinionated discussions about mathematical facts
* find a quick agreement on how to move on

As far as I can tell currently all implementations use some form of
Dijkstra algorithm in payment delivery with a strong emphasize on finding
paths with cheap fees. The reason seems to be that it is a well established
assumption that users would prefer a cheap solution on the market of
offered routing fees. (while routing nodes of course try to offer fees that
maximize their earnings)

If we look at the mentioned paper there are several results (I will soon
publish a separate mail here discussing some of the more interesting
results and consequences but I decided to split it and put this one here
first as it seemed to be more urgent). One of the results which I will
discuss now is the realization that - given the current fee function -
finding the cheapest payment flow is an NP-hard problem because the fee
function is neither linear nor convex.

Our fee function is `f(x) = rx + b` where `r`= fee rate, `b`=base fee and
`x` is the amount we want to send.

As we thought it was obvious that the function is not linear we only
explained in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee
breaks convexity. But as the question came up several times (for example
here [1]) I want to stress that the fee function - despite looking like a
straight line - is **not linear**. While writing this post I realized that
the issue might be that the concept of linearity [2] from the field of
linear algebra seems to be intermixed in the english language and American
school system with the concept of linear polynomials / linear functions
[3]. So maybe that is part of the problem that emerged in previous
discussions.

When I write linear here I am referring back to the concept of linearity
from linear algebra (c.f.: [2]) which btw seems to be also the main reason
why schnorr signatures [2b] are so powerful that everyone is happy they
will find their way into bitcoin. We know that a necessary condition for a
function to be called linear is that the following property holds:

f(x+y)=f(x)+f(y)

however if we look at our setting we see that:

f(x+y) = r(x+y) + b

and

f(x)+f(y) = rx+b + ry+b = r(x+y) + 2b

equality (and thus linearity) only holds if

r(x+y)+b = r(x+y) + 2b <==> b = 2b

the later is true if and only if `b=0`. In other words: **Our current fee
function is only linear if we set the base fee to zero.**

On the other side we refer to research in our paper that shows that an
optimal solution (in this case optimal means cheapest) cannot be found if
the fee function is neither linear nor convex. I think one of the biggest
misunderstandings that I saw in the discussions is that people seem to have
thought this has something to do with our new / proposed method. But as far
as I can tell it does absolutely not have any connection to it. Instead and
as most of you probably know the property to be an NP-hard problem is
completely independent of the used algorithm. This is why in the paper we
suggested to drop the base_fee and mentioned in the German Podcast that the
same effect could already be achieved by node operators today by setting
their base fee to 0. it is also the reason why we asked before we published
the paper why the base fee was introduced and what purpose it served [4].

I am so surprised by some of the resistance because some of the biggest
talking points by Lightning Network critics in the past have been that
routing is either not solved or if it was solved it would be NP-hard. In
our paper we show that delivering a payment can always be modeled as a min
cost flow and the resulting optimization problem will indeed be NP-hard
depending on the cost function. Given the current fee function with a non
zero base fee and the goal of minimizing fees that is followed by all
implementations I have to agree with such critics and say yes, in that
particular case delivering a payment optimally is an NP-hard problem.

Luckily there are things we can do about it:

1.) we can decide to have a different optimization goal. For example in the
Paper we used a previously introduced probabilisitic model that optimizes
for reliability instead of fees and we show that in that case the function

Re: [Lightning-dev] Proposal for an invoice pattern with an embedded Bitcoin onchain address

2021-07-10 Thread René Pickhardt via Lightning-dev
Hi,

I am sorry to hear you had trouble with payment pathfinding. However if I
understand your suggestion correctly I think the proposed functionality
already exists in a very similar way in today's invoices with a mechanism
called fallback address. The main difference seems to be that the fallback
adress is not a human readable part of the invoice string but encoded with
the other data in the bech32 part of the invoice.

Check bolt 11 [1] on github for more detail but I copied the relevant
snippets from there to this mail.


   - f (9): data_length variable, depending on version. Fallback on-chain
   address: for Bitcoin, this starts with a 5-bit version and contains a
   witness program or P2PKH or P2SH address.

The f field allows on-chain fallback; however, this may not make sense for
tiny or time-sensitive payments. It's possible that new address forms will
appear; thus, multiple f fields (in an implied preferred order) help with
transition, and f fields with versions 19-31 will be ignored by readers.

[1]:
https://github.com/lightningnetwork/lightning-rfc/blob/master/11-payment-encoding.md

With kind regards Rene Pickhardt

 schrieb am Sa., 10. Juli 2021, 07:56:

> Hi,
>
> I propose a new LN invoice pattern that contains a Bitcoin address for
> onchain transfer as backup.
>
> Motivation: My dream is to have an app wallet that works in a totally
> abstract and transparent way onchain and/or LN depending on the situation.
> Phoenix wallet almost achieves this, but there is still a certain
> LN/onchain distinction that confuses users a bit.
>
> I use Phoenix daily. Today, for some reason, I couldn't pay a friend.
> Payment failed in several attempts. It was not clear why. The fact is that
> I managed to transfer to Breeze and then from there I was finally able to
> transfer to the final destination. For some reason it had no liquidity on
> the specific route. These exception cases greatly confuse the most
> non-expert users. If, on the invoice my friend sent to me, I had embedded a
> Bitcoin address, the wallet could simply ask: "Couldn't send via LN, do you
> want to send it on-chain at XPTO fee rate? It can take a while."
>
> That way, in case of payment failure, there is an immediate onchain backup
> alternative, useful especially when rates are low, like now.
>
> The format could be something like:
>
> :::
>
> Example:
>
> ln:v2:Hi,
>
> I propose a new invoice pattern that contains a Bitcoin address for
> onchain transfer.
>
> Motivation: My dream is to have a portfolio that works in a totally
> abstract and transparent way onchain and/or LN depending on the situation.
> Phoenix wallet almost achieves this, but there is still a certain
> LN/onchain distinction that confuses users a bit.
>
> I use Phoenix daily. Today, for some reason, I couldn't pay a friend.
> Payment failed in several attempts. It was not clear why. The fact is that
> I managed to transfer to Breeze and then from there I was finally able to
> transfer to the final destination. For some reason it had no liquidity on
> the specific route. These exception cases greatly confuse the most
> non-expert users. If, on the invoice my friend sent me, I had embedded a
> Bitcoin address, the wallet could simply ask: "Couldn't send via LN, do you
> want to send onchain at XPTO rate?"
>
> That way, in case of payment failure, there is an immediate onchain backup
> alternative, useful especially when rates are low, like now.
>
> The format could be something like:
>
> :::
>
> Example:
>
>
> ln:v1:bc1qucfe06nunhrczh9nrfdxyvma84thy3eugs0825:lnbc20m1pvjluezpp5qqqsyqcyq5rqwzqfqqqsyqcyq5rqwzqfqqqsyqcyq5rqwzqfqypqhp58yjmdan79s6qqdhdzgynm4zwqd5d7xmw5fk98klysy043l2ahrqsfpp3qjmp7lwpagxun9pygexvgpjdc4jdj85fr9yq20q82gphp2nflc7jtzrcazrra7wwgzxqc8u7754cdlpfrmccae92qgzqvzq2ps8pqqpq9qqqvpeuqafqxu92d8lr6fvg0r5gv0heeeqgcrqlnm6jhphu9y00rrhy4grqszsvpcgpy9qqgq7qqzqj9n4evl6mr5aj9f58zp6fyjzup6ywn3x6sk8akg5v4tgn2q8g4fhx05wf6juaxu9760yp46454gpg5mtzgerlzezqcqvjnhjh8z3g2qqdhhwkj
>
> Thank you.
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] bLIPs: A proposal for community-driven app layer and protocol extension standardization

2021-06-30 Thread René Pickhardt via Lightning-dev
Hey everyone,

just for reference when I was new here (and did not understand the
processes well enough) I proposed a similar idea (called LIP) in 2018 c.f.:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-July/001367.html


I wonder what exactly has changed in the reasoning by roasbeef which I will
repeat here:

*> We already have the equiv of improvement proposals: BOLTs. Historically*

>* new standardization documents are proposed initially as issues or PR's when *

>* ultimately accepted. Why do we need another repo? *


As far as I can tell there was always some form of (invisible?) barrier to
participate in the BOLTs but there are also new BOLTs being offered:
* BOLT 12: https://github.com/lightningnetwork/lightning-rfc/pull/798
* BOLT 14: https://github.com/lightningnetwork/lightning-rfc/pull/780
and topics to be included like:
* dual funding
* splicing
* the examples given by Ryan

I don't see how a new repo would reduce that barrier - Actually I think it
would even create more confusion as I for example would not know where
something belongs. That being said I think all the points that are
addressed in Ryan's mail could very well be formalized into BOLTs but maybe
we just need to rethink the current process of the BOLTs to make it more
accessible for new ideas to find their way into the BOLTs? One thing that I
can say from answering lightning-network questions on stackexchange is that
it would certainly help if the BOLTs where referenced  on lightning.network
web page and in the whitepaper as the place to be if one wants to learn
about the Lightning Network

with kind regards Rene

On Wed, Jun 30, 2021 at 4:10 PM Ryan Gentry via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Hi all,
>
> The recent thread around zero-conf channels [1] provides an opportunity to
> discuss how the BOLT process handles features and best practices that arise
> in the wild vs. originating within the process itself. Zero-conf channels
> are one of many LN innovations on the app layer that have struggled to make
> their way into the spec. John Carvalho and Bitrefill launched Turbo
> channels in April 2019 [2], Breez posted their solution to the mailing list
> for feedback in August 2020 [3], and we know at least ACINQ and Muun
> (amongst others) have their own implementations. In an ideal world there
> would be a descriptive design document that the app layer implementers had
> collaborated on over the years that the spec group could then pick up and
> merge into the BOLTs now that the feature is deemed spec-worthy.
>
> Over the last couple of months, we have discussed the idea of adding a
> BIP-style process (bLIPs? SPARKs? [4]) on top of the BOLTs with various
> members of the community, and have received positive feedback from both app
> layer and protocol devs. This would not affect the existing BOLT process at
> all, but simply add a place for app layer best practices to be succinctly
> described and organized, especially those that require coordination. These
> features are being built outside of the BOLT process today anyways, so
> ideally a bLIP process would bring them into the fold instead of leaving
> them buried in old ML posts or not documented at all.
>
> Some potential bLIP ideas that people have mentioned include: each lnurl
> variant, on-the-fly channel opens, AMP, dynamic commitments, podcast
> payment metadata, p2p messaging formats, new pathfinding heuristics, remote
> node connection standards, etc.
>
> If the community is interested in moving forward, we've started a branch
> [5] describing such a process. It's based on BIP-0002, so not trying to
> reinvent any wheels. It would be great to have developers from various
> implementations and from the broader app layer ecosystem volunteer to be
> listed as editors (basically the same role as in the BIPs).
>
> Looking forward to hearing your thoughts!
>
> Best,
> Ryan
>
> [1]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-June/003074.html
>
> [2]
> https://www.coindesk.com/bitrefills-thor-turbo-lets-you-get-started-with-bitcoins-lightning-faster
>
> [3]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-August/002780.html
>
> [4] bLIP = Bitcoin Lightning Improvement Proposal and SPARK =
> Standardization of Protocols at the Request of the Kommunity (h/t fiatjaf)
>
> [5]
> https://github.com/ryanthegentry/lightning-rfc/blob/blip-0001/blips/blip-0001.mediawiki
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


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


[Lightning-dev] Lightning Network Protocol Suite Diagram - Request for feedback

2021-04-06 Thread René Pickhardt via Lightning-dev
Dear fellow Lightning Developers,

as you all probably know Andreas, Roasbeef and I are working on writing the
book "Mastering the Lightning Network" and I am happy to say that there has
been quite some progress over the last 18 months. In Particular it lead to
a diagram of the Lightning Network Protocol Suite which is the reason I am
sending this email. We would love to have your feedback and criticism (not
on my little design skills but on the content!). You can find the diagram
at:

https://commons.wikimedia.org/wiki/File:Lightning_Network_Protocol_Suite.png

As a Wikipedia Contributor I shared the current Version on Wikimedia
commons where the Diagram can easily be updated but the link will stay the
same as they also allow version control of files. Eventually I am happy to
open a PR and add this to BOLT 0 or the Readme of the lightning-rfc. But
first we would welcome and encourage your feedback and discussion.
Especially the naming of some layers are somewhat novel but also the labels
for the boxes and the geometry and semantics of the boxes themselves.

To give you some context: As you know the BOLTs are somewhat linked and
intermixed. For example BOLT2 describes the channel state machine with the
HTLCs which is mainly needed for routing, BOLT 07 is named gossip routing
though the main onion routing is happening in BOLT 04, ... I am not saying
that such things would be wrong. However I made the experience that those
iterdependencies can sometimes be a bit confusing when introducing the
protocol to new people.

Consequently this lead to plenty of internal discussions which we concluded
by deciding that we need an architecture diagram for the Lightning Network.
After a couple internal iterations we believe it is time to present our
current diagram to the community and hope to get even more feedback before
we `fix` it and use it also as a guide for some of the chapters in the
book. You can see a part of our discussions and previous versions on github
https://github.com/lnbook/lnbook/issues/342

Also please note that BOLT 03 and BOLT 5 which is the Bitcoin stuff is
currently not part of the diagram at all.

with kind Regards Rene



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


Re: [Lightning-dev] Towards more reliable payment path finding via probabilistic modeling the uncertainty of channel balance

2021-03-18 Thread René Pickhardt via Lightning-dev
Dear Elias,

Thanks for your kind words!

In the paper we suggest clients sort paths by probability but skip the ones
that charge fees that are too high for a user, which could be defined in a
user setting. I should have repeated that when I expressed that implicitly
with this sentence in my mail:

"This means that nodes which provide a lot of liquidity and thus utility
might be able to charge higher fees (as long as they are small enough so
that users are willing to pay them)"

I think that is very similar to your suggestion and of course one could
include not only fees but other criteria while filtering.

In general I think it is reasonable to be aware of the most likely path as
the inverse probability is the number of expected attempts. This if due to
failures and updating the knowledge and channel probabilities the remaining
path probabilities drop below a certain (configurable) value one might want
to stop trying or consider a more expensive path.

So if for example a user was to say I am willing to pay up to 0.5% of the
amount in routing fees but after a few attempts the likeliest path has only
a 0.01% chance a client could say something like: "it is very unlikely to
deliver the payment but if you pay 0.7% fees there is a chance (want to
try?)" Of course at some point onchain / opening a new channel might be
cheaper which would contribute to the potential emerging fee market.

Instead of filtering paths by fees one could also weight the probabilities
with the fees. An easy (but maybe not optimal) approach for that would be
to multiply the log probabilities (which have to be low for high success)
with the fees. That being said I think the main important result is that we
should always be aware of (multi)path probabilities during the trial and
error phase especially in order to make splitting decisions and to
determine when to stop trying

Best Rene

Elias Rohrer  schrieb am Do., 18. März 2021, 09:34:

> Dear René,
>
> thank you for the great work!
>
> One quick question regarding the consequence you mentioned: it seems
> plausible that manipulating the path choices would become harder, if the
> ability of doing so was correlated with the capacity locked in the network.
> However, if paths were only chosen regarding the probability of payment
> success (and neglecting accruing fees), couldn't high-capacity nodes in
> absence of competition simply raise their fee levels indefinitely, since
> they would be chosen regardless? Do you have any ideas how to protect
> against this?
>
> I imagine that some kind of 'mixed' strategy could be reasonable, in which
> certain paths are pre-filtered based on the probability of payment success,
> and then the final path is selected along the lines of the currently
> deployed fee rate/CLTV risk assessment?
>
> Kind Regards,
>
> Elias
>
> On 17 Mar 2021, at 13:50, René Pickhardt via Lightning-dev wrote:
>
> Dear fellow Lightning Network developers,
>
> I am very pleased to share with you some research progress [0] with
> respect to achieving better payment path finding and a better reliability
> of the payment process.
>
> TL;DR summary: In payment (multi)path finding use the (multi)paths with
> the highest success probability instead of the shortest or cheapest ones.
> (multi)path success probability is the product of channel success
> probabilities. Given current data crawled on the Network the channel
> success probability grows with the capacity of the channel and with smaller
> amounts that are to be sent (which is both intuitively obvious).
> (Multi)path success probability thus declines exponentially the more
> uncertain channels are included.
>
> I understand that the actual payment path finding is not part of the spec
> but I think my results should be relevant to the list since:
>
> a) The payment pathfinding is currently based on trial and error approach
> which has consequences that have not been studied well in the context of
> the Lightning Network
> b) All implementations will use some heuristics in order to achieve
> pathfinding.
> c) Quick path finding is a crucial for a good user experience.
> d) The uncertainty of payment paths is frequently quoted as a major
> criticism of the Lightning Network (c.f. [1]) and I believe the methodology
> of this paper can be used to address this.
>
> The main breakthrough is that  a very simple model that puts the
> uncertainty of channel balances at its heart. We belief the uncertainty of
> channel balance values is the main reason why some payments take several
> attempts and thus take more time.  With the help of probability theory we
> are able to define the channel success and failure probabilities and
> similarly (multi)path success and failure probabilities. Other Failure
> reasons could also be included to the

[Lightning-dev] Towards more reliable payment path finding via probabilistic modeling the uncertainty of channel balance

2021-03-17 Thread René Pickhardt via Lightning-dev
Dear fellow Lightning Network developers,

I am very pleased to share with you some research progress [0] with respect
to achieving better payment path finding and a better reliability of the
payment process.

TL;DR summary: In payment (multi)path finding use the (multi)paths with the
highest success probability instead of the shortest or cheapest ones.
(multi)path success probability is the product of channel success
probabilities. Given current data crawled on the Network the channel
success probability grows with the capacity of the channel and with smaller
amounts that are to be sent (which is both intuitively obvious).
(Multi)path success probability thus declines exponentially the more
uncertain channels are included.

I understand that the actual payment path finding is not part of the spec
but I think my results should be relevant to the list since:

a) The payment pathfinding is currently based on trial and error approach
which has consequences that have not been studied well in the context of
the Lightning Network
b) All implementations will use some heuristics in order to achieve
pathfinding.
c) Quick path finding is a crucial for a good user experience.
d) The uncertainty of payment paths is frequently quoted as a major
criticism of the Lightning Network (c.f. [1]) and I believe the methodology
of this paper can be used to address this.

The main breakthrough is that  a very simple model that puts the
uncertainty of channel balances at its heart. We belief the uncertainty of
channel balance values is the main reason why some payments take several
attempts and thus take more time.  With the help of probability theory we
are able to define the channel success and failure probabilities and
similarly (multi)path success and failure probabilities. Other Failure
reasons could also be included to the probability distributions.

With the help of crawling small samples of the network we observe that the
probability distributions of the channel balances can be estimated well
with a uniform distribution (which was a little bit surprising) but leads
to surprisingly easy formulas.  We are able to quantify the uncertainty in
the channels and use negative Bernoulli trials to compute the expected
number of attempts that are necessary to deliver a payment of a particular
amount from one node to another participant of the network. This can be
used to abort the trial and error path finding if the probability becomes
to low (expected number of attempts too high)

We can mathematically show what people already knew (and draw conclusions
like the mentioned ones from it):

a) smaller amounts have higher success probabilities
b) the success probability declines exponentially with the number of
uncertain channels in a (multi)path.
c) depending on the payment pair, amount and splitting strategy it can be
decided into how many parts a payment should be split to achieve the
highest success probability.
d) In particular for small amounts splitting almost never makes sense.

We demonstrate that sorting paths by their descending success probability
during the trial and error payment process (instead of currently used
heuristics like fees or route length) and updating the probabilities from
current failures decreases the number of average attempts and produces a
much faster delivery of payments.

Additionally we looked what happened if BOLT14 [2] was implemented or nodes
otherwise would pro-actively rebalance their channels according to previous
research [3] and realized that the observed prior distribution changes from
uniform to normal. This is great as small payments become even more likely
(as one would intuitively assume and as previously showed) Our results show
that probabilisitic path finding on a rebalanced network works even better
(as in fewer failed attempts) which is yet another hint why BOLT14 might be
a good idea. However as mentioned the results can be implemented even
without BOLT14 or without other protocol changes by any implementation.

One consequence from the paper that is not discussed heavily within the
paper that I find pretty interesting is that if implementations follow the
recommendation to use a probabilistic approach they will tend to route
payments along high capacity channels. While the fee based routing can
easily be gamed by dumping fees it is much harder to provide more
liquidity. And if done this would actually provide a service to the
network. This means that nodes which provide a lot of liquidity and thus
utility might be able to charge higher fees (as long as they are small
enough so that users are willing to pay them) which would probably allow
the emergence of a real routing fee market.

One note on the question of MPP: In the last couple weeks I have been
collaborating with Christian Decker. I belief (by using the methodology
from this paper) to also have a definite solution to the question of:

How to split a payment into k parts and how many funds to allocate to each
path to 

Re: [Lightning-dev] Collaborated stealing. What happens when the final recipient discloses the pre-image

2020-07-17 Thread René Pickhardt via Lightning-dev
Hey Ankit,

The lightning network sees the possession of a preimage as a proof of
payment. And I believe everyone agrees that a court should rule in favor of
A forcing E to deliver the good or reimburse A. The reason is that
possession of the preimage matching the signed payment hash from E is a
much stronger evidence of A actually having paid than E claiming to not
have received anything.
This is also due to the fact that guessing the preimage can practically be
considered impossible (though there is a tiny likelihood)

If E breaches the protocol by giving the preimage to C (for free) instead
of claiming the money from D (and thus settling the Htlc) it will be
considered E's problem, that E did not get reimbursed but just gave out the
preimage for free. (actually E's so called "partner in crime" did get
reimbursed). Even if D would testify that E never settled the Htlc one
would wonder why E never settled the incoming htlc as they should only have
created a payment hash for which they know the preimage. Since A can
actually provide one it is again unlikely if E for example claims they just
used a random hash for which they didn't know the preimage because they
wanted to just see if A has enough liquidity.

With kind regards Rene

Ankit Gangwal  schrieb am Fr., 17. Juli 2020, 08:43:

> Consider A wants to send some funds to E.
>
>
>
> They don’t have a direct payment channel among them. So, they use a
> following path A-B-C-D-E. A is the sender of payment and E is final
> recipient.
>
>
>
> E sends the hash of a secret r to A, A passes on the hash to B, B to C, C
> to D, and D to E.
>
>
>
> E discloses the secret to C (a partner in crime with E) and E do not
> respond to D. C gives the secret to B (settling the HTLC between them).
> Then, B gives the secret to A (settling the HTLC between them).
>
>
>
> A sent (and lost) the money, as E denies receiving the money (and the
> promised service/good).
>
>
>
> How the lightening network sees this? Out of their control?
>
>
>
> --
>
> A_G
>
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Disclosure of a fee blackmail attack that can make a victim loose almost all funds of a non Wumbo channel and potential fixes

2020-06-17 Thread René Pickhardt via Lightning-dev
Hey everyone and of course good morning ZmnSCPxj (:

about 11 months ago I discovered a potential blackmail attack with HTLCs
after answering this question on stack exchange (c.f
https://bitcoin.stackexchange.com/questions/89232/why-is-my-spendable-msat-much-lower-than-msatoshi-to-us/89235#89235).
This attack is similar to the one that was possible with tx malleability on
the funding transaction without the segwit upgrade (c.f.
https://commons.wikimedia.org/w/index.php?title=File:Introduction_to_the_Lightning_Network_Protocol_and_the_Basics_of_Lightning_Technology_(BOLT_aka_Lightning-rfc).pdf=126).
Meaning an attacker can force a victim to lose money and use this fact to
blackmail the victim, to potentially gain / steal some of the lost funds.

TL;DR:
=
* Depending on the circumstances this attack allows an attacker to make
channel partners lose a substantial amount of BTC without substantial costs
for the attacker.
* Depending on the exact circumstances this could be for example ~0.15 BTC.
In particular it demonstrates why opening a channel is not an entirely
trustless activity.
* The attacker will reliably only be able to force the victim to lose this
amount of Bitcoin.
* It is not clear how in practice the attacker could gain this amount or
parts of it as this would involve not only game theory but also rather
quick communication between attacker and victim and customized Lightning
nodes which at least for the victim would be unlikely to exist.
* None of the suggested fixes seems to be satisfying though the current
solution of lowering the maximum amount of HTLCs that can concurrently be
in flight seems to be a reasonable start for now.


Timeline on Disclosure
=
I have disclosed this attack on Sunday July 21st 2019 to Fabrice Drouin
(and shortly after to Christian Decker) in a phone call who in turn has
discussed it with people from the other implementations. From his feedback
I understood that people working on implementations have been more or less
aware of the possibility of this attack. Fabrice also mentioned that he
believed implementations currently try to mitigate this by setting low
limits of allowed / accepted HTLCs in flight. However at that time this was
only true for e-clair. It is now also true for c-lightning and as far as I
know still not true for lnd. Fabrice said that the people he talked to have
suggested that I should eventually describe the attack in public to raise
awareness (also from the group of node operators) for the problems related
to this attack. He also suggested that - if I wanted to - I should update
the rfc with recommendations  and warnings. While I already have in mind
how to change the rfc I wanted to start the discussion first. Maybe some
people find better fixes than just a warning that I have in mind. So far I
didn't do anything because I wanted to also give lnd the chance to handle
the problem.

There are two reasons I disclose this attack today:
1.) I think almost 1 year is enough time to do something about it. The only
implementation that afaik didn't yet is lnd (see below) but I got roasbeefs
ok last week to go ahead and publish the attack anyway so that we can have
a broader discussion on mitigation strategies.
2.) The attack seems actually very similar to the one described in the
"Flood & Loot: A Systemic Attack On The Lightning Network" - paper which
came out 2 days ago (c.f.: https://arxiv.org/abs/2006.08513 ). I believe
any person reading that paper will understand the possibility of the attack
that I describe anyway so I believe it is now more or less public anyway
and thus time for an open / public discussion.

The main difference between the two attacks (if I understand this novel
paper correctly) is: In the "flood and loot"-attack one tries to steal the
HTLC output of the victims. Where in the "flood and blackmail"-attack that
I describe I try to to force the victim to lose almost all its funds due to
high on chain fees (Which I could use to blackmail the victim)

Description of the attack
===
Let us assume the victim has funded a channel with an attacker meaning it
will have to pay the fees for the commitment transaction in case of a force
close.

During a fee spike (let us assume fee estimators suggest 150 sat / byte)
the attacker spams this channel with the maximum possible amount of HTLCs
that the protocol allows. The HTLCs can be of a small value but need to be
bigger than the dust limit so that additional outputs are actually added to
the commitment transaction which makes it quite large in Bytes. According
to the BOLTs these are 483 additional outputs to the commitment
transaction.
The direction of HTLCs are chosen so that the amount is taken from the
`to_remote` output of the attacker (obviously on the victims side it will
be the `to_local` output) For the actual attack it does not matter in which
direction the HTLCs are spammed but economically the direction I propose
makes even more sense for the attacker 

Re: [Lightning-dev] Force close of channel with unresolved htlc

2020-05-05 Thread René Pickhardt via Lightning-dev
Dear Subhra,

as discussed bilaterally and after clarification of your question the
situation is as follows:

Let us assume A and B have a channel in which A has 4 tokens and B has 6
tokens

Now A offers an HTLC with the amount of 2 tokens and B accepts (receives)
the offer then A and B both have negotiated the HTLC output in the most
recent commitment transaction.

If A stops responding and B has to force close the channel a commitment
transaction with 3 UTXOs will hit the chain. One UTXO with 2 tokens
spendable by A, another one with 6 tokens spendable by B and the received
HTLC output with 2 tokens. This one can be spend by two different
conditions as in the offchain protocol

1.) Before the timelock of the HTLC has passed B can spend the output if B
knows his to_local HTLC secret AND the preimage. OR
2.) after the timelock A can spend the output if A knows the to_remote HTLC
secret.

the mechanism with HTLCs can be read upon in BOLT 2 (channel operation
https://github.com/lightningnetwork/lightning-rfc/blob/master/02-peer-protocol.md)
and the scripts can be seen in BOLT 3:
https://github.com/lightningnetwork/lightning-rfc/blob/master/03-transactions.md

A less technical summary that is more focused on explaining the concepts is
currently being developed in the routing chapter of mastering the lightning
network:
https://github.com/lnbook/lnbook/blob/43ce57298b4da345286ae3b53c42ea3eb9d9b056/routing.asciidoc

With kind regards Rene Pickhardt

On Tue, May 5, 2020 at 8:06 PM Subhra Mazumdar <
subhra.mazumdar1...@gmail.com> wrote:

> Hi,
>  I am having a doubt regarding force closure of channel. Suppose A->B
> there is an htlc which has been established for transfering fund. Now
> suppose for some unfortunate reason B doesnt have the witness to resolve
> htlc and the mean time A suffers crash fault. Then can B close the channel
> given that it has no way out of resolving the htlc due to lack of witness?
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Direct Message draft

2020-02-20 Thread René Pickhardt via Lightning-dev
Hey Rusty,

I was very delighted to read your proposal. But I don't see how you prevent
message spam. If I understand you correctly you suggest that I can
communicate to any node along a path of peer connections (not necessarily
backed by payment channels but kind of only known through channel
announcements of gossip) via onions and these onions which are send within
a new gossip message are not bound to any fees or payments.

Let's assume I just missed some spam prevention mechanism or that we can
fix them. Do I understand the impact of your suggestion correctly that I
could use this protocol to

1.) create a fee free rebalancing protocol? Because I could also attach a
new lightning message inside the onions that would allow nodes without
direct peer connection to set up a circular rebalancing path.
2.) have the ability to communicate with nodes further away than just my
peers - for example to exchange information for pathfinding and / or
autopilots?


With kind regards Rene

Rusty Russell  schrieb am Do., 20. Feb. 2020, 10:37:

> Hi all!
>
> It seems that messaging over lightning is A Thing, and I want to
> use it for the offers protocol anyway.  So I've come up with the
> simplest proposal I can, and even implemented it.
>
> Importantly, it's unreliable.  Our implementation doesn't
> remember across restarts, limits us to 1000 total remembered forwards
> with random drop, and the protocol doesn't (yet?) include a method for
> errors.
>
> This is much friendlier on nodes than using an HTLC (which
> requires 2 round trips, signature calculations and db commits), so is an
> obvious candidate for much more than just invoice requests.
>
> The WIP patch is small enough I've pasted it below, but it's
> also at https://github.com/lightningnetwork/lightning-rfc/pull/748
>
> diff --git a/01-messaging.md b/01-messaging.md
> index 40d1909..faa5b18 100644
> --- a/01-messaging.md
> +++ b/01-messaging.md
> @@ -56,7 +56,7 @@ The messages are grouped logically into five groups,
> ordered by the most signifi
>- Setup & Control (types `0`-`31`): messages related to connection
> setup, control, supported features, and error reporting (described below)
>- Channel (types `32`-`127`): messages used to setup and tear down
> micropayment channels (described in [BOLT #2](02-peer-protocol.md))
>- Commitment (types `128`-`255`): messages related to updating the
> current commitment transaction, which includes adding, revoking, and
> settling HTLCs as well as updating fees and exchanging signatures
> (described in [BOLT #2](02-peer-protocol.md))
> -  - Routing (types `256`-`511`): messages containing node and channel
> announcements, as well as any active route exploration (described in [BOLT
> #7](07-routing-gossip.md))
> +  - Routing (types `256`-`511`): messages containing node and channel
> announcements, as well as any active route exploration or forwarding
> (described in [BOLT #7](07-routing-gossip.md))
>- Custom (types `32768`-`65535`): experimental and application-specific
> messages
>
>  The size of the message is required by the transport layer to fit into a
> 2-byte unsigned int; therefore, the maximum possible size is 65535 bytes.
> diff --git a/04-onion-routing.md b/04-onion-routing.md
> index 8d0f343..84eff9a 100644
> --- a/04-onion-routing.md
> +++ b/04-onion-routing.md
> @@ -51,6 +51,7 @@ A node:
>  * [Legacy HopData Payload Format](#legacy-hop_data-payload-format)
>  * [TLV Payload Format](#tlv_payload-format)
>  * [Basic Multi-Part Payments](#basic-multi-part-payments)
> +* [Directed Messages](#directed-messages)
>* [Accepting and Forwarding a
> Payment](#accepting-and-forwarding-a-payment)
>  * [Payload for the Last Node](#payload-for-the-last-node)
>  * [Non-strict Forwarding](#non-strict-forwarding)
> @@ -62,6 +63,7 @@ A node:
>* [Returning Errors](#returning-errors)
>  * [Failure Messages](#failure-messages)
>  * [Receiving Failure Codes](#receiving-failure-codes)
> +  * [Directed Message Replies](#directed-message-replies)
>* [Test Vector](#test-vector)
>  * [Returning Errors](#returning-errors)
>* [References](#references)
> @@ -366,6 +368,13 @@ otherwise meets the amount criterion (eg. some other
> failure, or
>  invoice timeout), however if it were to fulfill only some of them,
>  intermediary nodes could simply claim the remaining ones.
>
> +### Directed Messages
> +
> +Directed messages have an onion with an alternate `hop_payload`
> +format.  If this node is not the intended recipient, the payload is
> +simply a 33-byte pubkey indicating the next recipient.  Otherwise, the
> +payload is the message for this node.
> +
>  # Accepting and Forwarding a Payment
>
>  Once a node has decoded the payload it either accepts the payment
> locally, or forwards it to the peer indicated as the next hop in the
> payload.
> @@ -1142,6 +1151,11 @@ The _origin node_:
>- MAY use the data specified in the various 

Re: [Lightning-dev] Few questions

2020-02-09 Thread René Pickhardt via Lightning-dev
Good Morning Cezary,

you might want to direct questions about understanding the lightning
network protocol like yours to https://bitcoin.stackexchanage.com as this
mailinglist is more devoted towards driving the development of the
protocol. Anyway here are the answers to your questions 2 and 3 and
probably also to the first one though I am not entirely sure if I
understand exactly what you are asking for. In case I misunderstood you
suggest to put follow up questions on stackexchange.

1. Is this possible that by sending funds without invoice, the last hub
> prepares the last HTLC with small amount to the payee? In other words - Can
> payee detect, that the last HTLC amount is smaller that it should be?
>

But in general the payee will only release the preimage for an invoice if
the payee is satisfied with the amount - which is usually specified in the
invoice. If you talk about keysend then the payee does not expect an amount
and will most likely release the preimage as the payee would consider this
to be free money


> 2. Are there additional data added to the end of onion encrypted list of
> HTLCs in order to prevent last hub to guess, that it is the last hub in the
> route?
>

yes the onions are always of constant size (20 * 65 Byte = 1300 Byte) This
process of padding is well described in the Sphinx paper
https://cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf and in BOLT 04
https://github.com/lightningnetwork/lightning-rfc/blob/master/04-onion-routing.md

3. When payment is during confirmation, are channels locked entirely, or
> only for the in flight payment amount? In other words - can single channel
> process more that single transaction at once?
>

HTLCs are additional outputs in the commitment transaction. The protocol
allows for up to 483 htlcs concurrently in flight as specified in BOLT 04 ("
max_accepted_htlcs is limited to 483 to ensure that, even if both sides
send the maximum number of HTLCs, the commitment_signed message will still
be under the maximum message size. It also ensures that a single penalty
transaction can spend the entire commitment transaction, as calculated in BOLT
#5

.")

However the the standard of implementations and recommendation is 30. This
means that a single payment is not freezing the channel. It however "locks"
the amount of that payment which for the time until settlement cannot be
used by either party of the channel for other payments / activities.

with kind regards Rene


> I would like to kindly pleas to reply in simple words, as my English is
> still far from being perfect.
>
> Best Regards,
> Cezary Dziemian
>
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Research on proactive fee free channel rebalancing in the friend of a friend network / and roadmap for a protocol extension

2020-01-07 Thread René Pickhardt via Lightning-dev
Good morning ZmnSCPxj, and list,

the answer to your question is absolutely yes and we can can achieve this
actually in a very simple and elegant way.

Please find attached a clear and simple adaption of the algorithm described
from the paper for a general multipath payment and a small python code
example available at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network/blob/master/code/mppalgo.py
that computes this in a model case (assuming 10 payment channels that all
have a capacity of 1 BTC just to save some lines in coding). The output of
the code is at the end of the Mail.


Algorithm to conduct payments which optimally (? I have not proved this yet
but I see no way that would be more optimal with respect to the
Ginicoefficients) reduces the imbalance of nodes when conducting a
(multipath)payment.

Let us assume a node $u$ wants to pay someone for an amount $a$.

1. We assume the payment was already achieved over some channel(s) and
compute the new node balance coefficient $\nu'_u$ after this imaginary
payment has been conducted as $\frac{\tau_u - a}{\kappa_u}$. remember
\tau_u is just the total amount of funds that node $u$ currently has and
$\kappa_u$ is the sum of the capacities of all its payment channels.
2. For all online channel partners $\{v_1,...,v_d\}$ we compute
$\zeta_{(u,v_1),...,\zeta_{(u,v_d})}$
3. Let us assume channels are ordered such that
$\zeta_{(u,v_1)>...>\zeta_{(u,v_d'})}$ and omit channels with $\zeta(u,v_i)
- \nu'_u < 0$ Those channels need more funds and should not be used to pay.
That is why we might have $d' < d$
5. Compute all $d'$ rebalancing amounts $r_i =
c(u,v_i)*(\zeta_{(u,v_i)}-\nu'_u)$ as in the paper but with the new node's
balance coefficient!
6. set $R = sum_i r_i$
7. distribute payments across channels  $a_i = a*r_i/R$ being the amount
$a_i$ that should be paid on channel $i$. Recall $a_i < a$ and $sum_i a_i =
a$ and $a_i < r_i$. This means that with this computation all channel have
enough liquidity to do the subpayments and the subpayments will add up to
the amount (ignoring channel reserves)
8. probe for paths for each amount and channel (potentially split the
amount for a channel across several paths that all start with that
channel). As we don't know what the rest of the network looks like we don't
know if we will be able to find paths for each channel (as before)

Now the really nice side effect: We could compute routing hints for the
invoices in the same way! by now taking the channels where $\zeta(u,v_i) -
\nu'_u$ < 0. We could also split the amounts in that way and also give
amounts together with the routing hints. This would allow a sender to send
the payments in a way that is most benefitial too us. (The sender could
also follow the above method for their outgoing channels) Only the rest of
the network might suffer worse imbalance bus guess what they charge a
routing fee for that service!

With these nice results let me just review some notation from the paper (so
that we in future might all agree to this wording/termonology):

* *Rebalancing* is the operation of moving funds along circular paths
between channels. As pointed out in the past this does not really change
the topology of the graph as the properties like the max flow / min cut
will not be affected by this. As such some people (including myself) have
argued in the past that multipathpayments are sufficient for path finding
as they will quicker find the max flow and that rebalancing is not
necessary. However the results of my research indicate that such operations
will increase the likelihood of arbitrary payments to succeed and thus (at
least in my interpretation) increase the reliability of the network.
* in particular a node is *balanced* if the zeta values are the same and
the gini coefficient is zero. While this is the case for all channels being
50-50 there are far less strict ways of achieving a good balance than
asking for channels to be opened in such a way that everyone ha 50-50.
* *Making payments actually changes the topology* of the network (similarly
to opening and closing channels). With the notation of the paper the \tau
values change and are part of the topology. This way "rebalancing" with
submarine swaps using loop or any of those services is not a rebalancing
operation in the sense of the paper and/or the above point but in fact a
change of topology.
* combining topology changes with rebalancing operations (which is often
the goal when making submarine swaps) seems however to be a good idea. In
that sense your general thought of rebalancing while paying should be
pursued.

Last but not least the promised output of the example code:

$ python3 mppalgo.py
0.3 initial imblance
new funds 4.8 and new node balance coefficient 0.48

Conduct the following payments:
channel 0 old balance: 1.00, payment amount 0.22 new balance 0.78
channel 1 old balance: 0.90, payment amount 0.18 new balance 0.72
channel 2 old 

[Lightning-dev] Research on proactive fee free channel rebalancing in the friend of a friend network / and roadmap for a protocol extension

2019-12-23 Thread René Pickhardt via Lightning-dev
Dear fellow Lightning Developers,

today my research paper (together with Mariusz Nowostawski) "*Imbalance
measure and proactive channel rebalancing algorithm for the Lightning
Network*" was published on arxiv: https://arxiv.org/abs/1912.09555 The
LaTeX project as well as the code for the experiments (simulation and
evaluation) are open source (however not too well documented yet) at:
https://github.com/renepickhardt/Imbalance-measure-and-proactive-channel-rebalancing-algorithm-for-the-Lightning-Network
I am open for questions, feedback, discussions and in particular critical
remarks. Let me just state that I was quite surprised about the positive
impact of implementing such a rebalancing protocol in particular since in
its current form it seems to protect the privacy of nodes (more research
would be needed to be sure that the privacy is really protected).

# From the abstract:

*We further show that the success rate of a single unit payment increases
from 11.2% on the imbalanced network to 98.3% in the balanced network.
Similarly, the median possible payment size across all pairs of
participants increases from 0 to 0.5 mBTC for initial routing attempts on
the cheapest possible path. We provide an empirical evidence that routing
fees should be dropped for proactive rebalancing operations. Executing 4
different strategies for selecting rebalancing cycles lead to similar
results indicating that a collaborative approach within the friend of a
friend network might be preferable from a practical point of view*

# Some thoughts and context:

Already in my proposal of JIT Routing
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-March/001891.html
I suggested to allow for fee free rebalancing and do the rebalancing
operations in the friend of a friend network. With this research I tested
both assumptions and - unless someone points out methodological errors in
my evaluation - we now have strong evidence that this in deed makes a lot
of sense. I think it is in particular interesting that 0.5 mBTC can be
routed successfully on first attempt in 50% of the cases. I guess using
this together with Multi part / path payments as discussed in the future
work section of the paper might be the way to go for the lightning network.
I envision that while payments along several paths are routed and settled
nodes could already rebalance their channels in particular if we introduce
the redundancy to multi part / path payments as suggested in the Boomerang
Paper https://arxiv.org/abs/1910.01834 by Vivek Bagaria, Joachim Neu and
David Tse.

# Roadmap for BOLT 14 (Fee free Rebalancing Transport):

If no strong objections exist I would try to extend the BOLTs with the
following to be able to implement the rebalancing algorithm across the
network (as with JIT routing nodes can already opt to implement the
algorithm for themselves but this is probably not to useful from an
economic point of view).

* BOLT 07: a new gossip query and reply `query_want_rebalance_channel_ids`
/ `reply_want_rebalance_channel_ids` to ask channel partners on which of
their channels they want inbound / outbound liquidity. The query could
already include an optional offer how much the node initiating the
rebalancing operation is willing to offer while the reply could have an
optional offer field stating how much they nodes are willing to rebalance
(as the paper shows nodes might not have consensus about the amount and the
algorithm currently works by agreeing on the lowest value). Of course this
extension needs some protection against probing attacks to protect the
privacy of nodes.
* BOLT 14: (Fee Free Rebalancing Transport) While it seems tempting to
Reuse BOLT04 with a different realm that omits fees for the rebalancing
cycles (which nodes would have to accept then) this seems impossible as the
onions are not public and nodes could not verify that this is really a
rebalancing operation and not a payment which tries to "steel" fees. While
we might be able to extend BOLT 02 with a new message that transports a
"rebalancing" onion together with the keys for every envelop so that
everyone can verify that in fact this fee free onion is a rebalancing cycle
it seems plausible to have an open tansport for fee free rebalancing to
start with. We could also make it a feature flag and allow nodes to signal
if they support fee free rebalancing. I guess for backwards compatebility
this should be done in any case.
* One problem / attack vector with circular fee free payments that I see is
that if Alice wants to pay David she could initiate a rebalancing onion: A
--> B --> C --> D --> A with the paymenthash that David has created in an
invoice. David would just not set up the final HTLC from him to Alice as he
wanted to receive money from Alice. As far as I see this attack would only
be possible if Alice and David have a channel which they could have used
for the payment right away. Not using that channel is effectively a
rebalancing operation which is exactly 

[Lightning-dev] Congestion and Flow control for Multipath Routing

2019-07-15 Thread René Pickhardt via Lightning-dev
Dear fellow BOLT devs,

in this mail I want to suggest a congestion and flow control mechanism to
improve the speed and reliability of multi path routing schemes. This is
the first of a couple of emails that I will write in the following weeks as
I have used my break in hospital not only to recover but to tinker quite
a bit about path finding and routing algorithms on the lightning network.

Problem statement
===
Currently on the lightning network we have the issue of stuck payments [0].
As soon as an onion is sent it is out of the sender's control. This problem
seems to be in particular drastic if we wish to use Atomic Multi Path
routing [1] (which in the described form is not compatible with my
proposal. I believe my proposal should be compatible with the status quo of
base-AMP). The entire payments and HTLCs of a multipath payment will only
be settled once enough incoming HTLCs arrived at the recipient (meaning the
sum of amounts is bigger or equal to the amount specified in the invoice).
This has the following list of downsides:

- One malicious actor (who is just not forwarding the onion but also not
signaling an error) is enough to interrupt the entire payment process and
freeze all other HTLCs even of partial payments the actor is not part of.
- The entire payment process takes as long as `max_{p \in paths}(t(p))`
where `t(p)` is the time it took for path `p` to set up (and settle) HTLCs
- More HTLCs will be reserved by the network for a longer time. This means
more liquidity is bound / reserved and channels could even become unusable
if the 483 HTLC limit is reached.

Protocol Goals
===
I looked at the windowing mechanism used in TCP to achieve congestion
control and transferred this concept to the setting of the Lightning
Network. This idea is motivated by the Spider Network paper [2] which
mentions that in a simulation the success rate of payments is increased
when changing the lightning network from a circuit switched payment process
(which we currently have with our atomicity requirements) to a packet
switched mechanism that includes congestion control (though in that
publication congestion control had a different semantics than in has in my
proposal).

Protocol Benefits
=
- Improve the speed of multipath payments
- Reduce load from the network (in particular don't lock liquidity for such
a long time)
- less congestion at single nodes (I assume this is not a problem at this
point in time)
- more privacy (different preimages are used along different paths and
overall payments might become smaller or of uniform size)
- usual benefits from AMP

Protocol idea (base version)
=
Disclaimer: This base version has obvious drawbacks but I decided to
include it as it transports the idea.

A regular payment on the Lightning Network for amount `x` has a Payment
Hash `H` and a preimage `r`.  If a recipient would now accept that this
payment could be split over up to `n` paths the recipient would create a
sha-chain of preimages and payment hashes with `n` elements

```
r_0 = rand()
H_0 = H(r_0)
r_{i+1} = H_i
H_{i+1} = H(r_{i+1})
```

The payment process is initiated by the recipient providing H_{n-1} and
signaling (in the invoice) that up to `n` preimages are available to
complete this payment.

A sender can now decide to split the payment amount `x` into `n` seperate
payments for example of the amounts `x/n` though different splits should be
possible. Once the preimage of the first partial payment is returned the
payer learns the payment hash wich can be used for the next partial
payment. (One issue is that while we have a proof of payment we do not
necessarily have a proof of amount - which is true for the regular
lightning case though with a single atomic payment this is not an issue as
the preimage will not be relased if the amount is too low. We could avoid
this issue by demanding that mulipath payments have to be at least of size
`x/n`)

This protocol makes the AMP process sequential and reduces the load from
the network. Congestion (which is a local problem of routing nodes) becomes
less likely if only HTLCs are locked up for a partial payment independent
of the success or failure of other partial payments. However in the base
version there is a severe downside:

**Sequential payments will make the payment process even longer since it is
not the max time needed over all payments but the sum of times needed.**

We can resolve this issue by introducing flow control via a windowing
mechanism and allowing concurrency of partial payments

Protocol Overview (suggested version)
==
Let us assume the receiving node supports a window size of `s` concurrent
payments. Now the payee will not only create one sha-chain of `n` payment
hashes as in the base version but `s` sha-chains of `n` payment hashes.
In the invoice we would now transport the following data:

* `n` (we need a different letter as n is already taken) = amount of
partial 

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

2019-06-25 Thread René Pickhardt via Lightning-dev
Hey Ugam,

I like the very clearly communicated idea and the fact that we can do crazy
stuff with the filler of the onions. I have two concerns / questions:

1.) In pathfinding we actually try to make payments smaller (like moving to
AMP) instead of combining payments. I think it was shown several times that
the probability of finding a path (successful route) decreases with larger
amounts. So saving fees might actually not be the metric that we are trying
to optimize.
2.) Am I correct that this proposal would only work with the spontaneous
payment scenario as the payment hashes of Eric and Grace could not just be
added up as easy as the preimages can to get the overall payment hash for
Alice? So in that sense on the invoice based system your proposal is not
working and we don't have a proof of payment as Alice already knows the
preimages? Could one resolve this in the world of scriptless scripts or
when changing to secret / curve point based preimages based on the discrete
log?

best Rene

On Tue, Jun 25, 2019 at 7:07 AM Ugam Kamat  wrote:

> Hey guys,
>
>
>
> I’m kind of new to this mailing list, so let me know if this has been
> proposed previously. While reading Olaoluwa Osuntokun’s Spontaneous
> Payment proposal, I came up with the idea of simultaneous payments to
> multiple parties using the same partial route. In other words, say Alice,
> Bob, Charlie, Dave and Eric have channel opened with one another, and say
> Dave also has channel with Frank who has channel with Grace. Now, Alice is
> at a restaurant and wants to pay the bill amount to Eric (the restaurant
> owner) and a tip to Grace (who was her waiter). In the current scenario,
> Alice would have to send two payments A->B->C->D->E and A->B->C->D->F->G.
> However, if we repurpose the onion blob
>  in the same way
> as is needed for Spontaneous Payments, we can create a scenario where there
> is no path duplication. Dave would split the payments, one to Eric and
> other going to Grace through Frank. The preimage PM used in commitments
> A->B, B->C and C->D will be a function of pre-images P1 of D->E and P2 of
> D->F and F->G such that PM = f(P1, P2).
>
>
>
> *Proposal can be implemented by repurposing the onion in similar fashion
> as Spontaneous Payments with slight modification*
>
> This proposal works in similar fashion to Spontaneous Payment proposal, by
> packing in additional data in the unused hops. For B and C the onion blob
> will be identical to other lightning payments. When D parses the onion, the
> 4 MSB of the realm will tell D how much data can be extracted. This data
> will encode the hashes of the pre-images that would be used for commitment
> transaction towards Eric and other towards Frank.  For simplicity and
> privacy, I propose using 2 onion blobs for the data. So the payload can be
> 64 + 33 bytes = 97 bytes. The first byte would indicate how many hashes are
> packed, so we have 96 bytes for the payload, meaning we can pack a maximum
> of 3 hashes for 3 route payments from D. Now D will split the onion (18
> hops as it has used the first two for bifurcation data) into number of
> routes. In the above case it will be 9 hops each. Now these two onions are
> similar to other lightning payments. The first hop tells D the
> short-channel id, amount to forward, CLTV and the padding. Since, the
> preimage is 32 bytes, we can pack that in one single hop that is received
> by the final party. This leaves the remaining 7 hops can be used for
> routing. Below figure depicts the onion split in terms of how A will create
> it. D will add the filler to make each onion have 20 hops. Onion data is
> encoded in the same order in which the payment hashes are packed in the
> bifurcation data for D.
>
>
>
> *Calculating the preimages*
>
> Eric and Grace will parse the onion and use the pre-images for settlement.
> Let P1 represent the pre-images of D->E and P2 of D->F and F->G. When the
> pre-images arrive at node D, it will combine them such that PM = f(P1, P2).
> The easiest way for both A and D to calculate that will be PM = SHA256(P1
> || P2 || ss_d). Where || represents concatenation and ss_d is the shared
> secret created using the ephemeral public key of sender (the one generated
> by Alice) and private key of Dave. The need for using shared secret is to
> prevent the vulnerability where one channel operator who has nodes across
> both branches can use them to calculate the PM. Using shared secret also
> ensures that it is in fact D that has parsed them together.
>
>
>
> *Advantages of this proposal:*
>
>- Commitment transactions between A & B, B & C, and C & D now carry
>only one HTLC instead of two
>   - This means lower fees in case of on-chain settlement
>   - Lower routing fees for Alice as Bob and Charlie would not get to
>   charge for two routings
>   - Since 483 is the max limit of the htlcs nodes can accepts,
>   preventing duplication will 

Re: [Lightning-dev] Routemap scaling (was: Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0)

2019-03-28 Thread René Pickhardt via Lightning-dev
Dear ZmnSCPxj and fellow lightning developers,

I want to point out two things and make a suggestion for a new gossip
message.

A good pruning heuristic is "channel capacity", which can be checked
> onchain (the value of the UTXO backing the channel is the channel capacity).
> It is good to keep channels with large capacity in the routemap, because
> such large channels are more likely to successfully route a payment than
> smaller channels.
> So it is reasonable to delete channels with low capacity when the routemap
> memory is becoming close to full.
>

Intuitively (without simulation). I encourage to make that process not
deerministic but rather probabilistic. It would be good if everyone had a
different set of channels. (which is somewhat achieved with everyone
keeping their local view)

Nodes still need to track their direct channels (so they are implicitly
> always in the routemap).
>

I strongly advice that the local view should be extended. Every node should
always track their friends of a friend network. Maybe we could even create
a new gossip query message `query_ask_egonetwork` that asks for the
egonetwork of a node (the egonetwork are all the direct friends of a node
together with their friendships) every node knows at least the nodes in
their ego network and over time also the edges between them.

If I was interested in my friend of a friend network I could just send the
`query_ask_egonetwork` message to all my peers.

Best Rene






But payee nodes making BOLT1 invoices could also provide `r` routes in the
> invoice, with the given routes being from nodes with high-capacity
> channels, so that even if the intermediate channels are pruned due to low
> capacity, it is possible to get paid.
>
> Regards,
> ZmnSCPxj
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Outsourcing route computation with trampoline payments

2019-03-28 Thread René Pickhardt via Lightning-dev
Dear Pierre-Marie and fellow lightning developers,

I really like that suggestion. In the context of JIT routing I was
tinkering about the same idea (is it possible for sending nodes to only
know a small part of the network - for example the friend of a friend
network - to save Hardware / gossip bandwidth requirements) but I was
thinking about a different solution which I want to drop in here. (I
believe yours is better though)

My thought was to use rendez-vous routing. This would mean the sender would
have to provide a rendez vous point from his local (friend of a friend?)
network and the recipient provides a route to him/herself. Only the
recipient has to know the entire network topology.

One problem with rendez vous routing is of course that the routing fails if
the route from the rendez vous point does not work. This again could be
mitigated with JIT routing.

In the context of JIT routing it also makes sense to "overpay" fees so that
JIT nodes could rebalance without loss. Making my solution also
probabilistic with the fees. The fact that this pattern of probabilistic
fees occurs for the second time now leads me to the following 2 more
general ideas (maybe we should start a new thread if we discuss them to
stay on topic here) that might help with routing.

1.) A different fee mechanism. Let us (only as a radical thought
experiment) assume we drop the privacy of the final amount in routing. A
sending node could offer a fee for successful routing. Every routing node
could decide how much fee it would collect for forwarding. Nodes could try
to collect larger fees than the min they announce but that lowers the
probably for the payment to be successful. Even more radical: Nodes would
not even have to announce min fees anymore. Turning routing and fees to a
real interactive market

2.) A virtual hierarchical address space. Maybe we should start thinking
about the creation of a semantic overlynetwork / address space for nodes
similar to IP. This would allow any node to just have a pruned network view
but still make smart routing decisions. Obviously we would have to find a
way to assign virtual network addresses to nodes which might be hard.

The second suggestion would be of particular interest in your case if N
also did not know the entire network and has to decide to whom to to
forward for the final destination D.

Sorry for "hijacking" your suggestion and throwing so many new ideas but in
my mind this seems all very connected /related.

Best Rene


Pierre  schrieb am Do., 28. März 2019, 23:25:

> Hello List,
>
> I think we can use the upcoming "Multi-frame sphinx onion format" [1]
> to trustlessly outsource the computation of payment routes.
>
> A sends a payment to an intermediate node N, and in the onion payload,
> A provides the actual destination D of the payment and the amount. N
> then has to find a route to D and make a payment himself. Of course D
> may be yet another intermediate node, and so on. The fact that we can
> make several "trampoline hops" preserves the privacy characteristics
> that we already have.
>
> Intermediate nodes have an incentive to cooperate because they are
> part of the route and will earn fees. As a nice side effect, it also
> creates an incentive for "routing nodes" to participate in the gossip,
> which they are lacking currently.
>
> This could significantly lessen the load on (lite) sending nodes both
> on the memory/bandwidth side (they would only need to know a smallish
> neighborhood) and on the cpu side (intermediate nodes would run the
> actual route computation).
>
> As Christian pointed out, one downside is that fee computation would
> have to be pessimistic (he also came up with the name trampoline!).
>
> Cheers,
>
> Pierre-Marie
>
> [1]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-February/001875.html
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] I just released more than 200 slides trying to give an Overview of BOLT 1.0 for beginners. Feedback welcome!

2019-03-20 Thread René Pickhardt via Lightning-dev
Hey everyone,

as you know I am just a mathematician and not a cryptographer by training
who is interested and amazed by the Lightning Network Protocol. I joined
this open source effort pretty late (in the beginning of 2018) and tried to
catch up ever since. At that time reading the BOLTs (despite the fact that
Rusty had his helpful blog articles) was really hard for me.

Over the past year - especially due to your help and open ears - I was able
to catch up by a lot. Yesterday I held a 4 hour workshop giving an
extensive overview about the Lightning Network and BOLT 1.0.

I decided to open source the slides to give something (hopefully useful)
back to the community. To the best of my knowledge this is the most
extensive overview of the BOLTs in form of slides and I also tried to
restructure the content in the hope of making it easier to approach fo
newbies like I was a year ago.

Please feel free to fork the slides on the google doc address:
https://docs.google.com/presentation/d/1-eyceLlSmcLpbPJLzj6_CnVYQdo1AUP3y5XD716U-Lg

I uploaded the pdf version of the slides at
https://commons.wikimedia.org/wiki/File:Introduction_to_the_Lightning_Network_Protocol_and_the_Basics_of_Lightning_Technology_(BOLT_aka_Lightning-rfc).pdf

Obviously I am very happy if you have suggestions how the slides could be
improved even further. Probably I will still have some mistakes with them.
But maybe you have more comments on a meta level about the structure or
detail level or visualizations...

Therefor I will be happy if you send back a pdf with comments. I also share
a commentable version with this mailinglist on google docs:
https://docs.google.com/presentation/d/1YCKZzE53xjnBndl3U0uy1-bHO4Y0rlAwgrnujzef1sY


I will present the slides next time on chaincodelabs lightning residency in
late june where - as far as I know - the talks will also be recorded. So
any feedback before then will be highly appreciated.

While this mail was note particularly about development I hope it is not
considered offtopic. In case you do so I apologize for any inconvenience.

With kind Regards Rene


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Potential Privacy issue with dual funded channels

2019-03-15 Thread René Pickhardt via Lightning-dev
Hey everyone,

during the spec meeting we have discussed intensively about dual funded
channels and potential game theory with the fees however I now believe that
we missed out another important crucial part which is the privacy of the
node providing liquidity.

While I have not seen a concrete example for a channel establishment
protocol that supports dual funded channels I have seen this proposal (
https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-November/001532.html
)  for advertising channel liquidity which assumed that the `open_channel`
message would be modified as follows:

`open_channel`:
new feature flag (channel_flags): option_liquidity_buy [2nd least
significant bit]
push_msat: set to fee payment for requested liquidity
[8 liquidity_msat_request]: (option_liquidity_buy) amount of dual funding
requested at channel open

...

If a node cannot provide the liquidity requested in `open_channel`, it must
return an error.

With such a protocol I could now (basically only at the cost of internet
traffic) probe a lower bound for the amount of BTC available by a node that
allows for dual funded channels and abort the channel establishing process
at some time before I ever spend / lock any of my own bitcoin.

As I can even participate in the peer protocol without having a single
channel open this situation seems to be even more severe.

I don't have a clear suggestion how to mitigate against this. One general
potential idea / solution would be to make spamming / probing more
expensive. For example we could require the person to open a channel first
and then ask the partner to splice something in (meaning we don't allow for
one tx dual funded channels). In that case the node requesting liquidity
had to do an onchain tx. also the requests to splice in can be identified
and the person who feels to be probed can choose to fail the channel. I am
not happy with my barrier as it would still be able to relatively cheaply
abuse this and we run into a whole bunch of game theory about fees again.

As the lightning network seems very keen to provide strong privacy to its
users (c.f.: onion routing, keeping channel balances private, encrypted
transport layer,...)  I thought it is worthwhile pointing out the problem
with the privacy for dual funded channels even though I don't have a
concrete solution yet.

best Rene


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Just in Time Routing (JIT-Routing) and a channel rebalancing heuristic as an add on for improved routing success in BOLT 1.0

2019-03-05 Thread René Pickhardt via Lightning-dev
Hey everyone,

In this mail I introduce the Just in Time Routing schema (aka JIT Routing).
Its main idea is to mitigate the disadvantages from our current source
based routing (i.e.: guessing a route that will work in the sense that it
has enough liquidity in each channel) and make the routing process a little
bit more like the best effort routing that we know from IP-forwarding. As
far as I know this will not decrease the privacy of the nodes. As part of
this Routing scheme nodes need to be able to quickly rebalance their
channels. Thus in this mail I also propose a heuristic for doing this
efficiently which I have implemented and seems to provide pretty good
results. Obviously the heuristic should be tested with the help of a
simulation. I did not have the chance to do that yet. Partly also because I
am lacking a proper dataset and I don't want to do this on artificial data.

The advantages of JIT Routing are:
* it is possible to do now without any protocol modification. In particular
no modifications of the onions are necessary.
* routing nodes can already easily implement it. By implementing it they
will increase the routing success even for nodes which are running older
implementations
* it seems to be logically equivalent to AMP Routing. In particular its
properties will also help base AMP once it is part of the protocol.
* local channel balance information along the route can now be part of the
path finding process while not decreasing the privacy by sharing
information about channel balances with others. In fact the privacy of
nodes is even being increased.

The disadvantages seem:
* it might economically not be incentivized for a routing node in every
situation. Theoretically it can even happen that a node pays a fee in order
to use this technique but can't earn the routing fee as the onion fails
later. Nodes can implement risk management strategies to mitigate this
issue.
* The routing process might take a longer time as it starts sub routing
processes.
* While doing JIT routing the capacity for channels should be reserved even
before HTLCs are set up (to prevent hostile recursive chains of rebalancing
operations)

Obviously routing single big payments is a challenge for the lightning
network. During the developer summit in Adelaide we have agreed to put Base
AMP to BOLT 1.1. To review Base AMP the idea is basically after receiving a
payment hash to create several onions on various routes to the recipient.
While Base AMP in theory can find the maxflow / min cut and achieve maximum
liquidity it is not clear yet how well Base AMP will really work.

While it has been shown that smaller payments have a higher chance to be
routed successfully there is the downside that we have more payments which
increases the likelihood that any one of those payment eventually fails. As
far as I know there have not been any studies researching this fact. Also
the fact remains that Base AMP is still a source base routing protocol
putting the sender into a tough spot as it has to guess which routes might
work.

How to JIT Routing?

For the BOLTs we basically need one Recommendation (in fact even today
nodes can do this without this explicit recommendation, but I would suggest
to add the recommendation):

If a node cannot forward an incoming HTLC because the node has not enough
funds on the outgoing channel the node MAY pause the routing process and
try to rebalance the channel that misses liquidity. If it isn't able to
rebalance the channel it should fail the onion sending back an insufficient
wire funds error `temporary_channel_failure`

Let us consider the following Graph and situation for an example:

  100 / 110 80 / 200
S --> B > R
  \ /
80/200  \ /  100/200
  \ /
 T

Meaning we have the following channels:
S ---> B capacity: 110   A funds: 100  B funds:  10
B ---> R capacity: 200   B funds:  80  R funds: 120
B ---> T capacity: 200   B funds:  80  T funds: 120
T ---> R capacity: 200   T funds: 100  R funds: 100

Let us assume S wants to send a payment of 90 to R. With this distribution
of funds this will not work with a single route S ---> B ---> R as the
channel B--->R can only forward 78 (taking the channel reserve of 1% into
consideration)

Now with Base AMP after a protocol update this would be resolved by making
two onions forwarding for example 45 each. Also S would have to pay more
routing fees as the basefee of B will be charged twice.

Onion 1: S ---> B ---> R
Onion 2: S ---> B ---> T ---> R

However it is S again who has to guess how the problems with the liquidity
are it does not know how B has spread its funds between R and T (and
potentially other channels)

With the above recommendation in place B can create a different onion with
lets say moving 50 from the B---> T channel to the B ---> R channel
resulting in the following situation:

  100 / 110 130 / 200
S --> B > R
  \  

Re: [Lightning-dev] Lightning and the semantic web

2019-01-28 Thread René Pickhardt via Lightning-dev
Dear Melvin,

I believe the scheme lightning: should only apply
* for payments in the form of bolt11 strings
* to identifiy nodes like lightning:node_id@ipaddr:port
* maybe to identify channels (look up the short_channel_id of the form of a
triple separated by the letterx.  BLOCKHEIGHTxTXINDEXxOUTPUTINDEX)

the orther addresses you mentioned already have a sceme e.g. tcp:

keep in mind that the ip address and port may change but the only real
identifier is the node_id which as you mentioned correctly is the pubkey
from an HD seed and it is bech32 encoded. Also the short channel id points
to a funding transaction on the base layer so implicitly to identify the
base layer transaction we do also need the SHA-256 hash of the genesis
block otherwise it is not clear that the blockheigt, txindex, output index
triple belongs specifically to the bitcoin blockchain.

with kind regards Rene


On Mon, Jan 28, 2019 at 7:13 AM Melvin Carvalho 
wrote:

>
>
> On Thu, 24 Jan 2019 at 13:42, René Pickhardt 
> wrote:
>
>> Dear Melvin,
>>
>> I believe the vocabulary is not consistent across implementations. For
>> example if you look at c lightning there is no such command `describegraph`
>> but there are the two commands `listnodes` and `listchannels` which should
>> give the same information. For both I have attached a sample output at the
>> end of the mail to demonstrate how the naming of the vocabulary differs.
>>
>> Since the data of these commands is taken from the gossip store which
>> stores the gossip messages I would suggest to take the vocabulary from the
>> BOLT 07 which defines the gossip messages. Also this mailinglist is for
>> protocol development and the spec should be the authorative source for
>> naming:
>> https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md
>>
>> There are more terms specified in other bolts which could be a basis for
>> a vocabulary. I have created an overview by hand and made a Pull Request to
>> the repository which has not been merged yet as it was the wish of the
>> developers to have such a list to be extracted automatically.
>> Still this the overview in that pull request could serve as a basis for
>> such a vocabulary :
>> https://github.com/lightningnetwork/lightning-rfc/pull/458
>>
>> Now the example outputs from c-lightning we already that there are
>> differences in naming. Take the identifier for a node for example:
>> * BOLT07: node_id
>> * LND: pub_key
>> * clightning: nodeid
>>
>> example outputs:
>>
>> lighting-cli listnodes
>>  {
>>   "nodeid":
>> "02396bf51e81f8f67eaca3652271b4fe8d3f57bedb9578af711606391c5c66760e",
>>   "alias": "PuraSloboda",
>>   "color": "68f442",
>>   "last_timestamp": 1548200218,
>>   "globalfeatures": "",
>>   "global_features": "",
>>   "addresses": [
>> {
>>   "type": "ipv4",
>>   "address": "144.136.223.22",
>>   "port": 9735
>> }
>>   ]
>> }
>>
>> lightning-cli listchannels
>> {
>>   "source":
>> "03bb88ccc444534da7b5b64b4f7b15e1eccb18e102db0e400d4b9cfe93763aa26d",
>>   "destination":
>> "0272045af48b9871013753f7cce1cf82ed80b97d669ca44709e01976a67df80adc",
>>   "short_channel_id": "559893:1912:0",
>>   "public": true,
>>   "satoshis": 47000,
>>   "message_flags": 0,
>>   "channel_flags": 1,
>>   "flags": 1,
>>   "active": true,
>>   "last_update": 1548332847,
>>   "base_fee_millisatoshi": 1000,
>>   "fee_per_millionth": 1,
>>   "delay": 144
>> }
>>
>> With kind regards Rene
>>
>
> This is extremely helpful, thank you!
>
> I will go with the RFC naming then.  I'm starting with Nodes and Edges and
> will put together a document and demo for review.  First step is to do
> Nodes.
>
> I have two questions
>
> 1. node_id -- that's basically your public key -- what types of key and
> serialization is this (my guess an ecdsa pub key derived from the HD seed),
> any pointers would be great
>
> 2. regarding the four address types :
>
>- 1: ipv4; data = [4:ipv4_addr][2:port] (length 6)
>- 2: ipv6; data = [16:ipv6_addr][2:port] (length 18)
>- 3: Tor v2 onion service; data = [10:onion_addr][2:port] (length 12)
>   - version 2 onion service addresses; Encodes an 80-bit, truncated
>   SHA-1 hash of a 1024-bit RSA public key for the onion service
>   (a.k.a. Tor hidden service).
>- 4: Tor v3 onion service; data = [35:onion_addr][2:port] (length 37)
>   - version 3 (prop224
>   
> )
>   onion service addresses; Encodes: [32:32_byte_ed25519_pubkey] ||
>   [2:checksum] || [1:version], where checksum = sha3(".onion
>   checksum" | pubkey || version)[:2].
>
>
> These can be looked up in the spec.  But in the semantic web we like,
> where possible, to have self describing data.  In particular we like URIs
> with a scheme or protocol so instead of example.com we'll have
> 

Re: [Lightning-dev] Lightning and the semantic web

2019-01-24 Thread René Pickhardt via Lightning-dev
Dear Melvin,

I believe the vocabulary is not consistent across implementations. For
example if you look at c lightning there is no such command `describegraph`
but there are the two commands `listnodes` and `listchannels` which should
give the same information. For both I have attached a sample output at the
end of the mail to demonstrate how the naming of the vocabulary differs.

Since the data of these commands is taken from the gossip store which
stores the gossip messages I would suggest to take the vocabulary from the
BOLT 07 which defines the gossip messages. Also this mailinglist is for
protocol development and the spec should be the authorative source for
naming:
https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md

There are more terms specified in other bolts which could be a basis for a
vocabulary. I have created an overview by hand and made a Pull Request to
the repository which has not been merged yet as it was the wish of the
developers to have such a list to be extracted automatically.
Still this the overview in that pull request could serve as a basis for
such a vocabulary :
https://github.com/lightningnetwork/lightning-rfc/pull/458

Now the example outputs from c-lightning we already that there are
differences in naming. Take the identifier for a node for example:
* BOLT07: node_id
* LND: pub_key
* clightning: nodeid

example outputs:

lighting-cli listnodes
 {
  "nodeid":
"02396bf51e81f8f67eaca3652271b4fe8d3f57bedb9578af711606391c5c66760e",
  "alias": "PuraSloboda",
  "color": "68f442",
  "last_timestamp": 1548200218,
  "globalfeatures": "",
  "global_features": "",
  "addresses": [
{
  "type": "ipv4",
  "address": "144.136.223.22",
  "port": 9735
}
  ]
}

lightning-cli listchannels
{
  "source":
"03bb88ccc444534da7b5b64b4f7b15e1eccb18e102db0e400d4b9cfe93763aa26d",
  "destination":
"0272045af48b9871013753f7cce1cf82ed80b97d669ca44709e01976a67df80adc",
  "short_channel_id": "559893:1912:0",
  "public": true,
  "satoshis": 47000,
  "message_flags": 0,
  "channel_flags": 1,
  "flags": 1,
  "active": true,
  "last_update": 1548332847,
  "base_fee_millisatoshi": 1000,
  "fee_per_millionth": 1,
  "delay": 144
}

With kind regards Rene


On Thu, Jan 24, 2019 at 1:21 PM Melvin Carvalho 
wrote:

>
>
> On Mon, 21 Jan 2019 at 14:11, René Pickhardt 
> wrote:
>
>> Dear Melvin,
>>
>> have you looked into the W3C Payment Group?
>> https://www.w3.org/TR/payment-request/ The entire field of semantic web
>> kind of originated from W3C and they are working on a recommendation for
>> browser vendors to enable a low level payment API.
>>
>> Also there is LightningJoule that builds on top of webln. While this is
>> not an otology it goes implicitly in a similar direction (c.f.:
>> https://github.com/wbobeirne/webln and in particular this discussion:
>> https://github.com/wbobeirne/webln/issues/1 in which Will said that in
>> his thoughts webln is different to the W3C Payment Group.)
>>
>> I am looking forward to see your progress with integrating Lightning to
>> the semantic web!
>>
>> with kind regards Rene
>>
>
> My first observation is these two data structures in lnd describe graph,
> one for channels and one for nodes.  These seem to be two fundamental
> concepts in lightning.
>
> Channel
>
> {
> "channel_id": "615605565348708353",
> "chan_point":
> "d8cfed73e0004fe1427d3045c5b20da0418f3cb803e8e35be48ee713aadbf56d:1",
> "last_update": 1548330355,
> "node1_pub":
> "024a2e265cd66066b78a788ae615acdc84b5b0dec9efac36d7ac87513015eaf6ed",
> "node2_pub":
> "03e03c56bb540c36b9e77c2aea2bb6529b907ece6c1395228c05459af13d0e2a5c",
> "capacity": "100",
> "node1_policy": {
> "time_lock_delta": 144,
> "min_htlc": "1000",
> "fee_base_msat": "1000",
> "fee_rate_milli_msat": "1",
> "disabled": false
> },
> "node2_policy": {
> "time_lock_delta": 144,
> "min_htlc": "1000",
> "fee_base_msat": "1000",
> "fee_rate_milli_msat": "1",
> "disabled": false
> }
> }
>
> Node
>
> {
> "last_update": 1547380072,
> "pub_key":
> "0200072fd301cb4a680f26d87c28b705ccd6a1d5b00f1b5efd7fe5f998f1bbb1f1",
> "alias": "OutaSpace",
> "addresses": [
> {
> "network": "tcp",
> "addr": "46.163.78.93:9760"
> },
> {
> "network": "tcp",
> "addr": "[2a01:488:66:1000:2ea3:4e5d:0:1]:9760"
> },
> {
> "network": "tcp",
> "addr": "2dkobxxunnjatyph.onion:9760"

Re: [Lightning-dev] lightning-c RPC

2019-01-22 Thread René Pickhardt via Lightning-dev
Hey Alex,

I think this is currently not being implemented. Also there is a
mailinglist particularly for issues related to c-lightning at:
https://lists.ozlabs.org/listinfo/c-lightning and of course issues like
this could also be asked in the bug tracker at:
https://github.com/ElementsProject/lightning

with kind regards Rene

On Tue, Jan 22, 2019 at 1:08 PM Alex P  wrote:

> Hello guys!
>
> Is there a way to bind RPC to IP:port, not to unix socket?
>
> Of course, it's easy to patch source code, but may be there is a param
> for config?
>
> Thanks!
>
>
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Lightning and the semantic web

2019-01-21 Thread René Pickhardt via Lightning-dev
Dear Melvin,

have you looked into the W3C Payment Group?
https://www.w3.org/TR/payment-request/ The entire field of semantic web
kind of originated from W3C and they are working on a recommendation for
browser vendors to enable a low level payment API.

Also there is LightningJoule that builds on top of webln. While this is not
an otology it goes implicitly in a similar direction (c.f.:
https://github.com/wbobeirne/webln and in particular this discussion:
https://github.com/wbobeirne/webln/issues/1 in which Will said that in his
thoughts webln is different to the W3C Payment Group.)

I am looking forward to see your progress with integrating Lightning to the
semantic web!

with kind regards Rene



On Mon, Jan 21, 2019 at 7:17 AM Melvin Carvalho 
wrote:

> Hi All
>
> I work on the solid project [1] and am very interested in the lightning
> network.
>
> In particular, I am looking at trying to create an integration between
> lightning (layer 2) and solid (layer 3?  web layer?).
>
> The first step towards integration would be to port some of the lightning
> concepts to the semantic web.  This is done by creating an ontology.
>
> Does anyone know of any existing work in this area.  Alternatively, does
> anyone have an interest to collaborate on an ontology?
>
> Best
> Melvin
>
> [1] https://solid.mit.edu/
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Colored coins or non-fungible tokens

2018-12-04 Thread René Pickhardt via Lightning-dev
Dear Joao,

there are the people from BHB Networks (in Itally) working on colored coins
for Bitcoin and Lightning. The main contributor seems to be Alekos Filini.
As far as I understand there is quite some progress. You can find more
information in their spec repo at:
https://github.com/rgb-org/spec The 4th. md file in that repo is about the
lightning network (not sure if this is still up to date with the current
implementation that Alekos is also working on.)

I believe Alekos has talked about this at the third lightning hackday in
Berlin and on the LightningHackdayNYC both talks have been recorded and can
be found on youtube. Therefor I suggest to talk to Alekos (ccd) directly.

I hope that helps.

best Rene

On Tue, Dec 4, 2018 at 2:29 PM Joao Joyce  wrote:

> Hi list,
>
> Thank you all for the great work. LN is looking amazing!
>
> I was wondering if there is any discussion about exchanging colored-coins
> or non-fungible tokens through the LN.
> Or even issuance, which I'm not seeing how it would be possible, but
> recognise that  this space is full of surprises.
>
> That would be a great addition to LN and it would enable new use-cases.
>
> Thank you all for the great work.
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Reason for having HMACs in Sphinx

2018-11-29 Thread René Pickhardt via Lightning-dev
Hey CJP,

I am still not 100% through the SPHINX paper so it would be great if at
least another pair of eyes could lookt at this. However from the original
SPHINX paper I quote:

"Besides extracting the shared key, each mix has to be provided with
authentic and confidential routing information to direct the message to the
subsequent mix, or to its final destination. We achieve this by a simple
encrypt-then-MAC mechanism. A secure stream cipher or AES in counter mode
is used for encryption, and a secure MAC (with some strong but standard
properties) is used to ensure no part of the message header containing
routing information has been modified. Some padding has to be added at each
mix stage, in order to keep the length of the message invariant at each
hop."

At first I thought this would mean that the HMAC ensures that the previous
hop cannot change the routing information. which was the first answer that
I wanted to give. However I am confused now too. The HMAC commits to the
next onion. So if the entire onion was exchanged and a new HMAC was
provided (as you suggest) the processing hop would not know this. Such a
use case would obviously lead to a routing scenario which would not succeed
and would hardly be useful (unless the previous hop plans a reverse dos
attacks from error messages or some other sabotage attacks which are
references in the SPHINX paper but not discussed explicitly).

On a second thought I reviewed chapter 2.1 of the Sphinx paper in which the
thread model for attackers is described. As far as I understand that
section one attack vector for which the HMAC shall help are man in the
middle attacks. If HMACs are being used some bitflipping by man in the
middles would be detected. However I think if a man in the middle speaks
the BOLT protocol they could exchange the entire package and provide a new
HMAC as a previous hop could do. Also the Thread model does only speak
about security of the message not so much about the reliability of the
protocol. I believe it is quite clear that if a routing node wants to
manipulate the onion they can do so. In the same way how they can decide
not to forward the onion.

--> So the mix network itself can make sure that no wrong messages are
delivered it cannot make sure that messages (which are unseen and unknown
from where they came) are intercepted.

Besides the Bitflipping usecase that I mentioned I agree with your
criticism and also don't see the necessity of the HMAC anymore. The message
is encrypted anyway and if bits are flipped the decrypted version will just
be badly formated. If the header was manipulated the next hop would not be
able to decrypt.

Best regards Rene

Am Do., 29. Nov. 2018, 16:31 hat Corné Plooy via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> geschrieben:

> Hi,
>
>
> Is there a reason why we have HMACs in Sphinx? What could go wrong if we
> didn't?
>
> A receiving node doesn't know anyway what the origin node is; I don't
> see any attack mode where an attacker wouldn't be able to generate a
> valid HMAC.
>
> A receiving node only knows which peer sent it a Sphinx packet;
> verification that this peer really sent this Sphinx packet is (I think)
> already done on a lower protocol layer.
>
>
> AFAICS, The only real use case of the HMAC value is the special case of
> a 0-valued HMAC, indicating the end of the route. But that's just silly:
> it's essentially a boolean, not any kind of cryptographic verification.
>
>
> CJP
>
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] [META] Organization of 1.1 Spec Effort

2018-11-26 Thread René Pickhardt via Lightning-dev
Hey Rusty,

No matter how we agree for the process I suggest to create a wiki page on
which we make it transparent and link to it from README.md.

The current process was new to me and I think one cannot expect newcomers
to read through the entire Mailinglist.

As soon as we have an agreement I can create this PR together with more
useful information for newcomers.

Best regards Rene

Am Di., 27. Nov. 2018, 01:13 hat Matt Corallo 
geschrieben:

> +100 for IRC meetings, though, really, I'd much much stronger prefer
> substantive discussion happen on GitHub or the mailing list. Doing
> finalization in a live meeting is really unfair to those who can't find the
> time to attend regularly (or happen to miss the one where that thing was
> discussed that they care about).
>
> > On Nov 26, 2018, at 18:29, Rusty Russell  wrote:
> >
> > Hi all,
> >
> >As you may know, for 1.0 spec we had a biweekly Google Hangout,
> > at 5:30am Adelaide time (Monday 19:00 UTC, or 20:00 UTC Q3/4).  You can
> > see the minutes of all meetings here:
> >
> >
> https://docs.google.com/document/d/1oU4wxzGsYd0T084rTXJbedb7Gvdtj4ax638nMkYUmco
> >
> > The current process rules are:
> >
> > 1. Any substantive spec change requires unanimous approval at the
> >   meeting before application.
> > 2. Any implementation changes generally require two interoperable
> >   implementations before they are considered final.
> > 3. "typo, formatting and spelling" fixes which can be applied after two
> >   acks without a meeting necessary.
> >
> > It's time to revisit this as we approach 1.1:
> >
> > 1. Should we move to an IRC meeting?  Bitcoin development does this.
> >   It's more inclusive, and better recorded.  But it can be
> >   lower-bandwidth.
> >
> > 2. Should we have a more formal approval method for PRs, eg. a
> >   "CONSENSUS:YES" tag we apply once we have acks from two teams and no
> >   Naks, then a meeting to review consensus, followed by "FINAL" tag and
> >   commit the next meeting?  That gives you at least two weeks to
> >   comment on the final draft.
> >
> > Side note: I've added milestones to PRs as 1.0/1.1; I'm hoping to clear
> > all 1.0 PRs this week for tagging in the next meeting, then we can start
> > on 1.1 commits.
> >
> > Thanks!
> > Rusty.
> > ___
> > Lightning-dev mailing list
> > Lightning-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Penalty tx and RBF

2018-11-23 Thread René Pickhardt via Lightning-dev
Hey Cezary,

sorry I misread your initial question. I thought you where referring to the
(probably bigger problem) of getting the commitment transaction to be mined
because RBF does not work. But if we assume that your channel partner
published an outdated commitment transaction which got mined then you can
claim (both) outputs (your node should do this automatically) with this
penalty transaction. This penalty transaction is spending the outputs of
the commitment transaction and is signed with your nodes private key.
Therefor as far as I know you should be able to RBF this penalty
transaction. Also I believe you understand the process correctly.

Actually since the timelock on the commitment transaction will at some
point in time be over (in which case also your channel partner can spend
their output) you have an economic incentive to quickly get the penalty
transaction minded by using rather high fees or in case at this time really
a lot of transactions come in to RBF. I currently see no reason why you
could not RBF the penalty transaction. In case I oversee something I am
sure someone here on the list will correct me.

best regards Rene

On Fri, Nov 23, 2018 at 8:34 PM Cezary Dziemian 
wrote:

> Thanks for answer,
>
> My knowledge is mostly based on this article:
>
>
> https://bitcoinmagazine.com/articles/understanding-the-lightning-network-part-building-a-bidirectional-payment-channel-1464710791/
>
> Graph at the end shows that in order to claim former channel partner funds
> I need to provide child transaction that contains my signature and secret.
> This secret is evidence.that partner didn't commit the last transaction.
>
> So the penalty transaction uses comitment transaction output as its input
> and penalty transaction can be sign by one side only. Am I right, or I just
> don't understand how it works? Or maybe this graph do not represents
> correctly how commitment and penalty transactions are already developed?
>
> Best Regards,
> Cezary Dziemian
>
>
> pt., 23 lis 2018 o 19:07 René Pickhardt 
> napisał(a):
>
>> Dear Cezary,
>>
>> as far as I understand the problem in the case of a unilateral (force)
>> close are:
>>
>> 1.) In order to RBF your commitment transaction you would have to have
>> the signature of your former channel partner. since you initiated a force
>> close it is unlikely that you get this signature to RBF because then you
>> could have done a mutual close right away which is cheaper since less tx
>> are invovled to claim all funds back.
>> 2.) In order to CPFP you have to be able to spend your output which can't
>> work because there is a timelock on it.
>>
>> I believe on the last lightning developer summit this issue was discussed
>> and it was agreed that for BOLT1.1 we want have a third output in the
>> commitment transactions which anyone can spend (OP_TRUE) and which is just
>> above the dust level. This output is supposed to have no timelock so that
>> anyone can CPFP it. In the general case miners of the block could collect
>> the output as a fee. You can find a pointer to this on this wikipage in the
>> lightning-rfc git repo:
>> https://github.com/lightningnetwork/lightning-rfc/wiki/Lightning-Specification-1.1-Proposal-States
>> (look in the section tx and fees)
>>
>> best Rene
>>
>> On Fri, Nov 23, 2018 at 6:30 PM Cezary Dziemian <
>> cezary.dziem...@gmail.com> wrote:
>>
>>> Hello all,
>>>
>>> Sorry for my ignorance. I have two questions related with penalty txs. I
>>> assume, that when someone commits obsolete commitment tx, my node
>>> automatically commit penalty transaction.
>>>
>>> What if fees suddenly increases? Can my node use RBF to increase fee?
>>>
>>> Is there any approach common to major 3 implementations?
>>>
>>> How much time (how many blocks) do my node have to commit penalty tx? Is
>>> there some value common for implementations?
>>>
>>> Best regards,
>>> Cezary Dziemian
>>> ___
>>> Lightning-dev mailing list
>>> Lightning-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>>
>>
>>
>> --
>> https://www.rene-pickhardt.de
>>
>> Skype: rene.pickhardt
>>
>> mobile: +49 (0)176 5762 3618
>>
>

-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Base AMP

2018-11-20 Thread René Pickhardt via Lightning-dev
Hey List,

as this base AMP proposal seems pretty small I just started to write this
up to make a PR for BOLT04 and BOLT11. While doing my write up I realize
that there are smaller things that I would want to verify / double check
and propose with you.

## Verifying:
1.) I understand the receiving node signals support for Base AMP by setting
a feature bit in the BOLT11 String
2.) The sending node signals a multipath payment by setting a feature bit
and by using the same `amount to forward` value in the last hop of the
onion for all paths which will also be bigger that the incoming htlcs whose
sum has to be at least the size of `amount_to_forward`.

## Clarifying:
3.) Senders MUST NOT (SHOULD NOT?) create paths which would have to be
merged by intermediary nodes (as we don't know - and have no means of
querying - if they support the format of the adepted onion packages for
partial paths. Also it even seems impossible since the rest of the path for
at least one partial path could not be stored in the onion / forwarded
onions can't be seen)

## Proposing:
Should we specify an algorithm for executing a multipath payment for the
sending node or should this be left to the implementation. An obvious Idea
for an algorithm would be a divide and conquer scheme which should be
obvious with the following python style pseudo code:

def pay_base_amp(amount):
   success = False
   for route in get_available_routes():
   success = send_via_route(route, amount)
if not success:
   pay_base_amp(amount/2 + 1) # the +1 is to mitigate rounding errors.
there could be other ways to do so.
   pay_base_amp(amount/2 + 1)

Even if we leave the exact AMP execution to the sender we could still
suggest this divide and conquer scheme in BOLT 04

Another idea I had (which is probably a bad one as it allows for probing of
channel balances) would be to allow nodes on a partial path to send back
some hints of how much additional capacity they can forward if they see
that the partial payment feature bit is set (this would require to set this
feature bit in every onion) Also if we want to make use of this information
every node would have to support base amp. So I guess this idea is bad for
several reasons. Still we could have a MAY rule out of it?

best Rene


On Fri, Nov 16, 2018 at 4:45 PM Anthony Towns  wrote:

> On Thu, Nov 15, 2018 at 11:54:22PM +, ZmnSCPxj via Lightning-dev wrote:
> > The improvement is in a reduction in `fee_base_msat` in the C->D path.
>
> I think reliability (and simplicity!) are the biggest things to improve
> in lightning atm. Having the flag just be incuded in invoices and not
> need to be gossiped seems simpler to me; and I think endpoint-only
> merging is better for reliability too. Eg, if you find candidate routes:
>
>   A -> B -> M -- actual directed capacity $6
>   A -> C -> M -- actual directed capacity $5.50
>   M -> E -> F -- actual directed capacity $6
>   A -> X -> F -- actual directed capacity $7
>
> and want to send $9 form A to F, you might start by trying to send
> $5 via B and $4 via C.
>
> With endpoint-only merging you'd do:
>
>$5 via A,B,M,E,F -- partial success
>$4 via A,C,M,E -- failure
>$4 via A,X,F -- payment completion
>
> whereas with in-route merging, you'd do:
>
>$5 via A,B,M -- held
>$4 via A,C,M -- to be continued
>$9 via M,E -- both partial payments fail
>
> which seems a fair bit harder to incrementally recover from.
>
> > Granted, current `fee_base_msat` across the network is very low
> currently.
> > So I do not object to restricting merge points to ultimate payees.
> > If fees rise later, we can revisit this.
>
> So, while we already agree on the approach to take, I think the above
> provides an additional rationale :)
>
> Cheers,
> aj
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Strawman BOLT11 static "offer" format using probes.

2018-11-16 Thread René Pickhardt via Lightning-dev
Dear Rusty,

I am not getting this proposal (maybe I am lacking some technical basic
understandings) however I decided to ask more questions in order to
complete my onboarding process faster and hope this is fine.

My problem starts with the fact that I can't find the term "lightning probe
message" in the current BOLTs  (actually the term probe only occures two
times and these seem unrelated to what you are talking about) so I am
confused what this is.
As far as I understand your proposal from a high level the payer is
supposed to create an onion package which triggers the offering of HTLCs
with some additional metadata so that the receipient of the final onion can
answer with a BOLT11 invoice. What I don't get is the fact that a payment
hash needs to be known in order to offer HTLCs.
Though I imagine you ment it differently I would not see a problem with the
payer to know the preimage in advance as he is creating the entire onion on
his behalf and sponanious without invoice anyway. However I don't get why a
returned BOLT11 invoice is needed then. I assume that my previouse
statement is wrong anyway since you don't mention anywhere how the preimage
would be send from the payer to the payee.

In general I was wondering (already during the summit) why we don't include
a connection oriented communication layer on top of the current protocol
which would allow payer and payee to communicate more efficiently about
payment and routing process and to negotiate stuff like spontaneos
payments. I see two reasons against this: 1.) more synchronous
communication makes stuff more complicated to implement and 2.) privacy
concerns.
Am I missing something here? (and sorry for splitting the topic but I
didn't want to start a new one when it actually seems to fit to this
proposal.

best Rene

On Thu, Nov 15, 2018 at 4:57 AM Rusty Russell  wrote:

> Hi all,
>
> I want to propose a method of having reusable BOLT11 "offers" which
> provide almost-spontaneous payments as well as not requiring generating
> a BOLT11 invoice for each potential sale.
>
> An "offer" has a `p` field of 26 bytes (128 bits assuming top two are 0)
> (which is ignored by existing nodes).  The payer uses a new lightning
> probe message using the current onion format we use for HTLCs to
> retreive the complete invoice.
>
> The format of the final-hop lightning onion would contain:
>
> [whatever-marker-we-need?][128-bit-`p`-field][[type,len,data]+]
>
> We would probably define a few optional types to start:
>
> 1. quantity: for ordering multiple of an item, default 1.
> 2. delivery-address: steal from
> https://www.w3.org/TR/vcard-rdf/#Delivery_Addressing_Properties ?
> 3. signature: basically a blob so payer can prove it was them.
>
> The return lightning message would contain a new bolt11 invoice (perhaps
> we optimize some fields by copying from the bolt11 offer if they don't
> appear?), and an additional field:
>
> `m` (27) `data_length` 52.  Merkle hash of fields payer provided
> in onion msg above, and the offer `p` value.
>
> The payer checks the signature is correct, `m` is correct, and uses the
> invoice to pay as normal.  The bolt11 offer + fields-from-onion + bolt11
> invoice + preimage is the complete proof of payment.
>
> Refinements
> ---
>
> We can generate alternate leaves for the merkle tree (using
> SHA256(shared-secret | leafnum)) so revealing the `m` value doesn't risk
> revealing your delivery-address for example.
>
> The return needs to list the fields it *didn't* include in the merkle
> because it didn't accept them (the merchant doesn't want to be bound to
> conditions it doesn't understand!).
>
> We could add a `k` field to the bolt11 offer to allow the final invoice
> to delegated to a separate key.
>
> The default `x` (expiry) field for an offer which does not have an
> old-style 53-byte `p` field (ie. a "pure" offer) could be infinite.
>
> We could merkelize the delivery-address too :)
>
> I've handwaved a bit over the detailed format, because there are other
> things we want to put in the onion padding, and because the return is
> similar to the "soft-error"/"partial payment ack" proposals.
>
> Results
> ---
>
> This gives us static invoicing, and a single static invoice (without an
> amount field) can thus be used to approximate "spontaneous" donations,
> while still providing proof of payment; indeed, providing
> non-transferrable proof-of-payment since the invoice now commits to the
> payer-provided signature.
>
> It also provides a platform for recurring payments: while we can do this
> with preimage-is-next-payment_hash, that requires pre-generation and
> isn't compatible with static invoices.
>
> I apologize that this wasn't fleshed out before the summit, but I
> overestimated the power of Scriptless Scripts so had mentally deferred
> this.
>
> Thanks!
> Rusty.
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> 

[Lightning-dev] Proposal to include some form of best effort routing, fragmentation and local AMP

2018-11-16 Thread René Pickhardt via Lightning-dev
Good morning list,

in Adelaide I had a long conversation with another participant who
complained that slow payments and failing payments are still a major UX
issue for people that try to use the lightning network. While I believe
this is a very valid point and we might want to think heavily about
altering some design decisions after BOLT1.1 in order to mitigate this I
want to make another proposal which could still be an improvement to some
of the problems that we currently have with path finding. This proposal is
basically a standalone thread to my suggestions sketched in Connors PR at
https://github.com/lightningnetwork/lightning-rfc/pull/503 for non strict
forwarding.

I propose to implement a second routing algorithm that works on the
principle of best effort routing / forwarding with the help of local
payment fragmentation or maybe better called local AMP. I understand this
sounds drastic to start with, in particular since it seems that the
destination has to be known but I believe there  are ways to still keep up
with privacy.

The core idea is to allow intermediate nodes to fragment an HTLC to
something similar as Base AMP to reach the next hop that was specified in
the onion. This would still allow to forward a payment and allow the next
hop to to continue with the regular onion package.

The idea is if Alice is supposed to forward an HTLC to Bob with a value
smaller than their channel capacity but alice has not enough funds on her
side alice could try to fragment the payment and try to find several paths
(or maybe just one path without splitting) to Bob.

One particular strategy to find such a path would be to share friend of a
friend (FOAF) information.
Alice could look at the nodes that both she and Bob are connected to and
use them as bridge nodes for the payment. In particular she could even ask
Bob how much inbound capacity he has from those nodes. In case Bob would
share this information about the channel balance of mutual friends it could
deterministically be decided if the original HTLC could be forwarded from
Alice to Bob in a fragmented way.

With the autopilot we are trying to create many triangles in the network so
that there is always the chance for friend of a friend nodes which could be
used with this approach.

On the downside the original payer would have to allow a package to be
locally fragmented by including more fees at each hop and also by
increasing the CLTV deltas in each hop (so that an additional hop can be
included and financed).

With the suggestion I made the payer can still select the basic route and
the full route would still be private. The sender however could chose paths
on which a lot of common friends exist for each pair of nodes on the path
(thereby increasing the probability that the local fragmentation of the
payment has a higher likelihood to be successful)

Of course another solution is if we think that local AMP is too complex and
expensive we could still have the two nodes that fail to forward the htlcs
work collaboratively to find a path between them and return this
information about such a (multi) path as a routing suggestion in the error
message so that the adapted onion package could be tried and sent by the
payer.

best regards Rene

-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Splicing Proposal: Feedback please!

2018-10-10 Thread René Pickhardt via Lightning-dev
Dear Rusty,

thanks for the initiative. You suggested in your paragraph "messages
changes during splicing" during splicing to duplicate each commitment
transaction. One which spends the old funding tx and one which spends the
spliced tx. I believe this can be simplified. Though I think my workflow
pretty much resembles what you have written in "Splice Signing" from point
1. to 6. Maybe I might have misunderstood some parts of your suggestion.

I will not write this down as formal as your proposal as I believe we are
currently in the feedback and discussion phase. Maybe you already had
"those details" that I am suggesting in mind. In that case sorry for my
mail.

So let us take the example of Splicing in:
* The situation before splicing is that we have one output in our funding
tx that is being spent with each commitment tx. (actually if the channel
was spliced before we have more inputs but that should not change anything)
* Splice in would create one additional output that can be spent in future
commitment tx.
* I propose while splicing in this output should be spent by a special
commitment tx which goes to the funder of the splicing operation. This
should happen before the actual funding takes place. The other commitment
tx spending the original output continues to operate (assuring non blocking
splice in operation).
* Once we have enough confirmations we merge the channels (either
automatically or with the next channel update). A new commitment tx is
being created which now spends each output of each of the two funding tx
and assigns the channel balance to the channel partners accordingly to the
two independent channels. The old commitment txs are being invalidated.
* The disadvantage is that while splicing is not completed and if the
funder of the splicing tx is trying to publish an old commitment tx the
node will only be punished by sending all the funds of the first funding tx
to the partner as the special commitment tx of the 2nd output has no newer
state yet.

I believe splicing out is even safer:
* One just creates a spent of the funding tx which has two outputs. One
output goes to the recipient of the splice out operation and the second
output acts as a new funding transaction for the newly spliced channel.
Once signatures for the new commitment transaction are exchanged (basically
following the protocol to open a channel) the splicing operation can be
broadcasted.
* The old channel MUST NOT be used anymore but the new channel can be
operational right away without blockchain confirmation. In case someone
tries to publish an old state of the old channel it will be a double spent
of the splicing operation and in the worst case will be punished and the
splicing was not successful. if one publishes an old state of the new
channel everything will just work as normal even if the funding tx is not
yet mined. It could only be replaced with an old state of the previous
channel (which as we saw is not a larger risk than the usual operation of a
lightning node)

As mentioned maybe you had this workflow already in your mind but I don't
see why we need to send around all the messages twice with my workflow. We
only need to maintain double state but only until it is fair / safe to do
so. I would also believe that with my approach it should be possible (but
not really necessary) to have multiple splicing operations in parallel.

One other question: What happens to the short_channel_id of a channel to
which founds have been spliced in?

best Rene

On Wed, Oct 10, 2018 at 5:46 AM Rusty Russell  wrote:

> Hi all!
>
> We've had increasing numbers of c-lightning users get upset they
> can't open multiple channels, so I guess we're most motivated to allow
> splicing of existing channels.  Hence this rough proposal.
>
> For simplicity, I've chosen to only allow a single splice at a time.
> It's still complex :(
>
> Feedback welcome!
> --
> Splice Negotiation:
>
> 1. type: 40 (`splice_add_input`) (`option_splice`)
> 2. data:
>* [`32`:`channel_id`]
>* [`8`: `satoshis`]
>* [`32`: `prevtxid`]
>* [`4`: `prevtxoutnum`]
>* [`2`: `scriptlen`]
>* [`scriptlen`: `scriptpubkey`]
>
> 1. type: 41 (`splice_add_output`) (`option_splice`)
> 2. data:
>* [`32`:`channel_id`]
>* [`8`: `satoshis`]
>* [`2`: `scriptlen`]
>* [`scriptlen`: `outscript`]
>
> 1. type: 42 (`splice_all_added`) (`option_splice`)
> 2. data:
>* [`32`:`channel_id`]
>* [`4`:`feerate_per_kw`]
>* [`4`:`minimum_depth`]
>
> Each side sends 0 or more `splice_add_input` and 0 or more
> `splice_add_output` followed by `spice_all_added` to complete the splice
> proposal.  This is done either to initiate a splice, or to respond to a
> `splice_*` from the other party.
>
> `splice_add_input` is checked for the following:
> - must not be during a current splice
> - scriptpubkey is empty, or of form 'HASH160 <20-byte-script-hash> EQUAL'
> - `satoshis` doesn't wrap on addition.
> - MAY check that it matches outpoint 

Re: [Lightning-dev] Measuring centrality of nodes in LN graph

2018-08-27 Thread René Pickhardt via Lightning-dev
Hey Kulpreet,

thanks for this nice overview article! I have just today implemented a
first draft for the c-lightning autopilot [0]. I have implemented 4
heuristics to select nodes to which one could connect. On of those [1]
samples from the nodes that contribute to the high diameter. This heuristic
was included not to increase the utility of the node that is running the
autopilot but to improve the network properties. I believe that this
heuristic should also reduce the articulation points and biconnected
components that you mention in your article. As endpoints of longest
shortest paths will most likely be in two different biconnectivity
components (at least if those exist and have a certain size).

Regarding the centrality. I also calculated the betweeness centrality and
have similar results  [2] to yours. I guess the difference will be due to
the fact that we don't work on the exact same snapshot. My autopilot
implementation also connects to a few rather central nodes. I doubt this is
useful for the network but I guess it is good for the node running the
autopilot since it gains access to many nodes. ( Actually I think - but
don't know - that in combination with [1] it even helps the network).

Regarding your 200 Articulation points I would guess that many of those are
just nodes that only have one channel with the node that acts as an
articulation point. I guess this is not something that we would need to
take care of so much since it is also in the responsibility of those nodes
to have more than one channel. for larger biconnectivity components the
problem would probably be resolved with the above mentioned heuristic.
Therefor I believe looking at the articulation points should not be our
main focus.

Something that (regarding the autopilot) I am currently missing in your
article is how much funds should be allocated for the suggested channels. I
am currently experimenting with a probability density function that is
proportional to the average capacity of each node in the candidate set. I
smooth this with a uniform distribution. However simulations at this point
are quite expensive (if done primitively since the centralities have to be
recomputed) I guess this would be a nice future work. I will probably
tomorrow publish the rest of the code for the lib-autopilot that uses this
heuristic for channel balances since I am currently still working on it.

If you consider working more on the autopilot but also on research related
to this I would also suggest the following resources [3],[4] and [5]

[0] https://github.com/ElementsProject/lightning/pull/1888
[1]
https://github.com/renepickhardt/lightning/blob/8c91f57490b51f772513a274d679d3ab62e7201a/contrib/lib-autopilot.py#L205
[2] https://twitter.com/renepickhardt/status/1034066602273193985
[3] https://github.com/lightningnetwork/lnd/issues/677
[4]
https://github.com/renepickhardt/Automatically-Generating-a-Robust-Topology-for-the-Lightning-Network-on-top-of-Bitcoin
[5]
https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/

best regards Rene


On Mon, Aug 27, 2018 at 11:59 PM Kulpreet Singh  wrote:

> Hi all,
>
> I have been thinking about how we could measure the centrality of
> various nodes in the LN graph and the dependence on some nodes to
> route payments and to prevent network partitions. I think measuring
> and tracking the changes in key metrics could help the community
> decide on which nodes to open new channels with.
>
> I measured the centrality of nodes and the central point dominance as
> defined in the seminal paper by Lindon C. Freeman, "A Set of Measures
> of Centrality Based on Betweenness", Sociometry 40, pp. 35-41, 1977.
>
> I also measured the number of articulation points in the network as
> per Robert E. Tarjan, "Depth first search and linear graph algorithms"
> SIAM Journal on Computing, 1(2):146-160, 1972.
>
> I want to add, that this is just a start, I understand that we should
> probably look at treating LN as a directed graph and that we should do
> some work in trying to do some analysis based on treating LN as a flow
> network.
>
> However, I am eager to share my early results and would welcome any
> feedback or suggestions on the way forward.
>
> I wrote a medium post describing the approach and show my results
> there. I also elaborate on the choice of the two metrics and what they
> mean for LN. The post is available here:
>
> https://medium.com/@jungly/measuring-node-centrality-in-lightning-network-8102a5f0
>
> Looking forward to your suggestions and feedback.
>
> Thanks
> Kulpreet
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev 

[Lightning-dev] W3C Web Payments Working Group / Payment Request API

2018-08-23 Thread René Pickhardt via Lightning-dev
Hey lightning devs,

I was wondering if any of the companies here are members of W3C  and if
anyone here could be member of the W3C Web Payments Working Group (c.f.:
https://www.w3.org/Payments/WG/ )? According to this mail
https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-March.txt
Christian Decker is a member. Which I think would be awesome!

They have just released their candidate recommendation for a payment API
at: https://www.w3.org/TR/payment-request/ According to their site the
proposed recommendation will be published not earlier than October 31st
2018. They are currently looking for feedback in their github repository
at: https://github.com/w3c/payment-request/

I can see that they have bitcoin somewhat on their mind. But I guess it
would be even cooler if we could make sure that lightning payments will
also be compatible with their recommendation.

Christian - if you really are a member -  could you give us an update on
that work? How relevant is it for us?

best Rene

-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] proposal for Lightning Network improvement proposals

2018-07-22 Thread René Pickhardt via Lightning-dev
Sorry did not realized that BOLTs are the equivalent - and aparently many
people I spoke to also didn't realize that.

I thought BOLT is the protocol specification and the bolts are just the
sections. And the BOLT should be updated to a new version.

Also I suggested that this should take place for example within the
lightning rfc repo. So my suggestion was not about creating another place
but more about making the process more transparent or kind of filling the
gap that I felt was there.

I am sorry for spaming mailboxes with my suggestion just because I didn't
understand the current process.


Olaoluwa Osuntokun  schrieb am So., 22. Juli 2018 20:59:

> We already have the equiv of improvement proposals: BOLTs. Historically
> new standardization documents are proposed initially as issues or PR's when
> ultimately accepted. Why do we need another repo?
>
> On Sun, Jul 22, 2018, 6:45 AM René Pickhardt via Lightning-dev <
> lightning-dev@lists.linuxfoundation.org> wrote:
>
>> Hey everyone,
>>
>> in the grand tradition of BIPs I propose that we also start to have our
>> own LIPs (Lightning Network Improvement proposals)
>>
>> I think they should be placed on the github.com/lightning account in a
>> repo called lips (or within the lightning rfc repo) until that will happen
>> I created a draft for LIP-0001 (which is describing the process and is 95%
>> influenced by BIP-0002) in my github repo:
>>
>> https://github.com/renepickhardt/lips  (There are some open Todos and
>> Questions in this LIP)
>>
>> The background for this Idea: I just came home from the bitcoin munich
>> meetup where I held a talk examining BOLT. As I was asked to also talk
>> about the future plans of the developers for BOLT 1.1 I realized while
>> preparing the talk that many ideas are distributed within the community but
>> it seems we don't have a central place where we collect future enhancements
>> for BOLT1.1. Having this in mind I think also for the meeting in Australia
>> it would be nice if already a list of LIPs would be in place so that the
>> discussion can be more focused.
>> potential LIPs could include:
>> * Watchtowers
>> * Autopilot
>> * AMP
>> * Splicing
>> * Routing Protcols
>> * Broadcasting past Routing statistics
>> * eltoo
>> * ...
>>
>> As said before I would volunteer to work on a LIP for Splicing (actually
>> I already started)
>>
>> best Rene
>>
>>
>> --
>> https://www.rene-pickhardt.de
>>
>> Skype: rene.pickhardt
>>
>> mobile: +49 (0)176 5762 3618
>> ___
>> Lightning-dev mailing list
>> Lightning-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>
Am 22.07.2018 20:59 schrieb "Olaoluwa Osuntokun" :

We already have the equiv of improvement proposals: BOLTs. Historically new
standardization documents are proposed initially as issues or PR's when
ultimately accepted. Why do we need another repo?

On Sun, Jul 22, 2018, 6:45 AM René Pickhardt via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Hey everyone,
>
> in the grand tradition of BIPs I propose that we also start to have our
> own LIPs (Lightning Network Improvement proposals)
>
> I think they should be placed on the github.com/lightning account in a
> repo called lips (or within the lightning rfc repo) until that will happen
> I created a draft for LIP-0001 (which is describing the process and is 95%
> influenced by BIP-0002) in my github repo:
>
> https://github.com/renepickhardt/lips  (There are some open Todos and
> Questions in this LIP)
>
> The background for this Idea: I just came home from the bitcoin munich
> meetup where I held a talk examining BOLT. As I was asked to also talk
> about the future plans of the developers for BOLT 1.1 I realized while
> preparing the talk that many ideas are distributed within the community but
> it seems we don't have a central place where we collect future enhancements
> for BOLT1.1. Having this in mind I think also for the meeting in Australia
> it would be nice if already a list of LIPs would be in place so that the
> discussion can be more focused.
> potential LIPs could include:
> * Watchtowers
> * Autopilot
> * AMP
> * Splicing
> * Routing Protcols
> * Broadcasting past Routing statistics
> * eltoo
> * ...
>
> As said before I would volunteer to work on a LIP for Splicing (actually I
> already started)
>
> best Rene
>
>
> --
> https://www.rene-pickhardt.de
>
> Skype: rene.pickhardt
>
> mobile: +49 (0)176 5762 3618
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] proposal for Lightning Network improvement proposals

2018-07-22 Thread René Pickhardt via Lightning-dev
Hey everyone,

in the grand tradition of BIPs I propose that we also start to have our own
LIPs (Lightning Network Improvement proposals)

I think they should be placed on the github.com/lightning account in a repo
called lips (or within the lightning rfc repo) until that will happen I
created a draft for LIP-0001 (which is describing the process and is 95%
influenced by BIP-0002) in my github repo:

https://github.com/renepickhardt/lips  (There are some open Todos and
Questions in this LIP)

The background for this Idea: I just came home from the bitcoin munich
meetup where I held a talk examining BOLT. As I was asked to also talk
about the future plans of the developers for BOLT 1.1 I realized while
preparing the talk that many ideas are distributed within the community but
it seems we don't have a central place where we collect future enhancements
for BOLT1.1. Having this in mind I think also for the meeting in Australia
it would be nice if already a list of LIPs would be in place so that the
discussion can be more focused.
potential LIPs could include:
* Watchtowers
* Autopilot
* AMP
* Splicing
* Routing Protcols
* Broadcasting past Routing statistics
* eltoo
* ...

As said before I would volunteer to work on a LIP for Splicing (actually I
already started)

best Rene


-- 
https://www.rene-pickhardt.de

Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Including a Protocol for splicing to BOLT

2018-06-25 Thread René Pickhardt via Lightning-dev
Hey everyone,

I found a mail from 6 month ago on this list ( c.f.:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2017-December/000865.html
)
in which it was stated that there was a plan to include a splicing protocol
as BOLT 1.1 (On a side node I wonder weather it would make more sense to
include splicing to BOLT 3?) I checked out the git repo and issues and
don't see that anyone is currently working on that topic and that it hasn't
been included yet. Am I correct?
If noone works on this at the moment and the spec is still needed I might
take the initiative on that one over the next weeks. If someone is working
on this I would kindly offer my support.

The background for my question: Last weekend I have been attending the 2nd
lightninghackday in Berlin and we had quite some intensive discussions
about the autopilot feature and splicing. (c.f. a summary can be found on
my blog:
https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin
)

They people from lightning labs told me that they are currently started
working on splicing but even though it seems technically straight forward
the protocols should also be formalized. Previously I planned working on
improving the intelligence of the autopilot feature of the lightning
network however on the weekend I got convinced that splicing should be much
higher priority and the process should be specified in the lightning rfc.

Also it would be nice if someone would be willing to help out improving the
quality of the spec that I would create since it will be my first time
adding work to such a formal rfc.

best Rene


-- 
www.rene-pickhardt.de


Skype: rene.pickhardt

mobile: +49 (0)176 5762 3618
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


[Lightning-dev] Fwd: Opening channels with neighbors for cost/connectivity benefit

2018-03-28 Thread René Pickhardt via Lightning-dev
Sorry I sent this mail by accident only to Karan.

-- Forwarded message -
From: René Pickhardt 
Date: Di., 27. März 2018 11:10
Subject: Re: [Lightning-dev] Opening channels with neighbors for
cost/connectivity benefit
To: Karan Verma 


Dear karan,

There is a feature called autopilot in the lnd implementation that tries to
achieve something similar to what you describe.

However the problem is much harder than just using some plausible
heuristic. I have an open issue on github discussing these problems:
https://github.com/lightningnetwork/lnd/issues/677

>From there I also linked a draft of a whitepaper that I am working on in
which I plan to discuss ways of automatically create a well connected
network topology fitting the specific needs of the peers in the lightning
network.

Your help and ideas would be appreciated. Also you could just implement
your idea in the lnd autopilot interface

Best regards Rene Pickhardt

Karan Verma  schrieb am Di., 27. März 2018
05:58:

> Hello,
>
> The sender node doesn’t always have a route to the receiving node
> accepting lightning payments and since opening new channels is costly - I
> was wondering if there was a smarter way to open channels such that it
> increases the connectedness of the sender node with other nodes in the
> network and also possibly save money in the intended transaction.
>
> To clarify, if Bob wants to send money to Alice but doesn’t have a route
> to her. He would need to open a new channel with Alice and send the money.
> This is costly for Bob if that was the only transaction he ever wanted to
> do with Alice. However, if Alice was connected to Charlie and Dave
> (Unidirectional: Charlie -> Alice & Dave -> Alice due to the amount being
> sent). He could instead connect with Charlie/Dave or nodes connected with
> them which have a route to Alice through Charlie/Dave such that it
> minimizes the transaction cost to reaching Alice (some routes might have
> negative fee) and maximizes the number of nodes Bob can now reach through
> this channel. Lets say if Bob chose Charlie's neighbor, then he can now
> reach at-least three nodes - Charlie's neighbor, Charlie and Alice and end
> up paying less.
>
> Essentially we're sorting choice of the nodes to open a channel with by
> transaction fee and connectedness it brings to the origin node. This would
> benefit Bob in the long term and also maybe lightning network as a whole.
> I'm new to lightning and would appreciate feedback on this idea. Thanks.
>
> -Karan
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] New form of 51% attack via lightning's revocation system possible?

2018-03-13 Thread René Pickhardt via Lightning-dev
nt on there not being a 51%
> attacker, then things are pretty much broken anyway :-)
>
> Cheers,
> Christian
>
> René Pickhardt via Lightning-dev
> <lightning-dev@lists.linuxfoundation.org> writes:
> > Hey everyone,
> >
> > disclaimer: as mentioned in my other mail (
> > https://lists.linuxfoundation.org/pipermail/lightning-dev/
> 2018-March/001065.html
> > ) I am currently studying the revocation system of duplex micropayment
> > channels in detail but I am also pretty new to the topic. So I hope the
> > attack I am about to describe is not possible and it is just me
> overseeing
> > some detail or rather my lack of understanding.
> > That being said even after waiting one week upon discovery and double
> > checking the assumptions I made I am still positive that the revocation
> > system in its current form allows for a new form of a 51% attack. This
> > attack seems to be way more harmful than a successful 51% attack on the
> > bitcoin network. Afaik within the bitcoin network I could 'only double
> > spend' my own funds with a successful 51% attack. In the lightning case
> it
> > seems that an attacker could steal an arbitrary amount of funds as long
> as
> > the attacker has enough payment channels with enough balance open.
> >
> > The attack itself follows exactly the philosophy of lightning: "If a tree
> > falls in the forest and no one is around to hear it. Does it make a
> sound?"
> > In the context of the attack this would translate to: "If a 51% attacker
> > secretly mines enough blocks after fraudulently spending old commitment
> > transactions and no one sees it during the the *to_self_delay*  period,
> > have the commitment transactions been spent? (How) Can they be revoked?"
> >
> >
> > As for the technical details I quote from the spec of BOLT 3:
> > "*To allow an opportunity for penalty transactions, in case of a revoked
> > commitment transaction, all outputs that return funds to the owner of the
> > commitment transaction (a.k.a. the "local node") must be delayed for *
> > *to_self_delay** blocks. This delay is done in a second-stage HTLC
> > transaction (HTLC-success for HTLCs accepted by the local node,
> > HTLC-timeout for HTLCs offered by the local node)*"
> >
> > Assume an attacker has 51% of the hash power she could open several
> > lightning channels and in particular accept any incoming payment channel
> > (the more balance is in her channels the more lucrative the 51% attack).
> > Since the attacker already has a lot of hash power it is reasonable (but
> > not necessary) to assume that the attacker already has a lot of bitcoins
> > and is well known to honest nodes in the network which makes it even more
> > likely to have many open channels.
> >
> > The attacker keeps track of her (revocable) commitment transactions in
> > which the balance is mostly on the attackers side. Once the attacker
> knows
> > enough of these (old) commitment transactions the attack is being
> executed
> > in the following way:
> > 0.) The max value of to_self_delay is evaluated. Let us assume it is 72
> > blocks (or half a day).
> > 1.) The attacker secretly starts mining on her own but does not
> broadcasts
> > any successfully mined block. Since the attacker has 51% of the hash
> power
> > she will most likely be faster than the network to mine the 72 blocks of
> > the safety period in which fraudulent commitment transactions could be
> > revoked.
> > 2.) The attacker spends all the fraudulent (old) commitment transactions
> in
> > the first block of her secrete mining endeavor.
> > 3.) Meanwhile the attacker starts spending her own funds of her payment
> > channels e.g on decentralized exchanges for any other (crypto)currency.
> > 4.) As soon as the attacker has mined enough blocks that the commitment
> > transactions cannot be revoked she broadcasts her secretly minded
> > blockchain which will be accepted by the network as it is the longest
> > chain. (In Particular she includes all the other bitcoin transactions
> that
> > are also in the original public blockchain so that other people don't
> even
> > realize something suspicious has happened.)
> >
> > Since according to the spec channels should never be balanced worse than
> > 99% to 1% the attacker could steal up to 99% of all the bitcoins
> allocated
> > in the sum of all payment channels the attacker was connected to. This
> > amount could obviously be way higher than just double spending her own
> > funds. This attack would be interesting in 

[Lightning-dev] New form of 51% attack via lightning's revocation system possible?

2018-03-13 Thread René Pickhardt via Lightning-dev
Hey everyone,

disclaimer: as mentioned in my other mail (
https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-March/001065.html
) I am currently studying the revocation system of duplex micropayment
channels in detail but I am also pretty new to the topic. So I hope the
attack I am about to describe is not possible and it is just me overseeing
some detail or rather my lack of understanding.
That being said even after waiting one week upon discovery and double
checking the assumptions I made I am still positive that the revocation
system in its current form allows for a new form of a 51% attack. This
attack seems to be way more harmful than a successful 51% attack on the
bitcoin network. Afaik within the bitcoin network I could 'only double
spend' my own funds with a successful 51% attack. In the lightning case it
seems that an attacker could steal an arbitrary amount of funds as long as
the attacker has enough payment channels with enough balance open.

The attack itself follows exactly the philosophy of lightning: "If a tree
falls in the forest and no one is around to hear it. Does it make a sound?"
In the context of the attack this would translate to: "If a 51% attacker
secretly mines enough blocks after fraudulently spending old commitment
transactions and no one sees it during the the *to_self_delay*  period,
have the commitment transactions been spent? (How) Can they be revoked?"


As for the technical details I quote from the spec of BOLT 3:
"*To allow an opportunity for penalty transactions, in case of a revoked
commitment transaction, all outputs that return funds to the owner of the
commitment transaction (a.k.a. the "local node") must be delayed for *
*to_self_delay** blocks. This delay is done in a second-stage HTLC
transaction (HTLC-success for HTLCs accepted by the local node,
HTLC-timeout for HTLCs offered by the local node)*"

Assume an attacker has 51% of the hash power she could open several
lightning channels and in particular accept any incoming payment channel
(the more balance is in her channels the more lucrative the 51% attack).
Since the attacker already has a lot of hash power it is reasonable (but
not necessary) to assume that the attacker already has a lot of bitcoins
and is well known to honest nodes in the network which makes it even more
likely to have many open channels.

The attacker keeps track of her (revocable) commitment transactions in
which the balance is mostly on the attackers side. Once the attacker knows
enough of these (old) commitment transactions the attack is being executed
in the following way:
0.) The max value of to_self_delay is evaluated. Let us assume it is 72
blocks (or half a day).
1.) The attacker secretly starts mining on her own but does not broadcasts
any successfully mined block. Since the attacker has 51% of the hash power
she will most likely be faster than the network to mine the 72 blocks of
the safety period in which fraudulent commitment transactions could be
revoked.
2.) The attacker spends all the fraudulent (old) commitment transactions in
the first block of her secrete mining endeavor.
3.) Meanwhile the attacker starts spending her own funds of her payment
channels e.g on decentralized exchanges for any other (crypto)currency.
4.) As soon as the attacker has mined enough blocks that the commitment
transactions cannot be revoked she broadcasts her secretly minded
blockchain which will be accepted by the network as it is the longest
chain. (In Particular she includes all the other bitcoin transactions that
are also in the original public blockchain so that other people don't even
realize something suspicious has happened.)

Since according to the spec channels should never be balanced worse than
99% to 1% the attacker could steal up to 99% of all the bitcoins allocated
in the sum of all payment channels the attacker was connected to. This
amount could obviously be way higher than just double spending her own
funds. This attack would be interesting in particular for the power nodes
created by the Barabasi-Albert model of lnd's autopilot (c.f.:
https://github.com/lightningnetwork/lnd/issues/677 ).

I understand that with the growth of the bitcoin (mining) network a 51%
attack becomes less and less likely. Also I am very happy to be proven
false about the attack that I am describing.

Another sad thing about this attack is that I currently do not see any
(reasonable) way of preventing this form of a 51% attack (other than
creating payment channels that don't offer the possibility of revocation)
as it is abusing exactly the core idea of lightning to do something in
secret without broadcasting it.

Best regards Rene

---

http://www.rene-pickhardt.de
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev


Re: [Lightning-dev] Pinging a route for capacity

2018-03-01 Thread René Pickhardt via Lightning-dev
Hey everyone,

disclaimer I am new here and have not a full understanding of the complete
specs yet - however since I decided to participate in lighting dev I will
just be brave and try to add my ideas on the problem jimpo posed. So even
in case by ideas are complete bs please just tell me in a friendly way and
I know I need to read more code and specs in order to participate.

Reading about the described problem techniques like IP-Fragmentation (
https://en.wikipedia.org/wiki/IP_fragmentation ) come to my mind. The
setting is a little bit different but in from my current understanding it
should still be applicable and also be the favorable solution in comparison
to the proposed ping:

1.) IP setting: In IP-Fragmentation one would obviously just split the
IP-package in order to utilize a link layer protocol that doesn't have
enough bandwidth for a bigger size package.
2.) Lightning case: When the capacity of a channel during routing is not
high enough - which means that the channel balance on that side is
somewhere between 0 and the size of the payment - one would have to to send
the second part of the fragmented package on a different route. This is
obvious since the insufficient channel balance cannot come out of thin air
(as in IP-Routing).

My first intuition was that this would become a problem for onion routing
since the router in question does not know the final destination but only
knows the next hop which can't be utilized as the channel doesn't have
enough funds. However I imagine one could just encapsulate the second part
of the fragmented payment in a new onion routed package that goes on a
detour (using different payment channels) to the original "next" hop und
progresses from there as it was originally thought of.

Not sure however how the impacts to the HTLC would be and if it would
actually be possible to fragment a payment that is encapsulated within the
onion routing.

If possible the advantage in comparison to your proposed ping method is
that fragmentation would be highly dynamic and still work if a channel runs
out of funds while routing payment. In your ping scenario it could very
well happen that you do a ping for a designated rout, everything looks
great, you send a payment but while it is on its way a channel on that way
could run dry.

best Rene


On Thu, Mar 1, 2018 at 3:45 PM, Jim Posen  wrote:

> My understanding is that the best strategy for choosing a route to send
> funds over is to determine all possible routes, rank them by estimated fees
> based on channel announcements and number of hops, then try them
> successively until one works.
>
> It seems inefficient to me to actually do a full HTLC commitment handshake
> on each hop just to find out that the last hop in the route didn't have
> sufficient remaining capacity in the first place. Depending on how many
> people are using the network, I could also forsee situations where this
> creates more payment failures because bandwidth is locked up in HTLCs that
> are about to fail anyway.
>
> One idea that would likely help is the ability to send a ping over an
> onion route asking "does every hop have capacity to send X msat?" Every hop
> would forward the onion request if the answer is yes, or immediately send
> the response back up the circuit if the answer is no. This should reveal no
> additional information about the channel capacities that the sender
> couldn't determine by sending a test payment to themself (assuming they
> could find a loop). Additionally, the hops could respond with the latest
> fee rate in case channel updates are slow to propagate.
>
> The main benefit is that this should make it quicker to send a successful
> payment because latency is lower than sending an actual payment and the
> sender could ping all possible routes in parallel, whereas they can't send
> multiple payments in parallel. The main downside I can think of is that,
> by the same token, it is faster and cheaper for someone to extract
> information about channel capacities on the network with a binary search.
>
> -jimpo
>
> ___
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>


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