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 <zmnsc...@protonmail.com> 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 
> <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 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

Reply via email to