Good morning list,

Igor Cota has started implementing my idea:

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

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.


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

Reply via email to