bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 35쪽 중 2쪽
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .148
8.3 Unification of Mints and Pours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
8.4 Faerie Gold attack and fix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .149
8.5 Internal hash collision attack and fix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .151
8.6 Changes to PRF inputs and truncation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .152
8.7 In-band secret distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153
8.8 Omission inZerocashsecurity proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .154
5
8.9 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .155
9 Acknowledgements 155
10 Change History 157
11 References 192
Appendices 207
A Circuit Design 207
A.1 Quadratic Constraint Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .207
A.2 Elliptic curve background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .207
A.3 Circuit Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
A.3.1 Operations on individual bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
A.3.1.1 Boolean constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
A.3.1.2 Conditional equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .208
A.3.1.3 Selection constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
A.3.1.4 Nonzero constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
A.3.1.5 Exclusive-or constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
A.3.2 Operations on multiple bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
A.3.2.1 [Un]packing modulo𝑟 S . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .209
A.3.2.2 Range check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210
A.3.3 Elliptic curve operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .212
A.3.3.1 Checking that Affine-ctEdwards coordinates are on the curve . . . . . . . . . . . . .212
A.3.3.2 ctEdwards [de]compression and validation . . . . . . . . . . . . . . . . . . . . . . . .212
A.3.3.3 ctEdwards↔Montgomery conversion . . . . . . . . . . . . . . . . . . . . . . . . . . .212
A.3.3.4 Affine-Montgomery arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .213
A.3.3.5 Affine-ctEdwards arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .214
A.3.3.6 Affine-ctEdwards nonsmall-order check . . . . . . . . . . . . . . . . . . . . . . . . . .215
A.3.3.7 Fixed-base Affine-ctEdwards scalar multiplication . . . . . . . . . . . . . . . . . . . .215
A.3.3.8 Variable-base Affine-ctEdwards scalar multiplication . . . . . . . . . . . . . . . . . .216
A.3.3.9 Pedersen hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .217
A.3.3.10 Mixing Pedersen hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219
A.3.4 Merkle path check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
A.3.5 Windowed Pedersen Commitment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
A.3.6 Homomorphic Pedersen Commitment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .220
A.3.7 BLAKE2s hashes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .221
A.4 TheSaplingSpend circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .224
A.5 TheSaplingOutput circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .226
B Batching Optimizations 227
B.1RedDSAbatch validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227
B.2Groth16batch verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .228
B.3Ed25519batch validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .230
List of Theorems and Lemmata231
6
Index 231
7
1 Introduction #introduction
Zcashis an implementation of theDecentralized Anonymous Payment schemeZerocash [BCGGMTV2014], with
security fixes and improvements to performance and functionality. It bridges the existing transparent payment
scheme used byBitcoin [Nakamoto2008] with a shielded payment scheme secured byzero-knowledge succinct
non-interactive arguments of knowledge (zk-SNARKs).
In this document, technical terms for concepts that play an important rôle inZcashare written inslanted text,
which links to an index entry. Italics are used for emphasis and for references between sections of the document.
The symbol § precedes section numbers in cross-references.
The key wordsMUST,MUST NOT,SHOULD,SHOULD NOT,RECOMMENDED,MAY, andOPTIONALin this document
are to be interpreted as described in [RFC-2119] when they appear inALL CAPS. These words may also appear in
this document in lower case as plain English words, absent their normative meanings.
The most significant changes from the originalZerocashare explained in §8 ‘Differences from the Zerocash Zerocash Zerocash Zerocashpaper’
on p.148.
Changes before the Saplingupgrade are not highlighted.
Changes specific to the Saplingupgrade followingOverwinterare highlighted in green.
Changes specific to theBlossomupgrade following Saplingare highlighted in red.
Changes specific to theHeartwoodupgrade followingBlossomare highlighted in orange.
Changes specific to theCanopyupgrade followingHeartwoodare highlighted in purple.
Changes specific to the NU5upgrade followingCanopyare highlighted in slate blue.
Changes specific to the NU6upgrade following NU5are highlighted in pink.
Changes specific to the NU6.1upgrade following NU6are highlighted in burgundy.
Changes specific to the NU6.2upgrade following NU6.1are highlighted in brown.
All of these are also changes fromZerocash.
The name “Sprout” refers to theZcashprotocol prior to Sapling (both before and afterOverwinter), and in particular
its Sprout shielded protocol. The name “Sapling” refers to the Sapling network upgrade, and also theSapling shielded
protocolwhich is used for the Sapling pool. The name “Orchard” refers to the Orchard shielded protocol, used for
theOrchard pool.
This specification is structured as follows:
•Notation — definitions of notation used throughout the document;
•Concepts — the principal abstractions needed to understand the protocol;
•Abstract Protocol — a high-level description of the protocol in terms of ideal cryptographic components;
•Concrete Protocol — how the functions and encodings of the abstract protocol are instantiated;
•Network Upgrades — the strategy for upgrading theZcashprotocol.
• Consensus Changes fromBitcoin— howZcashdiffers fromBitcoinat the consensus layer, including the
Proof of Work;
•Differences from theZerocashprotocol — a summary of changes from the protocol in [BCGGMTV2014].
•Appendix: Circuit Design — details of how the Saplingcircuits are defined asquadratic constraint programs.
• Appendix: Batching Optimizations — improvements to the efficiency of validating multiple signatures and
verifying multiple proofs.
8
1.1 Caution #caution
Zcashsecurity depends on consensus. Should a program interacting with theZcashnetwork diverge from con-
sensus, its security will be weakened or destroyed. The cause of the divergence doesn’t matter: it could be a bug
in your program, it could be an error in this documentation which you implemented as described, or it could be
that you do everything right but other software on the network behaves unexpectedly. The specific cause will not
matter to the users of your software whose wealth is lost.
Having said that, a specification of intended behaviour is essential for security analysis, understanding of the
protocol, and maintenance ofZcashand related software. If you find any mistake in this specification, please file an
issue at https://github.com/zcash/zips/issues, or if security-relevant please submit a GitHub Security Advisory
to the relevant repository (seehttps://github.com/zcash/zips/security/policy).
1.2 High-level Overview #overview
The following overview is intended to give a concise summary of the ideas behind the protocol, for an audience
already familiar withblock chain-based cryptocurrencies such asBitcoin. It is imprecise in some aspects and is not
part of the normative protocol specification. This overview applies to Sprout, Sapling, and Orchard, differences in
the cryptographic constructions used notwithstanding.
All value inZcashbelongs to somechain value pool. The currentchain value poolsare the transparent pool, Sprout
pool, Sapling pool, Orchard pool, and deferred development fund pool. Transfers oftransparentvalue work essentially
as inBitcoinand have the same privacy properties. Value in ashielded chain value poolis carried bynotes 2, which
specify an amount and (indirectly) ashielded payment address, which is a destination to whichnotescan be sent.
As inBitcoin, this is associated with aprivate keythat can be used to spendnotessent to the address; inZcashthis
is called aspending key.
To eachnotethere is cryptographically associated anote commitment. Once thetransactioncreating anotehas
been mined, thenoteis associated with a fixednote positionin a tree ofnote commitments, and with anullifier 2
unique to thatnote. Computing thenullifierrequires the associated privatespending key(or thenullifier deriving
keyfor Sapling-pool or Orchard-pool notes). It is infeasible to correlate thenote commitmentornote positionwith
the correspondingnullifierwithout knowledge of at least this key. An unspent validnote, at a given point on the
block chain, is one for which thenote commitmenthas been publically revealed on theblock chainprior to that
point, but thenullifierhas not.
Atransactioncan containtransparentinputs, outputs, and scripts, which all work as inBitcoin [Bitcoin-Protocol]. It
also can includeJoinSplit descriptions,Spend descriptions,Output descriptionsandAction descriptions. Together
these describeshielded transferswhich take inshielded input notes, and/or produceshielded output notes. (For
Sprout, eachJoinSplit descriptionhandles up to twoshielded inputsand up to twoshielded outputs. For Sapling,
eachshielded inputorshielded outputhas its own description. For Orchard, eachAction descriptionhandles up to
oneshielded inputand up to oneshielded output.) It is also possible for value to be transferred betweenchain
value pools, eithertransparentorshielded; this always reveals the amount transferred.
In eachshielded transfer, thenullifiersof the inputnotesare revealed (preventing them from being spent again)
and the commitments of the outputnotesare revealed (allowing them to be spent in future).
Atransactionalso includes computationally soundzk-SNARKproofs and signatures, which prove that all of the
following hold except with insignificant probability:
2 InZerocash[BCGGMTV2014],noteswere called “coins”, andnullifierswere called “serial numbers”.
9
For eachshielded input,
•[ Saplingonward] there is a revealedvalue commitmentto the same value as the inputnote; 3
•if the value is nonzero, some revealednote commitmentexists for thisnote;
•the prover knew theproof authorizing keyof thenote;
•thenullifierandnote commitmentare computed correctly.
and for eachshielded output,
•[ Saplingonward] there is a revealedvalue commitmentto the same value as the outputnote; 3
•thenote commitmentis computed correctly;
•it is infeasible to cause thenullifierof the outputnoteto collide with thenullifierof any othernote.
For Sprout, theJoinSplit statementalso includes an explicit balance check. For Saplingand Orchard, thevalue
commitmentscorresponding to the inputs and outputs are checked to balance (together with any nettransparent
input or output) outside thezk-SNARK.
In addition, various measures (differing between Sproutand Saplingor Orchard) are used to ensure that thetrans-
actioncannot be modified by a party not authorized to do so.
Outside thezk-SNARK, it is checked that thenullifiersfor the inputnoteshad not already been revealed (i.e. they
had not already been spent).
Ashielded payment addressincludes atransmission keyfor a “key-private” asymmetric encryption scheme.
Key-private means that ciphertexts do not reveal information about which key they were encrypted to, except to a
holder of the correspondingprivate key, which in this context is called thereceiving key. This facility is used to
communicate encrypted outputnoteson theblock chainto their intended recipient, who can use thereceiving
keyto scan theblock chainfornotesaddressed to them and then decrypt thosenotes.
In Saplingand Orchard, for eachspending keythere is afull viewing keythat allows recognizing both incoming and
outgoingnoteswithout havingspending authority. This is implemented by an additional ciphertext in eachOutput
descriptionorAction description.
The basis of the privacy properties ofZcashis that when anoteis spent, the spender only proves that some
commitment for it had been revealed, without revealing which one. This implies that a spentnotecannot be
linked to thetransactionin which it was created. That is, from an adversary’s point of view the set of possibilities
for a givennoteinput to atransaction—itsnote traceability set— includes all previous notes that the adversary
does not control or know to have been spent.4 This contrasts with other proposals for private payment systems,
such as CoinJoin [Bitcoin-CoinJoin] or CryptoNote[vanSaberh2014] , that are based on mixing of a limited number
of transactions and that therefore have smallernote traceability sets.
Thenullifiersare necessary to preventdouble-spending: eachnoteon theblock chainonly has one validnullifier,
and so attempting to spend anotetwice would reveal thenullifiertwice, which would cause the secondtransaction
to be rejected.
3 For the Orchard shielded protocol, each Action reveals a singlevalue commitmentto the net value spent by the Action, rather than one
value commitmentfor the inputnoteand one for the outputnote.
4 We make this claim only for fully shielded transactions. It does not exclude the possibility that an adversary may use data present in
the cleartext of atransactionsuch as the number of inputs and outputs, or metadata-based heuristics such as timing, to make proba-
bilistic inferences abouttransactionlinkage. For consequences of this in the case of partially shieldedtransactions, see [Peterson2017],
[Quesnelle2017], and [KYMM2018].
10
2 Notation #notation
Bmeans the type of bit values, i.e.{0,1}.B Y Y means the type of byte values, i.e.{0..255}.
N means the type of nonnegative integers. N+ means the type of positive integers. Z means the type of integers.
Qmeans the type of rationals.
𝑥 𝑇 is used to specify that 𝑥 has type 𝑇 . A cartesian product type is denoted by 𝑆×𝑇 , and a function type by
𝑆→𝑇. An argument to a function can determine other argument or result types.
The type of a randomized algorithm is denoted by 𝑆→R 𝑇 . The domain of a randomized algorithm may be (),
indicating that it requires no arguments. Given 𝑓 𝑆→R 𝑇 and 𝑠 𝑆, sampling a variable 𝑥 𝑇 from the output of 𝑓
applied to𝑠is denoted by𝑥← R 𝑓(𝑠).
Initial arguments to a function or randomized algorithm may be written as subscripts, e.g. if 𝑥 𝑋, 𝑦 𝑌 , and
𝑓 𝑋×𝑌→𝑍, then an invocation of𝑓(𝑥, 𝑦)can also be written𝑓 𝑥(𝑦).
{𝑥 𝑇|𝑝 𝑥}means the subset of𝑥from𝑇for which𝑝 𝑥 (a boolean expression depending on𝑥) holds.
𝑇⊆𝑈indicates that𝑇is an inclusive subset or subtype of𝑈.
𝑆∪𝑇means the set union of𝑆and𝑇.
𝑆∩𝑇means the set intersection of𝑆and𝑇, i.e.{𝑥 𝑆|𝑥∈𝑇}.
𝑆∖𝑇means the set difference obtained by removing elements in𝑇from𝑆, i.e.{𝑥 𝑆|𝑥 /∈𝑇}.
𝑥 𝑇↦→𝑒 𝑥 𝑈 means the function of type 𝑇→𝑈 mapping formal parameter 𝑥 to 𝑒𝑥 (an expression depending
on𝑥). The types𝑇and𝑈are always explicit.
𝑥 𝑇↦→ ̸∈𝑉 𝑒𝑥 𝑈means𝑥 𝑇↦→𝑒 𝑥 𝑈∪𝑉restricted to the domain{𝑥 𝑇|𝑒 𝑥̸∈𝑉}and range𝑈.
P
(︀
𝑇
)︀
means the powerset of𝑇.
⊥ is a distinguished value used to indicate unavailable information, a failed decryption or validity check, or an
exceptional case.
𝑇 [ℓ], where 𝑇 is a type and ℓ is an integer, means the type of sequences of length ℓ with elements in 𝑇 . For example,
B[ℓ] means the set of sequences ofℓbits, andB Y Y[𝑘] means the set of sequences of𝑘bytes.
BY Y[N] means the type ofbyte sequencesof arbitrary length.
length(𝑆)means the length of (number of elements in)𝑆.
truncate𝑘(𝑆)means the sequence formed from the first𝑘elements of𝑆.
0x followed by a string of monospace hexadecimal digits means the corresponding integer converted from hexadec-
imal.[ 0x00]ℓ means the sequence ofℓzero bytes.
“...” means the given string represented as a sequence of bytes inUS-ASCII. For example, “abc” represents the
byte sequence[ 0x61, 0x62, 0x63 ].
[0]ℓ means the sequence ofℓzero bits.[1] ℓ means the sequence ofℓone bits.
𝑎..𝑏, used as a subscript, means the sequence of values with indices 𝑎 through 𝑏 inclusive. For example, anewpk,1..Nnew
means the sequence [anewpk,1,a newpk,2, ...anewpk,Nnew]. (For consistency with the notation in [BCGGMTV2014] and in [BK2016],
this specification uses 1-based indexing and inclusive ranges, notwithstanding the compelling arguments to the
contrary made in [EWD-831].)
{𝑎 .. 𝑏}means the set or type of integers from𝑎through𝑏inclusive.
[ [𝑓(𝑥)for𝑥from𝑎up to𝑏] ]means the sequence formed by evaluating 𝑓 on each integer from 𝑎 to 𝑏 inclusive, in
ascending order. Similarly, [ [𝑓(𝑥)for𝑥from𝑎down to𝑏] ]means the sequence formed by evaluating 𝑓 on each
integer from𝑎to𝑏inclusive, in descending order.
𝑎||𝑏means the concatenation of sequences𝑎then𝑏.
11
concatB(𝑆)means the sequence of bits obtained by concatenating the elements of𝑆asbit sequences.
sorted(𝑆)means the sequence formed by sorting the elements of𝑆.
F𝑛 means the finite field with𝑛elements, andF *𝑛 means its group under multiplication (which excludes0).
Where there is a need to make the distinction, we denote the unique representative of𝑎 F𝑛 in the range{0.. 𝑛−1}
(or the unique representative of 𝑎 F*𝑛 in the range{1.. 𝑛−1} ) as 𝑎mod𝑛 . Conversely, we denote the element of F𝑛
corresponding to an integer 𝑘 Z as 𝑘(mod𝑛) . We also use the latter notation in the context of an equality 𝑘=𝑘 ′
(mod𝑛) as shorthand for 𝑘mod𝑛=𝑘 ′ mod𝑛 , and similarly 𝑘̸=𝑘 ′ (mod𝑛) as shorthand for 𝑘mod𝑛̸=𝑘 ′ mod𝑛 .
(When referring to constants such as 0 and 1 it is usually not necessary to make the distinction between field
elements and their representatives, since the meaning is normally clear from context.)
F𝑛[𝑧]means the ring of polynomials over𝑧with coefficients inF 𝑛.
𝑎+𝑏 means the sum of 𝑎 and 𝑏. This may refer to addition of integers, rationals, finite field elements, or group
elements (see §4.1.9 ‘Represented Group’ on p.34) according to context.
−𝑎 means the value of the appropriate integer, rational, finite field, or group type such that (−𝑎) +𝑎= 0 (or when 𝑎
is an element of a groupG,(−𝑎) +𝑎=𝒪 G), and𝑎−𝑏means𝑎+ (−𝑏).
𝑎·𝑏 means the product of multiplying 𝑎 and 𝑏. This may refer to multiplication of integers, rationals, or finite field
elements according to context (this notation is not used for group elements).
𝑎/𝑏, also written 𝑎𝑏 , means the value of the appropriate integer, rational, or finite field type such that(𝑎/𝑏)·𝑏=𝑎.
𝑎mod𝑞 , for 𝑎 N and 𝑞 N+, means the remainder on dividing𝑎 by 𝑞. (This usage does not conflict with the not프로젝트로 돌아가기