# Proposal: Create a Better BLSExpander

## tl;dr

- BLSWallet is currently *more expensive* for ordinary users, because our current expander doesn't work for them. (The expander is *essential*, not just nice-to-have.)
- Let's fix this by creating a better expander.
- This new expander will also delegate to specialized expanders at the top-level, so that future dApps can add specialized expanders. This avoids the need for dApps to run dedicated aggregators - instead they stay in the same ecosystem and everyone benefits from larger bundles and therefore lower costs.
- TODO: This proposal focuses on minimizing L1 (calldata) costs. This can be done to great effect, but the cost of L2 gas is much higher than expected (even before the expander's L2 gas), and may be prohibitive.

## The Problem

The use of BLS in BLSWallet and the whole point of bundling is about delivering cheaper transactions by only needing 1 signature instead of N signatures.

We use accounts' BLS public keys to identify them, and they are 128 bytes long. Ordinary ETH transfers are only 117 bytes long, so we're already 11 bytes over-budget, even if the signature cost was zero, and before including nonce, value, and, destination address.

It's actually a lot worse than that out-of-the-box. Every user operation currently adds 300+ bytes (non-zero equivalent).

A big advantage of ordinary transactions that we miss out on is that the from address of a transaction is implicit in its signature. At just 68 bytes, this is already very efficient, and it's where our cost savings need to come from.

Granted, with the current expander, when sending many transactions *from the same address*, you only pay the 128 bytes once. However, there are two big problems with this:

1. It's a narrow use case, basically just air droppers. (Approve+transfer is affected but it's not enough to get a saving.)
2. The same saving can be achieved easier and cheaper by just putting multiple actions in an operation, so this isn't really a BLS use-case.

## Prior thoughts/work
- https://ethresear.ch/t/rollup-diff-compression/7933
- Expander: Simple param deduplication
- HubbleBLS: address indices, and possibly param compression
- PSE: byte compression (jz to link)
- VB: https://twitter.com/VitalikButerin/status/1554983955182809088

## The Solution

We create a much better expander using 3 main strategies:

1. Operate at the byte level so that savings can be made even when fields are not repeated
2. Store data like BLS public keys on-chain so they can be de-duplicated across many bundles, not just within one bundle
3. Start each encoded transaction with a switch between different expanders, and allow new expanders to be registered

### VLQ Encoding

This is a technique for encoding small (but unbounded) integers in a variable length such that:

| Range | Bytes Used |
| - | - |
| 0-127 | 1 |
| 128-16,383 | 2 |
| 16,384-2,097,151 | 3 |
| Max(uint256) | 37 |

In some cases these numbers will be allocated on a first-come first-served basis. In those cases, it would probably make sense to reserve some of the small numbers to ensure they are used effectively (finite number of small length places). There's also potential to make ERC721 tokens out of them to help raise money for subsidizing transactions.

[More about VLQ](https://en.wikipedia.org/wiki/Variable-length_quantity).

### Top-level Expander

Each operation should begin with a VLQ indicating which specific expander should be used to decode it.

(For maximum generality, specialized expanders will return an array of operations, but normally there will be just one operation inside.)

contract BLSExpander {
    mapping(uint256 => address) public expanders;
    uint256 public expanderCount = 0;

    // Potential to use fallback() instead to save 4 bytes
    function run(bytes calldata input) external {
        // Loop until all bytes consumed:
        //   Read VLQ
        //   Delegate to specialized expander
        //   Accumulate operations
        // Call VerificationGateway
    }

    function registerExpander(address expander) external {
        expanders[expanderCount] = expander;
        expanderCount++;
    }
}

### Fallback Expander

To ensure that all operations are supported, it is important to include a fallback expander which can encode any operation. This expander might still do something like RLP to improve over the raw abi (significant, but not as dramatic as specialized expanders).

### BLS Public Key and Address Registration

Our goal is to enable regular users to encode simple operations in about 30 bytes. BLS public keys are 128 bytes, so it is essential that they are stored on-chain and given a more compact representation.

contract AddressRegistry {
    mapping(uint256 => address) public addresses;

    function register(uint256 shortAddress, address addr) external {
        require(addresses[shortAddress]) == address(0);
        addresses[shortAddress] = addr;
    }
}

contract BLSPublicKeyRegistry {
    // Similar
}

Note: `uint256` occupies 32 bytes, which is far too many, but the idea is to use small numbers so that a compact encoding like VLQ can be used for them.

### Transfer Amount Encoding

Transfer amounts have a lot of excess precision. In the worst case, 32 bytes are used for this purpose. Even in ordinary transactions, where this value benefits from RLP encoding, sending 1 ETH still consumes about 9 bytes because of all the hidden decimal zeros.

Of course, if you wish to use that precision, we can't do much better than RLP's sizing. The fallback expander will still be available in the unusual case where you need this precision (or you could have an expander which leaves transfer amount alone but still helps with other fields).

With just 3 bytes (=24 bits), we can provide 6 digits of precision and specify 16 different orders of magnitude:

Amount = a * 10 ** (b + 3)

0.0123 ETH = 123 * 10 ** (11 + 3):
    0000 0000 0000 0111 1011   1011 (0x0007bb)
    ^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^
                       a=123   b=11

Min = 1000 Wei = 1 * 10 ** (0 + 3)
    0000 0000 0000 0000 0001   0000 (0x000010)
    ^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^
                         a=1    b=0

Max = 1048575 ETH = 1048575 * 10 ** (15 + 3)
    1111 1111 1111 1111 1111   1111 (0xffffff)
    ^^^^^^^^^^^^^^^^^^^^^^^^   ^^^^
                   a=1048575   b=15

 0.0004    => 00004b
 0.0112    => 00070b
 0.0019432 => 04be88
 0.0054    => 00036b
 0.0022    => 00016b
 1.1       => 0000be
 0.01      => 00001d
 1.39942   => 222a6a
60         => 0003cf
 0.533     => 00215c
 0.0925    => 0039db
 0.005525  => 015959
 0.012282  => 02ffa9
 0.0045    => 0002db
 0.03      => 00003d
 5.6       => 00038e
 0.013     => 0000dc
 0.0012    => 0000cb
 0.01      => 00001d
 0.0356    => 00164b

By analyzing the most recent 20 blocks on mainnet (script in appendix), I found that 41% (203/499) regular ETH transfers have amounts that are encodable with this method.

(41% may seem low, but this is without economic incentive to be compatible. It's likely that most of the remaining 59% are more interested in paying a lower fee than using more than 6 digits of precision.)

### Gas Limit Encoding

For expanders that specialize on a particular operation, they can use a fixed gas limit and avoid users needing to include any bytes for it.

When the gas limit is unknown, a single byte suffices by allowing <3.4% rounding error:

| Byte | Gas | | Byte | Gas | | Byte | Gas | | Byte | Gas |
| - | - | - | - | - | - | - | - | - | - | - |
| 18 | 18,998 | | 82 | 161,088 | | 146 | 1,365,875 | | 210 | 11,581,346 |
| 19 | 19,643 | | 83 | 166,559 | | 147 | 1,412,266 | | 211 | 11,974,696 |
| 20 | 20,310 | | 84 | 172,216 | | 148 | 1,460,232 | | 212 | 12,381,405 |
| 21 | 21,000 | | 85 | 178,065 | | 149 | 1,509,828 | | 213 | 12,801,927 |
| 22 | 21,713 | | 86 | 184,113 | | 150 | 1,561,107 | | 214 | 13,236,733 |
| 23 | 22,451 | | 87 | 190,366 | | 151 | 1,614,129 | | 215 | 13,686,306 |

function decodeGasLimit(byte) {
  return Math.floor(10_414 * Math.exp(0.0334 * byte));
}

decodeGasLimit(0); // 10,414
// less than half of the current minimum gas for any tx

decodeGasLimit(21); // 21,000
// exactly the amount needed for an ETH transfer

decodeGasLimit(255); // 52,059,941
// more gas than anyone needs (probably... there's always fallback 🤷‍♂️)

decodeGasLimit(51)/decodeGasLimit(50); // 1.034
decodeGasLimit(101)/decodeGasLimit(100); // 1.034
// Gas limits are only 3.4% apart, so on average your gas will be only
// 1.7% higher than necessary due to rounding

Note that this will require wallets to actually sign for a different gas value, otherwise the signature won't be valid.

### Nonce Encoding

In general, nonces can be excluded because they can be read from the contract wallet.

However, to avoid signatures being invalidated by reading the wrong nonce, a single byte could be used to encode `nonce % 256`. The expander would then read the nonce from the contract wallet and round down to the nearest value that is consistent with our value for `nonce % 256`. This could still fail, but only if the nonce is 256 operations in the past, which should be detected before submitting on chain.

## Example

A bundle containing 3 ETH transfers and 7 USDC transfers would use 188 bytes of data:

0x
c65cd289                    // BLSExpander.run
01 00007d aaaaaaa0 bbbbbbb0 // ETH  Transfer:    0.07       from a0 to b0
01 001ffb aaaaaaa1 bbbbbbb1 // ETH  Transfer:    0.0511     from a1 to b1
01 f04b67 aaaaaaa2 bbbbbbb2 // ETH  Transfer:    0.00984246 from a2 to b2
02 00023e aaaaaaa3 bbbbbbb3 // USDC Transfer: $  3.50       from a3 to b3
02 0003cf aaaaaaa4 bbbbbbb4 // USDC Transfer: $ 60.00       from a4 to b4
02 00038e aaaaaaa5 bbbbbbb5 // USDC Transfer: $  5.60       from a5 to b5
02 222a6a aaaaaaa6 bbbbbbb6 // USDC Transfer: $  1.39942    from a6 to b6
02 0007bd aaaaaaa7 bbbbbbb7 // USDC Transfer: $  1.23       from a7 to b7
02 0007be aaaaaaa8 bbbbbbb8 // USDC Transfer: $ 12.30       from a8 to b8
02 0007bf aaaaaaa9 bbbbbbb9 // USDC Transfer: $123.00       from a9 to b9
1125cc903859c3981f6d7dd7125148f353ab58567360493adc56f594a07bebbf // Sig
20022aaee56fecdfc3cffd7a56cf328e6eea6180c222f3b0b38cf559c9b24509 // Sig

| Metric | Value | Unit |
| --------------------- | ------------: | ---- |
| Total Bytes | 305 | |
| L1 gas | 4,880 | |
| L1 cost | $0.113 | USD |
| L2 processBundle gas | 1,710,000 | |
| L2 processBundle cost | $0.282 | USD |
| L2 expansion gas | ? | |
| L2 expansion cost | ? | USD |
| Total cost | ? + $0.395 | USD |
| Per-op cost | ? + $0.040 | USD |

(TODO: Got wrecked by L2 gas... need to double-check this 😕.)

Context:

| Metric | Value | Unit |
| --------------------- | ------------: | ---- |
| ETH price | $1,650 | USD |
| L1 gas price | 14 | gwei |
| L2 gas price | 0.1 | gwei |
| Regular transfer cost | $0.049 | USD |

Breakdown of an ETH transfer:

0x
01          // Use ETH transfer expander
aa aa aa aa // Index of sender's BLS public key in registry
bb bb bb bb // Index of recipient's address in registry
00 07 bb    // 0.0123 ETH

(See the appendix for what this looks like when expanded.)

Breakdown of a USDC transfer:

0x
02          // Use USDC transfer expander
aa aa aa aa // Index of sender's BLS public key in registry
bb bb bb bb // Index of recipient's address in registry
00 07 bd    // $1.23

Both types of operations consume 12 bytes, so that's 120 bytes in total.

All other bytes are a fixed per-bundle overhead, so as operations in a bundle grow, the L1 cost approaches a theoretical minimum of 12 * 16 = 192 gas, which currently costs $0.0044 (about half a cent).

To complete the `data` sent to `BLSExpander`, we need to add bytes for the BLS signature and 4 bytes for the functionId of `BLSExpander.run`, bringing the `data` field to 188 bytes.

(It's possible to avoid the 4 byte functionId using `fallback()`.)

Finally, we need to account for the remaining fields of the top-level EOA transaction. It's about 117 bytes, covering the sender's ECDSA signature, the address of the expander, nonce, etc.

This gives us a grand total of 305 bytes for our 10 transactions.

### Appendix

#### Script Used to Analyze Transfer Amounts

Paste this into your browser's dev console with a wallet extension that provides `window.ethereum`.

const blockNumbers = [...new Array(20)]
  .map((_, i) => '0x' + Number(i + 16472849).toString(16));

const blocks = await Promise.all(
  blockNumbers.map(n => ethereum.request({
    method: 'eth_getBlockByNumber',
    params: [n, true],
  })),
);

const transactions = blocks.map(b => b.transactions).flat();

const transferTransactions = transactions.filter(
  t => t.gas === '0x5208' && t.input === '0x',
);

function toDigitsAndExp(n) {
  if (n === 0n) {
    return { digits: 0n, exp: 0, digitCount: 0 };
  }

  let exp = 0;
  while (n % 10n === 0n) {
    n /= 10n;
    exp++;
  }

  const digits = n;

  let digitCount = 0;

  while (n > 0n) {
    n /= 10n;
    digitCount++;
  }

  return { digits, exp, digitCount };
}

const transferAmounts = transferTransactions.map(
  t => toDigitsAndExp(BigInt(t.value)),
);

console.log(transferAmounts.sort((a, b) => a.digitCount - b.digitCount));

#### Example of an Expanded User Operation

sender's BLS public key
2409925687d52a67b435a011cf9ec82d390300cd12e5842d2a0c5e1c27898551
0c4a8cbcc96cada40301e1d2a2d68425b5cf0e18f5cb12fa272f841017c36776
27b9f42b237d75bcb0473e2eada290e62ec77048187484f8952fffe0239f7ba9
24f1fc8a1f7256dc2914e524966309df2226fd329373aaaae1881bf5cd0c62f4

abi overhead
0000000000000000000000000000000000000000000000000000000000000020

nonce
0000000000000000000000000000000000000000000000000000000000000000

(another 32-byte word will be in here somewhere for gas limit)

more abi overhead
0000000000000000000000000000000000000000000000000000000000000040
0000000000000000000000000000000000000000000000000000000000000002
0000000000000000000000000000000000000000000000000000000000000040
00000000000000000000000000000000000000000000000000000000000000c0

ethValue (0.0123 ETH)
0000000000000000000000000000000000000000000000012300000000000000

contractAddress (recipient's address)
00000000000000000000000070997970c51812dc3a010c7d01b50e0d17dc79c8

encodedFunction (empty)
0000000000000000000000000000000000000000000000000000000000000060
0000000000000000000000000000000000000000000000000000000000000000

ethValue (0.000012 ETH, for tx.origin to pay for gas)
0000000000000000000000000000000000000000000000000012000000000000

contractAddress (AggregatorUtilities)
0000000000000000000000004bd2e4e99b50a2a9e6b9dabfa3c8dcd1f885f008

encodedFunction (0x1dfea6a0 - sentEthToTxOrigin)
0000000000000000000000000000000000000000000000000000000000000060
0000000000000000000000000000000000000000000000000000000000000004
1dfea6a000000000000000000000000000000000000000000000000000000000