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