Good morning Benjamin,

Rusty simulated an older version of my idea here; C code near the end of the 

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 

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.


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 
> <> 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: 
>>> 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 
>>> <> 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 mailing list

Reply via email to