This was a talk from Scaling Bitcoin “Kaizen” a few weeks back.
Title “A Scalable Drop in Replacement for Merkle Trees” by Benedikt Bünz, Benjamin Fisch and Dan Boneh.
The talk touches upon various methods of efficiently handling the UTXO set, specifically RSA accumulators as a superior alternative to Merkle paths. In the talk, using aggregate inclusion, Bünz is talking about reducing 160GB of UTXOs down to 1.5 kilobytes…
Thoughts? Something we should be paying attention to?
We should definitely pay attention. Keep in mind that at this point we only have a video to form an opinion on the described results, so take everything I’m writing with a grain of salt. But this could be very exciting.
First, assuming we can make the technique work, at a minimum this would allow us to replace our whole MMRs for one single piece of data of 1.5KB. This would simplify a lot of code, remove the need for somewhat complex storage and save a lot of space. But this is the boring part.
The less boring part is that we can break linkability between inputs and outputs. On lighter nodes, we could also get completely rid of the UTXO set as they wouldn’t be needed to validate transactions anymore (only for initial sync to validate supply). The idea can be broken down this way:
Already now, we could replace the input commitment references to an output by a Merkle proof that the output exists, which would be built from our MMR. This would be a bad idea however as one can still link the output using the MMR and those proofs would be large, bloating transactions.
RSA accumulators would allow us to do the same thing, but replacing the MMR with the accumulator and using its own much more compact version of a proof. This way an input can be validated without even having the output.
Those accumulators are Zero-Knowledge, so no one knows which output is being spent. You just know that the output has been added in the accumulator sometime and hasn’t been spent yet. This makes inputs and outputs unlinkable.
Having the output itself with its range proof and commitment becomes unnecessary as long as you trust the output addition was valid, which you can either have checked yourself in the past (full node) or trust others to have done (light node). One could also imagine an hybrid mode where you get sync’d almost instantly like a light node (including FlyClient), and then do fuller validation in the background.
I have some worries about some attacks like replay or handling of duplicates and without the paper it’s not worth thinking about it too hard yet. But the good news are that we’d actually have fairly simple needs.
In summary, it’s very grinnesque: simpler and removes a bunch of data while improving privacy. We just need some more time to get the paper and analyze what the solution would look like.
(One) of the really interesting things is the concept of a universal accumulator; the ability to generate proofs of both membership and non membership. This would potentially solve the duplicate problem. You can prove you are spending an unspent output and also prove you are creating new unique outputs, all with zero-knowledge on the current UTXO set.
Benedikt is my favorite cryptographer right now (no offense guys), and testnet5 will by my favorite testnet Going to reach out to him to see if we can get a draft of his math.
If we can (theoretically) represent the outputs being spent by a tx as a single aggregate inclusion proof then we potentially unlink inputs from outputs entirely. The anonymity set of those inputs (outputs being spent) is the entire UTXO set at that point in time. We don’t know which outputs are being spent or even how many outputs are being spent.
My cliffnotes and what I managed to make sense out of the paper, please correct me where I understood things wrong.
General
New type of universal accumulator is proposed, supporting batch adds and deletes, and also proof of membership and non-membership, which also can be aggregated into a single proof of constant size.
No trusted setup (in contrast to previous RSA accumulators) required, and no trapdoor is required.
How the proposed blockchain would work
Each block contains a (constant sized) snapshot of the entire blockchain state, ie the UTXO set.
Everytime there is a new block mined, miners would batch-delete UTXOs being spent as inputs in txs, and batch-add coinbase + new UTXOs being created as outputs in txs.
Verification that this was done correctly can be done by other miners efficiently.
End users would only need to store the proof of inclusion for their own UTXOs.
Nobody in the entire network would be required to store the entire state and history.
My questions
What are the security assumptions, and how do they compare to Grin’s current assumption that the Discrete Logarithm Problem is hard?
The final paragraph of page 30 reads:
Unfortunately, the design requires that user[s] update their witnesses for every addition or deletion to the set.
What is meant by this? That every user need to update the proof of inclusion they hold for each of their UTXOs after every new block is published on the chain? Or only when the user’s own UTXO set is updated?
What would be the role of the bridge nodes referred to in the subsequent sentences. How would they work in practice?
Is there anything in the approach that would break Grin as it works today?
What is missing from what is outlined in order to produce a working prototype?
Note: this is all based on a first read, I may have missed or misunderstood parts or all of it. First a minor correction:
Verification that this was done correctly can be done by other miners efficiently.
Despite what the paper says, I think all full nodes would still need to validate to not compromise the trust model. So not only miners. Also, as far as we’re concerned there are at least 3 distinct benefits to accumulators:
More compact representations than full MMR trees.
Stronger privacy guarantees as inputs and outputs are unlinked.
The stateless chain model described in the paper, where a node can get rid of all UTXOs.
The paper goes straight for 3 as I guess they think it’s the stronger result, but we could have 1 and 2 without requiring 3 in most cases, as it does come with additional usability restrictions (which you mention). Don’t get me wrong, 3 is very interesting (and fun), but I don’t think we should consider that a “full node” still.
Regarding your questions:
It requires the strong RSA assumption, which is over 20 years old now. While it’s a stronger assumption than the standard RSA assumption, there are no proofs or results I’m aware of showing that it’s any easier. It also requires the “adaptive root assumption” which is a little more slippery. It does seem that it’s closely related to the standard RSA assumption but to quote [Wes18]: " It is not known if this problem can easily be reduced to a standard assumption such as the difficulty of factoring N or the RSA problem". But keep in mind that most of these RSA-related are at least 20 years old. And while not being a security assumption, hashing to primes, which is used throughout the paper, doesn’t seem that it would be trivial to implement securely.
As I noted at the beginning of this message, this only applies to a stateless chain model. I’m not convinced that should be the chosen model for full nodes but could be very interesting for lighter nodes.
They would be able to produce the full proof that you’re able to spend a given output. In the stateless chain model, you wouldn’t be able to do that by yourself (although I’m not sure yet a hybrid model wouldn’t be possible).
Depends a lot on what you mean by break and how we’d implement this
From a paper-writing standpoint not much, from what I can tell the authors have done a really good job at covering a lot of ground. But the implementation would be a lot of work. Perhaps some crypto toolkits out there could be reused, but a lot of this is novel.
How would you describe this effort? Replacing the use of Merkle Mountain Range trees with universal accumulators basically? What are the implications? How much more compact would this be, and what other areas of Grin would be affected?
Stronger privacy guarantees as inputs and outputs are unlinked.
Scrolling up in this thread and reading @antioch’s previous post, if I understand correctly, this would mean that we would go from today’s “full blockchain state” where every synced node tracks “a bunch of inputs that spend to a bunch of outputs + transaction kernels”, to every synced node keeping a snapshot of the current state of the UTXO set, which would be a single aggregated inclusion proof. Is that right?
Would we only need an inclusion proof of outputs? Or do we need input inclusion proofs as well? What about transaction kernels?
And what are the key differences between this and the stateless blockchain? That we would still require every node to fully sync and keep track of the entire UTXO set in comparison to every user only tracking their own outputs? Would the size of the blockchain be fairly constant here as well?
Some more questions
I suppose the strong RSA assumption + Adaptive root assumption would still be required in the above approaches for MMR replacement and improving privacy? Or is that not the case? What about hashing to primes that you mention?
Going back to my previous question 2 + 3, this basically mean that you would be reliant on third party “validator nodes” to confirm that you are allowed to spend? It seems to me that this would introduce challenges in terms of censorship resistance and collusion prevention. Is that right?
Depends a lot on what you mean by break and how we’d implement this
How do you see we best could explore the concepts above in prototypes, using Grin as a baseline?
To me, this doesn’t look very compatible with Grin. It would probably be a major overhaul, not something easily swapped in. That said, it’s still really amazing!
But what do I know? That’s why I love this community: it’s the only place where I feel totally and completely outclassed.
The bulk of the effort would be in the RSA accumulator implementation. On the grin side it wouldn’t that much and fairly localized. We could likely get rid of a lot of code, making it a great @antiochp PR candidate. Our MMR roots would just get replaced with hashes of the RSA accumulator(s).
Is that right?
In short, no First we don’t track inputs right now. And in terms of tracking UTXOs and kernels data, it would be about the same. Except in the stateless chain model where we wouldn’t have any UTXO at all, but kernels would still have to be around. Until we figure out how to aggregate them, that is.
The “stronger privacy” comes from the fact that the RSA accumulator and associated proofs are zero-knowledge:
Your proof that says you can spend an output is only valid if the output is actually unspent. Once it’s spent, no valid proofs can be made anymore.
Said proof does not say which output you’re spending. It just says your spend checks against the accumulator. So there’s no linking anymore, and the anonymity set of an input is the whole UTXO set.
As a finer point, one could think it’s a problem because we can’t validate coinbase maturity anymore. I think we’d just keep 2 accumulators for that: a regular output one and a coinbae one.
Regarding your additional questions:
All required.
That’s right. Which is why I think the stateless chain model belongs more in what we’d call light nodes or SPV-like nodes right now. Note however that the proofs are trustless, they can’t be faked. So the only weakness is liveness (which is still an issue for censorship resistance).
First, make a PoC RSA accumulator implementation. That shouldn’t be too expensive, perhaps a few months (but don’t quote me yet on that). Making it solid and fast is what would take more time. Once there’s a semi-functional accumulator, we could add it as an alternative to MMRs, and test it over a new testnet. Once all of this matures and assuming we’re happy with the result and don’t find deal-breakers on the way, add to Floonet and then mainnet.
I might try to do a ELI15 RSA accumulator post, the main idea is actually not that hard. Would that help?
Trying to get my head around exactly how “zero knowledge” an accumulator like this would be.
Say we had a tx that spends a single output and produces two outputs.
And a block containing that single tx along with a single coinbase reward output.
We would have an accumulator prior to the block representing a UTXO set with say 1,000,000 unspent outputs.
We would remove a single output from the accumulator.
Then add three new outputs to the accumulator.
Now if our txs (and blocks) still reveal the outputs created (I’m assuming here that they do, along with their associated rangeproofs etc.), then -
We do not know exactly which output was spent in this tx.
But - we have accumulators representing before and after the spend (i.e. they differ by a single output).
So if we have all the outputs in the UTXO set it would seem to be possible to just brute-force one accumulator and determine which output needs to be removed to produce the correct result.
Presumably this is kind of slow for a UTXO set with 1,000,000 unspent outputs in it, but its not impossible.
And I guess this gets exponentially harder to do if the tx spends multiple outputs. You would need to try all combinations of two outputs for example.
So is this truly “zero knowledge”?
Os it just really expensive to do (rapidly approaching impossible for larger txs)?
Lots of good points, I agree I shouldn’t have characterized it as “zero knowledge”, computationally hard, especially with multiple inputs, seem like a better characterization.
Going to reach out to him to see if we can get a draft of his math.