Implement logic gates on Kusama
TLDR; Running 1 + 1 = 2 on Kusama: https://kusama.subscan.io/extrinsic/4025533-1
Inputs: Two accounts
- 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
ExtrinsicSuccessevent regardless. Just an extra
BatchInterruptedwill be emitted to indicate which transaction failed.
- So it is possible to use
utility.batchto wrap a transaction to make it always emit
- Combined with those features, we can use nested
utility.batchto 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.
and gate will simply be
batch([transfer(input1, temp, 1), transfer(input2, temp, 1), someOtherCall]) will execute
someOtherCall only if both
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.
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
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!