Activity Overview

Commits and releases over time

  • Commits
  • Releases
  • Authors

Repository Explorer

45 commits in all time Jun 29, 2026 05:47 – Sep 27, 2026 05:47 UTC
jannotti sortition
Merge pull request #10 from algorand/sortition-update-freeze
SelectF128: update frozen CDF index behavior
Git Commit e7002813 Branch main Document 8/301 ++ 104 --
cce sortition
return j instead of dist.at
Git Commit 29900eaa Branch main Document 3/14 ++ 15 --
cce sortition
more comments for newBinomialF128
Git Commit 4e3ecc80 Branch main Document 1/15 ++ 1 --
cce sortition
tests: strengthen frozen-boundary promotion coverage
Git Commit 51b5c443 Branch main Document 6/98 ++ 20 --
cce sortition
SelectF128: promote the frozen CDF boundary
Return the first permanently frozen CDF index instead of falling through to the account's stake. Mirror the policy in the same-precision oracle and pin current committee-scale outputs against high-precision and Boost references.
Git Commit 2b47f885 Branch main Document 8/202 ++ 96 --
cce sortition
fix comments
Git Commit b953c657 Branch sortition-plateau Document 1/12 ++ 7 --
cce sortition
SelectF128: export max weight factor, pin the frozen-tail weight gap
Git Commit 9699de3a Branch sortition-plateau Document 3/120 ++ 0 --
cce sortition
Merge pull request #8 from algorand/sortition-f128
Add SelectF128 sortition implementation
Git Commit d1d6e8e4 Branch main Document 22/3,951 ++ 7 --
cce sortition
CI: add cancel-in-progress: true
Git Commit 26c0c59b Branch main Document 1/4 ++ 0 --
cce sortition
ci: add emulated linux/arm/v7 leg (Raspberry Pi target)
armv7 (GOARM=7) has the same 32-bit int as 386 but on real ARM hardware like the Raspberry Pi. It has no native path on the amd64 runner, so it runs under QEMU via a foreign-arch container; the stock golang image carries gcc/g++ and Boost is vendored, so no extra install is needed. Emulated and thus the slowest leg, so it runs only the default rapid depth.
Git Commit 51f9204a Branch main Document 1/22 ++ 0 --
cce sortition
ci: add native linux/386 leg to exercise 32-bit int
Go's int is 32-bit on GOARCH=386, the platform width that motivates the explicitly-int64 f128 exponent. x86-64 runs i386 user code natively, so this validates cross-GOARCH bit-identity with no QEMU; gcc/g++-multilib supplies the 32-bit toolchain for the cgo/Boost build (Go adds -m32 automatically).
Git Commit 193a7f93 Branch main Document 1/34 ++ 0 --
cce sortition
CI: use original job name
Git Commit 5c069200 Branch main Document 1/1 ++ 1 --
cce sortition
fix CI and update copyright
Git Commit 357a49cf Branch main Document 14/29 ++ 12 --
cce sortition
test: harden f128 oracle and liveness coverage
Add exact, multiprecision, trajectory, metamorphic, and mutation checks for the f128 CDF walk.

Schedule certified Arb corpus verification and document the testing layers and developer commands in TESTING.md.
Git Commit 288b2700 Branch main Document 11/922 ++ 31 --
cce sortition
test: add independent f128 and CDF oracles
Add exact-integer primitive checks, an exhaustive small-domain boundary grid, and offline Arb-certified large-money quantile vectors.

Include the new tests in the curated mutation campaign and pin the optional oracle dependency.
Git Commit 237ce643 Branch main Document 8/936 ++ 1 --
cce sortition
fix args in windows CI
Git Commit b7835fb3 Branch main Document 1/1 ++ 1 --
cce sortition
go version for actions
Git Commit f3f87090 Branch main Document 1/4 ++ 0 --
cce sortition
bump actions versions
Git Commit 003ae1ba Branch main Document 1/4 ++ 7 --
cce sortition
scale the straddle step to the boundary's own ulp
TestSelectF128BoundaryStraddle stepped candidate digests by a fixed 2^128 digest units, which is one f128 ratio ulp only for boundaries in [0.5, 1); for small boundaries (a large-mean cdf(0) can sit at 2^-2000) the candidates landed many ulps away, diluting the straddle into ordinary sampling. Derive the step from the boundary's MantExp (2^(exp-128) in digest units, clamped to one digest unit when the ulp is finer than the digest grid), and assert the candidate window genuinely brackets the boundary whenever no candidate was clamped at the digest range's ends.
Git Commit d5f8c1e2 Branch main Document 1/26 ++ 2 --
cce sortition
run the mutation campaign in CI
A separate single-platform job runs go run mutation_check.go on every push: a weakened test lets a mutant survive and a semantic change to the arithmetic kills a proven-equivalent mutant or orphans a target string, so the kill-rate claim stays continuously verified instead of decaying into a stale number. The mutant table is deliberately coupled to the exact arithmetic lines it guards; editing those lines requires updating the table. Also drop an out-of-repo doc path from the tool header.
Git Commit 43b0ab09 Branch main Document 2/36 ++ 4 --
cce sortition
mutation_check: suppress rapid failfiles from killed mutants
Killed mutants fail the rapid tests by design, and each failure wrote a minimized reproducer under testdata/rapid that would then rerun as a stale regression case against the restored code. Pass -rapid.nofailfile in the kill suite.
Git Commit 8552735b Branch main Document 1/3 ++ 0 --
cce sortition
add an independent-formula exact oracle and a distribution test
The differential oracle shares the PMF recurrence with the implementation, so a shared algebra error would pass every differential test. selectExactRat computes the walk against the exact binomial CDF from first principles: stdlib big.Int.Binomial coefficients and pure integer cross-multiplication (t * T^money <= cdfNum(j) * (2^256-1)) -- no recurrence, no rounding, no floating point. TestSelectF128VsExactRat requires agreement within one boundary for money <= 50, over random inputs, near-maximum digests, and digests constructed to sit exactly on true CDF boundaries.

TestSelectF128Distribution mirrors TestSortitionBasic (which covers only the cgo path) for SelectF128 at toy and realistic stake scales with a fixed seed: summed selection weight must track N * money * p within 2%. Oracle-free and formula-free, so a gross semantic error fails it even if perfectly mirrored everywhere else. Both tests join the mutation campaign's kill suite via the TestSelectF128 pattern; the campaign still reports 33 mutants, 28 killed, 5 proven-equivalent, 0 unexpected.
Git Commit 24e95015 Branch main Document 1/128 ++ 0 --
cce sortition
add 512-bit tolerance oracle, knife-edge tests, and a mutation campaign
Three assurance layers beyond differential-vs-oracle testing, which is structurally blind to defects mirrored into the oracle (see docs/2026-07-21-sortition-f128-testing-blind-spots.md in the go-algorand docs area). TestSelectF128NearExactMath compares the walk against a 512-bit reference with the near-exact digest ratio and requires agreement within one boundary everywhere outside the defined frozen sliver, including supply-scale spot cases that nothing previously checked against any reference; the spots carry a mustAssert flag so a carve-out change can never silently skip them (an early version of the sliver bound misused big.Float SetMantExp, which multiplies rather than sets the exponent, and the spots passed vacuously until the flag caught it). TestSelectF128BoundaryStraddle constructs digests one ratio-ulp below, at, and above oracle CDF boundaries and requires bit-level agreement plus monotone transitions exactly where knife-edge bugs live. TestRapidSelectF128ScaleInvariance requires bit-identical results under power-of-two scaling of totalMoney and expectedSize, an exact oracle-free metamorphic property.

mutation_check.go (go run mutation_check.go) applies 33 curated single-site mutants to f128.go and requires the fast suite to kill each: 28 killed, 5 survive as proven-equivalent with the proof recorded in the table (among them: div cannot produce exact ties, the halfway correction makes n0's sticky redundant, and the refine loop's strictness is immaterial on exact digits). The campaign found two real gaps, both fixed here: no test broke a mul hi-branch tie through p0 alone (new constructed seeds for mul, add gap-128, divU remainder-only sticky, and a halfway-plus-low-bit digest family), and norm128 -- now used only as the harnesses' input constructor -- could corrupt values invisibly because the reference was derived downstream of it (the fuzz body now checks it against the raw words).
Git Commit 118d53fe Branch main Document 4/399 ++ 0 --
cce sortition
pin the defensive primitive arms with direct unit tests
Full-suite coverage showed shl128's n==0 and n>=128 arms, shr128's n>=128 arm, f128FromUint64(0), and cmp's zero-operand arms as unreachable: norm128 only shifts by 1..127 and CDF boundaries are never zero, so neither the walk nor any differential harness can exercise them. They are total functions with defined answers, so TestF128PrimitiveEdges asserts them by direct call, turning untested defensive code into tested semantics. f128.go coverage is now 100% minus one branch: divStep's add-back, which is unreachable under any inputs (the fixpoint-refinement argument does not even need divStep's preconditions) and stays documented rather than covered. Package coverage: 98.1%.
Git Commit 4008e65c Branch main Document 1/35 ++ 0 --
cce sortition
seed the fuzz blind spots, band the rapid generators, add a monotonicity property
Go's mutator explores integers locally around corpus values, so every input regime needs a seed planted in it. Coverage of f128.go from the seed corpus alone had 31 uncovered blocks; this brings it to 6, all provably-unreachable defensive arms. New FuzzF128Ops seeds: constructed exact-tie vectors for mul (both tie directions), an add tie at exponent gap 128 into an all-ones mantissa (exercising carry-out renormalization), gap 129 (addend fully below the round bit), constructed divStep qhat-cap vectors (plain and rhat-carry), a mined refine-decrement-overflow vector, denormalized mantissas, and a zero operand. New FuzzSelectF128 seeds: an exact-halfway digest (the denominator-correction branch, ~2^-128 density), small digests reaching each normalization word, fall-through-to-money via both the full walk (p=1/2) and the freeze short-circuit (tiny p), p just below 1 (deep exponents), extreme total/expected magnitudes, and totalMoney == 0. All tie/carry/divStep vectors were constructed or mined by an instrumented search and are verified against big.Float by the fuzz bodies themselves on every go test run.

The one uncovered branch worth a comment instead of a seed: divStep's add-back is believed unreachable -- the refine loop runs to fixpoint with an exact 128-bit test (equivalent to U - qhat*V >= 0), unlike Knuth's Algorithm D, which bounds the D3 adjustment and needs D6; a 3M-case instrumented search never fired it. Documented at the branch.

The rapid tests gain structure-banded mantissa generation (uniform/sparse/dense, raising tie and carry densities from ~2^-64), banded exponent gaps around add's 64/127/128/129 alignment boundaries, oracle-independent mul/add commutativity checks, and TestRapidSelectF128DigestMonotonic: the selection count is non-decreasing in the digest, an exact property of the walk that needs no oracle. That narrows, but does not close, the differential tests' structural blind spot: a defect mirrored into the oracle now cannot violate ordering unnoticed, but an order-preserving one (like the pmf(0) plateau, where the stuck band returns the maximal count) would still pass; that class is covered by the dedicated frozen-tail pins instead.

CI runs the rapid tests at -rapid.checks=20000 in a separate workflow step: deep enough to sample every generator band reliably (the divU shallow-quotient bug reproduced within ~30 banded cases), ~1.3s on a laptop.
Git Commit c190cfa7 Branch main Document 4/143 ++ 6 --