Zhuang's Diary

女巫攻击Sybil_Attack

Posted on 2018-07-14 Edited on 2023-09-14

什么是女巫攻击？

在对等网络中，但节点通常具有多个身份标识，通过控制系统的大部分节点来消弱冗余备份的作用。

八卦一下这个名字的来路：

根据 Flora Rhea Schreiberie 在1973年的小说《女巫》（Sybil）改编的同名电影，是一个化名 Sybil Dorsett 的女人心理治疗的故事。她被诊断为分离性身份认同障碍，兼具16种人格。

女巫攻击是在P2P网络中，因为节点随时加入退出等原因，为了维持网络稳定，同一份数据通常需要备份到多个分布式节点上，这就是数据冗余机制。女巫攻击是攻击数据冗余机制的一种有效手段。

如果网络中存在一个恶意节点，那么同一个恶意节点可以具有多重身份，就如电影的女主角都可以分裂出16个身份，那么恶意节点比女猪脚更加分裂。这一分可好，原来需要备份到多个节点的数据被欺骗地备份到了同一个恶意节点（该恶意节点伪装成多重身份），这就是女巫攻击。

怎么解决女巫攻击？

一种方法是工作量证明机制，即证明你是一个节点，别只说不练，而是要用计算能力证明，这样极大地增加了攻击的成本。

另一种方法是身份认证（相对于PoW协议，女巫攻击是基于BFT拜占庭使用容错协议的Blockchain需要考虑的问题，需要采用相应的身份认证机制）。

认证机制分为二类：

1）基于第三方的身份认证

每加入一个新的节点都需要与某一个可靠的第三方节点进行身份验证。

2）纯分布式的身份认证

每加入一个新的节点都需要获得当前网络中所有可靠节点的认证，这种方法采用了随机密钥分发验证的公钥体制的认证方式，需要获得网络中大多数节点的认证才能加入该网络。

简评三个基于VRF的共识算法

Posted on 2018-07-14 Edited on 2023-11-17

[转]https://www.jianshu.com/p/2b9fa8633df1

Algorand、Dfinity和Ouroboros Praos三个共识算法（Dfinity虽然是项目名，这里用来称呼其共识算法也应无不妥）近期较受关注，而且都是基于VRF(Verifiable Random Function) 设计，可以对照学习。Algorand的版本很多，以下单指 1607.01341v9，暂称其为Algorand’（笔者手中另有Algorand的最新版本，其中已对下文提及的几处问题完成了修正，可与本文参看）。

一、VRF的共性

VRF的意义很好理解——用以完成出块人（群）的随机选择。为此，VRF的返回值应尽力难以预测。先看Algorand’和Dfinity的套路是怎么做的：大体上是先将前一个随机数（最初的随机数却是协议给定的）和某种代表高度、轮次的变量进行组合，用某种私钥对之进行签名（或者是先签名再组合），最后哈希一下得出最新的随机数。这样产生的随机数旁人很容易验证其合乎算法，”V”就这样得到了；而哈希返回值又是随机分布的，“R”也因此得到保证。在此过程中，为降低操纵结果的可能性，有两个注意事项：A) 签名算法应当具有唯一性，也就是用同一把私钥对同样的信息进行签名，只有一个合法签名可以通过验证——普通的非对称加解密算法一般不具备这个属性，如SM2。如果用的签名算法没有这种uniqueness属性，那在生成新随机数的时候就存在通过反复多次尝试签名以挑出最有利者的余地，会降低安全性。B) 避免在生成新随机数时将当前块的数据作为随机性来源之一，比如引用本块交易列表的merkle root值等等，因为这样做会给出块人尝试变更打包交易顺序、尝试打包不同交易以产生最有利的新随机数的余地。在设计和检视新的共识算法时，以上两个注意事项是要特别留意的。

考察一下VRF的返回结果应该如何运用。目前所见用法中，VRF的返回结果可以用来公开完成节点或节点群体的选择，也可以私密地完成选择。以Dfinity为例，它是利用mod操作来唯一、公开地确定一个Group。Algorand、Ouroboros Praos是私密选择的范例，大致套路是对VRF的最新返回值，配上轮次等变量后用私钥进行签名并哈希，如果哈希值小于某个阈值，节点就可以私密地知道自己被选中。这种方法很可能在网络节点数较多时的表现会更稳定，否则幸运儿个数上下波动会较大，进而影响协议表现，包括空块和分叉。

二、简评强同步假设版本的Algorand

私密选择提供了较强的抗击定点攻击的能力，但由于幸运儿的总数对于任何一个幸运儿都是不能预知的，也因此给后续共识算法的设计和区块链的优化带来了困难。Algorand‘采用了很强的同步网络假设（同步网络假设下的共识算法当然容易做一些），要求预先知道网络消息传播时间的上限：在固定时间内完成对固定比例的用户的网络传播。比如要知道，1KB消息，在1秒钟内完成全网95%的传播，而1MB消息需要1.5分钟完成全网95%的传播。但这个传输上限应该如何选择？通过一段时间的统计结果再乘以一个系数这种经验统计？只能说“感觉上可以”，但如果要严谨和安全，Algorand‘算法应该补充证明即使在遭遇DDOS或互联网拥堵的情况下消息传播严重超限后算法仍然能够保证安全——然而这个证明是缺失的。作为对照，Ouroboros Praos公开承认之前在同步网络假设下设计的Ouroboros协议在异步网络条件下会出错，所以才又做了Ouroboros Praos；新版本的Algorand承认在弱同步网络时会在不同的块上达成共识（后续网络恢复强同步时分叉可以得到解决）云云，这些都可资参考。

即使我们暂且认可Algorand’算法可以通过设定一个很大的传播时间上限来回应上述问题，但随之而来的是此时可以看出此算法缺乏一个非常好的特性：Responsiveness。这个特性指的是：若一个协议被设计为在一个较大的传播时间上限DELTA下工作，但若实际传播时间是较小的delta，则协议的实际推进步调将只和delta有关，这种协议被称为Responsive的。具有Responsive特性的共识算法再配以同步网络假设会非常理想——出于安全，上限可以设置很大，然而协议执行速度只和当时网络条件有关。Algorand’并不具有这种特性。平均而言，Algorand’完成共识所需的消息传送次数是11轮，每轮如果要确保安全，完成共识的时间就会很长，单个分区的吞吐量就不会太高。当然，架构设计涉及很多取舍，最终评价一个算法好还是不好还是要回到初心——准备拿来实现的目标是什么。上述分析只是尝试客观地指出Algorand’算法的几个少为人知的固有特征，供读者自行评估。

三、简评Dfinity的可扩展性问题

私密选择并且立即上任的做法，也给系统分片带来了极大挑战。Dfinity是明确要做分片(Sharding)的，所以必须直面挑战。可扩展性问题非常复杂，完整解决这个问题需要通盘考虑网络、存储、计算三方面的可扩展性——时下大多数区块链3.0项目只注意到计算的分片和可扩展性，忽略了其余二者，从而不可能真正实现理想的扩展。由于公链节点网络带宽的制约，计算合约所需的数据通常很难迅速地从一个节点拷贝到另一节点，所以就算用VRF实现了飘忽来去的出块节点选择，存储节点是没法同样飘逸如风的。明显的选择有那么几个：全部节点存储全部数据，不同节点静态地分配用来存储不同分区。前者的可扩展性很差，对于后者而言，如果出块节点漂浮不定且出块节点还需要完成合约运算，就意味着基于P2P网络来回远程访问存储，性能多半急剧下降；动态决定的出块节点只完成排序共识，计算能力和存储捆绑，通过静态分区提供可扩展性，可能是合理的应对。然而，最可恨的就是“然而”二字——即使如此，系统还存在一处对存储和网络构成压力的所在：最终用户提交的待打包交易。普通公链（先不考虑EOS那种）的带宽有限，如果用户提交的待打包交易必须粗放型地全网泛滥传播，那现有网络带宽可以提供多少TPS？如果出块节点是静态分区或者至少提前一段时间公开知晓，事情尚有回旋余地；如果出块节点是如此飘忽不定，而且直到最后一刻也只有这些节点自己知道，那无论是用户还是出块节点候选人看起来最直接的应对之道就是全网泛滥传播全部待打包交易、保存全部待打包交易，这样带宽和存储仍然成为系统瓶颈。

所以这里碰到的，本质上还是安全、可扩展性、去中心化的不可能三角。

四、简评Ouroboros Praos

BM怼 Ouroboros的文字已经流传广泛。BM的话当然有些明显是不对的，比如Ouroboros的DPOS是指”Dynamic [stake distribution] POS”而不是BM的Delegate POS，但其关于Pareto分布的评论则值得玩味。如果我们仔细浏览后出的Ouroboros Praos，可以发现协议的安全假设和安全证明完全没有考虑经济博弈因素，因此洋洋洒洒的证明很可能会不得要领而错过真正需要防护的方向——毕竟一直以来POS/DPOS这些协议的血管里面流淌的就是基于经济博弈和人性进行设计的血液。最明显的例子是在forward secure signature的实现方法上，协议目前的设计是要求每个好的节点自觉主动地安全删除用过的私钥，而完全没有考虑近乎零的私钥保存成本如何面对bribe attack的诱惑，然而这却是值得考虑的。除了形式化证明之外，Ouroboros Praos本身并没有太多值得关注的协议特征，总体上就是用VRF抽签结合POS算法并针对某些安全假设进行了形式化证明，其做事的态度是非常值得赞赏的。

五、总结

这几个算法本身颇有创意，也很值得学习。与此同时，在看过以太坊CASPER目前披露的分区技术后，笔者的体会是：区块链3.0的竞争才刚刚开始，从以太坊团队的技术路线看，他们的技术考量和选择要比很多宣称要超越以太坊的团队来得深刻和全面。如果当真要超越以太坊，还是应该先从理解以太坊开始。

pbft图解

Posted on 2018-06-25 Edited on 2022-08-28

参考链接：https://github.com/bigpicturelabs/consensusPBFT

Definitions of each abbreviation in the diagram are;

m: Request message object
c: Client ID
t: Timestamp
v: View ID
n: Sequence ID
i: Peer(Node) ID
r: Result of the request’s operation

Why count >= 2 ?

In the diagram, the peer change its state to prepared or committed when the count value, which is the number of verified messages from other peers, is larger than 2. Actually, the condition is count >= 2*f where f is the maximum number of faulty peers, which the network can tolerate. In this case, f is just 1, so the condition is count >= 2.

What is the reply message?

Every node replies the result of the request’s operation to the client individually. The client will collect these reply messages and if f + 1 valid reply messages are arrived, the client will accept the result. In this sample implementation, there is no client. So, every node including the primary will return its reply message to the primary.

golang 随机数

Posted on 2018-06-25 Edited on 2022-09-29

随机数主要分为以下三类：

弱伪随机数
强伪随机数
真随机数

随机数的分类是根据随机数的性质进行的分类。随机数的性质分为以下三类：

随机性一不存在统计学偏差，是完全杂乱的数列
不可预测性一不能从过去的数列推测出”下一个出现的数
不可重现性一除非将数列本身保存下来，否则不能重现相同的数列

密码技术中所使用的随机数,仅仅具备随机性是不够的，至少还需要具备不可预测性才行。

GoLang 中的伪随机数

在 GoLang 中，我们可以通过 math/rand 包里的方法来生成一个伪随机数：

package main

import (
  "fmt"
  "math/rand"
)

func main() {
  fmt.Println(rand.Int())   // => 134020434
}

你会发现运行的结果一直是 134020434，怎样才能显示不同的结果，需要了解一下“随机种子”的概念。

随机种子

伪随机数，是使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机。

那么自然，在计算伪随机数时假如使用的开始值不变的话，那么算法计算出的伪随机数的数序自然也是不变的咯。

这个“开始值”，就被称为随机种子。

可以通过 rand.Seed 方法设置随机种子，如果不设置，则默认值显示为 1，为了保证每次伪随机数生成器工作时使用的是不同的种子，通常的做法是采用当前时间作为种子。

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {

    rand.Seed(int64(time.Now().Unix()))
    fmt.Println(rand.Intn(100))     
}

真随机数

如果我们的应用对安全性要求比较高，需要使用真随机数的话，那么可以使用 crypto/rand 包中的方法。

package main

import (
  "crypto/rand"
  "fmt"
  "math/big"
)

func main() {
    result, _ := rand.Int(rand.Reader, big.NewInt(100))
    fmt.Println(result)
}

go pprof trace完整操作

Posted on 2018-06-07 Edited on 2022-09-29

第一步：也是最重要的一步，就是下载谷歌浏览器！

第二步：下载 Graphviz http://graphviz.org/download/
安装后配置环境变量，再path里面添加安装目录！

第三步：添加以下测试代码（添加 _”net/http/pprof” 不然不会有效果！）

具体看源码

1 package main
2 import (
3    "net/http"
4    "runtime"
5    "os"
6    "fmt"
7    "runtime/trace"
8    _"net/http/pprof"
9    "runtime/debug"
10   "time"
11   "sync"
12 )
13 func main() {
14   //开启强大的分析器
15   go pprof()
16    //以下是运行测试(也可以贴你自己的)代码
17   var c sync.Map
18   for i:=0;i<100;i++{
19      time.Sleep(time.Second*1)
20      go func(){
21         for j:=0;j<1000000;j++{
22            time.Sleep(time.Millisecond*20)
23            c.Store(fmt.Sprintf("%d",j),j)
24            fmt.Println(c.Load(fmt.Sprintf("%d",j)))
25         }
26      }()
27   }
28   time.Sleep(time.Second*20)
29    fmt.Scan()
30 }
31 //运行pprof分析器
32 func pprof(){
33   go func() {
34      //关闭GC
35      debug.SetGCPercent(-1)
36      //运行trace
37      http.HandleFunc("/start", traces)
38      //停止trace
39      http.HandleFunc("/stop", traceStop)
40      //手动GC
41      http.HandleFunc("/gc", gc)
42      //网站开始监听
43      http.ListenAndServe(":6060", nil)
44   }()
45 }
46 //手动GC
47 func gc(w http.ResponseWriter, r *http.Request) {
48   runtime.GC()
49   w.Write([]byte("StartGC"))
50 }
51 //运行trace
52 func traces(w http.ResponseWriter, r *http.Request){
53   f, err := os.Create("trace.out")
54   if err != nil {
55      panic(err)
56   }
57   err = trace.Start(f)
58   if err != nil {
59      panic(err)
60   }
61   w.Write([]byte("TrancStart"))
62   fmt.Println("StartTrancs")
63 }
64 //停止trace
65 func traceStop(w http.ResponseWriter, r *http.Request){
66   trace.Stop()
67   w.Write([]byte("TrancStop"))
68   fmt.Println("StopTrancs")
69 }