【论文笔记】Proofs-of-delay and randomness beacons in Ethereum-2017IEEE SB Workshop

本文主要是介绍【论文笔记】Proofs-of-delay and randomness beacons in Ethereum-2017IEEE SB Workshop,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

论文作者:Benedikt B¨unzy, Steven Goldfeder,Joseph Bonneauy  Princeton University,  Stanford University

论文源代码:https://github.com/bbuenz/VerifiableBeacon

作者个人网站:https://crypto.stanford.edu/~buenz/publications/

论文简介:We show how one can generate an unpredictable randomness beacon that is publicly verifiable using a blockchain. The beacon can be used to verify the correct execution of randomized algorithms such as lotteries. The novel property of the beacon is that it is publicly verifiable in that a verifier is convinced that the beacon was unpredictable even if she did not partake in the generation of the beacon and without any trust assumptions. We also show how we can enable interactive verification using an efficient smart contract.

本文介绍了利用区块链来生成公开可验证的不可预测随机数。该随机数(beacon信标)可以用于验证随机算法是否正确执行,并且具有可被公开验证的特性,本文介绍了如何利用智能合约来完成交互式验证过程。

 

Abstract

利用区块链中的值来作为随机数可能被矿工控制。我们可以用 delay function 延迟函数来增加随机数的安全性。

本文中用以太坊作为环境,提出了一个利用 refereed delegation model 来验证延迟函数的多轮协议

文中评估了生成一个随机数的代价大概为180000gas,进行协议认证的代价为720000gas,并讨论了激励问题。

 

I. Introduction

很多密码学应用需要随机数,Rabin首次提出了 randomness beacon 随机信标的概念,它能产生不可预测的随机值。

传统的随机信标方法有:引入可信第三方 trusted third party 或者 利用 commit-and-reveal 从半诚实的 semi-trusted 多方获取随机数。但是要防止恶意的参与者,这需要可证明机制 provably verifable secret-sharing technique 或者 经济惩罚措施。

A. manipulating blockchain-based beacons

直接用区块链的值可能被矿工控制,可能遭受 network-manipulation attack (块很容易冲突,其他矿工可以不费代价来选择要哪一块,攻击者可以控制网络来阻止不想要的随机数结果) 和 block-withholding attack(矿工丢弃不想要的随机数的块)。

B. Preventing manipulation using delay functions

为抵抗上述两种攻击,本文利用延迟函数,使得矿工不能提前计算出随机数的结果,等攻击者想发起攻击影响随机数时,随机数已经公布出来,无法改变随机数。

延迟函数:需要花费一定时间计算,顺序进行,验证比计算更快。例如做开平方这个操作。

C. Our contributions

1. 提出并实现了一个随机数信标的协议,由 maintainer 来计算延迟函数的结果,把结果传到合约中,利用 challenge协议 来证明这个maintainer的随机数结果是正确的。

The basic idea is that a designated authority (a beacon maintainer) computes a delay function and publishes the result to a smart contract providing queryable access to the beacon results. Trust in this authority is mitigated by the use of a challenge protocol that any third party can initiate to prove that the authority has published an incorrect beacon result.

2. 分析了运行随机信标的激励机制,讨论了其中的经济机制和惩罚措施等。

 

II. PROTOCOL

1. 定义函数 f 是线性可组合的 compositionally-sequential,没有其他算法能加速计算,只能重复计算n次。

maintainer 会计算出结果 y = F(X),保存在合约中,现在要分析其可信程度。最简单的就是重新计算一次结果 y,但是很耗时。

Refereed delegation model:如果y错误,押金会没收。本文设计的协议使得单个验证者可以检查 y 是否正确。

Our goal is to make it efficient for independent verifiers (or referees) to check that the computation was performed correctly.

1) One-round refereeing protocol:   

总共要进行 t 次 f 函数计算,prover公开 k 个checkpoint 检查点的结果,i 从1~k,检查间隔为 t/k,y0 = x 

verifier 发现(4)式不成立时,就可以判定结果y不正确。

优点:

1. 计算可以并行,最多用 k 个处理器,有  y_{i-1} 可以并行计算 y_{i}

2. 合约可以用 m = t/k 次计算 f 来检查verifier的判定结果是否正确,只需要验证verifier所说的(4)式是否真的不正确。

3. prover只需要上传k个检查点,verifier的结论很容易被验证。

缺点:上传k个检查点,很贵,因此需要权衡 m(验证一个检查点需要的f计算次数)和 k(上传检查点格式)

2) n-round refereeing protocol: (这里最好看原文)

prover想要声明某一对  y_{i-1} , y_{i} 的值是不正确的,即 y_{i} \neq f^{\frac{t}{k}}\left (y_{i-1} \right) 其实也就是要提供一个 y_{i}^{'} = f^{\frac{t}{k}}\left (y_{i-1} \right)

本文设计n轮协议,prover和verifier的角色不断交换,互相公开一些检查点,直到检查点的距离到达m,能用合约直接进行验证

本协议能保证:

如果 y = F(x),那么诚实的prover不可能被挑战成功。

如果y != F(x),那么诚实的challenger一定能成功进行挑战 challenge.

3) Efficiency:

prover总共完成的工作 t=m\cdot k^{n} ,m是循环次数,k个检查点,n轮协议

总共发给合约 k*n 个检查点,和 n 个 challenged checkpoints (每个值都属于 1~k)

 

V. COSTS AND PARAMETERS

i5 CPU + OpenSSl,用了solidity的编译指令,参考 https://solidity.readthedocs.io/en/v0.5.3/assembly.html 

选择参数使得维护一个随机数服务和发现错误结果的成本最低。

A. Selecting the delay function f

hash函数:keccak256(SHA-3)消耗40gas,SHA-256消耗76gas

开平方根:512位和1024位的模数

下标展示了不同的 f 的计算代价和验证代价

B. Parameter selection and cost estimation

选择 t=2^40,差不多要一个小时计算,还要选择k,m,建议选择k=2^4, m = 2^8

这篇关于【论文笔记】Proofs-of-delay and randomness beacons in Ethereum-2017IEEE SB Workshop的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新,又或者克隆了某个项目之后,你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi