Skip to content

Commit fe7cc1f

Browse files
lhfbclhfbc
authored
[fix iotaledger-archive#272] fix one doubleSpend problem (iotaledger-archive#287)
* fix doubleSpend * split the oprations into two funciton. * add ut for utxograph and fix a bug.
1 parent 65012d5 commit fe7cc1f

3 files changed

Lines changed: 297 additions & 19 deletions

File tree

‎src/main/java/com/iota/iri/pluggables/utxo/TransactionData.java‎

Lines changed: 13 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -133,12 +133,12 @@ public void batchPutIndex(List<Hash> hashList) {
133133
if(hashList.size() != tmpStorage.size() || hashList.size() <= 1) {
134134
return;
135135
}
136-
int i=hashList.size()-1;
136+
int i=0;
137137
for(Hash h : hashList) {
138138
for (Txn t : tmpStorage.get(i)) {
139139
putIndex(t, h);
140140
}
141-
i--;
141+
i++;
142142
}
143143
tmpStorage.clear();
144144
}
@@ -238,10 +238,7 @@ public void readFromIPFSAddr(String ipfsAddr) throws IOException{
238238
constructTxnsFromRawTxns(rawTxnsList);
239239
}
240240

241-
242-
public void init() {
243-
transactions = new ArrayList<>();
244-
241+
public static Txn genesis() {
245242
List<TxnOut> txnOutList = new ArrayList<>();
246243
TxnOut txOut = new TxnOut();
247244
txOut.amount = 1000000000; //just for testing
@@ -256,7 +253,13 @@ public void init() {
256253

257254
newTxn.txnHash = generateHash(new Gson().toJson(newTxn));
258255

259-
addTxn(newTxn);
256+
return newTxn;
257+
}
258+
259+
public void init() {
260+
transactions = new ArrayList<>();
261+
262+
addTxn(genesis());
260263
}
261264

262265
public Txn getLast() {
@@ -365,7 +368,7 @@ private Txn doCreateRawTxn(RawTxn txn) {
365368
return newTxn;
366369
}
367370

368-
private String generateHash(String txnStr) {
371+
public static String generateHash(String txnStr) {
369372
String trytes = Converter.asciiToTrytes(txnStr);
370373

371374
byte[] trits = Converter.allocateTritsForTrytes(trytes.length());
@@ -395,11 +398,11 @@ public long getBalance(String account) {
395398
utxoGraph.markDoubleSpend(totalTopOrders, txnToTangleMap);
396399
//
397400
Set<String> visisted = new HashSet<>();
398-
401+
399402

400403
long total = 0;
401404

402-
for (int i = 0; i < transactions.size(); i++) {
405+
for (int i = 0; i < transactions.size(); i++) {
403406
Txn transaction = transactions.get(i);
404407
if(visisted.contains(transaction.txnHash)) {
405408
continue; //FIXME this is a problem

‎src/main/java/com/iota/iri/pluggables/utxo/UTXOGraph.java‎

Lines changed: 73 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,7 @@ public void addTxn(Txn newTx, int idx) {
6060
if(outGraph.get(key) == null) {
6161
outGraph.put(key, new HashSet<String>());
6262
}
63-
63+
6464
for(int i=0; i<newTx.outputs.size(); i++) {
6565
String val = newTx.txnHash + ":" + String.valueOf(i) + "," + newTx.outputs.get(i).userAccount;
6666
Set<String> outs = outGraph.get(key);
@@ -115,8 +115,8 @@ public void markDoubleSpend(List<Hash> order, HashMap<String, Hash> txnToTangleM
115115
}
116116
}
117117

118-
public void markTheLaterAsDoubleSpend(List<Hash> order, HashMap<String, Hash> txnToTangleMap, Set<String> valSet) {
119-
Map<String, Integer> toSort = new ConcurrentHashMap<>();
118+
private void markTheLaterAsDoubleSpend(List<Hash> order, HashMap<String, Hash> txnToTangleMap, Set<String> valSet) {
119+
Map<String, Integer> toSort = new ConcurrentHashMap<>();
120120
for(String out : valSet) {
121121
Hash h = txnToTangleMap.get(out);
122122
int pos = order.indexOf(h);
@@ -134,18 +134,82 @@ public void markTheLaterAsDoubleSpend(List<Hash> order, HashMap<String, Hash> tx
134134
.collect(
135135
toMap(e -> e.getKey(), e -> e.getValue(), (e1, e2) -> e2,
136136
LinkedHashMap::new));
137-
137+
138138
int i = 0;
139-
for(String key : sorted.keySet()) {
139+
for(String key : sorted.keySet()) {
140140
if(i>0) {
141141
doubleSpendSet.add(key);
142142
}
143143
i++;
144144
}
145145
}
146146

147+
private boolean isAllOutsWithSingleIns(Set<String> vals) {
148+
// If all the subs have only one 'up', as following, the up MUST have been spent.
149+
// *
150+
// / \
151+
// * *
152+
for (String s: vals) {
153+
Set<String> set = inGraph.get(s);
154+
if (set.size() != 1) {
155+
return false;
156+
}
157+
}
158+
return true;
159+
}
160+
161+
private boolean isAllOutsOkWithMultipleIns(String key, Set<String> vals) {
162+
// *1 *2
163+
// / \ /
164+
// *3 *4
165+
// If *2 is doubleSpent, *4 will be doubleSpent too. so *1 should be countted in total balance install of *3.
166+
167+
// divide all the vals into groups by the transaction hash.
168+
Map<String, Set<String>> groups = new HashMap<>();
169+
for (String s: vals) {
170+
String[] out = s.split(":");
171+
String hash = out[0];
172+
if (!groups.containsKey(hash)) {
173+
Set<String> set = new HashSet<>();
174+
set.add(s);
175+
groups.put(hash, set);
176+
} else {
177+
Set<String> set = groups.get(hash);
178+
set.add(s);
179+
}
180+
}
181+
182+
// check each group if it have an doubleSpent item
183+
for (String k: groups.keySet()) {
184+
boolean allTxnOutOk = true;
185+
for (String s: groups.get(k)) {
186+
if (isDoubleSpend(s)) {
187+
allTxnOutOk = false;
188+
}
189+
}
190+
191+
if (allTxnOutOk) {
192+
return true;
193+
}
194+
}
195+
196+
return false;
197+
}
198+
147199
public Boolean isSpent(String key) {
148-
return outGraph.containsKey(key);
200+
if (outGraph.containsKey(key)) {
201+
Set<String> vals = outGraph.get(key);
202+
203+
if (isAllOutsWithSingleIns(vals)) {
204+
return true;
205+
}
206+
207+
if (isAllOutsOkWithMultipleIns(key, vals)) {
208+
return true;
209+
}
210+
}
211+
212+
return false;
149213
}
150214

151215
public Boolean isDoubleSpend(String key) {
@@ -196,7 +260,7 @@ public void printGraph(Map<String, Set<String>> graph, String k, Set<String> spe
196260
if(spend.contains(val)) {
197261
writer.write("\""+IotaUtils.abbrieviateHash(val, 6)+"\"[" + "shape=square]\n");
198262
}
199-
}
263+
}
200264
} else {
201265
System.out.println("\"" + IotaUtils.abbrieviateHash(key, 6) + "\"->" +
202266
"\"" + IotaUtils.abbrieviateHash(val, 6) + "\"");
@@ -205,8 +269,8 @@ public void printGraph(Map<String, Set<String>> graph, String k, Set<String> spe
205269
System.out.println("\""+IotaUtils.abbrieviateHash(val, 6)+"\"[" + "style=filled, fillcolor=red]");
206270
} else if (!isSpent(val)) {
207271
System.out.println("\""+IotaUtils.abbrieviateHash(val, 6)+"\"[" + "style=filled, fillcolor=green]");
208-
}
209-
}
272+
}
273+
}
210274
} catch(Exception e) {
211275
;
212276
}

0 commit comments

Comments
 (0)