Solution MidTerm 2017 Solution MidTerm 2017
Advanced Programming Advanced Programming
Giuseppe Attardi
Giuseppe Attardi
Università di Pisa
Università di Pisa
General Remarks General Remarks
Follow good programming guidelines Follow good programming guidelines
– eg:
– https://github.com/twitter/commons/blob/master /src/java/com/twitter/common/styleguide.md
In particular: In particular:
–NEVER, EVER, EVER USE
global variables:
they hinder parallelism
Use exceptions sparingly (and handle Use exceptions sparingly (and handle them)
them)
Use strings sparingly (StringBuffer) Use strings sparingly (StringBuffer)
Use Object Oriented Use Object Oriented
Programming Programming
USE Polymorphism, USE Polymorphism
makes your code more modular, more readable, more extensible
Avoid using Reflection (instanceof)
Avoid static methods Avoid static methods , aka functions, , aka functions, in OOP
in OOP
Avoid functions for similar tasks Avoid functions for similar tasks : : use polymorphic method in each of use polymorphic method in each of
the classes where the operation is the classes where the operation is
needed
needed
Bad Example Bad Example
class Utils { class Utils {
static String bytesToString(); static String bytesToString();
static String inputstoString(); static String inputstoString();
static String outputsToString(); static String outputsToString();
… … } }
Alternative: Alternative:
– Use method serialize() in each class
Exercise 1
Exercise 1
Hash Hash
class
class HashHash { {
private static final MessageDigest md =private static final MessageDigest md = MessageDigest.getInstance(“SHA-256”);MessageDigest.getInstance(“SHA-256”);
public byte[] code;public byte[] code;
public Hashpublic Hash(byte[] bytes) {(byte[] bytes) { code = md.digest(bytes);
code = md.digest(bytes);
}}
boolean isValidboolean isValid() { return code[0] == 0 && () { return code[0] == 0 && …… code[2] == 0; }
code[2] == 0; }
boolean equalsboolean equals(Hash other) {(Hash other) {
return Arrays.equals(code, other.code);return Arrays.equals(code, other.code);
}} }}
Input Input
class
class InputInput extends Pair<Hash, Integer> { extends Pair<Hash, Integer> {
// Hash for transaction, Integer for index in outputs // Hash for transaction, Integer for index in outputs public Inputpublic Input(Transaction t, int idx) {(Transaction t, int idx) {
super(new Hash(t.serialize()), idx);super(new Hash(t.serialize()), idx);
} }
public byte[] public byte[] serializeserialize() {() {
byte[] hash = getKey().code;byte[] hash = getKey().code;
byte bb = ByteBuffer.allocate(hash.length + 4);byte bb = ByteBuffer.allocate(hash.length + 4);
bb.put(hash).putInt(getValue());bb.put(hash).putInt(getValue());
return bb.array();return bb.array();
}} }}
class
class OutputOutput extends Pair<Integer, PublicKey> { extends Pair<Integer, PublicKey> { public public OutputOutput(int v, PublicKey key) { (int v, PublicKey key) { …… } }
public byte[] serializepublic byte[] serialize() { () { …… } } }}
Transaction Transaction
class
class Transaction Transaction implements Serializable { implements Serializable { private List<Input> inputs; private List<Input> inputs;
private List<Output> outputs; private List<Output> outputs;
private byte[] signature; private byte[] signature;
public Transaction public Transaction () { () {
inputs = new ArrayList<>();
inputs = new ArrayList<>();
outputs = new ArrayList<>();
outputs = new ArrayList<>();
} }
public add public add (Input i) { (Input i) { inputs.add(i); inputs.add(i);
} }
public add public add (Output o) { (Output o) { outputs.add(o); outputs.add(o);
} }
Transaction Transaction
public void
public void signsign(PrivateKey key) {(PrivateKey key) {
Signature s = new Signature(”SHA256withRSA”);Signature s = new Signature(”SHA256withRSA”);
s.init(key);s.init(key);
for (Input i : inputs)for (Input i : inputs)
s.update(i.serialize());s.update(i.serialize());
for (Output o : outputs) for (Output o : outputs) s.update(o.serialize()); s.update(o.serialize());
signature = s.sign();signature = s.sign();
}}
public byte[]
public byte[] serializeserialize() {() {
byte bs = ByteArrayOutputStream();byte bs = ByteArrayOutputStream();
for (Input i : inputs)for (Input i : inputs) bs.write(i.serialize());bs.write(i.serialize());
for (Output o : outputs)for (Output o : outputs) bs.write(o.serialize());bs.write(o.serialize());
bs.write(signature);bs.write(signature);
return bs.toByteArray();return bs.toByteArray();
}}
Block Block
class
class BlockBlock implements Serializable { implements Serializable { private int seq;
private int nonce = -1;
private Hash previous;
private Transaction t;
public Block(int seq, Hash previous, Transaction t) { … } public hash() {
return new Hash(serialize());
}
public int mine() { Hash hash;
do {
nonce++;
hash = this.hash();
} while (!hash.isValid()) return nonce;
}
Block Block
public byte[]
public byte[] serializeserialize() {() {
byte bs = ByteArrayOutputStream();byte bs = ByteArrayOutputStream();
bs.write(ByteBuffer.allocate(4).putInt(bs.write( seq).array());seq).array());
bs.write(ByteBuffer.allocate(4).putInt(bs.write( nonce).array());nonce).array());
bs.write(previous.hash());bs.write(previous.hash());
bs.write(t.serialize());bs.write(t.serialize());
return bs.toByteArray();return bs.toByteArray();
}}
Exercise 2
Exercise 2
BlockChain BlockChain
class BlockChain { class BlockChain {
private List<Block> chain = new LinkedList<>();
boolean isValidBlockChain() {
Map<Hash, BitSet> spentOutputs = new HashMap<>();
Hash current = null; // current block in chain for (Block next : chain) { // next block in chain Transaction tx = next.transaction;
if (current == null) {
spentOutputs.put(new Hash(tx.serialize()), new BitSet(tx.getOutputs().size()));
current = next;
continue;
}
Hash previous = current.previous();
Hash hash = next.hash();
if (!hash.isValid() || !hash.equals(previous)) // current block must refer to next one return false;
for (Input input : tx.getInputs()) {
if (spentOutputs.computeIfPresent(input.getKey(), // update spentOutputs (k, v) -> {
if (v.get(input.getValue())) // already spent output at index input.getValue() return null;
v.set(input.getValue()); // update
return v; // put back into Map
}) == null) return false;
}
spentOutputs.put(new Hash(tx.serialize()), new BitSet(tx.getOutputs().size()));
current = next;
}
return true;
}
public int getBalance(PublicKey user) {
Map<Hash, BitSet> spentOutputs = new HashMap<>();
Iterator <Block> it = chain.descendingIterator(); // from last to first while (it.hasNext()) {
Block b = it.next();
Transaction tx = b.transaction();
Hash hash = new Hash(tx);
List<Output> outputs = tx.getOutputs();
for (int i = 0; i < outputs.size(); i++) { Output o = outputs.get(i);
if (user.equals(o.getValue()) &&
(spentOutputs.get(hash) == null || !spentOutputs.get(hash).get(i))) balance += o.getKey();
}
// now add the outputs to the map spentOutputs for (Input in : tx.getInputs())
spentOutputs.computeIfAbsent(in.getKey(), v -> new BitSet()).set(in.getValue()));
}
return balance;
}
Exercise 3
Exercise 3
public static void main(String args[]) { String input;
String[] tokens;
Scanner reader = new Scanner(System.in);
init();
do { do {
System.out.print("> ");
input = reader.nextLine().trim();
} while (input.equals(""));
tokens = input.split("\\s+");
switch (tokens[0]) { case "status":
printBlockChain();
break;
case "check":
if (chain.isValidBlockChain())
System.out.println("The block chain is valid!");
else
System.out.println("The block chain is not valid.");
break;
Exercise 4
Exercise 4
A closure is a functional object that consists of a function and the lexical environment at the time of its creation. The environment contains the bindings for the non local variables visible in the scope of the function.
In C#, a delegate type is a type that represents functions with a given signature.
A delegate instance is created on an object and a method on that object compatible with its
signature.
A delegate instance can be used as a function by invoking it with arguments, and this
corresponds to invoking the delegate method on the delegate target with the given
arguments.
