WebsiteTwitterTelegramDiscord
Search…
⌃K
Links

Bulletproofs

Bulletproofs-based mixing protocol​​

To prove correct mixing of confidential assets, the Zei library makes use of Bulletproofs. The protocol here follows a modular design. We first present the shuffle gadget and RHS-merge-or-not gadget as well as some helper functions, and then we describe how to construct the mixing protocol.
  • ​
    Shuffle(a_amount→,a_asset_type→,b_amount→,b_asset_type→)\mathsf{Shuffle}(\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}},\overrightarrow{\mathsf{b\_amount}}, \overrightarrow{\mathsf{b\_asset\_type}})
    :
    • This gadget enforces that
      b_amount→,b_asset_type→\overrightarrow{\mathsf{b\_amount}}, \overrightarrow{\mathsf{b\_asset\_type}}
       is a result of shuffling from
      a_amount→,a_asset_type→\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}}
      , where the amount and the asset type are being shuffled together, and each vector has length
      ℓ\ell
      .
    • Obtain two random challenges
      α,β∈F\alpha,\beta\in\mathbb{F}
       from the Bulletproofs R1CS interface. Note that Bulletproofs R1CS interface allows the program to pull random challenges in the middle.
    • Compute a random linear combination for
      (a_amount→,a_asset_type→)(\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}})
      .
      • ​
        left:=∏i=1ℓ(a_amount[i]+α⋅a_asset_type[i]−β)\mathsf{left} := \prod_{i=1}^\ell (\mathsf{a\_amount}[i] + \alpha\cdot \mathsf{a\_asset\_type}[i] - \beta)
        .
      • ​
        right:=∏i=1ℓ(b_amount[i]+α⋅b_asset_type[i]−β)\mathsf{right} := \prod_{i=1}^\ell (\mathsf{b\_amount}[i] + \alpha\cdot \mathsf{b\_asset\_type}[i] - \beta)
        .
    • Enforce
      left=right\mathsf{left} = \mathsf{right}
      .
  • ​
    RHSMergeOrNot(a_amount→,a_asset_type→,b_amount→,b_asset_type→)RHSMergeOrNot\mathsf{RHSMergeOrNot}(\overrightarrow{\mathsf{a\_amount}},\overrightarrow{\mathsf{a\_asset\_type}},\overrightarrow{\mathsf{b\_amount}},\overrightarrow{\mathsf{b\_asset\_type}})RHSMergeOrNot
    :
    • This gadget enforces that
      (b_amount→,b_asset_type→)(\overrightarrow{\mathsf{b\_amount}}, \overrightarrow{\mathsf{b\_asset\_type}})
       is obtained by doing \emph{optional} RHS merging over
      (a_amount→,a_asset_type→)(\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}})
       when the asset types of the two consecutive ones are the same. Each vector has length
      ℓ\ell
      .
    • Copy
      tmp_amount→:=a_amount→\overrightarrow{\mathsf{tmp\_amount}} := \overrightarrow{\mathsf{a\_amount}}
       and
      tmp_asset_type→:=a_asset_type→\overrightarrow{\mathsf{tmp\_asset\_type}} := \overrightarrow{\mathsf{a\_asset\_type}}
      . We will be working over these two temporary vectors.
    • For
      i=0,1,...,ℓ−1i = 0, 1, ..., \ell - 1
      ,
      • If
        tmp_asset_type[i]=tmp_asset_type[i+1]{\mathsf{tmp\_asset\_type}}[i] = {\mathsf{tmp\_asset\_type}}[i + 1]
        , then a merge is \emph{permitted}. Otherwise, a merge is prohibited.
      • If a merge is permitted and
        b_amount[i]=0\mathsf{b\_amount}[i] = 0
        , then the merge happens, we update
        tmp_amount→\overrightarrow{\mathsf{tmp\_amount}}
         and
        tmp_asset_type→\overrightarrow{\mathsf{tmp\_asset\_type}}
        ,
        • ​
          tmp_amount[i+1]:=tmp_amount[i]+tmp_amount[i+1]\mathsf{tmp\_amount}[i + 1] := \mathsf{tmp\_amount}[i] + \mathsf{tmp\_amount}[i + 1]
          ​
        • ​
          tmp_amount[i]:=0\mathsf{tmp\_amount}[i] := 0
          ​
      • Otherwise, the merge does not happen, we do not update
        tmp_amount→\overrightarrow{\mathsf{tmp\_amount}}
         and
        tmp_asset_type→​\overrightarrow{\mathsf{tmp\_asset\_type}}​
        .
    • Require
      tmp_amount→=b_amount→\overrightarrow{\mathsf{tmp\_amount}} = \overrightarrow{\mathsf{b\_amount}}
       and
      tmp_asset_type→=b_asset_type→\overrightarrow{\mathsf{tmp\_asset\_type}} = \overrightarrow{\mathsf{b\_asset\_type}}
      .
  • ​
    Pad(amount→,asset_type→,ℓ):=(amount→′,asset_type→′)\mathsf{Pad}(\overrightarrow{\mathsf{amount}},\overrightarrow{\mathsf{asset\_type}}, \ell) := (\overrightarrow{\mathsf{amount}}', \overrightarrow{\mathsf{asset\_type}}')
    :
    • Require
      ∣amount→∣=∣asset_type→∣≤ℓ\lvert\overrightarrow{\mathsf{amount}}\rvert = \lvert\overrightarrow{\mathsf{asset\_type}}\rvert \leq \ell
      .
    • Append
      00
       to the end of
      amount→\overrightarrow{\mathsf{amount}}
       and
      ⊥\perp
       to the end of
      asset_type→​\overrightarrow{\mathsf{asset\_type}}​
      , until their length reaches
      ℓ\ell
      .
  • ​
    RangeCheck(x)\mathsf{RangeCheck}(x)
    :
    • For
      i=0,1,...,64−1i = 0, 1, ..., 64-1
      :
      • Ask the prover for two bits,
        ai,bi∈{0,1}a_i,b_i\in\{0,1\}
        . An honest prover is expected to let
        aia_i
         be the
        ii
        -th bit of
        xx
         and let
        bi:=1−aib_i := 1 - a_i
        .
      • Require
        ai⋅bi=0a_i \cdot b_i = 0
         and
        ai=1−bia_i = 1 - b_i
        .
    • Require
      x=∑i=064−1bi⋅2ix = \sum_{i=0}^{64-1} b_i\cdot 2^i
      .
The entire Bulletproofs-based mixing protocol is as follows:
  • ​
    Mix(a_amount→,a_asset_type→,b_amount→,b_asset_type→)\mathsf{Mix}(\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}}, \overrightarrow{\mathsf{b\_amount}}, \overrightarrow{\mathsf{b\_asset\_type}})
    :
    • Ask the prover to provide a shuffled version of
      (a_amount→,a_asset_type→)(\overrightarrow{\mathsf{a\_amount}},\overrightarrow{\mathsf{a\_asset\_type}})
       and
      (b_amount→,b_asset_type→)(\overrightarrow{\mathsf{b\_amount}},\overrightarrow{\mathsf{b\_asset\_type}})
      . An honest prover is expected to sort the entries in each vector in a way that the entries for the same asset type are consecutive to each other. There is no particular requirement on the order of this sorting.
    • Let
      (sorted_a_amount→,sorted_a_asset_type→)(\overrightarrow{\mathsf{sorted\_a\_amount}},\overrightarrow{\mathsf{sorted\_a\_asset\_type}})
       and
      (sorted_b_amount→,sorted_b_asset_type→)(\overrightarrow{\mathsf{sorted\_b\_amount}},\overrightarrow{\mathsf{sorted\_b\_asset\_type}})
       be the vectors that the prover provides.
    • Invoke the shuffle gadget:
      • ​
        Shuffle(a_amount→,a_asset_type→,sorted_a_amount→,sorted_a_asset_type→)\mathsf{Shuffle}(\overrightarrow{\mathsf{a\_amount}}, \overrightarrow{\mathsf{a\_asset\_type}}, \overrightarrow{\mathsf{sorted\_a\_amount}}, \overrightarrow{\mathsf{sorted\_a\_asset\_type}})
        ​
      • ​
        Shuffle(b_amount→,b_asset_type→,sorted_b_amount→,sorted_b_asset_type→)\mathsf{Shuffle}(\overrightarrow{\mathsf{b\_amount}}, \overrightarrow{\mathsf{b\_asset\_type}}, \overrightarrow{\mathsf{sorted\_b\_amount}}, \overrightarrow{\mathsf{sorted\_b\_asset\_type}})
        ​
    • Ask the prover to provide a merged version of
      (sorted_a_amount→,sorted_a_asset_type→)(\overrightarrow{\mathsf{sorted\_a\_amount}},\allowbreak \overrightarrow{\mathsf{sorted\_a\_asset\_type}})
       and
      (sorted_b_amount→,sorted_b_asset_type→)(\overrightarrow{\mathsf{sorted\_b\_amount}}, \allowbreak \overrightarrow{\mathsf{sorted\_b\_asset\_type}})
      . An honest prover is expected to perform RHS merging whenever possible.
    • Let
      (merged_a_amount→,merged_a_asset_type→)(\overrightarrow{\mathsf{merged\_a\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_a\_asset\_type}})
       and
      (merged_b_amount→,merged_b_asset_type→)(\overrightarrow{\mathsf{merged\_b\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_b\_asset\_type}})
       be the vectors that the prover provides.
    • Invoke the RHS merging-or-not gadget:
      • ​
        RHSMergeOrNot(sorted_a_amount→,sorted_a_asset_type→,merged_a_amount→,merged_a_asset_type→)\mathsf{RHSMergeOrNot}(\overrightarrow{\mathsf{sorted\_a\_amount}},\allowbreak \overrightarrow{\mathsf{sorted\_a\_asset\_type}},\allowbreak \overrightarrow{\mathsf{merged\_a\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_a\_asset\_type}})
        ​
      • ​
        RHSMergeOrNot(sorted_b_amount→,sorted_b_asset_type→,merged_b_amount→,merged_b_asset_type→)\mathsf{RHSMergeOrNot}(\overrightarrow{\mathsf{sorted\_b\_amount}},\allowbreak \overrightarrow{\mathsf{sorted\_b\_asset\_type}},\allowbreak \overrightarrow{\mathsf{merged\_b\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_b\_asset\_type}})
        ​
  • Require
    ∣a_amount→∣=∣a_asset_type→∣\lvert \overrightarrow{\mathsf{a\_amount}}\rvert = \lvert \overrightarrow{\mathsf{a\_asset\_type}}\rvert
     and
    ∣b_amount→∣=∣b_asset_type→∣\lvert\overrightarrow{\mathsf{b\_amount}}\rvert = \lvert\overrightarrow{\mathsf{b\_asset\_type}}\rvert
    .
  • Let
    ℓ:=max⁡(∣a_amount→∣,∣b_amount→∣)\ell := \max(\lvert \overrightarrow{\mathsf{a\_amount}}\rvert, \lvert\overrightarrow{\mathsf{b\_amount}}\rvert)
    .
  • Compute the padded vectors by invoking the pad gadget:
    • ​
      (padded_a_amount→,padded_a_asset_type→):=Pad(merged_a_amount→,merged_a_asset_type→,ℓ)(\overrightarrow{\mathsf{padded\_a\_amount}},\allowbreak\overrightarrow{\mathsf{padded\_a\_asset\_type}}):=\mathsf{Pad}(\overrightarrow{\mathsf{merged\_a\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_a\_asset\_type}}, \ell)
      ​
    • ​
      (padded_b_amount→,padded_b_asset_type→):=Pad(merged_b_amount→,merged_b_asset_type→,ℓ)(\overrightarrow{\mathsf{padded\_b\_amount}},\allowbreak\overrightarrow{\mathsf{padded\_b\_asset\_type}}):=\mathsf{Pad}(\overrightarrow{\mathsf{merged\_b\_amount}},\allowbreak \overrightarrow{\mathsf{merged\_b\_asset\_type}}, \ell)
      ​
  • Invoke the shuffle gadget that the padded vectors are equivalent:
    • ​
      Shuffle(padded_a_amount→,padded_a_asset_type→,padded_b_amount→,padded_b_asset_type→)\mathsf{Shuffle}(\overrightarrow{\mathsf{padded\_a\_amount}}, \overrightarrow{\mathsf{padded\_a\_asset\_type}}, \overrightarrow{\mathsf{padded\_b\_amount}}, \overrightarrow{\mathsf{padded\_b\_asset\_type}})
      ​
  • For
    i=0,1,...,∣b_amount→∣−1i=0, 1, ..., \lvert\overrightarrow{\mathsf{b\_amount}}\rvert - 1
    :
    • Invoke the range-check gadget:
      RangeCheck(b_amount[i])\mathsf{RangeCheck}(\mathsf{b\_amount}[i])
      .

Bulletproofs-based range check​​

To prove that a pair of Pedersen commitments are committing a valid amount in confidential payments, the Zei library makes use of Bulletproofs.
This is a proof of knowledge, since a Pedersen commitment could be committing any number. What is being shown in this proof is that a prover knows a binding that can interpret a Pedersen commitment with a specific valid number that the prover knows. Assuming that the discrete log problem is hard and the CRS is secure, it is sufficient for confidential payments.
We omit a detailed description, as it simply invokes the proving and verifying algorithms for range checks in the Bulletproofs library that the Zei library depends on.
Key Concepts - Previous
Cryptography
Next
Cryptography Primitives
Last modified 4mo ago