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,...,641i = 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:=1aib_i := 1 - a_i
        .
      • Require
        aibi=0a_i \cdot b_i = 0
        and
        ai=1bia_i = 1 - b_i
        .
    • Require
      x=i=0641bi2ix = \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_amount1i=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.