Paper 2018/096

Paralysis Proofs: Secure Access-Structure Updates for Cryptocurrencies and More

Fan Zhang, Philip Daian, Gabriel Kaptchuk, Iddo Bentov, Ian Miers, and Ari Juels


Conventional (M, N )-threshold signature schemes leave users with a painful choice. Setting M = N offers maximum resistance to key compromise. With this choice, though, loss of a single key renders the signing capability unavailable, creating paralysis in systems that use signatures for access control. Lower M improves availability, but at the expense of security. For example, (3, 3)-multisig wallet experiences access-control paralysis upon loss of a single key, but a (2, 3)-multisig allows any two players to collude and steal funds from the third. In this paper, we introduce techniques that address this impasse by making general cryptographic access structures dynamic. Our schemes permit, e.g., a (3, 3)-multisig, to be downgraded to a (2, 3)- multisig if a player goes missing. This downgrading is secure in the sense that it occurs only if a player is provably unavailable. Our main tool is what we call a Paralysis Proof, evidence that play- ers, i.e., key holders, are unavailable or incapacitated. Using Paraly- sis Proofs, we show how to construct a Dynamic Access Structure System, which can securely and flexibly update target access struc- tures without a trusted third party such as a system administrator. We present DASS constructions that combine a trust anchor (a trusted execution environment or smart contract) with a censorship- resistant channel in the form of a blockchain. We offer a formal framework for specifying DASS policies, and define and show how to achieve critical security and usability properties (safety, liveness, and paralysis-freeness) in a DASS. Paralysis Proofs can help address pervasive key-management chal- lenges in many different settings. We present DASS schemes for three important example use cases: recovery of cryptocurrency funds should players become unavailable, returning funds to users when cryptocurrency custodians fail, and remediating critical smart- contract failures such as frozen funds. We report on practical im- plementations for Bitcoin and Ethereum.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.ACM Advances in Financial Technologies (AFT) 2019
blockchainaccess structuretrusted hardwareIntel SGXBitcoin
Contact author(s)
fz84 @ cornell edu
2019-09-24: last of 9 revisions
2018-01-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fan Zhang and Philip Daian and Gabriel Kaptchuk and Iddo Bentov and Ian Miers and Ari Juels},
      title = {Paralysis Proofs: Secure Access-Structure Updates for Cryptocurrencies and More},
      howpublished = {Cryptology ePrint Archive, Paper 2018/096},
      year = {2018},
      doi = {10.1145/3318041.3355459},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.