一个算法问题

[oxogenesis]

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

问题描述：

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

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

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

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

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

[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 内发邮件的实现方式吧。
一旦对方改密码导致秘钥对改变，那么也会导致收信人收到警告 “签名不被信任”，而需要导入新公钥。