Matrix multiplication

To multiply two matrices, you pair every row of the first with every column of the second. Each pairing gives one number of the answer.

That simple rule is the most important computation in modern AI, and it’s the work a Pearl miner does. This page shows how it works, how much it costs, and the “slab by slab” view that Pearl’s mining tickets are built on.

Try it

Hover over any cell of the answer to see the row and column that make it. Then step through the whole multiplication.

What’s the rule?

To get the cell in row i and column j of C = A·B, walk along row i of A and down column j of B together. Multiply each pair, and add everything up. That’s a dot product.

The other cells work the same way:

• Top right: row (1, −2, 3) with column (1, 3, 0): 1 − 6 + 0 = −5.
• Bottom left: row (0, 4, −1) with column (2, −1, 4): 0 − 4 − 4 = −8.
• Bottom right: row (0, 4, −1) with column (1, 3, 0): 0 + 12 + 0 = 12.

The shapes have to fit: A’s rows must be as long as B’s columns, k = 3 here. The answer has A’s number of rows and B’s number of columns.

How much work is it?

Each “multiply a pair and add it to the running total” is one multiply-accumulate (MAC). The answer has m·n cells, each a dot product of length k:

The example above took 2 · 2 · 3 = 12. Real ones are vastly bigger. The certificate of block 130,825 declares its matrices as m = 131,072, k = 8,192 and n = 262,144. A full multiplication of that shape is

The network as a whole is expected to do about 1.13 × 10²² multiply-accumulates per block at the snapshot difficulty of 40,157,376: some 40 million multiplications of that size. That’s why Pearl’s hashrate is counted in multiply-accumulates per second, not hashes. See hashrate.

What’s the slab-by-slab view?

The sum along k can be cut into pieces. Split the columns of A and the rows of B into slabs of the same width, multiply each pair of slabs, and add the results. You get exactly the same answer.

A tiny example. Take P = [[1, 2, 0, −1], [3, −1, 2, 1]] and Q = [[2, 1], [0, −1], [1, 3], [−2, 2]], and split k = 4 into two slabs of 2:

Why care? Because this is exactly how Pearl watches the work being done. A miner doesn’t just produce the final answer. For each small patch of the output, a tile, it records the running sums after every slab of width r = 128. Those records feed the patch’s lottery ticket.

Here is a tile from Pearl’s toy mining example (k = 16, slabs of 4), with the running sums after each slab and the 32-bit XOR of each set of sums:

Because the ticket depends on the sums along the way, a miner can’t get it by computing the final answer some cheaper way and adjusting it. That’s the subject of rank and noise, and the full ticket recipe is on tickets and target.

Are there faster ways to multiply?

In theory, yes. Mathematicians know algorithms that use fewer than m·n·k multiplications for very large matrices; Strassen’s 1969 method was the first. Pearl’s security argument has to allow for such tricks. They may be one reason for the rank penalty, though Pearl’s own explanation says only that a higher noise rank made each ticket cheaper.

In practice, GPU mining does the plain m·n·k version, split into tiles that fit the chip. That’s the next pages: integers, then GPUs and tiles.

for ll in (r..=k).step_by(r) {
    for u in 0..h {
        for v in 0..w {
            for l in ll - r..ll {
                jackpot[u][v] +=
                    (secret_a[u][l] as i32 + noise.a[u][l] as i32) * (secret_b[v][l] as i32 + noise.b[v][l] as i32);
            }
        }
    }
    let xored_tile = jackpot.iter().flatten().fold(0u32, |a, &x| a ^ x as u32);
    let tid = (ll / r - 1) % JACKPOT_SIZE;
    jackpot_msg[tid] = jackpot_msg[tid].rotate_left(LROT_PER_TILE) ^ xored_tile;
}