git 常用命令

2020-08-14 11:16:16 星期五

用户设置

修改用户名和邮箱地址命令如下，其中引号不能省略。

• git config --global user.name “xxxx”
• git config --global user.email “xxxx”

查看用户名和邮箱

• git config user.name
• git config user.email

远程相关

查看远程pull和push的地址

• git remote -v

添加远程仓库地址

• git remote add origin https://github.com/hzxGoForward/bitcoin-hzx.git

修改远程仓库地址

• git remote set-url origin https://github.com/hzxGoForward/bitcoin-hzx.git

将当前分支推送到远程分支

• git push origin 分支名

拉取并合并远程分支

• git pull origin 分支名

推送本地分支至远程分支

• git push origin 分支名

当前分支与远程分支关联

• git branch --set-upstream-to=origin/dev

创建分支并与远程分支关联

• git branch 分支名 origin/分支名

将本地内容推送到远程分支

• git push origin/分支名

查看当前分支与远程分支关联关系

• git branch -vv

删除远程分支

• git push origin --delete 分支名

分支相关

创建分支

• git branch 分支名

切换分支

• git checkout 分支名

创建一个新的分支并切换到该分支

• git checkout -b 分支名

• 删除本地分支

• git branch -d 分支名

提交内容

修改内容转移到新分支——方法一

1. git stash
2. git checkout -b 分支名
3. git stash pop

修改内容转移到新分支——方法二

1. git add .
2. git checkout -b 分支名
3. git commit -m “msg”

将修改存储至暂存区

• git add src/net_processing.cpp
• git add.

放弃对某个文件的修改

• git checkout – src/net_processing.cpp
• git checkout – .

提交修改

• git commit -m “修改说明”

.gitignore

忽略*.o和*.a文件

• *.[oa]

忽略dbg文件和dgb目录

• dbg

忽略dbg目录

• /dbg

只忽略dbg文件，不忽略dbg目录 !表示不忽略

• dbg
• !dbg/

Git中.gitignore文件不起作用的解决办法：

1. 修改gitignore文件
2. git rm -r --cached .
3. git add .
4. git commit -m ‘update .gitignore’
5. 再进行push操作

NKN

NKN（New Kind of Network） 是 2018年和 IPFS 一起产生的项目，IPFS 致力于构造一个去中心化存储层，而 NKN 致力于构建一个去中心化网络层。

NKN 的白皮书中介绍了它的若干特殊概念。

1. Cellular Automata powered DDTN（元胞自动机驱动的去中心化数据传输网络）。
2. Cullular Automata driven consensus (元胞自动机驱动的共识)。
3. Proof of Relay（传输证明）。
4. Tokenization of network connectivity and data transmission capability（代币化网络连接和数据传输）

下文对一些重要概念进行介绍。

Cellular Automata (CA)

根据 NKN 白皮书介绍，CA 是一群节点构成的一个状态机，每个节点都根据局部规则改变自身的状态，局部规则依赖于其邻居节点。

每个节点在改变的时候，将变化传递给邻居节点，最终其变化信息也会传递至 CA 中的所有节点，使得 CA 进行演进。元胞自动机是一个离散的的系统状态，其定义为：

$$CA = (S, N, K, f)$$

其中，$S$ 表示节点当前状态；$N$ 表示网络中节点数；$K$ 表示邻居节点集合； $f$ 表示状态转换函数。

元胞自动机的系统状态从初始状态开始演进，每个节点根据自身和邻居节点的状态进行改变，全局状态由所有节点的局部状态决定，并相应的演进。

元胞自动机中最重要的状态转移函数 $f$ ，具体指代的是网络拓扑更新规则。

Decentralized Data Transmission Network（DDTN）

NKN 引入了去中心化数据传输网络（DDTN）的概念。DDTN 将独立和自组织的转发节点组织起来为客户端提供连通性和数据传输能力。这些节点以无需信任的去中心化的方式协调，并且使用代币激励节点共享网络资源。

总体评价

1. 看起来引入了元包自动机这个高大上的概念，实际上没有什么实质性内容。例如，使用介绍元胞自动机构成的网络中，每个节点的网络拓扑更新规则到底是什么？整个文档自始至终都没交代，为什么使用元胞自动机就能比一般的网络构建方式更加去中心化？元胞自动机构建的网络如何保证效率性？
2. 参考文献的引用方式很混乱，Cellular Aotomata 的概念第一次出现的时候，完全没有写引用，后面介绍了很多的时候，突然来一大堆引用，这种引用方式很不正式。
3. 白皮书里面把很多重要的技术细节指向了黄皮书，然而截止现在2023年3月27日，黄皮书在网络上仍然找不到，该项目依托答辩。

参考

NKN-whitepaper

Solana Turbine Block Propagation

Solana中的共识节点称之为 validators，所有的 validators 构成一个 cluster（簇）。每次只有一个共识节点负责出块，这个负责出块的节点称之为 Leader（领导）。每个 Leader 有固定的出块区间，Solana中将其称之为 slot。

当一个 Leader 生产一个新区块后，需要尽快将其分发给其他 validator，为此，Solana 使用了一种称之为 Turbine 的方法。在这种方法中，当 Leader 分发新区块时，使用纠删码对新区块进行切分成若干份，随后将每一份数据分发给一个 validator。每个 validator 收到一份数据后，再将自己收到的数据分发给其他 validator。这是一种树形分发方式，其方式完全就是 split-stream 的翻版。

数据分发结构

当 Leader 分发区块时，会选择 DATA_PLANE_FANOUT 个节点，并向这些节点分发数据。DATA_PLANE_FANOUT 是配置的一个值。当前 Leader 选择时，直接按照各个 validator 质押的 stake 份额的高低选择，Leader 会按照从高到低选择一批节点，然后使用随机选取 DATA_PLANE_FANOUT 个节点，进行随机选择的目的是为了提高安全性。可以看出，质押份额越高的节点是最快收到新区块的节点。

假设 Leader 是分发过程中的根节点，构成了第 0 层（layer），那么 Leader 刚开始选择的这些节点构成了第 1 层，第一层的节点再次选择其他节点构成第 3 层，依次类推，最终，整个数据的分发方式构成了一个多播树，其方式类似下图，每个节点的子节点数由 DATA_PLANE_FANOUT 决定，当前这个值是在系统启动时配置好的。


Shred 分发过程

当 Leader 分发新区块时，Leader 在第 0 层。然后把编码为若干个分片，每个分片称之为一个 Shred。

当分发一个 Shred 时，Leader 节点选择并发送给一个特定的节点，这个节点称之为这个Turbine 树的根节点（root node）或者锚节点（anchor node）。锚节点会将该 Shred 分发给第 1 层的节点，同时还会发送给第 2 层的节点。因此，一个 锚节点需要将一个 Shred 分发给 $2 \times DATA\_PLANE\_FANOUT - 1$ 个节点，而普通节点只需要发送给下一层的 $DATA\_PLANE\_FANOUT$ 个节点。

下图展示了一个 Leader 在 fanout 设置为 2 的情况下把一个 Shred 分发给 Neighborhood 0 的过程。Leader 首先选择将 Shred 发送给 Validator 1（根节点），随后 Validator 1 将 Shred 转发给 Validator 2，而 Validator 1 和 Validator 2 构成了第 1 层。


如下图所示，Validator 1 和 Validator 2 继续将 Shred 发送给第 2 层的节点。可以看出，Validator 1 作为锚节点总共发送了 $2\times2-1=3$ 次，而 Validator 2 只发送了 $2$ 次。


需要说明的是，上述图解只是如何发送一份 Shred 的过程，实际上，Leader 会使用纠删码把一个区块编码为多个 Shred，然后针对每一个 Shred，把每个 Shred 发送给不同的根节点。假设整个区块被编码为 2 个 Shred，随后 Validator 1 将收到的 Shred 1 发送给 Validator2，而 Validator 2 会将收到的 Shred 2 发送给 Validator 2。最终 Validator 1 和 Validator 2 都可以通过纠删码解码原始的区块。

为了快速传输数据，Solana 使用 UDP 协议进行传输，而 UDP 不是可靠传输，因此，传输过程中加入 FEC 以增加数据的鲁棒性。

参考资料

1. Slolana Document－Turbine Block Propagation

一个合格的idea，需要具有如下 8 个信息，完整的介绍这个 idea 的过程，就是形成一篇论文的过程。

1.研究问题的背景

这部分内容隶属于 Introduction 部分，介绍研究背景, 通常在第一段就需要交代清楚 。

2. 研究问题

隶属于 Introduction 部分根据 idea 的背景引出具体的研究问题。这部分实际上是需要告诉评委，研究问题的重要性及其对该问题的解决能够获得的重大意义。

３. 相关工作

隶属于 Introduction 和 Related work。

在 Introduction 中，紧接着第 2 部分内容，指出研究问题的现有解决办法，由于 Related work 中会详细介绍，因此，这一部分只需要简要介绍这些方法的核心思想即可。

在 Related work 中，更加详细介绍这些方法，并且需要与本文的方法进行详细的比较和区分，这是为了让评委更加清楚本文的创新之处。

4.相关工作中存在的问题

隶属于 Introduction 和 Related work。

Introduction 中，紧接着第 3 部分，指出当前这些研究的不足，这些不足一定是可以被本文能够解决的问题，如果这些不足本文并不能解决，那么就不要指出了。

Related work 中，介绍这些方法的过程中，与本文方法进行比较区分，在指出它们缺点的同时，指出本文方法的创新。

5. 别人的方法出现这些问题的原因是什么

隶属于 Introduction 。

进一步分析当前研究方法中的不足，指出这些不足没有考虑的地方，这部分需要对已有的方法有着比较深刻的理解，因为只有对已有方法有着深刻的理解，作者才能提出本文的 idea。

6. 你发现了什么新的现象或者信息，并利用这一现象提出一个新的方法来避免前人的问题。

隶属于 Introduction。

根据当前方法中的不足，指出本文的新方法或者新 insight，随后进一步指出本文的解决方案的 overview。

7. 你的方法里面真正的挑战是什么。

隶属于 Introduction 和 Design 部分。指出新方法中面临的挑战，这个比较困难，一般有两种方法解决：一种是在实际方案设计中确实发现了一些问题，如实的讲述需要克服的问题。第二种方法是，制造挑战。而实际上，一篇重量的论文总会有一些需要克服的地方，一般是挖掘不到位导致的。

8. 为了克服挑战，你提出的具体的设计是什么。

隶属于 Introduction 和 Design 部分。

紧接 7 中的内容，介绍本文的具体解决办法。Design 中详细解说这样设计的动机和理由。

参考

为什么你提出来的 idea 和别人重合？

视频截取

1

ffmpeg -ss 00:00:02 -i v2.mp4 -to 00:00:32 -c:v copy -c:a copy  v2_trim.mp4

视频拼接

1. 新建一个 mylist.txt 文件，在文件中标记需要合并视频文件的名称，格式如下：

2. file 'v1.mp4'
   file 'v2.mp4'
   file 'v3.mp4'
   1
   2
   3
   4
   5
   
   3. 执行 concat 命令 
   
   4. ```
      ffmpeg -f concat -i mylist.txt -c copy merge.mp4
   
   
   

文件格式转码

1

ffmpeg -i v1.jpg v2.png

撰写博客：

1
2
3
4

1. hexo clean # 清理缓存
2. hexo g # 生成静态网页
3. hexo d # 开始部署
4. hexo s # 执行hexo s本地产看NexT主题效果

删除文章

1. 删除文件夹source/_posts下目标文章markdown文件
2. 删除.deploy_git文件夹
3. 执行hexo clean后，再执行hexo g，hexo g 即可。

hexo 命令介绍

1. https://segmentfault.com/a/1190000002632530
2. https://blog.csdn.net/wsmrzx/article/details/81478103

PBFT 是一种分布式节点间的状态复制协议,在总节点数为n的情况下,它能容错不超过 $\lfloor \frac {n-1}{3} \rfloor$ 的拜占庭节点,使得大多数的状态复制机(replica)保持一致的状态。保持分布式节点之间的系统状态的一致性,只需要做到如下两点即可:

1. 系统中节点就 client 的 request 分配一个唯一的编号,并且对于系统中任意两个非故障节点,同一个 request 对应相同并且唯一的编号.
2. 系统中的节点有序的执行 request ,保证任意两个非故障节点的系统状态一致.

PBFT 协议通过完成上述两个要求从而实现了系统的一致性.在介绍PBFT协议的具体内容前,应该首先明确该协议的系统模型.

一、 系统模型

• 网络是异步的分布式网络,网络中节点之间会出现信息发送失败, 延迟,重复发送,甚至无序的情况.
• 系统中可能有一个强力的恶意节点联合其他节点,故意导致发送信息出现延迟或者故意延迟正确的节点发送的信息,但是恶意节点不能无限延迟.
• 恶意节点无法伪造诚实节点的签名,而恶意节点之间可能串通,可以相互伪造签名.
• 恶意节点无法通过一条消息的摘要计算出消息体.
• 恶意节点无法针对一个消息m,找到另外一个对应的消息m’使得它们的摘要相同.(摘要是对消息求hash).
• 系统中总结点数为n的时候, PBFT协议最多容忍 $\lfloor \frac{n-1}{3}\rfloor$​ 的拜占庭节点.

二、 系统角色

• Replica, 状态复制机,所有的 replica 都会执行 PBFT 协议并保持系统状态一致性.
• Primary, 在 PBFT 协议中,每个 primary 都有一个任期,称之为 view, 在一个 view 中,只有一个 replica 会被称为 primary,可以理解为leader.
• Backup,除了primary 以外的 replica 都称之为backup.
• client, 向 primary 发送 request 请求服务的客户端.

三、PBFT协议简述

PBFT 协议以状态机复制的形式展示,将服务建立为在分布式环境下跨机器之间进行数据复制的状态机模型. 每一个状态复制机都会维护一个当前的服务状态,PBFT 协议可以保证所有非拜占庭节点的系统状态全部相同, 而这些状态复制机执行客户的请求后转入下一个状态,并将执行结果反馈给 client.

在PBFT协议中,主要有三个身份,client,primary 和 backup。replica 中有一个主节点,称之为primary, 其他 replica 称之为backup. client向 primary 发出操作请求, primary 把 client 的请求发送给所有 backup , primary和其他backup通过按照PBFT协议对操作进行响应,然后将执行结果返回给client.

PBFT论文中默认client在收到前一个 request 的执行结果之前不会发送下一个 request .每一个primary在其任期内对应一个view, 下一任primary上任时,view自动加1. 一个view中只有一个primary.

整个协议的整体流程如下:

• client向 primary发送一个 request .
• primary向其他备份节点广播 request .
• 所有节点执行 request 并且向client返回执行结果
• client 从f+1个不同的节点处得到相同的执行结果,则认为执行结果可靠并且接受这个结果.

PBFT 细节

再次强调的是，在该协议中,假定拜占庭节点的数目最多为 $f$​​ 个, 而全体节点的数目为 $n = 3f+1$​​​.

1. client 发出 request

client 向 primary 发出一个 request , request 的具体形式如下:

$<REQUEST, o,t,c>_{\sigma i}$

$o$ 表示 operation,即具体执行的操作, t 表示 timestamp, 之所以需要加上时间戳, 是在一个client在发出多次相同operation的时候, primary 用 timestamp 区分这些命令, c 表示 client 编号, $\sigma i$ 表示 client $i$ 将这些信息进行签名,以证实自身合法的身份.

注意: 如果 client 将 request 发送给了 backup 节点,那么该节点会将 client 的 request 转发给 primary.

2. pre-prepare 阶段

为了确保所有的非拜占庭节点保持一致的状态, primary 需要对 request 分配一个序号(sequence number),如果全体 replica 能够对每一个 request 的序号达成一致,那么就能达成整个系统服务状态的一致性.

2.1 Primary 收到 Request

收到一个 request 时，primary会检查 request 的合法性,首先检查客户端的签名是否正确, 如果不正确,则拒绝执行后续步骤;

如果正确,则给 request分配一个唯一的序列号n,然后向其他 backup 广播一条 $pre-prepare$ ​​​​(预准备)消息,形式如下:

$\left < \left < PRE-PREPARE, v, n, d \right > _{\sigma p}, m \right >$

$v$是当前view序号, $n$​是 primary 为 request 分配的序列号, d是 request 的摘要, m 代表 client的 request 信息, $\sigma_p$​ 是 primary 的签名.

2.2 Backup 收到 pre-prepare消息

backup收到pre-prepare消息时,会验证如下消息:

• request 的签名是否正确, 确保client的签名不是伪造的.
• view的序列号与当前backup当前的view序列号相等.
• backup确定当前 view下,序号n没有分配给另外一个不同的 request .
• n应该在某个范围[h, H].

如果上述条件全部符合,则backup接受这个 $pre-prepare$ 消息, 并且进入 prepare 阶段.

3. prepare阶段

3.1 广播 Prepare 消息

对于 Prepare 阶段做一下解释，节点收到 pre-prepare 消息之后，相当于收到了一个来自 primary 的提议，但是节点不清楚其他节点是否收到了同样的 pre-prepare 信息，因为 primary 节点可能是恶意节点，它可能向其 backup 发送不同的 pre-prepare 信息。因此，每个节点向网络中其他节点广播 prepare 信息进行同步，其含义是告诉其他节点：本节点收到了来自 primary 的一条 pre-prepare 信息。

backup 在 prepare 阶段,向本地的log中插入 $pre-prepare$​ 消息以及自身的 $prepare$ 消息 ,并向其他 backup(包括primary)广播一条prepare消息,prepare消息形式如下:

$\left < PREPARE, v, n, d,i\right >_{\sigma i}$

其中 $i$​​ 是 backup 的编号, $\sigma_i$​​ 表示节点 $i$​​ 的签名, backup(包括primary)收到来自其他节点的prepare消息时,会验证如下信息:

• view 序号和节点自身的 view序号相同.
• n在 [h,H] 范围内.
• d 和 pre-prepare阶段消息的摘要相同。

如果上述验证通过,则将这条信息插入本地log.

如果一个节点收到 $2f+1$ ​(包括自身的)相同的 $prepare$ 消息,并且这些消息与之前收到的 $pre-prepare$ 消息的 $m, v, n$​​相同, 则认为 prepared(m, v, n, i) 为真,并将 prepared(m, v, n, i) 插入log, 然后进入commit 阶段.

3.2 pre-prepare 和 prepare 阶段的作用

$prepared(m, v, n, i)$​​​ 的主要作用就是,确保在一个 view 中，一个 request 唯一的对应一个序列号 n。因为 $prepared(m, v, n, i)$​​​为真的条件是,有$2f+1$​​​个节点广播信息验证了$m, v, n$​​​的一一对应关系.证明如下：

1. $2f+1$​ 个一致的 $prepared(m, v, n, i)$​消息中，最多有 $f$​ 个拜占庭节点的 prepared 消息, 至少有 $f+1$​ 个诚实节点的 $prepared(m, v, n, i)$​ 消息。
2. 剩余的 $f$​ 个诚实节点由于收到了错误的prepare 消息，它们互相广播 $prepared(m', v, n, i)$​ 。由于存在 $f$​ 个拜占庭节点，这些节点可能广播了 $f$​ 个 $prepared(m, v, n, i)$​ 消息，又作恶的广播了 $f$​ 个 $prepared(m', v, n, i)$ 消息，此时也只能存在 $2f$ 个 $prepared(m', v, n, i)$ 消息，这不足以达成一致 (达成一致的要求是至少$2f+1$个相同的prepared消息)。

综上所述， pre-prepare和prepare两个阶段保证了在同一个 view下,n 和 request 的一一对应关系. 这一步骤带来的好处是，即使发生了 view change，此时最多 f 个节点出错，那么剩余的 2f+1 个节点至少有一个节点保留有最新的 2f+1 个prepare信息。当新的 leader 产生时，最新的 2f+1 个 prepare 消息仍然会被执行，保证了系统的安全性。

4. commit阶段

4.1 广播 commit 消息

对 commit 消息再作下解释，进入 commit 阶段的前提是节点收到了 2f+1 个合法的prepare消息，然而在异步环境下，节点不知道其他节点是否也收到了 2f+1 个prepare 消息，所以，节点向其他节点广播一条 commit 消息，其目的是告诉其他节点：本节点已经收到了 2f+1 个prepare 消息。

backup 进入commit 阶段时, 向其他 backup (包括 primary) 广播一条 commit 消息,具体形式如下:

$\left < COMMIT, v, n, D(m), i \right >_{\sigma i}$

其他replica收到commit消息后,验证如下信息:

• 节点 $i$​ 的签名正确.
• view 的序号和本地 view 序号相同.
• n在[h,H]范围内.

如果上述验证全部通过,节点将该commit信息插入本地log. 如果节点$i$满足两个条件:

1. 节点 $i$​ ​​的 $prepare(m, n, v,i)$​​​ 为真,即节点 $i$​​ ​也进入commi阶段.
2. 节点 $i$​ ​收到 $2f+1$​​ (包括自身)一致的 commit 信息, 并且它们与本地的 pre-prepare的$m, v, n$​​全部相同.

则作出定义$committed-local(m, n, v, i)$​​为真的判断。

4.2 执行 commit

$committed-local(m, n, v, i)$​​​​为真，表示系统中至少有$2f+1$ 个节点认同对 request 分配的编号，这些达成共识的节点执行 request 后的系统状态是一致的. 执行完毕后所有节点会向 client 发送一个 $reply$​ 消息. 其形式如下：

$<REPLY, v, t, c, i, r>_{\sigma i}$

其中 v 是当前的 view 编号，t 是 client 的 request 的时间戳，client可以根据时间戳判断是哪一个 request 的执行结果，因为client可能先后不同的时间发送同一个 request, i 是 replica 的编号， r 是执行结果.

4.3 client 验证结果

client如果只要收到 $f+1$​​​​个相同的执行结果（相同的 r，t）,则认为执行结果可信.

这里面对相同的执行结果的定义是，对应同一个 request，收到了 $f+1$​ 个执行结果，这些执行结果具有相同的 r，同时它们也对应于同一个时间戳。这里并不要求同一个 view， 具体详见 view change 阶段。

为什么是 $f+1$​ 个相同的结果，client 就能确保结果可信呢？ 因为 $f+1$​ 个节点中至少有一个诚实的节点，而一个诚实的节点能够执行一个 request，说明有其他 2f 个节点向其广播了 commit 信息，这 2f 个节点也必然进入了commit 阶段。这说明至少有 $2f+1$​ 个节点对 request 的编号 $n$ 达成一致，这种情况下，一个诚实节点返回的执行结果一定可信。

5 Garbage Collect

每个节点都有一个日志系统记录当前系统的执行状态，但是需要定时的对系统做一个snap shot，这是为了确保其他节点从错误中恢复时，可以从中间某个状态再次启动，因此就有了 checkpoint。

Checkpoint 有两个作用:

1. checkpoint之前的所有 request 的内容都已经执行，因此可以删除之前的log,节省 replica 的存储.
2. replica 丢失状态时,可以向其他节点请求系统状态时，可以请求最近的checkpoint以快速恢复状态.

假设系统每执行了 $T$ 个request后进行一次checkpoint，于是replica 执行第n个request后,如果 $n\%T == 0$​​, 则该节点向其他节点广播一条checkpoint 消息:

$<CHECKPOINT, n, d, i>_{\sigma i}$

其中 d 是执行完第 n 个 request 后的系统状态的摘要, $i$​​是节点编号.

如果收到 $2f+1$​​​​ 相互一致并且合法的 heckpoint 信息,则认为这些checkpoint代表的系统状态是合法并且一致的。

对于一个checkpoint，如果有其他 $2f$​​ 个 与之相同的checkpoint 信息，则这个 checkpoint 可以称作是 stable checkpoint。节点可以删除 checkpoint 对应的序列号n的所有 pre-prepared, prepared 和 commit 消息。

当其他节点请求本地传输某个系统状态时, $2f+1$个 checkpoint 消息可以作为传输的系统状态合法的证明.

checkpoint协议用来对下一次序列号的范围进行设定,当某个 checkpoint 被证明合法后,对序列号范围可以调整为H = h+k, 其中h是上一次稳定检查点的序列号, 假如每100个请求后进行一次检查点验证, k 可以设置为200, 即H = 200.

6. View Change(视图切换)

view-change 消息是为了应对系统中primary发生故障后切换新的 primary 的机制.

6.1 backup广播 View Change消息

如果 当前 view 的编号为 $v$​​​, 那么出现故障时，下一任 primary的编号为 $(v+1)\%n$​​​​​，因此，PBFT 协议不存在 primary 出现故障后其他 backup 竞争 primary 的情况，这一点和 RAFT 协议有所不同。

每个 backup 收到一个 request 时,就会启动一个计时器,如果计时器超时之后,仍然没有执行该 request ,该backup认为 primary 出现了故障，那么它向其他 replica 发出一个view-change消息,格式如下:

$<VIEW-CHANGE, v+1, n, C, P, i>_{\sigma i}$

其中，$v+1$​​​表示下一个视图的编号, n表示该节点已知的最近的一个stable checkpoint的编号, $C$​​ 是一个集合,其中包括 $2f+1$​​ 个有效的 checkpoint 信息以证明该 checkpoint是stable checkpoint. $P$​​ 也是一个集合,集合中的每一个元素是$P_m$​​, $P_m$​​本身又是一个集合, 每一个$P_m$​​中包含序列号大于n的pre-prepare消息以及与之匹配的$2f$​​​​​个 prepared 消息.
从这里看到，一条 view-change 消息中包含的消息数量复杂度是 $O(n)$ 级别的，而 $n$ 节点，每个节点都广播一个 new-view 消息，广播消息的复杂度是 $O(n^2)$ 级别，所以，整个 view-change 的广播的消息数量，其复杂度是 $O(n^3)$ 级别

6.2 新primary广播new-view消息

当 v+1视图对应的 primary 从其他 replica 收到 $2f$​ 个有效的 view-change 消息时,向其他所有节点广播new-view消息,具体格式如下:

$<NEW-VIEW, v+1, V, O>_{\sigma p}$

其中 $V$​ 是一个集合, 包括 $2f+1$​(包含新的primary自身)个view-change消息, O是pre-prepare消息的集合。

O的计算方式如下:

1. primary 首先确定两个变量 $min-s$​​ ​和 $max-s$​​​, $min-s$​​​指的是 primary 收到的所有view-change消息中最新的stable checkpoint的对应的序号n, $max-s$​​​指的是view-change消息中,集合$P$​​​中所有$P_m$​​​中pre-prepare消息编号的最大值.

2. primary 为编号为$( min-s, max-s]$​范围内的 request , 重新创建view序号为v+1的 pre-prepare 信息. 这里包含两种情况:

   1. primary 收到的所有 view-change 消息中,至少有1个集合P不为空, 即存在某个编号$n\in (min-s, max-s]$​的pre-prepare消息.
   2. 所有的view-change消息中的集合P全部为空.

   第一种情况下, primary为 P 中所有 request 创建一个新的pre-prepare消息,格式为:

   $$\left < \left < PRE-PREPARE, v+1, n, d \right > _{\sigma p}, m \right >$$

   其中 d是该 request 的摘要, n 的范围为$(min-s, max-s]$​，这表明这些 request 虽然处于不同的 view，但是为其分配的编号仍然不变。​

   第二种情况下, primary创建一个null request 的pre-prepare消息,格式如下:

   $$\left < PRE-PREPARE, v+1, n, d^{null} \right > _{\sigma p}$$

$d^{null}$​是特定的的null request摘要, null request不执行任何操作.

随后，primary 将 $O$​ 中的信息插入 log 之中。因为 $min-s$​ 是最新的一个 checkpoint 的 request 的编号，如果 primary 发现 $min-s$​​​ 大于 primary 本地最新的stable checkpoint的编号n,则primary也会将相应的 $min-s$​​​​ 对应的 checkpoint 的 proof 插入到 log之中, 然后丢弃 stable checkpoint 之前的所有信息。

6.3 backup 验证 new-view消息

当 backup 收到primary发送的new-view信息时, 检查如下信息:

• primary签名是否正确.
• new-view中包含的 view-change 消息是否合法。
• 根据new view信息中的集合V计算集合$O$, 检查计算得到的$O$是否消息中的$O$一致.

如果上述条件全部满足, backup选择最新的stable checkpoint, 删除stable checkpoint之前的所有log, 并根据执行集合O中的pre-prepare信息.执行步骤按照PBFT的协议进行,如果该节点已经执行过该 request ,则不再执行该 request，但是其他prepared、commit以及reply信息，都需要照常发送.

注意: backup如果没有最新的stable checkpoint的状态,应该首先向其他节点请求最新的stable checkpoint的系统服务状态,然后再执行$(min-s, max-s]$​​范围内的 request ,否则会导致系统状态不一致.

7. PBFT协议讨论

7.1 为什么PBFT协议中节点总数$N>3f$​, 为什么后两个阶段至少需要$2f+1$​的投票?

以下证明来自个人理解

设系统总节点数为$N$​, 拜占庭节点数目为$f$​,于是剩余的诚实节点的数量为$N-f$​，假设系统中有 $Q$ 个节点就一个消息达成一致，那么就认为达成共识。共识协议需要保证安全性(Safeness) 和活性方面(Liveness)。

1. 活性方面，即如果系统中 f 个拜占庭节点不参与投票，那么其他节点应该能够达成一致，于是:

   Q<=N-f \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \bold \{1\}$$​

   2f + A + B < 2Q \rightarrow N + f < 2Q \quad (已知A+B = N-f)\quad\quad\quad \bold \{2\}$$​​ 根据 1 和 2 得到的两个不等式，得到：

$$\rightarrow N+f<2N-2f$$

$$\rightarrow 3f < N \rightarrow 3f+1 \leq N \quad\quad\quad \bold\{3\}$$

将 3 的结果代入到 2 式中，得到 $2f < Q$， 即 $Q$ 的取值至少为 $2f+1$。

下文来自 PBFT 论文证明

1. 系统中 $f$ 个拜占庭节点可能不参与共识,此时协议应该保证剩余 $N-f$ 个 replica 达成共识，即 $Q<=N-f$。
2. $N-f$​​个节点中必须保证诚实节点数量超过拜占庭节点的数量（我不太理解作者为什么想当然这么说这句话，可能BFT问题中一个已知的定理）,即 $N-f-f = N-2f > f \rightarrow N>3f$​​​​​​​​​.
3. $3f+1 \leq N$, 根据第 2 式可得 $2f+1 \leq Q$​.
4. 当 $N = 3f+1$ 时，根据 $Q \leq N-f$,推导出$Q \leq 2f+1$,即此时Q的取值只能为 $2f+1$.
5. 当$N = 3f+k, (k>0)$时，Q 的取值范围为$[2f+1, 2f+k]$。

7.2 PBFT的三个步骤中将commit步骤去掉可以吗?

现在撤销$commit$步骤, 只有$pre-prepare$阶段和$prepare$,如果$prepare(m,n,v,i)$为真,则直接执行 request 并且返回给client.

假设有部分诚实的节点数量为$f$,成功的收到了$2f+1$与本地pre-prepare匹配的$prepare$消息, 它们执行了对应的request-m, 假设m对应的序号是$n$, view序号是$v$. 但是其他$2f+1$个节点在接收$prepare$消息过程中网络不好, 没能收到足够的$2f+1$个匹配的$prepare$消息, 所以它们不会执行这个m.(PBFT协议中假设网络中信息传输会出现丢失的情况). 然后这$2f+1$个节点进行了$view-change$, 并且primary在这$2f+1$个节点中产生, 这$2f+1$个$view-change$消息中没有request-m的对应的$2f$个prepared消息,并且如果出现 $2f+1$个节点的 view-change消息集合中的 P为空,新的primary重新发布$new-view$消息时,消息中的O只包含了一个null-request的pre-prepare消息:

$\left < PRE-PREPARE, v+1, n, d^{null} \right > _{\sigma p}$

此时执行了request-m的$f$个节点验证 new-view后通过,它们本地的序号n对应request-m,但是new-view中的序号$n$对应的是一个null request, 而不是request-m. 这就导致了这诚实的$f$个节点和另外$2f+1$个节点的系统状态已经出现了不一致.这不满足PBFT协议保证系统一致性的另外一个条件,所有系统中的非故障节点都必须对 request 的执行达成一致.

实际上,引入$commit$步骤中,$committed-locally$为真才执行 request 这一条件, 就是保证至少有$2f+1$个节点(其中至少$f+1$个诚实的节点)的$prepared(m,v,n)$为真, 这些节点一起执行 request .

view-change时,这$2f+1$个执行了reqeust-m的节点中,至少有$f+1$个节点参与其中,这个节点的参与,保证了request-m在view序号为 v+1的时候分配的编号仍然是 view序号为v时的序号,这就是为什么论文中说$commit$步骤保证了不同$view$中 request 的有序执行.

7.3 如果client在发出request之后在一定时间内没有收到足够多的响应怎么办?

client会将 request 广播给所有节点, 如果收到的节点已经处理了这条 request ,则会直接向client返回执行结果.如果该节点没有处理过这条 request ,则会将这条 request 转发给primary. 如果primary在一段时间内不广播该 request ,其他节点会怀疑primary作恶并且进行$view-change$操作以更换primary.

7.4 为什么client收到 $f+1$​ 个一致的结果就认为结果是正确的?

在PBFT协议中最多有$f$个恶意的节点,当client收到$f+1$个相同的执行结果时,说明其中至少包含一个诚实的节点的执行结果. 诚实的节点返回执行结果的前提就是, 分别在prepared和committed-local达成了一致,并且这个一致性是唯一的,这也能说明系统中诚实的节点达成了唯一的一致, 所以client可以相信执行结果.

7.5 backup 验证pre-prepare消息时为什么n的范围需要在[h, H]之间

为了防止恶意的primary选择一个超级大的序列号n耗尽序列号的空间.不过这个解释不太令人信服,我暂时也不太清楚.

7.6 PBFT协议中的log有什么作用?

• log可以记录节点是否执行了某个 request .

• 另外如果发生$view-change$时可能会从最新的stable checkpoint重新执行 request ,log记录了 request , 方便重新执行.

• 其他节点请求stable point时可以直接传输$committed-local$消息方便该节点恢复.

参考文献

[1] M. Fischer, N. Lynch, and M. Paterson. Impossibility of Distributed Consensus With One Faulty Process. Journal of the ACM, 32(2), 1985

[2] G. Bracha and S. Toueg. Asynchronous Consensus and Broadcast Protocols. Journal of the ACM, 32(4), 1995
[3] Castro M, Liskov B. Practical Byzantine fault tolerance[J]. operating systems design and implementation, 1999: 173-186.

摘要

随着区块链技术被越来越多的人熟知，数字加密货币的概念越来越普及，加密货币的用户也日益增多。作为加密货币界的创世币，比特币当之无愧的是其中执牛耳者，拥有着最高的市值和最大的用户量，受到了极大的关注。作为区块链技术的起源和典型代表，比特币仍然有其自身的局限，即匿名性。由于比特币上所有账户的交易都可以追踪，每笔交易的来龙去脉都在区块链上追踪溯源；从本质来说，比特币是化名的(pseudonymous)，而不是匿名的(anonymous)，这对于那些对匿名性有强要求的用户来说是不可接受的，有没有什么相关的解决方案呢？在需求的驱动和技术的发展两种因素的驱使下，匿名币应运而生。不同的匿名币币，使用了不同的技术以实现匿名要求，从目前的市值来看，典型的匿名币主要有Dash、Monero 和 ZCash三种，这三种匿名币分别使用了不同的匿名技术，下文会详细介绍其技术原理，并根据自身理解分析这些匿名币的匿名性。

匿名币

匿名性

从字面上理解，匿名指的是“没有名字”，通常的解释有两种：

• 交易的时候不适用真实的姓名。
• 交易的时候完全不适用名字。

如果按照第一个解释，那么比特币是匿名的，因为比特币交易过程中没有使用用户的真实姓名，而是使用比特币地址。如果按照第二种解释，比特币不具有匿名性，因为交易的过程中必须使用的地址是仍然是一种标识，在计算机语言中，使用一种特定标识的折中做法称之为化名。

在计算机科学中，匿名指的是具有无关联性的化名。无关联性指的是一种针对特定攻击者的能力而定义的属性，直观的理解是，如果一个用户和系统重复进行交互，从攻击者的角度考虑，不同的交互行为之间应该无法互相关联。比特币是具备化名性，但是如果要求绝对隐私，那么比特币的匿名性还不够。区块链技术是一种公开的账本系统，任何人都可以查询包含给定地址的所有交易，如果某人的真实身份和其比特币地址联系起来，那么他所有过去、现在和未来的交易，都会被追踪到，这种情况下，区块链的隐私保护甚至不如传统的银行。此时对于匿名加密数字货币的动机也就不难理解了，我们对其的要求是：

• 其匿名性至少和传统银行带来的隐私保护处于同一级别，降低公共区块链带来的信息泄露风险。
• 超越传统银行带来的隐私隐患，在技术上任何人不能够轻易的追踪交易。

那么如何才能做到更好的匿名性呢？这需要交易具有更强的无关联性。

无关联性

如果需要在交易的过程中做到强无关联性，至少需要做到如下三点：

1. 同一个用户的不同地址应该不易关联。
2. 同一个用户的不同交易应该不易关联。
3. 一个交易的交易双方应该不易关联。

上述第三点看起来令人费解，交易双方既要完成交易，却又要使得双方不易关联，这个确实难以做到，但并非不可能。后文介绍的Dash、Monero和ZCash，能做到去中心化的前提下，也能较好的做到交易双方的无关联性。下文会对三中典型的匿名币的相关匿名技术做一个概要的介绍和分析。

Dash

Dash的前身称之为Darkcoin，于2014年1月18日上线，其代码主要来自于Bitcoin，其主要特点如下：

1. 限量供应，Dash供应量大概在1800万～1900万之间。
2. Dash中出块时间被缩短到了2.5分钟，出块速度是比特币的4倍。
3. Dash网络中除了矿工和一般用户外，增加了另外一类节点，称之为Masternode. Masternode主要负责完成组织并发布Dash用户的混币交易以实现匿名性。
4. 在Dash中，将混币交易称之为PrivateSend, PrivateSend主要使用了CoinJoin(合币)思想，即将不同用户的输入和输出组织在同一笔交易中，从而使得外界用户无法判断交易中输入和输出的具体对应关系，这样经过多轮次的混币交易，实现用户交易的无法追踪性。
5. Dash中增加了InstantSend，用户一笔交易在尚未上链之前就能得到确认，同时保证这笔交易不会被双花。
   更多Dash的相关资料，可以参考其白皮书, 相关代码的实现，可以参考其github源代码 。

Dash中的匿名技术

前文说道，PrivateSend使用了CoinJoin(合币)，CoinJoin最先由Gregory Maxwell于2013年在比特币论坛提出，其核心思想是将多个不同用户的输入和输出放置在同一笔交易中，使得交易之外的第三方难以辨识输入和输出的对应关系。
早期的Dash币中采用CoinJoin技术（Dash中称之为DarkSend），而与Gregory Maxwell提出的CoinJoin不同的是，DarkSend交易中，Dash币必须是属于标准面额{ 100.001， 10.0001， 1.00001， 0.100001， 0.0100001 }, 同时输入和输出的个数必须相等，同时每个用户来说，DarkSend交易的输入和输出地址都是当前用户的钱包地址，DarkSend交易过程中用户的Dash没有离开自身的钱包。下图是一个典型的DarkSend交易，这笔交易中，有14个输入和输出的值都是0.100001；6个输入和输出的之都是1.00001.这里面具有多个用户，每个用户都有自己的输入和输出，只有参与DarkSend的用户自己知道输入和输出之间的对应关系。

后来Dash币中又对DarkSend进行了进一步升级(称之为PrivateSend技术)，在PrivateSend交易中，所有的输入和输出都是相同的标准面额值{ 10.0001， 1.00001， 0.100001， 0.0100001，0.00100001 }。因此，如果一个要进行PrivateSend交易，必须对UTXO中的面额拆分成标准化的面额，这需要一笔转账交易完成。下图是一个将UTXO拆分成标准面额的交易。将一个价值为0.01的UTXO，拆分为8个0.00100001，同时0.0004的转账交易作为PrivateSend的手续费用，剩余部分作为找零。在UTXO经过若干轮PrivateSend之后，和其他人进行转账交易时不能和找零的UTXO放在同一个交易中，否则就会暴露用户自身的隐私。因此，使用PrivateSend过程中会产生额外的找零UTXO，这是一个弊端。

完成对UTXO的面额化交易之后就可以进行PrivateSend交易，用户的客户端会向MasterNode发起进行PrivateSend的请求以进行混币。下图是一个PrivateSend的交易。

在DashCore 0.13.0版本之前，参与PrivateSend的用户固定是3人，后续的版本的PrivateSend中的用户数量介于3~5人之间。
相比于之前的DarkSend, PrivateSend中所有的输入和输出相等，增加了对输入和输出对应关系的追踪难度，DashCore的用户可以选择进行多次的PrivateSend以增强匿名性，目前组最新版本的DarkSend，最多可以进行16轮的PrivateSend。
对于一笔交易，不需要完全知道交易中每个输入对应的输出，UTXO的交易模式中，也没有具体的说明某个输入和某个输出的明确的对应关系。因此在PrivateSend中，我们关注的重点在于input和output是否对应于同一个用户。假定参与用户是3人，一轮PrivateSend中，共有3n个输入和3n个输出，每个用户都有相同的n个输入，外部用户能够猜对具体的输入和输出的概率为：

$$\frac{ 1 }{ { C }^{ n }_{ 3n } } \times \frac{ 1 }{ { C }^3_{ 3n } }$$

一般情况下，PrivateSend中的输入个数至少为5，为了方便计算，假设n=6，平均每个用户2个输入，此时猜对特定某个用户的输入和输出的概率为$\frac{ 1 }{ 225 }$, 在当前的DashCore中，一般进行4次的PrivateSend，最高可以进行16轮。如果用户进行16轮PrivateSend，能猜对同一个用户输入和输出的全部对应关系的概率为:

$${ (\frac{ 1 }{ 225 }) }^{ 16 } \approx 2.32 \times 10^{ -38 }$$

所以平均6个输入的PrivateSend，某个用户的输入和输出对应关系被猜对的概率范围是：

$$[{ (\frac{ 1 }{ 225 }) }^{ 4 }\approx { 3.90 }\times 10^{ -10 }, \quad \quad { (\frac{ 1 }{ 225 } })^{ 16 }\approx 2.32 \times 10^{ -38 }]$$

需要说明的是，PrivateSend的过程需要Dash中MasterNode的参与，每个钱包参与PrivateSend时，都会选择一个特定的MasterNode，MasterNode对PrivateSend中撮合不同用户的输入和输出，因此MasterNode作为第三方，却可以掌握输入和输出之间的对应关系，如果有人能够控制MasterNode并且监控MasterNode的混合信息，那么用户的隐私将会收到极大的威胁。目前MasterNode都运行在云服务提供商的服务器上，每个云服务上运行节点数目详情可以参考如下链接。

• http://178.254.23.111/~pub/Darkcoin/masternode_ISPs.html
  由于所有的输入和输出都需要经过MasterNode之手，虽然Dash白皮书上对其进行了分析，认为MasterNode数量巨大(目前大概有4000+MasterNode)，每个区块之后都会随机选择新的MasterNode进行PrivateSend,有效的降低了信息泄露的风险，但是这仍然不能掩盖PrivateSend的输入和输出对应关系会被MasterNode掌握的事实。

Dash的匿名性分析

• Unlinkability：对于不可关联性来说，Dash中每次进行PrivateSend时，默认情况下，每次的输出都会采用新的地址，因此，对于任意的两个PrivateSend交易，由于没有其他地址方面的信息，确实无法证明两笔交易中的某些输出隶属于同一个实体。
• UnTraceabiltiy：对于不可追踪性来说，Dash的PrivateSend中，除去交易参与方之外，只有MasterNode知道输入和输出的对应关系，此外其他的第三方难以知晓这种交易中输入和输出对应关系。
• Convencience：对于便利性来说，Dash的PrivateSend中，只有DashCore对PrivateSend的支持性比较好，而DashCore时一个全节点，目前Dash的节点信息大约12G左右，移动用户使用起来不太方便。Dash中每次进行PrivateSend最高上限是1000Dash，超过1000Dash时需要进行多次的PrivateSend，同时Dash的区块间隔为2.5分钟，如果要完成4轮PrivateSend，需要等待至少10分钟。

Monero

2012 年 7 月，应用层协议CryptoNote支撑的第一个去中心化货币Bytecoin问世。尽管 Bytecoin 十分有前景，但是人们也注意到发生了很多负面的事情，并且鉴于它已经产出了 80% 的币。所以，决定将 Bytecoin 分叉，新链上的币叫做 Bitmonero，最终被重新命名为 Monero（门罗），在世界语中叫做“coin”，硬币的意思。门罗由一个 7 人的开发者团队领导，其中 5 人匿名，另 2 人已公开。他们是 David Latapie 和 Riccardo Spagni aka “Fluffypony”。项目是开源众筹的形式进行。Monero是一个独立的虚拟币种，而不是比特币的分支，且它规避了比特币的设计缺陷，变得更加隐私、去中心化。

Monero中的匿名技术

Ring Signature： Monero中为了保护发送方的隐私，使用了环形签名，Alice 在给 Bob发送XMR的时候，除了给出花费的UTXO 的真实地址P之外，还会将Monero区块链中其他与P地址中余额相同的UTXO也添加到交易的inputs中，形成一个集合$S = (P_1, P_2, ..., P_m)$。

Alice会将这个集合S作为交易中的inputs一起发布出去，这样对于外界来说(尤其是矿工和Bob)，他们无从知晓Alice具体花费了S集合中的哪一个UTXO，这样就保护了Alice的隐私。其他被Alice添加进来用于迷惑其他人的UTXO称之为mixins，又叫chaff output或者 decoy output，Alice添加mixins的时候，并不需要得到其他用户的同意，Alice自行决定添加的mixins的数目。Monero中使用Ring Signature的主要目的就是实现发送方的untraceabity。

Stealth Public Address：如果 Alice 要给 Bob 发送门罗币，除了 Alice，应该没人任何人知道 Bob 就是这笔钱的接收者。为了做到不可追踪性，Alice利用Bob的public view key 和public send key来随机生成一个一次性的公钥地址，叫做Stealth public Address。假设Bob的view key的公私钥对是$(A, a)$, spend key 的公私钥对是$(B,b)$, 其中$A = aG, B = bG$, G是一个密码学常数，的生成过程如下：

• 随机产一个$r，r∈[1, l]， l$是G的一个素数阶。
• 令 $R = rG, P = H_s(rA)G+B， H_s()$是Monero中使用的Keccak哈希算法。
• 生成的Stealth public Address 即为P。

现在对P进行如下的推导：

$$P =\\ H_s(rA)G+B =H_s(raG)G+bG \\=G(H_s(raG)+b)=G(H_s(Ra)+b)$$

Alice告诉Bob这笔转账所在的区块号和交易号，Bob利用R、private view key a 和 private spend key b计算$P = G(H_s(Ra)+b)$找到交易中的所有output，然后寻找相应的output中是否存在某个输出地址为P，如果存在，则可以证明Alice确实给Bob转账了.

注意： 对于其他人来说，由于不知道Bob的private view key 和private spend key，其他人无法知晓Alice给Bob转账的地址是哪里。

Ring Confidential Transactions： 2017年1月10日Monero中正式使用了RingCTs。而在此之前，Monero中假如Alice需要向Bob转12.5个XMR，则需要将自己的UTXO分别发送至三个地址，分别转账10XMR、2XMR和0.5XMR，这是因为Monero中要求转账的XMR格式为$A ×10^{ B }$的格式。但是公开转账金额的做法无法隐藏交易本身的信息，为了解决这个问题，Gregory Maxwell提出了RingCT，RingCT可以做到隐藏交易额，这时候Alice挑选mixins的时候，可以选择RingCT中的output作为mix-in。

下图是一个Monero上的交易，通过区块链浏览器查看一笔交易显示结果如下。其中的每个input的金额显示为0，表示input的数额已经被隐藏。

这笔交易中，共有6个输入，4个输出，对其中第一个输入进行展开，可以看到下图的结果，其中第一个input中包含11个public key，但是其中只有1个是真正的input，其他input是decoy input。

对于第三方来说，难以辨别真正的input是到底是哪一个，decoy input数量越多，发现真正的input就越难。对于接收方而言，接收方的地址是发送方随机产生的地址，外部用户即使知道接收方的public view key 和public spend key，也无法知道其他人转给接收方的交易是哪一笔。

Monero的匿名性分析

• Unlinkability：对于不可关联性来说，Monero中采用的Ring Signature可以很好的隐藏发送方的隐私，Ring Signature中的input越多，隐藏能力越好。对于一笔交易，每次都会产生一个新的接收地址，只有接收方和发送方知道接收地址，外部用户无法知道金额发送哪里。
• UnTraceabiltiy：对于不可追踪性来说，Monero中可以同时保护发送方的隐私，接收方的隐私，同时也隐藏了交易数额，追踪某个人的交易记录变得几乎不可能。
• Convencience：Monero的发送和接收，没有对钱包本身有过多的需求，另外发送的数额没有过多限制。

ZCash

Zcash的代码是基于比特币0.11.2代码修改，于2016年10月28日上线，其总供应量是2100万。区块奖励方式如下：

• 前20000个块，第一个区块的奖励是0.000625币，随着高度线性递增，每增加1个区块，出块奖励提高0.000625 ZEC。
• 从第20000个区块开始，奖励变为12.5，奖励按照每840000个区块减半，Zcash出块时间为2.5分钟，算下来大概是每4年减半。

Zcash中规定，前4年挖矿中的25%交给创世团队，因此到2020年10月28日为止，创始人团队都会收到出块奖励的25%。Zcash的良好隐蔽性源于使用了一个被称为 zk-SNARK算法 的零知识证明密码学架构，该架构是由经验丰富的密码学家团队开发的。这个框架允许网络在不公开交易参与方或者交易数额的情况下维护一个安全的账户余额账本。Zcash 交易的元数据是加密的，而不是公开地展示交易参与方和交易数额，zk-SNARK算法 被用来证明没有人进行欺骗或者偷窃。

ZCash中的匿名技术

ZCash的核心技术是零知识证明，零知识证明可以证明一个交易的合法性却又不需要暴露交易的金额以及交易参与方的信息。

ZCash提供两种地址，一种叫做transparent address,简称t-address,这种地址以t开头. 另外一种地址叫做shielded address。两种地址类型，于是便有了4中转账方式：z->t, z->z, t->z, t->t，其中z->z的转账匿名性，这种类型转账称之为Private transactions,从z-toz交易中只能得知交易费，但交易地址、地址数量以及交易的ZEC数目都是未知的。

下图是一个典型的z->z的转账，右下角蓝色方块内文字表示确认数目，黄色方块内文字表示交易费，红色方块内文字表示交易数额。JoinSplits中的内容完成零知识证明。除了参与交易的双方外，外界无法得知交易地址和转账费用等信息。

ZCash的匿名性分析

• Unlinkability：对于不可关联性来说，ZCash中的z地址之间的转账，地址完全不可见，因此很好的实现了不可关联性。
• UnTraceabiltiy：对于不可追踪性来说，与Monero相同，ZCash中的z地址之间的交易可以同时保护发送方的隐私，接收方的隐私，同时也隐藏了交易数额，这也追踪某个人的交易记录变得几乎不可能。
• Convencience：目前的ZCash钱包，如果需要实现Z地址之间的转账，需要使用桌面电脑才能完成，其他的钱包只能完成t地址和t地址以及t地址和z地址之间的转账，这使得其便利性大打折扣，此外，涉及到z地址的转账，都需要用到零知识证明，需要更多的计算时间。

总结

Dash币中的PrivateSend有助于用户混淆自己的地址，但不能做到隐匿交易双方地址以及交易金额，使得第三方难以对交易记录进行追踪，同时也难以关联交易。但是由于在PrivateSend的过程中会有MasterNode的参与，MasterNode知道PrivateSend交易中的input和output的对应关系，同时MasterNode大部分都运行在云服务提供商的服务器上，如果MasterNode被控制，那么用户的交易隐私会暴露，在便利性方面，PrivateSend只能在DashCore桌面版本上使用，同时PrivateSend混币过程中需要其他用户的参与，需要的等待时间较长，此外，除了官方桌面版DashCore钱包外，其他钱包无法支持PrivateSend。

Monero中通过Stealth address的使用，使得第三方难以发现接收方的地址，保护了接收方的隐私，而使用Ring Signature则保护了发送方的隐私，第三方难以发现真正的发送方地址，但是Monero中不能隐藏发送方和接收方的地址。后续采用的Ring Confidential Transactions 可以隐藏交易金额，使得匿名性更强。Monero的便利性方面，在其钱包的使用情况上便利性上不存在这些问题，其便利性较好。但是Monero并非无懈可击，如果有人在Monero区块链中发布大量的小额交易，随后这些交易被用来当做decoy input时，那么就有可能追踪到其他人交易中的真正的input，引发瀑布效应，从而追踪到更多的交易信息。

ZCash中使用零知识证明，z地址之间的转账，可以直接隐藏发送方和接收方的地址，相比于Dash和Monero，具有更高的匿名性，在便利性方面，ZCash和Dash面临着同样的问题，两种币涉及到Z地址的转账，都需要桌面版ZecWallet的官方客户端的支持，便利性上两者都不如Monero。

Dash学习资料

• github-达世币白皮书

• Dash英文白皮书

• 达世币-中文帮助文档

• privateSend(匿名支付)

• Dash github 源代码

• PrivateSend

• reddit 上dash的介绍

Dash 匿名性分析

• Battle of the Privacycoins: Why Dash Is Not Really That Private

• Monero vs Zcash vs Dash: which is the most anonymous cryptocurrency?

• An in-depth analysis of Dash Cryptocurrency

• privacy-Dash VS Monero

• Dash Forum

• Dash VS Monero

• BlockSCI attack Dash

Dash的主要特征

• Launch: Dash was fairly launched under the name “XCoin”, very shortly after renamed “Darkcoin” on Janury 18th, 2014. It rebranded to “Dash” which stands for “Digital Cash” in March of 2015.

• Limited Supply: Maximum coin supply of Dash will be somewhere around 18.4 and 19.7 million. It can’t be known for certain because it’s impossible to know how much Dash will be requested from the Treasury each month (more on the “Treasury” below). You can view one possible inflation schedule here. Here is a script developed by a Dash Core Team developer showing inflation until the year 2225. Click “Run” to see it in action.

• Open Source: You can read the source code yourself here.

• Masternodes: Pioneered by Dash. While anyone is able to run a full node and thus support the Dash network, anyone with at least 1,000 Dash (akin to a collateral but impossible to lose during or after operation) is also able to run a Masternode, which offers additional services to the network and earn 45% of the block reward. The Masternode count over time is shown in this graph. Masternode operators are also granted one vote per node (see below).

• Decentralized Governance by Blockchain: Dash pioneered a blockchain governance system that is utilized for quick decision making in the project. Dash settled a debate on the size of its blocks in less than 24 hours. The same debate that has been going on in Bitcoin for several years. Dash is the first project that invented, developed and actively uses a blockchain based governance directed by “shareholders” with “skin in the game” (Masternode operators) looking out for their own and thus the network’s best interests.

• The Dash Treasury & proposal grants: Each month Masternode operators vote on budget proposals that aim to produce value for Dash as a whole. Anyone can make a proposal, ask the Masternode electorate for a grant in Dash and receive funding directly from the Dash blockchain.

• Self-sustainable development: The current Dash development team is paid directly from the blockchain, a novel approach that was pioneered by Evan Duffield, the creator of Dash, and has since then been copied by dozens of other projects in one way or another. Note that the Core Team could theoretically be voted out of a funding anytime, maintaining decentralization of the project unlike in other cryptocurrency projects.

• InstantSend: Another first invented by Dash. This technology allows Dash to be used in point-of-sale situations where a locked payment is sent in about 1 second, while not being exposed to double spends that other cryptos are susceptible to. For many this is Dash’s “killer feature” because InstantSend makes Dash the first cryptocurrency fully suitable for use in brick and mortar businesses.

• PrivateSend is the feature that gives Dash users the ability to erase the transactional history of received coins and thus send funds anonymously. Originally based on the CoinJoin-principle by Gregory Maxwell but heavily modified with mixing ahead of the spending transaction and other major improvements, avoiding the well known & fatal flaws of CoinJoin.

• Fungibility is the result of offering PrivateSend mixing on the network. Erasing the history of each Dash transaction before you spend it makes your Dash just as valuable as freshly minted coins. No more tainted funds.

• Dash-Evolution: This is the next generation of Dash. It will make Dash the most user-friendly cryptocurrency in the world. So user-friendly that even your grandmother could use it! Check out the Demo!

• A very clear vision of the future via on-chain scaling: The current Dash roadmap details the path to Evolution. Founder Evan Duffield also put out two manifesto articles elaborating on what Dash wants to achieve and how to get there.

Dash Blaock Explorers

• Official Dash.org Block Explorer

• Block Explorer by Cryptoid

Dash’s network

There are two main tiers in Dash, the miners and the master nodes. The Miners carry out similar functions to those in the bitcoin network. The master nodes are responsible for governance functions and for carrying out special transactions- InstantSend and PrivateSend.

InstantSend enables near-instantaneous transactions and is claimed to prevent double-spending, a potential problem with other cryptocurrencies. Regular block times are two and a half minutes whereas InstantSend transactions can be processed in under a second.

Decentralized Governance by Blockchain(DGBB), Dash attempt to solve two problems: governance and funding.

• Governance

• The DGBB system allows each masternode to vote once for each proposal. This is a bit like block producer(BP) in EOS. If a proposal passes, it can then be implemented by Dash’s developers.

• Funding

• DGBB provides a means for Dash to fund its own development.
  The network funds itself by reserving 10% of the block reward for budget projects.

MasterNode

• Distribution of 4765 Dash Masternodes (Summary by ISP)

• Distribution of 4765 Dash Masternodes V3
  (Summary by Country)

Masternodes are dedicated servers on the internet that enable instant transactions and perform the trustless anonymization of users’ funds. Further they’re the backbone of Dash’s governance model and the foundation of coming features in “Dash Evolution”. Masternodes require 1,000 Dash as “collateral” (you can’t lose the Dash, only its value), a secured server, a full-time Internet connection, and periodic updates. In return they receive 45% of the block reward which at current rates and number of nodes amounts to 1.8 Dash every 6-7 days.

Random Choose Masternode

A special deterministic algorithm is used to create a pseudo-random ordering of the masternodes. The pseudocode of selecting a masternode:

1
2
3
4
5
6
7
8
9
10

for( auto& masternode : masternodes){
    current_score = masternode.CalculateScore();
    wining_node = masternode;
}
CMasterNode::CalculateScore(){
  pow_hash = GetProofOfWorkHash(nBlockHeight);// get the hash of this block
  pow_hash_hash = hash(pow_hash);// hash the POW hash to increase the entropy
  difference = abs(pow_hash_hash - masternode_vin);
  return difference;
} 

Function of Masternode

1. Trustless Quorums

With the addition of the masternode network and the collateral requirements, we can use this secondary network to do highly sensitive tasks in a trustless way, where no single entity can control the outcome. By selecting N pseudo random masternodes from the total pool to perform the same task, these nodes can act as an oracle, without having the whole network do the task.

As an example, implementation of a trustless quorum , which uses quorums to approve transactions and lock the inputs or the proof-of-service implementation.

Another example use for trustless quorums can include utilizing the masternode network as a decentralized oracle for financial markets, making secure decentralized contracts a possibility.

2. Proo-Of-Service

To reduce the possibility of people using the system to their advantage nodes must ping the rest of the network to ensure they remain active. This work is done by the masternode network by selecting 2 quorums per block. Quorum A checks the service of Quorum B each block. Quorum A are the closest nodes to the current block hash, while Quorum B are the furthest nodes from said hash.

Block-Reward

• 45% of block rewards go to miners.

• 45% of block rewards go to masternodes.

• 10% of block rewards go to the Decentralized Governance Budget.

Masternodes vs mining

• masternodes powers the second tier, which enable financial privacy(PrivateSend), instant transactions(instantSend), and the decentralized governance and budget system. Since the masternodes carry out a great function, 45% of block reward goes to masternodes.

• masternodes have the power to reject improperly formed blocks from miners, if a miner tried to take the entire block reward for themselves or tried to run an old version of the Dash software, the masternode network would orphan that block.

• masternodes do not mine. each masternode is “secured” by 1000 DASH. Those Dash remain under the sole control of their owner at all times, and can still be freely spent. the funds are not locked in any way. if the funds are moved or spent, the associated masternode will go offline and stop receiving rewards.

• Miners powers the first tier, which is the basic sending and receiving of funds and prevention of doublespending.

• Miners do not serve as masternodes.

PrivateSend

PrivateSend is an implementation of CoinJoin. The privacy solution first proposed for Bitcoin by Bitcoin Core developer Gregory Maxwell. In PrivateSend, three users add their coins together in one big transaction, that sends the coins to freshly generated addresses belonging to the same three users. As such, the coins are effectively mixed between the three participants, breaking the blockchain trail of ownership between them. This process can be automatically repeated up to 16 times, with different mixing participants, for extra privacy.

PrivateSend is done by masternodes.

The step of PrivateSend is following:

1. Breakingdown a user’s transaction input into discrete denominations, with these denominations being: 0.01 DASH, 0.1 DASH, 1 DASH and 10 DASH.

2. A user’s Dash wallet will initiate a request to a Dash masternode, the masternode made aware that a user would like to mix a certain denomination of Dash coins. No identifiable information is sent to the masternodes, so they do not know who you are.

3. The masternode then issue a message to the network indicating that is ready to mix a denomination, and there is a users waiting.

4. Two other individuals who also wish to mix the same denomination of Dash coins can connect to the masternode that is hosting the other user’s transaction.

5. Start a mixing session, the masternode mixes up the inputs and instructs all three users’ wallets to pay the now-mixed input back to themselves.

6. A user’s wallet must repeat this mixing session multiple times(each time is called a round) to ensure that fund origins are fully anonymized.

• NOTE 1: Funds involved in the mixing process never leaves a user’s wallet, ensuring the entire process can remain trustless and secure.

• NOTE 2: Your wallet only contains 1000 of these “change addresses”. Every time a mixing event happens, one of your addresses is used up. Once enough of themn are used, your wallet must create more addresses. It can only do this, however, if you have automatic backups enabled. Consequently, users who have backups disabled will also have PrivateSend disabled.

• NOTE 3: To address DOS attacks, Dash developers propose all user submit a transaction as collateral to the pool when joining. When a user submits a request to the mixing pool, they must provide collateral at the beginging of this exchange. if at any point any user fails to cooperate, by refusing to sign for example, the collateral transaction will be broadcast automatically. This will make it expensive to carry out a sustained attack on the privacy network.

• NOTE 4: As of April 2019, PrivateSend is available in Desktop(Dash Core, Dash Electrum)/Mobile(Dash Electurm)/Web(MyDashWallet) wallets.

An example of PrivateSend

PrivateSend Security Considerations

as transactions are merged, masternodes can possibly “snoop” on users funds as they pass through. This is not considered a serious limitation due to the requirement for masternode’s to hold 1000 DASH, on the other hand, users utilize random masternodes to host their joins, so the probability of following a transaction throughout a chaining event can be calculated as follows:

Where:

• n is the total number of nodes controlled by the attacker.

• t is the total number of masternodes in the network.

• r is the depth of the chain.

Blinding Masternodes

Alough the probability of masternodes to snoop the user’s join is low, but the security problems still exists. This potential danger can be addressed by blinding masternodes so they cannot see which inputs/outputs belong to which users.

• relay system

  Dash uses relay system to protect user’s identity. Instead of a user submitting the inputs and outputs directly into the pool, they will pick a random masternode from the network and request that it relays the inputs/outpus/signatures to the target masternode. This means that the masternode will receive N sets of inputs/outputs/ and N sets of signatures. Each set belong to one of the users, but the masternode can’t know which belongs to which.

Dash Wallet

There are many wallet that support dash, details are in here.

Monero 名词解释

Monero(XMR) 是一个安全，隐私和不可追踪的加密货币。通过使用密码学中一种特殊的方法，门罗确保了所有交易保持 100% 的不可关联和不可追溯性(unlinkability and untraceability)。

• Unlinkability： 对于任意的两笔交易，无法证明这两笔交易是发送给同一个人。
  • Monero中实现这种特性使用了Stealth Public Address，每次发送方发送XMR时都会发送到随机生成的这个地址，称之为Stealth Public Address。
• Untraceability： 一笔交易中的inputs中有很多其他交易的output，无法证明真正花出去的是到底是哪一个output。
  • Monero中实现不可追踪性，采用环形签名（Ring Signature）。

• view key： Monero中有一个public view key 和private view key。

  • public view key 用于生成一次性的stealth public address(隐匿的公开地址)，XMR将会通过这个地址发送给接受者。
  • private view key 用于接收者扫描区块链来找到发送给他们的资金。

• spend key：也有public spend key和private spend key。

  • public spend key帮助发送方参与环交易(ring transaction) ,并且验证密钥镜像(key image)的签名。
  • private spend key 帮助创建密钥镜像，密钥镜像使得发送方能够发送交易。

  ---

Monero地址

Monero地址是一个95个字符的字符串，分别由public spend key 和public view key构成。下图是地址生成的图解。

注意： 所有的Monero地址都是以4开头。

Stealth Public Address

• Stealth Public Address：如果 Alice 要给 Bob 发送门罗币，除了 Alice，应该没人任何人知道 Bob 就是这笔钱的接收者。为了做到不可追踪性，Alice利用Bob的public view key 和public send key来随机生成一个一次性的公钥地址，叫做Stealth public Address 。假设Bob的view key的公私钥对是$(A, a)$, spend key 的公私钥对是$(B,b)$, 其中$A = aG, B = bG$, G是一个密码学常数，的生成过程如下：

  • 随机产一个$r，r∈[1, l]， l$是G的一个素数阶。

  • 令 $R = rG, P = H_s(rA)G+B， H_s()$是Monero中使用的Keccak哈希算法。

  • 生成的Stealth public Address 即为P。

现在对P进行如下的推导：

$$P =\\ H_s(rA)G+B =H_s(raG)G+bG \\=G(H_s(raG)+b)=G(H_s(Ra)+b)$$

Alice告诉Bob这笔转账所在的区块号和交易号，Bob利用R、private view key a 和 private spend key b计算$P = G(H_s(Ra)+b)$找到交易中的所有output，然后寻找相应的output中是否存在某个输出地址为P，如果存在，则可以证明Alice确实给Bob转账了.

注意： 对于其他人来说，由于不知道Bob的private view key 和private spend key，其他人无法知晓Alice给Bob转账的地址是哪里。

Key Image

Key Image：Alice 和 Bob之间的转账只有他们两个人知道，那么作为验证交易的矿工，如何确保Alice不会把同一个UTXO消费2次呢？这里就需要用到Key Image，定义如下：
* $Key Image = sH(P),s$是Alice 的private spend key， H()是哈希函数。
对于对于相同的UTXO，其地址为P，Alice 的private spend key 也是唯一的，因此Alice第二次花费的时候提供生成的Key Image也是相同的，每一笔消费矿工都会记录相应的Key Image，再次出现相同的Key Image时，矿工就会拒绝这笔交易，这就可以防止双花。

需要说明的是，这里的P不是指Alice发给Bob时生成的stealth address， 而是Alice花费的UTXO所在的地址，因为对于同一个UTXO，其地址P不会变化，Alice的private spend key也不变。因此对应于同一个UTXO，有唯一的Key Image

思考： Key Image的生成最终是乘法得到的，这就感觉有个问题，如果其他人花费自己的UTXO时生成和Alice相同的Key Image的时候，但是此时如果Alice并没有花费P中的XMR，那么岂不是把Alice的位于P地址中的XMR给冻结了吗？ 另外，如果Alice给出的Key Image不合法，即Alice根本不给出UTXO真正的Key Image，矿工如何判断Key Image的合法性呢？

Ring Signature

Ring Signature： Monero中为了保护发送方的隐私，使用了环形签名，Alice 在给 Bob发送XMR的时候，除了给出花费的UTXO 的真实地址P之外，还会将Monero区块链中其他与P地址中余额相同的UTXO也添加到交易的inputs中，形成一个集合$S = (P_1, P_2, ..., P_m)$。

Alice会将这个集合S作为交易中的inputs一起发布出去，这样对于外界来说(尤其是矿工和Bob)，他们无从知晓Alice具体花费了S集合中的哪一个UTXO，这样就保护了Alice的隐私。其他被Alice添加进来用于迷惑其他人的UTXO称之为mixins，又叫chaff output或者 decoy output，Alice添加mixins的时候，并不需要得到其他用户的同意，Alice自行决定添加的mixins的数目。Monero中使用Ring Signature的主要目的就是实现untraceabity。

Ring Confidential Transactions

Ring Confidential Transactions： 2017年1月10日Monero中正式使用了RingCTs。而在此之前，Monero中假如Alice需要向Bob转12.5个XMR，则需要将自己的UTXO分别发送至三个地址，分别转账10XMR、2XMR和0.5XMR，这是因为Monero中要求转账的XMR格式为$A ×10^{B}$的格式。使用了RingCTs之后，在区块链上隐藏了交易数额，这时候Alice挑选mixins的时候，不用考虑mixins的XMR的余额，提升了交易的隐私性。