GAS price for CheckWitness is too cheap: cost 13 mins with 20GAS

[dusmart]

The syscall System.Runtime.CheckWitness can check witness by signer's rules.
Although the rule itself is constrained to MaxSubitems = 16 and MaxNestingDepth = 2, the check could still be very slow due to cache miss.

The max rules can be MaxSubitems * MaxSubitems * MaxSubitems theoretically. While the max size is actually limited by the transaction's maxsize (102400) which make the MaxSubitems and MaxNestingDepth useless.

neo/src/neo/Network/P2P/Payloads/Conditions/CalledByGroupCondition.cs

Lines 38 to 43 in ed68274

	public override bool Match(ApplicationEngine engine)
	{
	engine.ValidateCallFlags(CallFlags.ReadStates);
	ContractState contract = NativeContract.ContractManagement.GetContract(engine.Snapshot, engine.CallingScriptHash);
	return contract is not null && contract.Manifest.Groups.Any(p => p.PubKey.Equals(Group));
	}

POC: https://gist.github.com/dusmart/f700d8f87256d61a12746bcb404f9c18
Attacking Source Code:

<lazy xmlns:a="Assembly" xmlns:b="Basic">
    <b:func name="main">
        <a:int val="600000" />
        <a:int val="1" />
        <pack />
        <a:contractcall hash="0x4625b78c56b7e43e1e6fb4ed0200e9a0a9152c92" method="go" />
        <!-- public static bool Go(int times) {
            var sender = ((Transaction)Runtime.ScriptContainer).Sender;
            for (int i = 0; i < times; i++) {
                Runtime.CheckWitness(sender);
            }
            return Runtime.CheckWitness(sender);
        } -->
        <b:return />
    </b:func>
</lazy>

[dusmart]

This opretion can slightly violate 10 seconds per GAS price standard (getExecFeeFactor is 3 instead of 30 for now).
#1863 (comment)

[roman-khimov]

{"id":1,"jsonrpc":"2.0","result":{"state":"HALT","gasconsumed":"1897309677","script":"AsAnCQARwB8MAmdvDBSSLBWpoOkAAu20bx4+5LdWjLclRkFifVtSQA==","stack":[{"type":"Boolean","value":false}],"notifications":[]}}

real    0m12,197s
user    0m0,014s
sys     0m0,004s

With 20 GAS for MaxGasInvoke (our default is 15 which isn't sufficient ("at instruction 25 (SYSCALL): failed to invoke syscall 2364286968: insufficient amount of gas")).

[dusmart]

With 20 GAS for MaxGasInvoke (our default is 15 which isn't sufficient ("at instruction 25 (SYSCALL): failed to invoke syscall 2364286968: insufficient amount of gas")).

Have you added the 256 witness rules to the test?
If so, neo-go's implementation seems good enough.

[roman-khimov]

I've just reproduced your testcase from https://gist.github.com/dusmart/f700d8f87256d61a12746bcb404f9c18 (but have found/fixed some minor JSON incompatibilites between implementations along the way).

[dusmart]

As a comparison, simply using reversen Opcode could also cost approximately this amount of time (2 min).

VwEAAfgHdwAMKGFhYWJiYmJiYmJiYmNjY2NjY2NkZGRkZGRkZWVlZWVlZWZmZmZmZmZvAJ13AG8AJc////8CwPNeAXcAAfgHVW8AnXcAbwAl9f///0lA

Maybe some improvement in C# such as adding the non-existing key into cache could accelarating this syscall. No fee change is needed.

Neo-go maintained a contracts cache so that no real disk access appears and can do it quickly.

https://github.com/nspcc-dev/neo-go/blob/613a23cc3f6c303882a81b61f3baec39b7e84597/pkg/core/native/management.go#L148-L158

[dusmart]

@roman-khimov I found that the real conditions number can be MaxSubitems * MaxSubitems * MaxSubitems because of the rules array itself's depth doesn't count to MaxNestingDepth. Could you please retry the attack on neo-go?

Actually, if the MaxNestingDepth do not limit the rules array, the max size is actually restrained by the transaction's max size which is 102400 bytes. In this new attack, I use 4 * 16 * 16 subitems in total so that it can't exceed the max transaction size.

[roman-khimov]

@roman-khimov I found that the real conditions number can be MaxSubitems * MaxSubitems * MaxSubitems because of the rules array itself's depth doesn't count to MaxNestingDepth. Could you please retry the attack on neo-go?

{"id":1,"jsonrpc":"2.0","error":{"code":-32602,"message":"Invalid Params","data":"not a signer: too many nesting levels"}} here.

And maybe in this case it's better to be slightly incompatible.

[dusmart]

And maybe in this case it's better to be slightly incompatible.

kkkkkkkk
Yes, two levels seems enough.

[shargon]

I think that the problem could be huge if you use a 33 bytes public key, because it will need to create the scriptHash

[shargon]

We can pay per rule

[dusmart]

I think that the problem could be huge if you use a 33 bytes public key, because it will need to create the scriptHash

That's a great idea. I didn't realize that. I only focused on cache-miss that time.