blockchainkit.privacy #

class blockchainkit.privacy.systems.mixnets.MixNode(name, secret, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Bases: object

A mix (or an onion router): a named key pair that removes one layer at a time.

Parameters:

name (str) – The address other nodes send to.
secret (int) – Its private key, in [1, q).
group (blockchainkit.crypto.systems.asymmetric.DHGroup) – The group of the keys.

open(sealed)[source]#

Remove the encryption of seal().

Raises:: ValueError – The announced key is not in the group: the message was not sealed for any key.
Parameters:: sealed (bytes)
Return type:: bytes

peel(onion)[source]#

Remove one layer and return (next hop, what to send it).

Parameters:: onion (bytes)
Return type:: tuple[str, bytes]

blockchainkit.privacy.systems.mixnets.wrap(message, route, recipient, rng, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Wrap message for recipient in one layer per node of route, innermost last.

Only the nodes’ names and public keys are used, as a sender would know them.

Examples

>>> from random import Random
>>> from blockchainkit.privacy import MixNode, wrap
>>> route = [MixNode("m1", 11), MixNode("m2", 22)]
>>> onion = wrap(b"hello", route, "bob", Random(0))
>>> hop, inner = route[0].peel(onion)
>>> hop, route[1].peel(inner)
('m2', ('bob', b'hello'))

Parameters:

message (bytes)
route (Sequence[MixNode])
recipient (str)
rng (Random)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.mixnets.mix_cascade(onions, mixes, *, seed=0)[source]#

Send a batch of onions through a cascade of mixes, each shuffling its output.

Every onion must be wrapped for exactly this cascade.

Raises:

ValueError – An onion’s next hop is not the next mix of the cascade.

Parameters:

onions (Sequence[bytes])
mixes (Sequence[MixNode])
seed (int)

Return type:

MixRun

Onion routing in Tor: low-latency anonymity and its end-to-end weakness (2004).

Tor wraps traffic in layers as a mix-net does, through a circuit of three relays: an entry guard, a middle relay and an exit. Each relay learns only its neighbours on the circuit. Unlike a mix, a relay forwards each packet at once, without batching or reordering, so web browsing stays fast. The price, which Dingledine, Mathewson and Syverson state in the design, is that an adversary watching both the entry and the exit of a circuit can match the timing of what goes in to what comes out. If it runs a fraction f of the relays, about f**2 of circuits are exposed.

The circuit itself reuses wrap(); real Tor builds circuits by telescoping Diffie-Hellman handshakes and then sends fixed 512-byte cells under symmetric keys.

blockchainkit.privacy.systems.onion.circuit_compromise_rate(relays, malicious, circuits, *, seed=0)[source]#

Fraction of random three-relay circuits whose entry and exit are both malicious.

Each circuit picks three distinct relays uniformly; real Tor weights the choice by bandwidth and keeps the same entry guard for months.

>>> from blockchainkit.privacy import circuit_compromise_rate
>>> circuit_compromise_rate(10, set(), 100)
0.0

Parameters:

relays (int)
malicious (Collection[int])
circuits (int)
seed (int)

Return type:

float

blockchainkit.privacy.systems.onion.simulate_flows(flows, packets, *, latency=0.2, jitter=0.01, seed=0)[source]#

Packet times of concurrent flows at their entry and at their exit.

Each flow sends packets packets with exponential gaps of mean 1. The network delays every packet by latency plus Gaussian jitter, and the exit side sees the flows in a shuffled order.

Parameters:

flows (int)
packets (int)
latency (float)
jitter (float)
seed (int)

Return type:

FlowObservation

blockchainkit.privacy.systems.onion.match_flows(entering, leaving)[source]#

Match each entering flow to the leaving flow with the most similar packet gaps.

The end-to-end timing attack: delay shifts every packet alike, so the gaps between packets survive the trip. Distance is the sum of absolute differences of the gaps.

Parameters:

entering (Sequence[Sequence[float]])
leaving (Sequence[Sequence[float]])

Return type:

tuple[int, …]

k-anonymity and anonymity sets: how many people a record could belong to (2002).

Sweeney showed that a ZIP code, a birth date and a sex, released without names, still single out most Americans: joined with a voter list, they named the Governor of Massachusetts in “anonymous” hospital records. A table is k-anonymous if every combination of those quasi-identifiers is shared by at least k rows, so each person hides among k.

The same year, Serjantov and Danezis, and Díaz, Seys, Claessens and Preneel, measured anonymity on networks the same way: by the anonymity set of possible senders. Counting the set overstates it when an attacker finds some members likelier than others, so they weighted it by the Shannon entropy of the attacker’s guess: \(2^{H}\) equally likely senders give the same uncertainty.

blockchainkit.privacy.systems.anonymity.equivalence_classes(rows, quasi_identifiers)[source]#

Count the rows sharing each combination of the quasi-identifiers.

>>> from blockchainkit.privacy import equivalence_classes
>>> rows = [{"zip": "021*", "sex": "F"}] * 2 + [{"zip": "022*", "sex": "M"}]
>>> equivalence_classes(rows, ["zip", "sex"])
{('021*', 'F'): 2, ('022*', 'M'): 1}

Parameters:

rows (Iterable[Mapping[str, Hashable]])
quasi_identifiers (Sequence[str])

Return type:

dict[tuple[Hashable, …], int]

blockchainkit.privacy.systems.anonymity.k_anonymity(rows, quasi_identifiers)[source]#

The k of a table: the size of its smallest equivalence class.

Raises:

ValueError – The table is empty.

Parameters:

rows (Iterable[Mapping[str, Hashable]])
quasi_identifiers (Sequence[str])

Return type:

blockchainkit.privacy.systems.anonymity.entropy_bits(probabilities)[source]#

Shannon entropy, in bits, of an attacker’s probabilities over the possible senders.

Raises:: ValueError – A probability is negative, or they do not add up to 1.
Parameters:: probabilities (Iterable[float])
Return type:: float

blockchainkit.privacy.systems.anonymity.effective_anonymity_set(probabilities)[source]#

2**H: the number of equally likely senders that leave the same uncertainty.

>>> from blockchainkit.privacy import effective_anonymity_set
>>> effective_anonymity_set([0.25] * 4)
4.0
>>> round(effective_anonymity_set([0.7, 0.1, 0.1, 0.1]), 2)
2.56

Parameters:: probabilities (Iterable[float])
Return type:: float

Ring signatures and stealth addresses#

Ring signatures: signing for a group chosen on the spot (Rivest, Shamir and Tauman, 2001).

A ring signature convinces anyone that one of the listed public keys signed, without revealing which. Unlike a group signature there is no manager and no setup: the signer picks the other members’ public keys itself, and they need not know. The signature is a closed ring of challenges: each member’s challenge is the hash of the previous member’s commitment, and the signer’s secret key is what lets it close the ring.

For keys \(y_i = g^{x_i}\) and signer \(s\), the signer picks \(u\) and starts the ring at \(c_{s+1} = H(m, g^u)\); every other member gets a random response \(r_i\) and \(c_{i+1} = H(m, g^{r_i} y_i^{c_i})\). Only the signer can then answer \(r_s = u - x_s c_s\), which makes \(g^{r_s} y_s^{c_s} = g^u\).

This is the discrete-log construction of Abe, Ohkubo and Suzuki (2002), which Monero’s signatures descend from. Rivest, Shamir and Tauman built their ring from RSA trapdoor permutations and a symmetric cipher.

blockchainkit.privacy.systems.ring_signatures.ring_sign(message, ring, index, secret, *, seed=0, base=None, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Sign message as one of ring, using the secret key of member index.

Parameters:

message (bytes) – What is signed.
ring (collections.abc.Sequence of int) – Public keys base**x_i, the signer’s among them.
index (int) – The signer’s position in the ring.
secret (int) – The signer’s private key.
seed (int) – Seeds the nonce and the other members’ responses.
base (int, optional) – The generator of the keys; group.g by default.
group (blockchainkit.crypto.systems.asymmetric.DHGroup) – The group of the keys.

Raises:

ValueError – secret is not the private key of member index.

Return type:

RingSignature

Examples

>>> from blockchainkit.privacy import ring_sign, ring_verify
>>> from blockchainkit.crypto import TEACHING_GROUP as G
>>> ring = [G.public(x) for x in (11, 22, 33)]
>>> ring_verify(b"hi", ring, ring_sign(b"hi", ring, 1, 22))
True

blockchainkit.privacy.systems.ring_signatures.ring_verify(message, ring, signature, *, base=None, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check that one member of ring signed message: the challenges close the ring.

Parameters:

message (bytes)
ring (Sequence[int])
signature (RingSignature)
base (int | None)
group (DHGroup)

Return type:

Linkable ring signatures and key images: anonymous, but only once (Liu, Wei and Wong, 2004).

A ring signature hides the spender, so on its own it would let a coin be spent twice: two signatures by the same key look unrelated. A linkable ring signature adds a key image \(I = H_p(P)^x\), a value fixed by the signer’s key \(P = g^x\) but not revealing it. Every signature by that key carries the same image, so the ledger rejects the second spend, yet nobody learns which ring member made either one.

The ring proves both statements with the same response, for each member \(i\) with challenge \(c_i\) and response \(r_i\):

\[L_i = g^{r_i} P_i^{c_i}, \qquad R_i = H_p(P_i)^{r_i} I^{c_i}, \qquad c_{i+1} = H(m, L_i, R_i).\]

Only the signer can close the ring with a single \(x\) that serves both. MLSAG (Noether, 2016) signs with one key per column for each member at once, the same challenge chaining them; RingCT uses a second column to prove amounts balance.

The key image here hashes the public key, as CryptoNote does, so it links signatures across different rings; Liu, Wei and Wong hashed the ring, which links only signatures over the same ring.

blockchainkit.privacy.systems.linkable.key_image(secret, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

H_p(P)**x for the key pair (x, P = g**x).

>>> from blockchainkit.privacy import key_image
>>> key_image(5) == key_image(5) != key_image(6)
True

Parameters:

secret (int)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.linkable.mlsag_sign(message, ring, index, secrets, *, seed=0, bases=None, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Sign as member index of a ring whose members each hold one key per column.

Parameters:

message (bytes) – What is signed.
ring (collections.abc.Sequence of collections.abc.Sequence of int) – ring[i][j] is member i’s public key in column j.
index (int) – The signer’s position.
secrets (collections.abc.Sequence of int) – The signer’s private keys, one per column.
seed (int) – Seeds the nonces and the other members’ responses.
bases (collections.abc.Sequence of int, optional) – The generator of each column; group.g for all by default. The key image is always taken in the first column.
group (blockchainkit.crypto.systems.asymmetric.DHGroup) – The group of the keys.

Raises:

ValueError – A secret does not match the signer’s key in its column.

Return type:

LinkableRingSignature

blockchainkit.privacy.systems.linkable.mlsag_verify(message, ring, signature, *, bases=None, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check a signature from mlsag_sign(): the challenges close the ring.

Parameters:

message (bytes)
ring (Sequence[Sequence[int]])
signature (LinkableRingSignature)
bases (Sequence[int] | None)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.linkable.lsag_sign(message, ring, index, secret, *, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

A linkable ring signature with one key per member: mlsag_sign() with one column.

Examples

>>> from blockchainkit.privacy import key_image, lsag_sign, lsag_verify
>>> from blockchainkit.crypto import TEACHING_GROUP as G
>>> ring = [G.public(x) for x in (11, 22, 33)]
>>> signature = lsag_sign(b"spend", ring, 2, 33)
>>> lsag_verify(b"spend", ring, signature), signature.key_image == key_image(33)
(True, True)

Parameters:

message (bytes)
ring (Sequence[int])
index (int)
secret (int)
seed (int)
group (DHGroup)

Return type:

LinkableRingSignature

blockchainkit.privacy.systems.linkable.lsag_verify(message, ring, signature, *, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check a signature from lsag_sign().

Parameters:

message (bytes)
ring (Sequence[int])
signature (LinkableRingSignature)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.linkable.linked(first, second)[source]#

Whether two signatures were made with the same key: their key images are equal.

Parameters:

first (LinkableRingSignature)
second (LinkableRingSignature)

Return type:

Stealth addresses: one published address, a fresh key for every payment (CryptoNote, 2013).

Reusing an address links every payment to it; asking each payer for a new one needs a conversation. CryptoNote, the protocol behind Monero, lets the payer derive a fresh one-time key from a single published address \((A, B) = (g^a, g^b)\). The payer picks \(r\), publishes \(R = g^r\) with the transaction, and pays to

\[P = g^{H(A^r)} B .\]

Only the payee can recognise it, since \(A^r = R^a\) needs either \(r\) or \(a\), and only the payee can spend it, with the key \(x = H(R^a) + b\). The view key \(a\) alone finds incoming payments without being able to spend them, so it can be handed to an auditor. To everyone else, the outputs paid to one address look unrelated.

CryptoNote hashes the output’s index in the transaction along with \(R^a\); here the index is an argument, 0 by default.

blockchainkit.privacy.systems.stealth.stealth_keys(view_secret, spend_secret, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

A wallet’s view and spend key pairs; the two public keys form its address.

>>> from blockchainkit.privacy import stealth_keys
>>> keys = stealth_keys(5, 7)
>>> keys.view_public != keys.spend_public
True

Parameters:

view_secret (int)
spend_secret (int)
group (DHGroup)

Return type:

StealthKeys

blockchainkit.privacy.systems.stealth.stealth_payment(view_public, spend_public, ephemeral, *, index=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Pay the address (A, B) at a one-time key, using the payer’s secret r.

Examples

>>> from blockchainkit.privacy import owns_output, stealth_keys, stealth_payment
>>> bob = stealth_keys(5, 7)
>>> output = stealth_payment(bob.view_public, bob.spend_public, ephemeral=1234)
>>> owns_output(output, bob.view_secret, bob.spend_public)
True

Parameters:

view_public (int)
spend_public (int)
ephemeral (int)
index (int)
group (DHGroup)

Return type:

StealthOutput

blockchainkit.privacy.systems.stealth.owns_output(output, view_secret, spend_public, *, index=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Whether output pays the wallet: the scan that needs only the view key.

Parameters:

output (StealthOutput)
view_secret (int)
spend_public (int)
index (int)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.stealth.one_time_secret(output, view_secret, spend_secret, *, index=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

The private key x = H(R**a) + b that spends output.

Raises:

ValueError – The output does not pay this wallet.

Parameters:

output (StealthOutput)
view_secret (int)
spend_secret (int)
index (int)
group (DHGroup)

Return type:

Tracing a ledger#

Address clustering: grouping a ledger’s addresses by owner (Meiklejohn et al., 2013).

Bitcoin users hide behind fresh addresses, but how they spend gives them away. A Fistful of Bitcoins clustered addresses with two heuristics:

Common input ownership. A transaction’s inputs are signed by their owners together, so every input address of one transaction belongs to one user (Nakamoto noted it in the white paper).
One-time change. A wallet sends the change back to a fresh address. If exactly one output address of a transaction has never appeared before, and no input address reappears among the outputs, that output is the change and belongs to the sender too.

Labelling a few clusters, by buying from a service or depositing at an exchange, then names every address in them.

simulate_payments() makes a toy economy with known owners; real wallets select coins and create change in many more ways, which is where the change heuristic makes its mistakes.

blockchainkit.privacy.systems.clustering.fresh_address(label)[source]#

A 16-hex-digit address derived from label, which an observer cannot read back.

Parameters:: label (str)
Return type:: str

blockchainkit.privacy.systems.clustering.simulate_payments(users, payments, *, coins=2, reuse=0.5, seed=0)[source]#

Simulate users paying each other, with the owner of every address recorded.

Every user starts with coins coins at fresh addresses. In each payment a random user pays a random share of its money to another, spending its largest coins first and sending the change to a fresh address. With probability reuse the payee is paid at an address it used before, as a shop or an exchange deposit address is.

Parameters:

users (int)
payments (int)
coins (int)
reuse (float)
seed (int)

Return type:

PaymentHistory

blockchainkit.privacy.systems.clustering.cluster_addresses(transactions, *, change=False)[source]#

Group addresses by common input ownership, and optionally by one-time change.

Returns the clusters, largest first.

>>> from blockchainkit.privacy import TransactionRecord, cluster_addresses
>>> tx = TransactionRecord((("a", 5), ("b", 5)), (("c", 10),))
>>> sorted(map(sorted, cluster_addresses([tx])))
[['a', 'b'], ['c']]

Parameters:

transactions (Iterable[TransactionRecord])
change (bool)

Return type:

tuple[frozenset[str], …]

blockchainkit.privacy.systems.clustering.score_clusters(clusters, owners)[source]#

Compare clusters with the true owners of their addresses.

Raises:

KeyError – A clustered address has no known owner.

Parameters:

clusters (Iterable[frozenset[str]])
owners (dict[str, str])

Return type:

ClusterScore

Traceability in Monero: how decoys fail (Möser et al.; Kumar et al., 2018).

A Monero input hides its real output among decoys (mixins) drawn from earlier outputs. Two studies in 2017-2018 found that, in practice, most inputs up to 2017 could be traced:

Zero-mixin chain reaction. Until 2016 Monero allowed rings with no decoys. Such an input reveals the output it spends; that output can then be struck from every other ring that uses it as a decoy, which may leave some of those rings with one member, and so on. Möser et al. could deduce the real output of most inputs made before 2017 this way.
Guess-newest. People tend to spend coins soon after receiving them, but decoys were drawn uniformly from all past outputs, so most of them were old. The newest member of a ring was the real one about 80% of the time.

Monero’s fixes were a minimum ring size (2016, raised to 11 in 2018) and drawing decoys from a distribution fitted to real spending ages. In simulate_rings() an output’s index is its age order, and real spends and "recent" decoys share one geometric age distribution.

blockchainkit.privacy.systems.traceability.SAMPLINGS = ('uniform', 'recent')#

How simulate_rings() draws decoys.

Type:: tuple of str

blockchainkit.privacy.systems.traceability.simulate_rings(outputs, inputs, *, ring_size=5, zero_mixin=0.0, sampling='uniform', mean_age=20.0, seed=0)[source]#

Simulate ring inputs over a ledger of outputs outputs created one after another.

Inputs are made at random heights after the first tenth of the outputs, and never so early that more than half the outputs are spent. Each spends a recent unspent output, chosen with a geometric age of mean mean_age. With probability zero_mixin its ring holds only that output; otherwise ring_size - 1 distinct decoys are added, drawn uniformly from all earlier outputs or with the same age distribution as real spends.

Parameters:

outputs (int)
inputs (int)
ring_size (int)
zero_mixin (float)
sampling (str)
mean_age (float)
seed (int)

Return type:

tuple[RingInput, …]

blockchainkit.privacy.systems.traceability.chain_reaction(rings)[source]#

Deduce real spends: {ring index: output} for every ring left with one possible member.

Repeatedly removes, from every other ring, the outputs already known to be spent by a deduced ring.

Parameters:: rings (Sequence[RingInput])
Return type:: dict[int, int]

blockchainkit.privacy.systems.traceability.guess_newest(rings)[source]#

Guess that each ring spends its newest member.

Parameters:: rings (Iterable[RingInput])
Return type:: tuple[int, …]

blockchainkit.privacy.systems.traceability.trace_rings(rings)[source]#

Measure how much of a ledger’s ring inputs the two heuristics trace.

>>> from blockchainkit.privacy import simulate_rings, trace_rings
>>> report = trace_rings(simulate_rings(1_000, 100, zero_mixin=1.0))
>>> report.deduced == report.rings == 100
True

Parameters:: rings (Sequence[RingInput])
Return type:: TraceReport

Mixing coins#

CoinJoin: many payers in one transaction, so its inputs need not share an owner (2013).

Gregory Maxwell pointed out on the Bitcoin forum that nothing requires a transaction’s inputs to belong to one person. Several users can each contribute an input and name an output, check the joint transaction, and sign only their own input. If every mixed output pays the same denomination, an observer cannot tell whose output is whose: for \(n\) such outputs each user hides among \(n\), and the common input ownership heuristic, applied to the transaction, merges strangers.

The change outputs are another matter. Each one is an input amount minus the denomination, which usually links it to its input, so only the equal-valued outputs are anonymous.

coinjoin() builds the transaction without fees or signatures; real rounds (JoinMarket, Wasabi, Whirlpool) coordinate through a server or a market and use blinded registrations so the coordinator cannot link inputs to outputs either.

blockchainkit.privacy.systems.coinjoin.coinjoin(participants, denomination, *, seed=0)[source]#

Join each participant’s (user, input address, amount) into one transaction.

Each gets an output of denomination at a fresh address and, if its input is larger, its change at another; the outputs are shuffled.

Raises:

ValueError – An input is smaller than the denomination, or a user joins twice.

Parameters:

participants (Sequence[tuple[str, str, int]])
denomination (int)
seed (int)

Return type:

CoinJoinRound

Examples

>>> from blockchainkit.privacy import coinjoin
>>> round_ = coinjoin([("ann", "a1", 10), ("bob", "b1", 13), ("cat", "c1", 10)], 10)
>>> round_.anonymity_set, round_.transaction.fee
(3, 0)

blockchainkit.privacy.systems.coinjoin.link_change(transaction, denomination)[source]#

Link each change output to the one input whose amount is the change plus the denomination.

Outputs of exactly the denomination are left out; so is any change that two or more inputs could have produced.

Parameters:

transaction (TransactionRecord)
denomination (int)

Return type:

dict[str, str]

TumbleBit: an untrusted payment hub that cannot link payers to payees (Heilman et al., 2017).

A tumbler mixes coins by receiving from payers and paying payees. A centralised mixer can steal and can see who paid whom. TumbleBit removes both risks with RSA puzzles. For each payee the tumbler issues a promise: a puzzle \(z = \\epsilon^{e} \bmod N\) and its payment token encrypted under \(\\epsilon\). Only the tumbler, with its RSA secret, can solve the puzzle. The payee blinds the puzzle,

\[\begin{split}z' = z \\cdot \rho^{e} \bmod N ,\end{split}\]

and gives \(z'\) to a payer, who pays the tumbler to solve it. The tumbler returns \(\\epsilon \rho\), the payer passes it on, and the payee divides by \(\rho\) to get \(\\epsilon\) and open its token. The tumbler saw \(z\) with the payee and \(z'\) with the payer, which are unrelated numbers to it: the same blinding as Chaum’s blind signatures.

TumbleBit makes each step a fair exchange on chain, with hash-locked escrows and cut-and-choose, so the tumbler cannot take a payment without solving the puzzle or promise a token it does not deliver. This model keeps only the puzzles and blinding, and the token is a byte string.

blockchainkit.privacy.systems.tumblebit.TUMBLER_KEY = RSAKeyPair(n=4613833553625995599, e=65537, d=3802750095375296513)#

A 62-bit textbook RSA key for the tumbler’s puzzles.

Type:: RSAKeyPair

class blockchainkit.privacy.systems.tumblebit.Tumbler(key=RSAKeyPair(n=4613833553625995599, e=65537, d=3802750095375296513))[source]#

Bases: object

The tumbler: promises puzzles to payees and sells their solutions to payers.

It keeps the log a curious tumbler would keep: every puzzle it promised, and every puzzle it was paid to solve.

Parameters:: key (blockchainkit.crypto.systems.asymmetric.RSAKeyPair) – Its RSA key; the puzzles are under its public half.

promised: list[tuple[str, int]]#

solved: list[tuple[str, int]]#

promise(payee, token, rng)[source]#

Lock token under a fresh puzzle for payee.

Parameters:

payee (str)
token (bytes)
rng (Random)

Return type:

PuzzlePromise

solve(payer, puzzle)[source]#

Solve puzzle for a payer who paid for it: puzzle**d mod N.

Parameters:

payer (str)
puzzle (int)

Return type:

blockchainkit.privacy.systems.tumblebit.open_promise(promise, solution)[source]#

Decrypt the token of promise with the puzzle’s solution epsilon.

Parameters:

promise (PuzzlePromise)
solution (int)

Return type:

blockchainkit.privacy.systems.tumblebit.run_tumbler(pairs, *, blind=True, seed=0)[source]#

Pay each (payer, payee) pair through one tumbler.

With blind=False the payee hands its puzzle to the payer unblinded, and the tumbler’s two logs match.

Parameters:

pairs (Sequence[tuple[str, str]])
blind (bool)
seed (int)

Return type:

TumblerRun

blockchainkit.privacy.systems.tumblebit.tumbler_links(run)[source]#

(payer, payee) pairs the tumbler links because the same puzzle reached it twice.

Parameters:: run (TumblerRun)
Return type:: tuple[tuple[str, str], …]

Tornado Cash: a mixer contract with zero-knowledge withdrawals (2019).

Tornado Cash put Zerocash’s notes and nullifiers in an Ethereum contract. A user deposits a fixed amount, say 1 ether, together with the commitment to a secret note; the contract appends it to a Merkle tree of deposits. Later, from a fresh address, anyone holding the note withdraws by publishing its nullifier and a zk-SNARK proving the note is a leaf under a recent root. The contract pays out once per nullifier. Because all deposits are the same size, the withdrawal could be any earlier deposit not yet withdrawn: that is the anonymity set.

The proof hides the link, but behaviour does not. Users who withdraw to the address they deposited from, or withdraw right after an unusual deposit, shrink their anonymity sets to one. In August 2022 the US Treasury sanctioned the Tornado Cash contracts, after hackers had laundered stolen funds through them.

This mixer proves with the Zerocash spend circuit of blockchainkit.proofs (Groth16 over a toy pairing, MiMC hashing). The circuit’s new-note commitment is used to bind the recipient: it must be the commitment to a zero-valued note “owned” by the recipient’s tag, so a front-runner cannot redirect a withdrawal. Tornado binds the recipient, a relayer and its fee as separate public inputs of its own circuit.

blockchainkit.privacy.systems.tornado.recipient_commitment(recipient)[source]#

The commitment a withdrawal to recipient must create: a zero note owned by its tag.

Parameters:: recipient (str)
Return type:: int

blockchainkit.privacy.systems.tornado.deposit_root(leaves, depth)[source]#

The MiMC Merkle root of the deposit tree, padded with zeros.

Parameters:

leaves (Sequence[int])
depth (int)

Return type:

class blockchainkit.privacy.systems.tornado.Mixer[source]#

Bases: Contract

A fixed-denomination mixer: deposit with a commitment, withdraw with a proof.

Constructor arguments: denomination, the tree depth, and the Groth16 verifying_key of the spend circuit for that depth.

layout: ClassVar[tuple[str, ...]] = ('denomination', 'depth', 'verifying_key', 'count', 'leaves', 'roots', 'nullifiers')#

constructor(denomination, depth, verifying_key)[source]#

Parameters:

denomination (int)
depth (int)
verifying_key (VerifyingKey)

Return type:

None

deposits()[source]#

Every deposit commitment, in order.

Return type:: tuple[int, …]

deposit(commitment)[source]#

Add a note commitment, paying exactly the denomination; return its index.

Parameters:: commitment (int)
Return type:: int

withdraw(withdrawal)[source]#

Pay the denomination to the recipient if the proof is valid and the nullifier new.

Parameters:: withdrawal (Withdrawal)
Return type:: None

blockchainkit.privacy.systems.tornado.prove_withdrawal(proving_key, deposits, depth, secret_key, note, recipient, *, seed=0)[source]#

Prove that note, owned by secret_key, is among deposits, paying recipient.

Raises:

ValueError – The note’s commitment is not among the deposits.

Parameters:

proving_key (ProvingKey)
deposits (Sequence[int])
depth (int)
secret_key (int)
note (Note)
recipient (str)
seed (int)

Return type:

Withdrawal

blockchainkit.privacy.systems.tornado.mixer_report(deposits, withdrawals)[source]#

Anonymity sets and address links from (address, block) deposits and withdrawals.

A withdrawal’s anonymity set counts the deposits in earlier blocks, less the withdrawals in earlier blocks. An address link pairs a deposit with a withdrawal paid to the same address.

>>> from blockchainkit.privacy import mixer_report
>>> report = mixer_report([("a", 1), ("b", 2), ("c", 3)], [("x", 4), ("b", 5)])
>>> report.anonymity_sets, report.address_links
((3, 2), ((1, 1),))

Parameters:

deposits (Sequence[tuple[str, int]])
withdrawals (Sequence[tuple[str, int]])

Return type:

MixerReport

Hidden coins and amounts#

Zerocoin: anonymous coins from commitments and a proof of membership (Miers et al., 2013).

A user mints a zerocoin by paying a fixed amount to the ledger together with a commitment \(C = g^S h^r\) to a random serial number \(S\). To spend it, the user reveals \(S\) and proves in zero knowledge that it knows the opening of some minted coin with that serial, without saying which. The ledger records spent serials, so a coin cannot be spent twice, but the spend cannot be linked to its mint: every coin ever minted is in the anonymity set.

Miers, Garman, Green and Rubin made the proof constant-size by gathering the coins, hashed to primes, in an RSA accumulator \(A = u^{\\prod_i c_i} \bmod N\): each coin has a witness \(w = u^{\\prod_{j \ne i} c_j}\) with \(w^{c_i} = A\), and the spend proves knowledge of a witness for a committed coin.

Here the membership proof is instead a ring signature over every minted coin, linear in their number: \(C_i g^{-S} = h^{r}\) holds exactly for the coin being spent, so knowing \(r\) for one ring member is knowing the opening of one coin. The accumulator is shown with its witnesses, but the spend does not use it.

blockchainkit.privacy.systems.zerocoin.ACCUMULATOR_MODULUS = 9030000060190000019#

A 63-bit RSA modulus for the accumulator; its factors must stay unknown to users.

Type:: int

blockchainkit.privacy.systems.zerocoin.ACCUMULATOR_BASE = 4#

The accumulator’s starting value u, a quadratic residue modulo the modulus.

Type:: int

blockchainkit.privacy.systems.zerocoin.hash_to_prime(value, bits=32)[source]#

Hash value to a prime of bits bits, trying successive counters.

>>> from blockchainkit.privacy import hash_to_prime
>>> from blockchainkit.crypto import is_prime
>>> is_prime(hash_to_prime(12345))
True

Parameters:

value (int)
bits (int)

Return type:

blockchainkit.privacy.systems.zerocoin.accumulate(primes, modulus=9030000060190000019, base=4)[source]#

base**(product of primes) mod modulus: one number standing for the whole set.

Parameters:

primes (Sequence[int])
modulus (int)
base (int)

Return type:

blockchainkit.privacy.systems.zerocoin.membership_witness(primes, index, modulus=9030000060190000019, base=4)[source]#

The accumulator of every prime but primes[index].

Parameters:

primes (Sequence[int])
index (int)
modulus (int)
base (int)

Return type:

blockchainkit.privacy.systems.zerocoin.verify_membership(accumulator, prime, witness, modulus=9030000060190000019)[source]#

Whether witness**prime == accumulator, so prime is in the accumulated set.

Parameters:

accumulator (int)
prime (int)
witness (int)
modulus (int)

Return type:

blockchainkit.privacy.systems.zerocoin.mint_coin(serial, blinding, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

The commitment g**serial * h**blinding that is published when minting.

Parameters:

serial (int)
blinding (int)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.zerocoin.prove_zerocoin_spend(coins, serial, blinding, message, *, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Reveal serial and prove it belongs to one of coins, signing message.

Raises:

ValueError – No coin in coins opens to (serial, blinding).

Parameters:

coins (Sequence[int])
serial (int)
blinding (int)
message (bytes)
seed (int)
group (DHGroup)

Return type:

ZerocoinSpend

class blockchainkit.privacy.systems.zerocoin.ZerocoinPool(group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Bases: object

The ledger’s side of Zerocoin: minted coins, the accumulator, and spent serials.

Examples

>>> from blockchainkit.privacy import ZerocoinPool, mint_coin, prove_zerocoin_spend
>>> pool = ZerocoinPool()
>>> for serial, blinding in [(101, 7), (202, 8), (303, 9)]:
...     _ = pool.mint(mint_coin(serial, blinding))
>>> pool.spend(prove_zerocoin_spend(pool.coins, 202, 8, b"pay bob"), b"pay bob")
>>> sorted(pool.spent)
[202]

Parameters:: group (DHGroup)

property coins: tuple[int, ...]#: Every minted coin commitment, in order.

property spent: frozenset[int]#: Serial numbers already spent.

property accumulator: int#: The RSA accumulator of the coins hashed to primes.

mint(coin)[source]#

Record a new coin commitment and return its index.

Parameters:: coin (int)
Return type:: int

spend(spend, message)[source]#

Accept a spend signed over message and record its serial.

Raises:

ValueError – The serial was already spent, or the proof does not verify against the current coins.

Parameters:

spend (ZerocoinSpend)
message (bytes)

Return type:

None

Confidential transactions: hidden amounts that still add up (Maxwell, 2015).

Each output’s amount is replaced by a Pedersen commitment \(C = g^{v} h^{r}\). Commitments multiply as their amounts add, so anyone can check that a transaction creates no money,

\[\begin{split}\\prod_{\text{in}} C_i = g^{\text{fee}} \\prod_{\text{out}} C_j ,\end{split}\]

as long as the sender chooses the blinding factors to cancel. That check alone is not enough: amounts are numbers modulo the group order \(q\), so an output of \(q - 1\), that is \(-1\), lets another output hold one coin more than was paid in. Every output therefore carries a range proof that its amount is small. Maxwell’s proof commits to each digit and proves, with a ring signature over \(\\{C_k, C_k / g^{2^k}\\}\), that one of them is a pure \(h^{r_k}\), so the digit is 0 or 1; the digit commitments multiply back to \(C\).

Elements and Liquid use base-4 digits joined into one Borromean ring signature; here every bit has its own two-member ring signature. Bulletproofs (see blockchainkit.proofs) later made the proof logarithmic.

blockchainkit.privacy.systems.confidential.DEFAULT_BITS = 16#

Bits of a range proof, so amounts lie in [0, 2**16).

Type:: int

blockchainkit.privacy.systems.confidential.prove_range(value, blinding, bits=16, *, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Prove that pedersen_commit(value, blinding) holds a value in [0, 2**bits).

Raises:

ValueError – value is out of range, so no proof exists.

Parameters:

value (int)
blinding (int)
bits (int)
seed (int)
group (DHGroup)

Return type:

RingRangeProof

Examples

>>> from blockchainkit.privacy import prove_range, verify_range
>>> from blockchainkit.crypto import pedersen_commit
>>> verify_range(pedersen_commit(1000, 99), prove_range(1000, 99))
True

blockchainkit.privacy.systems.confidential.verify_range(commitment, proof, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check that proof shows commitment to hold a value in [0, 2**proof.bits).

Parameters:

commitment (int)
proof (RingRangeProof)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.confidential.confidential_output(amount, blinding, bits=16, *, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

An output committing to amount, with its range proof.

Parameters:

amount (int)
blinding (int)
bits (int)
seed (int)
group (DHGroup)

Return type:

ConfidentialOutput

blockchainkit.privacy.systems.confidential.commitments_balance(inputs, outputs, fee, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Whether the input commitments equal g**fee times the output commitments.

Parameters:

inputs (Sequence[int])
outputs (Sequence[int])
fee (int)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.confidential.verify_confidential(inputs, outputs, fee, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

A confidential transaction is valid if it balances and every output has a range proof.

Parameters:

inputs (Sequence[int])
outputs (Sequence[ConfidentialOutput])
fee (int)
group (DHGroup)

Return type:

Ring Confidential Transactions: hiding the input and the amounts at once (Noether, 2016).

Monero hid which output a transaction spends with linkable ring signatures, but amounts stayed public, and a ring could only mix outputs of the same denomination. RingCT puts every amount in a Pedersen commitment, as confidential transactions do, and must then prove the amounts balance without saying which ring member is the input.

It does so with a second column in an MLSAG signature. Each ring member \(i\) is a pair (one-time key \(P_i\), amount commitment \(C_i\)), and the second column’s key is

\[\begin{split}Z_i = \frac{C_i}{g^{\text{fee}} \\prod_j C^{\text{out}}_j} ,\end{split}\]

which, for the real input whose amount equals the outputs plus the fee, is \(h^{z}\) with \(z\) the difference of blinding factors. Signing both columns with one ring of challenges proves the signer knows the key of some \(P_i\) and the \(z\) of the same \(Z_i\), so that member’s amount balances. The key image of \(P_i\) stops double spends.

This model has one input per transaction; Monero gives each input a pseudo-output commitment so several inputs balance together, and since 2019 it uses CLSAG and Bulletproofs in place of MLSAG and digit-wise range proofs.

blockchainkit.privacy.systems.ringct.ringct_spend(ring, index, secret, amount, blinding, outputs, fee, *, bits=16, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Spend ring member index, which holds amount under blinding, into outputs.

Parameters:

ring (collections.abc.Sequence of tuple of int) – (one-time key, amount commitment) of each possible input.
index (int) – The real input.
secret (int) – The real input’s one-time private key.
amount (int) – The real input’s amount and the blinding factor of its commitment.
blinding (int) – The real input’s amount and the blinding factor of its commitment.
outputs (collections.abc.Sequence of tuple of int) – (amount, blinding) of each new output.
fee (int) – The public fee.
bits (int) – Size of the outputs’ range proofs.
seed (int) – Seeds the signature and the range proofs.
group (blockchainkit.crypto.systems.asymmetric.DHGroup) – The group of keys and commitments.

Raises:

ValueError – The amounts do not balance, the blinding factors cancel exactly (no key for the second column), or the secrets do not match the ring.

Return type:

RingCTTransaction

blockchainkit.privacy.systems.ringct.verify_ringct(transaction, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check the ring signature, which also proves the amounts balance, and every range proof.

Parameters:

transaction (RingCTTransaction)
group (DHGroup)

Return type:

MimblewimbleTransaction

Mimblewimble: no addresses, no amounts, and a chain that forgets spent outputs (2016).

An anonymous author, “Tom Elvis Jedusor”, noticed that in a confidential transaction the blinding factors can serve as the keys. An output is just a commitment \(C = g^{v} h^{r}\), owned by whoever knows \(r\). If a transaction balances, the outputs divided by the inputs (and \(g^{\text{fee}}\)) leave \(h^{k}\) with \(k\) the change in blinding. The parties prove they know \(k\) by a Schnorr signature with the excess \(E = h^{k}\) as public key, recorded in a kernel. Nothing else is needed: no addresses, no scripts, no amounts.

Because only the sums matter, transactions merge non-interactively into one, and an output created and spent in the merged set cancels with its input. This cut-through lets a node discard every spent output yet still check that

\[\begin{split}\frac{\\prod \text{outputs}}{\\prod \text{inputs}} \\, g^{\text{fees} - \text{minted}} = \\Big(\\prod_k E_k\\Big) h^{\text{offset}} .\end{split}\]

Each transaction moves a random offset out of its kernel, as Grin does, so that merged transactions cannot be split back apart by matching kernels to subsets of inputs and outputs. Real Mimblewimble chains also attach a range proof to every output; see confidential.

blockchainkit.privacy.systems.mimblewimble.mimblewimble_transaction(inputs, outputs, fee=0, *, minted=0, seed=0, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Build a transaction spending (value, blinding) inputs into outputs.

Raises:

ValueError – The values do not balance: inputs plus minted must equal outputs plus fee.

Parameters:

inputs (Sequence[tuple[int, int]])
outputs (Sequence[tuple[int, int]])
fee (int)
minted (int)
seed (int)
group (DHGroup)

Return type:

Examples

>>> from blockchainkit.privacy import mimblewimble_transaction, verify_mimblewimble
>>> coinbase = mimblewimble_transaction([], [(50, 11)], minted=50)
>>> payment = mimblewimble_transaction([(50, 11)], [(30, 22), (19, 33)], fee=1, seed=1)
>>> verify_mimblewimble(coinbase), verify_mimblewimble(payment)
(True, True)

blockchainkit.privacy.systems.mimblewimble.verify_kernel(kernel, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check the kernel’s Schnorr signature: h**s == R * E**e.

Parameters:

kernel (Kernel)
group (DHGroup)

Return type:

blockchainkit.privacy.systems.mimblewimble.verify_mimblewimble(transaction, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Check every kernel signature and that the commitments sum to the kernels’ excesses.

Parameters:

transaction (MimblewimbleTransaction)
group (DHGroup)

Return type:

MimblewimbleTransaction

blockchainkit.privacy.systems.mimblewimble.aggregate(transactions, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Merge transactions into one: sorted inputs, outputs and kernels, offsets added.

Parameters:

transactions (Sequence[MimblewimbleTransaction])
group (DHGroup)

Return type:

blockchainkit.privacy.systems.mimblewimble.cut_through(transaction)[source]#

Remove every output that is also an input: it was created and spent in the same set.

Parameters:: transaction (MimblewimbleTransaction)
Return type:: MimblewimbleTransaction

Group helpers#

Hashing into the teaching group, and a hash keystream for layered encryption.

Every construction of blockchainkit.privacy works in TEACHING_GROUP, the order-q subgroup modulo a 62-bit safe prime, written multiplicatively: a public key is g**x mod p where elliptic-curve papers write xG.

blockchainkit.privacy.utils.groups.hash_to_scalar(domain, *values, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Hash a domain tag, the group and values to an integer modulo q.

The values are framed with canonical JSON, so (1, 23) and (12, 3) hash differently.

>>> from blockchainkit.privacy import hash_to_scalar
>>> hash_to_scalar(b"demo", 1, 23) != hash_to_scalar(b"demo", 12, 3)
True

Parameters:

domain (bytes)
values (object)
group (DHGroup)

Return type:

blockchainkit.privacy.utils.groups.hash_to_group(domain, *values, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Hash values to an element of the order-q subgroup whose log nobody knows.

Squaring modulo the safe prime p = 2q + 1 maps any nonzero residue into the subgroup; a degenerate result is hashed again with a counter.

Parameters:

domain (bytes)
values (object)
group (DHGroup)

Return type:

blockchainkit.privacy.utils.groups.keystream_xor(key, data, domain)[source]#

Encrypt or decrypt data by XOR with the SHA-256 keystream of key.

The same call undoes itself. A teaching stand-in for a stream cipher: there is no authentication tag.

>>> from blockchainkit.privacy import keystream_xor
>>> sealed = keystream_xor(42, b"attack at dawn", b"demo")
>>> keystream_xor(42, sealed, b"demo")
b'attack at dawn'

Parameters:

key (int)
data (bytes)
domain (bytes)

Return type: