This section composes the propositions of the preceding sections with the two assumptions on the Action proof, Assumptions 9.12 and 9.15. Theorem 12.4 states conservation per pool; its proof uses condition A4, the binding signature and Assumption 9.12. Lemma 12.5 and Theorem 12.6 exclude a second consumption of a note, Corollary 12.7 the Faerie Gold attack, Corollary 12.8 the consumption of a note of non-zero value in the block that creates it, and Theorem 12.10 a consumption without the spend authorising key; Theorem 12.13 states what the public data of a bundle hide. Theorem 12.15 collects, under one list of assumptions, membership soundness, Theorems 12.6, 12.4 and 12.10 with Proposition 11.10, and Theorem 12.13.
Efficient adversaries and negligible functions are those of the
Crypto Guide, §“Adversaries and the security parameter”, and
computational indistinguishability is that of its Definition “Perfect,
statistical, and computational indistinguishability” (§“Distribution
ensembles and indistinguishability”). An adversary interacts with the
honest parties, namely key holders, senders and signers, and with the random
oracles of Assumptions 2.8, 7.3,
9.12, 9.15 and 10.4, which are independent of one
another; every reduction simulates the honest parties and the random
oracles. Every result of the section holds except with negligible
probability, and every result that uses a property of key generation is
claimed for keys generated with
A pool is the Orchard pool or the Ironwood pool. A statement made for each pool uses that pool’s note commitment tree, anchors, nullifier set and bundle, its balancing value, or , and its binding signature, or .
An adversary outputs a block chain: a sequence of blocks each of whose transactions passes the verification of “Verification of a transaction” (§11.6) against the chain state that the state update of that subsection produces from the preceding transactions. An Action, or a bundle, of a transaction of that chain is accepted.
In this section a note is given by its expanded receiver (Definition “Flag values and expanded receiver”, §9.1) in place of its address, and its trapdoor acts through its residue modulo ; two notes are equal when these six components are. Its note commitment is and its extracted commitment is , with the message of Definition 4.4 formed from .
A committed note of a pool is a note whose extracted commitment is a leaf of that pool’s note commitment tree.
Assumption 9.12 is stated for one aggregate proof. For a block chain it is applied to each bundle, to the algorithm that runs the adversary, with every honest party and random oracle of the experiment, and outputs that bundle’s primary inputs and proof; the extractors of distinct bundles are run on the same execution. An oracle that a reduction does not simulate itself, such as the random oracle of Assumption 7.3 or a signing oracle, receives each new query of a rewound run, and a query repeated on the same prefix of a run is answered as before. By the union bound over the polynomially many bundles, every witness satisfies Definition 9.2, except with negligible probability. By Remark “-weakened conditions” (§9.2), conditions A1, A2, A3 and A7 then hold in their unweakened forms, without the case, except with negligible probability, under Assumptions 2.22 and 2.8. The results below include these events in their negligible terms.
Step 1 of the proof of Proposition 4.5(b) shows that the map
Let
then the two sides are equal as integers. The hypotheses hold for every accepted bundle of either pool: the bound on and the range of the balancing value are consensus rules (“The transaction format”, §11.2; protocol specification, §“Transaction Consensus Rules”, for both pools), and and are -bit values of the auxiliary input of Definition 9.2.
Let
The hypothesis makes a multiple of , and
The range of the values and is a hypothesis that the conclusion needs. Proposition 8.11 certifies the sum of the net values only modulo , and values that differ from the true ones by multiples of have the same value commitments; without the range, a bundle could pass the binding signature while creating value (Remark “Necessity of the conditions”, §9.2, item (v); Crypto Guide, §“The Pedersen commitment”, whose worked example shows such a wrap-around in a small group).
The security argument of the protocol specification, §“Balance and Binding Signature (Orchard)”, bounds the balancing value by its signed -bit encoding instead, which places in
that bound is also below , so the conclusion holds without the range rule of the balancing value.
Under Assumptions 9.12, 2.22, 2.8 and 7.3, for each pool, the Ironwood pool included, every accepted bundle of that pool output by an efficient adversary, with Actions and balancing value , satisfies
as integers, the values read from the Actions’ witnesses, except with negligible probability. The binding signature checked is that of the same pool, under the binding validating key recomputed from that bundle’s net value commitments and balancing value; both pools use the bases and .
Fix a pool and an efficient adversary . The adversary outputs
polynomially many bundles, and the union bound reduces the claim to the
-th bundle of the pool, for each . Let be the algorithm
that runs with the extractors of Assumption 9.12 and outputs
that bundle’s net value commitments
read from the witnesses, the digest of its transaction and the pool’s binding signature. Algorithm is efficient and forwards the queries of to .
(1) Openings. By condition A4 of Definition 9.2,
(2) Signature. The bundle is accepted, so its binding signature is valid on under
in the binding-signature instance of RedPallas, with base (step (6) of the verification of §11.6). This key belongs to the pool’s own bundle: each pool’s sums only that pool’s net value commitments and subtracts only its balancing value (§8.3).
(3) Congruence. Algorithm is therefore an efficient
party of the consequence of Proposition 8.11: it outputs the net
value commitments and the balancing value of a bundle, openings of every
commitment, and a binding signature under the resulting on a
message of its choice. The consequence is proved in two steps. The
extraction of Proposition 7.12, in the random-oracle
model for (Assumption 7.3), yields with
(4) Integers. The bundle is accepted, so it has
The argument uses no property of the pool beyond its own bundle and binding signature, and applies to the Ironwood pool as to the Orchard pool. □
Under Assumptions 9.12, 2.22 and 2.8, except with negligible probability: whenever two accepted Actions, of either pool, have witnesses whose consumed notes have the same extracted commitment , the two witnesses consume the same note with the same nullifier deriving key , and the two Actions publish the same nullifier . The lemma uses neither nor condition A3.
Let and be the two witnesses, primed components belonging to . Outside the negligible events of the paragraph after Definition “Pools, accepted Actions and witnesses”, both satisfy Definition 9.2 with A1 and A7 unweakened. Every step below is carried out by the efficient algorithm that runs the adversary with the extractors and searches the accepted Actions for such a pair.
(1) The note. By A1,
(2) The key. By A7,
and, the notes being equal,
except with negligible probability; in particular
(3) The nullifier. By A5,
Let two distinct accepted Actions of one pool consume the same note. Their consumed notes have the same extracted commitment, so by Lemma 12.5, except with negligible probability, the two Actions publish the same nullifier. Both belong to transactions of the adversary’s block chain, and the nullifier rule of “Nullifier sets” (§6.2), step (4) of the verification of §11.6, rejects a nullifier of the pool that repeats within a transaction or across the transactions of the chain. The event therefore lies in the negligible event of the lemma. The argument uses neither the value nor the membership of the note and holds for every note; the case of a committed note of non-zero value is the one that moves value. The nullifier sets of the two pools are separate (§6.2), so the argument concerns two Actions of one pool only. □
Under Assumptions 9.12, 2.22 and 2.8, except with negligible probability:
the notes created by distinct accepted Actions of one pool have pairwise distinct elements , and are therefore pairwise distinct;
two distinct notes have distinct nullifiers, whatever their nullifier deriving keys: no efficient algorithm outputs two distinct notes, with note commitments other than , and two keys , , equal or not, under which the two notes have equal nullifiers.
Hence the Faerie Gold attack, as defined in “Nullifier chaining” (§6.3), fails within a pool: (a) excludes two Actions creating the same note, which would carry one nullifier, and (b) excludes distinct notes sharing a nullifier, so that consuming one note accepted by a recipient never blocks another. The uniqueness of is pool-local: the pools’ nullifier sets are separate, so one value of may occur once in each pool.
(a) The note that the witness of an accepted Action creates has
(b) Two distinct notes have distinct note commitments, except with negligible probability, by the same remark; Proposition 6.8, which admits every pair of nullifier deriving keys, then excludes equal nullifiers.
Faerie Gold. Let a recipient accept a note from an accepted
Action of a pool, and let be its nullifier under the recipient’s
. By (a) no other accepted Action of the pool creates , so the
notes that the recipient accepts from distinct Actions are distinct. An
accepted Action of the pool whose witness consumes a note
Pool locality. The argument of (a) uses the nullifier set of one pool. An Orchard-pool Action and an Ironwood-pool Action may publish the same nullifier and create notes with the same ; a consumption in one pool inserts its nullifier into that pool’s set only, and so blocks no note of the other pool (Remark “Pool locality”, §6.2). □
Let an accepted Action of a pool lie in a transaction of a block , and let its witness consume a note of non-zero value. Under Assumptions 9.12, 2.22 and 2.8, except with negligible probability, the extracted commitment of was appended to the pool’s tree in a block that precedes , and is the note created by the accepted Action that appended it and by no other accepted Action of the pool. Hence no accepted Action consumes a note of non-zero value created by its own transaction, by another transaction of , or by a transaction not in a block that precedes : consumptions of notes of non-zero value do not chain within a block or through transactions not yet in the chain.
As stated after Definition “Pools, accepted Actions and witnesses”, the
witness satisfies Definition 9.2 with the anchor
of the Action’s bundle, and conditions A1, A2 and A3 hold without their
cases, except with negligible probability. By A1 the note has the
commitment , a point, so its extracted commitment is
. Since
A key holder generates a spending key with
Let an efficient adversary win with probability , and write
(1) Idealised key. By Lemma “Rejection in key generation”
(§3.2), the key is replaced by a single draw from a
uniform without rejection, at a cost negligible under
Assumptions 2.12, 2.22
and 2.8. By Lemma 2.15
(Assumption 2.12), its triple ,
before the sign normalisation, is then replaced by independent uniform
elements of , and , at a
further negligible cost. Both hops apply because the event that wins
is efficiently decidable from the triple: an algorithm derives the key’s
components, runs , answers its signing queries with , runs the
extractors on its output and checks the winning condition. After this step
and are independent of , and, when
(2) Reduction. An algorithm plays the adversary of
Proposition 7.12. It receives
(3) The witnessed key. Except with negligible probability,
(4) Forgery. An answer of the signing oracle to a query
has validating key
for a negligible , the costs of step (1) and of the events excluded in step (3).
(5) Discrete logarithm. By Proposition 7.12(i),
an algorithm runs twice on shared coins and
outputs, with at least the probability that part states for the forging
probability of , a scalar with
An Action publishes and a signature under
The public leakage of a bundle is its pool, its number of Actions, its anchor, its flags and its balancing value; the rest of the transaction, namely its transparent components, the other pool’s bundle and its header with the expiry height, is public as well. The private inputs of a bundle are, per Action, its witness (Definition 9.2), the plaintext of its created note (“The note plaintext”, §10.1), the outgoing viewing key under which its is formed, or , and whether each side is real or a dummy. The privacy preconditions are:
every key involved, namely the key of each consumed note, of
each recipient, and the key whose the sender uses, is generated
honestly with
the bundle is an Ironwood-pool bundle generated by the procedure of “Construction of a transaction” (§11.5): the seed of each created note fresh and uniform, the trapdoor uniform, the randomiser drawn by , each real consumed note a note of the pool that the procedure of “Trial decryption and note acceptance” (§10.4) accepted from an output of an accepted Action, and dummies as in the protocol specification, §“Dummy Notes (Orchard)”: a dummy consumed note has a random spending key, value , the -coordinate of a uniform point, a uniform and an unchecked path, and a dummy created note is an ordinary note of value to an address of a freshly generated key;
the authentication path is computed locally from public data (Lemma 5.16);
the adversary holds no viewing key of a key involved (no of a spender, no of a recipient, no of the sender), and no output is a coinbase output.
Within these preconditions the adversary may choose which notes are consumed and the recipients’ addresses, and may know the consumed notes’ contents.
Under (P2) the real consumed notes of one key have pairwise distinct
elements . An accepted note has
Assume preconditions (P1) to (P4), and let two sequences of private inputs of one Ironwood-pool bundle have equal public leakage, both satisfy Definition 9.2 with the common anchor and flags, and each Action consume either a leaf of the tree at that anchor not consumed before or a dummy, and create either a note to an honestly generated address or a dummy. Under Assumptions 9.15, 2.12, 3.13, 6.2, 3.16, 2.8, 10.4, 10.5 and 7.3, with Assumption 2.22 for Lemma “Rejection in key generation” (§3.2) and the redraw of the note seed (§4.3), the public data of the two bundles (per Action , , , , , , and the spend-authorisation signature; the proof and the binding signature) are computationally indistinguishable. In particular, beyond its public leakage an Action reveals nothing about its private inputs, and an Action whose spend or output side is a dummy is indistinguishable from one whose sides are real.
Precisely, in the following experiment every efficient adversary has
negligible advantage. Keys are generated as in (P1), and the adversary
receives addresses of them at indices of its choice. It outputs the leaves
of the Ironwood-pool tree through an anchoring block, the rest of a
transaction, flags, and two specifications of Actions with equal
balancing values. A specification gives, per Action, a consumed side,
either “dummy” or a note at one of these addresses whose extracted
commitment is a leaf; a created side, either “dummy” or one of these
addresses with a value and a memo; and the sender’s , that of one of
the keys or . The consumed leaves of a specification are pairwise
distinct, the consumed notes of one key have pairwise distinct , and
the construction of (P2) yields witnesses of Definition 9.2
with the anchor and flags. A challenger builds the bundle of specification
, for a uniform bit , by that construction and gives the
adversary its public data; the adversary outputs a bit , and its
advantage is
For
Game (proof). The aggregate proof is replaced by the output of the simulator of Assumption 9.15 on the primary inputs, which are public; the witnesses satisfy Definition 9.2 by hypothesis. The cost is the statistical distance of that assumption. From on, a witness enters the game only through the public fields computed from its components.
Game (keys). Each key involved is replaced in turn, as in the
preliminary step of the proof of Proposition 10.6 and
hybrids to of the proof of Proposition 6.10:
by a single draw without rejection (Lemma “Rejection in key generation”,
§3.2; Assumptions 2.12,
2.22 and 2.8); its triple
by independent uniform elements
(Lemma 2.15); and its triple by
, for a uniform point and uniform
-byte strings and (Assumption 3.13, whose
reduction draws and itself, and the negligible event that
Game (outgoing ciphertexts). Each is replaced by
the encryption of a fixed -byte string under an independent uniform key,
by Proposition “Confidentiality of the outgoing ciphertext”
(§10.3). For
Game (randomised keys). Each randomiser is replaced by a
uniform scalar, at a cost of at most
Game (nullifiers). For each key that consumes a note in the bundle,
real or dummy, the key enters only through the nullifiers of
those notes: removed it from the proof and from the viewing
keys. As in hybrids and of the proof of
Proposition 6.10, is replaced by a uniformly random function
(Assumption 6.2), and each multiplier of
by a uniform scalar
Game (ephemeral keys and note ciphertexts). For each created note in turn, real or dummy, is replaced by a uniform non-identity point and by the encryption of a fixed -byte string under an independent uniform key, by steps (1) to (4) of the proof of Proposition 10.6 (Assumptions 10.4, 3.16, 10.5, 2.8 and 2.12), which keep . The other public data, the data of that proposition, depend after to on the recipient’s key only through the addresses of that key given to the adversary and the outputs to them. The reduction of step (2) of that proof embeds the exponent as the of the recipient’s key in every such address, computing its transmission key as for the diversified base that it programs, and computes every other output to that key from its own ; the proof is otherwise as written.
Game (note commitments). For each created note in turn, is
replaced by the -coordinate of a uniform point. After the seed
of the note enters the game only through and ,
that is through : step (1) of replaced , and the
ciphertexts no longer depend on the plaintext. The proof of
Proposition 4.8 then places within
Value commitments and the binding signature. In every field other than the net value commitments and the binding signature is distributed independently of : the nullifiers and the extracted commitments are -coordinates of uniform points, each is a uniform non-identity point, the ciphertexts encrypt fixed strings under fresh keys, each and come from a fresh key , the proof is simulated from the primary inputs, and the rest of the transaction is common. The net values of specification enter only
and, through these, the digest, the primary inputs of the simulator and . Let be the discrete logarithm of to the base , which exists because generates the group (§8.1). The map
is a bijection of . It carries the net value
commitments of specification to those of specification , and it
preserves , because
The advantage of the adversary is therefore at most the sum of the costs of
the hops for
Theorem 12.13 hides nothing of the public leakage: each bundle’s balancing value, so the net amount that each transaction moves across a pool’s boundary is public; each pool’s chain value pool balance, the negation of the sum of its balancing values (“Chain state and pool rules”, §11.4), so a pool hides which notes are held by whom, never the aggregate value it holds; the number of Actions and the presence of each component; the flags; the transparent components; the fee; the anchor, which confines the consumed note to the leaves of the anchored tree (“Authentication paths”, §5.3); and the transaction’s timing and expiry height. Per Action the chain gains one nullifier and one extracted note commitment, which by the theorem reveal neither sender, recipient nor amount. The theorem claims nothing for coinbase outputs, whose outgoing ciphertexts decrypt under the all-zero (§11.4); nothing against a holder of a viewing key of a key involved, whose powers are stated in “Nullifier uniqueness and unlinkability” (§6.4), “The outgoing ciphertext” (§10.3) and “Trial decryption and note acceptance” (§10.4); nothing for an Orchard-pool bundle, whose created notes use lead byte and a derivation on which the volume does not rely (§10.4); and nothing about linkage through information outside the transaction, such as an address given to several parties, voluntary disclosures, or wallet and network metadata.
Assume, listed once: Assumption 2.22;
Assumptions 9.12 and 9.15, with
Assumption 9.11 in the supporting analysis of
Assumption 9.12; Assumption 3.16;
Assumptions 2.12 and 6.2;
Assumption 3.13; Assumptions 10.4
and 10.5; Assumption 11.9; and
Assumptions 2.8 and 7.3, for
and as random oracles. Clauses (iv) and (v) are key-derived and
are claimed for keys generated with
an accepted Action for which the extractor of Assumption 9.12 outputs no witness satisfying Definition 9.2; or a second opening, other than its witnessed created note, of the of an accepted Action; or an accepted Action whose witnessed is non-zero and whose consumed note is not a committed note of the pool, a leaf of the tree at the Action’s anchor (membership soundness) [R1 and R2 soundness];
two accepted Actions of the pool consuming one committed note of non-zero value [R3 soundness];
an accepted bundle whose balancing value differs, as an
integer, from the sum of its Actions’
winning the spend-authority experiment of “Authorisation of spends”, that is, an accepted Action consuming a note of an honestly generated key without a signature of the key holder, the adversary holding the key’s full viewing key but not its ; or an accepted transaction that changes the effecting data of a transaction while retaining one of its Actions, where the Actions of are authorised by holders of honestly generated keys who sign as hypothesis (S) of Proposition 11.10 states [R5];
for Ironwood-pool bundles, distinguishing the public data of two bundles with equal public leakage under preconditions (P1) to (P4) of “Privacy”, in particular a real Action from a dummy one [R1 hiding; R2 hiding, without identifying the note; R3 hiding, without a public list of consumed notes; R4 hiding, without disclosed amounts].
The bracketed tags refer to the requirement map of “The Action statement” (§9.2, Table 6), which is not repeated.
Each clause is a result of this section or of an earlier one.
(i) The first part is Assumption 9.12, applied to each bundle as
stated after Definition “Pools, accepted Actions and witnesses”, with
Remark “-weakened conditions” (§9.2) for the
unweakened forms of A1, A2, A3 and A7. By A2 the created note opens ,
and by Remark “Binding for notes given by expanded receivers” it is the
only opening that an efficient algorithm finds. For
(ii) Theorem 12.6.
(iv) The first part is Theorem 12.10. The second is Proposition 11.10, under Assumptions 11.9, 2.22 and 7.3; its hypothesis (H) holds for honestly generated keys up to a negligible change in the probability of every efficiently decidable event, the event of that proposition included, under Assumptions 2.12, 2.22 and 2.8 (Remark “Hypothesis (H) for honest keys”, §11.3).
(v) Theorem 12.13.
Clauses (i) to (iii) use Assumptions 9.12, 2.22,
2.8 and 7.3 only, and no property of key
generation; clauses (iv) and (v) use honest key generation with
Beyond Assumption 9.12, every soundness reduction ends in a discrete-logarithm problem on Pallas: either a non-trivial relation among values of , modelled as a random oracle (Assumption 2.8), namely Sinsemilla collisions and outputs (Proposition 2.24), with membership soundness (Proposition 5.9), the binding of and of , nullifier uniqueness (Proposition 6.8) and the independence of and (Proposition 8.11); or the discrete logarithm of a given point, in the spend-authority reduction through the RedPallas extraction of Proposition 7.12. Every extraction from a RedPallas signature, the binding signature included, holds in the random-oracle model for (Assumption 7.3). The digest step of bundle binding ends instead in a BLAKE2b collision (Assumption 11.9). Soundness is therefore computational and conditional on Assumption 9.12, which “The Action circuit and the Halo 2 proof” (§9.3) classifies as designed but unspecified, with discrete logarithms on Vesta entering only its supporting analysis; no concrete bound is asserted, since that assumption carries no loss factor. In clause (v), the contribution of the proof is statistical (Assumption 9.15; Halo 2 Guide, §“Zero knowledge: hiding the witness in Halo 2”); that of the value commitments with the binding signature is perfect (the final step of the proof of Theorem 12.13); that of and the spend-authorisation signatures is statistical in the random-oracle model for (game there); and the unlinkability of every other published field is computational. Assumption 6.2 is cryptanalytic, with no reduction to a standard problem.