Zhuang's Diary

言之有物,持之以恒

zk-SNARKs 原文链接

参考

Zcash协议规范

解释SNARKs系列文章

1. 同态隐藏

2. 多项式盲评估

3. 系数测试知识和假设

4. 如何验证多项式盲评估

5. 从计算到多项式

6. Pinocchio Protocol — 皮诺曹协议

7. 配对椭圆曲线

8. 零知识证明在 Quorum 中是如何使用的 — Zero Knowledge Proofs and how they can be implemented in Quorum

9. 零知识证明在以太坊智能合约端如何实现区间证明 — zero knowledge range-proof precompiled contract for the go-ethereum client

论文

1. 皮诺曹协议

2. Paramgen白皮书

3. Zerocash论文

技术博客文章

1. Matt Green: 零知识证明

2. Zcash交易解剖

3. 隐私交易如何完成的

4. Zcash的参数是如何生成的

5. 在Rust进行密码学配对

相关项目

1. HAWK:私有的智能合约

2. BOLT:私有的支付通道

后面的博客中会针对上述内容进行分析。

背景

channel,即“管道”,是用来传递数据(叫消息更为合适)的一个数据结构,即可以从channel里面塞数据,也可以从中获取数据。channel本身并没有什么神奇的地方,但是channel加上了goroutine,就形成了一种既简单又强大的请求处理模型,即N个工作goroutine将处理的中间结果或者最终结果放入一个channel,另外有M个工作goroutine从这个channel拿数据,再进行进一步加工,通过组合这种过程,从而胜任各种复杂的业务模型。

goroutine不同于thread,threads是操作系统中的对于一个独立运行实例的描述,不同操作系统,对于thread的实现也不尽相同;但是,操作系统并不知道goroutine的存在,goroutine的调度是有Golang运行时进行管理的。启动thread虽然比process所需的资源要少,但是多个thread之间的上下文切换仍然是需要大量的工作的(寄存器/Program Count/Stack Pointer/…),Golang有自己的调度器,许多goroutine的数据都是共享的,因此goroutine之间的切换会快很多,启动goroutine所耗费的资源也很少,一个Golang程序同时存在几百个goroutine是很正常的。

Go Channel的基本操作语法如下:

1
2
3
4
5
c := make(chan bool)    //创建一个无缓冲的bool型Channel
c <- x //向一个Channel发送一个值
<- c //从一个Channel中接收一个值
x = <- c //从Channel c接收一个值并将其存储到x中
x, ok = <- c //从Channel接收一个值,如果channel关闭了或没有数据,那么ok将被置为false

不带缓冲的Channel兼具通信和同步两种特性,颇受青睐。

模型01-go关键字

直接加上go关键字,就可以让一个函数脱离原先的主函数独立运行,即主函数直接继续进行剩下的操作,而不需要等待某个十分耗时的操作完成。

1
2
3
4
5
6
7
8
9
func (m *SomeController) PorcessSomeTask() {
var task models.Task
if err := task.Parse(m.Ctx.Request); err != nil {
m.Data["json"] = err
m.ServeJson()
return
}
go task.Process()
m.ServeJson()

如果 func(peer Peer) 函数需要耗费大量时间的话,这个请求就会被 block 住。有时候,前端只需要发出一个请求给后端,并且不需要后端立即所处响应。遇到这样的需求,直接在耗时的函数前面加上go关键字就可以将请求之间返回给前端了,保证了体验。

不过,这种做法也是有许多限制的。比如:

  • 只能在前端不需要立即得到后端处理的结果的情况下使用
  • 这种请求的频率不应该很大,因为目前的做法没有控制并发量

模型02-并发控制

上一个方案有一个缺点就是无法控制并发,如果这一类请求同一个时间段有很多的话,每一个请求都启动一个goroutine,如果每个goroutine中还需要使用其他系统资源,消耗将是不可控的。

遇到这种情况,一个解决方案是:将请求都转发给一个channel,然后初始化多个goroutine读取这个channel中的内容,并进行处理。假设我们可以新建一个全局的channel

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
var TASK_CHANNEL = make(chan models.Task)

// 然后,启动多个goroutine:
for i := 0; i < WORKER_NUM; i ++ {
go func() {
for {
select {
case task := <- TASK_CHANNEL:
task.Process()
}
}
} ()
}

// 服务端接收到请求之后,将任务传入channel中即可:
func (m *SomeController) PorcessSomeTask() {
var task models.Task
if err := task.Parse(m.Ctx.Request); err != nil {
m.Data["json"] = err
m.ServeJson()
return
}
// go task.Process()
TASK_CHANNEL <- task
m.ServeJson()
}

这样一来,这个操作的并发度就可以通过WORKER_NUM来控制了。

模型03-处理channel满的情况

不过,上面方案有一个bug:那就是channel初始化时是没有设置长度的,因此当所有WORKER_NUM个goroutine都正在处理请求时,再有请求过来的话,仍然会出现被block的情况,而且会比没有经过优化的方案还要慢(因为需要等某一个goroutine结束时才能处理它)。因此,需要在channel初始化时增加一个长度:

1
var TASK_CHANNEL = make(chan models.Task, TASK_CHANNEL_LEN)

这样一来,我们将 TASK_CHANNEL_LEN 设置得足够大,请求就可以同时接收 TASK_CHANNEL_LEN 个请求而不用担心被block。不过,这其实还是有问题的:那如果真的同时有大于 TASK_CHANNEL_LEN 个请求过来呢?一方面,这就应该算是架构方面的问题了,可以通过对模块进行扩容等操作进行解决。另一方面,模块本身也要考虑如何进行“优雅降级了”。遇到这种情况,我们应该希望模块能够及时告知调用方,“我已经达到处理极限了,无法给你处理请求了”。其实,这种需求,可以很简单的在Golang中实现:如果channel发送以及接收操作在select语句中执行并且发生阻塞,default语句就会立即执行。

1
2
3
4
5
6
7
8
select {
case TASK_CHANNEL <- task:
//do nothing
default:
//warnning!
return fmt.Errorf("TASK_CHANNEL is full!")
}
//...

模型04-接收发送给channel之后返回的结果

如果处理程序比较复杂的时候,通常都会出现在一个goroutine中,还会发送一些中间处理的结果发送给其他goroutine去做,经过多道“工序”才能最终将结果产出。

那么,我们既需要把某一个中间结果发送给某个channel,也要能获取到处理这次请求的结果。解决的方法是:将一个channel实例包含在请求中,goroutine处理完成后将结果写回这个channel。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type TaskResponse struct {
//...
}

type Task struct {
TaskParameter SomeStruct
ResChan *chan TaskResponse
}

//...

task := Task {
TaskParameter : xxx,
ResChan : make(chan TaskResponse),
}

TASK_CHANNEL <- task
res := <- task.ResChan
//...

(这边可能会有疑问:为什么不把一个复杂的任务都放在一个goroutine中依次的执行呢?是因为这里需要考虑到不同子任务,所消耗的系统资源不尽相同,有些是CPU集中的,有些是IO集中的,所以需要对这些子任务设置不同的并发数,因此需要经由不同的channel + goroutine去完成。)

模型05-等待一组goroutine的返回

将任务经过分组,交由不同的goroutine进行处理,最终再将每个goroutine处理的结果进行合并,这个是比较常见的处理流程。这里需要用到WaitGroup来对一组goroutine进行同步。一般的处理流程如下:

1
2
3
4
5
6
7
8
9
10
11
var wg sync.WaitGroup
for i := 0; i < someLen; i ++ {
wg.Add(1)
go func(t Task) {
defer wg.Done()
//对某一段子任务进行处理
} (tasks[i])
}

wg.Wait()
//处理剩下的工作

模型06-超时机制

即使是复杂、耗时的任务,也必须设置超时时间。一方面可能是业务对此有时限要求(用户必须在XX分钟内看到结果),另一方面模块本身也不能都消耗在一直无法结束的任务上,使得其他请求无法得到正常处理。因此,也需要对处理流程增加超时机制。

我一般设置超时的方案是:和之前提到的“接收发送给channel之后返回的结果”结合起来,在等待返回channel的外层添加select,并在其中通过time.After()来判断超时。

1
2
3
4
5
6
7
8
9
10
11
task := Task {
TaskParameter : xxx,
ResChan : make(chan TaskResponse),
}

select {
case res := <- task.ResChan:
//...
case <- time.After(PROCESS_MAX_TIME):
//处理超时
}

模型07-广播机制

既然有了超时机制,那也需要一种机制来告知其他 goroutine 结束手上正在做的事情并退出。很明显,还是需要利用channel来进行交流,第一个想到的肯定就是向某一个chan发送一个struct即可。比如执行任务的goroutine在参数中,增加一个 chan struct{} 类型的参数,当接收到该channel的消息时,就退出任务。但是,还需要解决两个问题:

  1. 怎样能在执行任务的同时去接收这个消息呢?
  2. 如何通知所有的goroutine?

对于第一个问题,比较优雅的作法是:使用另外一个channel作为函数的输出,再加上select,就可以一边输出结果,一边接收退出信号了。

另一方面,对于同时有未知数目个执行goroutine的情况,一次次调用 done <-struct{}{},显然无法实现。这时候,就会用到golang对于channel的tricky用法:当关闭一个channel时,所有因为接收该channel而阻塞的语句会立即返回。示例代码如下:

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
// 执行方
func doTask(done <-chan struct{}, tasks <-chan Task) (chan Result) {
out := make(chan Result)
go func() {
// close 是为了让调用方的range能够正常退出
defer close(out)
for t := range tasks {
select {
case result <-f(t):
// do task
case <-done:
return
}
}
}()

return out
}

// 调用方
func Process(tasks <-chan Task, num int) {
done := make(chan struct{})
out := doTask(done, tasks)

go func() {
<- time.After(MAX_TIME)
//done <-struct{}{}

//通知所有的执行goroutine退出
close(done)
}()

// 因为goroutine执行完毕,或者超时,导致out被close,range退出
for res := range out {
fmt.Println(res)
//...
}
}

参考:

http://blog.golang.org/pipelines

https://gobyexample.com/non-blocking-channel-operations

web3

Github: https://github.com/ethereum/web3.js/
web3.js是以太坊提供的一个Javascript库,它封装了以太坊的RPC通信API,提供了一系列与区块链交互方法,使js与以太坊交互变得简单。

infura

官网: https://infura.io/
本地安装geth的方法需要花比较多的时间和空间来同步区块,利用infura可以简单很多,infura提供公开以太坊和测试节点,可以利用infura提供的api访问以太坊以及IPFS。去官网只需要提供email注册得到链接即可。

使用web3和infura开发

最常用的操作例如查看一个以太坊地址的ether余额为例(类似etherscan).

通过npm或其他方式引入web3, 并使用infura提供主网/测试网进行初始化。

1
2
3
4
5
6
7
// xxxx为你在infura申请的地址
web3 = new Web3(new Web3.providers.HttpProvider("https://mainnet.infura.io/xxxxxxxx"));
// 接下来就可以调用web3的接口了,例如获取一个地址的ether数量
// wei是以太坊上的的最小单位,ether小数点后18位为一个wei
var balanceWei = web3.eth.getBalance("0xC257274276a4E539741Ca11b590B9447B26A8051").toNumber();
// 从wei转换成ether
var balance = web3.fromWei(balanceWei, 'ether');

至此便可以从以太坊主网上进行操作了,例如查看区块信息,部署智能合约等。
具体开发可以参考以太坊JS API: https://github.com/ethereum/wiki/wiki/JavaScript-API

相关内容:

  1. 以太坊编程 III
  2. 以太坊编程 II
  3. 以太坊编程 I

gRPC 简介:

gRPC 是一款高性能、开源的 RPC(Remote Procedure Call)框架,产自 Google,基于 ProtoBuf 序列化协议进行开发,支持多种语言(Golang、Python、Java等),本篇只介绍 Golang 的 gRPC 使用。因为 gRPC 对 HTTP/2 协议的支持使其在 Android、IOS 等客户端后端服务的开发领域具有良好的前景。gRPC 提供了一种简单的方法来定义服务,同时客户端可以充分利用 HTTP/2 stream 的特性,从而有助于节省带宽、降低 TCP 的连接次数、节省CPU的使用等。

安装:

gRPC 的安装:

1
$ go get -u google.golang.org/grpc

因为 gRPC 是基于 protobuf 实现的接口序列化,所以也要安装 protobuf: 安装及简介教程(Golang 序列化之 ProtoBuf)。

实验:

下面我们使用 gRPC 定义一个接口,该接口实现对传入的数据进行大写的格式化处理。

  1. 创建项目 golang Demo 工程:

client目录下的 main.go 实现了客户端用于发送数据并打印接收到 server 端处理后的数据

  1. server 目录下的 main.go 实现了服务端用于接收客户端发送的数据,并对数据进行大写处理后返回给客户端
  2. example 包用于编写 proto 文件并生成 data 接口
  3. 定义 gRPC 接口:
1
2
3
4
5
6
7
8
9
syntax = "proto3";
package example;
service FormatData {
rpc DoFormat(Data) returns (Data){}
// 此处定义的方法为简单RPC。其余的服务器端流式 RPC,客户端流式 RPC,双向流式 RPC请查询参考链接
}
message Data {
string text = 1;
}

编译 protobuf:

1
protoc --go_out=plugins=grpc:. *.proto // 在 example 目录中执行编译,会生成:data.pb.go

实现 server 端:

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
package main
import (
"gRPCDemo/example"
"net"
"google.golang.org/grpc"
"google.golang.org/grpc/reflection"
"golang.org/x/net/context"
"strings"
"log"
)
// 定义监听地址
const (
HOST string = "localhost"
PORT string = "8080"
)
// 定义接口
type FormatData struct{}
func (fd *FormatData) DoFormat(ctx context.Context, in *example.Data) (out *example.Data, err error) {
str := in.Text
out = &example.Data{Text: strings.ToUpper(str)}
return out, nil
}
// 直接在 main 方法中注册接口
func main() {
// 启动服务器
// 指定我们期望客户端请求的监听端口
listener, err := net.Listen("tcp", HOST+":"+PORT)
if err != nil {
log.Fatalln("faile listen at: " + HOST + ":" + PORT)
} else {
log.Println("Demo server is listening at: " + HOST + ":" + PORT)
}
// 创建 gRPC 服务器的一个实例
rpcServer := grpc.NewServer()
// 在 gRPC 服务器注册我们的服务实现
example.RegisterFormatDataServer(rpcServer, &FormatData{})
reflection.Register(rpcServer)
// 实现阻塞等待,直到进程被杀死或者 Stop() 被调用
if err = rpcServer.Serve(listener); err != nil {
log.Fatalln("faile serve at: " + HOST + ":" + PORT)
}
}

实现 client 端:

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
package main
import (
"google.golang.org/grpc"
"log"
"gRPCDemo/example"
"golang.org/x/net/context"
)
// 定义请求地址
const (
ADDRESS string = "localhost:8080"
)
// main 方法实现对 gRPC 接口的请求
func main() {
// 为了调用服务方法,我们首先创建一个 gRPC channel 和服务器交互。
// 可以使用 DialOptions 在 grpc.Dial 中设置授权认证(如, TLS,GCE认证,JWT认证)
conn, err := grpc.Dial(ADDRESS, grpc.WithInsecure())
if err != nil {
log.Fatalln("Can't connect: " + ADDRESS)
}
defer conn.Close()
// 一旦 gRPC channel 建立起来,我们需要一个客户端 存根 去执行 RPC
client := example.NewFormatDataClient(conn)
// 调用简单 RPC
resp,err := client.DoFormat(context.Background(), &example.Data{Text:"hello,world!"})
// 如果调用没有返回错误,那么我们就可以从服务器返回的第一个返回值中读到响应信息
if err != nil {
log.Fatalln("Do Format error:" + err.Error())
}
log.Println(resp.Text)
}

执行验证结果:
先启动 server,之后再执行 client
client 侧控制台如果打印的结果为: HELLO,WORLD! ,证明 gRPC 接口定义成功。

参考

http://doc.oschina.net/grpc?t=60133

https://github.com/grpc/grpc-go

https://grpc.io/

什么是protobuf

protobuf(Google Protocol Buffers) 是一套完整的 IDL(接口描述语言),出自Google,基于 C++ 进行的实现,开发人员可以根据 ProtoBuf 的语言规范生成多种编程语言(Golang、Python、Java 等)的接口代码,本篇只讲述 Golang 的基础操作。ProtoBuf 所生成的二进制文件在存储效率上比 XML 高 310 倍,并且处理性能高 12 个数量级,这也是选择 ProtoBuf 作为序列化方案的一个重要因素之一。

项目地址

https://github.com/golang/protobuf

安装protobuf

  1. 直接安装

https://github.com/google/protobuf/releases 下载最新版本。例如 Mac 机器下载 osx 版本

Mac 中默认的 go root 地址为 ++/usr/local/go++,将解压缩出来的 protoc 可执行文件 copy 到 /usr/local/go/bin 下。

执行

1
2
$ protoc --version
# 如果正常打印 libprotoc 的版本信息就表明 protoc 安装成功
1
2
Will:bin zhuangweiming$ protoc --version
libprotoc 3.5.1
  1. 编译安装

    1. https://github.com/google/protobuf/releases 下载最新版本,++protobuf-all-3.5.1.tar.gz++。
    2. 解压缩,在终端执行:tar zxvf protobuf-all-3.5.1.tar.gz
    3. 进入文件目录,在终端执行:cd protobuf-3.5.1/
    4. 执行配置,在终端执行:./configure
    5. 编译,在终端执行:make
    6. 检测编译,在终端执行:make check
    7. 安装 protoc,在终端执行:make install

执行

1
2
Will:bin zhuangweiming$ protoc --version
libprotoc 3.5.1

显示 libprotoc 3.5.1 则为成功。

安装 ProtoBuf 相关的 golang 依赖库。获取 goprotobuf 提供的支持库,包含诸如编码(marshaling)、解码(unmarshaling)等功能。

$ go get -u github.com/golang/protobuf/{protoc-gen-go,proto}

使用

1.创建 protocDemo golang工程

2.在 example 包中编写 person.proto

1
2
3
4
5
6
7
8
9
10
11
syntax = "proto3";
package example;

message person { // aa 会生成 Aa 命名的结构体
int32 id = 1;
string name = 2;
}

message all_person { // aa_bb 会生成 AaBb 的驼峰命名的结构体
repeated person Per = 1;
}

3.进入 Demo 工程的 example 目录,使用 protoc 编译 person.proto

1
2
$ protoc --go_out=. person.proto
# 就会生成 person.pb.go 文件

4.在 golang 工程中使用 protobuf 进行序列化与反序列化

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
package main

import (
"github.com/golang/protobuf/proto"
"protocDemo/example"
"log"
)

func main() {
// 为 AllPerson 填充数据
p1 := example.Person{
Id:*proto.Int32(1),
Name:*proto.String("xieyanke"),
}

p2 := example.Person{
Id:2,
Name:"gopher",
}

all_p := example.AllPerson{
Per:[]*example.Person{&p1, &p2},
}

// 对数据进行序列化
data, err := proto.Marshal(&all_p)
if err != nil {
log.Fatalln("Mashal data error:", err)
}
println(data)

// 对已经序列化的数据进行反序列化
var target example.AllPerson
err = proto.Unmarshal(data, &target)
if err != nil{
log.Fatalln("UnMashal data error:", err)
}

println(target.Per[0].Name) // 打印第一个 person Name 的值进行反序列化验证
}

console 输出:

1
2
[26/32]0xc4200140e0
xieyanke

参考链接:
https://github.com/google/protobuf