This post was first published on Medium.
We develop an efficient algorithm to verify arbitrary data signed by a certain party in Bitcoin smart contracts. Compared to previous signature algorithm based on Rabin signatures, it is based on ECDSA and thus reuses native Bitcoin keys to generate and verify signatures directly.
Overview
Bitcoin smart contracts require oracles to import external data such as weather and commodity price. Once imported, smart contracts need to way to verify the data actually comes from authorized oracles. More specifically, we need to solve the following problem.
How to verify a piece of data is signed by an oracle with a known public key?
P and p denote an oracle’s public and private key, respectively. We first hash the data to be signed. The result is added with p, yielding a new private key p’.
x = sha256(data)
p’ = p + x
The corresponding public key, P’, can be derived as follows:
P’ = p’ * G = (p + x) * G = P + x * G
G is the generator of the elliptic curve used in Bitcoin.
The oracle uses the derived private key p’ to sign, instead of the original p. Everything here is publicly known, except p. Since only the oracle knows p, only he knows p’ and can use it to sign against P’. To calculate P’ in a contract, we need to calculate x * G and then add the result with P.
Efficiently Calculate x * G in Script
The naive way to calculate x * G is to use point multiplication on elliptic curve. However, it is computationally expensive. We note G is a special point on the elliptic curve. If we regard x as a private key, x * G is essentially x’s public key X.
X = x * G
Thus it suffices to verify (x, X) is a valid private and public key pair.
To verify this, we leverage the OP_PUSH_TX technique. In OP_PUSH_TX, we use a private key to sign the sighash preimage and use native signature checking, OP_CHECKSIG, to check the resulting signature against the corresponding public key. If the check passes, we can be sure the sighash preimage must be for the current spending transaction. Also, the public key must be derived from the private key. We choose (x, X) to the key pair in OP_PUSH_TX and thus verify X is indeed x’s public key.
Efficient Public Key Addition
Using the previous elliptic curve library, we can add P and X efficiently.
P’ = P + X
Once we have P’, we can use the native OP_CHECKSIG to verify the spending transaction containing data is signed by the oracle using p’. The full code is shown below.
Line 16 use OP_PUSH_TX to verify X = x * G. Line 19 verifies P’ = P + X. Line 22 checks the signature is generated with p’.
It is worth noting that the oracle participates in signing of the transaction, of which the data is in the unlocking script of one of its inputs. To allow maximal flexibility for creating the remaining parts of the transaction, he can use sighash flags such as SIGHASH_NONE | SIGHASH_ANYONECANPAY when signing. By contrast, Rabin signature-based oracles can simply publish signed data without participating in creation of transactions.
Summary
By reusing Bitcoin key pairs, an ECDSA-based oracle can leverage existing infrastructure and network effects that the Bitcoin ecosystem already provides (including all Bitcoin wallets and many service providers such as block explorers) and thus significantly lowers development cost. In practice, it becomes a competitive alternative to state-of-the-art Rabin signatures-based oracles, even though the latter has smaller script size and thus lower transaction cost.
Acknowledgements
This article is an extension of nChain patent WO2018189634, by Ying Chen now at Cambridge Cryptographic..
Watch: CoinGeek New York presentation, Smart Contracts & Computation on Bitcoin
New to blockchain? Check out CoinGeek’s Blockchain for Beginners section, the ultimate resource guide to learn more about blockchain technology.
