IJTCS | 分论坛日程：区块链技术

编者按

第二届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2021年8月16日-20日在线上线下交互举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。图灵奖获得者、中科院外籍院士、北京大学访问讲席教授John Hopcroft教授任大会主席。

本期带来“区块链技术”分论坛精彩介绍。

“区块链技术”介绍

区块链技术的核心是用去中心化的方式实现大规模分布式数据库，使互联网上不能相互信任的用户不需要借助可信第三方就能进行交易，并为交易的可靠性和最终性提供保障。这项技术被认为是继互联网之后最具颠覆性的技术创新，正在给很多行业，如金融、电子商务、知识产权保护、医疗保险等等带来巨大机遇和变革。

区块链行业的高速发展给计算机科学的很多方向，如密码学、分布式计算、编程语言、博弈论、计算机网络、形式化验证等等提出了很多重要的研究问题。在这次会议中，我们着重关注理论计算及相关学科在区块链领域的研究，邀请了多位活跃在这一领域前沿的学者来介绍他们的工作。相信这样的交流会给不同学科的科研人员和区块链行业的从业者带来思想的碰撞，使与会者了解最新的科研动态，促进国内外区块链领域的交流和发展。

“区块链技术”分论坛主席

 

Jing Chen

Stony Brook University and Algorand

“区块链技术”分论坛议程

时间：2021年8月19日

时间	讲者	报告题目
10:00-10:55	陈婧	Speculative Smart Contracts
11:00-11:25	Artem  Barger	Sublinear-Round Byzantine Agreement under Corrupt Majority
13:30-13:55	Bo Li	Maximal Information Propagation via Lotteries
14:00-14:25	Georgios  Piliouras	Dynamical Analysis of the EIP-1559 Ethereum Fee Market
14:30-14:55	会议接收论文报告
15:00-15:25	会议接收论文报告

“区块链技术”分论坛报告简介

 

Speculative Smart Contracts

Jing Chen, Stony Brook University and Algorand

Abstract

In this talk, I'll introduce Algorand's layer-2 speculative smart contract architecture and discuss the design principles behind it.

Biography

Jing Chen is Chief Scientist and Head of Theory Research at Algorand Inc. She is an Assistant Professor in the Computer Science Department at Stony Brook University, and an affiliated assistant professor at the Economics Department. Her main research interests are distributed ledgers, smart contracts, game theory, and algorithms. Jing received her bachelor's and master’s degrees in computer science from Tsinghua University, and her PhD in computer science from MIT. Jing received the NSF CAREER Award in 2016.

 

Enabling an alternative trust model with Blockchain DB

Artem Barger, IDEAS

Abstract

Blockchain DB is a concept which came to combine traditional databases with intrinsic primitives of the blockchain. Thus, creating a distributed system with an append-only transactions log, leveraging cryptography to guarantee non-repudiation and data integrity. Such synergy will allow for securing every transaction and establishing the provable chronology of events. Therefore, blockchain database will ensure business application layer with extreme data integrity, temper resistant data source and ability to generate full data trail. These properties become extremely important in missions or applications to connect to external data oracles to collect and extract information. In contrast, a central authoritative entity does storage and processing of the information.

Biography

Currently leading working as a Director of Blockchain Research Group at Interdisciplinary research organization IDEAS. Used to work at IBM Research for almost 10 years as being staff member working at the Cloud Foundation group in Haifa Research Lab, with over 10 years of experience in the design and development of distributed systems. Holding a BSc from the Technion - Israel Institute of Technology. MSc from Haifa University with thesis research focused on Machine Learning clustering algorithms, Big Data processing and mining in distributed and streaming models. Currently, Artem is a Linux Foundation maintainer leading design and development of scalable replication of distributed ledgers for Hyperledger Fabric - the permissioned enterprise-grade blockchain platform. Contributing to design and maintenance of the project.

 

Sublinear-Round Byzantine Agreement under Corrupt Majority

Hubert Chan, University of Hong Kong

Abstract

Although Byzantine Agreement (BA) has been studied for three decades, until recently, there still exist significant gaps in our understanding regarding its round complexity. An open question was the following: Can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS'07) and  Fitzi and Nielsen (DISC'09), we have partial and affirmative answers to this question albeit for the narrow regime  where  is the number of corrupt nodes and  is the total number of nodes. So far, no positive result is known about the setting  even for static corruption!

In this work, we make progress along this somewhat stagnant front. We show that there exists a corrupt-majority BA protocol that terminates in  rounds in the worst case, satisfies consistency with probability at least  , and tolerates  fraction of corrupt nodes. Our protocol secures against an adversary that can corrupt nodes adaptively during the protocol execution but cannot perform "after-the-fact" removal of honest messages that have already been sent prior to corruption. Our upper bound is optimal up to a logarithmic factor in light of the elegant  lower bound by Garay et al. (FOCS'07).

This work has appeared in PKC 2020, and is a collaboration with Rafael Pass and Elaine Shi.

Biography

Hubert Chan is an Associate Professor at the Department of Computer Science at the University of Hong Kong. He completed his PhD in Computer Science at Carnegie Mellon University in 2007.  His main research interests are approximation algorithms, discrete metric space, privacy and security inspired problems.

 

Maximal Information Propagation via Lotteries

Bo Li, Hong Kong Polytechnic University

Abstract

Propagating information to more people through their friends is becoming an increasingly important technology used in domains such as blockchain, advertising, and social media. To incentivize people to broadcast the desired information, the designer may use a (monetary) rewarding scheme, which specifies who gets how much, to compensate for the propagation. Several properties are desirable for the rewarding scheme, such as budget feasible, individually rational, incentive compatible and Sybil-proof. In this work, we design a free market with lotteries, where every participant decides how much of the reward she wants to withhold before propagating to others. We show that under our scheme, all agents will maximally propagate and all above properties are satisfied.

Biography

Bo Li is currently an assistant professor in the Department of Computing at The Hong Kong Polytechnic University. Formerly, he was a Postdoctoral Fellow at University of Oxford and University of Texas at Austin. He received his PhD in Computer Science from Stony Brook University. He is broadly interested in algorithms, AI and game theory.

 

Dynamical Analysis of the EIP-1559 Ethereum Fee Market

Georgios Piliouras, Singapore University of Technology and Design

Abstract

Participation in permissionless blockchains results in competition over system resources, which needs to be controlled with fees. Ethereum’s current fee mechanism is implemented via a first-price auction that results in unpredictable fees as well as other inefficiencies. EIP-1559 is a recent, improved proposal that introduces a number of innovative features such as a dynamically adaptive base fee that is burned, instead of being paid to the miners. Despite intense interest in understanding its properties, several basic questions such as whether and under what conditions does this protocol self-stabilize have remained elusive thus far. We perform a thorough analysis of the resulting fee market dynamic mechanism via a combination of tools from game theory and dynamical systems. We start by providing bounds on the step-size of the base fee update rule that suffice for global convergence to equilibrium via Lyapunov arguments. In the negative direction, we show that for larger step-sizes instability and even formally chaotic behavior are possible under a wide range of settings. We complement these qualitative results with quantitative bounds on the resulting range of base fees. We conclude our analysis with a thorough experimental case study that corroborates our theoretical findings.

Biography

Dr. Piliouras is the Provost's chair associate professor at the Singapore University of Technology and Design (SUTD). His research interests lie in the areas of multi-agent learning, algorithmic game theory, blockchain and dynamical systems. He received his PhD in Computer Science from Cornell University in 2010. He has held research positions at the Georgia Institute of Technology (GaTech, ECE Dept.) and California Institute of Technology (Caltech, Dept. of Computing and Mathematical Sciences) as well as a visiting professor position at UC Berkeley. He is a research collaborator of DeepMind and the Ethereum Foundation. He is the recipient of a Singapore NRF Fellowship (2018), a Simons/UC Berkeley Fellowship (2015), a best paper nomination at AAMAS (2019) and a best paper award at AAAI (2021).

IJTCS注册信息

大会现已正式面向公众开放注册！

观看线上报告：免费

通过在线观看直播的方式参与大会，可通过直播平台提问。

线上会议注册：

（普通）$100 /￥700

（学生）$50 /￥350*

获得所有Zoom会议参会链接，作为参会人在线参加全部会议，直接在线提问讨论并参与特设互动环节。

线下会议注册：

（普通）$200 / ￥1400

（学生）$100 / ￥700*

作为参会人在线下（北京大学）参加会议，与知名学者们面对面交流；同时享受线上注册的所有权益。

*因防疫要求，仅开放10个校外线下参会名额。

点击 ↓↓↓二维码↓↓↓ 跳转注册页面

*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至[e-mail]，邮件主题格式为＂Student Registration+姓名+线上/线下"。

大会主席 

 

John Hopcroft

图灵奖获得者

中国科学院外籍院士

北京大学访问讲席教授

大会联合主席 

 

邓小铁

北京大学讲席教授

欧洲科学院外籍院士

ACM/IEEE Fellow

顾问委员会主席 

高  文

中国工程院院士

北京大学教授

梅  宏

中国科学院院士

CCF理事长

张平文

中国科学院院士

CSIAM理事长

北京大学教授

程序委员会主席 

孙晓明

中科院计算所

研究员

邓小铁

北京大学

讲席教授

李闽溟

香港城市大学

副教授

陆品燕

上海财经大学

教授

李  建

清华大学

副教授

组织单位 

合作媒体

联系人

大会赞助、合作等事宜

请联系

[e-mail]

010-62761029

大会网站

https://econcs.pku.edu.cn/ijtcs2021/index.htm

↑↑扫码直达大会官网↑↑

推荐阅读 

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点“阅读原文”转大会注册页面