HotStuff 协议的理解

发表于 | 分类于

HotStuff 协议的理解

简介

HotStuff是继 PBFT 之后 BFT 共识协议中又一里程碑。它具有更低的消息复杂度和更好的扩展性。它的优点如下：

  1. 将共识节点之间完成一轮共识的消息复杂度降低到 O(n)\mathcal{O(n)} 级别，其中 nn 表示消息的数量。与之相比，PBFT中共识节点完成一轮共识的消息复杂度是 O(n2)\mathcal{O(n^2)} 级别。
  2. 将更换主节点的消息复杂度降低到 O(n)\mathcal{O(n)} 级别。与之相比，PBFT中更换主节点的消息复杂度是 O(n3)\mathcal{O(n^3)}。

HotStuff 协议的第一个优点使得它具有更好的扩展性，即当共识组中共识节点数量线性增加时，节点间进行共识的消息复杂度仅仅是线性增加。做过分布式共识实验的都知道，当节点数量增加到 16 以上时，PBFT 协议的每秒处理交易的量（Transaction Per Second，TPS）会由比较明显的衰退，造成这一现象的主要原因是节点间通信消息的复杂度平方级上涨。但是 HotStuff 中节点数量增加时TPS 的衰减的更加缓慢一些。

HotStuff的第二个优点使得能够频繁的切换主节点，带来的好处是使得整个共识组中每个节点都能拥有排序的权力，这能打破主节点对排序权的垄断。与之相比，PBFT 协议中只有主节点出现故障时共识组才会更换主节点。

关键概念和数据结构

关键概念

HotStuff 有 3 个版本，分别使 Basic HotStuff、Chained HotStuff 以及 Event-driven HotStuff，下面分别介绍之。在介绍前，需要介绍一些关键概念。

本文将发起提议的节点称之为主节点，将其他节点称之为从节点，被排序的内容称之为命令。

数据结构

Node

一个 node 对应一个提议（proposal），主要包含如下两部分内容：

  • parent，它的前一个提议的哈希值。
  • cmd，该提议包含的命令。

QC

QC 全称为 quorum certificate，是 HotStuff 中一个重要概念，翻译为足量的证书，QC 主要包含如下数据：

  • type，该 QC 的命令类型。
  • view Number，视图编号，节点本地的视图用 CurView 表示。
  • node，我更愿意称之为提议，每个 node 包含两个内容：一条来自客户端的命令（cmd）以及它的前一个 proposal 的摘要（digest）。摘要实际上是数据的哈希值。
  • sig，由（n-f）个节点签名联合组成的一个门限签名，这个签名证明该证书被绝大多数节点认可。

QC 的主要目的是作为一个可靠证明，表示当前 QC 中包含的命令以及提议被绝大多数节点接收。因为 QC 中的 sig 有 n−fn-f 个节点的签名聚合而成，通过验证 QC 中的签名的合法性，就能知道该 QC 对应的提议是否被其他节点接受。

MSG

主节点向其他节点发送的消息被称之为 MSG，MSG 主要包含如下数据：

  • type，消息类型。
  • viewNumber，消息对应的视图编号。
  • node，消息对应的提议。
  • justify，实际其类型是一个 QC，文中将其称之为 justify。

VoteMSG

从节点向主节点的 MSG 进行投票时发送的消息，主要包含如下数据：

  • MSG，主节点发送的消息内容本身。
  • partialSig，从节点对MSG 中 type、viewNumber 和 node 部分签名。

curView

curView 表示每个节点本地的视图，它是一个局部变量，不同的节点之间的视图编号会有所不同。

⊥

⊥ 符号在 HotStuff 的论文中经常出现，表示空值的含义。

Basic HotStuff

HotStuff的主要运行过程如下图所示。其中 R0 作为 leader，负责发起共识提议，R1、R2和R3负责投票。

HotStuff

New-Veiw

HotStuff 中一轮新的共识开始，都是以主节点收集 n−fn-f 个 NEW-VIEW 消息开始。

共识开始时， R1、R2和R3向新任的主节点发送一个 new-view 消息，NEW-VIEW 消息表示其他节点即将过渡到最新的一个视图中。**NEW-VIEW **中包含一个重要的内容，即 prepared QC。 prepare QC 是节点在执行共识算法过程中生成的，后续的步骤中读者自会知晓。

当主节点至少收到 n−fn-f 个 prepare QC 后，从中选择出具有最高视图编号的 prepare QC，并以该 prepare QC 中的 node 作为父节点，并在该 node 之后创建一个新的 node，新的 node 中包含一条客户端的命令以及它的父 node 的哈希值。随后主节点将 prepare QC、node 等这些信息生成一条 PREPARE 消息中，然后将其广播给其他节点。PREPARE 消息的结构如下所示，分别表示消息的类型、视图编号、提议内容和 prepare QC。

MSG= <PREPARE,CurView, NODE, PREPARE QC>

当从节点收到一条 PREPARE 消息后，开始进行检查，主要检查如下三项内容：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 prepare，并且视图编号正确。
  2. proposal 是 prepare QC 的子节点。
  3. safeNode 检查，内容如下：
    1. proposal 是节点本地 locked QC 的子节点，安全性规则。
    2. prepare QC 的视图编号大于 locked QC 的视图编号，活性规则。

当上述三项检查全部通过时，从节点向主节点发送一条投票消息 （VoteMSG）。

与 prepare QC 相同， locked QC 也是节点在执行共识过程中生成的，后续步骤中读者自会知晓。

PRE-COMMIT

当主节点至少收到 n−fn-f 个 VoteMSG 时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type 为 commit，因而称之为 commit QC，随后主节点构建一个 PRE-COMMIT 消息，该消息内容如下：

MSG = <PRE-COMMIT, CurView,NODE = None, commitQC>

主节点将该消息广播给所有节点。

从节点收到该消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 pre-commit，并且视图编号正确。
  2. 消息中 QC 的类型为 prepare，并且其视图编号为当前视图编号。

当通过上述检查时，从节点本地记录 prepare QC = MSG.QC。

此外，从节点还会生成一个 VoteMsg 并发送给主节点，其内容如下：

VoteMSG=<MSG, partial sig>

COMMIT

当主节点收到至少 n−fn-f 个 VoteMSG 时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type为 pre-commit，因而称之为 precommit QC。随后主节点向从节点广播一条 COMMIT 消息，该消息内容如下：

MSG=<COMMIT, CurView, NODE = None, precommit QC>

当从节点收到主节点的 COMMIT 消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 commit，并且视图编号正确。
  2. 消息中 QC 的类型为 pre-commit，并且其视图编号为当前视图编号。

当通过上述检查时，从节点本地记录 locked QC = MSG.QC。

此外，从节点还会生成一个 VoteMsg 并发送给主节点,其内容如下：

VoteMSG=<MSG, partial sig>

DECIDE

当主节点收到至少 n−fn-f 个 VoteMSG时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type 为 commit QC，以内称之为 commit QC。随后主节点向从节点广播一条 DECIDE 消息，该消息内容如下：

MSG=<DECIDE, CurView, NODE = None, commit QC>

当从节点收到主节点的 DECIDE 消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 decide，并且视图编号正确。
  2. 消息中 QC 的类型为 commit，并且其视图编号为当前视图编号。

当通过上述检查时，节点开始执行 QC 中对应的 node 的命令。与此同时，节点本地的当前视图编号自增一（++curView），随后向下一任主节点发送 NEW-VIEW 消息以开启下一轮共识，它的消息内容如下：

MSG=<NEW-VIEW, curView，⊥，prepare QC>

Chained-HotStuff

可以发现，Basic HotStuff 中主节点在提议阶段主要作用是构建新的提议并选择最新的 QC，其他阶段主要作用是组合新的 QC 并广播给其他节点，那么为什么不令主节点在每个阶段都做出一个新的提议呢？基于这个思路，就产生了链式的 HotStuff，即文中的 Chained-HotStuff。在 Chained-HotStuff 中不再区分每个阶段的 QC ，而是统一称之为 Generic QC。主要运行过程按照角色划分，主要过程如下：

主节点

根据从节点的投票信息，从中选择出视图编号最大的 QC，在此 QC 之后创建一个新的提议消息并广播给其他节点，消息类型如下：

MSG=<GENERIC, CurView, NODE, GENERIC QC>

从节点

从节点收到 GENERIC 消息之后，检查如下信息：

  1. 消息类型为 GENERIC ，并且其视图编号和本地视图编号一致并且来自于对应的主节点。
  2. 使用 SAFENode 规则验证当前提议NODE 和 NODE 的父节点的正确性，如果通过，则向下一个视图的主节点发送投票消息 VOTEMSG=<MSG, partialSig>。
  3. 沿着其中的链式规则，找到一系列的提议 b->b’->b‘’->b*，进行如下验证和处理：
    1. 如果 b* 的父节点是 b“，那么记录 prepare QC = b*.justify
    2. 如果 b* 的父节点是 b“ 并且 b’‘ 是 b‘ 的父节点，那么记录 locked QC = b’.justify
    3. 如果 b* 的父节点是 b“ 并且 b’‘ 是 b‘ 的父节点并且 b 是 b‘ 的父节点，那么执行 b.justify 中的提议，并且向客户端返回执行结果。

View-Change

在等待消息期间，如果发生超时，节点本地视图 curView 自增，随后向对应的主节点发送 NEXT-VIEW 消息，内容如下：

MSG=<GENERIC, CurView, NODE=none, GENERIC QC>

说明

  1. 每个特定的视图编号下最多确认一个提议。因为当一个提议被确认时视图编号就会加一，当某个视图下没有达成共识时引起超时，此时视图继续增加一。
  2. prepare QC 表示一条命令处于准备状态，并且这个准备状态已经被绝大多数节点承认。它的主要作用在发生 view-change 时，令新任的主节点在最新的处于准备状态的命令的基础上进行提议，这样能最大化利用前任主节点的共识工作。但是由于处于准备状态，这条命令也可能会被新任主节点作废。locked QC 表示指令处于锁定状态。锁定状态表示该指令已经被锁定为下一个需要执行的指令，它一定会绝大多数节点执行。

Q&&A 环节

  1. 为什么 new-view 中使用 prepare QC 作为切换视图的依据，locked QC 可以吗？

    locked QC 是完全可以的，因为当一个 node 具有 locked QC 时，那么必然有 prepare QC，因此，使用 locked QC 也可以作为 new-view 中的根据。

  2. 在切换视图时，为什么使用 prepare QC 而没有使用 locked QC 呢？

    使用 prepare QC 能够最大化利用被替换的主节点在共识过程中做的工作。节点本地存储的locked QC 和 prepare QC 有两种可能的情况：

    1. locked QC 和 prepare QC 指向同一个提议。
    2. locked QC 指向提议 A，prepare QC 指向提议 B。此时提议 B 必然是提议A 的一个子孙提议，区别是 A已经被共识锁定，但是 B 没有被共识锁定。如果在 new-view 消息中使用 locked QC，那么新任主节点的新提议会废掉提议 A。实际上，因为 A 已经获得 prepare QC，那么在 B 的基础上继续提议是更好的选择。需要说明的是，实际上，如果主节点执意选择在 locked QC，即 A 处进行新的提议 B‘，其他节点也会接受这一提议，因为新的提议也能通过 safeNode 函数的检查。因为新的提议 B’ 也是绝大多数节点 locked QC（也就是A）的子节点。

    综上，使用 prepare QC 能够最大化利用前任主节点的共识工作。

  3. 为什么 HotStuff 中 commit 步骤之后可以达到和 PBFT 中 commit 步骤相同的作用，那么为什么 HotStuff 中还会额外增加 decide 步骤呢？

    这一步骤的作用是降低 HotStuff 中 new-view 消息的复杂度，也正是这一步骤，将 HotStuff 中更换主节点的消息复杂度降低到了 O(n) 级别。

    假设我们去掉 decide 阶段，并且令节点在 commit 阶段收到主节点的 commit 消息之后，不再继续向主节点发送 commit-vote 消息，而是直接执行该命令。

    现在考虑一种场景，假设视图编号为 v 的主节点是拜占庭节点，它将 commit 消息只发送给 f−1f-1 个节点，这 ff 个节点（主节点和 f−1f-1个节点）更新了 locked QC，并且执行 commit 消息对应的命令。

    随后出现超时， HotStuff 中节点向下一任主节点发送 NEW-VIEW 消息，每个节点发送最新的 prepare QC，其中ff个节点发送视图编号为 v 的prepare QC，n−fn-f 个节点发送视图编号为 v-1 的 prepare QC。

    新任主节点在收到 n−fn-f 个 new-view 消息后从中选择出 prepare QC 中视图编号最大的一个 QC，随后在这个 QC 后生成新的 proposal，并将其放入 PREPARE 消息广播给其他节点。需要注意的是，PREPARE 消息只包含主节点挑选的视图编号最大的 QC而并非 n−fn-f 个 QC。PREPARE消息中的 QC 到底是不是 n−fn-f 个 new-view 消息中视图编号最大的 QC 是没有办法证明的。

    从全局视角看，视图编号最大的 prepare QC 的视图编号为 v，但是主节点可以选择视图编号为 v-1 的一个 prepare QC。此时该主节点在视图编号为 v-1的QC后面提出一个新的提议，然后构建一个 PREPARE 消息（该消息的视图编号是 v+1）后广播给其他节点。其中最大prepare QC 的视图编号为 v 的ff 个节点会拒绝投票（safeNode 函数中安全规则无法通过），但是剩余的 n−fn-f 个最大视图编号为 v-1 的节点会接收这一提议。这就造成不一致，即 HotStuff 更换主节点的方法会导致 commit 阶段执行命令时会出现系统安全性问题。

    因此，解决办法有两种（任选其一）：

    1. 增加一个 decide 阶段，保证一个命令被执行前，绝大多数节点都会锁定该命令，即绝大多数的节点的 locked QC 都是该命令。在 HotStuff 中的 decide 阶段，节点收到 commit QC 时，可以确认绝大多数节点的 locked QC 都是该命令，那么就可以安全的执行该命令,这种方法的弊端是，一条命令的确认时间增加了一个round tripe。
    2. 在主节点的 PREPARE 中附带上 n−fn-f 个 prepare QC 以方便从节点验证主节点挑选出来的视图编号最大的 QC 确实是全局视角下视图编号最大的 QC，但是这种方法带来的弊端就是 PREPARE 消息的复杂度直接变为 O(n2)\mathcal{O(n^2)} 。

    在 HotStuff 中选择了第一种解决办法，因为命令确认额外增加的时间延迟，可以通过chained-HotStuff 比较好的解决。

  4. HotStuff 中的 pacemaker 具体是如何工作的？

参考资料

  1. HotStuff arxive 论文

共识协议需要确定的若干个步骤

  1. 确定新提议是什么?

  2. 发现有足够节点确定了新提议后,预先提交下一个提议(局部)

  3. 有足够多的节点预先提交了新提议,正式提交新提议(局部)

  4. 有足够多的节点正式提交新提议,确定新协议被确认(全局)

  5. L-BFT 协议为什么需要view-change?

    1. 主节点出现故障时,必须从已有的节点中选择出最新的 主节点以保证共识能够继续。

  6. view-change 时最新的 leader 应该在哪个状态的基础上再次进行共识？

    1. 假设通过投票确定最新的 leader，那么应该以投票信息中所有节点的最新状态为准，这样能够避免最新 leader 推翻前任 leader 的共识结果。
    2. 最新状态应该是可验证的，例如每个节点投票新 leader 时，将本地最新的 2f+1 个 prepare 消息发送给新的 leader。

  7. view-change 时需要注意的点

    1. view-change 的时候，一定不能回滚已经确认的共识消息。

未命名

发表于 | Edited on

主流的公链种网络构建和数据分发过程。

名称定义

共识节点：参与共识并生成新区块后扩展区块链的节点，又称之为验证节点。

全节点：不参与共识，但是会跟踪和验证账本数据并存储完整区块链数据的节点。

Aptos

Near

near.org/developers

SUI

节点发现以及入网过程

节点启动时有一个配置文件 fullnode.yaml 文件，该文件中指定节点进入 Testnet 还是 Mainnet。配置文件中还指定了种子节点的信息。例如如果进入主网时种子节点的信息为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
p2p-config:
  seed-peers:
    - address: /dns/icn-00.mainnet.sui.io/udp/8084
      peer-id: 303f1f35afc9a6f82f8d21724f44e1245f4d8eca0806713a07c525dadda95a66
    - address: /dns/icn-01.mainnet.sui.io/udp/8084
      peer-id: cb7ce193cf7a41e9cc2f99e65dd1487b6314a57c74be42cc8c9225b203301812
    - address: /dns/mel-00.mainnet.sui.io/udp/8084
      peer-id: d32b55bdf1737ec415df8c88b3bf91e194b59ee3127e3f38ea46fd88ba2e7849
    - address: /dns/mel-01.mainnet.sui.io/udp/8084
      peer-id: bbf3be337fc16614a1953da83db729abfdc40596e197f36fe408574f7c9b780e
    - address: /dns/ewr-00.mainnet.sui.io/udp/8084
      peer-id: c7bf6cb93ca8fdda655c47ebb85ace28e6931464564332bf63e27e90199c50ee
    - address: /dns/ewr-01.mainnet.sui.io/udp/8084
      peer-id: 3227f8a05f0faa1a197c075d31135a366a1c6f3d4872cb8af66c14dea3e0eb66
    - address: /dns/sjc-00.mainnet.sui.io/udp/8084
      peer-id: 6f0b25087cd6b2fd2e4329bcf308ac95a37c49277dd7286b72470c124809db5b
    - address: /dns/sjc-01.mainnet.sui.io/udp/8084
      peer-id: af1d5d8468b3612ac2b6ff3ca91e99a71390dbe5b83dea9f6ae2da708d689227
    - address: /dns/lhr-00.mainnet.sui.io/udp/8084
      peer-id: c619a5e0f8f36eac45118c1f8bda28f0f508e2839042781f1d4a9818043f732c
    - address: /dns/lhr-01.mainnet.sui.io/udp/8084
      peer-id: 53dcedf250f73b1ec83250614498947db00d17c0181020fcdb7b6db12afbc175

SUI 中全节点入网时，每个从 seed 节点处获取网络中的节点，然后从中随机选择一些节点建立连接，基于这种方式进入网络。

数据同步

文件源码位置：sui/crates/sui-network/src/state_sync/mod.rs at main · MystenLabs/sui · GitHub

数据类型：checkpoint 、transactions。

当共识层的 validator 产生一个 checkpoint 之后，调用 send_checkpoint 方法将最新状态发送给其他节点。

其他节点收到新的 checkpoint 之后，存储该信息后调用 spawn_notify_peers_of_checkpoint 函数将该信息通知给其他节点。通知的内容为 PeerStateSyncInfo，其结构如下。可以发现其中只包含 checkpoint 的摘要，最低的区块高度和最高的区块高度，但是并不包含 checkpoint 本身。

1
2
3
4
5
6
7
8
9
10
11
12
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
struct PeerStateSyncInfo {
    /// The digest of the Peer's genesis checkpoint.
    genesis_checkpoint_digest: CheckpointDigest,
    /// Indicates if this Peer is on the same chain as us.
    on_same_chain_as_us: bool,
    /// Highest checkpoint sequence number we know of for this Peer.
    height: CheckpointSequenceNumber,
    /// lowest available checkpoint watermark for this Peer.
    /// This defaults to 0 for now.
    lowest: CheckpointSequenceNumber,
}

当一个节点收到其他节点最新 checkpoint 的消息时，检查其高度是否高于自身，如果高于自身高度，则开启状态同步过程。

此外，每个节点定期与邻居同步最新的 checkpoint 消息，如果发现自身落后，则请求区块。

Solana

Reference: Synchronization | Solana Docs

未命名

发表于 | Edited on

layout: checking
title: Byzantine Ordered Consensus without Byzantine Oligarchy
date: 2023-6-14 15:03:13
tags: 共识
categories: 区块链技术研究

Byzantine Ordered Consensus without Byzantine Oligarchy

论文地址: OSDI

Q1 论文试图解决什么问题？

In the permissioned blockchains that rely on Byzantine fault tolerant (BFT) SMR, however, nodes have a stake in the specific sequence that ledger records, as well as in preventing other parties from manipulating the sequencing to their advantage. The traditional specification of SMR correctness, however, has no language to express these concerns.
This paper introduces Byzantine ordered consensus, a new primitive that augments the correctness specification of BFT SMR to include specific guarantees on the total orders it produces; and a new architecture for BFT SMR.

Q2 这是否是一个新的问题？

是。

Q3 这篇文章要验证一个什么科学假设？

Q4 有哪些相关研究？如何归类？谁是这一课题在领域内值得关注的研究员？

Q5 论文中提到的解决方案之关键是什么？

Q6 论文中的实验是如何设计的？

Q7 用于定量评估的数据集是什么？代码有没有开源？

Q8 论文中的实验及结果有没有很好地支持需要验证的科学假设？

Q9 这篇论文到底有什么贡献？

Q10 下一步呢？有什么工作可以继续深入？

GossipSub-Attack-Resilient Message Propagation in the Filecoin and ETH2.0 Networks

发表于 | Edited on | 分类于

GossipSub: Attack-Resilient Message Propagation in the Filecoin and ETH2.0 Networks

GossipSub 的组成

在 GossipSub 论文中，它由两部分内容构成：构建网格网络（mesh construction）和评分函数（score function）。其中网格网络主要用于构建快速、资源利用率高、扩展性好的数据传输网络。score function 使得节点拥有抵抗恶意行为的能力。

构建网格

每个节点都会选择一部分邻居节点并与之构成局部网格（local mesh）。所有节点的局部网格的并集构成了全局网格（global mesh）。当一个节点转发一条消息时，只会将消息转发给至局部网格，接收节点也会将消息继续转发给它的局部网格。需要注意的是，并不是每个节点都需要构建局部网格，因为节点仍然可以通过 gossip 协议请求缺失的数据。

每个节点局部网格节点的数量（也称之为度数） $D$，即该协议的放大因子。局部网格的初始构建根据节点发现机制进行。$D$ 的取值介于 $D{low}$ 和 $D{high}$ 之间。当节点网格的度数超过 $D{high}$ 时，该节点处于过度订阅（over-subscribed）的状态，并且需要在网格中剪除一些节点。当节点网格的度数超过 $D{low}$ 时，该节点处于低订阅（under-subscribed）的状态，需要将新节点加入到网格中。

在将新节点加入网格中时，需要对节点进行筛选，其中 $D_{score}$ 专门用于对每个节点进行排序。

另外一个相关的概念是 $D_{out}$ ，它表示节点主动建立的连接数，这个主要是用于防止节点受到日食攻击。

GossipSub 消息类型

  • GRAFT：发送方告知接收方被纳入发送方的网格中。
  • PRUNE：发送方告知接收方被剔除发送方的网格中。
  • PRUNE-Peer Exchange (PX)：发送方向接收方发送一些网格节点以帮助接收方构建自己的网格。
  • IHAVE：gossip 消息，发送方告知接收方一些可以获取的数据。
  • IWANT：gossip 消息，发送方根据接收方的 IHVAE 消息请求数据。
  • heartbeat：心跳消息，用于维护 mesh 和 gossip 消息，1 秒 1 次。

通过消息类型可知，节点向局部网格发送消息时，直接发送消息内容本身。如果是向非网格节点发送，则会发送 IHAVE 消息。

Gossip 过程

节点 Gossip 的时候，随机选择一些节点。选择的节点可能是网格节点，也有可能不是。

Gossip 通过心跳发送，节点存储在 1 秒内所有见过的消息，然后通过心跳包发送给其他节点。

当前 GossipSub 中，gossip 的内容通过 3 轮次连续的 heartbeat 消息发出去的。每次 gossip 的时候，只选择一部分节点进行 gossip，经过 3 轮的 gossip使得所有节点都能拿到数据。为什么这么设计？文章后续有交代。

Score 函数

其中 $TC$ 表示 TopicCap，具体概念文中没有做解释。$t_i$ 表示话题权重。下文参数的介绍是基于个人理解，本章中实际上介绍不是很清楚。

  • $P_1$: 网格中的存在时间。
  • $P_2$: 第一条消息的发送量。
  • $P_{3a}$: 网格消息发送率，即网格内节点在一定时间窗口内提交的消息量。
  • $P_{3b}$: 网格消息发送失败率。即网格中节点没有成功发送的消息数量。
  • $P_4$: 非法消息数，用于惩罚发送非发消息的恶意节点。
  • $P_5$: 特定应用的分数。
  • $P_6$: 同一 IP 地址连接的数量，避免女巫攻击。

同步、半同步、异步的概念

发表于 | Edited on | 分类于

同步、半同步、异步的理解

同步、半同步、异步定义一

  • 同步是指节点之间的延迟存在一个已知的 Δt 上界
  • 半同步是指节点之间的延迟存在一个 Δt 的上界，但是不知道上界是多少，但是消息一定会传送到。
  • 异步只保证最终消息可达，对传输时间的上限没有假设。

同步、半同步、异步定义二

  • 同步（synchronous）网络假设网络中的消息能够在一个已知的时间 Δ 内到达，这是一种非常理想的假设，实际的工程实践中很难保证这一假设成立。
  • 半同步（partially synchronous）网络假设在一个 GST（global stabilization time）事件之后，消息在 Δ 时间内到达。随着网络技术的发展，这种假设已经能符合我们生活中遇到多绝大多数网络情况，而且设计和实现这类协议的难度不高，因此很多常见的协议比如 Paxos、Raft、PBFT 等都是基于半同步网络假设设计的共识协议。这些协议虽然能够保证在任何网络情况下系统的一致性，但在异步网络下会丧失活性。
  • 异步（Asynchronous）网络只保证消息最终能到达，并没有到达时间的限制，这几乎涵盖所有网络情况。由此可见，异步 BFT 协议的鲁棒性最强，即使在极端网络条件下协议也不会丧失活性。

比特币为什么是同步协议

同步和半同步的区别在于，同步假设下，超过设定的时间，系统安全性会丧失。半同步假设下，超时之后系统安全性不会丧失。

在比特币系统中，如果节点 10 分钟内无法收到新区块，那么整个网络有很大的风险会出现分叉，当网络出现分叉时，系统的安全性已经受到威胁，因此，比特币可以理解为同步协议。

CAP 理论

一个分布式系统中，Consistency、Availability、Partition tolerance 无法同时获得。

  • 一致性（Consistency）：任何事务应该都是原子的，所有副本上的状态都是事务成功提交后的结果，并保持强一致；
  • 可用性（Availability）：系统（非失败节点）能在有限时间内完成对操作请求的应答；
  • 分区容忍性（Partition）：系统中的网络可能发生分区故障（成为多个子网，甚至出现节点上线和下线），即节点之间的通信无法保障。而网络故障不应该影响到系统正常服务。

CAP 原理认为，分布式系统最多只能保证三项特性中的两项特性。

FLP 不可能原理

FLP 不可能原理：在网络可靠、但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。

参考

Consensus: Bridging Theory and Practice (stanford.edu)

FLP 不可能原理 - 区块链技术指南 (gitbook.io)

[Synchrony, Asynchrony and Partial synchrony](Synchrony, Asynchrony and Partial synchrony (decentralizedthoughts.github.io))

[共识问题之三：拜占庭容错（BFT）共识算法的发展历程](共识问题之三：拜占庭容错（BFT）共识算法的发展历程 - 知乎 (zhihu.com))

ssh 远程登录和拷贝

发表于 | 分类于

SSH 远程登录+远程拷贝

远程登录方法：

1
ssh 用户名@ip地址 -p 端口号

例如： ssh zxhu@192.168.1.1 -p 22 , 然后输入密码。

将本地的文件拷贝到远程：

1
2
scp -P 22 -r 本地文件路径 用户名@ip地址:远程目录
scp -P 22 -r ./bitcoinSource/ zxhu@192.168.1.1:/home/zxhu

将远程文件拷贝到本地：

1
2
scp -P 22 -r 用户名@ip地址:远程目录 本地文件路径
scp -P 22 -r zxhu@10.0.0.47:/usr/local/sin.sh ~/tmp/

如果是传输的文件夹，加上-r选项表示递归拷贝，文件夹中内容一起拷贝。

Rust 实现 tcp 服务器和客户端

发表于 | 分类于

Rust 实现 tcp 服务器和客户端

服务器端代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
by hzx 2020-08-01
一个简易的echo tcp server实现
*/

use std::io::{Error, Read, Write};
use std::net::{Shutdown, TcpListener, TcpStream};
use std::str;
use std::thread;
use std::time;

/// 该函数处理接入的连接
fn handle_client(mut stream: TcpStream) -> Result<(), Error> {
    // 512字节的缓冲区读取数据
    let mut buf = [0; 512];
    // 设置read函数超时时间为60秒
    stream
        .set_read_timeout(Some(time::Duration::from_secs(60 as u64)))
        .expect("set_read_timeout call failed");
    // 获取远程节点的ip地址和端口号
    let addr = stream.peer_addr().unwrap();

    // 打印远程节点的ip地址和端口号
    println!("accept a new connection from {}", addr);

    // loop无限循环，直到read函数超时或者远程客户端关闭连接
    loop {

        // 以阻塞模式尝试从stea中接收数据
        let res = stream.read(&mut buf);

        // match语句判定读取结果
        match res {
            // 读取数据成功
            Ok(bytes_read) => {
                // 如果读取数据长度大于0
                if bytes_read > 0 {
                    // 输出远程客户端ip地址、端口号以及接收的数据
                    println!(
                        "{}: {}",
                        addr,
                        str::from_utf8(&buf[..bytes_read])
                            .expect("Could not write buffer as string")
                    );
                    // echo 服务器将原数据返回
                    stream.write(&buf[..bytes_read])?;
                }
            }
            // 读取过程出现错误
            Err(e) => {
                // 打印错误
                println!("{}, error: {:?}", addr, e);

                // 跳出loop循环
                break;
            }
        }
        // 线程休息100毫秒
        thread::sleep(time::Duration::from_millis(100 as u64));
    }
    // 关闭连接
    stream
        .shutdown(Shutdown::Both)
        .expect("shutdown call failed");
    // 返回
    return Ok(());
}

fn main() -> std::io::Result<()> {
    // 创建一个TcpListener并绑定至本地8080端口
    let listener = TcpListener::bind("127.0.0.1:8080").expect("bind error");
    // 创建一个线程Vec管理线程
    let mut thread_vec: Vec<thread::JoinHandle<()>> = Vec::new();

    // 持续监听
    for stream in listener.incoming() {
        // 获取监听到的TcpStream，否则报错。
        let stream = stream.expect("failed!");

        // 创建一个新的线程并返回线程句柄
        let handle = thread::spawn(move || {
            handle_client(stream).unwrap_or_else(|error| eprintln!("{:?}", error));
        });
        // 将该线程句柄放入thread_vec中
        thread_vec.push(handle);
    }

    // 遍历thread_vec中所有线程，等待线程执行完毕
    for handle in thread_vec {
        handle.join().unwrap();
    }
    // 返回结果
    Ok(())
}

客户端代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
by hzx 2020-08-01
一个简易的echo tcp client 实现
*/

use std::io::{self, prelude::*, BufReader, Write};
use std::net::{Shutdown, TcpStream};
use std::str;
use std::thread;
use std::time;

fn main() -> std::io::Result<()> {
    // 创建TcpStream并尝试与服务器建立连接
    let mut stream = TcpStream::connect("127.0.0.1:8080")?;
    // 设置60秒读取数据超时时间
    stream
        .set_read_timeout(Some(time::Duration::from_secs(60 as u64)))
        .expect("set_read_timeout call failed");

    // 从标准输入中持续读取数据
    loop {
        // 新建字符串input
        let mut input = String::new();
        //
        // 从标准输入中读取数据
        io::stdin()
            .read_line(&mut input)
            .expect("Failed to read from stdin");
        // 如果input数据为exit，则退出程序
        if input.trim() == String::from("exit") {
            break;
        }

        // 向服务器发送数据
        stream
            .write(input.as_bytes())
            .expect("Failed to write to stream");
        // 使用BufReader读取stream中的数据
        let mut reader = BufReader::new(&stream);
        // buffer存储全部数据
        let mut buffer: Vec<u8> = Vec::new();
        // 尝试读取数据
        let res = reader.read_until(b'\n', &mut buffer);
        // 模式匹配数据
        match res {
            // 读取数据成功
            Ok(bytes_read) => {
                if bytes_read > 0 {
                    // 输出数据
                    println!(
                        "echo: {}",
                        str::from_utf8(&buffer).expect("Could not write buffer as string")
                    );
                }
            }
            // 读取数据失败
            Err(e) => {
                // 打印错误
                eprintln!("occur error {:?}", e);
                // 退出循环
                break;
            }
        }
        // 睡眠100ms
        thread::sleep(time::Duration::from_millis(100 as u64));
    }
    // 输出退出信息
    println!("we are going to shutdown the connection");
    // 关闭连接
    stream.shutdown(Shutdown::Both).expect("shutdown error");
    Ok(())
}

RAFT 共识协议

发表于 | 分类于

相比 PBFT 协议，RAFT 协议是一种容忍CFT(Crash Fault Tolerance)类型的协议，即不考虑节点之间存在作恶的情况。RAFT 协议中主要包括 leader、follower、candidate 三个角色，下面按照协议的运行方式，首先从如何选取 Leader 这一步骤开始讲起。

Leader 选择

Raft 协议中使用心跳(heartbeat) 的机制触发 leader 选择。当服务器集群启动时，所有的节点都以 follower 的身份启动。当一个节点启动时，首先随机在 150ms~300ms 之间选定一个超时时间，然后等待 leader 发送的 heartbeat。Leader 节点应该定时的向所有的 follower 节点发送 heartbeat 节点以证明自己处于存活状态。如果一个 follower 节点在其超时的时间间隔内还是没有收到 heartbeat，则称之为 election timeout(选举超时)。此时该 follower 假定 leader 可能出错，此时进入 leader 选举阶段。

进入选举阶段，一个 follower 将自己当前的 term(类似于PBFT 协议中的 view) 增加 1，然后切换为 candidate 身份。随后节点向自己投一票，同时向其他 follower 节点发送 RequestVote RPC 以请求它们向该节点投票。在等待其他节点的投票期间，这个节点一只保持自己 candidate 的身份，但是，如果下列三件事情发生，其身份会发生变化：

  1. 该节点在本轮投票赢得选举。

  2. 该节点在本轮选举期间收到来自 leader 的消息。

  3. 选举超时，没有选出 leader。

一个 candidate 如果能得到大部分节点的选票，那么就能成为 leader。当一个candidate 成为 leader 后，就会立刻向其他 follower 发送 heartbeat 消息以告知自己的 leader 身份以防止其他节点再次进行选举。

节点在向 candidate 投票时，Raft 协议规定在一个 term 只能给一个节点投票，一般按照先来先投票的原则。而成为 leader 的必须收到大多数节点的投票，获得过半票数的设计保证一个 term 最多产生一名 leader。

当一个节点是 candidate 时，如果收到其他节点自称 leader 的消息，则检查消息中的 term，如果leader 的 term 大于等于本节点的 term，则认同发送节点的 leader 身份，并且转至 follower 身份，否则该节点继续保持自己 candidate 的身份。

一个节点可能在一个 term 情况下，没有选举成功，但是也没有选举失败，这是因为多个 candidate 在本次 term 中对票数进行分流。为了解决这个问题，raft 采用随机选举超时的机制，即一个节点如果 candidate 失败之后，再次随机选择一个超时时间，如果这段时间内没有收到新的 leader 的 heartbeat，那么继续保持自己 candidate 身份并继续参加选举。

日志复制(Log Replication)

当一个节点成为一个 leader 之后，它便开始处理客户端的 request，每一个 request 都包含一条需要被执行的命令。当 leader 收到一个 request 时，leader 便将该命令当做一个新的 entry 放入到 log 中，随后将这条命令也告知其他 follower。当一个 entry 被安全地复制后，leader 将执行这一条 entry 并且将执行结果反馈给 client。

log 的组织形式如下图所示，log 中的每一个 entry 都包含其对应的 term 、命令以及在 log 中的索引。log 中的 term 用来判检测log 的不一致问题。

leader 用来决策一个 entry 是否要被执行，而一条 entry 被执行前必须首先被 commit。一个 entry 被 commit 的前提是，leader 已经确保这一条 entry 已经被大多数的 follower 收到。当一条 entry 被 commit 之后，这个 entry 之前的所有 entry 也会被 commit。Raft 保证 commit 之后的 entry 是持久化的，并且最终会被所有的状态机执行。

image-20220123191025495

Raft 中如何根据每一条log 的 index 和 term 来确认 log 的一致性呢？其规则如下：

  • 如果两个不同 log 中的两个 entry 分别具有相同的 index 和 term，那么这两条 entry 肯定相同。
  • 如果不同两个 log 的两个 entry 具有相同的 index 和 term，那么它们之前的所有 entry 也是相同的。

上述第一个规则正确的原因是，对于一个给定的 index，一个 leader 在一个 term 中最多创建一个 entry。

上述第二个规则正确的原因是，每个 leader 发送 log entry 时，每个 entry 都包含其在 leader 的 log 中的 index 和term，follower 将该 entry 放入自己的 log 之后，检查该 entry 的 term 和 index 是否和 leader 的 term 和 index 一致，如果不一致，follower 会拒绝该消息，并且请求重新复制 leader 的 log 。通过这样的措施， follower 的 log 必然可以和 leader 的 log 保持一致。

在 Raft 中，由于网络原因，leader 和 follower 的 log 消息肯定会出现不一致，有可能 leader 的 log 远远多于 follower 的 log ，或者 follower 的 log 比 leader 的还要多。而 Raft 协议中，始终让 follower 复制 leader 的 log 使得 follower 的 log 和 leader 的 log 保持一致，即如果 follower 的 log 和 leader 的log 不一致，那么 follower 的 log 会被重写。

为了维护 log 中的一致性，每个 leader 会为每一个 follower 维护一个变量 nextIndex，这个变量维护了下一次要发送给 follower 的 log 的 index。当一个节点刚刚成为 leader 时，每个 follower 的 nextIndex 会被设置为 leader 节点最后一条日志的后面一个位置。随后 leader 分别向每一个 follower 发送 nextIndex 指向的 log。 如果 follower 收到的 nextIndex 指向的 log 和本地的 log 不同，则 follower 会拒绝该消息，随后 leader 需要在通信过程中发现两者 log 最后一个匹配的位置，随后 follower 才会接受 leader 的 entry。

安全性说明

python 获取文件路径-文件名-后缀名

发表于 | 分类于

Python 获取文件路径-文件名-后缀名

1
2
3
4
5
import os
file_dir = "/home2/zxhu/bitcoin-0.19.0_hzx/backup2/2020-07-20_compactBlockValidation.log"
file_path, file_name = os.path.split(dir)
file_name, extend_name = os.path.splitext(file_name)

运行结果如下：

获取当前路径下目录，代码如下：

1
2
3
4
5
6
import os
os.getcwd() #获取当前工作目录路径
os.path.abspath('.') #获取当前工作目录路径
os.path.abspath('test.txt') #获取当前目录文件下的工作目录路径
os.path.abspath('..') #获取当前工作的父目录 ！注意是父目录路径
os.path.abspath(os.curdir) #获取当前工作目录路径

Manacher(马拉车) 算法

发表于 | 分类于

Manacher算法

求解一个字符串s中的最长子串，一般的方法是，遍历s中每个字符e，以字符e为回文中心，向两边拓展，求以字符e为回文中心的最长回文串的长度，这样的方法时间复杂度为O(n2)O(n^2)。鉴于其复杂度，出现了Manacher’s Algorithm，中文名叫马拉车算法，是一位名叫Manacher的人在1975年提出的一种算法。该算法可以在O(n)O(n)时间复杂度内求解一个字符串中的最长回文子串，也可以求解一个字符串中回文子串的总数。

方法

1. 预处理

由于回文串分为偶回文（比如 bccb）和奇回文（比如 bcacb），处理过程中需要考虑不同的情况，于是Manacher算法对字符串进行了预处理，过程如下：

  1. 在所有的相邻字符中间插入 #，例如字符串ab，添加#变为 #a#b#。
  2. 字符的首尾加入两个不同的字符，例如 ？和 ! , s成为 ?#a#b#!。

预处理好处是，如果从#开始拓展回文字符串，那么得到回文子串对应 s 中的偶回文。如果非#的字符开始拓展，找到的回文字符串对应 s 中的奇回文，在处理的过程中不用考虑奇回文还是偶回文的问题，以任意一个字符为回文中心，既可以包含原来的奇数长度的情况，也可以包含原来偶数长度的情况。并且这种处理方式的特点是，对处理后的字符串，以每一个字符为回文中心进行拓展，每次拓展得到的回文数的首尾一定是#，并且其长度是奇数。预处理后可以进入求解过程。

2. 求解

假设原字符串为 s， 预处理后的字符串为T。

  1. 定义一个辅助数组f，f[i]表示T中以字符T[i]为回文中心的最长回文半径，例如#c#a#c#，以字符a为回文字符串的最长半径为 4。f[i] - 1是s中以T[i]为回文中心的最大回文串长度，该问题的证明见推论1及其证明。

  2. Manacher 算法依旧需要枚举 T 的每一个字符并先假设它是回文中心，但是它会利用已经计算出来的状态来更新$ f(i)。假设我们已经计算好了。假设我们已经计算好了[1, i-1]$区间内所有点的 ff（即我们知道[1,i−1][1, i-1] 这些点作为回文中心时候的最大半径）， 那么我们求出[1,i−1][1, i-1]范围内字符拓展出的最长回文字符串的右端点。

  3. 例如 i = 4 的时候 f(i) = 5，说明以第 4 个元素为回文中心，最大能拓展到的回文半径是 5，此时对应最长回文字符串的右端点的索引为 4 + 5 - 1 = 8。所以我们可以根据 i以及f(i)时，可以很容易得到它的右端点为$ i + f(i) - 1$。

  4. 已知[1,i−1][1, i-1]范围的 f 求解f(i)时，Manacher 算法要求我们维护[1,i−1][1, i-1]范围内每个字符最长回文字符串的右端点的最大值rm， 以及该字符串的回文中心im。

  5. 整个过程如下：初始时令 im = 0， rm = 0，遍历T中[0, T.size()-1]范围内每个 i ：

    1. 初始化f(i)
      1. 如果$ i ≤ rm说明被包含在[0,i−1]范围内某个字符的最长回文子串中，假设j是i这个最大回文字符串回文中心im的对称位置,经过Manacher算法处理的最长回文字符串始终是奇数，因此说明被包含在[0, i-1]范围内某个字符的最长回文子串中，假设 j 是 i 这个最大回文字符串回文中心 im 的对称位置, 经过Manacher算法处理的最长回文字符串始终是奇数，因此 j + i = 2 \times im,于是我们令, 于是我们令f(i) = min(f(j), rm-i+1)$,这一步骤为什么取最小值的原因，见推论2及其证明。
      2. 初始化 f(i)=1f(i)=1f(i) = 1f(i)=1。
    2. 中心拓展
      1. 做完初始化之后，因为 i+f(i)−1i + f(i)-1 是T[i]字符最长回文字符串的右端点，所以可以保证 T[i+f(i)−1]=T[i−f(i)+1]T[i + f(i) - 1] = T[i - f(i) + 1]，要继续拓展这个区间，我们就要继续判断 T[i+f(i)]T[i + f(i)]和 T[i−f(i)]T[i - f(i)] 是否相等，如果相等则将 f(i)f(i) 自增；这样循环直到 $s[i + f(i)] \neq s[i - f(i)] $。
      2. 遍历结束后如果 i+f(i)−1>rmi + f(i)-1 > rm, 则更新 $ rm = i + f(i)-1, im = i$。
      3. 可以看出循环每次结束时都能保证 T[i+f(i)−1]=T[i−f(i)+1]T[i + f(i) - 1] = T[i - f(i) + 1]，而循环继续（即可拓展的条件）一定是 T[i+f(i)]=T[i−f(i)]T[i + f(i)] = T[i - f(i)]。 这个时候需要注意不能让下标越界，但是Manacher方法中在字符串的开头加一个 ?，并在结尾加一个 !，这样开头和结尾的两个字符一定不相等，就可以保证每次f(i)f(i)自增的时候不会越界。

证明

推论1

  • f[i]表示T中以字符T[i]为回文中心的最长回文字符串的半径， f[i] - 1是s中以T[i]为回文中心的最大回文串长度。

证明

假设原字符串中，第i个字符最大回文串长度为L，经过马拉车算法处理后的回文字符串长度增加了L+1，总长度为2L+1.已知在处理后的字符串中，第i个字符的最大回文半径为f(i), 则其回文字符串长度为2*f(i)-1 = 2L+1, 由此可知 L = f(i)-1。

推论2

  • f(i)=min(f(j),rm−i+1)f(i) = min(f(j), rm-i+1)

证明

                                ---X----j---------Im---------i------rm---

上图中，以im为中心的最长回文字符串的右端端点为rm, 如果i<=rm，说明 i 被包含在im为中心的最长回文字符串中，假设j是最长回文字符串中i在左侧的对称位置，再假设X是最长回文串rm对应的最左端断点，其中X<=j，已知以j为中心的回文字符串长度为f(j), f(i)的初始化分下列两种情况：

  • case 1： 如下图所示， 如果j的最长回文串的最左侧端点y不在X的左侧(在右侧或者与X重合)，说明y也包含在i的最长回文字符串中，根据i和j的对应关系可知f(i)>=f(j)f(i) >= f(j)，并且f(j)<=rm−i+1f(j) <= rm -i+1, 因此把f(i)初始化为f(j)。

                                ---X--y--j--y------Im-------y--i--y----rm---

  • case 2： 如下图所示，如果j为中心的最长回文串的最左侧端点在X左侧，说明y不在i的最长回文字符串中，此时rm−i+1<f(j)rm-i+1 < f(j), 根据i和j的对应关系，我们最多可知f(i)f(i) 的长度至少为rm−i+1rm -i +1,因此把f(i)f(i)初始化为rm−i+1rm-i+1。

                                   -y--X----j--------Im---------i------rm---

综合case1 和case2， f(i)的长度最大不应该超过rm-i+1, 因此$f(i) = min(f(j), rm−i+1rm -i +1)$;

示例代码

下列代码求解一个给定字符串中回文字符串的总数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int manacher(string s) {
        string mlcStr;
        mlcStr.reserve(s.size()*2+3);
        // 预处理
        mlcStr.push_back('S');
        mlcStr.push_back('#');
        for(const auto& e: s){
            mlcStr.push_back(e);
            mlcStr.push_back('#');
        }
        mlcStr.push_back('!');
		// 定义f，遍历mlcStr并求解,将遍历范围控制在[1, mlcStr.size()-1]，排除了？和！，保证数组不会越界
        vector<int> f(mlcStr.size(), 1);
        int im = 0, rm = 0, res = 0;
        for(int i = 1; i < mlcStr.size()-1; ++i){
            // 初始化f[i]
            if(i <= rm)
                f[i] = min(rm - i + 1, f[2*im - i]);
            // 中心拓展
            while(mlcStr[i+f[i]] == mlcStr[i-f[i]]) f[i]++;
            // 更新rm和im
            if( i + f[i]-1 > rm){
                rm = i+f[i]-1;
                im = i;
            }
            // 求和
            res += f[i]/2;
        }
        return res;
    }

复杂度分析

从实现代码来看，由于有两层循环，看起来貌似是O(n2)O(n^2)级别，但是实际上:

  • 如果每次f(j)f(j)的值不等于rm−i+1rm - i + 1的时候，i的最长回文字符串都无法更新，如果可以更新，根据回文字符串可以推出矛盾，这种情况下rm和im不会更新。

  • 如果f(j)==rm−i+1f(j) == rm - i + 1，此时以T[i]为回文中心的最长回文字符串有可能更新，而rm只能增大不会减小，rm最多更新T.size()次。

  • 假设原来s长度为L，那么预处理后T变为2L+12L+1次(除去头尾添加的字符，因为实际遍历过程中排除了这两个字符)，rm最多更新2L+12L+1次，于是整个字符串的便利操作和和中心拓展最多为2L+1+2L+1=4L+22L+1+2L+1 = 4L+2次，因此其时间复杂度为O(n)O(n)，平均访问次数为(4L+2)÷L=4(4L+2)\div L = 4次。

  • 由于使用了额外的空间，其空间复杂度为O(n)O(n)。

  • 如果想看更加详细的证明，可以参看这里。

  • 力扣题目链接：回文子串