Provide a verify signature function

[EnoF]

I believe there is a relatively cheap way to provide for offchain transactions. In order to do so I'd need a way to verify a signature.

(defun verify-sig:boolean (public-key:string message:string signature:string))
(defun verify-sig:boolean (public-key:string message:string signature:string algorithm:string))

A function to verify the sig either predefined or where the specification of an algorithm is allowed would help provide the dApps with a lot of flexibility.

To elaborate on the offchain transactions idea:

Sparse Merkle Tree Entry
The offchain account balances will be stored in a Sparse Merkle Tree and synced to other participants via a mesh p2p network. To enter the tree you'd transfer KDA to the dApp which holds the KDA so this KDA can be registered on the SMT. The SMT hash will be signed by the account holder.

Offchain Transaction
A transaction can only take place when both the debit and credit account are present in the SMT. The owner of the debit account will sign for both the hash after the debit and credit took effect on the SMT.

Verification
To verify the transactions the signatures of the SMT hashes have to be verified with the public key associated with the debit account. This check should both be performed on and off chain. Off chain verification allows peers to make sure their next transactions will not render invalid and on chain verification will unlock withdrawal potentials. In order to make sure there is no foul play with transactions of withdrawn KDA, the debit account information should be retrieved from the dApp to verify any withdrawal information.

Withdrawal
In order to withdraw the KDA from the dApp a sync moment is required. For the sake of simplicity imagine a daily sync. End of day the latest state will be synced to the chain. A account holder can request their funds to be withdrawn, but needs to queue their withdrawal. When queuing their withdrawal their account will be marked with the amount of withdrawal. After the next X amount of syncs the KDA can be withdrawn, and while in this state the KDA will be reserved in the peer network.

[sirlensalot]

@EnoF this looks like this would support ED25519 signatures only is that correct? We would want a solution to consider supporting multiple curves (e.g. also ECDSA, specifically Ethereum and/or Bitcoin).

However, it's also worth considering other crypto altogether. This approach is certainly effective for single-signatures but for instance in a threshold-ring scenario you could be needing to capture and verify many signatures, in which case BLS is the better choice. @jwiegley could provide some insight here.

Regarding the use-case example --

1. What signatures are verified?
2. How does the on-chain SMT verification work? This seems like more than just signatures.

[sirlensalot]

Ethereum BLS spec: https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/beacon-chain.md#bls-signatures

[EnoF]

The idea is atm indeed only taking 1 sig per account for this idea. Probably could expand it to multi sig similar to how we do it on chain, but for sake for simplicity and testing the idea I scoped it to single sig.

This would support any curve as long as it is provided via pact. i.e.

(defun verify-sig:boolean (public-key:string message:string signature:string algorithm:string))

where algorithm could be ED25519, ECDSA or any other curve that we deem safe and efficient enough.

If we can somehow provide a similar check based on a keyset like:

(enforce-msg-keyset message sig keyset)

then multi sig could work as well.

SMT verification
regarding SMT verification, in this idea the SMT verification is done implicitly by all signers. Since all signers have signed the SMT, the the hashes prior to their transaction have already been verified. Every user joining the SMT can revalidate all hashes with their associated signatures. With that said, I'm not sure if I've left doors open for an attack.

edit: forgot to address point 2

[jwiegley]

I don't quite understand the "off-chain SMT" concept here. It sounds like you could only trust account balances to be validated simply by signature if you can fully trust the SMT itself -- i.e., if it's also a full chain.

One of the reasons proof production for ZK is so expensive is that it permits external validators who have stake in the dApp to confirm settlement transactions, while also providing the L1 settlement layer with an extremely easy to verify result. That is, it shifts compute/time expense almost entirely to the dApp. Since the rollup dApp isn't usually in any particular hurry to settle, there's no problem with it taking several minutes to generate that proof.

I wonder what the requirements you're aiming to solve are in this proposal. Why is expensive proof production bad? Does anything motivate this signature-based scheme beyond optimization?

[CryptoPascal31]

RSA Signatures verification in Pact.

https://github.com/CryptoPascal31/pact-rsa

I did that mostly for fun (to test how Pact could handle big numbers), but maybe it could help ?

Gas usage is high but practicable.