blockchainkit.proofs#

blockchainkit.proofs hub · History · Examples · API reference

Proofs: zero-knowledge and succinct proof systems.

How a prover convinces a verifier that a computation is correct, cheaply and without revealing its secrets: polynomial identity testing and sum-check, interactive proofs and PCPs, Merkle-committed arguments, polynomial commitments, circuits and QAPs, pairing-based SNARKs (Groth16, PLONK) and their trusted setups, private payments, and transparent systems from hashes and discrete logs (Bulletproofs, FRI, STARKs, Halo). Everything runs over small fields and groups whose numbers can be inspected by hand.

How a prover convinces a verifier that a computation is correct, cheaply and without revealing its secrets: polynomial identity testing and sum-check, interactive proofs and PCPs, Merkle-committed arguments, KZG commitments, circuits and QAPs, Groth16 and PLONK with their trusted setups, private payments, and the transparent systems Bulletproofs, FRI, STARKs and Halo.

Every public name below is re-exported by the subpackage: import it as bk.proofs.<name>. The plotting helpers are the exception: import them explicitly from blockchainkit.proofs.visualizers, which loads Matplotlib.

Results#

Shared types and result containers for blockchainkit.proofs.

blockchainkit.proofs.core.base.Polynomial#

Coefficients, constant term first, with no trailing zeros.

alias of tuple[int, …]

class blockchainkit.proofs.core.base.IdentityTest(equal, trials, witness)[source]#

Bases: object

The outcome of testing two polynomials for equality at random points.

Variables:

  • equal (bool) – Whether the two agreed at every point tried. True may be wrong, with probability at most degree / field size per point; False is always right.

  • trials (int) – Points tried.

  • witness (tuple of int or None) – A point where they differ, if one was found.

Parameters:
equal: bool#
trials: int#
witness: tuple[int, ...] | None#
class blockchainkit.proofs.core.base.CNF(num_variables, clauses)[source]#

Bases: object

A Boolean formula in conjunctive normal form, and its arithmetization.

Parameters:

  • num_variables (int) – Variables are numbered 1 to num_variables.

  • clauses (tuple of tuple of int) – Each clause lists literals: i for variable i, -i for its negation, as in the DIMACS format.

Examples

>>> from blockchainkit.proofs import CNF
>>> xor = CNF(2, ((1, 2), (-1, -2)))
>>> xor.count_solutions(), xor.evaluate((1, 0), 97), xor.evaluate((1, 1), 97)
(2, 1, 0)
num_variables: int#
clauses: tuple[tuple[int, ...], ...]#
property degree: int#

The arithmetization’s degree in any one variable, its most occurrences.

evaluate(point, prime)[source]#

Evaluate the arithmetized formula at a point of the field.

A literal becomes x or 1 - x, a clause becomes 1 - prod(1 - literal), and the formula the product of its clauses. On 0/1 inputs this is the formula’s truth value.

Parameters:
Return type:

int

is_satisfied(assignment)[source]#

Whether a 0/1 assignment satisfies every clause.

Parameters:

assignment (Sequence[int])

Return type:

bool

count_solutions()[source]#

Count the satisfying assignments by trying all 2**n of them.

Return type:

int

class blockchainkit.proofs.core.base.SumcheckRun(claim, true_sum, polynomials, challenges, accepted)[source]#

Bases: object

One run of the sum-check protocol between a prover and a verifier.

Variables:

  • claim (int) – The sum the prover asserted.

  • true_sum (int) – The actual sum over the Boolean cube.

  • polynomials (tuple of Polynomial) – The univariate polynomial the prover sent in each round.

  • challenges (tuple of int) – The verifier’s random field element after each round.

  • accepted (bool) – Whether every round check and the final oracle query passed.

Parameters:
claim: int#
true_sum: int#
polynomials: tuple[tuple[int, ...], ...]#
challenges: tuple[int, ...]#
accepted: bool#
class blockchainkit.proofs.core.base.QBF(quantifiers, formula)[source]#

Bases: object

A fully quantified Boolean formula: one quantifier per variable, then a CNF.

Parameters:

Examples

>>> from blockchainkit.proofs import CNF, QBF
>>> QBF("AE", CNF(2, ((1, 2), (-1, -2)))).evaluate()  # for all x, some y differs
True
quantifiers: str#
formula: CNF#
evaluate()[source]#

Decide the formula by trying every assignment: exponential time, linear space.

Return type:

bool

class blockchainkit.proofs.core.base.TQBFRound(operator, variable, polynomial, challenge)[source]#

Bases: object

One round of Shamir’s protocol: an operator, its variable, and the prover’s polynomial.

Variables:

  • operator (str) – "A" (product), "E" (complemented product) or "L" (linearization).

  • variable (int) – The variable it acts on, from 1.

  • polynomial (Polynomial) – The prover’s claim for the inner expression as a polynomial in that variable.

  • challenge (int) – The random value the verifier then assigned to the variable.

Parameters:
operator: str#
variable: int#
polynomial: tuple[int, ...]#
challenge: int#
class blockchainkit.proofs.core.base.TQBFRun(claim, true_value, rounds, accepted)[source]#

Bases: object

One run of the interactive proof that a quantified Boolean formula is true.

Variables:
Parameters:
claim: int#
true_value: int#
rounds: tuple[TQBFRound, ...]#
accepted: bool#
property max_degree: int#

The largest degree among the prover’s polynomials.

class blockchainkit.proofs.core.base.QuadraticSystem(num_variables, equations)[source]#

Bases: object

Quadratic equations over GF(2): the NP-complete language of the Hadamard PCP.

Parameters:

  • num_variables (int) – Variables u_0, …, u_{n-1}, with n between 1 and 4.

  • equations (tuple) – Each equation is (terms, constant): it says that the sum of u_i u_j over the pairs (i, j) in terms is constant modulo 2. A linear term u_i is the pair (i, i).

Examples

>>> from blockchainkit.proofs import QuadraticSystem
>>> system = QuadraticSystem(2, ((((0, 1),), 1), (((0, 0), (1, 1)), 0)))
>>> system.solutions()  # u0 u1 = 1 and u0 + u1 = 0
((1, 1),)
num_variables: int#
equations: tuple[tuple[tuple[tuple[int, int], ...], int], ...]#
is_satisfied(assignment)[source]#

Whether a 0/1 assignment satisfies every equation.

Parameters:

assignment (Sequence[int])

Return type:

bool

solutions()[source]#

Every satisfying assignment, by trying all 2**n.

Return type:

tuple[tuple[int, …], …]

class blockchainkit.proofs.core.base.HadamardProof(linear, quadratic)[source]#

Bases: object

The exponentially long proof of the Hadamard PCP.

Variables:

  • linear (tuple of int) – <u, x> mod 2 for every x in {0, 1}**n, indexed by x as a binary number (bit i is x_i).

  • quadratic (tuple of int) – <u (x) u, y> mod 2 for every y in {0, 1}**(n**2), where bit i n + j of y pairs with u_i u_j.

Parameters:
linear: tuple[int, ...]#
quadratic: tuple[int, ...]#
property bits: tuple[int, ...]#

Both tables concatenated, the string a PCP verifier queries.

class blockchainkit.proofs.core.base.PCPRun(accepted, queries, failed_test)[source]#

Bases: object

The PCP verifier’s verdict.

Variables:

  • accepted (bool)

  • queries (int) – Proof bits read.

  • failed_test (str or None) – The first test that failed.

Parameters:

  • accepted (bool)

  • queries (int)

  • failed_test (str | None)

accepted: bool#
queries: int#
failed_test: str | None#
class blockchainkit.proofs.core.base.KilianRun(root, accepted, queries, communication, proof_length)[source]#

Bases: object

One run of Kilian’s interactive argument: a Merkle-committed PCP, opened where queried.

Variables:

  • root (bytes) – The prover’s commitment to the whole PCP.

  • accepted (bool) – Whether every opening matched the root and the PCP verifier accepted.

  • queries (int) – PCP bits opened.

  • communication (int) – Bytes the prover sent: the root, then each bit with its Merkle path.

  • proof_length (int) – Bits in the PCP itself, which the prover never sends.

Parameters:
root: bytes#
accepted: bool#
queries: int#
communication: int#
proof_length: int#
class blockchainkit.proofs.core.base.Opening(position, bit, path)[source]#

Bases: object

One PCP bit and its Merkle path.

Parameters:
position: int#
bit: int#
path: MerkleProof#
class blockchainkit.proofs.core.base.CSProof(root, salt, openings)[source]#

Bases: object

Micali’s computationally sound proof: a root, a salt, and the openings it selects.

Variables:

  • root (bytes) – Merkle root of the PCP.

  • salt (int) – Hashed with the root to select the queries; varying it is how a cheating prover grinds.

  • openings (tuple of blockchainkit.proofs.core.base.Opening) – The queried bits, in the order the verifier reads them.

Parameters:
root: bytes#
salt: int#
openings: tuple[Opening, ...]#
property size: int#

Bytes sent for the root, the salt, and each opening’s bit, position and path.

class blockchainkit.proofs.core.base.SRS(powers, curve)[source]#

Bases: object

A structured reference string: [tau**i] G for i = 0, …, max_degree.

Variables:
Parameters:
powers: tuple[tuple[int, int] | None, ...]#
curve: Curve#
property max_degree: int#

The largest degree it can commit to.

class blockchainkit.proofs.core.base.KZGOpening(point, value, witness)[source]#

Bases: object

A claimed evaluation f(point) = value and its witness [q(tau)] G.

Parameters:
point: int#
value: int#
witness: tuple[int, int] | None#
class blockchainkit.proofs.core.base.Contribution(srs, public)[source]#

Bases: object

One participant’s update to a ceremony: the new string and [secret] G.

Parameters:
srs: SRS#
public: tuple[int, int] | None#
blockchainkit.proofs.core.base.Row#

One sparse row of an R1CS matrix, as (variable index, coefficient) pairs.

alias of tuple[tuple[int, int], …]

class blockchainkit.proofs.core.base.R1CS(prime, num_variables, num_public, a, b, c)[source]#

Bases: object

A rank-1 constraint system: <a_j, z> * <b_j, z> = <c_j, z> for every row j.

Variables:

  • prime (int) – Field modulus.

  • num_variables (int) – Length of the witness z, including the leading constant 1.

  • num_public (int) – Public inputs, which follow the constant in z.

  • c (a, b,) – The sparse rows of the three matrices.

Parameters:
prime: int#
num_variables: int#
num_public: int#
a: tuple[tuple[tuple[int, int], ...], ...]#
b: tuple[tuple[tuple[int, int], ...], ...]#
c: tuple[tuple[tuple[int, int], ...], ...]#
property num_constraints: int#

Number of rows.

row_values(witness)[source]#

Return (<a_j, z>, <b_j, z>, <c_j, z>) for every row.

Parameters:

witness (Sequence[int])

Return type:

tuple[tuple[int, int, int], …]

is_satisfied(witness)[source]#

Whether every constraint holds for witness.

Parameters:

witness (Sequence[int])

Return type:

bool

class blockchainkit.proofs.core.base.QAP(prime, domain_size, a, b, c, target)[source]#

Bases: object

A quadratic arithmetic program: one polynomial per variable and matrix.

Variables:

  • prime (int)

  • domain_size (int) – n, the size of the domain {w**j} of roots of unity.

  • c (a, b,) – A_i, B_i, C_i for each witness variable i.

  • target (Polynomial) – t(X) = X**n - 1, which vanishes on the domain.

Parameters:
prime: int#
domain_size: int#
a: tuple[tuple[int, ...], ...]#
b: tuple[tuple[int, ...], ...]#
c: tuple[tuple[int, ...], ...]#
target: tuple[int, ...]#
class blockchainkit.proofs.core.base.QAPDivision(left, right, output, quotient, remainder)[source]#

Bases: object

A B - C = H t + R for one witness.

Variables:

  • output (left, right,) – A(X), B(X) and C(X).

  • quotient (Polynomial) – H(X).

  • remainder (Polynomial) – R(X), zero exactly when the witness satisfies every constraint.

Parameters:
left: tuple[int, ...]#
right: tuple[int, ...]#
output: tuple[int, ...]#
quotient: tuple[int, ...]#
remainder: tuple[int, ...]#
property satisfied: bool#

Whether the target divides A B - C.

class blockchainkit.proofs.core.base.Groth16Trapdoor(tau, alpha, beta, gamma, delta)[source]#

Bases: object

The setup’s toxic waste: five secret field elements that must be destroyed.

Anyone who keeps them can prove false statements.

Parameters:
tau: int#
alpha: int#
beta: int#
gamma: int#
delta: int#
class blockchainkit.proofs.core.base.VerifyingKey(alpha, beta, gamma, delta, public_query, curve)[source]#

Bases: object

What a Groth16 verifier needs: four points and one point per public input.

Variables:
Parameters:
alpha: tuple[int, int] | None#
beta: tuple[int, int] | None#
gamma: tuple[int, int] | None#
delta: tuple[int, int] | None#
public_query: tuple[tuple[int, int] | None, ...]#
curve: Curve#
class blockchainkit.proofs.core.base.ProvingKey(r1cs, domain_size, a_query, b_query, private_query, h_query, verifying_key)[source]#

Bases: object

What a Groth16 prover needs: the circuit and the encoded QAP at the secret point.

Variables:
Parameters:
r1cs: R1CS#
domain_size: int#
a_query: tuple[tuple[int, int] | None, ...]#
b_query: tuple[tuple[int, int] | None, ...]#
private_query: tuple[tuple[int, int] | None, ...]#
h_query: tuple[tuple[int, int] | None, ...]#
verifying_key: VerifyingKey#
class blockchainkit.proofs.core.base.Groth16Proof(a, b, c)[source]#

Bases: object

Three group elements, whatever the size of the circuit.

Parameters:
a: tuple[int, int] | None#
b: tuple[int, int] | None#
c: tuple[int, int] | None#
class blockchainkit.proofs.core.base.Note(owner, value, rho, randomness)[source]#

Bases: object

A Zerocash note: who owns it, its value, its unique serial seed, and commitment randomness.

Variables:

  • owner (int) – The owner’s public key H(sk, 0).

  • value (int)

  • rho (int) – Unique per note; its nullifier is H(sk, rho).

  • randomness (int) – Hides the note inside its commitment.

Parameters:
owner: int#
value: int#
rho: int#
randomness: int#
class blockchainkit.proofs.core.base.SpendTransaction(root, nullifier, new_commitment, public_value, proof)[source]#

Bases: object

What a Zerocash spend publishes: root, nullifier, new commitment, amount and proof.

Parameters:
root: int#
nullifier: int#
new_commitment: int#
public_value: int#
proof: Groth16Proof#
class blockchainkit.proofs.core.base.PlonkKey(prime, n, omega, wiring, selectors, sigmas, sigma_labels, selector_commitments, sigma_commitments)[source]#

Bases: object

A preprocessed PLONK circuit: selector and permutation polynomials, and their commitments.

Variables:

  • prime (int)

  • n (int) – Rows of the padded circuit, a power of two.

  • omega (int) – Generator of the domain of n-th roots of unity.

  • wiring (tuple of tuple of int) – The variables on each row’s left, right and output wires.

  • selectors (tuple of Polynomial) – q_L, q_R, q_O, q_M, q_C.

  • sigmas (tuple of Polynomial) – The permutation, one polynomial per wire column.

  • sigma_labels (tuple of tuple of int) – The permutation’s values on the domain.

  • sigma_commitments (selector_commitments,) – What the verifier holds.

Parameters:
prime: int#
n: int#
omega: int#
wiring: tuple[tuple[int, int, int], ...]#
selectors: tuple[tuple[int, ...], ...]#
sigmas: tuple[tuple[int, ...], ...]#
sigma_labels: tuple[tuple[int, ...], ...]#
selector_commitments: tuple[tuple[int, int] | None, ...]#
sigma_commitments: tuple[tuple[int, int] | None, ...]#
class blockchainkit.proofs.core.base.PlonkProof(wires, z, t, evaluations, opening, shifted_opening)[source]#

Bases: object

Five commitments, fourteen evaluations and two opening witnesses.

Variables:

  • wires (tuple of Point) – Commitments to the wire polynomials a, b, c.

  • z (Point) – Commitment to the running product of the permutation argument.

  • t (Point) – Commitment to the quotient polynomial.

  • evaluations (tuple of int) – a, b, c, sigma_1..3, q_L, q_R, q_O, q_M, q_C, z and t at zeta, then z at zeta omega.

  • shifted_opening (opening,) – Batched KZG witnesses at zeta and at zeta omega.

Parameters:
wires: tuple[tuple[int, int] | None, ...]#
z: tuple[int, int] | None#
t: tuple[int, int] | None#
evaluations: tuple[int, ...]#
opening: tuple[int, int] | None#
shifted_opening: tuple[int, int] | None#
class blockchainkit.proofs.core.base.RangeProof(commitment, a, s, t1, t2, tau_x, mu, t_hat, left, right, final_a, final_b)[source]#

Bases: object

A Bulletproofs range proof for the commitment V = g**v h**gamma.

Variables:

  • commitment (int) –

  • t2 (a, s, t1,) – Commitments to the bit vectors, the blinding vectors, and the coefficients of t(X).

  • t_hat (tau_x, mu,) – The blinding of t(x), the blinding of A S**x, and t(x).

  • right (left,) – L and R from each halving round of the inner-product argument.

  • final_b (final_a,) – The last scalars of the folded vectors.

Parameters:
commitment: int#
a: int#
s: int#
t1: int#
t2: int#
tau_x: int#
mu: int#
t_hat: int#
left: tuple[int, ...]#
right: tuple[int, ...]#
final_a: int#
final_b: int#
property size: tuple[int, int]#

(group elements, scalars) sent, not counting the commitment V.

class blockchainkit.proofs.core.base.IPAOpening(point, value, left, right, final, g_final)[source]#

Bases: object

An inner-product-argument opening of a polynomial commitment.

Variables:

  • value (point,) – The claim f(point) = value.

  • right (left,) – L and R from each halving round.

  • final (int) – The last coefficient after folding.

  • g_final (int) – The prover’s claim for the folded generator, which a full verifier recomputes and a Halo verifier defers.

Parameters:
point: int#
value: int#
left: tuple[int, ...]#
right: tuple[int, ...]#
final: int#
g_final: int#
class blockchainkit.proofs.core.base.HaloAccumulator(challenges, g_final)[source]#

Bases: object

A deferred claim: g_final commits to prod (1 + c_j X**(2**(k-j))).

Variables:

  • challenges (tuple of int) – The halving challenges c_j that define the polynomial.

  • g_final (int) – The claimed commitment to it.

Parameters:
challenges: tuple[int, ...]#
g_final: int#
class blockchainkit.proofs.core.base.AccumulationProof(opening)[source]#

Bases: object

The opening that merges several accumulators into one.

Parameters:

opening (IPAOpening)

opening: IPAOpening#
class blockchainkit.proofs.core.base.FRILayerOpening(low, low_path, high, high_path)[source]#

Bases: object

The two values of one layer that fold together, f(x) and f(-x), with their Merkle paths.

Parameters:
low: int#
low_path: MerkleProof#
high: int#
high_path: MerkleProof#
class blockchainkit.proofs.core.base.FRIQuery(index, layers)[source]#

Bases: object

One query: a position of the first layer and its openings in every layer.

Parameters:
index: int#
layers: tuple[FRILayerOpening, ...]#
class blockchainkit.proofs.core.base.FRIProof(roots, final, queries)[source]#

Bases: object

A FRI proof: one Merkle root per layer, the final constant, and the queries.

Variables:
Parameters:
roots: tuple[bytes, ...]#
final: int#
queries: tuple[FRIQuery, ...]#
property size: int#

Bytes sent for the roots, the constant, and each opened value with its path.

class blockchainkit.proofs.core.base.TraceOpening(values, paths)[source]#

Bases: object

Trace values at x, g x and g**2 x, with their Merkle paths.

Parameters:
values: tuple[int, ...]#
paths: tuple[MerkleProof, ...]#
class blockchainkit.proofs.core.base.StarkProof(trace_root, fri, trace_openings)[source]#

Bases: object

A STARK: the trace’s Merkle root, a FRI proof, and the trace openings it needs.

Variables:
Parameters:
trace_root: bytes#
fri: FRIProof#
trace_openings: tuple[TraceOpening, ...]#
property size: int#

Bytes sent for the root, the FRI proof, and the opened trace values with paths.

Fields, polynomials and transcripts#

Univariate polynomials over a prime field, and the fast Fourier transform.

A polynomial is a tuple of coefficients, constant term first, with no trailing zeros: (5, 0, 1) is 5 + x**2 and () is the zero polynomial. Every function takes the field modulus as prime; it defaults to FIELD_PRIME, the BabyBear prime 15 * 2**27 + 1, whose multiplicative group has a subgroup of every power-of-two order up to 2**27. Those subgroups are the evaluation domains of the FFT, of FRI, and of PLONK.

blockchainkit.proofs.utils.polynomials.FIELD_PRIME = 2013265921#

The BabyBear prime 2013265921, used by RISC Zero and SP1. Its multiplicative group has order 2**27 * 15, so power-of-two domains up to 2**27 points exist.

Type:

int

blockchainkit.proofs.utils.polynomials.FIELD_GENERATOR = 31#

A generator of the multiplicative group of FIELD_PRIME.

Type:

int

blockchainkit.proofs.utils.polynomials.polynomial(coefficients, prime=2013265921)[source]#

Reduce coefficients into the field and drop trailing zeros.

>>> from blockchainkit.proofs import polynomial
>>> polynomial([3, -1, 0], prime=7)
(3, 6)
Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.degree(poly)[source]#

Return the degree, or -1 for the zero polynomial.

Parameters:

poly (Sequence[int])

Return type:

int

blockchainkit.proofs.utils.polynomials.poly_add(left, right, prime=2013265921)[source]#

Add two polynomials.

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.poly_scale(poly, scalar, prime=2013265921)[source]#

Multiply every coefficient by scalar.

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.poly_sub(left, right, prime=2013265921)[source]#

Subtract right from left.

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.poly_mul(left, right, prime=2013265921)[source]#

Multiply two polynomials by schoolbook convolution.

>>> from blockchainkit.proofs import poly_mul
>>> poly_mul([1, 1], [1, 1], prime=97)
(1, 2, 1)
Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.poly_divmod(numerator, denominator, prime=2013265921)[source]#

Divide with remainder: numerator = quotient * denominator + remainder.

Raises:

ZeroDivisionError – denominator is the zero polynomial.

Parameters:
Return type:

tuple[tuple[int, …], tuple[int, …]]

Examples

>>> from blockchainkit.proofs import poly_divmod
>>> poly_divmod([-1, 0, 1], [-1, 1], prime=97)  # (x**2 - 1) / (x - 1)
((1, 1), ())
blockchainkit.proofs.utils.polynomials.poly_eval(poly, x, prime=2013265921)[source]#

Evaluate at x by Horner’s rule.

>>> from blockchainkit.proofs import poly_eval
>>> poly_eval([5, 0, 1], 3, prime=97)
14
Parameters:
Return type:

int

blockchainkit.proofs.utils.polynomials.vanishing_polynomial(roots, prime=2013265921)[source]#

Return the monic polynomial whose roots are roots: the product of (x - root).

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.interpolate(points, prime=2013265921)[source]#

Return the unique polynomial of degree below len(points) through points.

Lagrange’s formula, in O(n**2) field operations.

Raises:

ValueError – Two points share an x-coordinate.

Parameters:
Return type:

tuple[int, …]

Examples

>>> from blockchainkit.proofs import interpolate
>>> interpolate([(0, 5), (1, 6), (2, 9)], prime=97)  # 5 + x**2
(5, 0, 1)
blockchainkit.proofs.utils.polynomials.root_of_unity(n, prime=2013265921)[source]#

Return an element of multiplicative order exactly n, a power of two.

The domain {w**i} of the FFT. n must divide prime - 1.

>>> from blockchainkit.proofs import root_of_unity
>>> w = root_of_unity(8)
>>> pow(w, 8, 2013265921), pow(w, 4, 2013265921) != 1
(1, True)
Parameters:
Return type:

int

blockchainkit.proofs.utils.polynomials.domain(n, prime=2013265921, offset=1)[source]#

Return the n points offset * w**i of a (shifted) power-of-two subgroup.

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.evaluate_on_domain(poly, n, prime=2013265921, offset=1)[source]#

Evaluate at the n points of domain() with the radix-2 FFT.

Costs O(n log n) field operations instead of the O(n**2) of evaluating point by point. The polynomial’s degree must be below n.

>>> from blockchainkit.proofs import evaluate_on_domain, poly_eval, domain
>>> evaluate_on_domain([1, 2, 3], 4) == tuple(poly_eval([1, 2, 3], x) for x in domain(4))
True
Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.polynomials.interpolate_on_domain(values, prime=2013265921, offset=1)[source]#

Inverse of evaluate_on_domain(): the polynomial taking values on the domain.

>>> from blockchainkit.proofs import evaluate_on_domain, interpolate_on_domain
>>> interpolate_on_domain(evaluate_on_domain([4, 0, 7], 8, offset=31), offset=31)
(4, 0, 7)
Parameters:
Return type:

tuple[int, …]

A Fiat-Shamir transcript: the prover’s messages hashed into the verifier’s challenges.

Fiat and Shamir (1986) replaced an interactive verifier by a hash of everything said so far. Transcript keeps a running SHA-256 state: append absorbs a labelled message, and challenge squeezes an integer below a modulus that depends on every message before it. The prover and the verifier run the same transcript, so they derive the same challenges, and the prover cannot choose its messages after seeing them.

blockchainkit.proofs.utils.transcript.Message = int | bytes | None | collections.abc.Sequence['Message']#

Integers, bytes, None (a point at infinity), or sequences of them.

class blockchainkit.proofs.utils.transcript.Transcript(protocol)[source]#

Bases: object

A labelled, append-only Fiat-Shamir transcript.

Parameters:

protocol (bytes) – Names the protocol, so challenges never transfer between protocols.

Examples

>>> from blockchainkit.proofs import Transcript
>>> prover, verifier = Transcript(b"demo"), Transcript(b"demo")
>>> prover.append("commitment", 42); verifier.append("commitment", 42)
>>> prover.challenge("c", 97) == verifier.challenge("c", 97)
True
append(label, value)[source]#

Absorb a labelled message.

Parameters:
Return type:

None

challenge(label, modulus)[source]#

Squeeze an integer in [0, modulus) from everything absorbed so far.

The 256-bit digest is reduced modulo modulus, which must be below 2**64, so the bias is below 2**-192.

Parameters:
Return type:

int

Group helpers for the commitment schemes: independent generators and linear combinations.

blockchainkit.proofs.utils.groups.independent_generators(count, label, group=DHGroup(p=4611686018427377339, q=2305843009213688669, g=4))[source]#

Derive count generators of the order-q subgroup whose mutual logs nobody knows.

Each one hashes the group, a label and an index into the subgroup, as pedersen_generators() does for one. Vector commitments need them: whoever knew a relation between two generators could open a commitment two ways.

>>> from blockchainkit.proofs import independent_generators
>>> len(set(independent_generators(8, "demo")))
8
Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.utils.groups.multi_exponent(bases, exponents, group)[source]#

Return the product of base**exponent modulo p: a vector commitment.

Parameters:
Return type:

int

blockchainkit.proofs.utils.groups.linear_combination(scalars, points, curve)[source]#

Return the sum of scalar * point on a curve (a multi-scalar multiplication).

Parameters:
Return type:

tuple[int, int] | None

Interactive proofs#

The Schwartz-Zippel lemma: testing polynomial identities at random points (1980).

Two different polynomials of total degree at most d agree on at most a d / p fraction of the points of F^n. To test whether two expressions define the same polynomial, evaluate both at a random point: if they are equal the test always passes, and if not it fails with probability at least 1 - d / p. Every proof system in this subpackage reduces its statement to such a test.

blockchainkit.proofs.systems.identity.schwartz_zippel_bound(total_degree, field_size)[source]#

Return d / p, the most that two distinct polynomials agree on a random point.

>>> from blockchainkit.proofs import schwartz_zippel_bound
>>> schwartz_zippel_bound(3, 97)
0.030927835051546393
Parameters:

  • total_degree (int)

  • field_size (int)

Return type:

float

blockchainkit.proofs.systems.identity.identity_test(left, right, num_variables, prime=2013265921, *, trials=1, seed=0)[source]#

Test whether two polynomial functions are equal by evaluating them at random points.

Parameters:

  • left (collections.abc.Callable) – Each takes a sequence of num_variables field elements and returns an integer; they are compared modulo prime.

  • right (collections.abc.Callable) – Each takes a sequence of num_variables field elements and returns an integer; they are compared modulo prime.

  • num_variables (int) – Number of variables.

  • prime (int) – Field modulus.

  • trials (int) – Independent random points to try.

  • seed (int) – Seed of the verifier’s randomness.

Returns:

equal is False as soon as a point separates them.

Return type:

blockchainkit.proofs.core.base.IdentityTest

Examples

>>> from blockchainkit.proofs import identity_test
>>> square = lambda v: (v[0] + v[1]) ** 2
>>> expanded = lambda v: v[0] ** 2 + 2 * v[0] * v[1] + v[1] ** 2
>>> identity_test(square, expanded, 2).equal
True
>>> identity_test(square, lambda v: v[0] ** 2 + v[1] ** 2, 2).equal
False

The sum-check protocol of Lund, Fortnow, Karloff and Nisan (1990).

A prover claims that a polynomial f in n variables sums to H over the Boolean cube {0, 1}**n. Summing directly takes 2**n evaluations. In round i, the prover instead sends the univariate polynomial

g_i(X) = sum of f(r_1, …, r_{i-1}, X, b_{i+1}, …, b_n) over the bs,

the verifier checks g_i(0) + g_i(1) against the previous claim and fixes X to a random r_i. After n rounds the verifier evaluates f once, at (r_1, …, r_n). A false claim survives each round with probability at most d / p (Schwartz-Zippel), so with probability at most n d / p.

blockchainkit.proofs.systems.sumcheck.multilinear_extension(values, point, prime=2013265921)[source]#

Evaluate the multilinear extension of a table of 2**n values at a field point.

The extension is the unique polynomial of degree at most one in each variable that takes values[b] at each Boolean vector b, read as a binary number with the first variable most significant.

>>> from blockchainkit.proofs import multilinear_extension
>>> multilinear_extension([3, 5, 7, 9], [1, 0], 97)  # the table entry at b = 10
7
>>> multilinear_extension([3, 5, 7, 9], [2, 0], 97)  # 3 + 4 * x1 + 2 * x2, beyond the cube
11
Parameters:
Return type:

int

blockchainkit.proofs.systems.sumcheck.sumcheck(f, num_variables, degree, prime=2013265921, *, claim=None, seed=0)[source]#

Run the sum-check protocol for the sum of f over {0, 1}**n.

The prover is honest when claim is the true sum (the default). Given a false claim, it lies as well as it can: each round’s polynomial is consistent with the previous claim and differs from the true one by a polynomial with degree roots, in case the verifier picks one.

Parameters:

  • f (collections.abc.Callable) – A polynomial function of num_variables field elements, of degree at most degree in each variable.

  • num_variables (int) – Number of variables n.

  • degree (int) – The degree bound the verifier enforces on each round’s polynomial.

  • prime (int) – Field modulus.

  • claim (int, optional) – The sum the prover asserts.

  • seed (int) – Seed of the verifier’s random challenges.

Return type:

blockchainkit.proofs.core.base.SumcheckRun

Examples

>>> from blockchainkit.proofs import CNF, sumcheck
>>> formula = CNF(3, ((1, 2), (-2, 3)))
>>> run = sumcheck(lambda x: formula.evaluate(x, 97), 3, formula.degree, 97)
>>> run.claim, run.accepted
(4, True)
>>> sumcheck(lambda x: formula.evaluate(x, 97), 3, formula.degree, 97, claim=5).accepted
False
blockchainkit.proofs.systems.sumcheck.verify_sumcheck(f, claim, polynomials, challenges, degree, prime=2013265921)[source]#

Check a sum-check transcript: the verifier’s side of sumcheck().

Each polynomial must have degree at most degree and satisfy g_i(0) + g_i(1) = g_{i-1}(r_{i-1}) (the claim for i = 1); finally g_n(r_n) must equal f(r_1, ..., r_n), the one evaluation of f the verifier makes. The verifier is sound only if each challenge was drawn after its polynomial was sent.

Parameters:
Return type:

bool

Shamir’s IP = PSPACE: an interactive proof for quantified Boolean formulas (1990).

A quantified formula such as “for all x, there exists y: phi(x, y)” is arithmetized like a CNF, with “for all” becoming a product, A f = f(0) f(1), and “there exists” a complemented product, E f = 1 - (1 - f(0))(1 - f(1)). The prover convinces the verifier of the formula’s value by sum-check-style rounds, one per operator, peeling operators from the outside in.

Each product doubles degrees, so after n quantifiers the polynomials would have degree about 2**n. Shen’s linearization operator, L_i f = (1 - x_i) f(x_i = 0) + x_i f(x_i = 1), which agrees with f on 0/1 inputs and is linear in x_i, is inserted after every quantifier to keep every polynomial of degree at most max(2, degree of phi).

blockchainkit.proofs.systems.ip_pspace.tqbf_operators(qbf, *, linearize=True)[source]#

List the arithmetized operators of a formula from the outside in.

With linearization, the quantifier on x_i is followed by L_1, ..., L_i: the order of Shen’s proof.

>>> from blockchainkit.proofs import CNF, QBF, tqbf_operators
>>> tqbf_operators(QBF("AE", CNF(2, ((1, 2),))))
(('A', 1), ('L', 1), ('E', 2), ('L', 1), ('L', 2))
Parameters:
Return type:

tuple[tuple[str, int], …]

blockchainkit.proofs.systems.ip_pspace.tqbf_protocol(qbf, prime=2013265921, *, claim=None, seed=0, linearize=True)[source]#

Run the interactive proof of a quantified Boolean formula’s value.

The prover evaluates every inner expression by brute force, which is exponential but needs only polynomial space; the verifier does polynomial work. A false claim survives with probability at most (rounds * degree) / prime.

Parameters:

  • qbf (blockchainkit.proofs.core.base.QBF) – The formula.

  • prime (int) – Field modulus.

  • claim (int, optional) – The value the prover asserts, 1 (true) or 0 (false); the true value by default. A false claim makes the prover lie as well as it can.

  • seed (int) – Seed of the verifier’s challenges.

  • linearize (bool) – Insert Shen’s linearization operators. Without them the protocol is still sound but the degrees grow exponentially.

Return type:

blockchainkit.proofs.core.base.TQBFRun

Examples

>>> from blockchainkit.proofs import CNF, QBF, tqbf_protocol
>>> formula = QBF("AE", CNF(2, ((1, 2), (-1, -2))))
>>> tqbf_protocol(formula).accepted, tqbf_protocol(formula, claim=0).accepted
(True, False)

PCPs and arguments#

Probabilistically checkable proofs: the Hadamard PCP for quadratic equations (1992).

The PCP theorem (Arora and Safra; Arora, Lund, Motwani, Sudan and Szegedy, 1992) says every NP statement has a proof that a verifier checks by reading a constant number of its bits, chosen at random, and rejecting a false statement with constant probability. This module implements the first step of the ALMSS proof: an exponentially long proof checked with 14 queries.

The statement is that a system of quadratic equations over GF(2) has a solution u. The proof writes out the Hadamard encodings of u and of u (x) u: every parity <u, x> and every <u (x) u, y>. The verifier tests that both tables are linear functions (Blum, Luby and Rubinfeld, 1990), that the second is the tensor square of the first, and that a random combination of the equations holds, reading each table through self-correction, f(x) = f(x + s) - f(s), so that a few corrupted entries cannot be targeted.

blockchainkit.proofs.systems.pcp.Oracle#

Reads one bit of a proof at a position of the concatenated tables.

alias of Callable[[int], int]

blockchainkit.proofs.systems.pcp.hadamard_proof(assignment)[source]#

Encode an assignment u as the tables of <u, x> and <u (x) u, y>.

Parameters:

assignment (collections.abc.Sequence of int) – Between 1 and 4 bits; the second table has 2**(n**2) entries.

Return type:

HadamardProof

Examples

>>> from blockchainkit.proofs import hadamard_proof
>>> proof = hadamard_proof([1, 0, 1])
>>> len(proof.linear), len(proof.quadratic)
(8, 512)
blockchainkit.proofs.systems.pcp.run_pcp_verifier(system, oracle, rng, repetitions)[source]#

Run the Hadamard PCP verifier against any proof oracle.

Positions below 2**n read the linear table; position 2**n + y reads entry y of the quadratic table. Each repetition makes 14 queries: linearity of both tables (3 + 3), tensor consistency (6), and one random combination of the equations (2).

Parameters:
Return type:

PCPRun

blockchainkit.proofs.systems.pcp.pcp_verify(system, proof, *, repetitions=1, seed=0)[source]#

Check a Hadamard proof by reading 14 random bits per repetition.

A correct proof of a satisfiable system always passes. If the system has no solution, every proof is rejected with constant probability per repetition, so repetitions drives the error down exponentially.

Examples

>>> from blockchainkit.proofs import QuadraticSystem, hadamard_proof, pcp_verify
>>> system = QuadraticSystem(2, ((((0, 1),), 1), (((0, 0),), 1)))  # u0 u1 = 1, u0 = 1
>>> pcp_verify(system, hadamard_proof([1, 1]), repetitions=10).accepted
True
Parameters:
Return type:

PCPRun

Succinct arguments from Merkle commitments: Kilian (1992) and Micali’s CS proofs (1994).

A PCP is short to check but long to send: the Hadamard proof of an n-variable system has 2**n + 2**(n**2) bits. Kilian’s argument sends only a Merkle root of the PCP. The verifier then picks its random queries, and the prover opens each queried bit with its authentication path. The prover cannot change an answer after committing without finding a hash collision, so communication drops to the root plus a logarithmic path per query.

Micali removed the interaction: the queries are derived by hashing the root, so the prover writes the whole argument down at once, a computationally sound proof. Soundness then rests on the hash behaving like a random oracle, and a cheating prover can grind: change the commitment (here, a salt) and rehash until the queries miss its lies.

blockchainkit.proofs.systems.kilian.commit_pcp(proof)[source]#

Build a Merkle tree whose leaf i is bit i of the PCP, one byte per leaf.

Parameters:

proof (HadamardProof)

Return type:

MerkleTree

blockchainkit.proofs.systems.kilian.kilian_argument(system, proof, *, repetitions=1, seed=0, respond=None)[source]#

Run Kilian’s interactive argument for a quadratic system.

The prover commits to proof and sends the root; the verifier then draws the PCP queries from seed; the prover answers each with a bit and the Merkle path of the committed bit.

Parameters:
Return type:

blockchainkit.proofs.core.base.KilianRun

Examples

>>> from blockchainkit.proofs import QuadraticSystem, hadamard_proof, kilian_argument
>>> system = QuadraticSystem(3, ((((0, 1), (2, 2)), 1),))
>>> run = kilian_argument(system, hadamard_proof([1, 1, 0]), repetitions=4)
>>> run.accepted, run.queries
(True, 56)
blockchainkit.proofs.systems.kilian.micali_proof(system, proof, *, repetitions=1, salt=0)[source]#

Write a non-interactive CS proof: the queries come from hashing the root and a salt.

Examples

>>> from blockchainkit.proofs import (
...     QuadraticSystem, hadamard_proof, micali_proof, verify_cs_proof)
>>> system = QuadraticSystem(3, ((((0, 1), (2, 2)), 1),))
>>> cs = micali_proof(system, hadamard_proof([1, 1, 0]), repetitions=4)
>>> verify_cs_proof(system, cs, repetitions=4)
True
Parameters:
Return type:

CSProof

blockchainkit.proofs.systems.kilian.verify_cs_proof(system, cs_proof, *, repetitions=1)[source]#

Re-derive the queries from the root and salt, and check every opening and PCP test.

Parameters:
Return type:

bool

Pairings and polynomial commitments#

A toy bilinear pairing on a supersingular curve, the engine of KZG, Groth16 and PLONK.

A pairing is a map e from two copies of a group of prime order r into a third, with e(aP, bQ) = e(P, Q)**(a b). It lets a verifier check one multiplication between hidden exponents, which is what every pairing-based SNARK needs.

The curve y**2 = x**3 + x over F_p, with p = 3 mod 4, is supersingular: it has p + 1 points, and its pairing values live in F_(p**2), the complex-like numbers a + b i with i**2 = -1. The distortion map (x, y) -> (-x, i y) makes the reduced Tate pairing, computed by Miller’s algorithm, symmetric and nondegenerate on the subgroup of order r. This is the Boneh-Franklin construction (2001) with r = 2013265921, the BabyBear prime, and p = 12 r - 1, a 35-bit prime. Discrete logarithms in a group that small take seconds, so this curve teaches the algebra and nothing about security; deployed systems use BN254 or BLS12-381.

blockchainkit.proofs.systems.pairing.GTElement#

An element a + b i of F_(p**2), as (a, b).

alias of tuple[int, int]

blockchainkit.proofs.systems.pairing.PAIRING_CURVE = Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing')#

y**2 = x**3 + x over the prime 12 * 2013265921 - 1, with a generator of order 2013265921 (the BabyBear field prime, so scalars are elements of FIELD_PRIME).

Type:

Curve

blockchainkit.proofs.systems.pairing.pairing(left, right, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Compute the reduced Tate pairing e(left, distort(right)).

Parameters:

  • left (Point) – Points of the order-r subgroup; the point at infinity pairs to 1.

  • right (Point) – Points of the order-r subgroup; the point at infinity pairs to 1.

  • curve (blockchainkit.crypto.systems.curves.Curve) – A supersingular curve y**2 = x**3 + x with p = 3 mod 4.

Returns:

An r-th root of unity in F_(p**2).

Return type:

GTElement

Examples

>>> from blockchainkit.proofs import PAIRING_CURVE as E, pairing, gt_power
>>> from blockchainkit.crypto import multiply
>>> G = E.generator
>>> pairing(multiply(3, G, E), multiply(5, G, E)) == gt_power(pairing(G, G), 15)
True
blockchainkit.proofs.systems.pairing.gt_multiply(left, right, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Multiply two pairing values in F_(p**2).

Parameters:
Return type:

tuple[int, int]

blockchainkit.proofs.systems.pairing.gt_power(element, exponent, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Raise a pairing value to an integer power, reduced modulo the group order.

Parameters:
Return type:

tuple[int, int]

Kate-Zaverucha-Goldberg polynomial commitments (2010).

A trusted setup publishes [tau**i] G for a secret tau and then forgets tau. A commitment to f is the single point C = [f(tau)] G, computed from the published powers without knowing tau. To prove f(z) = y, the prover sends W = [q(tau)] G for the quotient

q(X) = (f(X) - y) / (X - z),

which is a polynomial exactly when f(z) = y. The verifier checks the divisibility at the hidden point tau with one pairing equation,

e(C - [y] G, G) = e(W, [tau] G - [z] G).

Commitments and openings are one group element each, whatever the degree. Whoever knows tau can open a commitment to any value: see forge_opening().

blockchainkit.proofs.systems.kzg.trusted_setup(max_degree, secret, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Publish [secret**i] G for i up to max_degree: a structured reference string.

secret is the toxic waste tau. A single party running this knows it; contribute() spreads it over many parties so that one honest one suffices.

>>> from blockchainkit.proofs import trusted_setup
>>> trusted_setup(4, secret=1234).max_degree
4
Parameters:
Return type:

SRS

blockchainkit.proofs.systems.kzg.kzg_commit(poly, srs)[source]#

Commit to a polynomial: [f(tau)] G, a linear combination of the published powers.

Examples

>>> from blockchainkit.proofs import trusted_setup, kzg_commit, kzg_open, kzg_verify
>>> srs = trusted_setup(4, secret=1234)
>>> commitment = kzg_commit([5, 0, 1], srs)  # 5 + x**2
>>> opening = kzg_open([5, 0, 1], 3, srs)
>>> opening.value, kzg_verify(commitment, opening, srs)
(14, True)
Parameters:
Return type:

tuple[int, int] | None

blockchainkit.proofs.systems.kzg.kzg_open(poly, point, srs)[source]#

Evaluate at point and prove it with a commitment to the quotient polynomial.

Parameters:
Return type:

KZGOpening

blockchainkit.proofs.systems.kzg.kzg_verify(commitment, opening, srs)[source]#

Check e(C - [y] G, G) = e(W, [tau] G - [z] G); malformed inputs return False.

Parameters:
Return type:

bool

blockchainkit.proofs.systems.kzg.forge_opening(commitment, point, value, secret, srs)[source]#

Open a commitment to any value, using the toxic waste tau.

W = (C - [y] G) / (tau - z) satisfies the verification equation whatever y is, so a party that kept tau can prove false evaluations. This is why the setup’s secret must be destroyed.

Parameters:
Return type:

KZGOpening

Trusted-setup ceremonies: Zcash’s parameter generation (2016) and the powers of tau.

A pairing-based SNARK needs [tau**i] G for a tau nobody knows. In a ceremony, each participant in turn multiplies the current string by its own secret s, raising every power to (tau s)**i, and then destroys s. The final tau is the product of all the secrets, so it stays unknown unless every participant kept theirs: one honest participant is enough.

Anyone can check each contribution with pairings: it publishes [s] G, and the new string must satisfy

e(new_1, G) = e(old_1, [s] G) and e(new_(i+1), G) = e(new_i, new_1),

the first proving the update used s, the second that the result is still a list of consecutive powers. Bowe, Gabizon and Miers (2017) made the ceremony scale to any number of participants, as Zcash’s Powers of Tau (2017-2018) and Ethereum’s KZG ceremony (2023) did.

blockchainkit.proofs.systems.ceremony.start_ceremony(max_degree, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Return the trivial string with tau = 1: every power is the generator.

>>> from blockchainkit.proofs import start_ceremony, contribute, verify_contribution
>>> srs = start_ceremony(4)
>>> step = contribute(srs, 1234)
>>> verify_contribution(srs, step)
True
Parameters:
Return type:

SRS

blockchainkit.proofs.systems.ceremony.contribute(srs, secret)[source]#

Multiply the hidden tau by secret: power i is multiplied by secret**i.

The participant publishes the new string and [secret] G, then must forget secret.

Parameters:
Return type:

Contribution

blockchainkit.proofs.systems.ceremony.verify_contribution(before, contribution)[source]#

Check with pairings that a contribution updated before by a known secret.

It fails if the new string is not a list of consecutive powers, if it does not build on before, or if the contribution is degenerate.

Parameters:
Return type:

bool

Circuits and SNARKs#

Arithmetic circuits and rank-1 constraint systems (R1CS).

SNARKs prove statements written as arithmetic over a prime field. A rank-1 constraint system lists constraints of the form

<a_j, z> * <b_j, z> = <c_j, z>,

over a witness vector z = (1, public inputs, private values). Additions and multiplications by constants are free: they only change the linear combinations. Each multiplication of two unknowns costs one constraint.

Circuit builds an R1CS while computing the witness: a Wire is a linear combination of variables that also carries its value, so x * x * x + x + 5 written with Circuit.mul() produces both the constraints and the satisfying assignment.

class blockchainkit.proofs.systems.circuits.Wire(terms, value, prime)[source]#

Bases: object

A linear combination of circuit variables, and its value in the current witness.

Wires support +, -, negation, and multiplication by an integer constant. Multiplying two wires is a constraint: use Circuit.mul().

Parameters:
terms#
value#
prime#
class blockchainkit.proofs.systems.circuits.Circuit(prime=2013265921)[source]#

Bases: object

Build an R1CS and its witness together.

Declare every public input first, then private inputs and gates. The witness vector is (1, public..., private...).

Parameters:

prime (int) – Field modulus; defaults to the BabyBear prime, the scalar field of PAIRING_CURVE.

Examples

>>> from blockchainkit.proofs import Circuit
>>> circuit = Circuit()
>>> out = circuit.public(35)
>>> x = circuit.private(3)
>>> x3 = circuit.mul(circuit.mul(x, x), x)
>>> circuit.assert_equal(x3 + x + 5, out)
>>> r1cs = circuit.r1cs()
>>> r1cs.num_constraints, r1cs.is_satisfied(circuit.witness())
(5, True)
property one: Wire#

The constant 1, variable 0 of every witness.

property num_constraints: int#

Constraints so far, not counting the public-input rows r1cs() adds.

public(value)[source]#

Declare a public input with its value.

Parameters:

value (int)

Return type:

Wire

private(value)[source]#

Declare a private input (part of the witness only the prover knows).

Parameters:

value (int)

Return type:

Wire

assert_product(left, right, output)[source]#

Add the constraint left * right = output.

Parameters:
Return type:

None

mul(left, right)[source]#

Return a new variable constrained to equal left * right.

Parameters:
Return type:

Wire

assert_equal(left, right)[source]#

Add the constraint (left - right) * 1 = 0.

Parameters:
Return type:

None

assert_boolean(wire)[source]#

Add the constraint wire * (1 - wire) = 0: the wire is 0 or 1.

Parameters:

wire (Wire)

Return type:

None

witness()[source]#

Return (1, public..., private...).

Return type:

tuple[int, …]

public_inputs()[source]#

Return the public inputs, without the leading 1.

Return type:

tuple[int, …]

r1cs()[source]#

Freeze the constraints into an R1CS.

One row x_i * 0 = 0 is appended for the constant and for each public input, as Bellman and snarkjs do: it makes the public inputs’ polynomials linearly independent, so a Groth16 proof binds them even if a public input appears in no other constraint.

Return type:

R1CS

Quadratic arithmetic programs: Gennaro, Gentry, Parno and Raykova (2013), used by Pinocchio.

An R1CS with m constraints is m separate equations. A QAP turns them into one polynomial identity. Assign constraint j to the point w**j of a power-of-two domain, and let A_i(X) interpolate column i of the first matrix over the domain (likewise B_i and C_i). For a witness z,

A(X) = sum z_i A_i(X), B(X) = sum z_i B_i(X), C(X) = sum z_i C_i(X)

agree with the constraint values at each w**j, so every constraint holds exactly when A(X) B(X) - C(X) vanishes on the whole domain, that is, when it is divisible by the target t(X) = X**n - 1:

A(X) B(X) - C(X) = H(X) t(X).

Pinocchio (Parno, Howell, Gentry and Raykova, 2013) checked this divisibility at one secret point with pairings, giving the first practical general-purpose SNARK; Groth16 refined it.

blockchainkit.proofs.systems.qap.domain_size(r1cs)[source]#

The smallest power of two, at least 2, that holds one point per constraint.

Parameters:

r1cs (R1CS)

Return type:

int

blockchainkit.proofs.systems.qap.r1cs_to_qap(r1cs)[source]#

Interpolate each column of the R1CS matrices over the domain of roots of unity.

Examples

>>> from blockchainkit.proofs import Circuit, r1cs_to_qap, qap_divide
>>> circuit = Circuit()
>>> out, x = circuit.public(35), circuit.private(3)
>>> circuit.assert_equal(circuit.mul(circuit.mul(x, x), x) + x + 5, out)
>>> qap = r1cs_to_qap(circuit.r1cs())
>>> qap.domain_size, qap_divide(qap, circuit.witness()).satisfied
(8, True)
Parameters:

r1cs (R1CS)

Return type:

QAP

blockchainkit.proofs.systems.qap.qap_divide(qap, witness)[source]#

Form A, B and C for a witness and divide A B - C by the target polynomial.

The witness satisfies the R1CS exactly when the remainder is zero.

Parameters:
Return type:

QAPDivision

Groth’s succinct non-interactive argument (2016): three group elements per proof.

The setup encodes the QAP of a circuit at a secret point tau, blinded by secrets alpha, beta, gamma and delta. With prover randomness r and s,

A = alpha + sum z_i A_i(tau) + r delta, B = beta + sum z_i B_i(tau) + s delta, C = (sum over private i of z_i K_i(tau) + H(tau) t(tau)) / delta + s A + r B - r s delta,

and the verifier checks one pairing equation,

e(A, B) = e(alpha, beta) e(sum over public i of x_i L_i, gamma) e(C, delta),

which holds, by the QAP identity, exactly when A B - C is divisible by the target. Proofs are three points and verification three pairings plus one per public input, whatever the circuit; r and s make every proof a fresh, zero-knowledge one.

This implementation uses the symmetric toy pairing of pairing, so A, B and C lie in one group; Groth’s paper and deployments use asymmetric pairings, with B in a second group.

blockchainkit.proofs.systems.groth16.groth16_setup(r1cs, trapdoor, curve=Curve(p=24159191051, a=1, b=0, generator=(4010265589, 9478310149), order=2013265921, name='toy-pairing'))[source]#

Encode a circuit’s QAP at the trapdoor’s secret point.

The QAP polynomials are evaluated at tau directly through the Lagrange basis of the domain, L_j(tau) = (tau**n - 1) w**j / (n (tau - w**j)), without ever writing them out.

Parameters:
Returns:

Its verifying_key attribute is the verifier’s key.

Return type:

blockchainkit.proofs.core.base.ProvingKey

blockchainkit.proofs.systems.groth16.groth16_prove(proving_key, witness, *, seed=0)[source]#

Prove that witness satisfies the circuit, revealing only its public inputs.

Parameters:
Raises:

ValueError – The witness does not satisfy the circuit.

Return type:

Groth16Proof

blockchainkit.proofs.systems.groth16.groth16_verify(verifying_key, public_inputs, proof)[source]#

Check e(A, B) = e(alpha, beta) e(L, gamma) e(C, delta); malformed proofs return False.

Examples

>>> from blockchainkit.proofs import (Circuit, Groth16Trapdoor, groth16_setup,
...     groth16_prove, groth16_verify)
>>> circuit = Circuit()
>>> out, x = circuit.public(35), circuit.private(3)
>>> circuit.assert_equal(circuit.mul(circuit.mul(x, x), x) + x + 5, out)
>>> key = groth16_setup(circuit.r1cs(), Groth16Trapdoor(11, 22, 33, 44, 55))
>>> proof = groth16_prove(key, circuit.witness(), seed=1)
>>> vk = key.verifying_key
>>> groth16_verify(vk, [35], proof), groth16_verify(vk, [36], proof)
(True, False)
Parameters:
Return type:

bool

PLONK: gates, permutation arguments and a universal setup (2019).

Gabizon, Williamson and Ciobotaru wrote a circuit as n gates, each

q_L a + q_R b + q_O c + q_M a b + q_C = 0,

over the gate’s left, right and output wires a, b, c, with the selectors q fixing the gate’s kind. That a wire carries the same value in two gates is a separate copy constraint: the wire values must be unchanged by a permutation sigma of the 3n wire positions. PLONK checks it with a grand product. With random beta and gamma,

prod over positions (w + beta id + gamma) = prod over positions (w + beta sigma + gamma)

holds whp only if the values are constant on every cycle of sigma. The prover builds the running product z(X) over the domain, z(1) = 1 and

z(w X) prod (w_k + beta sigma_k(X) + gamma) = z(X) prod (w_k + beta k_k X + gamma),

so gates, copies, and z(1) = 1 all become polynomial identities that vanish on the domain, combined with powers of a random alpha and divided by X**n - 1. Every polynomial is a KZG commitment, opened at a random zeta. Unlike Groth16, the setup is universal: one powers-of-tau string serves every circuit up to its size.

This version opens every polynomial at zeta instead of using PLONK’s linearization, and adds no blinding, so it is succinct and sound but not zero-knowledge. There are no public inputs: constants go in q_C.

blockchainkit.proofs.systems.plonk.K1 = 31#

The coset shifts that label the right and output wire columns.

blockchainkit.proofs.systems.plonk.K2 = 961#

The coset shifts that label the right and output wire columns.

class blockchainkit.proofs.systems.plonk.PlonkCircuit(prime=2013265921)[source]#

Bases: object

Build PLONK gates over numbered variables.

Examples

>>> from blockchainkit.proofs import PlonkCircuit
>>> circuit = PlonkCircuit()
>>> x = circuit.variable(3)
>>> x3 = circuit.mul(circuit.mul(x, x), x)
>>> circuit.assert_constant(circuit.add(x3, x), 30)  # x**3 + x = 30
>>> len(circuit.gates), circuit.is_satisfied()
(4, True)
Parameters:

prime (int)

values: list[int]#
gates: list[tuple[tuple[int, int, int], tuple[int, int, int, int, int]]]#
variable(value)[source]#

Add a variable holding value; return its index.

Parameters:

value (int)

Return type:

int

gate(left, right, output, *, ql=0, qr=0, qo=0, qm=0, qc=0)[source]#

Add the gate ql a + qr b + qo c + qm a b + qc = 0 on three variables.

Parameters:
Return type:

None

add(left, right)[source]#

Return a new variable constrained to left + right.

Parameters:
Return type:

int

mul(left, right)[source]#

Return a new variable constrained to left * right.

Parameters:
Return type:

int

assert_constant(variable, value)[source]#

Add the gate variable - value = 0.

Parameters:
Return type:

None

wire_values()[source]#

The values on each gate’s left, right and output wires.

Return type:

tuple[tuple[int, int, int], …]

is_satisfied()[source]#

Whether every gate equation holds.

Return type:

bool

blockchainkit.proofs.systems.plonk.plonk_setup(circuit, srs)[source]#

Preprocess a circuit: interpolate and commit to its selectors and permutation.

The same srs serves every circuit whose padded size n satisfies 3 n <= srs.max_degree.

Parameters:
Return type:

PlonkKey

blockchainkit.proofs.systems.plonk.permutation_product(key, rows, beta, gamma)[source]#

Return the running product z_0 = 1, z_1, …, z_n of the copy-constraint argument.

The last value is 1 when every copy constraint holds, and differs from 1 whp otherwise.

Parameters:
Return type:

tuple[int, …]

blockchainkit.proofs.systems.plonk.plonk_prove(key, srs, rows)[source]#

Prove that wire values satisfy the gates and the copy constraints.

Parameters:
Raises:

ValueError – A gate fails, or a copy constraint fails (the running product does not return to 1).

Return type:

PlonkProof

Examples

>>> from blockchainkit.proofs import (PlonkCircuit, plonk_setup, plonk_prove,
...     plonk_verify, trusted_setup)
>>> circuit = PlonkCircuit()
>>> x = circuit.variable(3)
>>> circuit.assert_constant(circuit.add(circuit.mul(circuit.mul(x, x), x), x), 30)
>>> srs = trusted_setup(12, secret=4321)
>>> key = plonk_setup(circuit, srs)
>>> plonk_verify(key, srs, plonk_prove(key, srs, circuit.wire_values()))
True
blockchainkit.proofs.systems.plonk.plonk_verify(key, srs, proof)[source]#

Recompute the challenges, check the identity at zeta, and check both batched openings.

Parameters:
Return type:

bool

Zerocash: private payments from notes, nullifiers and a SNARK (2014).

Ben-Sasson, Chiesa, Garman, Green, Miers, Tromer and Virza hid the sender, receiver and amount of every payment. Coins are notes (owner, value, rho, r), and the ledger stores only their hiding commitments, in a Merkle tree. To spend a note, its owner publishes

  • its nullifier PRF_sk(rho), which the ledger records so the note cannot be spent twice, yet which nobody can link to the commitment,

  • the commitment to a new note for the payee, and

  • a zk-SNARK that some commitment in the tree opens to a note owned by the spender, with this nullifier and enough value for the new note.

The ledger learns that some unspent note paid someone, and nothing else.

This model uses Groth16 on the toy pairing, MiMC (Albrecht et al., 2016) as the arithmetic-friendly hash, and one input and one output per spend, with a public amount leaving the pool. Zerocash used SHA-256 inside its circuits, two inputs and two outputs per transaction, and encryption of the new note for the payee.

blockchainkit.proofs.systems.zerocash.MIMC_ROUNDS = 12#

Rounds of MiMC-7 over the BabyBear field: ceil(log_7 p).

Type:

int

blockchainkit.proofs.systems.zerocash.VALUE_BITS = 16#

Note values are range-checked to this many bits inside the circuit.

Type:

int

blockchainkit.proofs.systems.zerocash.mimc_hash(left, right, prime=2013265921)[source]#

Compress two field elements with MiMC-7 in Miyaguchi-Preneel mode.

Each round computes x = (x + key + c_i)**7 with key = left, starting from x = right; the output is x + 2 key + right. Seven is the smallest exponent coprime to p - 1, so each round permutes the field, and it costs four multiplications in a circuit.

>>> from blockchainkit.proofs import mimc_hash
>>> mimc_hash(1, 2) == mimc_hash(1, 2) != mimc_hash(2, 1)
True
Parameters:
Return type:

int

blockchainkit.proofs.systems.zerocash.mimc_gadget(circuit, left, right)[source]#

Constrain a new wire to mimc_hash(left, right): 4 constraints per round.

Parameters:
Return type:

Wire

blockchainkit.proofs.systems.zerocash.owner_key(secret_key)[source]#

The public address of a spending key: H(sk, 0).

Parameters:

secret_key (int)

Return type:

int

blockchainkit.proofs.systems.zerocash.note_commitment(note)[source]#

H(H(owner, value), H(rho, r)): hiding thanks to r, binding thanks to the hash.

Parameters:

note (Note)

Return type:

int

blockchainkit.proofs.systems.zerocash.nullifier(secret_key, rho)[source]#

H(sk, rho): only the owner can compute it, and it reveals nothing about the note.

Parameters:
Return type:

int

blockchainkit.proofs.systems.zerocash.spend_circuit(depth, secret_key, note, siblings, index, new_note, public_value)[source]#

Build the spend statement and its witness.

Public inputs: the Merkle root, the nullifier, the new commitment and the amount leaving the pool. The circuit checks that the spender owns the note, that its commitment is a leaf on the path to the root, that the nullifier is derived from it, that the new commitment is well formed, and that value = new value + public value with the new value in [0, 2**16). Without that range check, a “negative” new value p - k would mint k coins.

Parameters:
Return type:

Circuit

blockchainkit.proofs.systems.zerocash.spend_setup(depth, trapdoor)[source]#

Run the Groth16 setup for the spend circuit of a tree of the given depth.

Parameters:
Return type:

ProvingKey

class blockchainkit.proofs.systems.zerocash.ShieldedPool(depth, verifying_key)[source]#

Bases: object

The ledger side of Zerocash: commitments, nullifiers, and proof checks.

Parameters:

Examples

>>> from blockchainkit.proofs import (Groth16Trapdoor, Note, ShieldedPool, owner_key,
...     prove_spend, spend_setup)
>>> key = spend_setup(2, Groth16Trapdoor(5, 6, 7, 8, 9))
>>> pool = ShieldedPool(2, key.verifying_key)
>>> alice, bob = 1111, 2222
>>> coin = Note(owner_key(alice), 100, rho=1, randomness=77)
>>> index = pool.mint(coin)
>>> payment = Note(owner_key(bob), 60, rho=2, randomness=88)
>>> spend = prove_spend(key, pool, alice, coin, index, payment, public_value=40)
>>> pool.spend(spend), pool.supply
(1, 60)
property commitments: tuple[int, ...]#

Every note commitment in order, which is all an observer sees of the notes.

property nullifiers: frozenset[int]#

The nullifiers of spent notes.

property root: int#

The current root of the commitment tree.

mint(note)[source]#

Deposit public value into a new note; the value is visible, the owner is not.

Parameters:

note (Note)

Return type:

int

siblings(index)[source]#

The Merkle path of a note: the sibling hash at each level.

Parameters:

index (int)

Return type:

tuple[int, …]

spend(transaction)[source]#

Check a spend and record it; return the new note’s index.

Raises:

ValueError – Unknown root, reused nullifier, amount out of range, or invalid proof.

Parameters:

transaction (SpendTransaction)

Return type:

int

blockchainkit.proofs.systems.zerocash.prove_spend(proving_key, pool, secret_key, note, index, new_note, public_value, *, seed=0)[source]#

Spend note (at index in the pool) into new_note plus a public amount.

Raises:

ValueError – The statement is false: a key that does not own the note, values that do not balance, or a new value outside [0, 2**16).

Parameters:
Return type:

SpendTransaction

Transparent proofs#

Bulletproofs: short range proofs without a trusted setup (2018).

Confidential amounts hide a value v in a Pedersen commitment V = g**v h**gamma, which is useless unless the value is shown to lie in [0, 2**n): otherwise a “negative” output mints money. Bünz, Bootle, Boneh, Poelstra, Wuille and Maxwell write v’s bits as a vector a_L, set a_R = a_L - 1, and reduce the three facts

<a_L, 2**n> = v, a_L o a_R = 0, a_L - a_R - 1 = 0

with random challenges y and z to one inner product t = <l, r>. The prover commits to l and r with vectors of independent generators, and proves the inner product by halving: each round it sends two group elements L and R, the verifier sends a challenge x, and both fold the vectors and generators to half their length,

a’ = x a_lo + x**-1 a_hi, G’ = G_lo**(x**-1) o G_hi**x.

After log2(n) rounds one scalar pair remains: a proof of 2 log2(n) + 4 group elements and 5 scalars, with no trusted setup, because the generators are hashed into the group (Bootle, Cerulli, Chaidos, Groth and Petit, 2016).

This version works in the 62-bit Schnorr group TEACHING_GROUP (multiplicatively); deployments use elliptic curves such as Curve25519.

blockchainkit.proofs.systems.bulletproofs.range_commitment(value, blinding)[source]#

The Pedersen commitment g**value h**blinding that a range proof is about.

Parameters:
Return type:

int

blockchainkit.proofs.systems.bulletproofs.range_proof(value, blinding, bits=32, *, seed=0)[source]#

Prove that the commitment to value hides a number in [0, 2**bits).

Parameters:

  • value (int) – The hidden amount.

  • blinding (int) – The commitment’s randomness gamma.

  • bits (int) – A power of two up to 64.

  • seed (int) – Seed of the prover’s blinding vectors and scalars.

Raises:

ValueError – value is not below 2**bits: no proof exists.

Return type:

RangeProof

Examples

>>> from blockchainkit.proofs import range_proof, verify_range_proof
>>> proof = range_proof(1000, blinding=77, bits=16)
>>> verify_range_proof(proof, bits=16), len(proof.left)
(True, 4)
blockchainkit.proofs.systems.bulletproofs.verify_range_proof(proof, bits=32)[source]#

Check a range proof: one equation for t, then the folded inner-product argument.

Malformed proofs return False.

Parameters:
Return type:

bool

FRI: fast Reed-Solomon interactive oracle proofs of proximity (2018).

Ben-Sasson, Bentov, Horesh and Riabzev showed how to check, with a few hash-based queries, that a committed list of N values is (close to) the evaluations of a polynomial of degree below d, a Reed-Solomon codeword. Split f into even and odd parts, f(X) = f_e(X**2) + X f_o(X**2); a random alpha folds them into one polynomial of half the degree on a domain of half the size,

f’(x**2) = (f(x) + f(-x)) / 2 + alpha (f(x) - f(-x)) / (2 x).

The prover commits to each layer with a Merkle tree, and after log2(d) folds the polynomial is a constant. The verifier picks random positions and checks each fold from two Merkle-opened values. A function far from every low-degree polynomial stays far after folding whp, so each query catches it with constant probability: no trusted setup, only hashes.

Domains are cosets offset * <w> of power-of-two subgroups of the BabyBear field; the challenges come from a Fiat-Shamir transcript.

blockchainkit.proofs.systems.fri.fri_prove(evaluations, degree_bound, *, offset=31, num_queries=8, transcript=None)[source]#

Commit to evaluations on offset * <w> and prove they have degree below degree_bound.

Parameters:

  • evaluations (collections.abc.Sequence of int) – Values at offset * w**i for i < N, with N a power of two.

  • degree_bound (int) – A power of two, at most N / 2; N / degree_bound is the blowup.

  • offset (int) – The coset shift.

  • num_queries (int) – Positions the verifier checks.

  • transcript (blockchainkit.proofs.utils.transcript.Transcript, optional) – Continue an existing Fiat-Shamir transcript, as a STARK does.

Return type:

blockchainkit.proofs.core.base.FRIProof

Examples

>>> from blockchainkit.proofs import evaluate_on_domain, fri_prove, fri_verify
>>> values = evaluate_on_domain(range(1, 9), 32, offset=31)  # degree 7 on 32 points
>>> proof = fri_prove(values, 8)
>>> fri_verify(proof, domain_size=32, degree_bound=8)
True
blockchainkit.proofs.systems.fri.fri_verify(proof, *, domain_size, degree_bound, offset=31, num_queries=8, transcript=None)[source]#

Check every query’s Merkle openings and folds, down to the final constant.

The query positions must be the ones the transcript dictates, so a caller that continues the transcript (a STARK) can trust proof.queries[k].index once this returns True.

Parameters:
Return type:

bool

STARKs: scalable, transparent arguments of knowledge from hashes (2018).

Ben-Sasson, Bentov, Horesh and Riabzev proved computations with nothing but a hash function: no trusted setup, no pairings, and (as far as is known) no quantum weakness. The computation is written as an execution trace with algebraic constraints between consecutive rows (an AIR). Here the trace is the Fibonacci sequence, a_0 = a_1 = 1 and a_(i+2) = a_(i+1) + a_i, over T steps, and the claim is a_(T-1).

Interpolate the trace over the subgroup <g> of order T as a polynomial f, so f(g**i) = a_i. Each constraint becomes a divisibility: the transition holds on rows 0 to T-3 exactly when

(f(g**2 X) - f(g X) - f(X)) (X - g**(T-2)) (X - g**(T-1)) / (X**T - 1)

is a polynomial, and each boundary value when (f(X) - a) / (X - g**i) is. The prover evaluates f on a larger coset (the low-degree extension), commits to it with a Merkle tree, combines the quotients with random coefficients, and proves with FRI that the combination has low degree. The verifier recomputes the combination at FRI’s query positions from Merkle-opened trace values at x, g x and g**2 x. A false claim leaves a quotient that is not a polynomial, which FRI rejects.

blockchainkit.proofs.systems.stark.fibonacci_trace(steps)[source]#

The first steps Fibonacci numbers modulo the BabyBear prime, from 1, 1.

>>> from blockchainkit.proofs import fibonacci_trace
>>> fibonacci_trace(8)
(1, 1, 2, 3, 5, 8, 13, 21)
Parameters:

steps (int)

Return type:

tuple[int, …]

blockchainkit.proofs.systems.stark.stark_prove(steps, *, claimed=None, blowup=8, num_queries=16)[source]#

Prove that the Fibonacci sequence from 1, 1 reaches claimed after steps terms.

Parameters:

  • steps (int) – T, a power of two, at least 4.

  • claimed (int, optional) – The claimed last term; the true one by default. A false claim still yields a “proof”, which fails verification.

  • blowup (int) – The low-degree extension’s size over T: the code’s inverse rate.

  • num_queries (int) – FRI queries; each also opens the trace.

Return type:

blockchainkit.proofs.core.base.StarkProof

Examples

>>> from blockchainkit.proofs import stark_prove, stark_verify
>>> proof = stark_prove(16)
>>> stark_verify(proof, steps=16, result=987), stark_verify(proof, steps=16, result=988)
(True, False)
blockchainkit.proofs.systems.stark.stark_verify(proof, *, steps, result, blowup=8, num_queries=16)[source]#

Check FRI on the composition, then its values against the opened trace.

Parameters:
Return type:

bool

Halo: recursive proof composition without a trusted setup (2019).

A proof that verifies another proof, which verified another, can compress an entire blockchain’s history into one constant-size proof, if verification is cheap enough to run inside a proof. Inner-product arguments need no setup, but verifying one costs a multi-exponentiation of length n. Bowe, Grigg and Hopwood noticed that this expensive step has a special form: after the log2(n) challenges c_j of the halving rounds, the verifier needs

G_final = prod G_i**s_i, where sum s_i X**i = g(X) = prod (1 + c_j X**(2**(k-j))),

a commitment to a polynomial g that anyone can evaluate in O(log n). So the verifier does the cheap part, and keeps (c, G_final) as an accumulator: a claim to be checked later. Two accumulators merge into one by opening a random combination of their G_finals at a random point, which is again an inner-product argument, with its own deferred claim. A chain of any length then needs one O(n) check at the very end.

This module provides the inner-product polynomial commitment and its accumulation, in the 62-bit teaching group. Halo itself ran the cheap verifier inside a circuit over a cycle of two elliptic curves (Tweedledum and Tweedledee); here the verifier runs in Python. Commitments carry no blinding, so they are binding but not hiding.

blockchainkit.proofs.systems.halo.ipa_generators(size)[source]#

Return size independent generators G_i, then one more, U, for the evaluation.

Parameters:

size (int)

Return type:

tuple[int, …]

blockchainkit.proofs.systems.halo.ipa_commit(coefficients, generators)[source]#

Commit to a polynomial of degree below n: prod G_i**a_i.

>>> from blockchainkit.proofs import ipa_commit, ipa_generators
>>> gens = ipa_generators(4)
>>> ipa_commit([1, 2], gens) == ipa_commit([1, 2, 0, 0], gens)
True
Parameters:
Return type:

int

blockchainkit.proofs.systems.halo.challenge_polynomial(challenges, point)[source]#

Evaluate g(X) = prod (1 + c_j X**(2**(k-j))) at a point in O(log n).

>>> from blockchainkit.proofs import challenge_polynomial
>>> challenge_polynomial([2, 3], 5) == (1 + 2 * 5**2) * (1 + 3 * 5)
True
Parameters:
Return type:

int

blockchainkit.proofs.systems.halo.ipa_open(coefficients, point, generators, *, label=b'halo-ipa')[source]#

Prove the value of a committed polynomial at point by halving.

Each round sends L = prod G_hi**a_lo U**<a_lo, b_hi> and R = prod G_lo**a_hi U**<a_hi, b_lo>, where b = (1, x, x**2, ...), and folds a' = a_lo + c**-1 a_hi, b' = b_lo + c b_hi, G' = G_lo G_hi**c.

Examples

>>> from blockchainkit.proofs import ipa_commit, ipa_generators, ipa_open, ipa_verify
>>> gens = ipa_generators(8)
>>> opening = ipa_open([3, 1, 4, 1, 5], 2, gens)
>>> opening.value, ipa_verify(ipa_commit([3, 1, 4, 1, 5], gens), opening, gens)
(109, True)
Parameters:
Return type:

IPAOpening

blockchainkit.proofs.systems.halo.ipa_defer(commitment, opening, generators, *, label=b'halo-ipa')[source]#

Do the cheap part of verification and return the deferred claim about G_final.

This takes O(log n) group operations: it folds the commitment with L and R and evaluates g(x) without the generators, trusting the opening’s g_final. It returns None if the final equation fails, and otherwise an accumulator that decide() must eventually check.

Parameters:
Return type:

HaloAccumulator | None

blockchainkit.proofs.systems.halo.decide(accumulator, generators)[source]#

The expensive O(n) check: is g_final really prod G_i**s_i?

Parameters:
Return type:

bool

blockchainkit.proofs.systems.halo.ipa_verify(commitment, opening, generators)[source]#

Verify an opening completely: the deferred checks, then decide() at once.

Parameters:
Return type:

bool

blockchainkit.proofs.systems.halo.accumulate(accumulators, generators)[source]#

Merge deferred claims into one: open sum rho**j g_j(X) at a random point.

The prover knows each g_j’s coefficients from its challenges, so it can open the combination of the G_finals; if any G_final were wrong, it could not. The result’s own deferred claim is the new accumulator.

Parameters:
Return type:

AccumulationProof

blockchainkit.proofs.systems.halo.verify_accumulation(accumulators, proof, generators)[source]#

Check an accumulation step in O(k log n) and return the new accumulator, or None.

Examples

>>> from blockchainkit.proofs import (ipa_generators, ipa_commit, ipa_open, ipa_defer,
...     accumulate, verify_accumulation, decide)
>>> gens = ipa_generators(8)
>>> claims = [ipa_defer(ipa_commit(f, gens), ipa_open(f, 5, gens), gens)
...           for f in ([1, 2, 3], [4, 5, 6, 7])]
>>> merged = verify_accumulation(claims, accumulate(claims, gens), gens)
>>> decide(merged, gens)
True
Parameters:
Return type:

HaloAccumulator | None

Plotting#

Plotting helpers for blockchainkit.proofs: polynomials over a field, proof sizes, and wiring.

blockchainkit.proofs.visualizers.plots.plot_copy_constraints(key, *, ax=None)[source]#

Draw a PLONK circuit’s wire grid and the cycles of its copy-constraint permutation.

Each row is a gate and each column a wire (a, b, c); positions joined by a line must carry the same value.

Parameters:
Return type:

matplotlib.axes.Axes

blockchainkit.proofs.visualizers.plots.plot_field_polynomials(polynomials, prime, *, ax=None)[source]#

Scatter each polynomial’s value at every point of a small field, and ring where they agree.

Parameters:
Return type:

matplotlib.axes.Axes

blockchainkit.proofs.visualizers.plots.plot_proof_sizes(series, *, xlabel='statement size', ylabel='bytes', ax=None)[source]#

Draw how proof sizes grow, on log-log axes, one line per series.

Parameters:
Return type:

matplotlib.axes.Axes

On this page
Show Source