Links

Delegated Schnorr

The Zei library implements a protocol that is specifically used to open Pedersen commitments over Ristretto inside zk-SNARK over BLS12-381
This is a new protocol that has not been documented and studied before.For now, we call this protocol delegated Schnorr, though we believe that a better name exists. Since this protocol is special-purpose, we feel it helpful to describe the problem that this protocol wants to solve.

Problem: lifting a Pedersen commitment to a Rescue commitment

In Findora, we support two types of privacy payments: confidential payments and anonymous payments.
  • Confidential payment: The private tokens are represented by two Pedersen commitments over the Ristretto group, one for the amount, another one for the asset type. We represent the commitment for the amount as
    P=xG+γHP = xG + \gamma H
    where
    xx
    is the amount and
    γ\gamma
    is the randomizer, and we represent the commitment for the asset type as
    Q=yG+δHQ = yG + \delta H
    where
    yy
    is the asset type and
    δ\delta
    is the randomizer. This confidential payment is therefore able to hide the amount and the asset type, but is unable to hide the sender. The zero-knowledge proof protocol used for confidential payment is Bulletproofs.
  • Anonymous payment: The private tokens are represented by a Rescue commitment, which commits the amount, the asset type, and the owner's public key, as well as a randomizer. This Rescue commitment corresponds to, and is invalidated by, a Rescue nullifier, which commits the amount, the asset type, the owner's public key, as well as the owner's private key. This is able to hide the sender and the receiver, the amount, and the asset type, and we sometimes refer to it as ``triple masking''. The Rescue commitment is defined over BLS12-381 curve, and the zero-knowledge proof protocol used for anonymous payment is a five-wire high-degree TurboPlonk.
The problem that we face in production is that, we want to enable the user to transform a confidential token into an anonymous token, and during this transform, we want to keep the amount and asset type hidden. The challenge is that the Pedersen commitments are defined over the Ristretto group, but the Rescue commitments are defined over the BLS12-381 scalar field. Verifying such a Pedersen commitment in zk-SNARK over BLS12-381 requires field simulation. That is, we need to perform the computation for point multiplication over a different field, through the use of field simulation that we describe before.

Problem: field simulations are costly

Naively, the field simulation would require about
6×1036×1036\times 10^36×103
simulated multiplication steps. Since field simulation is expensive, it would take a significant amount of time for the user, and would not be feasible in production.
In our implementation, we try to reduce the number of field simulations. The approach is that, instead of doing point simulation inside the zk-SNARK, we push the point operations out of zk-SNARK, in which case simulation is not needed, and we permit only a few field simulations inside the zk-SNARK, for the purposes of connecting with the point operations done externally.
This protocol, delegated Schnorr, describes the part that is being pushed out from zk-SNARK from the naive construction. It is an extension of the classical Schnorr protocol, with the additional change that the witness,
a,b,c,da,b,c,da, b, c, da,b,c,d
below, is committed in the protocol under a randomizer
rrrr
, using the Rescue hash function.

Protocol

As follows, we assume that the order of the Ristretto scalar field is
pp
, and the order of the BLS12-381 scalar field is
qq
. We let
GG
and
HH
be two generators suitable for Pedersen commitments over the Ristretto group.
Prove(x,γ,y,δ,P,Q,z)(π,w,β,λ)\mathsf{Prove}(x,\gamma, y, \delta, P, Q, z) \rightarrow (\pi, w, \beta, \lambda)
:
  • Require
    P=xG+γHP = x G+\gamma H
    and
    Q=yG+δHQ = y G+\delta H
    .
  • Sample
    a,b,c,d,rFpa,b,c,d,r\leftarrow\mathbb{F}_p
    .
  • Let
    x_limbs,y_limbs\overrightarrow{\mathsf{x\_limbs}}, \overrightarrow{\mathsf{y\_limbs}}
    ,
    a_limbs\overrightarrow{\mathsf{a\_limbs}}
    ,
    b_limbs\overrightarrow{\mathsf{b\_limbs}}
    be the limb representations of
    x,y,a,bx, y, a, b
    when these values are represented in field simulation. This gives us
    4×6=244\times 6 = 24
    limbs in total, where each limb has at most
    4343
    bits.
  • Compress these limbs into
    55
    elements in
    Fq\mathbb{F}_q​
    :
    • compressed_limbs[0]:=x_limbs[0]+x_limbs[1]243+x_limbs[2]243×2+x_limbs[3]243×3+x_limbs[4]243×4\mathsf{compressed\_limbs}[0] := \mathsf{x\_limbs}[0] + \mathsf{x\_limbs}[1] \cdot 2^{43} + \mathsf{x\_limbs}[2] \cdot 2^{43\times 2} + \mathsf{x\_limbs}[3] \cdot 2^{43\times 3} + \mathsf{x\_limbs}[4] \cdot 2^{43\times 4}
    • compressed_limbs[1]:=x_limbs[5]+y_limbs[0]243+y_limbs[1]243×2+y_limbs[2]243×3+y_limbs[3]243×4\mathsf{compressed\_limbs}[1] := \mathsf{x\_limbs}[5] + \mathsf{y\_limbs}[0] \cdot 2^{43} + \mathsf{y\_limbs}[1] \cdot 2^{43\times 2} + \mathsf{y\_limbs}[2] \cdot 2^{43\times 3} + \mathsf{y\_limbs}[3] \cdot 2^{43\times 4}
    • compressed_limbs[2]:=y_limbs[4]+y_limbs[5]243+a_limbs[0]243×2+a_limbs[1]243×3+a_limbs[2]243×4compressedlimbs[2]:=ylimbs[4]+ylimbs[5]243+alimbs[0]243×2+alimbs[1]243×3+alimbs[2]243×4\mathsf{compressed\_limbs}[2] := \mathsf{y\_limbs}[4] + \mathsf{y\_limbs}[5] \cdot 2^{43} + \mathsf{a\_limbs}[0] \cdot 2^{43\times 2} + \mathsf{a\_limbs}[1] \cdot 2^{43\times 3} + \mathsf{a\_limbs}[2] \cdot 2^{43\times 4}compressed_limbs[2]:=y_limbs[4]+y_limbs[5]⋅243+a_limbs[0]⋅243×2+a_limbs[1]⋅243×3+a_limbs[2]⋅243×4
    • compressed_limbs[3]:=a_limbs[3]+a_limbs[4]243+a_limbs[5]243×2+b_limbs[0]243×3+b_limbs[1]243×4\mathsf{compressed\_limbs}[3] := \mathsf{a\_limbs}[3] + \mathsf{a\_limbs}[4] \cdot 2^{43} + \mathsf{a\_limbs}[5] \cdot 2^{43\times 2} + \mathsf{b\_limbs}[0] \cdot 2^{43\times 3} + \mathsf{b\_limbs}[1] \cdot 2^{43\times 4}
    • compressed_limbs[4]:=b_limbs[2]+b_limbs[3]243+b_limbs[4]243×2+b_limbs[5]243×3\mathsf{compressed\_limbs}[4] := \mathsf{b\_limbs}[2] + \mathsf{b\_limbs}[3] \cdot 2^{43} + \mathsf{b\_limbs}[4] \cdot 2^{43\times 2} + \mathsf{b\_limbs}[5] \cdot 2^{43\times 3}
  • This step differs from classical Schnorr protocol. Use a Rescue hash function
    RescueHash:(Fq)4Fq\mathsf{RescueHash}: (\mathbb{F}_q)^4\rightarrow \mathbb{F}_q
    to compute a commitment, using
    rrrr
    as the randomizer.
    • comm:=RescueHash(RescueHash(compressed_limbs[0],compressed_limbs[1],compressed_limbs[2],compressed_limbs[3]),compressed_limbs[4],r,0)\mathsf{comm} := \mathsf{RescueHash}\left(\mathsf{RescueHash}\left(\begin{array}{l} \mathsf{compressed\_limbs}[0],\\ \mathsf{compressed\_limbs}[1],\\ \mathsf{compressed\_limbs}[2],\\ \mathsf{compressed\_limbs}[3]\end{array}\right), \mathsf{compressed\_limbs}[4], r, 0\right)
  • Compute
    R=aG+cHR = aG + cH
    ,
    S=bG+dHS=bG+ dH
    .
  • Put
    (G,H,P,Q,z,comm,R,S)(G, H, P, Q, z, \mathsf{comm}, R, S)
    into the cryptographic sponge for Fiat-Shamir transform and squeeze out a random challenge
    βFp\beta\in\mathbb{F}_p
    .
  • Compute the responses:
    • s1=βx+as_1 = \beta x + a
    • s2=βy+bs_2 = \beta y + b
    • s3=βγ+cs_3 = \beta\gamma + c
    • s4=βδ+ds_4 = \beta\delta + d
  • Put
    (s1,s2,s3,s4)(s_1, s_2, s_3, s_4)
    into the cryptographic sponge for the Fiat-Shamir transform and squeeze out a random challenge
    λFp\lambda\in\mathbb{F}_p​
    .
  • Let
    π:=(comm,R,S,s1,s2,s3,s4)\pi := (\mathsf{comm}, R, S, s_1, s_2, s_3, s_4)
    .
  • Let
    w:=(x,y,a,b,r)w := (x, y, a, b, r)
    .
  • Output
    (π,w,β,λ)(\pi, w, \beta, \lambda)
    .
Verify(P,Q,z,π):=b{0,1}\mathsf{Verify}(P, Q, z, \pi):= b\in\{0,1\}
:
  • Parse
    π=(comm,R,S,s1,s2,s3,s4)\pi = (\mathsf{comm}, R, S, s_1, s_2, s_3, s_4)
    .
  • Put
    (G,H,P,Q,z,comm,R,S)(G,H, P, Q, z, \mathsf{comm}, R, S)
    into the cryptographic sponge for the Fiat-Shamir transform and squeeze out a random challenge
    βFp\beta\in\mathbb{F}_p
    .
  • Continue by putting
    (s1,s2,s3,s4)(s_1, s_2, s_3, s_4)
    into the cryptographic sponge and squeeze out a random challenge
    λFp\lambda\in\mathbb{F}_p​
    .
  • Check that
    s1G+s3H=βP+Rs_1 G + s_3 H = \beta P + R
    .
  • Check that
    s2G+s4H=βQ+Ss_2 G + s_4 H = \beta Q + S
    .S$
  • Output
    b=1b=1
    if all the checks pass, and
    b=0b=0
    otherwise.