# Outcome Collection

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`

, `B`

,
and `C`

respectively.

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.

Conversely, `(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. `(A|X)`

) cannot
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 `uint`

.

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.

NoteIn 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.

`web3.utils.soliditySha3({ // See section "A Categorical Example" for derivation of this condition ID t: 'bytes32', v: '0x67eb23e8932765c1d7a094838c928476df8c50d1d3898f278ef1fb2a62afab63' }, { t: 'uint', v: 0b011 // Binary Number literals supported in newer versions of JavaScript })`

This results in an initial x-coordinate of

`0x52ff54f0f5616e34a2d4f56fb68ab4cc636bf0d92111de74d1ec99040a8da118`

, or`37540785828268254412066351790903087640191294994197155621611396915481249947928`

.An

`odd`

flag 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

`21888242871839275222246405745257275088696311157297823662689037894645226208583`

.The first time, this results in an updated x-coordinate

`x= 15652542956428979189819946045645812551494983836899331958922359020836023739346`

.The x-coordinate is checked to see if it is the x-coordinate of points on the elliptic curve. Specifically,

`x**3 + 3`

gets 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.When

`x= 15652542956428979189819946045645812551494983836899331958922359020836023739346`

,`x**3 + 3 == 7181824697751204416624405172148440000524665091599802536460745194285959874882`

is not a quadratic residue in the base field, so go back to step 2.When

`x= 15652542956428979189819946045645812551494983836899331958922359020836023739347`

,`x**3 + 3== 19234863727839675005817902755221636205208068129817953505352549927470359854418`

is also not a quadratic residue in the base field, so go back to step 2.When

`x= 15652542956428979189819946045645812551494983836899331958922359020836023739348`

,`x**3 + 3 == 15761946137305644622699047885883332275379818402942977914333319312444771227121`

is still not a quadratic residue in the base field, so go back to step 2.When

`x= 15652542956428979189819946045645812551494983836899331958922359020836023739349`

,`x**3 + 3 == 18651314797988388489514246309390803299736227068272699426092091243854420201580`

is 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,`odd`

is unset, so we're done, and the collection ID for`(A|B)`

is`15652542956428979189819946045645812551494983836899331958922359020836023739349`

, or`0x229b067e142fce0aea84afb935095c6ecbea8647b8a013e795cc0ced3210a3d5`

.

We may also combine collection IDs for outcome collections for different conditions by performing elliptic curve point addition on them.

NoteLet's denote the slots for range ends 0 and 1000 from our scalar condition example as`LO`

and`HI`

. We can find the collection ID for`(LO)`

to be`0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2`

using 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:`(15652542956428979189819946045645812551494983836899331958922359020836023739349, 11459896044816691076313215195950563425899182565928550352639564868174527712586)`

Note the even y-coordinate is chosen here.

`(LO)`

, which has a collection ID of`0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2`

, gets decompressed to the point:`(9970120961273109372766525305441055537695652051815636823675568206550524069826, 5871835597783351455285190273403665696556137392019654883787357811704360229175)`

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:

`(21460418698095194776649446887647175906168566678584695492252634897075584178441, 4596536621806896659272941037410436605631447622293229168614769592376282983323)`

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

`(A|B)&(LO)`

is`0x6f722aa250221af2eba9868fc9d7d43994794177dd6fa7766e3e72ba3c111909`

.

**Warning**

**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 `CTHelpers`

library
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.

**Parameters:**

**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.