Skip to content

Commit 0b1295b

Browse files
sipasipa
committed
Add SipHash-2-4 primitives to hash
1 parent 1f01443 commit 0b1295b

File tree

4 files changed

+142
-0
lines changed

4 files changed

+142
-0
lines changed

‎src/hash.cpp‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -81,3 +81,97 @@ void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char he
8181
num[3] = (nChild >> 0) & 0xFF;
8282
CHMAC_SHA512(chainCode.begin(), chainCode.size()).Write(&header, 1).Write(data, 32).Write(num, 4).Finalize(output);
8383
}
84+
85+
#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
86+
87+
#define SIPROUND do { \
88+
v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; \
89+
v0 = ROTL(v0, 32); \
90+
v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2; \
91+
v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0; \
92+
v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; \
93+
v2 = ROTL(v2, 32); \
94+
} while (0)
95+
96+
CSipHasher::CSipHasher(uint64_t k0, uint64_t k1)
97+
{
98+
v[0] = 0x736f6d6570736575ULL ^ k0;
99+
v[1] = 0x646f72616e646f6dULL ^ k1;
100+
v[2] = 0x6c7967656e657261ULL ^ k0;
101+
v[3] = 0x7465646279746573ULL ^ k1;
102+
count = 0;
103+
}
104+
105+
CSipHasher& CSipHasher::Write(uint64_t data)
106+
{
107+
uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
108+
109+
v3 ^= data;
110+
SIPROUND;
111+
SIPROUND;
112+
v0 ^= data;
113+
114+
v[0] = v0;
115+
v[1] = v1;
116+
v[2] = v2;
117+
v[3] = v3;
118+
119+
count++;
120+
return *this;
121+
}
122+
123+
uint64_t CSipHasher::Finalize() const
124+
{
125+
uint64_t v0 = v[0], v1 = v[1], v2 = v[2], v3 = v[3];
126+
127+
v3 ^= ((uint64_t)count) << 59;
128+
SIPROUND;
129+
SIPROUND;
130+
v0 ^= ((uint64_t)count) << 59;
131+
v2 ^= 0xFF;
132+
SIPROUND;
133+
SIPROUND;
134+
SIPROUND;
135+
SIPROUND;
136+
return v0 ^ v1 ^ v2 ^ v3;
137+
}
138+
139+
uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val)
140+
{
141+
/* Specialized implementation for efficiency */
142+
uint64_t d = val.GetUint64(0);
143+
144+
uint64_t v0 = 0x736f6d6570736575ULL ^ k0;
145+
uint64_t v1 = 0x646f72616e646f6dULL ^ k1;
146+
uint64_t v2 = 0x6c7967656e657261ULL ^ k0;
147+
uint64_t v3 = 0x7465646279746573ULL ^ k1 ^ d;
148+
149+
SIPROUND;
150+
SIPROUND;
151+
v0 ^= d;
152+
d = val.GetUint64(1);
153+
v3 ^= d;
154+
SIPROUND;
155+
SIPROUND;
156+
v0 ^= d;
157+
d = val.GetUint64(2);
158+
v3 ^= d;
159+
SIPROUND;
160+
SIPROUND;
161+
v0 ^= d;
162+
d = val.GetUint64(3);
163+
v3 ^= d;
164+
SIPROUND;
165+
SIPROUND;
166+
v0 ^= d;
167+
v3 ^= ((uint64_t)4) << 59;
168+
SIPROUND;
169+
SIPROUND;
170+
v0 ^= ((uint64_t)4) << 59;
171+
v2 ^= 0xFF;
172+
SIPROUND;
173+
SIPROUND;
174+
SIPROUND;
175+
SIPROUND;
176+
return v0 ^ v1 ^ v2 ^ v3;
177+
}

‎src/hash.h‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -171,4 +171,19 @@ unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char
171171

172172
void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64]);
173173

174+
/** SipHash-2-4, using a uint64_t-based (rather than byte-based) interface */
175+
class CSipHasher
176+
{
177+
private:
178+
uint64_t v[4];
179+
int count;
180+
181+
public:
182+
CSipHasher(uint64_t k0, uint64_t k1);
183+
CSipHasher& Write(uint64_t data);
184+
uint64_t Finalize() const;
185+
};
186+
187+
uint64_t SipHashUint256(uint64_t k0, uint64_t k1, const uint256& val);
188+
174189
#endif // BITCOIN_HASH_H

‎src/test/hash_tests.cpp‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,4 +47,24 @@ BOOST_AUTO_TEST_CASE(murmurhash3)
4747
#undef T
4848
}
4949

50+
BOOST_AUTO_TEST_CASE(siphash)
51+
{
52+
CSipHasher hasher(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL);
53+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0x726fdb47dd0e0e31ull);
54+
hasher.Write(0x0706050403020100ULL);
55+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0x93f5f5799a932462ull);
56+
hasher.Write(0x0F0E0D0C0B0A0908ULL);
57+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0x3f2acc7f57c29bdbull);
58+
hasher.Write(0x1716151413121110ULL);
59+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0xb8ad50c6f649af94ull);
60+
hasher.Write(0x1F1E1D1C1B1A1918ULL);
61+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0x7127512f72f27cceull);
62+
hasher.Write(0x2726252423222120ULL);
63+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0x0e3ea96b5304a7d0ull);
64+
hasher.Write(0x2F2E2D2C2B2A2928ULL);
65+
BOOST_CHECK_EQUAL(hasher.Finalize(), 0xe612a3cb9ecba951ull);
66+
67+
BOOST_CHECK_EQUAL(SipHashUint256(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL, uint256S("1f1e1d1c1b1a191817161514131211100f0e0d0c0b0a09080706050403020100")), 0x7127512f72f27cceull);
68+
}
69+
5070
BOOST_AUTO_TEST_SUITE_END()

‎src/uint256.h‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -83,6 +83,19 @@ class base_blob
8383
return sizeof(data);
8484
}
8585

86+
uint64_t GetUint64(int pos) const
87+
{
88+
const uint8_t* ptr = data + pos * 8;
89+
return ((uint64_t)ptr[0]) | \
90+
((uint64_t)ptr[1]) << 8 | \
91+
((uint64_t)ptr[2]) << 16 | \
92+
((uint64_t)ptr[3]) << 24 | \
93+
((uint64_t)ptr[4]) << 32 | \
94+
((uint64_t)ptr[5]) << 40 | \
95+
((uint64_t)ptr[6]) << 48 | \
96+
((uint64_t)ptr[7]) << 56;
97+
}
98+
8699
template<typename Stream>
87100
void Serialize(Stream& s, int nType, int nVersion) const
88101
{

0 commit comments

Comments
 (0)