写在最前面
这个系列的博客初衷是安全计算课程的小组作业，我们组分到的方向是安全计算与区块链，要求每人或两三个人讲一篇与该方向相关的顶会顶刊论文
之前找论文找了两三天，要么不是顶会顶刊，要么就是与方向不搭，寻思着去会议直接找，然后在Eurocrypt 2019找到了这篇论文
$[CGJ19]$ Arka Rai Choudhuri, Vipul Goyal, and Abhishek Jain. Founding secure computation on blockchains. In EUROCRYPT, pages 351–380, 2019.
刚开始的时候看不太懂，紧急恶补了不少安全计算和零知识证明方面的知识点，前后看了大约一周，找了六篇论文还找到了原文作者在会议上做报告的录像，也是反复听了好几遍才大致听明白这篇论文想讲什么，其中涉及到很多密码学的工具，包括如何安全的使用这些工具和概念，以及在区块链上如何更好的使用这些工具
其次，本文涉及到区块链的知识，仅从客观角度描述和讨论这个技术，不涉及任何政治话题，不涉及炒币、挖矿等话题
前置知识
本系列文章涉及到了很多前置知识，暂时列一下，但是由于个人水平以及理解能力有限，所列知识点可能不全面，部分内容会在后面的博客中简单介绍
- 区块链
- 安全计算
- 零知识协议
- 密码学
- 形式语言
浅谈
安全计算概述
安全计算通常指代安全多方计算（当然也可以是两方），主要研究在无可信第三方的情况下，如何安全的计算一个约定函数的问题
安全计算主要的应用场景包括电子投票，门限签名，电子拍卖等等，近年来，将安全计算与机器学习或联邦学习相结合也是研究热门方向之一
安全计算最先由姚期智教授于1982年提出的百万富翁问题开始，此后主要由姚期智、Goldwasser、Micali、Rackoff等学者开始研究， 并开创了一些列的关于理论计算机科学、复杂性密码学、安全形式化、可证明安全性等极为重要的子领域
- 百万富翁问题：两个百万富翁想比较一下谁更富有，但是都不希望让对方知道自己有多少钱
对于安全计算而言，其有几个易于理解的特性
隐私性：整个计算过程不会泄露参与计算的用户的敏感数据
健壮性：任意多个参与者共谋，不影响计算结果的正确性
对于健壮性而言，这个要求实际上极其严格，在大部分情况下都达不到，因此提出一个弱化版的健壮性（青春版）
弱化健壮性：诚实的参与者能够检测出协议执行时发生的错误
而在安全计算中，还有一个比较重要的点就是如何实现公平，假设有如下一个场景，两个人希望分蛋糕，没有可信第三者的情况下，如何做到绝对的公平，简单的方法就是，一个人切，另一个人选，对于混淆电路而言，就是一方作为真值表的处理者，另一方作为电路的计算者
但对于有多个参与方而言，又该如何实现？换句话说，多个参与方协同计算一个约定的函数，并且保证每一方仅获取自己的计算结果，无法通过计算过程中的交互数据推测出其他任意一方的输入和输出数据，这就是安全计算需要研究的问题
记得之前在刷知乎的时候刷到过一个回答（搜了一下原回答已经找不到了），大致就是办公室里的各位想知道大家的平均工资是多少，但是又不希望透露自己的具体工资（可能怕太高被嫉妒或太低挂不住面子）
如果说有个可信第三方（比如老板或者财务），老板作为发钱的人当然知道各位的工资几何，也就理所应当的可以计算出办公室各位员工的平均工资
但仅限于这个简单的场景，实际场景中不可能永远都存在一个可信第三方，就算是上述场景中，也可能出现老板经常出差不在公司，或者老板根本就不屑于告诉你的情况，此时就可以用安全多方计算来解决问题，简单来说就是通过安全多方计算协议来替代上述中的可信第三方（老板原地辞职）
安全计算的组成
安全计算并不是一个单一的技术，和上文提到的区块链一样，其内部结合了很多密码学的技术和原语，我个人在学习过程中更偏向于将安全计算理解为一个技术栈，或者一个工具，而不是一个密码学原语或单一的技术
安全计算包含了很多的的密码学工具，其中不乏经典的对称加密、公钥加密、Hash函数，密钥交换协议、伪随机函数，也包括近年来的研究热点，如秘密共享（Secret Share），同态加密（Homomorphic Encryption）、不经意传输（Oblivious Transfer）等等
下面简单介绍一些常见的工具
秘密共享
将一个秘密拆分成若干个无意义的子秘密，将这些子秘密分发到各个参与方中，每个参与方都会有自己的秘密（的一部分），同时也会收到其他人的秘密的一部分，仅凭一个或少数几个参与方无法还原出原始的秘密，只有将各自的子秘密凑在一起时才可以还原
关于秘密共享，有一个典中典的方案，Shamir (n-t)，简单来说就是安全计算的n个参与方中，当任意大于等于t个参与方联合时，可以解开秘密数据，具体的方案和原理不在这里展开，感兴趣的话可以查阅Wiki，这里给出链接
回到之前的工资的例子，简单说一下如何安全的计算办公室里各位员工的平均工资，这里以三位员工为例，更多位员工的计算方法类似
假设我的工资是10k，小王的工资是20k，小李的工资是30k，则平均工资是20k，此时每个人将工资拆成三个数之和（如果有n个人，则拆成n个数之和）
我的做法如下
$$ Me:10000=1619859230+(-2034786203)+414936973 $$
同理，小王和小李也可以进行与我相同的操作
$$ Wang:20000=10238476.12+(-9187340.243)+(-1031135.877) $$
$$ Li:30000=(-3628800)+3724788+(-65988) $$
这个拆分过程，可以是任意的数，小数，或者无理数，如果小王和小李的数学功底足够好，也可以用矩阵，复数，或者傅里叶变换来做，这里仅阐述一个大致的思想，采用最简单的方法
之后每个人将这三个数分发给每个人，对于我而言，我将1619859230分发给我自己，-2034786203分发给小王，414936973分发给小李
经过上述过程后，每个人都有了自己的数（的一部分），和从其他人那里接收到的他的数的拆分的一部分，这里假设：
- 我收到了来自小王的
-9187340.243和来自小李的-3628800 - 小王收到了来自我的
-2034786203和来自小李的-65988，自己保留-1031135.877 - 小李收到来自我的
414936973和来自小王的10238476.12，自己保留3724788
此时对于我手上的三个数，计算其平均值
$$ \frac{1619859230+(-9187340.243)+(-3628800)}{3}=535681029.919 $$
小王和小李也按照他们收到的和拥有的数，计算平均值
$$ Wang:\frac{(-2034786203)+(-65988)+(-1031135.877)}{3}=-678627775.6256667 $$
$$ Li:\frac{414936973+10238476.12+3724788}{3}=142966745.706667 $$
然后再把三个人计算得到的平均数加起来，就可以得到三个人的平均工资了
$$ 535681029.919+(-678627775.6256667)+142966745.706667=20000 $$
对于计算过程中的小数点问题，也即计算精度问题，可以由参与方协商忽略，这里只讨论大致的思想，具体的计算精度需要权衡考虑包括效率在内的很多方面，此处不再展开
上述是比较通俗的理解，而对于数学化一点的描述方式如下
众所周知，三点可以确定一条抛物线，因此，可以构造一个基于抛物线的秘密共享
我和小王小李各自选择一条抛物线，约定抛物线在y轴的截距为我的工资，假设三个人选择三条抛物线如下
$$ Me:y_1=a_1x^2+b_1x+c_1=3x^2+4x+10000 $$
$$ Wang:y_2=a_2x^2+b_2x+c_2=-x^2+x+20000 $$
$$ Li:y_3=a_3x^2+b_3x+c_3=2x^2+(-x)+30000 $$
然后三个人分别找出各自选择的抛物线上的三个x轴坐标相同的点
$$ Me:(1,10007),(2,10020),(3,10039) $$
$$ Wang:(1,20000),(2,19998),(3,19994) $$
$$ Li:(1,30001),(2,30006),(3,30015) $$
这里为了简单计算起见，选择了三个简单的点（太大的点我懒得按计算器）实际应用时应当选择更为复杂的参数
此时约定每个人x=1的点发送给我，x=2的点发送给小王，x=3的点发送给小李，对于我而言，我可以计算出一个点(1,10007+20000+30001)，同理，小王和小李分别得到(2,10020+19998+30006)和(3,10039+19994+30015)，此时根据这三个点可以计算出一条抛物线
$$ y=(a_1+a_2+a_3)x^2+(b_1+b_2+b_3)x+(c_1+c_2+c_3) $$
此时这条抛物线在y轴的截距就是三人的工资之和，再对其取平均值即可
首先再次强调，实际应用时应当选择更为复杂的参数
其次，需要注意的是，每个人都只得到了其他各个参与方的一个点，即便是小王和小李合谋算计我，他们也只能得到我选择的抛物线上的两个点，而由高中知识可以知道，过任意两点存在无数条抛物线，因此仅得到两个点仍然无法还原我所选择的抛物线，因此这个方案实际上不存在共谋的情况
安全计算发展
自1982年姚期智教授提出百万富翁问题以来，安全计算一直在不断地发展与完善，1987年提出了GMW协议，以共享的观点来实现安全计算，次年提出了BGW协议，是一个针对代数计算提出的共享思路协议，到了2004年，Fairplay协议提出，这是一个第一次实际执行的安全计算协议，2009年开始，出现了将安全计算商业化的公司（当时还在上小学的我，电脑中病毒都不知道怎么办的我）
直到今日，安全计算已经广泛应用在许多领域和应用场景，如物联网、互联网远程医疗、云存储、金融领域等，发展前景于潜力巨大
后记
由于安全计算和零知识协议都是这学期甚至最近一周才开始学的，不像之前发的无线网安全的那篇论文，主要是这篇论文设涉及的知识面比较宽，也比较深，想认真学一下，形成知识体系
虽然说还不确定以后会不会往这方面走，毕竟现在看论文仍然处于一个看懂且仅能看懂的阶段，还暂时不能再这些理论的基础上提出新的创新点，更别说安全性了，对于目前研究领域而言，并不了解具体的研究方向，也不知道能不能做下去
因此博客的初衷只是记录自己学习和思考的过程，并尝试把这方面理解且讲明白（尝试给有一个没有任何基础的人讲明白）
本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正
参考文章
$[1]$ 区块链(Blockchain) - 知乎 (zhihu.com)
$[2]$ 区块链为何对安全多方计算如此热情？ - 简书 (jianshu.com)
$[3]$ Shamir's Secret Sharing
$[4]$ Secret sharing
为随机函数--->伪随机函数
已修改，感谢指出错误