Tri-op redactable blockchains with block modification, removal, and insertion

In distributed computations and cryptography, it is desirable to record events on a public ledger, such that later alterations are computationally infeasible. An implementation of this idea is called blockchain, which is a distributed protocol that allows the creation of an immutable ledger. While such an idea is very appealing, the ledger may be contaminated with incorrect, illegal, or even dangerous data, and everyone running the blockchain protocol has no option but to store and propagate the unwanted data. The ledger is bloated over time, and it is not possible to remove redundant information. Finally, missing data cannot be inserted later. Redactable blockchains were invented to allow the ledger to be mutated in a controlled manner. To date, redactable blockchains support at most two types of redactions: block modification and removal. The next logical step is to support block insertions. However, we show that this seemingly innocuous enhancement renders all previous constructs insecure. We put forward a model for blockchains supporting all three redaction operations and construct a blockchain that is provably secure under this formal definition.

PDF

___

[1] Akkoyunlu EA, Ekanadham K, Huber RV. Some constraints and tradeoffs in the design of network communications. In: ACM 1975 Symposium on Operating Systems Principles; Austin, Texas, USA; 1975. pp. 67–74.
[2] Nakamoto S. Bitcoin: a peer-to-peer electronic cash system. White paper; 2008.
[3] Kolb J, AbdelBaky M, Katz RH, Culler DE. Core concepts, challenges, and future directions in blockchain: a centralized tutorial. ACM Computing Surveys 2020; 53 (1): 1–39. doi: 10.1145/3366370.
[4] Cachin C. Architecture of the hyperledger blockchain fabric. In: IBM 2016 Workshop on Distributed Cryptocurrencies and Consensus Ledgers; Chicago, IL, USA; 2016.
[5] Matzutt R, Hiller J, Henze M, Ziegeldorf JH, Müllmann D et al. A quantitative analysis of the impact of arbitrary blockchain content on Bitcoin. In: Springer 2018 Financial Cryptography and Data Security; Nieuwpoort, Curaçao; 2018. pp. 420–438.
[6] Ateniese G, Magri B, Venturi D, Andrade E. Redactable blockchain–or–rewriting history in bitcoin and friends. In: IEEE 2017 European Symposium on Security and Privacy; Paris, France; 2017. pp. 111–126.
[7] Derler D, Samelin K, Slamanig D, Striecks C. Fine-grained and controlled rewriting in blockchains: chameleonhashing gone attribute-based. In: The Internet Society 2019 Network and Distributed System Security Symposium; San Diego, CA, USA; 2019. pp. 1–15.
[8] Dousti MS, Küpçü A. Moderated redactable blockchains: a definitional framework with an efficient construct. In: Springer 2020 Data Privacy Management, Cryptocurrencies and Blockchain Technology; Guildford, UK; 2020. pp. 355–373.
[9] Grigoriev D, Shpilrain V. RSA and redactable blockchains. International Journal of Computer Mathematics: Computer Systems Theory 2021; 6 (1): 1–6. doi: 10.1080/23799927.2020.1842808.
[10] Puddu I, Dmitrienko A, Capkun S. µchain: how to forget without hard forks. Cryptology ePrint Archive, 2017.
[11] Deuber D, Magri B, Thyagarajan SAK. Redactable blockchain in the permissionless setting. In: IEEE 2019 Symposium on Security and Privacy; San Francisco, CA, USA; 2019. pp. 124–138.
[12] Liu JK, Au MH, Susilo W, Zhou J. Short generic transformation to strongly unforgeable signature in the standard model. In: Springer 2010 European Symposium on Research in Computer Security; Athens, Greece; 2010. pp. 168–181.
[13] Rompel J. One-way functions are necessary and sufficient for secure signatures. In: ACM 1990 Symposium on Theory of Computing; Baltimore, MD, USA; 1990. pp. 387–394.
[14] Boneh D, Shen E, Waters B. Strongly unforgeable signatures based on computational Diffie–Hellman. In: Springer 2006 Public Key Cryptography; New York, NY, USA; 2006. pp. 229–240.
[15] Pass R, Shi E. FruitChains: a fair blockchain. In: ACM 2017 Symposium on Principles of Distributed Computing; Washington, DC, USA; 2017. pp. 315–324.