We propose a proof-of-sequential-work (PoSW) that can be verified with only a single query to the random oracle for each random challenge. Proofs-of-sequential-work are protocols that facilitate a verifier to efficiently verify if a prover has executed a specified number of computations sequentially. Denoting this number of sequential computations with N , the prover with poly(N) parallelism must take $\Omega(N)$-sequential time while the verifier verifies the computation in O(log N)-sequential time using upto O(log N) parallelism. We propose a PoSW that allows any verifier, even the one with no parallelism, to verify using just a single sequential computation on a single challenge. All the existing PoSWs [10, 5, 2, 6] mandate a prover to compute a sequence of responses from a random oracle against N-rounds of queries. Then the prover commits this sequence using a commitment scheme (e.g., Merkle root (like) commitment) predefined in the PoSWs. Now the verifier asks the prover to provide a set of proofs against t randomly chosen checkpoints, called challenges, in the computed sequence. The verifier finds out the commitment from each of these proofs spending O(log N) rounds of queries to the oracle. It can be reduced to a single round of queries only if the verifier owns O(log N) parallelism [6]. The verifier in our PoSW demands no parallelism but uses a single query to the random oracle in order to verify each of the t challenges. The key observation is that the commitment schemes themselves in the prior works demand O(log N ) oracle queries to verify.


翻译:我们提出一个序列序列测试( POSW ), 只能通过对随机挑战随机的 O( log N ) 的随机质询来验证。 序列性测试是协议, 方便验证者对证明者是否连续执行一定数量的计算进行高效率的核查。 与 N 相比的序列计算次数, 与 mol( N) 平行的验证者必须使用 $\ Omega( N) 序列时间, 而核查者只能对O( log N) 随机挑战进行一次平行序列的计算。 我们提议一个 PoSW, 允许任何验证者( 即使是没有平行的验证者), 对单个挑战仅使用单次顺序计算进行核查。 所有现有的 PoSW 系统 [10、 5、 2 、 6] 都要求校验匹配随机或随机查询的序列。 然后, 验证者只能使用承诺方案( 如 Merkle room ) 向 O( orral road) 的对 O 的校验( ) 校验之前的 O 。

0
下载
关闭预览

相关内容

甲骨文公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989年正式进入中国市场。2013年,甲骨文已超越 IBM ,成为继 Microsoft 后全球第二大软件公司。
专知会员服务
25+阅读 · 2021年4月2日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2010年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年7月14日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
ACM TOMM Call for Papers
CCF多媒体专委会
2+阅读 · 2022年3月23日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium9
中国图象图形学学会CSIG
0+阅读 · 2021年12月17日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2010年12月31日
国家自然科学基金
1+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员