Generic On-Chain Ergo Swaps

Fri, Jan 1, 2021

Happy New Year!

Ergo makes it very easy to create on-chain swap orders, which can be atomically settled on-chain without any third party taking custody.

There are many types of orders in theory, all of which could be supported with various options, but let’s start with the simplest and most common: a straightforward “swap” order, where a user wishes to swap ERG and receive some tokens in return.

Here is a proposed template for swap orders:

Parameters:

rate and divisor of type Long: multiplying by rate / divisor converts from nanoERGs to tokens when buying, or vice-versa when selling.
recipient of type GroupElement: the public key of the recipient.

Buy orders only:

token_id of type Coll[Byte]: the token being bought.
fee of type Long: the trading fee in nanoERGs.

Swapping two tokens directly:

other_token_id of type Coll[Byte]: the other token.

In the case of a sell order, it is assumed the nanoERGs are the fee, and tokens(0) is being sold.

In the case of swapping two tokens directly, it is assumed the nanoERGs sent to the contract are the fee.

The following contract denotes buying a token:

{
  val user_pk = proveDlog(recipient);
  val deadline = SELF.creationInfo._1 + 30;

  val erg_amount = SELF.value - fee;
  val token_amount = erg_amount * rate / divisor;

  val valid_height = HEIGHT < deadline;

  sigmaProp(OUTPUTS.exists({ (box: Box) =>
    allOf(Coll(
      if (valid_height) {
        val t = box.tokens(0);
        t._1 == token_id &&
        t._2 >= token_amount
      } else {
        // refund
        box.value >= erg_amount
      },
      box.R4[Coll[Byte]].get == SELF.id,
      box.propositionBytes == user_pk.propBytes
    ))
  }))
}

The following contract denotes selling a token:

{
  val user_pk = proveDlog(recipient);
  val deadline = SELF.creationInfo._1 + 30;

  val self_tokens = SELF.tokens;
  val token_amount = self_tokens(0)._2;
  val erg_amount = token_amount * rate / divisor;

  val valid_height = HEIGHT < deadline;

  sigmaProp(OUTPUTS.exists({ (box: Box) =>
    allOf(Coll(
      if (valid_height) {
        box.value >= erg_amount
      } else {
        // refund
        box.tokens == self_tokens
      },
      box.R4[Coll[Byte]].get == SELF.id,
      box.propositionBytes == user_pk.propBytes
    ))
  }))
}

The following contract denotes swapping two tokens:

{
  val user_pk = proveDlog(recipient);
  val deadline = SELF.creationInfo._1 + 30;

  val self_tokens = SELF.tokens;
  val token_amount = self_tokens(0)._2;
  val other_token_amount = token_amount * rate / divisor;

  val valid_height = HEIGHT < deadline;

  sigmaProp(OUTPUTS.exists({ (box: Box) =>
    allOf(Coll(
      if (valid_height) {
        val t = box.tokens(0);
        t._1 == other_token_id &&
        t._2 >= other_token_amount
      } else {
        // refund
        box.tokens == self_tokens
      },
      box.R4[Coll[Byte]].get == SELF.id,
      box.propositionBytes == user_pk.propBytes
    ))
  }))
}

Notes:

As long as the conditions are met, anyone can spend a box protected by either of the above contracts. This allows maximum composability with any Ergo-based trading protocols, e.g. AMMs and other types of DEXes.
A collection of boxes protected by these contracts form a primitive orderbook.
Partial filling of these orders is not supported; these orders are intended to be filled immediately assuming the user has picked an appropriate price. In practice, the user will choose a price based on the last spot price plus some slippage value.
An order must be filled within 30 blocks of its creation (~1 hour), otherwise the funds will be returned to the user.

More complex orders are certainly possible, such as those that allow partial filling, but the above should provide a foundation for these types of on-chain swaps.

Another ErgoMix Vulnerability

Wed, Sep 23, 2020

Since reporting the first ErgoMix vulnerability, after some further digging, I found another vulnerability!

ErgoMix Recap

The following is the fixed half-mix 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 &&
    c1 != c2
  ) && {
    proveDHTuple(g, gX, c1, c2) ||
    proveDHTuple(g, gX, c2, c1)
  }) || (proveDlog(gX))
}

The full-mix script is:

{
  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)
}

Given any half-mix box, a user of ErgoMix can choose a secret y and compute c1=g^xy, c2=g^y. This allows them to create two indistinguishable full-mix boxes (simply swap c1 and c2):

The original half-mix box creator can spend in the case proveDHTuple(g, c1=g^y, gX, c2=g^xy).
The user can spend in the other case, with proveDlog(c2=g^y).

Poisoned Half-Mix Attack

Notice that the value c1=g^xy utilises g^x, which is chosen by the half-mix box creator. Is it possible for an attacker to pick a “poisonous” value of g^x?

Look again at the full-mix box script. The proveDHTuple(g, c1, gX, c2) condition can be satisfied if we know x such that g^x=gX and c1^x=c2.

We already know we can spend in the case proveDHTuple(g, c1=g^y, gX, c2=g^xy). The other case is proveDHTuple(g, c1=g^xy, gX, c2=g^y), which would require:

(g^xy)^x = g^y
x^2y = y
x^2 = 1
x = +1 or x = -1

Note that in the case x=1, the attack wouldn’t work because of the c1 != c2 condition in the half-mix script. However, the x=-1 case would allow an attacker to create a poisoned half-mix box with g^x = g^-1. Anyone spending such a half-mix box would risk losing all of their funds as the attacker could immediately spend both of the resulting full-mix boxes.

Similar to the previous vulnerability, the attacker does risk their funds by creating poisoned half-mix boxes, since anyone else with knowledge of the vulnerability could spend their funds using x=-1, as well as the resulting full-mix boxes.

The recommended fix is that clients ignore any poisoned half-mix boxes. This is simpler than modifying the on-chain scripts, which would add complexity and increase verification costs. For completeness and defence-in-depth, the case g^x=1 should also be checked and ignored.

Disclosure

The vulnerability was reported to core developer Alex Chepurnoy on 23rd September 2020. Thanks for the quick response and bug bounty.

Collateral-based Pool for Ergo

Wed, May 6, 2020

After multiple iterations on the design, the following is a final version of the collateral scheme for an upcoming Ergo mining pool, for public review.

Perpetual Token

This is a singleton token, which is intended to last “forever”, with an additional restriction that prevents it from being spent more than once per block.

{
  val createdPreviousBlock = {(b: Box) => b.creationInfo._1 < HEIGHT}
  val createdCurrentBlock = {(b: Box) => b.creationInfo._1 == HEIGHT}

  val isPerpetualWithHeight = {(b: Box) =>
    b.propositionBytes == SELF.propositionBytes &&
    b.tokens == SELF.tokens &&
    createdCurrentBlock(b)
  }

  sigmaProp(OUTPUTS.exists(isPerpetualWithHeight) &&
    createdPreviousBlock(SELF))
}

Without this technique, I was concerned that users might accidentally create more than one unspent collateral box for the same miner public key, which would then allow a pool to claim more than one reward in the same block.

Collateral

This is the main pool collateral script, which allows a pool to take a reward from the collateral box when the miner finds a block.

{
  val minersReward = fixedRate - foundersInitialReward
  val minersFixedRatePeriod = fixedRatePeriod + 2 * epochLength
  val epoch = 1 + ((HEIGHT - fixedRatePeriod) / epochLength)
  val coinsToIssue = if (HEIGHT < minersFixedRatePeriod) {
    minersReward
  } else {
    fixedRate - oneEpochReduction * epoch
  }
  val totalSelf = INPUTS.fold(0L, {(a: Long, b:Box) =>
    if (b.propositionBytes == SELF.propositionBytes) {
      a + b.value
    } else {
      a
    }
  })
  val remainder = totalSelf - coinsToIssue

  val remainderToSelf = {(b: Box) =>
    (remainder <= 0) || (
      b.propositionBytes == SELF.propositionBytes &&
      b.value == remainder
    )
  }

  val perpetualToken = {(b: Box) =>
    b.tokens(0)._1 == perpetualTokenId
  }

  val aliceFoundBlock = sigmaProp(
    CONTEXT.preHeader.minerPk == alice &&
    perpetualToken(INPUTS(0)) &&
    remainderToSelf(OUTPUTS(0))
  )

  val aliceWithdraw = proveDlog(alice)

  aliceFoundBlock || aliceWithdraw
}

Pool Reward Transaction

Let’s call the spending transaction involving one or more collateral boxes as inputs the pool reward transaction. The following properties should hold for this transaction in the case of aliceFoundBlock:

The block was mined by Alice.
The first input contains the special perpetual token.
After the pool has taken its reward from the total value of the input collateral boxes, if the remainder is non-zero it is sent in full to a new collateral box (protected by the same script).

The following properties hold for the special perpetual token (and for the pool reward transaction, since it is forced to spend this token):

There is only one indivisible token (a “singleton” token), hence there is a maximum of one unspent token box at any time. This property is guaranteed when we issue the token with amount == 1.
When the token box is spent, it must have box.creationHeight < HEIGHT and newBox.creationHeight == HEIGHT. This guarantees that only one perpetual token box can be created per block, since newBox can only be spent in a future block.

Since the pool reward transaction is forced to spend this token, then by extension, there can only be one pool reward transaction per block.

Note that there is currently no restriction on where the pool might send its reward, or indeed which pool might spend this reward transaction.

Final notes:

This transaction will have zero mining fees, since it will be mined by the pool anyway.
The token box must contain the minimum value required. If miners modify the minimum value for a box by voting, then the pool must contribute a small amount of ERG to the new token box to achieve the correct minimum value.

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.