Choice of range proof params in cli wallet reveals transaction magnitude to very narrow range for Blinded transfers

[Agorise]

The cli_wallet includes functionality for sending blind transfers in which the values of the input and outputs amounts are “blinded.”

In the case where a transaction produces two or more outputs, (e.g. an amount to the intended recipient plus “change” back to the sender), a "range proof" must be supplied to prove that none of the outputs commit to a negative value.

The range proofs are computed by library functions in secp256k1-zkp, which provides a very flexible and capable range proof library, in which a balance can be struck between amount of privacy and compactness of proof.

At present, blind transfer functionality exists only in the cli_wallet. Agorise is working to bring this functionality to the Bitshares-UI as well.

Agorise has discovered that the blind transfer code currently used in the cli_wallet utilizes a range proof parameter resulting in far too little privacy, and far less than the user of the wallet would expect, revealing the committed value to within just a factor of TWO.

In particular, the library function secp256k1_rangeproof_sign() takes a parameter min_bits which specifies the minimum number of bits of the value to keep hidden. The special value of 0 implies that secp256k1_rangeproof_sign() will hide the minimum number of bits necessary to represent the value. Although this minimizes the size of the proof while still blinding every precision bit in the value, this default behavior is nevertheless not desirable in practice because min_bits is a public parameter and therefore immediately reveals the order of magnitude of the committed value. It would be more desirable to either (a) use the maximum blinding of 64 bits, or (b) add a random number of bits to min_bits to vastly increase the uncertainty in the value amount while still saving some amount of space in the range proof. Option (a) provides the most privacy, of course.

The cli_wallet (bitshares-core/libraries/wallet/wallet.cpp) calls secp256k1_rangeproof_sign() via wrapper function range_proof_sign() with the default min_bits parameter of 0 in the following locations:

wallet.cpp lines 4064, 4069, and 4177.

We propose changing the min_bits value from 0 to 64.

To illustrate the vulnerability of the existing code, Agorise has broadcast a test transaction on the main net in block 21759522. This transaction has two blinded outputs, and thus supplies two range proofs. The second byte of the serialized range proof codes min_bits. In the example transaction, we have:

Output 0:

min_bits is 0x10, implying a value range of 2^16 to 2^17 satoshi units, or ~0.65 to 1.31 BTS. Indeed, the actual committed value is 1.0 BTS.

Output 1:

min_bits is 0x15, implying a value range of 2^21 to 2^22 satoshi units, or ~20.9 to 41.9 BTS. Indeed, the actual committed value is 30 BTS.

CORE TEAM TASK LIST

• Evaluate / Prioritize Feature Request
• Refine User Stories / Requirements
• Design / Develop Solution
  • Issue estimation: 6 hours
  • Issue assigned to @christophersanborn
• Perform QA/Testing
• Update Documentation

[abitmore]

Sounds good. Please submit a pull request.

[xeroc]

The root cause of this is the trade-off between transaction size (and thus transaction fee) and privacy.
Ideally, we let the user pick between "cheapness" and "privacy-ness" ..

[pmconrad]

Nice catch.
How big is the difference in size and computational cost? If it is small, go for 64 bits, otherwise add it as an option to the cli_wallet command.

[xeroc]

it's not so much about the operational cost, it is about the size of the data that needs to be stored on chain.
Basically, Range Proofs that are stronger need more bits which result in a bigger transaction and thus higher transaction price (I would expect that tx to have a per_kbyte fee).

[pmconrad]

Yes, but how big is the difference in practice?

[Agorise]

The Borromean ring signature uses one ring per two bits blinded. Each ring is composed of four 32-byte signatures and is paired with one 32-byte commitment. So the size of the ring-sig is 160 bytes per two bits blinded.

Without using the exponent field or revealing a minimum value, all bits after the most-significant bit need to be encoded. (If the user is willing to expose a minimum value, or else to truncate the significant digits of the value amount, then some savings can be achieved by not blinding the lower-order bits. This could be a user option and also automated to some degree.)

Thus, some size references (assuming all precision bits kept blind):

1.0 BTS (100000 base units); 17 bits; ~1.4 kB

1,000 BTS; 27 bits; ~2.2 kB

1,000,000 BTS; 37 bits; ~3.0 kB

1,000,000,000 BTS; 47 bits; ~3.8 kB

A 64-bit value would require a range proof of ~5.0 kB

Given the money supply of BTS, and looking at the above, it should actually be more-than-sufficient to set the min-bits parameter to 48, rather than 64. (Although the same may not be true of an other-than-BTS asset with a greater issued supply and/or more decimal places for the base unit.)

As regards cost:

The fees for blind-to-blind are 5.0 BTS base fee plus 5.0 BTS / output. (Typically there are two outputs: one for the recipient and one “change,” making a typical B2B 15.0 BTS.)

There are no per_kb fees, and thus no incentive the keep the range proof small. However, as one range proof is needed per output, and 5.0 BTS charged per output, one could look at it as a per_kb fee of 1.0 BTS per kB, assuming a 64-bit blinded value, or a higher per_kb fee if less bits are kept blind. The user is certainly paying for the space…

[pmconrad]

Thanks for the explanation!

The max supply for an asset is never greater than GRAPHENE_MAX_SHARE_SUPPLY = 10**15, which fits into 50 bits.

Wrt the cost, the range proof size is only one factor to look at. The other is computational cost. If I understand the above correctly, for a 50-bit range proof we need 25 rings for a total of 100 signatures to verify. This is significant.

IMO we should set the default blinding bits to 50 52, and the committee should keep the associated cost in mind when determining the cost per output, like you suggested.

(Edit: changed bits to 52 because I remember we recently discussed increasing MAX_SHARE_SUPPLY to something that still fits into an IEEE double.)

[ryanRfox]

@christophersanborn intends to work this Issue.

[christophersanborn]

Expanding on the comments of @pmconrad and others above…

Neither setting the default blinding bits to 50 nor 52 will work under current consensus rules. The reason is that the validation step includes a sanity check that the max possible proved value does not exceed GRAPHENE_MAX_SHARE_SUPPLY. 49 bits is the highest supportable value, representing ~56% of max supply. (This could be changed via a consensus change removing the sanity check or by changing the check to < 2*GRAPHENE_MAX_SUPPLY. But under current rules the max bits is 49.)

In keeping with the spirit of the suggestion to set to 52 bits, I propose instead to set the default to 49 bits. However, since total-supply blinding is not allowed anyway, it may be worth considering whether some moderate storage savings by adopting a default minimum mantissa length of 46 bits would be desirable. This would save 256 bytes per proof, and still be sufficient to blind ~7% of max supply into a single Pedersen commitment. (Presumably, a single actor blinding 7% of supply in one go would be a very unlikely event.) We could probably even set the minimum mantissa even lower to 44 or 42 bits, but a consideration against doing so is that there may be possible use cases for UIA assets in which blinding large fractions of the supply is a desired feature, so it seems unwise to preempt this too cavalierly.

For reference, the following table shows the tradeoff between secrecy and proof length. The “value threshold” is the value amount up to which blinded balances will be indistinguishable from other blinded balances via the length of the range proof. Any Pedersen commitments with longer proofs will “hint” at the possibility of a large honeypot.

Mantissa	Proof size (bytes)	Value threshold	% of …MAX_SHARE_SUPPLY
44	3525	176M BTS	2%
46	3685	704M BTS	7%
47	3781	1.4B BTS	14%
48	3845	2.8B BTS	28%
49	3941	5.6B BTS	56%
50	N/A	N/A	N/A

[christophersanborn]

I have a PR for this nearly ready to submit, and am estimating the fix, including test case, at six (6.0) hours.

(Tagging: @ryanRfox)

[oxarbitrage]

closed by #1117