Skip to content

Instantly share code, notes, and snippets.

@laanwj

laanwj/cns001.txt

Last active September 6, 2025 08:11
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save laanwj/6b52e6cc516c0fa32637287aa83df38c to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save laanwj/6b52e6cc516c0fa32637287aa83df38c to your computer and use it in GitHub Desktop.
Download ZIP
Monero CNS documents from defunct https://cryptonote.org/cns site
Raw
cns001.txt
CRYPTONOTE STANDARD 001 Nicolas van Saberhagen
Category: Main Track Johannes Meier
Antonio M. Juarez
CryptoNote
December 2011
CryptoNote Signatures
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the exact method of
zero-knowledge proof to establish the ownership of an asset. The
standard CryptoNote approach is the one-time ring signature scheme:
it allows a user to sign a message on behalf of the group while
keeping his identity indistinguishable from others. Only one
signature is allowed under the same key ("one-time" property), as any
other signatures will be unambiguously linked with the first one,
which prevents double-spending.
Copyright and License Notice
Copyright (c) 2011 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. One-Time Ring Signatures . . . . . . . . . . . . . . . . . . . 2
4. Data Types and Accessory Functions . . . . . . . . . . . . . . 3
5. Signature Generation . . . . . . . . . . . . . . . . . . . . . 4
6. Signature Verification . . . . . . . . . . . . . . . . . . . . 4
7. Security Considerations . . . . . . . . . . . . . . . . . . . . 5
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Van Saberhagen et al. CryptoNote Signatures [Page 1]
CRYPTONOTE STANDARD 001 December 2011
1. Introduction
A distinguishing feature of cryptocurrencies is that they establish
the money ownership and the authenticity of money transfers by
cryptographic means, specifically through the use of digital
signatures. A digital signature certifies that a particular
transaction is authorized by the owner of a particular key. However,
with regular digital signatures, the key which was used to
authenticate each transaction can be precisely identified. While the
keys are not directly linked to their owners' identities, they can be
used to link transactions. This means that it is possible to start
from a transaction whose sender or recipient is known, and trace the
funds either forward or backward to deduce how they are spent, or
where they were obtained.
CryptoNote uses advanced cryptography to obscure some of this
information. An ideal scheme would leave attackers completely
oblivious to a transaction's funding sources, but the scheme used in
CryptoNote is more limited. Firstly, a transaction input can only
obtain its funds from an output of the same amount. Secondly, each
input lists specific outputs, and it is known that the output spent
by the input is present in the list. However, no information is
disclosed beyond this point; the real spender is unidentifiable from
other outputs in the list.
2. Definitions
digital signature: a cryptographic method of showing that a
particular message was authorized by a particular peer
public key: a datum used to identify a peer for the purpose of
digital signature verification
ring signature: a class of schemes that allow a user to sign a
message on behalf of a group, making his identity indistinguishable
from the other members of the group
secret key: data known to a peer only, which enables him to create
digital signatures under his identity
3. One-Time Ring Signatures
Like regular digital signatures, keys for CryptoNote signatures come
in pairs. Public keys are included in transaction outputs and are
used to check the signatures, while the corresponding secret keys are
used to create them. However, CryptoNote utilizes ring signatures
Van Saberhagen et al. CryptoNote Signatures [Page 2]
CRYPTONOTE STANDARD 001 December 2011
instead of regular, and these signatures may need multiple keys for
verification. A single secret key is needed to create a signature,
and this key must correspond to one of the public keys the signature
is verified against. Moreover, it is computationally infeasible to
recover the secret key used to create the signature. This means that
the sender of a transaction can link his inputs to multiple outputs,
making the task of tracking the funds more complex.
However, if CryptoNote used standard ring signatures, it would not be
known which outputs are spent and which are not. Therefore, it would
be possible to spend the same output multiple times. This would lead
to a double-spend problem, nullifying the scarcity of the currency.
To solve this issue, CryptoNote signatures were made one-time, which
means that it is possible to detect when multiple signatures are made
under the same key without revealing the key. This means that the
double-spend protection does not break the privacy properties.
The properties of CryptoNote signatures can be summarized as follows:
1. Usability: any person with a secret key can create a signature
on any message under that key and any other public keys. The list
of keys under which the signature is created, including the public
key which corresponds to the secret key used, is called a ring.
2. Security: it is not possible to create a signature without
possessing a secret key corresponding to one of the public keys in
the ring.
3. Anonymity: the signature does not convey any information beyond
being created by one of the keys in the ring. Signatures created
using different keys are indistinguishable, with a small
exception:
4. Linkability: it is possible to tell if two signatures were made
with the same secret key. No information is revealed beyond that,
therefore it could be any of the keys present in both rings.
The construction of the One-Time Ring Signatures used in CryptoNote
is a simplified version of Traceable Ring Signatures by Fujisaki and
Suzuki [TRS].
4. Data Types and Accessory Functions
The CryptoNote signature scheme can be instantiated with any elliptic
curve of prime order. The curve will be referred to as E, with its
order being q. The terms "points" and "scalars" will be used to refer
to the elements of E and the integers modulo q respectively. The
Van Saberhagen et al. CryptoNote Signatures [Page 3]
CRYPTONOTE STANDARD 001 December 2011
parameters are E, two points of order q - G1 and G2, and a hash
function H producing a scalar. Secret keys are scalars, and the
public key corresponding to the secret key a is the point A = a*G1.
A signature in a ring of n keys consists of a point Q and 2*n
scalars.
5. Signature Generation
In the following two procedures || denotes concatenation.
To generate a signature, the following procedure is used:
Procedure generate_signature(M, A[1], A[2], ..., A[n], i, a[i]):
Q <- a[i]*G2
c[j], r[j] [j=1..n, j!=i] <- random
k <- random
For j <- 1..n, j!=i
X[j] <- c[j]*A[j]+r[j]*G1
Y[j] <- c[j]*Q+r[j]*G2
End For
X[i] <- k*G1
Y[i] <- k*G2
c[i] <- H(H(M) || X[1] || Y[1] || X[2] || Y[2] || ... || X[n] ||
Y[n])-Sum[j=1..n, j!=i](c[j])
r[i] <- k-a[i]*c[i]
Return (Q, c[1], r[1], c[2], r[2], ..., c[n], r[n])
End Procedure
6. Signature Verification
Signatures are verified using the following procedure:
Procedure verify_signature(M, A[1], A[2], ..., A[n], Q, c[1], r[1],
c[2], r[2], ..., c[n], r[n]):
For i <- 1..n
X[i] <- c[i]*A[i]+r[i]*G1
Y[i] <- c[i]*Q+r[i]*G2
End For
If H(H(M) || X[1] || Y[1] || X[2] || Y[2] || ... || X[n] || Y[n])
= Sum[i=1..n](c[i])
If Q has been used before
Return "Double spend"
Else
Return "Correct"
End If
Van Saberhagen et al. CryptoNote Signatures [Page 4]
CRYPTONOTE STANDARD 001 December 2011
Else
Return "Incorrect"
End If
End Procedure
7. Security Considerations
It is of utmost importance that the random numbers used during the
signatures generation are produced by a cryptographically secure
random number generator. The distribution of the numbers must be
indistinguishable from the uniform distribution. Insecure generation
of the numbers c[j] and r[j] (j!=i) can be used to compromise
anonymity, while insecure generation of k can compromise the secret
key a[i].
8. References
[TRS] Fujisaki, E., and K. Suzuki, "Traceable Ring Signature", 2007.
Van Saberhagen et al. CryptoNote Signatures [Page 5]
Raw
cns002.txt
CRYPTONOTE STANDARD 002 Nicolas van Saberhagen
Obsoletes: CNS001 Johannes Meier
Category: Main Track Antonio M. Juarez
Max Jameson
Seigen
CryptoNote
May 2012
CryptoNote Signatures
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the exact method of
zero-knowledge proof to establish the ownership of an asset. The
standard CryptoNote approach is the one-time ring signature scheme:
it allows a user to sign a message on behalf of the group while
keeping his identity indistinguishable from others. Only one
signature is allowed under the same key ("one-time" property), as any
other signatures will be unambiguously linked with the first one,
which prevents double-spending.
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. One-Time Ring Signatures . . . . . . . . . . . . . . . . . . . 2
4. Theoretical Description . . . . . . . . . . . . . . . . . . . . 3
5. Data Types and Accessory Functions . . . . . . . . . . . . . . 4
6. Signature Generation . . . . . . . . . . . . . . . . . . . . . 5
7. Signature Verification . . . . . . . . . . . . . . . . . . . . 5
8. Security Considerations . . . . . . . . . . . . . . . . . . . . 5
9. Differences from CNS001 . . . . . . . . . . . . . . . . . . . . 6
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Van Saberhagen et al. CryptoNote Signatures [Page 1]
CRYPTONOTE STANDARD 002 May 2012
1. Introduction
A distinguishing feature of cryptocurrencies is that they establish
the money ownership and the authenticity of money transfers by
cryptographic means, specifically through the use of digital
signatures. A digital signature certifies that a particular
transaction is authorized by the owner of a particular key. However,
with regular digital signatures, the key which was used to
authenticate each transaction can be precisely identified. While the
keys are not directly linked to their owners' identities, they can be
used to link transactions. This means that it is possible to start
from a transaction whose sender or recipient is known, and trace the
funds either forward or backward to deduce how they are spent, or
where they were obtained.
CryptoNote uses advanced cryptography to obscure some of this
information. An ideal scheme would leave attackers completely
oblivious to a transaction's funding sources, but the scheme used in
CryptoNote is more limited. Firstly, a transaction input can only
obtain its funds from an output of the same amount. Secondly, each
input lists specific outputs, and it is known that the output spent
by the input is in the list. However, no information is disclosed
beyond this fact; a signature does not reveal any information about
how likely it is that an input spends a particular output in the
list.
2. Definitions
digital signature: a cryptographic method of showing that a
particular message was authorized by a particular peer
public key: a datum used to identify a peer for the purpose of
digital signature verification
ring signature: a class of schemes that allow a user to sign a
message on behalf of a group, making his identity indistinguishable
from the other members of the group
secret key: data known to a peer only, which enables him to create
digital signatures under his identity
3. One-Time Ring Signatures
Like regular digital signatures, keys for CryptoNote signatures come
in pairs. Public keys are included in transaction outputs and are
used to check the signatures, while the corresponding secret keys are
Van Saberhagen et al. CryptoNote Signatures [Page 2]
CRYPTONOTE STANDARD 002 May 2012
used to create them. However, CryptoNote utilizes ring signatures
instead of regular, and these signatures may need multiple keys for
verification. A single secret key is needed to create a signature,
and this key must correspond to one of the public keys the signature
is verified against. Moreover, it is computationally infeasible to
recover the secret key used to create the signature. This means that
the sender of a transaction can link his inputs to multiple outputs,
making the task of tracking the funds more complex.
However, if CryptoNote used standard ring signatures, it would not be
known which outputs are spent and which are not. Therefore, it would
be possible to spend the same output multiple times. This would lead
to a double-spend problem, nullifying the scarcity of the currency.
To solve this issue, CryptoNote signatures were made one-time, which
means that it is possible to detect when multiple signatures are made
with the same key without revealing the key. This means that the
double-spend protection does not break the privacy properties.
The properties of CryptoNote signatures can be summarized as follows:
1. Usability: any person with a secret key can create a signature
on any message under that key and any other public keys. The list
of keys under which the signature is created, including the public
key which corresponds to the secret key used, is called a ring.
2. Security: it is not possible to create a signature without
possessing a secret key corresponding to one of the public keys in
the ring.
3. Anonymity: the signature does not convey any information beyond
being created by one of the keys in the ring. Signatures created
using different keys are indistinguishable, with a small
exception:
4. Linkability: it is possible to tell if two signatures were made
with the same secret key. No information is revealed beyond that,
therefore it could be any of the keys present in both rings.
4. Theoretical Description
The construction of the One-Time Ring Signatures used in CryptoNote
is a simplified version of Traceable Ring Signatures by Fujisaki and
Suzuki [TRS]. It is based on the framework of Camenisch and Stadler
[DLOG]. It uses a group with an element G of prime order l. A secret
key is an integer modulo l, and the corresponding public key is the
value A=a*G.
Van Saberhagen et al. CryptoNote Signatures [Page 3]
CRYPTONOTE STANDARD 002 May 2012
A signature includes a key image, which is a value that corresponds
to a key that can't be derived without the knowledge of the
respective secret key. The key image included in a signature must
correspond to the key used to create it. This facilitates the
detection of signatures made with the same key: all such signatures
will include the same key image. The key image corresponding to
public key A is a*H(A), where a is the corresponding secret key and H
is a hash function which maps public keys to group elements.
In addition to the key image, each signature includes a zero-
knowledge proof of knowledge of the secret key corresponding to one
of the public keys used to validate the signature, such that the key
image in the signature corresponds to that key. If the signature is
validated with keys A[1], A[2], ..., A[n] and includes key image I,
then the proof is as follows:
ZKPoK[(i, a) | A[i]=a*G and I=a*H(A[i])]
The proof is made non-interactive by means of Fiat-Shamir transform
[FS]. The hash of the message is added to the commitment, which binds
the signature to the message.
5. Data Types and Accessory Functions
The CryptoNote signature scheme uses Curve25519 (see [CURVE]) as the
underlying group. Group elements are encoded in the same way as in
Ed25519 (see [ED25519]). Integers modulo l (henceforth named scalars)
are represented in the 32-byte little-endian form. To prevent
malleability, the integers encoded must lie between 0 and l-1.
The signature consists of the key image (a single group element) and
2*n scalars, where n is the number of keys used. Scalars are grouped
into n pairs, the scalars in the i-th pair are the challenge and the
response values c[i] and r[i] for the part of the proof concerning
A[i]. The commitment consists of the hash of the message followed by
2*n group elements grouped into n pairs. The elements in the i-th
pair are respectively c[i]*A[i]+r[i]*G and c[i]*I+r[i]*H(A[i]).
The hash function used is the same Keccak function that is used
throughout CryptoNote. When the value of the hash function is
interpreted as a scalar, it is converted into a little-endian integer
and taken modulo l. When it is interpreted as a group element, it is
passed to a special function that is guaranteed to return a valid
group element.
Van Saberhagen et al. CryptoNote Signatures [Page 4]
CRYPTONOTE STANDARD 002 May 2012
6. Signature Generation
In the following two procedures || denotes concatenation.
To generate a signature, the following procedure is used:
Procedure generate_signature(M, A[1], A[2], ..., A[n], i, a[i]):
I <- a[i]*H(A[i])
c[j], r[j] [j=1..n, j!=i] <- random
k <- random
For j <- 1..n, j!=i
X[j] <- c[j]*A[j]+r[j]*G
Y[j] <- c[j]*I+r[j]*H(A[j])
End For
X[i] <- k*G
Y[i] <- k*H(A[i])
c[i] <- H(H(M) || X[1] || Y[1] || X[2] || Y[2] || ... || X[n] ||
Y[n])-Sum[j=1..n, j!=i](c[j])
r[i] <- k-a[i]*c[i]
Return (I, c[1] || r[1] || c[2] || r[2] || ... || c[n] || r[n])
End Procedure
7. Signature Verification
Signatures are verified using the following procedure:
Procedure verify_signature(M, A[1], A[2], ..., A[n], I, c[1], r[1],
c[2], r[2], ..., c[n], r[n]):
For i <- 1..n
X[i] <- c[i]*A[i]+r[i]*G
Y[i] <- c[i]*I+r[i]*H(A[i])
End For
If H(H(M) || X[1] || Y[1] || X[2] || Y[2] || ... || X[n] || Y[n])
= Sum[i=1..n](c[i])
Return "Correct"
Else
Return "Incorrect"
End If
End Procedure
8. Security Considerations
It is of utmost importance that the random numbers used during the
signatures generation are produced by a cryptographically secure
random number generator. The distribution of the numbers must be
indistinguishable from the uniform distribution. Insecure generation
Van Saberhagen et al. CryptoNote Signatures [Page 5]
CRYPTONOTE STANDARD 002 May 2012
of the numbers c[j] and r[j] (j!=i) can be used to compromise
anonymity, while insecure generation of k can compromise the secret
key a[i].
Some obvious choices of hash-to-group-element function admit certain
attacks that can be used to break user anonymity. The function used
in CryptoNote is not susceptible to such attacks.
9. Differences from CNS001
These are the major differences between this document and [CNS001]:
- a new section "Theoretical Description" has been added,
- the signature algorithm has been updated to obviate the
necessity for the second basepoint G2,
- a new entity "key image" has been defined instead of a group
element Q,
- specific elliptic curve parameters (namely, Curve25519) have
been chosen.
10. References
[CNS001] "CryptoNote Signatures", CryptoNote Standard 001, December
2011.
[CURVE] Bernstein, D. J., "Curve25519: new Diffie-Hellman speed
records", 2006, http://cr.yp.to/ecdh/curve25519-20060209.pdf.
[DLOG] Camenisch, J., and M. Stadler, "Proof Systems for General
Statements about Discrete Logarithms", 1997.
[ED25519] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., and B.-
Y. Yang, "High-speed high-security signatures", 2011,
http://ed25519.cr.yp.to/ed25519-20110926.pdf.
[FS] Fiat, A., and A. Shamir, "How To Prove Yourself: Practical
Solutions to Identification and Signature Problems", 1987.
[TRS] Fujisaki, E., and K. Suzuki, "Traceable Ring Signature", 2007.
Van Saberhagen et al. CryptoNote Signatures [Page 6]
Raw
cns003.txt
CRYPTONOTE STANDARD 003 Albert Werner
Category: Main Track Montag
Ardolabar
Tereno
Antonio M. Juarez
CryptoNote
September 2012
CryptoNote Blockchain
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the way data is stored
within blocks and the blockhain along with the corresponding data
structures.
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Variable-Length Encoding of Integers (varint) . . . . . . . . . 2
4. Block Structure . . . . . . . . . . . . . . . . . . . . . . . . 3
4.1 Block Header . . . . . . . . . . . . . . . . . . . . . . . 3
4.2 Base Transaction . . . . . . . . . . . . . . . . . . . . . 4
4.3 List of Transaction Identifiers . . . . . . . . . . . . . . 5
5. Calculation of Block Identifier . . . . . . . . . . . . . . . . 6
5.1 Merkle Root Hash Calculation . . . . . . . . . . . . . . . 6
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Werner et al. CryptoNote Blockchain [Page 1]
CRYPTONOTE STANDARD 003 September 2012
1. Introduction
CryptoNote's distributed public ledger is organized in the form of
blockchain similar to Bitcoin's blockchain described in [BITCOIN].
The blockchain consists of blocks chained together: each block refers
to the previous one through block identifiers. The blockchain has a
tree-like form with a single root block and branches that may start
from any other blocks. At any moment only one branch is considered to
be the main branch. The main branch is chosen by a consensus
algorithm at each network node.
Each block has a block header and an additional payload. The
additional payload consists of a base transaction and a list of
transaction identifiers. The transactions themselves (except for the
base transaction) are not included in the block. The block's payload
(the transactions attached to the block via identifiers) is expected
to be non-self-contradictory and not contradict the blockchain branch
it is attached to. This ensures that the entire blockchain is non-
contradictory.
The blockchain acts as an append-only database. Each block contains
certain information that is appended on top of some branch (usually
the main branch).
2. Definitions
base transaction: a transaction that generates new coins
block: a set of data (payload) with a block header
block header: metadata at the beginning of each block
block height: the distance between the block and the genesis block in
the blockchain
blockchain: a tree structure of blocks
genesis block: the root of the blockchain
3. Variable-Length Encoding of Integers (varint)
Most integers in CryptoNote are encoded in a variable-length prefix-
free representation. The same encoding is used in the .xz file format
[XZ].
Werner et al. CryptoNote Blockchain [Page 2]
CRYPTONOTE STANDARD 003 September 2012
Integers between 0 and 127 (inclusive) are represented by a single
byte having the same value as the integer. Larger integers are first
represented in base 128. Let a[0], a[1], ..., a[n-1] be such
representation, where a[0] is the least significant base-128 digit
and a[n-1] is the most significant one. Then, the encoding is the
sequence of n bytes with values a[0]+128, a[1]+128, ..., a[n-2]+128,
a[n-1]. Since a[n-1] > 0, such encoding does not contain null bytes.
Decoding such an integer requires scanning the stream until a byte
with the value less than 128 is found. If it is not the first byte
and its value is 0, the encoding is invalid. Otherwise, the sequence
of values of the bytes from the first byte to the byte that was found
before (inclusive) with their most significant bits cleared (except
for the last one) is interpreted as a little-endian base-128 integer.
This integer is the result of the decoding.
4. Block Structure
A block consists of three parts:
- block header,
- base transaction body,
- list of transaction identifiers.
The list starts with the number of transaction identifiers that it
contains.
4.1 Block Header
Each block starts with a block header. The major version defines the
block header parsing rules (i.e. block header format) and is
incremented with each block header format update. The table below
describes version 1 of the block header format. The minor version
defines the interpretation details that are not related to block
header parsing.
It is always safe to parse the block header of a particular major
version with a parsing procedure suitable for said version, even if
the minor version is unknown. Parsing the block header with an
unknown major version is not safe as the content of the block header
may be misinterpreted.
Werner et al. CryptoNote Blockchain [Page 3]
CRYPTONOTE STANDARD 003 September 2012
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| major_version | varint | Major block header version |
| | | (always 1) |
+---------------+------------------+--------------------------------+
| minor_version | varint | Minor block header version |
| | | |
+---------------+------------------+--------------------------------+
| timestamp | varint | Block creation time |
| | | (UNIX timestamp) |
+---------------+------------------+--------------------------------+
| prev_id | hash | Identifier of the previous |
| | | block |
+---------------+------------------+--------------------------------+
| nonce | 4 bytes | Any value which is used in the |
| | | network consensus algorithm |
+---------------+------------------+--------------------------------+
Table 4.1: Block header structure description
4.2 Base Transaction
Each valid block contains a single base transaction. The base
transaction's validity depends on the block height due to the
following reasons:
- the emission rule is generally defined as a function of time;
- without the block height field, two base transactions could
be indistinguishable as they can have the same hash (see [BH] for
a description of a similar problem in Bitcoin).
Werner et al. CryptoNote Blockchain [Page 4]
CRYPTONOTE STANDARD 003 September 2012
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| version | varint | Transaction format version |
| | | |
+---------------+------------------+--------------------------------+
| unlock_time | varint | UNIX timestamp. See [CNS004] |
| | | |
+---------------+------------------+--------------------------------+
| input_num | varint | Number of inputs. Always 1 for |
| | | base transactions |
+---------------+------------------+--------------------------------+
| input_type | byte | Always 0xff for base |
| | | transactions |
+---------------+------------------+--------------------------------+
| height | varint | Height of the block which |
| | | contains the transaction |
+---------------+------------------+--------------------------------+
| output_num | varint | Number of outputs |
| | | |
+---------------+------------------+--------------------------------+
| outputs | array of outputs | Array of outputs. See [CNS004] |
| | | |
+---------------+------------------+--------------------------------+
| extra_size | varint | Number of bytes in the Extra |
| | | field |
+---------------+------------------+--------------------------------+
| extra | array of bytes | Additional data associated with|
| | | a transaction |
+---------------+------------------+--------------------------------+
Table 4.2: Base transaction structure description
For general transaction structure description see [CNS004].
4.3 List of Transaction Identifiers
Base transaction is followed by a list of transaction identifiers. A
transaction identifier is a transaction body hashed with the Keccak
hash function. The list starts with the number of identifiers and is
followed by the identifiers themselves if it is not empty.
Werner et al. CryptoNote Blockchain [Page 5]
CRYPTONOTE STANDARD 003 September 2012
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| tx_num | varint | Number of transaction |
| | | identifiers |
+---------------+------------------+--------------------------------+
| identifiers | array of hashes | Array of transaction |
| | | identifiers |
+---------------+------------------+--------------------------------+
Table 4.3: List of transaction identifiers structure description
5. Calculation of Block Identifier
The identifier of a block is the result of hashing the following data
with Keccak:
- size of [block_header, Merkle root hash, and the number of
transactions] in bytes (varint)
- block_header,
- Merkle root hash,
- number of transactions (varint).
The goal of the Merkle root hash is to "attach" the transactions
referred to in the list to the block header: once the Merkle root
hash is fixed, the transactions cannot be modified.
5.1 Merkle Root Hash Calculation
Merkle root hash is computed from the list of transactions as
follows: let tx[i] be the i-th transaction in the block, where 0 <= i
<= n-1 (n is the number of transactions) and tx[0] is the base
transaction. Let m be the largest power of two, less than or equal to
n. Define the array h as follows:
h[i] = H(h[2*i] || h[2*i+1])
where 1 <= i <= m-1 or 3*m-n <= i <= 2*m-1.
h[i] = H(tx[i-m])
where m <= i <= 3*m-n-1
h[i] = H(tx[i-4*m+n])
where 6*m-2*n <= i <= 4*m-1.
Where H is the Keccak function that is used throughout CryptoNote,
Werner et al. CryptoNote Blockchain [Page 6]
CRYPTONOTE STANDARD 003 September 2012
and || denotes concatenation. Then, h[1] is the root hash.
The figure below illustrates the calculation of Merkle root hash in a
block with 9 transactions. Each arrow represents a computation of H.
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
|tx[0]| |tx[1]| |tx[2]| |tx[3]| |tx[4]| |tx[5]| |tx[6]| |tx[7]| |tx[8]|
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| | | | | | | | |
| | | | | | | V V
| | | | | | | +-----+ +-----+
| | | | | | | |h[30]| |h[31]|
| | | | | | | +-----+ +-----+
| | | | | | | | |
| | | | | | | +---+---+
| | | | | | | |
V V V V V V V V
+----+ +----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
|h[8]| |h[9]| |h[10]| |h[11]| |h[12]| |h[13]| |h[14]| |h[15]|
+----+ +----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| | | | | | | |
+---+---+ +---+---+ +---+---+ +-----+-----+
| | | |
V V V V
+----+ +----+ +----+ +----+
|h[4]| |h[5]| |h[6]| |h[7]|
+----+ +----+ +----+ +----+
| | | |
+-------+-------+ +--------+--------+
| |
V V
+----+ +----+
|h[2]| |h[3]|
+----+ +----+
| |
+----------------+---------------+
|
V
+-----------+
|root = h[1]|
+-----------+
Figure 5.1: Merkle root hash calculation algorithm
Werner et al. CryptoNote Blockchain [Page 7]
CRYPTONOTE STANDARD 003 September 2012
6. References
[BITCOIN] Nakamoto, S., "Bitcoin: A Peer-to-Peer Electronic Cash
System", 2008.
[BH] Andresen, G., comment to pull request "Transition to requiring
block height in block coinbases", June 28, 2012,
https://github.com/bitcoin/bitcoin/pull/1526.
[CNS004] "CryptoNote Transactions", CryptoNote Standard 004,
September 2012.
[XZ] "The .xz File Format", 2009, http://tukaani.org/xz/xz-file-
format-1.0.4.txt.
Werner et al. CryptoNote Blockchain [Page 8]
Raw
cns004.txt
CRYPTONOTE STANDARD 004 Albert Werner
Category: Main Track Kenji Sugihara
Montag
Ardolabar
Tereno
Antonio M. Juarez
CryptoNote
September 2012
CryptoNote Transactions
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the transfer of assets
between users through transactions. Each transaction consists of
inputs (i.e. references to the funds owned by the sender prior to the
transaction) and outputs (i.e. records of the subsequent ownership of
those funds). As a proof of ownership, the sender digitally signs the
transaction with his secret keys in zero-knowledge, using one-time
ring signature.
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Transaction Structure . . . . . . . . . . . . . . . . . . . . . 3
3.1 Transaction Prefix . . . . . . . . . . . . . . . . . . . . 4
3.2 Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.1 txin_gen . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.2 txin_to_key . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.3.1 txout_to_key . . . . . . . . . . . . . . . . . . . . . 7
3.4 unlock_time . . . . . . . . . . . . . . . . . . . . . . . . 8
4. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Werner et al. CryptoNote Transactions [Page 1]
CRYPTONOTE STANDARD 004 September 2012
1. Introduction
Each transaction can be considered as a transfer of asset ownership.
Typically, there are two parties: the sender and the receiver. In
CryptoNote, we will refer to asset as "coins" or "money".
Sender collects references to the money he is willing to redistribute
into an array of inputs. Then he generates a number of keys
recognizable by receiver and puts them into an array of outputs,
together with the amounts. Some of the outputs will return the odd
money to the sender, in case there is any.
To prove his ownership and to protect the transaction from being
altered, the sender generates a signature using his secret key and
attaches it to the transaction. This operation is performed for each
input, so the number of signatures would be the same as the number of
inputs.
2. Definitions
base transaction: a transaction that generates new coins
block: a set of data (payload) with a block header
block height: the distance between the block and the genesis block in
the blockchain
double-spending: the result of successfully spending an amount of
money more than once
input: a reference to an asset owned by the sender prior to the
transaction
output: a new record of ownership of an asset transferred by the
transaction
peer: a participant in the p2p (peer-to-peer) CryptoNote network
transaction: a single record of assets ownership transfer
transaction prefix: the part of a transaction that contains all the
data except signatures
Werner et al. CryptoNote Transactions [Page 2]
CRYPTONOTE STANDARD 004 September 2012
3. Transaction Structure
Each transaction consists of two parts:
1. Prefix. This part contains all the data about the previous and
the new owners of the money, including how and when the funds
contained in transaction can be released, and, possibly, some
extra information. The whole structure must be hashed and signed
by the sender.
2. Signatures. An array of signatures which prove the sender's
money ownership (see [CNS002]).
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| prefix | transaction | Transaction data without the |
| | prefix | signatures. See section 3.1 |
+---------------+------------------+--------------------------------+
| signatures | array of | Array of transaction |
| | signatures | signatures |
+---------------+------------------+--------------------------------+
Table 3: Transaction structure description
Werner et al. CryptoNote Transactions [Page 3]
CRYPTONOTE STANDARD 004 September 2012
3.1 Transaction Prefix
The table below describes version 1 of transaction_prefix.
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| version | varint | Transaction format version |
| | | |
+---------------+------------------+--------------------------------+
| unlock_time | varint | UNIX timestamp |
| | | |
+---------------+------------------+--------------------------------+
| input_num | varint | Number of inputs |
| | | |
+---------------+------------------+--------------------------------+
| inputs | array of inputs | Array of inputs. See section |
| | | 3.2 |
+---------------+------------------+--------------------------------+
| output_num | varint | Number of outputs |
| | | |
+---------------+------------------+--------------------------------+
| outputs | array of outputs | Array of outputs. See section |
| | | 3.3 |
+---------------+------------------+--------------------------------+
| extra_size | varint | Number of bytes in the Extra |
| | | field |
+---------------+------------------+--------------------------------+
| extra | array of bytes | Additional data associated |
| | | with a transaction |
+---------------+------------------+--------------------------------+
Table 3.1: Transaction prefix structure description
- version: Version defines the transaction parsing rules (i.e.
transaction content) and is incremented by each transaction format
update. Parsing transactions with transaction_prefix of an unknown
version is not safe because transaction content could be
misinterpreted. Currently only transactions of version 1 are
defined.
- unlock_time: This field stores the timestamp corresponding to
the time the funds may be redeemed by another transaction. See
section 3.4.
- inputs: This array consists of one or more inputs. See section
3.2.
Werner et al. CryptoNote Transactions [Page 4]
CRYPTONOTE STANDARD 004 September 2012
- outputs: This array consists of one or more outputs. Each output
is a tuple (amount, target), where targets can be of different
types.
- extra: This field may store arbitrary information. Usually it is
used as a part of one-time key generation process.
For varint (variable-length encoding of integers) description see
section 3 of [CNS003].
3.2 Inputs
Each input contains the information about a particular sum that is
used by the transaction. See [CNS002] for details on how the sender
proves his ownership of the funds.
Allowed types of inputs are txin_gen and txin_to_key.
3.2.1 txin_gen
This type is used only once per block as the sole input of the very
first transaction. This transaction can be created only by the peer
who has found the block.
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| input_type | byte | Input type. |
| | | 0xff = txin_gen |
+---------------+------------------+--------------------------------+
| height | varint | Height of the block which |
| | | contains the transaction |
+---------------+------------------+--------------------------------+
Table 3.2.1: txin_gen structure description
See [CNS003] for details.
Werner et al. CryptoNote Transactions [Page 5]
CRYPTONOTE STANDARD 004 September 2012
3.2.2 txin_to_key
This is the most frequent type of input, since it corresponds to the
common case with the sole owner of the funds spending his money. Each
input "spends" one of the past outputs of type txout_to_key in a way
that indistinguishably hides this output among the others. To
anonymously prove his ownership the sender must create a ring
signature and put it into the array of signatures at the end of the
transaction (see [CNS002]).
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| input_type | byte | Input type. |
| | | 0x2 = txin_to_key |
+---------------+------------------+--------------------------------+
| amount | varint | Input amount |
| | | |
+---------------+------------------+--------------------------------+
| key_offset_num| varint | Number of keys used by the |
| | | input |
+---------------+------------------+--------------------------------+
| key_offsets | array of varints | Offsets corresponding to the |
| | | outputs referenced by the input|
+---------------+------------------+--------------------------------+
| key_image | key image | Image of the key of the output |
| | | spent by the input, used to |
| | | prevent double-spending |
+---------------+------------------+--------------------------------+
Table 3.2.2: txin_to_key structure description
- amount: This field stores the amount of money; this value is
equal to the corresponding output's amount, which is actually
being spent.
- key_offsets: The list of offsets in the global array of outputs
of type txout_to_key having the same amount as the input. The
first value is the ordinal number of the first referenced output
among those having the same amount. Each of the following values
is the offset of the next referenced output relative to the
previous one. One of the outputs referenced is the actual output
being spent, but only the sender known which one it is. The array
of the corresponding public keys is a part of one-time ring
signature verification algorithm input [CNS002].
- key_image: This field stores the image of the output's key. Each
Werner et al. CryptoNote Transactions [Page 6]
CRYPTONOTE STANDARD 004 September 2012
key has only one image, which is used to prevent double-spending.
Only the sender can compute this value, because this process
requires the knowledge of the corresponding secret key. The same
value occurring in more than one input indicates that the same
output is being spent more than once. Note that while it prevents
double-spending, each output may be nonetheless used in any number
of key_offsets as a hiding factor. The key image is a part of one-
time ring signature [CNS002].
3.3 Outputs
Each output is a tuple (amount, the way how these funds can be
redeemed). The sum of all outputs' amounts must not exceed the sum of
all inputs' amounts.
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| amount | varint | Output amount |
| | | |
+---------------+------------------+--------------------------------+
| target | output target | Output destination. |
| | | Destinations can be of |
| | | different types |
+---------------+------------------+--------------------------------+
Table 3.3: Output structure description
- amount: The amount of money being transferred to the new owner.
- target: The content of this field specifies the way the new
owner can claim the money. Allowed type is txout_to_key.
3.3.1 txout_to_key
This type of output target corresponds to the most common case: a
single receiver gets the right to redeem the amount specified in the
output using his own secret key. The target content is therefore the
corresponding public key.
Werner et al. CryptoNote Transactions [Page 7]
CRYPTONOTE STANDARD 004 September 2012
+---------------+------------------+--------------------------------+
| Field | Type | Content |
+---------------+------------------+--------------------------------+
| output_type | byte | Output type. |
| | | 0x2 = txout_to_key |
+---------------+------------------+--------------------------------+
| key | public key | Output public key |
| | | |
+---------------+------------------+--------------------------------+
Table 3.3.1: txout_to_key structure description
- key: The field stores the receiver's one-time public key.
Instead of using a permanent receiver's public key, the sender
utilizes Diffie-Hellman protocol [DH] (using his own random data
and the recipient's address) to obtain a unique key. Thus he
achieves unlinkability of all keys and transactions.
3.4 unlock_time
Creating a transaction, the sender specifies the unlock_time. If this
value is less than CRYPTONOTE_MAX_BLOCK_NUMBER (500000000), then it
is interpreted as the block height at which the funds are unlocked.
Otherwise, the value is interpreted as the UNIX timestamp.
unlock_time is used as a way to temporarily lock the funds.
Precisely, each output can only be spent (or referenced by an input,
even if it is not really spent) after the unlock_time elapses. Until
then these funds are considered locked and non-spendable.
4. References
[CNS002] "CryptoNote Signatures", CryptoNote Standard 002, May 2012.
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[DH] Diffie, W., and M. Hellman, "New Directions in Cryptography",
1976.
Werner et al. CryptoNote Transactions [Page 8]
Raw
cns005.txt
CRYPTONOTE STANDARD 005 Albert Werner
Category: Main Track Montag
Prometheus
Tereno
CryptoNote
October 2012
CryptoNote Transaction Extra Field
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the way extra data can
be added to a CryptoNote transaction. The content of transaction
Extra field is not verified by the network. Transaction Extra field
can contain arbitrary data.
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Extra Field Format . . . . . . . . . . . . . . . . . . . . . . 2
4. Sub-Field Tags . . . . . . . . . . . . . . . . . . . . . . . . 3
5. Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Werner et al. CryptoNote Transaction Extra Field [Page 1]
CRYPTONOTE STANDARD 005 October 2012
1. Introduction
Every transaction contains the Extra field, which is a part of
transaction prefix (i.e. is signed) [CNS004].
All network nodes verify CryptoNote transactions before they are
included into blocks. If verification fails, a transaction will be
rejected. However, the content of Extra field is not verified.
2. Definitions
transaction: a single record of assets ownership transfer
transaction prefix: the part of a transaction that contains all the
data except signatures
3. Extra Field Format
The value of Extra field is an array of bytes. In transactions, the
array is preceded by its size value:
+------------+--------------------------+
| Size | Transaction Extra data |
| (varint) | (array of bytes) |
+------------+--------------------------+
Figure 3a: Extra field size
The Extra field can be used to store certain user-defined content.
There are common rules for the interpretation of the content of Extra
field to ensure compatibility among different software.
The Extra field can contain several sub-fields. Each sub-field
contains a sub-field tag followed by sub-field content. The sub-field
tag indicates the nature of the data. In some cases the size of the
data is implied by the sub-field tag itself (Figure 3b). In other
cases the size is specified explicitly after the sub-field tag
(Figure 3c). The list of the defined sub-field tags is provided in
the next section.
Werner et al. CryptoNote Transaction Extra Field [Page 2]
CRYPTONOTE STANDARD 005 October 2012
+-------+--------+
| Tag | Data |
+-------+--------+
Figure 3b: Data size implied by the sub-field tag
+-------+--------+--------+
| Tag | Size | Data |
+-------+--------+--------+
Figure 3c: Data size specified explicitly
If the data size is specified explicitly, it is encoded as varint
(variable-length encoding of integers). See section 3 of [CNS003].
4. Sub-Field Tags
This section defines known sub-fields tags and the corresponding data
sizes. If the size is missing in this table, it has to be explicitly
specified as shown in Figure 3c.
+---------------+-------------+-------------------------------------+
| Value | Length | Meaning |
+---------------+-------------+-------------------------------------+
| 0x00 | - | Transaction padding. |
| | | The following restrictions apply: |
| | | - padding is allowed only at the |
| | | end of the Extra field, |
| | | - padding can only contain null |
| | | bytes, |
| | | - the padding length is limited |
| | | to 255 bytes, |
| | | - no explicit size is specified |
| | | for padding (it occupies the |
| | | remaining space of the Extra |
| | | field) |
+---------------+-------------+-------------------------------------+
| 0x01 | 32 bytes | Transaction public key |
+---------------+-------------+-------------------------------------+
| 0x02 | - | Extra nonce (for pooled mining) |
+---------------+-------------+-------------------------------------+
Table 4: Sub-field tag descriptions
Werner et al. CryptoNote Transaction Extra Field [Page 3]
CRYPTONOTE STANDARD 005 October 2012
5. Example
Below is an example of Extra field of a base transaction with three
sub-fields:
- transaction public key (size is omitted for the public key;
it always equals 32 bytes),
- extra nonce (size is specified explicitly),
- transaction padding (size is omitted; only null bytes are
possible).
+--------------------+--------+
| Extra field size | 0x78 |
+--------------------+--------+
+--------------------+--------+-----------------------+
| Tx public key | 0x01 | 32-byte public key |
+--------------------+--------+-----------------------+
Tag Data
+--------------------+--------+--------+-------------+
| Extra nonce | 0x02 | 0x52 | . . . . . |
+--------------------+--------+--------+-------------+
Tag Size Data
+--------------------+--------+-------------+
| Tx size padding | 0x00 | 0x00 0x00 |
+--------------------+--------+-------------+
Tag Data
Figure 5: Transaction Extra field example
6. References
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[CNS004] "CryptoNote Transactions", CryptoNote Standard 004,
September 2012.
Werner et al. CryptoNote Transaction Extra Field [Page 4]
Raw
cns006.txt
CRYPTONOTE STANDARD 006 Nicolas van Saberhagen
Category: Main Track Seigen
Johannes Meier
Richard Lem
November 2012
CryptoNote One-Time Keys
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the exact method of
achieving the unlinkability property of transactions: the anonymity
of receivers. Unique keys are generated for each payment via modified
Diffie-Hellman protocol [DH].
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Data Types and Accessory Functions . . . . . . . . . . . . . . 3
4. The Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . 3
5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Van Saberhagen et al. CryptoNote One-Time Keys [Page 1]
CRYPTONOTE STANDARD 006 November 2012
1. Introduction
CryptoNote utilizes peer-to-peer transactions to transfer asset
ownership between anonymous users. The sender collects references to
the money he is willing to redistribute into an array of inputs.
Then, he generates a number of public keys that can be recognized by
the receiver and puts them into an array of outputs, together with
the corresponding sums.
Every user remains anonymous as long as his public payment address
has no connection with his real identity and no information contained
in transactions leads to that address. Therefore, each output's
public key must be unlinkable to the receiver's address: no third
party should be able to derive the address from the output key and
vice versa.
CryptoNote's solution is based on one-time keys which the sender
derives from random data and the receiver's address. Upon receiving a
transaction, user scans all output keys and checks if he can recover
the corresponding secret key. He succeeds if and only if that
particular output was sent to his address.
2. Definitions
address: a textual representation of a user's public keys required to
make a payment
input: a reference to an asset owned by the sender prior to the
transaction
output: a new record of ownership of an asset transferred by the
transaction
public key: a datum used to identify a peer for the purpose of
digital signature verification
secret key: data known to a peer only, which enables him to create
digital signatures under his identity
transaction: a single record of assets ownership transfer
Van Saberhagen et al. CryptoNote One-Time Keys [Page 2]
CRYPTONOTE STANDARD 006 November 2012
3. Data Types and Accessory Functions
CryptoNote's signature scheme uses Curve25519 (see [CURVE]) as the
underlying group. Group elements are encoded in the same way as in
Ed25519 (see [ED25519]).
The hash function H is the same Keccak function that is used in
CryptoNote. When the value of the hash function is interpreted as a
scalar, it is converted into a little-endian integer and taken modulo
l.
4. The Scheme
Output key generation:
- Sender selects a sum S that he wants to transfer to the
address (A,B).
- He generates a random integer r modulo l and computes a value
R = r*G. R is called tx_pubkey.
- Then he computes a one-time public key P = H(r*A || n)*G + B,
where n is the index of the output in the transaction, encoded
as varint (see section 3 of [CNS003]).
- The pair (S, P) is put in the transaction output. Refer
to [CNS004] for more information on CryptoNote transactions.
- The value R is put in the Extra field. See [CNS005].
Secret key recovery:
- Receiver checks every output of every transaction to find if it
was sent to his address.
- For every output he computes P' = H(a*R || n)*G + B.
- If P' is equal to the output key P, that output was sent to him.
- The corresponding secret key x for P (i.e. such that P = x*G)
can be computed as follows: x = H(a*R || n) + b.
Where || denotes concatenation. The general scheme for output key
generation and secret key recovery is provided in the figure below.
Van Saberhagen et al. CryptoNote One-Time Keys [Page 3]
CRYPTONOTE STANDARD 006 November 2012
+--------+ +-----------+
| Sender | | Receiver |
+----+---+ +-----+-----+
| |
| +-----------+------------+
| | A, a <- generate_key() |
| | B, b <- generate_key() |
| +-----------+------------+
| |
| A, B |
|<------------------------|
| |
+------------+-----------+ |
| R, r <- generate_key() | |
| P <- H(r*A || n)*G+B | |
+------------+-----------+ |
| |
| R, P |
|------------------------>|
| |
| +-----------+------------+
| | P' <- H(a*R || n)*G+B |
| | if P = P' then: |
| | x <- H(a*R || n)+b |
| +-----------+------------+
| |
' '
Figure 4: One-time keys in CryptoNote transactions
5. References
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[CNS004] "CryptoNote Transactions", CryptoNote Standard 004,
September 2012.
[CNS005] "CryptoNote Transaction Extra Field", CryptoNote Standard
005, October 2012.
[CURVE] Bernstein, D. J., "Curve25519: new Diffie-Hellman speed
records", 2006, http://cr.yp.to/ecdh/curve25519-20060209.pdf.
[DH] Diffie, W., and M. Hellman, "New Directions in Cryptography",
1976.
Van Saberhagen et al. CryptoNote One-Time Keys [Page 4]
CRYPTONOTE STANDARD 006 November 2012
[ED25519] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., and B.-
Y. Yang, "High-speed high-security signatures", 2011,
http://ed25519.cr.yp.to/ed25519-20110926.pdf.
Van Saberhagen et al. CryptoNote One-Time Keys [Page 5]
Raw
cns007.txt
CRYPTONOTE STANDARD 007 Antonio M. Juarez
Category: Main Track Oscar Norton
Neocortex
Albert Werner
CryptoNote
November 2012
CryptoNote Keys and Addresses
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines various types of user
keys used in CryptoNote and the way the addresses are encoded into
alphanumeric strings.
Copyright and License Notice
Copyright (c) 2012 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Address and Keys . . . . . . . . . . . . . . . . . . . . . . . 2
4. Address Serialization . . . . . . . . . . . . . . . . . . . . . 3
5. CryptoNote Base58 . . . . . . . . . . . . . . . . . . . . . . . 4
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Juarez et al. CryptoNote Keys and Addresses [Page 1]
CRYPTONOTE STANDARD 007 November 2012
1. Introduction
CryptoNote Standards can refer to the term "keys" in two cases:
1) One-time private and public keys used in transactions.
txout_to_key is the basic transaction type in CryptoNote. See
[CNS004] for details.
2) User's permanent keys stored in personal CryptoNote wallets.
They are used for checking incoming transaction and deriving one-
time private keys for ring signatures.
Each user has two pairs of (private, public) permanent keys by
default. The public parts of the keys are represented as user
address.
2. Definitions
public key: a datum used to identify a peer for the purpose of
digital signature verification
secret key: data known to a peer only, which enables him to create
digital signatures under his identity
3. Address and Keys
In order to send money, one needs two public keys corresponding to
the two secret keys the receiver possesses. These keys allow him to
send unlinkable payments (see [CNS002] and [CNS006] for details).
+----------------+
| |
| Public key A |
| |
+----------------+
| |
| Public key B |
| |
+----------------+
Figure 3a: Full address for unlinkable payments
When serialized to a string, these keys become a human-friendly
CryptoNote address.
Juarez et al. CryptoNote Keys and Addresses [Page 2]
CRYPTONOTE STANDARD 007 November 2012
Spend key is a pair of secret keys corresponding to the public keys
in a CryptoNote address. Spend key is required to sign transactions.
+-----------------+
| |
| Secret key a |
| |
+-----------------+
| |
| Secret key b |
| |
+-----------------+
Figure 3b: Spend key
View key consists of one secret key corresponding to a public key in
a CryptoNote address and one public key from the same address. View
key allows its holder to identify incoming transactions,
circumventing unlinkability. Said key does not allow the holder to
spend any funds.
+----------------+
| |
| Secret key a |
| |
+----------------+
| |
| Public key B |
| |
+----------------+
Figure 3c: View key
CryptoNote keys are Ed25519 keys encoded into 32 bytes. See
[ED25519].
4. Address Serialization
CryptoNote addresses are serialized to strings using CryptoNote
Base58 encoding scheme. The data encoded consists of three parts:
- public address prefix (used to distinguish the addresses of
different currencies),
- a pair of public keys,
Juarez et al. CryptoNote Keys and Addresses [Page 3]
CRYPTONOTE STANDARD 007 November 2012
- checksum.
The pseudo-code below defines the process of generating an address:
Checksum = H(Varint(Prefix) || A || B)[0..3]
SerializedString = Base58(Prefix || A || B || Checksum)
H here is the Keccak function that is used in CryptoNote, and ||
denotes concatenation. For varint (variable-length encoding of
integers) description see section 3 of [CNS003].
Keccak
+-----------------------------------+
| |
| V
+---------+-------------+-------------+ +----------+--------------+
| Public | | | | Checksum | |
| address | A | B | | (first | Unused |
| prefix | | | | 4 bytes) | |
+---------+-------------+-------------+ +----------+--------------+
+----------------------------------------------------+
|
| Base58
V
+--------------------+
| CryptoNote Address |
+--------------------+
Figure 4: Address serialization algorithm
5. CryptoNote Base58
CryptoNote Base58 is a binary-to-text encoding scheme used to
represent arbitrary binary data as a sequence of alphanumeric
characters.
CryptoNote Base58 uses the following alphabet:
123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz
The input is split into 8-byte blocks. The last block may be smaller
than 8 bytes. Each block is interpreted as a big-endian integer,
converted into base 58 (again, big-endian), and encoded using the
alphabet shown above. The number of base-58 digits used to encode a
block is the smallest number of digits sufficient to encode every
Juarez et al. CryptoNote Keys and Addresses [Page 4]
CRYPTONOTE STANDARD 007 November 2012
block of the same size. For example, 8-byte blocks are encoded using
11 characters.
6. References
[CNS002] "CryptoNote Signatures", CryptoNote Standard 002, May 2012.
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[CNS004] "CryptoNote Transactions", CryptoNote Standard 004,
September 2012.
[CNS006] "CryptoNote One-Time Keys", CryptoNote Standard 006,
November 2012.
[ED25519] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., and B.-
Y. Yang, "High-speed high-security signatures", 2011,
http://ed25519.cr.yp.to/ed25519-20110926.pdf.
Juarez et al. CryptoNote Keys and Addresses [Page 5]
Raw
cns008.txt
CRYPTONOTE STANDARD 008 Seigen
Category: Main Track Max Jameson
Tuomo Nieminen
Neocortex
Antonio M. Juarez
CryptoNote
March 2013
CryptoNight Hash Function
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the CryptoNote's default
proof-of-work hash function, CryptoNight.
Copyright and License Notice
Copyright (c) 2013 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Scratchpad Initialization . . . . . . . . . . . . . . . . . . . 2
4. Memory-Hard Loop . . . . . . . . . . . . . . . . . . . . . . . 4
5. Result Calculation . . . . . . . . . . . . . . . . . . . . . . 6
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Seigen et al. CryptoNight Hash Function [Page 1]
CRYPTONOTE STANDARD 008 March 2013
1. Introduction
CryptoNight is a memory-hard hash function. It is designed to be
inefficiently computable on GPU, FPGA and ASIC architectures. The
CryptoNight algorithm's first step is initializing large scratchpad
with pseudo-random data. The next step is numerous read/write
operations at pseudo-random addresses contained in the scratchpad.
The final step is hashing the entire scratchpad to produce the
resulting value.
2. Definitions
hash function: an efficiently computable function which maps data of
arbitrary size to data of fixed size and behaves similarly to a
random function
scratchpad: a large area of memory used to store intermediate values
during the evaluation of a memory-hard function
3. Scratchpad Initialization
First, the input is hashed using Keccak [KECCAK] with parameters b =
1600 and c = 512. The bytes 0..31 of the Keccak final state are
interpreted as an AES-256 key [AES] and expanded to 10 round keys. A
scratchpad of 2097152 bytes (2 MiB) is allocated. The bytes 64..191
are extracted from the Keccak final state and split into 8 blocks of
16 bytes each. Each block is encrypted using the following procedure:
for i = 0..9 do:
block = aes_round(block, round_keys[i])
Where aes_round function performs a round of AES encryption, which
means that SubBytes, ShiftRows and MixColumns steps are performed on
the block, and the result is XORed with the round key. Note that
unlike in the AES encryption algorithm, the first and the last rounds
are not special. The resulting blocks are written into the first 128
bytes of the scratchpad. Then, these blocks are encrypted again in
the same way, and the result is written into the second 128 bytes of
the scratchpad. Each time 128 bytes are written, they represent the
result of the encryption of the previously written 128 bytes. The
process is repeated until the scratchpad is fully initialized.
This diagram illustrates scratchpad initialization:
Seigen et al. CryptoNight Hash Function [Page 2]
CRYPTONOTE STANDARD 008 March 2013
+-----+
|Input|
+-----+
|
V
+--------+
| Keccak |
+--------+
|
V
+-------------------------------------------------------------+
| Final state |
+-------------+--------------+---------------+----------------+
| Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
+-------------+--------------+---------------+----------------+
| |
V |
+-------------+ V
| Round key 0 |------------+---+->+-----+
+-------------+ | | | |
| . | | | | |
| . | | | | AES |
| . | | | | |
+-------------+ | | | |
| Round key 9 |----------+-|-+-|->+-----+ +---+
+-------------+ | | | | | | |
| | | | +------------------->| |
| | | | | | |
| | | | V | |
| | | +->+-----+ | |
| | | | | | S |
| | | | | | |
| | | | AES | | c |
| | | | | | |
| | | | | | r |
| | +--->+-----+ | |
| | | | a |
| | +------------------->| |
| | . | t |
| | . | |
| | . | c |
| | +------------------->| |
| | | | h |
| | V | |
| +----->+-----+ | p |
| | | | |
| | | | a |
| | AES | | |
Seigen et al. CryptoNight Hash Function [Page 3]
CRYPTONOTE STANDARD 008 March 2013
| | | | d |
| | | | |
+------->+-----+ | |
| | |
+------------------->| |
| |
+---+
Figure 3: Scratchpad initialization diagram
4. Memory-Hard Loop
Prior to the main loop, bytes 0..31 and 32..63 of the Keccak state
are XORed, and the resulting 32 bytes are used to initialize
variables a and b, 16 bytes each. These variables are used in the
main loop. The main loop is iterated 524,288 times. When a 16-byte
value needs to be converted into an address in the scratchpad, it is
interpreted as a little-endian integer, and the 21 low-order bits are
used as a byte index. However, the 4 low-order bits of the index are
cleared to ensure the 16-byte alignment. The data is read from and
written to the scratchpad in 16-byte blocks. Each iteration can be
expressed with the following pseudo-code:
scratchpad_address = to_scratchpad_address(a)
scratchpad[scratchpad_address] = aes_round(scratchpad
[scratchpad_address], a)
b, scratchpad[scratchpad_address] = scratchpad[scratchpad_address],
b xor scratchpad[scratchpad_address]
scratchpad_address = to_scratchpad_address(b)
a = 8byte_add(a, 8byte_mul(b, scratchpad[scratchpad_address]))
a, scratchpad[scratchpad_address] = a xor
scratchpad[scratchpad_address], a
Where, the 8byte_add function represents each of the arguments as a
pair of 64-bit little-endian values and adds them together,
component-wise, modulo 2^64. The result is converted back into 16
bytes.
The 8byte_mul function, however, uses only the first 8 bytes of each
argument, which are interpreted as unsigned 64-bit little-endian
integers and multiplied together. The result is converted into 16
bytes, and finally the two 8-byte halves of the result are swapped.
This diagram illustrates the memory-hard loop:
Seigen et al. CryptoNight Hash Function [Page 4]
CRYPTONOTE STANDARD 008 March 2013
+-------------------------------------------------------------+
| Final state |
+-------------+--------------+---------------+----------------+
| Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
+-------------+--------------+---------------+----------------+
| |
| +-----+ |
+-->| XOR |<--+
+-----+
| |
+----+ +----+
| |
V V
+---+ +---+
| a | | b |
+---+ +---+
| |
--------------------- REPEAT 524288 TIMES ---------------------
| | address +---+
+-------------|----------------------------------->| |
| +-----+ | read | |
+-->| AES |<--|------------------------------------| |
| +-----+ V | |
| | +-----+ | S |
| +-->| XOR | | |
| | +-----+ write | c |
| | | +------------------------------>| |
| | +----+ address | r |
| +------------------------------------------>| |
| | +-----------+ read | a |
| +->| 8byte_mul |<--+------------------------| |
| | +-----------+ | | t |
| | | | | |
| | V | | c |
| | +-----------+ | | |
+------|->| 8byte_add | | | h |
| +-----------+ | | |
| | | write | p |
| +---------|----------------------->| |
| | | | a |
| V | | |
| +-----+ | | d |
| | XOR |<-----+ | |
| +-----+ | |
+------+ | | |
+-------------|-+ | |
| | +---+
-------------------------- END REPEAT -------------------------
Seigen et al. CryptoNight Hash Function [Page 5]
CRYPTONOTE STANDARD 008 March 2013
| |
Figure 4: Memory-hard loop diagram
5. Result Calculation
After the memory-hard part, bytes 32..63 from the Keccak state are
expanded into 10 AES round keys in the same manner as in the first
part.
Bytes 64..191 are extracted from the Keccak state and XORed with the
first 128 bytes of the scratchpad. Then the result is encrypted in
the same manner as in the first part, but using the new keys. The
result is XORed with the second 128 bytes from the scratchpad,
encrypted again, and so on.
After XORing with the last 128 bytes of the scratchpad, the result is
encrypted the last time, and then the bytes 64..191 in the Keccak
state are replaced with the result. Then, the Keccak state is passed
through Keccak-f (the Keccak permutation) with b = 1600.
Then, the 2 low-order bits of the first byte of the state are used to
select a hash function: 0=BLAKE-256 [BLAKE], 1=Groestl-256 [GROESTL],
2=JH-256 [JH], and 3=Skein-256 [SKEIN]. The chosen hash function is
then applied to the Keccak state, and the resulting hash is the
output of CryptoNight.
The diagram below illustrates the result calculation:
Seigen et al. CryptoNight Hash Function [Page 6]
CRYPTONOTE STANDARD 008 March 2013
+-------------------------------------------------------------+
| Final state |
+-------------+--------------+---------------+----------------+
| Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
+-------------+--------------+---------------+----------------+
| | | |
| +--------+ | |
| V | | |
|+-------------+ | | |
|| Round key 0 |-|---+---+ | |
|+-------------+ | | | | |
|| . | | | | | |
|| . | | | | | |
|| . | | | | | |
|+-------------+ | | | | |
+---+ || Round key 9 |-|-+-|-+ | V |
| | |+-------------+ | | | | | +-----+ |
| |-|----------------|-|-|-|-|->| XOR | |
| | | | | | | | +-----+ |
| S | | | | | | | | |
| | | | | | | | V |
| c | | | | | | +->+-----+ |
| | | | | | | | | |
| r | | | | | | | | |
| | | | | | | | AES | |
| a | | | | | | | | |
| | | | | | | | | |
| t | | | | | +--->+-----+ |
| | | | | | | |
| c | | | | | V |
| | | | | | +-----+ |
| h |-|----------------|-|-|----->| XOR | |
| | | | | | +-----+ |
| p | | | | | | |
| | | | | | . |
| a | | | | | . |
| | | | | | . |
| d | | | | | | |
| | | | | | V |
| | | | | | +-----+ |
| |-|----------------|-|-|----->| XOR | |
| | | | | | +-----+ |
+---+ | | | | | |
| | | | V |
| | | +----->+-----+ |
| | | | | |
| | | | | |
| | | | AES | |
Seigen et al. CryptoNight Hash Function [Page 7]
CRYPTONOTE STANDARD 008 March 2013
| | | | | |
| | | | | |
| | +------->+-----+ |
| | | |
V V V V
+-------------+--------------+---------------+----------------+
| Bytes 0..31 | Bytes 32..63 | Bytes 64..191 | Bytes 192..199 |
+-------------+--------------+---------------+----------------+
| Modified state |
+-------------------------------------------------------------+
|
V
+----------+
| Keccak-f |
+----------+
| |
+-----------+ |
| |
V V
+-------------+ +-------------+
| Select hash |->| Chosen hash |
+-------------+ +-------------+
|
V
+--------------+
| Final result |
+--------------+
Figure 5: Result calculation diagram
Hash examples:
Empty string:
eb14e8a833fac6fe9a43b57b336789c46ffe93f2868452240720607b14387e11.
"This is a test":
a084f01d1437a09c6985401b60d43554ae105802c5f5d8a9b3253649c0be6605.
6. References
[AES] "Announcing the ADVANCED ENCRYPTION STANDARD", FIPS 197, 2001.
[BLAKE] Aumasson, J.-P., Henzen, L., Meier, W., and R. C.-W. Phan,
"SHA-3 proposal BLAKE", 2010.
[GROESTL] Gauravaram, P., Knudsen, L., Matusiewicz, K., Mendel, F.,
Seigen et al. CryptoNight Hash Function [Page 8]
CRYPTONOTE STANDARD 008 March 2013
Rechberger, C., Schlaffer, M., and S. Thomsen, "Groestl - a SHA-3
candidate", 2011.
[JH] Wu, H., "The Hash Function JH", 2011.
[KECCAK] Bertoni, G., Daemen, J., Peeters, M., and G. Van Assche,
"The Keccak reference", 2011.
[SKEIN] Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare,
M., Kohno, T., Callas, J., and J. Walker, "The Skein Hash Function
Family", 2008.
Seigen et al. CryptoNight Hash Function [Page 9]
Raw
cns009.txt
CRYPTONOTE STANDARD 009 Brandon Hawking
Category: Main Track Pacific_skyline
Yggdrasil
Johannes Meier
CryptoNote
August 2013
CryptoNote Technology
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the core concepts of the
CryptoNote technology and surveys the whole system's workflow. All
transactions are public data and are stored by every peer, yet none
of the private information is revealed. Payments cannot be
unambiguously traced to senders; transfers can only be interlinked by
their owners. Peers validate all the data and rely on proof of work
to reach a consensus. The proof-of-work function guarantees
egalitarian voting, so that none of the participants can utilize
special purpose devices to obtain an excessive voting advantage.
Copyright and License Notice
Copyright (c) 2013 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. CryptoNote Protocol . . . . . . . . . . . . . . . . . . . . . . 3
3.1 Transactions . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.1 Transaction Untraceability . . . . . . . . . . . . . . 4
3.1.2 Transaction Unlinkability . . . . . . . . . . . . . . . 4
3.2 Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Proof-of-Work Function . . . . . . . . . . . . . . . . . . 5
3.4 Adjustable Parameters . . . . . . . . . . . . . . . . . . . 6
4. Asset Exchange . . . . . . . . . . . . . . . . . . . . . . . . 7
5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Hawking et al. CryptoNote Technology [Page 1]
CRYPTONOTE STANDARD 009 August 2013
1. Introduction
CryptoNote is a technology that allows anonymous, unlinkable and
untraceable peer-to-peer payments.
The system is based on Satoshi Nakamoto's Bitcoin [BITCOIN] concept:
a distributed public ledger (blockchain) of transactions (ordered
records of money transfers). Each peer stores a local copy of
blockchain and verifies every new transaction. Hash-based proof of
work [POW] is the solution to "the problem of determining
representation in majority decision making", when some of the data
was missed by an offline peer. If there are multiple conflicting
versions, peers choose the one with more work presented. All data is
sent on the best-effort basis.
2. Definitions
alternative branch: a blockchain branch that includes blocks that are
not on the main branch
block: a dataset (payload) with a block header
blockchain: a tree structure of blocks
blockchain fork: a situation when there are two such peers that the
main branch for each of them is an alternative one for the other peer
double-spending: the result of successfully spending an amount of
money more than once
main branch: the set of blocks that represents the current state of
the distributed ledger
nonce: a field in a block header that peers change as part of the
proof-of-work scheme
peer: a participant in the p2p (peer-to-peer) CryptoNote network
proof of work (PoW): a way for a computer system to demonstrate that
it expended a certain amount of computational resources in support of
a particular decision
ring signature: a class of schemes that allow a user to sign a
message on behalf of a group, making his identity indistinguishable
from the other members of the group
transaction: a single record of assets ownership transfer
Hawking et al. CryptoNote Technology [Page 2]
CRYPTONOTE STANDARD 009 August 2013
3. CryptoNote Protocol
This section describes the principles of the CryptoNote technology.
3.1 Transactions
Each user possesses several unique secret keys, each associated with
a certain amount of money. A key gives user the ability to spend the
money, lock, or even destroy it. At any moment there is a definite
many-to-one mapping between all currency units and keys.
User can divide his funds into smaller pieces or merge several
amounts into one by reassigning ownership from his old keys to new
ones. Each set of such transfers forms a new transaction that will be
stored in the blockchain. Each key (old or new one) belongs to a
sender or to some other user (i.e. there might be several senders and
addressees in a single transaction). See [CNS004] for details.
After a transaction has been created and sent to other peers, it
exists in one of the four possible states:
1. Unconfirmed: every peer is aware of the transaction, but it is
not included in the blockchain yet.
2. Confirmed: the transaction is now a part of the blockchain. In
case of a blockchain fork, newly confirmed transactions may become
unconfirmed again.
3. Irreversible: the transaction has stayed confirmed for some
time. The probability of an irreversible transaction becoming
unconfirmed is negligible.
4. Rejected: the transaction is not included into the blockchain,
since a contradicting one (involving the same funds) has been
confirmed. These transactions cannot be stored in the same
blockchain branch, therefore any rejected transaction should be
abandoned.
The users' privacy depends on how the transactions are constructed.
The properties described below are integral parts of the CryptoNote
anonymous transactions technology:
1. Untraceability: it is impossible to determine the exact sender
of a transaction.
2. Unlinkability: it is impossible to determine whether any two
Hawking et al. CryptoNote Technology [Page 3]
CRYPTONOTE STANDARD 009 August 2013
transactions are sent to the same address.
3.1.1 Transaction Untraceability
The untraceability requirement can be fulfilled through ring
signatures [TRS]. Any signature is, in fact, a proof of the user's
knowledge of the secret key that allows spending the corresponding
amount of money. Regular digital signature schemes ((EC)DSA or
similar) reveal the signer's identity, since they use only one public
key for the verification procedure.
Unlike regular digital signature schemes, a ring signature is a much
more sophisticated scheme that allows a user to sign his message on
behalf of a group. A verifier is able to see that the message was
signed by someone within the group of signers, but he is not able to
determine the exact signer. All public keys required for verification
are indistinguishable in that sense.
To prove the ownership of the money the user randomly chooses public
keys of other users and then adds his key to produce a ring signature
that must be verified with all these keys. The owner of one of those
keys may produce his own ring signature with the same set of public
keys (making his own transaction), and there will still be no way
(better than guessing with 1/n probability) to determine from which
particular key the money was reassigned.
There are several ring signature schemes. An implementor should use a
scheme, which is not completely anonymous, but allows to check
whether two signatures were made under the same secret key. Every
peer should be able to perform this check to prevent double-spending.
One possible algorithm is described in [TRS].
See [CNS002] for details.
3.1.2 Transaction Unlinkability
Usually a person has a public address that unambiguously identifies
him. However, none of his incoming transactions should expose the
connection with this address.
This can be achieved through generating a unique key for each
transfer with the modified Diffie-Hellman protocol [DH]. The original
scheme allows two parties to produce a common secret by exchanging
data via open channels. In CryptoNote, public keys are generated in
such a way that only the recipient can link them to his account,
while even the sender cannot recover the corresponding secret key.
Hawking et al. CryptoNote Technology [Page 4]
CRYPTONOTE STANDARD 009 August 2013
The sender uses the address and his random data to create a new
public key and transfers money to it. The recipient scans all the
keys in new transactions and checks if he can recover the
corresponding secret key. If he succeeds, he learns that he is the
new owner of the money, i.e. the transfer is completed. The keys can
only be linked by the receiver, as this requires the knowledge of the
secret key corresponding to the address.
See [CNS006] for details.
3.2 Blocks
All transactions are stored in a single distributed ledger that
consists of chained blocks. Each block contains a hash reference to
its predecessor, several new transactions that have been sent since
the previous block, and some additional information, such as a
timestamp and nonce (see below). To go along with Nakamoto's notation
[BITCOIN], we will call this ledger the blockchain.
A consensus on the state of the blockchain is achieved by a voting
mechanism called proof of work. Each block is considered valid only
if the value of a special hash function of this block is less than
the target value. Peers that choose to participate in the voting
alter the block by iterating the value of the nonce field in the
header of the block. If the hash of the resulting block meets the
above criterion, the block is added to the blockchain. This
stochastic process provides a continual supply of new blocks. If two
or more blocks with the same predecessor appear simultaneously, a
blockchain fork occurs. If this happens, each peer can choose any of
the branches as a current one. Eventually one of the branches will
outrun the other one, making all peers switch to it.
See [CNS003] for details.
3.3 Proof-of-Work Function
Voting on the state of the blockchain is performed through
calculation of a special hash function. The right choice of the
function is of fundamental importance.
The main concern is security. The blockchain model is proved by
Nakamoto's Bitcoin [BITCOIN] to be safe in case more than 50% of the
hashing power is under the control of honest users. Therefore, a
potential attacker should not be able to acquire massive hashing
power. There should not be a significantly cheaper source of powerful
hardware beyond the reach of ordinary users. For this reason memory-
Hawking et al. CryptoNote Technology [Page 5]
CRYPTONOTE STANDARD 009 August 2013
bound algorithms are superior to CPU-bound.
Another issue with PoW is the nature of voting. Any public mechanism
of a majority decision-making process must satisfy a natural
assumption of egalitarianism. There may be several contradictory
transactions that result in two or more valid versions of the
blockchain (a blockchain fork). Since only one of the versions will
win, it must represent the majority of people, i.e. all users must be
nearly equal in terms of hashing power to guarantee the "majority
rule".
Generally, the hash function must not allow a user to have a
significant advantage over another. The most acceptable way of
discovering new blocks is to use regular hardware, such as a PC, and
utilize uniformly distributed resource (such as fast on-chip memory,
not just CPU power [MBOUND]). Special purpose devices may always be
possible in theory, but their manufacturing costs should be as high
as possible. With the billions of PCs running and millions being
produced every day, an emergence of ASICs with a comparable
speed/cost ratio is inconceivable.
See [CNS008] for the description of CryptoNote default proof-of-work
function.
3.4 Adjustable Parameters
There are many internal parameters in CryptoNote that affect the
performance of the system. The size of blocks and transactions is
limited in order to prevent a flood attack. The proof-of-work
difficulty changes following the hashrate of the whole network to
provide nearly constant time between new blocks. Sometimes these
parameters need to be changed.
There are two ways of changing the parameters: manual (developers
change the parameters with a new software release) or automatic.
However, the first option is not suitable for a distributed software,
as it is crucial that the values of the parameters are the same for
all peers and it is not feasible to make all the peers upgrade
simultaneously.
CryptoNote uses adaptive algorithms instead of hardcoded values. New
values are computed for each new block on the basis of past data. The
values should be adequate to the current state of the system and no
one should be able to arbitrarily manipulate these values unless he
has the majority of hashrate. Only robust statistics should be used
(for example, the median should be used instead of the mean value).
Hawking et al. CryptoNote Technology [Page 6]
CRYPTONOTE STANDARD 009 August 2013
4. Asset Exchange
CryptoNote is an ownership tracking system. It means that the keys
can be associated not only with the money but with any digital asset
as well. It is possible to create a separate blockchain with its own
inner currency and distinct rules. An alternative blockchain can
reuse the proof of work from the main one. As a result, both systems
will combine their hashing powers for better protection against
possible attacks.
Alternatively, a person can use an already existing blockchain as a
platform for a public offering. By proving his ownership of some keys
and announcing that these keys are now associated with a new type of
assets (i.e. company's shares), he can manage these assets within the
blockchain. Asset ownership can be transferred privately just like
money. The only limitation is that it should not be mixed with
another currency or asset; every ring signature must use the keys of
the same "color".
The concept of "colors" within a single blockchain can evolve into a
system more powerful than just a p2p transactions ledger. By
introducing new types of transactions it is possible to create a
private decentralized exchange with any type of assets: money,
shares, or commodities.
5. References
[BITCOIN] Nakamoto, S., "Bitcoin: A Peer-to-Peer Electronic Cash
System", 2008.
[CNS002] "CryptoNote Signatures", CryptoNote Standard 002, May 2012.
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[CNS004] "CryptoNote Transactions", CryptoNote Standard 004,
September 2012.
[CNS006] "CryptoNote One-Time Keys", CryptoNote Standard 006,
November 2012.
[CNS008] "CryptoNight Hash Function", CryptoNote Standard 008, March
2013.
[DH] Diffie, W., and M. Hellman, "New Directions in Cryptography",
1976.
Hawking et al. CryptoNote Technology [Page 7]
CRYPTONOTE STANDARD 009 August 2013
[MBOUND] Abadi, M., Burrows, M., Manasse, M., and T. Wobber,
"Moderately hard, memory-bound functions", 2005.
[POW] Dwork, C., and M. Naor, "Pricing via Processing, Or, Combatting
Junk Mail", 1993.
[TRS] Fujisaki, E., and K. Suzuki, "Traceable Ring Signature", 2007.
Hawking et al. CryptoNote Technology [Page 8]
Raw
cns010.txt
CRYPTONOTE STANDARD 010 Albert Werner
Category: Main Track Marec Pliskov
Montag
CryptoNote
August 2014
CryptoNote Difficulty Adjustment
Abstract
This document is part of the CryptoNote Standards describing a peer-
to-peer anonymous payment system. It defines the method for
maintaining the rate at which blocks are generated.
Copyright and License Notice
Copyright (c) 2014 CryptoNote. This document is available under the
Creative Commons Attribution 3.0 License (international). To view a
copy of the license visit http://creativecommons.org/licenses/by/3.0/
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3. Algorithm Parameters . . . . . . . . . . . . . . . . . . . . . 2
4. Algorithm Description . . . . . . . . . . . . . . . . . . . . . 3
5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Werner et al. CryptoNote Difficulty Adjustment [Page 1]
CRYPTONOTE STANDARD 010 August 2014
1. Introduction
CryptoNote uses a hash-based proof-of-work scheme to reach a
distributed consensus among peers. When connected to the network, a
peer considers the main branch of the blockchain (the branch with the
most work done) to be the reference transaction history. See [CNS003]
and [CNS009] for basic information on CryptoNote blockchain.
The work being done by peers is an iterated hash calculation
[CNS008]. Every block is considered valid only if the value of its
hash is less than or equal to some target value. As the hash rate of
the network changes, the target value is adjusted to keep the rate of
block generation steady.
This document describes the exact algorithm for calculating this
value.
2. Definitions
block: a set of data (payload) with a block header
block height: the distance between the block and the genesis block in
the blockchain
blockchain: a tree structure of blocks
difficulty: a number that measures the amount of work necessary to
find a block
proof of work: a way for a computer system to demonstrate that it
expended a certain amount of computational resources in support of a
particular decision
target: the maximal possible value of the hash of a block header for
it to be considered valid
3. Algorithm Parameters
TargetTime: expected time to find a block. Default value: 120
seconds.
DiffWindow: the number of the previous blocks used by the algorithm
to estimate the hash rate. The algorithm will adjust to small changes
in the hash rate in approximately TargetTime*DiffWindow seconds.
Default value: 720 blocks or one day.
Werner et al. CryptoNote Difficulty Adjustment [Page 2]
CRYPTONOTE STANDARD 010 August 2014
DiffCut: the number of highest and lowest timestamp values to be
ignored, as they are considered to be outliers. Default value: 60.
DiffLag: the number of last blocks that should be discarded previous
to any subsequent computation. This is done to make it harder to
create a blockchain fork with higher cumulative difficulty. Default
value: 15.
4. Algorithm Description
The idea behind the algorithm is to estimate the hash rate of the
network as a ratio of the total difficulty of several last blocks to
the time it took the peers to find these blocks. However, individual
timestamps are not reliable, so the array of timestamps is sorted and
order statistics are used as more robust estimators for the actual
time values. At the same time, the array of past difficulty values is
accurate, so there is no need to sort it.
In addition to this, a few last blocks are completely ignored when
computing the difficulty. This guarantees that in a blockchain fork
of small length, blocks at the same height would have the same
difficulty. This makes it harder to make one of the chains have
higher cumulative difficulty by manipulating timestamps.
In the first step of the algorithm, the exact blocks that are going
to be used in the subsequent computation are determined. There are
three cases:
- If the current branch has no more than DiffWindow blocks, all
blocks are used.
- If the current branch has no less than DiffWindow blocks, but no
more than DiffWindow+DiffLag blocks, the first DiffWindow blocks
are used.
- Otherwise, the last DiffLag blocks are discarded and then the
last DiffWindow blocks are used.
The number of blocks selected by this step will be denoted by N. The
value of N is equal to either DiffWindow or the number of blocks in
the current branch, whichever is smaller.
In the second step, the timestamps of the selected blocks are sorted,
but the difficulty values are left in place.
In the third step, some of the first and some of the last blocks are
discarded. The number of blocks to be discarded is determined as
Werner et al. CryptoNote Difficulty Adjustment [Page 3]
CRYPTONOTE STANDARD 010 August 2014
follows:
- If N is not greater than DiffWindow - 2*DiffCut, no blocks are
discarded.
- Otherwise, the first Ceiling((N + 2*DiffCut - DiffWindow) / 2)
and the last Floor((N + 2*DiffCut - DiffWindow) / 2) are
discarded.
The number of blocks that remain is either DiffWindow - 2*DiffCut or
N, whichever is smaller.
In the last step, the value TotalT is computed as the difference
between the timestamps of the last and the first blocks and the value
TotalD is computed as the sum of the difficulty values of all blocks
except the first (the first block is excluded because it was mined
before the time indicated by its timestamp, so the time it took to
mine it is not included in TotalT). If the value of TotalT is not
positive, it is assumed to be 1. Then, the difficulty of the next
block is Ceiling(TotalD / TotalT * TargetTime).
Special case: the difficulty of the first two blocks is 1.
The target value is computed as follows: Target = Floor((2^256 - 1) /
Difficulty). Alternatively, it is possible to check the hash of a
block without explicitly computing the target value: the block is
valid if Hash*Difficulty < 2^256.
5. References
[CNS003] "CryptoNote Blockchain", CryptoNote Standard 003, September
2012.
[CNS008] "CryptoNight Hash Function", CryptoNote Standard 008, March
2013.
[CNS009] "CryptoNote Technology", CryptoNote Standard 009, August
2013.
Werner et al. CryptoNote Difficulty Adjustment [Page 4]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment