Where would Halo2 fit in this chart?

Technology
#1

Chart showing scalability (chainsize) and privacy tradeoffs in Bitcoin, Liquid, Grin, Monero, and Zcash.
The last 4 chains are representative of CT (Confidential Transactions), Mimblewimble, RingCT, and ZKSNARKs.
H2r denotes a possible future (memo-less) recursive Halo2 chain.

Privacy leaks

AMT,ADR,LNK |          BTC
            |
            |
            |
ADR,LNK     |                                                       LQD
            |
            |
LNK         | GRIN
            |
I11         |                                                                                        XMR
0           |                      H2r                                                       ZEC(z2z)

               1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
            Chainsize (size of historical 2-input 2-output tx / 100 bytes)

In roughly decreasing order of importance:

AMT  = amounts visible on-chain
ADR  = on-chain addresses
LNK  = input-output linkability in mempools
I11  = each input hiding among 10 decoys
3 Likes
#2

It’s worth noting that ZEC Sapling z2z’s large size is in part due to the fixed memo field per output, which doesn’t have any effect on the chain privacy that zk-SNARKs provide. Without that (still having encCiphertext for in-band note distribution but without the 512-byte memo), ZEC would be down around 17 on your chainsize chart.

(There are also other transaction-size inefficiencies that we plan to address in later upgrades, but I presume other chains have similar inefficiencies, whereas ZEC is AFAIK the only listed coin that has built-in memo fields; subtracting them out provides a more accurate comparision of the underlying tech.)

As for a potential Halo2-based Pollard protocol, it will sit on the same privacy row as Sapling (being derived from it). I don’t know what the proof size will end up being yet, but we can do some rough estimation to guess where it would end up on the chainsize axis.

The base transaction without proofs and without memo field contributions will be around 800 bytes for 2-in 2-out, and there will be probably a few kB of proofs on top of that. Then we can make some more assumptions to guess the chainsize position:

  • Assuming Halo2 without recursion, Pollard would end up further to the right than Sapling (guessing probably >30).
  • Assuming Halo2 with recursion (which is the end goal), and assuming that aggregation is only performed during block mining, you’d end up with a single Halo2 proof per block. (I don’t know what assumptions your graph makes about Grin, but I’ll presume it’s similar.) Without per-transaction proofs, you could likely fit 1000 2-in 2-out Pollard transactions into a block (here I am counting memo field size towards the 2MB block size limit), which would bring the per-transaction proof cost down from a few kB to a few bytes, which on your graph we can basically ignore. So that would place Pollard around 8.

As a side-note, it would be nice to have similar notes about the what assumptions went into the other datapoints (besides 2-in 2-out). I noted unknown Grin assumptions above, and similarly IDK what goes into the Liquid datapoint.

3 Likes
#3

Grin sits at 1, because all that remains of a transaction with spent outputs is the ~100 byte transaction kernel, which is a public key (0-valued Pedersen commitment), and a signature with that key. So it’s not due to amortization, which you would have with a single Halo2 proof for all txs in a block.
I will add a memo-less recursive Halo2 point at 800 bytes then, as the proof gets amoritzed to just a few bytes.

#4

Btw, Mina protocol https://minaprotocol.com/ (formerly known as Coda / O(1) labs) claims to have the entire chain fit in 22KB, but that doesn’t seem to apply to nodes producing blocks and proofs.

If anyone knows what historical tx size is applicable for the latter, then please share…