Neo: New witness type: PublicKeyHashWitness

[erikzhang]

Summary or problem description
Every transaction requires Witnesses to be verified. Currently, we allow to run NeoVM and execute the verification script during Witness's verification process. We call this the ScriptHash validation model. But in NEO, the vast majority of transactions just verify the signature, in which case we don't need to run the VM.

Do you have any solution you want to propose?
Therefore, I propose that we can support a new Witness model: the PublicKeyHash verification model similar to Bitcoin. We can add a type field to Witness. In the new PublicKeyHashWitness, the original VerificationScript becomes PublicKey and InvocationScript becomes Signature. In this way, we do not need to run NeoVM when verifying most transactions, which greatly improves TPS.

Neo Version

• Neo 3

Where in the software does this update applies to?

• Other

[vncoelho]

For most type of applications this is good, @erikzhang, however, for lock and other important features we still need the current model.

[igormcoelho]

Strongly agree, great design Erik :+1:

[doubiliu]

We have done a test before, this change is not very effective. The main reason is that the script is relatively simple, VM doesn't consume computation resources, and the main consumption is still on the cryptographic computation.

[shargon]

@doubiliu do you have some statistics about your research?

[eryeer]

Neo Stopwatch code:
```C#
namespace Neo.SmartContract
{
public static class Helper
{
...
public static double totaltime1;
public static double totaltime2;
public static int count;

    internal static bool VerifyWitnesses(this IVerifiable verifiable, Snapshot snapshot, long gas)
    {
        Stopwatch stopwatch1 = new Stopwatch();
        Stopwatch stopwatch2 = new Stopwatch();
        stopwatch1.Start();
        if (gas < 0) return false;

        UInt160[] hashes;
        try
        {
            hashes = verifiable.GetScriptHashesForVerifying(snapshot);
        }
        catch (InvalidOperationException)
        {
            return false;
        }
        if (hashes.Length != verifiable.Witnesses.Length) return false;
        for (int i = 0; i < hashes.Length; i++)
        {
            byte[] verification = verifiable.Witnesses[i].VerificationScript;
            if (verification.Length == 0)
            {
                verification = snapshot.Contracts.TryGet(hashes[i])?.Script;
                if (verification is null) return false;
            }
            else
            {
                if (hashes[i] != verifiable.Witnesses[i].ScriptHash) return false;
            }
            stopwatch2.Start();
            using (ApplicationEngine engine = new ApplicationEngine(TriggerType.Verification, verifiable, snapshot, gas))
            {
                engine.LoadScript(verification);
                engine.LoadScript(verifiable.Witnesses[i].InvocationScript);
                if (engine.Execute().HasFlag(VMState.FAULT)) return false;
                if (engine.ResultStack.Count != 1 || !engine.ResultStack.Pop().GetBoolean()) return false;
            }
            stopwatch2.Stop();
            totaltime2 += stopwatch2.Elapsed.TotalSeconds;
            stopwatch2.Reset();
            count++;
        }
        stopwatch1.Stop();
        totaltime1 += stopwatch1.Elapsed.TotalSeconds;
        stopwatch1.Reset();
        return true;
    }
}

}

```C#
namespace Neo.SmartContract
{
    static partial class InteropService
    {
        public static double totaltime3;
        private static bool Crypto_CheckSig(ApplicationEngine engine)
        {
            Stopwatch stopwatch3 = new Stopwatch();
            byte[] pubkey = engine.CurrentContext.EvaluationStack.Pop().GetByteArray();
            byte[] signature = engine.CurrentContext.EvaluationStack.Pop().GetByteArray();
            stopwatch3.Start();
            try
            {
                engine.CurrentContext.EvaluationStack.Push(Crypto.Default.VerifySignature(engine.ScriptContainer.GetHashData(), signature, pubkey));
            }
            catch (ArgumentException)
            {
                engine.CurrentContext.EvaluationStack.Push(false);
            }
            stopwatch3.Stop();
            totaltime3 += stopwatch3.Elapsed.TotalSeconds;
            stopwatch3.Reset();
            return true;
        }
    }
}

UT code
```C#
[TestMethod]
public void TestVerifyWitness()
{
var snapshot = Blockchain.Singleton.GetSnapshot();
var walletA = TestUtils.GenerateTestWallet();

        using (var unlockA = walletA.Unlock("123"))
        {
            var acc = walletA.CreateAccount();

            // Fake balance

            var key = NativeContract.GAS.CreateStorageKey(20, acc.ScriptHash);
            var entry = snapshot.Storages.GetAndChange(key, () => new StorageItem
            {
                Value = new Nep5AccountState().ToByteArray()
            });

            entry.Value = new Nep5AccountState()
            {
                Balance = 100_000_000 * NativeContract.GAS.Factor
            }
            .ToByteArray();

            snapshot.Commit();

            typeof(Blockchain)
                .GetMethod("UpdateCurrentSnapshot", BindingFlags.Instance | BindingFlags.NonPublic)
                .Invoke(Blockchain.Singleton, null);

            // Make transaction
            var txs = new List<Transaction>();
            for (int i = 0; i < 10000; i++)
            {
                var tx = CreateValidTx(walletA, acc.ScriptHash, 0);
                txs.Add(tx);
            }
            foreach (var tx in txs)
            {
                var res = tx.VerifyParallelParts(snapshot);
                res.Should().BeTrue();
            }
            Console.WriteLine($"timespan for verifyWitness: {Neo.SmartContract.Helper.totaltime1/ Neo.SmartContract.Helper.count}");
            Console.WriteLine($"timespan for VM execution: {Neo.SmartContract.Helper.totaltime2/ Neo.SmartContract.Helper.count}");
            Console.WriteLine($"timespan for cryptographic VerifySignature: {InteropService.totaltime3/ Neo.SmartContract.Helper.count}");
        }
    }

    private Transaction CreateValidTx(NEP6Wallet wallet, UInt160 account, uint nonce)
    {
        var tx = wallet.MakeTransaction(new TransferOutput[]
            {
                new TransferOutput()
                {
                        AssetId = NativeContract.GAS.Hash,
                        ScriptHash = account,
                        Value = new BigDecimal(1,8)
                }
            },
            account);

        tx.Nonce = nonce;

        var data = new ContractParametersContext(tx);
        Assert.IsTrue(wallet.Sign(data));
        Assert.IsTrue(data.Completed);

        tx.Witnesses = data.GetWitnesses();

        return tx;
    }

Console print:

timespan for verifyWitness: 0.00076064605
timespan for VM execution: 0.00074115756
timespan for cryptographic VerifySignature: 0.000708882510000001
```
The result shows VM execution consumpts 0.03ms while cryptographic computation consumpts 0.71ms for each tx on average.

[fyrchik]

I believe signature checking can be made more fast by providing index of validators which have signed the block (may be just as a hint). It takes negligible amount of space (2-byte mask) and in this case it will also be_easy_ to parallelize signature checking.
At least it can be useful when restoring a state from dump. When testing this with neo-go, speed difference between with/without signature checking is about 10x. When it is paralellized I expect similar performance gains (maybe at least 5x)
What do you think about this?

[vncoelho]

Sounds good and aligned with BLS and Schnoor discussions were have been caring on, @fyrchik. #1085

Can you copy this question in that aforementioned issue? Because it looks like to be more related there than here.