Redactable blockchain

From CryptoWiki
Jump to: navigation, search

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. [1]

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. [2]

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.

Contents

Description

Figure 1: Redaction 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 B0i) and all the padlocks are once again locked, making the blockchain immutable.

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.

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).

Denotes

Redblc x.png - string. |Redblc x.png| - length of string.

Redblc X.png - set. |Redblc X.png| - number of elements in Redblc X.png.

Redblc 1.png - random Redblc x.png from Redblc X.png.

Redblc 2.png - А is an algorithm on input Redblc x.png, and output Redblc y.png.

Redblc 3.png - А algorithm, on input Redblc x.png, on ouptup is random Redblc r.png.

Algorithm А is probabilistic polynomial-time (PPT) if, A is randomized and for any input Redblc 4.png, the computation of Redblc 5.png terminates in at most |Redblc x.png| steps.

Redblc 6.png - security parameter.

A function Redblc 7.png - is negligible in the security parameter (or simply negligible) if it vanishes faster than the inverse of any polynomial in Redblc 8.png, i.e. Redblc 9.png.

Redblc 10.png - random variable and Redblc 11.png, for the probability that Redblc 12.png takes on a particular value Redblc 13.png (whereRedblc 14.png is the set where Redblc 15.png is defined).

Two ensembles Redblc 16.png and Redblc 17.png will be referred Redblc 18.png, to denote that the two ensembles are identically distributed, and Redblc 19.png to denote that they are computationally indistinguishable.

Blockchain Basics

Redblc 21.png - block, where Redblc 20.png, Redblc 22.png and Redblc 23.png. Block Redblc B.png is valid, if

Redblc 25.png

where Redblc 26.png and Redblc 27.png - are collision-resistant hash functions, and the parameters Redblc 28.png and Redblc 29.png 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.[3]

Redblc С.png - chain (or sequence) of blocks, i.e. blockchain.

Redblc 31.png - rightmost block, i.e. head of the chain.

Any blockchain Redblc С.png with a head Redblc 32.png can be extended to a new longer chain Redblc 33.png, by attaching a (valid) block Redblc 34.png, such that Redblc 35.png; the head of the new chain Redblc 36.png is Redblc 37.png. blockchain Redblc С.png can also be empty, and in such a case we let Redblc 38.png

The function Redblc 39.png - denotes the length of a chain Redblc С.png (i.e., its number of blocks).

For a chain Redblc С.png with length Redblc n.png or any Redblc 40.png we denote Redblc 41.png the chain resulting from removing the Redblc k.png rightmost blocks of Redblc С.png.

Analogously we denote by Redblc 43.png the chain resulting in removing the Redblc k.png leftmost blocks of Redblc С.png. Отметим, что если Redblc 44.png, тогда Redblc 45.png и Redblc 46.png.

If Redblc С.png - is a prefix of Redblc 47.png, it written as Redblc 48.png.

We also note that the difficulty level Redblc D.png can be different among blocks in a chain.

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.[4]

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.[5]

Secret-coin hashing

Definition 1 (Secret-coin chameleon hash):

A secret-coin chameleon hash function is a tuple of efficient algorithms Redblc 51.png specified as follows:

  • Redblc 52.png the probabilistic key generation algorithm Redblc 53.png takes as input the security parameter Redblc 54.png, and outputs a public hash key Redblc 55.png and a secret trapdoor key Redblc 56.png.
  • Redblc 57.png the probabilistic hashing algorithm Redblc 58.png takes as input the hash key Redblc 59.png, a message Redblc 60.png, and implicit random coins Redblc 61.png, and outputs a pair Redblc 62.pngthat consists of the hash value Redblc h.png and a check string Redblc psi.png.
  • Redblc 65.png the deterministic verification algorithm Redblc 66.png r takes as input a message Redblc 67.png, a candidate hash value Redblc h.png, and a check string Redblc psi.png, and returns a bit Redblc d.png that equals 1 if Redblc 71.png is a valid hash/check pair for the message Redblc m.png.
  • Redblc 74.png the probabilistic collision finding algorithm Redblc 75.png takes as input the trapdoor key Redblc 76.png, a valid tuple Redblc 77.png, and a new message [File:Redblc_78.png]], and returns a new check string Redblc 79.png such that Redblc 80.png. If Redblc 62.png is

not a valid hash/check pair for message Redblc m.png, then the algorithm returns Redblc 81.png.

Definition 2 (Correctness for chameleon hashing):

Let Redblc 82.png be a secret-coin chameleon hash function with message space Redblc M.png. Then Redblc 84.png satisfies correctness if for all Redblc 85.png, there exists a negligible function Redblc 86.png such that

Redblc 87.png

Public-coin hashing

In the definition above the hashing algorithm is randomized, and, upon input some message Redblc m.png, it produces a hash value Redblc h.png together with a check value Redblc psi.png, 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 Redblc psi.png consists of the random coins Redblc r.png, used to generate Redblc h.png, as the hash computation becomes completely deterministic once Redblc m.png and Redblc r.png 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 Redblc 84.png 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 Redblc 90.png specified as in Definition 1, with the following differences:

  • The hashing algorithm Redblc 91.png, upon input the hash key Redblc 92.png, and message Redblc 92.png, returns a pair Redblc 93.png, where Redblc 94.png h denote the implicit random coins used to generate the hash value.
  • The verification algorithm Redblc 96.png, given as input the hash key Redblc 97.png, message Redblc m.png and a pair Redblc 98.png, returns 1 if and only if Redblc 99.png

Collision-resistant

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 Redblc 92.png, can find two pairs Redblc 101.png and Redblc 102.png, that are valid under Redblc 92.png and such that Redblc 103.png with all but a negligible probability.

Key managment

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.

Conclusion

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.

Glossary

Bibliography

Go to list of references.

Dyorov O., 2016