The bulletproofs protocol allows to prove that the value carried by a Pedersen commitment is contained between 0 and 2^64 - 1 nanogrins.
The problem with 0-value outputs is that an attacker can set up 24/7 bots on the network which are nodes mechanically appending 0-value outputs to each and every transactions that they receive from peers.
Unlike for non-0 outputs, appending 0-value outputs to any transaction is something possible since this operation does not effect the correctness of the balance equation provided that the kernel_offset is accordingly adjusted, which is trivial to do.
This possibility allows for 2 unfortunate consequences:
Reducing by potentially a large degree the capacity for transactions to properly aggregate (in particular with output uniqueness rule).
Allowing to post large amounts of (useless) data on the blockchain for free.
This data individually consists of around 700 bytes, which is around the size of a single bulletproof.
Proposed fix, which is a consensus change:
All bulletproofs should not be generated, and verified, against P, but against P' = P - H, where P = vH + rG. This implies that the values v contained by the Pedersen commitments P = vH + rG must be contained between 1 and 2^64 nanogrin, instead of between 0 and 2^64 -1.
This overhead of data on the blockchain is not only a problem of data overhead, but is also an unnecessary overhead for verification time, since bulletproofs are not trivial to verify. (Around 150 exponentiations and group operations for a single bulletproof)
On the other hand, doing the operation P <- P - H is only one group operation.
The balance equations should still be verified againt P (and not P - H).
Interesting idea, good job. So the existing 0 value utxo becomes invalid? The problem is that if you throw 0 valued utxos out then the kernels become invalid. However you can’t spend them since they’re not valid for new transactions. How would you handle this?
oops, I may have wrongly read your question. For existing 0-outputs it is not an issue. This change would require a hard fork, and all outputs belonging to blocks before the HF takes effect have still their bulletproofs calculated against P. Only the outputs belonging to blocks after the HF takes effect have their bulletproofs calculated against P - H.
Nope, bulletproofs is for values between 0 and 2^64 - 1 as I mentioned in OP.
So if v = 2^64 + 1, then v - 1 = 2^64, and you can’t make a bulletproof for that.
Thanks for starting this debate! It’s something I’ve been wondering for some time and shared on the last meeting. I remember asking this question about 0-value outputs on keybase many months ago and was convinced by others that it doesn’t really solve the spamming issue. The attacker needs to create utxos with 1 nano grin instead of 0 which means that they would need to invest $1 to get 1 billion possible outputs so unfortunately the attack vector does not go away and it doesn’t get much more expensive to perform the attack I suspect a better way to mitigate this spam vector is to either:
make it more expensive to add outputs e.g. higher fees
make sure that the chain growth can handle this worst case
I think that you are forgetting the fees in your accountability with the one billion txs
It is not possible to append non-0-value outputs to exisiting transactions since the balance equation would not hold anymore with any new non-0-value output.
yeah, I forgot to mention that. You’re right, but I think it requires the attacker to add a single input to get past this. So the attacker could use the 1 Grin output as an input and add 1000 outputs. Of course this is ignoring the tx fee which would likely need to be added in this case, but that’s true regardless of what v the attacking outputs hold
Ah yes that is true, although this attack would be more difficult to prepare, it is a possible attack depending on how fees are calculated and verified by the network. And depending the maximum number of outputs a transaction can contain. It may make sense to not allow txs (aggregation included) have more than something like 10, 20, or 30 outputs.
Due to transaction aggregation, I don’t see yet how practical/feasible would it be to make tx fees depend on the number of inputs/outputs in the transaction.
yeah, I look forward to people trying out some new fee mechanisms so we can see if this can be mitigated as well somehow. Otherwise, this will need to be tackled in some other way.
Do you think we can verify fees currently when tx are aggregated ? It would require that the fee formula is linear in the number of outputs and inputs, which i think is not the case currently.
Having a linear fee formula would probably solve the problem since everyone could verify fees based on number of inputs and outputs at any state of aggregation.
Only because we don’t have a dynamic fee market. Once blocks are full, we’ll probably have some serious issues with users appending 0- or low-value outputs to transactions in the stem phase to intentionally lower the fee rate.
It is easily fixable by having two fields fees1 and fees2. fees1 is a linear function of the number of inputs and outputs.
For example fees1 = x.n_outputs - y.n_inputs, where x and y are two positive numbers (consensus paramters) with x > y, and another field, fees2 that the user uses to add more fees to the tx if the blocks are full. totalfees = fees1 + fees2.
That’s true, good point. Maybe there is a way to fix this, but i think it might be hard if we want to have fees linear functions of number of outputs and inputs, thus preventing spamming attacks. Will think about it.
Having two parameters in the fee calculation still allows for some sort of “spamming”.
For example if x = 4 and y = 1, and in the original tx there were 2 outputs and 1 input, then fees1 = 4x2 - 1x1 = 7, but 7 = 4x3 - 1x5, then an attacker could append 1 output and 4 inputs to spam the blockchain.
The good news is that the number of appended outputs is always less than the number of appended inputs, so that an attacker using this strategy would need to create 4 outputs first, and making it less efficient (as spamming attack) to use the tx above as a spamming vector, as opposed to just not spend those 4 outputs and leave them on the blockchain.
Depending on the aggregation, an observer may not be able to know if the kernel with 7 as fees1 had 2 outputs and 1 input, or for example 3 outputs and 5 inputs.
If blocks are filling up, we only want to aggregate txs that are fee compatible. Dandelion stem nodes that add outputs to high-fee transactions are malicious in a way similar to such nodes dropping transactions.
I suspect a better way to mitigate this spam vector is to either: