The main concept for understanding the mechanics of this system is that of a position. We will build to this concept from conditions and outcome slots, and then demonstrate the use of this concept.
However, before we can talk about positions, we first have to talk about outcome collections, which may be defined like so:
A nonempty proper subset of a condition’s outcome slots which represents the sum total of all the contained slots’payout values.
Categorical Example Featuring Alice, Bob, and Carol
We'll denote the outcome slots for Alice, Bob, and Carol as
A valid outcome collection may be
(A|B). In this example, this outcome
collection represents the eventuality in which either Alice or Bob is
chosen. Note that for a categorical condition, the payout vector which
the oracle reports will eventually contain a one in exactly one of the
three slots, so the sum of the values in Alice's and Bob's slots is one
precisely when either Alice or Bob is chosen, and zero otherwise.
(C) by itself is also a valid outcome collection, and this simply
represents the case where Carol is chosen.
() is an invalid outcome collection, as it is empty. Empty outcome
collections do not make sense, as they would essentially represent no
eventuality and have no value no matter what happens.
(A|B|C) is also an invalid outcome collection, as it is
not a proper subset. Outcome collections consisting of all the outcome
slots for a condition also do not make sense, as they would simply
represent any eventuality, and should be equivalent to whatever was used
to collateralize these outcome collections.
Finally, outcome slots from different conditions (e.g.
be composed in a single outcome collection.
Index Set Representation and Identifier Derivation
An outcome collection may be represented by a condition and an index
set. This is a 256 bit array which denotes which outcome slots are
present in an outcome collection. For example, the value
3 == 0b011
corresponds to the outcome collection
(A|B), whereas the value
4 == 0b100 corresponds to
(C). Note that the indices start at the
lowest bit in a
An outcome collection may be identified with a 32 byte value called a collection identifier. Calculating the collection ID for an outcome collection involves hashing its condition ID and index set into a point on the alt_bn128 elliptic curve.
Note In order to calculate the collection ID for
(A|B), the following steps must be performed:
An initial value for the point x-coordinate is set by hashing the condition ID and the index set of the outcome collection, and interpreting the resulting hash as a big-endian integer.
This results in an initial x-coordinate of
oddflag is set according to whether the highest bit of the hash result is set. In this case, because the highest bit of the hashing result is not set,
odd = false.
The x-coordinate gets incremented by one modulo the order of the alt_bn128 base field, which is
The first time, this results in an updated x-coordinate
The x-coordinate is checked to see if it is the x-coordinate of points on the elliptic curve. Specifically,
x**3 + 3gets computed in the base field, and if the result is a quadratic residue, the x-coordinate belongs to a pair of points on the elliptic curve. If the result is a non-residue however, return to step 2.
x**3 + 3 == 7181824697751204416624405172148440000524665091599802536460745194285959874882is not a quadratic residue in the base field, so go back to step 2.
x**3 + 3== 19234863727839675005817902755221636205208068129817953505352549927470359854418is also not a quadratic residue in the base field, so go back to step 2.
x**3 + 3 == 15761946137305644622699047885883332275379818402942977914333319312444771227121is still not a quadratic residue in the base field, so go back to step 2.
x**3 + 3 == 18651314797988388489514246309390803299736227068272699426092091243854420201580is a quadratic residue in the base field, so we have found a pair of points on the curve, and we may continue.
Note that the base field occupies 254 bits of space, meaning the x-coordinate we found also occupies 254 bits of space, and has two free bits in an EVM word (256 bits). Leave the highest bit unset, and set the next highest bit if
odd == true. In our example,
oddis unset, so we're done, and the collection ID for
We may also combine collection IDs for outcome collections for different conditions by performing elliptic curve point addition on them.
Note Let's denote the slots for range ends 0 and 1000 from our scalar condition example as
HI. We can find the collection ID for
0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2using the procedure illustrated in the previous note. The combined collection ID for
(A|B)&(LO)can be calculated in the following manner:
Decompress the constituent collection IDs into elliptic curve point coordinates. Take the low 254 bits as the x-coordinate, and pick the y-coordinate which is even or odd depending on the value of the second highest bit.
(A|B), which has a collection ID of
0x229b067e142fce0aea84afb935095c6ecbea8647b8a013e795cc0ced3210a3d5, gets decompressed to the point:
Note the even y-coordinate is chosen here.
(LO), which has a collection ID of
0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2, gets decompressed to the point:
The odd y-coordinate indication bit was chopped off the compressed form before its use as the decompressed form's x-coordinate, and the odd y-coordinate is chosen here.
Perform point addition on the alt_bn128 curve with these points. The sum of these points is the point:
Compress the result by taking the x-coordinate, and setting the second highest bit, which should be just outside the x-coordinate, depending on whether the y-coordinate was odd. The combined collection ID for
Both bitwise XOR and truncated addition is not used in this scenario because these operations are vulnerable to collisions via a generalized birthday attack.
Similar to with conditions, the contract and the
also provide helper functions for calculating outcome collection IDs:
function getCollectionId (bytes32 parentCollectionId, bytes32 conditionId, uint indexSet) external view returns (bytes32)
Constructs an outcome collection ID from a parent collection and an outcome collection.
- parentCollectionId – Collection ID of the parent outcome collection, or bytes32(0) if there’s no parent.
- conditionId – Condition ID of the outcome collection to combine with the parent outcome collection.
- indexSet – Index set of the outcome collection to combine with the parent outcome collection.