一个算法问题

[oxogenesis]

不要改题目，能回答的回答

问题描述：

固定数量的客户端连接同一服务器
服务器不具备数据存储功能，只有单条消息定向转发功能
客户端之间借助服务器数据中继传播消息

每个客户端具有唯一编号
发送的每条消息有编号，从 1 开始，依次加 1，并且都带有时间戳
比如：
客户端 A 发的消息是 A1，A2，A3...
客户端 B 发的消息是 B1，B2，B3...
...

客户端可以保存自己生成的消息和收到的消息
客户端不能伪造其他客户端的消息
客户端可以转发其他客户端的消息，举例：
A 可以向 C 转发消息 B2

客户端知道所有其他客户端的编号
客户端并不保证总是在线
在一个时刻，有可能全都在线，有可能都不在线，有可能部分在线

如何用最少的消息，使得每一个客户端都尽可能获得全部客户端的消息

[oxogenesis]

来个大佬大神，回答回答，谢谢！

实在不行改问题歪楼也行啊，捧个人场

消灭零回复

[12tall]

前排插眼，学习经验

[mengzhuo]

经典的区块链，不用我多说了吧

[arrow8899]

最后一句没看明白

[a7a2a7a2]

貌似考这个是不是：
1、基于原始客户端可信度最高设计，cdn，可去中心化动态服务（原始掉线后从其他服务器获取，基于最后时间戳可信度最高）
2、基于消息发出即不可修改设计,类似区块连

[oxogenesis]

@mengzhuo 用
@arrow8899 举例说明
客户端 A、B、C...不断的再发消息 A1~An、B1~Bm、C1~Cx...

如果所有客户端都在线，一个客户端生成一条消息，可以向其他客户端各发一条消息
如果有客户端下线一段时间，然后再上线，如何将离线这段时间内的所有消息全部同步回来？
先得找一下谁在线，然后告诉对方自己最后收到的消息，对方给你同步后续消息，但是对方也有可能是刚刚上线，对方消息就不全

[mengzhuo]

@oxogenesis 你乱想的太多了，看下区块链的介绍你就明白怎么搞了。

[oxogenesis]

@a7a2a7a2 一个算法的问题，不是考题
自己弄得个聊天程序，借用区块链思想，现在在想群聊的实现方法
目前初步拟定群控制消息，群消息格式
https://github.com/oxogenesis/oxo-chat-client/blob/master/src/utils/json_schema.js#L225

[a7a2a7a2]

@oxogenesis 如我回复的第二条，那就是区块连的话，很简单。
消息不全也要先同步最大数量的

任何刚上线的的客户端都要请求一次所有编号内的客户端的最后一条消息，等所有客户端返回他们最后一条消息的编号，取最大编号，然后对比自己的存储的该客户端唯一编号最大消息编号就能知道少了多少，然后直接从刚才返回最大消息编号的服务区同步没有的数据。

每当收到最新在线客户端发来消息的编号跟自己存储的编号不连续的时候就需要触发同步服务。

看我上面的 2 个设计，你需要的是什么
@oxogenesis

[oxogenesis]

这里的问题是不是所有客户端都在线

请求所有客户端，对方不一定在线，那就需要有重试机制，可能有的客户端说完话后就长时间不在线

等待某个客户端发消息（这个触发机制肯定是要的），可能有的客户端说完话后，长时间不发言

我倾向于，上线以后，靠在线的部分客户端，尽可能多的同步当前在线客户端的所有数据，再加上被动触发机制、引用关联机制、适当强度的轮询机制，消息类型要少，消息请求响应数量要少，降低系统复杂度和服务器的负载

[wutiantong]

这是基于 BLE/WiFi-Direct 的 Local Chat 么？

[oxogenesis]

@wutiantong 不是，还是需要服务器的，但是服务器只做消息转发，不存储数据，所有数据都存在个人计算设备

[fluorinedog]

写个 Gossip 协议吧。
看起来服务器只需要保存账号->ip 的映射，其他都靠 P2P （暂时不考虑穿透）。信息转发靠洪泛。
不过，如果楼主不在服务器上放数据的话，完全无法实现离线留言功能啊。A 上线给 B 发消息=>A 下线=>B 上线

[w516322644]

MQTT ？

[wutiantong]

@oxogenesis 客户端发的这些消息是广播（ to all ），还是私聊（ to peer ），还是兼而有之呢？
题目前半段的描述感觉像是广播，但又忽然提到了转发（ A 向 C 转发 B2 ），这又是属于私聊的性质了。

[IanPeverell]

Gossip 协议；轮询附近节点最近消息时间戳并发送本地最新消息时间戳，如果接受者本地最新消息时间戳比询问者时间戳晚则发送询问者缺失时间段消息，否则不做处理
基本思想就是把 Bitcoin 的 height 换成时间戳

[oxogenesis]

@fluorinedog 对，私聊的话，得两个人同时在线，群聊只要有一个人在线，就相当于给所有后上线的人做种子了
服务器什么都不能存，要断绝对任何服务器的依赖，服务器只形式路由器的职能
这样才能保证，客户端对数据的完全控制
可以承受牺牲部分可靠性、便利性，
现在网络这么发达，如果个体愿意，保持持续在线并不难

[oxogenesis]

@wutiantong 所有的消息都是一个客户端通过服务器发送给另一个客户端，通过多条消息来实现“广播的效果”

私聊（已经实现客户端到客户端加密），并且密钥隔一段时间换一次
群聊的想法是，每个群里的任意两个客户端协商一次密钥，以后都用这个密钥来加密，群聊就是把同一句话用不同的密钥加密后发个对应的客户端

[oxogenesis]

@IanPeverell
我的想法还停留在，不依赖特定服务器，将服务器降维到网络设备。
而不是完全的 p2p，感觉 p2p 的服务质量不太靠谱

[no1xsyzy]

如果说 A 向 B 发送消息，结果 B 突然变得暂时不可及（比如 B 连续宣称包完整性检验失败），那么这时候会发生什么？
1. 服务器留存并等待 B 再次可及；
2. 丢弃；
3. 服务器将 “不可及” 这一结果返回给 A，由 A 来决定如何处理。

根据你的 spec，1 不被允许。剩下的，2 就是 UDP，3 就是 TCP。把服务器等价成 ARP，允许任何一台机器成为网关和边际网关就行。
然后在这之上建立一个 P2P 聊天系统。那么就可以抄答案了。
现在你还有什么问题吗？

[oxogenesis]

@no1xsyzy
B 收到的要么就是一条完整的 Ax 消息，要么就是什么都没有。
所以没有 1、3，只有 2。

“把服务器降维成网络设备”
服务器成为网络设备，服务器只处理客户端之间的消息转发业务，并不保证传达到位，类似 UDP （这是对的）。
连上服务器的客户端之间就可以聊天了，消息只中继一次，时效性有保障。

P2P 的话，等 A 找到 B，都猴年马月了，早就没聊天的兴致了，没见过能用的 P2P 聊天系统。
P2P 做文件分享还可以，聊天这种业务它做不了。

[cassyfar]

赞同 @fluorinedog 提到的观点。

如果只是这个聊天室的客户端同步消息是不可行的。
比如 C 在只有他一个人在线的时候发了个消息，然后下线，再也没上线，这个消息就彻底丢失了。除非这个聊天室之外的客户端对这个消息进行了备份 /同步。但这样一来，怎么确定一个客户端对于哪些消息需要同步。如果一个客户端同步所有消息，也没有办法 scale。

[fluorinedog]

楼主别想区块链了，共识机制要求大部分的用户永远在线，和你这个应用完全不搭。牺牲大量算力换来的安全可信共识对你这应用也没啥用。

最后，简化一下问题，把上下线改成机器可能随时静默崩溃，服务器改成固定的路由网络，你这个不就是要搞个分布式一致性协议吗。

不过大多数协议要保证正确性的话，对机器同时崩溃（或者说下线）数量是有限制的，你感兴趣的话可以去看一下

[oxogenesis]

真理越变越明，感谢坛友与我一起头脑风暴

@cassyfar 服务器只做转发，“比如 C 在只有他一个人在线的时候发了个消息，然后下线，再也没上线，这个消息就彻底丢失了。”这个现象是可能出现，这是为了隐私所必须要做的牺牲。

@fluorinedog 我认为区块链并不严重依赖于一般意义上的“共识机制（全网的共识）”
区块链可以被用只需要“事件参与方的达成共识”即可的业务场景。
比如私聊，只需要两个人达成共识即可，服务器转发一下消息即可，除此以外的全网其他客户端都感知不到。
同理群聊，也只是入群的这些人范围内转发相关消息。

私聊是两个人，每人一条消息链，自己生成一条，同步对方一条
群聊也是每人一条消息链，自己一条，同步其他人（ N-1 ）条
除了自身 sequence 和 prehash 锁定之外，再加入一个外链引用字段，就可以起到跨链校验，把不同的链拧成一根绳的效果。

根本就没有算力牺牲，我本来就极度反感挖矿这种 2B 行为。
有空可以看看我写的 wiki，https://github.com/oxogenesis/oxo-chat-client/wiki，还没写完，虽然狗屁不通

[no1xsyzy]

@oxogenesis skype 是半 P2P 的（好像是就近，P2P 还是过服务器就看哪个近）（不确定后来是否有修改）
我说的 P2P 则是不包含 “发现” 的，是知道对方 IP （类比到你的系统就好像对方的名称）的情况下直接 nc 过去的情况。

[no1xsyzy]

如果丢弃，又发生一个问题，A 给 B 发消息并不一定能抵达对方，不管是对方拒绝还是不可及，但 A 却无法得知这些消息不能抵达对方，也就是好像微信不显示红叹号，但其实只有你一个人自言自语。
或者你在应用层重新实现一个回执？

[oxogenesis]

@no1xsyzy #26

私聊的回执机制在 v0.0.1 已经实现了

私聊回执机制
https://github.com/oxogenesis/oxo-chat-client/wiki/3.%E4%B8%9A%E5%8A%A1%E6%B6%88%E6%81%AF#%E8%81%8A%E5%A4%A9%E6%B6%88%E6%81%AF

聊天消息
参照公告消息，出于同步和区块链化的考虑，聊天消息也应该包含聊天消息序号和前聊天消息散列值，
另外，为了通知对方哪些消息已经接收了，增加字段 PairHash
具体如下：

Action：205
Sequence：聊天消息序号
PreHash：前聊天消息散列值
PairHash：是一个 0 到 8 个元素的数组，每个元素为一条未确认接收的对方消息的散列值
Content：聊天消息内容，为加密后的消息内容
To：聊天对方的账号地址
Timestamp
PublicKey
Signature

客户端都在线的时候，双方有来有回的情况下，可以及时确认那条消息已被接收
一方不在线时，在线方的消息现在本地存着，等都在线了，再同步

群聊准备在 v0.0.2 中按类似的原理做，但不打算实现回执

要阉割掉服务器的特权，保障个体对数据的绝对控制，这点牺牲我觉得是值得的！
现在的网络接人是很方便的，只需要保障数据一致性，应对偶发短线情况，我觉得就可以了。

[no1xsyzy]

其实你就是在类似 “ ARP 表+IP 协议” 的服务器上通过客户端实现一个 UDP 协议咯
然后应用层实现一个反向链表并进行同步。
另外，将公钥混入业务消息的意义是？ 1. 方便第三者提供自己的公钥伪装成你的对话方； 2. 通过随时更换自己的公钥让对方认不出自己是对方的对话方； 3. 只是把双方的共识再传输一遍以拖慢网络速度。

[oxogenesis]

@no1xsyzy 两个地方需要公钥
1、f(公钥）=账号地址，不是直接把公钥作为账号地址，
接收方收到消息，知道是谁发的
2、公钥时是校验签名有效性的一个参数，f （ msg,公钥，签名）=true/false
接收方收到消息，确认签名有效性，确认是谁发的

服务器用账号地址来标识每一个连接

[no1xsyzy]

@oxogenesis
1. 接受方是否提前知道公钥？
1a. 是的。
既然知道，告诉对方你已经知道对方知道的事，有什么意义吗？
1b. 不是
那么是不是任何一个人可以装作是 “那个人”？

[oxogenesis]

@oxogenesis
私聊的话，接收方需要提前将对方的账号（接近 1a ），加为好友，接收方只接收白名单内的消息。

接收的每条消息，接收方要判断这条消息签名是否有效，f(公钥)=账号，检查账号是否在白名单内。

不给公钥，没法算账号，没法确认是否在白名单啊

[no1xsyzy]

@oxogenesis 简单地说，应该验证公钥是否在白名单内，而不是账号。
参考下 Protonmail 内发邮件的实现方式吧。
一旦对方改密码导致秘钥对改变，那么也会导致收信人收到警告 “签名不被信任”，而需要导入新公钥。