Paper 2019/1264

Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era

Juan Garay, Aggelos Kiayias, Rafail Ostrovsky, Giorgos Panagiotakos, and Vassilis Zikas


Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private correlated-randomness setup, such as a PKI, protocols can tolerate up to $t<n/3$ of the parties being malicious. The introduction of ``Nakamoto style'' consensus, based on Proof-of-Work (PoW) blockchains, put forth a somewhat different flavor of BA, showing that even a majority of corrupted parties can be tolerated as long as the majority of the computation resources remain at honest hands. This assumption on honest majority of some resource was also extended to other resources such as stake, space, etc., upon which blockchains achieving Nakamoto-style consensus were built that violated the $t<n/3$ bound in terms of number of party corruptions. The above state of affairs begs the question of whether the seeming mismatch is due to different goals and models, or whether the resource-restricting paradigm can be generically used to circumvent the $n/3$ lower bound. In this work we study this question and formally demonstrate how the above paradigm changes the rules of the game in cryptographic definitions. First, we abstract the core properties that the resource-restricting paradigm offers by means of a functionality wrapper, in the UC framework, which when applied to a standard point-to-point network restricts the ability (of the adversary) to send new messages. We show that such a wrapped network can be implemented using the resource-restricting paradigm---concretely, using PoWs and honest majority of computing power---and that the traditional $t<n/3$ impossibility results fail when the parties have access to such a network. Our construction is in the {\em fresh} Common Reference String (CRS) model---i.e., it assumes a CRS which becomes available to the parties at the same time as to the adversary. We then present constructions for BA and MPC, which given access to such a network tolerate $t<n/2$ corruptions without assuming a private correlated randomness setup. We also show how to remove the freshness assumption from the CRS by leveraging the power of a random oracle. Our MPC protocol achieves the standard notion of MPC security, where parties might have dedicated roles, as is for example the case in Oblivious Transfer protocols. This is in contrast to existing solutions basing MPC on PoWs, which associate roles to pseudonyms but do not link these pseudonyms with the actual parties.

Available format(s)
Cryptographic protocols
Publication info
Published by the IACR in EUROCRYPT 2020
MPCbroadcastconsensusproof of workblockchain
Contact author(s)
juan a garay @ gmail com
akiayias @ inf ed ac uk
pagio91i @ gmail com
rafail @ cs ucla edu
vassilis zikas @ gmail com
2020-03-17: last of 4 revisions
2019-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juan Garay and Aggelos Kiayias and Rafail Ostrovsky and Giorgos Panagiotakos and Vassilis Zikas},
      title = {Resource-Restricted Cryptography: Revisiting MPC Bounds in the Proof-of-Work Era},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1264},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.