# CIP-0122

## Abstract

We describe the semantics of a set of logical operations for Plutus
`BuiltinByteString`

s. Specifically, we provide descriptions for:

- Bitwise logical AND, OR, XOR and complement;
- Reading a bit value at a given index;
- Setting bits value at given indices; and
- Replicating a byte a given number of times.

As part of this, we also describe the bit ordering within a `BuiltinByteString`

,
and provide some laws these operations should obey.

## Motivation: why is this CIP necessary?

Bitwise operations, both over fixed-width and variable-width blocks of bits,
have a range of uses, including data structures (especially
succinct ones) and cryptography. Currently,
operations on individual bits in Plutus Core are difficult, or outright
impossible, while also keeping within the tight constraints required onchain.
While it is possible to some degree to work with individual *bytes* over
`BuiltinByteString`

s, this isn't sufficient, or efficient, when bit
maniputations are required.

To demonstrate where bitwise operations would allow onchain possibilities that are currently either impractical or impossible, we give the following use cases.

### Case 1: integer set

An *integer set* (also known as a bit set, bitmap, or bitvector) is a
succinct data structure for representing a set of
numbers in a pre-defined range $[0, n)$ for some $n in mathbb{N}$. The
structure supports the following operations:

- Construction given a fixed number of elements, as well as the bound $n$.
- Construction of the empty set (contains no elements) and the universe (contains all elements).
- Set union, intersection, complement and difference (symmetric and asymmetric).
- Membership testing for a specific element.
- Inserting or removing elements.

These structures have a range of uses. In addition to being used as sets of bounded natural numbers, an integer set could also represent an array of Boolean values. These have a range of applications, mostly as 'backends' for other, more complex structures. Furthermore, by using some index arithmetic, integer sets can also be used to represent binary matrices (in any number of dimensions), which have an even wider range of uses:

- Representations of graphs in adjacency-matrix form
- Checking the rules for a game of Go
- FSM representation
- Representation of an arbitrary binary relation between finite sets

The succinctness of the integer set (and the other succinct data structures it enables) is particularly valuable on-chain, due to the limited transaction size and memory available.

Typically, such a structure would be represented as a packed array of bytes
(similar to the Haskell `ByteString`

). Essentially, given a bound $n$, the
packed array has a length in bytes large enough to contain at least $n$ bits,
with a bit at position $i$ corresponding to the value $i in mathbb{N}$. This
representation ensures the succinctness of the structure (at most 7 bits of
overhead are required if $n = 8k + 1$ for some $k in mathbb{N}$), and
also allows all the above operations to be implemented efficiently:

- Construction given a fixed number of elements and the bound $n$ involves allocating the packed array, then modifying some bits to be set.
- Construction of the empty set is a packed array where every byte is
`0x00`

, while the universe is a packed array where every byte is`0xFF`

. - Set union is bitwise OR over both arguments.
- Set intersection is bitwise AND over both arguments.
- Set complement is bitwise complement over the entire packed array.
- Symmetric set difference is bitwise XOR over both arguments; asymmetric set difference can be defined using a combination of bitwise complement and bitwise OR.
- Membership testing is checking whether a bit is set.
- Inserting an element is setting the corresponding bit.
- Removing an element is clearing the corresponding bit.

Given that this is a packed representation, these operations can be implemented very efficiently by relying on the cache-friendly properties of packed array traversals, as well as making use of optimized routines available in many languages. Thus, this structure can be used to efficiently represent sets of numbers in any bounded range (as ranges not starting from $0$ can be represented by storing an offset), while also being minimal in space usage.

Currently, such a structure cannot be easily implemented in Plutus Core while
preserving the properties described above. The two options using existing
primitives are either to use `[BuiltinInteger]`

, or to mimic the above
operations over `BuiltinByteString`

. The first of these is not space *or*
time-efficient: each `BuiltinInteger`

takes up multiple machine words of space,
and the list overheads introduced are linear in the number of items stored,
destroying succinctness; membership testing, insertion and removal require
either maintaining an ordered list or forcing linear scans for at least some
operations, which are inefficient over lists; and 'bulk' operations like union,
intersection and complement become very difficult and time-consuming. The second
is not much better: while we preserve succinctness, there is no easy way to
access individual bits, only bytes, which would require a division-remainder
loop for each such operation, with all the overheads this imposes; intersection,
union and symmetric difference would have to be simulated byte-by-byte,
requiring large lookup tables or complex conditional logic; and construction
would require immense amounts of copying and tricky byte construction logic.
While it is not outright impossible to make such a structure using current
primitives, it would be so impractical that it could never see real use.

Furthermore, for sparse (or dense) integer sets (that is, where either most elements in the range are absent or present respectively), a range of compression techniques have been developed. All of these rely on bitwise operations to achieve their goals, and can potentially yield significant space savings in many cases. Given the limitations onchain that we have to work within, having such techniques available to implementers would be a huge potential advantage.

### Case 2: hashing

Hashing, that is, computing a fixed-length 'fingerprint' or 'digest' of a variable-length input (typically viewed as binary) is a common task required in a range of applications. Most notably, hashing is a key tool in cryptographic protocols and applications, either in its own right, or as part of a larger task. The value of such functionality is such that Plutus Core already contains primitives for certain hash functions, specifically two variants of SHA256 and BLAKE2b. At the same time, hash functions choices are often determined by protocol or use case, and providing individual primitives for every possible hash function is not a scalable choice. It is much preferrable to give necessary tools to implement such functionality to users of Plutus (Core), allowing them to use whichever hash function(s) their applications require.

As an example, we consider the Argon2 family of hash functions. In order to implement any variant of this family requires the following operations:

- Conversion of numbers to bytes
- Bytestring concatenation
- BLAKE2b hashing
- Floor division
- Indexing bytes in a bytestring
- Logical XOR

Operations 1 to 5 are already provided by Plutus Core (with 1 being included in
CIP-121); however, without logical XOR, no function in the
Argon2 family could be implemented. While in theory, it could be simulated with
what operations already exist, much as with Case 1, this would be impractical at
best, and outright impossible at worst, due to the severe limits imposed
on-chain. This is particularly the case here, as all Argon2 variants call
logical XOR in a loop, whose step count is defined by *multiple* user-specified
(or protocol-specified) parameters.

We observe that this requirement for logical XOR is not unique to the Argon2 family of hash functions. Indeed, logical XOR is widely used for a variety of cryptographic applications, as it is a low-cost mixing function that happens to be self-inverting, as well as preserving randomness (that is, a random bit XORed with a non-random bit will give a random bit).

## Specification

We describe the proposed operations in several stages. First, we specify a
scheme for indexing individual bits (rather than whole bytes) in a
`BuiltinByteString`

. We then specify the semantics of each operation, as well as
giving costing expectations and some examples. Lastly, we provide some laws that
any implementation of these operations is expected to obey.

### Bit indexing scheme

We begin by observing that a `BuiltinByteString`

is a packed array of bytes
(that is, `BuiltinInteger`

s in the range $[0, 255]$) according to the API
provided by existing Plutus Core primitives. In particular, we have the ability
to access individual bytes by index as a primitive operation. Thus, we can view
a `BuiltinByteString`

as an indexed collection of bytes; for any
`BuiltinByteString`

$b$ of length $n$, and any $i in 0, 1, ldots, n - 1$, we
define $b{i}$ as the byte at index $i$ in $b$, as defined by the
`indexByteString`

primitive. In essence, for any `BuiltinByteString`

of
length `n`

, we have *byte* indexes as follows:

`| Index | 0 | 1 | ... | n - 1 |`

|-------|----|----| ... |----------|

| Byte | w0 | w1 | ... | w(n - 1) |

To view a `BuiltinByteString`

as an indexed collection of *bits*, we must first
consider the bit ordering within a byte. Suppose $i in 0, 1, ldots, 7$ is an
index into a byte $w$. We say that the bit at $i$ in $w$ is *set* when

$$ left lfloor frac{w}{2^{i}} right rfloor mod 2 equiv 1 $$

Otherwise, the bit at $i$ in $w$ is *clear*. We define $w[i]$ to be $1$ when
the bit at $i$ in $w$ is set, and $0$ otherwise; this is the *value* at index
$i$ in $w$.

For example, consider the byte represented by the `BuiltinInteger`

42. By the
above scheme, we have the following:

Bit index | Set or clear? |
---|---|

$0$ | Clear |

$1$ | Set |

$2$ | Clear |

$3$ | Set |

$4$ | Clear |

$5$ | Set |

$6$ | Clear |

$7$ | Clear |

Put another way, we can view $w[i] = 1$ to mean that the $(i + 1)$ th least significant
digit in $w$'s binary representation is $1$, and likewise, $w[i] = 0$ would mean
that the $i$th least significant digit in $w$'s binary representation is $0$.
Continuing with the above example, $42$ is represented in binary as `00101010`

;
we can see that the second-least-significant, fourth-least-significant, and
sixth-least-significant digits are `1`

, and all the others are zero. This
description mirrors the way bytes are represented on machine architectures.

We now extend the above scheme to `BuiltinByteString`

s. Let $b$ be a
`BuiltinByteString`

whose length is $n$, and let $i in 0, 1, ldots, 8 cdot n - 1$.
For any $j in 0, 1, ldots, n - 1$, let $j^{prime} = n - j - 1$. We say that the bit
at $i$ in $b$ is set if

$$ bleft{left(leftlfloor frac{i}{8} rightrfloorright)^{prime}right}[imod 8] = 1 $$

We define the bit at $i$ in $b$ being clear analogously. Similarly to bits in a
byte, we define $b[i]$ to be $1$ when the bit at $i$ in $b$ is set, and $0$
otherwise; similarly to bytes, we term this the *value* at index $i$ in $b$.

As an example, consider the `BuiltinByteString`

`[42, 57, 133]`

: that is, the
`BuiltinByteString`

$b$ such that $b{0} = 42$, $b{1} = 57$ and $b{2}
= 133$. We observe that the range of 'valid' bit indexes $i$ into $b$ is in
$[0, 3 cdot 8 - 1 = 23]$. Consider $i = 4$; by the definition above, this
corresponds to the *byte* index 2, as $leftlfloorfrac{4}{8}rightrfloor =
0$, and $3 - 0 - 1 = 2$ (as $b$ has length $3$). Within the byte $133$, this
means we have $leftlfloorfrac{133}{2^4}rightrfloor mod 2 equiv 0$. Thus,
$b[4] = 0$. Consider instead the index $i = 19$; by the definition above, this
corresponds to the *byte* index 0, as $leftlfloorfrac{19}{8}rightrfloor =
2$, and $3 - 2 - 1 = 0$. Within the byte $42$, this means we have
$leftlfloorfrac{42}{2^3}rightrfloormod 2 equiv 1$. Thus, $b[19] = 1$.

Put another way, our *byte* indexes run 'the opposite way' to our *bit* indexes.
Thus, for any `BuiltinByteString`

of length $n$, we have *bit* indexes relative
*byte* indexes as follows:

`| Byte index | 0 | 1 | ... | n - 1 |`

|------------|--------------------------------|----| ... |-------------------------------|

| Byte | w0 | w1 | ... | w(n - 1) |

|------------|--------------------------------|----| ... |-------------------------------|

| Bit index | 8n - 1 | 8n - 2 | ... | 8n - 8 | ... | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

### Operation semantics

We describe precisely the operations we intend to implement, and their semantics. These operations will have the following signatures:

`bitwiseLogicalAnd :: BuiltinBool -> BuiltinByteString -> BuiltinByteString -> BuiltinByteString`

`bitwiseLogicalOr :: BuiltinBool -> BuiltinByteString -> BuiltinByteString -> BuiltinByteString`

`bitwiseLogicalXor :: BuiltinBool -> BuiltinByteString -> BuiltinByteString -> BuiltinByteString`

`bitwiseLogicalComplement :: BuiltinByteString -> BuiltinByteString`

`readBit :: BuiltinByteString -> BuiltinInteger -> BuiltinBool`

`writeBits :: BuiltinByteString -> [(BuiltinInteger, BuiltinBool)] -> BuiltinByteString`

`replicateByteString :: BuiltinInteger -> BuiltinInteger -> BuiltinByteString`

We assume the following costing, for both memory and execution time:

Operation | Cost |
---|---|

`bitwiseLogicalAnd` | Linear in longest `BuiltinByteString` argument |

`bitwiseLogicalOr` | Linear in longest `BuiltinByteString` argument |

`bitwiseLogicalXor` | Linear in longest `BuiltinByteString` argument |

`bitwiseLogicalComplement` | Linear in `BuiltinByteString` argument |

`readBit` | Constant |

`writeBits` | Additively linear in both arguments |

`replicateByteString` | Linear in the value of the first argument |

#### Padding versus truncation semantics

For the binary logical operations (that is, `bitwiseLogicalAnd`

,
`bitwiseLogicalOr`

and `bitwiseLogicalXor`

), the we have two choices of
semantics when handling `BuiltinByteString`

arguments of different lengths. We
can either produce a result whose length is the *minimum* of the two arguments
(which we call *truncation semantics*), or produce a result whose length is the
*maximum* of the two arguments (which we call *padding semantics*). As these can
both be useful depending on context, we allow both, controlled by a
`BuiltinBool`

flag, on all the operations listed above.

In cases where we have arguments of different lengths, in order to produce a
result of the appropriate lengths, one of the arguments needs to be either
padded or truncated. Let `short`

and `long`

refer to the `BuiltinByteString`

argument of shorter length, and of longer length, respectively. The following
table describes what happens to the arguments before the operation:

Semantics | `short` | `long` |
---|---|---|

Padding | Pad at high byte indexes | Unchanged |

Truncation | Unchanged | Truncate high byte indexes |

We pad with different bytes depending on operation: for `bitwiseLogicalAnd`

, we
pad with `0xFF`

, while for `bitwiseLogicalOr`

and `bitwiseLogicalXor`

we pad
with `0x00`

instead. We refer to arguments so changed as
*semantics-modified* arguments.

For example, consider the `BuiltinByteString`

s `x = [0x00, 0xF0, 0xFF]`

and ```
y =
[0xFF, 0xF0]
```

. The following table describes what the semantics-modified
versions of these arguments would become for each operation and each semantics:

Operation | Semantics | `x` | `y` |
---|---|---|---|

`bitwiseLogicalAnd` | Padding | `[0x00, 0xF0, 0xFF]` | `[0xFF, 0xF0, 0xFF]` |

`bitwiseLogicalAnd` | Truncation | `[0x00, 0xF0]` | `[0xFF, 0xF0]` |

`bitwiseLogicalOr` | Padding | `[0x00, 0xF0, 0xFF]` | `[0xFF, 0xF0, 0x00]` |

`bitwiseLogicalor` | Truncation | `[0x00, 0xF0]` | `[0xFF, 0xF0]` |

`bitwiseLogicalXor` | Padding | `[0x00, 0xF0, 0xFF]` | `[0xFF, 0xF0, 0x00]` |

`bitwiseLogicalXor` | Truncation | `[0x00, 0xF0]` | `[0xFF, 0xF0]` |

Based on the above, we observe that under padding semantics, the result of any of the listed operations would have a byte length of 3, while under truncation semantics, the result would have a byte length of 2 instead.

`bitwiseLogicalAnd`

`bitwiseLogicalAnd`

takes three arguments; we name and describe them below.

- Whether padding semantics should be used. If this argument is
`False`

, truncation semantics are used instead. This is the*padding semantics argument*, and has type`BuiltinBool`

. - The first input
`BuiltinByteString`

. This is the*first data argument*. - The second input
`BuiltinByteString`

. This is the*second data argument*.

Let $b_1, b_2$ refer to the semantics-modified first data argument and
semantics-modified second data argument respectively, and let $n$ be either of
their lengths in bytes; see the
section on padding versus truncation semantics
for the exact specification of this. Let the result of `bitwiseLogicalAnd`

, given
$b_1, b_2$ and some padding semantics argument, be $b_r$, also of length $n$
in bytes. We use $b_1{i}$ to refer to the byte at index $i$ in $b_1$ (and
analogously for $b_2$, $b_r$); see the section on the bit indexing
scheme for the exact specification of this.

For all $i in 0, 1, ldots, n - 1$, we have $b_r{i} = b_0{i} text{ }& text{ } b_1{i}$, where $&$ refers to a bitwise AND.

Some examples of the intended behaviour of `bitwiseLogicalAnd`

follow. For
brevity, we write `BuiltinByteString`

literals as lists of hexadecimal values.

`-- truncation semantics`

bitwiseLogicalAnd False [] [0xFF] => []

bitwiseLogicalAnd False [0xFF] [] => []

bitwiseLogicalAnd False [0xFF] [0x00] => [0x00]

bitwiseLogicalAnd False [0x00] [0xFF] => [0x00]

bitwiseLogicalAnd False [0x4F, 0x00] [0xF4] => [0x44]

-- padding semantics

bitwiseLogicalAnd True [] [0xFF] => [0xFF]

bitwiseLogicalAnd True [0xFF] [] => [0xFF]

bitwiseLogicalAnd True [0xFF] [0x00] => [0x00]

bitwiseLogicalAnd True [0x00] [0xFF] => [0x00]

bitwiseLogicalAnd True [0x4F, 0x00] [0xF4] => [0x44, 0x00]

`bitwiseLogicalOr`

`bitwiseLogicalOr`

takes three arguments; we name and describe them below.

- Whether padding semantics should be used. If this argument is
`False`

, truncation semantics are used instead. This is the*padding semantics argument*, and has type`BuiltinBool`

. - The first input
`BuiltinByteString`

. This is the*first data argument*. - The second input
`BuiltinByteString`

. This is the*second data argument*.

Let $b_1, b_2$ refer to the semantics-modified first data argument and
semantics-modified second data argument respectively, and let $n$ be either of
their lengths in bytes; see the
section on padding versus truncation semantics
for the exact specification of this. Let the result of `bitwiseLogicalOr`

, given
$b_1, b_2$ and some padding semantics argument, be $b_r$, also of length $n$
in bytes. We use $b_1{i}$ to refer to the byte at index $i$ in $b_1$ (and
analogously for $b_2$, $b_r$); see the section on the bit indexing
scheme for the exact specification of this.

For all $i in 0, 1, ldots, n - 1$, we have $b_r{i} = b_0{i} text{ } | text{ } b_1{i}$, where $|$ refers to a bitwise OR.

`-- truncation semantics`

bitwiseLogicalOr False [] [0xFF] => []

bitwiseLogicalOr False [0xFF] [] => []

bitwiseLogicalOr False [0xFF] [0x00] => [0xFF]

bitwiseLogicalOr False [0x00] [0xFF] => [0xFF]

bitwiseLogicalOr False [0x4F, 0x00] [0xF4] => [0xFF]

-- padding semantics

bitwiseLogicalOr True [] [0xFF] => [0xFF]

bitwiseLogicalOr True [0xFF] [] => [0xFF]

bitwiseLogicalOr True [0xFF] [0x00] => [0xFF]

bitwiseLogicalOr True [0x00] [0xFF] => [0xFF]

bitwiseLogicalOr True [0x4F, 0x00] [0xF4] => [0xFF, 0x00]

`bitwiseLogicalXor`

`bitwiseLogicalXor`

takes three arguments; we name and describe them below.

- Whether padding semantics should be used. If this argument is
`False`

, truncation semantics are used instead. This is the*padding semantics argument*, and has type`BuiltinBool`

. - The first input
`BuiltinByteString`

. This is the*first data argument*. - The second input
`BuiltinByteString`

. This is the*second data argument*.

Let $b_1, b_2$ refer to the semantics-modified first data argument and
semantics-modified second data argument respectively, and let $n$ be either of
their lengths in bytes; see the
section on padding versus truncation semantics
for the exact specification of this. Let the result of `bitwiseLogicalXor`

, given
$b_1, b_2$ and some padding semantics argument, be $b_r$, also of length $n$
in bytes. We use $b_1{i}$ to refer to the byte at index $i$ in $b_1$ (and
analogously for $b_2$, $b_r$); see the section on the bit indexing
scheme for the exact specification of this.

For all $i in 0, 1, ldots, n - 1$, we have $b_r{i} = b_0{i} text{ } wedge text{ } b_1{i}$, where $wedge$ refers to a bitwise XOR.

Some examples of the intended behaviour of `bitwiseLogicalXor`

follow. For
brevity, we write `BuiltinByteString`

literals as lists of hexadecimal values.

`-- truncation semantics`

bitwiseLogicalXor False [] [0xFF] => []

bitwiseLogicalXor False [0xFF] [] => []

bitwiseLogicalXor False [0xFF] [0x00] => [0xFF]

bitwiseLogicalXor False [0x00] [0xFF] => [0xFF]

bitwiseLogicalXor False [0x4F, 0x00] [0xF4] => [0xBB]

-- padding semantics

bitwiseLogicalOr True [] [0xFF] => [0xFF]

bitwiseLogicalOr True [0xFF] [] => [0xFF]

bitwiseLogicalOr True [0xFF] [0x00] => [0xFF]

bitwiseLogicalOr True [0x00] [0xFF] => [0xFF]

bitwiseLogicalOr True [0x4F, 0x00] [0xF4] => [0xBB, 0x00]

`bitwiseLogicalComplement`

`bitwiseLogicalComplement`

takes a single argument, of type `BuiltinByteString`

;
let $b$ refer to that argument, and $n$ its length in bytes. Let $b_r$ be
the result of `bitwiseLogicalComplement`

; its length in bytes is also $n$. We
use $b[i]$ to refer to the value at index $i$ of $b$ (and analogously for $b_r$);
see the section on the bit indexing scheme for the exact
specification of this.

For all $i in 0, 1, ldots , 8 cdot n - 1$, we have

$$ b_r[i] = begin{cases} 0 & text{if } b[i] = 1 1 & text{otherwise} end{cases} $$

Some examples of the intended behaviour of `bitwiseLogicalComplement`

follow. For
brevity, we write `BuiltinByteString`

literals as lists of hexadecimal values.

`bitwiseLogicalComplement [] => []`

bitwiseLogicalComplement [0x0F] => [0xF0]

bitwiseLogicalComplement [0x4F, 0xF4] => [0xB0, 0x0B]

`readBit`

`readBit`

takes two arguments; we name and describe them below.

- The
`BuiltinByteString`

in which the bit we want to read can be found. This is the*data argument*. - A bit index into the data argument, of type
`BuiltinInteger`

. This is the*index argument*.

Let $b$ refer to the data argument, of length $n$ in bytes, and let $i$ refer to the index argument. We use $b[i]$ to refer to the value at index $i$ of $b$; see the section on the bit indexing scheme for the exact specification of this.

If $i error

readBit [] 345 => error

-- Negative indexes fail readBit [] (-1) => error

readBit [0xFF] (-1) => error

-- Indexing reads 'from the end' readBit [0xF4] 0 => False

readBit [0xF4] 1 => False

readBit [0xF4] 2 => True

readBit [0xF4] 3 => False

readBit [0xF4] 4 => True

readBit [0xF4] 5 => True

readBit [0xF4] 6 => True

readBit [0xF4] 7 => True

-- Out-of-bounds indexes fail readBit [0xF4] 8 => error

readBit [0xFF, 0xF4] 16 => error

-- Larger indexes read backwards into the bytes from the end readBit [0xF4, 0xFF] 10 => False

#### `writeBits`

`writeBits` takes two arguments: we name and describe them below.

1. The `BuiltinByteString` in which we want to change some bits. This is the

_data argument_.

2. A list of index-value pairs, indicating which positions in the data argument

should be changed to which value. This is the _change list argument_. Each

index has type `BuiltinInteger`, while each value has type `BuiltinBool`.

Let $b$ refer to the data argument of length $n$ in bytes. We define `writeBits`

recursively over the structure of the change list argument. Throughout, we use

$b_r$ to refer to the result of `writeBits`, whose length is also $n$. We use

$b[i]$ to refer to the value at index $i$ of $b$ (and analogously, $b_r$); see

the [section on the bit indexing scheme](#bit-indexing-scheme) for the exact

specification of this.

If the change list argument is empty, we return the data argument unchanged.

Otherwise, let $(i, v)$ be the head of the change list argument, and $ell$ its

tail. If $i error

-- Irrespective of index

writeBits [] [(15, False)] => error

-- And value

writeBits [] [(0, True)] => error

-- And multiplicity

writeBits [] [(0, False), (1, False)] => error

-- Negative indexes fail

writeBits [0xFF] [((-1), False)] => error

-- Even when mixed with valid ones

writeBits [0xFF] [(0, False), ((-1), True)] => error

-- In any position

writeBits [0xFF] [((-1), True), (0, False)] => error

-- Out-of-bounds indexes fail

writeBits [0xFF] [(8, False)] => error

-- Even when mixed with valid ones

writeBits [0xFF] [(1, False), (8, False)] => error

-- In any position

writeBits [0xFF] [(8, False), (1, False)] => error

-- Bits are written 'from the end'

writeBits [0xFF] [(0, False)] => [0xFE]

writeBits [0xFF] [(1, False)] => [0xFD]

writeBits [0xFF] [(2, False)] => [0xFB]

writeBits [0xFF] [(3, False)] => [0xF7]

writeBits [0xFF] [(4, False)] => [0xEF]

writeBits [0xFF] [(5, False)] => [0xDF]

writeBits [0xFF] [(6, False)] => [0xBF]

writeBits [0xFF] [(7, False)] => [0x7F]

-- True value sets the bit

writeBits [0x00] [(5, True)] => [0x20]

-- False value clears the bit

writeBits [0xFF] [(5, False)] => [0xDF]

-- Larger indexes write backwards into the bytes from the end

writeBits [0xF4, 0xFF] [(10, False)] => [0xF0, 0xFF]

-- Multiple items in a change list apply cumulatively

writeBits [0xF4, 0xFF] [(10, False), (1, False)] => [0xF0, 0xFD]

writeBits (writeBits [0xF4, 0xFF] [(10, False)]) [(1, False)] => [0xF0, 0xFD]

-- Order within a change list is unimportant among unique indexes

writeBits [0xF4, 0xFF] [(1, False), (10, False)] => [0xF0, 0xFD]

-- But _is_ important for identical indexes

writeBits [0x00, 0xFF] [(10, True), (10, False)] => [0x00, 0xFF]

writeBits [0x00, 0xFF] [(10, False), (10, True)] => [0x04, 0xFF]

-- Setting an already set bit does nothing

writeBits [0xFF] [(0, True)] => [0xFF]

-- Clearing an already clear bit does nothing

writeBits [0x00] [(0, False)] => [0x00]

`replicateByteString`

`replicateByteString`

takes two arguments; we name and describe them below.

- The desired result length, of type
`BuiltinInteger`

. This is the*length argument*. - The byte to place at each position in the result, represented as a
`BuiltinInteger`

(corresponding to the unsigned integer this byte encodes). This is the*byte argument*.

Let $n$ be the length argument, and $w$ the byte argument. If $n 255$, then `replicateByteString`

fails. In this
case, the resulting error message must specify *at least* the following
information:

- That
`replicateByteString`

failed due to the byte argument not being a valid byte; and - What
`BuiltinInteger`

was passed as the byte argument.

Otherwise, let $b$ be the result of `replicateByteString`

, and let $b{i}$ be the
byte at position $i$ of $b$, as per the section describing the bit indexing
scheme. We have:

- The length (in bytes) of $b$ is $n$; and
- For all $i in 0, 1, ldots, n - 1$, $b{i} = w$.

Some examples of the intended behaviour of `replicateByteString`

follow. For
brevity, we write `BuiltinByteString`

literals as lists of hexadecimal values.

`-- Replicating a negative number of times fails`

replicateByteString (-1) 0 => error

-- Irrespective of byte argument

replicateByteString (-1) 3 => error

-- Out-of-bounds byte arguments fail

replicateByteString 1 (-1) => error

replicateByteString 1 256 => error

-- Irrespective of length argument

replicateByteString 4 (-1) => error

replicateByteString 4 256 => error

-- Length of result matches length argument, and all bytes are the same

replicateByteString 0 0xFF => []

replicateByteString 4 0xFF => [0xFF, 0xFF, 0xFF, 0xFF]

### Laws

#### Binary operations

We describe laws for all three operations that work over two
`BuiltinByteStrings`

, that is, `bitwiseLogicalAnd`

, `bitwiseLogicalOr`

and
`bitwiseLogicalXor`

, together, as many of them are similar (and related). We
describe padding semantics and truncation semantics laws, as they are slightly
different.

All three operations above, under both padding and truncation semantics, are commutative semigroups. Thus, we have:

`bitwiseLogicalAnd s x y = bitwiseLogicalAnd s y x`

bitwiseLogicalAnd s x (bitwiseLogicalAnd s y z) = bitwiseLogicalAnd s

(bitwiseLogicalAnd s x y) z

-- and the same for bitwiseLogicalOr and bitwiseLogicalXor

Note that the semantics (designated as `s`

above) must be consistent in order
for these laws to hold. Furthermore, under padding semantics, all the above
operations are commutative monoids:

`bitwiseLogicalAnd True x "" = bitwiseLogicalAnd True "" x = x`

-- and the same for bitwiseLogicalOr and bitwiseLogicalXor

Under truncation semantics, `""`

(that is, the empty `BuiltinByteString`

) acts
instead as an absorbing element:

`bitwiseLogicalAnd False x "" = bitwiseLogicalAnd False "" x = ""`

-- and the same for bitwiseLogicalOr and bitwiseLogicalXor

`bitwiseLogicalAnd`

and `bitwiseLogicalOr`

are also semilattices,
due to their idempotence:

`bitwiseLogicalAnd s x x = x`

-- and the same for bitwiseLogicalOr

`bitwiseLogicalXor`

is instead involute:

`bitwiseLogicalXor s x (bitwiseLogicalXor s x x) = bitwiseLogicalXor s`

(bitwiseLogicalXor s x x) x = x

Additionally, under padding semantics, `bitwiseLogicalAnd`

and
`bitwiseLogicalOr`

are self-distributive:

`bitwiseLogicalAnd True x (bitwiseLogicalAnd True y z) = bitwiseLogicalAnd True`

(bitwiseLogicalAnd True x y) (bitwiseLogicalAnd True x z)

bitwiseLogicalAnd True (bitwiseLogicalAnd True x y) z = bitwiseLogicalAnd True

(bitwiseLogicalAnd True x z) (bitwiseLogicalAnd True y z)

-- and the same for bitwiseLogicalOr

Under truncation semantics, `bitwiseLogicalAnd`

is only left-distributive over
itself, `bitwiseLogicalOr`

and `bitwiseLogicalXor`

:

`bitwiseLogicalAnd False x (bitwiseLogicalAnd False y z) = bitwiseLogicalAnd`

False (bitwiseLogicalAnd False x y) (bitwiseLogicalAnd False x z)

bitwiseLogicalAnd False x (bitwiseLogicalOr False y z) = bitwiseLogicalOr False

(bitwiseLogicalAnd False x y) (bitwiseLogicalAnd False x z)

bitwiseLogicalAnd False x (bitwiseLogicalXor False y z) = bitwiseLogicalXor

False (bitwiseLogicalAnd False x y) (bitwiseLogicalAnd False x z)

`bitwiseLogicalOr`

under truncation semantics is left-distributive over itself
and `bitwiseLogicalAnd`

:

`bitwiseLogicalOr False x (bitwiseLogicalOr False y z) = bitwiseLogicalOr False`

(bitwiseLogicalOr False x y) (bitwiseLogicalOr False x z)

bitwiseLogicalOr False x (bitwiseLogicalAnd False y z) = bitwiseLogicalAnd False

(bitwiseLogicalOr False x y) (bitwiseLogicalOr False x z)

If the first and second data arguments to these operations have the same length, these operations satisfy several additional laws. We describe these briefly below, with the added note that, in this case, padding and truncation semantics coincide:

`bitwiseLogicalAnd`

and`bitwiseLogicalOr`

form a bounded lattice`bitwiseLogicalAnd`

is distributive over itself,`bitwiseLogicalOr`

and`bitwiseLogicalXor`

`bitwiseLogicalOr`

is distributive over itself and`bitwiseLogicalAnd`

We do not specify these laws here, as they do not hold in general. At the same time, we expect that any implementation of these operations will be subject to these laws.

`bitwiseLogicalComplement`

The main law of `bitwiseLogicalComplement`

is involution:

`bitwiseLogicalComplement (bitwiseLogicalComplement x) = x`

In combination with `bitwiseLogicalAnd`

and `bitwiseLogicalOr`

,
`bitwiseLogicalComplement`

gives rise to the famous De Morgan laws, irrespective of semantics:

`bitwiseLogicalComplement (bitwiseLogicalAnd s x y) = bitwiseLogicalOr s`

(bitwiseLogicalComplement x) (bitwiseLogicalComplement y)

bitwiseLogicalComplement (bitwiseLogicalOr s x y) = bitwiseLogicalAnd s

(bitwiseLogicalComplement x) (bitwiseLogicalComplement y)

For `bitwiseLogicalXor`

, we instead have (again, irrespective of semantics):

`bitwiseLogicalXor s x (bitwiseLogicalComplement x) = x`

#### Bit reading and modification

Throughout, we assume any index arguments to be 'in-bounds'; that is, all the index arguments used in the statements of any law are such that the operation they are applied to wouldn't produce an error.

The first law of `writeBits`

is similar to the set-twice law of
lenses:

`writeBits bs [(i, b1), (i, b2)] = writeBits bs [(i, b2)]`

Together with `readBit`

, we obtain the remaining two analogues to the lens
laws:

`-- writing to an index, then reading from that index, gets you what you wrote`

readBit (writeBits bs [(i, b)]) i = b

-- if you read from an index, then write that value to that same index, nothing

-- happens

writeBits bs [(i, readBit bs i)] = bs

Furthermore, given a fixed data argument, `writeBits`

acts as a monoid
homomorphism lists under concatenation to functions:

`writeBits bs [] = bs`

writeBits bs (is <> js) = writeBits (writeBits bs is) js

`replicateByteString`

Given a fixed byte argument, `replicateByteString`

acts as a monoid
homomorphism from natural numbers under addition to
`BuiltinByteString`

s under concatenation:

`replicateByteString 0 w = ""`

replicateByteString (n + m) w = replicateByteString n w <> replicateByteString m w

Additionally, for any 'in-bounds' index (that is, any index for which
`indexByteString`

won't error) `i`

, we have

`indexByteString (replicateByteString n w) i = w`

Lastly, we have

`lengthByteString (replicateByteString n w) = n`

## Rationale: how does this CIP achieve its goals?

The operations, and semantics, described in this CIP provide a set of well-defined bitwise logical operations, as well as bitwise access and modification, to allow cases similar to Case 1 to be performed efficiently and conveniently. Furthermore, the semantics we describe would be reasonably familiar to users of other programming languages (including Haskell) which have provisions for bitwise logical operations of this kind, as well as some way of extending these operations to operate on packed byte vectors. At the same time, there are several choices we have made that are somewhat unusual, or could potentially have been implemented differently based on existing work: most notably, our choice of bit indexing scheme, the padding-versus-truncation semantics, and the multiplicitous definition of bit modification. Among existing work, a particularly important example is CIP-58, which makes provisions for operations similar to the ones described here, and from which we differ in several important ways. We clarify the reasoning behind our choices, and how they differ from existing work, below.

Aside from the issues we list below, we don't consider other operations
controversial. Indeed, `bitwiseLogicalComplement`

has a direct parallel to the
implementation in CIP-58, and `replicateByteString`

is a direct wrapper
around the `replicate`

function in `ByteString`

. Thus, we do not discuss them
further here.

### Relationship to CIP-58 and CIP-121

Our work relates to both CIP-58 and CIP-121. Essentially,
our goal with both this CIP and CIP-121 is to both break CIP-58 into more
manageable (and reviewable) parts, and also address some of the design choices
in CIP-58 that were not as good (or as clear) as they could have been. In this
regard, this CIP is a direct continuation of CIP-121; CIP-121 dealt with
conversions between `BuiltinByteString`

and `BuiltinInteger`

, while this CIP
handles bit indexing more generally, as well as 'parallel' logical operations
that operate on all the bits of a `BuiltinByteString`

in bulk.

We describe how our work in this CIP relates to (and in some cases, supercedes) CIP-58, as well as how it follows on from CIP-121, in more detail below.

### Bit indexing scheme

The bit indexing scheme we describe here is designed around two considerations. Firstly, we want operations on these bits, as well as those results, to be as consistent and as predictable as possible: any individual familiar with such operations on variable-length bitvectors from another language shouldn't be surprised by the semantics. Secondly, we want to anticipate future bitwise operation extensions, such as shifts and rotations, and have the indexing scheme support efficient implementations (and predictable semantics) for these.

While prior art for bit access (and modification) exists
in almost any programming language, these are typically over types of fixed
width (usually bytes, machine words, or something similar); for variable-width
types, these typically are either not implemented at all, or if they are
implemented, this is done in an external library, with varying support for
certain operations. An example of the first is Haskell's `ByteString`

, which has
no way to even access, much less modify, individual bits; an example of the
second is the CRoaring library for C, which supports all the
operations we describe in this CIP, along with multiple others. In the second
case, the *exact* arrangement of bits inside the representation is not something
users are exposed to directly: instead, the bitvector type is opaque, and the
library only guarantees consistency of API. In our case, this is not a viable
choice, as we require bit access *and* byte access to both work on
`BuiltinByteString`

, and thus, some consistency of representation is required.

The scheme for indexing bits within a byte that we describe in the relevant
section is the same as the one used by the `Data.Bits`

API in Haskell for `Word8`

bit indexing, and mirrors the decisions of most
languages that provide such an API at all, as well as the conventional
definition of such operations as `(w >> i) & 1`

for access, `w | (1 BuiltinInteger -> BuiltinBool ->
BuiltinByteString

Essentially, `writeBit bs i v` would be equivalent to `writeBits bs

[(i, v)]` as currently defined. This was the choice made by [CIP-58][cip-58],

with the consideration of simplicity in mind.

At the same time, due to the immutability semantics of Plutus Core, each time

`writeBit` would be called, we would have to copy its `BuiltinByteString`

argument. Thus, a sequence of $k$ `setBit` calls in a fold over a

`BuiltinByteString` of length $n$ would require $Theta(nk)$ time and

$Theta(nk)$ space. Meanwhile, if we instead used `writeBits`, the time

drops to $Theta(n + k)$ and the space to $Theta(n)$, which is a non-trivial

improvement. While we cannot avoid the worst-case copying behaviour of

`setBit` (if we have a critical path of read-write dependencies of length

$k$, for example), and 'list packing' carries some cost, we have

[benchmarks][benchmarks-bits] that show not only that this 'packing cost' is

essentially zero, but that for `BuiltinByteString`s of 30 bytes or fewer,

copying completely overwhelms the work required to modify the bits specified in

the change list argument. This alone is good evidence for having `writeBits` instead;

indeed, there is prior art for doing this [in the `vector` library][vector], for

the exact reasons we give here.

The argument could also be made whether this design should be extended to other

primitive operations in this CIP which both take `BuiltinByteString` arguments

and also produce `BuiltinByteString` results. We believe that this is not as

justified as in the `writeBits` case, for several reasons. Firstly, for

`bitwiseLogicalComplement`, it's not clear what benefit this would have at

all: the only possible signature such an operation would have is

`[BuiltinByteString] -> [BuiltinByteString]`, which in effect would be a

specialized form of mapping. While an argument could be made for a _general_

form of mapping as a Plutus Core primitive, it wouldn't be reasonable for an

operation like this to be considered for such.

Secondly, the performance benefits of such an operation aren't nearly as

significant in theory, and likely wouldn't be in practice either. Consider

this hypothetical operation (with fold semantics):

```haskell

bitwiseLogicalXors :: BuiltinBool -> [BuiltinByteString] -> BuiltinByteString

Simulating this operation as a fold using `bitwiseLogicalXor`

, in the worst
case, irrespective of padding or truncation semantics, requires $Theta(nk)$
time and space, where $n$ is the size of each `BuiltinByteString`

in the
argument list, and $k$ is the length of the argument list itself. Using
`bitwiseLogicalXors`

instead would reduce the space required to $Theta(n)$,
but would not affect the time complexity at all.

Lastly, it is questionable whether 'bulk' operations like `bitwiseLogicalXors`

above would see as much use as `writeBits`

. In the context of Case 1,
`bitwiseLogicalXors`

corresponds to taking the symmetric difference of multiple
integer sets; it seems unlikely that the number of sets we'd want to do this
with would frequently be higher than 2. However, in the same context,
`writeBits`

corresponds to constructing an integer set given a list of
members (or, for that matter, *non*-members): this is an operation that is both
required by the case description, and also much more likely to be used often.

On the basis of the above, we believe that choosing to implement
`writeBits`

as a 'bulk' operation, but to leave others as 'singular' is the
right choice.

## Path to Active

### Acceptance Criteria

We consider the following criteria to be essential for acceptance:

- A proof-of-concept implementation of the operations specified in this document, outside of the Plutus source tree. The implementation must be in GHC Haskell, without relying on the FFI.
- The proof-of-concept implementation must have tests, demonstrating that it behaves as the specification requires.
- The proof-of-concept implementation must demonstrate that it will successfully build, and pass its tests, using all GHC versions currently usable to build Plutus (8.10, 9.2 and 9.6 at the time of writing), across all Tier 1 platforms.

Ideally, the implementation should also demonstrate its performance characteristics by well-designed benchmarks.

### Implementation Plan

MLabs has begun the implementation of the proof-of-concept as required in the acceptance criteria. Upon completion, we will send a pull request to Plutus with the implementation of the primitives for Plutus Core, mirroring the proof-of-concept.

## Copyright

This CIP is licensed under Apache-2.0.

## CIP Information

This null ./CIP-0122 created on **2024-05-03** has the status: Proposed.

This page was generated automatically from: cardano-foundation/CIPs.