Skip to content

Instantly share code, notes, and snippets.

@xlc

xlc/readme.md

Last active May 18, 2022 07:27
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save xlc/f064f492a4040f698a2b4eb838f0bf2b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save xlc/f064f492a4040f698a2b4eb838f0bf2b to your computer and use it in GitHub Desktop.
Download ZIP
Implement logic gates on Kusama
Raw
readme.md

Implement logic gates on Kusama

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

Inputs: Two accounts

Output:

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!

Raw
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()
})
Raw
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()
@kianenigma
Copy link

kianenigma commented Sep 19, 2020

This is SO cool.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment