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.
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.
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
, or37540785828268254412066351790903087640191294994197155621611396915481249947928
.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)
is15652542956428979189819946045645812551494983836899331958922359020836023739349
, or0x229b067e142fce0aea84afb935095c6ecbea8647b8a013e795cc0ced3210a3d5
.
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
LO
andHI
. We can find the collection ID for(LO)
to be0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2
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 of0x229b067e142fce0aea84afb935095c6ecbea8647b8a013e795cc0ced3210a3d5
, gets decompressed to the point:(15652542956428979189819946045645812551494983836899331958922359020836023739349, 11459896044816691076313215195950563425899182565928550352639564868174527712586)
Note the even y-coordinate is chosen here.
(LO)
, which has a collection ID of0x560ae373ed304932b6f424c8a243842092c117645533390a3c1c95ff481587c2
, 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)
is0x6f722aa250221af2eba9868fc9d7d43994794177dd6fa7766e3e72ba3c111909
.
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.