[Lightning-dev] Minisketch and lightning gossip

[Rusty Russell]

Hi all,

In case you're bored with the limited range of improvements
going into the 1.1 spec, you might like to ruminate on:

  https://github.com/sipa/minisketch/blob/master/README.md

It's a library for efficient summaries of data, such as bitcoin
transaction gossip.  It has an implementation sweet-spot at 64-bits,
which almost works well for our gossip messages.  I've a straw-man
protocol below.

===
1. type: 260 (`gossip_sync`) (`option_gossip_sync`)
2. data:
* [`32`:`chain_hash`]
* [`32`:`latest_block_hash`]
* [`minisketch_len`:`minisketch`]

The `latest_block_hash` is because the whole sync is less reliable if
this differs between nodes, so a node may choose to wait, or adapt
accordingly if the other node is behind.

Because there is some overhead in maintaining the minisketch, it'd be
nice if we can have global agreement on the format so each peer need
only maintain one (i.e. no seed, no changing encodings depending on
block height, etc).

Fitting everything we need into 64 bits is possible, with various
degrees of ugliness; I've proposed one here:

We currently use a short_channel_id which has 3-byte block height,
3-byte txindex, 2-byte output index.  The biggest win is to combine
block height & txindex into a "txnumber since block 500,000", which only
needs about 27 bits per year; 40 bits for this number is sufficient for
the forseeable future.  2 bits for type, 1 for channel direction,
leaving 21 bits for output number and timestamp.

We can encode output number as N ones followed by a zero followed by
N*2+1 bits (commonly, this means 2 bits, but future mixers may make this
much larger).  The remaining bits are used as the lower bits of the
timestamp[1].

A node announcement is encoded by using the scid of the oldest channel
associated with the node, and the direction bit.

Using this direct encoding (rather than a hash of values) allows us to
immediately use an INV-style query, or maybe send automatically the
stuff the peer doesn't have.

The required size of the minisketch we send depends on the number of
differences with our peer.  We can use some minimum value (maybe based
on past gossip rates?), and add the number of changes we've received
since last time, increasing if we failed to reconstruct a previous one.

There doesn't need to be consensus between peers on the minisketch size
though, since truncated minisketches regrow into whole ones when tossed
back into the ocean[3].

Cheers,
Rusty.
[1]  You're supposed to refresh gossip every week, 17 bits should
be sufficient.   And since the originator controls timestamps
they can mitigate collisions themselves.[2]
[2] I wish I'd insisted we use block numbers for timestamps though
[3] I may have misunderstood this part, but it's basically magic.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] Fulgurite: ideas for making a more flexible Lightning Network protocol

[Trey Del Bonis]

Hello ZmnSCPxj,

>In any case, it is certainly possible for the spec to simply specify allowing 
>some multiparty system with unspecified link-level behavior, but with 
>specified global-level behavior (i.e. contains some channels that can be 
>routed through, but the spec will not define how the multiparty system 
>communicates between the nodes in order to coordinate updates to the system).

Maybe discussion on this should be left for the standards meeting in a
few weeks.

>It is simply the option that the Fulgurite user has.
>That is, balance the cost of transmitting a large number of DLC signatures, 
>vs. the benefit of earning a little money for routing.

Oh I see what you're saying now.  Misunderstanding on my part there.

I think that these kinds of decisions should be communicated when
setting up a channel.  Perhaps during channel setup peers should
specify how they expect to use a channel, like "should we do
pseudo-BDW or are we ok with doing Layer-1 payments even in a
multiparty scenario?".

>Perhaps a new `channel_balance_update` gossip message that is signed by both 
>sides instead.

>But the fact that we do not *currently* publish such, and yet payments in 
>current LN are reasonably successful, suggests that it might not be at all 
>necessary.

I would agree with both statements.

>This greatly increases bandwidth use for gossip, though.
>In addition, most of the time the information will not be useful, since it is 
>not likely I will need the accurate information about this channel state if I 
>never have to make a payment that will route through that channel.
>Current implementations already retry routes, and work well enough without 
>this information.
>Various mini-enhancements like non-binding short-channel-id in onion hops, as 
>well as the potential to reuse rendezvous routing for rerouting via 
>alternative routes (modulo reservations Christian Decker has with actually 
>doing the math) can help improve payment success even with no accurate 
>knowledge of the channel state.

Perhaps clients should try to talk to each node in the route and ask
if they would be willing to or are able to relay a payment (or in the
case of AMP, how much they can relay of the total).  Of course they
could lie (say they can but then refuse), but it would at least inform
about peers that are genuinely dead.  I'm not sure if this has been
throughly discussed before or not.

~~~

Some of this is straying from Fulgurite itself and is relatively
inconsequential.  Should this be moved to another thread or IRC?

- Trey Del Bonis

On Mon, Dec 10, 2018 at 10:56 PM ZmnSCPxj  wrote:
>
> Good morning Trey,
>
> >
> > Would it really be masquerading though? The standard shouldn't care
> > about how a multiparty channel is implemented, only the effective
> > balance between each party in each subchannel. And that's regardless
> > of if it's with Fulgurite being nested in BDW as previously mentioned,
> > or with multiparty Fulgurite acting as though it were just BDW.
>
> I suppose it would depend on how we end up defining words.
> In any case, it is certainly possible for the spec to simply specify allowing 
> some multiparty system with unspecified link-level behavior, but with 
> specified global-level behavior (i.e. contains some channels that can be 
> routed through, but the spec will not define how the multiparty system 
> communicates between the nodes in order to coordinate updates to the system).
>
> >
> > > LN cannot support lying on gossip.
> > > The issue is that if lying were possible, then it would be possible to 
> > > just give fake channels that do not exist at all (rather than being an 
> > > alias to some other channel) and which cannot actually route payments.
> > > By requiring that funds be visibly locked onchain, we ensure that lying 
> > > attacks are costly and that attackers have the option of behaving 
> > > honestly (performing forwarding requests) and get compensated for the 
> > > opportunity cost, or swallowing the opportunity cost.
> >
> > I'm not saying lie altogether, you still have to have the funds locked
> > on-chain. Just say "here's this (layer 1) channel, we can route x
> > msat through it" and leave it at that, and have peers verify that x is
> > less than or equal to what the on-chain txo says it should have. And
> > apparently that's already in BOLT 1.1 so that should be doable soon.
> > You still have the same security guarantees (with regard to verifying
> > funds actually seem to exist) with BDW as you would with Fulgurite
> > subchannels as external users can't verify that there's actually funds
> > in a channel if there's no tx spending into it on-chain, which still
> > happens with both systems as I understand it.
>
> Yes.
>
> > And I'd say that it is (somewhat) possible to lie in gossip. If
> > parties in a BDW channel collude they could absolutely produce
> > announcements that say there's much more balance in subchannels than
> > there actually is, or vice-versa. But