# Efficient Multi-Input Transaction Grinding for OP_CAT-based Bitcoin Covenants

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.

[1] We use python notation here: `my_array[-1]`

returns the last element of the array `my_array`

.