ErgoMix Vulnerability

Thu, Apr 30, 2020

Introduction to ErgoMix

ErgoMix is a non-interactive protocol for enhancing privacy on the Ergo blockchain, using a cryptographic primitive called a proof of Diffie-Hellman tuple to repeatedly mix pairs of input boxes from different participants and generate indistinguishable output boxes, their order being swapped at random.

The protocol consists of two types of box:

• Half-Mix: has a single register containing a group element g^x, where x is a one-time secret.
• Full-Mix: has three registers: a group element g^x, a group element g^y, and a group element g^xy, where y is a one-time secret.

Note that to an outside observer, it’s not possible to distinguish between g^y and g^xy due to the DDH assumption.

The half-mix box can only be spent as the first input to a transaction that creates two indistinguishable full-mix boxes, and in order to spend it, a proof of Diffie Hellman tuple (g, g^y, g^x, (g^x)^y) must be provided. See the following script:

{
  val g = groupGenerator
  val gX = SELF.R4[GroupElement].get

  val c1 = OUTPUTS(0).R4[GroupElement].get
  val c2 = OUTPUTS(0).R5[GroupElement].get
  val u1 = OUTPUTS(0).R6[GroupElement].get
  val u2 = OUTPUTS(1).R6[GroupElement].get

  (sigmaProp(
    OUTPUTS(0).value == SELF.value &&
    OUTPUTS(1).value == SELF.value &&
    u1 == gX && u2 == gX &&
    blake2b256(OUTPUTS(0).propositionBytes) == fullMixScriptHash &&
    blake2b256(OUTPUTS(1).propositionBytes) == fullMixScriptHash &&
    OUTPUTS(1).R4[GroupElement].get == c2 &&
    OUTPUTS(1).R5[GroupElement].get == c1 &&
    SELF.id == INPUTS(0).id
  ) && {
    proveDHTuple(g, gX, c1, c2) ||
    proveDHTuple(g, gX, c2, c1)
  }) || (proveDlog(gX))
}

The resulting two full-mix boxes (one with c1/c2 swapped) are protected by the following script:

{
  val g = groupGenerator
  val c1 = SELF.R4[GroupElement].get
  val c2 = SELF.R5[GroupElement].get
  val gX = SELF.R6[GroupElement].get
  proveDlog(c2) ||
  proveDHTuple(g, c1, gX, c2)
}

Case 1:

c1 = g^y
c2 = (g^x)^y = g^xy = (g^y)^x

This can be spent with knowledge of x:

proveDHTuple(g, c1=g^y, gX=g^x, c2=(g^y)^x)

Note that this cannot be spent using the proveDlog(c2) branch, since c2=g^xy.

Case 2:

c1 = (g^x)^y
c2 = g^y

This can be spent with knowledge of y:

proveDlog(c2=g^y)

Note that this cannot be spent using the proveDHTuple(g, c1, gX, c2) branch, since we do not know z such that (g^xy)^z=g^y.

Due to the use of the sigma protocol it is not possible to determine which sigma condition was used when spending either full-mix box.

Points at Infinity

By design, anyone can spend a half-mix box that they don’t own, as long as they comply with the contract parameters, i.e. by creating two full-mix boxes with the appropriate register values. One of these resulting full-mix boxes should then only be spendable by the owner of the half-mix box.

Now, if an attacker sets y=0, this results in c1=g^y=O and c2=g^xy=O, where O is the point at infinity. Ergo does not prevent points-at-infinity from being used in scripts.

Since both full-mix boxes now have c1=c2=O, they can both be spent by the attacker using the proveDlog(c2) branch in the script above, allowing the attacker to double their money.

Note that anyone can spend these full-mix boxes using proveDlog(O), so the attacker risks losing their own funds when carrying out this attack.

Resolution

This vulnerability can be avoided by adding a check for points at infinity to the half-mix script:

!c1.isInfinity // this implies !c2.isInfinity

Disclosure

The vulnerability was reported to core developer Alex Chepurnoy on 30th April 2020. Thanks for the quick response and bug bounty.