Skip to content

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.

Table 3.1. Cryptographic primitives and their uses
PrimitiveSectionUsed for
BLAKE-256 (14 rounds)Section 3.2Transaction and block hashes, Merkle trees, signature hashes, the version 1 proof-of-work hash, OP_BLAKE256, OP_HASH160, OP_HASH256, the Schnorr challenge
BLAKE3Section 3.4The version 2 proof-of-work hash (DCP-0011)
RIPEMD-160Section 3.5OP_RIPEMD160, OP_HASH160, address hashes
SHA-256Section 3.5OP_SHA256; HMAC inside deterministic nonce generation (not consensus)
SHA-1Section 3.5OP_SHA1
secp256k1Section 3.6Public keys for ECDSA and EC-Schnorr-DCRv0
ECDSASection 3.8OP_CHECKSIG, OP_CHECKMULTISIG and their VERIFY forms
EC-Schnorr-DCRv0Section 3.9OP_CHECKSIGALT with signature type 2; treasury spend authorization
Ed25519Section 3.10OP_CHECKSIGALT with signature type 1
Merkle treeSection 3.11Transaction 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 232, 𝑎⊕𝑏 (^ in pseudocode) is bitwise exclusive or, and rotr(𝑎,𝑛) is rotation to the right by 𝑛 bits. In pseudocode the mask M32 = 0xffffffff makes the reduction modulo 232 explicit.

For an integer 𝑥 with 0≤𝑥<2256, BE256(𝑥) is its 32-byte big-endian encoding and LE256(𝑥) its 32-byte little-endian encoding. For a byte string 𝑏, intBE(𝑏) and intLE(𝑏) 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 BE256(𝑥); int_be(b) and int_le(b) are intBE and intLE; 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 𝑐0,…,𝑐15 (Table 3.3) are the first 512 bits of the fractional part of 𝜋. Each round uses one of ten permutations 𝜎0,…,𝜎9 of the message word indices (Table 3.4); round 𝑟 (counting from 0) uses 𝜎𝑟mod10, so rounds 10 to 13 repeat 𝜎0 to 𝜎3.

Table 3.2. BLAKE-256 initial chaining value IV (also the BLAKE3 IV)
IV0IV1IV2IV3IV4IV5IV6IV7
6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19
Table 3.3. BLAKE-256 constants 𝑐𝑖
𝑐0𝑐1𝑐2𝑐3𝑐4𝑐5𝑐6𝑐7
243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c89
𝑐8𝑐9𝑐10𝑐11𝑐12𝑐13𝑐14𝑐15
452821e638d01377be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5b5470917
Table 3.4. BLAKE message permutations 𝜎𝑗: entry 𝑖 of row 𝑗 is 𝜎𝑗(𝑖)
0123456789101112131415
𝜎00123456789101112131415
𝜎11410489151361120211753
𝜎21181205215131014367194
𝜎37931131211142651040158
𝜎49057241015141111268313
𝜎52126100118341375151419
𝜎61251151413410076392811
𝜎71311714121395015486210
𝜎86151491130812213714105
𝜎91028476151511914312130

3.2.2 Compression function

The compression function maps a chaining value ℎ0,…,ℎ7, a 64-byte block and the counter 𝑡 to a new chaining value. The block is read as sixteen big-endian words 𝑚0,…,𝑚15. A 16-word state 𝑣0,…,𝑣15, viewed as a 4×4 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 𝜎=𝜎𝑟mod10, the message word 𝑚𝜎(2𝑖) is combined with the constant 𝑐𝜎(2𝑖+1), and 𝑚𝜎(2𝑖+1) with 𝑐𝜎(2𝑖). 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 𝑠0,…,𝑠3, the initial 𝑣8,…,𝑣11 would be 𝑠𝑖⊕𝑐𝑖 and the output ℎ𝑖⊕𝑠𝑖mod4⊕𝑣𝑖⊕𝑣𝑖+8; 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 𝑡=0.

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
                                              adbb11cb5245d386bf1ffda1cb26c9d7

Quoted 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.

Table 3.5. Hash functions derived from BLAKE-256
NameDefinitionUsed 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 hashBLAKE-256(varstr(Decred Signed Message:\n)‖varstr(𝑚))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 except OP_HASH256, and must replace SHA-256 by BLAKE-256 inside HASH160.
Test vector: Derived hashes
HASH256("")    d8ee5f957b78a961fb729098b4efb56440a14e05e3c55890f5edbc626380aaa6
HASH256("abc") f1a44bb867d5ac7053d5e071d62d4513d5b243420d9863e2718823a161c1344a
HASH160(02ba9cf60e2ea62eb020697b80a34eaaf17cdf7ee6114b3bdbdaac3494066a10fd)
                 2f4b63971d0e28df5c6fa3ace542adb5eee4b2ab

The 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.

Table 3.6. BLAKE3 parameters used for single-chunk inputs
ParameterValue
IVIdentical to the BLAKE-256 IV of Table 3.2
Message permutation PERM2, 6, 3, 10, 7, 0, 4, 13, 1, 11, 12, 5, 9, 14, 15, 8 (new word 𝑖 is old word PERM[i])
FlagsCHUNK_START = 1, CHUNK_END = 2, ROOT = 8 (PARENT = 4 and the keyed and key-derivation flags are not used for single-chunk unkeyed hashing)
Rounds7
CounterThe 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   3419118e1c6537b8de8a2e6a22dcc2734c0d92729ce542484de3e829e6e67f12
Test vector: Main-network genesis block header
serialized header (180 bytes):
  0100000000000000000000000000000000000000000000000000000000000000
  000000000dc101dfc3c6a2eb10ca0c5374e10d28feb53f7eabcc850511ceadb9
  9174aa6600000000000000000000000000000000000000000000000000000000
  0000000000000000000000000000000000000000ffff011b00c2eb0b00000000
  0000000000000000a0d7b8560000000000000000000000000000000000000000
  0000000000000000000000000000000000000000
BLAKE-256  80d9212bf4ceb066ded2866b39d4ed89e0ab60f335c11df8e7bf85d9c35c8e29
BLAKE3     1baa4b79809fc85fac9333371d37e203f34c345595f5ed5ed435fbc10b09d3d7

Both 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")
                8eb208f7e05d987a9b044a8e98c6b087f15a0bfc

3.6 The secp256k1 Curve

ECDSA and EC-Schnorr-DCRv0 both operate on secp256k1 [13], the Koblitz curve 𝑦2=𝑥3+7 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.

Table 3.7. secp256k1 domain parameters (hexadecimal, big-endian)
ParameterValue
𝑝fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f =2256−232−977
𝑎, 𝑏𝑎=0, 𝑏=7
𝐺.𝑥79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
𝐺.𝑦483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
𝑛fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
𝑛−127fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
𝑝−𝑛14551231950b75fc4402da1722fc9baee
Cofactor ℎ1

A scalar is an integer modulo 𝑛. A private key is a scalar 𝑑 with 1≤𝑑≤𝑛−1, 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.

Table 3.8. secp256k1 public key formats and where each is accepted
FormatPrefixLengthParse (Rule 3.4)Strict (Rule 3.5)Schnorr (Rule 3.10)
Compressed02 (𝑦 even), 03 (𝑦 odd)33yesyesyes
Uncompressed0465yesyesno
Hybrid06 (𝑦 even), 07 (𝑦 odd)65yesnono
Anything elsenonono

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.

  1. |𝑏|=65, 𝑏0∈{04,06,07}, and with 𝑥=intBE(𝑏[1:33]) and 𝑦=intBE(𝑏[33:65]): 𝑥<𝑝, 𝑦<𝑝, if 𝑏0=06 then 𝑦 is even, if 𝑏0=07 then 𝑦 is odd, and 𝑦2≡𝑥3+7(mod𝑝). The key is (𝑥,𝑦).
  2. |𝑏|=33, 𝑏0∈{02,03}, 𝑥=intBE(𝑏[1:33])<𝑝, and 𝑥3+7 is a quadratic residue modulo 𝑝. The key is (𝑥,𝑦) where 𝑦 is the square root of 𝑥3+7 modulo 𝑝 that is even if 𝑏0=02 and odd if 𝑏0=03.

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 𝑝≡3(mod4), the square root of a residue 𝑎 is 𝑎𝑝+14mod𝑝; 𝑥3+7 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 byte 02 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              rejected

The 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 min(|𝑏|,32) 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 𝑧mod𝑛; 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.

Table 3.9. Signature schemes reachable from scripts
Opcode familyTypeSchemePublic keySignature (excluding the hash type byte)
OP_CHECKSIG, OP_CHECKMULTISIGECDSA / secp256k133 or 65 bytes, strictDER, 8 to 72 bytes
OP_CHECKSIGALT0noneAlways yields false
OP_CHECKSIGALT1Ed2551932 bytes64 bytes
OP_CHECKSIGALT2EC-Schnorr-DCRv0 / secp256k133 bytes, compressed64 bytes
OP_CHECKSIGALTothernoneAlways 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 == r

dcrd: dcrec/secp256k1/ecdsa/signature.go · Signature.Verify

Note

dcrd avoids converting 𝑋 to affine coordinates: with 𝑋 in Jacobian coordinates (𝑋𝐽,𝑌𝐽,𝑍𝐽) it accepts if 𝑟𝑍𝐽2≡𝑋𝐽 or, when 𝑟+𝑛<𝑝, if (𝑟+𝑛)𝑍𝐽2≡𝑋𝐽 modulo 𝑝. Since 𝑋.𝑥<𝑝<2𝑛, this is exactly the condition 𝑋.𝑥mod𝑛=𝑟.

Implementation pitfall

𝑢1 is zero when 𝑒≡0, making 𝑢1𝐺=𝒪︀, and 𝑢1𝐺+𝑢2𝑄 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.

Table 3.10. DER encoding of an ECDSA signature
FieldTypeBytesDescription
seqbyte10x30, the ASN.1 SEQUENCE identifier.
lenbyte1Number of remaining bytes; must equal the signature length minus 2.
rtypebyte10x02, the ASN.1 INTEGER identifier.
rlenbyte1Length ℓ𝑟 of 𝑅 in bytes.
Rbytesℓ𝑟𝑟 as a minimal big-endian two’s complement integer.
stypebyte10x02.
slenbyte1Length ℓ𝑠 of 𝑆 in bytes.
Sbytesℓ𝑠𝑠 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 (ℓ𝑟=ℓ𝑠=1) and the longest 72 bytes (ℓ𝑟=ℓ𝑠=33).

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, ℓ𝑟=𝑏3, 𝑜𝑠=4+ℓ𝑟 (the offset of the S type byte), and ℓ𝑠=𝑏𝑜𝑠+1:

  1. 8≤𝐿≤72.
  2. 𝑏0=0x30.
  3. 𝑏1=𝐿−2.
  4. 𝑜𝑠<𝐿 and 𝑜𝑠+1<𝐿 (the S type and length bytes are inside 𝑏).
  5. 𝑜𝑠+2+ℓ𝑠=𝐿 (the lengths account for every byte; there is no trailing data).
  6. 𝑏2=0x02.
  7. ℓ𝑟≠0.
  8. 𝑏4 has its high bit clear (𝑅 is not negative).
  9. Not (ℓ𝑟>1 and 𝑏4=0x00 and 𝑏5 has its high bit clear) (𝑅 has no excess leading zero).
  10. 𝑏𝑜𝑠=0x02.
  11. ℓ𝑠≠0.
  12. 𝑏𝑜𝑠+2 has its high bit clear (𝑆 is not negative).
  13. Not (ℓ𝑠>1 and 𝑏𝑜𝑠+2=0x00 and 𝑏𝑜𝑠+3 has its high bit clear) (𝑆 has no excess leading zero).
  14. With all leading zero bytes stripped from the 𝑅 field, at most 32 bytes remain, and their big-endian value 𝑟 satisfies 1≤𝑟≤𝑛−1.
  15. With all leading zero bytes stripped from the 𝑆 field, at most 32 bytes remain, and their big-endian value 𝑠 satisfies 1≤𝑠≤𝑛−1.

The result is the pair (𝑟,𝑠). The parser does not require 𝑠≤(𝑛−1)/2; 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 𝑟=0 or 𝑟≥𝑛, or 𝑠=0, 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 𝑠≤(𝑛−1)/2. In particular a strictly encoded signature has 𝑠≤7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0.

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 𝑠≤(𝑛−1)/2 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, recid

dcrd: 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 bits2octets(𝑧)=intBE(𝑧)mod𝑛 into the HMAC. dcrd feeds 𝑧 itself, unreduced. The two differ only when intBE(𝑧)≥𝑛, which happens with probability about 2−128 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.

Table 3.11. Compact signature
FieldTypeBytesDescription
codebyte127+recid+4𝑐, where recid is the recovery code of Algorithm 3.5 and 𝑐=1 if the signer’s address uses the compressed public key, else 0. Valid values are 27 to 34.
rbytes32BE256(𝑟).
sbytes32BE256(𝑠), with 𝑠≤(𝑛−1)/2 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:

  1. Require the length to be 65 and the first byte 𝑐 to satisfy 27≤𝑐≤34. Let 𝑐′=𝑐−27; the original key was compressed if bit 2 of 𝑐′ is set, and recid=𝑐′mod4.
  2. Parse 𝑟 and 𝑠 from the next two 32-byte fields; require 1≤𝑟≤𝑛−1 and 1≤𝑠≤𝑛−1 (rejecting on overflow).
  3. Let 𝑥=𝑟. If bit 1 of recid is set, require 𝑟+𝑛<𝑝 and let 𝑥=𝑟+𝑛.
  4. Find 𝑦 with 𝑦2≡𝑥3+7(mod𝑝) whose parity equals bit 0 of recid; fail if none exists. Let 𝑋=(𝑥,𝑦).
  5. Let 𝑒 be 𝑧 reduced as in Section 3.6.2, 𝑤=𝑟−1mod𝑛, 𝑢1=−𝑒𝑤mod𝑛, 𝑢2=𝑠𝑤mod𝑛, and 𝑄=𝑢1𝐺+𝑢2𝑋. Fail if 𝑄=𝒪︀.
  6. The recovered key is 𝑄, to be serialized compressed if compressed is set and uncompressed otherwise.

A signed message 𝑚 (a UTF-8 string) is verified by computing the message hash

𝑧=BLAKE-256(varstr("Decred Signed Message:\n")‖varstr(𝑚)),

(3.1)

where varstr 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
       57e7baef2a9b5f28ea02008c28fb34868541a6b4c23326501cf46f4a2364cf17

Here the raw 𝑠 exceeded (𝑛−1)/2 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
    07e9ce1734285c6f9a79ef3617ce8453f38d9a104c93cd14b4d7c7070dc236af
Test vector: DER parsing and strict encoding

The base signature is the DER signature above, with R = 00c766...ea4e and S = 57e7...cf17.

ModificationParse (Rule 3.7)Strict (Rule 3.8)
Noneokok
𝑆 replaced by 𝑛−𝑠 (022100a818...722a, 72 bytes)okhigh S
Extra 00 before 𝑅 (02220000c766...)excess padding (9)excess padding
First byte of 𝑅 field 80 instead of 00negative R (8)negative R
𝑅 = 00 (020100)R is 0 (14)ok
𝑅 = 00 ‖ BE256(𝑛)R >= n (14)ok
𝑆 = 00 (020100)S is 0 (15)ok
𝑆 length 0 (0200)zero S length (11)zero S length
First byte 31sequence id (2)sequence id
Length byte 46 instead of 45bad length (3)bad length
One trailing byte appendedbad length (3)bad length
R type byte 03R integer id (6)R integer id
3006020101020101 (𝑟=𝑠=1)okok
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 𝑠=𝑘−𝑒𝑑mod𝑛 with challenge 𝑒=BLAKE-256(BE256(𝑟)‖𝑚). 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

Table 3.12. EC-Schnorr-DCRv0 signature
FieldTypeBytesDescription
rbytes32BE256(𝑟), the 𝑥 coordinate of 𝑅, with 𝑟<𝑝.
sbytes32BE256(𝑠), with 𝑠<𝑛.

Rule 3.9 · Parsing an EC-Schnorr-DCRv0 signature

A byte string 𝑏 parses as an EC-Schnorr-DCRv0 signature if and only if |𝑏|=64, 𝑟=intBE(𝑏[0:32])<𝑝 and 𝑠=intBE(𝑏[32:64])<𝑛. No other condition is checked: 𝑟=0, 𝑠=0, 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 is 02 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 == r

dcrd: 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 𝑠=0 and 𝑒=0 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, s

dcrd: 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
             908e6a2805b90ade93188d193394e10d3c1e178522a316237618b3d4d40fa229

Parsing edge cases: 64 zero bytes parse (𝑟=𝑠=0) but cannot verify; replacing 𝑠 by BE256(𝑛) fails to parse (𝑠≥𝑛); replacing 𝑟 by BE256(𝑝) 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 𝑆=0, and are specified below.

Table 3.13. edwards25519 parameters
ParameterValue
Field prime 𝑞2255−19
Curve−𝑥2+𝑦2=1+𝑑𝑥2𝑦2
𝑑−121665/121666mod𝑞 = 52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3
Group order ℓ2252+27742317777372353535851937790883648493 = 1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed
Cofactor8
Base point 𝐵𝐵.𝑦=4/5mod𝑞 = 6666666666666666666666666666666666666666666666666666666666666658, 𝐵.𝑥 even = 216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a; encoded 5866666666666666666666666666666666666666666666666666666666666666

3.10.1 Point encoding and decoding

A point (𝑥,𝑦) is encoded as 32 bytes: LE256(𝑦) 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 𝑎(𝑞+3)/8 or that value times −1=2(𝑞−1)/4mod𝑞.

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 |𝑏|=32, Algorithm 3.9 succeeds on 𝑏 giving 𝐴=(𝑥,𝑦), and it is not the case that 𝑥=0 and the sign bit (bit 7 of 𝑏[31]) 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 |𝑏|=64, Algorithm 3.9 succeeds on 𝑅enc=𝑏[0:32], and 𝑆=intLE(𝑏[32:64]) satisfies 0<𝑆<ℓ. The signature retains the 32 bytes 𝑅enc exactly as given.

dcrd: dcrec/edwards/signature.go · parseSig, ParseSignature

Rule 3.14 · Ed25519 verification

A parsed signature (𝑅enc,𝑆) is valid for a message 𝑚 and a parsed public key 𝐴 if and only if

encode(𝑆𝐵−𝑘𝐴)=𝑅enc,𝑘=intLE(SHA-512(𝑅enc‖𝐴enc‖𝑚))modℓ,

(3.2)

where 𝐴enc is the canonical encoding of 𝐴 (Section 3.10.1), not necessarily the bytes from which 𝐴 was parsed, encode is the canonical encoding, and the comparison is of all 32 bytes. In consensus 𝑚 is the 32-byte signature hash.

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 𝑅enc never verifies. No condition is placed on the order of 𝐴 or 𝑅: small-order and mixed-order points are accepted if the equation holds.

Table 3.14. Ed25519 as implemented compared with RFC 8032
AspectRFC 8032dcrd
Public key with 𝑦≥𝑞Decoding fails𝑦 reduced modulo 𝑞; accepted if the reduced value decodes, and the canonical re-encoding is hashed
Public key with 𝑥=0, sign bit 1Decoding failsRejected
𝑅 with 𝑦≥𝑞Decoding failsParses if the reduced value decodes; never verifies
𝑅 with 𝑥=0, sign bit 1Decoding failsParses, never verifies
𝑆=0AllowedRejected
𝑆≥ℓRejectedRejected
Verification equation[8]𝑆𝐵=[8]𝑅+[8]𝑘𝐴 (the unmultiplied form is permitted)𝑆𝐵−𝑘𝐴 re-encoded and compared with 𝑅enc (cofactorless)
MessageArbitraryThe 32-byte signature hash (pure Ed25519, no context or prehash)

Signing from a 32-byte secret 𝑠seed follows RFC 8032 exactly: ℎ=SHA-512(𝑠seed), the scalar 𝑎 is intLE(ℎ[0:32]) with bits 0, 1, 2 and 255 cleared and bit 254 set, 𝐴=𝑎𝐵, 𝑟=intLE(SHA-512(ℎ[32:64]‖𝑚))modℓ, 𝑅=𝑟𝐵, and 𝑆=(𝑟+𝑘𝑎)modℓ 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
      ee1c6b29a2c9a472591759f35ea53e1700c6d773722bcb79a0493d273c541d0b

Parsing 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 𝑦=𝑞+1 parses and re-encodes as 01 followed by 31 zero bytes; 02 followed by 31 zero bytes (𝑦=2) is not on the curve. As 𝑅enc, the identity with the sign bit set and the non-canonical encoding of 𝑦=𝑞+1 both parse (and cannot verify); a signature with 𝑆=0 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 [𝐿0,𝐿1,𝐿2] and [𝐿0,𝐿1,𝐿2,𝐿2] 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 𝐿𝑖=BLAKE-256(𝑖) 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]) 1a3f528d95b03c38767aaf2daab6ee3a97c3040adfffbb67ecb357d418b34517

root([L0..L2]) =𝐻(𝐻(𝐿0‖𝐿1)‖𝐻(𝐿2‖𝐿2)), 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 𝑁≥1 leaves has ⌈log2𝑁⌉ 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 proof

dcrd: 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 == root

dcrd: 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] f71e10d28e0d14e884e043114c2e30cfbed5ef375faf4fd9790b122a0e574e0b

For index 2 the entries are 𝐿3, 𝐻(𝐿0‖𝐿1) and the hash of the duplicated right subtree 𝐻(𝐻(𝐿4‖𝐿4)‖𝐻(𝐿4‖𝐿4)); for index 4 they are 𝐿4 itself (its own duplicate), 𝐻(𝐿4‖𝐿4) (the duplicate of its parent), and the root of 𝐿0,…,𝐿3. Both verify against root([L0..L4]). The index 4 proof presented with index 8 is rejected, since 8 exceeds 23−1.

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.