Benjamin Mord [ARCHIVE] on Nostr: 📅 Original date posted:2018-04-19 📝 Original message: Hello ZmnSCPxj, I think ...
📅 Original date posted:2018-04-19
📝 Original message:
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 <ZmnSCPxj at protonmail.com> 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/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 at 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 at 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 <ZmnSCPxj at 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 at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180419/a12578c3/attachment-0001.html>;
📝 Original message:
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 <ZmnSCPxj at protonmail.com> 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/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 at 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 at 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 <ZmnSCPxj at 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 at 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 at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180419/a12578c3/attachment-0001.html>;