Implement logic gates on Kusama

readme.md

Implement logic gates on Kusama

TLDR; Running 1 + 1 = 2 on Kusama: https://kusama.subscan.io/extrinsic/4025533-1

Inputs: Two accounts

• https://kusama.subscan.io/account/F3NJ4gDQR8WCGGauo3ewRxx2cyxWbj8nH3Q8sDdSb66on1D
• https://kusama.subscan.io/account/DDb6Ln2vywhV7fXZfmy2j4prsaXiUgKXJB5GYMiZjtwYgvN

Output:

• Sum: https://kusama.subscan.io/account/EBXFwugvZGsBC794dkkuhZ6B8h6xLNC6AUFmwFPBqzyYb7j
• Carry: https://kusama.subscan.io/account/JHb4QY1xec5ZH6Fh2bWzcPJR1n8rNagHDq8yuypnPfA2mKy

Have KSM means 1, and no KSM means 0.

Kusama have many interesting features, but running user provided logic is not one of them. However, it does have a powerful transaction system and have many features.

Here are few less commonly known features on Kusama / Polkadot:

• People can batch their transaction with utility.batch, however it will bail out as soon as one of the transaction failed. But it will not revert previous executed transaction and will still emit ExtrinsicSuccess event regardless. Just an extra BatchInterrupted will be emitted to indicate which transaction failed.
• So it is possible to use utility.batch to wrap a transaction to make it always emit ExtrinsicSuccess event.
• Combined with those features, we can use nested utility.batch within utility.batch to make it execute all transactions regardless if any of them in the batch failed.
• People can have sub-account by using utility.asDerivative. It will generate a indexed pseudonym account.

With all the above features, we can actually implement logic gates by execute a specially crafted transaction.

We use an account balance to represent a bit, 0 if balance is zero, 1 if balance is non-zero.

To test if a bit is true is simply trying to transfer the balance into another account. The execution result indicates if the bit is true of false. One small issue is a success transfer will also clear the bit as well, but we can always transfer the money back to restore the state.

To read the test result, we can use the batch call. batch([transfer(input, temp, 1), someOtherCall]) will only execute someOtherCall if source is true.

So an and gate will simply be batch([transfer(input1, temp, 1), transfer(input2, temp, 1), someOtherCall]) will execute someOtherCall only if both input1 and input2 are true.

Negate will be batch([transfer(input, result, 1), transfer(input, temp, 1), transfer(result, temp, 1)]). Basically mark result true first, and attempt to clear it if input is true.

With and and not, we will be able to implement or and all other gates. And a adder will just be a combination of those gates.

One more issue is that one transaction can only have one origin, but we will want to manipulate multiple accounts. This is where utility.asDerivative comes handy. It allow me to generate many new accounts on the go and all from a single origin.

A mock implementation was used to develop and test the logics without waiting for block confirmation: https://gist.github.com/xlc/f064f492a4040f698a2b4eb838f0bf2b#file-simulated-ts

This is the code will work with all Substrate based chain with pallet-utility: https://gist.github.com/xlc/f064f492a4040f698a2b4eb838f0bf2b#file-real-ts

I would not recommend to run it unmodified on Kusama / Polkadot because it will try all the combinations to generate truth table and the cost will adde up quickly.

Suggestions for optimization are welcome!

real.ts

import { ApiPromise, WsProvider } from '@polkadot/api'
import { Keyring, decodeAddress } from '@polkadot/keyring';
import { SubmittableExtrinsic } from '@polkadot/api/types';
import { stringToU8a, numberToU8a, u8aConcat } from '@polkadot/util';
import { blake2AsU8a } from '@polkadot/util-crypto/blake2';
import { KeyringPair } from '@polkadot/keyring/types';

const config = {
    ws: 'ws://localhost:9944',
    seed: '//Alice',
}

const derivedAccount = (origin: string, index: number) => {
    const prefix = stringToU8a('modlpy/utilisuba')
    const acc = decodeAddress(origin)
    const idx = numberToU8a(index, 16).reverse()
    return blake2AsU8a(u8aConcat(prefix, acc, idx))
}

const transfer = (api: ApiPromise, to: string | Uint8Array, amount: number) => api.tx.balances.transfer(to, amount)
const sequence = (api: ApiPromise, calls: SubmittableExtrinsic<'promise'>[]) => api.tx.utility.batch(calls)
const asDerive = (api: ApiPromise, index: number, call: SubmittableExtrinsic<'promise'>) => api.tx.utility.asDerivative(index, call)

class World {
    constructor(public api: ApiPromise, public origin: KeyringPair, public minTransfer = 1) {}

    temp(i = 0) {
        return new Bit(this, 1000 + i)
    }

    newBit(index: number) {
        return new Bit(this, index)
    }
}

class Bit {
    constructor(public world: World, public account: number) {}

    get derivedAccount() {
        return derivedAccount(this.world.origin.address, this.account)
    }

    get api() {
        return this.world.api
    }

    test() {
        return asDerive(this.api, this.account, transfer(this.api, this.world.origin.addressRaw, this.world.minTransfer))
    }

    clear() {
        return sequence(this.api, [ // make this always success
            asDerive(this.api, this.account, transfer(this.api, this.world.origin.addressRaw, this.world.minTransfer))
        ])
    }

    set() {
        return sequence(this.api, [
            this.clear(),
            transfer(this.api, this.derivedAccount, this.world.minTransfer)
        ])
    }

    setValue(val: number | boolean) {
        if (val) {
            return this.set()
        } else {
            return this.clear()
        }
    }

    copyTo(other: Bit) {
        return sequence(this.api, [
            other.clear(),
            this.test(),
            this.set(),
            other.set(),
        ])
    }

    move(other: Bit) {
        return sequence(this.api, [
            other.clear(),
            asDerive(this.api, this.account, transfer(this.api, other.derivedAccount, this.world.minTransfer))
        ])
    }

    assignNegate(result: Bit) {
        return sequence(this.api, [
            result.set(),
            this.test(),
            result.clear(),
        ])
    }

    negate() {
        const temp = this.world.temp()
        return sequence(this.api, [
            this.assignNegate(temp),
            temp.move(this),
        ])
    }
}

const and = (a: Bit, b: Bit, result: Bit) => sequence(a.api, [
    result.clear(),
    a.test(),
    b.test(),
    result.set(),
])

const or = (a: Bit, b: Bit, result: Bit) => sequence(a.api, [
    a.negate(),
    b.negate(),
    and(a, b, result),
    result.negate()
])

const nand = (a: Bit, b: Bit, result: Bit) => sequence(a.api, [
    result.set(),
    a.test(),
    b.test(),
    result.clear()
])

// and(or(a, b), nand(a, b))
const xor = (a: Bit, b: Bit, result: Bit, tmp1: Bit, tmp2: Bit) => {
    return sequence(a.api, [
        a.copyTo(tmp1),
        b.copyTo(result),
        or(tmp1, result, tmp2),
        nand(a, b, tmp1),
        and(tmp1, tmp2, result),
    ])
}

const nor = (a: Bit, b: Bit, result: Bit) => sequence(a.api, [
    a.negate(),
    b.negate(),
    and(a, b, result),
])

const halfAdder = (a: Bit, b: Bit, c: Bit, s: Bit, tmp1: Bit, tmp2: Bit) => sequence(a.api, [
    a.copyTo(tmp1),
    b.copyTo(tmp2),
    and(tmp1, tmp2, c),
    xor(a, b, s, tmp1, tmp2),
])

const send = async (origin: KeyringPair, tx: SubmittableExtrinsic<'promise'>) => {
    await new Promise(async (resolve) => {
        await tx.signAndSend(origin, res => {
            if (res.isInBlock) {
                resolve()
            }
        })
    })
}

const printTable = async (api: ApiPromise, origin: KeyringPair) => {
    const world = new World(api, origin, api.consts.balances.existentialDeposit.toNumber())

    const start = 0

    const a = world.newBit(start + 1)
    const b = world.newBit(start + 2)
    const c = world.newBit(start + 3)
    const d = world.newBit(start + 4)
    const e = world.newBit(start + 5)
    const f = world.newBit(start + 6)

    // const set = sequence(api, [
    //     a.setValue(1),
    //     b.setValue(1),
    // ])

    // const tx = sequence(api, [
    //     set,
    //     halfAdder(a, b, c, d, e, f)
    // ])

    // console.dir(tx.toHuman(), { depth: 100 })
    
    // await send(origin, tx)

    // const res1 = (await api.query.system.account(c.derivedAccount)).data.free
    // const res2 = (await api.query.system.account(d.derivedAccount)).data.free

    // console.log(res1, res2)

    // return

    const result = []

    for (const x of [0, 1]) {
        for (const y of [0, 1]) {
            const values: any = {
                x, y
            }

            const set = sequence(api, [
                a.setValue(x),
                b.setValue(y),
            ])

            await send(origin, sequence(api, [
                set,
                and(a, b, c)
            ]))

            values.and = (await api.query.system.account(c.derivedAccount)).data.free.toString()
            
            await send(origin, sequence(api, [
                set,
                or(a, b, c)
            ]))

            values.or = (await api.query.system.account(c.derivedAccount)).data.free.toString()

            await send(origin, sequence(api, [
                set,
                xor(a, b, c, d, e)
            ]))

            values.xor = (await api.query.system.account(c.derivedAccount)).data.free.toString()

            await send(origin, sequence(api, [
                set,
                nand(a, b, c)
            ]))

            values.nand = (await api.query.system.account(c.derivedAccount)).data.free.toString()

            await send(origin, sequence(api, [
                set,
                nor(a, b, c)
            ]))

            values.xor = (await api.query.system.account(c.derivedAccount)).data.free.toString()

            await send(origin, sequence(api, [
                set,
                halfAdder(a, b, c, d, e, f)
            ]))

            values.addCarry = (await api.query.system.account(c.derivedAccount)).data.free.toString()
            values.addSum = (await api.query.system.account(d.derivedAccount)).data.free.toString()

            result.push(values)
        }
    }

    console.table(result)
}

const main = async () => {
    const ws = new WsProvider(config.ws)
    const api = new ApiPromise({ provider: ws })
    await api.isReady

    const keyring = new Keyring({ type: 'sr25519' })
    const pair = keyring.addFromUri(config.seed)

    await printTable(api, pair)
}

main()
.catch(err => {
    console.error('Error:', Object.entries(err), err)
})
.finally(() => {
    process.exit()
})

simulated.ts

export abstract class Call {
    abstract invoke(state: ChainState, origin: number): boolean
}

export class Transfer extends Call {
    constructor(public to: number, public amount: number) {
        super()
    }

    invoke(state: ChainState, origin: number): boolean {
        if ((state.accounts[origin] | 0) < this.amount) {
            return false
        }
        state.accounts[origin] -= this.amount
        state.accounts[this.to] = (state.accounts[this.to] | 0) + this.amount
        return true
    }
}

export class Batch extends Call {
    constructor(public calls: Call[]) {
        super()
    }

    invoke(state: ChainState, origin: number): boolean {
        for (const c of this.calls) {
            if (!state.call(origin, c)) {
                return true
            }
        }
        return true
    }
}

const derivedAccount = (origin: number, index: number) => 10000 + origin * 1000 + index

export class AsDerive extends Call {
    constructor(public index: number, public call: Call) {
        super()
    }

    invoke(state: ChainState, origin: number): boolean {
        return state.call(derivedAccount(origin, this.index), this.call);
    }
}

const transfer = (to: number, amount: number) => new Transfer(to, amount)
const sequence = (calls: Call[]) => new Batch(calls)
const asDerive = (index: number, call: Call) => new AsDerive(index, call)

class ChainState {
    level = 0
    log = false
    constructor(public accounts: Record<number, number> = {}) {}

    call(from: number, c: Call): boolean {
        if (this.log) {
            console.log(new Array(this.level * 2).fill(' ').join(''), '>>', from, c)
            this.level++
        }
        const res = c.invoke(this, from)
        if (this.log) {
            this.level--
            console.log(new Array(this.level * 2).fill(' ').join(''), '<<', this.accounts)
        }
        return res
    }
}

class World {
    constructor(public origin: number) {}

    temp(i = 0) {
        return new Bit(this, 1000 + i)
    }

    newBit(index: number) {
        return new Bit(this, index)
    }
}

class Bit {
    constructor(public world: World, public account: number) {}

    get derivedAccount() {
        return derivedAccount(this.world.origin, this.account)
    }

    test() {
        return asDerive(this.account, transfer(this.world.origin, 1))
    }

    clear() {
        return sequence([ // make this always success
            asDerive(this.account, transfer(this.world.origin, 1))
        ])
    }

    set() {
        return sequence([
            this.clear(),
            transfer(this.derivedAccount, 1)
        ])
    }

    setValue(val: number | boolean) {
        if (val) {
            return this.set()
        } else {
            return this.clear()
        }
    }

    copyTo(other: Bit) {
        return sequence([
            other.clear(),
            this.test(),
            this.set(),
            other.set(),
        ])
    }

    move(other: Bit) {
        return sequence([
            other.clear(),
            asDerive(this.account, transfer(other.derivedAccount, 1))
        ])
    }

    assignNegate(result: Bit) {
        return sequence([
            result.set(),
            this.test(),
            result.clear(),
        ])
    }

    negate() {
        const temp = this.world.temp()
        return sequence([
            this.assignNegate(temp),
            temp.move(this),
        ])
    }
}

const and = (a: Bit, b: Bit, result: Bit) => sequence([
    result.clear(),
    a.test(),
    b.test(),
    result.set(),
])

const or = (a: Bit, b: Bit, result: Bit) => sequence([
    a.negate(),
    b.negate(),
    and(a, b, result),
    result.negate()
])

const nand = (a: Bit, b: Bit, result: Bit) => sequence([
    result.set(),
    a.test(),
    b.test(),
    result.clear()
])

// and(or(a, b), nand(a, b))
const xor = (a: Bit, b: Bit, result: Bit, tmp1: Bit, tmp2: Bit) => {
    return sequence([
        a.copyTo(tmp1),
        b.copyTo(result),
        or(tmp1, result, tmp2),
        nand(a, b, tmp1),
        and(tmp1, tmp2, result),
    ])
}

const nor = (a: Bit, b: Bit, result: Bit) => sequence([
    a.negate(),
    b.negate(),
    and(a, b, result),
])

const halfAdder = (a: Bit, b: Bit, c: Bit, s: Bit, tmp1: Bit, tmp2: Bit) => sequence([
    a.copyTo(tmp1),
    b.copyTo(tmp2),
    and(tmp1, tmp2, c),
    xor(a, b, s, tmp1, tmp2),
])

const printTable = () => {
    const state = new ChainState({
        0: 1000
    })

    const world = new World(0)

    const a = world.newBit(1)
    const b = world.newBit(2)
    const c = world.newBit(3)
    const d = world.newBit(4)
    const e = world.newBit(5)
    const f = world.newBit(6)

    const result = []

    for (const x of [0, 1]) {
        for (const y of [0, 1]) {
            const values: any = {
                x, y
            }

            const set = sequence([
                a.setValue(x),
                b.setValue(y),
            ])

            state.call(0, sequence([
                set,
                and(a, b, c)
            ]))

            values.and = state.accounts[c.derivedAccount] | 0
            
            state.call(0, sequence([
                set,
                or(a, b, c)
            ]))

            values.or = state.accounts[c.derivedAccount] | 0

            state.call(0, sequence([
                set,
                xor(a, b, c, d, e)
            ]))

            values.xor = state.accounts[c.derivedAccount] | 0

            state.call(0, sequence([
                set,
                nand(a, b, c)
            ]))

            values.nand = state.accounts[c.derivedAccount] | 0

            state.call(0, sequence([
                set,
                nor(a, b, c)
            ]))

            values.nor = state.accounts[c.derivedAccount] | 0

            state.call(0, sequence([
                set,
                halfAdder(a, b, c, d, e, f)
            ]))

            values.addCarry = state.accounts[c.derivedAccount] | 0
            values.addSum = state.accounts[d.derivedAccount] | 0

            result.push(values)
        }
    }

    console.table(result)
}

const main = () => {
    printTable()
}

main()

This is SO cool.