Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

SMIP: Spacemesh Transactions Syntax and Binary Encoding #23

Open
avive opened this issue Jun 22, 2020 · 31 comments
Open

SMIP: Spacemesh Transactions Syntax and Binary Encoding #23

avive opened this issue Jun 22, 2020 · 31 comments
Assignees

Comments

@avive
Copy link
Member

avive commented Jun 22, 2020

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: SMIP: Spacemesh Reference Wallets - File Format and Accounts Derivation #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
Copy link
Member

lrettig commented Jun 22, 2020

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.

@avive
Copy link
Member Author

avive commented Jul 14, 2020

moved to this smip's first comment.

@avive
Copy link
Member Author

avive commented Jul 14, 2020

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
Copy link
Member

noamnelke commented Jul 14, 2020

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.

@avive avive changed the title SMIP: Spacemesh Transactions Syntax (WIP) SMIP: Spacemesh Transactions Syntax and Binary Encoding Jul 14, 2020
@lrettig
Copy link
Member

lrettig commented Jul 15, 2020

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 spacemeshos/api#79, and now here we are :)

@lrettig
Copy link
Member

lrettig commented Jul 15, 2020

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
Copy link

y0sher commented Jul 20, 2020

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
Copy link
Member Author

avive commented Jul 22, 2020

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
Copy link
Member

lrettig commented Jul 22, 2020

@avive
Copy link
Member Author

avive commented Aug 13, 2020

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 avive self-assigned this Aug 13, 2020
@avive
Copy link
Member Author

avive commented Aug 31, 2020

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
Copy link
Member Author

avive commented Sep 13, 2020

@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
Copy link
Member Author

avive commented Sep 21, 2020

Updated net-id to 32 bytes from 20 bytes.

@avive
Copy link
Member Author

avive commented Dec 27, 2020

@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
Copy link
Member

lrettig commented Dec 29, 2020

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

See #26

@avive
Copy link
Member Author

avive commented Dec 31, 2020

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

@avive
Copy link
Member Author

avive commented Dec 31, 2020

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
Copy link
Member

noamnelke commented Jan 3, 2021

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
Copy link
Member Author

avive commented Jan 3, 2021

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
Copy link

sudachen commented Jan 3, 2021

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
Copy link
Member

noamnelke commented Jan 3, 2021

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
Copy link

sudachen commented Jan 3, 2021

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
Copy link
Member

noamnelke commented Jan 3, 2021

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
Copy link
Member

lrettig commented Jan 5, 2021

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

@noamnelke
Copy link
Member

noamnelke commented Jan 5, 2021

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
Copy link
Member Author

avive commented Jan 5, 2021

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 avive assigned noamnelke and unassigned avive Jan 12, 2021
@avive
Copy link
Member Author

avive commented Jan 12, 2021

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

@noamnelke
Copy link
Member

noamnelke commented Jan 25, 2021

@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
Copy link

sudachen commented Jan 25, 2021

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
Copy link
Member

noamnelke commented Jan 26, 2021

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
Copy link

sudachen commented Jan 27, 2021

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants