精华内容
下载资源
问答
  • 2020-01-20 16:27:46

    关键字:Netty BFT-SMaRt Channel findCache KeyLoader Bootstrap NioEventLoopGroup ChannelFuture 视图

    Netty是目前最高效便捷的NIO框架。Netty可提供更加高可用、更好健壮性的稳定大规模连接的IO通道。任何一款区块链早期的技术产品,都是从联盟链开始演进,因为联盟链降低了很多原教旨的难度。回到BFT-SMaRt,它的网络连接分为节点之间的连接,节点与客户端之间的连接。节点之间的连接,我们在BFT-SMaRt:用Java做节点间的可靠信道一文中详细分析了在共识逻辑之前节点之间能够做到的连接准备。那么,本文将继续探索在BFT-SMaRt项目中,节点与客户端之间的连接是如何实现的。

    作为源码研究的起点,有两个现成的入口:

    • 服务端:ServerCommunicationSystem构造函数的最后一个步骤,即clientsConn的创建。
    • 客户端:CounterClient类的入口命令,将本地作为客户端对节点发起访问请求。

    一、Netty服务端的构建

    首先构建服务端,转到ServerCommunicationSystem构造函数的最后一行。

    clientsConn = CommunicationSystemServerSideFactory.getCommunicationSystemServerSide(controller);

    这里采用了工厂模式的设计:构建一个controller基类,业务方可有多个实现类,在工厂get方法中传入实现类对象,通过不同的实现类,返回不同的处理对象。BFT-SMaRt并未有多个实现类,这里可以在上层业务方进行丰富。

    public class CommunicationSystemServerSideFactory {
        public static CommunicationSystemServerSide getCommunicationSystemServerSide(ServerViewController controller) {
            return new NettyClientServerCommunicationSystemServerSide(controller);
        } // 直接返回NettyClientServerCommunicationSystemServerSide对象
    }

    直接返回NettyClientServerCommunicationSystemServerSide对象,以下称NettyClientServerCommunicationSystemServerSide类为Netty服务端类。

    1. 父类构造函数

    直接进入NettyClientServerCommunicationSystemServerSide类的构造函数,函数体内无super指定父类构造函数,因此隐式调用父类SimpleChannelInboundHandler的无参构造函数。

    对于不熟悉继承关系下构造函数的执行顺序的朋友,请自行补充上。

    protected SimpleChannelInboundHandler() {
        this(true);
    }

    父类的无参构造函数指定了本地的有参构造。设定了本地属性autoRelease为true。

    protected SimpleChannelInboundHandler(boolean autoRelease) {
      this.matcher = TypeParameterMatcher.find(this, SimpleChannelInboundHandler.class, "I");
      this.autoRelease = autoRelease;
    }

    接下来执行TypeParameterMatcher的find方法。find方法主要维护一个查找缓存,包括构建和使用。

    ① 查找缓存

    该方法首先获得并配置查找缓存findCache:

    Map<Class<?>, Map<String, TypeParameterMatcher>> findCache = InternalThreadLocalMap.get().typeParameterMatcherFindCache(); // InternalThreadLocalMap容器
    Class<?> thisClass = object.getClass();
    Map<String, TypeParameterMatcher> map = (Map)findCache.get(thisClass); // 类型参数匹配器
    if (map == null) {
    map = new HashMap();
    findCache.put(thisClass, map);
    }

    查找缓存会将热度较高的内容优先缓存,以增进查询速度。

    查找缓存的容器结构是通过InternalThreadLocalMap来构建,注意从SimpleChannelInboundHandler开始,始终带着泛型<I>进入,而本例中的泛型类为TOMMessage,该类是共识排序消息类,将会在BFT-SMaRt共识部分展开介绍。那么,find方法会将泛型类放置到查找缓存findCache中。

    a) 匹配器

    接下来,获得并配置类型参数匹配器,也是用于增强查找。

    TypeParameterMatcher matcher = (TypeParameterMatcher)((Map)map).get(typeParamName);
    if (matcher == null) {
        matcher = get(find0(object, parametrizedSuperclass, typeParamName));
        ((Map)map).put(typeParamName, matcher);
    }
    return matcher;

    匹配器使用到Java的反射机制来查找类。

    首先通过本地map查找类型参数匹配器,如果没有查到,则初始构建。使用调用find时传入的类型参数名,调用find0方法通过反射机制得到泛型类,然后调用get方法通过反射机制获得对应匹配器,最后填充进匹配器map,共同构成查找缓存findCache的内容。最后回顾一下findCache容器的结构。

    Map<Class<?>, Map<String, TypeParameterMatcher>>

    因此,一个类可以有多个对应不同类型参数名的匹配器。

    ② 相关日志

    该缓存的容器结构是InternalThreadLocalMap,类加载进入内存,首先执行static静态方法。

    static {
        logger.debug("-Dio.netty.threadLocalMap.stringBuilder.initialSize: {}", STRING_BUILDER_INITIAL_SIZE);
        STRING_BUILDER_MAX_SIZE = SystemPropertyUtil.getInt("io.netty.threadLocalMap.stringBuilder.maxSize", 4096);
        logger.debug("-Dio.netty.threadLocalMap.stringBuilder.maxSize: {}", STRING_BUILDER_MAX_SIZE);
    }

    打印出日志,StringBuilder的初始化长度以及最大长度。日志输出如下:

    11:18:32.645 [main] DEBUG io.netty.util.internal.InternalThreadLocalMap - -Dio.netty.threadLocalMap.stringBuilder.initialSize: 1024
    11:18:32.645 [main] DEBUG io.netty.util.internal.InternalThreadLocalMap - -Dio.netty.threadLocalMap.stringBuilder.maxSize: 4096

    2. 服务端构造

    回到NettyClientServerCommunicationSystemServerSide的构造函数,首先是配置读取及分析。通过配置文件获得私钥、IP、端口号、节点总数、节点id等信息。

    ① 配置读取

    配置读取可分为三方面:

    • 私钥读取
    • IP加端口号读取处理
    • 配置域信息读取

    a) 私钥读取

    Netty服务端类有一个私有属性字段privKey,用于存储私钥,以备后续签名使用。

    private PrivateKey privKey;

    该字段通过服务端类的构造函数赋值。

    privKey = controller.getStaticConf().getPrivateKey();

    跳转到Configuration类,调用getPrivateKey方法。私钥内容是从配置域controller中获取。

    return keyLoader.loadPrivateKey();

    keyLoader对象是在Configuration类构造时传入。而Configuration类的构造要追踪到其子类TOMConfiguration的构造函数,继续TOMConfiguration是在ViewController构造时调用。这部分内容将在CounterClient入口时展开。回到keyLoader,它是KeyLoader的实例,而KeyLoader有三个子类。

    • RSAKeyLoader,适用于RSA类非对称加密算法簇的秘钥加载。
    • ECDSAKeyLoader,适用于ECDSA类非对称加密算法簇的秘钥加载,全称椭圆曲线数字签名算法。是ECC与DSA的结合。Java原生类库中在jdk1.7以后已经加入支持。
    • SunECKeyLoader,适用于jdk自带的sunEC加密秘钥的加载,位于sun.security.ec.SunEC。

    下面是他们的类图关系。

    b) IP端口号

    接下来是从配置域中读取节点服务器端的IP端口号。

    // 获取IP、端口号
    String myAddress;
    String confAddress = controller.getStaticConf().getRemoteAddress(controller.getStaticConf().getProcessId())
          .getAddress().getHostAddress();
    if (InetAddress.getLoopbackAddress().getHostAddress().equals(confAddress)) {
       myAddress = InetAddress.getLoopbackAddress().getHostAddress();
    }
    else if (controller.getStaticConf().getBindAddress().equals("")) {
       myAddress = InetAddress.getLocalHost().getHostAddress();
       // 如果Netty绑定到环回地址,客户端将无法连接节点。为了解决这个问题,我们绑定到config/hosts.config中提供的地址。
       if (InetAddress.getLoopbackAddress().getHostAddress().equals(myAddress)
             && !myAddress.equals(confAddress)) {
          myAddress = confAddress;
       }
    } else {
       myAddress = controller.getStaticConf().getBindAddress();
    }
    int myPort = controller.getStaticConf().getPort(controller.getStaticConf().getProcessId());

    这段读取代码与上一篇节点间通信如出一辙。但值得注意的是,配置域端口号是由两项组成,我们再次查看配置域内容。

    #server id, address and port (the ids from 0 to n-1 are the service replicas) 
    0 127.0.0.1 11000 11001
    1 127.0.0.1 11010 11011
    2 127.0.0.1 11020 11021
    3 127.0.0.1 11030 11031

    IP后面有两个端口号,第一列为客户端通信端口,第二列为节点间通信端口。就拿节点id为0的第一行举例,本地作为节点服务,其他节点要通过(server <-> server)11001端口进行访问,而其他客户端需要通过(client <-> server)11000端口进行访问。这一段在下面日志输出代码中也有体现。

    logger.info("Port (client <-> server) = "
          + controller.getStaticConf().getPort(controller.getStaticConf().getProcessId()));
    logger.info("Port (server <-> server) = "

    日志打印:

    14:36:19.223 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - Port (client <-> server) = 11000
    14:38:02.617 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - Port (server <-> server) = 11001

    c) 配置域信息

    最后就是配置中的其他信息了。首先看代码,然后看日志输出。

    logger.info("ID = " + controller.getStaticConf().getProcessId());      // 节点id
    logger.info("N = " + controller.getCurrentViewN());                // 节点总数
    logger.info("F = " + controller.getCurrentViewF());                // 节点最大容错数
    logger.info("requestTimeout = " + controller.getStaticConf().getRequestTimeout());
    logger.info("maxBatch = " + controller.getStaticConf().getMaxBatchSize());
    // 根据配置中是否使用签名,打印不同的提示信息
    if(controller.getStaticConf().getUseSignatures() == 1) logger.info("Using Signatures");
                         else if (controller.getStaticConf().getUseSignatures() == 2)           logger.info("Using benchmark signature verification");
    
    logger.info("Binded replica to IP address " + myAddress);
    // SSL/TLS 协议版本
    logger.info("SSL/TLS enabled, protocol version: {}", controller.getStaticConf().getSSLTLSProtocolVersion());

    系统配置中关于是否使用签名的配置项,用于定义客户端是否应该对消息认证码使用签名。

    system.communication.useSignatures

    接下来相关日志输出内容。

    14:36:16.545 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - ID = 0
    14:36:16.989 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - N = 4
    14:36:17.230 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - F = 1
    14:43:47.637 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - requestTimeout = 2000
    14:43:47.637 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - maxBatch = 1024
    14:43:47.637 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - Binded replica to IP address 127.0.0.1
    14:43:47.637 [main] INFO bftsmart.communication.client.netty.NettyClientServerCommunicationSystemServerSide - SSL/TLS enabled, protocol version: TLSv1.2

    ② 服务端配置

    讲到这里,想延伸讨论一下Netty的必要性和实现原理。Netty的必要性可以从Socket(Socket之前的网络传输技术发展就不赘述了)说起。

    a) Netty的必要性

    一个Socket通常是由一个线程来管理,它实现了最初安全可靠的点到点IO通信。但当客户端较多时,可能会耗尽服务端的线程资源,这是一种阻塞IO的模型。实践过程中,大量的由线程维护的网络连接始终在监听状态而没有数据传输,这是对于线程资源的浪费。

    我们在上一篇关于节点间通信的研究中,使用的就是这种模型,然而那是基于节点数量不多的联盟链场景。4节点的网络只需要6条线程即可承担,不用实现复杂逻辑来处理大流量的资源维护,简单稳定的阻塞IO模型显然是更加适用的。但是,本文的研究重点转向了客户端通信,这就需要一个能够处理大流量的新模型。

    设想一种任务加线程池的方式。线程不再死盯着一条两方参与的连接,而是被线程池统一管理起来。网络传输的工作会被放到任务中去,线程池通过调度机制领取任务并执行网络传输工作。在任务多的时候,调度逻辑会将任务排到一个队列中去,然后根据调度机制,启动对应规模的线程数量来控制处理任务的速度。每条线程执行完任务就会自动回归到线程池可用资源库,等待执行新的通信任务。这就是一种非阻塞IO的模型。

    我们继续延伸,所谓的“调度逻辑”是如何接收任务的,这里引用到linux的多路复用IO模型,即一个select可以通过顺序扫描(轮询)的方式监测多个通道是否有通信就绪的状态,一旦有,就会启动一个回调函数将该通信内容封装到任务容器,并排到队列中去。回到函数会启动线程池资源的实例来处理IO的工作,而select将该通信实例交出去以后,就可以释放资源继续监听。

    Netty就是对以上内容的封装框架,更易于使用。

    b) Netty的实现原理

    Netty是基于事件驱动模式的、Reactor线程模型的。事件驱动是相对于主动轮询提出的,主动轮询是说主线程在不断检查是否有事件发生,如果有则调用事件处理函数。事件驱动仍旧是主线程去检查事件的发生,当有事件时将事件放到一个队列,同时还有一条线程在不断的消费这个队列,消费时调用事件的处理函数。事件驱动方式基于主动轮询,又提出了一个线程专门作为事件消费对象,分担了原主线程的工作内容,这取自观察者模式,也更加符合单一职责原则。Reactor线程模型是一种分发机制,首先它会不断的执行selector.select()方法,用来检测并产生新的事件,然后分发事件给到适当的线程来处理。Reactor模型良好地实现了事件驱动理念。Netty应用Reactor线程模型,分为主从关系,主线程用于发现事件,从线程用于消费事件。

    • bossGroup,线程池在bind一个端口以后返回一条线程作为主线程,接收产生新事件。
    • workerGroup,线程池用来消费事件。

    Netty有一个Bootstrap概念,BoostStrap是引导程序的含义,通过引导程序,可以快速配置,串联搭建起来一个Netty项目,其中ServerBootstrap是针对服务端的,Bootstrap是针对客户端的。所以,包括但不限于以上两个线程池的内容,全部被包含在Bootstrap的实例中。Netty同时也是一个异步框架,所有的操作包括绑定、IO通信等都会返回一个ChannelFuture对象,该对象可以判断isDone,isSuccess,getCause,isCanceled,以及通过addListener加入监听回调。Channel是具体的Netty中用于处理通信的组件,针对不同的通信环境,都会有不同的Channel子类来处理,处理内容包括维持通道、连接配置参数、异步IO处理ChannelHandler、返回ChannelFuture。Selector是Channel的管理器,轮询器,可以管理Channel。另外,所有Group均为线程池的意思,而NioEventLoop的含义是一个维护队列的线程。

    c) 结合源码

    接下来回到Netty服务端的源码配置。

    ServerBootstrap b = new ServerBootstrap(); // 综上所述,先构建一个服务端启动程序。
    EventLoopGroup bossGroup = new NioEventLoopGroup(bossThreads); // 构建主线程池,初始容量为8条,用于监听Accept事件。
    EventLoopGroup workerGroup = new NioEventLoopGroup(Runtime.getRuntime().availableProcessors()); // 构建从线程池,初始容量为当前系统中所有的可用线程数量。

    我们按流程构建了ServerBootstrap对象,然后构建了主线程池bossGroup,初始设定为8,最后构建了从线程池workerGroup,初始设定为系统当前所有可用线程数量。这也不难理解,因为实践过程中,我们总会注意到事件的发现相较于事件的处理是更快速的。因此8条主线程可以覆盖事件发现的工作,而为了更高效使用机器性能,剩余的线程资源都用来事件的消费了。下面是BFT-SMaRt自定义的编解码工具工厂。

    sessionReplicaToClient = new ConcurrentHashMap<>(); // 并发主流容器,线程安全且高效的HashMap
    rl = new ReentrantReadWriteLock(); // 可重入读写锁
    serverPipelineFactory = new NettyServerPipelineFactory(this, sessionReplicaToClient, controller, rl); // 本地开发的工具工厂,用于编解码处理。

    接下来将以上准备好的资源设定配置到ServerBootstrap。

    b.group(bossGroup, workerGroup).channel(NioServerSocketChannel.class)
    .option(ChannelOption.SO_REUSEADDR, true).option(ChannelOption.SO_KEEPALIVE, true)
    .option(ChannelOption.TCP_NODELAY, true).option(ChannelOption.SO_SNDBUF, tcpSendBufferSize)
    .option(ChannelOption.CONNECT_TIMEOUT_MILLIS, connectionTimeoutMsec)
    .option(ChannelOption.SO_BACKLOG, connectionBacklog)
    .childHandler(new ChannelInitializer<SocketChannel>() {
        @Override
        public void initChannel(SocketChannel ch) throws Exception {
            ch.pipeline().addLast(serverPipelineFactory.getDecoder());
            ch.pipeline().addLast(serverPipelineFactory.getEncoder());
            ch.pipeline().addLast(serverPipelineFactory.getHandler());
        }
        })
    .childOption(ChannelOption.SO_KEEPALIVE, true)
    .childOption(ChannelOption.TCP_NODELAY, true);

    首先通过ServerBootstrap的group方法配置主从线程池,然后配置channel类,接着配置一系列参数option。最后为事件消费线程配置参数和channel初始化initChannel,编辑码部分不多展开(编解码也是Netty的功能特色),主要是消费事件的处理类,设定为this,即当前服务端类。接下来给ServerBootstrap绑定IP端口 。

    ChannelFuture f = b.bind(new InetSocketAddress(myAddress, myPort)).sync();

    ServerBootstrap绑定IP端口会返回一个ChannelFuture对象,通过sync()阻塞等待绑定完成返回状态给新建ChannelFuture对象f。最后,将f的channel赋值给服务端类的私有属性Channel对象mainChannel。

    mainChannel = f.channel();

    3. 服务端功能

    NettyClientServerCommunicationSystemServerSide类继承自SimpleChannelInboundHandler<TOMMessage>,实现了CommunicationSystemServerSide接口。其中CommunicationSystemServerSide接口是BFT-SMaRt自定义的,主要用于描述客户端通信中服务端的常用功能。

    ① 通用接口功能

    下面进入CommunicationSystemServerSide接口,查看接口函数。

    public interface CommunicationSystemServerSide {   
       public void send(int[] targets, TOMMessage sm, boolean serializeClassHeaders);
       public int[] getClients();
       public void setRequestReceiver(RequestReceiver requestReceiver);
       public void shutdown();
    }

    其中send方法是网络通信中,节点给客户端发送消息的具体方法,消息类型为TOMMessage。getClient方法会遍历sessionReplicaToClient数据集合,将已建立的节点-客户端会话连接中的客户端统计出来并返回一个整形数组,目前该方法未被使用。setRequestReceiver是设置本地属性requestReceiver。shutdown方法是关闭当前Netty系统。

    ② Channel处理器

    前面介绍了,Bootstrap构建的Netty系统中的Channel处理器就是服务端类本身,我们回到该类的声明部分,也看到了它是继承自SimpleChannelInboundHandler<TOMMessage>,继续追本溯源,它是ChannelHandler的子类,这符合处理器的声明。

    public ServerBootstrap childHandler(ChannelHandler childHandler)

    下面,我们查看在服务端类中关于Channel处理器的重写方法,也是包含4个方法:

    • channelActive
    • channelInactive
    • exceptionCaught
    • channelRead0

    前三个方法都是来自于祖父类ChannelInboundHandlerAdapter,这三个方法是捕捉了channel的三个生命周期,方法体就是在不同的生命周期需要补充做的事。他们的实现更多像是一种标准。第四个方法来自于父类SimpleChannelInboundHandler,是核心的channel读取数据的方法。

    a) Channel生命周期

    进入ChannelInboundHandlerAdapter类,该类完整地展示了Channel生命周期中的所有状态。

    一个Channel从最初注册到Selector上面,变为活跃状态,便可以读取数据,期间可以更改可写入能力,捕获异常,触发用户事件。接着Channel可能变为不活跃状态。Channel也可以随时选择从Selector上解除注册。

    服务端类对于Channel生命周期的3个实现,是一些常规处理和日志提醒。

    b) 读取数据

    channelRead0方法是Channel读取信道中数据的核心方法。

    protected void channelRead0(ChannelHandlerContext ctx, TOMMessage sm) throws Exception {
       if (this.closed) {
          closeChannelAndEventLoop(ctx.channel());
          return;
       }
       // 交付消息到TOM层
       if (requestReceiver == null)
          logger.warn("Request receiver is still null!");
       else
          requestReceiver.requestReceived(sm);
    }

    closeChannelAndEventLoop是前面生命周期方法中常用的方法,用于清空数据、解除注册、关闭channel,关闭相关线程。下面核心方法是调用了requestReceiver的requestReceived方法。requestReceiver是前面介绍的通用接口setRequestReceiver设置的,RequestReceiver接口目前只有一个实现类是TOMLayer。这也放在共识阶段再研究。

    4. 节点通信层已完成

    到目前为止,结合前一篇文章,本地节点的服务端通信系统ServerCommunicationSystem就全部构建完成了。

    public ServerCommunicationSystem(ServerViewController controller, ServiceReplica replica) throws Exception {
        super("Server Comm. System");
        this.controller = controller;
        messageHandler = new MessageHandler();
        inQueue = new LinkedBlockingQueue<SystemMessage>(controller.getStaticConf().getInQueueSize());
    
        serversConn = new ServersCommunicationLayer(controller, inQueue, replica);
        clientsConn = CommunicationSystemServerSideFactory.getCommunicationSystemServerSide(controller);
    }

    目前,节点服务部分重新回到bftsmart.tom.ServiceReplica#init方法,

    cs = new ServerCommunicationSystem(this.SVController, this);

    这一行代码的内容通过这两篇文章已经全部介绍完毕,从下一篇开始,继续向下分析,将initTOMLayer()作为入口介绍节点服务中共识部分的实现原理。

    二、CounterClient入口

    前文通过一个章节的叙述,分析了BFT-SMaRt在节点客户端通信过程中Netty服务端的构建。本章介绍另一方,即Netty客户端的构建,计划从CounterClient的main函数作为入口开始研究。

    public static void main(String[] args) throws IOException {
        if (args.length < 2) { // 参数个数校验,最少2个
            System.out.println("CounterClient <process id> <increment> [<operations>]");
            System.out.println("if <increment> equals 0, read-only");
            System.out.println("default <number of operations> equals 1000");
            System.exit(-1);
        }
        // (1)通过节点id,建立客户端服务代理
        ServiceProxy counterProxy = new ServiceProxy(Integer.parseInt(args[0]));
        try {
            int inc = Integer.parseInt(args[1]); // 影响值
            // 操作次数,默认1000次
            int numberOfOps = (args.length > 2) ? Integer.parseInt(args[2]) : 1000;
            for (int i = 0; i < numberOfOps; i++) { // 按照操作次数循环
                // 将影响值放入输出流out
                ByteArrayOutputStream out = new ByteArrayOutputStream(4);
                new DataOutputStream(out).writeInt(inc);
                System.out.print("Invocation " + i);
                // (2)调用实操方法,通过输出流传入影响值
                byte[] reply = (inc == 0) ?
                        counterProxy.invokeUnordered(out.toByteArray()) :
                        counterProxy.invokeOrdered(out.toByteArray()); //magic happens here
                if (reply != null) {
                    // 通过输入流读取返回值
                    int newValue = new DataInputStream(new ByteArrayInputStream(reply)).readInt();
                    System.out.println(", returned value: " + newValue);
                } else {
                    System.out.println(", ERROR! Exiting.");
                    break;
                }
            }
        } catch (IOException | NumberFormatException e) {
            counterProxy.close(); // 关闭代理
        }
    }

    该方法中比较重要的两个步骤,

    • 其一是为客户端构建服务代理
    • 其二是调用实操方法,消费影响值。

    1. 构建服务代理

    进入ServiceProxy类的构造函数,

    public ServiceProxy(int processId) {
       this(processId, null, null, null, null);
    }

    跳转到本地的五参数的构造函数,

    public ServiceProxy(int processId, String configHome,
          Comparator<byte[]> replyComparator, Extractor replyExtractor, KeyLoader loader) {
       // 代理服务初始化,包括网络通信、共识视图、系统配置
       if (configHome == null) {
          init(processId, loader);
       } else {
          init(processId, configHome, loader);
       }
       // 构建一个TOMMessage数组,大小为节点总数。
       replies = new TOMMessage[getViewManager().getCurrentViewN()];
       // 比较器,继承自jdk工具Comparator,重写方法实现可比较两个字节数组是否相等的功能。
       comparator = (replyComparator != null) ? replyComparator : new Comparator<byte[]>() {
          @Override
          public int compare(byte[] o1, byte[] o2) {
             return Arrays.equals(o1, o2) ? 0 : -1;
          }
       };
       // 导出器,继承自工具Extractor,可构建自定义的响应消息提取器。
       extractor = (replyExtractor != null) ? replyExtractor : new Extractor() {
          @Override
          public TOMMessage extractResponse(TOMMessage[] replies, int sameContent, int lastReceived) {
             return replies[lastReceived];
          }
       };
    }

    主要代码为初始化,由于当前configHome传入为null,调用的两个参数的init方法。由于ServiceProxy类是TOMSender的子类,因此调用的init方法是父类的方法。

    public void init(int processId, KeyLoader loader) {
       // 构建视图控制器
       this.viewController = new ClientViewController(processId, loader);
       // 启动Netty通信
       startsCS(processId);
    }

    ① 视图控制器

    ViewController类是系统的上下文环境,是由系统配置项构建。以下是BFT-SMaRt关于视图的类图关系。

    视图层级的根节点是View类,它实现了Serializable接口,所以视图都是可序列化的。视图最基本的属性就是id,容错数,节点id数组以及连接地址集合。在视图控制器ViewController中,最终可以得到所有网络配置属性及方法。

    a) 配置整合

    ViewController类是View子类,包含了更全面的属性字段,这些属性的值来自于两个渠道:

    • 配置文件包括host.config以及system.config
    • 配置类Configuration。

    而TOMConfiguration类通过一个map容器Map<String, String>对象configs,有机地将以上两个渠道的所有配置全部提取出来,在内存中构建了静态配置对象staticConf。

    b) 视图存储

    继续ViewController类的研究,视图除了在内存中使用,也可以被持久化存储在文件中。这个能力来自于接口ViewStorage,该接口提供了两个功能,

    public interface ViewStorage {
        public boolean storeView(View view);    // 是否存储成功
        public View readView();                 // 读取视图
    }

    目前该接口的实现只有DefaultViewStorage类,它可以将视图对象通过对象输出流写入文件保存在磁盘上,同时还可以从磁盘上通过对象输入流将文件数据恢复成内存中的View对象。

    c) 服务端视图控制器

    根据上面的类图,ServerViewController是ViewController的一个子类。作为共识节点服务端,它主要提供了共识方面的属性功能。核心属性如下:

    private int quorumBFT; // ((n + f) / 2) replicas
    private int quorumCFT; // (n / 2) replicas
    private int[] otherProcesses;
    private int[] lastJoinStet;
    private List<TOMMessage> updates = new LinkedList<TOMMessage>();
    private TOMLayer tomLayer;

    quorumBFT是指在BFT网络中的有效确认数,同理quorumCFT则是在CFT网络中的有效确认数。lastJoinStet是用来记录最后加入加点的,是指那些配置域以外的节点,可以是TTP,或者是陌生节点,需要重新配置reconfigure视图参数。updates是共识消息TOMMessage的容器,tomLayer是共识层的对象。ServerViewController对象是构建节点通信系统的参数,这是前面所遗漏的部分,在此补充上。

    首先在节点服务类的构建中包含:

    this.SVController = new ServerViewController(id, configHome, loader);

    接着构造函数内继续执行init方法,会构建节点通信系统,

    cs = new ServerCommunicationSystem(this.SVController, this);

    第一个参数传入的就是服务端视图对象,该对象在构建节点通信系统时发挥了重要作用,例如读取系统配置,判断节点来源等等。那么后续的内容在上一篇博文中就已经非常详细了,这里就到此为止。

    d) 客户端视图控制器

    我们回到TOMSender的init方法,构建客户端视图控制器。相对来讲,ClientViewController的内容就很少了,它只有两个构造函数和两个自有方法。

    public ClientViewController(int procId, KeyLoader loader) {
        super(procId, loader); // 初始化系统配置
        View cv = getViewStore().readView(); // 从磁盘读取视图对象
        // 调用reconfigureTo将视图内容配置View属性。
        if(cv == null){
            // 若未读取成功,则通过配置参数构建新视图
            reconfigureTo(new View(0, getStaticConf().getInitialView(),
                getStaticConf().getF(), getInitAdddresses()));
        }else{
            reconfigureTo(cv);
        }
    }

    初始化配置,然后读取视图,通过ViewController的reconfigureTo方法(注意区分ServiceProxy也有一个reconfigureTo方法,要比这个方法复杂)替换视图。

    public void reconfigureTo(View newView) {
        this.lastView = this.currentView;   // 将当前视图变为上一个视图
        this.currentView = newView;         // 传入的新视图变为当前视图
    }

    到此,客户端的视图控制器就构建完成了。

    ② 启动Netty客户端

    前面第一章节已经详细介绍了节点Netty服务端的构建,下面就开始启动相对应的Netty客户端。通过TOMSender类的startCS方法。可以注意到参数clientId在前面的名字是processId,该参数是用来标识客户端的,而不是用来指定请求节点的。

    private void startsCS(int clientId) {
       this.cs = CommunicationSystemClientSideFactory.getCommunicationSystemClientSide(clientId, this.viewController);
       this.cs.setReplyReceiver(this); // This object itself shall be a reply receiver
       this.me = this.viewController.getStaticConf().getProcessId();
       this.useSignatures = this.viewController.getStaticConf().getUseSignatures() == 1;
       this.session = new Random().nextInt();
    }

    我们注意到,Netty服务端的构建只传入了一个服务端视图控制器ServerViewController对象,

    public NettyClientServerCommunicationSystemServerSide(ServerViewController controller)

    而Netty客户端的构建传入了客户端id和客户端视图控制器ClientViewController对象两个参数。

    public NettyClientServerCommunicationSystemClientSide(int clientId, ClientViewController controller)
    • NettyClientServerCommunicationSystemClientSide,后面简称为Netty客户端类。
    • NettyClientServerCommunicationSystemServerSide,前面介绍过了,简称为Netty服务端类。

    下面进入到客户端类的构造函数,首先执行的父类构造函数super(),由于Netty客户端类和服务端类都是继承自同一个父类SimpleChannelInboundHandler,因此可参照(一-1)父类构造函数的内容。接下来,客户端类并没有主线程池而只有从线程池workerGroup,即bossGroup是Netty服务端类特有的。

    this.workerGroup = new NioEventLoopGroup(Runtime.getRuntime().availableProcessors());

    构建从线程池,初始容量为当前系统中所有的可用线程数量。接下来,私钥的读取也可参考(一-2-①-a)。然后通过视图对象获取所有的节点id。

    int[] currV = controller.getCurrentViewProcesses();

    对节点id数组进行遍历,向每个节点发起连接请求,secretKeyFactory是加密工具组件。

    ChannelFuture future = connectToReplica(replicaId, secretKeyFactory);

    客户端指定自身id,然后向共识网络发起请求,而不是指定节点,进入共识网络以后,会遍历节点分别建立连接,这与理论部分中的逻辑图是吻合的。

    a) 连接到指定节点

    进入connectToReplica连接到指定节点方法。

    public synchronized ChannelFuture connectToReplica(int replicaId, SecretKeyFactory fac)
          throws NoSuchAlgorithmException, InvalidKeySpecException, InvalidKeyException {
       // 2端参与的连接认证密码,暂未使用
       String str = this.clientId + ":" + replicaId;
       PBEKeySpec spec = TOMUtil.generateKeySpec(str.toCharArray());
       SecretKey authKey = fac.generateSecret(spec);
       // 配置启动程序
       Bootstrap b = new Bootstrap();
       b.group(workerGroup);
       b.channel(NioSocketChannel.class);
       b.option(ChannelOption.SO_KEEPALIVE, true);
       b.option(ChannelOption.TCP_NODELAY, true);
       b.option(ChannelOption.SO_SNDBUF, tcpSendBufferSize);
       b.option(ChannelOption.CONNECT_TIMEOUT_MILLIS, connectionTimeoutMsec);
       b.handler(getChannelInitializer()); // 添加channel处理器
       // 启动连接到指定的节点replicaId,返回ChannelFuture
       ChannelFuture channelFuture = b.connect(controller.getRemoteAddress(replicaId));
       // 缓存连接会话到sessionClientToReplica,这是一个ConcurrentHashMap容器
       NettyClientServerSession ncss = new NettyClientServerSession(
             channelFuture.channel(), replicaId); // 构建Netty客户端请求服务端的会话对象
       sessionClientToReplica.put(replicaId, ncss);
    
       return channelFuture;
    }

    相对Netty服务端来讲,连接过程差不多但简单很多,仍旧通过启动程序Bootstrap完成快速构建。首先为Bootstrap添加了线程池workerGroup,然后指定了Channel类型为NioSocketChannel(注意区分服务端的channel类型为NioServerSocketChannel),接着配置参数,添加Channel处理器。然后,通过连接方法建立与指定节点的连接通信。

    ChannelFuture f = b.connect(controller.getRemoteAddress(replicaId));

    这对应的是Netty服务端的,

    ChannelFuture f = b.bind(new InetSocketAddress(myAddress, myPort)).sync();

    客户端的connect也可以加一个阻塞等待sync(),即:

    ChannelFuture f = b.connect(controller.getRemoteAddress(replicaId)).sync();

    服务端成功绑定了IP端口,就开始监听该地址了。此时客户端通过connect方法连接指定地址的节点。connect方法的参数是通过controller.getRemoteAddress(replicaId)返回的SocketAddress类型对象,内容就是IP端口号。连接成功以后,客户端ChannelFuture可以通过isSuccess()方法返回true来得到结果。回到客户端类的构造函数,

    future.awaitUninterruptibly();

    将线程阻塞在这一行代码,保持线程的通信可用性,直到Channel关闭,此处是通过捕捉connect方法抛出的异常而完成线程关闭。

    public ChannelFuture connect(SocketAddress remoteAddress) {
        if (remoteAddress == null) {
            throw new NullPointerException("remoteAddress");
        } else {
            this.validate();
            return this.doResolveAndConnect(remoteAddress, this.config.localAddress());
        }
    }

    connect方法中往下调用,会根据通道的不同情况抛出异常。

    b) Channel处理器

    注意观察以上代码,作为重要的组成部分,channel处理器是通过getChannelInitializer()构建的。

    private ChannelInitializer getChannelInitializer() throws NoSuchAlgorithmException {
    
       final NettyClientPipelineFactory nettyClientPipelineFactory = new NettyClientPipelineFactory(this,
             sessionClientToReplica, controller, rl);
    
       ChannelInitializer channelInitializer = new ChannelInitializer<SocketChannel>() {
          @Override
          public void initChannel(SocketChannel ch) throws Exception {
             ch.pipeline().addLast(nettyClientPipelineFactory.getDecoder());
             ch.pipeline().addLast(nettyClientPipelineFactory.getEncoder());
             ch.pipeline().addLast(nettyClientPipelineFactory.getHandler());
          }
       };
       return channelInitializer;
    }

    这部分代码与Netty服务端也很相似,最终Channel处理器也指向了客户端类本身。

    2. Netty通信原理

    到此为止,我们构建了Netty服务端,也建立了客户端并对服务端发起了连接请求。那么通过以上Netty相关的内容,下面通过一张图来介绍Netty的通信原理。

    首先由服务端启动程序初始化channel,然后发起绑定将channel注册到主线程池的按顺序的某一个线程的selector。Selector会轮询channel的accept事件。这时候如果有客户端启动程序发起的connect连接触发accept事件,该事件会执行一个任务并被放到任务队列中去,等待消费。当runAllTasks消费到该任务,则建立起另一条channel并注册到从线程池的按顺序的某一个线程的selector。Selector会轮询读写事件。Channel中当数据被接收完成,表示读就绪就是读事件;同样的,Channel中当可以写数据时,标识写就绪就是写事件。读写事件发生都会单独执行一个任务并被放到任务队列中去,等待任务消费。当runAllTasks消费到该任务,则会处理具体读写事件。

    3. 客户端功能

    客户端与节点之间通过Netty建立了通信。客户端类实现了CommunicationSystemClientSide接口,与服务端同样继承了SimpleChannelInboundHandler<TOMMessage>,因此也可分为通用客户端接口类和Channel生命周期方法。

    ① 通用接口功能

    客户端类实现了CommunicationSystemClientSide接口,该接口定义了客户端节点通信中,节点应该具备的功能。

    public interface CommunicationSystemClientSide {
       public void send(boolean sign, int[] targets, TOMMessage sm);
       public void setReplyReceiver(ReplyReceiver trr); // 设置ReplyReceiver字段
       public void sign(TOMMessage sm); // 未使用
       public void close();
       public void updateConnections();
    }

    a) 发送消息准备

    首先看send接口,在客户端类的实现体中,send首先计算出基于BFT或CFT的最少确认数quorum。

    int quorum;
    Integer[] targetArray = Arrays.stream(targets).boxed().toArray(Integer[]::new);
    Collections.shuffle(Arrays.asList(targetArray), new Random());
    if (controller.getStaticConf().isBFT()) {
       quorum = (int) Math.ceil((controller.getCurrentViewN() + controller.getCurrentViewF()) / 2) + 1;
    } else {
       quorum = (int) Math.ceil((controller.getCurrentViewN()) / 2) + 1;
    }
    listener.waitForChannels(quorum); // 等待前面的传输完成,收集足够的消息确认数

    当共识要求的最少确认数达成以后,客户端才可以发起请求。请求的类型是TOMMessage,被发送前要通过字节数组输出流序列化得到消息对象sm的序列化消息serializedMessage。(这个在EOS的合约请求中也是常见的,data对象中除明文参数以外,还会有hex作为请求的序列化消息,便于传输。)

    if (sm.serializedMessage == null) {
       DataOutputStream dos = null;
       try {
          ByteArrayOutputStream baos = new ByteArrayOutputStream();
          dos = new DataOutputStream(baos);
          sm.wExternal(dos);
          dos.flush();
          sm.serializedMessage = baos.toByteArray();
       } catch (IOException ex) {
          logger.debug("Impossible to serialize message: " + sm);
       }
    }

    b) 消息签名

    接下来,要通过本地私钥给已序列化的消息进行签名。

    sm.serializedMessageSignature = signMessage(privKey, sm.serializedMessage);

    调用本地signMessage方法进行签名。

    public byte[] signMessage(PrivateKey key, byte[] message) {
       try {
          // 签名引擎,用于签名的工具。
          if (signatureEngine == null) {
             signatureEngine = TOMUtil.getSigEngine();
          }
          byte[] result = null;
          // 载入私钥 java.security.Signature.initSign(java.security.PrivateKey)
          signatureEngine.initSign(key);
          // 载入待签名消息 java.security.Signature.update(byte[])
          signatureEngine.update(message);
          // 执行签名 java.security.Signature.sign()
          result = signatureEngine.sign();
          // 返回签名结果
          return result;
       } catch (Exception e) {
          logger.error("Failed to sign message", e);
          return null;
       }
    }

    签名的底层代码是由jdk中java.security.Signature包所完成的,感兴趣的小伙伴可深入研究。签名后得到了消息对象sm的serializedMessageSignature字段的值。

    c) 发送消息

    接下来,会遍历发送终点,即所有的节点。每拿到一个节点,则将该节点作为目的地存入消息对象sm的destination字段。

    sm.destination = targets[target];

    接下来上锁并获得channel,

    rl.readLock().lock();
    Channel channel = ((NettyClientServerSession) sessionClientToReplica.get(targets[target])).getChannel();
    rl.readLock().unlock();

    sessionClientToReplica容器在前面建立Netty客户端时谈到过,是一个连接会话的容器,当再次获取连接时不必重新构建。在这个容器中按照节点查找得到指定节点的连接channel。判断如果该channel是可用的,则发送。

    if (channel.isActive()) {
       sm.signed = sign; // 签名成功后会将该标示位sign置为true。
       ChannelFuture f = channel.writeAndFlush(sm);
       f.addListener(listener);
       sent++; // 发送计数器,用于共识确认数。
    }

    将消息写入channel,然后为该处理添加监听器,以便能捕捉处理状态事件。该监听器在Netty客户端类构建时被赋值。

    this.listener = new SyncListener();

    SyncListener类是Netty客户端类的内部类,它重写了operationComplete事件。同时,增加了方法waitForChannels,用于共识机制中,收集回复确认数的相关通道的等待。

    d) 关闭通道

    close方法是用来将通道关闭的。

    public void close() {
       this.closed = true;                  // 设置关闭标志位
       rl.readLock().lock();                // 上锁
       ArrayList<NettyClientServerSession> sessions = new ArrayList<>(sessionClientToReplica.values());      // 读取连接会话容器中的所有连接
       rl.readLock().unlock();
       for (NettyClientServerSession ncss : sessions) { // 遍历关闭
          Channel c = ncss.getChannel();    // 从对象中获取channel
          closeChannelAndEventLoop(c);      // 安全关闭channel以及EventLoop线程
       }
    }

    e) 更新连接(视图)

    当有新的节点加入时,需要更新视图。以便于客户端遍历节点发送消息,因此会涉及修改Netty客户端的连接。我们知道,Netty客户端与各个节点的连接被放在了连接会话容器sessionClientToReplica。更新连接时,说明视图已经更新完毕。那么要对视图中所有节点进行遍历。

    int[] currV = controller.getCurrentViewProcesses();
    for (int i = 0; i < currV.length; i++) {
        ...
    }

    遍历每一个节点,然后判断是否在sessionClientToReplica存在连接,如果存在说明是老节点,如果不存在说明是新节点。那么针对新节点,要建立新的连接并放到sessionClientToReplica。建立连接的方式与新建是相同的。

    ChannelFuture future = connectToReplica(replicaId, secretKeyFactory);
    future.awaitUninterruptibly();

    参考前面(二-1-②-a)。

    ② channel处理器

    这部分主要是处理channel的生命周期,与Netty服务端的内容基本一致。也是四个方法:

    • channelActive,标识
    • channelInactive,调用scheduleReconnect
    • channelUnregistered,调用scheduleReconnect
    • exceptionCaught,输出错误日志

    这四个实现与Netty服务端完全一致。这里补充一下scheduleReconnect方法的内容。

    a) 定时重连

    scheduleReconnect顾名思义,是定时重连的含义。

    private void scheduleReconnect(final ChannelHandlerContext ctx, int time) {
       if (closed) { // 如果是已关闭状态,则走关闭流程。
          closeChannelAndEventLoop(ctx.channel());
          return;
       }
       // 未关闭状态,则定时重连。
       final EventLoop loop = ctx.channel().eventLoop();    // 首先获得eventLoop线程
       loop.schedule(new Runnable() {                       // 为线程增加定时任务
          @Override
          public void run() {
             reconnect(ctx);                                // 任务执行reconnect方法。
          }
       }, time, TimeUnit.SECONDS);
    }

    下面进入重连方法reconnect,这个方法在Netty服务端也有,与新建连接差不多,但是重连一般都会在sessionClientToReplica容器已存在。

    public void reconnect(final ChannelHandlerContext ctx) {
       rl.writeLock().lock();
       ArrayList<NettyClientServerSession> sessions = new ArrayList<NettyClientServerSession>(
             sessionClientToReplica.values());
       for (NettyClientServerSession ncss : sessions) { // 遍历连接
          if (ncss.getChannel() == ctx.channel()) {
             int replicaId = ncss.getReplicaId();
             try {
                if (controller.getRemoteAddress(replicaId) != null) {
                   ChannelFuture future;
                   try {
                      // 建立连接
                      future = connectToReplica(replicaId, secretKeyFactory);
                   } catch (InvalidKeyException | InvalidKeySpecException e) {
                      logger.error("Error in key.",e);
                   }
                   logger.info("ClientID {}, re-connection to replica {}, at address: {}", clientId, replicaId,
                         controller.getRemoteAddress(replicaId));
                } else {
                   // 说明该节点已经删除,则从sessionClientToReplica删除连接。
                   removeClient(replicaId);
                }
             } catch (NoSuchAlgorithmException ex) {
                logger.error("Failed to reconnect to replica", ex);
             }
          }
       }
       rl.writeLock().unlock();
    }

    建立连接时仍旧调用connectToReplica方法。参考前面(二-1-②-a)。

    ③ 已完成内容

    致此,CounterClient中通过节点id,建立客户端服务代理的工作已完成。

    4. 调用排序消息

    BFT-SMaRt中经常出现的TOM前缀的内容,一般我都会归并到共识中去,这几篇文章也未展开。那么TOM的含义是什么?其实就是Total ordered messages的含义,也就是全排序消息,这就是共识的一种体现。

    byte[] reply = (inc == 0) ?
            counterProxy.invokeUnordered(out.toByteArray()) :
            counterProxy.invokeOrdered(out.toByteArray()); 

    回到CounterClient,当影响值为0时,调用无序方法invokeUnordered,对应类型为TOMMessageType.UNORDERED_REQUEST。当影响值为其他值时,调用共识方法invokeOrdered。后续我的猜测是通过Netty服务端拿到这个值,然后通过ServerViewController的lastView的值加上影响值,然后变为currentView即可,返回currentView的最新的值。这部分内容可以在下一篇详细展开。

    三、后记

    经过本文以及前面几篇BFT-SMaRt相关的文章,可靠信道的部分就全部介绍完了。后续会展开节点对于消息的共识逻辑,以及视图更换后状态同步的逻辑的研究。

    更多文章请转到一面千人的博客园

    更多相关内容
  • 它补充了论文Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus 。概述我们建议将交易传播任务与交易排序任务分开,以在许可设置中实现高性能拜占庭容错共识。为此,我们设计并评估了一个 mempool...
  • Concord-BFT:分布式信任基础结构 概述 Concord-bft是通用状态机复制库,可以处理恶意(拜占庭式)副本。 它的实现基于文中描述的算法。 它被设计用作复制的分布式数据存储的核心构建块,并且特别适合用作许可的...
  • 在之前的博客中,我们已经从一个更为宏观的视角了解了Cosmos/Tendermint技术栈。在本文中,我们将深入介绍Tendermint共识引擎的共识层和网络层。Cosmos-SDK将实现区块链的应用逻辑,它与Tendermint共识引擎一起实现...
  • Test_BFT

    2021-03-13 10:00:14
    Test_BFT
  • 区块链中最重要的便是共识算法,比特币使用的是POW(Proof of Work,工作量证明),以太币使用的POS(Proof of Stake,股权证明)而EOS使用的是BFT-DPOS。 什么是BFT-DPOS呢?即拜占庭容错式的委任权益证明。 要想...
  • #资源达人分享计划#
  • archistar-bft是Java开放源代码库。 它是为项目开发的,并在内部进行了开发。2014年,BFT算法的状态引擎被提取到其自己的库中。 提取库的原因是要创建一个独立于平台和传输的BFT引擎,该引擎可以在其他项目中重用。...
  • BFT写作精粹 完整版

    2018-07-14 15:32:48
    BFT写作精粹 完整版 BFT考试,对一些要出国的程序员来说市非常重要的,这部分市关于写作的,希望能帮助到大家
  • tendermint, 在Go中,Tendermint内核( BFT一致性) Tendermint拜占庭容错 状态机复制系统。 或者链 。 分支测试覆盖母版 开发 注意:这里是alpha软件。 如果你想在生产中运行,请与我们联系。 Tende
  • BFT智能合约 回购有2个主要合同,即BftCrowdsale和BftToken。 请遵循单元测试并与规格进行比较。 进行单元测试的说明 git clone git@github.com:BankToTheFuture/bft.git cd bft git submodule update --init --...
  • 权益证明到底是什么?权益证明算法的推出就是为了作为资源浪费比较严重的工作量证明的替代。权益证明最先是由Sunny King 和Scott Nadal在2012年提出的,而且自从提出之时,权益证明就被认为是资源浪费型的工作量证明...
  • 这种结构可实现许多功能,包括灵活的BFT选择,多链支持,通过BFT服务的即插即用法证监控平台,以及在两个不同区块链之间架起信任的能力。 建筑学 BFT服务:委员会基于一个简单和通用接口BFT服务:这需要考生共识...
  • Honey Badger BFT(异步共识算法)笔记

    千次阅读 多人点赞 2021-09-28 09:14:29
    最近一直在看Honey Badger BFT共识协议,看了很多博客和一些相关的论文,但是发现有些博客存在着部分理解错误的地方,或者就是直接翻译2016年的那一篇论文,在经过半个多月的细读之后,打算整理出这篇博客,方便给...

    最近一直在看Honey Badger BFT共识协议,看了很多博客和一些相关的论文,但是发现有些博客存在着部分理解错误的地方,或者就是直接翻译2016年的那一篇论文,在经过半个多月的细读之后,打算整理出这篇博客,方便给学习这个共识协议的人学习,同时自己也留存一份笔记,以下仅是笔者通过阅读论文和博客等方式,描述自己对Honey Badger的理解。如有错误,还请指正。
    Miller等人提出的Honey Badger BFT是一种在异步网络环境下可以正常运行的BFT协议。

    • 异步,比PBFT的吞吐量和延迟性能好
    • 仅支持封闭网络,即主机个数已知,协议执行过程中没有新的主机接入网络。
    • 无Leader,每个节点都可作为共识的发起者。
      Honey Badger BFT使用了两个方法来提升共识效率:
    • 通过纠删码分割交易来环节单节点带宽瓶颈。
    • 通过在批量交易中选择随机交易块,并配合门限加密来提升交易的吞吐量。

    基础知识

    纠删码

    (我是在一篇博客上面看到的关于RS纠删码的介绍,这里只是粗略的介绍一个概念,让大家知道是用来干什么的,以及是一个什么原理。纠删码技术在后面的RBC阶段会使用到,主要是用于均分带宽,缓解提出共识交易节点的带宽瓶颈。)
    纠删码工作原理简介:
    RS(Reed-solomom)码是一种比较常见的纠删码,它的两个参数m和n分别代表校验块个数和原始数据块个数(课容忍m个数据块的丢失,拜占庭共识中,设m = 2f,原始数据块为f+1),我们可以使用n数据块就恢复出原始的数据块。
    纠删码编码过程:C代表校验块,D代表原始的数据块。
    在这里插入图片描述
    假设我丢失了D1、D4、C2数据块:
    在这里插入图片描述
    解码过程:(一共三步)
    Step1:在编码矩阵中去掉求实数据块以及该数据块对应的行。即B矩阵变为了n*n维度的方阵,C和D组合的矩阵由(n+m)行变为n行,在上诉假设过程中,我们得到新的矩阵以及对应的矩阵运算关系式,其中在丢失了部分数据块后,D所代表的原始数据块成为了要求的目标。
    step2:求B’的逆矩阵:
    如下图所示:

    step1
    step3:可以采用对等式两边同时乘上B’的逆矩阵,于是得到所求解。
    在这里插入图片描述
    在这里插入图片描述
    如果大家没太看懂,我贴上关于纠删码部分原作者的博客链接:

    https://www.cnblogs.com/Robin5/p/11710005.html

    随机交易块

    为了降低各个节点之间提交交易的重复性,Honey Badger BFT算法使用随机选择交易块的方法来选择需要共识的交易集,具体选择条件如下:
    假设网络中共有N个节点,每个节点进行共识的交易大小为B。每个节点收集交易数据,放到自身的交易缓冲池中,每一轮共识之前,节点从交易缓冲池的第一个B大小的交易池中随机选取 B/N 个交易进行共识。(提问:为什么节点只选择B/N个交易进行共识?答:因为不止一个节点提交共识交易集,是所有节点都会进行提交,当前节点 Pi 会从其他N-1个节点处收到他们提交的交易集,然而每个节点能够共识的交易大小为BN * B/N = B,所以知道了么?)
    在这里插入图片描述

    门限加密

    第三方可信机构(2016年的论文提出:如果可信机构不可信了,可以使用分布式密钥生成协议替代)会将私钥分片放给所有参与共识的节点,在解密的时候,只要节点收集到一定门限数量的解密分片,则该节点可以恢复出密文。使用门限加密还可以实现审查弹性,避免了敌手知道哪个交易由哪个节点发起而阻挠共识的达成。

    在这里插入图片描述

    默克尔树

    默克尔树会在后面的RBC协议阶段使用到。默克尔树(或者哈希树)是一棵能够存储哈希值的树,树的叶子节点是数据块(例如交易集、文件等)的哈希值,内部节点则是其对应子节点串联字符串的哈希值。这里以RBC中的交易块 sj 为例。
    如何校验数据块的叶子节点 sj 和路径 bj 校验是否等于 h,假设 j = 2,交易分块 s2b2 以及 hb2 = {h1, h8, h11}
    在这里插入图片描述
    在这里插入图片描述

    Honey Badger BFT算法总流程

    总体的算法主要包括三个步骤:

    • 随机选取交易集并对交易集加密
    • 交易的可靠广播(采用RBC实现)。
    • 共识(采用ABA实现)
      算法流程如下
    • 节点 Pi 先根据随机选择交易块的选择规则选取要进行共识的交易集合(B/N个交易),第三方可信机构分发私钥分片给每个节点。
    • 节点 Pi 使用公钥PK对交易集进行加密,加密的交易用 x 表示。
    • x 作为ACS(后面会详细讲解)的输入,ACS结束后,会收到N个(包括自己的那一个,其余为其他节点发起的交易共识)交易集 vj ,以及交易对应的01比特串,每个比特对应一个节点发起的共识交易集合(1表示该交易集最终会被提交,0表示该交易集不会被提交)。
    • 将二进制共识结果为 1 的交易块收集起来,并对它进行解密,当 Pi 收到 f + 1个解密分片的时候 Pi 就可以解密得到 vj 的明文交易集合。交易被解密之后,会进行赛重、校验交易正确性、和排序等环节。交易被提交之后,就会从待提交的交易缓冲池中删除。

    在这里插入图片描述
    下图为Honey Badger BFT算法总流程图(运行于Pi)。
    在这里插入图片描述

    ACS(异步公共子集协议)

    Hoeny Badger BFT是第一个实现最佳渐近效率的一步原子广播协议。
    Honey Badger BFT算法采用ACS(Asynchronous Common Subset)协议实现了原子广播(Atomic Broadcast)。
    ACS协议由两个协议组成:一个是可靠广播协议RBC(Reliable Broadcast),一个是异步二进制协议ABA(Asynchronous Binary Agreement)。

    • RBC协议:广播交易。
    • ABA协议:形成一致的二进制交易列表。

    下图为RBC和ABA协议具体执行过程:这只是在 Pi 为发起共识交易者的角度进行解释,其实其他的节点也是相同的步骤,并且并发执行。
    在这里插入图片描述

    RBC协议

    论文采用基于纠删码的RBC协议来广播每个节点提交的交易集。RBC的协议包括如下步骤(这里只是针对 Pi 为消息的发送者,其实其他的节点也在同时进行与 Pi 相同的步骤):

    • Pi 将加密后的交易块 v 作为RBC的输入,使用纠删码技术生成N个数据块 {sj}j∈N
    • 将所有的 sj 计算出默克尔根 hbjsjh 的路径,并将 VAL(h, bi, si) 消息广播给其他节点。(关于默克尔树部分的理解,可以参考前面基础知识关于其的介绍)
    • 如果其他节点收到来自PiVAL信息,则广播 ECHO(h, bi, si) 消息。
    • 当其他节点收到EHCO消息之后,他首先会校验根据 sibi 是否能算出h(对 Pi 来说,就是校验 ECHO(h, bj, sj)),检查这个ECHO是否有效,如果能够正确推算,就表示此ECHO有效,如果无效则直接丢弃这个ECHO
    • 当节点收到 2f+1ECHO消息(h相同)之后,则选取其中 f+1ECHO,根据其sjbj计算出 h’。然后对比 h’h 是否相等。如果相等则广播 REDAY(h) 消息。
    • 当节点收到 2f+1READY(h) 消息,则使用前面收到的 f+1ECHO消息恢复出原始的密文 v(纠删码技术)。
      注释:下图中算法的倒数第二个小圆点的部分。我没有在流程中叙述出来,肯定有人会有疑惑,根据我自己的理解,我认为这一部分是为那些网络情况不好的正确节点准备的,或许他们在收到了 f+1 个别的节点发出的READY(h)消息的时候,还没有收到足够多的ECHO消息,所以他自己本身还不能触发发送READY的契机。但是收到了那么多人已经发了READY消息,那么他就知道这个答案是对的,那么他就抄作业。直接发送READY消息,这也就解释了最后一个点为什么有wait for N-2f ECHO messages)。

    在这里插入图片描述

    ABA协议

    如果节点能够根据 f+1ECHO消息重构出交易密文 v,则对对应的实例ABA发送一个1,如果当前节点已经重构出了 2f+1 个节点提交的交易块(指已经输入了2f+1个1),那么就会对后面所有的ABA实例都输入0,表示在收到 2f+1个交易块之后,后面的我都不要了。
    (为啥这么任性?因为这是在拜占庭共识中,会有 f 个是拜占庭节点,如果我要等到全部节点的交易块都收到再进行下一步,其实是不太可能的,万一有拜占庭节点故意不发,那样我们的等待很可能会阻塞共识的达成,所以我们就假设排除掉 f 个个节点的交易,只收到2f+1个就行啦)。
    其实这里会有一个情况2(当然接下来只是我的理解,如ACS的第一个图中我标注的情况2这个阶段所示)。一个节点已经对2f+1个ABA实例输入1,对剩下的 ABA 实例都为0,但是这时候所有节点输入为 1 的ABA实例的集合其实并不相同,所以需要一次交互,当节点对某个 ABA 实例设置为0,但是他又收到了 f+1 个其他节点发来将该实例设置为1的消息,那么他就会把自己设置为0的ABA实例重新设置为1,并且他还需要等待该实例对应的交易集从RBC中重构出来。如果没有收到那么多1,那就不更新。
    在这里插入图片描述
    假设节点P1经过前一轮的交互,已经将自己拥有的ABA实例对应的二进制序列更新,此时我们以ABA2为例。节点对应的其他ABA实例也是相同的步骤,其他节点也与P1并行执行。r表示轮次,会根据循环的轮次而不断自增。

    1. est1初始化为1
    2. 广播BVAL1(1)
    3. bin_values1 = ∅
    4. 在节点P1接收 2f+1个到BVAL1(1),则bin_values1= bin_values1∪{1} = {1}
    5. bin_values1 不为空集的时候:

    广播AUX1(w),w是属于集合bin_values1里面的元素,这时候bin_values1里面只有一个元素——1,所以所有节点在bin_values1里面选的的元素w必然相同。
    vals表示所有节点选取的w的集合,当前为第一轮,vals集合里面也只会有元素1
    s 可以看做是一个随机数,其实它就是所有节点将轮次 r 进行门限签名再聚合之后形成的聚合签名。
    这时vals集合是与{b} = {1}相等的,那么他会进入下面的那个if语句,est2 = 1,如何当前的1与随机抛硬币算法选取出的结果相等,那么表示已经对这个交易块的提交达成了共识,输入当前的共识结果1。(s%2 ∈{0,1})
    如果不凑巧与抛硬币算法没有相等,那会在进入一次上面的循环。随着循环的次数越多,会更容易达成共识。

    其实这一部分给我的感觉就是:节点之间选出一个结果,然后还需要老天爷(随机数)来决定你这个结果要不要被采纳。相同就采纳,不相同就不采纳。但是这个2016年那篇论文中提到了已经证明了在常数轮次可以达成最终的共识。
    在这里插入图片描述
    最后经过ABA协议之后,得到一串共识后的二进制列表(假设二进制列表是存储在数组中,文中没有提及,只是我的猜想)。再对收到的交易序列按照二进制列表的结果进行处理,下图中第一排为二进制列表,第二排位对应的节点下标。将为1的交易集提取出来,使用门限解密密钥进行解密,当收到 f+1个对应同一个交易集的解密分片的时候,就可以解密出当前的交易集。在进行一系列的交易去重、验证交易正确性的手段。然后将最终的交易集进行提交。并从每个节点的待提交交易缓存池中将提交成功的交易删除。
    在这里插入图片描述
    以上只是我这段时间自己学习和理解的Honey Badger BFT,如有不对之处,还望指出。
    附上的2016年的Honey Badger BFT原文,以及门限加密原文,以及参考的ABA算法的原文可以在我的博客主页找到。

    展开全文
  • Tendermint Core是拜占庭式容错(BFT)中间件,它采用状态转换机(以任何编程语言编写),并在许多机器上安全地复制它。 有关协议的详细信息,请参见。 有关包括安全性和活动性证明在内的共识协议的详细分析,请...
  • Tendermint-2-共识算法:Tendermint-BFT详解

    千次阅读 2021-07-23 13:42:49
    Tendermint项目目录: Tendermint-1-基础概念 上一篇已经简单的介绍了Tendermint的基础概念,包括...一、Tendermint-BFT详解 1.1 共识环境分析 角色:Validator(预先配置的网络中的一般验证者账户们)、Propo.

    关注公众号,查看更多区块链科研内容:
    2DrbmZ

    Tendermint项目目录:

    上一篇已经简单的介绍了Tendermint的基础概念,包括优势与特点、应用与生态等。下面将会详细的介绍Tendermint的共识算法,你将会学习到一下几个方面:

    • Tendermint-PBFT详解(high-level view -> detail)
    • TBFT与传统PBFT的比较分析

    一、Tendermint-BFT详解

    1.1 共识环境分析

    • 角色:Validator(预先配置的网络中的一般验证者账户们)、Proposer(选举出的出块人)
    • 阶段:Propose阶段、Prevote阶段、Precommit阶段
    • 投票种类:prevote、precommit、commit

    这些名词下面会一一介绍到

    1.2 Round-based协议

    1.2.1 共识的开始

    整个Tendermint区块链网络需要通过Round-based协议来决定下一个区块,在区块链中共识的直接目的就是确定下一个区块内容、链接下一个区块

    共识的决定需要所有角色进行投票,vote的基本结构如图(来自于PPIO):

    gtpHpr

    通过这些字段指定以下内容:

    1. 当前投票的目标区块 <= Height、Hash
    2. 当前投票的轮次 <= round
    3. 当前投票的发起者 <= 签名

    1.2.2 总体流程

    Round-based协议的流程总的来说有五个步骤不断循环执行:

    状态机流程: NewHeight => Propose => Prevote => Precommit => Commit

    • NewHeight、Commit都是特殊的流程,后面会详述
    • 中间Propose、Prevote、Precommit称之为一个Round
    • 一个Round不一定就一定会产生一个区块,因为其中会有共识失败的可能,一旦失败就会重新开始轮次

    以下就是整个流程图(图片来自PPIO):

    CYYuL5

    1. 进入新的高度阶段,等待时间后,进入Propose阶段

    2. Propose阶段,选举Proposer, 然后Proposer提交一个Proposal, 进入Prevote阶段

    3. Prevote阶段Validators对收到的Proposal进行prevote投票, 当达到2/3的prevote投票后进入Precommit阶段

    4. Precommit阶段进行precommit投票,当达到2/3的投票后进入Commit阶段;未达到重新进入Propose阶段即Step 2

    5. Commit阶段准备好新的高度以及广播了新的状态给节点,进入Step 1

    以上是整个过程,下面对于每个过程进行一一详细的介绍

    1.2.3 Proposal

    选举Proposer,也就是常见共识算法中的Leader,从Validators中选举,最初的Validator的注册通过编写配置文件genesis.json在区块链创世区块中配置(后期也可通过命令行添加)

    • Validator: 所有参与共识验证的注册节点
    • Proposer: 每轮从Validators中选举出的出块节点

    选择的规则:Round-robin

    规则其实很简单:

    • 初始化配置Validators后,全网的节点都会将所有的Validator数据备份到本地
    • 一个区块高度一般对应一次选举即可结束,但有时单节点障碍或网络异常等原因会造成一个高度需要多个轮次
    • 全网从已构建好的Validator循环排序数组的0位置开始指定Validator为Proposer,本次高度确定后,新的高度后依次向后指定(选择位置1的Validator为Proposer), 达到最后时从0重新开始
    • 当出现Proposer无法连接或异常时会跳过该节点继续向下指定,算法得以自动不断执行

    这里也就解释了“非阻塞轮询机制核心是为了避免选中的Proposer中断连接,从而共识阻塞”的意思

    那么,Validator循环排序数组是怎样挑选Validator的呢?

    根据Validator的votingPower来决定顺序,其votingPower越大被选中的概率也就越大。

    每个Validator的初始化的votingPower由其质押的资金stake1:1恒定 (PoS机制需要质押资金,质押资金也是在配置文件中配置)

    怎样防止votingPower很大的Validator选举垄断?

    votingPower更新算法:

    初始化后每轮votingPower都会更新:

    • 本轮未被选中的Validator本轮后其votingPower增加其初始化的stake,即 v o t i n g P o w e r = v o t i n g P o w e r + s t a k e votingPower= votingPower+stake votingPower=votingPower+stake​​
    • 本轮被选中的Validator本轮后其votingPower减少为Validator循环数组中其他Validator的stake之和,即
      v o t i n g P o w e r = v o t i n g P o w e r − ∑ i N s t a k e i   ,   i ≠ t h i s V a l i d a t o r votingPower = votingPower - \sum_{i}^Nstake_i \ , \ i \neq thisValidator votingPower=votingPoweriNstakei , i=thisValidator

    举例:初始化stake配置:A:1, B:2, C:3

    (图片引自知乎:吴寿鹤) 深色表示Proposer

    image-20210723102822577

    这张图片理解无障碍则已了解选举过程

    总结:

    1. 可以结合初始化配置将Pos设计成为DPoS
    2. Round-robin策略的问题在于下一个Proposer可以被预测到容易引发对于特点单点主机的DDos攻击,所以还需要隐藏Validator节点的Ip地址

    在选举出Proposer之后该Proposer提交一个Proposal,全网广播,其数据结构如下:

    proposal

    Proposal最为重要的字段就是Block,其核心目的就是将自己打包的区块广播更新区块链状态

    1.2.4 Prevote

    Validator 不断监听是否有新的Proposal区块…….

    在每个Validator进行Prevote阶段的投票之前,需要先判断自己是否锁定在上一轮的Proposal区块上:

    • 是则继续签名广播上一轮锁定的Proposal区块并广播prevote投票
    • 否则签名广播当前轮Proposal区块并广播prevote投票
    • 某些原因导致Validator没有锁定/收到任一Proposal区块,那么就签名广播一个的prevote投票

    通过不同轮次将统一网络中的Validator区分开避免多次prevote投票,prevote投票与Proposal区块一一对应

    1.2.5 Precommit

    对于每一个Validator不断接收网络中的Prevote投票…….

    在Precommit开始阶段,Validator会收集prevote投票:

    • 如果达到了总数的2/3个prevote投票,则为这个区块签名广播precommit投票,并且当前Validator锁定在此Proposal区块上,同时释放之前锁定的区块 , 一个Validator只能锁定在一个区块中
    • 如果其收到了超过2/3的空nil区块prevote投票, 那么释放之前锁定的所有区块
    • 如果没有收集超过任何2/3的prevote投票,那么其不会锁定在任何区块
      处于锁定状态的 Validator 会为锁定的区块收集 prevote 投票,并把这些投票打成包放入 proof-of-lock 中,proof-of-lock 会在之后的propose阶段用到。

    对于每个Validator需要维护一个**PoLC(Proof of Lock Change)**的投票集结构:

    PoLC表示在一个高度h和轮次r构成的元祖 ( h , r ) (h, r) (h,r)下, 对于一个区块b(可能为空nil)prevote投票数超过2/3的集合

    1.2.6 Commit

    对于每一个Validator不断接收网络中的precommit投票…….

    在 precommit 阶段后期,如果 Validator 收集到超过2/3的 precommit 投票,那么 Validator 进入到 Commit 阶段。

    否则进入下一轮的 Proposal 阶段

    Commit 阶段分为两个并行的步骤:

    1. Validator 收到了被全网 commit 的区块,Validator 会为这个区块广播一个commit 投票。
    2. Validator 需要为被全网络precommit的区块,收集到超过 ⅔ commit投票。

    一旦两个条件全部满足了,节点会将 commitTime 设置到当前时间上,并且会进入NewHeight 阶段, 开启新的一轮

    在整个共识过程的任何阶段,一旦节点收到超过⅔ commit 投票,那么它会立刻进入到commit 阶段。

    二、共识讨论

    2.1 为什么Tendermint-BFT可以不分叉

    分叉的诞生

    更详细的阶段流程图:

    image-20210723114007223

    1. 在propose阶段,proposer节点广播出了新块 B l o c k x Block_x Blockx
    2. A在超时时间内没有收到这个新块,向外广播pre-vote nil,B,C,D都收到了,向外广播pre-vote投给 B l o c k x Block_x Blockx
    3. 现在四个节点进入了pre-commit阶段,A处于红色内圈,B,C,D处于蓝色外圈
    4. 假设A由于自身网络不好,又没有在规定时间内收到超过2/3个对 B l o c k x Block_x Blockx 的投票,于是只能发出 pre-commit nil投票消息投给空块
    5. D收到了B和C的pre-vote消息,加上自己的,就超过了2/3了,于是D在本地区块链里commit了 B l o c k x Block_x Blockx
    6. B和C网络出现问题,收不到D在pre-commit消息,这是B和C只能看到2票投给了 B l o c k x Block_x Blockx ,一票投给了空块,全部不足2/3,于是B和C都只能 commit空块,高度不变,进人R+1轮,A也只能看到2票投给了 B l o c k x Block_x Blockx,一票投给了空块,也只能commit空块,高度不变,进人R+1轮
    7. 在R+1轮,由于新换了一个proposer, 提议了新的区块blockY,A,B,C 三个个可能会在达成共识,提交 B l o c k y Block_y Blocky于是对于节点D来说在同样的高度,就有 B l o c k x Block_x Blockx B l o c k y Block_y Blocky两个块,产生了分叉。

    Tendermint加上了锁的机制,具体就是,在第7步,即使proposer出了新块 B l o c k y Block_y Blocky​,A,B,C只能被锁定在第6步他们的pre-commit块上:

    • A在第6步投给了空块,那么在第R+1轮,只能继续投给空块
    • B、C在第6步投给了 B l o c k x Block_x Blockx,那么在新一轮,永远只能投给 B l o c k x Block_x Blockx

    这样在R+1轮,就会有1票投给空块,两票投给 B l o c k x Block_x Blockx,最终达成共识 B l o c k x Block_x Blockx,A,B,C三人都会commit B l o c k x Block_x Blockx,与D一致,没有产生冲突。

    原因

    首先PBFT的要求是全网有小于1/3的拜占庭节点,这是共识的基本前提条件,也是讨论分叉的前提条件。

    当一个区块B在第R轮被Commit,那么就表明有大于2/3的节点在R轮投了precommit投票,进而就表明至少有大于1/3的节点锁定在R’>R轮

    拜占庭共识的环境就是假设节点都不一定是诚实的,所以投precommit的2/3中的节点并不一定都是诚实的,所以可能会有大于1/3的节点锁定的更高轮次

    对于不同轮次的同一高度的区块确定来说也就不会出现两个2/3的prevote投票(因为有1/3在R’轮锁定), 所以就不会分叉

    对于同一个高度,想要确定此高度的最终区块,可能会产生多个轮次的投票

    总结:其不可分叉来自于其BFT共识的锁定以及PoLC共同完成

    2.2 Tendermint-BFT与PBFT的比较

    相同点:

    • 都属于BFT类型的算法,最多容忍不超过1/3的恶意节点
    • 都是三阶段提交,Tendermint的propose->pre-vote->pre-commit三个阶段,跟PBFT的三个阶段,pre-prepare, prepare, commit 三阶段是一一对应的
    • 都在超时的时候,换掉proposer/primary (都是leader)

    不同点:

    不够Tendermint相对于PBFT有两处简化。

    1. Tendermint没有PBFT那种View Change阶段
      Tendermint很巧妙的把超时的情况跟普通情况融合成了统一的形式,都是 propose->pre-vote->pre-commit 三阶段,只是超时的时候新块是一个特殊的空块切换proposer是通过提交commit空块来触发的,而PBFT是有一个单独的view change过程来触发primary轮换。
    2. Tendermint的所有信息都存储在区块链
      因为PBFT是1999年提出来的,那时候还没有blockchain这个东西(blockchain是2009年比特币出现之后才有的),因此PBFT的所有节点虽有有一致的数据,但数据是分散存放的。PBFT的每个节点的数据包括:

    The state of each replica includes the state of the service, a message log containing messages the replica has accepted, and an integer denoting the replica’s current view.

    每个副本的状态包括服务状态、包含副本已接受消息的消息日志和一个表示副本当前视图的整数。

    Blockchain就是一个分布式数据库,好比在MySQL这类DBMS数据库没出现之前,人们都是把数据写入文件然后存在硬盘上,发明出各种奇怪的文件格式和组织方式。有了MySQL后,管理数据就方便多了。同理,Tendermint 把数据全部存入blockchain, PBFT没有blockchain这样一个分布式数据库,所有全节点需要自己在硬盘上管理数据,比如为了压缩消息日志,丢弃老的消息,节省硬盘空间,引入了checkpoint的概念,光是数据管理这一块就多了很多繁琐的步骤。

    总结:

    Tendermint和PBFT关系类似于Raft和Paxos的关系,Tendermint是PBFT的简化版,是针对blockchain这个场景下的简化版PBFT 。

    三、总结

    区块链技术元素提取:

    改进传统PBFT方法:

    • Pos+BFT选举共识与主链共识的解耦合搭配
    • 对区块施加锁机制以及PoFL,将节点绑定在一个区块的共识中防止分叉
    • 提交nil块的投票可以省略view change流程
    展开全文
  • BFT类共识协议概览与分析实测

    万次阅读 2019-05-16 18:22:23
    本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等; 针对拜占庭错误场景优化的,包括Aardvark、Primer等等; 为公链应用而优化的协议,...

    摘要

    本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览:

    • 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等;
    • 针对拜占庭错误场景优化的,包括Aardvark、Primer等等;
    • 为公链应用而优化的协议,包括DPoS+BFT、Zilliqa等等。

    本文还选用PBFT、Zyzzyva、Zilliqa协议,编写程序进行实测,主要得到以下结果及技术指导建议:

    • Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多;
    • 调整PBFT检查点周期对性能没有太大影响;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力;
    • Zyzzyva在其客户端足够的情况下,增加批量数会对吞吐量和共识时间等性能指标均有较大提升;
    • 虽然增加批量数对Zilliqa等协议都有促进效果,但这也会增加带宽占用。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。

    目录

    1. 引言
    2. 主要结论
    3. 共识问题及BFT协议简介
     3.1 一致性问题及原理
     3.2 BFT共识原理及流程简介
     3.3 技术思路分析换手率
    4. BFT类共识概览
     4.1 针对无拜占庭错误场景进行优化
     4.2 很对拜占庭错误场景进行优化
     4.3 为公链应用优化
    5. 实测对比
     5.1 测试方案介绍
     5.2 场景1:节点均正常的横向比较
     5.3 场景2:节点异常时的横向比较
     5.4 场景3:PBFT测试研究
     5.5 场景4:Zyzzyva测试研究
     5.6 场景5:Zilliqa测试研究
    6. 参考资料


    1. 引言

    共识协议被许多人视为是区块链项目的核心。无论是对区块链平台的交易处理能力、扩展性影响还是对通证经济的激励模型设计,共识协议都会产生很大影响。

    共识协议从大的方面可分为自比特币诞生以来产生的PoW等中本聪共识协议和拜占庭容错(BFT)类共识协议这两大类协议。其中,在计算机科学的分布式系统研究领域已较多研究的BFT类共识协议近年来被越来越多的应用于联盟链平台。与此同时,也有越来越多的研发工作尝试将BFT应用于公链平台。

    我们在本文中对BFT类协议进行了综述性概览分析,并从改进思路上将现有BFT类共识协议分为3大类:针对无拜占庭错误场景优化的协议、针对拜占庭错误场景优化的协议以及为公链应用而优化的协议;另外选用了PBFT、Zyzzyva、Zilliqa协议,编写程序并运行后得到实测对比结果,对共识协议的具体设计提供一些技术性指导建议。

    2. 主要结论

    经过研究与测试分析,我们得到以下主要结论及技术建议:

    • Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多;
    • 对PBFT,调整检查点周期对性能没有太大影响;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力;
    • Zyzzyva在其客户端足够的情况下,增加批量数会对吞吐量和共识时间等性能指标均有较大提升;
    • 虽然增加批量数对Zilliqa等协议都有促进效果,但网络中消息量也会增加。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。

    3. 共识问题及BFT协议简介

    3.1. 一致性问题及原理

    计算机世界早已从“单机版”进入了“大型多人在线”的时代,区块链的诞生与发展更是让这一特性得到了充分的体现。这个过程中不可避免的产生了多个计算机之间如何达成一致的问题。常见问题包括:

    表 1 常见网络服务器错误[1]

    在已经大规模投入使用中的分布式数据库系统环境中,有可能存在很多的宕机错误。根据CAP原理[2],Paxos和Raft协议被设计为在牺牲一定可用性的情况下,解决在节点服务器可能宕机问题的协议[3]。

    然而这些协议在区块链领域内还不能直接使用,因为还有其他更多在区块链领域内可能出现的错误。在表1中这种任意类型错误都可能发生的场景中,服务器有可能产生原本不应该输出的内容,系统要做好最坏情况的准备。例如,当一个服务器向不同的服务器发送截然相反的消息时,那么仅可处理宕机错误Paxos协议就无能为力了。

    这种类型错误,也被称为拜占庭错误,最早由Pease和Lamport在上世纪80年代通过拜占庭将军问题进行描述和分析[4][5]。

    因此相较于分布式数据库,区块链的对于一致性问题的设计和实现要更为复杂,这也是为什么区块链不只是一个简单的分布式数据库的原因之一。

    3.2 BFT共识原理及流程简介

    Lamport等人在其经典论文[4]中除了提出拜占庭将军问题外,也提供了两种解决办法[6][7]。

    第一种为“口头消息”的OM(m)协议,即除了链路上可使用加密安全保障外,不允许使用任何的加密算法。该协议需要两两之间递归的传递大量消息,因此消息复杂度很高,为指数级,不太具有可实际操作性。但这一算法仍有其很高的价值,首先是为“实用拜占庭容错”(Practical Byzantine Fault Tolerance)这一多项式级别复杂度协议的诞生做了一个铺垫;另外,其1/3容错节点数量也被证明为是该类算法的理论上限。

    而第二种为“加密消息”的SM(m)协议。该算法与第一种不同之处在于使用签名算法。每个节点都能产生一个不可伪造的签名,并可由其他节点进行验证。当收到消息后,节点会通过签名来判断及验证该消息是否已收到过。最终不再收到消息后,消息共识结束。它同样假设是在一个同步网络内进行;另外,签名身份体系信息需要在网络运行前确定,较难实现扩展。Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》[8]就是根据这一协议在区块链实际场景中所作的适应性改造探索[9]。

    3.3 技术思路分析

    与从比特币系统中衍生出的中本聪共识不同,BFT类协议基于节点间传递消息对网络中提案达成共识。因此一般来说消息复杂度较高,而且节点的加入和退出过程需要进行特别处理,但一旦达成共识则形成确定性结果,而不是中本聪共识的概率上的最终一致。

    因此基于以上特性,BFT类共识目前在金融场景以及联盟链场景中应用的更多。不过随着研究的探索推进,一些可在公有链场景下使用的BFT共识也正在不断研发出来。

    4. BFT类共识概览

    我们在已有BFT类共识分类[10][11]的基础上,继续对目前BFT协议进行了梳理。因为BFT协议中的无论是口头协议还是书面协议都不够“实用”,很难在实际场景中直接运用。因此后来学术界和业界对BFT协议有了大量的改进。按照改进思路的不同,这些协议主要可分为以下3大类方向:

    • 针对无拜占庭错误场景进行优化
    • 针对拜占庭错误场景进行优化
    • 为公链应用而做的优化

    4.1 针对无拜占庭错误场景进行优化

    此场景假设大部分情况下,网络中的节点运行都正常,拜占庭错误并不经常出现,因此可对这种节点均正常情况下的共识机制进行简化或优化。

    下面我们根据不同的优化方法,对这些协议进行分项介绍。

    4.1.1. 基于协约的方法

    对BFT协议最为经典的改进主要是以PBFT为代表的基于节点协约一致(Agreement)的方法。该类协议通常会有一个主节点作为网络中的枢轴。比其他节点相比,主节点在共识过程中会发出最主要的作用,但通常也会成为系统性能的瓶颈。因为主节点需要将客户端发来的请求排序后发送给所有的备节点。所有节点通过互相通信后达成一致,实现安全性(Safety);大多数协议中所有节点也会向客户端回复响应,实现活性(Liveness)。该类协议通常需要3f+1个节点来实现对f个拜占庭节点的容错。

    实用拜占庭容错Practical Byzantine Fault Tolerance. 简称PBFT)[12]是早期对其进行的改进,将BFT的消息复杂度从指数级降低为 级别,即具备了可实际使用的条件。

    图 1 正常情况下的PBFT消息传播过程[12]

    PBFT协议将共识过程分为了5个阶段(如果不算与客户端交互的阶段,则可视为3个阶段):

    • Request阶段是客户端发送信息;
    • 在Pre-prepare阶段,主节点接到消息对其签名并分配一个唯一的序号n并将该消息发送给其他节点;
    • Prepare阶段:所有备份节点收到主节点发来的PRE-PREPARE消息后,将一个包含当前视图号v、消息序号n、消息摘要的PREPARE信息发给所有其他节点。如果节点收到了2f个以上的PREPARE消息后则进入到下一阶段并且该消息处于Prepared状态;
    • Commit阶段:每个节点广播一个保护当前视图号v、消息序号n的COMMIT消息。当节点收到2f个相同的COMMIT消息并且小于序号n的消息都已被执行,那么当前消息会被执行并被标记为Committed状态;
    • Reply阶段:所有节点将执行结果返回给客户端。

    除了以上阶段流程外,协议运行过程中还涉及到几个重要概念:

    • 水位:每个节点在运行协议时会设置一个处理消息的窗口,消息序号在这个区间内的时候才会被处理,例如最小序号设为h、最大序号为H;
    • 检查点(Checkpoint):在运行提交过程中所有已处于已准备好(Prepared)和已提交状态(Committed)的信息会被记录在内存中。节点会定期(每执行k个请求后)记录一个稳定的检查点并截断记录,即每执行k个请求后,会将水位h和H提高k个单位;
    • 视图切换(View Change):但是当节点发现对某个消息的等待超过一定时间后,则认为是主节点失效,会发送视图切换(VIEW-CHANGE)消息并开始视图切换的过程;
    • 批量(Batch):实际执行中会采用的一些优化改进技术,例如批量方式,即实际程序并不是对单个提交来每次运行协议,而是会在以集合形式同时在网络中处理,并通过设置批量大小(Batch Size)的方式来控制处理消息的数量。

    在设置了以上运行机制后,尽管消息复杂度仍然较高,PBFT已具备了实际运行的可行性。之后的许多BFT类协议均在PBFT协议基础上进行改进,并将PBFT作为研究对比的基准对象。

    Chain协议。Chain协议[13]采用了一个和其名称很相似的链条式传播路径[14]。从主节点开始,每一次传播时即加入该节点的摘要信息。当客户端较多时,Chain通常会比PBFT、Zyzzyva等吞吐量更高。

    图 2 Chain消息传播过程[10]

    Ring协议。Ring协议[15]使用环形拓扑方式来传递消息,即每个节点都有消息的上一个发送者和下一个接收者,以此方式来降低对部分节点分配更多工作而形成的性能瓶颈问题。对有无错误的不同场景,Ring分别采用两种运行模式:快速模式(Fast Mode)和弹性模式(Resilient Mode),并采用ABSTRACT框架进行切换[14]。

    图 3 快速模式下Ring消息传播过程[15]

    BFT-SMaRt协议。BFT-SMaRt[16]与PBFT、UpRight[17]类似,但增强了可靠性、模块化程度、同时还提供了灵活的编程接口。

    4.1.2 基于Quorum的方法

    Quorum机制是一种分布式系统中常用的机制,用来保证数据冗余和最终一致性的投票算法。其主要思想来源于抽屉原理,常用于分布式系统的读写访问控制[18]。

    该类共识协议不需要节点间相互通讯,而是由节点直接执行并响应客户端发来的请求。当受到足够数量的响应后,客户端才会将结果最终提交。但是当出现拜占庭错误场景时,通常会花费较大的代价来解决。另外,由于缺少对请求的排序机制,Quorum方法无法处理有竞争(contention)的情况。

    Q/U协议。Q/U协议(Query/Update)[19]是一个典型的基于Quorum的协议。Q/U没有主节点来为请求排序,而是由客户端直接向节点发送请求并由节点反馈结果。它需要5f+1个节点来对f个拜占庭节点容错。

    HQ协议(Hybrid Quorum)[20]是另一个较为早期和著名的共识协议。正如其名称,HQ综合参考并优化了Q/U协议和PBFT协议:只需要3f+1个节点进行容错,并针对没有竞争的情况简化了PBFT节点间通讯。当没有竞争情况下,共识主要分为两个阶段:第一阶段是客户端发送请求并收集节点的状态信息;当收到结果表明2f+1个节点状态相同且可以执行请求后,开始第二阶段信息发送、由节点执行请求。而如果发现有竞争,则采用类似PBFT的解决过程,性能也退化为和PBFT类似。

    图 4 HQ的消息传播模式[20]

    Quorum协议也是基于Quorum机制的一个共识协议[14],主要没有客户端竞争的非异步网络而进行设计,只需要3f+1个节点进行拜占庭容错。当没有错误产生时,Quorum协议的传播路径和Q/U类似,节点独立执行请求并自己维护一个执行历史记录。当客户端数量较少时,其吞吐量和延迟等性能指标均比其他BFT类共识更好。但其缺点也和Q/U类似,无法处理客户端有竞争的情况[10]。

    4.1.3 基于Speculation的方法

    在这类协议中,节点不需要通过需要消耗大量系统代价的3阶段提交过程即可响应客户端的请求。采用了更乐观的策略,节点同意由主节点发出的排序请求并给客户端返回结果。由客户端而不是节点来负责考虑一致性问题。如果发现不一致问题,由客户端负责通知节点回滚至一致状态。

    Zyzzyva协议。Zyzzyva是该类中最典型的一个协议[21]。它需要3f+1个节点进行拜占庭容错。与基于Agreement的协议类似,Zyzzyva中的主节点也是将客户端发来的请求排序后转发其他节点。每个节点根据自身历史记录来执行请求并将结果反馈给客户端。客户端根据节点返回的一致性结果数量分别执行不同的动作。

    在没有错误的场景下,Zyzzyva表现比PBFT和Q/U等协议要好;但是当有错误时,因为要涉及到和PBFT类似的view change过程,其性能也会急剧下降。

    图 5 Zyzzyva的消息传播模式[21]

    Zeno协议。Zeno协议[22]在Zyzzyva基础上进行修改,将原有的强一致性替换为一个较弱的最终一致性保证。它允许客户端偶尔忽略其他更新,但是当网络不稳定时,所有节点的状态需要进行合并以达成一致。

    ZZ协议。ZZ协议[23]同样基于Speculation机制。因其还采用了分离处理的机制,也可将其归为“分离处理一致性与执行请求的阶段”的类别,我们将在后续章节继续介绍。

    4.1.4 基于客户端的方法

    基于客户端的方法通过避免节点间通信的方式,来避免异常节点对正常节点的攻击、误导或延迟。协议完全依赖于这些客户端的正确性,假设客户端都没有异常、是诚实且在宕机时会被外部所感知的。

    OBFT(Obfuscated BFT)协议[24]是这一类协议的典型代表。它需要3f+1个节点进行容错,但与其他很多BFT协议涉及到节点间通讯不同,OBFT协议中的节点完全不需要关注其他节点并只与客户端联系,因此避免了恶意节点干扰其他正常从而影响系统性能的问题,不过这也带来了一个较强的假设:必须完全信任客户端不会作恶。因此该类协议都存在着较难在实际场景中进行应用的问题。

    图 6 OBFT的消息传播模式[24]

    4.1.5 基于可信组件的方法

    因为FLP不可能性原理(即使网络通讯可靠也无法在任何场景下都能达到共识[25]),一些协议并不使用传统的超时等机制而是基于外部的可信组件进行设计。这些组件也需要被认为是无拜占庭错误的,但允许存在宕机等临时性无法提供服务的情况[11]。基于以上条件,该类协议可以将容错节点数量从3f+1将为2f+1。

    例如,CheapBFT协议[26]。需要基于一个叫做CASH的FPGA可信设备,从而降低正常情况下协议对于资源的使用。

    4.1.6 基于拜占庭锁的方法

    拜占庭锁是拜占庭协议的扩展,通过利用IO绝大多数时间里不会出现竞争的特性来达到降低服务器响应时间、提高吞吐量与扩展性的效果。

    这种方法最早由Zzyzx协议[27]提出,包括加锁和解锁两个部分。加解锁过程均基于现有拜占庭协议达成对客户端授权的一致。当授权完成,则获得锁的客户端可直接进行操作,从而去掉了主节点排序、节点间通讯等操作,从而大幅度提高吞吐量。但当有多个客户端需要频繁切换时,其性能也会大幅下降,因此该协议较为适用于客户端不会频繁发生变化的情况下。

    4.1.7 基于分离一致性与执行请求的方法

    还有一类改进方法是将共识与执行提交的过程分开,因为执行客户端请求只需要f+1个(当没有拜占庭节点或者客户端可验证结果正确性时)或2f+1个节点(当有可能存在拜占庭节点且客户端不可验证正确性时),因此可将协议的执行分为2个部分,一部分节点负责一致性共识协议,而另一部分负责执行提交,从而提高吞吐量。

    ZZ协议,通过虚拟化技术[23]把节点均正常场景下的执行所需节点数量从2f+1降为f+1个。在没有错误场景时,只通过f+1个节点来执行请求,其余服务器在休息状态;而当执行请求的节点发生错误时,客户端通过虚拟化技术快速启动更多的节点来执行[11]。

    ODRC协议也是将执行节点数量将为了f+1,但与ZZ协议不同,它并没有采用额外的虚拟化等技术,而是在BFT协议过程中的节点达成一致后、执行请求前增加了一个选择执行节点的阶段。该阶段根据当前系统状态,选择指定数量的节点执行请求[11]。

    4.2 针对拜占庭错误场景进行优化

    上面介绍的一类协议均是针对没有错误的场景对BFT协议进行简化而设计,因此当遇到拜占庭错误时,这类协议的性能一般都会下降比较多,甚至很难保证系统活性。而另一类协议的改进目的是为了有效对拜占庭行为(甚至是一些罕见的行为)进行容错,降低系统在有无拜占庭错误这两种场景下的表现差异。主要有以下几个比较典型的协议。

    Aardvark协议。Aardvark协议[28]的通讯过程与PBFT类似,但对许多可能的错误场景设计了适应性机制以保证系统的安全性和活性。这些适应性机制包括:对客户端采用混合签名等机制来防止客户端作恶;更为积极主动的触发view change过程以避免主节点有拜占庭行为;为每个节点设计3f+1个网络接口(其中1个用于其与客户端通信,其余3f个用于节点间通讯),以此隔离网络通道来防止流量攻击。

    Prime协议。因为PBFT协议中当主节点作恶的view change过程对性能的影响较大,即便主节点不进行任何主动作恶,只要在处理排序过程中刻意增加延迟就可以降低系统整体性能表现。Prime协议[29]针对此情况进行了改进,在PBFT过程前增加了一个预排序的阶段,包括PO Request、PO ACK、PO ARU等阶段。通过这种分析主节点排序时间的方式,使得所有节点来监控网络表现。因此主节点必须及时将消息发送给其他节点以避免被替换掉。因为引入了额外的阶段,Prime在正常场景中的性能要比PBFT等协议要低;但在存在错误场景中其表现要比其他协议要好。

    图 7 Prime消息传播模式[10]

    Spinning协议。Spinning协议[30]在PBFT协议的基础上,设计用来减轻更换主节点的代价。在正常场景中的,Spinning通讯过程与PBFT相同。不过它没有view change过程,而是通过合并操作的方式来收集不同节点信息来决定之前视图中的操作是否应在新视图中执行。

    RBFT协议。Redundant-BFT协议[31]利用目前所流行的多核技术来保障鲁棒性。该协议采用与PBFT类似的通讯过程,但在Pre-prepare阶段前增加了一个Propagate阶段。客户端首先将消息发送给f+1个节点,这些节点在Propagate阶段相互传递消息以此来保证客户端请求会被所有正常节点接收到。RBFT执行f+1个同一个协议的多个实例,其中每个实例都对应一个在不同物理机器上运行的主节点,不过只有被主实例所排序的请求才会被有效执行。备份实例运行的意义主要在于监测运行性能:当发现主实例运行缓慢时,备份实例将触发view change过程选择出一个新的主实例。

    图 8 RBFT的消息传播模式[31]

    4.3 为公链应用优化

    传统PBFT及类似协议,其自身的特性导致应用场景有较多限制,例如消息复杂度随节点数成平方级别上升、主节点容易成为系统性能瓶颈、节点列表需要提前固定且节点间相互已知。所以在分布式账本系统中,更多应用于联盟链或私有链场景中。

    为了适应公有链场景中的大规模扩展需求,有不少项目进行了有益尝试,具体方式可主要包括与公链共识结合以及基于密码学机制等两大类方式。

    4.3.1 与中本聪共识结合

    为了在公有链中利用BFT类共识的结果可快速得到最终确认等优点,一类做法是将BFT类协议与中本聪协议进行结合,以此来取长补短,将BFT类共识引入应用到公有链的业务场景中。

    例如,Elaine Shi等在2017年提出将BFT类共识与中本聪共识结合的办法[32]:通过PoW先选出负责共识的委员会(Commitee);由委员会再进行PBFT过程达成共识并出块[33]。

    DPoS+BFT协议也是类似的思路。该协议是BFT类协议与中本聪协议结合的一个典型代表,被用于BM开发的石墨烯[34]“全家桶”平台,包括BitShares[35]、Steemit[36]、EOS[37]等。通证持有者以投票等方式选出自己支持的“代表”,并由这些代表组成的见证人网络通过BFT的方式进行共识。例如EOS中,用户投票产生21个可出块的“超级节点”,以BFT方式共识后轮流出块,对1/3以下的“超级节点”可以容错。基于该类共识协议的平台性能较高,且不需要竞争挖矿等,但缺点是略微中心化。

    DBFT协议是NEO提出的授权拜占庭容错协议[38],和DPoS+BFT思路有些类似,是一种通过代理投票实现大规模参与的共识协议。通证持有者可通过投票选出他所支持的“代理”,然后代理再通过BFT达成共识。因此它也和DPoS+BFT类似,具有快速、扩展性好等特点,但也同样受到共识节点数量有限、中心化程度太高等质疑。

    Tendermint BFT协议。Cosmos项目提出了名为Tendermint BFT的一种基于BFT的PoS共识协议[39]。它以加权轮询的方式产生验证者集合,由选出的验证者产生共识提议并进行BFT过程。因此它也是一种在半同步网络中使用的确定性算法[40]。

    FBA协议。Stellar使用的恒星共识协议(Stellar Consensus Protocol)的背后是一种联邦拜占庭协议(Federated Byzantine Agreement)。该协议并不是直接把BFT和某一个中本聪共识结合,而是参考了中本聪对比特币的设计理念。该协议实现一个开放式的节点成员列表,任何人都可以加入。网络中的每个节点可自行选择其Quorum,降低对非理性行为的容忍程度,所以其性能和可扩展性都较为突出,但一些拜占庭行为也可能导致分叉等情况发生,因此节点需要花费不少代价去设置其所信任的节点列表。

    还有一些项目在尝试探索把BFT协议引入当前公链平台中,例如Istanbul BFT(IBFT)[41]就是通过引入验证者(validator)并基于Quorum机制运行,并被探索用于当前以太坊平台。

    除了狭义的“区块链”方式外,Hashgraph[42]也可认为是一种BFT类共识与DAG结合的协议。它通过gossip about gossip降低通信量,并且也是异步的BFT协议。

    4.3.2 基于密码学优化

    另一种可运用于公链的思路是利用密码学的方法,包括聚合签名、可验证随机函数、门限签名等,以达到降低BFT类共识的通讯代价、提高共识效率的目的。

    聚合签名

    E.Kokoris-Kogias等在其论文中提出了在共识机制中使用聚合签名的方法。论文中提到的ByzCoin[43]以数字签名方式替代原有PBFT使用的MAC将通讯延迟从 降低至 ;使用聚合签名方式将通讯复杂度进一步降低至 。但ByzCoin在主节点作恶或33%容错等方面仍有局限。

    之后一些公链项目,例如Zilliqa[44]等基于这种思想,采用EC-Schnorr多签算法提高PBFT过程中Prepare和Commit阶段的消息传递效率,并结合分片等优化技术以希望突出改进公有链平台TPS。

    Gosig[45]也使用该方法,同时还结合了Algorand以VRF方式选择“Leader”和多轮投票等方法来尽量降低Leader作恶可能性。

    可验证随机函数

    Algorand的BA★协议[46]使用了另一种密码学方法 — — 可验证随机函数(VRF),以加密抽签的形式随机决定“验证者”,并以带有权重的方式来全网共识,可认为是BFT类共识+PoS或PoWeight的架构。投票过程分为两个阶段:第一阶段通过一个分级共识选出“验证者”共识最多的候选区块;第二阶段运行一个二元拜占庭协议(接受出块或产生空块)。执行速度很快,不太容易产生分叉且交易确认时间虽用户数增加变化不大[33]。另外,Algorand通过加密方式隐藏了“领导者”的真实身份,提高了针对Leader攻击的安全性。

    VBFT协议也是使用VRF的一个共识协议[47],由Ontology提出,可认为是PoS+VRF+BFT:在共识协议的各个阶段,分别使用VRF从网络中选出该阶段所需要的节点,例如提案节点、验证节点、确认节点等并完成最终的共识。其中的选择参数是根据PoS来确定。

    门限签名

    以上介绍的协议大部分都需要假设基于一个同步或半同步的网络环境,而HoneyBadger BFT是第一个知名的异步BFT类协议[48],可在消息延迟没有明确上限的异步网络中运行。它首先将交易拆分为多份,各个节点间相互,减轻发起节点的消息发送瓶颈问题。而因为其异步网络环境,节点间收到交易是非同步的、随机顺序的。节点以二元拜占庭协议剔除无效交易和重复交易等后,得到一个异步公共交易子集(Asynchronous Common Subset)[49]。

    而门限加密使得只有f+1个诚实节点共同合作才能解密出消息原文,防止恶意节点对于最终交易集的攻击。HoneyBadger BFT协议的主要限制是其在异步网络下为一个非确定性共识算法(FLP不可能性原理[25])。

    5. 实测对比

    除了进行理论上的归纳总结与分析外,我们选用PBFT、Zyzzyva、Zilliqa协议,编写共识协议的程序进行实测模拟。通过横向与纵向的测试比较,以期得出以上共识协议的技术建议。

    5.1 测试方案介绍

    由于共识协议都需要基于一个实际的应用场景,我们在程序中将节点处理计算的过程设定为一个固定的延时;消息传输采用消息队列方式来实现。程序基于Java 8编写实现。

    因为PBFT、Zilliqa等共识协议在一些实现细节上缺少明确描述,我们在实现程序时进行了以下设定:

    • 节点之间的网络时延在5–10毫秒内;
    • 网络带宽设置为100MB(假设每条请求消息平均100B大小)。

    5.2 场景1:节点均正常的横向比较

    首先在所有节点均为诚实节点的情况下,我们进行多组实测,横向比较PBFT、Zyzzyva、Zilliqa共识协议在不同情况下的协议吞吐量、网络中平均消息量、达成共识总时长等性能指标。

    本场景的第1组测试条件为:

    • 批量大小= 10
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1,消息发送间隔=1ms

    横向比较的结果(其中吞吐量和网络平均消息量单位均为消息笔数,下同)如下:

    整体来看,BFT类协议的吞吐量确实均会随着节点数增加而下降(性能降低),当节点数量过多时,很难完成处理。

    对于PBFT协议,可看到其消息量和节点数量确实有平方级的关系(本例中约为 );

    Zyzzyva和Zilliqa的消息量为线性关系,即以上协议的方法确实会降低PBFT消息量大的问题

    由于批量大小会影响网络中处理消息的数量,因此我们在第2组观察批量大小对性能的影响。测试条件为:

    • 节点数=22
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1,消息发送间隔=1ms

    从结果可以看出,增加批量大小对吞吐量均有较为明显的提升,但也会增加网络中的消息量。其中,Zilliqa的吞吐量提升最为明显,因为该算法可以在一个单位时间内进行聚合签名并且可以批量验证,即批量大小相当于打包区块的大小。所以当总带宽允许的情况下,Zilliqa算法可以通过增加批量而获取极大的吞吐量。

    PBFT和Zyzzyva提升到一定阶段后在实测中会遇到瓶颈(批量数>30后,吞吐量始终接近1000),原因是本次测试客户端消息间隔导致。如果降低发送间隔或者增加客户端数量均可提高吞吐量。例如,当假设消息可并行处理且没有到达网络带宽瓶颈,增加客户端可得到如下PBFT的性能结果为:

    5.3 场景2:节点异常时的横向比较

    BFT类协议的一个复杂之处在于部分节点存在拜占庭行为情况下的处理,各个协议对不同数量的异常节点,该情况下的效率可能也不一样。

    在本场景中我们设置节点数固定为22个。

    本场景第1组测试设置条件为:

    • 批量大小=10
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1

    经过测试PBFT、Zyzzyva、Zilliqa的吞吐量分别为:

    其中,可看到PBFT吞吐量和共识时间都优于Zyzzyva和Zilliqa,是因为本次测试暂忽略了网络消息量增大对消息传播延迟的影响。

    从结果也可看到网络平均消息量会减小,尤其是PBFT的消息量会随着节点增多而降低较快。其原因是当出现拜占庭节点时,作恶节点的消息会被忽略掉;而同时,消息传播和达成共识的时间会相应延长。

    5.4 场景3:PBFT测试研究

    下面的几个场景我们对比PBFT的批量、检查点周期与吞吐量、网络中平均消息量以及达成共识时间等性能表现之间的关系。

    • 节点数=22
    • 水位大小=50

    可以看到,对于PBFT来说,检查点周期调整对性能的影响并没有太大;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力。

    5.5 场景4:Zyzzyva测试研究

    从上述场景已可看到,调整批量大小会对共识性能产生影响;而Zyzzyva的主节点负责接收各客户端发来的请求,因此在客户端数量不同的情况下,表现可能也会不一样。因此我们针对不同的批量大小和客户端数量进行分析研究。

    从结果可以看到,当批量数较小时,增加客户端数量后,Zyzzyva整体性能并没有太大改观。

    当增大批量后,Zyzzyva的吞吐量提高较为明显;在增加客户端数量后,吞吐量和共识时间均有改观,但在增加一定程度后其表现并不会继续提升。

    另外和PBFT类似,增加客户端数量或增大批量后,Zyzzyva的网络消息也会随之增加。

    5.6 场景5:Zilliqa测试研究

    从场景1的测试中可看出,Zilliqa的Batch可以设置的远比PBFT大从而获得极大的吞吐量,因此与前两个纵向对比测试略有不同,本场景测试着眼点在网络带宽消耗上。在不同Batch下,我们测试研究Zilliqa的消耗情况(以PBFT作为一个基准对比)。

    测试条件为:

    • 节点数=22
    • 检查点周期=10
    • 消息大小=100B

    可以看到,尽管可设置较大的批量数来获得更高的吞吐量,但Zilliqa的最大带宽消耗也会随着批量数而线性增长作为对比,PBFT在批量数到达一定数量后,最大消耗带宽会趋于稳定。因此在实际应用共识协议时,应充分考虑好选用的共识协议以及实际网络带宽情况。

    6. 参考资料

    [1] M. van Steen and A. S. Tanenbaum, Distributed Systems, 3.01. 2017.

    [2] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,” ACM SIGACT News, 2002.

    [3] S. Gilbert and N. Lynch, “Perspectives on the CAP Theorem,” Computer (Long. Beach. Calif)., vol. 45, no. 2, pp. 30–36, 2012.

    [4] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Program. Lang. Syst., 1982.

    [5] LoomNetwork, “了解区块链的基本(第一部分):拜占庭容错(Byzantine Fault Tolerance),” 2018. [Online]. Available: https://segmentfault.com/a/1190000014009235.

    [6] bangerlee, “[上篇] 大话分布式系统理论基础.” [Online]. Available: https://mp.weixin.qq.com/s/p4PEZPjxJyYXKpkCCdShbw.

    [7] 初夏虎, “拜占庭将军问题深入探讨,” 2015. [Online]. Available: https://www.8btc.com/article/70370.

    [8] V. Buterin, “A Guide to 99% Fault Tolerant Consensus,” 2018. [Online]. Available: https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html.

    [9] 袁煜明 and 胡智威, “【火线视点10】Vitalik的‘99%容错共识算法’解析.”

    [10] D. Gupta, L. Perronne, and S. Bouchenak, “BFT-Bench: Towards a practical evaluation of robustness and effectiveness of BFT protocols,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.

    [11] J. FAN, L.-T. YI, and J.-W. SHU, “Research on the Technologies of Byzantine System,” J. Softw., vol. 24, no. 6, pp. 1346–1360, 2014.

    [12] M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” ACM Trans. Comput. Syst., 2002.

    [13] R. van Renesse and F. B. Schneider, “Chain Replication for Supporting High Throughput and Availability,” Proc. 6th Conf. Symp. Opearting Syst. Des. Implement. — Vol. 6, 2004.

    [14] P.-L. Aublin, R. Guerraoui, N. Knežević, V. Quéma, and M. Vukolić, “The Next 700 BFT Protocols,” ACM Trans. Comput. Syst., vol. 32, no. 4, pp. 1–45, 2015.

    [15] R. Guerraoui, N. Knezevic, V. Quema, and M. Vukolic, “Stretching BFT,” 2010.

    [16] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with BFT-SMART,” in Proceedings — 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, 2014.

    [17] A. Clement et al., “Upright cluster services,” in Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles — SOSP ’09, 2009.

    [18] Wikipedia, “Quorum (distributed computing).” [Online]. Available: https://en.wikipedia.org/wiki/Quorum_(distributed_computing).

    [19] M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie, “Fault-scalable Byzantine fault-tolerant services,” in Proceedings of the twentieth ACM symposium on Operating systems principles — SOSP ’05, 2005.

    [20] B. Bershad, D. ACM Digital Library., B. ACM Special Interest Group in Operating Systems., R. Rodrigues, and L. Shrira, “HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance,” Proc. 7th Symp. Oper. Syst. Des. Implement., p. 407, 2006.

    [21] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: Speculative Byzantine Fault Tolerance,” Proc. Symp. Oper. Syst. Princ., pp. 45–58, 2007.

    [22] A. Singh, P. Fonseca, and P. Kuznetsov, “Zeno: Eventually Consistent Byzantine-Fault Tolerance.,” Nsdi, pp. 169–184, 2009.

    [23] T. Wood, R. Singh, A. Venkataramani, P. Shenoy, and E. Cecchet, “ZZ and the art of practical BFT execution,” in Proceedings of the sixth conference on Computer systems — EuroSys ’11, 2011.

    [24] A. Shoker, J. P. Bahsoun, and M. Yabandeh, “Improving independence of failures in BFT,” in Proceedings — IEEE 12th International Symposium on Network Computing and Applications, NCA 2013, 2013.

    [25] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” J. ACM, 1985.

    [26] R. Kapitza et al., “CheapBFT: Resource-efficient Byzantine Fault Tolerance,” Proc. 7th ACM Eur. Conf. Comput. Syst., 2012.

    [27] J. Hendricks, S. Sinnamohideen, G. R. Ganger, and M. K. Reiter, “Zzyzx: Scalable fault tolerance through Byzantine locking,” in Proceedings of the International Conference on Dependable Systems and Networks, 2010.

    [28] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults,” Symp. A Q. J. Mod. Foreign Lit., 2009.

    [29] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Prime: Byzantine replication under attack,” IEEE Trans. Dependable Secur. Comput., 2011.

    [30] G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Spin one’s wheels? Byzantine fault tolerance with a spinning primary,” in Proceedings of the IEEE Symposium on Reliable Distributed Systems, 2009.

    [31] P. L. Aublin, S. Ben Mokhtar, and V. Quema, “RBFT: Redundant byzantine fault tolerance,” in Proceedings — International Conference on Distributed Computing Systems, 2013.

    [32] R. Pass and E. Shi, “Hybrid consensus: {Efficient} consensus in the permissionless model,” Leibniz {Int}. {Proc}. {Informatics}, {LIPIcs}, 2017.

    [33] 姚前, 数字货币初探. 中国金融出版社, 2018.

    [34] “Graphene Technical Documentation.” [Online]. Available: http://docs.bitshares.org/.

    [35] “BitShares Whitepapers.” [Online]. Available: http://docs.bitshares.org/bitshares/papers/.

    [36] “Steem Whitepaper.” [Online]. Available: https://steem.io/steem-whitepaper.pdf.

    [37] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

    [38] NEO, “A Byzantine Fault Tolerance Algorithm for Blockchain.” [Online]. Available: http://docs.neo.org/en-us/basic/consensus/whitepaper.html.

    [39] “Cosmos Whitepaper.” [Online]. Available: https://github.com/cosmos/cosmos/blob/master/WHITEPAPER.md.

    [40] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

    [41] Z.-C. Lin, “Istanbul BFT (IBFT).” [Online]. Available: https://medium.com/getamis/istanbul-bft-ibft-c2758b7fe6ff.

    [42] H. Hashgraph, “Hedera: A Governing Council & Public Hashgraph Network.” [Online]. Available: https://s3.amazonaws.com/hedera-hashgraph/hh-whitepaper-v1.1-180518.pdf.

    [43] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.

    [44] T. Z. Team, “Zilliqa Technical Whitepaper,” Zilliqa, pp. 1–8, 2017.

    [45] P. Li, G. Wang, X. Chen, and W. Xu, “Gosig: Scalable Byzantine Consensus on Adversarial Wide Area Network for Blockchains,” 2018.

    [46] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,” Proc. 26th Symp. Oper. Syst. Princ., 2017.

    [47] “VBFT算法介绍.” [Online]. Available: https://github.com/ontio/documentation/blob/master/vbft-intro/vbft-intro-CN.md.

    [48] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The Honey Badger of BFT Protocols,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security — CCS’16, 2016.

    [49] Juniway, “Honey Badger of BFT 协议详解.” [Online]. Available: https://www.jianshu.com/p/15d5b6f968d9.

    展开全文
  • 拜占庭容错状态机复制(BFT)协议是一种复制协议,它容忍少量副本的任意故障。 但现有的BFT协议在故障发生时不能提供可接受的性能。 这是由于所有现有的针对高吞吐量的BFT协议都使用了一个称为主副本primary的特殊副本...
  • 分布式构建系统通过拜占庭容错(BFT)共识提供加密的可复制性证明。 关于 同步性是用于Rust板条箱的分布式构建系统,该系统已发布到 。 它可以在使用 ( 和等工具背后的核心库)管理的Docker容器内可复制地构建板条...
  • 1. DPoS共识 通过在一群数量有限的节点中,使用轮换或者其他算法来筛选出某个节点作为主节点。并且赋予该节点出块的权利。 主节点是将该时段的交易打包成区块后用...1.1 BFT(拜占庭容错机制) 当一个小区块在区
  • 本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等 针对拜占庭错误场景优化的,包括Aardvark、Primer等等 为公链应用而优化的协议,包括...
  • BFT-SMaRT共识算法

    2021-03-08 04:11:35
    BFT-SMaRT是一个基于Java的开源库,为基于BFT的状态机复制算法提供了一套改善的解决方案;它实现了类似于PBFT的共识协议,但在无故障执行时具有更高的性能,且在拜占庭副本进行任意错误行为时能保证整体共识的正确性...
  • bft英语测试题.doc

    2021-10-03 15:30:56
    bft英语测试题.doc
  • 榕树贷款分布式共识算法可以分为CFT(Crash Fault Tolerance)与BFT(Byzantine Fault Tolerance)。 榕树贷款CFT算法如Paxos、Raft,只能容忍分布式节点中存在故障,不能容忍分布式节点中有节点作恶。榕树贷款适用...
  • 共识算法是实现自主产权区块链的必不可少的关键环节,本文列出社区中相对成熟的区块链共识算法开源实现,包括BFT共识、Raft共识、Paxos共识、PoW共识等,可供希望开发自主产权区块链的团队参考学习。 相关推荐:...
  • 共识算法-BFT

    2020-07-26 12:14:48
    什么是 BFT BFT( Byzantine Fault Tolerance)称为拜占庭容错。拜占庭容错技术是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因,计算机和...
  • Test_BFT-源码.rar

    2021-10-10 20:46:57
    Test_BFT-源码.rar
  • cems2000BFT手册

    2015-07-07 13:08:02
    关于系统的使用方法及描述,该文件系统的阐述了相关问题,及问题解决的方法,
  • BFT-DPoS共识算法讲解

    2020-06-11 04:25:55
    BFT-DPoS是在DPoS上改进而来,因为DPoS有如下的缺点: 一个区块的确认时间(不可篡改时间)为45s,从而制约了吞吐量 为什么确认时间这么久? 是因为一个区块由producer生成后,不能立刻被其他producers验证。只有...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,217
精华内容 1,286
关键字:

bft

友情链接: mplzdhh748.zip