Redactable blockchain - built according to certain rules chain of transactions generated by units with the "lock" between them, which in knowledge key allows you to edit the block. Each chain is appointed administrator, who is the sole owner of the key.
Redaction of blockchain will be available only in exceptional circumstances, in order to correct typos and factual errors operators and bring the data into compliance with the requirements of the changed legislation. 
Redactable blockchain came up and developed by the international group of scientists: Giuseppe Ateniese of Stevens Institute of Technology, USA; Bernardo Magri from the English Sapienza University of Rome, Italy; Daniele Venturi from the English University of Trento, Italy; Ewerton Andrade from the University of Sao Paulo, Brazil. 
Their idea has caused a lot of criticism due to the fact that, by definition blokcheyn - obviously immutable structure. However, the authors justify their approach is the fact that their system is designed for private blokcheynov that are most popular among banks. They, in turn, will be able to assign administrators to work with the system, endowed with the right of access to the right and edit the data in compliance with the corporate code.
All blockchain designs rely on a hash chain that connects each block to the previous one, to create an immutable sequence. The immutability comes from the collision resistance property of the hash function. 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 is immutable, but given the lock key it is possible to efficiently find collisions and thus replace the content of any block in the chain. With the knowledge of the key, any reduction is then possible: deletion, modification, and insertion of any number of blocks. Note that if the lock key is lost or destroyed, then a redactable blockchain reverts to an immutable one.
The main idea of our design is to employ a special hash function that is collision-resistant unless a trapdoor is known. This special hash is an evolution of a standard chameleon hash. Indeed, in a standard chameleon hash, collisions must be kept private since the trapdoor can be extracted from a single collision. In our improved design, it is safe to reveal any number of collisions.
- А is an algorithm on input , and output .
- А algorithm, on input , on ouptup is random .
Algorithm А is probabilistic polynomial-time (PPT) if, A is randomized and for any input , the computation of terminates in at most || steps.
where and - are collision-resistant hash functions, and the parameters and 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.
- chain (or sequence) of blocks, i.e. blockchain.
Work of models the Bitcoin protocol in a setting where the number of participants is always fixed and the network in synchronized. They show that the protocol satisfies consistency in this model, meaning that all honest participants have the same chain prefix of the blockchain. A more recent work analyses the case where the network is asynchronous and the number of participants can dynamically change.
Redactable blockchain does not depend on these parameters.
Chameleon Hash Functions
The concept of chameleon hashing was put forward by Krawczyk and Rabin, building on the notion of chameleon commitments. Informally, a chameleon hash is a cryptographic hash functions that contains a trapdoor: Without the trapdoor it should be hard to find collisions, but knowledge of the trapdoor information allows to efficiently generate collisions for the hash functions.
Definition 1 (Secret-coin chameleon hash):
A secret-coin chameleon hash function is a tuple of efficient algorithms specified as follows:
- the probabilistic key generation algorithm takes as input the security parameter , and outputs a public hash key and a secret trapdoor key .
- the probabilistic hashing algorithm takes as input the hash key , a message , and implicit random coins , and outputs a pair that consists of the hash value and a check string .
- the deterministic verification algorithm r takes as input a message , a candidate hash value , and a check string , and returns a bit that equals 1 if is a valid hash/check pair for the message .
- the probabilistic collision finding algorithm takes as input the trapdoor key , a valid tuple , and a new message [File:Redblc_78.png]], and returns a new check string such that . If is
not a valid hash/check pair for message , then the algorithm returns .
Definition 2 (Correctness for chameleon hashing):
In the definition above the hashing algorithm is randomized, and, upon input some message , it produces a hash value together with a check value , that helps verifying the correct computation of the hash given the public hash key. The random coins of the hashing algorithm are, however, secret. A particular case is the one where the check value consists of the random coins , used to generate , as the hash computation becomes completely deterministic once and are fixed. This chameleon hash function called public-coin. Since the verification algorithm simply re-runs the hashing algorithm, they typically drop the verification algorithm from in the case of public-coin chameleon hashing.
Definition 3 (Public-coin chameleon hash):
A public-coin chameleon hash is a collection of efficient algorithms specified as in Definition 1, with the following differences:
- The hashing algorithm , upon input the hash key , and message , returns a pair , where h denote the implicit random coins used to generate the hash value.
- The verification algorithm , given as input the hash key , message and a pair , returns 1 if and only if
The main security property satisfied by a secret/public-coin chameleon hash function is that of collision resistance: No PPT algorithm, given the public hash key , can find two pairs and , that are valid under and such that with all but a negligible probability.
Although we view the technical tools that make redactions possible as the main contribution of this work, a natural question that may arise is how the trapdoor key for the chameleon hash function is managed. We stress that the answer to this question is completely application dependent, but we still provide some examples. Below we briefly describe three types of blockchains that occur in real-world applications, and clarify how the trapdoor key could be managed in each case.
- Private blockchain: In this type of blockchain, which is widely used by the financial sector, the write permissions are only given to a central authority, and the read permissions may be public or restricted. In this case the key management becomes simple; the trapdoor key could be given to the central authority that has the power to compute collisions and therefore redact blocks.
- Consortium blockchain: In this type of blockchain the consensus is controlled by a predetermined set of parties (i.e., a consortium). In this case the trapdoor key can be shared among all the parties of the consortium, and redactions can be realized using MPC.
- Public blockchain: This type of blockchain is completely decentralized, and any party is allowed to send transactions to the network and have them included in the blockchain (as long as the transactions are valid). The consensus process is decentralized and not controlled by any party. The best example of a public blockchain is Bitcoin. In this case we have two options to manage the trapdoor key.
- The trapdoor key can be distributed among all the parties (full miners) of the network. The drawback of this solution is that, if the number of parties in the network is too big (e.g., > 200), it might not be very efficient due to performance issues of the MPC protocol.
- The trapdoor key can be distributed among a carefully chosen subset of the parties. For example, in Bitcoin it is well known that the majority of the network hashing power is actually controlled by a small number of parties. Although we acknowledge that the concentration of hashing power to a small number of parties can be unhealthy to the system, this solution does not change the existing Bitcoin trust assumption (i.e., Bitcoin already assumes trusted majority).
Integration with Bitcoin
Redactable blockchain framework proposes to replace the G function with a (enhanced collision resistant) chameleon hash function. In Bitcoin, this means that the inner SHA-256 function is replaced by a chameleon hash function, and its output is then used as the input to the outer SHA-256 function. The Bitcoin block header needs to be extended to accommodate the randomness of the chameleon hash (or the hash/check pair in case of a secret-coin chameleon hash).
For the standard (immutable) Bitcoin operation, the only modifications necessary are for blocks creation and verification. There are no changes on how transactions or other aspects of the Bitcoin works. When a block is being created the miner first selects all the transactions that will be part of the block, and then it starts to fill in the block header. Initially, the miner fills in the hash of the previous block header, the root of the Merkle tree (summarizing all transactions inside the block), the timestamp of the block creation, and the current difficulty target. Hence, it samples fresh randomness7 and computes the chameleon hash function of the block header with the sampled randomness. The output of the chameleon hash, together with a nonce (or a counter), is used to solve the proof-of-work of the block. Once the proof-of-work is solved, the miner fills in the remaining fields of the block header, i.e., the randomness and the nonce.
After the newly created block is broadcasted, the other Bitcoin nodes can verify the validity of the block by first performing the usual verifications on the transactions, and later byrecomputing the chameleon hash using the randomness stored in the block header, and hashing its ouput together with the nonce (via SHA-256). If the block passes all verifications, and the resulting hash is smaller than the target difficulty, then the block is considered valid and shall be added to the chain.
To manipulate the blocks we propose the creation of two new algorithms; one to remove blocks from the chain and the other to replace the contents of existing blocks. To validate the integrity of the blockchain, a verification procedure, that checks that each block header contains the hash of the previous block header, is performed on the entire blockchain. Once a block is modified or removed this integrity becomes compromised. In order to keep the integrity of the chain, a hash collision for the modified block (in the case of the redaction algorithm) or for the next block remaining on the chain (in the case of the shrink algorithm) must be computed. The hash collision algorithm computes a new randomness value that, when hashed together with the block header, outputs the same hash value as some other block (that is passed as a parameter to the function). After a collision is found, the randomness value on the block header is updated to the new computed value. As a consequence, the integrity of the blockchain is restored, and every node on the network can verify the validity of the chain.
Redactable blockchain - a framework for editing and compressing blocks of content in virtually any technology based on blockchain. And this is not an abstract thing, but very real design that can work now, since the implementation of the edit blockchain requires only minor changes to the current structure of the blocks, and besides, the overhead is negligible.
Go to list of references.
Dyorov O., 2016