一个CM通信gydF4y2Ba

研究突出了gydF4y2Ba

比特币上的安全多方计算gydF4y2Ba

文/ Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski， Łukasz MazurekgydF4y2Ba
ACM通信，2016年4月，第59卷第4期，第76-84页gydF4y2Ba
10.1145 / 2896386gydF4y2Ba
评论gydF4y2Ba

有没有可能以一种完全去中心化的方式，也就是说，不依赖于可信任的第三方，设计一个在线彩票协议?或者，是否可以为出售秘密信息构建一个完全去中心化的协议，使卖方和买方都不能在其中欺骗?直到最近，似乎每个对参与者产生经济影响的在线协议都需要依赖某种可信任的服务器，以确保资金在参与者之间转移。在这项工作中，我们建议使用比特币(2008年推出的一种数字货币)来设计这种完全去中心化的协议，即使没有可信的第三方可用，它也是安全的。作为这个想法的一个实例，我们构建了使用比特币的安全多方彩票协议，而不依赖于可信任的权威。我们的协议保证诚实的一方公平，不管输家的行为如何。例如，如果一方中断了协议，那么她的钱就会转给诚实的参与者。我们的协议是实用的(为了证明这一点，我们在实际的比特币系统中执行了他们的交易)，原则上可以在现实生活中使用，作为在线赌博网站的替代品。gydF4y2Ba

回到顶部gydF4y2Ba

1.简介gydF4y2Ba

互联网最吸引人的特性之一是它的去中心化:TCP/IP协议本身，以及运行在它之上的其他几个协议不依赖于单个服务器，通常可以在不需要彼此信任，甚至不需要知道彼此真实身份的各方之间执行。此类协议的示例包括:SMTP和HTTP协议、对等内容分发平台、消息传递系统和许多其他协议。一个自然的问题是，数字世界的“去中心化”能走多远?换句话说，在不需要可信的第三方的情况下，可以在Internet上实现哪些实际应用程序?直到最近，一个似乎总是需要某种“可信服务器”的任务的显著例子是在线金融交易(必须依赖于银行或信用卡公司)。2009年，当第一种完全去中心化的数字货币比特币被中本聪使用时，这种情况发生了根本性的变化。gydF4y2Ba^{17gydF4y2Ba，gydF4y2Ba一个gydF4y2Ba}比特币的巨大成功(目前的市值约为50亿美元)正是由于它的分布式特性和缺乏控制比特币交易的中央机构。我们在第2节更详细地描述比特币。gydF4y2Ba

比特币转账可以在没有受信任的服务器的情况下完成，这一事实提出了另一个有趣的问题，即，我们能否进一步“去中心化”金融系统，即，我们能否以分布式的方式实现一些更先进的金融工具?比特币规范通过提供所谓的“非标准交易”部分回答了这个问题。我们将在第2节中更详细地描述这一特性，但暂时让我们只说比特币允许各方指定更复杂的条件，即何时可以花钱。这进而允许他们创建所谓的“比特币合约”，这是一种协议形式，其执行稍后由比特币系统本身强制执行(不需要可信的第三方)。此类合同的例子包括快速调整的小额支付、保证合同和纠纷调解gydF4y2Bahttps://en.bitcoin.it/wiki/ContractsgydF4y2Ba更多信息)。gydF4y2Ba

可能，可以数字化执行的最先进的多方协议类型之一是加密的“安全多方计算(MPC)”协议，它起源于Yao的开创性工作gydF4y2Ba^20.gydF4y2Ba和Goldreich等人。gydF4y2Ba^14gydF4y2Ba在非正式的情况下，这样的协议允许一组相互不信任的当事人计算一个联合函数gydF4y2BafgydF4y2Ba依靠他们的私人投入。例如，对于两方，Alice和Bob, Alice有一个输入gydF4y2BaxgydF4y2Ba， Bob有一个输入gydF4y2BaygydF4y2Ba他们都想学习gydF4y2BafgydF4y2Ba（gydF4y2BaxgydF4y2Ba，gydF4y2BaygydF4y2Ba)，但是爱丽丝没有学习gydF4y2BaygydF4y2Ba或鲍勃学习gydF4y2BaxgydF4y2Ba．在本文中，我们开始了使用比特币执行MPC协议的研究。gydF4y2Ba

得到了协议。gydF4y2Ba此类协议的一个非常简单的示例是gydF4y2Ba得到了问题gydF4y2Ba，gydF4y2Ba^6gydF4y2Ba由Alice和Bob双方执行，他们想共同计算一点gydF4y2BabgydF4y2Ba它同样可能是0或1。换句话说，他们想要计算一个随机函数gydF4y2BafgydF4y2Ba_rndgydF4y2Ba: {} ×{}{0,1}，它不接受输入和输出作为一致随机位。该协议可以使用类似于石头剪刀布游戏的想法来实现:Alice发送比特gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}发送给Bob，同时Bob发送一点gydF4y2BabgydF4y2Ba_BgydF4y2Ba爱丽丝。输出gydF4y2BabgydF4y2Ba是计算gydF4y2BabgydF4y2Ba：=gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}bgydF4y2Ba_BgydF4y2Ba(其中""表示gydF4y2BaxgydF4y2Ba或函数)。显然，如果至少有一个比特gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BabgydF4y2Ba_BgydF4y2Ba是均匀随机的吗gydF4y2BabgydF4y2Ba也是统一随机的，因此每一方都可以确保游戏是公平的，只要她行为诚实(也就是，统一地选择她的位置)。当一个人试图在因特网上实现这个协议时，当然，主要的挑战是确保Alice和Bob同时发送他们的位。这是因为如果一方，比如说爱丽丝，可以选择自己的立场gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}在她学习gydF4y2BabgydF4y2Ba_BgydF4y2Ba，然后她就可以做gydF4y2BabgydF4y2Ba等于任意值gydF4y2BabgydF4y2Ba她想要通过选择gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}：=gydF4y2BabgydF4y2BabgydF4y2Ba_BgydF4y2Ba．gydF4y2Ba

Blum中提出的解决方案gydF4y2Ba^6gydF4y2Ba是要用一种叫a的工具吗gydF4y2Ba加密方案的承诺。gydF4y2Ba在非正式的情况下，这样的方案是一个在a之间执行的双方协议gydF4y2Ba提交者gydF4y2Ba和一个gydF4y2Ba接收器。gydF4y2Ba在开始时，提交者知道一些值gydF4y2Ba年代gydF4y2Ba这是接收方的秘密。双方首先履行gydF4y2Ba承诺阶段gydF4y2Ba（gydF4y2Ba提交gydF4y2Ba)．在此阶段执行之后，接收方仍然不知道gydF4y2Ba年代gydF4y2Ba(此属性称为gydF4y2Ba隐藏gydF4y2Ba)．随后，双方执行开始阶段(gydF4y2Ba开放gydF4y2Ba)，在此过程中接收者学习gydF4y2Ba年代gydF4y2Ba．承诺方案的关键属性是提交者在承诺阶段之后不能“改变主意”。更准确地说，在执行第一个阶段之后，只存在一个值gydF4y2Ba年代gydF4y2Ba可以在第二阶段开放。这个属性叫做gydF4y2Ba绑定。gydF4y2Ba在某种意义上，承诺阶段类似于发送消息gydF4y2Ba年代gydF4y2Ba在一个上锁的盒子里，打开阶段可以被认为是把钥匙送到盒子里。显然，在发送盒子之后，提交者不能更改它的内容，但在获得密钥之前，接收方不知道盒子里面是什么。gydF4y2Ba

有几种构建此类承诺的安全方法。在本文中，我们使用的是基于加密哈希函数的函数(参见第3节)。gydF4y2Ba

现在很容易看出承诺方案是如何用来解决抛硬币问题的:而不是发送她的比特gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}直接提交给Bob, Alice就提交给它(也就是说，Alice和Bob执行承诺方案，Alice作为提交者，Bob作为接收者，并且gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}是秘密)。与此同时，鲍勃也投入了自己的工作gydF4y2BabgydF4y2Ba_BgydF4y2Ba．gydF4y2Ba在这个承诺阶段结束后，双方执行开放阶段并学习彼此的比特。然后计算输出为gydF4y2BabgydF4y2Ba＝gydF4y2BabgydF4y2Ba_{一个gydF4y2Ba}bgydF4y2Ba_BgydF4y2Ba．承诺方案的安全性保证了任何一方都不能根据另一方的比特选择自己的比特，因此该过程产生了一个一致随机比特。gydF4y2Ba

布尔操作。gydF4y2Ba上面抛硬币的例子是一个特别简单的多方协议案例，因为执行它的各方不接受任何输入。为了解释协议各方接受输入的含义，考虑一下Alice和Bob计算的函数是合取函数的情况gydF4y2BafgydF4y2Ba（gydF4y2Ba一个gydF4y2Ba，gydF4y2BabgydF4y2Ba) =gydF4y2Ba一个gydF4y2BabgydF4y2Ba,在那里gydF4y2Ba一个gydF4y2Ba，gydF4y2BabgydF4y2Ba{0,1}是布尔变量，分别表示Alice和Bob的输入。这有时被称为gydF4y2Ba求婚的问题gydF4y2Ba因为如果她/他想要和另一方结婚，就可以把双方的输入理解为一种宣言。更准确地说,假设gydF4y2Ba一个gydF4y2Ba= 1当且仅当Alice想嫁给Bob，且gydF4y2BabgydF4y2Ba= 1当且仅当Bob想娶Alice。在这种情况下gydF4y2BafgydF4y2Ba（gydF4y2Ba一个gydF4y2Ba，gydF4y2BabgydF4y2Ba= 1当且仅当gydF4y2Ba这两个gydF4y2Ba双方都想结婚，因此，举个例子，gydF4y2BabgydF4y2Ba= 0，那么Bob在知道函数的输出后没有关于Alice输入的信息。因此，Alice的隐私受到了保护。gydF4y2Ba

我们可以概括这个例子并考虑gydF4y2Baset-intersectiongydF4y2Ba问题。这里爱丽丝和鲍勃有一组gydF4y2Ba一个gydF4y2Ba而且gydF4y2BaBgydF4y2Ba因为它们的输入和输出等于gydF4y2BafgydF4y2Ba（gydF4y2Ba一个gydF4y2Ba，gydF4y2BaBgydF4y2Ba) =gydF4y2Ba一个gydF4y2BaBgydF4y2Ba．例如，想想gydF4y2Ba一个gydF4y2Ba而且gydF4y2BaBgydF4y2Ba作为Alice和Bob联系人列表中的电子邮件地址集，然后输出gydF4y2BafgydF4y2Ba（gydF4y2Ba一个gydF4y2Ba，gydF4y2BaBgydF4y2Ba)是他们共有的联系人列表。这里的安全性意味着:(1)双方对彼此输入的了解不会超过他们从自己的输入和输出中推断出的程度，(2)恶意的一方不能导致结果不正确(例如，一个腐败的Alice不能错误地使Bob认为某个电子邮件地址在她的联系人列表中)。对于本例，条件(1)意味着对于每个gydF4y2Ba一个gydF4y2Ba一个gydF4y2Ba， Alice将不会获得任何信息，如果gydF4y2Ba一个gydF4y2Ba是在gydF4y2BaBgydF4y2Ba(对鲍勃也是对称的)。gydF4y2Ba

一般的结果和缺乏“公平”。gydF4y2Ba上面的例子可以从几个方面加以概括。首先，可以考虑在两个以上的团体之间执行的协议(因此称为mpc，而不是gydF4y2Ba两个gydF4y2Ba方上面的例子)。例如，一个多方掷硬币协议被指定为完全相同的两方协议，除了参与者的数量大于2。gydF4y2Ba

第二，可以考虑比上面描述的更复杂的函数。Goldreich等人已经证明了这一点。gydF4y2Ba^14gydF4y2Ba对于任何可有效计算的函数gydF4y2BafgydF4y2Ba(包括掷硬币例子中的“随机”函数)，存在一种有效的协议可以安全地计算它，假设存在活板门排列(这是一个公认的假设，被广泛认为是成立的)。如果少数当事人是恶意的(即，不遵守协议)，那么协议总是终止的，并且每个诚实的参与者都知道输出。但是，如果超过一半的恶意方是恶意方，那么恶意方可以在学习输出后终止协议，阻止诚实方学习输出。注意，在两方协议的情况下，假设大多数参与者都是诚实的是没有意义的，因为这仅仅意味着没有参与者是恶意的。这个问题在上面抛硬币的例子中很明显，因为每一方都可以在了解对方的比特之后拒绝打开自己的承诺。在某些情况下，这不是问题，因为双方可以同意拒绝打开承诺等同于输掉游戏。gydF4y2Ba

然而，事实证明gydF4y2Ba^9gydF4y2Ba那一般这个问题，叫做缺乏gydF4y2Ba公平gydF4y2Ba,是不可避免的。因此，双方协议通常不能提供完全的公平性。gydF4y2Ba

为什么MPC没有在互联网上广泛使用?gydF4y2Ba自从mpc引入以来，人们为提高这些协议的效率付出了巨大的努力gydF4y2Ba^{4gydF4y2Ba，gydF4y2Ba10gydF4y2Ba，gydF4y2Ba16gydF4y2Ba}有时甚至在现实生活中使用它们，如在线拍卖。gydF4y2Ba^7gydF4y2Ba另一方面，也许令人惊讶的是，mpc并没有在许多其他领域得到应用，而这些领域似乎完全适合mpc。一个突出的例子是互联网赌博:有趣的是，目前互联网上的赌博几乎完全是在扮演“可信方”角色的网站的帮助下进行的，而不是使用加密的抛硬币协议来消除信任的需要。从安全的角度来看，这种情况显然是令人不满意的，特别是因为在过去，这些网站的经营者曾滥用他们的特权地位来谋取自己的经济利益。gydF4y2Ba^18gydF4y2Ba因此，看起来多党制技术消除了对受信任方的需求，将是传统赌博网站的完美替代品。另外一个好处是赌博的成本会降低，因为赌博网站通常会对他们的服务收费。gydF4y2Ba

在我们看来，mpc不被用于在线赌博至少有两个主要原因。第一个原因是，如果参与者中没有诚实的多数，多方协议就不能提供公平性。例如，考虑一个简单的基于掷硬币协议的两方彩票:双方首先计算一个随机比特gydF4y2BabgydF4y2Ba,如果gydF4y2BabgydF4y2Ba= 0，那么Alice支付1美元给Bob，如果gydF4y2BabgydF4y2Ba= 1，则Bob向Alice支付1美元，如果协议没有正确终止，则双方不向彼此支付任何钱。在这种情况下，恶意方(比如Alice)可以阻止Bob学习等于0的输出，使1成为协议唯一可能的输出。这意味着双方抛硬币在实践中并不安全。更一般地说，只有在大多数人都是诚实的情况下，多方抛硬币才会起作用，这在完全分布式的互联网环境中是不现实的假设，gydF4y2Ba西比尔gydF4y2Ba攻击gydF4y2Ba^11gydF4y2Ba允许恶意一方创建和控制多个“假”身份，轻松获得参与者中的“多数”。gydF4y2Ba

第二个原因更为根本，因为它直接来自MPC安全定义的固有限制:这样的协议只关心计算的安全，而不“负责”确保用户向协议提供“真正的”输入并尊重输出。gydF4y2Ba

例如，考虑一下求婚问题:很明显，没有技术方法可以确保用户诚实地向受信任的一方提供他们的输入。鲍勃说，没有什么能阻止一方在他的感受和设定上撒谎gydF4y2BabgydF4y2Ba= 1来学习Alice的输入gydF4y2Ba一个。gydF4y2Ba同样，强迫双方尊重协议的结果并结婚也不能以加密的方式保证。gydF4y2Ba

这个问题在赌博应用程序中尤其重要:即使在上面描述的最简单的“两方彩票”示例中，也不存在强制输家将钱转移给赢家的加密方法。gydF4y2Ba

对于这个问题，无论是在数字世界还是非数字世界，一个实用的解决方案是使用“声誉”的概念:被发现作弊的一方(例如，提供错误的输入或不尊重游戏结果)会损害她的声誉，并且下次可能很难找到另一方愿意与她赌博。已有几篇论文对声誉系统进行了构建和分析。gydF4y2Ba^19gydF4y2Ba然而，在许多应用程序中使用它们似乎太麻烦了，一个原因是如果允许用户随时选择新名称，那么如何定义新用户的声誉是不清楚的。gydF4y2Ba^12gydF4y2Ba

另一个选择是利用金融交易是通过电子方式进行的这一事实。可以尝试将最终的交易(将1美元从输家转移到赢家)“合并”到协议中，以这样一种方式，只有在交易已经执行时，双方才知道谁赢得了游戏。不幸的是，如何在现有电子现金系统的框架内做到这一点并不明显。显然，由于双方互不信任，我们不能接受获胜一方知道败者的信用卡号码或帐户密码的解决方案。一个可能的解决方案是设计一个多方协议，以一种安全的方式模拟同时访问参与者的所有在线账户，并以他们的名义执行电汇。即使理论上可行，这种解决方案在现实生活中也很难实现，特别是因为协议需要适应玩家使用的多个银行(并且需要在它们更改时进行更新)。gydF4y2Ba

这篇论文的主要贡献是引入了一个新的范式，我们称之为“比特币上的MPC协议”，它为上述两个问题提供了一个解决方案:缺乏公平性，以及缺乏“现实生活”和加密计算结果之间的联系。我们将在第1.1节中描述我们的解决方案。gydF4y2Ba

1.1.我们的贡献gydF4y2Ba

我们研究如何在比特币上进行“mpc”。首先，我们展示了比特币系统提供了一种有吸引力的方式来构建一个版本的“定时承诺”，gydF4y2Ba^{8gydF4y2Ba，gydF4y2Ba13gydF4y2Ba}报送人必须在一定期限内披露秘密，否则必须缴纳罚款的。反过来，这又可用于在某些多方协议中获得公平性。因此，它可以被视为“比特币在mpc上的应用”。gydF4y2Ba

可能更有趣的是我们的第二个想法，它在某种意义上通过展示“mpc对比特币的应用”与前一个相反，即我们引入了一个直接在比特币上工作的多方协议的概念。如上所述，mpc的标准定义只保证协议安全地执行计算，但确保输入是正确的和各方不中断协议执行超出了安全定义的范围。我们观察到，比特币系统可以被用来超越这个标准定义，通过构建连接输入和输出与真实比特币交易的协议。这是可能的，因为比特币缺乏一个中央权威，交易列表是公开的，它的语法允许更高级的交易，而不是简单地转移资金。gydF4y2Ba

作为这个想法的一个实例，我们构建了使用比特币的安全多方彩票协议，而不依赖于可信任的权威。所谓“抽签”，我们指的是一种协议，其中一组参与者最初投资一些钱，最后，随机选出的其中一个获得所有投资的钱(称为抽签)gydF4y2Ba锅gydF4y2Ba)．我们的协议工作在纯粹的点对点环境中，可以在匿名和互不信任的玩家之间执行。我们的建设有一个非常强大的安全保障:无论不诚实的人怎么做，诚实的人永远不会受骗。更准确地说，每一个诚实的一方都可以确信，一旦游戏开始，它总是会终止，并且是公平的。gydF4y2Ba

我们的主要结构将在第4节中介绍。它的安全性是通过gydF4y2Ba存款gydF4y2Ba:每个用户需要先存入一定数额的资金，当用户诚实地完成协议后，这些资金将返还给用户。否则，保证金将支付给其他方，并“补偿”他们过早终止游戏的事实。该协议使用上面描述的定时承诺方案。该协议的一个缺点是押金需要相当大，特别是当协议在更大的玩家群体中执行时。更准确地说，为了实现安全，每个玩家的存款都需要gydF4y2BaNgydF4y2Ba（gydF4y2BaNgydF4y2Ba1)乘以赌注的大小，其中gydF4y2BaNgydF4y2Ba是玩家的数量。对于双方的情况，这仅仅意味着保证金是赌注的两倍。gydF4y2Ba

在我们的协议中，参与者需要支付的唯一成本是比特币交易费用。目前大多数比特币交易都是免费的。然而，我们协议的参与者需要进行少量的非标准交易(所谓的“奇怪交易”，见第2节)，通常会有少量的费用(目前在0.0001左右)gydF4y2Ba0.04美元)。gydF4y2Ba^bgydF4y2Ba为了保持说明的简单性，我们假设费用为零。为了简单起见，我们还假设彩票中的投注数等于1gydF4y2Ba．应该很容易看出如何将我们的协议推广到投注的其他值。gydF4y2Ba

我们的构造基于上面解释的抛硬币协议。我们设法使这个协议适应我们的模型，而不需要修改当前的比特币系统。我们不使用像MPC或零知识编译器这样的通用方法，因此我们的协议非常高效。我们使用的唯一加密原语是使用哈希函数实现的承诺方案(这是标准比特币原语)。我们的协议强烈地依赖于比特币的高级特性(特别是所谓的“交易脚本”和“时间锁”)。由于篇幅有限，我们只概述了正式的安全性定义。我们用真正的比特币进行交易。我们提供了这些交易的描述，并在比特币区块链中引用它们。gydF4y2Ba^cgydF4y2Ba

1.2.独立及后续工作gydF4y2Ba

使用比特币来创建安全、公平的两人抽奖是由Back和Bentov独立提出的。gydF4y2Ba^3.gydF4y2Ba在本文的扩展版本中，我们对他们的协议和我们的协议进行了详细的比较。gydF4y2Ba

在随后的工作中，gydF4y2Ba^{1gydF4y2Ba，gydF4y2Ba2gydF4y2Ba}我们将展示如何扩展本文中的思想，为任何功能构建一个公平的双方协议，从而使该协议的执行具有“财务后果”。更准确地说，在第一篇论文中，gydF4y2Ba^1gydF4y2Ba我们展示了如何在假设比特币交易不可延展性的前提下解决这个问题(见Andrychowicz等人)。gydF4y2Ba^{1gydF4y2Ba，gydF4y2Ba2gydF4y2Ba}在Andrychowicz等人的著作中，gydF4y2Ba^2gydF4y2Ba我们展示了如何修改Andrychowicz等人的协议。gydF4y2Ba^1gydF4y2Ba以获得当前版本比特币中安全的协议。Bentov和Kumaresan独立开发了一些在多方协议中获得公平的替代想法。gydF4y2Ba^{5gydF4y2Ba，gydF4y2Ba15gydF4y2Ba}

1.3.应用及未来工作gydF4y2Ba

尽管如本文扩展版所述，在实践中使用我们的协议实际上可能具有经济意义，但我们主要将赌博视为引入“比特币上的mpc”概念的一个激励例子，并希望它有其他应用。使用我们的技术可以实现的一个任务示例是一个为比特币出售秘密信息的协议。假设Alice和Bob知道一个集合的描述gydF4y2BaXgydF4y2Ba包含一些有价值的信息。例如,gydF4y2BaXgydF4y2Ba可能包含一些难以找到的敏感数据(例如:由某个公共机构的秘密密钥签名的个人数据)。爱丽丝知道某个子集gydF4y2Ba一个gydF4y2Ba的gydF4y2BaXgydF4y2Ba鲍勃认识一个子集gydF4y2BaBgydF4y2Ba的gydF4y2BaXgydF4y2Ba．他们的目标是互相推销gydF4y2Ba一个gydF4y2BaBgydF4y2Ba以这样一种方式，他们只会为他们事先不知道的元素向对方付费。换句话说，Alice将支付给Bob (|gydF4y2BaBgydF4y2Ba＼gydF4y2Ba一个gydF4y2Ba| |gydF4y2Ba一个gydF4y2Ba＼gydF4y2BaBgydF4y2Ba|)gydF4y2Ba（如果这个值是负数，那么Bob将把它的负数支付给Alice)。没有MPC技术，就不清楚如何做到这一点:每当Alice向Bob透露某些元素时gydF4y2Ba一个gydF4y2Ba一个gydF4y2Ba鲍勃总是可以声称他已经知道了gydF4y2Ba一个gydF4y2Ba．此外，即使使用MPC技术，Alice也无法强迫Bob支付她的钱(反之亦然)。我们的工具(在1.2节中提到的后续论文中开发的)解决了这个问题:我们可以设计一个协议来传输精确的比特币数量，而且，这是当且仅当双方都真正了解了计算的输出时才会发生的!gydF4y2Ba

上面的例子可以用几种不同的方法进行推广。例如，输出只能发送给一方(比如:Alice)，而Alice愿意支付的信息的条件可能要复杂得多。例如，Alice可以是一个具有特殊秘密功能的情报机构gydF4y2BaggydF4y2Ba它指定给定信息(对于某些输入集)的值gydF4y2BaggydF4y2Ba甚至可以输出0)。然后鲍勃可以试着“出售”他的信息gydF4y2BaxgydF4y2Ba爱丽丝设置了一个极小值gydF4y2BavgydF4y2Ba他认为这是值得的。协议会计算gydF4y2BaggydF4y2Ba（gydF4y2BaxgydF4y2Ba)，并检查gydF4y2BaggydF4y2Ba（gydF4y2BaxgydF4y2Ba）gydF4y2BavgydF4y2Ba如果是，爱丽丝就会学习gydF4y2BaxgydF4y2Ba并支付gydF4y2BavgydF4y2Ba否则Alice将什么也学不到(Bob将赚到0)。gydF4y2Ba

最后，让我们指出，我们的协议可能被用于恶意目的。例如，考虑一种勒索软件，它加密受害者机器的硬盘，并承诺只有在受害者支付赎金时才提供解密密钥。目前，这类恶意程序无法证明，如果支付了赎金，它们真的会发送正确的密钥。使用我们的技术，可以保证密钥的安全交付(在某种意义上，只有在密钥真正解密磁盘时才会发生支付)。另一个潜在的风险是对在线投票计划的攻击:众所周知，如果这些计划没有收据，那么对手就可以购买选票。我们的技术可以使这种攻击更容易，因为它们消除了投票卖家信任投票买家的需要。gydF4y2Ba

回到顶部gydF4y2Ba

2.比特币的简短描述gydF4y2Ba

比特币gydF4y2Ba^17gydF4y2Ba作为点对点网络工作，其中参与者共同模拟控制事务正确性的中央服务器。在这个意义上，它类似于MPC协议的概念。回想一下，如上所述，传统mpc的一个基本问题是，如果参与者中没有诚实的多数，它们就不能提供公平性，这在可能发生sybil攻击的点对点网络中尤其难以保证。比特币系统通过以下方式克服了这个问题:诚实的大多数被定义为“大多数计算能力”。换句话说，为了破坏系统，对手需要控制计算机，其总计算能力与协议所有其他参与者的计算能力之和相当。因此，例如，sybil攻击不起作用，因为在网络中创建大量假身份对对手没有帮助。稍后我们将解释这是如何实现的，但让我们先描述用户模拟的受信任方的功能。gydF4y2Ba

数字货币的一个主要问题是潜在的重复消费:如果硬币只是一串比特，那么硬币的所有者可以多次消费它。显然，如果用户能够访问包含所有交易列表的受信任分类帐，则可以避免这种风险。在这种情况下，一笔交易只有被记录在分类账上才被认为是有效的。例如，假设事务的形式是:“用户a传输gydF4y2BaxgydF4y2Ba比特币给用户b "在这种情况下，每个用户都可以验证A是否真的有gydF4y2BaxgydF4y2Ba比特币(也就是说，她在之前的一些交易中收到了比特币)，但她还没有花出去。比特币网络所模拟的受信任方的功能恰恰做到了这一点:它维护系统中发生的交易的完整列表。比特币交易的格式实际上比上面的例子要复杂得多。由于我们对它特别感兴趣，我们将在第2.1节中更详细地描述它。然而，为了简单起见，我们省略了比特币的一些与我们的工作无关的特征，如交易费用或比特币的创建方式。gydF4y2Ba

比特币账簿实际上是一个链gydF4y2Ba块gydF4y2Ba(每个块包含事务)，所有参与者都试图扩展它。系统的参数以这样一种方式进行选择，即平均每10分钟发生一次扩展。区块链的思想是最长的链gydF4y2BaCgydF4y2Ba被接受为正确的一个，并且向链中添加一个新块需要进行非平凡的计算。由于扩展区块链或创建一个新的区块链非常困难，所有用户将使用相同的原始区块链。更详细地说，这种结构可以防止事务的重复花费。如果一个事务包含在一个块中gydF4y2BaBgydF4y2Ba_我gydF4y2Ba而且在它之后还有几个新的区块，那么对于一个计算能力不到比特币网络总计算能力一半的对手来说，要恢复是不可能的，因为它必须挖出一个新的区块gydF4y2BaCgydF4y2Ba分叉的gydF4y2BaCgydF4y2Ba在块gydF4y2BaBgydF4y2Ba_{我gydF4y2Ba1gydF4y2Ba}(或更早)gydF4y2BaCgydF4y2Ba应该比gydF4y2BaCgydF4y2Ba．难度会随着新方块的数量呈指数增长gydF4y2BaBgydF4y2Ba_我gydF4y2Ba．在实践中，事务需要1020分钟来进行合理的强确认，需要60分钟(6块)来几乎绝对确定它们是不可逆的。gydF4y2Ba

综上所述，当用户想用比特币支付某人时，他创建了一个交易，并将其广播到网络中的其他节点。他们验证这个事务，进一步发送它，并将它添加到他们正在挖掘的块中。当某个节点解决了挖掘问题，它向网络广播它的块。节点获得一个新块，验证其中的事务及其散列，并通过在其上挖掘来接受它。事务在块中的存在是对该事务的确认，但有些用户可能会选择等待几个块来获得更多的保证。在我们的协议中，我们假设存在一个最大延迟gydF4y2BaTgydF4y2Ba_{马克斯gydF4y2Ba}广播交易和交易确认之间的关系每一笔交易一旦确认就是不可逆转的。gydF4y2Ba

2.1.比特币交易gydF4y2Ba

与传统的银行系统相比，比特币的基础是gydF4y2Ba交易gydF4y2Ba而不是gydF4y2Ba账户。gydF4y2Ba一个用户gydF4y2Ba一个gydF4y2Ba他有一些比特币，如果在系统中有未赎回的交易，他是接收人。每笔交易都有一定的价值(正在传输的比特币数量)和一个收件人gydF4y2Ba地址。gydF4y2Ba地址只是一个公钥gydF4y2BapkgydF4y2Ba．通常，每个这样的密钥都有相应的私钥gydF4y2BaskgydF4y2Ba只有一个用户知道该用户是该地址的所有者gydF4y2BapkgydF4y2Ba．私钥用于对事务进行签名(授权)，公钥用于验证签名。系统的每个用户都需要知道某个地址的至少一个私钥，但这很容易实现，因为对(gydF4y2BaskgydF4y2Ba，gydF4y2BapkgydF4y2Ba)可以很容易地离线生成。我们经常用大写字母表示键对(例如，gydF4y2Ba一个gydF4y2Ba的私钥和公钥gydF4y2Ba一个gydF4y2Ba通过gydF4y2BaA.skgydF4y2Ba而且gydF4y2BaA.pkgydF4y2Ba,分别。gydF4y2Ba

简化版本。gydF4y2Ba我们首先描述一个简化版的比特币，然后展示如何扩展它以获得真实比特币的描述。让(gydF4y2BaA.sk, A.pkgydF4y2Ba)和(gydF4y2BaB.sk, B.pkgydF4y2Ba)是属于用户的密钥对gydF4y2Ba一个gydF4y2Ba而且gydF4y2BaBgydF4y2Ba,分别。在我们的简化视图中，一笔交易描述了一笔金额gydF4y2BavgydF4y2Ba(称为gydF4y2Ba价值gydF4y2Ba)从一个地址转移过来gydF4y2BaA.pkgydF4y2Ba到一个地址gydF4y2BaB.pkgydF4y2Ba的形式gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba，gydF4y2BavgydF4y2Ba，gydF4y2BaB.pkgydF4y2Basig),gydF4y2BaygydF4y2Ba是以前事务的索引吗gydF4y2BaTgydF4y2Ba_ygydF4y2Ba， sig是使用发送方的密钥计算的签名gydF4y2BaA.skgydF4y2Ba整个交易，不包括签名本身(即在(gydF4y2BaygydF4y2Ba，gydF4y2BavgydF4y2Ba，gydF4y2BaB.pkgydF4y2Ba))。我们说gydF4y2BaB.pkgydF4y2Ba是gydF4y2BaTgydF4y2Ba_xgydF4y2Ba这就是交易gydF4y2BaTgydF4y2Ba_ygydF4y2Ba是一个gydF4y2Ba输入gydF4y2Ba交易的gydF4y2BaTgydF4y2Ba_xgydF4y2Ba,或者gydF4y2BaTgydF4y2Ba_ygydF4y2Ba是gydF4y2Ba救赎gydF4y2Ba通过gydF4y2BaTgydF4y2Ba_xgydF4y2Ba．更准确地说，是指gydF4y2BaTgydF4y2Ba_xgydF4y2Ba是这个金额吗?gydF4y2BavgydF4y2Ba资金转移到gydF4y2BaA.pkgydF4y2Ba在事务gydF4y2BaTgydF4y2Ba_ygydF4y2Ba被进一步转移到gydF4y2BaB.pkgydF4y2Ba．事务gydF4y2BaTgydF4y2Ba_xgydF4y2Ba仅当(1)时有效gydF4y2BaA.pkgydF4y2Ba是交易的接收者吗gydF4y2BaTgydF4y2Ba_ygydF4y2Ba，(2)的值gydF4y2BaTgydF4y2Ba_ygydF4y2Ba等于gydF4y2BavgydF4y2Ba(3)交易gydF4y2BaTgydF4y2Ba_ygydF4y2Ba未提前兑换，且(4)gydF4y2Ba一个gydF4y2Ba是正确的。所有这些条件都可以公开核实。gydF4y2Ba

我们将把事务显示为方框。交易的兑换将用带有交易价值的箭头表示。例如，事务gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2Bay, v, B.pkgydF4y2Ba， sig)，传输gydF4y2BavgydF4y2Ba比特币的gydF4y2Ba一个gydF4y2Ba来gydF4y2BaBgydF4y2Ba，描述于gydF4y2Ba图1 (a)gydF4y2Ba．gydF4y2Ba

这个简化系统的第一个重要概括是，一个交易可以有多个“输入”，这意味着它可以从多个过去的交易中积累资金gydF4y2BaTgydF4y2Ba_{ygydF4y2Ba1gydF4y2Ba}、……gydF4y2BaTgydF4y2Ba_{yl型gydF4y2Ba}．gydF4y2Ba让gydF4y2Ba一个gydF4y2Ba_1gydF4y2Ba、……gydF4y2Ba一个gydF4y2Ba_lgydF4y2Ba是这些事务的接收者各自的密钥对。那么多输入事务有以下形式:gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba_1gydF4y2Ba、……gydF4y2BaygydF4y2Ba_lgydF4y2Bav, B.pkgydF4y2Ba，gydF4y2Ba团体gydF4y2Ba_1gydF4y2Ba、……gydF4y2Ba团体gydF4y2Ba_lgydF4y2Ba),每个gydF4y2Ba团体gydF4y2Ba_我gydF4y2Ba签名是用密钥计算的吗gydF4y2Ba一个gydF4y2Ba_我gydF4y2Ba.skgydF4y2Ba不包括签名的信息。这种交易的结果是gydF4y2BaB.pkgydF4y2Ba得到了数量gydF4y2BavgydF4y2Ba，只要它等于交易的价值之和gydF4y2BaTgydF4y2Ba_{ygydF4y2Ba1gydF4y2Ba}、……gydF4y2BaTgydF4y2Ba_{yl型gydF4y2Ba}．这只发生在gydF4y2Ba没有一个gydF4y2Ba这些交易中有一部分之前被赎回过，而且gydF4y2Ba所有gydF4y2Ba签名是有效的。每个事务也可以有几个输出，这是在几个用户之间分配钱或获得零钱的一种方法，但我们在协议中没有使用这个特性。gydF4y2Ba

一个更详细的版本。gydF4y2Ba真正的比特币系统要比上面描述的复杂得多。首先，有一些语法差异，对我们来说最重要的是每个事务gydF4y2BaTgydF4y2Ba_xgydF4y2Ba不是通过它的索引，而是通过整个事务的散列来标识，gydF4y2BaHgydF4y2Ba（gydF4y2BaTgydF4y2Ba_xgydF4y2Ba)．因此，从现在开始，我们将假设gydF4y2BaxgydF4y2Ba＝gydF4y2BaHgydF4y2Ba（gydF4y2BaTgydF4y2Ba_xgydF4y2Ba)．此外，每个事务可以有一个gydF4y2Ba时间同步tgydF4y2Ba它告诉事务何时生效。在本例中，我们有:gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba_1gydF4y2Ba、……gydF4y2BaygydF4y2Ba_lgydF4y2Bav, b.p pk, tgydF4y2Ba，gydF4y2Ba团体gydF4y2Ba_1gydF4y2Ba、……gydF4y2Ba团体gydF4y2Ba_lgydF4y2Ba)．这样的事务只有在时间gydF4y2BatgydF4y2Ba达到且满足前面提到的所有条件。之前的时间gydF4y2BatgydF4y2Ba,事务gydF4y2BaTgydF4y2Ba_xgydF4y2Ba不能使用(它将不包含在时间之前的任何块。gydF4y2BatgydF4y2Ba)．gydF4y2Ba

然而，主要的区别是，在真正的比特币中，用户在定义如何兑换交易的条件方面有更大的灵活性。考虑一下最简单的事务，其中只有一个输入，没有时间锁。回想一下，在上面描述的简化系统中，为了兑换交易，接收者gydF4y2BaA.pkgydF4y2Ba必须进行另一笔交易gydF4y2BaTgydF4y2Ba_xgydF4y2Ba用他的私钥签名gydF4y2BaA.sk。gydF4y2Ba在真实的比特币中，这可以概括为:每笔交易gydF4y2BaTgydF4y2Ba_ygydF4y2Ba附带一个函数(称为gydF4y2Ba输出脚本gydF4y2Ba）gydF4y2Ba_ygydF4y2Ba它的输出是布尔值。事务gydF4y2BaTgydF4y2Ba_xgydF4y2Ba补偿事务gydF4y2BaTgydF4y2Ba_ygydF4y2Ba是有效的,如果gydF4y2Ba_ygydF4y2Ba输入时求值为truegydF4y2BaTgydF4y2Ba_xgydF4y2Ba．在标准交易中，gydF4y2Ba_ygydF4y2Ba是处理的函数吗gydF4y2BaTgydF4y2Ba_xgydF4y2Ba作为一对(消息)gydF4y2Ba米gydF4y2Ba_xgydF4y2Ba,一个签名gydF4y2Ba_xgydF4y2Ba)并检查gydF4y2Ba_xgydF4y2Ba是否有有效的签名gydF4y2Ba米gydF4y2Ba_xgydF4y2Ba对于公钥gydF4y2BaA.pkgydF4y2Ba．然而，更通用的功能gydF4y2Ba_ygydF4y2Ba是有可能的。进一步了解细节，事务如下所示:gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba，gydF4y2Ba_xgydF4y2Bav,gydF4y2Ba_xgydF4y2Ba), (gydF4y2BaTgydF4y2Ba_xgydF4y2Ba) = (gydF4y2BaygydF4y2Ba，gydF4y2Ba_xgydF4y2Ba, vgydF4y2Ba)称为gydF4y2Ba身体gydF4y2Ba的gydF4y2BaTgydF4y2Ba_xgydF4y2Ba而且gydF4y2Ba_xgydF4y2Ba是一个gydF4y2Ba输入脚本gydF4y2Ba用来制作剧本的证人gydF4y2Ba_ygydF4y2Ba求值为truegydF4y2BaTgydF4y2Ba_xgydF4y2Ba(在标准事务gydF4y2Ba_xgydF4y2Ba是发件人在[上的签名gydF4y2BaTgydF4y2Ba_xgydF4y2Ba])。这些脚本是用比特币脚本语言编写的，这是一种基于堆栈的语言，而不是图灵完备语言(其中没有循环)。它提供了对数字的基本算术操作、对堆栈的操作、if-then-else语句和一些加密函数，如计算哈希函数或验证签名。对带时间锁的多输入事务的概括很简单:事务具有这样的形式gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba_1gydF4y2Ba、……gydF4y2BaygydF4y2Ba_lgydF4y2Ba，gydF4y2Ba_xgydF4y2Ba, v, t,gydF4y2Ba_1gydF4y2Ba、……gydF4y2Ba_lgydF4y2Ba)，其中体[gydF4y2BaTgydF4y2Ba_xgydF4y2Ba等于(ygydF4y2Ba_1gydF4y2Ba、……gydF4y2BaygydF4y2Ba_lgydF4y2Ba，gydF4y2Ba_xgydF4y2Ba, v, tgydF4y2Ba)，当(1)时间时有效gydF4y2BatgydF4y2Ba, (2)gydF4y2Ba每一个gydF4y2Ba_我gydF4y2Ba([gydF4y2BaTgydF4y2Ba_xgydF4y2Ba),gydF4y2Ba_我gydF4y2Ba)的值为true，其中每个gydF4y2Ba_我gydF4y2Ba．gydF4y2Ba是事务的输出脚本吗gydF4y2BaTgydF4y2Ba_易gydF4y2Ba(3)这些交易之前都没有被赎回过，(4)交易的价值之和gydF4y2BaTgydF4y2Ba_易gydF4y2Ba等于gydF4y2BavgydF4y2Ba．gydF4y2Ba

一个有两个输入的一般事务的框表示，gydF4y2BaTgydF4y2Ba_xgydF4y2Ba= (gydF4y2BaygydF4y2Ba_1gydF4y2Ba，gydF4y2BaygydF4y2Ba_2gydF4y2Ba，gydF4y2Ba_xgydF4y2Ba, v, t,gydF4y2Ba_1gydF4y2Ba，gydF4y2Ba_2gydF4y2Ba)，见gydF4y2Ba图1 (b)gydF4y2Ba．gydF4y2Ba

最常见的事务类型是没有时间锁或任何特殊脚本的事务:输入脚本是签名，输出脚本是签名验证算法。我们会叫它们gydF4y2Ba标准交易gydF4y2Ba，进行核实的地址称为gydF4y2Ba收件人gydF4y2Ba一个事务。目前，一些矿工只接受标准交易(尽管根据比特币的描述，非标准交易也是正确的)。我们相信，在未来，接受非标准交易将变得普遍。这对我们的应用程序很重要，因为我们的协议严重依赖于非标准事务。gydF4y2Ba

回到顶部gydF4y2Ba

3.基于比特币的定时承诺方案gydF4y2Ba

我们首先构建一个基于比特币的时间承诺方案。第1节已经介绍了承付计划。实现承诺的一种简单方法是使用加密哈希函数gydF4y2BaHgydF4y2Ba．保密:对一个秘密负责gydF4y2Ba年代gydF4y2Ba{0,1}*，提交者选择一个随机字符串gydF4y2BargydF4y2Ba{0,1}gydF4y2Ba^128gydF4y2Ba并发送到接收端gydF4y2BacgydF4y2Ba＝gydF4y2BaHgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba||gydF4y2BargydF4y2Ba)(其中"||"表示连接)。要打开承诺，提交者发送(gydF4y2Ba年代gydF4y2Ba，gydF4y2BaxgydF4y2Ba)，接收端进行验证gydF4y2BaHgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba||gydF4y2BaxgydF4y2Ba) =gydF4y2BacgydF4y2Ba．gydF4y2Ba

尽管在许多应用程序中非常有用，但标准承诺方案存在以下问题(在引言中已经描述过):没有办法强迫提交者透露他的秘密gydF4y2Ba年代gydF4y2Ba，特别是，如果他在gydF4y2Ba开放gydF4y2Ba阶段开始,然后gydF4y2Ba年代gydF4y2Ba仍是秘密。比特币为解决这个问题提供了一种有吸引力的方式。也就是说，使用比特币系统，可以迫使提交者用一些钱来支持他的承诺，称为gydF4y2Ba存款gydF4y2Ba，如果收信人在一段时间内拒绝打开承诺，收信人就会收到gydF4y2BatgydF4y2Ba双方同意。更准确地说，在承诺阶段，提交者用比特币进行存款。如果他在规定期限前开立保函，他就可以拿回这笔存款gydF4y2Bat。gydF4y2Ba否则，该保证金将自动支付给收件人。gydF4y2Ba

3.1.建设gydF4y2Ba

我们构建的基于比特币的定时承诺方案(CS)将基于前面描述的简单承诺方案。比特币中使用的哈希函数是SHA256，在我们的协议中也使用它，因为它可以在比特币脚本语言中使用。但为了清楚起见，我们还是用gydF4y2BaHgydF4y2Ba在协议的描述中。此外，我们假设秘密已经填充了随机位，所以我们不会在描述中添加或删除它们。事实上，我们稍后将使用CS协议提交长随机字符串，因此在这种情况下填充是不必要的。gydF4y2Ba

我们协议的基本思想如下。在提交阶段，提交者创建一个事务gydF4y2Ba提交gydF4y2Ba有一些公认的价值gydF4y2BadgydF4y2Ba，作为押金。赎回存款的唯一方法是提交另一笔交易gydF4y2Ba开放gydF4y2Ba，这就揭示了秘密gydF4y2Ba年代。gydF4y2Ba事务gydF4y2Ba提交gydF4y2Ba以这样一种方式构造gydF4y2Ba开放gydF4y2Ba交易必须打开承诺，即揭示秘密价值gydF4y2Ba年代。gydF4y2Ba这意味着提交者的钱被“冻结”，直到他透露gydF4y2Ba年代。gydF4y2Ba如果提交人在一定时间内没有打开承诺，为了允许接收人索赔保证金，我们还要求提交人向接收人发送一个交易gydF4y2BaPayDepositgydF4y2Ba可以赎回gydF4y2Ba提交gydF4y2Ba如果时间gydF4y2BatgydF4y2Ba传球。gydF4y2Ba

从技术上讲，这是通过构造事务的输出脚本来完成的gydF4y2Ba提交gydF4y2Ba通过这种方式，赎回交易必须提供C的签名和秘密gydF4y2Ba年代gydF4y2Ba(因此，所有的交易都是公开可见的)或C和r的签名gydF4y2Ba提交gydF4y2Ba，提交者创建事务gydF4y2BaPayDepositgydF4y2Ba，它将存款发送给收件人，并具有时间锁gydF4y2Bat。gydF4y2Ba提交者签名并将其发送给接收方。在收到gydF4y2BaPayDepositgydF4y2Ba，收信人会检查邮件是否正确，并在上面加上自己的签名。在此之后，他可以确定提交者将在此之前打开其承诺gydF4y2BatgydF4y2Ba或者他可以使用这笔交易gydF4y2BaPayDepositgydF4y2Ba要求gydF4y2BadgydF4y2Ba存款。gydF4y2Ba

该协议中的事务图描述在gydF4y2Ba图1 (c)gydF4y2Ba．协议的完整描述可以在本文的扩展版本中找到。gydF4y2Ba

回到顶部gydF4y2Ba

4.彩票协议gydF4y2Ba

正如第1节所讨论的，作为“比特币上的mpc”概念的应用示例，我们为在Alice (a)和Bob (B)两方之间执行的彩票构建了一个协议。我们称协议为gydF4y2Ba公平的抽签协议gydF4y2Ba如果它是gydF4y2Ba正确的gydF4y2Ba而且gydF4y2Ba安全。gydF4y2Ba

为了定义正确性，假设双方都遵守协议，并且他们之间的通信通道是安全的(即，它在双方之间可靠地无延迟地传输消息)。我们还假设在协议开始之前，双方都有足够的资金来玩彩票，包括双方的赌注(为了简单起见，我们假设赌注等于1gydF4y2Ba）和存款，因为在协议中我们将使用第3节中的承诺方案。如果这些假设成立，一个正确的协议必须确保在协议结束时，以均匀概率选择的一方必须得到由两种赌注组成的全部赌注，而另一方则失去她的赌注。此外，双方都必须拿回自己的存款。gydF4y2Ba

要定义安全性，请从一方的角度来看协议的执行，假设A(另一方的情况是对称的)是诚实的。显然，A不能保证协议成功终止，因为另一方可以在协议完成之前离开协议。重要的是，A应该确保她不会因为终止协议而损失金钱，例如，不允许另一方在得知A赢了之后终止协议。这是形式化的如下:我们定义gydF4y2Ba回报的gydF4y2Ba协议执行时的A等于A投入的钱和协议执行后她拥有的钱之间的差。我们说协议是gydF4y2Ba安全gydF4y2Ba如果对手的任何策略控制了网络并腐化了一方，那么另一方，诚实的一方的预期收益就不是负的。我们也注意到，当然，一个不诚实的参与者总是可以在非常早期的阶段终止，当她不知道谁是赢家时，这并不改变诚实一方的回报。gydF4y2Ba

4.1.该协议gydF4y2Ba

我们的协议建立在Blum的经典掷硬币协议之上gydF4y2Ba^6gydF4y2Ba如第一节所述。正如前面提到的，这个协议不能直接用于我们的应用程序，因此我们需要使其适应比特币。特别是，在我们的解决方案中，创建和打开承诺是由事务脚本使用(双)SHA-256散列完成的。在选择一个随机位后gydF4y2BabgydF4y2Ba_pgydF4y2Ba,党gydF4y2BaPgydF4y2Ba{A, B}选择一个字符串gydF4y2Ba年代gydF4y2Ba_pgydF4y2Ba从{0,1}中均匀随机抽样gydF4y2Ba^{128 +gydF4y2Ba英国石油公司gydF4y2Ba}的值，即长度为128或129位的字符串集合gydF4y2BabgydF4y2Ba_pgydF4y2Ba．聚会，派对gydF4y2BaPgydF4y2Ba然后提交gydF4y2Ba年代gydF4y2Ba_PgydF4y2Ba使用定时承诺。获胜者是由gydF4y2Ba胜者选择函数fgydF4y2Ba，定义如下:gydF4y2Baf (sgydF4y2Ba_{一个gydF4y2Ba}，gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba= A if |gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}| = |gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba|和B，否则，其中gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba是当事人和|选择的秘密字符串吗gydF4y2Ba年代gydF4y2Ba_PgydF4y2Ba|gydF4y2Ba的长度gydF4y2Ba年代gydF4y2Ba_PgydF4y2Ba在碎片。很容易看出，只要有一方拿出自己的筹码gydF4y2BabgydF4y2Ba_PgydF4y2Ba均匀，则输出gydF4y2BafgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}，gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba)也是统一随机的(前提是双方只能选择字符串gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba长度为128或129)。gydF4y2Ba

第一次尝试。gydF4y2Ba我们首先给出协议的一个简单且不安全的构造，然后展示如何修改它以获得一个安全的方案。双方都向对方宣布自己的公钥。爱丽丝和鲍勃也随机抽取他们的秘密线索gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba(分别)，它们交换散列gydF4y2BahgydF4y2Ba_{一个gydF4y2Ba}＝gydF4y2BaHgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}),gydF4y2BahgydF4y2Ba_BgydF4y2Ba＝gydF4y2BaHgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba)．如果gydF4y2BahgydF4y2Ba_{一个gydF4y2Ba}＝gydF4y2BahgydF4y2Ba_BgydF4y2Ba，然后球员放弃协议。gydF4y2Ba^dgydF4y2Ba双方都广播他们的输入交易，并向另一方发送他们在区块链中出现的链接。如果在以后的任何时候gydF4y2BaPgydF4y2Ba{A, B}意识到另一方在欺骗，那么第一件事gydF4y2BaPgydF4y2Ba所要做的是“拿了钱就跑”，也就是说，发布一个交易来赎回输入交易。我们称之为“停止执行”。只要输入事务没有被其他事务赎回，这显然是可以完成的。在下一步中，其中一方构建一个事务gydF4y2Ba计算gydF4y2Ba定义如下:gydF4y2Ba

注意的主体gydF4y2Ba计算gydF4y2Ba可以从公开的信息中计算出来。因此，该构造可以按以下方式实现:第一个参与方，例如，Bob计算的主体gydF4y2Ba计算gydF4y2Ba然后把他的签名寄给爱丽丝。Alice计算主体，向其添加两个签名，并广播整个事务gydF4y2Ba计算。gydF4y2Ba

的输出脚本gydF4y2Ba计算gydF4y2Ba是很棘手的。让它的值为truegydF4y2Ba身体gydF4y2Ba，须提供当事人的签名作为“见证人”gydF4y2BaPgydF4y2Ba和字符串gydF4y2BaxgydF4y2Ba_{一个gydF4y2Ba}，gydF4y2BaxgydF4y2Ba_BgydF4y2Ba,在那里gydF4y2BaxgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaxgydF4y2Ba_BgydF4y2Ba是的前像吗gydF4y2BahgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BahgydF4y2Ba_BgydF4y2Ba(对gydF4y2BaHgydF4y2Ba)．的collision-resistancegydF4y2BaHgydF4y2Ba意味着gydF4y2BaxgydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BaxgydF4y2Ba_BgydF4y2Ba必须等于什么gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba(职责)。因此，只有在胜者选择函数的情况下才能满足gydF4y2BafgydF4y2Ba计算结果为gydF4y2BaPgydF4y2Ba在输入gydF4y2Ba(年代gydF4y2Ba_{一个gydF4y2Ba},年代gydF4y2Ba_BgydF4y2Ba)．因为只有党gydF4y2BaPgydF4y2Ba知道她的私钥，只有她以后可以提供一个签名，使输出脚本的值为true。gydF4y2Ba

之前gydF4y2Ba计算gydF4y2Ba出现在区块链上，每一方gydF4y2BaPgydF4y2Ba能否“改变她的想法”并赎回她的输入交易，从而完成交易gydF4y2Ba计算gydF4y2Ba无效的。就像我们之前说的，如果一方打断扔硬币的程序，我们是可以接受的，只要她自己决定要不要这么做gydF4y2Ba之前gydF4y2Ba她知道她输了。因此，Alice和Bob一直等到事务完成gydF4y2Ba计算gydF4y2Ba在他们进入决定获胜者的步骤之前就被确认了。最后一步很简单:Alice和Bob进行广播gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba,分别。现在:如果gydF4y2Baf (sgydF4y2Ba_{一个gydF4y2Ba},年代gydF4y2Ba_BgydF4y2Ba) = A，那么Alice就可以赎回交易gydF4y2Ba计算gydF4y2Ba在一个事务gydF4y2BaClaimMoneygydF4y2Ba_{一个gydF4y2Ba}构造成:gydF4y2Ba

另一方面，鲍勃不能赎回gydF4y2Ba计算gydF4y2Ba，作为条件gydF4y2BafgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba},年代gydF4y2Ba_BgydF4y2Ba) = B的值为false。对称:如果gydF4y2BafgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba},年代gydF4y2Ba_BgydF4y2Ba= B，那么只有Bob可以赎回gydF4y2Ba计算gydF4y2Ba通过一个类似的事务gydF4y2BaClaimMoneygydF4y2Ba_BgydF4y2Ba．gydF4y2Ba

这个协议显然是正确的。它看起来也很安全，因为它本质上与前面描述的Blum协议相同(使用哈希函数作为承诺方案)。不幸的是，它存在以下问题:无法保证当事人总是披露gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba．gydF4y2Ba特别是:一方，比如说鲍勃，可以拒绝发送gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba后gydF4y2Ba他知道他输了gydF4y2BafgydF4y2Ba（gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba},年代gydF4y2Ba_BgydF4y2Ba) = A).因为他的钱已经“没了”(他的输入交易已经在交易中赎回了gydF4y2Ba计算gydF4y2Ba)，他不会得到任何东西，但他这样做可能只是因为纯粹的肮脏。不幸的是，在一个纯粹的点对点环境中，没有“声誉”的概念，这样的行为可能发生，而且没有办法惩罚它。这正是我们需要使用第3节中基于比特币的承诺方案的原因。gydF4y2Ba

方案的安全版本。gydF4y2Ba背后的大意是gydF4y2BaSecureLotterygydF4y2Ba协议是，每一方首先提交其输入，使用基于比特币的时间承诺方案，而不是标准的承诺方案。回忆,gydF4y2BaCSgydF4y2Ba协议可以通过发送一个值打开gydF4y2Ba年代gydF4y2Ba，通过检查该开口来验证该开口gydF4y2Ba年代gydF4y2Ba是否需要长度(128或129)和哈希值gydF4y2BahgydF4y2Ba在提交阶段由提交者发送。爱丽丝执行gydF4y2BaCSgydF4y2Ba协议作为提交者，Bob作为接收者。让gydF4y2Ba年代gydF4y2Ba_{一个gydF4y2Ba}而且gydF4y2BahgydF4y2Ba_{一个gydF4y2Ba}是变量gydF4y2Ba年代gydF4y2Ba而且gydF4y2BahgydF4y2Ba这种方式创建。对称地，Bob执行gydF4y2BaCSgydF4y2Ba协议作为提交者，Alice作为接收者，对应的变量为gydF4y2Ba年代gydF4y2Ba_BgydF4y2Ba而且gydF4y2BahgydF4y2Ba_BgydF4y2Ba．gydF4y2Ba一旦两个承诺阶段都成功执行(回想一下，这包括接收每一方签署的gydF4y2BaPayDepositgydF4y2Ba事务)，双方继续进行下一个步骤，这与前面的步骤完全相同:首先，他们各自广播一个输入事务。一旦这些事务被确认，它们就会创建gydF4y2Ba计算gydF4y2Ba交易的方式和以前一样，一旦它出现在区块链上，他们就会打开承诺。唯一的区别是，因为他们用了gydF4y2BaCSgydF4y2Ba承诺方案，他们现在可以“惩罚”对方如果她没有打开她的承诺时间gydF4y2BatgydF4y2Ba并索取他们的押金。另一方面，每一个诚实的一方总是保证能拿回她的押金，因此她在协议开始时投资这笔钱不会有任何风险。该协议的事务图显示在gydF4y2Ba图2gydF4y2Ba．gydF4y2Ba

我们还需要评论参数的选择:gydF4y2BatgydF4y2Ba:存款对收款人有效的时间gydF4y2BadgydF4y2Ba:存款的价值。我们的协议每一轮包含四个“轮”交易，各方在进行下一轮交易之前等待这一轮交易的所有确认。因此，协议的正确执行总是在时间4·内终止gydF4y2BaTgydF4y2Ba_{马克斯gydF4y2Ba},在那里gydF4y2BaTgydF4y2Ba_{马克斯gydF4y2Ba}确认事务所需的最长时间。因为我们可以安全地设置gydF4y2BatgydF4y2Ba为协议的开始时间加上5·gydF4y2BaTgydF4y2Ba_{马克斯gydF4y2Ba}．gydF4y2Ba

的参数gydF4y2BadgydF4y2Ba应该选择这样一种方式，它将充分补偿每一方的事实，另一个玩家中止。这意味着，对于一个双人彩票，每个人都应该交相当于两个赌注的存款。这样，如果一方终止协议，那么另一方可能会失去价值1的赌注gydF4y2Ba，但她得到了价值2的押金gydF4y2Ba，因此作为协议执行的结果，她获得1gydF4y2Ba对她来说，没有比执行协议更糟糕的事情了。gydF4y2Ba

该协议的完整描述可以在本文的扩展版本中找到，我们还展示了如何将其推广到gydF4y2BaNgydF4y2Ba派对。在我们的多方解决方案中，每个玩家在存款中投入的总金额必须等于gydF4y2BaNgydF4y2Ba（gydF4y2BaNgydF4y2Ba1）gydF4y2Ba．在现实生活中，这可能对小群体来说是可行的gydF4y2BaNgydF4y2Ba= 2,3，但对较大的不适用。gydF4y2Ba

回到顶部gydF4y2Ba

致谢gydF4y2Ba

我们要感谢Iddo Bentov和Ranjit Kumaresan进行了富有成效的讨论，并指出了我们之前版本彩票的一个错误。我们也非常感谢大卫·瓦格纳仔细阅读了我们的论文并提出了一些有用的意见。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.gydF4y2Ba

---

没有发现记录gydF4y2Ba