3 Cryptographic Primitives¶
This chapter specifies every cryptographic primitive on which Decred’s consensus rules depend: the hash functions, the elliptic curves, the three signature schemes that scripts can verify, and the Merkle tree used to commit to the transactions of a block. Later chapters use these primitives by name and do not repeat their definitions.
Decred differs from Bitcoin in its choice of primitives more than its structure suggests. Its general-purpose hash is BLAKE-256, not double SHA-256; its proof-of-work hash has been BLAKE-256 and then BLAKE3; and besides ECDSA over secp256k1 its script language can verify Schnorr signatures over secp256k1 (a Decred-specific scheme) and Ed25519 signatures. The definitions below are taken from the reference implementation. Where a primitive is specified by an external standard, the standard is cited and the parameters and any departures from it are stated.
Table 3.1 summarizes the primitives and where they appear.
| Primitive | Section | Used for |
|---|---|---|
| BLAKE-256 (14 rounds) | Section 3.2 | Transaction and block hashes, Merkle trees, signature hashes, the version 1 proof-of-work hash, OP_BLAKE256, OP_HASH160, OP_HASH256, the Schnorr challenge |
| BLAKE3 | Section 3.4 | The version 2 proof-of-work hash (DCP-0011) |
| RIPEMD-160 | Section 3.5 | OP_RIPEMD160, OP_HASH160, address hashes |
| SHA-256 | Section 3.5 | OP_SHA256; HMAC inside deterministic nonce generation (not consensus) |
| SHA-1 | Section 3.5 | OP_SHA1 |
| secp256k1 | Section 3.6 | Public keys for ECDSA and EC-Schnorr-DCRv0 |
| ECDSA | Section 3.8 | OP_CHECKSIG, OP_CHECKMULTISIG and their VERIFY forms |
| EC-Schnorr-DCRv0 | Section 3.9 | OP_CHECKSIGALT with signature type 2; treasury spend authorization |
| Ed25519 | Section 3.10 | OP_CHECKSIGALT with signature type 1 |
| Merkle tree | Section 3.11 | Transaction tree roots in the block header; header commitment proofs |
3.1 Notation¶
A word is a uint32. For words, in the hash function definitions means addition modulo , (^ in pseudocode) is bitwise exclusive or, and is rotation to the right by bits. In pseudocode the mask M32 = 0xffffffff makes the reduction modulo explicit.
For an integer with , is its 32-byte big-endian encoding and its 32-byte little-endian encoding. For a byte string , and interpret as an unsigned integer in big-endian and little-endian order, and is the substring of bytes up to but not including , counting from 0. is concatenation.
The pseudocode follows Section 2.7 and uses these helpers in addition: be32(w), le32(w) and be64(x) encode an integer as 4 or 8 bytes; be32_decode(b) and le32_decode(b) decode 4 bytes; be256(x) is ; int_be(b) and int_le(b) are and ; left_pad(b, 32) prefixes zero bytes up to 32 bytes; blake256 is Algorithm 3.2; hmac_sha256(K, m) is HMAC (RFC 2104 [8]) with SHA-256; pow(a, e, m) is modular exponentiation; and scalar_mult, point_add and INFINITY are elliptic curve scalar multiplication, point addition (complete, handling the identity and doubling) and .
For elliptic curves, upper-case letters denote points and lower-case letters integers. is scalar multiplication, is the point at infinity (the group identity), and , are the affine coordinates of a point , always as fully reduced integers. An integer is odd or even according to its least significant bit after full reduction.
3.2 BLAKE-256¶
BLAKE-256 is the 256-bit member of the BLAKE family, a finalist of the NIST SHA-3 competition, in the final version 1.3 of its specification, which uses 14 rounds [9]. Decred uses it wherever Bitcoin uses SHA-256 or double SHA-256. It is not BLAKE2s (a later, different function with 10 rounds and little-endian words), and it is not the 10-round BLAKE-32 of the first round of the competition. BLAKE-256 is an iterated hash with a 512-bit block, a 256-bit chaining value, and a 64-bit counter of message bits; the specification also defines an optional 128-bit salt. Decred always uses a zero salt, and the definition below is written with the salt removed.
Rule 3.1 · BLAKE-256
Wherever this document writes BLAKE-256, or , the function defined by Algorithm 3.1 and Algorithm 3.2 with the constants of Table 3.2, Table 3.3 and Table 3.4 is meant. Its output is always 32 bytes. An implementation MUST reproduce it bit for bit, including the counter rule for padding-only blocks.dcrd: crypto/blake256/hasher.go · finalize, finalize256 | crypto/blake256/internal/compress/blocks_generic.go · blocksGeneric
3.2.1 Constants¶
The initial chaining value (Table 3.2) is the same as SHA-256′s. The sixteen constants (Table 3.3) are the first 512 bits of the fractional part of . Each round uses one of ten permutations of the message word indices (Table 3.4); round (counting from 0) uses , so rounds 10 to 13 repeat to .
6a09e667 | bb67ae85 | 3c6ef372 | a54ff53a | 510e527f | 9b05688c | 1f83d9ab | 5be0cd19 |
243f6a88 | 85a308d3 | 13198a2e | 03707344 | a4093822 | 299f31d0 | 082efa98 | ec4e6c89 |
452821e6 | 38d01377 | be5466cf | 34e90c6c | c0ac29b7 | c97c50dd | 3f84d5b5 | b5470917 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
| 14 | 10 | 4 | 8 | 9 | 15 | 13 | 6 | 1 | 12 | 0 | 2 | 11 | 7 | 5 | 3 | |
| 11 | 8 | 12 | 0 | 5 | 2 | 15 | 13 | 10 | 14 | 3 | 6 | 7 | 1 | 9 | 4 | |
| 7 | 9 | 3 | 1 | 13 | 12 | 11 | 14 | 2 | 6 | 5 | 10 | 4 | 0 | 15 | 8 | |
| 9 | 0 | 5 | 7 | 2 | 4 | 10 | 15 | 14 | 1 | 11 | 12 | 6 | 8 | 3 | 13 | |
| 2 | 12 | 6 | 10 | 0 | 11 | 8 | 3 | 4 | 13 | 7 | 5 | 15 | 14 | 1 | 9 | |
| 12 | 5 | 1 | 15 | 14 | 13 | 4 | 10 | 0 | 7 | 6 | 3 | 9 | 2 | 8 | 11 | |
| 13 | 11 | 7 | 14 | 12 | 1 | 3 | 9 | 5 | 0 | 15 | 4 | 8 | 6 | 2 | 10 | |
| 6 | 15 | 14 | 9 | 11 | 3 | 0 | 8 | 12 | 2 | 13 | 7 | 1 | 4 | 10 | 5 | |
| 10 | 2 | 8 | 4 | 7 | 6 | 1 | 5 | 15 | 11 | 9 | 14 | 3 | 12 | 13 | 0 |
3.2.2 Compression function¶
The compression function maps a chaining value , a 64-byte block and the counter to a new chaining value. The block is read as sixteen big-endian words . A 16-word state , viewed as a matrix, is initialized from the chaining value, the constants and the counter; each round applies the function to the four columns and then to the four diagonals of the matrix. In the -th application of within round , with , the message word is combined with the constant , and with . In the pseudocode, IV, C and SIGMA are the tables Table 3.2, Table 3.3 and Table 3.4, indexed from 0.
Algorithm 3.1 · BLAKE-256 compression
M32 = 0xffffffff
def rotr32(x, n):
return ((x >> n) | (x << (32 - n))) & M32
def G(v, m, sigma, i, a, b, c, d):
x, y = sigma[2 * i], sigma[2 * i + 1]
v[a] = (v[a] + v[b] + (m[x] ^ C[y])) & M32
v[d] = rotr32(v[d] ^ v[a], 16)
v[c] = (v[c] + v[d]) & M32
v[b] = rotr32(v[b] ^ v[c], 12)
v[a] = (v[a] + v[b] + (m[y] ^ C[x])) & M32
v[d] = rotr32(v[d] ^ v[a], 8)
v[c] = (v[c] + v[d]) & M32
v[b] = rotr32(v[b] ^ v[c], 7)
def blake256_compress(h: list[uint32], block: bytes, t: uint64) -> list[uint32]:
m = [be32_decode(block[4 * i : 4 * i + 4]) for i in range(16)]
t0, t1 = t & M32, t >> 32
v = h[0:8] + C[0:4] + [t0 ^ C[4], t0 ^ C[5], t1 ^ C[6], t1 ^ C[7]]
for r in range(14):
sigma = SIGMA[r % 10]
G(v, m, sigma, 0, 0, 4, 8, 12) # columns
G(v, m, sigma, 1, 1, 5, 9, 13)
G(v, m, sigma, 2, 2, 6, 10, 14)
G(v, m, sigma, 3, 3, 7, 11, 15)
G(v, m, sigma, 4, 0, 5, 10, 15) # diagonals
G(v, m, sigma, 5, 1, 6, 11, 12)
G(v, m, sigma, 6, 2, 7, 8, 13)
G(v, m, sigma, 7, 3, 4, 9, 14)
return [h[i] ^ v[i] ^ v[i + 8] for i in range(8)]dcrd: crypto/blake256/internal/compress/blocks_generic.go · g, blocksGeneric
With a non-zero salt , the initial would be and the output ; with the zero salt used by Decred these reduce to the expressions above.
3.2.3 Padding, counter and output¶
The message is padded with a 1 bit, then zero bits until its length is congruent to 447 modulo 512, then a 1 bit (which distinguishes BLAKE-256 from BLAKE-224, where this bit is 0), and finally the message length in bits as a 64-bit big-endian integer. For messages made of whole bytes this is the byte sequence 80 00 ... 00 01 followed by the length, where the first and last padding bytes merge into the single byte 81 when exactly one padding byte fits.
The counter passed with each block is the number of message bits contained in that block and all preceding blocks. A block that contains no message bits at all, which is the case for the only block of the empty message, for the extra padding block appended when a message’s final partial block has more than 55 bytes, and for the padding block of a message whose length is a non-zero multiple of 64, is compressed with .
Algorithm 3.2 · BLAKE-256
def blake256(msg: bytes) -> bytes:
L = len(msg)
p = bytearray(msg) + b"\x80"
while len(p) % 64 != 56:
p += b"\x00"
p[-1] |= 0x01 # 0x80 becomes 0x81 if L % 64 == 55
p += be64(8 * L)
h = IV
for j in range(len(p) // 64):
if 64 * j < L:
t = 8 * min(64 * (j + 1), L) # message bits up to the end of block j
else:
t = 0 # block holds padding only
h = blake256_compress(h, p[64 * j : 64 * j + 64], t)
return be32(h[0]) + be32(h[1]) + ... + be32(h[7])dcrd: crypto/blake256/hasher.go · write, finalize, wordsToBytes256
Implementation pitfall
Three details distinguish BLAKE-256 from the functions it resembles and are the usual causes of wrong output: the message words and the output are big-endian (BLAKE2 and BLAKE3 are little-endian); every message word is XORed with a constant before it is added, and the constant index is the other half of the pair; and a block containing only padding is compressed with counter 0, not with the total bit length. The vectors for 55-, 56- and 64-byte inputs below exercise the three padding cases.Test vector: BLAKE-256
input BLAKE-256
(empty) 716f6e863f744b9ac22c97ec7b76ea5f
5908bc5b2f67c61510bfc4751384ea7a
00 0ce8d4ef4dd7cd8d62dfded9d4edb0a7
74ae6a41929a74da23109e8f11139c87
"abc" 1833a9fa7cf4086bd5fda73da32e5a1d
75b4c3f89d5c436369f9d78bb2da5c28
"a" x 55 6e8d7898571228c1106fcec9ef9c5db9
df8a3a2dcd2655a848af596d181bbae4
"a" x 56 ea7a29472a26148914abb8033869be9b
dea294fdd2b73ed7a02a7692940f5b9e
"a" x 64 84d7f3bbf2cfc3ee940ddb6d25045c6d
3f756c4b2077a8128e171d5d165be170
00 x 72 d419bad32d504fb7d44d460c42c5593f
e544fa4c135dec31e21bd9abdcc22d41
"The quick brown fox jumps over the lazy dog" 7576698ee9cad30173080678e5965916
adbb11cb5245d386bf1ffda1cb26c9d7Quoted inputs are ASCII without a terminator; "a" x 55 is 55 bytes of 0x61. The 1-byte and 72-byte inputs are the examples from the BLAKE specification [9].
3.3 Hash Functions Derived from BLAKE-256¶
dcrd names its general-purpose hash chainhash.HashB (returning bytes) and chainhash.HashH (returning a 32-byte hash value); both are a single BLAKE-256. Transaction hashes, block hashes, Merkle tree nodes and signature hashes all use this single application. Table 3.5 lists the other compositions in use.
| Name | Definition | Used by |
|---|---|---|
| BLAKE-256 | Everything not listed below | |
| HASH256 | BLAKE-256(BLAKE-256) | OP_HASH256 (the only consensus use); the Base58Check checksum (Chapter 5) |
| HASH160 | RIPEMD-160(BLAKE-256) | OP_HASH160; public key hashes and script hashes in addresses (Chapter 5) |
| Message hash | BLAKE-256 | Signed messages (Section 3.8.4); not consensus |
Rule 3.2 · Derived hash functions
HASH160 MUST be computed as RIPEMD-160 of the 32-byte BLAKE-256 digest, giving 20 bytes. HASH256 MUST be computed as BLAKE-256 of the 32-byte BLAKE-256 digest. Where a consensus structure is said to be hashed without further qualification, a single BLAKE-256 is meant.dcrd: chaincfg/chainhash/hashfuncs.go · HashB, HashH | txscript/opcode.go · opcodeHash160, opcodeHash256 | txscript/stdaddr/addressv0.go · Hash160
Implementation pitfall
Decred has no double hashing in its block or transaction identifiers, Merkle trees or signature hashes. An implementation adapted from Bitcoin code must remove the second hash everywhere in consensus exceptOP_HASH256, and must replace SHA-256 by BLAKE-256 inside HASH160.Test vector: Derived hashes
HASH256("") d8ee5f957b78a961fb729098b4efb56440a14e05e3c55890f5edbc626380aaa6
HASH256("abc") f1a44bb867d5ac7053d5e071d62d4513d5b243420d9863e2718823a161c1344a
HASH160(02ba9cf60e2ea62eb020697b80a34eaaf17cdf7ee6114b3bdbdaac3494066a10fd)
2f4b63971d0e28df5c6fa3ace542adb5eee4b2abThe public key is the one used in the ECDSA vectors of Section 3.8.
3.4 BLAKE3¶
Since the activation of the blake3pow agenda (DCP-0011), the proof-of-work hash of a block header is BLAKE3 [10] instead of BLAKE-256. dcrd computes it with the Go library lukechampine.com/blake3 at version v1.3.0, in the default hash mode (unkeyed, no key derivation) with a 32-byte output. The input is the 180-byte serialized block header, the same bytes that are hashed with BLAKE-256 to form the block hash (Chapter 4). Which blocks use which proof-of-work hash, and how the result is compared with the target, is specified in Chapter 9.
Rule 3.3 · BLAKE3 proof-of-work hash function
The BLAKE3 hash used by Decred MUST be the BLAKE3 hash function of [10] in hash mode with the default 32-byte output, which is the first 32 bytes of the extendable output. For inputs of at most 1024 bytes, including the 180-byte block header, it is fully specified by Algorithm 3.3; longer inputs, which do not occur in consensus, use the tree mode of [10].dcrd: wire/blockheader.go · PowHashV2 | lukechampine.com/blake3 v1.3.0 · New, Sum
BLAKE3 splits its input into 1024-byte chunks, each made of up to sixteen 64-byte blocks, and combines the chunks in a binary tree. An input of at most 1024 bytes is a single chunk, which is also the root of the tree, so the hash is computed by chaining the compression function over the blocks of that chunk. The compression function shares the function and rotation amounts of BLAKE-256 but differs in everything else: 7 rounds, little-endian words, no constants mixed into the message, a fixed message permutation applied between rounds, and a state that includes the block length and a set of domain flags.
| Parameter | Value |
|---|---|
| IV | Identical to the BLAKE-256 IV of Table 3.2 |
Message permutation PERM | 2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8 (new word is old word PERM[i]) |
| Flags | CHUNK_START = 1, CHUNK_END = 2, ROOT = 8 (PARENT = 4 and the keyed and key-derivation flags are not used for single-chunk unkeyed hashing) |
| Rounds | 7 |
| Counter | The chunk index, which is 0 for a single-chunk input |
Algorithm 3.3 · BLAKE3 for inputs of at most 1024 bytes
PERM = [2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8]
CHUNK_START, CHUNK_END, ROOT = 1, 2, 8
def g3(v, a, b, c, d, x, y):
v[a] = (v[a] + v[b] + x) & M32
v[d] = rotr32(v[d] ^ v[a], 16)
v[c] = (v[c] + v[d]) & M32
v[b] = rotr32(v[b] ^ v[c], 12)
v[a] = (v[a] + v[b] + y) & M32
v[d] = rotr32(v[d] ^ v[a], 8)
v[c] = (v[c] + v[d]) & M32
v[b] = rotr32(v[b] ^ v[c], 7)
def blake3_compress(cv, m, counter: uint64, block_len, flags) -> list[uint32]:
v = cv[0:8] + IV[0:4] + [counter & M32, counter >> 32, block_len, flags]
for r in range(7):
g3(v, 0, 4, 8, 12, m[0], m[1]); g3(v, 1, 5, 9, 13, m[2], m[3])
g3(v, 2, 6, 10, 14, m[4], m[5]); g3(v, 3, 7, 11, 15, m[6], m[7])
g3(v, 0, 5, 10, 15, m[8], m[9]); g3(v, 1, 6, 11, 12, m[10], m[11])
g3(v, 2, 7, 8, 13, m[12], m[13]); g3(v, 3, 4, 9, 14, m[14], m[15])
m = [m[PERM[i]] for i in range(16)]
return [v[i] ^ v[i + 8] for i in range(8)] + [v[i + 8] ^ cv[i] for i in range(8)]
def blake3_256(msg: bytes) -> bytes: # len(msg) <= 1024
n = max(1, (len(msg) + 63) // 64) # block count; the empty input has one
cv = IV
for j in range(n):
block = msg[64 * j : 64 * j + 64]
block_len = len(block) # 64, except possibly for the last block
block = block + bytes(64 - block_len)
m = [le32_decode(block[4 * i : 4 * i + 4]) for i in range(16)]
flags = 0
if j == 0:
flags |= CHUNK_START
if j == n - 1:
flags |= CHUNK_END | ROOT
cv = blake3_compress(cv, m, 0, block_len, flags)[0:8]
return le32(cv[0]) + le32(cv[1]) + ... + le32(cv[7])dcrd: lukechampine.com/blake3 v1.3.0 · guts.CompressNode, guts.CompressChunk | blake3.go · Hasher.Sum, rootNode
For the 180-byte header the chunk has three blocks of 64, 64 and 52 bytes, compressed with flags 1, 0 and 10 respectively and block lengths 64, 64 and 52.
Test vector: BLAKE3 (32-byte output)
(empty) af1349b9f5f9a1a6a0404dea36dcc9499bcb25c9adc112b7cc9a93cae41f3262
"abc" 6437b3ac38465133ffb63b75273a8db548c558465d79db03fd359c6cd5bd9d85
00 x 180 3419118e1c6537b8de8a2e6a22dcc2734c0d92729ce542484de3e829e6e67f12Test vector: Main-network genesis block header
serialized header (180 bytes):
0100000000000000000000000000000000000000000000000000000000000000
000000000dc101dfc3c6a2eb10ca0c5374e10d28feb53f7eabcc850511ceadb9
9174aa6600000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000ffff011b00c2eb0b00000000
0000000000000000a0d7b8560000000000000000000000000000000000000000
0000000000000000000000000000000000000000
BLAKE-256 80d9212bf4ceb066ded2866b39d4ed89e0ab60f335c11df8e7bf85d9c35c8e29
BLAKE3 1baa4b79809fc85fac9333371d37e203f34c345595f5ed5ed435fbc10b09d3d7Both hashes are shown with their bytes in order. The BLAKE-256 value is the genesis block hash, displayed in reversed byte order as in Section 2.4. The BLAKE3 value is only an example of the function: the genesis block predates DCP-0011 and is never checked against it.
3.5 SHA-256, SHA-1 and RIPEMD-160¶
These three functions are used exactly as standardized and are specified by reference. SHA-256 and SHA-1 are defined in FIPS 180-4 [11]; RIPEMD-160 is defined by its authors [12]. dcrd uses Go’s standard library for SHA-256 and SHA-1 and a copy of the golang.org/x/crypto RIPEMD-160 code (crypto/ripemd160).
In consensus they appear only as script opcodes: OP_RIPEMD160, OP_SHA1, OP_SHA256 (which is interpreted as SHA-256 only when the corresponding script flag is in effect), and inside OP_HASH160. Their stack semantics and activation are given in Chapter 6. SHA-256 also appears, outside consensus, as the hash of the HMAC used for deterministic nonces (Algorithm 3.6), and SHA-512 inside Ed25519 (Section 3.10).
Test vector: SHA-256, SHA-1 and RIPEMD-160
SHA-256("") e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA-256("abc") ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
SHA-1("") da39a3ee5e6b4b0d3255bfef95601890afd80709
SHA-1("abc") a9993e364706816aba3e25717850c26c9cd0d89d
RIPEMD-160("") 9c1185a5c5e9fc54612808977ee8f548b2258d31
RIPEMD-160("abc")
8eb208f7e05d987a9b044a8e98c6b087f15a0bfc3.6 The secp256k1 Curve¶
ECDSA and EC-Schnorr-DCRv0 both operate on secp256k1 [13], the Koblitz curve over the prime field . Its group of points has prime order and cofactor 1, so every point other than generates the whole group. Table 3.7 lists the domain parameters.
| Parameter | Value |
|---|---|
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f | |
| , | , |
79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 | |
483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 | |
fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 | |
7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 | |
14551231950b75fc4402da1722fc9baee | |
| Cofactor | 1 |
A scalar is an integer modulo . A private key is a scalar with , and its public key is the point .
3.6.1 Public key encodings¶
Public keys are serialized in the formats of SEC 1 [14] and ANSI X9.62, with coordinates as 32-byte big-endian integers. The first byte identifies the format (Table 3.8). dcrd always produces the compressed format, or the uncompressed format on request, and never produces the hybrid format.
| Format | Prefix | Length | Parse (Rule 3.4) | Strict (Rule 3.5) | Schnorr (Rule 3.10) |
|---|---|---|---|---|---|
| Compressed | 02 ( even), 03 ( odd) | 33 | yes | yes | yes |
| Uncompressed | 04 | 65 | yes | yes | no |
| Hybrid | 06 ( even), 07 ( odd) | 65 | yes | no | no |
| Anything else | no | no | no |
Rule 3.4 · Parsing a secp256k1 public key
A byte string parses as a secp256k1 public key if and only if one of the following holds; otherwise parsing fails.
- , , and with and : , , if then is even, if then is odd, and . The key is .
- , , , and is a quadratic residue modulo . The key is where is the square root of modulo that is even if and odd if .
Every other length, and every other prefix byte for the given length, fails. A successfully parsed key is never , since has no encoding.
dcrd: dcrec/secp256k1/pubkey.go · PublicKey.parse, ParsePubKey
Because , the square root of a residue is ; is a residue exactly when the square of that value equals it.
The script engine applies a stricter syntactic test to ECDSA public keys before parsing them. It is part of the consensus rules wherever the script chapter applies it (Chapter 6); it rejects the hybrid format even though the parser accepts it.
Rule 3.5 · Strict public key encoding
A public key byte string is strictly encoded if and only if it is 33 bytes long with first byte02 or 03, or 65 bytes long with first byte 04. Strict encoding is purely syntactic: it does not check that the coordinates are in range or that the point is on the curve.dcrd: txscript/engine.go · isStrictPubKeyEncoding | txscript/consensus.go · CheckPubKeyEncoding
Since ECDSA public keys in scripts must pass Rule 3.5 before they are parsed, and EC-Schnorr-DCRv0 keys must be compressed (Rule 3.10), a hybrid key can never validate a signature in consensus even though Rule 3.4 accepts it. A key that is strictly encoded but fails Rule 3.4 (for example, one not on the curve) makes the signature check fail rather than aborting the script (Chapter 6).
Test vector: Public key parsing
key parse strict
02ba9c...10fd (compressed) ok ok
04ba9c...1674 (uncompressed) ok ok
06ba9c...1674 (hybrid, y even) ok rejected
07ba9c...1674 (hybrid, y even) fails: parity mismatch rejected
05ba9c...1674 fails: unsupported format rejected
04ba9c...1675 (y + 1) fails: not on curve ok
02 || BE256(p) fails: x >= p ok
02 || BE256(5) fails: x not on curve ok
first 32 bytes of 02ba9c... fails: length rejectedThe full keys are those of the ECDSA vector in Section 3.8.5.
3.6.2 Scalars from byte strings¶
Several algorithms below convert a byte string to a scalar. dcrd does this by taking the first bytes of , left-padding them with zero bytes to 32 bytes, and interpreting the result as a big-endian integer . It reports overflow if and otherwise yields . Where an algorithm below reduces (written scalar_reduce(b) in pseudocode), the value used is ; where it rejects on overflow, is a failure. The same conversion into a field element reports overflow when .
3.7 Signature Schemes in Consensus¶
Scripts verify signatures with two families of opcodes, whose full semantics are given in Chapter 6. This chapter owns the mathematics and the encodings; Table 3.9 shows how they connect.
| Opcode family | Type | Scheme | Public key | Signature (excluding the hash type byte) |
|---|---|---|---|---|
OP_CHECKSIG, OP_CHECKMULTISIG | ECDSA / secp256k1 | 33 or 65 bytes, strict | DER, 8 to 72 bytes | |
OP_CHECKSIGALT | 0 | none | Always yields false | |
OP_CHECKSIGALT | 1 | Ed25519 | 32 bytes | 64 bytes |
OP_CHECKSIGALT | 2 | EC-Schnorr-DCRv0 / secp256k1 | 33 bytes, compressed | 64 bytes |
OP_CHECKSIGALT | other | none | Always yields true (reserved for future soft forks) |
The signature type numbers are the constants STEcdsaSecp256k1 = 0, STEd25519 = 1 and STSchnorrSecp256k1 = 2 defined in dcrec/common.go. ECDSA is never selected through OP_CHECKSIGALT: type 0 makes it yield false. Types 1 and 2 are executed by the consensus engine, so both alternative schemes are reachable in consensus. In all cases the message that is signed is the 32-byte signature hash of the spending transaction defined in Chapter 6, and every signature carries one trailing hash type byte that is removed before the signature is parsed. Outside scripts, EC-Schnorr-DCRv0 also authorizes treasury spends (Chapter 12); that 64-byte signature carries no hash type byte.
3.8 ECDSA¶
ECDSA over secp256k1 is the primary signature scheme. Verification is standard ECDSA [14]; Decred’s specifics lie in the signature encoding and in deterministic signing.
3.8.1 Verification¶
Rule 3.6 · ECDSA verification
An ECDSA signature is valid for a 32-byte message hash and a public key if and only if Algorithm 3.4 returns true. In consensus, comes from Rule 3.7, from Rule 3.4, and is the signature hash.dcrd: dcrec/secp256k1/ecdsa/signature.go · Signature.Verify
Algorithm 3.4 · ECDSA verification
def ecdsa_verify(r: int, s: int, z: bytes, Q: Point) -> bool:
if r == 0 or s == 0: # cannot happen after DER parsing
return False
e = scalar_reduce(z) # first 32 bytes, big-endian, mod n
w = pow(s, n - 2, n) # s^-1 mod n
u1 = e * w % n
u2 = r * w % n
X = point_add(scalar_mult(u1, G), scalar_mult(u2, Q))
if X == INFINITY:
return False
return X.x % n == rdcrd: dcrec/secp256k1/ecdsa/signature.go · Signature.Verify
Note
dcrd avoids converting to affine coordinates: with in Jacobian coordinates it accepts if or, when , if modulo . Since , this is exactly the condition .Implementation pitfall
is zero when , making , and may be . Point addition must handle the identity and the doubling case; a formula that assumes distinct, non-identity operands produces wrong verdicts on such inputs.3.8.2 DER signature encoding¶
ECDSA signatures in scripts are encoded with the ASN.1 Distinguished Encoding Rules (DER, ITU-T X.690 [15]) as a sequence of two integers (Table 3.10). All lengths are single bytes, since no valid signature needs a long-form length.
| Field | Type | Bytes | Description |
|---|---|---|---|
| seq | byte | 1 | 0x30, the ASN.1 SEQUENCE identifier. |
| len | byte | 1 | Number of remaining bytes; must equal the signature length minus 2. |
| rtype | byte | 1 | 0x02, the ASN.1 INTEGER identifier. |
| rlen | byte | 1 | Length of in bytes. |
| R | bytes | as a minimal big-endian two’s complement integer. | |
| stype | byte | 1 | 0x02. |
| slen | byte | 1 | Length of in bytes. |
| S | bytes | as a minimal big-endian two’s complement integer. |
“Minimal two’s complement” means that the first byte of an integer must not have its high bit set (that would make it negative), and a leading 0x00 byte is allowed only when the following byte has its high bit set. The shortest valid signature is therefore 8 bytes () and the longest 72 bytes ().
Rule 3.7 · Parsing a DER signature
Let be the signature with its hash type byte removed and . parses as an ECDSA signature if and only if all of the following hold, where offsets are zero-based, , (the offset of the S type byte), and :
- .
- .
- .
- and (the S type and length bytes are inside ).
- (the lengths account for every byte; there is no trailing data).
- .
- .
- has its high bit clear ( is not negative).
- Not ( and and has its high bit clear) ( has no excess leading zero).
- .
- .
- has its high bit clear ( is not negative).
- Not ( and and has its high bit clear) ( has no excess leading zero).
- With all leading zero bytes stripped from the field, at most 32 bytes remain, and their big-endian value satisfies .
- With all leading zero bytes stripped from the field, at most 32 bytes remain, and their big-endian value satisfies .
The result is the pair . The parser does not require ; high- signatures parse and verify.
dcrd: dcrec/secp256k1/ecdsa/signature.go · ParseDERSignature
The script engine additionally applies a strict encoding check to every ECDSA signature before parsing it (Chapter 6). It repeats items 1 to 13 of Rule 3.7 and adds the low- requirement, but it does not check the range of : a signature that is strictly encoded but has or , or , passes the strict check and then fails to parse. The two outcomes differ in script: a strict-encoding failure aborts the script with an error, whereas a parse failure makes the signature check return false.
Rule 3.8 · Strict ECDSA signature encoding
A signature (without hash type) is strictly encoded if and only if it satisfies items 1 to 13 of Rule 3.7 and, with all leading zero bytes stripped from the field, at most 32 bytes remain and their value satisfies and . In particular a strictly encoded signature has .dcrd: txscript/consensus.go · CheckSignatureEncoding
Rationale
If is a valid signature then so is . Without the low- rule anyone could change the value of a signature in a transaction, and thereby the transaction’s full hash, without invalidating it. Requiring leaves one valid choice.3.8.3 Signing¶
Signing is not part of consensus, but dcrd’s signatures are deterministic and implementations that wish to reproduce them, or the test vectors, must follow Algorithm 3.5. The nonce is generated per RFC 6979 [16] with HMAC-SHA256 (Algorithm 3.6), and is normalized to the lower half of the range as required by Rule 3.8.
Algorithm 3.5 · Deterministic ECDSA signing
def ecdsa_sign(d: int, z: bytes) -> tuple[int, int, int]:
for iteration in range(0, 2**32):
k = nonce_rfc6979(be256(d), z, b"", iteration)
X = scalar_mult(k, G)
r = X.x % n
if r == 0:
continue
e = scalar_reduce(z)
s = pow(k, n - 2, n) * (e + d * r) % n
if s == 0:
continue
recid = (2 if X.x >= n else 0) | (X.y & 1) # public key recovery code
if s > (n - 1) // 2:
s = n - s
recid ^= 1 # -k gives the opposite y parity
return r, s, reciddcrd: dcrec/secp256k1/ecdsa/signature.go · signRFC6979, sign
A signature is serialized in DER (Table 3.10) by encoding and as 32-byte big-endian values, prefixing a zero byte, and stripping leading zero bytes while more than one byte remains and the next byte has its high bit clear.
Algorithm 3.6 · RFC 6979 nonce generation as implemented
def nonce_rfc6979(key: bytes, z: bytes, extra: bytes, iteration: uint32) -> int:
key = left_pad(key[0:32], 32) # truncate to 32 bytes or left-pad with zeros
z = left_pad(z[0:32], 32)
data = key + z
if len(extra) == 32: # extra data is used only if exactly 32 bytes
data = data + extra
V = b"\x01" * 32
K = b"\x00" * 32
K = hmac_sha256(K, V + b"\x00" + data)
V = hmac_sha256(K, V)
K = hmac_sha256(K, V + b"\x01" + data)
V = hmac_sha256(K, V)
generated = 0
while True:
V = hmac_sha256(K, V)
k = int_be(V)
if 1 <= k <= n - 1:
generated += 1
if generated > iteration:
return k
K = hmac_sha256(K, V + b"\x00")
V = hmac_sha256(K, V)dcrd: dcrec/secp256k1/nonce.go · NonceRFC6979
The function also accepts an optional 16-byte “version” string that is appended after the extra data (with 32 zero bytes standing in for absent extra data); no signature scheme in this chapter uses it.
Implementation pitfall
RFC 6979 feeds into the HMAC. dcrd feeds itself, unreduced. The two differ only when , which happens with probability about for a hash output, but an implementation that reduces produces different nonces, and therefore different signatures, for such messages.3.8.4 Compact recoverable signatures and signed messages¶
A compact signature is a 65-byte encoding of an ECDSA signature from which the signer’s public key can be recovered. It is used for signed messages (the signmessage interface of wallets and the verifymessage interface of wallets and dcrd; Chapter 5 gives the message format) and is not part of consensus.
| Field | Type | Bytes | Description |
|---|---|---|---|
| code | byte | 1 | , where is the recovery code of Algorithm 3.5 and if the signer’s address uses the compressed public key, else 0. Valid values are 27 to 34. |
| r | bytes | 32 | . |
| s | bytes | 32 | , with as produced by signing. |
Bit 0 of the recovery code is the parity of for the nonce point (after the low- adjustment), and bit 1 is set when , so that . Recovery from a compact signature and a 32-byte hash proceeds as follows, failing at any step that cannot be completed:
- Require the length to be 65 and the first byte to satisfy . Let ; the original key was compressed if bit 2 of is set, and .
- Parse and from the next two 32-byte fields; require and (rejecting on overflow).
- Let . If bit 1 of is set, require and let .
- Find with whose parity equals bit 0 of ; fail if none exists. Let .
- Let be reduced as in Section 3.6.2, , , , and . Fail if .
- The recovered key is , to be serialized compressed if is set and uncompressed otherwise.
A signed message (a UTF-8 string) is verified by computing the message hash
(3.1)
where is the variable-length string encoding of Chapter 4 (a variable-length integer byte count followed by the bytes), recovering from the compact signature and , and comparing the version 0 pay-to-public-key-hash address of HASH160 of ’s serialization with the claimed address (Chapter 5). Unlike Bitcoin, the message hash is a single BLAKE-256, not double SHA-256.
3.8.5 Test vectors¶
Test vector: ECDSA key, nonce and signature
d cbe35df915b1e955c4956bba366d95256a7ee187c9d5267a8f0c69afae669c0e
(= BLAKE-256("Decred crypto chapter test key"))
z 5a029fb117f154fc26caa93ca613772e2795e5776e2fd4208abbf6386be52dc7
(= BLAKE-256("Decred crypto chapter test message"))
Q compressed 02ba9cf60e2ea62eb020697b80a34eaaf17cdf7ee6114b3bdbdaac3494066a10fd
Q uncompr. 04ba9cf60e2ea62eb020697b80a34eaaf17cdf7ee6114b3bdbdaac3494066a10fd
5b94e113908bde6f4dc99d83494af73fdf7db95194617ff0418056a978481674
k (iter. 0) 83d68d3a073a926fdd7f485df64f27e829bc7c07334b795f5d36b161f5139ab1
X.x c766d1c56552499bca21cc0f329b3ca2ecd96b501a60e5797576f33331c6ea4e
X.y parity even
s (raw) a8184510d564a0d715fdff73d704cb78356d3631ed1579eba2ddef42acd1722a
r c766d1c56552499bca21cc0f329b3ca2ecd96b501a60e5797576f33331c6ea4e
s 57e7baef2a9b5f28ea02008c28fb34868541a6b4c23326501cf46f4a2364cf17
DER 3045022100c766d1c56552499bca21cc0f329b3ca2ecd96b501a60e5797576f33331c6ea4e
022057e7baef2a9b5f28ea02008c28fb34868541a6b4c23326501cf46f4a2364cf17
compact (compressed key, recid 1: code 27 + 1 + 4 = 0x20)
20c766d1c56552499bca21cc0f329b3ca2ecd96b501a60e5797576f33331c6ea4e
57e7baef2a9b5f28ea02008c28fb34868541a6b4c23326501cf46f4a2364cf17Here the raw exceeded and was negated, which flipped the recovery code’s parity bit from 0 to 1.
Test vector: Signed message
message "hello"; key d as above
z = BLAKE-256(17 "Decred Signed Message:\n" 05 "hello")
= 776fea952d41c5269b91e9710afcd91103ad41a06e814f8ecba72f49044fdfe6
compact signature
208900fad91d879b2643d8b2046f033ca389247e3a9fe499d6d7908cb72d14712f
07e9ce1734285c6f9a79ef3617ce8453f38d9a104c93cd14b4d7c7070dc236afTest vector: DER parsing and strict encoding
The base signature is the DER signature above, with R = 00c766...ea4e and S = 57e7...cf17.
| Modification | Parse (Rule 3.7) | Strict (Rule 3.8) |
|---|---|---|
| None | ok | ok |
replaced by (022100a818...722a, 72 bytes) | ok | high S |
Extra 00 before (02220000c766...) | excess padding (9) | excess padding |
First byte of field 80 instead of 00 | negative R (8) | negative R |
= 00 (020100) | R is 0 (14) | ok |
= 00 | R >= n (14) | ok |
= 00 (020100) | S is 0 (15) | ok |
length 0 (0200) | zero S length (11) | zero S length |
First byte 31 | sequence id (2) | sequence id |
Length byte 46 instead of 45 | bad length (3) | bad length |
| One trailing byte appended | bad length (3) | bad length |
R type byte 03 | R integer id (6) | R integer id |
3006020101020101 () | ok | ok |
30060201010201 (7 bytes) | too short (1) | too short |
Numbers in parentheses are the items of Rule 3.7 that fail.
3.9 EC-Schnorr-DCRv0¶
EC-Schnorr-DCRv0 is a Schnorr signature scheme [17] over secp256k1 defined by Decred. A signature is the pair where is the coordinate of the nonce point , whose coordinate is required to be even, and with challenge . Verification checks . It is not compatible with BIP 340 [18] Schnorr signatures, which use a different challenge hash, the opposite sign convention and -only public keys. The scheme is described in the README of the schnorr package, which this section follows; where the README and the code differ in detail, the code is authoritative.
3.9.1 Encoding¶
| Field | Type | Bytes | Description |
|---|---|---|---|
| r | bytes | 32 | , the coordinate of , with . |
| s | bytes | 32 | , with . |
Rule 3.9 · Parsing an EC-Schnorr-DCRv0 signature
A byte string parses as an EC-Schnorr-DCRv0 signature if and only if , and . No other condition is checked: , , and an that is not the coordinate of any curve point all parse (and then fail or succeed in verification on their merits).dcrd: dcrec/secp256k1/schnorr/signature.go · ParseSignature
Rule 3.10 · Parsing an EC-Schnorr-DCRv0 public key
A byte string parses as an EC-Schnorr-DCRv0 public key if and only if it is exactly 33 bytes long, its first byte is02 or 03, and it parses as a compressed key under Rule 3.4. Uncompressed and hybrid keys are rejected.dcrd: dcrec/secp256k1/schnorr/pubkey.go · ParsePubKey
3.9.2 Verification¶
Rule 3.11 · EC-Schnorr-DCRv0 verification
A parsed signature is valid for a message and a parsed public key if and only if Algorithm 3.7 returns true.dcrd: dcrec/secp256k1/schnorr/signature.go · schnorrVerify, Signature.Verify
Algorithm 3.7 · EC-Schnorr-DCRv0 verification
def schnorr_verify(r: int, s: int, m: bytes, Q: Point) -> bool:
if len(m) != 32:
return False
if not on_curve(Q): # always true for a parsed key
return False
e = int_be(blake256(be256(r) + m)) # r is always encoded as 32 bytes
if e >= n: # no reduction: overflow is a failure
return False
R = point_add(scalar_mult(s, G), scalar_mult(e, Q))
if R == INFINITY:
return False
if R.y % 2 == 1:
return False
return R.x == rdcrd: dcrec/secp256k1/schnorr/signature.go · schnorrVerify
Implementation pitfall
The challenge is not reduced modulo : a hash value makes the signature invalid. The comparison is over the field, not modulo . Because and are both possible inputs, point arithmetic must handle correctly.3.9.3 Signing¶
Signing is deterministic. The nonce comes from Algorithm 3.6 with 32 bytes of extra data that separate it from ECDSA nonces for the same key and message:
Algorithm 3.8 · EC-Schnorr-DCRv0 signing
def schnorr_sign(d: int, m: bytes) -> tuple[int, int]:
if len(m) != 32 or d == 0:
fail()
for iteration in range(0, 2**32):
k = nonce_rfc6979(be256(d), m, EXTRA_DCRV0, iteration)
R = scalar_mult(k, G)
if R.y % 2 == 1:
k = n - k # -k gives a nonce point with even y
r = R.x
e = int_be(blake256(be256(r) + m))
if e >= n:
continue
s = (k - e * d) % n
return r, sdcrd: dcrec/secp256k1/schnorr/signature.go · Sign, schnorrSign
Test vector: EC-Schnorr-DCRv0
d, z, Q as in the ECDSA vector (Q compressed = 02ba9c...10fd)
k (iter. 0) 18de4f626d03fb5ce2b99e35c1a647001de4a09b17b10575f7f14069885fa651
R.y parity even (k not negated)
r fc941c3662ebb36c6ac57a1399e5d1c914ebba55e5632e450f5069d9c6023954
e f574323b5a096cf37a2fc5c63dc0ab696204ae903083a9e89835a6918dc67ba1
s 908e6a2805b90ade93188d193394e10d3c1e178522a316237618b3d4d40fa229
signature fc941c3662ebb36c6ac57a1399e5d1c914ebba55e5632e450f5069d9c6023954
908e6a2805b90ade93188d193394e10d3c1e178522a316237618b3d4d40fa229Parsing edge cases: 64 zero bytes parse () but cannot verify; replacing by fails to parse (); replacing by fails to parse (); the 65-byte uncompressed form of is rejected as a public key.
3.10 Ed25519¶
Ed25519 [19] is EdDSA over the twisted Edwards curve edwards25519, as standardized in RFC 8032 [20]. dcrd’s implementation, the dcrec/edwards package (module github.com/decred/dcrd/dcrec/edwards/v2 at version v2.0.4, which dcrd’s go.mod takes as a published module rather than from its own source tree; the two copies differ only in their tests), wraps the Go library github.com/agl/ed25519 (pinned at version v0.0.0-20170116200512-5312a6153412), adding its own decoding and range checks. Signatures produced by dcrd from a 32-byte secret are exactly RFC 8032 Ed25519 signatures, and honestly generated RFC 8032 signatures on a 32-byte message verify. The differences lie in the treatment of unusual encodings and of , and are specified below.
| Parameter | Value |
|---|---|
| Field prime | |
| Curve | |
= 52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3 | |
| Group order | = 1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed |
| Cofactor | 8 |
| Base point | = 6666666666666666666666666666666666666666666666666666666666666658, even = 216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a; encoded 5866666666666666666666666666666666666666666666666666666666666666 |
3.10.1 Point encoding and decoding¶
A point is encoded as 32 bytes: with the most significant bit of the last byte set to the least significant bit of (the “sign” of ). The encoding produced by the implementation always has (it is canonical).
Decoding, as performed by the library and relied upon by every rule below, is more permissive than RFC 8032:
Algorithm 3.9 · Ed25519 point decoding as implemented
def ed_decode(b: bytes) -> Point: # len(b) == 32
sign = b[31] >> 7
y = (int_le(b) & (2**255 - 1)) % q # y >= q is NOT rejected; it is reduced
u = (y * y - 1) % q
v = (d * y * y + 1) % q
x = sqrt_mod_q(u * inverse(v, q)) # fail if u/v is not a square mod q
if (x & 1) != sign:
x = (q - x) % q # x = 0 stays 0 even if sign == 1
return (x, y)dcrd: dcrec/edwards/primitives.go · encodedBytesToBigIntPoint | github.com/agl/ed25519/edwards25519 · ExtendedGroupElement.FromBytes
A square root of modulo , when it exists, is or that value times .
3.10.2 Parsing and verification¶
Rule 3.12 · Parsing an Ed25519 public key
A byte string parses as an Ed25519 public key if and only if , Algorithm 3.9 succeeds on giving , and it is not the case that and the sign bit (bit 7 of ) is 1. (dcrd represents that case internally with and rejects it because .) A non-canonical encoding (bits 0 to 254 encoding a value ) is accepted and reduced.dcrd: dcrec/edwards/pubkey.go · ParsePubKey
Rule 3.13 · Parsing an Ed25519 signature
A byte string parses as an Ed25519 signature if and only if , Algorithm 3.9 succeeds on , and satisfies . The signature retains the 32 bytes exactly as given.dcrd: dcrec/edwards/signature.go · parseSig, ParseSignature
Rule 3.14 · Ed25519 verification
A parsed signature is valid for a message and a parsed public key if and only if
(3.2)
dcrd: dcrec/edwards/ecdsa.go · Verify | github.com/agl/ed25519 · Verify
The equation is the cofactorless one: it is not multiplied by 8. Since the left side is canonical, a non-canonical never verifies. No condition is placed on the order of or : small-order and mixed-order points are accepted if the equation holds.
| Aspect | RFC 8032 | dcrd |
|---|---|---|
| Public key with | Decoding fails | reduced modulo ; accepted if the reduced value decodes, and the canonical re-encoding is hashed |
| Public key with , sign bit 1 | Decoding fails | Rejected |
| with | Decoding fails | Parses if the reduced value decodes; never verifies |
| with , sign bit 1 | Decoding fails | Parses, never verifies |
| Allowed | Rejected | |
| Rejected | Rejected | |
| Verification equation | (the unmultiplied form is permitted) | re-encoded and compared with (cofactorless) |
| Message | Arbitrary | The 32-byte signature hash (pure Ed25519, no context or prehash) |
Signing from a 32-byte secret follows RFC 8032 exactly: , the scalar is with bits 0, 1, 2 and 255 cleared and bit 254 set, , , , and with as in Rule 3.14. (The package also has a mode for keys given as a bare scalar, which signs with an RFC 6979 nonce; dcrd’s transaction signing code in txscript/sign does not use it. Its signatures are verified by the same rules.)
Test vector: Ed25519
seed 232b277c698f23760d3bb922ffd92c47f80db87382f567de705c1c96108a6818
(= BLAKE-256("Decred crypto chapter ed25519 seed"))
A 4fb3bab83ba936b65d6e5aeefe6433aae325b78121f18401aaadda5090a7465e
m 5a029fb117f154fc26caa93ca613772e2795e5776e2fd4208abbf6386be52dc7
sig 86e6c6ce81e30f209948be1bba9e1313ca78355b428206af9341dea5cc57a8c9
ee1c6b29a2c9a472591759f35ea53e1700c6d773722bcb79a0493d273c541d0bParsing edge cases: the public key 01 followed by 31 zero bytes (the identity) parses; the same with the last byte 80 is rejected; the non-canonical encoding eeff...ff7f of parses and re-encodes as 01 followed by 31 zero bytes; 02 followed by 31 zero bytes () is not on the curve. As , the identity with the sign bit set and the non-canonical encoding of both parse (and cannot verify); a signature with or is rejected.
3.11 Merkle Trees¶
A Merkle tree [21] commits to an ordered list of 32-byte leaves with a single 32-byte root. Each interior node is the BLAKE-256 hash of the concatenation of its two children. When a level has an odd number of nodes, its last node is paired with itself. The block header commits to the transactions of a block with Merkle roots whose leaves are transaction hashes; which hashes are used, and how the regular and stake tree roots are combined under DCP-0005, is specified in Chapter 4 and Chapter 10. This section defines the generic tree.
Rule 3.15 · Merkle root
The Merkle root of a list of leaves MUST be computed by Algorithm 3.10. In particular, the root of the empty list is 32 zero bytes, the root of a single leaf is that leaf itself (it is not hashed), and at each level with an odd number of nodes greater than one the last node is duplicated before pairing.dcrd: blockchain/standalone/merkle.go · CalcMerkleRoot, CalcMerkleRootInPlace
Algorithm 3.10 · Merkle root
def merkle_root(leaves: list[bytes]) -> bytes:
if len(leaves) == 0:
return bytes(32)
level = list(leaves)
while len(level) > 1:
if len(level) % 2 == 1:
level.append(level[-1])
level = [blake256(level[2 * i] + level[2 * i + 1])
for i in range(len(level) // 2)]
return level[0]dcrd: blockchain/standalone/merkle.go · CalcMerkleRootInPlace
Implementation pitfall
Because the last node of an odd level is duplicated, the lists and have the same root, and in general appending copies of trailing leaves can preserve the root. A Merkle root therefore does not by itself determine the number of leaves. The rule that makes this harmless for blocks (no duplicate transactions) is part of Chapter 10.Test vector: Merkle roots
Leaves for the single byte :
L0 0ce8d4ef4dd7cd8d62dfded9d4edb0a774ae6a41929a74da23109e8f11139c87
L1 4a6c419a1e25c85327115c4ace586decddfe2990ed8f3d4d801871158338501d
L2 49af37ab5270015fe25276ea5a3bb159d852943df23919522a202205fb7d175c
L3 b706d561742ad3671703c247eb927ee8a386369c79644131cdeb2c5c26bf6c5d
L4 4c6eb9e38415034f4c93d3304d10bef38bf0ad420eefd0f72f940f11c5857786
root([]) 0000000000000000000000000000000000000000000000000000000000000000
root([L0]) 0ce8d4ef4dd7cd8d62dfded9d4edb0a774ae6a41929a74da23109e8f11139c87
root([L0..L1]) ad204769bc6f9a916299fe1af8d54828b7403e2dbe65c8888e16e9fa1deae0c5
root([L0..L2]) 0135cd60725091a8795118c7ed50b8bf8a272707938a9fa7b24f0399bbe4a048
root([L0..L3]) f71e10d28e0d14e884e043114c2e30cfbed5ef375faf4fd9790b122a0e574e0b
root([L0..L4]) 1a3f528d95b03c38767aaf2daab6ee3a97c3040adfffbb67ecb357d418b34517root([L0..L2]) , and it equals the root of [L0, L1, L2, L2].
3.11.1 Inclusion proofs¶
An inclusion proof for the leaf at zero-based index is the list of sibling hashes on the path from that leaf to the root, ordered from the leaf level upward. Together with the leaf and its index it suffices to recompute the root. dcrd generates such proofs for the header commitments of DCP-0005, which it serves to light clients (Chapter 16); they are not used in block validation. The proof for a tree of leaves has entries, and none for a single leaf.
Algorithm 3.11 · Inclusion proof generation
def inclusion_proof(leaves: list[bytes], index: uint32) -> list[bytes] | None:
if len(leaves) == 0 or index >= len(leaves):
return None
level = list(leaves)
proof = []
while len(level) > 1:
if len(level) % 2 == 1:
level.append(level[-1])
sibling = index ^ 1 # left if index is odd, else right
proof.append(level[sibling])
level = [blake256(level[2 * j] + level[2 * j + 1])
for j in range(len(level) // 2)]
index = index >> 1
return proofdcrd: blockchain/standalone/inclusionproof.go · GenerateInclusionProof
Algorithm 3.12 · Inclusion proof verification
def verify_inclusion(root: bytes, leaf: bytes, index: uint32,
proof: list[bytes]) -> bool:
if len(proof) > 32:
return False
if index > 2**len(proof) - 1: # largest index this proof length covers
return False
h = leaf
for sibling in proof:
if index & 1 == 1:
h = blake256(sibling + h)
else:
h = blake256(h + sibling)
index = index >> 1
return h == rootdcrd: blockchain/standalone/inclusionproof.go · VerifyInclusionProof
Verification does not learn the number of leaves. A proof for the last leaf of an odd level contains a copy of that leaf as its own sibling.
Test vector: Inclusion proofs for the five leaves above
index 2:
[0] b706d561742ad3671703c247eb927ee8a386369c79644131cdeb2c5c26bf6c5d
[1] ad204769bc6f9a916299fe1af8d54828b7403e2dbe65c8888e16e9fa1deae0c5
[2] 92ad3df5fcd26cbbd6ea00363893dd6f201516f3760bdfa9f9359945369beacd
index 4:
[0] 4c6eb9e38415034f4c93d3304d10bef38bf0ad420eefd0f72f940f11c5857786
[1] 72b0e5fb43e19eb8b640aec409532c2cd8a583cfb5ada680f8664a6b53c36558
[2] f71e10d28e0d14e884e043114c2e30cfbed5ef375faf4fd9790b122a0e574e0bFor index 2 the entries are , and the hash of the duplicated right subtree ; for index 4 they are itself (its own duplicate), (the duplicate of its parent), and the root of . Both verify against root([L0..L4]). The index 4 proof presented with index 8 is rejected, since 8 exceeds .
3.12 Other Primitives¶
No other cryptographic primitive is evaluated in block validation outside the chapters that own it:
- The pseudorandom number generator that selects winning tickets is built on BLAKE-256 and is specified in Chapter 8.
- SipHash and Golomb-coded sets, used by the version 2 compact filters committed to by header commitments, are specified in Chapter 16.
- Base58Check (whose checksum is the first four bytes of HASH256 of the payload) and hierarchical deterministic keys are specified in Chapter 5; neither is consensus-critical.
- The signature hash that each signature commits to is specified in Chapter 6.