Possible DoS vector using .distinct and GroupElement

[SethDusek]

The following script has cost 677756 but takes around 24 seconds to run, the code is a bit messy since I was trying to avoid repeated calls to .distinct on the same array being optimized by the compiler, so I could probably reduce this to a more minimal example.

The issue seems to be that hashing a GroupElement is very expensive, since it requires normalization (modInv done in constant-time, same operation is performed in GroupElement.getEncoded which has high cost set), which takes around 40-50 microseconds on my system (benchmarked by timing EcPoint.hashCode).

property("distinct - spam attempt") {
    val customExt = Seq(21.toByte -> CollectionConstant[SGroupElement.type](
      Colls.fromArray(Array.fill(65535)(decodeGroupElement("026930cb9972e01534918a6f6d6b8e35bc398f57140d13eb3623ea31fbd069939b"))),
      SGroupElement),
      22.toByte -> CollectionConstant[SGroupElement.type](
      Colls.fromArray(Array.fill(65535)(decodeGroupElement("026930cb9972e01534918a6f6d6b8e35bc398f57140d13eb3623ea31fbd069939b"))),
      SGroupElement), 23.toByte -> CollectionConstant[SGroupElement.type](
        Colls.fromArray(Array.fill(65535)(decodeGroupElement("026930cb9972e01534918a6f6d6b8e35bc398f57140d13eb3623ea31fbd069939b"))),
        SGroupElement), 24.toByte -> CollectionConstant[SGroupElement.type](
        Colls.fromArray(Array.fill(1000)(decodeGroupElement("026930cb9972e01534918a6f6d6b8e35bc398f57140d13eb3623ea31fbd069939b"))),
        SGroupElement))
    def distinctTest() = test("serialize", env, customExt,
      s"""{
            val coll1 = getVar[Coll[GroupElement]](21).get
            val coll2 = getVar[Coll[GroupElement]](22).get
            val coll3 = getVar[Coll[GroupElement]](23).get
            val coll4 = getVar[Coll[GroupElement]](24).get

            coll4.filter({(a: GroupElement) => coll1.distinct.size == coll2.distinct.size}).size != coll3.distinct.size
          }""",
      null,
      true
    )

    if (activatedVersionInTests < V6SoftForkVersion) {
      an[sigma.validation.ValidationException] should be thrownBy distinctTest()
    } else {
      val start = System.nanoTime()
      distinctTest()
      println((System.nanoTime() - start) / 1000000)
    }
  }

[aslesarenko]

@SethDusek, @kushti This is not realistic example, as it ignores the size limits on transaction and boxes.
In real transactions it is not possible to create collections in context variables with so many items.
And boxes can only be 4K bytes size.
The only way to create such collection as intermediate data is to use fold and append.
But I wonder what cost it will have.

[SethDusek]

@SethDusek, @kushti This is not realistic example, as it ignores the size limits on transaction and boxes. In real transactions it is not possible to create collections in context variables with so many items. And boxes can only be 4K bytes size. The only way to create such collection as intermediate data is to use fold and append. But I wonder what cost it will have.

Good point regarding TX limits, I wasn't sure what they were exactly, but I think there might be ways to stuff in more data. For example putting them in registers of another box and using them as data inputs. I've tried to fit within the 4k box/TX limit with this example and tried to force as many distinct calls as possible.

I estimate that the size of ContextExtension here is (33 bytes/GroupElem * 100 GroupElems) + (1bit/bool * 800 booleans) ~= 3400bytes, which leaves some space for the rest of the transaction. This script has cost 21194 (seems unusually low, maybe I did something wrong) but takes 5 seconds to run

  property("distinct - spam attempt") {
    val customExt = Seq(
      21.toByte -> CollectionConstant[SGroupElement.type](
        Colls.fromArray((0 to 100).map(_ => GroupElement(CryptoConstants.dlogGroup.createRandomElement())).toArray),
        SGroupElement),
      22.toByte -> CollectionConstant[SBoolean.type](Colls.fromArray(Array.fill[Boolean](800)(true)), SBoolean),
      )

    def distinctTest() = test("serialize", env, customExt,
      s"""{
            val boolcoll = getVar[Coll[Boolean]](22).get
            val gecoll = getVar[Coll[GroupElement]](21).get
            val bigcoll = boolcoll.fold(gecoll, {(a: Coll[GroupElement], b: Boolean) => a.append(gecoll.distinct).distinct})
            val bigcoll2 = boolcoll.fold(gecoll, {(a: Coll[GroupElement], b: Boolean) => a.append(gecoll.distinct).distinct})
            sigmaProp(bigcoll.filter({(a: GroupElement) => bigcoll.distinct.size != gecoll.distinct.size}).distinct.size != bigcoll.distinct.size && bigcoll.distinct.size == bigcoll2.distinct.size)
          }""",
      null,
      true
    )

    if (activatedVersionInTests < V6SoftForkVersion) {
      an[sigma.validation.ValidationException] should be thrownBy distinctTest()
    } else {
      // we have wrapped CostLimitException here
      val start = System.nanoTime()
      distinctTest()
      println((System.nanoTime() - start) / 1000000)
    }
  }

[SethDusek]

A reduced example. This one has cost 115939 but takes 30 seconds to run (since test() runs both prover and verifier, running script takes 15 seconds). Each extra .distinct only adds a few thousand to cost so this could be repeated even more :

{
            val boolcoll = getVar[Coll[Boolean]](22).get
            val gecoll = getVar[Coll[GroupElement]](21).get
            val bigcoll = boolcoll.fold(gecoll, {(a: Coll[GroupElement], b: Boolean) => a.append(gecoll.distinct.distinct.distinct.distinct.distinct.distinct.distinct.distinct)})
            sigmaProp(bigcoll.size != 0)
  }

[kushti]

There is soft transaction limit only, currently of 96 kb, so peers do not propagate such transactions (and refuse to accept them by default). However, a miner can include bigger transaction (up to block size) in a block still.