Papers Link
Redactable Blockchain – or – Rewriting History in Bitcoin and Friends
Introduction
Category
- Problem Pattern: Less studied problem
- Idea Pattern: New FrameWork or Improvement
Motivation
Background
- The immutability of blockchain fits perfectly with the currency system but not appropriate for all new applications that are being envisaged for the blockchain.
- The ability to store arbitrary messages has already been abused that blockchain systems contain some improper content affecting the life of people forever.
- Bitcoin 2.0 applications require re-writable storage.
Literature Review
Bitcoin, the first prototype blockchain.
Chameleon hash function.
Anti-presistence: history independent data structure.
Research Niche
The immutability of blockchain fits perfectly with the currency system but not appropriate for all new applications that are being envisaged for the blockchain.
Work
Research Objectives
Propose a new design for redactable blockchain that integrated chameleon hash function and discuss some issues occurring in the redactable blockchain.
Insight
Chameleon hash function provide a trap-door that find collision-resistant efficiently. Thus integrating this function into blockchain can make a redactable one.
Research Summary
A framework to redact and compress the content of blocks in virtually any blockchain based technology as implementing a redactable blockchain requires only minor modifications to the current structure of the blocks.
Novelty
Contributions
- Propose a new design of a redactable blockchain which is compatible with all popular blockchain proposals.
- Improved chameleon hash function design.
- Implementation of redactable blockchain.
Key Concepts
Hash Function
A hash function is any function that can be used to map data of arbitrary size to data of a fixed size. A cryptographic hash function allows one to easily verify that some input data maps to a given hash value, but if the input data is unknown, it is deliberately difficult to reconstruct it (or any equivalent alternatives) by knowing the stored hash value.
Collision resistant
- a hash function H is collision resistant: for a fixed input a, it is hard to find another input b such that H(a) = H(b),and a ≠ b.
- more strictly: a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.
Chameleon Hash Function
Informally, a chameleon hash is a cryptographic hash function that contains a trapdoor: Without the trapdoor, it should be hard to find collisions, but knowledge of the trapdoor information allows collisions to be generated efficiently.
Technical Content
Redactable Blockchain
by redaction we mean one of the following actions (and any combination of those): re-writing one or more blocks, compressing any number of blocks into a smaller number of blocks, and inserting one or more blocks.
Redactions can be made only by authorized entities and under specific constraints; moreover, redactions are publicly auditable by existing miners, since they must approve the new blockchain and have access to its old copies.
The best way to grasp the concept of a redactable blockchain is to think of adding a lock to each link of the hash chain (see Figure 1): Without the lock key it is hard to find collisions and the chain remains immutable, but given the lock key it is possible to efficiently find collisions and thus replace the content of any block in the chain.
Figure 1: Redactable operations on a redactable blockchain. In the top blockchain, all padlocks are locked resulting in an immutable blockchain. In the middle blockchain, the padlock from block Bi+1 to block Bi is open, meaning that the content of block Bi can be redacted. In the bottom blockchain, the block Bi was redacted ( resulting in block B’i ) and all the padlocks are once again locked, making the blockchain immutable.
Figure 2: The redactable blockchain structure (using a public-coin chameleon hash). The field s of a block stores the value shown in the top white field of the previous block. We note that the top white field is not stored in the block. The bottom darker field (Randomness) is updated when the block is redacted (i.e., a collision is computed).
Formalizing Blockchain
A block is a triple of the form B=⟨s,x,ctr⟩ , where s∈{0,1}κ,x∈{0,1}∗ and ctr∈N. Block B is valid if
Here, H:{0, 1}∗→{0, 1}κ and G:{0, 1}∗→{0, 1}κ are collision-resistant hash functions, and the parameters D∈N and q∈N are the block’s difficulty level and the maximum number of hash queries that a user is allowed to make in any given round of the protocol, respectively.
The blockchain is simply a chain (or sequence) of blocks, that we call C. The rightmost block is called the head of the chain, denoted by Head(C). Any chain C with a head Head(C):=⟨s,x,ctr⟩ can be extended to a new longer chain C′:=C∥B′ by attaching a (valid) block B′:=⟨s′, x′, ctr′⟩ such that s′=H(ctr, G(s, x)); the head of the new chain C′ is Head(C′)=B′.
Secret-coin hashing
this paper proposed a generalization chameleon hash function referred to as “secret-coin” and it includes standard chameleon hashes as a special case (refferred to as “public-coun”).
Definition 1 (Secret-coin chameleon hash). A secret-coin chameleon hash function is a tuple of efficient algorithms CH=(HGen, Hash, HVer, HCol) specified as follows.
- (hk,tk)←$HGen(1κ) : The probabilistic key generation algorithm HGen takes as input the security parameter κ∈N , and outputs a public hash key hk and a secret trapdoor key tk.
- (h,ξ)←$Hash(hk,m) : The probabilistic hashing algorithm Hash takes as input the hash key hk, a message m∈M , and implicit random coins r∈Rhash , and outputs a pair (h, ξ) that consists of the hash value h and a check string ξ .
- d=HVer(hk, m, (h, ξ)) : The deterministic verification algorithm HVer takes as input a message m∈M , a candidate hash value h, and a check string ξ , and returns a bit d that equals 1 if (h,ξ) is a valid hash/check pair for the message m (otherwise d equals 0).
- ξ′←$HCol(tk, (h, m, ξ), m′) : The probabilistic collision finding algorithm HCol takes as input the trapdoor key tk, a valid tuple (h, m, ξ) , and a new message m′∈M , and returns a new check string ξ′ such that HVer(hk, m, (h, ξ))=HVer(hk, m′, (h, ξ′))=1. If (h, ξ) is not a valid hash/check pair for message m then the algorithm returns ⊥ .
Definition 2 (Correctness for chameleon hashing). Let CH=(HGen, Hash, HVer, HCol) be a secret-coin chameleon hash function with message space M. We say that CH satisfies correctness if for all m∈M there exists a negligible function v:N→[0, 1] such that P[HVer(hk, m, (h, ξ))=1:(h, ξ)←$Hash(hk, m); (hk, tk)←$HGen(1κ)]≥1−v(κ).
Public-coin hashing
Definition 3 (Public-coin chameleon hash). A public-coin chameleon hash is a collection of efficient algorithms CH=(HGen,Hash,HVer,HCol) specified as in Definition 1, with the following differences:
- The hashing algorithm Hash, upon input the hash key hk and message m∈M , returns a pair (h, r), where r∈Rhash denote the implicit random coins used to generate the hash value.
- The verification algorithm HVer, given as input the hash key hk, message m, and a pair (h, r), returns 1 if and only if Hash(hk, m; r)=h .