Bitcoin Core  27.99.0
P2P Digital Currency
compressor.cpp
Go to the documentation of this file.
1 // Copyright (c) 2009-2010 Satoshi Nakamoto
2 // Copyright (c) 2009-2021 The Bitcoin Core developers
3 // Distributed under the MIT software license, see the accompanying
4 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
5 
6 #include <compressor.h>
7 
8 #include <pubkey.h>
9 #include <script/script.h>
10 
11 /*
12  * These check for scripts for which a special case with a shorter encoding is defined.
13  * They are implemented separately from the CScript test, as these test for exact byte
14  * sequence correspondences, and are more strict. For example, IsToPubKey also verifies
15  * whether the public key is valid (as invalid ones cannot be represented in compressed
16  * form).
17  */
18 
19 static bool IsToKeyID(const CScript& script, CKeyID &hash)
20 {
21  if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160
22  && script[2] == 20 && script[23] == OP_EQUALVERIFY
23  && script[24] == OP_CHECKSIG) {
24  memcpy(&hash, &script[3], 20);
25  return true;
26  }
27  return false;
28 }
29 
30 static bool IsToScriptID(const CScript& script, CScriptID &hash)
31 {
32  if (script.size() == 23 && script[0] == OP_HASH160 && script[1] == 20
33  && script[22] == OP_EQUAL) {
34  memcpy(&hash, &script[2], 20);
35  return true;
36  }
37  return false;
38 }
39 
40 static bool IsToPubKey(const CScript& script, CPubKey &pubkey)
41 {
42  if (script.size() == 35 && script[0] == 33 && script[34] == OP_CHECKSIG
43  && (script[1] == 0x02 || script[1] == 0x03)) {
44  pubkey.Set(&script[1], &script[34]);
45  return true;
46  }
47  if (script.size() == 67 && script[0] == 65 && script[66] == OP_CHECKSIG
48  && script[1] == 0x04) {
49  pubkey.Set(&script[1], &script[66]);
50  return pubkey.IsFullyValid(); // if not fully valid, a case that would not be compressible
51  }
52  return false;
53 }
54 
56 {
57  CKeyID keyID;
58  if (IsToKeyID(script, keyID)) {
59  out.resize(21);
60  out[0] = 0x00;
61  memcpy(&out[1], &keyID, 20);
62  return true;
63  }
64  CScriptID scriptID;
65  if (IsToScriptID(script, scriptID)) {
66  out.resize(21);
67  out[0] = 0x01;
68  memcpy(&out[1], &scriptID, 20);
69  return true;
70  }
71  CPubKey pubkey;
72  if (IsToPubKey(script, pubkey)) {
73  out.resize(33);
74  memcpy(&out[1], &pubkey[1], 32);
75  if (pubkey[0] == 0x02 || pubkey[0] == 0x03) {
76  out[0] = pubkey[0];
77  return true;
78  } else if (pubkey[0] == 0x04) {
79  out[0] = 0x04 | (pubkey[64] & 0x01);
80  return true;
81  }
82  }
83  return false;
84 }
85 
86 unsigned int GetSpecialScriptSize(unsigned int nSize)
87 {
88  if (nSize == 0 || nSize == 1)
89  return 20;
90  if (nSize == 2 || nSize == 3 || nSize == 4 || nSize == 5)
91  return 32;
92  return 0;
93 }
94 
95 bool DecompressScript(CScript& script, unsigned int nSize, const CompressedScript& in)
96 {
97  switch(nSize) {
98  case 0x00:
99  script.resize(25);
100  script[0] = OP_DUP;
101  script[1] = OP_HASH160;
102  script[2] = 20;
103  memcpy(&script[3], in.data(), 20);
104  script[23] = OP_EQUALVERIFY;
105  script[24] = OP_CHECKSIG;
106  return true;
107  case 0x01:
108  script.resize(23);
109  script[0] = OP_HASH160;
110  script[1] = 20;
111  memcpy(&script[2], in.data(), 20);
112  script[22] = OP_EQUAL;
113  return true;
114  case 0x02:
115  case 0x03:
116  script.resize(35);
117  script[0] = 33;
118  script[1] = nSize;
119  memcpy(&script[2], in.data(), 32);
120  script[34] = OP_CHECKSIG;
121  return true;
122  case 0x04:
123  case 0x05:
124  unsigned char vch[33] = {};
125  vch[0] = nSize - 2;
126  memcpy(&vch[1], in.data(), 32);
127  CPubKey pubkey{vch};
128  if (!pubkey.Decompress())
129  return false;
130  assert(pubkey.size() == 65);
131  script.resize(67);
132  script[0] = 65;
133  memcpy(&script[1], pubkey.begin(), 65);
134  script[66] = OP_CHECKSIG;
135  return true;
136  }
137  return false;
138 }
139 
140 // Amount compression:
141 // * If the amount is 0, output 0
142 // * first, divide the amount (in base units) by the largest power of 10 possible; call the exponent e (e is max 9)
143 // * if e<9, the last digit of the resulting number cannot be 0; store it as d, and drop it (divide by 10)
144 // * call the result n
145 // * output 1 + 10*(9*n + d - 1) + e
146 // * if e==9, we only know the resulting number is not zero, so output 1 + 10*(n - 1) + 9
147 // (this is decodable, as d is in [1-9] and e is in [0-9])
148 
149 uint64_t CompressAmount(uint64_t n)
150 {
151  if (n == 0)
152  return 0;
153  int e = 0;
154  while (((n % 10) == 0) && e < 9) {
155  n /= 10;
156  e++;
157  }
158  if (e < 9) {
159  int d = (n % 10);
160  assert(d >= 1 && d <= 9);
161  n /= 10;
162  return 1 + (n*9 + d - 1)*10 + e;
163  } else {
164  return 1 + (n - 1)*10 + 9;
165  }
166 }
167 
168 uint64_t DecompressAmount(uint64_t x)
169 {
170  // x = 0 OR x = 1+10*(9*n + d - 1) + e OR x = 1+10*(n - 1) + 9
171  if (x == 0)
172  return 0;
173  x--;
174  // x = 10*(9*n + d - 1) + e
175  int e = x % 10;
176  x /= 10;
177  uint64_t n = 0;
178  if (e < 9) {
179  // x = 9*n + d - 1
180  int d = (x % 9) + 1;
181  x /= 9;
182  // x = n
183  n = x*10 + d;
184  } else {
185  n = x+1;
186  }
187  while (e) {
188  n *= 10;
189  e--;
190  }
191  return n;
192 }
A reference to a CKey: the Hash160 of its serialized public key.
Definition: pubkey.h:24
An encapsulated public key.
Definition: pubkey.h:34
bool IsFullyValid() const
fully validate whether this is a valid public key (more expensive than IsValid())
Definition: pubkey.cpp:304
void Set(const T pbegin, const T pend)
Initialize a public key using begin/end iterators to byte data.
Definition: pubkey.h:89
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
A reference to a CScript: the Hash160 of its serialization.
Definition: script.h:583
Implements a drop-in replacement for std::vector<T> which stores up to N elements directly (without h...
Definition: prevector.h:37
size_type size() const
Definition: prevector.h:296
value_type * data()
Definition: prevector.h:532
iterator begin()
Definition: prevector.h:304
void resize(size_type new_size)
Definition: prevector.h:330
bool DecompressScript(CScript &script, unsigned int nSize, const CompressedScript &in)
Definition: compressor.cpp:95
bool CompressScript(const CScript &script, CompressedScript &out)
Definition: compressor.cpp:55
static bool IsToPubKey(const CScript &script, CPubKey &pubkey)
Definition: compressor.cpp:40
static bool IsToKeyID(const CScript &script, CKeyID &hash)
Definition: compressor.cpp:19
static bool IsToScriptID(const CScript &script, CScriptID &hash)
Definition: compressor.cpp:30
uint64_t DecompressAmount(uint64_t x)
Definition: compressor.cpp:168
uint64_t CompressAmount(uint64_t n)
Compress amount.
Definition: compressor.cpp:149
unsigned int GetSpecialScriptSize(unsigned int nSize)
Definition: compressor.cpp:86
@ OP_CHECKSIG
Definition: script.h:189
@ OP_EQUAL
Definition: script.h:145
@ OP_DUP
Definition: script.h:124
@ OP_HASH160
Definition: script.h:186
@ OP_EQUALVERIFY
Definition: script.h:146
assert(!tx.IsCoinBase())