Benedikt Bünz's UTXO commitments / RSA Accumulators

Development and Technical Discussion
21

One option would be to reintroduce the concept of “archive nodes” - where these may promise to maintain the full UTXO set for this and potentially other purposes.
A lightweight node may then be able to ask for relevant parts of the UTXO set (via a bloom filter or something similar), for example.

Archive nodes would not be required for network security but they would provide a valuable service in terms of making wallet restore possible etc.
They would maintain data that other nodes are normally able to prune during normal day to day network use.

22

I worry that if there were a disincentive to maintain the UTXO set, i.e. one could still participate in the network but use less data and storage by not maintaining the UTXO set, then nodes might not do so. It would be nice if there was some incentive, even if it was a very minor one.

23

Incentives are centralizing in a forced way vs having universities or random players donating their beefed up nodes to the network. I don’t know. We move into realm of mastenodes, which maybe aren’t so bad.

24

https://www.michaelstraka.com/posts/classgroups/

Came across via twitter, write up on class groups of imaginary quadratic order which eliminates the trusted setup requirement of the RSA group in order to construct accumulators.

2 Likes
25

Accumulators in Rust !

1 Like
26

Awesome discussion re accumulators in /dev the other night:

Michalis Kargakis @kargakis 00:04

with TXOs we just need to delete 32 bytes from the file next time we rewrite it

so you still track UTXOs in the MMR but with a tree that is pruned when an output is spent. it’s just that we cannot use that MMR to prove unspentness, does that sound right?
wondering now how this is going to look like with accumulators

goldenMetteyya @goldenMetteyya 00:20
MMR is append only so if you change something as said before the whole tree must be rehashed, if you build a MMR after each block for UTXO’s then you can prove unspentness for that block only next one its invalid

David Burkett @DavidBurkett 00:20
There’s a bitset that tells whether the output is unspent based on the MMR position

goldenMetteyya @goldenMetteyya 00:21
is this bitset updated after each block ?

David Burkett @DavidBurkett 00:21
As far as accumulators go, I spent the last couple weeks working with them, and right now, there’s a roadblock that could make them a non-starter.
@goldenMetteyya Yes

goldenMetteyya @goldenMetteyya 00:22
dynamic accumulators have fast verification but they have issues that each change results in all proofs to need to change
So your UTXO inclusion proof is valid for one block

David Burkett @DavidBurkett 00:22
That’s correct, and I was thinking we could get around that, but due to the way we prune, I don’t think we can without help from “Archive nodes"

goldenMetteyya @goldenMetteyya 00:24
with the latest accumulator research someone still needs to hold ALL the chain data

David Burkett @DavidBurkett 00:24
UTXO inclusion proofs can be updated by the miner really easily/efficiently. But the problem is restoring transactions makes it impossible to provide proofs

goldenMetteyya @goldenMetteyya 00:24
to generate the proos
@DavidBurkett depemds on the accumilator construction
if you are using RSA or Class group based then its not super fast
NlogN

David Burkett @DavidBurkett 00:25
Class group is still super fast, thanks to improvements realized by the Chia VDF competition
Not as fast as RSA, I agree, but still fast enough

goldenMetteyya @goldenMetteyya 00:27
depends on your chains block interval
its relative

Michalis Kargakis @kargakis 00:27

if a malicious actor rewrites enough history then its possible nobody (if we prune obsolete UTXOs) has ever seen those outputs

does this mean that nobody gets to validate a malicious output for a year (assuming we obsolete utxos in a year)?

David Burkett @DavidBurkett 00:27
@goldenMetteyya With 1 minute blocks, it’s still fast enough. Just did some testing this morning.

goldenMetteyya @goldenMetteyya 00:28
Nice:)
but like 15 seconds its not that good

David Burkett @DavidBurkett 00:28
Possibly not

goldenMetteyya @goldenMetteyya 00:28
even then for 1 minute block time
you have a small window
where the miner who generated the block and then proofs get generated

David Burkett @DavidBurkett 00:29
If you’re looking at the cambrian implementation, just note that the code in master is really slow compared to the code in the class group improvement PR

goldenMetteyya @goldenMetteyya 00:29
by the time a wallet sees and tries to use it
@DavidBurkett can you share the link please

David Burkett @DavidBurkett 00:30
cambrian/accumulator#35

goldenMetteyya @goldenMetteyya 00:37

this is a library i have used its based on chia entrant
I extracted into its own crate

this one is only RSA based for now
i have rough code that tested classgroups
i think that the vector commitments are more useful now as they have constant proofs to multiple openings
based on the accumulators

David Burkett @DavidBurkett 00:41
Nice, I’ll check it out

goldenMetteyya @goldenMetteyya 00:42
Recent propsal is Utreexo which is based on hashes, again the issue is proof updates in all of them, the windoe of use is not much
but stateless blockchain idea is cool, but i think MW is the closest that get to one on principles for a light chain

David Burkett @DavidBurkett 00:44
I was just going to ask if you knew anything about Uteexo. I was going to investigate it next. Sounds like it has the same problem though, so you saved me some time

goldenMetteyya @goldenMetteyya 00:46
its based on hashes which is the best assumption out of all them
it has logn proofs
like merkle trees
Its basically a variant, but the accumulators have constant proofs which is wat better
compared to the MMR you can delete items without having to rehash everything

David Burkett @DavidBurkett 00:48
Is the paper out yet? Or anything concrete?

goldenMetteyya @goldenMetteyya 00:49
no paper

David Burkett @DavidBurkett 00:49
O cool. Thanks

goldenMetteyya @goldenMetteyya 01:05
Essential one needs a dynamic set, that can proove inclusion ideally with constant size no matter the set size, and this proof of inclucion should remain valid even though elements are added and removed. There is no construction that gives this to us :confused:
UTXO case has the benefit that additions and deletion are done through autherizaion and there cant be duplicate items

3 Likes
27

Thank you for posting this, I have been missing much of the discussion lately and highlights like this are invaluable to me.

28

David Burkett @DavidBurkett 00:22
That’s correct, and I was thinking we could get around that, but due to the way we prune, I don’t think we can without help from “Archive nodes"

I was wrong about this. We don’t need archive nodes. Restoring a wallet just requires additional processing to add all of the UTXOs, excluding your own, to the initial accumulator value. Given the current size of the UTXO set, and using the cambrian implementation with class groups on a 2017 macbook pro, this takes ~1 minute. A full proposal for accumulators in Grin is in progress.

3 Likes
29

I fail to see how. A transaction would still needs to specify inputs and outputs. But since full nodes would no longer have an MMR in which to lookup inputs, the transaction needs to provide accumulator inclusion proofs of the inputs as well.

1 Like
30

Got time to read the cambrian’s RSA accumulator implementation and that demo. Unfortunately, I don’t think it will bring us an amazing tiny stateless chain, which I had quite expected before.

The full UTXO sets are still needed to be there, for creating the Inclusion Proof of even one single UTXO when spending it; or we have to provide some kind of service as the “Bridge” in that [demo] which need to manage the “user account” and the user’s UTXO sets. But obviously, this kind of “bridge” service doesn’t make sense in Grin (or in Bitcoin).

The “deletion” operation of the accumulator need a Inclusion Proof:

“the inclusion proof was the accumulator value without the element. So the inclusion proof has the accumulator with my element deleted”.

So, to spend an UTXO, the user have to calculate an accumulator with this UTXO deleted from the latest accumulator (on latest chain head). Indeed, this “deletion” operation is a beautiful stateless deletion! but, to get this Inclusion Proof, I don’t see any “stateless” method.

Either the user/wallet must maintain a full chain UTXO sets, or some kind of “bridge” service must maintain. Both are far from the ideal “stateless” chain.

Please correct me if sth’s wrong here.

2 Likes
31

This problem has been referred to in "Utreexo: A dynamic accumulator for bitcoin state" by Tadge Dryja - #4 by lehnberg

The problem is resulted from:
Whenever a new block is mined, the UTXO set change, so ==> accumulator change, so ==> inclusion proof of every UTXO change. So the inclusion proof of every UTXO should be re-calculated whenever a new block is mined.

So user has to maintain full node to get the full UTXO sets, to calculate the accumulator and inclusion proof of his UTXO.

Or the user can request these data from “Bridge”.
But if there are millions of UTXO belonged to users connected to it, the bridge have to re-caculate millions times of inclusion proof, in every block interval.

2 Likes
32

You’re correct. This is unworkable for bitcoin, but is still feasible for Grin if and only if we choose not to support full “light” clients. Since in Grin we can get the UTXO set without having to download and process the whole history, it’s not too difficult to rebuild out inclusion proofs during a wallet restore, for example.

To make it even simpler, we could aggregate all inclusions and all deletions in each block to just 1 inclusion and 1 deletion that we could add to the header, allowing nodes to more easily maintain their UTXO proofs. Once again though, my arch nemesis the 1 minute block makes this a bit more difficult than it could be.

Of course, this still isn’t stateless, but it eliminates the MMRs.

1 Like
33

it’s not too difficult to rebuild out inclusion proofs during a wallet restore

If that’s one time cost it should be acceptable. But the problem is you need progressive “restore” to rebuild inclusion proof each time when you need create a tx to spend an output. That makes it suck.

34

Possibly, but optimizations like the one I mentioned make it suck much less! :smile:

To make it even simpler, we could aggregate all inclusions and all deletions in each block to just 1 inclusion and 1 deletion that we could add to the header,

1 Like
35

How much would a longer block time help? If we get lightning in grin, then slower bigger blocks could be worth considering.

1 Like
36

It would help some, but I’m not sure how much. I’ve always believed 1 minute blocks were too short though, for numerous reasons (Grin headers are large and can’t really be pruned, frequent blocks defeat the purpose of mw since it limits tx graph obfuscation, etc). I could never convince any of the core devs of this, so I doubt it will ever change.

1 Like
37

Have always agreed with you. Especially since 1min blocks doesn’t solve anything like TPS or buying coffee. Everyone already assumes 2nd layer networks on top of grin, so why not lean into that and make block times longer for the aggregation benefits.

1 Like