Blockchains provide a strong mechanism to ensure that data blocks have not been altered, but this feature conflicts with many privacy requirements, such as those in GDPR, which allow users to have private data deleted at their request. The immutability property makes a blockchain solution impractical for many such privacy rules, leading to the need for "editable blockchains".  

The blockchain immutability property was designed to solve the problem of double spending in cryptocurrencies.  But conventional blockchains are hard to use in many distributed system applications, without the ability to modify or delete data. The added trust of distributed ledgers is a valuable feature, providing greatly simplified auditability and verification of actions among multiple parties in applications such as supply chain and others, but the inability to modify or delete data is often still needed. 

We have designed and implemented a new form of distributed ledger technology (DLT), known as a data block matrix, which provides the integrity assurance of blockchain but allows for controlled revision or deletion of data. This is an essential property for using DLT in applications that must support privacy requirements for deletion of private data at a user's request.  The blockmatrix data structure has been implemented with an API for practical use in distributed database applications, and is now included in the open source release of Next Generation Database Access Control (NDAC).  Blockmatrix extends the market for blockchain solutions by solving the conflict between privacy regulations and blockchain, and allowing exception management.

Blockchain vs. Privacy

The most widely recognized form of DLT is the blockchain structure, which provides the basis for cryptocurrencies and a variety of other applications.  Most currently available distributed ledger designs using blockchain provide certain properties:

• Pseudo-anonymity – especially for cryptocurrency, blockchains enable participation using only identifiers.  Permissioned blockchains may not include this property.
• Public access, transparency – every participant can see all transactions on the blockchain, although they may be anonymized.  This property may also not be provided in permissioned systems.
• Small transaction size – Blockchains were originally designed for monetary transactions, so messages are assumed to be relatively small.
• Immutable records – As a consequence of the linked chain of cryptographic hashes of records, a change to one record would cause the hash of subsequent records to be invalid, so changes require recomputing the entire chain.  As a result, it is generally intractable to change any record in a blockchain.
• Proof of work or other expensive consensus models – A consequence of the need to prevent double spending. Permissioned blockchains do not generally need this feature and can use simpler consensus.
• Block ordering guarantee – the consensus mechanism ensures ordering of the blocks and therefore transactions, preventing the possibility of double spending. 
• Decentralization – there is no central authority for records.  With each update, records are dispersed to peer nodes simultaneously, who ensure the updates are correct.
• Replication and Synchronization guarantee – transactions are duplicated across all nodes of the network, so that every node has an identical copy of all transaction records, current to the most recent update cycle.  Consensus protocols are designed such that when the consensus is complete, all nodes have an identical copy of the distributed ledger records.
• Integrity protection – Cryptographic hashes are used to guarantee that records have not been changed. 

We compare these properties with the needs of more typical applications of distributed data storage and retrieval in Table 1.  Note that six of the nine blockchain properties designed for cryptocurrency are at odds with the requirements of many other applications.

Table 1.  Comparing characteristics of DLT applications

Need for an Alternative Solution

The mismatch between blockchain properties and many application needs has led to a number of problems in applying blockchain designs to data management problems.  For example, Bitcoin is designed to provide some degree of anonymity in transactions (i.e., only public identifiers, not real-world identities are used), but the law may prohibit anonymity for many types of transactions and require participants to be identified for tax or other purposes. Laws such as the European Union General Data Protection Regulation (GDPR), that require the ability to delete privacy relevant information, may limit the type of information that can be stored in a blockchain. 

For system engineers, the price of distributed trust is often added complexity.  The design choices that were made to incorporate anonymity and prevent double spending in blockchains often lead to seemingly unnecessary complications when applied to areas beyond cryptocurrency.  For example, immutability has resulted in designs where alterable records must be kept off of the blockchain, with only pointers to them stored in the blockchain itself. Alternatively, some designs involve encrypting data on the blockchain, then destroying the encryption key to “delete” the data. Neither of these options may be desirable for many applications, as the first option leads to unnecessary complications, and the second risks the data being decrypted in the future, when data must be protected for decades. These are serious design issues for supporting privacy requirements such as those of GDPR, resulting in proposals such as an “editable blockchain” using new forms of hashing. For cryptocurrency, a consensus algorithm is needed to guarantee record ordering in the absence of a central time authority (i.e., transactions are ordered based on group consensus, rather than time of entry into a system), and this ordering is used to prevent double spending.  Designs for access control using blockchain may involve tokenizing permissions, then passing these to users, and spending down the value to remove a permission from a user.  All of these strategies are needed to take advantage of blockchain’s trust properties, but blockchains would probably not be used if a more conventional database could provide the desired distributed trust. 

At first glance, blockchain solutions for applications such as supply chain, financial settlement, and others may appear to offer nothing more than added complexity in comparison with a conventional database.  However, when more than one organization is involved, the decentralized trust of blockchains and other distributed ledgers can be a tremendous advantage. For example, consider regulated industries where audit is a part of doing business. Every node on the system can have a full set of records detailing the movement of assets. Any shared database can keep track of asset movement, but DLT adds trust by maintaining current, integrity-protected records at every organization, making it easy to audit the process.  Thus, the financial industry views full traceability and simplified reconciliation of transactions among the key advantages of DLT.  We can view DLT as adding a layer of distributed trust to the problem of data storage and retrieval.

Capabilities

Blockchain's hash-based integrity verification provides trust, at the cost of an inability to delete or update records, leading to design complications that would not arise with conventional database management systems.  Similarly, the sequencing guarantees of blockchain consensus protocols are needed for cryptocurrency in the absence of a universal timestamp.  Moreover, actions within the distributed ledger must be connected with other actions in the real world, through accurate timestamps.  We are developing a new architecture that provides the trust features of blockchains, with characteristics that allow for simpler designs and greater practicality in conventional data management problems.  This alternative can lead to new approaches to incorporating trust into distributed systems applications. The data blockmatrix data structure provides key capabilities:

• Trust and integrity of data - In the same manner as blockchain, hash computations are used to ensure data integrity
• Editability - GDPR and other privacy regulations require that users have the ability to remove data, making blockchain incompatible with privacy in many applications.  The data blockmatrix makes it possible to meet privacy requirements while retaining the assurance of data integrity provided by blockchain.
• Performance - Maintaining integrity-assured local copies of data, especially for security and access control, drastically reduces the need for communication among networked nodes in a distributed system.  This feature of the blockmatrix is now being used in the Next Generation Database Access Control (NDAC) system (open source link below).  

Key Capabilities

• Modifiable blocks -a data block matrix structure that provides hash-based integrity while allowing controlled deletion or modification of data.  This capability can support privacy requirements that are difficult or impossible to meet with conventional DLT.
• Verified time - a high-resolution time protocol that allows guaranteed time stamps to be used in place of consensus algorithms to ensure record ordering, making possible much higher throughput and higher precision timestamps that possible with conventional blockchain. 

Summary - how is the data block matrix different from blockchain?

Blockchain – provides integrity, immutability 

• No erasure possible, by design
• Double-spend problem solved by distributed time-stamp/sequencing guarantees
• Sequencing guarantees require proof of work algorithms
• Proof of work extremely slow, by design

Data block matrix – provides integrity, erasure

• Integrity protection guarantees for all blocks not erased
• Verified timestamps instead of sequencing guarantee
• Greater range of consensus algorithms available, suitable for permissioned DL
• Very fast consensus algorithms can be used

Team
    Rick Kuhn, NIST 
    Jeff Voas, NIST
    Dylan Yaga, NIST
    Josh Roberts, NIST
    Temur Saidkhodjaev, Univ of Maryland

Additional resources

• IEEE Blockchain Initiative
• IEEE Blockchain Summit, 2019 (NIST)
• IEEE Blockchain Summit, 2018 (NIST)