技术分享 | VRF抽签与投票的思考

2023-10-09 16:50

本文主要是介绍技术分享 | VRF抽签与投票的思考,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

VRF(可验证随机函数)在Algorand提出后,被越来越多的公链项目应用。VRF的特点在于其能够产生一个能够被验证的随机结果,通过该随机结果,在区块链中可以实现随机“选举”或“抽签”。与POS结合后能够减轻POS的“富者恒富”的现象。

然而我们知道,鱼和熊掌不可兼得,提高公平性(去中心化)的代价是牺牲性能或安全性。Algorand选择了牺牲一定的共识效率来换取公平性(去中心化)。以下是在分析Algorand、Ont等使用VRF的共识算法中,对VRF抽签的一些思考。

 

一. Algorand概括

Algorand作为第一个使用了VRF的共识算法,其共识流程可以大致总结为三个步骤:

1. 随机选举多个提案者,提案新区块。(提案者由VRF抽签)

2. 收集多个提案区块并选出权重最高者。

3. BA* 对多个区块提案中的一个提案达成共识。(每一步的投票者均需要VRF抽签)

二. POS+Random

VRF本质是随机函数,而在区块链系统的共识流程中不能用完全公平的随机,因为出块者需要有激励,同时每个节点的贡献值也并非一致。 所以通常都会在VRF抽签之前加一层POS,将“更优”的一批节点先选出来作为候选人。

对于POS+Random 的共识算法,一般有如下三种情况:

Case 1. 随机抽签出一个提案者,其他节点验证并接受该节点提案。

Case 2. 随机抽签出一个提案者与多个投票者,需要投票者对区块达成共识。(代表:Tendermint)

Case 3. 随机抽签出多个提案者与多个投票者,需要投票者从多个提案区块中选出一个并达成共识。(代表:Algorand)

下面我们来一一解析以上case:

Case 1即为很纯粹的POS,希望通过随机抽签抑制“富者恒富”的现象。但纯粹的POS有Nothing at stake的问题,提案者可以基于多个分叉链提出不同的区块,使得分叉进一步加剧。(以太坊Casper FFG依靠惩罚金来解决,但这无疑也增加了系统的复杂度)

Case 2很类似于自带viewchange的PBFT,一般容错率也为1/3。投票者的目的在于给于deterministic confirmation,且部分解决了Nothing at stake问题。为何说是“部分解决”,因为为了最大化提高区块通过的概率,提案者仍会给多个分叉链投票。但由于有投票者这一角色,可保证在网络不分区的情况下理论上不会产生分叉。同时,由于随机抽签采用公开的信息,提案者也能够被预测。

Case 3其实是Algorand的高度简化版,Case 2也可作为Case 3的一个特例。一方面,多个提案者之间相互竞争,促使提案者本身提出正确的区块;另一方面,对于抽取多个提案者的场景,可采用VRF作为随机函数:节点使用公开的信息和自己的密钥直接在本地运行选举函数判断自己是否被选中,其他节点能够验证但无法预测提案者。

这里值得注意的是,在分布式网络中,VRF无法完成固定数量的抽签任务,原因是VRF的一个Input是节点私钥,这使得每个节点产生的随机值均不相同,全网只能验证结果是否合法,但无法设计统一的标准使得某个随机结果唯一性地符合某个条件。

三. VRF抽签的优势

在VRF出现之前,为了满足选举信息的可验证,通常采用公开的信息作为Input,通过公开的随机函数得出随机结果,以随机结果作为依据进行抽签。 由于所有信息均为公开,故所有节点都可以在本地计算出抽签结果。但上述抽签方案有一个很大的问题:攻击者有一定的时间窗口能够预测出抽签结果,及时对被选举人实施攻击。

VRF很好地解决了这个问题:

1. 由于使用节点私钥作为Input,VRF的结果无法被预测。其他节点只有通过网络接收到随机结果后才能对其合法性进行验证,即攻击者在得知选举结果时,选举人已经做出行动了。

2. VRF的输出值除了随机值外,还包含一个proof,提供了随机值验证的零知识证明,即不必知道某人私钥即可证明该随机值是由某人产生的。

四. VRF抽签的弊端

VRF为随机抽签提供了隐私性和可验证,但也带来了一个很棘手的问题:丢失全局的抽签信息,降低投票共识的成功率

由于VRF需要私钥作为Input,其他节点只能通过网络通信获得相应proof后才能验证随机结果是否合法,所以任何节点都无法得知全网的真实选举情况的。这对投票类共识算法带来了巨大的挑战。投票类共识算法必须设置一个通过阈值(如2/3以上),只有通过该阈值才视为投票通过。而基于VRF的共识算法丢失了全局的选举信息后,只能以期望值的形式设置阈值,使得投票退化为概率型投票。

如何理解概率型投票?首先,我们需要明确确定型投票的定义——投票结果应遵循大部分提案者的意见(通过或不通过)。当投票结果不一定会遵循大部分提案者的意见,那么就属于概率型投票。对于由VRF选出的投票者的投票阶段,由于阈值的设置与实际选举情况是割裂的,则即使大部分投票者同意提案,提案仍有可能达不到阈值,从而显示“不同意”的结果,与大多数投票者的意志相背。我认为,之所以Algorand在BinaryBA*中要设计多轮投票,并且每一步均重新选举投票者,其目的是通过不断重选提高实际投票达到阈值的概率,通过多轮投票提高达成共识的概率。

640?wx_fmt=png


五. 总结

VRF算法最早由Silvio Micali(图灵奖得主,Algorand的创始人)在1999年提出,也是由他首次将其引入到区块链中,为区块链的共识算法提供了崭新的研究思路和解决方案。但我们在分析并使用VRF的时候,不仅需要分析VRF本身,也应该关注先驱者是如何思考和设计基于VRF的共识算法过程。一味地将VRF迁移至其他的共识算法,可能并不能达到预期的效果,甚至反而会有带来其他的不确定性风险。

推荐阅读

640?wx_fmt=png

这篇关于技术分享 | VRF抽签与投票的思考的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/174202

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python解析器安装指南分享(Mac/Windows/Linux)

《Python解析器安装指南分享(Mac/Windows/Linux)》:本文主要介绍Python解析器安装指南(Mac/Windows/Linux),具有很好的参考价值,希望对大家有所帮助,如有... 目NMNkN录1js. 安装包下载1.1 python 下载官网2.核心安装方式3. MACOS 系统安

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

Python中常用的四种取整方式分享

《Python中常用的四种取整方式分享》在数据处理和数值计算中,取整操作是非常常见的需求,Python提供了多种取整方式,本文为大家整理了四种常用的方法,希望对大家有所帮助... 目录引言向零取整(Truncate)向下取整(Floor)向上取整(Ceil)四舍五入(Round)四种取整方式的对比综合示例应

linux进程D状态的解决思路分享

《linux进程D状态的解决思路分享》在Linux系统中,进程在内核模式下等待I/O完成时会进入不间断睡眠状态(D状态),这种状态下,进程无法通过普通方式被杀死,本文通过实验模拟了这种状态,并分析了如... 目录1. 问题描述2. 问题分析3. 实验模拟3.1 使用losetup创建一个卷作为pv的磁盘3.

MySQL8.2.0安装教程分享

《MySQL8.2.0安装教程分享》这篇文章详细介绍了如何在Windows系统上安装MySQL数据库软件,包括下载、安装、配置和设置环境变量的步骤... 目录mysql的安装图文1.python访问网址2javascript.点击3.进入Downloads向下滑动4.选择Community Server5.

CentOS系统Maven安装教程分享

《CentOS系统Maven安装教程分享》本文介绍了如何在CentOS系统中安装Maven,并提供了一个简单的实际应用案例,安装Maven需要先安装Java和设置环境变量,Maven可以自动管理项目的... 目录准备工作下载并安装Maven常见问题及解决方法实际应用案例总结Maven是一个流行的项目管理工具

10个Python自动化办公的脚本分享

《10个Python自动化办公的脚本分享》在日常办公中,我们常常会被繁琐、重复的任务占据大量时间,本文为大家分享了10个实用的Python自动化办公案例及源码,希望对大家有所帮助... 目录1. 批量处理 Excel 文件2. 自动发送邮件3. 批量重命名文件4. 数据清洗5. 生成 PPT6. 自动化测试