SVM Transactions Signatures

[YaronWittenstein]

SVM Transaction Signatures

Overview

This SMIP extends the AA Transactions & SVM Integration and SVM Raw Transaction Ranges SMIPs.
It outlines how to support in the SVM infrastructure-level different Signatures Schemes.
It's highly recommended to read both SMIPs before reading this one.

Goals and Motivation

The introduction of Account Unification to Spacemesh opened doors to extend the system with features that otherwise had to be part of the protocol. One of the implications is being able to shift the Transactions Signatures Schemes implementation to the Template level.

We want each Template to be able to have its Signature Schemes.
One Template might use a Single Signature Scheme while the other might apply MultiSig 2-3 Scheme.

High-level design

The Signatures Schemes verification will take place within the verify method of a Template.
Each Template may decide about its verification algorithm. Almost any Template will apply some form of Digital Signatures (DS) as part of their verify.

In theory, a Template might choose to always return true in its verify logic - in such a case, no Signature Data will be involved.

The number of parties signing the Transaction and the exact algorithms used will be different between Templates.
Any Template using DS will involve signing the Transaction (in its binary format) digitally.

Terminology-wise, the Signatures Data is part of the Message part of any Transaction. (i.e Deploy/Spawn/Call),
That being said, we need to distinguish between:

• A Transaction, excluding the Signatures Data.
• The whole Transaction, including the Signatures Data.

This distinction is crucial and can easily be mistaken.
When referring to a Transaction, we need to know the context - whether it includes the Signatures Data or not.

For example, when sending a Transaction over the network, we infer that the Signatures Data is part of the transmitted data. In other cases, it might require an explicit mention of whether the Signatures Data are available or not.

We'll call the Signatures Data in their binary form the sigdata (using the same convention as in calldata/verifydata/returndata).

From the infrastructure standpoint, it's just a blob of bytes. But, in general, it is a list of Signatures Data that the verify knows how to interpret. That being said, it's advised not to use any fancy ABI here. Instead, the most straightforward implementation will be concatenating the Signatures Data one next to another.

Then the verify code will grab each Signature by its offsets within the sigdata. These offsets could be hardcoded within the code. The sigdata will be accessible in the Wasm Memory in the same manner as in other similars such as svm_tx_range

The best way to describe the whole mechanism is by examples.
Say we have a Single Signature Scheme with 64 byte-long signatures and 32 byte-long public keys.

In that case, the code of the verify could be similar to this pseudo-code:

func verify() -> bool {
	(sigdata_start, sigdata_end) <- svm_tx_sigdata_range() 

	;; computing the `sigdata` length (in bytes)
	sigdata_length <- sigdata_end - sigdata_start + 1

	;; asserting that we have 64 exactly bytes in the `sigdata`
	ASSERT sigdata_length == 64

	;; The raw transaction (WITHOUT the `Signature Data`)
	;; sits in memory addresses: `tx_start`..`tx_end` (inclusive)
	(tx_start, tx_end) <- svm_tx_range()

	;; load variable with var_id=0 under the `Immutable Section` (section_id=0) 
	;; that variable holds the `PubKey` previously given in constructor
	;; the length of the `PubKey` is 32 bytes (`256 bits`)
	var_id <- 0
	section_id <- 0
	pub_key <- svm_load256(var_id, section_id)

	;; `svm_sig_verify` assumes the `sigdata` and `pub_key` are 64 and 32 bytes respectively.
	valid <- svm_sig_verify(tx_start, tx_end, sigdata_start, pub_key)
	return valid
}

;; Should be implemented as Host Function
fn svm_sig_verify(tx_start: i32, tx_end: i32, sig_start: i32, pub_key: i32) -> bool { 
  ...
}

A few notes:

• svm_tx_sigdata_range Should return a tuple containing the memory range holding the sigdata.
• section_id - The additional section_id to part of the host functions is explained at SVM Code Reuse between Templates.
• svm_sig_verify - this is the host function that should be implemented as a result of this SMIP.
  In practice, there might be more than one Digital Signatures Verification host function.

Now, let's see what the verify of a MultiSig 2-3 might look like in pseudo-code:

func verify(pk_idx1: byte, pk_idx2: byte) -> bool {
	ASSERT pk_idx1 in 0..3 AND pk_idx2 in 0..3 AND pk_idx1 <> pk_idx2

	(sigdata_start, sigdata_end) <- svm_tx_sigdata_range() 

	;; computing the `sigdata` length (in bytes)
	sigdata_length <- sigdata_end - sigdata_start + 1

	;; asserting that we have 128 exactly bytes in the `sigdata`
	ASSERT sigdata_length == 128

	;; The raw transaction (WITHOUT the `Signature Data`)
	;; sits in memory addresses: `tx_start`..`tx_end` (inclusive)
	(tx_start, tx_end) <- svm_tx_range()

	pk1 <- read_pub_key(pk_idx1)
	pk2 <- read_pub_key(pk_idx2)

	;; `svm_sig_verify` assumes the `sigdata` and `pub_key` are 128 and 32 bytes respectively.
	return 
		svm_sig_verify(tx_start, tx_end, sig_offset(sigdata_start, 0), pk1)
			AND
		svm_sig_verify(tx_start, tx_end, sig_offset(sigdata_start, 1), pk2)
}

func read_pub_key(pk_idx: byte) -> Blob {
	ASSERT pk_idx in 0..3 

	section_id <- 0
	pub_key <- svm_load256(pk_idx, section_0)
	return pub_key
}

fn sig_offset(sigdata_start: i32, index: i32) -> i32 {
	;; The 1st signature under `sigdata` starts at offset `sigdata_start`
	;; The 2nd signature under `sigdata` starts at offset `sigdata_start + 64`
	;; and so on...
	return sigdata_start + index * 64
}

A few notes:

• svm_load256 doesn't exist at the time of writing this SMIP.
  It seems likely that svm_load256, svm_store256, and similars will have to be added to SVM. (and SVM SDK and SVM ABI).
• The verify expects two numbers, each pointing to the corresponding Public Key variables stored at the Immutable Storage Section.
  The code assumes that the three public keys provided to the constructor (as part of the Account Spawn) are located at variables=0,1 and 2 under the Immutable Storage Section.
  That's why the code asserts that each input is within the range 0..3 (exclusive).
• sigdata holding the signatures is distinguished from the rest of the Transaction.
  The inputs to verify (pk_idx1 and pk_idx2) are stored in the verifydata buffer.
• This pseudo-code assumes that the sigdata contains two public keys, one after the other.
  It means that the first public key will be located as offset zero of the sigdata, and the second one will start at offset=32 of the sigdata.

Questions/concerns

TBD

Stakeholders and reviewers

@noamnelke
@lrettig
@neysofu
@avive
@moshababo

[lrettig]

Thanks Yaron! Made a couple of tiny fixes in the pseudocode, hope that's okay. Some questions:

we need to distinguish between: A Transaction, excluding the DS signatures. The whole Transaction, including the DS Signatures.

Can we refer to these as Transaction and InnerTransaction, to disambiguate?

For the multisig case, here we're assuming that there are two distinct signatures (blobs), one per pubkey. What if we wanted to do some form of signature aggregation, e.g., BLS, such that there's only a single signature blob?

The verify expects two numbers

• Doesn't verify need a generic function signature, which can handle the single-sig use case as well?

[YaronWittenstein]

I agree about being more precise. We can interchangeably use the terms InnerTransaction or Transaction Message.

So when saying a Transaction, we'd refer to the whole structure (Envelope + Message).
It might be more beneficial to mention whether the Envelope is included explicitly.

The signature of verify is generic, of course. In practice, the emitted Wasm will have a function called svm_verify with an empty input. The data is passed as a blob. Each Template (or even a function) could have its own ABI implemented.
We call it that blob verifydata (in the same way we call it calldata for other public functions).

[noamnelke]

I think the term Signature Scheme as used in this document is confusing. It's usually used to refer to actual cryptographic signature schemes (e.g. ECDSA, Schnorr, etc.) and not the way they're used (e.g. n-of-m multisig).

In the single-sig example you made signatures 64 bytes long and then in the multisig example 32 bytes long. It was a little confusing for me, especially since svm_dig_verify makes an assumption about the sig length. It should probably be 64 bytes in both examples.

[avive]

Minor terminology comment: Can we please change term DS signatures to Signature Data because I think that this is what we are talking about here - data of one or more signatures and it is obvious that this data is for DS, aka digital signatures. It is a bit confusing to me. Typically this data will just be one or more signatures but it is generalized to optionally include other things as far as I understand. If this is not the case then signature data can be defined as a list of one or more signatures.

[noamnelke]

I actually like Witness Data to keep it more general.

[YaronWittenstein]

I actually like Witness Data to keep it more general.

Sorry, @avive has asked first to rename to Signature Data 😃

[YaronWittenstein]

Minor terminology comment: Can we please change term DS signatures to Signature Data because I think that this is what we are talking about here - data of one or more signatures and it is obvious that this data is for DS, aka digital signatures. It is a bit confusing to me. Typically this data will just be one or more signatures but it is generalized to optionally include other things as far as I understand. If this is not the case then signature data can be defined as a list of one or more signatures.

done

[YaronWittenstein]

I think the term Signature Scheme as used in this document is confusing. It's usually used to refer to actual cryptographic signature schemes (e.g. ECDSA, Schnorr, etc.) and not the way they're used (e.g. n-of-m multisig).

In the single-sig example you made signatures 64 bytes long and then in the multisig example 32 bytes long. It was a little confusing for me, especially since svm_dig_verify makes an assumption about the sig length. It should probably be 64 bytes in both examples.

• Modified the second example to have 64 bytes for each Signature as well.
• Renamed svm_dig_verify to svm_sig_verify

[countvonzero]

made obsolete by current implemenation spacemeshos/go-spacemesh#3220