SMIP: Spacemesh Transactions Syntax and Binary Encoding

[avive]

Motivation

We need to specify the binary (packed) and decoded (into typed field) syntax of Spacemesh transactions.

We have 3 types of transactions and each type can be signed by one of 2 possible signature schemes: ed25519 or ed25519++.

1. Simple coin transfer transaction (to another account or app). See binary encoding spec here: #17
2. Spawn app transaction - create a smart wallet app from a deployed code-template.
3. Create app transaction - call a method on a smart wallet instance (app).

Wallets need to implement encoding of user-provided data into valid binary transaction, sign the binary data with one of the supported signature schemes, add signature fields to the binary tx data and submit them to the pool. Full nodes need to check the syntactic validity of user submitted transactions based on the the transaction's binary syntax.

The Spacemesh API needs to know how to decode a binary transaction (as stored on the mesh) and provide all the fields typed and unpacked to clients.

Specification

Glossary

• ed - ed25519 signature scheme. When used, transaction include a public key field.
• ed++ - custom ed25519 signature scheme, as implemented in this library. When used, transaction does not include a public key field.
• network_id - 32 bytes binary data that is unique for a Spacemesh network, e.g. a testnet or a mainnet. The network id is computed by a full node based on immutable network params and genesis data.
• address - a Spacemesh address identifies an account. It is the 20-byte suffix of an account's public key.

Transactions data is encoded in binary format using the XDR format.

Following is the the binary layout of each of the supported transaction type, declared in accordance with IETF RFC 4506 (XDR).

Simple Coin TX

struct SimpleCoinTx {
    unsigned int TTL; // 32-bit
    opaque Nonce[1];
    opaque Recipient[20];
    unsigned hyper Amount;
    unsigned hyper GasLimit;
    unsigned hyper GasPrice;
};

Call App Transaction

struct CallAppTx {
    unsigned int TTL; // 32-bit
    opaque Nonce[1];
    opaque AppAddress[20];
    unsigned hyper Amount;
    unsigned hyper GasLimit;
    unsigned hyper GasPrice;
    opaque CallData<>;
};

Spawn Transaction

struct SpwanAppTx {
    unsigned int TTL; // 32-bit
    opaque Nonce[1];
    opaque TemplateAddress[20];
    unsigned hyper Amount;
    unsigned hyper GasLimit;
    unsigned hyper GasPrice;
    opaque CallData<>;
};

---

SignedTransaction Binary Format

When a transaction is stored or transmitted, the following format for a signed transaction is used:

struct SignedTransaction {
    opaque Type[1];
    opaque Signature[64];
    opaque TransactionData<>;
    opaque *PubKey[32]; // optional, depending on Type.
};

Type

A 1-byte enumeration specifying the transaction type.

The least-significant-bit defines the signature scheme: 0 ⇨ ED; 1 ⇨ ED++.

The remaining 7 bits define the type of the internal transaction:

enum TransactionType {
    COIN_TX   = 0, // coin transaction
    EXEC_APP  = 1, // exec app transaction
    SPAWN_APP = 2, // spawn app
    // future types to be added here
};

The entire type byte can also be interpreted as a single enumeration, defined as follows:

enum TransactionAndSignatureType {
    COIN_TX_ED       = 0, // coin transaction / ed
    COIN_TX_EDPLUS   = 1, // coin transaction / ed++
    EXEC_APP_ED      = 2, // exec app transaction / ed
    EXEC_APP_EDPLUS  = 3, // exec app transaction / ed++
    SPAWN_APP_ED.    = 4, // spawn app / ed
    SPWAN_APP_EDPLUS = 5, // spawn app / ed++
    // future types to be added here
};

Signature

Signature is a digital signature, using the specified signature scheme, of a TransactionAuthenticationMessage constructed from the transaction.

TransactionAuthenticationMessage

TransactionAuthenticationMessage is a data structure that is never transmitted or stored, but constructed on-the-fly to sign transactions and validate their signature.

struct TransactionAuthenticationMessage {
    opaque NetworkID[32];
    opaque Type[1];
    opaque TransactionData<>;
};

NetworkID is a 32-byte unique identifier that is never transmitted, but used to ensure that transactions cannot be valid on more than a single network. This prevent replay attacks and other bugs which may be caused by a node processing a transaction that was not created and signed for the network it is being added to.

TransactionData

The actual bytes of the transaction object.

In a TransactionAuthenticationMessage, the CallData field (if present) should be replaced with a 32-byte sha256 sum of the actual call data:

opaque CallDataHash[32];

Signing a Transaction

Input: transaction type, transaction data, network ID, private key. Output: SignedTransaction binary data.

1. Obtain the XDR binary encoding of the TransactionAuthenticationMessage.
2. Sign this binary data with the given private key, using the signature scheme specified in the given transaction type.
3. Return a SignedTransaction.

Note that the SignedTransaction doesn't include the NetworkID. Both the signer and validator should have this data preconfigured.

Decoding and Verifying a Signed Transaction

Input: A binary encoded signed transaction. Output: A transaction structure of a transaction in one of the supported types. Signature. Transaction type byte.

1. Decode the SignedTransaction.
2. Compose an TransactionAuthenticationMessage from the pre-configured network ID, the given transaction type and the given transaction data.
3. If regular ED is specified in the transaction type, use the provided public key to validate the TransactionAuthenticationMessage.
   ---
   Otherwise, extract the public key from the signature and the TransactionAuthenticationMessage.
4. Based on the transaction type deserialize the transaction data into the relevant native transaction representation.

TransactionID

The TransactionID is not a field in the actual transaction object, it's calculated on the fly and used to index and reference transactions. Blocks contain a list of TransactionIDs and therefore this definition is part of the consensus rules.

The TransactionID is the 32-byte SHA256 hash sum of the SignedTransaction.

[lrettig]

Send the serialized transaction to node using the node's API service.

Note that we don't currently have an API endpoint for this. Opened https://github.com/spacemeshos/api/issues/78 to investigate.

[avive]

moved to this smip's first comment.

[avive]

Send the serialized transaction to node using the node's API service.

Note that we don't currently have an API endpoint for this. Opened spacemeshos/api#78 to investigate.

We have TransactionService.SubmitTransaction() for this, what am I missing?

[noamnelke]

I'm for removing SigId. If PubKey is included use ed25519, otherwise use ed25519+.

We should also include a txFormatVersion byte.

If we ever intend to support additional schemes (I would bet we won't) we should introduce a new version of the transaction format, which might be required anyway since it's hard to anticipate what changes we'll need (e.g. we may need more than just a pubkey). Including a tx version byte will also enable other future unforeseen changes.

[lrettig]

Send the serialized transaction to node using the node's API service.

Note that we don't currently have an API endpoint for this. Opened spacemeshos/api#78 to investigate.

We have TransactionService.SubmitTransaction() for this, what am I missing?

You're not missing anything. We didn't have one, then we modified that endpoint in https://github.com/spacemeshos/api/pull/79, and now here we are :)

[lrettig]

Including a tx version byte will also enable other future unforeseen changes.

I imagine something like supporting a different VM would be more likely than a new signature scheme, but I wouldn't rule that out either. This is of course a good idea.

[y0sher]

I'm for removing SigId. If PubKey is included use ed25519, otherwise use ed25519+.

We should also include a txFormatVersion byte.

If we ever intend to support additional schemes (I would bet we won't) we should introduce a new version of the transaction format, which might be required anyway since it's hard to anticipate what changes we'll need (e.g. we may need more than just a pubkey). Including a tx version byte will also enable other future unforeseen changes.

I'm also in for including a tx format version byte. and I'm also in for supporting only one signature scheme for now as it looks weird to duplicate everything to support both (unless there's a very good reason for it)..

[avive]

I have updated the smip initial comment with a proposal for an XDR binary format for transactions. The basc idea is to use xdr's discriminated unions to specify struct format based on a discriminant which specifies the transaction type and noam's idea of a type per transaction type and a signature type. There are other ways to do it, for example, have only 3 tx types instead of 6 (coin, spawn and call) and encode the existence of public key and the sig scheme using another union. A signature union can have just a signature or a signature and a pub key, based on a discriminant included in the tx as a data field. e.g. SignatureType.... Versioning is supported by just adding a new tx type and the xdr schema for the new version.

[lrettig]

I agree with Noam that we only need 3 tx types, and that the signature type (assuming we end up having two) can be implicit based on the existence or non-existence of the pubkey.

[avive]

We need to update the encoding and decoding part of the spec to include the net id to the binary payload that is being signed and verified.

[avive]

I've updated the smip to include a netid in the signed message without having to have the netid in transaction binary payloads. @noamnelke @lrettig - what we talked about recently. Trying to formulate it before it needs to be implemented.

[avive]

@moshababo @noamnelke - I've updated the smip based on the most recent decisions regarding network id: it is 20 bytes binary data and should be prefixed to binary transaction payload when signing and verifying signatures.

[avive]

Updated net-id to 32 bytes from 20 bytes.

[avive]

@noamnelke @lrettig as part of work needed before implementing this fully, we need to formally spec network id - how it is created from net int id, and other genesis params. There was a discussion about this with research. Do we have it written down somewhere?

[lrettig]

There was a discussion about this with research. Do we have it written down somewhere?

See #26

[avive]

I don't think so - maybe deep inside research forum. We need it properly speced out.

[avive]

I added some clarifications to the spec based on a discussion I had with @noamnelke . Next step for this important spec is to discuss the non-xdr optimization that noam is proposing to save 4 bytes for smart contract transactions in an r&d call.

[noamnelke]

to save 4 bytes for smart contract transactions

It's actually 8 bytes. The inner transaction would have 4 bytes preceding the CallData and the SignedTransaction would have another 4 bytes preceding the TransactionData.

Non-smart contract transactions would also save 4 bytes (preceding the TransactionData), where the savings may actually be more meaningful, since I expect to have more of these types of transactions.

[avive]

I'm all for saving as many bytes as we can even if we do our own codec. I hope we can get closure on this with research this week.

[sudachen]

I think it's not a good idea to have Ed and EdPlus transactions as different structures. The reason is it's not an attribute of the transaction but of the signed transaction. So I offer to move the public key for ed signing to the signed transaction. For the ed++ this field can have zero length.

[noamnelke]

You still need to account for the sig-scheme in the transaction type. I think that a mapping:

TransactionType -> relevant Go type

Is easy to implement. The ED types can be implemented by Go type inheritance. E.g.

type SimpleCoinTransaction struct {
    TTL       uint32
    Nonce     byte
    Recipient Address
    Amount    uint64
    GasLimit  uint64
    GasPrice  uint64
}

type SimpleCoinTransactionED struct {
    SimpleCoinTransaction
    PublicKey PublicKey
}

We can then use the internal SimpleCoinTransaction when handling this type of transaction.

I don't think it will be easier or cleaner to implement if we put the public key in the signed transaction, but I'm open to hear why if you're still unconvinced.

[sudachen]

There is one very important question when publicKey is set and how does it relate to privetKey which used for signing transaction? Also why we need publicKey in transaction at all? I mean why we need to set public key in unsigned transaction? As I see when we have publicKey in unsigned transaction we have abstraction leaking and layers crossing.

So when we need to sign AuthMessage we need to update public key in transaction data? When we need to verify signed transaction we need access to transaction internals to get public key, so there is no reason to have signedtransaction and authmessage abstractions because they bouned to every exact transaction. As result signing/verification code can't be decoupled from every exect transaction and have to know about all transaction types. It happens because public key is an attribute derived from signed transaction and is not public attribute of transaction. So there is no difference between Ed and Ed++ transactions just between methods of signing. After decoding the both have read access to public key via Transaction interface but no one contains it directly.

[noamnelke]

You're right, you convinced me. It should be part of the SignedTransaction. If/when we get rid of XDR we'll just append it to the end of the signed transaction (and it won't be part of the TransactionAuthenticationMessage). For now, you can make it a variable sized field and leave it empty when not needed, or make it a fixed size field and leave it as zeros.

[lrettig]

TransactionType is nice, but for future proofing don't we think we might want a version field in front as well?

[noamnelke]

Custom Encoding for Transactions

The Problem with XDR

XDR's variable-length data field is always "counted", meaning that the actual data is prefixed with its length (a 4-byte integer).

Our SVM transaction types all contain a CallData field, which is of variable length.

On-the-wire, and probably on-disk, the transaction data is wrapped with a SignedTransaction, which includes the Type, Signature and (for non-ED++ transactions) the PubKey. Because the TransactionData in this structure is a variable-length byte array, it must, again, be "counted" adding another 4 bytes of overhead, 8 in total. This is in addition to higher layers (communication and persistence protocols) wrapping the transaction object with metadata, including the length of the entire object.

Additionally, XDR fields are always padded to be in 4-byte increments, so our Type and Nonce fields, which are a single byte will actually take up 3 additional bytes of overhead, each. This totals 14 wasted bytes per transaction.

Possible Solutions

XDR's Discriminated Unions

We could reduce the overhead to 4 bytes if we don't encode the TransactionData as a variable-length byte array and use XDR's Discriminated Union instead. However, this is not supported by Go's built-in XDR library, and while other libraries support this feature, it's a little clunky to use. It also only saves 4 of the 8 wasted bytes.

Discriminated unions won't allow us to reduce any of the 6 wasted bytes due to 4-byte alignment.

Using Custom Encoding

I propose to inherit XDR's rules (e.g. endian-ness) but compose the fields ourselves. This allows us to not add any overhead for variable-length fields, since we know the length of the entire transaction object.

This also allows us to avoid wasting bytes on padding for our single byte fields.

[avive]

my 2 cents on this: xdr discriminated unions are indeed clunky to use - I tried. I support 100% custom simple binary encoding to save on tx sizes. I think that saving on size clearly overpower the con of diverging from a battle-tested codec. It should not be an issue if we write enough tests to cover all major codec use cases and as the codec is a quite straightforward binary one, especially since we reuse xdr rules when applicable.

[avive]

So - is this Smip final and we can start implementing across the platform?

[noamnelke]

@sudachen I've added the following to the part about TransactionData:

In a TransactionAuthenticationMessage, the CallData field (if present) should be replaced with a 32-byte sha256 sum of the actual call data:

opaque CallDataHash[32];

So, unfortunately, this requires creating separate structs for the transaction data when used for signing and for everything else. If you have a more efficient idea lmk.

cc: @avive

[sudachen]

I don't understand why it needs. What the problem it solve? For protocol, we sign not a "original tx bytes + a hash of the calldata". We sign hash of "original tx bytes". I really don't understand the difference wich additionl hash gives as. But yes, if it required, I have better idea - add to AuthMessage field Digest the SHA-512 digest of data for signing. So the AuthMessage be the same, signable, can be used for ID generation, and transaction encoding. Also it will not change size or layout of Signed or Decoded transactions.

[noamnelke]

I should have explained the motivation for this change, I apologize.

We want to implement (later, not at this point) pruning for transactions that didn't make it into the global state. We can't prune the entire transaction because then it's impossible to validate that this transaction shouldn't have made it into the global state, so we must preserve the fields used to prioritize or validate transactions - TTL, Nonce, Amount, GasLimit, GasPrice.

The remaining fields, the destination address and the call data, can be pruned. But it must be possible to validate the signature or extract the public key. By replacing the CallData with a hash of the call data in the signed message we can preserve the hash and prune the rest of the data. Since call data can be very large, saving only a hash (20 or 32 bytes) can potentially enable us to prune hundreds of bytes per transaction.

---

I've given it some more thought and I think we can simplify it considerably. I've written a forum post so research can sign-off on it: https://community.spacemesh.io/t/transaction-signing-and-pruning/141

@sudachen please take a look at the post and comment on it if you have anything to add.

[sudachen]

I implemented this requirement for smart contract transactions as a proposal without abstraction leaking. Looks like there is no reason to do pruning for SimpleCoin transactions (it just will take additional space). Please review.

Also, I recommend using Xrd just for encoding the transaction body, but not for SignedTransaction because of the last is just bytes concatenation. It will reduce space without dropping XDR.

[countvonzero]

implemented as described https://github.com/spacemeshos/go-spacemesh/issues/3220