Instead of using a Merkle Tree for accumulating the bottom buffer other algorithms can be used that would have a constant witness size
Constant size witnesses is definitely something that would be awesome. There are schemes with constant-sized witnesses, e.g. RSA accumulators (see my first ethresear.ch post, and see below). There are downsides to RSA accumulators:
- They have a backdoor (namely, the RSA modulus
N) - They make strong-ish cryptographic assumptions
- They use crypto that is not post-quantum secure
Vitalik’s opinion (and mine) is that, any of the above three criteria makes an accumulator scheme “fancy”, unsuitable for the protocol layer of Ethereum. I’ve spent a lot of time studying accumulator literature, and unfortunately all non-Merkle accumulators I could find (RSA-based, pairing-based, Euclidian ring-based) are fancy.
Nonetheless developers can make use of these accumulators at the application layer and so still benefit from their power. This is especially relevant in custom execution models (see point 3 here). Below are the two constant-sized witness schemes for applications that I’m most excited about.
RSA accumulators
The most important thing that needs to be dealt with is picking the RSA modulus, and I only know of three approaches that may be suitable for decentralised applications:
- Do a multi-party computation with many players (e.g. 100), hoping that at least two properly destroy their prime.
- Build a super large random number from smaller random numbers, filter out small prime factors, and make a statistical analysis on the strength of the resulting RSA modulus.
- Pick RSA-2048 from the RSA challenge as your modulus. A $200,000 bounty was posted 27 years ago for the factorisation of this number. Zcoin makes use of this modulus, which probably increases the bounty to a few tens of millions of dollars.
Unfortunately 1) and 2) are unpractical because the bit-size of the modulus would be too large. This leaves us with RSA-2048. 
The size of the witness would be on the order of the bit-size of the modulus, i.e. 64 bytes.
SNARK-compressed Merkle paths
This is preliminary research with Jacob Eberhard. I’ll share some initial results because they are very promising. The basic idea is that you can take a Merkle path (or even better, many Merkle paths with batching) and compress all the hashes into a single SNARK. Below is the setup of our test, and the numbers that came out:
Setup:
- Prover is given 64 hashes (SHA256 compression function) to subsume into a single SNARK
- Prover has 2GB of RAM, 2 cores
Results:
- The SNARK has size 127 bytes (using Groth’s three point SNARK)
- Prover time is 5 seconds
From a verification perspective, Groth’s three point SNARK requires only 1 pairing check, compared to the 3 pairing check currently used e.g. in Zcash. Additionally, my understanding is that the SNARK library in Ethereum clients can be replaced by one which is about 10 times faster. I think verifying a SNARK currently costs 1.8M gas, so with the above 30x savings this may go down to 60K gas for verifying a SNARK.
But then again, we can use custom execution models where the cost of “execution” is just the cost of real-time data availability, namely 68 gas per non-zero byte of transaction data. So with a custom execution model, you only have to pay ~127*68 = 8,636 gas to “verify” a SNARK.