An Introduction to Hash Chains
In the previous article, we identified how to enforce a common script template across inputs and outputs. This technique is valuable for a variety of reasons, but for tokenization protocols is allows one to easily filter transactions from the blockchain that are relevant to the protocol utilizing a common identifier — the hash of the template. In this article we will cover token access chains and how they can be utilized in Bitcoin. Credit goes to nChain for a paper on the hash chain technique.
A hash chain is a method whereby a successive application of a hash function can be used to produce many one-time keys from a single key or password. Traditional applications of a hash chain utilize the technique so that a client can act in a secure manner with a server, and the server needs only to keep the last used key by the client to validate the next used key. We will implement the technique using the Bitcoin blockchain as the server, and any token issuer as the client.
For this implementation we require that each token issued is related to the token before it through the use of a hash function:
To generate the token, the issuer (Alice) and the blockchain (Miners) agree on a number n of events requiring a token to access. This can be done in Script when issuing the first token. Alice generates a 256-bit number t_0. We can do this utilizing a hash function on a piece of data or utilizing a random number. This token (t_0) will be the last used token. Alice stores this token and no other value.
This value is hashed n times to generate t_n:
We now have created an access chain of tokens that satisfy:
And so forth until:
The token t_n is sent to the blockchain in an issuance transaction and acts solely for verification purposes. Note that any miner or other actor listening to the blockchain cannot calculate any other tokens from this value.
Alice can now calculate the value of her first token:
And activate it by creating a transaction that contains the token. In a traditional sense, the server would now validate that Alice has activated the correct token by checking that t_n = H(T_{n-1}). If it has, the server now stores t_{n-1} and discards t_n. This process can be repeated iteratively until t_0 is revealed.
Using Bitcoin Script, we can use the miners as the validators of the hash chain by structuring our transaction whereby the token is revealed in the unlocking script of the transaction to satisfy a condition in the input’s locking script.
I will outline an example whereby n = 5 and t_0 = 4bc1e4b940e46fe42bfe00f2be03d5a41c0f312478d2a31e32d1864c75ce0e2d
Using SHA256 as our hashing function, Alice generates t_n = 4036ec7b619e9c1d8abd72dc20a884da46cd798d0b4b2c2ee9ad74650d673a67
As such, she structures a transaction that includes in the locking script:
OP_SHA256 4036ec7b619e9c1d8abd72dc20a884da46cd798d0b4b2c2ee9ad74650d673a67
OP_EQUALVERIFY
Her first token t_{n-1} is then calculated= 9dff79932e69a4c3857df7796e44bde0d46cba94c239b46582e3f36cb7ef6f7d
Alice now publishes a new transaction that includes this value in the unlocking script. In order for this transaction to be accepted by the mining network, the script must evaluate to true. This replaces our server in the traditional architecture with the blockchain itself. We can also include further logic in our script to enforce that only n tokens can be spent.
To demonstrate this onchain we’ve created the above access chain in the following transaction. The input defines the access chain with t_n, and the output is the first spend of the first token t_{n-1}. You can follow index 0 in the outputs to see the full chain of spends for the 5 tokens.
Remember — in the previous article we outlined how we can enforce a common script template between inputs and outputs by hashing our script template. Since the token (t_{n-m}), where m = the number of activated tokens, is data of a fixed size that can be stripped from our script template, we can combine the technique used in that article to now enforce a structure as each token is activated.
There also exist techniques to transfer tokens to a new owner, such that Alice can sell her remaining tokens t_{n-m-1} to Charlie. This can be done securely using a technique that will be covered in a future article.
Combining Hash Chain Tokens with Public Keys
We can also link tokens to public keys such that the tokens are embedded in P2PKH transactions and a validator needs only to check the public key that is exposed in the locking script.
Looking at the chain of transactions we created above, the issuing transaction is made with an input from the key associated with address 1KJ4nEze9Z3ntVHLLoZY1zqEqhvZpcXpfF. The tokens are then sent back and forth between that address and the key associated with 1B31pjTLB7XhGUgdoGiA4xdALxNwfUuKkY.
There exists a way in which we can create these tokens offline and generate deterministic keys from the tokens themselves. Recall that a public key P_0 is the private key S_0 multiplied by G, the generating point of an elliptic curve.
Alice can share P_0 with Bob or another validator. Using her first token, t_{n-1}, Alice can calculate P_1:
Since only Alice knows t_{n-1}, only she can create this public key. P_1 can now be provably linked with the first token in Alice’s access chain. Alice can initiate a transaction to the address associated with P_1 and send t_{n-1} to Bob. Bob can now verify that the token t_{n-1} has been activated by checking that Alice made a transaction to P_1.
Using the same token chain above, we can calculate for P_0 = 0264863783b52d6fce816fb6cbd8f2917344341b14dc93269f855e5ea5c777fdf1, P_1 = 030d084486d4e7d54594f5400102cc9a106555061e296678978b61c44204276a30.
We can calculate more public keys for values up to P_5.
For this issuing transaction and the subsequent spends at outpoint 0, we used the same token access chain and the same keypairs as the transactions outlined above. This allows us to use the hash chain technique with regular P2PKH transactions.
The possibilities from here grow endlessly…
Play with hash chains and recreate the example transactions above using this golang library.
