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/000029.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 <ben@mord.family> 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 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

_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev