Efficient multi-input transaction grinding for OP_CAT Bitcoin covenants

This post was first published on Medium.

In a previous post, we have implemented Bitcoin covenants using OP_CAT, based on this Schnorr trick. We can greatly simplify signature calculation (s) by choosing specific signing key and ephemeral key.

s = 1 + e

Bitcoin Script, more specifically OP_ADD, only works on 32-bit signed integer and thus cannot directly add 1 to e by using the following script, because e is a 256-bit integer. It is the SHA256 hash of the transaction data among other things.

<1> OP_ADD

The proposed workaround is to break e into two parts: the Least Significant Byte (e[-1])¹ and the rest (e_).

e = e_ || e[-1]
|| denotes concatenation, i.e., OP_CAT.

We keep changing the transaction till its hash ends in 1. This is akin to proof of work in Bitcoin mining, but with a negligible difficulty. Typically, we can malleate the nLockTime or nSeq field of a transaction, since slightly changing them generally do not affect the validity of the transaction. Then s is simply.

s = e_ || 2

The problem

This transaction grinding is blazingly fast, since each hashing try has 1/256 chance of success. It only takes 256 tries on average and completes in milliseconds on a personal computer. Problem arises when the transaction involves multiple inputs (N) using covenants.

To see why, note e value differs from input to input when computing signatures. That is why each input in a transaction has to be individually signed. An nLockTime value makes e for one input end with 1 may make it end with 5 for another input. The probability of finding a common nLockTime value that makes e’s in all inputs end with 1 is now

(1/256)^N

In many applications that require contract interaction and complex business logic, N could easily be 4 or 5. Now it could take minutes to finish the grinding. If N is even larger like 10, it is computationally infeasible.

Besides inefficiency, another issue is the limiting range of mutable fields. For example, nLocktime is only 32 bit long and can only support N up to 4. This issue cannot be circumvented if ASICs are used for the hashing.

The solution

To address this, we leverage Script’s ability to perform arithmetic on signed 32-bit integers. Instead of limiting e[-1] to a specific value like 1, we allow it to be in a much wider range.

If the range is extended to non-negative integers, e[-1] can be any integer other than 127, which causes overflows. Now we can use OP_ADD to calculate (e[-1] + 1)

<1> OP_ADD
s becomes
s = e_ || (e[-1] + 1)

The following sCrypt code demonstrates this process.

With this change, the probability of finding a valid nLockTime increases to

(127/256)^N ~= (1/2)^N

Even for N of 10, the grinding only takes less than a second.

Alternative

We can accelerate the grinding by further expanding e[-1]’s range to [-126, 126]. That is, we only exclude -127 and 127 to avoid underflows and overflows. Note integer is encoded using signed magnitude in Script. When we increment a negative integer by one, we actually have to do the following.

<-1> OP_ADD

To see why, let us look at e[-1] of 0x83, which is treated as -3 in Script. If we want to it to be 0x84 (interpreted as -4) after increment, we subtract 1 from it.

Now the success probability increases to

(254/256)^N

Full change can be found in this Github commit.

Watch: sCrypt wants to bring hackathon initiative to more people