Fabrice Drouin [ARCHIVE]

⚠️ This account is not associated with a real person. It's an archival account for mailing list messages.
🗓️ Active from 2016-02-01 to 2021-10-15
💬 Posted a total of 30 messages
📚 Participated in the following categories: Lightning-dev, RFC
🔇 Please do not DM this user as it's used for archive purposes only.

Public Key

npub1s8zghfrvyydu3ld5jrgue7crvzw8agyslpv8mh9pexgxwmcfelfsk5yaw4

Profile Code

nprofile1qqsgr3yt53kzzx7glk6fp5wvlvpkp8r75zg0skramjsunyr8duyul5cpz3mhxue69uhhyetvv9ujuerpd46hxtnfduqs6amnwvaz7tmwdaejumr0ds7gl056

Publishing to

relay.damus.io

nos.lol

Author Public Key

npub1s8zghfrvyydu3ld5jrgue7crvzw8agyslpv8mh9pexgxwmcfelfsk5yaw4

Show more details

Last Notes

2023-06-09 15:04:05

- reply

📅 Original date posted:2021-10-15
📝 Original message:
On Tue, 12 Oct 2021 at 21:57, Olaoluwa Osuntokun <laolu32 at gmail.com> wrote:
> Also note that lnd has _never_ referred to itself as the "reference"
> implementation. A few years ago some other implementations adopted that
> title themselves, but have since adopted softer language.
I don't remember that but if you're referring to c-lightning it was
the first lightning implementation, and the only one for a while, so
in a way it was a "reference" at the time ?
Or it could have been a reference to their policy of "implementing the
spec, all the spec and nothing but the spec" ?
> I think it's worth briefly revisiting a bit of history here w.r.t the github
> org in question. In the beginning, the lightningnetwork github org was
> created by Joseph, and the lightningnetwork/paper repo was added, the
> manuscript that kicked off this entire thing. Later lightningnetwork/lnd was
> created where we started to work on an initial implementation (before the
> BOLTs in their current form existed), and we were added as owners.
> Eventually we (devs of current impls) all met up in Milan and decided to
> converge on a single specification, thus we added the BOLTs to the same
> repo, despite it being used for lnd and knowingly so.
Yes, work on c-lightning then eclair then lnd all began a long time
before the BOLTs process was implemented, and we all set up repos,
accounts...
I agree that we all inherited things from the "pre-BOLTS" era and
changing them will create some friction but I still believe it should
be done. You also mentioned potential admin rights issues on the
current specs repos which would be solved by moving them to a new
clean repo.
> As it seems the primary grievance here is collocating an implementation of
> Lightning along with the _specification_ of the protocol, and given that the
> spec was added last, how about we move the spec to an independent repo owned
> by the community? I currently have github.com/lightning, and would be happy
> to donate it to the community, or we could create a new org like
> "lightning-specs" or something similar.
Sounds great! github.com/lightning is nice (and I like Damian's idea
of using github.com/lightning/bolts) and seems to please everyone so
it looks that we have a plan!
Fabrice

2023-06-09 15:04:03

- reply

📅 Original date posted:2021-10-12
📝 Original message:
On Tue, 12 Oct 2021 at 01:14, Martin Habovštiak
<martin.habovstiak at gmail.com> wrote:
>
> I can confirm I moved a repository few months ago and all links kept working fine.
>
Yes, github makes it really easy, and you keep your issues, PRs,
stars, .. depending on your dev/packaging you may need to rename
packages (something java/scala/... devs have to do from time to time)
but it's also very simple.
The issue here is not technical.
Fabrice

2023-06-09 15:04:02

- reply

📅 Original date posted:2021-10-08
📝 Original message:
Hello,
When you navigate to https://github.com/lightningnetwork/ you find
- the Lightning Network white paper
- the Lightning Network specifications
- and ... the source code for lnd!
This has been an anomaly for years, which has created some confusion
between Lightning the open-source protocol and Lightning Labs, one of
the companies specifying and implementing this protocol, but we didn't
do anything about it.
I believe that was a mistake: a few days ago, Arcane Research
published a fairly detailed report on the state of the Lightning
Network: https://twitter.com/ArcaneResearch/status/1445442967582302213.
They obviously did some real work there, and seem to imply that their
report was vetted by Open Node and Lightning Labs.
Yet in the first version that they published you’ll find this:
"Lightning Labs, founded in 2016, has developed the reference client
for the Lightning Network called Lightning Network Daemon (LND)....
They also maintain the network standards documents (BOLTs)
repository."
They changed it because we told them that it was wrong, but the fact
that in 2021 people who took time do do proper research, interviews,
... can still misunderstand that badly how the Lightning developers
community works means that we ourselves badly underestimated how
confusing mixing the open-source specs for Lightning and the source
code for one of its implementations can be.
To be clear, I'm not blaming Arcane Research that much for thinking
that an implementation of an open-source protocol that is hosted with
the white paper and specs for that protocol is a "reference"
implementation, and thinking that since Lightning Labs maintains lnd
then they probably maintain the other stuff too. The problem is how
that information is published.
So I'm proposing that lnd's source code be removed from
https://github.com/lightningnetwork/ (and moved to
https://github.com/lightninglabs for example, with the rest of their
Lightning tools, but it's up to Lightning Labs).
Thanks,
Fabrice

2023-06-09 14:53:55

- reply

📅 Original date posted:2019-01-07
📝 Original message:
Hi Chris,
What we've learned building a lite bitcoin/LN wallet is that there are
different things it must implement:
- a bitcoin wallet. We started with bitcoinj, but there are known
issues with Bloom Filters, which is one of the reasons why we ended up
building our own wallet that connect to Electrum Servers (and it seems
we're not the only ones). I'm not sure that a "better" implementation
of BIP37 is actually needed, if that's what you mean by "traditional
SPV". Client-side filters is a nice improvement, and we have a basic
Neutrino prototype that is up to date with the BIPs but not used in
our mobile app. We could collaborate on this ?
- monitoring your channels" part: detect that your peer is trying to
cheat and published an old commit tx, and publish a penalty tx. This
is fairly easy (the "detecting" part at least :))
- validating channels: you receive gossip message, and check that
channels actually exist, detect when they've been closed and remove
them from your routing table. This is much harder. Electrum servers
now have a method for retrieving a tx from its coordinates (height +
position), but as the number of channels grows it may become
impractical to watch every channel. With Bloom Filters and client-side
filters you probably end up having to download all blocks (but not
necessarily store them all).
I also think that it's very important the lite wallet support mobile
platforms, android in your case, and since it's basically stuck at
Java 7 you may wan to consider using plain Java (or Kotlin) instead of
Scala as much as possible.
Cheers,
Fabrice
On Sun, 6 Jan 2019 at 15:58, Chris Stewart <chris at suredbits.com> wrote:
>
> Hi all,
>
> Hope your 2019 is off to a fantastic start. I'm really excited for Lightning in 2019.
>
> We are currently reviving a lite client project in bitcoin-s (https://github.com/bitcoin-s/bitcoin-s-core/pull/280). The goal is to have a modern replacement for bitcoinj that also can be used for L2 applications like lightning. We also are planning on supporting multiple coins, hsms etc.
>
> The current plan is to implement traditional SPV, and then implement neutrino when development is picking back up on that in bitcoin core. If that takes too long, we will consider implementing neutrino against btcd.
>
> What I wanted to ask of the mailing list is to give us "things to consider" when developing this lite client from a usability perspective for lightning devs. How can we make your lives easier?
>
> One thing that seems logical is to adhere to the bitcoin core api when possible, this means you can use bitcoin-s as a drop in lite client replacement for bitcoin core.
>
> Thoughts?
>
> -Chris
>
>
>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-09 14:53:53

- reply

📅 Original date posted:2019-01-20
📝 Original message:
Additional info on channel_update traffic:
Comparing daily backups of routing tables over the last 2 weeks shows
that nearly all channels get at least a new update every day. This
means that channel_update traffic is not primarily cause by nodes
publishing new updates when channel are about to become stale:
otherwise we would see 1/14th of our channels getting a new update on
the first day, then another 1/14th on the second day and so on.This is
confirmed by comparing routing table backups over a single day: nearly
all channels were updated, one average once, with an update that
almost always does not include new information.
It could be caused by "flapping" channels, probably because the hosts
that are hosting them are not reliable (as in is often offline).
Heuristics can be used to improve traffic but it's orhtogonal to the
problem of improving our current sync protocol.
Also, these heuristics would probaly be used to close channels to
unreliable nodes instead of filtering/delaying publishing updates for
them.
Finally, this is not just obsessing over bandwidth (though bandwidth
is a real issue for most mobile users). I'm also over obsessing over
startup time and payment UX :), because they do matter a lot for
mobile users, and would like to push the current gossip design as far
as it can go. I also think that we'll face the same issue when
designing inventory messages for channel_update messages.
Cheers,
Fabrice
On Wed, 9 Jan 2019 at 00:44, Rusty Russell <rusty at rustcorp.com.au> wrote:
>
> Fabrice Drouin <fabrice.drouin at acinq.fr> writes:
> > I think there may even be a simpler case where not replacing updates
> > will result in nodes not knowing that a channel has been re-enabled:
> > suppose you got 3 updates U1, U2, U3 for the same channel, U2 disables
> > it, U3 enables it again and is the same as U1. If you discard it and
> > just keep U1, and your peer has U2, how will you tell them that the
> > channel has been enabled again ? Unless "discard" here means keep the
> > update but don't broadcast it ?
>
> This can only happen if you happen to lose connection to the peer(s)
> which sent U2 before it sends U3.
>
> Again, this corner case penalizes flapping channels. If we also
> ratelimit our own enables to 1 per 120 seconds, you won't hit this case?
>
> > But then there's a risk that nodes would discard channels as stale
> > because they don't get new updates when they reconnect.
>
> You need to accept redundant updates after 1 week, I think.
>
> Cheers,
> Rusty.

2023-06-09 14:53:52

- reply

📅 Original date posted:2019-01-08
📝 Original message:
On Tue, 8 Jan 2019 at 17:11, Christian Decker
<decker.christian at gmail.com> wrote:
>
> Rusty Russell <rusty at rustcorp.com.au> writes:
> > Fortunately, this seems fairly easy to handle: discard the newer
> > duplicate (unless > 1 week old). For future more advanced
> > reconstruction schemes (eg. INV or minisketch), we could remember the
> > latest timestamp of the duplicate, so we can avoid requesting it again.
>
> Unfortunately this assumes that you have a single update partner, and
> still results in flaps, and might even result in a stuck state for some
> channels.
>
> Assume that we have a network in which a node D receives the updates
> from a node A through two or more separate paths:
>
> A --- B --- D
> \--- C ---/
>
> And let's assume that some channel of A (c_A) is flapping (not the ones
> to B and C). A will send out two updates, one disables and the other one
> re-enables c_A, otherwise they are identical (timestamp and signature
> are different as well of course). The flush interval in B is sufficient
> to see both updates before flushing, hence both updates get dropped and
> nothing apparently changed (D doesn't get told about anything from
> B). The flush interval of C triggers after getting the re-enable, and D
> gets the disabling update, followed by the enabling update once C's
> flush interval triggers again. Worse if the connection A-C gets severed
> between the updates, now C and D learned that the channel is disabled
> and will not get the re-enabling update since B has dropped that one
> altogether. If B now gets told by D about the disable, it'll also go
> "ok, I'll disable it as well", leaving the entire network believing that
> the channel is disabled.
>
> This is really hard to debug, since A has sent a re-enabling
> channel_update, but everybody is stuck in the old state.
I think there may even be a simpler case where not replacing updates
will result in nodes not knowing that a channel has been re-enabled:
suppose you got 3 updates U1, U2, U3 for the same channel, U2 disables
it, U3 enables it again and is the same as U1. If you discard it and
just keep U1, and your peer has U2, how will you tell them that the
channel has been enabled again ? Unless "discard" here means keep the
update but don't broadcast it ?
> At least locally updating timestamp and signature for identical updates
> and then not broadcasting if they were the only changes would at least
> prevent the last issue of overriding a dropped state with an earlier
> one, but it'd still leave C and D in an inconsistent state until we have
> some sort of passive sync that compares routing tables and fixes these
> issues.
But then there's a risk that nodes would discard channels as stale
because they don't get new updates when they reconnect.
> I think all the bolted on things are pretty much overkill at this point,
> it is unlikely that we will get any consistency in our views of the
> routing table, but that's actually not needed to route, and we should
> consider this a best effort gossip protocol anyway. If the routing
> protocol is too chatty, we should make efforts towards local policies at
> the senders of the update to reduce the number of flapping updates, not
> build in-network deduplications. Maybe something like "eager-disable"
> and "lazy-enable" is what we should go for, in which disables are sent
> right away, and enables are put on an exponential backoff timeout (after
> all what use are flappy nodes for routing?).
Yes there are probably heuristics that would help reducing gossip
traffic, and I see your point but I was thinking about doing the
opposite: "eager-enable" and "lazy-disable", because from a sender's
p.o.v trying to use a disabled channel is better than ignoring an
enabled channel.
Cheers,
Fabrice

2023-06-09 14:53:51

- reply

📅 Original date posted:2019-01-04
📝 Original message:
On Fri, 4 Jan 2019 at 04:43, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> > - in set reconciliation schemes: we could reconcile [channel id |
> > timestamp | checksum] first
>
> Perhaps I misunderstand how set reconciliation works, but --- if timestamp is changed while checksum is not, then it would still be seen as a set difference and still require further communication rounds to discover that the channel parameters have not actually changed.
>
> Perhaps it is better to reconcile [channel_id | checksum] instead, and if there is a different set of channel parameters, share the set difference and sort out which timestamp is later at that point.
Ah yes of course, the `timestamp` should not be included.
Cheers,
Fabrice

2023-06-09 14:53:50

- reply

📅 Original date posted:2019-01-02
📝 Original message:
Hello All, and Happy New Year!
To understand why there is a steady stream of channel updates, even
when fee parameters don't seem to actually change, I made hourly
backups of the routing table of one of our nodes, and compared these
routing tables to see what exactly was being modified.
It turns out that:
- there are a lot of disable/enable/disable etc…. updates which are
just sent when a channel is disabled then enabled again (when nodes go
offline for example ?). This can happen
there are also a lot of updates that don’t change anything (just a new
timestamp and signatures but otherwise same info), up to several times
a day for the same channel id
In both cases we end up syncing info that we already have.
I don’t know yet how best to use this when syncing routing tables, but
I thought it was worth sharing anyway. A basic checksum that does not
cover all fields, but only fees and HTLC min/max values could probably
be used to improve routing table sync ?
Cheers,
Fabrice

2023-06-09 14:53:50

- reply

📅 Original date posted:2019-01-02
📝 Original message:
On Wed, 2 Jan 2019 at 18:26, Christian Decker
<decker.christian at gmail.com> wrote:
>
> For the ones that flap with a period that is long enough for the
> disabling and enabling updates being flushed, we are presented with a
> tradeoff. IIRC we (c-lightning) currently hold back disabling
> `channel_update`s until someone actually attempts to use the channel at
> which point we fail the HTLC and send out the stashed `channel_update`
> thus reducing the publicly visible flapping. For the enabling we can't
> do that, but we could think about a local policy on how much to delay a
> `channel_update` depending on the past stability of that peer. Again
> this is local policy and doesn't warrant a spec change.
>
> I think we should probably try out some policies related to when to send
> `channel_update`s and how to hide redundant updates, and then we can see
> which ones work best :-)
>
Yes, I haven't looked at how to handle this with local policies. My
hypothesis is that when you're syncing a routing table that is say one
day old, you end up querying and downloading a lot of information that
you already have, and that adding a basic checksum to our channel
queries may greatly improve this. Of course this would be much more
actionable with stats and hard numbers which I'll provide ASAP.
Cheers,
Fabrice

2023-06-09 14:53:50

- reply

📅 Original date posted:2019-01-03
📝 Original message:
Follow-up: here's more detailed info on the data I collected and
potential savings we could achieve:
I made hourly routing table backups for 12 days, and collected routing
information for 17 000 channel ids.
There are 130 000 different channel updates :on average each channel
has been updated 8 times. Here, “different” means that at least the
timestamp has changed, and a node would have queried this channel
update during its syncing process.
But only 18 000 pairs of channel updates carry actual fee and/or HTLC
value change. 85% of the time, we just queried information that we
already had!
Adding a basic checksum (4 bytes for example) that covers fees and
HTLC min/max value to our channel range queries would be a significant
improvement and I will add this the open BOLT 1.1 proposal to extend
queries with timestamps.
I also think that such a checksum could also be used
- in “inventory” based gossip messages
- in set reconciliation schemes: we could reconcile [channel id |
timestamp | checksum] first
Cheers,
Fabrice

2023-06-09 14:51:55

- reply

📅 Original date posted:2018-10-31
📝 Original message:
Context
======
Sent payments that remain pending, i.e. payments which have not yet
been failed or fulfilled, are currently a major UX challenge for LN
and a common source of complaints from end-users.
Why payments are not fulfilled quickly is not always easy to
investigate, but we've seen problems caused by intermediate nodes
which were stuck waiting for a revocation, and recipients who could
take a very long time to reply with a payment preimage.
It is already possible to partially mitigate this by disconnecting
from a node that is taking too long to send a revocation (after 30
seconds for example) and reconnecting immediately to the same node.
This way pending downstream HTLCs can be forgotten and the
corresponding upstream HTLCs failed.
Proposed changes
===============
It should be possible to provide a faster "proceed/try another route"
answer to the sending node using probing with short timeout
requirements: before sending the actual payment it would first send a
"blank" probe request, along the same route. This request would be
similar to a payment request, with the same onion packet formatting
and processing, with the additional requirements that if the next node
in the route has not replied within the timeout period (typically a
few hundred milliseconds) then the current node will immediately send
back an error message.
There could be several options for the probe request:
- include the same amounts and fee constraints than the actual payment request.
- include no amount information, in which case we're just trying to
"ping" every node on the route.
Implementation
============
I would like to discuss the possibility of implementing this with a "0
satoshi" payment request that the receiving node would generate along
with the real one. The sender would first try to "pay" the "0 satoshi"
request using the route it computed with the actual payment
parameters. I think that it would not require many changes to the
existing protocol and implementations.
Not using the actual amount and fees means that the actual payment
could fail because of capacity issues but as long as this happens
quickly, and it should since we checked first that all nodes on the
route are alive and responsive, it still is much better than “stuck”
payments.
And it would not help if a node decides to misbehave, but would not
make things worse than they are now (?)
Cheers,
Fabrice

2023-06-09 14:51:54

- reply

📅 Original date posted:2018-10-29
📝 Original message:
Nice work, thank you!
On Fri, 26 Oct 2018 at 17:37, <tomokio203 at gmail.com> wrote:
>
> Hello lightning network developers.
> Nayuta team is developing Wireshark plug-in for Lightning Network(BOLT) protocol.
> https://github.com/nayutaco/lightning-dissector
>
> It’s alpha version, but it can decode some BOLT message.
> Currently, this software works for Nayuta’s implementation(ptarmigan) and Éclair.
> When ptarmigan is compiled with some option, it write out key information file. This Wireshark plug-in decode packet using that file.
> When you use Éclair, this software parse log file.
>
> Through our development experience, interoperability test is time consuming task.
> If people can see communication log of BOLT message on same format (.pcap), it will be useful for interoperability test.
>
> Our proposal:
> Every implementation has compile option which enable output key information file.
>
> We are glad if this project is useful for lightning network eco-system.
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-09 14:51:50

- reply

📅 Original date posted:2018-10-18
📝 Original message:
Hello,
> 1. Rather than trying to agree on what fees will be in the future, we
> should use an OP_TRUE-style output to allow CPFP (Roasbeef)
We could also use SIGHASH_ANYONECANPAY|SIGHASH_SINGLE for HTLC txs, without
adding the "OP_TRUE" output to the commitment transaction. We would still
need the update_fee message to manage onchain fees for the commit tx (but
not the HTLC txs) but there would be no reason anymore to refuse fee rates
that are too high and channels would not get closed anymore when there's a
spike in onchain fees.
Cheers,
Fabrice
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20181018/955aa508/attachment.html>

2023-06-09 14:51:35

- reply

📅 Original date posted:2018-10-12
📝 Original message:
Hi Zmn,
> It may be reduced to a set reconciliation problem if we consider the timestamp and enable/disable state of channel updates as part of an item, i.e. a channel update of 111:1:1 at 2018-10-04 state=enabled is not the same as a channel update of 111:1:1 at 2018-10-05 state=disabled.
>
> Then both sides can use standard set reconciliation algorithms, and for channel updates of the same short channel ID, we simply drop all items except the one with latest timestamp.
>
> The above idea might be less efficient than your proposed extension.
Yes there may be some way use the structure of channel_update messages
to transpose this into a set reconciliation problem, and use smarter
tools like IBLTs. But we would need to have a good estimate for the
number of differences between the local and remote sets. This would be
the really hard part I think, and probably even harder to get right
with channel_updates than with channel_announcements. I had a quick
look at how this type of sync issue is handled in different contexts
and my impression is that exchanging and and comparing timestamps
would be the most natural solution ?
But mostly my point is that I think we missed something with the
current channel queries, so first I would like to know if other people
agree with that :) and propose something that is close to what we have
today, should be easy to implement if you already support channel
queries, and should fix the issue that I think we have.
Thanks,
Fabrice

2023-06-09 14:51:34

- reply

📅 Original date posted:2018-10-04
📝 Original message:
Hi,
This a a proposal for an extension of our current “channel queries”
that should allow nodes to properly sync their outdated channel
updates. I already opened a issue on the RFC’s github repo
(https://github.com/lightningnetwork/lightning-rfc/issues/480) but
decided to post here too to, to have a less “constrained” discussion.
And it looks like a fairly standard synchronisation problem so maybe
someone will think of others similar schemes that have been used in a
different context.
Thanks,
Fabrice
Background: Routing Table Sync
(If you’re familiar with LN you can just skip this section)
LN is a p2p network of nodes, which can be represented as a graph
where nodes are vertices and channels are edges, and where you can pay
any node you can find a route to:
- each nodes maintains a routing table i.e. a full view of the LN graph
- to send a payment, nodes use their local routing table to compute a
route to the destination, and send a onion-like message to the first
node on that route, which will forward it to the next node and so on
until it reaches its destination
The routing table includes:
- “static” information: channel announcements
- “dynamic” information: channel updates (relay fees)
(It also includes node announcements, which are not needed for route
computation)
Using our graph analogy, channel updates would be edge parameters
(cost, max capacity, min payment amount, …). They can change often,
usually when nodes decide to change their relay fee policy, but also
to signify that a channel is temporarily unusable. A new channel
update will replace the previous one.
Channel ids are identified with an 8 bytes "short transaction id": we
use the blockchain coordinates of the funding tx: block height (4
bytes) + tx index (2 bytes) + output index (2 bytes)
Chanel updates include a channel id, a direction (for a channel
between Alice and Bob there are 2 channel updates: one for Alice->Bob
and one for Bob->Alice), fee parameters, and a 4 bytes timestamp.
To compute routes, nodes need a way to keep their routing table
up-to-date: we call it "routing table sync" or "routing sync".
There is something else to consider: route finding is only needed when
you're * sending * payments, not when you're relaying them or
receiving them. A node that sits in the "middle" of the LN network and
just keeps relaying payments would work even if it has no routing
information at all.
Likewise, a node that just creates payment requests and receives
payments does not need a routing table.
On the other end of the spectrum, a LN "wallet" that is mostly used to
send payments will not work very well it its routing table is missing
info or contains outdated info, so routing sync is a very important
issue for LN wallets, which are also typically offline more often than
other nodes.
If your wallet is missing channel announcements it may not be able to
find a route, and if its channel updates are outdated it may compute a
route that includes channels that are temporarily disabled, or use fee
rates that are too old and will be refused by relaying nodes. In this
case nodes can return errors that include their most recent channel
update, so that the sender can try again, but this will only work well
if just a few channel updates are outdated.
So far, these are the “routing table sync” schemes that have been
specified and implemented:
Step #1: just send everything
The first routing sync scheme was very simple: nodes would request
that peers they connect to send them a complete "dump" of their entire
routing table. It worked well at the beginning but was expensive for
both peers and quickly became impractical.
Step #2: synchronise channel announcements
New query messages where added to the LN protocol to improve routing
table sync: nodes can ask their peers for all their channel ids in a
given block range, compare that list to their own channel ids and
query the ones they're missing (as well as related channel updates).
Nodes can also send a timestamp-based filter to their peers ("only
send me channel updates that match this timestamp filter").
It's a nice improvement but there are still issues with nodes that are
offline very often: they will be able to sync their channel
announcements, but not their channel updates.
Suppose that at T0 a node has 1000 channel updates that are outdated.
It comes back online, starts syncing its routing table, and goes
offline after a few minutes. It now has 900 channel updates that are
outdated.
At T1 = T0 + 8 hours it comes back online again. If it uses T0 to
filter out channel updates, it will never receive the info it is
missing for its 900 outdated channel updates. Using our "last time I
was online at" timestamp as a gossip filter does not work here.
=> Proposed solution: timestamp-based channel updates sync
We need a better method for syncing channel updates. And it is not
really a set reconciliation problem (like syncing channel
announcements for example): we’re not missing items, we’re missing
updates for existing items.
So I propose to extend query parameters to include channel update timestamps:
When A connects to B, it ask for a list of [channel id (8 bytes)|
channel update timestamp #1 (4 bytes)| channel update timestamp #2 (4
bytes)] in a given [start_height, number_of_blocks] block range
B replies with a list of [channel id (8 bytes)| channel update
timestamp #1 (4 bytes)| channel update timestamp #2 (4 bytes)]
A checks its local routing table, and sends a query that includes a
list of [channel id (8 bytes) | flag (1 byte)], where flag is a
combination of
send me the channel announcement for this channel id
send me the channel update #1 for this channel id
send me the channel update #2 for this channel id
B replies with the requested items.
This will allow B to know very quickly how far behind it is, and
display a “sync progress” indicator as it receives the items it
requested.
We’ve been testing this strategy on our mobile wallet for a few weeks
and so far our test results are positive: it fixes the issue we had
when local routing tables were missing a lot of “temporarily
disabled” channel updates. And it’s fairly easy to support these new
queries for implementations that already support channel range
queries.

2023-06-09 14:48:55

- reply

📅 Original date posted:2018-02-21
📝 Original message:
On 20 February 2018 at 02:08, Rusty Russell <rusty at rustcorp.com.au> wrote:
> Hi all,
>
> This consumed much of our lightning dev interop call today! But
> I think we have a way forward, which is in three parts, gated by a new
> feature bitpair:
We've built a prototype with a new feature bit `channel_range_queries`
and the following logic:
When you receive their init message and check their local features
- if they set `initial_routing_sync` and `channel_range_queries` then
do nothing (they will send you a `query_channel_range`)
- if they set `initial_routing_sync` and not `channel_range_queries`
then send your routing table (as before)
- if you support `channel_range_queries` then send a
`query_channel_range` message
This way new and old nodes should be able to understand each other
> 1. query_short_channel_id
> =========================
>
> 1. type: 260 (`query_short_channel_id`)
> 2. data:
> * [`32`:`chain_hash`]
> * [`8`:`short_channel_id`]
We could add a `data` field which contains zipped ids like in
`reply_channel_range` so we can query several items with a single
message ?
> 1. type: 262 (`reply_channel_range`)
> 2. data:
> * [`32`:`chain_hash`]
> * [`4`:`first_blocknum`]
> * [`4`:`number_of_blocks`]
> * [`2`:`len`]
> * [`len`:`data`]
We could add an additional `encoding_type` field before `data` (or it
could be the first byte of `data`)
> Appendix A: Encoding Sizes
> ==========================
>
> I tried various obvious compression schemes, in increasing complexity
> order (see source below, which takes stdin and spits out stdout):
>
> Raw = raw 8-byte stream of ordered channels.
> gzip -9: gzip -9 of raw.
> splitgz: all blocknums first, then all txnums, then all outnums, then gzip -9
> delta: CVarInt encoding: blocknum_delta,num,num*txnum_delta,num*outnum.
> deltagz: delta, with gzip -9
>
> Corpus 1: LN mainnet dump, 1830 channels.[1]
>
> Raw: 14640 bytes
> gzip -9: 6717 bytes
> splitgz: 6464 bytes
> delta: 6624 bytes
> deltagz: 4171 bytes
>
> Corpus 2: All P2SH outputs between blocks 508000-508999 incl, 790844 channels.[2]
>
> Raw: 6326752 bytes
> gzip -9: 1861710 bytes
> splitgz: 964332 bytes
> delta: 1655255 bytes
> deltagz: 595469 bytes
>
> [1] http://ozlabs.org/~rusty/short_channels-mainnet.xz
> [2] http://ozlabs.org/~rusty/short_channels-all-p2sh-508000-509000.xz
>
Impressive!

2023-06-09 14:48:53

- reply

📅 Original date posted:2018-02-13
📝 Original message:
On 12 February 2018 at 02:45, Rusty Russell <rusty at rustcorp.com.au> wrote:
> Christian Decker <decker.christian at gmail.com> writes:
>> Rusty Russell <rusty at rustcorp.com.au> writes:
>>> Finally catching up. I prefer the simplicity of the timestamp
>>> mechanism, with a more ambitious mechanism TBA.
>>
>> Fabrice and I had a short chat a few days ago and decided that we'll
>> simulate both approaches and see what consumes less bandwidth. With
>> zombie channels and the chances for missing channels during a weak form
>> of synchronization, it's not that clear to us which one has the better
>> tradeoff. With some numbers behind it it may become easier to decide :-)
>
> Maybe; I think we'd be best off with an IBLT-approach similar to
> Fabrice's proposal. An IBLT is better than a simple hash, since if your
> results are similar you can just extract the differences, and they're
> easier to maintain. Even easier if we make the boundaries static rather
> than now-relative. For node_announce and channel_update you'd probably
> want separate IBLTs (perhaps, though not necessarily, as a separate
> RTT).
Yes,
real filters would be better, but
the 'bucket hash' idea works (from what I've seen on testnet)
for our
specific
target
(nodes which are connected to very small number of peers and go offline

very often)
.
> Note that this approach fits really well as a complement to the
> timestamp approach: you'd use this for older pre-timestamp, where you're
> likely to have a similar idea of channels.
Both approaches maybe needed because they may be solutions to different
problems (nodes which get
d
isconnected from

a small set of peers vs nodes connected to many peers, which remain
online but not some of their peers)
>>> Now, as to the proposal specifics.
>>>
>>> I dislike the re-transmission of all old channel_announcement and
>>> node_announcement messages, just because there's been a recent
>>> channel_update. Simpler to just say 'send anything >=
>>> routing_sync_timestamp`.
>>
>> I'm afraid we can't really omit the `channel_announcement` since a
>> `channel_update` that isn't preceded by a `channel_announcement` is
>> invalid and will be dropped by peers (especially because the
>> `channel_update` doesn't contain the necessary information for
>> validation).
>
> OTOH this is a rare corner case which will eventually be fixed by weekly
> channel_announce retransmission. In particular, the receiver should
> have already seen the channel_announce, since it preceeded the timestamp
> they asked for.
>
> Presumably IRL you'd ask for a timestamp sometime before you were last
> disconnected, say 30 minutes.
>
> "The perfect is the enemy of the good".
This is precisely what I think
would
not work very well with the timestamp approach:

when you're missing an 'old' channel announcement, and only have a few
sources for them.

It can have a huge impact on terminal nodes which won't be able to find
routes and waiting for a

new channel update would take too long.
Yes, using just a few peers mean that you will be limited to the routing
table they will give you, but

having some kind of filter would let nodes connect

to other peers just to retrieve
them and check how far off they are from the rest of the nework. This
would not possible with a timestamp (you would need to download the entire
routing table again, which is what we're trying to avoid)
>>> Background: c-lightning internally keeps an tree of gossip in the order
>>> we received them, keeping a 'current' pointer for each peer. This is
>>> very efficient (though we don't remember if a peer sent us a gossip msg
>>> already, so uses twice the bandwidth it could).
Ok so a peer would receive an announcement it has sent, but woud
immediately dismiss it ?
>>
>> We can solve that by keeping a filter of the messages we received from
>> the peer, it's more of an optimization than anything, other than the
>> bandwidth cost, it doesn't hurt.
>
> Yes, it's on the TODO somewhere... we should do this!
>
>>> But this isn't *quite* the same as timestamp order, so we can't just set
>>> the 'current' pointer based on the first entry >=
>>> `routing_sync_timestamp`; we need to actively filter. This is still a
>>> simple traverse, however, skipping over any entry less than
>>> routing_sync_timestamp.
>>>
>>> OTOH, if we need to retransmit announcements, when do we stop
>>> retransmitting them? If a new channel_update comes in during this time,
>>> are we still to dump the announcements? Do we have to remember which
>>> ones we've sent to each peer?
>>
>> That's more of an implementation detail. In c-lightning we can just
>> remember the index at which the initial sync started, and send
>> announcements along until the index is larger than the initial sync
>> index.
>
> True. It is an implementation detail which is critical to saving
> bandwidth though.
>
>> A more general approach would be to have 2 timestamps, one highwater and
>> one lowwater mark. Anything inbetween these marks will be forwarded
>> together with all associated announcements (node / channel), anything
>> newer than that will only forward the update. The two timestamps
>> approach, combined with a new message, would also allow us to send
>> multiple `timestamp_routing_sync` messages, e.g., first sync the last
>> hour, then the last day, then the last week, etc. It gives the syncing
>> node control over what timewindow to send, inverting the current initial
>> sync.
>
> That would fit neatly with the more complicated bucketing approaches:
> you'd use this technique to ask for the entire bucket if the SHA
> mismatched/IBLT failed.
There is also somehting that would work fairly well today: just exchange
all shortIds that you have.
With the simplest possible implementation (sort and concatenate all 8 bytes
short ids and compress with xz or gz or zip)
it fits in about 8 Kb. And there are lots of easy optimizations
(heights are mostly consecutive integers, tx and output index are small...)
> Cheers,
> Rusty.
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180213/18989ef5/attachment-0001.html>

2023-06-09 14:48:53

- reply

📅 Original date posted:2018-02-19
📝 Original message:
I'm still pushing for the hash-based solution because it can be
implemented and developed quickly and easily and fixes the main issues
we've seen on testnet:
- routing sync on mobile nodes
- "route not found" errors when you're missing routing info.
It can be deployed as an optional feature and will give us time to
specify and implement proper IBLT-based filters.
It can be combined with the timestamp approach: nodes would send
bucket hashes + low and high watermarks.
I've tried and summarised the issue below:
## The problem
The current scheme (broadcast + optionally ask for a full routing
table when you connect) works well for nodes which are never
completely offline, but is becoming unpractical on mobile
node/end-user nodes which are often offline and connected to a few
peers. We need a way to improve the initial routing sync and retrieve
announcements that we've missed without having to download the entire
routing table.
Additionally, the only way to check that routing information is
consistent between different nodes is to ask each one of them to send
you their entire routing table. Exchanging filters/digests/… would
mitigate the issue of having to “trust” that your peers do provide do
with a good routing table, especially when you’re connected to very
few peers.
## Requirements
- Easy to specify and implement
- Low overhead
- Ability to retrieve missing routing information
- (Nice to have) Ability to query multiple peers for consistency checks
## Background
The current method for retrieving this routing table is to set the
`initial_routing_sync` flag in the `init` message that you send every
time you connect/reconnect to a peer, which will then send back its
entire routing table (currently 6000 channels on testnet).
If a node believes that a channel is available when it has in fact
been closed, and uses it to build a route, it will receive an error
message and try again without this specific channel.
But if a node is missing a channel, and cannot route payments, there
is currently no way to recover it: it has to wait until the channel
parameters are updated, and will then receive a `channel_announcement`
and the matching `channel_update`. This could take a very long time.
Hence, the only option for mobile nodes is to request a routing table
dump every time they connect/reconnect, which simply does not work.
We need a way to improve this initial table sync, which is simple
enough to be implemented and deployed quickly. Otherwise, these nodes
will probably use ugly specific hacks (like use their own mechanisms
for retrieving and syncing routing tables) or even rely on remote
servers to compute routes for them.
## Proposed solutions
### Timestamps/watermarks
When they connect to another peer, nodes send a timestamp (I know the
routing table up to X) or a pair of timestamps (I know the routing
table from time X to time Y).
Pros:
- Very simple to specify (use `channel_update` timestamps) and implement.
- Very little overhead
- Solves the “download the entire routing table every time” issue
Cons:
- Does not solve the "missing announcements" issue: if you're missing
routing info you would have to wait for channel parameters to be
updated etc.., as above
### Bucket hashes
Routing info (i.e. channel announcements) are grouped by buckets, one
bucket being a group of 144 blocks. A hash is computed for each
bucket, peers exchanges these hashes and send back all announcements
for which bucket hashes don't match.
We propose to use a bucket per block for the last 7 days, one bucket
per 144 blocks for older announcements,
If gives a total of `(365 + 7*144) = 1373` hashes, for a year of announcements
Pros:
- Simple to specify and implement
- Little overhead (a few dozen Kb)
- If a node is missing a few elements it will immediately recover
them, even if they're very old
- Works well when routing tables are mostly synchronized, which would
be the case for nodes which connect to a very small number of peers
- Bucket hashes are the same for all peers you connect to, and can be
used for consistency checks between peers
Cons:
- Buckets hashes are not queryable filters
- Since a single mismatch will invalidate an entire buckets, even with
small differences nodes could end up having to send their entire
routing table (which exactly what they are doing today)
### IBLT filters
Upon connection, nodes exchange information to estimate the number of
differences between their routing table.
Using this estimate, they build and exchange IBLT filters, and use
them to compute the announcements that they should send to their peer.
Pros:
- Queryable filters
- Very efficient if the number of differences is small, even with very
large routing tables
Cons:
- More complex to specify and implement: we need a good estimator for
the number of differences (send min height + max height + a sample of
announcements ?)
- Filters become peer-specific (similar to the server-side vs
client-side filtering for SPV clients)
On 16 February 2018 at 13:34, Fabrice Drouin <fabrice.drouin at acinq.fr> wrote:
> I like the IBLT idea very much but my understanding of how they work
> is that that the tricky part would be first to estimate the number of
> differences between "our" and "their" routing tables.
> So when we open a connection we would first exchange messages to
> estimate how far off we are (by sending a sample of shortids and
> extrapolate ?) then send filters which would be specific to each peer.
> This may become an issue if a node is connected to many peers, and is
> similar to the server-side vs client-side filtering issue for SPV
> clients.
> Basically, I fear that it would take some time before it is agreed
> upon and available, hindering the development of mobile nodes.
>
> The bucket hash idea is naive but is very simple to implement and
> could buy us enough time to implement IBLT filters properly. Imho the
> timestamp idea does not work for the mobile phone use case (but is
> probably simpler and better that bucket hashes for "centre" nodes
> which are never completely off the grid)
>
>
> On 14 February 2018 at 01:24, Rusty Russell <rusty at rustcorp.com.au> wrote:
>> Fabrice Drouin <fabrice.drouin at acinq.fr> writes:
>>> Yes, real filters would be better, but the 'bucket hash' idea works
>>> (from what I've seen on testnet) for our specific target (nodes which
>>> are connected to very small number of peers and go offline very
>>> often)
>>
>> What if we also add an 'announce_query' message: if you see a
>> 'channel_update' which you discard because you don't know the channel,
>> 'announce_query' asks them to send the 'channel_announce' for that
>> 'short_channel_id' followed by re-sending the 'channel_update'(s)?
>> (Immediately, rather than waiting for next gossip batch).
>>
>> I think we would want this for IBLT, too, since you'd want this to query
>> any short-channel-id you extract from that which you don't know about.
>
> Yes, unless it is part of the initial sync (compare filters. then send
> what they're missing)
>
>> I see. (BTW, your formatting makes your post sounds very Zen!).
> Sorry about that, I've disabled the haiku mode :)
>
>> Yes, we can probably use difference encoding and use 1 bit for output
>> index (with anything which is greater appended) and get down to 1 byte
>> per channel_id at scale.
>>
>> But my rule-of-thumb for scaling today is 1M - 10M channels, and that
>> starts to get a little excessive. Hence my interest in IBLTs, which are
>> still pretty trivial to implement.
>
> Yes, sending all shortids would also have been a temporary measure
> while a more sophisticated approach is being designed.
>>
>> Cheers,
>> Rusty.

2023-06-09 14:48:50

- reply

📅 Original date posted:2018-02-07
📝 Original message:
Hi,
Suppose you partition nodes into 3 generic roles:
- payers: they mostly send payments, are typically small and operated
by end users, and are offline quite a lot
- relayers: they mostly relay payments, and would be online most of
the time (if they're too unreliable other nodes will eventually close
their channels with them)
- payees: they mostly receive payments, how often they can be online
is directly link to their particular mode of operations (since you
need to be online to receive payments)
Of course most nodes would play more or less all roles. However,
mobile nodes would probably be mostly "payers", and they have specific
properties:
- if they don't relay payments they don't have to be announced. There
could be millions of mobile nodes that would have no impact on the
size of the routing table
- it does not impact the network when they're offline
- but they need an accurate routing table. This is very different from
nodes who mostly relay or accept payements
- they would be connected to a very small number of nodes
- they would typically be online for just a few hours every day, but
could be stopped/paused/restarted many times a day
Laolu wrote:
> So I think the primary distinction between y'alls proposals is that
> cdecker's proposal focuses on eventually synchronizing all the set of
> _updates_, while Fabrice's proposal cares *only* about the newly created
> channels. It only cares about new channels as the rationale is that if once
> tries to route over a channel with a state channel update for it, then
> you'll get an error with the latest update encapsulated.
If you have one filter per day and they don't match (because your peer
has channels that you missed, or
have been closed and you were not aware of it) then you will receive
all channel announcements for
this particular day, and the associated updates
Laolu wrote:
> I think he's actually proposing just a general update horizon in which
> vertexes+edges with a lower time stamp just shouldn't be set at all. In the
> case of an old zombie channel which was resurrected, it would eventually be
> re-propagated as the node on either end of the channel should broadcast a
> fresh update along with the original chan ann.
Yes but it could take a long time. It may be worse on testnet since it
seems that nodes
don't change their fees very often. "Payer nodes" need a good routing
table (as opposed
to "relayers" which could work without one if they never initiate payments)
Laolu wrote:
> This seems to assume that both nodes have a strongly synchronized view of
> the network. Otherwise, they'll fall back to sending everything that went on
> during the entire epoch regularly. It also doesn't address the zombie churn
> issue as they may eventually send you very old channels you'll have to deal
> with (or discard).
Yes I agree that for nodes which have connections to a lot of peers,
strongly synchronized routing tables is
harder to achieve since a small change may invalidate an entire
bucket. Real queryable filters would be much
better, but worst case scenario is we've sent an additionnal 30 Kb or
o of sync messages.
(A very naive filter would be sort + pack all short ids for example)
But we focus on nodes which are connected to a very small number of
peers, and in this particular
case it is not an unrealistic expectation.
We have built a prototype and on testnet it works fairly well. I also
found nodes which have no direct
channel betweem them but produce the same filters for 75% of the
buckets ("produce" here means
that I opened a simple gossip connection to them, got their routing
table and used it to generate filters).
Laolu wrote:
> How far back would this go? Weeks, months, years?
Since forever :)
One filter per day for all annoucements that are older than now - 1
week (modulo 144)
One filter per block for recent announcements
>
> FWIW this approach optimizes for just learning of new channels instead of
> learning of the freshest state you haven't yet seen.
I'd say it optimizes the case where you are connected to very few
peers, and are online a few times every day (?)
>
> -- Laolu
>
>
> On Mon, Feb 5, 2018 at 7:08 AM Fabrice Drouin <fabrice.drouin at acinq.fr>
> wrote:
>>
>> Hi,
>>
>> On 5 February 2018 at 14:02, Christian Decker
>> <decker.christian at gmail.com> wrote:
>> > Hi everyone
>> >
>> > The feature bit is even, meaning that it is required from the peer,
>> > since we extend the `init` message itself, and a peer that does not
>> > support this feature would be unable to parse any future extensions to
>> > the `init` message. Alternatively we could create a new
>> > `set_gossip_timestamp` message that is only sent if both endpoints
>> > support this proposal, but that could result in duplicate messages being
>> > delivered between the `init` and the `set_gossip_timestamp` message and
>> > it'd require additional messages.
>>
>> We chose the other aproach and propose to use an optional feature
>>
>> > The reason I'm using timestamp and not the blockheight in the short
>> > channel ID is that we already use the timestamp for pruning. In the
>> > blockheight based timestamp we might ignore channels that were created,
>> > then not announced or forgotten, and then later came back and are now
>> > stable.
>>
>> Just to be clear, you propose to use the timestamp of the most recent
>> channel updates to filter
>> the associated channel announcements ?
>>
>> > I hope this rather simple proposal is sufficient to fix the short-term
>> > issues we are facing with the initial sync, while we wait for a real
>> > sync protocol. It is definitely not meant to allow perfect
>> > synchronization of the topology between peers, but then again I don't
>> > believe that is strictly necessary to make the routing successful.
>> >
>> > Please let me know what you think, and I'd love to discuss Pierre's
>> > proposal as well.
>> >
>> > Cheers,
>> > Christian
>>
>> Our idea is to group channel announcements by "buckets", create a
>> filter for each bucket, exchange and use them to filter out channel
>> announcements.
>>
>> We would add a new `use_channel_announcement_filters` optional feature
>> bit (7 for example), and a new `channel_announcement_filters` message.
>>
>> When a node that supports channel announcement filters receives an
>> `init` message with the `use_channel_announcement_filters` bit set, it
>> sends back its channel filters.
>>
>> When a node that supports channel announcement filters receives
>> a`channel_announcement_filters` message, it uses it to filter channel
>> announcements (and, implicitly ,channel updates) before sending them.
>>
>> The filters we have in mind are simple:
>> - Sort announcements by short channel id
>> - Compute a marker height, which is `144 * ((now - 7 * 144) / 144)`
>> (we round to multiples of 144 to make sync easier)
>> - Group channel announcements that were created before this marker by
>> groups of 144 blocks
>> - Group channel announcements that were created after this marker by
>> groups of 1 block
>> - For each group, sort and concatenate all channel announcements short
>> channel ids and hash the result (we could use sha256, or the first 16
>> bytes of the sha256 hash)
>>
>> The new `channel_announcement_filters` would then be a list of
>> (height, hash) pairs ordered by increasing heights.
>>
>> This implies that implementation can easily sort announcements by
>> short channel id, which should not be very difficult.
>> An additional step could be to send all short channel ids for all
>> groups for which the group hash did not match. Alternatively we could
>> use smarter filters
>>
>> The use case we have in mind is mobile nodes, or more generally nodes
>> which are often offline and need to resync very often.
>>
>> Cheers,
>> Fabrice
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

2023-06-09 14:48:49

- reply

📅 Original date posted:2018-02-05
📝 Original message:
Hi,
On 5 February 2018 at 14:02, Christian Decker
<decker.christian at gmail.com> wrote:
> Hi everyone
>
> The feature bit is even, meaning that it is required from the peer,
> since we extend the `init` message itself, and a peer that does not
> support this feature would be unable to parse any future extensions to
> the `init` message. Alternatively we could create a new
> `set_gossip_timestamp` message that is only sent if both endpoints
> support this proposal, but that could result in duplicate messages being
> delivered between the `init` and the `set_gossip_timestamp` message and
> it'd require additional messages.
We chose the other aproach and propose to use an optional feature
> The reason I'm using timestamp and not the blockheight in the short
> channel ID is that we already use the timestamp for pruning. In the
> blockheight based timestamp we might ignore channels that were created,
> then not announced or forgotten, and then later came back and are now
> stable.
Just to be clear, you propose to use the timestamp of the most recent
channel updates to filter
the associated channel announcements ?
> I hope this rather simple proposal is sufficient to fix the short-term
> issues we are facing with the initial sync, while we wait for a real
> sync protocol. It is definitely not meant to allow perfect
> synchronization of the topology between peers, but then again I don't
> believe that is strictly necessary to make the routing successful.
>
> Please let me know what you think, and I'd love to discuss Pierre's
> proposal as well.
>
> Cheers,
> Christian
Our idea is to group channel announcements by "buckets", create a
filter for each bucket, exchange and use them to filter out channel
announcements.
We would add a new `use_channel_announcement_filters` optional feature
bit (7 for example), and a new `channel_announcement_filters` message.
When a node that supports channel announcement filters receives an
`init` message with the `use_channel_announcement_filters` bit set, it
sends back its channel filters.
When a node that supports channel announcement filters receives
a`channel_announcement_filters` message, it uses it to filter channel
announcements (and, implicitly ,channel updates) before sending them.
The filters we have in mind are simple:
- Sort announcements by short channel id
- Compute a marker height, which is `144 * ((now - 7 * 144) / 144)`
(we round to multiples of 144 to make sync easier)
- Group channel announcements that were created before this marker by
groups of 144 blocks
- Group channel announcements that were created after this marker by
groups of 1 block
- For each group, sort and concatenate all channel announcements short
channel ids and hash the result (we could use sha256, or the first 16
bytes of the sha256 hash)
The new `channel_announcement_filters` would then be a list of
(height, hash) pairs ordered by increasing heights.
This implies that implementation can easily sort announcements by
short channel id, which should not be very difficult.
An additional step could be to send all short channel ids for all
groups for which the group hash did not match. Alternatively we could
use smarter filters
The use case we have in mind is mobile nodes, or more generally nodes
which are often offline and need to resync very often.
Cheers,
Fabrice

2023-06-09 14:47:09

- reply

📅 Original date posted:2017-05-03
📝 Original message:
Hi Rusty,
Payment requests should also include a timestamp and an expiry date (they
could be optional tagged items but I think it makes more sense to make them
mandatory)

Thanks!
Fabrice
On 2 May 2017 at 18:11, Pierre <pm+lists at acinq.fr> wrote:
> >> On the topic of signatures: as is proposed now, a user isn't able to
> verify
> >> the validity of the signature (and thereby authenticity of the payreq
> and
> >> integrity of the contents) without first having a (direction || chanID)
> ->
> >> pubKey mapping. In my opinion, the payreqs are already so long that
> >> optimizing for size is a bit of a waste. By replacing the chanID with
> the
> >> compressed serialized public key, users will be able to immediately
> verify
> >> the signature without the use of an external mapping.
>
> As much as I pushed for using the short chanID in the onion, I too am
> a reluctant to use
> it here. In addition to laolu's arguments, I would say:
> - making the assumption that the network is well-known doesn't take
> into account the fact
> that announcements take time to propagate through the network
> (typically a few minutes with
> staggered broadcast every minute); ok it doesn't change often, but now
> we will need to worry
> about not using our most recently created/closed channels as reference.
> - we already know that we won't always be able to have a full view of
> the network in
> the future, so I feel like we should rely on it as less as possible
> - since payment requests are sent out-of-band, optimizing their size
> is maybe not as
> important as messages exchanged on the p2p network?
>
> >As you pointed out offline, we can do key recovery from the signature[1],
> >so the information is there already in fact :) The chanid is really a
> >courtesy, from this POV.
>
> That is really amazing! Why not completely ditch the chanid then? ;-)
>
> Cheers,
>
> Pierre
>
> 2017-05-02 2:40 GMT+02:00 Rusty Russell <rusty at rustcorp.com.au>:
> > Olaoluwa Osuntokun <laolu32 at gmail.com> writes:
> >> Hi Rusty,
> >>
> >> I was thinking of proposing something similar recently, but looks like
> you
> >> beat me to it!
> >>
> >> I really like the flexibility of the tag format. Over the past few
> months, I
> >> thought of quite a bit of things application developers can do by
> utilizing
> >> a tag-based payment request format in conjunction with either: the spare
> >> bytes of the onion payload or an abuse of the encrypted back errors (in
> >> combo with some onion payload bytes).
> >
> > Yes, I thought about this too, but I'm reluctant to assign those onion
> > bytes as they're a limited resource. Easy to add later, though.
> >
> >> On the topic of bech32: I'm all for piggybacking on existing emerging
> >> standards in the space, but I'm not convinced we really gain anything by
> >> using it outside of the initial prefix. The human-readable amount
> within the
> >> prefix is nice for UX as you can eyeball exactly how much one is about
> to
> >> pay/receive. However, these payment requests can get rather long, so I
> don't
> >> envision any user typing them out by hand or reading them to someone
> over
> >> the phone. As a result, I don't think we have much use for bech32
> character
> >> which has been optimized for manual-entry. Additionally, as this
> proposal
> >> includes a signature that covers the entire payreq, what's the use of
> the
> >> added checksum? Detecting 3 characters out of 1024+ is rather
> >> insignificant.
> >
> > I kind of agree, but I think the code reuse outweighs other arguments,
> > since codebases are going to have bech32 anyway.
> >
> > The minimal theoretical size we can do is 20 (payment hash160) + 64
> > (signature). We'd have to change the protocol to use hash160 instead of
> > sha256 (we already do this onchain). But even that is 135 characters,
> > which is not going to be entered by hand, so I don't think it's worth
> > it.
> >
> >> On the topic of signatures: as is proposed now, a user isn't able to
> verify
> >> the validity of the signature (and thereby authenticity of the payreq
> and
> >> integrity of the contents) without first having a (direction || chanID)
> ->
> >> pubKey mapping. In my opinion, the payreqs are already so long that
> >> optimizing for size is a bit of a waste. By replacing the chanID with
> the
> >> compressed serialized public key, users will be able to immediately
> verify
> >> the signature without the use of an external mapping.
> >
> > As you pointed out offline, we can do key recovery from the signature[1],
> > so the information is there already in fact :) The chanid is really a
> > courtesy, from this POV.
> >
> >> I think this is a good step in the right direction. However, it
> utilizes an
> >> encoding whose rationale make sense for the Bitcoin address use-case,
> but in
> >> my opinion, doesn't carry over those compelling traits to the LN payreq
> >> use-case.
> >
> > Thanks!
> > Rusty.
> > [1] You also pointed out that we can use the same technique to remove
> > node-id and bitcoin-key from the channel announcement. Which would
> > be awesome magic...
> > _______________________________________________
> > Lightning-dev mailing list
> > Lightning-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20170503/3885b9e8/attachment.html>

2023-06-09 14:46:59

- reply

📅 Original date posted:2017-01-25
📝 Original message:
On 25 January 2017 at 01:53, Rusty Russell <rusty at rustcorp.com.au> wrote:
>> - for htlcs received we don't need to wait for the htlc timeout refund to claim the funds and we don't need to watch for HTLC-success transactions.
>
> For offered htlcs we still need to handle both the HTLC-success and
> commit tx cases though, since it can race with the other side.
> Similarly with received htlcs and HTLC-timeout transactions.
That's right, I removed the last part about not watching for HTLC
success transactions from the issue description
>> ## Changes to the Offered HTLC Output script:
>>
>> The solution we propose is to use a multisig 2-of-3 with `localkey`, `remotekey` and `revocationkey` for the Offered HTLC Output script:
>> ```
>> <remotekey> OP_SWAP
>> OP_SIZE 32 OP_EQUAL
>> OP_NOTIF
>> # To me via HTLC-timeout transaction (timelocked) or to you with revocation key.
>> OP_DROP 2 OP_SWAP <localkey> <revocationkey> 3 OP_CHECKMULTISIG
>> OP_ELSE
>> # To you with preimage.
>> OP_HASH160 <ripemd-of-payment-hash> OP_EQUALVERIFY
>> OP_CHECKSIG
>> OP_ENDIF
>> ```
>>
>> This output can be spent, as before, with the remote key and payment preimage, or with the remote key and local key,
>> but it can be spent also be spent with the remote key and revocation key, with the following witness script:
>
> Clever abuse of multisig :) It can also be spent with the local and
> revocation keys, but that should never happen. OK.
Yes, because of the very clever way revocation keys are computed: you
don't know the revocation key that can be used to take all your funds
if you publish a revoked commit tx. This is one of the many
improvements in the new specs :)
>> <remotekey> OP_SWAP
>> OP_SIZE 32 OP_EQUAL
>> OP_IF
>> # To me via HTLC-success transaction.
>> OP_HASH160 <ripemd-of-payment-hash> OP_EQUALVERIFY
>> 2 OP_SWAP <localkey> 2 OP_CHECKMULTISIG
>> OP_ELSE
>> OP_SIZE 0 OP_EQUAL
>> OP_IF
>
> Would OP_SIZE OP_NOTIF work here as an optimization?
Not any more because of the "minimal IF constraints" which was added a
few months ago (see
https://github.com/bitcoin/bitcoin/commit/c72c5b1e3bd42e84465677e94aa83316ff3d9a14)
>> # To you after timeout.
>> OP_DROP <locktime> OP_CHECKLOCKTIMEVERIFY OP_DROP
>> OP_CHECKSIG
>> OP_ELSE
>> # To you if you have the revocation key
>> OP_SWAP 2 OP_SWAP <revocationkey> 2 OP_CHECKMULTISIG
>> OP_ENDIF
>> OP_ENDIF
>> ```
>>
>> This output can be spent, as before, with the payment preimage and the remote and local keys, with the remote key after a delay,
>> but it can also be spent with the remote key and revocation key, with the following witness script:
>>
>> ```
>> 0 <remote-sig> <revocation-sig>
I can be improved like this:
<remotePubkey> OP_SWAP
OP_SIZE 32 OP_EQUAL
OP_IF
OP_HASH160 paymentHash) <ripemd-of-payment-hash> OP_EQUALVERIFY
OP_2 OP_SWAP <localKey> OP_2 OP_CHECKMULTISIG
OP_ELSE
OP_SIZE OP_0 OP_EQUAL
OP_IF
OP_DROP <lockTime> OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG
OP_ELSE
OP_SWAP OP_DROP <revocationPubKey> OP_CHECKSIG
OP_ENDIF
OP_ENDIF
It can now be spent with: <revocation-sig>
Cheers,
Fabrice

2023-06-09 14:46:10

- reply

📅 Original date posted:2016-04-28
📝 Original message:
Hi!
On 26 April 2016 at 04:21, Rusty Russell <rusty at rustcorp.com.au> wrote:
> Pierre <pm+lists at acinq.fr> writes:
>> Hello,
>
> Hi Pierre!
>
> I'm glad I'm not the only one who had trouble with this. I just
> thought I was being dumb! Concurrent updates are conceptually harder
> than the previous synchronous model, unfortunately.
>
>> I am trying to understand how we should handle concurrent signatures,
>> and I am wondering if we couldn't use an ordering of some sort to
>> resolve conflicts when they occur, for example by simply comparing
>> signatures. If two nodes send each other a signature at the same time,
>> they could agree that the one that sent the "greatest" signature has
>> to immediately resend a new signature including all pending changes.
>> This new signature would encompass all the changes both parties wanted
>> in the first place so everybody would be happy.
>
> I originally had an alternating priority scheme which worked, but I don't
> think it's necessary any more.
>
> This diagram is a simplification. Each node tracks two commitment
> states: its own and the state of the other side. This is because they
> can run independently.
>
> The rules are simple (though the results might not be!):
>
> 1) Nodes must process packets in order.
> 2) When you send something, update their state.
> 3) When you ack something, update their state.
> 4) When you receive something, update your own state.
> 5) When you receive an ack for something, update your own state.
>
> When you sign a commit tx, you sign their state at the time (this makes
> sense: you're signing their commit tx, not yours).
>
> So, when a node sends an ADD HTLC, it modifies the other side's state.
> It only modifies its own state when it receives an ack covering that ADD
> HTLC.
>
> The ADD HTLC receiver modifies its own state, and modifies the other
> side's state when it sends the next ack (in practice, we do that
> immediately because it doesn't matter, but diagram below does it
> strictly).
>
> Thus, in your case:
>
> NODE A NODE B
>
> Committed: [] Committed: []
> States: [] [X] States: [] [Y]
> ADD HTLC X ---- ---- ADD HTLC Y
> \ /
> \ /
> Committed: [] \ / Committed: []
> States: [] [X] \/ States: [] [Y]
> SIG A0 --- /\ --- SIG B0
> \ / \ /
> \/ \/
> /\ /\
> <--- \ / --->
> Committed: [] \/ Committed: []
> States: [Y] [X] /\ States: [X] [Y]
> / \
> / \
> <---- ----->
> Committed: [Y] Committed: [X]
> States: [Y] [X] States: [X] [Y]
>
> Now, at this point both nodes have outstanding changes, so they can send
> another SIG (which acks the received changes, thus modifying the other
> state):
>
> Committed: [Y] Committed: [X]
> States: [Y] [X Y] States: [X] [X Y]
> SIG A1 --- --- SIG B1
> \ /
> \ /
> \ /
> \ /
> \/
> /\
> / \
> / \
> <---- ----->
> PROCESS ACK:
> Committed: [Y] Committed: [X]
> States: [X Y] [X Y] States: [X Y] [X Y]
> PROCESS SIG:
> Committed: [X Y] Committed: [X Y]
> States: [X Y] [X Y] States: [X Y] [X Y]
>
What if instead of immediately sending a new SIG, A and B then decide
to send each
other a new HTLC? Could we get stuck in an infinite loop where A and B
never converge on a
commitment tx?
Or should it be specified that the only valid answer to a signature is
either a signature (if there
are outstanding changes) or a revocation ?
Cheers,
Fabrice

2023-06-09 14:46:05

- reply

📅 Original date posted:2016-04-01
📝 Original message:
Hello,
We've thought about it some more and it seems now that htlc ids are
indeed not enough and we do have to take the acknowledge field into
account in some cases anyway. Consider the following scenario:
A sends ADD HTLC X, ADD HTLC Y, ADD HTLC Z
B sends FAIL Y
A has not yet received this last message and sends SIG Z
B receives SIG Z which includes (X,Y,Z) and won't match expected
signature (X,Z). B has no way to know whether A did receive the "FAIL
Y" message or not without checking the 'acknowledge' field (as
mentioned by Rusty), and might decide that SIG Z is not valid and
close the channel, when it could just ignore it and keep it open.
Cheers,
Fabrice

2023-06-09 14:45:51

- reply

📅 Original date posted:2016-03-07
📝 Original message:
Ok, got my answer from the thread you started on deterministic R values
and which I had missed :)
On 7 March 2016 at 20:09, Fabrice Drouin <fabrice.drouin at acinq.fr> wrote:
> Hi,
> I may have misunderstood something, but with this scheme instead of R
> + shachain/elkrem, then how do nodes react when old commit tx are
> published ? It seems that they would have to store lots of signatures
> ?
>
>
> On 7 March 2016 at 08:28, Nicolas Dorier <nicolas.dorier at gmail.com> wrote:
>> I managed to adapt the payment channel script to use less space.
>>
>> This version is winning around 32 bytes in the scriptpubkey (for the R
>> value) as well as 70 bytes in the signature when Alice close the channel.
>>
>> Alice closing the channel:
>> http://n.bitcoin.ninja/checkscript?savedScript=51225750-f245-45b5-a86c-6ca1e87dcafb
>>
>> Bob using revocation:
>> http://n.bitcoin.ninja/checkscript?savedScript=c4d7ebaa-5a79-4c03-ab55-c499854f1e94
>>
>> This amount to 100 bytes saved between the anchor transaction + commitment
>> broadcasted.
>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>

2023-06-09 14:45:50

- reply

📅 Original date posted:2016-03-07
📝 Original message:
Hi,
I may have misunderstood something, but with this scheme instead of R
+ shachain/elkrem, then how do nodes react when old commit tx are
published ? It seems that they would have to store lots of signatures
?
On 7 March 2016 at 08:28, Nicolas Dorier <nicolas.dorier at gmail.com> wrote:
> I managed to adapt the payment channel script to use less space.
>
> This version is winning around 32 bytes in the scriptpubkey (for the R
> value) as well as 70 bytes in the signature when Alice close the channel.
>
> Alice closing the channel:
> http://n.bitcoin.ninja/checkscript?savedScript=51225750-f245-45b5-a86c-6ca1e87dcafb
>
> Bob using revocation:
> http://n.bitcoin.ninja/checkscript?savedScript=c4d7ebaa-5a79-4c03-ab55-c499854f1e94
>
> This amount to 100 bytes saved between the anchor transaction + commitment
> broadcasted.
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>