Minimizing Bitcoin transactions using Utreexo (Part 2)
If you have not read the first part, you can find it here: https://medium.com/@RongxinZhang/minimizing-bitcoin-transactions-using-utreexo-part-1-f842eff76c41
RSA Accumulators:
Most of the work in the space was done by Benedikt Bunz, Ben Fisch and Dan Boneh [1][2]. RSA based accumulators are based on the same assumptions as RSA itself. This is based on the hardness of integer factorization. A simple example is shown below [1]
Set up:
Acc ← Gen()
N = p⋅ q where p, q are large primes.
G = generator from group Zₚ^*
We compute the accumulator in the following way C in the following way
C = G^S mod N
The outputs of such accumulators are mostly constant sized
Add:
Acc, Proof ← Add(Acc, Item)
{u}: set of secret values within the accumulator
U = Πᵏᵢuᵢ, where i is all the us
Now, we want to provide proof that a subset {r} of set {u} belongs to the group. We first split the entire set{u} into two sets, {r} for the set to reveal and {s} for the set to reveal, where R=Πᵏᵢrᵢ and S=Πᵏᵢsᵢ. We want to be sure that S⋅ R = U.
Verify:
Result ←Verify(Acc, Item, Proof)
To provide an inclusion proof for {r} in U. The prover needs to provide two parts.
{r} and P = G^S \mod N
The verifier can now take these values and generate C’, such that C’ = P^R mod N where R is the product of {r}.
The verifier then, simply needs to check: C’ = (G^S)^R = G^{(S ⋅ R)} = G^U = C mod N
Delete:
Acc ← Delete(Acc, Item)
The verifier then, simply needs to check: C’ = (G^S)^R = G^(S ⋅ R) = G^U = C mod N
The key to accumulators is the ability to delete. This is exactly what RSA accumulators also provides. This is because UTXOs within bitcoin are constantly changing and some are removed during each transaction. Therefore one must be able to easily remove elements within the accumulator.
The focus is to replace Merkle Trees for Bitcoin’s Proofs within each block. This means that instead of providing a Merkle proof to show that a specific address has a certain amount of Bitcoin, they will use an RSA variant. This directly builds on Li, Li, Xue’s Universal Accumulators who’s key contribution is in creating a proof of “non-inclusion”. However, there are several practical problems in implementing and RSA based accumulator.
- Trusted set up:
A major issue with using RSA accumulators is the need for someone to create the p and q used to initialize the operation. However, who will do this trusted set up and who should have the right to access it. If the key is not created in the correct way, it will allow anyone to create proofs. It is unclear how one can do this properly. ZCash has similar issues with their internal RSA accumulators. They have figured our novel ways of using multi-party computation to solve such issues, but it’s unclear how this can be done in Bitcoin and their security. https://z.cash/technology/paramgen/ - Adoption:
As discussed by Dryja, it requires each node to maintain its own set of UTXO proofs. However, there is a chicken and egg problem. In order for accumulators to work, every node within the network must support this, and every wallet on the network must also support this. However, no one is going to adopt this without everyone else adopting it first. A solution around this is for someone to run an intermediary node within the network which supports both accumulator proofs and normal proofs. These nodes are considered to be bridge nodes. However, a critical issue is that these bridge nodes need to compute the inclusion proofs for every UTXO every time transactions are added to the blockchain, which requires a recompilation of the inclusion proofs for every block.
Based on running RSA times from (https://www.cryptopp.com/benchmarks.html). It takes 0.16 milliseconds to run an RSA operation. Assuming something similar for RSA accumulators, a wild guess would assume that if there are 60 million UTXOs, and around 3000 transactions per block, it would take more than a years to compute on a computer from 2005. Also computers have gotten faster, it will still require substantial computing investments and power for bridge nodes to operate. (60000000⋅3500)(0.00016)/60/60
Bünz, Fisch and Boneh have made progress to create “Batching Techniques for Accumulators…” in 2019 BPase to address these issues which may solve the problem. However, these rely on novel approaches of using “class” group of quadratic number fields, which is at the cutting edge and has not been tested for performance or security.
References:
[1]https://medium.com/@aurelcode/cryptographic-accumulators-da3aa4561d77
