We have empirically demonstrated that any Turing machine can be simulated on Bitcoin and thus definitively proven it is Turing-complete¹. We have implemented a Turing machine that recognizes balanced parentheses and deployed it on the Bitcoin blockchain. Any other Turing machines can be simulated in the same way.
A Turing machine consists of the following components (simplified):
We have implemented ECDSA signature verification algorithm in Script. It can verify if an arbitrary message is signed by a private key corresponding to a given public key, while OP_CHECKSIG can only verify signatures when the message is the current spending transaction¹. Surprisingly, this is done without introducing any new opcode such as OP_DATASIGVERIFY (aka, OP_CHECKDATASIG) on BCH.
ECDSA is the algorithm used in Bitcoin for signature generation and verification. The verification algorithm is listed below.
We have implemented Schnorr signatures on BitCoin. It is the first and only known implementation without any changes to the original protocol¹.
Schnorr is an alternative algorithm to the ECDSA algorithm currently used for signatures in Bitcoin. One key advantage is that multiple signatures, either in one input or multiple inputs of the same transaction, can be aggregated into a single signature. There has been a lot of hype about Schnoor signatures on BTC, which requires enormous changes as BIP 340 details.
We have shown how to implement it, using just the original Bitcoin protocol. The full code to verify Schnorr signatures is listed below, using elliptic curve operations we released previously.
 The legal implication of using Schnorr signatures is out of the scope of this article.
We present a novel and efficient method for computing point addition and scalar multiplication on elliptic curve, within bitcoin Script. For point addition, we reduce a script size of more than 1MB to ~400 bytes.
For each i, each point Pi is represented by two coordinates (xi, yi). To compute P3 = P1 + P2, we use the following formula:
We present an efficient implementation of multisig with enhanced privacy, using a technique called tree signature. In contrast with the original tree signature¹, our implementation does not require any changes to the Bitcoin protocol.
In a standard M-of-N multisig, M signatures are needed to move funds. All N public keys have to be exposed on the blockchain. This quickly bloats Script size when N is big, for example, in a 1-of-100 multisig.
To solve this issue, tree signature organizes keys in a Merkle tree. Each leaf represents a specific combination of M keys of N. There are C(M, N)² leaves…
Merklized Abstract Syntax Tree MAST (aka, Merklized Alternative Script Trees) is a technique to compress Bitcoin smart contracts using Merkle tree. We have implemented MAST on Bitcoin SV. Different from all other implementations, ours leverages the original Bitcoin protocol, without any consensus change.
There are generally more than one way to spend coins locked in a Bitcoin smart contract. In sCrypt, each way is modelled as a public function, representing a conditional spending branch. For example, in contract TimeCommit, the contract can be unlocked either by Alice’s preimage and her signature, or by Alice and Bob’s signatures.
We present a novel way to develop a decentralized machine learning (ML) marketplace on Bitcoin. Anyone can outsource a machine learning task by publishing a smart contract with a reward attached. Anyone who submits the best performing model will receive the reward via a blockchain transaction, without going through a centralized authority.
Kaggle competitions are machine learning tasks made by Kaggle or other companies like Facebook and Microsoft. If you compete successfully, you can win monetary prizes, sometimes over a million dollars.
Similar to Kaggle competitions, ML competitions on Bitcoin consist of the following steps:
sCrypt does not support floating point natively, mainly due to the high overhead of implementing it (such as IEEE Floating Point Standard) using integral arithmetic in Bitcoin Script. However, there are many use cases where fractional numbers are indispensable. We provide two libraries to support such cases.
One simple way to represent a fractional number is storing a fixed number of digits of their fractional part, by scaling it with a fixed factor. For example, when you divide integer 1 by integer 2 in sCrypt, normally you get zero:
1 / 2 = 0
By scaling them both by 10…
We introduce a novel approach to call one smart contract from another. It is built upon a technique called OP_PUSH_TX. We illustrate the approach by letting one contract call another to solve a quadratic equation. It has been generalized and extensively used in projects such as Sensible Contract.
From the specification of sighash preimage, we can see each input in a transaction has a different sighash preimage. We also see their preimages overlap. Most notably, they share the same outputs (colored). The preimage of input0 and input1 both include output0 and output1 as highlighted below in an example transaction¹. …
We have implemented Rule 110 on Bitcoin. Similar to two-dimensional cellular automata (CA) Conway’s Game of Life, Rule 110, a one-dimensional CA, is also Turing-complete. By deduction, we have shown Bitcoin is Turing Complete, once again.
The Rule 110 cellular automaton is a 1-dimensional elementary CA, where a linear pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value and on those of its two neighbors. The Rule 110 has the following set of rules: