# Efficient Multi-Input Transaction Grinding for OP\_CAT-based Bitcoin Covenants

**URL:** <https://delvingbitcoin.org/t/efficient-multi-input-transaction-grinding-for-op-cat-based-bitcoin-covenants/1080>\
**Category:** Implementation\
**Created:** [August 20, 2024, 9:27am UTC](https://delvingbitcoin.org/t/efficient-multi-input-transaction-grinding-for-op-cat-based-bitcoin-covenants/1080 "2024-08-20T09:27:09Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![sCrypt-ts](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/scrypt-ts/32/746_2.png) [@sCrypt-ts](https://delvingbitcoin.org/u/sCrypt-ts)\
**Post date:** [August 20, 2024, 9:27am UTC](https://delvingbitcoin.org/t/efficient-multi-input-transaction-grinding-for-op-cat-based-bitcoin-covenants/1080/1 "2024-08-20T09:27:09Z")

</div>

In a [previous post](https://scryptplatform.medium.com/trustless-ordinal-sales-using-op-cat-enabled-covenants-on-bitcoin-0318052f02b2), we have implemented Bitcoin covenants using OP\_CAT, based on [this Schnorr trick](https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html). 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.

 ![](https://delvingbitcoin.org/uploads/default/original/1X/8959f89ff9adeb3956a99871e74b7f6f3c05c91b.jpeg)

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.

```ts
@method()
static checkSHPreimage(shPreimage: SHPreimage): Sig {
    // Check e[-1] is in range.
    assert(shPreimage.eSuffix < 127n, 'e suffix not in range [0, 127)')

    const e = sha256(SigHashUtils.ePreimagePrefix + shPreimage.sigHash)
    assert(e == shPreimage._e + int2ByteString(shPreimage.eSuffix), 'invalid value of _e')

    const s = SigHashUtils.Gx + shPreimage._e + int2ByteString(shPreimage.eSuffix + 1n)
    
    ...
}

```

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](https://en.wikipedia.org/wiki/Signed_number_representations) 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.

```ts
@method()
static checkSHPreimage(shPreimage: SHPreimage): Sig {
    // Check e[-1] is in range.
    assert(
          shPreimage.eSuffix > -127n && shPreimage.eSuffix < 127n, 
          'e suffix not in range [-126, 127)'
    )

    const e = sha256(SigHashUtils.ePreimagePrefix + shPreimage.sigHash)
    assert(e == shPreimage._e + int2ByteString(shPreimage.eSuffix), 'invalid value of _e')

    // If e[-1] is negative, we have to substract. (e.g. 0x83 - 0x01 = 0x84)
    const sDelta: bigint = shPreimage.eSuffix < 0n ? -1n : 1n;
    const s = SigHashUtils.Gx + shPreimage._e + int2ByteString(shPreimage.eSuffix + sDelta)

    ...
}

```

Now the success probability increases to

> _**(254/256)^N**_

Full change can be found in [this Github commit](https://github.com/sCrypt-Inc/cat-contracts/commit/3f48ae33da08046a3c2121083031ef523dd7aef9).

[1] We use python notation here: `my_array[-1]` returns the last element of the array `my_array`.

---

<div class="post-metadata">

**Author:** ![benthecarman](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/benthecarman/32/1098_2.png) [@benthecarman](https://delvingbitcoin.org/u/benthecarman)\
**Post date:** [September 26, 2024, 7:49am UTC](https://delvingbitcoin.org/t/efficient-multi-input-transaction-grinding-for-op-cat-based-bitcoin-covenants/1080/2 "2024-09-26T07:49:09Z")

</div>

Instead of using \<1/-1\> OP\_ADD, it’d be more efficient to just push the last byte and last byte +1 in the witness, saves a byte and removes the need to handle if its 1 or -1

---

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [September 26, 2024, 12:59pm UTC](https://delvingbitcoin.org/t/efficient-multi-input-transaction-grinding-for-op-cat-based-bitcoin-covenants/1080/3 "2024-09-26T12:59:34Z")

</div>

If you have `<x> <y>` on the stack, you can verify that `y=x+1` with:

```auto
2DUP
1 SWAP OVER CAT TOALTSTACK CAT
1 ADD FROMALTSTACK EQUALVERIFY

```

The process is just to append a `0x01` byte to both suffixes, to ensure neither value is treated as negative or non-minimal (`0x00` or `0x80` or a multibyte string ending in `0x00` or `0x0080`), then increment, then check. The suffix can be one, two or three bytes this way, so this only doesn’t work if the smaller hash ends with `FFFFFF`, but that’s a one-in-16-million chance, instead of 1-in-2 or 255-in-256.