the idea of this issue is to implement radix, step 2 of the 4-step lower-bound ladder for the privacy metric
(brute force → radix → sparse convolution → sasamoto)
all paths coexisting in PrivacyBundle as independent metrics
a sub-transaction mapping is a partition of the transaction into groups where each group has matching input and output sums; the more such valid partitions exist, the higher the ambiguity, and the higher the privacy. Counting them reduces to subset-sum: enumerating output subsets whose sums match input subset sums. General subset-sum is NP-hard, so the cost function needs bounds that are cheap to compute
the radix path applies when outputs decompose into standard denominations, three Hamming-weight-1 series in complementary bases:
{2^k} (powers of 2: 1, 2, 4, 8, 16, …), {1,2}·3^k (1, 2, 3, 6, 9, 18, …), and {1,2,5}·10^k(1, 2, 5, 10, 20, 50, …, the fiat banknote shape). Bases 2 and 3 are complementary, high Hamming weight in one usually means low weight in the other, and each series is a geometric progression with non-trivial multiplicity, so the resulting subset-sum instances are dense by construction
the count per output is k × m!, where:
k : number of distinct standard denominations whose sum equals the output value
m: minimum multiplicity, across the transaction outputs, of the denominations used in that decomposition
this counts mappings produced by an exchange between a k-sized subset and a single-output subset of equal value: k is the linear orientation choice, m! permutes the m identical copies of each denomination across sub-transactions. Outputs that cannot decompose into ≤ max_size denominations (default 6) contribute 0. The total is a lower bound on consistent mappings; returned as u128 with saturation
3 PRs implement proposal:
1 (radix-primitives): mapping count primitives, factorial, radix_mapping_count, STANDARD_DENOMS + range helpers (standard_denoms_in_range, powers_in_range...), radix_decompose (DFS with backtracking), and radix_mappings(outputs, max_size) -> u128
2 (radix-sumsets): param consts, sumset, gap, density, and approximate_from_below analytical tooling
3 (radix-wire): RadixMetric into PrivacyBundle , consuming crate::radix::radix_mappings
add proptest dep to btsim/Cargo.toml, to verify algebraic properties (factorial recurrence, monotonicity, decomposition correctness) across random inputs to catch corner cases unit tests miss
other count paths (brute force already exists; sparse convolution and sasamoto) are out of scope here.
ref:
makes sense?
the idea of this issue is to implement radix, step 2 of the 4-step lower-bound ladder for the privacy metric
(brute force → radix → sparse convolution → sasamoto)
all paths coexisting in
PrivacyBundleas independent metricsa sub-transaction mapping is a partition of the transaction into groups where each group has matching input and output sums; the more such valid partitions exist, the higher the ambiguity, and the higher the privacy. Counting them reduces to subset-sum: enumerating output subsets whose sums match input subset sums. General subset-sum is NP-hard, so the cost function needs bounds that are cheap to compute
the radix path applies when outputs decompose into standard denominations, three Hamming-weight-1 series in complementary bases:
{2^k}(powers of 2: 1, 2, 4, 8, 16, …),{1,2}·3^k(1, 2, 3, 6, 9, 18, …), and{1,2,5}·10^k(1, 2, 5, 10, 20, 50, …, the fiat banknote shape). Bases 2 and 3 are complementary, high Hamming weight in one usually means low weight in the other, and each series is a geometric progression with non-trivial multiplicity, so the resulting subset-sum instances are dense by constructionthe count per output is
k × m!, where:k: number of distinct standard denominations whose sum equals the output valuem: minimum multiplicity, across the transaction outputs, of the denominations used in that decompositionthis counts mappings produced by an exchange between a k-sized subset and a single-output subset of equal value:
kis the linear orientation choice,m!permutes themidentical copies of each denomination across sub-transactions. Outputs that cannot decompose into≤ max_sizedenominations (default 6) contribute 0. The total is a lower bound on consistent mappings; returned asu128with saturation3 PRs implement proposal:
1 (radix-primitives): mapping count primitives,
factorial,radix_mapping_count,STANDARD_DENOMS+ range helpers (standard_denoms_in_range,powers_in_range...),radix_decompose(DFS with backtracking), andradix_mappings(outputs, max_size) -> u1282 (radix-sumsets): param consts,
sumset,gap,density, andapproximate_from_belowanalytical tooling3 (radix-wire):
RadixMetricintoPrivacyBundle, consumingcrate::radix::radix_mappingsadd
proptestdep tobtsim/Cargo.toml, to verify algebraic properties (factorial recurrence, monotonicity, decomposition correctness) across random inputs to catch corner cases unit tests missother count paths (brute force already exists; sparse convolution and sasamoto) are out of scope here.
ref:
makes sense?