<unnamed>

Public Key

npub16ycdmhx5sct3h37cwvjff8le7qlp9k0ngst5ry5n262j6gkesrssskjvwy

Profile Code

nprofile1qqsdzvxamn2gv9cmclv8xfy5nlulq0sjm8e5g96pj2f4d9fdytvcpcgpz4mhxue69uhhyetvv9ujumn0wd68ytnwv46qz9rhwden5te0wfjkccte9ejxzmt4wvhxjmcpp4mhxue69uhkummn9ekx7mqzk2833

Publishing to

relay.nostr.net

relay.damus.io

nos.lol

Last Notes

2023-06-09 14:50:41 CEST

- reply

📅 Original date posted:2018-05-08
📝 Original message:
Sorry, I do not wish to spam the list, but I need to correct a rather
serious error in my last email. We must never call something
"post-quantum", absent mathematical proof. (And good luck with that.) I
apologise for my mistake in doing so myself.
I should not even refer to lattice based cryptography as a post-quantum
algorithm, I should at best call it a Shor's algorithm-resistant scheme. At
least, it is not (yet) known how Shor's algorithm could be used to break
it. Not in public circles, anyhow.
A cursory glance at the history of cryptanalysis shows that primitives
generally have finite life, which makes it odd that systems seldom use
redundant primitives, and seldom provide for their rapid and safe swap. A
system whose entire security rests on nothing but cryptography, ought to
take particular care! The spectre of quantum computers may render the
finite life of certain primitives more salient than others, but we must not
suppose that, absent Shor's algorithm, there would be no need to plan for
cryptographic failures. The question is not if, but when, Bitcoin and
lightning will contend with broken primitives, whether due to classical or
quantum cryptanalysis. Likely, both will come into play at various times,
and one must plan accordingly.
On Tue, May 8, 2018, 9:09 AM Benjamin Mord <ben at mord.io> wrote:
>
> That would be awesome. Do you have a reference?
>
> As pertains to the whole of asymmetric cryptography, I believe there are
> not a variety of post quantum schemes, there is only one*: lattice-based
> cryptography. (Which scares me, because it is not all that different from
> the others.)
>
> (* Actually, in contexts where time can be used for asymmetry, as in
> TESLA, we can then use hash functions to create something like asymmetric
> signatures as well. But the functional context has to be compatible with
> delayed verification.)
>
> (But I do not mean to focus exclusively on Schor's algorithm, the history
> of even pre-quantum cryptanalysis shows that primitives tend to have finite
> lifespan. Redundancy of any sort of good, even when not focused
> specifically on quantum risks.)
>
> On Tue, May 8, 2018, 8:58 AM Greg Sanders <gsanders87 at gmail.com> wrote:
>
>> From what I understand talking to folks, the linear properties of these
>> signature tricks are maintained under a number of post-quantum schemes.
>>
>> On Tue, May 8, 2018 at 8:44 AM, Benjamin Mord <ben at mord.family> wrote:
>>
>>>
>>> If I'm not mistaken, the scriptless scripts concept (as currently
>>> formulated) falls to Schor's algorithm, and at present there is no
>>> alternative implementation of the concept to fall back on. Correct? Lest we
>>> build a house of cards, I'd strongly urge everyone to not depend on
>>> functional concepts whose underlying cryptographic primitives cannot be
>>> swapped in an emergency.
>>>
>>> Sure, we use ecdsa for example (which is also vulnerable to Schor's
>>> algorithm), but in contrast to scriptless scripts we have a variety of
>>> backup primitives at our disposal that fulfill the same functional
>>> objective.
>>>
>>> If scriptless scripts are found possible under lattice-based
>>> cryptography for example, that would be something I suppose. The functional
>>> concept of scriptless scripts is indeed very awesome - we just need to add
>>> some cryptographic conservatism before we build on it.
>>>
>>>
>>> _______________________________________________
>>> 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/20180508/664c63d0/attachment-0001.html>

2023-06-09 14:50:40 CEST

- reply

📅 Original date posted:2018-05-08
📝 Original message:
If I'm not mistaken, the scriptless scripts concept (as currently
formulated) falls to Schor's algorithm, and at present there is no
alternative implementation of the concept to fall back on. Correct? Lest we
build a house of cards, I'd strongly urge everyone to not depend on
functional concepts whose underlying cryptographic primitives cannot be
swapped in an emergency.
Sure, we use ecdsa for example (which is also vulnerable to Schor's
algorithm), but in contrast to scriptless scripts we have a variety of
backup primitives at our disposal that fulfill the same functional
objective.
If scriptless scripts are found possible under lattice-based cryptography
for example, that would be something I suppose. The functional concept of
scriptless scripts is indeed very awesome - we just need to add some
cryptographic conservatism before we build on it.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180508/e565d776/attachment.html>

2023-06-09 14:50:40 CEST

- reply

📅 Original date posted:2018-05-08
📝 Original message:
That would be awesome. Do you have a reference?
As pertains to the whole of asymmetric cryptography, I believe there are
not a variety of post quantum schemes, there is only one*: lattice-based
cryptography. (Which scares me, because it is not all that different from
the others.)
(* Actually, in contexts where time can be used for asymmetry, as in TESLA,
we can then use hash functions to create something like asymmetric
signatures as well. But the functional context has to be compatible with
delayed verification.)
(But I do not mean to focus exclusively on Schor's algorithm, the history
of even pre-quantum cryptanalysis shows that primitives tend to have finite
lifespan. Redundancy of any sort of good, even when not focused
specifically on quantum risks.)
On Tue, May 8, 2018, 8:58 AM Greg Sanders <gsanders87 at gmail.com> wrote:
> From what I understand talking to folks, the linear properties of these
> signature tricks are maintained under a number of post-quantum schemes.
>
> On Tue, May 8, 2018 at 8:44 AM, Benjamin Mord <ben at mord.family> wrote:
>
>>
>> If I'm not mistaken, the scriptless scripts concept (as currently
>> formulated) falls to Schor's algorithm, and at present there is no
>> alternative implementation of the concept to fall back on. Correct? Lest we
>> build a house of cards, I'd strongly urge everyone to not depend on
>> functional concepts whose underlying cryptographic primitives cannot be
>> swapped in an emergency.
>>
>> Sure, we use ecdsa for example (which is also vulnerable to Schor's
>> algorithm), but in contrast to scriptless scripts we have a variety of
>> backup primitives at our disposal that fulfill the same functional
>> objective.
>>
>> If scriptless scripts are found possible under lattice-based cryptography
>> for example, that would be something I suppose. The functional concept of
>> scriptless scripts is indeed very awesome - we just need to add some
>> cryptographic conservatism before we build on it.
>>
>>
>> _______________________________________________
>> 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/20180508/45b1c742/attachment.html>

2023-06-09 14:50:15 CEST

- reply

📅 Original date posted:2018-04-20
📝 Original message:
Good afternoon ZmnSCPxj,
"I do not see a bloom filter?"
Well, if you look at it kinda sideways, you are using a bloom filter in
your March 23rd proposal. As originally defined, I think the "false
positives" in bloom filtering were the unfortunate cost of performance. In
BIP 37, the false positives become desirable, although still are 'false' in
that their only function is to serve as red herrings. But (omitting i for
clarity), your proposal takes BIP 37's spin on bloom filters one step
further to actually take the 'false positives' as the very definition of
our desired set, since what you are "searching for" is just your own public
key, which ends up being the least interesting result within that set.
" Regarding 24 vs 23, the condition for 23 allows a 3 members of a 5-member
neighborhood to think they form a single 3-member neighborhood, while the
remaining 2 members think they are in a 5-member neighborhood that includes
the other 3 members who have formed a 3-member neighborhood."
Oh, I see. But the reason that occurs is because different nodes are
considering different numbers of high-order bits. If everyone used the same
number of high-order bits, then it would become an equivalence
relationship, with which we can partition the network. This is because
then, a=b, would imply b=a, and also a=b and b=c, would imply a=c.
https://en.wikipedia.org/wiki/Equivalence_relation#Partition
I think algorithm from March 24 is broken actually, on second look, but I
understand now what you are trying to achieve. You want to allow local
judgement over best local cell size, and yet somehow end up with precise
uniform agreement on who is in which cells, because cycles require such
precision. But if you throw in that the network is dynamic, knowledge is
imperfect, and malicious behavior may occur, then I think strict
equivalence relationships and cycles become brittle. Perhaps we should
generalize the equivalence relationship into a distance function, so that
we can start thinking of this as a metric space which we want to fill with
some sort of structure. Perhaps then we can design efficient yet robustly
"fuzzy" structures. Perhaps we want a fuzzy fractal of some sort. Hmm...
"Intermediate nodes already know two hops? The incoming and outgoing hop?
Or do you need more information?"
Yes, nodes would need to know one hope more, since the idea would be to
attract competition to the high-usage yet high-fee links.
Thanks,
Ben
On Thu, Apr 19, 2018 at 11:24 PM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Benjamin,
>
>
> 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?
>
>
> I do not see a bloom filter? But then I am not a mathematician so it is
> possible I fail to see how the Bloom filter arises from the algorithm I
> described.
>
> Regarding 24 vs 23, the condition for 23 allows a 3 members of a 5-member
> neighborhood to think they form a single 3-member neighborhood, while the
> remaining 2 members think they are in a 5-member neighborhood that includes
> the other 3 members who have formed a 3-member neighborhood.
>
>
> 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?
>
>
> I believe that is what the algorithm already does? It dynamically sizes
> neighborhoods to be small, with high probability of neighborhoods to be
> 3->5 members.
>
> 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.
>
>
> The algorithm does not consider what happens when we have a cycle already
> existing, and a new member joins or an existing one wishes to leave. There
> is no way to inform this. My expectation is that people will just close
> channels that they no longer find useful; this makes funds available
> onchain. Then a process notices there are onchain funds, and calls this
> algorithm to get a proposed channel; this adapts to whatever the topology
> is right now.
>
> It is not clear when we should close channels. For one, gossip requires
> that a node first open a channel to somebody, before its existence is
> acknowledged and gossiped across the network: this is intended to prevent
> spammers from spinning up nodes without actually intending to join the
> network. Similarly, to leave the network, we assume that nodes will at
> least get all their channels closed: channel closure is an onchain event
> visible to everyone monitoring the the blockchain (which is what all LN
> nodes SHOULD do), and once all channels of a node have closed, we MAY drop
> them from the network view (c-lightning implements this, but I do not know
> if other implementations do).
>
> So at least for *leaving* LN permanently, the leaving node SHOULD close
> all its channels (or at least their peers SHOULD close it for them in
> unilateral closes if the peer just does not respond at all anymore). This
> updates the network view of everybody (assuming they follow the
> recommendation that they MAY drop nodes from the network view, if that node
> has all its channels closed). The closing will also put the channel funds
> onchain, and presumably the autopilots of its neighbors will notice the
> onchain funds, calls the algorithm to get a peer to channel to, which
> computes (hopefully) using the updated network view that has the leaving
> node removed already (this may not be true: the leaving node might not be
> able to close all channels simultaneously, and may misbehave and expect its
> neighbors to close the channels for it), and adapts correctly to the node
> leaving the network.
>
> However for a new node entering the network, there is problem. This
> requires existing nodes to close existing channels and open new ones to the
> new node: as this costs onchain fees, there is no real incentive for them
> to do so. I can only fall back on the informal argument: that people will
> at first experiment with the Lightning Network and commit a tiny amount of
> funds, then later they will put in more funds and thus open new channels,
> hopefully using this algorithm so that other people who come in later will
> also get new channels to them: the first channels people make will
> (eventually) not be in the neighborhood later on, but since they will open
> new channels later those will adapt to new neighborhoods of the larger
> network graph.
>
> I believe the main benefit of the algorithm I describe is that it flattens
> the number of channels a node will have and reduces centralization
> (although I believe roasbeef argues that centralization at the LN layer is
> relatively unimportant?). If each node opens two channels to two different
> nodes, pure random selection will by chance award a few lucky nodes with 3
> or 4 or 5 or more incoming channels while about 1/4 of nodes will have no
> channels incoming, but this algorithm will force all nodes to have exactly
> two incoming and two outgoing channels, while having similar reachability
> as random selection. Of course, that assumes everyone already knows the
> entire network beforehand, and the issue of new nodes coming in is absent.
>
>
> 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.
>
>
> Intermediate nodes already know two hops? The incoming and outgoing hop?
> Or do you need more information?
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180420/ab47485a/attachment-0001.html>

2023-06-09 14:50:14 CEST

- reply

📅 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>

2023-06-09 14:50:12 CEST

- reply

📅 Original date posted:2018-04-18
📝 Original message:
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/20180418/067b809c/attachment-0001.html>

2023-06-09 14:50:01 CEST

- reply

📅 Original date posted:2018-04-13
📝 Original message:
Good morning ZmnSCPxj,
As a skeptic of discrete logarithm's long-term security, I view scriptless
scripts as dangerously seductive. (But wow, are they cool! Almost cool
enough to wish we could uninvent quantum computing. I wonder if R-LWE can
be used instead as foundation? Not that I expect R-LWE to hold long-term
either...) But I digress.
As I listen to all the work starting up in the legacy financial markets to
mitigate the likely future failure of LIBOR, given how little thought went
into that possibility in the writing of currently-traded derivative
contracts, I'm reminded of how important and also how possible it is to
think about short and long-term goals simultaneously as we build systems.
It is far easier now than it will soon be to add expressiveness into the
core protocol, such as negative fees and optional exponential component.
Just because we pragmatically ignore negative fees and exponents in routing
decisions today, does not mean we will not feel enormous need for them in
the future - and having the ability to express such fee structures now will
enable efficiency improvements in the future, as simple implementation
(rather than protocol) upgrades.
I recognize AMP (at least as you proposed) is a long way out, but it seems
like something we'll inevitably want and will surely add. It is therefore
worth assuming now, as we think strategically about how fee dynamics will
improve efficiency over time. Who knows, my skepticism of discrete
logarithm hardness may prove misplaced, or else we'll find other ways to
achieve AMP. (I have not read roasbeef's proposal, but I shall.) The
protocol does not presently allow an exponential component, but it would be
trivial to add (even if, at first, defaulted to 1).
Thanks,
Ben
On Fri, Apr 13, 2018 at 9:26 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Benjamin,
>
>
>
>
> Sent with ProtonMail <https://protonmail.com> Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On April 13, 2018 4:37 AM, Benjamin Mord <ben at mord.io> wrote:
>
> Thank you, ZmnSCPxj.
>
> "... by adjusting the on-Lightning `fee_base_msat` and
> `fee_proportional_millionths` of channels."
>
> Yes, I agree these prices are a critical signaling mechanism that can have
> substantial impact on expected channel lifetime and thus economic
> efficiency of lightning operation overall. (As you may recall, I believe we
> should allow negative prices - even if present day routing algorithms
> choose to treat negative fees as zero for temporary simplicity.) You make
> a good point it can also improve routing efficiency by hinting at capacity,
> but for now they are unfortunately linear.
>
> The following paper did not account for the improved efficiency that price
> adjustment in response to channel state will likely enable, but one thing
> which may be relevant here is the underlying power law assumption of
> transaction size distribution (which is apparently drawn from actual data),
> and the more general approach to estimating channel lifespan. In lieu of
> advertising max capacity, perhaps we should instead permit a price exponent
> which may optionally be set to something larger than 1. The cost to channel
> operator of processing a transaction is largely the impact to expected
> channel lifespan, which in turn is nonlinear with respect to transaction
> size - and dramatically so as transaction size approaches (or exceeds)
> remaining capacity.
> https://arxiv.org/pdf/1712.10222.pdf
>
>
> Larger payments also have a much lower chance of successfully propagating
> through the network, as every channel in its route needs to have the
> requisite capacity, so I think it somewhat balances out (maybe).
>
> Adding a nonlinear component would be difficult to add on to the protocol
> currently, as I think there is no provision for it in the protocol. But
> maybe I am incorrect..?
>
> If we combine nonlinear pricing with your March 19 AMP proposal, I expect
> economic efficiency could be greatly improved.
>
>
> My AMP proposal cannot work soon. It requires at minimum for
> Bellare-Neven/MuSig/Schnorr (I get confused, which is the proper name for
> this) signatures to be added to Bitcoin to get HD+SS. Then we need to
> switch over all implementations to using scriptless script contingent
> payments rather than hashlocked contingent payments (and convince all
> network node operators to upgrade); we will be unable to use an
> intermediate node that does not understand SS contingent payments for my
> style of AMP.
>
> The earlier AMP proposal by roasbeef is back-compatible (uses the same
> hashlocked contingent payments we already use now), but does not support a
> proof-of-payment compatible with ZKCP protocols (although possibly I am
> wrong, I think roasbeef has mentioned before that it is ZKCP compatible).
>
> Regards,
> ZmnSCPxj
>
> Thanks again,
> Benjamin Mord
>
>
> On Thu, Apr 12, 2018 at 12:49 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com>
> wrote:
>
>> Good morning Benjamin,
>>
>> Do (should) channels have the option of publicizing their balances, so as
>> to improve routing performance / scalability in a large network, and for
>> competitive differentiation among competing routes? This would allow
>> channel owners to balance privacy with efficiency, and where the incentive
>> to publish would go up in proportion to network scalability requirements.
>> Brute force trial & error seems expensive at scale, and also reduces
>> privacy of the sender - so it seems a useful hedge to leave this decision
>> to the market (if technically practical).
>>
>>
>> I think brute-force scales well enough, but perhaps we should see the
>> network in action more.
>>
>> To an extent, it is possible to hint the suitability of a channel for
>> routing in a particular direction, without completely leaking your balance
>> in detail, by adjusting the on-Lightning `fee_base_msat` and
>> `fee_proportional_millionths` of channels. If you have a high balance on a
>> channel, you reduce your side of the fee for that channel (i.e. the
>> direction where you are the source for payments on that channel) to
>> encourage others to use it and hopefully pay you on a depleted channel. If
>> you have a low balance, you increase your fee. These fees are already
>> propagated using `channel_update`. No current node software implements
>> this yet, however.
>>
>> Regards,
>> ZmnSCPxj
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180413/c35af87b/attachment.html>

2023-06-09 14:50:00 CEST

- reply

📅 Original date posted:2018-04-12
📝 Original message:
Thank you, ZmnSCPxj.
"... by adjusting the on-Lightning `fee_base_msat` and
`fee_proportional_millionths` of channels."
Yes, I agree these prices are a critical signaling mechanism that can have
substantial impact on expected channel lifetime and thus economic
efficiency of lightning operation overall. (As you may recall, I believe we
should allow negative prices - even if present day routing algorithms
choose to treat negative fees as zero for temporary simplicity.) You make a
good point it can also improve routing efficiency by hinting at capacity,
but for now they are unfortunately linear.
The following paper did not account for the improved efficiency that price
adjustment in response to channel state will likely enable, but one thing
which may be relevant here is the underlying power law assumption of
transaction size distribution (which is apparently drawn from actual data),
and the more general approach to estimating channel lifespan. In lieu of
advertising max capacity, perhaps we should instead permit a price exponent
which may optionally be set to something larger than 1. The cost to channel
operator of processing a transaction is largely the impact to expected
channel lifespan, which in turn is nonlinear with respect to transaction
size - and dramatically so as transaction size approaches (or exceeds)
remaining capacity.
https://arxiv.org/pdf/1712.10222.pdf
If we combine nonlinear pricing with your March 19 AMP proposal, I expect
economic efficiency could be greatly improved.
Thanks again,
Benjamin Mord
On Thu, Apr 12, 2018 at 12:49 AM, ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
> Good morning Benjamin,
>
> Do (should) channels have the option of publicizing their balances, so as
> to improve routing performance / scalability in a large network, and for
> competitive differentiation among competing routes? This would allow
> channel owners to balance privacy with efficiency, and where the incentive
> to publish would go up in proportion to network scalability requirements.
> Brute force trial & error seems expensive at scale, and also reduces
> privacy of the sender - so it seems a useful hedge to leave this decision
> to the market (if technically practical).
>
>
> I think brute-force scales well enough, but perhaps we should see the
> network in action more.
>
> To an extent, it is possible to hint the suitability of a channel for
> routing in a particular direction, without completely leaking your balance
> in detail, by adjusting the on-Lightning `fee_base_msat` and
> `fee_proportional_millionths` of channels. If you have a high balance on a
> channel, you reduce your side of the fee for that channel (i.e. the
> direction where you are the source for payments on that channel) to
> encourage others to use it and hopefully pay you on a depleted channel. If
> you have a low balance, you increase your fee. These fees are already
> propagated using `channel_update`. No current node software implements
> this yet, however.
>
> Regards,
> ZmnSCPxj
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180412/d4d4baee/attachment-0001.html>

2023-06-09 14:49:59 CEST

- reply

📅 Original date posted:2018-04-11
📝 Original message:
Do (should) channels have the option of publicizing their balances, so as
to improve routing performance / scalability in a large network, and for
competitive differentiation among competing routes? This would allow
channel owners to balance privacy with efficiency, and where the incentive
to publish would go up in proportion to network scalability requirements.
Brute force trial & error seems expensive at scale, and also reduces
privacy of the sender - so it seems a useful hedge to leave this decision
to the market (if technically practical).
On Wed, Apr 11, 2018 at 5:17 AM, ZmnSCPxj via Lightning-dev <
lightning-dev at lists.linuxfoundation.org> wrote:
> Good morning Alejandro,
>
>
> No, channel balance of each peer on the channel is not revealed on node
> gossip.
>
> Logically, invert the question: do you want to report how much you
> spend/receive on each of your channels to the network? Do you want to
> report how much you own on Lightning to be reported to everyone on
> Lightning?
>
> Since the balance on each peer is effectively the amount of money each
> peer owns on that channel, and each change to that balance represents a
> send/receive on that channel, you will not want to report your balance, and
> any changes in that balance, to the entire network.
>
> Logically you can then expect not to receive such updates from anybody
> else, either.
>
> How do real-life implementations like c-lightning get your payment routes
> then? By brute-force trial-and-error
>
>
> If payment routes are discovered by brute-force trial-and-error, and
> actually the sender can interrupt any payment by simply not revealing the
> secret, isn't it possible for any sender to simply start probing
> to discover the capacities in each path?
>
>
> Yes. Although now the sender risks its funds: if a node along the route
> it selects stalls, then the sender risks having its money locked for some
> blocks.
>
> Also, the sender only gets one bit of information to the question: Is the
> channel balance in this direction greater than X?
>
> Finally, the exact failure TEMPORARY_CHANNEL_FAILURE can mean that the
> other node is currently down rather than the channel not having enough
> capacity in that direction, or if there are too many HTLCs in-flight on
> that channel, or so on (the most likely currently seems to be the node is
> currently down rather than the channel balance being insufficient, since it
> seems many people do not leave their nodes running 24/7).
>
> So it is always less desirable than getting the exact channel balances at
> each balance update. You get degraded privacy, but not a full loss of
> privacy compared to broadcasting all balance updates.
>
> (in particular, if the channel balance changes, you would have to re-query
> the channel again to learn this)
>
> (your technique is flawed in the detail that the sender simply selects a
> destination randomly and a random payment hash, which has negligible
> probability of the randomly-selected destination knowing its preimage, but
> is otherwise sound in its broad strokes)
>
> 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/20180411/5d786b71/attachment-0001.html>

2023-06-09 14:48:35 CEST

- reply

📅 Original date posted:2018-01-16
📝 Original message:
It isn't obvious to me from the BOLTs if fees can be negative, and I'm
finding uint in the go source code - which suggests not. In scenarios where
the funding of a payment channel has been fully committed in one direction,
why not allow negative fees to incent unwinding, in scenarios where nodes
consider that cheaper than on-chain rebalancing?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180116/e91b10db/attachment.html>

2023-06-09 14:48:35 CEST

- reply

📅 Original date posted:2018-01-16
📝 Original message:
Thanks. It sounds like it was dropped due to difficulty in the routing
protocol. Is that difficulty documented somewhere I can review? If so, I
might take a crack at a solution to it. But regardless I suggest the
protocol should support negative fees, even if an individual routing
implementation prefers to treat as 0 for simplicity. That should be up to
the implementation I think, and not a protocol constraint.
On Tue, Jan 16, 2018 at 2:58 PM, William Casarin <jb55 at jb55.com> wrote:
> Benjamin Mord <ben at mord.io> writes:
> > [..]
> > why not allow negative fees to incent unwinding, in scenarios where nodes
> > consider that cheaper than on-chain rebalancing?
>
> This was brought up before here [1]:
>
> Rusty Russell <rusty at rustcorp.com.au> writes:
> >> Edward Marynarz <edziumarynarz at gmail.com> writes:
> >> Another trivial question: can the fee be negative? It might help with
> some
> >> channel rebalancing.
>
> >In my original implementation, they could be. However, that turns out
> >to be a very strange idea, and complicates routing.
>
> [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/
> 2017-December/000827.html
>
> Cheers,
>
> --
> https://jb55.com
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180116/79b12b13/attachment.html>

2023-06-09 14:47:42 CEST

- reply

📅 Original date posted:2017-11-16
📝 Original message:
Ivan,
That is mostly false, but with bits of truth sprinkled in. Contact me at
ben at mord.io for further discussion so we tread lightly on the lists' email
inboxes. But briefly: scale-capable routing protocols are possible as
demonstrated by IP and thus by the internet itself. As for centralizing
flow through small number of liquidity providers, yes that does seem
economically probable, at least unless / until off-chain channel
rebalancing mechanism (like the recently proposed "revive" protocol) come
about. Bitcoin script is not currently revive-capable but Ethereum is, so
either Bitcoin revive could be enabled via two-way pegged sidechain
protocol with Ethereum, or even better, by a purpose-built (yet still not
Turing-complete) extension to Bitcoin script itself in the future. In
either case the lightning network seems a key first step, and even were
off-chain payment rebalancing not possible for some odd reason, the
lightning network seems extremely valuable and scaleable - regardless
because the centralization you speak is not one that affects safety of the
money supply itself, and these centralized hubs would be more dispensable /
swappable versus the mining centralization risk that people more often talk
about in Bitcoin. Lightning network centralization, even if it persisted
somehow despite revive and future concepts, would not be an existential
risk. As for transaction fees, the idea is only channel setup / tear down
are required greatly reducing fees. Yes if txin fees were millions of
dollars then people could not practically penalize fraud, but that is
unlikely. Even if txin fees made fraud claims marginally unprofitable (yet
practical) that would still be ok - the judicial systems of most countries
prove that people go beyond self-interest when sufficiently ticked, a fact
of human psychology which in turn creates the incentives that support
honest business. (Also please be aware I'm not a lightning code
contributor, so that team might also be doing more to address already than
I thought to mention above.)
I'll post more about this on http://ben.mord.io
Thanks,
Ben
On Thu, Nov 16, 2017 at 9:26 AM, Ivan Raszl <iraszl at gmail.com> wrote:
> I came across a thread discussing lightning network on reddit. A comment
> was stating there is an unresolvable issue with the concept of lightning
> network, related to routing. Quoting the comment:
>
> "The problem is, actually scaling and preventing decentralization requires
> far more than a nice UX that lets you shoot tx from alpha-tester-A to
> alpha-tester-B, and Lightning currently utterly fails at both of them. It
> can't scale to 100,000 users due to routing difficulties; nor does it has
> any plan of bootstrapping to "everyone using it" without the hubs
> hypercentralizing to a few "liquidity providers" (read:banks); nor does it
> have any plans to have actual security on a congested blockchain with high
> fees. As a scaling solution, Lightning is a lot worse than the blockchain
> itself right now."
>
> Can somebody comment on this? Thanks!
>
> _______________________________________________
> 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/20171116/d24b925d/attachment.html>