Access External Data from Bitcoin Smart Contracts
Oracles
For smart contracts, on Bitcoin or other blockchains, to be practical, they often need to access data from outside the blockchain, such as weather for an insurance contract or sports outcome for a betting contract. Running in an isolated sandbox, smart contracts are prohibited to initiate retrieval of external data for security considerations. They rely on third-party data providers, called oracle¹, to provide these data. This creates an integrity problem known as the Oracle problem. A digital signature is required to verify the authenticity and integrity of the data provided by known oracles.
We introduce an efficient way to verify and thus access any arbitrary data, onchain or off-chain, signed by an oracle inside Bitcoin smart contracts.
Rabin Signature
Rabin signature is an alternative digital signature algorithm (DSA) to ECDSA used in Bitcoin. The security of Rabin signature depends on the fact that calculating a modular square-root is as hard as integer factorisation.
Key Generation
Similar to RSA, key is generated by identifying two large primes p and q. The private key is combination (p, q) with the corresponding public key n = p * q.
Signing
A padding U is appended to the message m to be signed such that the hash h(m||U) is a quadratic residue modulo n. Signature is combination (S, U).
Verification
With signature (S, U), message m, and public key n, we can verify the signature by checking if the equation above holds.
As can be seen, Rabin signature has the beautiful asymmetry that signature generation is computationally expensive, but signature verification is computationally cheap. This property renders it extremely amenable to an onchain implementation, where only signature verification is needed. In principle, we can use ECDSA to verify signature, but it is many orders of magnitude more expensive³.
Implementation
Here is code for Rabin signature, including key generation, signature generation, and signature verification. We also implement it in sCrypt. The code is shown in its entirety below. Notice the core part is only about 10 lines of code and only involves basic algebraic and hashing operations. We only have to implement signature verification, since it is the only part to be done on chain. Also we demonstrate a generic technique to generate longer hashes, 512 bits in the example, by rehashing SHA256 hashes and concatenating them.
Conclusion
Thanks to Rabin signatures, we can embed arbitrary signed data inside a Bitcoin transaction and verify it efficiently on chain using existing Bitcoin script. Also the complexity and cost can be customized per application’s security requirements, which is more flexible than hardcoding a specific DSA at the consensus layer. If stronger security is desired, longer keys and hashes can simply be used. By allowing smart contracts to access external data, they become tremendously more powerful.
Acknowledgments
Thanks go to Owen Vaughan and Dr. Craig Wright of nChain for discovering Rabin Signatures’ usage in Bitcoin.
[1]: How to minimize required trusts in oracles, e.g., by leveraging multiple independent oracles, is beyond the scope of this article.
[2]: || is concatenation.
[3]: Actually we have implemented ECDSA signature verification in sCrypt and our measurement shows it is indeed in the order of a million-fold subsidy.
