Một triệu vé, không dò lại vé nào: Megapot đếm người trúng on-chain kiểu gì?

Đường đi của một tấm vé

Đây là toàn bộ vòng đời một kỳ quay trong contract. Các câu hỏi bên dưới đi lần lượt qua từng bước.

Câu 1: chốt kỳ thì khó ở chỗ nào?

Khi Pyth Entropy trả về số ngẫu nhiên, nó gọi hàm scaledEntropyCallback của Jackpot. Trong đúng một giao dịch đó, contract phải biết mỗi hạng giải có bao nhiêu vé trúng để tính tiền cho từng hạng.

Cách naive ai cũng nghĩ ra đầu tiên: lưu danh sách vé, lúc chốt thì lặp qua từng vé và so với kết quả.

for (uint256 t = 0; t < tickets.length; t++) {       // 10.000 vé = 10.000 vòng
    uint8 hits = countHits(tickets[t].normals, winning);  // đọc vé từ storage rồi so
    bool b = tickets[t].bonus == winningBonus;
    tierCount[2 * hits + (b ? 1 : 0)]++;
}

Nó gãy ở đâu? Mỗi giao dịch có giới hạn gas. Callback của Pyth còn chặt hơn: nó chạy với một mức gas do contract đặt trước, entropyBaseGasLimit + 250.000 × bonusballMax, khoảng vài triệu gas với 10 bonus. Chỉ riêng việc đọc một ô storage chưa đụng tới đã tốn khoảng 2.100 gas, nên 10.000 vé là hơn 21 triệu gas, vượt xa mức đó. Bán càng nhiều vé thì vòng lặp càng dài, và đến một ngày giao dịch chốt kỳ hết gas giữa chừng. Kỳ quay bị kẹt, không ai nhận được tiền.

Megapot giải bài này bằng cách đổi chỗ chi phí: phần việc nặng được làm sẵn lúc mua vé, mỗi người mua tự trả gas cho phần của mình trong giao dịch riêng của họ. Đến lúc chốt, chỉ còn một lượng việc cố định. Để làm được vậy cần ba mảnh ghép: vé dạng bitmap, bảng đếm theo nhóm số, và phép bao hàm – loại trừ.

Câu 2: lưu một tấm vé thế nào?

Cách naive là lưu đúng như người mua gửi lên: mảng uint8[] [3, 9, 11, 13, 28] cộng một số bonus. Muốn biết hai vé có bao nhiêu số chung thì phải so từng cặp, 5 × 5 = 25 phép so sánh, và muốn chặn số trùng trong vé cũng phải lặp lồng nhau.

Megapot làm khác: gói cả vé vào một số uint256, coi mỗi bit như một ô đánh dấu:

• bit 0: bỏ trống (không có số 0)
• bit 1 đến 30: số thường, bit n bật nghĩa là chọn số n
• bit 31 đến 40: bonus, bonus b nằm ở bit 30 + b

Bit n có giá trị 2ⁿ. Khi in ra nhị phân, bit nhỏ nằm bên phải giống hàng đơn vị trong số thập phân, nên đọc chuỗi nhị phân phải đếm từ phải sang trái. Bạn có thể đổi vé ở ô dưới để xem:

Gói vé: OR từng bit

Người mua gửi lên mảng số bình thường (struct Ticket { uint8[] normals; uint8 bonusball; }). Contract tự đổi sang bitmap bằng một vòng lặp ngắn:

uint256 bitVector = 0;
for (uint256 i; i < _set.length; ++i) {
    require(_set[i] <= _maxNormalBall && _set[i] > 0, "Invalid set selection");
    require((bitVector & (1 << _set[i])) == 0, "Duplicate number in set");
    bitVector |= 1 << _set[i];
}
// rồi trong insert(): gắn bonus lên vùng trên số thường
ticketNumbers = set | 1 << (_bonusball + 30);

Hai phép bit làm hai việc ngược nhau. OR | là gộp: thêm bit vào, bit nào đã bật thì giữ nguyên. AND & là lọc: chỉ giữ bit mà cả hai bên cùng có. Dòng require thứ hai dùng AND để kiểm tra số trùng: nếu bit n đã bật sẵn thì kết quả khác 0, giao dịch bị revert.

Khi các bit không đè nhau, OR cho kết quả bằng phép cộng (2² | 2⁴ | 2⁵ = 4 + 16 + 32 = 52). Nhưng nếu nhập trùng số, phép cộng sẽ tràn sang bit khác thành một vé sai (4 + 4 = 8, tức là số 3). OR thì không bị vậy, và contract còn chặn trùng trước đó.

Câu 3: làm sao biết một vé trúng mấy số?

Cách naive với mảng số là hai vòng lặp lồng nhau:

for (i = 0; i < 5; i++)
    for (j = 0; j < 5; j++)
        if (ticket[i] == winning[j]) hits++;     // 25 lần so

Với bitmap, contract làm bằng đúng hai phép tính. AND giữ lại các số mà vé và kết quả cùng có, rồi popCount (thư viện Solady, tốn gas cố định) đếm số bit 1:

uint256 matchingBits = _ticketNumbers & _winningNumbers;
matches = LibBit.popCount(matchingBits);
uint256 ticketBonusball  = _ticketNumbers  >> (_normalBallMax + 1);   // >> 31: bỏ vùng số thường
uint256 winningBonusball = _winningNumbers >> (_normalBallMax + 1);
uint256 bonusballMatch = (ticketBonusball == winningBonusball) ? 1 : 0;
return 2 * (matches - bonusballMatch) + bonusballMatch;

Contract không có câu if (bit > 30) nào để nhận ra bonus. Nghĩa của bit nằm ở vị trí: số thường không bao giờ vượt bit 30, nên dịch phải 31 bit là chỉ còn lại phần bonus. Khi cần đọc ngược bonus ra số, unpackTicket lấy vị trí bit cao nhất (LibBit.fls) trừ đi 30.

Dòng cuối là một mẹo trải bảng 2 chiều thành mảng 1 chiều. Hạng giải có hai thông tin, trúng k số (0 đến 5) và có bonus hay không, nên được xếp thành 12 ô với index = 2k + bonus:

Câu 4: đếm mỗi hạng có bao nhiêu vé mà không duyệt vé?

So một vé thì đã rẻ. Nhưng lúc chốt kỳ vẫn cần biết tổng số vé ở mỗi hạng, và Câu 1 đã cho thấy không được lặp qua vé.

Thử lần 2, vẫn naive: lúc mua, đếm sẵn theo vé đầy đủ, kiểu count[vé] += 1. Hạng jackpot thì dễ: đọc đúng một ô count[kết quả]. Nhưng hạng "3 số + bonus" thì sao? Phải liệt kê mọi vé có thể có đúng 3 số trúng rồi đọc từng ô, tức 10 × C(25,2) = 3.000 ô. Cộng mọi hạng có ít nhất một số trúng, ở cả 10 cột bonus, là 893.760 lần đọc. Không vòng lặp theo vé nữa, nhưng vẫn quá nặng.

Ý tưởng của Megapot (thư viện TicketComboTracker): đừng đếm theo vé đầy đủ, mà đếm theo mọi tập con của vé. Mỗi khi bán một vé, tăng bộ đếm cho mọi nhóm số nằm trong vé đó. Khi đó câu hỏi "có bao nhiêu vé chứa cả 3 và 11?" chỉ là đọc một ô.

Trong bài, mình gọi chung các bộ đếm này là bảng đếm. Đó là một bảng lưu trong storage của contract (mapping comboCounts). Mỗi ô ứng với một nhóm số, ví dụ {3, 11}, và chỉ chứa một con số: đã bán bao nhiêu vé có chứa nhóm số đó.

Vé 5 số có 2⁵ − 1 = 31 tập con khác rỗng. Mỗi tập con cũng là một bitmap, tức một con số, nên dùng thẳng làm khóa của mapping. Đây là 31 ô mà vé ở phần trên sẽ tăng (đổi vé ở trên là danh sách này đổi theo):

struct ComboCount { uint128 count; uint128 dupCount; }     // gói vừa 1 slot storage
struct Tracker {
    uint8 normalMax;       // 30
    uint8 bonusballMax;    // thay đổi theo kỳ, ví dụ 10
    uint8 normalTiers;     // 5
    mapping(uint8 => mapping(uint256 => ComboCount)) comboCounts;  // [bonus][bitmap tập con]
    mapping(uint8 => ComboCount) bonusballTicketCounts;            // [bonus] tổng vé
}

// insert(): chạy cho từng vé lúc mua
isDup = comboCounts[_bonusball][set].count > 0;              // đủ 5 số + bonus đã có người mua?
for (uint8 i = 1; i <= 5; i++) {
    uint256[] memory subsets = Combinations.generateSubsets(set, i);   // C(5, i) tập con
    for (uint256 j = 0; j < subsets.length; j++)
        isDup ? comboCounts[_bonusball][subsets[j]].dupCount++
              : comboCounts[_bonusball][subsets[j]].count++;
}

Ba chi tiết đáng để ý:

• Sổ không lưu ai mua vé nào, chỉ lưu con số đếm. Quyền sở hữu nằm ở NFT vé, một chỗ khác.
• Bonus là khóa ngoài, không phải một bit trong tập con. Bonus chỉ có trúng hoặc trượt, không có "trúng một phần", nên tách thành cột riêng. Nếu nhét bit bonus vào tập con thì mỗi vé phải ghi 2⁶ − 1 = 63 ô thay vì 31.
• Sổ có kích thước hữu hạn. Mỗi cột bonus có tối đa C(30,1) + C(30,2) + … + C(30,5) = 174.436 ô. Bán thêm vé chỉ làm số đếm trong các ô tăng lên.

Mỗi kỳ có một bảng đếm riêng: mapping(uint256 => TicketComboTracker.Tracker) drawingEntries. Kết quả quay số thì không nằm trong bảng đếm, mà ở drawingState[kỳ].winningTicket.

Câu hỏi phụ: vé này đã có ai mua chưa?

Ô của tập con đủ 5 số chính là "số vé y hệt vé này". Nên kiểm tra trùng chỉ là đọc một ô: comboCounts[bonus][set].count > 0. Contract còn mở hàm view checkIfTicketsBought(drawingId, tickets) để app hỏi trước khi mua, miễn phí vì là hàm view. Biết điều này có ích vì vé trùng phải chia jackpot (Câu 7).

Câu 5: liệt kê 31 tập con trong Solidity thế nào?

Cách naive là viết cứng các vòng lặp lồng nhau: 2 vòng cho tập 2 số, 3 vòng cho tập 3 số, và cứ thế. Code dài, mỗi cỡ một đoạn riêng. Còn đệ quy thì tốn gas cho mỗi lần gọi hàm và dễ chạm giới hạn độ sâu stack của EVM.

Megapot dùng một hàm chung generateSubsets(set, k) cho mọi k, không đệ quy, bằng cách tách việc thành hai tầng.

1. Chọn vị trí bằng một số nhỏ 5 bit tên comb. Bit j bật nghĩa là "lấy số thứ j của vé". Các cách chọn đúng k số chính là các số 5 bit có đúng k bit 1.
2. Dịch vị trí sang số thật: đi qua các bit của vé, mỗi khi gặp một số của vé thì đọc một bit của comb để quyết định lấy hay bỏ.

Điểm bắt đầu là (1 << k) − 1, tức k bit 1 ở cuối (số nhỏ nhất có k bit 1). Điểm dừng là 1 << 5 = 32, vì vượt 5 bit là đã chọn tới "số thứ 6" mà vé không có. Bước nhảy là Gosper's hack: ba phép tính bit để đi thẳng tới số lớn hơn kế tiếp có cùng số bit 1, bỏ qua mọi số không hợp lệ ở giữa.

uint256 bound = 1 << n;             // n = popCount(set) = 5 → 32
uint256 comb = (1 << k) - 1;        // k = 2 → 0b00011
while (comb < bound) {
    // tầng 2: comb (vị trí) → mapped (bitmap số thật)
    for (uint256 i; i < 256 && _set != 0; ++i) {
        if (_set & 1 == 1) {                      // bit i là một số của vé
            if (_comb & 1 == 1) mapped |= (1 << i);
            _comb >>= 1;                           // sang vị trí kế
        }
        _set >>= 1;
    }
    subsets[count++] = mapped;
    // tầng 1: Gosper's hack
    uint256 c = comb & uint256(-int256(comb));   // bit 1 thấp nhất
    uint256 r = comb + c;                        // đẩy khối 1 thấp nhất lên
    comb = (((r ^ comb) >> 2) / c) | r;          // trả các bit 1 còn dư về đáy
}

Có một chỗ đáng lưu ý: comb không được lưu ở đâu cả. Nó chỉ là biến đếm tạm. Mảng subsets cũng nằm trong memory và mất khi giao dịch kết thúc. Thứ duy nhất được ghi lên chain là các ô comboCounts[bonus][mapped].

Câu 6: đọc bảng đếm xong, sao con số lại sai?

Khi có kết quả, contract lấy 31 tập con của bộ số trúng, đọc các ô tương ứng trong bảng đếm ở mọi cột bonus. Cột trùng bonus trúng được cộng vào các hạng "có bonus", các cột còn lại cộng vào hạng "không bonus". Với 10 bonus là 31 × 10 = 310 lần đọc.

Nhưng tổng đọc được bị đếm lặp. Một vé trúng 3 số, ví dụ {3, 11, 15}, chứa 3 cặp số của kết quả là {3,11}, {3,15}, {11,15}. Vì vậy khi cộng theo từng cặp, vé đó bị tính 3 lần ở hàng "2 số". Tổng quát: một vé trúng m số bị đếm C(m, k) lần ở hàng k số.

Cách gỡ là đi từ trên xuống. Hàng 5 số không bị lẫn gì nên đọc là ra. Hàng 4 số trừ đi phần vé 5 số đã bị đếm lẫn. Hàng 3 số trừ phần của vé 4 và 5 số, và cứ thế:

for (uint256 k = 5; k >= 1; --k) {                // từ hạng 5 số xuống
    uint256 s  = _matches[2*k];                   // tổng đọc từ bảng đếm, không bonus
    uint256 sp = _matches[2*k+1];                 // có bonus
    for (uint256 m = k + 1; m <= 5; ++m) {
        uint256 c = Combinations.choose(m, k);    // vé trúng m số chứa C(m,k) nhóm k số
        s  -= c * result[2*m];                    // result[2m] đã tính ở vòng trước
        sp -= c * result[2*m+1];
    }
    result[2*k] = s;  result[2*k+1] = sp;         // điền ngay để hàng dưới dùng
}

Hạng "chỉ trúng bonus" không có tập con 0 số nên tính riêng: lấy tổng vé có đúng bonus (bonusballTicketCounts), trừ đi các vé có bonus đã trúng thêm số thường.

Thử thêm vài nghìn dòng vé vào ô trên: số ô đọc lúc chốt vẫn là 310. Đó là toàn bộ ý nghĩa của thiết kế.

Câu 7: chia tiền thế nào khi không biết ai trúng?

Biết số vé mỗi hạng rồi, giờ phải biết mỗi vé được bao nhiêu tiền và trả cho ai.

Cách naive là kiểu chia đều truyền thống: lấy phần tiền của hạng, chia cho số người trúng thật, rồi lặp qua danh sách người trúng để chuyển tiền. Cách này gặp ba vấn đề:

• Lại cần danh sách người trúng và một vòng lặp chuyển tiền, đúng thứ Câu 1 đã loại.
• Chỉ cần một người nhận từ chối nhận tiền (ví dụ một contract cố tình revert) là cả giao dịch chốt kỳ hỏng.
• Giải mỗi người thay đổi theo số người cùng trúng, nên không ai biết trước giải đáng bao nhiêu.

Megapot làm khác ở hai điểm. Thứ nhất, lúc chốt chỉ tính và lưu mức thưởng mỗi hạng, người chơi tự đến claim sau (Câu 3), không có vòng lặp chuyển tiền. Thứ hai, và thú vị hơn, nằm ở mẫu số: GuaranteedMinimumPayoutCalculator không chia cho số người thật sự trúng. Nó chia cho tổng số tổ hợp có thể trúng hạng đó, dù có ai mua hay không, cộng thêm số vé mua trùng:

tierWinners[i] = _calculateTierTotalWinningCombos(k, 30, bonusballMax, coBonus) + _dupResult[i];
// có bonus:    C(5,k) × C(25, 5−k)
// không bonus: C(5,k) × C(25, 5−k) × (bonusballMax − 1)

premium    = remainingPool × weight[i] / tierWinners[i];
tierPayout = (minPayoutTiers[i] ? minPayout : 0) + premium;
totalPayout += tierPayout × (uniqueResult[i] + dupResult[i]);   // chỉ trả cho vé đã bán

Phần tiền ứng với tổ hợp không ai mua thì không trả cho ai, mà ở lại trong pool của LP. Từ một dòng mẫu số này kéo theo hai hệ quả quan trọng cho người chơi:

• Giải của bạn không giảm khi nhiều người khác cùng trúng hạng đó. Có 1 hay 500 người trúng "3 số + bonus" thì mỗi người vẫn nhận cùng một số tiền.
• Chỉ bị chia khi có người mua y hệt vé của bạn (dupCount). Điều này gần như chỉ có ý nghĩa ở jackpot. Vì vậy chọn số nào cũng không làm các hạng nhỏ đáng giá hơn.

Lưu ý là ở bước chốt kỳ, contract mới chỉ tính và lưu tierPayouts[kỳ][hạng]. Nó chưa chuyển tiền cho ai. Người chơi tự claim NFT vé sau đó, lúc ấy contract mới so riêng vé bằng AND + popCount như ở phần đầu, trả tiền và burn NFT để không claim được hai lần.

Câu 8: cái giá phải trả là gì?

Không có gì miễn phí. Thiết kế này đẩy chi phí sang chỗ khác, và có vài điểm yếu cần biết:

• Mua vé đắt gas hơn. Mỗi vé tốn khoảng 31 lần ghi storage, chưa kể mint NFT. Ghi vào ô mới tinh tốn khoảng 20 nghìn gas, ô đã có số tốn khoảng 5 nghìn gas. Trên Base thì vẫn rẻ, nhưng mua nhiều vé trong một giao dịch là đáng kể.
• Chi phí chốt tăng theo số cột bonus. Số lần đọc là 31 × bonusballMax, mà bonusballMax tăng khi pool lớn. Đây là gốc của lỗi H-02 trong audit: nếu bonusballMax lên quá cao thì callback hết gas và kỳ bị kẹt, đúng loại lỗi mà thiết kế muốn tránh.
• Một chút lãng phí trong code. Lúc chốt, generateSubsets được gọi lại bên trong vòng lặp bonus, nên 31 tập con bị tính lại 10 lần. Phần này chỉ tốn tính toán trong memory, rẻ hơn nhiều so với đọc storage, nhưng có thể đưa ra ngoài vòng lặp.

Nhìn lại: bài toán, cách naive, cách Megapot

Mang về dùng được gì

Bỏ chuyện xổ số sang một bên, đây là những mẫu thiết kế áp dụng được cho contract khác:

Nguồn

• Repo audit: code-423n4/2025-11-megapot, các file contracts/lib/TicketComboTracker.sol, contracts/lib/Combinations.sol, contracts/Jackpot.sol, contracts/GuaranteedMinimumPayoutCalculator.sol.
• Bài trước trong loạt này: Máy quay số Megapot (cách Pyth Entropy tạo số ngẫu nhiên).