This is the final of a series of blog posts relating to Notaries in Corda 5.
Archiving of notary data has been a long-standing challenge within Corda due to the presence of state data determining whether a state is considered to be spent. In previous versions of Corda, this results in ever-growing data sets that limit the scalability of notary services. Corda 5 solves this problem through the novel application of some of the foundational technology that underpins Corda’s transaction model by enabling double-spend prevention even in the absence of state data. In this blog post, we will outline how this is possible, and how we can build on this to support safe archiving of state data.
Double spend prevention
Let’s quickly recap how repeated spending of the same state, otherwise known as a double-spend is prevented within Corda. From the perspective of Corda’s uniqueness checking functionality, states are defined by the root hash of the Merkle Tree representing the transaction that created the state as a transaction output, and an index representing the position of the output state within the transaction. For example, :0 for the first output state, :1 for the second, and so on.
Transactions which wish to spend a state as an input make a request to the notary service the state is associated with. In previous versions of Corda, the transaction is only accepted if the state does not exist in the uniqueness database, as the existence of the state in the database implies the state is already spent. Corda 5 takes this a step further by tracking both unspent and spent states, and additionally ensures that any states being spent by a transaction are known to the notary, rejecting any unknown states. This is an important piece in solving the archiving puzzle which we will come back to later.
This logic is very simple, however given Corda’s ability to parallelize flow operations, it is entirely possible that multiple transactions requesting notarization may be in-flight at the same time, and these may try to spend the same state at the same time. To protect against this, we rely on the ACID properties of the underlying uniqueness database. This is why all notary virtual nodes representing a notary service must share the same uniqueness database, and why the database must be strongly consistent.
Merkle Trees and notarization
We previously mentioned that states are identified by the root hash of a transaction Merkle Tree. We will not delve into all the details of Merkle Trees here, though this article provides a good overview if you wish to learn more. For the purposes of this discussion, it is sufficient to understand that Merkle Trees are a type of binary tree that store hashes of data components in leaf nodes of the tree, with each parent node storing a hash of its children. This is repeated all the way up to the root node, with the root node hash used as the transaction id in our ledger implementation. The crucial traits of a Merkle Tree for our purposes are:
- It is possible to verify the integrity of certain data components that the tree represents without revealing all data components. This is important from a privacy perspective.
- Changing any data component in the tree changes its hash, and by extension, the hash of all parent nodes all the way up to the root node. This means that changing any data component fundamentally changes the transaction id stored in the ledger and would be considered an entirely different transaction.
The non-validating notary protocol implemented in Corda 5 receives what is known as a filtered transaction, which hides some of the data components of the transaction constructed by the other parties to the transaction, revealing only the information the notary needs in order to perform its uniqueness checking and basic validation. This aids privacy by ensuring that we do not leak data unnecessarily to the notary.
One of these pieces of information is a time window, which indicates a time before and / or after which the notary must have signed the transaction. A notary will refuse to notarize a transaction that is presented outside of these specified time bounds. This means that if a notary has signed a transaction with a time window, you can assume the signature, and hence confirmation of the transaction happened within the time bounds of the transaction. The full transaction also includes a list of signatories who must provide valid signatures over the transaction in order for the transaction to be considered valid. These are visible to Alice and Bob, but not in the filtered transaction sent to the notary, in order to maintain privacy.
The above diagram shows a very simplified representation of a filtered transaction Merkle Tree, where Alice and Bob are participants (and signatories) to the transaction, and it has now been sent to the notary to be confirmed. The notary is provided with the time window data and the necessary Merkle Tree hash information. The notary can check:
- The current time window is valid.
- The Merkle Tree is validated by re-computing up to the root hash using the known information and supplied hashes for the hidden data, and ensuring the computed hash matches the specified transaction id.
Assuming these checks pass, and any input states are present in the notary’s database and are unspent, the notary provides a signature over the transaction, meaning it can now be considered confirmed. It also updates its records of unspent and spent states based on any supplied input states and / or number of output states specified in the transaction (these are also part of the Merkle Tree and provided to the notary but are excluded from the diagram for simplicity). The other participants on the network (Alice and Bob in this case) with full transaction visibility can now also verify that each party in the transaction signatories list have signed the transaction.
Note on validity vs confirmation
There is a subtle but important difference between transaction validity and confirmation, which is important to understand as we delve into the details of archiving. As specified in the Corda 5 ledger documentation, for a transaction to be committed to the ledger, it must both be valid, meaning that it is contractually valid, and also unique, which means that if the transaction is presented to the notary, it will return a notary signature indicating the notary’s confirmation of the transaction, and by implication, confirming the status of the transaction on the ledger as the unique consumer of the input states it references.
The notary keeps records of transactions it has seen previously, which means that if a transaction is replayed to the notary, it will return the original result (a signature in the case of a successful transaction, and an error message otherwise). This is true even if the result of time window validation would be different now to when the transaction was originally submitted – the original result is returned regardless.
Once data is archived, the original result can no longer be returned, as there is no longer a record of the transaction. However, transactions that were successfully notarized, even those that have been archived by the notary, continue to be valid. This is a key point because even after data is archived on the notary, transactions may still need to be exchanged between, and verified by Corda nodes as part of backchain verification. These transactions will continue to verify, because there will be a valid notary signature stored with these transactions. However, a notary would refuse to confirm the transaction if it were presented again to the notary after the transaction has been archived, because the historic copy of the original result no longer exists, and the current time means it would fail time window checks when attempting to notarize the transaction again.
Safe data archiving
What does any of this have to do with archiving? There are two small but crucial changes in Corda 5 that enable us to safely delete historic state data:
- It is now mandatory to specify a time window upper bound on a transaction. This means that from the notary perspective, all transactions now have a finite point at which they can no longer be confirmed.
- As mentioned earlier, the notary now tracks unspent (output) states of transactions, in addition to spent states that were consumed as inputs by subsequent transactions. This allows it to reject any attempts to spend states that the notary is not already aware of.
Putting these points together, we can now delete states that have been consumed, but only once we have passed the time window upper bound of the transaction that initially created the state. This works because we can rely on the above additional checks to prevent replay of historic transactions. This insight may not be immediately obvious, but is crucial to our solution, so lets explore how this works by example. Consider the following scenario:
- An initial transaction is created by Alice to create a token, which is assigned to Bob. Bob can redeem this token for some item of value in future. For arguments sake, lets say this transaction has hash
8A42. This creates a single new output state,
8A42:0which is marked as unspent in the notary.
- A subsequent redemption transaction is created by Bob to redeem the token. This consumes state
8A42:0which is now marked as spent in the notary.
Buy one, get one free?
It turns out Bob likes a bargain and decides to try and bag himself a buy one get one free deal by redeeming the token again. Of course, the notary sees that this state is already spent in its uniqueness database, and immediately rejects the action.
Some time passes, and we pass the time window upper bound for the initial transaction, so the notary proceeds to delete the state data. Bob gets wind of this and tries to redeem this state again.
In previous versions of Corda, this action would be successful, because the notary has no record of the spent state, so it allows the state to be consumed again. This is why we cannot delete historic states in previous Corda versions. Unfortunately for Bob, Corda 5 is smarter. The notary receives the transaction request, however this time, it has no record of the unspent state for
8A42:0, so rejects the transaction with an unknown state error.
Bob the (transaction) builder
Not one to be defeated easily, Bob now raises the stakes. If the notary doesn’t know about the state, then all he needs to do is replay the original transaction that created the state, right? Bob is thwarted again, because this is where our time window validation comes in. The current time is now beyond the time window upper bound of the original transaction and is therefore rejected by the notary again. The transaction, while valid, will no longer be confirmed by the notary.
Finally, in desperation, Bob resorts to tampering with the transaction itself. He generates a new transaction which is a clone of the old transaction, but with the time window set to a point beyond the current time. Bob signs this transaction, and maliciously adds Alice’s signature from the original transaction, before presenting this to the notary. The notary confirms the transaction, because from its perspective, the transaction is now valid with respect to its time window data:
However, all of this is for naught, because as we said earlier, changing any component of the Merkle Tree fundamentally changes the hash of its root. So from the perspective of the notary and ledger, this is a unique transaction that has generated entirely new states, and does not constitute a replay of the original transaction and state creation. Ultimately, any legitimate party subsequently interrogating the transaction and inspecting the signatures would find that Alice did not in fact sign this new transaction, and therefore these newly created states are useless. It may also fail CorDapp specific verification; in our example, it could be that only Alice is allowed to issue new states, and therefore any transactions proposed by Bob that create new states would fail transaction verification.
Putting into practice
Corda 5.0 does not provide archiving functionality; however, the notary captures all the necessary information and performs the validation mentioned earlier to make safe archiving of data straightforward. The rules for archiving data within the uniqueness database are simple:
- States can be archived when they are spent, and the transaction that originally created the states time window upper bound has passed.
- Transaction related data can be archived when there are no longer any output states associated with it in the uniqueness database, i.e., all states that the transaction created have themselves been archived.
This approach does rely on CorDapp developers to set sensible time window upper bounds on transactions. If this is set years in the future, then it means that any output states of that transaction cannot be archived until that point.
A rudimentary solution can be implemented as desired via SQL query. However, a more sophisticated background archiving solution will be implemented in a future release.
What we have demonstrated above is a specific application of a general and powerful solution; the ability to store arbitrary time-limited data in a tamper-evident way by leveraging the ability to distill the data down to a hash that can be used as a unique database key, which can then be verified against an expected set of signers that act as gatekeepers to the integrity of the data.
This is just one application of Distributed Ledger Technology, and herein lies its true power; it provides the same guarantees that society relies on to secure the internet in the form of digital certificates to data, such that the data can be moved freely between different parties and its contents trusted, without relying on a fully centralized system. I believe this technology will be transformative in the years and decades ahead.