新闻 | 中心师生参加FAW 2019并作报告
关键词：FAW
编者按
2019年4月29日至5月3日，北京大学前沿计算研究中心邓小铁老师、孔雨晴老师和北大图灵班学生马义平、吴怡凡、周子鑫参加了第13届国际算法前沿研讨会（The Thirteenth International Frontiers of Algorithmics Workshop，FAW 2019），并在会上展示了相关工作。
与会人员合影
新闻到此结束，下面，延续EcnoCS@PKU风格，开始论文解读——
Securely Trading Unverifiable Information without Trust
马义平、吴怡凡
指导教师：孔雨晴
1
背景
显式地展示出来后便立即失去了价值。就算向购买者展示信息，信息购买者仍然会感到困惑，特别是当它无法验证时（例如主观意见或没有ground truth）。此外，一个普遍受信任的第三方中介可能逐渐成长为一个信息垄断者，如谷歌、亚马逊。由此可见，对可信任第三方的依赖严重限制了信息资产的交易。
为此，我们需要一个无信任的（即没有可信任第三方，只有买方和卖方）无法验证的信息交易协议，使得它同时解决：
机制运行过程中参与者的诚实性
参与者的隐私安全问题
对不可验证的信息的定价问题
效率问题（即高效计算）
无授权第三方
2
工具
协议的设计中，我们主要运用了如下的工具：
同行评审（Peer Prediction）
为了评估数据的价值，我们引入了同行评审。卖方手中信息的价格由他和其他卖方数据的互信息决定。先前的工作已经证明了，当卖方诚实地报告自己的信息时，他的利益才能被最大化。
安全多方计算（MPC, short for Secure Multi-party Computation）
安全多方计算（MPC）协议帮助两个（或多个）参与者，在不透露任何信息的情况下，通过交互计算出一个函数的值（图1左）。它的功能就像一个可信任的第三方，两位参与者将函数的输入交给第三方，第三方根据函数计算完毕后，只透露函数的输出（图1右）。
智能合约（smart contract）
先前的工作已经证明，完全公平（一手交钱、一手交货）的交易，在没有第三方做裁判的情况下是无法实现的。智能合约在我们的协议中起到了裁判的作用。通过区块链的共识协议，智能合约能够帮助强制执行合约代码的内容。这样，合约就不需要双方互相信任。
图1
3
主要结果
在无法验证的信息交易场景中，我们通过借用包括同行预测，安全多方计算和智能合约在内的三种工具，提出了一种无信任，诚实，安全的信息交易协议Smart Information-Dealer (Smind)。
SMind机制：图2阐述了SMind机制的运行过程。
图2
首先，买方和卖方签订合约，确定支付函数，并向智能合约支付押金。
之后买房向卖方发放题目（买方想买的是卖方的答案），且向两个卖方发放的题目的顺序完全独立。当卖方完成问题的回答之后，他们把自己的题目和对应的答案加密，将其发送给买方；同时他们向合约上传自己数据加密后的哈希值和加密的密钥的哈希值。
两位卖方运行MPC协议，计算支付函数的结果。计算完成后，将计算结果和能解开数据密钥的密钥提交给智能合约，由智能合约公开。
买方收到密钥后，解开数据，查看数据是否符合要求（回答的是否是指定的问题、答案是否符合支付函数的结果）。如果符合，由智能合约发起转账，并退回押金。如果不符合，买方向智能合约提起申诉，由智能合约根据之前提交的信息来仲裁交易。
An Improved Incentive Ratio of the Resource Sharing on Cycles
周子鑫
指导教师：邓小铁
我们研究了P2P网络中资源共享的问题，在P2P网络中每个参与者既是资源的提供者也是使用者，每个参与者通过与其他参与者互相共享资源的方式获益。我们研究了P2P网络在Sybil Attack下是否稳定，改进了之前对于环形网络中Sybil Attack效果的上界分析。
图文 | 吴怡凡、周子鑫
EconCS@PKU
近 期 热 点
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”到FAW'19官网