diff --git a/src/hash.cpp b/src/hash.cpp index 35c7e8161..53264c65a 100644 --- a/src/hash.cpp +++ b/src/hash.cpp @@ -1,218 +1,259 @@ // Copyright (c) 2013-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "hash.h" #include "crypto/common.h" #include "crypto/hmac_sha512.h" #include "pubkey.h" inline uint32_t ROTL32(uint32_t x, int8_t r) { return (x << r) | (x >> (32 - r)); } unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector &vDataToHash) { // The following is MurmurHash3 (x86_32), see // http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp uint32_t h1 = nHashSeed; if (vDataToHash.size() > 0) { const uint32_t c1 = 0xcc9e2d51; const uint32_t c2 = 0x1b873593; const int nblocks = vDataToHash.size() / 4; //---------- // body const uint8_t *blocks = &vDataToHash[0] + nblocks * 4; for (int i = -nblocks; i; i++) { uint32_t k1 = ReadLE32(blocks + i * 4); k1 *= c1; k1 = ROTL32(k1, 15); k1 *= c2; h1 ^= k1; h1 = ROTL32(h1, 13); h1 = h1 * 5 + 0xe6546b64; } //---------- // tail const uint8_t *tail = (const uint8_t *)(&vDataToHash[0] + nblocks * 4); uint32_t k1 = 0; switch (vDataToHash.size() & 3) { case 3: k1 ^= tail[2] << 16; // FALLTHROUGH case 2: k1 ^= tail[1] << 8; // FALLTHROUGH case 1: k1 ^= tail[0]; k1 *= c1; k1 = ROTL32(k1, 15); k1 *= c2; h1 ^= k1; } } //---------- // finalization h1 ^= vDataToHash.size(); h1 ^= h1 >> 16; h1 *= 0x85ebca6b; h1 ^= h1 >> 13; h1 *= 0xc2b2ae35; h1 ^= h1 >> 16; return h1; } void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, uint8_t header, const uint8_t data[32], uint8_t output[64]) { uint8_t num[4]; num[0] = (nChild >> 24) & 0xFF; num[1] = (nChild >> 16) & 0xFF; num[2] = (nChild >> 8) & 0xFF; num[3] = (nChild >> 0) & 0xFF; CHMAC_SHA512(chainCode.begin(), chainCode.size()) .Write(&header, 1) .Write(data, 32) .Write(num, 4) .Finalize(output); } #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b)))) #define SIPROUND \ do { \ v0 += v1; \ v1 = ROTL(v1, 13); \ v1 ^= v0; \ v0 = ROTL(v0, 32); \ v2 += v3; \ v3 = ROTL(v3, 16); \ v3 ^= v2; \ v0 += v3; \ v3 = ROTL(v3, 21); \ v3 ^= v0; \ v2 += v1; \ v1 = ROTL(v1, 17); \ v1 ^= v2; \ v2 = ROTL(v2, 32); \ } while (0) CSipHasher::CSipHasher(uint64_t k0, uint64_t k1) { v[0] = 0x736f6d6570736575ULL ^ k0; v[1] = 0x646f72616e646f6dULL ^ k1; v[2] = 0x6c7967656e657261ULL ^ k0; v[3] = 0x7465646279746573ULL ^ k1; count = 0; tmp = 0; } CSipHasher &CSipHasher::Write(uint64_t data) { uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3]; assert(count % 8 == 0); v3 ^= data; SIPROUND; SIPROUND; v0 ^= data; v[0] = v0; v[1] = v1; v[2] = v2; v[3] = v3; count += 8; return *this; } CSipHasher &CSipHasher::Write(const uint8_t *data, size_t size) { uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3]; uint64_t t = tmp; int c = count; while (size--) { - t |= ((uint64_t)(*(data++))) << (8 * (c % 8)); + t |= uint64_t(*(data++)) << (8 * (c % 8)); c++; if ((c & 7) == 0) { v3 ^= t; SIPROUND; SIPROUND; v0 ^= t; t = 0; } } v[0] = v0; v[1] = v1; v[2] = v2; v[3] = v3; count = c; tmp = t; return *this; } uint64_t CSipHasher::Finalize() const { uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3]; - uint64_t t = tmp | (((uint64_t)count) << 56); + uint64_t t = tmp | (uint64_t(count) << 56); v3 ^= t; SIPROUND; SIPROUND; v0 ^= t; v2 ^= 0xFF; SIPROUND; SIPROUND; SIPROUND; SIPROUND; return v0 ^ v1 ^ v2 ^ v3; } uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256 &val) { /* Specialized implementation for efficiency */ uint64_t d = val.GetUint64(0); uint64_t v0 = 0x736f6d6570736575ULL ^ k0; uint64_t v1 = 0x646f72616e646f6dULL ^ k1; uint64_t v2 = 0x6c7967656e657261ULL ^ k0; uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d; SIPROUND; SIPROUND; v0 ^= d; d = val.GetUint64(1); v3 ^= d; SIPROUND; SIPROUND; v0 ^= d; d = val.GetUint64(2); v3 ^= d; SIPROUND; SIPROUND; v0 ^= d; d = val.GetUint64(3); v3 ^= d; SIPROUND; SIPROUND; v0 ^= d; - v3 ^= ((uint64_t)4) << 59; + v3 ^= uint64_t(4) << 59; SIPROUND; SIPROUND; - v0 ^= ((uint64_t)4) << 59; + v0 ^= uint64_t(4) << 59; + v2 ^= 0xFF; + SIPROUND; + SIPROUND; + SIPROUND; + SIPROUND; + return v0 ^ v1 ^ v2 ^ v3; +} + +uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256 &val, + uint32_t extra) { + /* Specialized implementation for efficiency */ + uint64_t d = val.GetUint64(0); + + uint64_t v0 = 0x736f6d6570736575ULL ^ k0; + uint64_t v1 = 0x646f72616e646f6dULL ^ k1; + uint64_t v2 = 0x6c7967656e657261ULL ^ k0; + uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d; + + SIPROUND; + SIPROUND; + v0 ^= d; + d = val.GetUint64(1); + v3 ^= d; + SIPROUND; + SIPROUND; + v0 ^= d; + d = val.GetUint64(2); + v3 ^= d; + SIPROUND; + SIPROUND; + v0 ^= d; + d = val.GetUint64(3); + v3 ^= d; + SIPROUND; + SIPROUND; + v0 ^= d; + d = (uint64_t(36) << 56) | extra; + v3 ^= d; + SIPROUND; + SIPROUND; + v0 ^= d; v2 ^= 0xFF; SIPROUND; SIPROUND; SIPROUND; SIPROUND; return v0 ^ v1 ^ v2 ^ v3; } diff --git a/src/hash.h b/src/hash.h index dbbe97ac3..9a29ada21 100644 --- a/src/hash.h +++ b/src/hash.h @@ -1,219 +1,221 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_HASH_H #define BITCOIN_HASH_H #include "crypto/ripemd160.h" #include "crypto/sha256.h" #include "prevector.h" #include "serialize.h" #include "uint256.h" #include "version.h" #include typedef uint256 ChainCode; /** A hasher class for Bitcoin's 256-bit hash (double SHA-256). */ class CHash256 { private: CSHA256 sha; public: static const size_t OUTPUT_SIZE = CSHA256::OUTPUT_SIZE; void Finalize(uint8_t hash[OUTPUT_SIZE]) { uint8_t buf[CSHA256::OUTPUT_SIZE]; sha.Finalize(buf); sha.Reset().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash); } CHash256 &Write(const uint8_t *data, size_t len) { sha.Write(data, len); return *this; } CHash256 &Reset() { sha.Reset(); return *this; } }; /** A hasher class for Bitcoin's 160-bit hash (SHA-256 + RIPEMD-160). */ class CHash160 { private: CSHA256 sha; public: static const size_t OUTPUT_SIZE = CRIPEMD160::OUTPUT_SIZE; void Finalize(uint8_t hash[OUTPUT_SIZE]) { uint8_t buf[CSHA256::OUTPUT_SIZE]; sha.Finalize(buf); CRIPEMD160().Write(buf, CSHA256::OUTPUT_SIZE).Finalize(hash); } CHash160 &Write(const uint8_t *data, size_t len) { sha.Write(data, len); return *this; } CHash160 &Reset() { sha.Reset(); return *this; } }; /** Compute the 256-bit hash of an object. */ template inline uint256 Hash(const T1 pbegin, const T1 pend) { static const uint8_t pblank[1] = {}; uint256 result; CHash256() .Write(pbegin == pend ? pblank : (const uint8_t *)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 256-bit hash of the concatenation of two objects. */ template inline uint256 Hash(const T1 p1begin, const T1 p1end, const T2 p2begin, const T2 p2end) { static const uint8_t pblank[1] = {}; uint256 result; CHash256() .Write(p1begin == p1end ? pblank : (const uint8_t *)&p1begin[0], (p1end - p1begin) * sizeof(p1begin[0])) .Write(p2begin == p2end ? pblank : (const uint8_t *)&p2begin[0], (p2end - p2begin) * sizeof(p2begin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 256-bit hash of the concatenation of three objects. */ template inline uint256 Hash(const T1 p1begin, const T1 p1end, const T2 p2begin, const T2 p2end, const T3 p3begin, const T3 p3end) { static const uint8_t pblank[1] = {}; uint256 result; CHash256() .Write(p1begin == p1end ? pblank : (const uint8_t *)&p1begin[0], (p1end - p1begin) * sizeof(p1begin[0])) .Write(p2begin == p2end ? pblank : (const uint8_t *)&p2begin[0], (p2end - p2begin) * sizeof(p2begin[0])) .Write(p3begin == p3end ? pblank : (const uint8_t *)&p3begin[0], (p3end - p3begin) * sizeof(p3begin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 160-bit hash an object. */ template inline uint160 Hash160(const T1 pbegin, const T1 pend) { static uint8_t pblank[1] = {}; uint160 result; CHash160() .Write(pbegin == pend ? pblank : (const uint8_t *)&pbegin[0], (pend - pbegin) * sizeof(pbegin[0])) .Finalize((uint8_t *)&result); return result; } /** Compute the 160-bit hash of a vector. */ inline uint160 Hash160(const std::vector &vch) { return Hash160(vch.begin(), vch.end()); } /** Compute the 160-bit hash of a vector. */ template inline uint160 Hash160(const prevector &vch) { return Hash160(vch.begin(), vch.end()); } /** A writer stream (for serialization) that computes a 256-bit hash. */ class CHashWriter { private: CHash256 ctx; const int nType; const int nVersion; public: CHashWriter(int nTypeIn, int nVersionIn) : nType(nTypeIn), nVersion(nVersionIn) {} int GetType() const { return nType; } int GetVersion() const { return nVersion; } void write(const char *pch, size_t size) { ctx.Write((const uint8_t *)pch, size); } // invalidates the object uint256 GetHash() { uint256 result; ctx.Finalize((uint8_t *)&result); return result; } template CHashWriter &operator<<(const T &obj) { // Serialize to this stream ::Serialize(*this, obj); return (*this); } }; /** Compute the 256-bit hash of an object's serialization. */ template uint256 SerializeHash(const T &obj, int nType = SER_GETHASH, int nVersion = PROTOCOL_VERSION) { CHashWriter ss(nType, nVersion); ss << obj; return ss.GetHash(); } unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector &vDataToHash); void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, uint8_t header, const uint8_t data[32], uint8_t output[64]); /** SipHash-2-4 */ class CSipHasher { private: uint64_t v[4]; uint64_t tmp; int count; public: /** Construct a SipHash calculator initialized with 128-bit key (k0, k1) */ CSipHasher(uint64_t k0, uint64_t k1); /** * Hash a 64-bit integer worth of data. * It is treated as if this was the little-endian interpretation of 8 bytes. * This function can only be used when a multiple of 8 bytes have been * written so far. */ CSipHasher &Write(uint64_t data); /** Hash arbitrary bytes. */ CSipHasher &Write(const uint8_t *data, size_t size); /** Compute the 64-bit SipHash-2-4 of the data written so far. The object * remains untouched. */ uint64_t Finalize() const; }; /** Optimized SipHash-2-4 implementation for uint256. * * It is identical to: * SipHasher(k0, k1) * .Write(val.GetUint64(0)) * .Write(val.GetUint64(1)) * .Write(val.GetUint64(2)) * .Write(val.GetUint64(3)) * .Finalize() */ uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256 &val); +uint64_t SipHashUint256Extra(uint64_t k0, uint64_t k1, const uint256 &val, + uint32_t extra); #endif // BITCOIN_HASH_H diff --git a/src/test/hash_tests.cpp b/src/test/hash_tests.cpp index ba48885fe..0cbd52eef 100644 --- a/src/test/hash_tests.cpp +++ b/src/test/hash_tests.cpp @@ -1,142 +1,159 @@ // Copyright (c) 2013-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "hash.h" #include "test/test_bitcoin.h" #include "utilstrencodings.h" #include #include BOOST_FIXTURE_TEST_SUITE(hash_tests, BasicTestingSetup) BOOST_AUTO_TEST_CASE(murmurhash3) { #define T(expected, seed, data) \ BOOST_CHECK_EQUAL(MurmurHash3(seed, ParseHex(data)), expected) // Test MurmurHash3 with various inputs. Of course this is retested in the // bloom filter tests - they would fail if MurmurHash3() had any problems - // but is useful for those trying to implement Bitcoin libraries as a // source of test data for their MurmurHash3() primitive during // development. // // The magic number 0xFBA4C795 comes from CBloomFilter::Hash() T(0x00000000, 0x00000000, ""); T(0x6a396f08, 0xFBA4C795, ""); T(0x81f16f39, 0xffffffff, ""); T(0x514e28b7, 0x00000000, "00"); T(0xea3f0b17, 0xFBA4C795, "00"); T(0xfd6cf10d, 0x00000000, "ff"); T(0x16c6b7ab, 0x00000000, "0011"); T(0x8eb51c3d, 0x00000000, "001122"); T(0xb4471bf8, 0x00000000, "00112233"); T(0xe2301fa8, 0x00000000, "0011223344"); T(0xfc2e4a15, 0x00000000, "001122334455"); T(0xb074502c, 0x00000000, "00112233445566"); T(0x8034d2a0, 0x00000000, "0011223344556677"); T(0xb4698def, 0x00000000, "001122334455667788"); #undef T } /* SipHash-2-4 output with k = 00 01 02 ... and in = (empty string) in = 00 (1 byte) in = 00 01 (2 bytes) in = 00 01 02 (3 bytes) ... in = 00 01 02 ... 3e (63 bytes) from: https://131002.net/siphash/siphash24.c */ uint64_t siphash_4_2_testvec[] = { 0x726fdb47dd0e0e31, 0x74f839c593dc67fd, 0x0d6c8009d9a94f5a, 0x85676696d7fb7e2d, 0xcf2794e0277187b7, 0x18765564cd99a68d, 0xcbc9466e58fee3ce, 0xab0200f58b01d137, 0x93f5f5799a932462, 0x9e0082df0ba9e4b0, 0x7a5dbbc594ddb9f3, 0xf4b32f46226bada7, 0x751e8fbc860ee5fb, 0x14ea5627c0843d90, 0xf723ca908e7af2ee, 0xa129ca6149be45e5, 0x3f2acc7f57c29bdb, 0x699ae9f52cbe4794, 0x4bc1b3f0968dd39c, 0xbb6dc91da77961bd, 0xbed65cf21aa2ee98, 0xd0f2cbb02e3b67c7, 0x93536795e3a33e88, 0xa80c038ccd5ccec8, 0xb8ad50c6f649af94, 0xbce192de8a85b8ea, 0x17d835b85bbb15f3, 0x2f2e6163076bcfad, 0xde4daaaca71dc9a5, 0xa6a2506687956571, 0xad87a3535c49ef28, 0x32d892fad841c342, 0x7127512f72f27cce, 0xa7f32346f95978e3, 0x12e0b01abb051238, 0x15e034d40fa197ae, 0x314dffbe0815a3b4, 0x027990f029623981, 0xcadcd4e59ef40c4d, 0x9abfd8766a33735c, 0x0e3ea96b5304a7d0, 0xad0c42d6fc585992, 0x187306c89bc215a9, 0xd4a60abcf3792b95, 0xf935451de4f21df2, 0xa9538f0419755787, 0xdb9acddff56ca510, 0xd06c98cd5c0975eb, 0xe612a3cb9ecba951, 0xc766e62cfcadaf96, 0xee64435a9752fe72, 0xa192d576b245165a, 0x0a8787bf8ecb74b2, 0x81b3e73d20b49b6f, 0x7fa8220ba3b2ecea, 0x245731c13ca42499, 0xb78dbfaf3a8d83bd, 0xea1ad565322a1a0b, 0x60e61c23a3795013, 0x6606d7e446282b93, 0x6ca4ecb15c5f91e1, 0x9f626da15c9625f3, 0xe51b38608ef25f57, 0x958a324ceb064572}; BOOST_AUTO_TEST_CASE(siphash) { CSipHasher hasher(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x726fdb47dd0e0e31ull); static const uint8_t t0[1] = {0}; hasher.Write(t0, 1); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x74f839c593dc67fdull); static const uint8_t t1[7] = {1, 2, 3, 4, 5, 6, 7}; hasher.Write(t1, 7); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x93f5f5799a932462ull); hasher.Write(0x0F0E0D0C0B0A0908ULL); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x3f2acc7f57c29bdbull); static const uint8_t t2[2] = {16, 17}; hasher.Write(t2, 2); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x4bc1b3f0968dd39cull); static const uint8_t t3[9] = {18, 19, 20, 21, 22, 23, 24, 25, 26}; hasher.Write(t3, 9); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x2f2e6163076bcfadull); static const uint8_t t4[5] = {27, 28, 29, 30, 31}; hasher.Write(t4, 5); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x7127512f72f27cceull); hasher.Write(0x2726252423222120ULL); BOOST_CHECK_EQUAL(hasher.Finalize(), 0x0e3ea96b5304a7d0ull); hasher.Write(0x2F2E2D2C2B2A2928ULL); BOOST_CHECK_EQUAL(hasher.Finalize(), 0xe612a3cb9ecba951ull); BOOST_CHECK_EQUAL( SipHashUint256(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL, uint256S("1f1e1d1c1b1a191817161514131211100f0e0d0c0b0a09" "080706050403020100")), 0x7127512f72f27cceull); // Check test vectors from spec, one byte at a time CSipHasher hasher2(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL); for (uint8_t x = 0; x < ARRAYLEN(siphash_4_2_testvec); ++x) { BOOST_CHECK_EQUAL(hasher2.Finalize(), siphash_4_2_testvec[x]); hasher2.Write(&x, 1); } // Check test vectors from spec, eight bytes at a time CSipHasher hasher3(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL); for (uint8_t x = 0; x < ARRAYLEN(siphash_4_2_testvec); x += 8) { BOOST_CHECK_EQUAL(hasher3.Finalize(), siphash_4_2_testvec[x]); hasher3.Write(uint64_t(x) | (uint64_t(x + 1) << 8) | (uint64_t(x + 2) << 16) | (uint64_t(x + 3) << 24) | (uint64_t(x + 4) << 32) | (uint64_t(x + 5) << 40) | (uint64_t(x + 6) << 48) | (uint64_t(x + 7) << 56)); } CHashWriter ss(SER_DISK, CLIENT_VERSION); CMutableTransaction tx; // Note these tests were originally written with tx.nVersion=1 // and the test would be affected by default tx version bumps if not fixed. tx.nVersion = 1; ss << tx; BOOST_CHECK_EQUAL(SipHashUint256(1, 2, ss.GetHash()), 0x79751e980c2a0a35ULL); + + // Check consistency between CSipHasher and SipHashUint256[Extra]. + FastRandomContext ctx; + for (int i = 0; i < 16; ++i) { + uint64_t k1 = ctx.rand64(); + uint64_t k2 = ctx.rand64(); + uint256 x = GetRandHash(); + uint32_t n = ctx.rand32(); + uint8_t nb[4]; + WriteLE32(nb, n); + CSipHasher sip256(k1, k2); + sip256.Write(x.begin(), 32); + CSipHasher sip288 = sip256; + sip288.Write(nb, 4); + BOOST_CHECK_EQUAL(SipHashUint256(k1, k2, x), sip256.Finalize()); + BOOST_CHECK_EQUAL(SipHashUint256Extra(k1, k2, x, n), sip288.Finalize()); + } } BOOST_AUTO_TEST_SUITE_END()