Skip to main content

BitMillions: Constant-Complexity Parimutuel Winner Counting via Boolean Lattice Transforms on EVM

Rodrigo Dias · Pedro Gonçalves bitmillions.app

Last updated: 2026-04-10

Abstract. We present the algorithmic design underlying BitMillions, a fully on-chain parimutuel lottery protocol on Base. The central challenge of building a parimutuel lottery on a blockchain is winner counting: determining how many tickets match each prize tier requires comparing every purchased ticket against the winning numbers — an $O(n)$ operation that becomes infeasible at scale under EVM gas constraints. BitMillions resolves this with a two-phase approach. At ticket purchase time, each ticket incrementally populates a Boolean lattice via submask enumeration, recording the superset structure of all purchased tickets at a fixed gas cost per ticket, independent of total volume. At draw time, submask enumeration over the winning ticket combined with Möbius inversion — implemented as Sum-over-Subsets dynamic programming (Yates' algorithm) — computes exact winner counts for all prize tiers in $O(k \cdot 2^k)$ operations, where $k$ is the number of drawn values per ticket. This complexity is strictly independent of ticket count. For the launch configuration of $k = 7$, draw resolution requires at most 896 operations. We describe the data structure, demonstrate the correctness of the Möbius inversion, analyze gas complexity, and compare the approach with existing on-chain lottery designs.

1. Introduction​

Decentralized smart contract platforms make it possible to operate financial applications without a trusted intermediary. Lotteries are a natural target: the mechanics are simple, the trust requirements are high, and the record of traditional operators is poor. State lotteries typically divert more than 50% of ticket revenue to operating costs, charitable distributions, and profit; randomness sources are opaque; winners depend on the operator to receive their prizes. A blockchain lottery eliminates all three problems in principle.

The practical obstacle is scalability. A lottery's core computation — determining how many tickets match each prize tier — requires comparing every purchased ticket against the winning numbers. For a simple raffle (one winner, no tiers), this is trivially $O(n)$ in ticket count. For a set-based parimutuel lottery, where ticket order is irrelevant and partial matches yield prizes, the problem is harder: the system must compute, for every prize tier, the exact number of tickets whose selections overlap the winning numbers in the right way. At scale, naive $O(n)$ winner counting is infeasible on the EVM — gas costs per operation are non-trivial, and upkeep execution is bounded by Chainlink Automation's approximately five million gas cap per call.

Existing on-chain lotteries sidestep this problem in one of four ways: they use fixed jackpots that require no winner counting; they reduce to raffles (one randomly selected winner from all entrants); they make ticket order matter, so that winner identification becomes a direct hash lookup rather than a set-matching problem — a format compromise that departs from the nature of a genuine parimutuel lottery; or they move winner-counting computation off-chain, reintroducing the trust dependency that on-chain protocols are designed to eliminate.

BitMillions takes a different approach. We observe that winner counting across all prize tiers is equivalent to computing exact subset-match counts on a Boolean lattice restricted to the winning ticket's selections. By building this lattice incrementally as tickets are purchased — at a constant gas cost per ticket — we eliminate the $O(n)$ work from draw time entirely. The lattice is fully populated when the draw closes, and a single bounded computation resolves winner counts for all tiers regardless of how many tickets were sold.

This paper describes that computation in detail. Section 2 gives a protocol overview. Section 3 formalizes the winner-counting problem and its constraints. Sections 4, 5, and 6 describe the bitmap representation, buy-time lattice construction, and draw-time Möbius inversion respectively. Section 7 analyzes complexity. Sections 8 and 9 cover randomness and the two-upkeep automation architecture. Section 10 discusses related work, and Section 11 concludes.

2. Protocol Overview​

BitMillions is a parimutuel lottery protocol deployed on Base (Ethereum Layer 2). All funds, tickets, draws, and payouts are managed on-chain. There is no backend, no custodian, and no manual draw operation. The protocol is designed to run indefinitely after deployment, driven entirely by Chainlink Automation and Chainlink VRF.

2.1 Ticket Format​

Each ticket consists of two independent selections: $N$ main numbers chosen from a pool of $\text{NP}$ values, and $S$ lucky stars chosen from a pool of $\text{SP}$ values. $\text{NP} = 50$, $\text{SP} = 12$, $N = 5$, $S = 2$, giving $k = N + S = 7$. Each ticket costs 3 USDC. Selections are unordered sets; order does not affect prize eligibility.

2.2 Draw Lifecycle​

Each draw proceeds through three states. In the Open state, players purchase tickets. When the schedule triggers, the contract enters Mixing: a Chainlink VRF randomness request is submitted, and a one-hour timelock begins. Upon receiving the verified random seed, the next upkeep call enters the Drawing state, resolves winner counts, allocates prizes and charity donations, and immediately opens the next draw. If VRF fails or no tickets were sold, the draw is postponed cleanly and retried at the next trigger.

2.3 Economic Structure​

BitMillions uses a parimutuel prize model: prizes are funded entirely by ticket sales and distributed among winners. No fixed prizes, no external funding. Every USDC in the prize pool comes from a ticket purchase. The allocation per ticket sale is split into four streams: jackpot rollover (min 25%), prizes pool (min 15%), charity donation (5–25%), and royalties (max 15%). These bounds are immutable contract constants — compiled into the bytecode and not overridable by the owners. Prizes are claimed via a pull model: winners call the contract to withdraw. No funds are ever pushed to external addresses.

3. The Winner-Counting Problem​

Let $T_1, \ldots, T_n$ denote the set of $n$ purchased tickets, where each $T_i = (T_{i,m}, T_{i,s})$ with $T_{i,m} \subseteq {1,\ldots,\text{NP}}$, $|T_{i,m}| = N$, and analogously for stars. Let $W = (W_m, W_s)$ be the winning ticket drawn at random. Prize tier $(n, s)$ is awarded to tickets matching exactly $n$ main numbers and $s$ lucky stars from $W$. Define:

$$M(n, s) = \bigl|{ i : |T_{i,m} \cap W_m| = n \text{ and } |T_{i,s} \cap W_s| = s }\bigr|$$

The system must compute $M(n, s)$ for each configured prize tier after the winning ticket is known. Prize per winner at tier $(n, s)$ is then the tier's allocated fraction of the prizes pool divided by $M(n, s)$, computed once at draw time and stored for cheap claim lookups.

3.1 Notation​

SymbolDefinition
NPMain numbers pool size (50)
SPLucky stars pool size (12)
NMain numbers drawn per ticket (5)
SLucky stars drawn per ticket (2)
kN + S — total values drawn per ticket; determines lattice size (7)
nNumber of tickets purchased in a draw
$T_i$$i$-th purchased ticket, encoded as bitmap pair $(T_{i,m}, T_{i,s})$
$W$Winning ticket, encoded as bitmap pair $(W_m, W_s)$
$L[m]$On-chain lattice: count of purchased tickets $T$ with $m \subseteq T$
$\text{exact}[p]$Count of tickets $T$ with $T \cap W = p$ exactly
$M(n, s)$Winner count for prize tier $(n, s)$: tickets matching exactly $n$ main numbers and $s$ lucky stars

Table 1. Summary of notation.

3.2 Why Naive Counting Fails at Scale​

The direct approach evaluates, for each ticket $T_i$, the intersection $T_{i,m} \cap W_m$ and its cardinality, and does the same for stars. This requires $O(n)$ operations at draw time. On the EVM, each SLOAD (reading a stored ticket) costs 2,100 gas cold. At one million tickets, that is 2.1 billion gas — roughly 420 times Chainlink Automation's per-upkeep limit. Even at 10,000 tickets the cost may not fit a single transaction. $O(n)$ at draw time is not viable for a protocol intended to run at scale indefinitely.

3.3 The Key Insight​

Rather than iterating tickets at draw time, we can build a data structure at buy time that encodes the answer. Specifically, we observe that computing $M(n, s)$ for all tiers simultaneously is equivalent to the Möbius inversion of a function on the Boolean lattice of subsets of $W$. If we can make $L[p]$ — the number of tickets containing a given subset $p$ of $W$ — available at constant cost, then Möbius inversion resolves all winner counts in $O(k \cdot 2^k)$ operations, independent of $n$.

4. Bitmap Ticket Representation​

Each ticket $T = (T_m, T_s)$ is stored not as an array of chosen numbers but as two integer bitmasks. The main selection $T_m$ is encoded as an NP-bit integer where bit $j$ is set if number $j$ was chosen. The lucky stars selection $T_s$ is encoded as an SP-bit integer analogously.

This representation has three gas-efficiency properties critical to the algorithm:

  • Subset check: $p \subseteq T$ iff (p & T) == p, a single bitwise AND and comparison, $O(1)$.
  • Hamming weight (population count): $|p| = \text{popcount}(p)$, the EVM's native opcode, $O(1)$. Used to identify which prize tier a submask belongs to.
  • Submask enumeration: all non-empty submasks of a bitmask $m$ can be enumerated using the identity: next = (current − 1) & m, starting at $m$ and terminating when the value reaches 0. Exactly $2^{|m|} - 1$ non-empty submasks are visited.

Each ticket's bitmap is stored in a per-player on-chain record for use at claim time (Section 6.5). In addition, each ticket incrementally updates the shared lattice (Section 5). The gas efficiency comes from draw time: winner counts for all tiers are resolved entirely from the lattice without revisiting individual ticket bitmaps. The lattice is a sparse on-chain mapping that grows with ticket volume, but the draw-time computation reads at most $2^k$ entries — those that are submasks of the winning ticket — regardless of how many total entries the lattice contains.

5. Buy-Time Lattice Construction​

We maintain a mapping $L$ indexed by pairs of bitmasks $(m_m, m_s)$. The semantic invariant is:

$$L[m_m, m_s] = \bigl|{ i : m_m \subseteq T_{i,m} \text{ and } m_s \subseteq T_{i,s} }\bigr|$$

In other words, $L[m]$ is the number of purchased tickets whose main selection is a superset of $m_m$ and whose star selection is a superset of $m_s$. This is the sum-over-supersets (super-Zeta) transform of the per-ticket indicator function.

5.1 Update Procedure​

When a ticket $T = (T_m, T_s)$ is purchased, the contract enumerates all submasks of $(T_m, T_s)$ and increments $L$ at each:

For each non-empty $(m_m, m_s)$ with $m_m \subseteq T_m$ and $m_s \subseteq T_s$:

$$L[m_m, m_s] \leftarrow L[m_m, m_s] + 1$$

The number of non-empty $(m_m, m_s)$ pairs enumerated per ticket is $2^k - 1$. For $k = 7$, this is exactly 127 SSTORE operations per ticket, a fixed cost independent of how many other tickets have been purchased. The empty submask is skipped since it is never consulted at draw time. The invariant is established and maintained after every purchase, requiring no batch recomputation.

5.2 Correctness of the Invariant​

After $n$ purchases, $L[m]$ has been incremented by ticket $T_i$ iff $m_m \subseteq T_{i,m}$ and $m_s \subseteq T_{i,s}$, which is exactly the condition in the invariant definition. The incremental construction is therefore equivalent to computing the full super-Zeta transform over all $n$ tickets simultaneously, but spread across $n$ constant-cost operations rather than a single $O(n \cdot 2^k)$ batch.

graph TD
    top["111 — {w₀,w₁,w₂}"]
    p01["110 — {w₀,w₁}"]
    p02["101 — {w₀,w₂}"]
    p03["011 — {w₁,w₂}"]
    p11["100 — {w₀}"]
    p12["010 — {w₁}"]
    p13["001 — {w₂}"]
    bot["000 — ∅"]

    top --- p01
    top --- p02
    top --- p03
    p01 --- p11
    p01 --- p12
    p02 --- p11
    p02 --- p13
    p03 --- p12
    p03 --- p13
    p11 --- bot
    p12 --- bot
    p13 --- bot

Figure 1. Boolean lattice $\mathcal{B}_3$ for $k = 3$. Each node is a 3-bit mask representing a subset of the three drawn values ${w_0, w_1, w_2}$, re-indexed so that bit $i$ corresponds to $w_i$. Nodes are arranged by Hamming weight: $000 = \varnothing$ at the bottom, singletons ${001, 010, 100}$ at level 1, pairs ${011, 101, 110}$ at level 2, and $111 = {w_0, w_1, w_2}$ at the top. An edge connects two nodes whose masks differ in exactly one bit. At buy time, purchasing a ticket with intersection mask $m$ against $W$ increments every ancestor node (superset of $m$) — propagating upward through the lattice. At draw time, Yates' algorithm inverts this by propagating counts downward, recovering the exact match count at each node.

6. Draw Resolution via Möbius Inversion​

At draw time, the VRF delivers a random seed from which the winning ticket $W = (W_m, W_s)$ is derived. The goal is to compute $M(n, s)$ for each prize tier using only $L$ lookups.

6.1 Restricting the Lattice to Subsets of W​

The subsets of $W$ — pairs $(p_m, p_s)$ with $p_m \subseteq W_m$ and $p_s \subseteq W_s$ — form a Boolean lattice of size $2^k$. We re-index these $2^k$ subsets as integers in $[0, 2^k - 1]$ by mapping each element of $W$ to a bit position. Define:

$$L'[\text{mask}'] = L[p_m(\text{mask}'), p_s(\text{mask}')]$$

where $p_m(\text{mask}')$ and $p_s(\text{mask}')$ are the main and star submasks of $W$ corresponding to the re-indexed mask. After re-indexing, $L'[\text{mask}']$ counts tickets containing at least all winning values indicated by $\text{mask}'$.

Example. Suppose $k = 3$ and the draw produces winning values $w_0 = 5$, $w_1 = 12$, $w_2 = 42$. We assign bit positions: $5 \mapsto$ bit $0$, $12 \mapsto$ bit $1$, $42 \mapsto$ bit $2$. A purchased ticket whose selection contains ${5, 42}$ from the winning set has bits $0$ and $2$ set, giving re-indexed mask $\text{mask}' = 101_2 = 5$. The lattice entry $L'[5]$ therefore counts all tickets containing both 5 and 42 (regardless of whether they also contain 12). The full set ${5, 12, 42}$ corresponds to $\text{mask}' = 111_2 = 7$, and $L'[7]$ counts tickets matching all three winning values. More generally, $L'[\text{mask}']$ is the superset-count for the subset of winning values indicated by the set bits of $\text{mask}'$.

6.2 The Möbius Inversion Identity​

Define the $\text{exact}$ function: $\text{exact}[p] =$ number of tickets $T$ with $T_m \cap W_m = p_m$ and $T_s \cap W_s = p_s$, i.e., tickets matching exactly the values in $p$ and no others from $W$. Then:

$$L'[p] = \sum_{p \subseteq q \subseteq W} \text{exact}[q]$$

This holds because a ticket counted in $\text{exact}[q]$ matches exactly $q$ from $W$, and it contributes to $L'[p]$ for every $p \subseteq q$. Since $p \subseteq W$ and $L'[p]$ counts tickets with $p \subseteq T$: a ticket with $T \cap W = q$ contributes to $L'[p]$ iff $p \subseteq q$. The identity follows. By the Möbius inversion theorem on the Boolean lattice:

$$\text{exact}[p] = \sum_{p \subseteq q \subseteq W} (-1)^{|q| - |p|} \cdot L'[q]$$

This is the Inclusion-Exclusion Principle applied to the Boolean lattice restricted to subsets of $W$. It is the standard Möbius function of the Boolean lattice, equal to $(-1)^{|q|-|p|}$.

6.3 SOS Dynamic Programming (Yates' Algorithm)​

Rather than computing the Möbius sum independently for each $p$ (which would cost $O(4^k)$ total), we apply the inverse Sum-over-Subsets DP. Starting with $L'$ already loaded:

$$ \begin{aligned} &\textbf{for } i \in {0, \ldots, k-1}\textbf{:}\ &\quad \textbf{for } \text{mask}' \in {0, \ldots, 2^k-1}\textbf{:}\ &\qquad \textbf{if } \text{bit } i \text{ is set in } \text{mask}'\textbf{:}\ &\qquad\quad L'[\text{mask}'] \leftarrow L'[\text{mask}'] - L'[\text{mask}' \text{ with bit } i \text{ cleared}] \end{aligned} $$

After $k$ passes, $L'[p]$ holds $\text{exact}[p]$ for every $p \subseteq W$. This is Yates' algorithm, equivalent to the inverse Zeta transform on the Boolean lattice, running in $O(k \cdot 2^k)$ time.

6.4 Tier Aggregation​

After the SOS DP, compute $M(n, s)$ by iterating all $2^k - 1$ non-empty submasks of $W$ and accumulating:

$$M(n, s) = \sum_{\substack{p, :, \text{popcount}(p_m) = n \ \text{popcount}(p_s) = s}} \text{exact}[p]$$

Tier identification for each submask, computing $\text{popcount}(p_m)$ and $\text{popcount}(p_s)$, uses the EVM's Hamming weight opcode, $O(1)$ per submask. The aggregation pass is $O(2^k)$.

6.5 Prize Per Winner, Claiming, and Rounding​

Once all $M(n, s)$ values are known, the prize per winner for each tier is computed as a single integer division and stored in tierPayouts. Claims read this pre-computed value directly.

Prize settlement uses a progressive lazy evaluation model. Each player record tracks lastDrawUpdate — the most recent draw processed for that player. At the start of every buyTickets() call, the contract settles the previous completed draw for the player: it iterates their stored ticket bitmaps for that draw, applies a bitwise AND with the winning bitmap, reads the pre-computed tierPayouts value, and accumulates their winnings. This means that a player who purchases tickets across consecutive draws progressively settles each prior draw with each subsequent buy. By the time the player calls claimPrizes(), all prior draws are already settled; the claim function handles any remaining unsettled draw and transfers the full accumulated balance in a single call. One call to claimPrizes() is always sufficient, regardless of how many draws the player has participated in. Per-draw claim cost is $O(t)$ where $t \leq$ ticket total limit — a per-draw configurable cap, not a function of draws entered or total ticket volume.

Let $P$ denote the total prize allocation for tier $(n, s)$ in atomic USDC units, and let $M = M(n, s)$ be the winner count. The per-winner payout is

$$\left\lfloor \frac{P}{M} \right\rfloor$$

and the rounding remainder (dust) is

$$R = P - M \cdot \left\lfloor \frac{P}{M} \right\rfloor, \quad 0 \leq R < M.$$

Since USDC carries 6 decimal places, one atomic unit equals $10^{-6}$ USDC. In the worst case $R = M - 1$ atomic units, sub-cent for any realistic winner count. The remainder $R$ is not distributed; it remains in the contract and is swept into the following draw's jackpot when that draw opens.

7. Complexity Analysis​

Table 2 summarises the computational cost of each operation. All complexities are measured in terms of elementary on-chain operations (SLOAD, SSTORE, arithmetic).

OperationComplexityNotes
Ticket purchase (buy-time lattice update)$O(2^k)$127 SSTORE for k=7 ($2^k - 1$ non-empty submasks); fixed cost per ticket
Lattice reads (cold SLOADs during inversion)$O(2^k)$Up to $2^k$ cold SLOAD calls; one per submask of $W$, charged on first access within the inversion loop
Möbius inversion (SOS DP)$O(k \cdot 2^k)$$k$ passes over $2^k$ entries; arithmetic on values read from the lattice
Tier aggregation$O(2^k)$One pass; $O(1)$ popcount per submask
Prize per winner computation$O(T)$$T$ = number of configured prize tiers; one division per tier
Total draw-time cost$O(k \cdot 2^k)$Independent of ticket count $n$
Prize claim (per player)$O(t)$$t \leq$ ticket total limit (configurable per draw); lazy evaluation processes at most one draw per call; reads pre-computed tierPayouts

Table 2. Computational complexity of each operation.

7.1 Concrete Numbers at Launch Configuration​

With $k = 7$ (N = 5 main + S = 2 lucky stars): $2^k = 128$ lattice nodes. Buy-time cost per ticket: 127 SSTORE operations ($2^k - 1$ non-empty submasks; a one-time fixed cost, not a function of $n$). Draw-time SOS DP: $k \cdot 2^k = 896$ arithmetic operations (an upper bound on the DP pass count; the exact iteration count in the contract is lower, as the inversion and tier aggregation loops skip certain branches). Up to 128 cold SLOAD calls are charged on first access to each of the $2^k$ lattice nodes within the inversion loop. This fits comfortably within Chainlink Automation's gas budget for a single upkeep call, regardless of whether 100 or one million tickets were sold.

7.2 Comparison with $O(n)$ Ticket Iteration​

The naive $O(n)$ approach iterates all $n$ purchased tickets at draw time, computing intersections and cardinalities for each. At a conservative 5,000 gas per ticket (one SLOAD + intersection + popcount), the gas cost at $n = 1{,}000$ is 5M gas — already at the Chainlink limit. Beyond 1,000 tickets, the naive approach fails. The lattice approach's draw-time gas cost is dominated by up to 128 cold SLOAD calls to the lattice ($128 \times 2{,}100 \approx 269{,}000$ gas), plus the in-memory SOS DP arithmetic — well under one million gas in total, regardless of $n$.

7.3 Comparison with $O(4^k)$ Naive Inclusion-Exclusion​

A naive approach to the Möbius inversion evaluates the inclusion-exclusion sum directly for each $p$ by scanning all supersets of $p$ within $W$. For a fixed $p$, there are $2^{k - |p|}$ such supersets; summing over all $2^k$ choices of $p$ gives $\sum_{p \subseteq W} 2^{k-|p|} = 3^k$ total operations — commonly cited as $O(4^k)$ as a loose upper bound. For $k = 7$ this is $3^7 = 2{,}187$ operations — still bounded in $k$, but larger than necessary. Replacing this with SOS DP reduces draw-time operations to $O(k \cdot 2^k) = 896$, a $2.4\times$ improvement at $k = 7$ (and increasingly favorable as $k$ grows, since $3^k / (k \cdot 2^k) = (3/2)^k / k$ grows without bound).

8. Randomness and Winning Number Derivation​

A lottery's integrity depends entirely on the unpredictability and tamper-resistance of its randomness source. BitMillions uses Chainlink VRF V2 Plus, the only system providing verifiable, on-chain-provable randomness on EVM-compatible networks today.

Chainlink VRF generates a random value alongside a cryptographic proof of its validity. This proof is verified on-chain before the seed is accepted by the contract. If proof verification fails, the seed is rejected and the draw is postponed. There is no fallback to block hashes or timestamps. The VRF is configured to require the maximum block confirmation depth before delivering the seed, providing the strongest security guarantee the protocol offers.

The mathematical guarantee: no party — not the protocol owners, not Chainlink node operators, not block producers — can know or influence the winning numbers before they are derived from the verified seed. This is a cryptographic property of the VRF, not a policy or a trust assumption.

8.2 Winning Number Derivation​

The contract receives one random word (256-bit integer) from the VRF coordinator. Winning main numbers and lucky stars are derived sequentially by repeatedly hashing the seed:

$$ \begin{aligned} \text{seed} &\leftarrow \text{keccak256}(\text{seed}) \ \text{value} &= (\text{seed} \bmod \text{NP}) + 1 \end{aligned} $$

Numbers are drawn without replacement: if the derived value duplicates an already-drawn number, the seed is hashed again and a new value is derived. In the worst case (unlikely in practice), this process is bounded by the pool size. The resulting $W_m$ and $W_s$ are encoded as bitmasks and stored for the lattice lookup in Section 6.

9. Two-Upkeep Architecture​

BitMillions separates the draw lifecycle into two Chainlink Automation upkeep calls rather than one. This is a deliberate gas architecture decision, not a workaround.

Upkeep 1 (Mixing): Submits the VRF randomness request to the Chainlink coordinator and starts the one-hour timelock. The VRF callback function, invoked by Chainlink upon delivering the seed, performs only minimal work: storing the verified seed and transitioning state to Drawing. Chainlink imposes restrictions on computation inside VRF callbacks; keeping the callback minimal avoids any risk of hitting those limits.

Upkeep 2 (Drawing): Consumes the stored seed to derive winning numbers, runs the full draw resolution (SOS DP, tier aggregation, prize allocation), opens the next draw, and emits all relevant events. This upkeep has the full gas budget available with no competing concerns.

The separation ensures that the most computationally intensive step (lattice lookup and Möbius inversion) always has its full gas budget. The timelock also acts as a minimum draw interval: because draws can only open once per upkeep trigger and each trigger must be spaced at least TIMELOCK apart, rapid draw cycling is structurally impossible. This prevents a compromised or malicious operator from triggering draws in rapid succession to drain prize funds. If VRF fails to deliver within the timelock, the state resets to Open cleanly, and the next upkeep trigger retries from the beginning. The protocol cannot enter a permanently broken state.

The draw advancement function is public: any caller can trigger upkeep if the conditions are met. Chainlink Automation is the default and expected trigger, but it is not the only one. If Automation were unavailable, any external actor could advance the draw. The only component that cannot be substituted is Chainlink VRF: verifiable randomness has no equivalent alternative on current EVM-compatible networks.

10.1 Sequence-Based Hash Lookups (e.g., PancakeSwap Lottery)​

PancakeSwap Lottery is the most comparable on-chain lottery project. It solves the winner-counting problem by making ticket number order matter: a winning ticket must match the drawn numbers in the same sequence, not just as a set. This transforms winner identification from a set-matching problem into a direct hash lookup — $O(1)$ per ticket — but it changes the nature of the lottery. Players cannot freely choose their numbers without regard to order, and the prize structure reflects ticket ordering rather than combinatorial selection. BitMillions retains true set semantics: order does not matter, and the parimutuel prize tiers reflect genuine combinatorial overlap with the winning numbers.

10.2 Traditional Lotteries​

Traditional lotteries (state-operated or private) resolve winner counting off-chain, have opaque randomness sources, divert around 50% of ticket revenue away from prizes, and require trust in the operator for prize distribution. The comparison is instructive on each dimension: BitMillions enforces a maximum 15% royalty via contract constants; Chainlink VRF provides a cryptographic randomness guarantee rather than a trust-based one; and the pull model for withdrawals means no operator can block, delay, or intercept a winner's prize. The algorithmic challenge described in this paper (scalable on-chain winner counting) does not arise in off-chain systems, since computation is unconstrained.

10.3 Boolean Lattice Techniques in Computer Science​

Zeta and Möbius transforms on the Boolean lattice are classical tools in combinatorics and algorithm design. Yates' algorithm for the Sum-over-Subsets (SOS) DP runs in $O(k \cdot 2^k)$ and is well-studied [1]. The Möbius function of the Boolean lattice is the function $\mu(x, y) = (-1)^{|y|-|x|}$ for $x \subseteq y$, which corresponds exactly to the Inclusion-Exclusion Principle [2]. The contribution of this work is applying these techniques in an on-chain context with an incremental, buy-time construction that avoids any batch computation at draw time.

11. Conclusion​

We have described the algorithmic design of BitMillions, a fully on-chain parimutuel lottery protocol that resolves winner counts across all prize tiers in $O(k \cdot 2^k)$ operations at draw time, where $k$ is the number of values drawn per ticket — a constant independent of the number of tickets sold. The key insight is the separation of concerns between buy time and draw time: each ticket purchase contributes $O(2^k)$ incremental updates to a Boolean lattice, fully populating the data structure needed for Möbius inversion without any batch recomputation. At draw time, Yates' algorithm resolves exact winner counts in a single bounded pass.

This makes BitMillions the first on-chain lottery with true set-based parimutuel mechanics at constant draw-time complexity. Prior designs either compromised the lottery format to avoid $O(n)$ winner counting, or operated as raffles with no tier matching. BitMillions achieves both format integrity and on-chain scalability simultaneously.

The protocol is open source and verified on-chain. The smart contract code, the lattice implementation, and the SOS DP draw resolution are publicly auditable on the Base block explorer [5]. The web application is accessible at [6] and protocol documentation at [7]. The protocol is designed to run indefinitely after deployment, with no backend, no manual operations, and no trusted parties required for draw execution or prize distribution.

Author contributions. R.D. designed and implemented the smart contract protocol, including the Boolean lattice winner-counting algorithm, draw lifecycle, Chainlink VRF and Automation integration, economic model, and contract constants. R.D. also led the Farcaster miniapp integration logic on the frontend. P.G. developed the web frontend with full UI/UX design, including mobile-ready layout and Base App compatibility.

Acknowledgements. The authors thank the Chainlink team for VRF and Automation infrastructure, and the OpenZeppelin and Solady library maintainers whose audited implementations underpin portions of the contract.

References​

[1] Yates, F. A. (1937). The Design and Analysis of Factorial Experiments. Technical Communication No. 35. Commonwealth Bureau of Soils. (Describes the fast subset sum algorithm widely attributed to Yates and used as the basis for the modern SOS DP.)

[2] Rota, G.-C. (1964). On the foundations of combinatorial theory I: Theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 2(4), 340–368.

[3] Chainlink Labs. (2023). Chainlink VRF V2 Plus Documentation. https://docs.chain.link/vrf

[4] Chainlink Labs. (2023). Chainlink Automation Documentation. https://docs.chain.link/chainlink-automation

[5] BitMillions Protocol. Verified smart contract, Base block explorer. [TODO: insert contract address URL post-deployment]

[6] BitMillions Protocol. Web application. https://bitmillions.app/

[7] BitMillions Protocol. Documentation. https://docs.bitmillions.app/