Show Idle (>14 d.) Chans


← 2021-07-03 | 2021-07-05 →
14:59 thimbronion http://thimbron.com/2021/07/the-comms-chronicle/
~ 1 hours 19 minutes ~
16:18 asciilifeform thimbronion: notbad summary, ty for writing.
16:19 asciilifeform thimbronion: thinking about it, the shared-keys thing + fixed-size deduplication message cache is prolly the simplest scheme that has a chance of working.
~ 1 hours 16 minutes ~
17:36 thimbronion asciilifeform: Ah. And that would be with UDP for peers, and IRC emulation for clients?
17:36 asciilifeform thimbronion: aha, as described in prev. thrd
~ 34 minutes ~
18:11 gregory4 http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042446 << with or without the PoW?
18:11 dulapbot Logged on 2021-07-04 12:19:50 asciilifeform: thimbronion: thinking about it, the shared-keys thing + fixed-size deduplication message cache is prolly the simplest scheme that has a chance of working.
18:11 asciilifeform gregory4: without. simply shared key for each link in graph.
18:19 asciilifeform welcome to dulapnet, punkman !
18:20 punkman hey asciilifeform
18:20 punkman happy 'murica day mother uckers
18:22 gregory4 asciilifeform: glad to hear. another question: are we going to encrypt the messages, sign them, or both?
18:22 asciilifeform gregory4: it unfortunately isn't practical to sign anything -- or verify sigs on anything -- at Gb/s on pc
18:22 dulapbot Logged on 2021-05-18 16:15:41 asciilifeform: the main obstacle currently is that non-leaking rsa is slow on pc.
18:23 asciilifeform so what remains is symmetrics, e.g. serpent, with shared key.
18:23 asciilifeform (shared via pgpgram, out of band)
18:23 gregory4 so we are encrypting.
18:24 gregory4 right, by shared you mean symmetric. my bad.
18:24 asciilifeform aha.
18:25 gregory4 do you have any particular algorithm in mind? I can start looking into it.
18:25 asciilifeform gregory4: already linked above. and long ago implemented.
18:25 asciilifeform gregory4: the major gnarly bit in all of this, imho, is the irc emulation end.
18:26 punkman so I have to manually exchange symmetric key with 50 different people?
18:26 asciilifeform if that's how many you intend to directly peer with -- then yes
18:26 gregory4 sorry I missed that message.
18:27 asciilifeform gregory4: http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042458
18:27 dulapbot Logged on 2021-07-04 14:23:37 asciilifeform: so what remains is symmetrics, e.g. serpent, with shared key.
18:27 asciilifeform punkman: if you have a better algo (see last 3d of log re: the open problem) i'm all ears.
18:28 shinohai http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042468 <<< yeah it was udp, so understandable if you didn't get it.
18:28 dulapbot Logged on 2021-07-04 14:26:59 gregory4: sorry I missed that message.
18:28 asciilifeform lol
18:28 shinohai And nice blog post thimbronion
18:31 asciilifeform http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042466 << observe that irc peering already suffered from this.
18:31 dulapbot Logged on 2021-07-04 14:26:34 punkman: so I have to manually exchange symmetric key with 50 different people?
18:38 * asciilifeform has the algo 'in head', will try to write it up as human text in coming days.
18:38 punkman is this a gossipd?
18:39 asciilifeform punkman: not all that similar to mp's scheme, which to be fair he proposed before anyone knew what constant-time rsa costs
18:39 punkman yeah in the abstract sense
18:39 punkman I don't think mp' scheme ever made sense
18:40 asciilifeform punkman: i tried to turn it into an algo that could make sense ( what's left of mp inc. recently put back comments, so you can read, thimbronion linked in his summary)
18:40 asciilifeform btw 'gossip routing' is a 1990s term of art, did not originate w/ mp or asciilifeform
18:42 asciilifeform in the most common form, peers randomly converse and sync a db of some kind ('do you have x?' 'no' 'here's x' etc)
18:42 asciilifeform the 'inventory' in trb is an example of this.
18:43 asciilifeform what i'm proposing is much simpler, known as 'flood routing', where an incoming message, after determined to be authentic -- and novel (i.e. not equal to any of N previous received messages) is sent to all peers save for the one who brought it to begin with.
18:44 asciilifeform i.e. there is no 'asking'. you get sent packets, and then decide whether to emit to client and/or to rebroadcast (and to whom).
18:46 asciilifeform incidentally, this is how it was once thought networks would have to work, before invention of 'spanning tree' (an algo i explicitly reject in p2pism -- it is inherently incatronic)
18:47 asciilifeform e.g. ethernet -- uses spanning-tree to guarantee acyclicity.
18:47 asciilifeform (phunphakt, asciilifeform used similar algo in the context of vtron, for ringing alarm if cyclic patch sequence is found)
18:53 punkman any thoughts on message ordering?
18:53 asciilifeform punkman: what about it ?
18:53 asciilifeform punkman: observe that irc already makes no guarantees of message ordering. somehow no one (almost) ever gives a damn.
18:55 punkman guarantees are hard, but it does try to keep things in order
18:55 asciilifeform in practice, everyone will see 100 copies of your message before the switch in your kbd stops bouncing, typically.
18:56 asciilifeform (in flood routing, every message takes in fact every possible path to each participant)
18:57 asciilifeform ^ this necessarily includes the shortest path. important, imho, point.
18:58 asciilifeform now, almost all received messages will be duplicates. but cpu has been cheap enuff for this not to be a problem for 30yrs nao
18:59 asciilifeform ... even if you want to keep and dedupe against last mil+ of messages.
19:00 * asciilifeform suspects that even does not require 'fancy' data structure; would work ok with simple ring buffer of msg hashes.
19:01 asciilifeform msg, importantly, gotta include a timestamp ~generated by originator~.
19:01 asciilifeform (simply as pill against this nonsense)
19:01 dulapbot Logged on 2021-07-01 18:08:25 asciilifeform: i.e. 1 nick can't utter e.g. 'yes' or '$vwap' etc within <N min ?
19:02 asciilifeform anyways imho the above is just about enuff to work with.
19:02 * asciilifeform must bbl, but encourages folx to ask q's and generally discuss w/out waiting for him
19:10 verisimilitude A symmetric scheme, with the secrets not generally being valuable, would work for me. Once I generate a truly trustworthy PGP key, I'm damn certain not letting it touch the Internet.
19:17 thimbronion shinohai: ty
~ 37 minutes ~
19:54 punkman I think msg ordering is the gnarly problem in this. Suppose your peer gets a message with a timestamp of 1 hour (or 1 minute) in the past. Does it emit this to your IRC client as new msg? Suppose my peer has better connection to bot than alf, and I always get bot replies before whatever alf said that triggered the bot.
19:55 punkman IRC does a lot to maintain order
19:56 gregory4 punkman: the timestamp is not for ordering, simply for indicating that two messages with same content are distinct.
19:56 asciilifeform punkman: timestamp, in my proposed algo, is issued by the message's originator. and gregory4 is correct, it is strictly for '2 people being able to say 'yes' within 1 deduplication interval'
19:57 asciilifeform this imho is a key point, and i rec to think about it until fully sinks in. i.e. it is factually impossible to make for faster propagation than offered by flood fill.
19:57 dulapbot Logged on 2021-07-04 14:57:38 asciilifeform: ^ this necessarily includes the shortest path. important, imho, point.
20:02 asciilifeform re: 'hour in the past' -- i'd rather use per-peer incremented counters, rather than political time (which introduces ye olde sync question)
20:03 asciilifeform (why? not only for 'two can say yes', but to prevent a third party from replaying last year's packets to flood the net)
20:07 punkman asciilifeform: are you saying the flood routing solves the problem of getting bot answer before bot command?
20:07 asciilifeform for cutoff, i'd use simple algo: any message which passes the dupe litmus (i.e. not found in the circular buffer) but with a counter value 'older' than the oldest (optionally -- for-peer) message in the buffer, is rejected.
20:07 asciilifeform punkman: what i'm saying is that it solves it in all cases where anything else could have solved it.
20:08 asciilifeform (and naturally -- does not, where nothing could)
20:09 asciilifeform consider the typical case where your pathgraph to the bot is shorter than to the peer who issued the command. the bot will relay the command to peers, which includes you, before issuing its answer.
20:09 asciilifeform which then follows same paths-including-shortest.
20:09 asciilifeform hence you will receive the command and bot reply in the correct order, w/out anyone doing any elaborate reordering.
20:10 asciilifeform it is possible to construct a scenario where this is not the case on account of packets arriving out-of-order. but there is no clean universal pill against this.
20:12 asciilifeform imho it would be quite misguided to perform any kind of 'smart' reorderings, considering that the endpoints remain traditional irc clients which are 'append-only', you cannot direct an incoming message to be displayed somewhere other than at the 'bottom'.
20:13 * asciilifeform has zero interest in attempting to 'reinvent bicycle' of desktop irc clients, or using anyone else's attempt at same
20:14 asciilifeform tldr: messages will almost always arrive in apparently-correct order. but when they do not -- live with it. it imho is a very small price to pay for massive reduction in movingparts count.
20:16 asciilifeform hypothetically, if anyone gave a damn about exact orderings, msg would include hash of the latest predecessor known to the sender. but again, imho no such thing is needed.
20:17 punkman messages will almost always arrive in apparently-correct order << if this holds, yes it's a small price. but I've encountered ordering problems in the wild, and it gets annoying pretty fast
20:17 asciilifeform punkman: i imagine it'll get a little annoying when each peer is on different planet. but i do not expect to find us in this or similar situation any time soon.
20:19 punkman hash of the latest predecessor << still hits wall against "irc clients which are 'append-only'"
20:19 asciilifeform exactly, it'd be completely pointless
20:21 asciilifeform i have no intention of attempting to make so much as a scratch in that wall. logs are append-only as fucking beelzebub intended'em to be.
20:22 asciilifeform if it bothers the reader that two messages seem to be out of order, let him go to various folxs' public logs until finds an ordering to his liking.
20:23 asciilifeform (and let him become better connected with the relevant people until he sees messages in-order. etc)
~ 1 hours 22 minutes ~
21:46 punkman http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042524 << the universal pill is: master does the ordering for all peers. which is of course not p2p. As an example, paxos,raft and other such "consensoos" algos, then add "if master dies, elect new master" on top of that.
21:46 dulapbot Logged on 2021-07-04 16:10:52 asciilifeform: it is possible to construct a scenario where this is not the case on account of packets arriving out-of-order. but there is no clean universal pill against this.
~ 23 minutes ~
22:09 asciilifeform punkman: lolyes; we're talking into that right nao tho, 0 reason to make another one
22:11 asciilifeform spanning-tree protocol is arguably a variant of same -- the precise location of the points of failure shifts, but at all times there remain such points
22:11 dulapbot Logged on 2021-07-04 14:47:32 asciilifeform: e.g. ethernet -- uses spanning-tree to guarantee acyclicity.
~ 42 minutes ~
22:53 verisimilitude This channel is hardly active enough for this to even be an issue.
22:55 verisimilitude http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042515 I completely agree. It shouldn't even be thought of as time.
22:55 dulapbot Logged on 2021-07-04 16:02:13 asciilifeform: re: 'hour in the past' -- i'd rather use per-peer incremented counters, rather than political time (which introduces ye olde sync question)
~ 21 minutes ~
23:16 punkman found a relevant paper https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2004/CS/CS-2004-04.pdf
23:16 punkman "In this paper we formally prove that constrained flooding along the logical arcs of a
23:16 punkman deterministic overlay network preserve causal ordering at no additional cost."
23:16 punkman not sure what exactly is meant by deterministic here
~ 15 minutes ~
23:32 asciilifeform http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042541 << ~protocol~ oughta be able to withstand a ddos; and/or various folx sending fat warez over it; and the like.
23:32 dulapbot Logged on 2021-07-04 18:53:58 verisimilitude: This channel is hardly active enough for this to even be an issue.
23:32 asciilifeform every piece of rubbish pseudoinfrastructure on the net started out as 'this is enuff for me an' my bottle mates'. don't be a that.
23:33 asciilifeform (or rather, whoever wants, can go an' be a that, but count asciilifeform out, he has 0 interest in participating)
23:36 asciilifeform http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042542 << aha, but needs to behave rather like a timestamp, in that messages which attempt to advance it 'by centuries' must be rejected, or you quickly run outta counter and the ability to guarantee unique #
23:36 dulapbot Logged on 2021-07-04 18:55:01 verisimilitude: http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042515 I completely agree. It shouldn't even be thought of as time.
23:37 asciilifeform i.e. counter gotta increase monotonically.
23:39 asciilifeform ''This protocol, nicknamed Overlay, is simply constrained flooding across the logical arcs of the overlay topology. In other words, the idea is to broadcast each message along the overlay edges. Node i that wishes to send message m to all nodes in the system, sends the message only to its overlay neighbors. The first time node j receives message m, j sends m to all its overlay neighbors
23:39 asciilifeform excluding the node from which it received m. Afterwards, j delivers m to the application.'
23:39 asciilifeform punkman: lulzy that this ended up as 'a paper', it's simply restatement of flood-fill algo, circa 1950s.
23:40 punkman so each peer has logical clock. when it wants to send message, it increments own clock, then makes a list of own clock and last observed clocks of N other peers. then send msg + list-of-clocks. When you receive msg, you check if your last observed clock of those N peers equals list-of-clocks. If not, you wait until you get the missing messages,
23:40 punkman before pushing msg to your irc client.
23:41 punkman (The Timestamp protocol in the paper)
23:41 punkman well, sort of
23:41 asciilifeform punkman: that there has the obvious problem of potentially infinite wait
23:42 punkman could have timeout
23:42 punkman then you just push message
23:42 asciilifeform could, at which point it reverts to flood-fill.
23:42 asciilifeform (a pointlessly slowed-down flood fill..)
23:43 asciilifeform i can't speak for erryone, but i don't give one half of a shit if two people who hit 'return' within 1ms get displayed on my terminal in order a,b or b,a
23:43 asciilifeform i can't picture any situation in which it matters, and moreover, if you find yourself in such a situation, imho you had necessarily done something foolish.
23:44 asciilifeform what ilkka kokkarinen called 'martian problem'. (iirc from pokerism, term of art.)
23:50 punkman flood fill in the peer network? peer only delays sending to irc client, can push immediately to other peers
23:51 asciilifeform punkman: i still don't understand why to bother with this. (see above)
23:51 asciilifeform the req'd moving parts aint free.
23:53 asciilifeform note that asciilifeform isn't opposed to punkman (or anybody else) configuring ~his~ own client to attempt to reorder, somehow, messages perceived as outta order. but i utterly fail to see why this mechanism ~must~ be an integral part of the protocol.
23:54 asciilifeform from asciilifeform's pov, reordering is approx as useful as tits on a hog.
23:55 punkman I don't want total order. I guess each peer sending only its own logical clock, will work ok. But again peer must delay sending alf's msg #5 before alf's msg #4 to irc client.
23:57 asciilifeform punkman: i'm deeply skeptical that 2 messages i send w/ min. (say 100ms) delay b/w them (e.g. if client broke up a paste) will ever arrive out of order anywhere, even if no special precautions are taken.
23:59 verisimilitude http://logs.nosuchlabs.com/log/asciilifeform/2021-07-04#1042550 I agree. The issue is this is still so vague I feel like a disconnected observer more than anything else. I'll be more help once some foundations are settled.
23:59 dulapbot Logged on 2021-07-04 19:32:46 asciilifeform: every piece of rubbish pseudoinfrastructure on the net started out as 'this is enuff for me an' my bottle mates'. don't be a that.
23:59 asciilifeform verisimilitude: is ok, do not feel somehow obligated to grasp the thread. (but if you do -- welcome to comment)
← 2021-07-03 | 2021-07-05 →