Conditional Tokens

• Prediction markets (betting on outcomes of events like elections or sports games)

• Insurance contracts (payouts triggered by real-world events)

Core Setup & Concepts

1. Question ID (questionId)

• A unique identifier for the event or question that the oracle will answer.

• Example: "Will ETH/USD price be above $2000 on Dec 31, 2025?" → questionId = keccak256("ETH_2000_DEC31_2025").

• It doesn’t contain outcome info itself, just the identity of the “question”.

2. Condition ID (conditionId)

• A hash of three parameters:

keccak256(abi.encodePacked(oracle, questionId, outcomeSlotCount))

• Oracle = the account that reports the outcome.

• Question ID = which question this condition is about.

• Outcome Slot Count = how many possible outcomes exist (e.g., 2 for yes/no, 3 for sports match).

• Multiple oracles could theoretically answer the same question → oracle address ensures uniqueness.

• Same question with different numbers of outcomes → outcomeSlotCount ensures uniqueness.

3. Collection ID (collectionId)

• A subset of outcomes from a condition.

• Built from:
• A parent collection (possibly empty, bytes32(0) if none). (parent condition is used to chain conditions together, refer)
• A condition ID.
• An index set (a bitmask representing chosen outcomes).

• Condition has 3 outcomes = A, B, C.

• Index set 0b110 = {A, B}.

• Index set 0b001 = {C}.

1. tomorrow is sunny or rainy day
1. Outcomes:
1. tomorrow is sunny
2. tomorrow is rainy

2. tomorrow alice or bob wins
1. Outcomes:
1. tomorrow alice wins
2. tomorrow bob wins

• Commutative: A + B = B + A

• Associative: (A + B) + C = A + (B + C)

getCollectionId(getCollectionId(0, C1, A), C2, B)
== getCollectionId(getCollectionId(0, C2, B), C1, A)

4. Position ID (positionId)

• The ERC-1155 token ID that represents a tradable stake in a collection.

• Computed as:

keccak256(abi.encodePacked(collateralToken, collectionId))

• Collateral Token = the asset backing the position (DAI, USDC, ETH, etc.).

• Collection ID = the outcome set this position refers to.

Workflow: Lifecycle of Conditional Tokens

1. Prepare a Condition (prepareCondition)

• Oracle + Question ID + Outcome count → defines a new condition.

• Initializes the payout vector (payoutNumerators).

• Example:
• Oracle = 0xOracleAddress
• Question = “Will ETH > $2000?”
• Outcomes = 2 (Yes / No)
• → conditionId = keccak256(oracle, questionId, 2)

2. Report the Outcome (reportPayouts)

• Only the oracle (sender) can report.

• Provides a payout vector, e.g.:
• Yes = 1, No = 0 → full payout to "Yes" token holders.
• Or Yes = 0.5, No = 0.5 → both get partial payout.

3. Split a Position (splitPosition)

• Converts collateral or a broader outcome position into more granular outcome positions.

• Example:
• Alice deposits 1 DAI collateral.
• Condition has 2 outcomes (Yes, No).
• She calls splitPosition with partition [0b01, 0b10].
• She receives 1 DAI worth of Yes tokens and 1 DAI worth of No tokens.

• Alice already has a "Yes or No" combined token (index set = 0b11).

• She can split it into "Yes only" (0b01) and "No only" (0b10).

4. Merge Positions (mergePositions)

• The reverse of splitting.

• Takes two or more disjoint positions and merges them into a more general one.

• Example:
• Alice holds 1 Yes token and 1 No token.
• She merges them → gets back 1 DAI collateral.

• Works even if she merges partial subsets (like A|C from A, C).

5. Redeem Positions (redeemPositions)

• Once oracle reports, holders of winning outcome tokens redeem collateral.

• Steps:
1. Check payout vector.
2. Burn the user’s position tokens.
3. Transfer collateral back in proportion to payout.

• Example:
• Alice has 10 Yes tokens.
• Oracle reports: Yes = 1, No = 0.
• Alice redeems → gets 10 DAI.
• Anyone holding No tokens → worthless.

Prepare condition

/// --- gnosis/conditional-tokens-contracts/contracts/ConditionalTokens.sol ---

/// Mapping key is an condition ID. Value represents numerators of the payout vector associated with the condition. This array is initialized with a length equal to the outcome slot count. E.g. Condition with 3 outcomes [A, B, C] and two of those correct [0.5, 0.5, 0]. In Ethereum there are no decimal values, so here, 0.5 is represented by fractions like 1/2 == 0.5. That's why we need numerator and denominator values. Payout numerators are also used as a check of initialization. If the numerators array is empty (has length zero), the condition was not created/prepared. See getOutcomeSlotCount.
mapping(bytes32 => uint[]) public payoutNumerators;
/// Denominator is also used for checking if the condition has been resolved. If the denominator is non-zero, then the condition has been resolved.
mapping(bytes32 => uint) public payoutDenominator;
    
/// @dev This function prepares a condition by initializing a payout vector associated with the condition.
/// @param oracle The account assigned to report the result for the prepared condition.
/// @param questionId An identifier for the question to be answered by the oracle.
/// @param outcomeSlotCount The number of outcome slots which should be used for this condition. Must not exceed 256.
function prepareCondition(address oracle, bytes32 questionId, uint outcomeSlotCount) external {
    // Limit of 256 because we use a partition array that is a number of 256 bits.
    require(outcomeSlotCount <= 256, "too many outcome slots");
    require(outcomeSlotCount > 1, "there should be more than one outcome slot");
    bytes32 conditionId = CTHelpers.getConditionId(oracle, questionId, outcomeSlotCount);
    require(payoutNumerators[conditionId].length == 0, "condition already prepared");
    payoutNumerators[conditionId] = new uint[](outcomeSlotCount);
    emit ConditionPreparation(conditionId, oracle, questionId, outcomeSlotCount);
}

/// --- gnosis/conditional-tokens-contracts/contracts/CTHelpers.sol ---
/// @dev Constructs a condition ID from an oracle, a question ID, and the outcome slot count for the question.
/// @param oracle The account assigned to report the result for the prepared condition.
/// @param questionId An identifier for the question to be answered by the oracle.
/// @param outcomeSlotCount The number of outcome slots which should be used for this condition. Must not exceed 256.
function getConditionId(address oracle, bytes32 questionId, uint outcomeSlotCount) internal pure returns (bytes32) {
    return keccak256(abi.encodePacked(oracle, questionId, outcomeSlotCount));
}

Report payout

1. Alice wins

2. Bob wins

3. Draw

/// --- gnosis/conditional-tokens-contracts/contracts/ConditionalTokens.sol ---

/// Mapping key is an condition ID. Value represents numerators of the payout vector associated with the condition. This array is initialized with a length equal to the outcome slot count. E.g. Condition with 3 outcomes [A, B, C] and two of those correct [0.5, 0.5, 0]. In Ethereum there are no decimal values, so here, 0.5 is represented by fractions like 1/2 == 0.5. That's why we need numerator and denominator values. Payout numerators are also used as a check of initialization. If the numerators array is empty (has length zero), the condition was not created/prepared. See getOutcomeSlotCount.
mapping(bytes32 => uint[]) public payoutNumerators;
/// Denominator is also used for checking if the condition has been resolved. If the denominator is non-zero, then the condition has been resolved.
mapping(bytes32 => uint) public payoutDenominator;

/// @dev Called by the oracle for reporting results of conditions. Will set the payout vector for the condition with the ID ``keccak256(abi.encodePacked(oracle, questionId, outcomeSlotCount))``, where oracle is the message sender, questionId is one of the parameters of this function, and outcomeSlotCount is the length of the payouts parameter, which contains the payoutNumerators for each outcome slot of the condition.
/// @param questionId The question ID the oracle is answering for
/// @param payouts The oracle's answer
function reportPayouts(bytes32 questionId, uint[] calldata payouts) external {
    uint outcomeSlotCount = payouts.length;
    require(outcomeSlotCount > 1, "there should be more than one outcome slot");
    // IMPORTANT, the oracle is enforced to be the sender because it's part of the hash.
    bytes32 conditionId = CTHelpers.getConditionId(msg.sender, questionId, outcomeSlotCount);
    require(payoutNumerators[conditionId].length == outcomeSlotCount, "condition not prepared or found");
    require(payoutDenominator[conditionId] == 0, "payout denominator already set");

    uint den = 0;
    for (uint i = 0; i < outcomeSlotCount; i++) {
        uint num = payouts[i];
        den = den.add(num);

        require(payoutNumerators[conditionId][i] == 0, "payout numerator already set");
        payoutNumerators[conditionId][i] = num;
    }
    require(den > 0, "payout is all zeroes");
    payoutDenominator[conditionId] = den;
    emit ConditionResolution(conditionId, msg.sender, questionId, outcomeSlotCount, payoutNumerators[conditionId]);
}

Split position

• collateralToken: ERC20 token backing the positions (like USDC). Positions represent claims on this collateral depending on the outcome.

• parentCollectionId: ID of a parent outcome collection. Can be zero (bytes32(0)), in which case the split is directly from collateral. Otherwise, the split is from an existing position.

• conditionId: The condition (event) the split is based on.

• partition: Array of disjoint sets representing how to split the outcomes.
• E.g., for a condition with outcomes [A, B, C], 0b110 means [A|B] and 0b010 means [B].

• amount: Amount of collateral or position stake to split.

1. Validate Partition Count
1. Partition must contain at least two sets, otherwise it’s trivial (nothing to split).
2. Ensure the condition has been registered.
1. payoutNumerators[conditionId] stores the value of outcomes and payout fractions (used in redeemPositions later).

2. Prepare Full Outcome Set
• fullIndexSet represents all possible outcomes of the condition in bitmask form:
• E.g., 3 outcomes → 0b111
• 4 outcomes → 0b1111
• freeIndexSet keeps track of which outcomes have not yet been assigned to any partition.
• This is used to check there is no conflicts between partitions.

3. Check Partition Validity & Compute Position IDs
For each subset in the partition:
1. Ensure the index set is valid (>0 and < fullIndexSet).
2. Ensure disjointness: no outcome belongs to more than one subset (indexSet & freeIndexSet).
3. Remove the subset from freeIndexSet using XOR (^=).
4. Calculate ERC1155 token IDs for each split position using CTHelpers.getCollectionId and getPositionId.
5. Store the split amounts (same as the input amount).

4. Handle Source of Split
Case A: Partitioning full outcome set (freeIndexSet == 0)
• Means the entire position is being split.
• Two scenarios:
1. Directly from collateral (parentCollectionId == 0):
• Transfer amount of collateral from the user into the contract.
2. From existing position (parentCollectionId != 0):
• Burn the user’s parent position of amount.
Case B: Partitioning subset (freeIndexSet != 0)
• Only splitting part of a position, e.g., splitting $:(A|C) into $:(A) and $:(C).
• Burn the subset of the position being split:
• fullIndexSet ^ freeIndexSet gives the bitmask representing the outcomes being split.

5. Mint New Positions
• Mint ERC1155 tokens representing the split positions to the sender.
• Each token corresponds to a new subset of outcomes defined in partition.

6. Emit Event

/// --- gnosis/conditional-tokens-contracts/contracts/ConditionalTokens.sol ---
/// @dev This function splits a position. If splitting from the collateral, this contract will attempt to transfer `amount` collateral from the message sender to itself. Otherwise, this contract will burn `amount` stake held by the message sender in the position being split worth of EIP 1155 tokens. Regardless, if successful, `amount` stake will be minted in the split target positions. If any of the transfers, mints, or burns fail, the transaction will revert. The transaction will also revert if the given partition is trivial, invalid, or refers to more slots than the condition is prepared with.
/// @param collateralToken The address of the positions' backing collateral token.
/// @param parentCollectionId The ID of the outcome collections common to the position being split and the split target positions. May be null, in which only the collateral is shared.
/// @param conditionId The ID of the condition to split on.
/// @param partition An array of disjoint index sets representing a nontrivial partition of the outcome slots of the given condition. E.g. A|B and C but not A|B and B|C (is not disjoint). Each element's a number which, together with the condition, represents the outcome collection. E.g. 0b110 is A|B, 0b010 is B, etc.
/// @param amount The amount of collateral or stake to split.
function splitPosition(
    IERC20 collateralToken,
    bytes32 parentCollectionId,
    bytes32 conditionId,
    uint[] calldata partition,
    uint amount
) external {
		/// --- Validate Partition Count ---
    require(partition.length > 1, "got empty or singleton partition");
    uint outcomeSlotCount = payoutNumerators[conditionId].length;
    require(outcomeSlotCount > 0, "condition not prepared yet");

		/// --- Prepare Full Outcome Set ---
    // For a condition with 4 outcomes fullIndexSet's 0b1111; for 5 it's 0b11111...
    uint fullIndexSet = (1 << outcomeSlotCount) - 1;
    // freeIndexSet starts as the full collection
    uint freeIndexSet = fullIndexSet;
    
    /// --- Check Partition Validity & Compute Position IDs ---
    // This loop checks that all condition sets are disjoint (the same outcome is not part of more than 1 set)
    uint[] memory positionIds = new uint[](partition.length);
    uint[] memory amounts = new uint[](partition.length);
    for (uint i = 0; i < partition.length; i++) {
        uint indexSet = partition[i];
        require(indexSet > 0 && indexSet < fullIndexSet, "got invalid index set");
        require((indexSet & freeIndexSet) == indexSet, "partition not disjoint");
        freeIndexSet ^= indexSet;
        positionIds[i] = CTHelpers.getPositionId(collateralToken, CTHelpers.getCollectionId(parentCollectionId, conditionId, indexSet));
        amounts[i] = amount;
    }

		/// --- Handle Source of Split ---
    if (freeIndexSet == 0) {
        // Partitioning the full set of outcomes for the condition in this branch
        if (parentCollectionId == bytes32(0)) {
            require(collateralToken.transferFrom(msg.sender, address(this), amount), "could not receive collateral tokens");
        } else {
            _burn(
                msg.sender,
                CTHelpers.getPositionId(collateralToken, parentCollectionId),
                amount
            );
        }
    } else {
        // Partitioning a subset of outcomes for the condition in this branch.
        // For example, for a condition with three outcomes A, B, and C, this branch
        // allows the splitting of a position $:(A|C) to positions $:(A) and $:(C).
        _burn(
            msg.sender,
            CTHelpers.getPositionId(collateralToken,
                CTHelpers.getCollectionId(parentCollectionId, conditionId, fullIndexSet ^ freeIndexSet)),
            amount
        );
    }

		/// --- Mint New Positions ---
    _batchMint(
        msg.sender,
        // position ID is the ERC 1155 token ID
        positionIds,
        amounts,
        ""
    );
    emit PositionSplit(msg.sender, collateralToken, parentCollectionId, conditionId, partition, amount);
}

Merge positions

• splitPosition takes a coarse-grained position (like A|B) and splits it into finer outcomes (A, B).

• mergePositions takes finer outcome positions (A, B) and merges them back into a coarser-grained position (A|B), or even into collateral if you merge everything.

1. Input Validation
• Must merge at least two outcome sets.
• Condition must already be prepared with outcomes(registered).

2. Initialize Outcome Sets
• fullIndexSet = all possible outcomes as a bitmask (e.g., 3 outcomes → 0b111).
• freeIndexSet tracks which outcomes haven’t been consumed yet.

3. Validate Partition & Collect Position IDs
• Each partition subset must:
• Not be empty or the entire set.
• Not overlap with others (disjoint).
• Builds positionIds (ERC-1155 token IDs) for positions to burn.
• Records amount to burn from each.
Ensures logical partitioning of the condition.

4. Burn Input Positions
• Burns the user’s stake in each fine-grained position.
• This removes them from the more specific outcomes.

5. Handle Merge
1. Case 1 — Merging All Outcomes
If partition covers all outcomes:
• If no parent → return collateral.
• If parent exists → mint parent position tokens.
Equivalent of “closing” the condition.
b. Case 2 — Merging a Subset
• If not all outcomes merged → mint a new position representing the union of merged outcomes.
• Example: Condition {A,B,C}, merge A+C → new position (A|C).
Allows regrouping without fully exiting the condition.

6. Emit Event

/// --- gnosis/conditional-tokens-contracts/contracts/ConditionalTokens.sol ---
function mergePositions(
    IERC20 collateralToken,
    bytes32 parentCollectionId,
    bytes32 conditionId,
    uint[] calldata partition,
    uint amount
) external {
		/// --- Input Validation ---
    require(partition.length > 1, "got empty or singleton partition");
    uint outcomeSlotCount = payoutNumerators[conditionId].length;
    require(outcomeSlotCount > 0, "condition not prepared yet");

		/// --- Initialize Outcome Sets ---
    uint fullIndexSet = (1 << outcomeSlotCount) - 1;
    uint freeIndexSet = fullIndexSet;
    
    /// --- Validate Partition & Collect Position IDs ---
    uint[] memory positionIds = new uint[](partition.length);
    uint[] memory amounts = new uint[](partition.length);
    for (uint i = 0; i < partition.length; i++) {
        uint indexSet = partition[i];
        require(indexSet > 0 && indexSet < fullIndexSet, "got invalid index set");
        require((indexSet & freeIndexSet) == indexSet, "partition not disjoint");
        freeIndexSet ^= indexSet;
        positionIds[i] = CTHelpers.getPositionId(collateralToken, CTHelpers.getCollectionId(parentCollectionId, conditionId, indexSet));
        amounts[i] = amount;
    }
    
    /// --- Burn Input Positions ---
    _batchBurn(
        msg.sender,
        positionIds,
        amounts
    );

		/// --- Handle Merge ---
    if (freeIndexSet == 0) {
        if (parentCollectionId == bytes32(0)) {
            require(collateralToken.transfer(msg.sender, amount), "could not send collateral tokens");
        } else {
            _mint(
                msg.sender,
                CTHelpers.getPositionId(collateralToken, parentCollectionId),
                amount,
                ""
            );
        }
    } else {
        _mint(
            msg.sender,
            CTHelpers.getPositionId(collateralToken,
                CTHelpers.getCollectionId(parentCollectionId, conditionId, fullIndexSet ^ freeIndexSet)),
            amount,
            ""
        );
    }

    emit PositionsMerge(msg.sender, collateralToken, parentCollectionId, conditionId, partition, amount);
}

Redeem Positions

• ERC-1155 tokens representing outcomes are burned, and the user receives either:
• Collateral tokens (if parentCollectionId == 0), or
• Parent position tokens (if there is a parent collection).

1. Validate condition outcome
Checks that:
• Condition has been resolved (payoutDenominator > 0).
• Condition was prepared (payoutNumerators defined).
This prevents redeeming positions before the outcome is known.

2. Initialize variables
• totalPayout: accumulates how much the user should receive.
• fullIndexSet: bitmask representing all possible outcomes.

3. Loop over requested index sets
Validates each requested subset of outcomes:
• Cannot be empty (>0).
• Cannot cover the entire set (< fullIndexSet).

4. Compute position ID
Calculates ERC-1155 token ID for this outcome subset.

5. Compute payout numerator for the subset
• Iterates over all individual outcomes (j).
• For each outcome included in this subset (indexSet bitmask), adds the payout numerator.

6. Burn user’s position and add payout
• payoutStake: number of ERC-1155 tokens user holds for this subset.
• Computes proportional payout:

payoutStake * payoutNumerator / payoutDenominator

• Burns the ERC-1155 tokens to prevent double redemption.

7. Transfer payout to user
Two cases:
1. Root-level position (parentCollectionId == 0) → send collateral tokens.
2. Child collection → mint parent position instead.
This mirrors splitPosition / mergePositions logic for consistency.

8. Emit event

/// --- gnosis/conditional-tokens-contracts/contracts/ConditionalTokens.sol ---
function redeemPositions(IERC20 collateralToken, bytes32 parentCollectionId, bytes32 conditionId, uint[] calldata indexSets) external {
		/// --- Validate condition outcome ---
    uint den = payoutDenominator[conditionId];
    require(den > 0, "result for condition not received yet");
    uint outcomeSlotCount = payoutNumerators[conditionId].length;
    require(outcomeSlotCount > 0, "condition not prepared yet");

		/// --- Initialize variables ---
    uint totalPayout = 0;
    uint fullIndexSet = (1 << outcomeSlotCount) - 1;
    
    /// --- Loop over requested index sets ---
    for (uint i = 0; i < indexSets.length; i++) {
        uint indexSet = indexSets[i];
        require(indexSet > 0 && indexSet < fullIndexSet, "got invalid index set");
				/// --- Compute position ID ---
        uint positionId = CTHelpers.getPositionId(collateralToken,
            CTHelpers.getCollectionId(parentCollectionId, conditionId, indexSet));

				/// --- Compute payout numerator for the subset ---
        uint payoutNumerator = 0;
        for (uint j = 0; j < outcomeSlotCount; j++) {
            if (indexSet & (1 << j) != 0) {
                payoutNumerator = payoutNumerator.add(payoutNumerators[conditionId][j]);
            }
        }

				/// --- Burn user’s position and add payout ---
        uint payoutStake = balanceOf(msg.sender, positionId);
        if (payoutStake > 0) {
            totalPayout = totalPayout.add(payoutStake.mul(payoutNumerator).div(den));
            _burn(msg.sender, positionId, payoutStake);
        }
    }

		/// --- Transfer payout to user ---
    if (totalPayout > 0) {
        if (parentCollectionId == bytes32(0)) {
            require(collateralToken.transfer(msg.sender, totalPayout), "could not transfer payout to message sender");
        } else {
            _mint(msg.sender, CTHelpers.getPositionId(collateralToken, parentCollectionId), totalPayout, "");
        }
    }
    emit PayoutRedemption(msg.sender, collateralToken, parentCollectionId, conditionId, indexSets, totalPayout);
}

What is a Collection and Parent Collection

collectionId = hash(parentCollectionId, conditionId, indexSet)

• conditionId = the event (e.g., “Will Team A win the match?”).

• indexSet = bitmask representing the subset of outcomes of that condition.

• parentCollectionId = allows nesting conditions. It represents "the outcomes that were already fixed from earlier splits."

What is parentCollectionId?

• If you start from pure collateral: parentCollectionId = 0x0.

• If you already split once, and now want to refine further: parentCollectionId = the previous collection ID.

Example Walkthrough

• Condition 1 (C1): Weather tomorrow = {Sunny, Rainy} (2 outcomes).

• Condition 2 (C2): Match result = {Team A wins, Team B wins} (2 outcomes).

1. Sunny & A wins

2. Sunny & B wins

3. Rainy & A wins

4. Rainy & B wins

Step A: Split from collateral into Condition 1

• Here parentCollectionId = 0x0 (raw collateral).

• Partition = [Sunny, Rainy].

• posSunny = Position(DAI, Coll(Sunny))

• posRainy = Position(DAI, Coll(Rainy))

• 100 DAI locked in the contract

• 100 units of Sunny-position + 100 units of Rainy-position

Step B: Refine Sunny into Condition 2

• Here parentCollectionId = Coll(Sunny) (not 0x0 anymore).

• Partition = [A wins, B wins].

• posSunny_A = Position(DAI, Coll(Sunny & A wins))

• posSunny_B = Position(DAI, Coll(Sunny & B wins))

Step C: If you refine Rainy too…

• posRainy_A = Position(DAI, Coll(Rainy & A wins))

• posRainy_B = Position(DAI, Coll(Rainy & B wins))

Why parentCollectionId Matters

• It lets you build nested conditions step by step instead of going from raw collateral every time.

• It encodes the conditioning history.
For example:
• From 0x0 → Condition 1 → Coll(Sunny)
• Then from Coll(Sunny) → Condition 2 → Coll(Sunny & A wins)

Visualization

100 DAI collateral
   │
   ├─ split on Condition 1 (Sunny vs Rainy)
   │      parentCollectionId = 0x0
   │
   ├─ Sunny (100) ── split on Condition 2 (A vs B)
   │         parentCollectionId = Coll(Sunny)
   │         ├─ Sunny & A (100)
   │         └─ Sunny & B (100)
   │
   └─ Rainy (100) ── split on Condition 2 (A vs B)
             parentCollectionId = Coll(Rainy)
             ├─ Rainy & A (100)
             └─ Rainy & B (100)

Summary

• parentCollectionId is the collection you’re splitting from.

• 0x0 means splitting directly from collateral.

• Nonzero means you’re splitting a subset of outcomes you already created.

• This allows chaining conditions together, so you can express combinatorial outcomes (Sunny & A wins, Rainy & B wins, etc.).

Collection Id Calculation

• a parent collection (possibly empty),

• combined with a condition ID and an index set.

• Each collection = a point on secp256k1 (the same elliptic curve used in Ethereum signatures).

• To derive a new collection, we map (conditionId, indexSet) → an EC point.

• If there’s a parent, we add the EC points (ecadd) to combine.

• Finally, we compress (x, y) back into a single bytes32.

• Commutative: A + B = B + A

• Associative: (A + B) + C = A + (B + C)

getCollectionId(getCollectionId(0, C1, A), C2, B)
== getCollectionId(getCollectionId(0, C2, B), C1, A)

/// --- gnosis/conditional-tokens-contracts/contracts/CTHelpers.sol ---
/// @dev Constructs an outcome collection ID from a parent collection and an outcome collection.
/// @param parentCollectionId Collection ID of the parent outcome collection, or bytes32(0) if there's no parent.
/// @param conditionId Condition ID of the outcome collection to combine with the parent outcome collection.
/// @param indexSet Index set of the outcome collection to combine with the parent outcome collection.
function getCollectionId(bytes32 parentCollectionId, bytes32 conditionId, uint indexSet) internal view returns (bytes32) {
    uint x1 = uint(keccak256(abi.encodePacked(conditionId, indexSet)));
    bool odd = x1 >> 255 != 0;
    uint y1;
    uint yy;
    do {
        x1 = addmod(x1, 1, P);
        yy = addmod(mulmod(x1, mulmod(x1, x1, P), P), B, P);
        y1 = sqrt(yy);
    } while(mulmod(y1, y1, P) != yy);
    if(odd && y1 % 2 == 0 || !odd && y1 % 2 == 1)
        y1 = P - y1;

    uint x2 = uint(parentCollectionId);
    if(x2 != 0) {
        odd = x2 >> 254 != 0;
        x2 = (x2 << 2) >> 2;
        yy = addmod(mulmod(x2, mulmod(x2, x2, P), P), B, P);
        uint y2 = sqrt(yy);
        if(odd && y2 % 2 == 0 || !odd && y2 % 2 == 1)
            y2 = P - y2;
        require(mulmod(y2, y2, P) == yy, "invalid parent collection ID");

        (bool success, bytes memory ret) = address(6).staticcall(abi.encode(x1, y1, x2, y2));
        require(success, "ecadd failed");
        (x1, y1) = abi.decode(ret, (uint, uint));
    }

    if(y1 % 2 == 1)
        x1 ^= 1 << 254;

    return bytes32(x1);
}

1. Turn (conditionId, indexSet) into an EC point

uint x1 = uint(keccak256(abi.encodePacked(conditionId, indexSet)));
bool odd = x1 >> 255 != 0;
uint y1;
uint yy;
do {
    x1 = addmod(x1, 1, P);
    yy = addmod(mulmod(x1, mulmod(x1, x1, P), P), B, P);
    y1 = sqrt(yy);
} while(mulmod(y1, y1, P) != yy);

• Start with a hash x1 = keccak256(conditionId, indexSet).

• Interpret it as a candidate x-coordinate.

• Try successive values of x1 until it lies on the curve:

• Compute the valid y1 with sqrt.

2. Pick a canonical y (sign fixing)

if(odd && y1 % 2 == 0 || !odd && y1 % 2 == 1)
    y1 = P - y1;

• For each x, there are two possible y values (since y² = ... has two roots).

• To avoid ambiguity, we pick one deterministically:
• Use the high bit of the original hash (odd) to decide which y to keep.

3. If parent exists, add parent’s point

uint x2 = uint(parentCollectionId);
if(x2 != 0) {
    odd = x2 >> 254 != 0;
    x2 = (x2 << 2) >> 2;
    yy = addmod(mulmod(x2, mulmod(x2, x2, P), P), B, P);
    uint y2 = sqrt(yy);
    if(odd && y2 % 2 == 0 || !odd && y2 % 2 == 1)
        y2 = P - y2;
    require(mulmod(y2, y2, P) == yy, "invalid parent collection ID");

    (bool success, bytes memory ret) = address(6).staticcall(abi.encode(x1, y1, x2, y2));
    require(success, "ecadd failed");
    (x1, y1) = abi.decode(ret, (uint, uint));
}

• parentCollectionId is encoded in the same format (compressed EC point).

• Decode it back to (x2, y2) using the same parity trick.

• Verify (x2, y2) is valid.

• Call precompiled contract 0x06 (ecadd) to compute:

(x1, y1) = (x1, y1) + (x2, y2)

• Now (x1, y1) represents the combined collection.

4. Compress back into bytes32

if(y1 % 2 == 1)
    x1 ^= 1 << 254;

return bytes32(x1);

• Use x1 as the base value.

• Store the parity of y1 in bit 254.

• Return as bytes32.

Relation to Elliptic Curve Math

• Curve equation: secp256k1 → y² = x³ + 7 mod P.

• Point encoding: (x, y) → compressed form (x + y-parity).

• Point addition: combine conditions by EC addition.

• Composability: Adding points preserves order-independence.

• Each (conditionId, indexSet) = base generator point.

• Each parentCollectionId = previously combined generator.

• getCollectionId = "hash-to-curve, then add to parent".