rangeproof: add secp256k1_rangeproof_max_size function to estimate rangeproof size by apoelstra · Pull Request #201 · BlockstreamResearch/secp256k1-zkp

apoelstra · 2022-08-13T00:43:54Z

Provides a method that will give an upper bound on the size of a rangeproof,
given an upper bound on the value to be passed in and an upper bound on the
min_bits parameter.

There is a lot of design freedom here since the actual size of the rangeproof
depends on every parameter passed to rangeproof_sign, including the value to
be proven, often in quite intricate ways. For the sake of simplicity we assume
a nonzero min_value and that exp will be 0 (the default, and size-maximizing,
choice), and provide an exact value for a proof of the given value and min_bits.

jonasnick

Looks good overall. I created a branch on top of the additional tests of #160 and added more rangeproof_max_size tests. Some of those tests fail: it seems like max_size returns the wrong result when min_bits is 0. The branch is here (also includes a small fixup).

real-or-random · 2022-08-22T14:02:17Z

+ * To obtain the size of largest possible proof, set `min_value` to 1 and
+ * `max_value` to UINT64_MAX.


I think this would make the text clearer:

Suggested change

* To obtain the size of largest possible proof, set `min_value` to 1 and

* `max_value` to UINT64_MAX.

* To obtain an upper bound that is valid for all values of `min_value`

* and `max_value`, set `min_value` to 1 and `max_value` to UINT64_MAX.

ah no, this function doesn't even have a min_value arg :P

Oops, it originally did, which would save a few bytes when min_value was 0 ... but then I realized that sometimes rangeproof_sign would override the user's choice of 0 if exp was also set, so I gave up on it.

BTW @jonasnick I wonder if this addresses your "sometimes wrong values when min_value is 0" observation?

@real-or-random I will remove the reference to min_value but I think the existing text "size of the largest possible proof" is correct and what we want to say.

An "upper bound" is too weak, and it seems weird to mention min_value and max_value without mentioning ct_bits or exp or any of the other parameters to rangeproof_sign which could affect the size.

@apoelstra I wrote max_value but I meant min_bits (it's right in the branch)

Ok, how it is implied? I don't see it. Shouldn't the upper limit of the range be independent of value? I mean that's the entire point of a rangeproof?

Sorry, I must be missing something, I guess I'm having a mental block here.... ^^

It's not independent because gmax's code will increase the range if the value would otherwise be outside of it.

Oh I see. That was totally unclear to me from the docs. I think we should clarify this in the docs of rangeproof_sign, ideally by describing max_value as mathematical function of value and min_bits...

Also this is unclear to the reader in the docs.
min_bits: Number of bits of the value to keep private. (0 = auto/minimal, - 64).

which bits? most significant or least significant?

what's "auto/minimal" supposed to do?

But this can be done in another PR.

That was totally unclear to me from the docs.

Lol. We could add something to rangeproof_sign to the effect of "other than value and blind basically every value may be overridden by the signing logic, in ad-hoc ways, if the proof otherwise would be impossible to construct.

ideally by describing max_value as mathematical function of value and min_bits

I mean, this function is a somewhat arbitrary choice of function here. It won't match the behavior of rangeproof_sign because rangeproof_sign also takes its other arguments into account.

which bits? most significant or least significant?

All of them. If value is too large the code just increases min_bits, unless exp is -1 (IIRC) in which case it will create a single-value proof.

In general I think it's a fool's errand to try to document the existing rangeproof signer logic (it may be feasible to just rip it out, respect the user's params, and refuse to sign if they're incompatible, but it's quite hard to communicate what needs to be adjusted, which I think is why gmax made the choices he did). What I need right now is a way for Elements to swag the size of a rangeproof, for fee estimation, given that it knows the user's choice of min_bits and that any output value will be <= MAX_MONEY.

ideally by describing max_value as mathematical function of value and min_bits

I mean, this function is a somewhat arbitrary choice of function here. It won't match the behavior of rangeproof_sign because rangeproof_sign also takes its other arguments into account.

Ah I see. Sorry, I misunderstood. I assumed the max value in rangeproof_sign only depends on these two arguments because you said "it's implied by the union of value and min_bits".

Anyway, this PR here is fine. I think the docs of rangeproof_sign can be improved but if anything, that's a separate issue.

apoelstra · 2022-08-22T19:14:53Z

Pushed to address @real-or-random's comments.

Ideally we could merge #160 so that I could just cherry-pick @jonasnick's commits... as is I'm not sure where the bug is and it's a bit of a PITA for me to find it.

Edit ok, I'm just working directly on his branch while I investigate. This is astonishing -- my function returns 106 for an upper bound while the actual returned plen is 5000.

apoelstra · 2022-08-22T19:33:48Z

@jonasnick actually I think your tests are wrong.

The first CHECK that you've commented out fails because you're doing a check after rangeproof_sign failed (and when it fails it doesn't set plen at all). The second CHECK that you've commented out actually passes for me when I uncomment it.

jonasnick · 2022-08-22T19:56:02Z

facepalm sorry! I fixed my commit in the branch (feel free to cherry-pick) https://github.com/jonasnick/secp256k1-zkp/tree/2022-01--rangeproof-cleanups-jn

apoelstra · 2022-08-22T21:11:34Z

I would love to cherry-pick but the commits don't apply cleanly without also bringing #160 in

jonasnick · 2022-08-23T10:00:04Z

Only the first two commits of #160 which only add tests and seem uncontroversial. But I'm fine with this PR either way.

apoelstra · 2022-08-23T13:11:59Z

Ok, I took your three commits (one of which is a cherry-pick from 160). Will push them when my local tests finish, probably 10-15 minutes.

apoelstra · 2022-08-23T13:26:24Z

Pushed. You can verify with git range-diff that they match your branch (or better, that they match #160). Note that the range-diff will show a bunch of removed memcmp->secp256k1_memcmp_var changes; this is because #160 is out of date. These changes were included in #198.

…ngeproof size Provides a method that will give an upper bound on the size of a rangeproof, given an upper bound on the value to be passed in and an upper bound on the min_bits parameter. There is a lot of design freedom here since the actual size of the rangeproof depends on every parameter passed to rangeproof_sign, including the value to be proven, often in quite intricate ways. For the sake of simplicity we assume a nonzero `min_value` and that `exp` will be 0 (the default, and size-maximizing, choice), and provide an exact value for a proof of the given value and min_bits.

Add two new fixed rangeproof vectors; check that various extracted values are correct; add a test for creating and verifying single-value proofs.

Fixes BlockstreamResearch#42

apoelstra · 2022-08-25T14:45:07Z

Updated only to change the docs as @real-or-random suggested.

real-or-random

tACK 6b6ced9

apoelstra · 2022-08-25T19:48:00Z

@jonasnick ok to merge?

jonasnick

ACK 6b6ced9

jonasnick reviewed Aug 21, 2022

View reviewed changes

real-or-random reviewed Aug 22, 2022

View reviewed changes

apoelstra force-pushed the 2022-08--rangeproof-len branch from 22aab3c to bcfbbc9 Compare August 22, 2022 19:13

real-or-random reviewed Aug 24, 2022

View reviewed changes

Comment thread include/secp256k1_rangeproof.h Outdated

apoelstra and others added 4 commits August 25, 2022 14:26

rangeproof: add a bunch more testing

310e517

Add two new fixed rangeproof vectors; check that various extracted values are correct; add a test for creating and verifying single-value proofs.

rangeproof: add more static test vectors

34876ec

Fixes BlockstreamResearch#42

rangeproof: add more max_size tests

6b6ced9

apoelstra force-pushed the 2022-08--rangeproof-len branch from 6bf08df to 6b6ced9 Compare August 25, 2022 14:44

real-or-random approved these changes Aug 25, 2022

View reviewed changes

jonasnick reviewed Aug 25, 2022

View reviewed changes

jonasnick merged commit f7e9a85 into BlockstreamResearch:master Aug 25, 2022

apoelstra deleted the 2022-08--rangeproof-len branch August 25, 2022 20:25

		* To obtain the size of largest possible proof, set `min_value` to 1 and
		* `max_value` to UINT64_MAX.

Uh oh!

Conversation

apoelstra commented Aug 13, 2022

Uh oh!

jonasnick left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jonasnick Aug 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

apoelstra commented Aug 22, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

apoelstra commented Aug 22, 2022

Uh oh!

jonasnick commented Aug 22, 2022

Uh oh!

apoelstra commented Aug 22, 2022

Uh oh!

jonasnick commented Aug 23, 2022

Uh oh!

apoelstra commented Aug 23, 2022

Uh oh!

apoelstra commented Aug 23, 2022

Uh oh!

Uh oh!

apoelstra commented Aug 25, 2022

Uh oh!

real-or-random left a comment

Choose a reason for hiding this comment

Uh oh!

apoelstra commented Aug 25, 2022

Uh oh!

jonasnick left a comment

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

jonasnick left a comment •

edited

Loading

jonasnick Aug 22, 2022 •

edited

Loading

apoelstra commented Aug 22, 2022 •

edited

Loading