There is increasing discussion in the Bitcoin community about a workable solution to the back-to-genesis problem. When presented with a token transaction, the goal is to be able to answer the following question efficiently and without help of a trusted third party:
‘Is this a valid token?’
In nChain R&D we have developed a solution that can be implemented on the BSV blockchain today. It is a generic approach that involves a mathematical construction known as a zero-knowledge proof (ZKP) and can be implemented on many other blockchains as well, such as BTC.
I personally worked on this solution together with my colleagues Dr. Mehmet Sabir Kiraz and Dr. Enrique Larraia. Please contact us if you are interested in learning more about the idea and implementation.
Context: The Back-to-Genesis Problem
A token ruleset (or other additional logic) can be encoded on top of the Bitcoin ruleset. But just because a transaction satisfies the token ruleset itself does not mean that it is a valid token. We need to check that all preceding transactions have also satisfied the token ruleset, which becomes harder as more token transactions are created. This is known as the back-to-genesis problem or the traceback problem.
Let’s discuss a simplified example.
Consider a chain of transactions that each have exactly one input and one output. Each transaction spends the output of the previous transaction. We call this a transaction chain.
In fact, a transaction chain can be used to model the lifetime of an NFT. We can use the following simple token ruleset:
- Transaction Tx0 is the issuance of the NFT
- Transaction Tx1 assigns the NFT to a first owner
- Transaction Tx2 assigns the NFT to a second owner
- …
If any transaction has more than one input or output, then the token ruleset has not been followed and ownership is not transferred. We can interpret this as the NFT being burned and no longer owned by anyone.
Suppose we are presented with transaction Txn. It has one input and one output, so it satisfies the token ruleset. But how do we know that it is part of an unbroken chain of transactions that all satisfy the token ruleset since the issuance transaction?
One option is for us to inspect every transaction starting with Tx1, Tx2,… etc all the way up to Txn. We can then explicitly check that each transaction has exactly one input and one output. If each transaction is 200 bytes, then a chain of one million transactions will be 200 MB, so this process can require some computational resources.
Another solution is to use a trusted third party, for example the token issuer, who keep track of every transaction and check that there is exactly one input and one output. This trusted third party will be able to give us a quick answer as to whether Txn is indeed part of the chain. This is a great solution for many use cases. But what if the token issuer cannot be available at all times?
It is the goal of this article to explore whether it is possible to solve this problem without a trusted third party, and without checking every transaction in a chain. This is an embodiment of the back-to-genesis problem. In the above example, what we need is an efficient way to prove that Txn is part of the transaction chain originating from Tx0.
A solution using a Transaction Chain Proof
We have developed a solution using a Transaction Chain Proof (TCP). This is a mathematical proof that transaction Txn is linked to transaction Tx0 through an unbroken chain of transactions. The type of proof system we use is called a recursive ZKP. The recursive property allows us to create a proof that gets updated every time a new transaction is added to the chain.
The advantages and disadvantages of our solution are as follows.
Advantages:
- Proofs are of constant size regardless of the length of the transaction chain;
- Proofs do not need to be stored on-chain, nor verified by miners;
- Transaction sizes can be small – they can just use Pay-To-Public-Key-Hash script patterns, for example;
- It is backwards compatible with existing token protocols;
- It is blockchain agnostic
Disadvantages:
- Non-negligible processing time to create each new proof.
- Uses cutting edge technology that is not yet battle tested.
It works like this, for each new transaction an updated proof is required. Each updated proof allows the following to be verified:
i. The new transaction Txn satisfies the token ruleset. In our example in the context section, this means that there is exactly one input and one output.
ii. Either the previous transaction Txn-1 has a valid proof, or it is the issuance transaction Tx0.
We can construct a ZKP circuit for each token ruleset. Once this is established, each transaction uses the same ZKP circuit. A unique token identifier is hardcoded into the initial proof.
Miners play no role in the creation or verification of these proofs, and the proofs themselves do not involve Bitcoin script. As such, they don’t need to be recorded on-chain at all. This means that transaction sizes are kept to the minimum. However, one may optionally include the proofs in each transaction to have a complete on-chain record of the validity of each token.
The proof size depends on the ZKP implementation. These come with different security and efficiency trade-offs. For example, Groth16 requires a proof size of 1.5 kB but requires a trusted setup per-circuit. Whereas Halo requires a proof size of 3.5 kB but does not require a trusted setup.
These proofs can be constructed by anyone, and their validity can be explicitly checked. This means that we do not need to trust the creator of the proof.
Where are we now?
We have presented a method to prove that a transaction is part of an unbroken chain of transactions that satisfy a token ruleset. This can be used to establish a token a protocol that solves the back-to-genesis problem without a third party. It requires small proof-carrying data that does not need to be stored on-chain, but the proofs take a non-negligible time to construct with current ZKP implementations. The protocol can be implemented on any blockchain.
At nChain R&D we are actively developing the protocol. Our initial tests are promising, and we are refining and optimising our final designs for simple use cases such as NFTs (as described above). But we are also working towards providing more flexibility for more complex token implementations such as CBDCs.
If you are interested in learning more about the method or potential implementations, please contact us.