Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Sapling] specify Pedersen hashes for a collision-resistant hash function inside the SNARK #2234

Closed
zookozcash opened this Issue Apr 2, 2017 · 71 comments

Comments

@zookozcash
Copy link

commented Apr 2, 2017

from #2230

Ian Miers noticed that a pedersen hash is an exceptionally good application for this fast ECC. Pedersen hashes have been mentioned in papers spanning decades, but have been largely ignored due to inefficiency. However, in our case they are perfect. Inside the circuit they are very competitive with MiMC (a hash function submitted to Asiacrypt last year) except that a pedersen hash has collision resistance that reduces to discrete log -- far more believable than their construction.

In particular, we select a vector g of n group elements of unknown exponent, and given a vector x of n scalar bits, we compute:

g1x1 g2x2 ... gnxn

It is trivial to see that finding a collision requires defeating discrete log in the group. Further, in our construction we can return the y coordinate of the result, which is a single field scalar. (Recall that in Edwards curves, the x coordinate encodes the sign.) Because the group order is an odd prime, collision resistance still reduces to discrete log.

@zookozcash zookozcash changed the title Pedersen commitments for a collision-resistant hash function inside the SNARK evaluate Pedersen commitments for a collision-resistant hash function inside the SNARK Apr 2, 2017

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 2, 2017

@ebfull wrote at #2230 (comment): Here's is an excerpt from an email I sent Matt/Ian a couple months ago.

Currently relying on per-bit point addition allows each addition to be 5 constraints, except the first (which is just 2) and the last (which is 3, because we end up discarding the x coordinate).

It doesn't immediately seem intuitive that a window table lookup is efficient inside the circuit, both because they scale poorly to large windows and because the general point addition becomes 7 constraints (and 4 constraints for the last addition).

However, for a window size of 4, there is a sweet spot. For input bits w, x, y, z, we precompute the following constraints:

yz = y * z
xy = x * y
xz = x * z
xyz = xy * z

Now, a window lookup can be performed for constants a, b, c, ..., o, p, by evaluating the following single gigantic R1CS constraint, which is a polynomial designed to vanish at the constants we aren't selecting:

w * (a(xyz) + a(xy) + a(xz) + a(x) + a(yz) + a(y) + a(z) - a + b(xyz) + b(xz) + b(yz) - b(z) + c(xyz) + c(xy) + c(yz) - c(y) + d(xyz) - d(yz) + e(xyz) + e(xy) + e(xz) - e(x) + f(xyz) - f(xz) + g(xyz) - g(xy) - h(xyz) -i(xyz) - i(xy) - i(xz) - i(x) - i(yz) - i(y) - i(z) + i - j(xyz) - j(xz) - j(yz) + j(z) - k(xyz) - k(xy) - k(yz) + k(y) - l(xyz) + l(yz) - m(xyz) - m(xy) - m(xz) + m(x) - n(xyz) + n(xz) - o(xyz) + o(xy) + p(xyz)) = r + a(xyz) + a(xy) + a(xz) + a(x) + a(yz) + a(y) + a(z) - a + b(xyz) + b(xz) + b(yz) - b(z) + c(xyz) + c(xy) + c(yz) - c(y) + d(xyz) - d(yz) + e(xyz) + e(xy) + e(xz) - e(x) + f(xyz) - f(xz) + g(xyz) - g(xy) - h(xyz)

(Note that there are errors in this polynomial, but the idea is valid.)

This means we can lookup the x, y coordinate pair from a window 4 table with just 6 constraints. After this window size, the cost of lookups explodes.

In our CRH, we have to do more than just base point multiplication. We need to unpack some input field elements -- for random field elements, this costs 255 boolean constraints, 1 packing constraint, and 254 constraints for performing a partial boolean subtraction to ensure the bit representation is actually in the field. This means just processing the inputs costs 1020 constraints.

By employing the windowed exponentiation above, the constraint complexity of the final output is:

1020 + 6(510/4) + (510/4 - 1) * 7 + 4 = 2674.5 constraints. (The fraction here is just because 4 does not divide 510, so the actual constraint complexity is 2675 as there are merely less terms in the final window table lookup constraints.)

This is quite a bit better than the (1020 + 5*508 + 3 + 2 = 3565) constraints before.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 2, 2017

In our CRH, we have to do more than just base point multiplication. We need to unpack some input field elements -- for random field elements, this costs 255 boolean constraints, 1 packing constraint, and 254 constraints for performing a partial boolean subtraction to ensure the bit representation is actually in the field. This means just processing the inputs costs 1020 constraints.

I believe we can reduce this. The modulus p is just under 255 bits. Let y be the y-coordinate of a CRH output, with binary representation y = ∑[2i.yi for i from 0 up to 254]. We can express the condition ∑[2i.yi for i from 0 up to 254] < p as a boolean circuit and then apply a general-purpose boolean logic minimizer such as SAT-ESPRESSO to this circuit. (The problem of finding an optimal solution is NP-complete, but we only need a good solution for a single instance.)

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 6, 2017

We need to have a way to choose the generators (points on an elliptic curve E over Fp) so that their discrete logarithms are not known. I propose the following method:

  • Let hi = FromLE(BLAKE2b(ToLE(i))). ToLE(i) is a little-endian representation of the nonnegative integer i with no trailing zero bytes (in particular ToLE(0) is the empty byte sequence), and FromLE(s) is the nonnonnegative integer represented in little-endian form by s.
  • Let xi = floor(hi / 2) mod p and let ỹi = hi mod 2.
  • Let Pi be the result of decompressing xi and ỹi from "LSB compressed form", i.e. the unique point (xi, yi) such that ỹi = yi mod 2, if this yields a point satisfying the curve equation for E; or ⊥ otherwise. [Edit: we should change this to SORT-compressed form since that's the encoding we have settled on for compressed points.]
  • Let G be the (almost) infinite sequence of points obtained by filtering out instances of ⊥ from P.

Note that since 2511 >> p, the bias from reducing floor(hi / 2) modulo p is negligible.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 6, 2017

Note that there do exist deterministic methods of generating curve points (that would not require filtering out points failing to satisfy the curve equation), such as https://eprint.iacr.org/2009/340 . However they are more complicated and involve more arbitrary choices that might raise "something up my sleeve" suspicions.

@tromer

This comment has been minimized.

Copy link
Contributor

commented Apr 7, 2017

(Partially repeating #705 (comment)):

While Pedersen (or other algebraic hashes) are attractive for the Merkle tree, we should be careful about the security implications of using them elsewhere, and in particular in the PRFs in the note.

For context, let's set terminology for some attacks:
Stealing an existing note, so that the intended owner can no longer spend it.
Destroying an existing note, so the intended owner can no longer spend it.
Forgery of an arbitrary note.
Duplication of an existing note, so that the attacker gets a copy of the ZEC (or user-issed token...) but the intended owner can still spend the original note.

Now, stealing or destroying requires the attacker to post a transaction containing the "correct" nullifier, that would be used when the intended owner tries to spend the note. To learn that nullifier, the attacker needs both rho (which is protected by the hiding property of the note commitment in conjunction with Curve25519 hiding the note plaintext) and a_sk (which is protected by PRF^addr).

So, as long as PRF^addr is really pseudorandom, stealing and destroying attacks remain infeasible.

Now, recall that (completely) breaking the zkSNARK would enable forgery and duplication.

Hence:

Replacing SHA-256 with Pedersen in the Merkle tree and in the note commitment -- this can be done at no loss of security (assuming that discrete logs in Pedersen group are not easier than for the zkSNARK).

But replacing SHA-256 with Pedersen in the PRF does reduce security: it makes some security properties depend on hardness of discrete log, whereas previously they depended just on bit-twiddling hashes.

Of course, in practice forgery or duplication attacks are so bad that the question may be moot.

@daira daira changed the title evaluate Pedersen commitments for a collision-resistant hash function inside the SNARK evaluate Pedersen hashes for a collision-resistant hash function inside the SNARK Apr 8, 2017

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 8, 2017

[...] 254 constraints for performing a partial boolean subtraction to ensure the bit representation is actually in the field

I'm not sure why the bit representation of the whole input needs to be in the field. The representation of each exponent xi needs to be in the index field Fr of the internal curve, but it will be due to the unpacking constraints. No extra constraints are needed to ensure this. So I make it 2421 constraints overall.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 8, 2017

Oh, but the problem is to ensure that the splitting into the xi is unique, given that we can only do arithmetic mod p.

@daira

This comment has been minimized.

Copy link
Contributor

commented Jul 17, 2017

Note that the proposed Pedersen hash is collision-resistant, but is not a PRF — it has visible structure that a PRF wouldn't have.

Therefore, we either need to relax the requirements on the functions used in the circuit that are currently specified as collision-resistant PRFs, or use an algebraic PRF that would still be SNARK-efficient, such as one of those described by Boneh, Montgomery and Raghunathan. Note that the 1/w inversion in their main construction is very SNARK-efficient, since it can be verified using multiplication and nondeterministic advice.

The asymmetric payment construction described in #2277 removes some, but I think not all, of the PRFs. Obviously it's desirable to remove as many as we can first, since that both improves performance and relaxes the performance constraints on any remaining PRFs (or greatly simplifies the circuit if there are none remaining).

@daira

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2017

Looking at #2277 (comment) and applying the simplification in the first sentence of the immediately following comment, we have:

Let r = PRFrandprf_key(ρ), where ρ is verified to be unique to this input note. The nullifier is [r] [sk] G) and the prover has to be given prf_key and [sk] G. For the variant with diversified keys, the address is (d, pkenc,d) where pkenc,d = [vkenc] GH(d). (I've renamed skenc to vkenc to make it clearer that it is a viewing key.)

We derive sk, prf_key, and vkenc from a single skspend, using a PRF that does not need to be checked in the circuit.

[Edit: I got this wrong — we need to check in the circuit that the (d, pkenc,d) committed by the input note commitment is the correct public key. We want to do this without giving the prover sk; the prover should only have [sk] G, in order to have least-authority delegated proving. So vkenc should be derived from [sk] G rather than being derived directly from skspend. Note that G is fixed and sk is derived from skspend outside the circuit.]

The note encryption is done with GH(d) as the base and pkenc,d as the public key. The note_plaintext is (d, pkenc,d, v, ρ, r, meta). The note commitment cm = Commitr(note_plaintext). A spend proves knowledge of (d, pkenc,d, v, ρ, r, meta, prf_key, [sk] G) and a Merkle tree path from the input note cm to anchor, such that r = PRFrandprf_key(ρ) and nf = [r] [sk] G). It can also optionally prove that the note encryption is correct, if the prover is also given the ephemeral secret esk. The spend reveals the proof, anchor, nf, and a Schnorr signature proving knowledge of r.sk such that nf = [r.sk] G.

Now, what happened to the PRFs that are used in the Sprout circuit when we replace it with the above construction?

[To be continued.]

[Edit: rename the diversifier i to d, and use additive notation for the inner curve.]

[Edit: use [z] P notation for scalar multiplication.]

@str4d str4d added this to the 1.0.14 milestone Nov 29, 2017

@daira

This comment has been minimized.

Copy link
Contributor

commented Nov 30, 2017

[I thought of most of this before @ebfull's and @zookozcash's entreaties to stop optimising, I promise :-) I'm just writing it up so that it doesn't get lost. I do however think that we should use it for Sapling.]

For reference, the affine addition formulae given in section 4.3.2 of Montgomery curves and the Montgomery ladder are:

    x3 = B.λ2 - A - x1 - x2
    y3 = (x1 - x3).λ2 - y1
    where λ = (3.x12 + 2.A.x1 + 1)/2.B.y1, if x1 = x2
                  = (y2 - y1)/(x2 - x1), otherwise

Theorem: Let Q be a point of odd-prime order s on a Montgomery curve EA,B / Fr. Let k1..2 be integers in {1 .. (s-1)/2}. Let Pi = [ki] Q = (xi, yi) for i ∈ {1..2}, with k1 ≠ k2. Then the non-unified addition constraints

    (x2 - x1) × (λ) = (y2 - y1)
    (B.λ) × (λ) = (A + x1 + x2 + x3)
    (x1 - x3) × (λ) = (y3 + y1)

implement the affine Montgomery addition (x3, y3) := P1 + P2 in all cases.

Proof:
The given constraints are equivalent to the Montgomery addition formulae under the side condition x1 ≠ x2. (Note that neither Pi can be the zero point.) Assume for a contradiction that x1 = x2. For any P1 = [k1] Q, there can be only one other point −P1 with the same x-coordinate. (This follows from the fact that the curve equation determines ±y as a function of x.) But −P1 = [−1] [k1] Q = [s - k1] Q. Since k ↦ [k] Q is injective on k ∈ {0..s-1}, either k2 = k1 (contradiction), or k2 = s - k1 (contradiction since k1..2 are in {1 .. (s-1)/2}). ∎

The conditions of the theorem give us a "distinct-x criterion" that can be used to argue that it is safe to do a non-unified addition. It is straightfoward to see that all of the additions in:

  • the usual Montgomery ladder algorithm
  • fixed-window left-to-right scalar multiplication (with either fixed or variable base)

satisfy the distinct-x criterion provided that the range of the scalar is limited appropriately. In particular this is true for the Pedersen hash when using the segmented approach from #2234 (comment) . The additions of the partial results from each segment however need to use unified addition. The simplest approach is to convert each partial result to twisted Edwards form and use the complete formulae; this also ensures that the final hash result can take just the Edwards x-coordinate without risk of introducing collisions.

For the Pedersen hashes and for the fixed-base scalar multiplication (with separate precomputed windows for each position), we don't need doubling. For the variable-base scalar multiplication we do. Affine Montgomery doubling can be done in 4 constraints:

    (x) × (x) = (xx)
    (2.B.y) × (λ) = (3.xx + 2.A.x + 1)
    (B.λ) × (λ) = (A + 2.x + xout)
    (x - xout) × (λ) = (yout + y)

with the side-condition y ≠ 0. However we already established that for a Montgomery curve with A2 - 4 nonsquare (like the Montgomery form of Jubjub), the only point with y = 0 is (0, 0) which has order 2, and therefore is not in the odd-prime-order subgroup.

The conversion from Montgomery form (x, y) to twisted Edwards form (u, v) is done as follows:

    (y) × (u) = (x)
    (x + 1) × (v) = (x - 1)

This takes 2 constraints which was taken into account in the cost of the Pedersen hash above.
It has the same side-condition y ≠ 0 which similarly does not occur for points in the subgroup.

Note that we might be concerned that v could be unconstrained because x + 1 = 0. However this cannot occur if the twisted Edwards form of the curve is complete, as it is for Jubjub: If x + 1 = 0, then subtituting x = −1 into the Montgomery curve equation gives B.y2 = x3 + A.x2 + x = A - 2. So in that case y2 = (A - 2)/B which is equal to the twisted Edwards parameter d (see section 4.3.5 of Montgomery curves and the Montgomery ladder). But for complete twisted Edwards curves, d is nonsquare, so this equation has no solutions for y, hence x + 1 ≠ 0.

@ebfull

This comment has been minimized.

Copy link
Contributor

commented Dec 5, 2017

In your doubling formula:

(B.λ) × (λ) = (A + x1 + x2 + x3)

x2 should be x1. (Or x, for consistency.)

@daira

This comment has been minimized.

Copy link
Contributor

commented Dec 7, 2017

Thanks @ebfull. Fixed in-place.

@daira

This comment has been minimized.

Copy link
Contributor

commented Mar 19, 2018

This is fully specified; see sections 5.4.1.7, 5.4.7.2, and A.3.3.9 of the Sapling spec.

@daira daira closed this Mar 19, 2018

Sapling Protocol Upgrade automation moved this from In Progress to Complete Mar 19, 2018

@nicola

This comment has been minimized.

Copy link

commented Mar 29, 2018

@daira where can I find the sapling spec?
What is the PRF that you ended up using?

@daira

This comment has been minimized.

Copy link
Contributor

commented Mar 30, 2018

@nicola https://github.com/zcash/zips/blob/master/protocol/sapling.pdf

The PRF isn't this ticket, it was ticket #2630. See section 5.4.2 of the Sapling spec for that.

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 23, 2018

@ebfull wanted me to explicitly write out the lookup constraints for 3-bit windows, i.e. 2 bits + negation. (I thought I had before, but I hadn't.)

Let the window bits in little-endian order be [s0, s1, s2], as in section 5.4.1.7 of the spec. s2 is the negation bit, i.e. we want to implement a lookup of (xs, ys) = [(1 - 2.s2) . (1 + s0 + 2.s1)] P. We define the intermediate value before negation as (xs, yr) = [1 + s0 + 2.s1] P.

Let (x1, y1) = [1] P,  (x2, y2) = [2] P, etc.

Assume s0, s1 and s2 have been boolean-constrained. We start by ANDing s0 and s1:

    (s0) × (s1) = (s&)

xs and yr are now linear in s0, s1 and s&:

    let xs = x1 + (x2-x1).s0 + (x3-x1).s1 + (x4+x1-x2-x3).s&
    let yr = y1 + (y2-y1).s0 + (y3-y1).s1 + (y4+y1-y2-y3).s&

As a general rule it's simplest to perform substitutions into as few constraints as possible, so we substitute yr only into the negation constraint:

    (yr) × (1 - 2.s2) = (ys)
=>
    (y1 + (y2-y1).s0 + (y3-y1).s1 + (y4+y1-y2-y3).s&) × (1 - 2.s2) = (ys)

Now we have to substitute xs into the Montgomery addition. Assume that we're adding the result of the lookup on the right-hand-side of the addition. To avoid variable name clashes, let's express the addition as (xc, yc) = (xa, ya) + (xb, yb):

    (xb - xa) × (λ) = (yb - ya)
    (B.λ) × (λ) = (A + xa + xb + xc)
    (xa - xc) × (λ) = (yc + ya)

The substitution is not quite as nice as it could be, because xb occurs twice, but it's not too bad. Collecting this together, we get 5 constraints for a lookup-and-add operation, (xc, yc) = (xa, ya) + [(1 - 2.s2) . (1 + s0 + 2.s1)] P:

    (s0) × (s1) = (s&)
    (y1 + (y2-y1).s0 + (y3-y1).s1 + (y4+y1-y2-y3).s&) × (1 - 2.s2) = (yb)
    (x1 + (x2-x1).s0 + (x3-x1).s1 + (x4+x1-x2-x3).s& - xa) × (λ) = (yb - ya)
    (B.λ) × (λ) = (A + xa + x1 + (x2-x1).s0 + (x3-x1).s1 + (x4+x1-x2-x3).s& + xc)
    (xa - xc) × (λ) = (yc + ya)

The first lookup of each segment costs 3 constraints:

    (s0) × (s1) = (s&)
    (x1 + (x2-x1).s0 + (x3-x1).s1 + (x4+x1-x2-x3).s&) × (1) = (xa)
    (y1 + (y2-y1).s0 + (y3-y1).s1 + (y4+y1-y2-y3).s&) × (1 - 2.s2) = (ya)

(We could have saved one constraint here by avoiding the "× (1)" but it's not worth it.)

So the cost of a segment with n chunks/windows, including 2 constraints to convert to Edwards at the end, is 3 + 5*(n-1) + 2 = 5*n constraints. The total cost of a Merkle tree layer, including boolean-constraining the input and conditionally swapping halves, is 255*2 + 2 + 2*5*63 + 5*44 + 6 + 5 = 1373 constraints.

[Edit: fixed the negation for Montgomery coordinates.]
[Edit: correction from "xr and ys are now linear" to "xs and yr are now linear" as pointed out by Tore Frederiksen et al.]

@daira daira reopened this Apr 23, 2018

@daira

This comment has been minimized.

Copy link
Contributor

commented Apr 23, 2018

@sean did the conditional negation differently, as (2.yr) × (s2) = (yr - ys) before substitution (which ends up being more complicated because you have to substitute twice). It's not a big deal; either way works and uses the same number of constraints.

@arielgabizon

This comment has been minimized.

Copy link
Contributor

commented Jul 1, 2018

Comments on above:

  • Just to see I'm following - should it be (x0, y0) = [1] P above instead of (x1,y1)?
    i.e. if s=0 then s1=s2 =0, so [1 + s0 + 2.s1] P =[1] P.

  • You're using that the inverse of (x,y) is (-x,y) for Montgomery. Would say that explicitly. Also I would be more explicit on the point where you finish discussing the lookup and move to addition.

@daira

This comment has been minimized.

Copy link
Contributor

commented Jul 3, 2018

@arielgabizon wrote:

  • Just to see I'm following - should it be (x0, y0) = [1] P above instead of (x1,y1)?
    i.e. if s=0 then s1=s2 =0, so [1 + s0 + 2.s1] P =[1] P.

No, (xi, yi) = [i] P. But this is just a numbering convention. In any case that convention is used consistently above.

Also I would be more explicit on the point where you finish discussing the lookup and move to addition.

I think I was already pretty explicit about that.

@daira

This comment has been minimized.

Copy link
Contributor

commented Jul 3, 2018

All of the discussion of range constraints has been moved to #3366.

@arielgabizon

This comment has been minimized.

Copy link
Contributor

commented Jul 4, 2018

@daira wrote

I think I was already pretty explicit about that.

The point at which you say "Now we have to substitute xs into..." it's not that clear to the reader you've finished lookup and are getting into addition.

@daira

This comment has been minimized.

Copy link
Contributor

commented Sep 29, 2018

The only reason this ticket was still open was that Appendix A.3.3.9 of the protocol spec doesn't go into sufficient detail about the lookup used in the Pedersen hashes (explained in #2234 (comment) above). That is now tracked in zcash/zips#179 .

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.