Re: [Lightning-dev] Towards a gridlike Lightning Network

[Benjamin Mord]

Good afternoon ZmnSCPxj,

"I do not see a bloom filter?"

Well, if you look at it kinda sideways, you are using a bloom filter in
your March 23rd proposal. As originally defined, I think the "false
positives" in bloom filtering were the unfortunate cost of performance. In
BIP 37, the false positives become desirable, although still are 'false' in
that their only function is to serve as red herrings. But (omitting i for
clarity), your proposal takes BIP 37's spin on bloom filters one step
further to actually take the 'false positives' as the very definition of
our desired set, since what you are "searching for" is just your own public
key, which ends up being the least interesting result within that set.

" Regarding 24 vs 23, the condition for 23 allows a 3 members of a 5-member
neighborhood to think they form a single 3-member neighborhood, while the
remaining 2 members think they are in a 5-member neighborhood that includes
the other 3 members who have formed a 3-member neighborhood."

Oh, I see. But the reason that occurs is because different nodes are
considering different numbers of high-order bits. If everyone used the same
number of high-order bits, then it would become an equivalence
relationship, with which we can partition the network. This is because
then, a=b, would imply b=a, and also a=b and b=c, would imply a=c.
https://en.wikipedia.org/wiki/Equivalence_relation#Partition

I think algorithm from March 24 is broken actually, on second look, but I
understand now what you are trying to achieve. You want to allow local
judgement over best local cell size, and yet somehow end up with precise
uniform agreement on who is in which cells, because cycles require such
precision. But if you throw in that the network is dynamic, knowledge is
imperfect, and malicious behavior may occur, then I think strict
equivalence relationships and cycles become brittle. Perhaps we should
generalize the equivalence relationship into a distance function, so that
we can start thinking of this as a metric space which we want to fill with
some sort of structure. Perhaps then we can design efficient yet robustly
"fuzzy" structures. Perhaps we want a fuzzy fractal of some sort. Hmm...

"Intermediate nodes already know two hops?  The incoming and outgoing hop?
Or do you need more information?"

Yes, nodes would need to know one hope more, since the idea would be to
attract competition to the high-usage yet high-fee links.

Thanks,
Ben


On Thu, Apr 19, 2018 at 11:24 PM, ZmnSCPxj  wrote:

> Good morning Benjamin,
>
>
> I think there are two distinct concepts here. The first is the
> identification of a 'neighborhood', and the second is the establishment of
> an order within that neighborhood for purpose of cycle formation.
>
> Your use of bloom filters to define a neighborhood, is I think the most
> valuable contribution. Formation of neighborhoods with high connectivity,
> with sparse but redundant connections among these neighborhoods, does seem
> like an economically efficient approach to maintaining useful competition
> and redundancy. If there are any graph theorists or category theorists on
> the list, perhaps they could offer some formal validation or optimization.
> For this, I prefer your March 23 proposal over March 24, I'm curious what
> improvement is intended in March 24 vs 23?
>
>
> I do not see a bloom filter? But then I am not a mathematician so it is
> possible I fail to see how the Bloom filter arises from the algorithm I
> described.
>
> Regarding 24 vs 23, the condition for 23 allows a 3 members of a 5-member
> neighborhood to think they form a single 3-member neighborhood, while the
> remaining 2 members think they are in a 5-member neighborhood that includes
> the other 3 members who have formed a 3-member neighborhood.
>
>
> The emergent definition and maintenance of a unique ordering for cycle
> establishment within a neighborhood is, I think, a much more ambitious
> undertaking. I'm not sure how we efficiently make that robust in a dynamic
> context, except perhaps with interactive coordination among the members
> operating off something other than just static global data. Otherwise
> different members would have different ideas about cycle order, depending
> on when they first joined. I also don't see how cycles recover when someone
> leaves.
>
> As people come and go, cycles will break. As the lightning network grows
> overall, neighborhoods identified by one setting of the bloom filter will
> become undesirably large. Perhaps a less ambitious but more robust
> heuristic would be one where probability of establishing a channel is
> proportional to the number of bits in common in the pubkey hash, normalized
> by the number of nodes currently observed?
>
>
> I believe that is what the algorithm already does? It dynamically sizes
> neighborhoods to be small, with high probability of neighborhoods to be
> 3->5 members.
>
> This heuristic would automatically adjust granularity over time as
> lightning me

Re: [Lightning-dev] Towards a gridlike Lightning Network

[ZmnSCPxj via Lightning-dev]

Good morning Benjamin,

> I think there are two distinct concepts here. The first is the identification 
> of a 'neighborhood', and the second is the establishment of an order within 
> that neighborhood for purpose of cycle formation.
>
> Your use of bloom filters to define a neighborhood, is I think the most 
> valuable contribution. Formation of neighborhoods with high connectivity, 
> with sparse but redundant connections among these neighborhoods, does seem 
> like an economically efficient approach to maintaining useful competition and 
> redundancy. If there are any graph theorists or category theorists on the 
> list, perhaps they could offer some formal validation or optimization. For 
> this, I prefer your March 23 proposal over March 24, I'm curious what 
> improvement is intended in March 24 vs 23?

I do not see a bloom filter? But then I am not a mathematician so it is 
possible I fail to see how the Bloom filter arises from the algorithm I 
described.

Regarding 24 vs 23, the condition for 23 allows a 3 members of a 5-member 
neighborhood to think they form a single 3-member neighborhood, while the 
remaining 2 members think they are in a 5-member neighborhood that includes the 
other 3 members who have formed a 3-member neighborhood.

> The emergent definition and maintenance of a unique ordering for cycle 
> establishment within a neighborhood is, I think, a much more ambitious 
> undertaking. I'm not sure how we efficiently make that robust in a dynamic 
> context, except perhaps with interactive coordination among the members 
> operating off something other than just static global data. Otherwise 
> different members would have different ideas about cycle order, depending on 
> when they first joined. I also don't see how cycles recover when someone 
> leaves.
>
> As people come and go, cycles will break. As the lightning network grows 
> overall, neighborhoods identified by one setting of the bloom filter will 
> become undesirably large. Perhaps a less ambitious but more robust heuristic 
> would be one where probability of establishing a channel is proportional to 
> the number of bits in common in the pubkey hash, normalized by the number of 
> nodes currently observed?

I believe that is what the algorithm already does? It dynamically sizes 
neighborhoods to be small, with high probability of neighborhoods to be 3->5 
members.

> This heuristic would automatically adjust granularity over time as lightning 
> membership grows and shrinks. Nodes could periodically reevaluate their 
> channel allocations as the overall network grows or shrinks.

The algorithm does not consider what happens when we have a cycle already 
existing, and a new member joins or an existing one wishes to leave.  There is 
no way to inform this.  My expectation is that people will just close channels 
that they no longer  find useful; this makes funds available onchain.  Then a 
process notices there are onchain funds, and calls this algorithm to get a 
proposed channel; this adapts to whatever the topology is right now.

It is not clear when we should close channels.  For one, gossip requires that a 
node first open a channel to somebody, before its existence is acknowledged and 
gossiped across the network: this is intended to prevent spammers from spinning 
up nodes without actually intending to join the network.  Similarly, to leave 
the network, we assume that nodes will at least get all their channels closed: 
channel closure is an onchain event visible to everyone monitoring the the 
blockchain (which is what all LN nodes SHOULD do), and once all channels of a 
node have closed, we MAY drop them from the network view (c-lightning 
implements this, but I do not know if other implementations do).

So at least for *leaving* LN permanently, the leaving node SHOULD close all its 
channels (or at least their peers SHOULD close it for them in unilateral closes 
if the peer just does not respond at all anymore).  This updates the network 
view of everybody (assuming they follow the recommendation that they MAY drop 
nodes from the network view, if that node has all its channels closed).  The 
closing will also put the channel funds onchain, and presumably the autopilots 
of its neighbors will notice the onchain funds, calls the algorithm to get a 
peer to channel to, which computes (hopefully) using the updated network view 
that has the leaving node removed already (this may not be true: the leaving 
node might not be able to close all channels simultaneously, and may misbehave 
and expect its neighbors to close the channels for it), and adapts correctly to 
the node leaving the network.

However for a new node entering the network, there is problem.  This requires 
existing nodes to close existing channels and open new ones to the new node: as 
this costs onchain fees, there is no real incentive for them to do so.  I can 
only fall back on the informal argument: that people will at first experiment 
with the L

Re: [Lightning-dev] Towards a gridlike Lightning Network

[Benjamin Mord]

Hello ZmnSCPxj,

I think there are two distinct concepts here. The first is the
identification of a 'neighborhood', and the second is the establishment of
an order within that neighborhood for purpose of cycle formation.

Your use of bloom filters to define a neighborhood, is I think the most
valuable contribution. Formation of neighborhoods with high connectivity,
with sparse but redundant connections among these neighborhoods, does seem
like an economically efficient approach to maintaining useful competition
and redundancy. If there are any graph theorists or category theorists on
the list, perhaps they could offer some formal validation or optimization.
For this, I prefer your March 23 proposal over March 24, I'm curious what
improvement is intended in March 24 vs 23?

The emergent definition and maintenance of a unique ordering for cycle
establishment within a neighborhood is, I think, a much more ambitious
undertaking. I'm not sure how we efficiently make that robust in a dynamic
context, except perhaps with interactive coordination among the members
operating off something other than just static global data. Otherwise
different members would have different ideas about cycle order, depending
on when they first joined. I also don't see how cycles recover when someone
leaves.

As people come and go, cycles will break. As the lightning network grows
overall, neighborhoods identified by one setting of the bloom filter will
become undesirably large. Perhaps a less ambitious but more robust
heuristic would be one where probability of establishing a channel is
proportional to the number of bits in common in the pubkey hash, normalized
by the number of nodes currently observed? This heuristic would
automatically adjust granularity over time as lightning membership grows
and shrinks. Nodes could periodically reevaluate their channel allocations
as the overall network grows or shrinks.

Were it not for the privacy goals, dynamic optimization based on actual
usage would be possible. Nodes could track the routes of payments that flow
through their channels and could spot fees that seem both large and
popular, and could use this information to identify under-served nodes to
which a direct channel might be in order. If we allowed nodes to see two
hops of the route instead of just the one, then such optimization would
become possible, although this compromise would require longer minimum
routes for a given level of privacy.

Thanks,
Ben


On Wed, Apr 18, 2018 at 10:04 PM, ZmnSCPxj  wrote:

> Good morning Benjamin,
>
> Rusty simulated an older version of my idea here; C code near the end of
> the message: https://lists.ozlabs.org/pipermail/c-lightning/2018-
> April/29.html
>
> However this has a bug: I specify that:
>
> >If the candidate already has a channel with us, or has no address info and
> >cannot be found by DNS seed or so on, or cannot be contacted, or refuses
> >incoming channels or some other error, then increment i and try finding 
> >again.
>
> The code there does not implement the check "if the candidate has a
> channel with us", leading to smaller reachability since nodes who could
> afford to create multiple channels will create multiple channels to the
> same peer in the simulation.
>
> A naive analysis suggests that if only one node in the entire network uses
> the algorithm I described, it should be indistinguishable from a random
> connection policy, so a naive analysis suggests that something has gone
> wrong if the reachability of this algorithm is significantly less than the
> reachability of a random connection algorithm.  The simulation also does
> not consider that existing nodes may break old channels or make new
> channels themselves; it is not certain how often that happens on the real
> network.
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail  Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On April 19, 2018 7:56 AM, Benjamin Mord  wrote:
>
>
> Elegant idea.
>
> Is there a simulation platform yet for experimenting with ideas such as
> this? I imagine it may sometimes be useful to empirically test aggregate
> effects of different routing heuristics, however naive or artificial the
> underlying assumptions may need to be.
>
> Is there an API, perhaps implementation agnostic, to separate such
> strategies from the protocol itself?
>
> Is there a place yet to specify such heuristics where tight coordination
> on details are of mutual benefit, such as a bolt?
>
> On Sat, Mar 24, 2018, 8:08 AM ZmnSCPxj via Lightning-dev <
> lightning-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning list,
>>
>> I have decided on a better termination condition for searching for a
>> cyclic superhub.  I re-describe below the algorithm:
>>
>> Start with `i` = 0 and a set of known nodes, including our own node.
>>
>> Iterate over `i`:
>>
>> - Compute hash = H(i || pubkey) for each node. H = RIPEMD160 . SHA256,
>> serialize `i` as a big-endian 32-bit number.  Also compute 

Re: [Lightning-dev] Towards a gridlike Lightning Network

[ZmnSCPxj via Lightning-dev]

Good morning Benjamin,

Rusty simulated an older version of my idea here; C code near the end of the 
message: https://lists.ozlabs.org/pipermail/c-lightning/2018-April/29.html

However this has a bug: I specify that:

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

The code there does not implement the check "if the candidate has a channel 
with us", leading to smaller reachability since nodes who could afford to 
create multiple channels will create multiple channels to the same peer in the 
simulation.

A naive analysis suggests that if only one node in the entire network uses the 
algorithm I described, it should be indistinguishable from a random connection 
policy, so a naive analysis suggests that something has gone wrong if the 
reachability of this algorithm is significantly less than the reachability of a 
random connection algorithm.  The simulation also does not consider that 
existing nodes may break old channels or make new channels themselves; it is 
not certain how often that happens on the real network.

Regards,
ZmnSCPxj

Sent with [ProtonMail](https://protonmail.com) Secure Email.

‐‐‐ Original Message ‐‐‐
On April 19, 2018 7:56 AM, Benjamin Mord  wrote:

> Elegant idea.
>
> Is there a simulation platform yet for experimenting with ideas such as this? 
> I imagine it may sometimes be useful to empirically test aggregate effects of 
> different routing heuristics, however naive or artificial the underlying 
> assumptions may need to be.
>
> Is there an API, perhaps implementation agnostic, to separate such strategies 
> from the protocol itself?
>
> Is there a place yet to specify such heuristics where tight coordination on 
> details are of mutual benefit, such as a bolt?
>
> On Sat, Mar 24, 2018, 8:08 AM ZmnSCPxj via Lightning-dev 
>  wrote:
>
>> Good morning list,
>>
>> I have decided on a better termination condition for searching for a cyclic 
>> superhub.  I re-describe below the algorithm:
>>
>> Start with `i` = 0 and a set of known nodes, including our own node.
>>
>> Iterate over `i`:
>>
>> - Compute hash = H(i || pubkey) for each node. H = RIPEMD160 . SHA256, 
>> serialize `i` as a big-endian 32-bit number.  Also compute our_hash = H(i || 
>> our_pubkey) for our self.  Put this in a working set.
>>
>> - Iterate over bits (start with the 7th bit (128) of the first byte):
>>
>> - - Split the working set into two sets, the matching set and the 
>> non-matching set, where the bit in the hash matches the bit in our_hash.
>>
>> - - If the non-matching set is empty, skip to the next bit.
>>
>> - - If the matching set is 1 or 2 members, or the non-matching set is 1 or 2 
>> members, merge the two sets together into the working set and exit this 
>> loop: we have found a cyclic superhub.
>>
>> - - else set the working set to the matching set.
>>
>> - Sort the set according to the hash (treat the hash as a 160-bit big-endian 
>> number).
>>
>> - We should open a channel to the node after us in the sorted list; if we 
>> are the last, wrap around to the first node in the list.
>>
>> Regards,
>> ZmnSCPxj
>>
>> Sent with [ProtonMail](https://protonmail.com) Secure Email.
>>
>> ‐‐‐ Original Message ‐‐‐
>> On March 23, 2018 11:29 PM, ZmnSCPxj  wrote:
>>
>>> Good morning list,
>>>
>>> Igor Cota has started implementing my idea: 
>>> https://github.com/icota/presto/commit/3311785e660d840f0ac8f2e333d0f0097aec980e
>>>
>>> This forced me to actually start thinking more deeply about the algorithm I 
>>> gave.
>>>
>>> 1.  We should use a well-used hash algorithm, such as RIPEMD160(SHA256(x))
>>> 2.  We should specify the size of `i` - 32-bits, 4 bytes - and indicate its 
>>> endianness.  Let us use big-endian, as is typical for the rest of Lightning 
>>> and for network order.
>>> 3.  My original algorithm had a significant probability of diverging.  So I 
>>> respecify the termination condition later.
>>> 4.  Our own node should be part of the original working set.
>>> 5.  In the decimation loop, start with the highest bit.  This is the 
>>> 7-index bit (1 << 7) of the first byte in the 20-byte hash (we treat the 
>>> hash as a big-endian 160-bit number).
>>>
>>> The modified termination condition for the decimation loop is below:
>>>
>>> * If the working set is 7 nodes or more, decimate (i.e. match the next bit 
>>> in the hashes and remove those that do not match our own hash in that bit.).
>>> * If the working set is 3 to 6 nodes, stop, that is now the members of the 
>>> superhub and we then sort them by hash and decide our position in the 
>>> superhub (who will channel to us and who we will channel to).
>>> * If the working set is 1 or 2 nodes, fail to form a superhub.  Increment 
>>> `i` and restart.
>>>
>>> Regards,
>>> ZmnSCPxj
>>>
>>> Sent with [ProtonMail](https://protonmail.com) Secure Em

Re: [Lightning-dev] Towards a gridlike Lightning Network

[Benjamin Mord]

Elegant idea.

Is there a simulation platform yet for experimenting with ideas such as
this? I imagine it may sometimes be useful to empirically test aggregate
effects of different routing heuristics, however naive or artificial the
underlying assumptions may need to be.

Is there an API, perhaps implementation agnostic, to separate such
strategies from the protocol itself?

Is there a place yet to specify such heuristics where tight coordination on
details are of mutual benefit, such as a bolt?

On Sat, Mar 24, 2018, 8:08 AM ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Good morning list,
>
> I have decided on a better termination condition for searching for a
> cyclic superhub.  I re-describe below the algorithm:
>
> Start with `i` = 0 and a set of known nodes, including our own node.
>
> Iterate over `i`:
>
> - Compute hash = H(i || pubkey) for each node. H = RIPEMD160 . SHA256,
> serialize `i` as a big-endian 32-bit number.  Also compute our_hash = H(i
> || our_pubkey) for our self.  Put this in a working set.
>
> - Iterate over bits (start with the 7th bit (128) of the first byte):
>
> - - Split the working set into two sets, the matching set and the
> non-matching set, where the bit in the hash matches the bit in our_hash.
>
> - - If the non-matching set is empty, skip to the next bit.
>
> - - If the matching set is 1 or 2 members, or the non-matching set is 1 or
> 2 members, merge the two sets together into the working set and exit this
> loop: we have found a cyclic superhub.
>
> - - else set the working set to the matching set.
>
> - Sort the set according to the hash (treat the hash as a 160-bit
> big-endian number).
>
> - We should open a channel to the node after us in the sorted list; if we
> are the last, wrap around to the first node in the list.
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail  Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On March 23, 2018 11:29 PM, ZmnSCPxj  wrote:
>
> Good morning list,
>
> Igor Cota has started implementing my idea:
> https://github.com/icota/presto/commit/3311785e660d840f0ac8f2e333d0f0097aec980e
>
> This forced me to actually start thinking more deeply about the algorithm
> I gave.
>
> 1.  We should use a well-used hash algorithm, such as RIPEMD160(SHA256(x))
> 2.  We should specify the size of `i` - 32-bits, 4 bytes - and indicate
> its endianness.  Let us use big-endian, as is typical for the rest of
> Lightning and for network order.
> 3.  My original algorithm had a significant probability of diverging.  So
> I respecify the termination condition later.
> 4.  Our own node should be part of the original working set.
> 5.  In the decimation loop, start with the highest bit.  This is the
> 7-index bit (1 << 7) of the first byte in the 20-byte hash (we treat the
> hash as a big-endian 160-bit number).
>
> The modified termination condition for the decimation loop is below:
>
> * If the working set is 7 nodes or more, decimate (i.e. match the next bit
> in the hashes and remove those that do not match our own hash in that bit.).
> * If the working set is 3 to 6 nodes, stop, that is now the members of the
> superhub and we then sort them by hash and decide our position in the
> superhub (who will channel to us and who we will channel to).
> * If the working set is 1 or 2 nodes, fail to form a superhub.  Increment
> `i` and restart.
>
>
> Regards,
> ZmnSCPxj
>
>
> Sent with ProtonMail  Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On March 20, 2018 11:19 AM, ZmnSCPxj via Lightning-dev <
> lightning-dev@lists.linuxfoundation.org> wrote:
>
> Good morning list,
>
> As my award-winning and supremely notable and
> talked-about-by-the-man-on-the-street article "Cyclic Superhubs as Solution
> Towards Reasonable Lightning Network Topography" points out, cycles are a
> good way to organize the LN in order to allow easier accessibility to the
> network for all participants of all kinds.
>
> An issue here is the need for coordination in order to set up cyclic
> superhubs.  A node acting by itself cannot form cyclic superhubs.
>
> However, one can consider that coordination is needed only to identify
> peers with which one forms superhubs.  But we already have a system that
> identifies peers: the node gossip.
>
> So let us assume: All nodes have similar-enough views of the
> publicly-visible peers on the node graph, as built by node gossip.
>
> I now present an algorithm, which given a set of nodes extracted from node
> gossip, returns a peer to try connecting and funding a channel to.
>
> --
>
> First, start with a 32-bit number i = 0.
>
> For each node, get hash = H(i || pubkey), where H is some standard hash
> algorithm, and pubkey is the public key of the node.  Also get our_hash =
> H(i || our_pubkey)
>
> Perform successive filtering.  While the set is larger than 2 nodes,
> successively compare high bits.  If the highest bit of hash does not match
> the highest bi

Re: [Lightning-dev] Towards a gridlike Lightning Network

[ZmnSCPxj via Lightning-dev]

Good morning list,

I have decided on a better termination condition for searching for a cyclic 
superhub.  I re-describe below the algorithm:

Start with `i` = 0 and a set of known nodes, including our own node.

Iterate over `i`:

- Compute hash = H(i || pubkey) for each node. H = RIPEMD160 . SHA256, 
serialize `i` as a big-endian 32-bit number.  Also compute our_hash = H(i || 
our_pubkey) for our self.  Put this in a working set.

- Iterate over bits (start with the 7th bit (128) of the first byte):

- - Split the working set into two sets, the matching set and the non-matching 
set, where the bit in the hash matches the bit in our_hash.

- - If the non-matching set is empty, skip to the next bit.

- - If the matching set is 1 or 2 members, or the non-matching set is 1 or 2 
members, merge the two sets together into the working set and exit this loop: 
we have found a cyclic superhub.

- - else set the working set to the matching set.

- Sort the set according to the hash (treat the hash as a 160-bit big-endian 
number).

- We should open a channel to the node after us in the sorted list; if we are 
the last, wrap around to the first node in the list.

Regards,
ZmnSCPxj

Sent with [ProtonMail](https://protonmail.com) Secure Email.

‐‐‐ Original Message ‐‐‐
On March 23, 2018 11:29 PM, ZmnSCPxj  wrote:

> Good morning list,
>
> Igor Cota has started implementing my idea: 
> https://github.com/icota/presto/commit/3311785e660d840f0ac8f2e333d0f0097aec980e
>
> This forced me to actually start thinking more deeply about the algorithm I 
> gave.
>
> 1.  We should use a well-used hash algorithm, such as RIPEMD160(SHA256(x))
> 2.  We should specify the size of `i` - 32-bits, 4 bytes - and indicate its 
> endianness.  Let us use big-endian, as is typical for the rest of Lightning 
> and for network order.
> 3.  My original algorithm had a significant probability of diverging.  So I 
> respecify the termination condition later.
> 4.  Our own node should be part of the original working set.
> 5.  In the decimation loop, start with the highest bit.  This is the 7-index 
> bit (1 << 7) of the first byte in the 20-byte hash (we treat the hash as a 
> big-endian 160-bit number).
>
> The modified termination condition for the decimation loop is below:
>
> * If the working set is 7 nodes or more, decimate (i.e. match the next bit in 
> the hashes and remove those that do not match our own hash in that bit.).
> * If the working set is 3 to 6 nodes, stop, that is now the members of the 
> superhub and we then sort them by hash and decide our position in the 
> superhub (who will channel to us and who we will channel to).
> * If the working set is 1 or 2 nodes, fail to form a superhub.  Increment `i` 
> and restart.
>
> Regards,
> ZmnSCPxj
>
> Sent with [ProtonMail](https://protonmail.com) Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On March 20, 2018 11:19 AM, ZmnSCPxj via Lightning-dev 
>  wrote:
>
>> Good morning list,
>>
>> As my award-winning and supremely notable and 
>> talked-about-by-the-man-on-the-street article "Cyclic Superhubs as Solution 
>> Towards Reasonable Lightning Network Topography" points out, cycles are a 
>> good way to organize the LN in order to allow easier accessibility to the 
>> network for all participants of all kinds.
>>
>> An issue here is the need for coordination in order to set up cyclic 
>> superhubs.  A node acting by itself cannot form cyclic superhubs.
>>
>> However, one can consider that coordination is needed only to identify peers 
>> with which one forms superhubs.  But we already have a system that 
>> identifies peers: the node gossip.
>>
>> So let us assume: All nodes have similar-enough views of the 
>> publicly-visible peers on the node graph, as built by node gossip.
>>
>> I now present an algorithm, which given a set of nodes extracted from node 
>> gossip, returns a peer to try connecting and funding a channel to.
>>
>> --
>>
>> First, start with a 32-bit number i = 0.
>>
>> For each node, get hash = H(i || pubkey), where H is some standard hash 
>> algorithm, and pubkey is the public key of the node.  Also get our_hash = 
>> H(i || our_pubkey)
>>
>> Perform successive filtering.  While the set is larger than 2 nodes, 
>> successively compare high bits.  If the highest bit of hash does not match 
>> the highest bit of our_hash, remove it from the set.  If the resulting set 
>> is still larger than 2, match the next bit.  When the set is now 2 or 1 
>> node, back off by one bit and add back the most recently removed nodes.  
>> This yields a set that is at least 3 or more nodes.
>>
>> Sort the nodes according to hash.
>>
>> Identify where our node is in the sorted list.  Then our candidate is the 
>> next node in the list, or if we are the last node, then the first node in 
>> the list.
>>
>> If the candidate already has a channel with us, or has no address info and 
>> cannot be found by DNS seed or so on, or cannot be contacted, or refuses 
>> incoming cha

Re: [Lightning-dev] Towards a gridlike Lightning Network

[ZmnSCPxj via Lightning-dev]

Good morning list,

Igor Cota has started implementing my idea: 
https://github.com/icota/presto/commit/3311785e660d840f0ac8f2e333d0f0097aec980e

This forced me to actually start thinking more deeply about the algorithm I 
gave.

1.  We should use a well-used hash algorithm, such as RIPEMD160(SHA256(x))
2.  We should specify the size of `i` - 32-bits, 4 bytes - and indicate its 
endianness.  Let us use big-endian, as is typical for the rest of Lightning and 
for network order.
3.  My original algorithm had a significant probability of diverging.  So I 
respecify the termination condition later.
4.  Our own node should be part of the original working set.
5.  In the decimation loop, start with the highest bit.  This is the 7-index 
bit (1 << 7) of the first byte in the 20-byte hash (we treat the hash as a 
big-endian 160-bit number).

The modified termination condition for the decimation loop is below:

* If the working set is 7 nodes or more, decimate (i.e. match the next bit in 
the hashes and remove those that do not match our own hash in that bit.).
* If the working set is 3 to 6 nodes, stop, that is now the members of the 
superhub and we then sort them by hash and decide our position in the superhub 
(who will channel to us and who we will channel to).
* If the working set is 1 or 2 nodes, fail to form a superhub.  Increment `i` 
and restart.

Regards,
ZmnSCPxj

Sent with [ProtonMail](https://protonmail.com) Secure Email.

‐‐‐ Original Message ‐‐‐
On March 20, 2018 11:19 AM, ZmnSCPxj via Lightning-dev 
 wrote:

> Good morning list,
>
> As my award-winning and supremely notable and 
> talked-about-by-the-man-on-the-street article "Cyclic Superhubs as Solution 
> Towards Reasonable Lightning Network Topography" points out, cycles are a 
> good way to organize the LN in order to allow easier accessibility to the 
> network for all participants of all kinds.
>
> An issue here is the need for coordination in order to set up cyclic 
> superhubs.  A node acting by itself cannot form cyclic superhubs.
>
> However, one can consider that coordination is needed only to identify peers 
> with which one forms superhubs.  But we already have a system that identifies 
> peers: the node gossip.
>
> So let us assume: All nodes have similar-enough views of the publicly-visible 
> peers on the node graph, as built by node gossip.
>
> I now present an algorithm, which given a set of nodes extracted from node 
> gossip, returns a peer to try connecting and funding a channel to.
>
> --
>
> First, start with a 32-bit number i = 0.
>
> For each node, get hash = H(i || pubkey), where H is some standard hash 
> algorithm, and pubkey is the public key of the node.  Also get our_hash = H(i 
> || our_pubkey)
>
> Perform successive filtering.  While the set is larger than 2 nodes, 
> successively compare high bits.  If the highest bit of hash does not match 
> the highest bit of our_hash, remove it from the set.  If the resulting set is 
> still larger than 2, match the next bit.  When the set is now 2 or 1 node, 
> back off by one bit and add back the most recently removed nodes.  This 
> yields a set that is at least 3 or more nodes.
>
> Sort the nodes according to hash.
>
> Identify where our node is in the sorted list.  Then our candidate is the 
> next node in the list, or if we are the last node, then the first node in the 
> list.
>
> If the candidate already has a channel with us, or has no address info and 
> cannot be found by DNS seed or so on, or cannot be contacted, or refuses 
> incoming channels or some other error, then increment i and try finding again.
>
> ---
>
> Even if nodes have some divergence in their own local maps of the network, 
> there is the chance that the difference will be filtered away and the nodes 
> that are "destined" to form a superhub can still find each other in the same 
> superhub.
>
> Assuming all nodes have the same routemap, then all nodes will form their 
> own, non-overlapping superhubs for each i.  However if some nodes get to 
> increment i, hopefully because it already has a channel with its destined 
> candidate peer at one value of i, it can then potentially form superhubs with 
> other nodes that have also reached higher i.
>
> Regards,
> ZmnSCPxj___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev