Permit batching transactions

[mvines]

Right now a Transaction contains a single command to a single program. This means that more complex operations that require multiple commands to complete will run at the clockrate of finality.

The proposal to resolve this is to permit multiple instructions to be batched within a single Transactions. Such a Transaction is only confirmed if all instructions within it successfully complete.

A sketch of what the current Transaction struct turns into is:

#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
struct Instruction {
    /// the program_id to execute
    program_id: Pubkey,
    /// These indicies point to Transaction::keys array and accounts 
    /// for those keys will be loaded for execution
    keys: Vec<u8>,
    /// Userdata to pass to the program
    userdata: Vec<u8>,
}

#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
pub struct TransactionData {
    /// The `Pubkeys` that are executing this transaction userdata.  
    /// The meaning of each key is program-specific.
    pub keys: Vec<Pubkey>,

    // Indices into the `keys` vector vector indicating the `Pubkey`s that are
    // expected to sign this `TransactionData` struct
    pub signed_keys: Vec<u8>

    /// The ID of a recent ledger entry.
    pub last_id: Hash,

    /// The number of tokens paid for processing and storage of this transaction.
    pub fee: i64,

    /// Execute the instructions atomically and in order
    pub instructions: Vec<Instruction>,
}

#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
pub struct Transaction {
    /// A tuple of digital signatures that signed the `data` field.
    /// The order of these signatures must match the order of `Pubkey`s
    /// identified by the signed_keys[] vector in `data`.
    pub signatures: Vec<Signature>,

    pub data: TransactionData,
}

[aeyakovenko]

@mvines the indecies should be signed as well. I think we will need to change the entry point also

[garious]

Your SignedTransaction contains only the unsigned part.

[garious]

We've called it TransactionData in previous iterations.

[garious]

How about signatures: Vec<PubKey, Signature>? And then just don't include those pubkeys in keys.

[garious]

nevermind. I see how that'd break your Instruction definition.

[mvines]

I updated the sketch to include:

• TransactionData rename
• the indices for the signature pubkeys are now also signed

[garious]

I like it!

[garious]

Any feelings about that u8 index? I find it easy to imagine a single batch containing far more than 256 public keys, although difficult in practice if we continue to limit transactions to single UDP packets. But what if we offered a way to submit very large transactions over TCP. Should we have a separate binary format for that? One that can index thousands or millions of pubkeys?

[aeyakovenko]

There are other ways to solve for huge transactions. Users could upload transactions that get put together and then executed atomically. Large sessions are hard to defend against spammers, so the piecemeal approach might be better for us anyways. I just hate to waste those bits on zeros :)

[garious]

A more conservative design:

#[derive(Serialize, Deserialize, Debug, PartialEq, Eq, Clone)]
pub struct Transaction {
    /// A digital signature of `keys`, `interpreter_id`, `last_id`, `fee` and `bytecode`,
    /// signed by `from`.
    pub from_signature: Vec<Signature>, 

    // The owner of this transaction.
    pub from: Pubkey, 

    /// A list of additional signatures. Each signature authorizes `bytecode` to spend
    /// tokens from the corresponding Pubkey and to modify the memory it refers to.
    /// It is a signature of the `from_signature` field and proves ownership of the
    /// corresponding Pubkey.
    pub authorizations: Vec<(Pubkey, Signature)>,

    /// The addresses of additional memory referenced by `bytecode`. The
    /// network hosts this memory, and uses these keys to identify them. If
    /// memory has not yet been allocated for it, bytecode may spend its
    /// tokens. Otherwise, bytecode may only read that pubkey's memory
    /// and credit it tokens.
    /// * keys[0] - Typically the process_id, which holds the process state.
    pub keys: Vec<Pubkey>,

    /// The address of the program that will interpret `bytecode`.
    pub interpreter_id: Pubkey,

    /// The ID of a recent ledger entry. This tells the network how long it's been
    /// since this transaction was created and what recent transactions
    /// the provided program is unaware of.
    pub last_id: Hash,

    /// The number of tokens paid for processing and storage of this transaction.
    pub fee: i64,

    /// The compiled data that will be interpreted by the interpreter at `interpreter_id`.
    pub bytecode: Vec<u8>,
}

Differences from existing code:

• bytecode hosts Vec<Instruction>, not Instruction. ...or one type of Instruction in that language is Box<Vec<Instruction>>.
• program_id is renamed interpreter_id, suggesting it is a particular type of program - one that implements invoke(accounts, bytecode). The representation that was compiled to bytecode might more precisely be labeled "program."
• from is moved out of keys, since it is always required and means something to signature verification.

Differences from previous proposal:

• Each signature in signatures signs from_signature, alleviating the need for TransactionData.
• A single transaction cannot switch between interpreters. Instead, a higher-level interpreter such as Budget would wrap calls to lower-level interpreters such as System.
• All bytecode instructions would have access to the accounts of all provided pubkeys. To keep instructions composable, bytecode would need to lookup accounts by Pubkey instead of making assumptions about their position in keys or authorizations.

[garious]

Fixed in #1309

[mvines]

Wait, not so fast! We can't have a transaction signed by multiple keys yet.

[garious]

It couldn't before. Shouldn't that be a separate ticket?

[mvines]

If you want. The multiple key requirement is right in the initial issue description though:

    // Indices into the `keys` vector vector indicating the `Pubkey`s that are
    // expected to sign this `TransactionData` struct
    pub signed_keys: Vec<u8>

[garious]

@aeyakovenko, do you plan to upgrade the signature: Signature field to signatures: Vec<Signature>? That'll require changes to the GPU code. Can we ask @sakridge to take care of it? Once that's in place, adding signed_keys: Vec<u8> to instructions can be added without affecting GPU code.

[garious]

Added #1531 to track just that sigverify work.

[aeyakovenko]

@garious, yes, we need some way to pass a vector of signatures in the tx.

[mvines]

Closing, as what remains here is #1531