Compressed transactions

TL;DR; with a few tricks, the size of a basic transaction can be reduced from 163 bytes to 12 bytes.

Standard, one party to another party, transactions are probably the most important operation on the chain. While it’s important to retain the genericity of the ledger, identifying and optimizing specific paths is definitely worthwhile. I’ve been a longtime proponent of grabbing low hanging fruits in order to scale the capacity of the chain and this is clearly one of them. I recently heard Vitalik Buterin make a good case for transaction compression which made me want to run the numbers for Tezos. They are presented below:

Let’s look at the size of a standard transaction today:

  • First, there is the “branch”, a recent hash used to prevent replay attacks and create hard to fake forensic evidence about the chain’s history (useful if one is a bit paranoid about long-range attacks).

    That’s 32 bytes, followed by the operation data

  • The operation itself has a tag (1 byte), followed by 4 bytes to indicate how long the actual operation encoding will be, the encoding of the transaction itself, a 1 byte flag to tell us a signature is attached, and finally 64 bytes of signature.

    That’s 102 bytes so far, but we haven’t encoded the transaction itself yet.

  • The transaction has a tag to tell us… it’s a transaction. That’s 1 byte. We then have the source 22 bytes, the destination 22 bytes. There’s a 1 byte flag to tell us there is no “parameters” field.

  • We now have to encode the amount, storage_limit, gas_limit, counter, and fee. The size of those depends on how large the integers involved are. Let’s give them about 3 bytes each, that’s 15 bytes. We now have an extra 61 bytes to describe the transaction.

Total: about 163 bytes (depending on the length of the amounts etc)

How much can we compress that?

  • We can start by giving each address in Tezos a unique, incremental id. Assuming a generous four billion addresses, sender + receiver can fit in 8 bytes.

  • Most amounts do not need many digits of precision. A number between 0 and 1000 can be coded with 10 bits. Amounts cover 15 orders of magnitude at most in Tezos, for which 4 bits is enough. Let’s add 2 bits of precision in our numbers, we’ll get things like “6.78 ¾ × 10³ tez”. That’s now 2 bytes.

  • Gas limit and storage limit can be inferred from the fact that this is a basic transaction and thus they do not need to be provided. 0 bytes

  • Counter: while it’s important that the counter be signed as part of the transaction there is no need to actually include the counter in the transaction data as it can be inferred from the chain’s state. 0 bytes

  • Fee: this can be expressed as a percentage deviation from the average fee paid for transactions with a similar amount of gas / storage involved. 1 byte is plenty.

EDIT: while this is really efficient from a compression perspective it opens up an attack surface by manipulating fees. Another 1 byte solution which does not open up such an attack vector is to represent the fee with a 4 bit mantissa and 4 bit exponent, representing any number between 1 and 63,608 to within 1/16th.

  • Branch: while it’s important to sign the branch, the full hash does not need to be included in the transaction, 1 byte can tell us which branch to pick (by indicating the level modulo 256 of the block whose hash is being signed).

  • Signature: using BLS signatures those can all be non-interactively aggregated for the entire block. Almost 0 bytes (amortized).

Total: 12 bytes (no need for a byte tag, these can go in a specific part of the block), a 13× improvement.

With 500 kb blocks every minute, this could in principle fit about 700 basic transactions per second, though gas related to disk I/O (not bandwidth or block space) would become the bigger bottleneck.

The main technical roadblocks in implementing the above are:

  • Many small things need to be added to the context: running average of fees, assigning ids to addresses, etc. This is a straightforward but tedious task.

  • The scheme requires BLS signatures, otherwise, the gain is only a mediocre 2×.

    • While adding the bindings to a pairing library is not particularly burdensome, BLS signatures are unfortunately not yet well supported on hardware wallets.
    • There remains the very practical problem of choosing which curve to use, given that no standard has really emerged. While it’s certainly possible to introduce multiple curves (tz4, tz5, tz6 etc), this increases the cost of implementing clients, and thus it would make sense to take the time and select one that’s likely to have staying power (and be implemented on hardware wallets, see above).
  • There are subtleties involved in the baking software as we likely want the baker, not the transaction sender to perform the compression.

14 Likes

:100: Pruning the low hanging fruit for scaling wins :100:

I’d be interested to learn more about the potential implications for:

  • indexers (conseil, tzstats, nomadic indexer)
  • future proposals such as sapling. How much complexity would compressed transactions impose on privacy extensions for example?
1 Like