HS18
Distributed Systems Advanced & Blockchain (DSA)
DSA Challenge Task HS 2018 Winner
The winning group is: Dumeni Vincenz, Fabio Rosetto, Alessandro Bonomo.
The jury and students were impressed by their innovative solution to use the IOTA blockchain as a signaling layer for WebRTC. Their chat application met all the requirements and showed how a truly decentralized solution could be built.
The contents of the lecture are still being defined. Thus, topics below are just an indication. The PDFs and other files are accessible within the HSR network. If you want to access these files from home, use VPN.
| Nr | Date | Preliminary Topics | Who | Files |
|---|---|---|---|---|
| 01 | 18.09.2018 | Admin / Miniproject / Repetition VSS | Thomas Bocek | DSA-HS18-01-Admin_v2.pdf, DSA-HS18-01-VSS_v3.pdf |
| 02 | 25.09.2018 | Repetition VSS / TomP2P Basics | Thomas Bocek | DSA-HS18-02-TomP2P_v1.pdf, tomp2ptest.zip |
| 03 | 02.10.2018 | WebRTC / TomP2P recap | Thomas Bocek | DSA-HS18-03-WebRTC_v1.pdf, DSA-HS18-02-TomP2P-2_v1.pdf |
| 04 | 09.10.2018 | Security Considerations / Ethereum | Thomas Bocek | DSA-HS18-02-Security_v3.pdf, DSA-HS18-04-Ethereum_v2.pdf |
| 05 | 16.10.2018 | Ethereum II / Security | Roman Blum / Thomas Bocek | DSA-HS18-05-SmartContracts_v1.pdf |
| 06 | 23.10.2018 | ICOs / NEO | Thomas Bocek | DSA-HS18-06-ICO_v1.pdf, DSA-HS18-06-NEO_v2.pdf |
| 07 | 30.10.2018 | IOTA / Bazo PoS and Bazo Sharding | Roman Blum / Thomas Bocek | DSA-HS18-06-IOTA_v4.pdf, DSA-HS18-07-ConsensusScalability_v3.pdf |
| 08 | 06.11.2018 | Protocol Details - Noise, RLPx, QUIC / Kademlia broadcast | Thomas Bocek | DSA-HS18-08-Protocol_v3.pdf |
| 09 | 13.11.2018 | vDHT / Raft / Paxos / Applied Cryptography | Thomas Bocek | DSA-HS18-09-Consensus-Classic_v1.pdf, DSA-HS18-09-ECC_v1.pdf |
| 10 | 20.11.2018 | Monero | Sebastian Küng | monero.pdf |
| 11 | 27.11.2018 | Bitcoin Advanced | James Chiang | teachbitcoin.github.io Due to the restructuring of the course material, no questions about this topic will be asked in the exam |
| 12 | 04.12.2018 | Blockchain Voting Cryto Mining Admin(challenge task, exam, feedback) | 08:10-08:55 Christian Killer, Raphael Matile 09:05-09:30 Nello Tolino 09:35-09:50 Thomas Bocek | provotum.pdf Mining_Lecture.pdf DSA-HS18-12-Admin_v1.pdf |
| 13 | 11.12.2018 | Challenge Task Presentations | Students | |
| 14 | 18.12.2018 | Fragestunde und Feedback | Thomas Bocek/Roman Blum | DSA-HS18-14-Admin_v1.pdf |
| 15 | 08.01.2019 | Beratungswoche | Thomas Bocek/Roman Blum |
Questions that were asked during the exam
- Assume that 2 peers are behind different NATs and no network device blocks ports. Describe one reason why UPD hole-punching can fail.
- Ports are assigned randomly, little chance to know the port in advance (correct)
- The conntrack table entries have a TTL, if an entry expires, connections can fail (correct)
- TCP sequence number was guessed wrong, so the connection was aborted (correct in case of TCP, UDP does not have a sequence number)
- Which bucket should peer 0x101b check for id 0x010b
- 1, 2, 3 (correct), 4, or 5?
- Which replication strategy for online availability is preferred
- Direct Replication (correct)
- Indirect Replication
- Rsync works well with compressed data
- There are some issues with rsync and compressed data (correct)
- No issue with rsync and compressed data
- Merkle proof only needs to know the uncle hashes (log n)
- True (correct)
- False, it needs to know all the hashes
- How to stay anonymous when using Bitcoins? (answer: go against the known heuristics, don't post any address from your wallet that links to your identity)
- Why is running a DHT on a mobile phone not optimal? (answer: battery drain due to network always being used)
- add(location_key, value) → is translated to put(location_key, hash(value), value). Is this a set or list?
- Its a set (correct)
- Its a list
- Its both
- Why is sharding in Blockchains not is easy? Why is a DHT not suitable to store blocks? (answer: DHT can loose data, blockchain should never loose data)
- On the English Wikipedia, it says: "UDP hole punching will not work with symmetric NAT devices...". Why is this statement wrong? (answer: a symmetric NAT can still support port-preservation or if the port assignment is deterministic, it can be probed
- Is anonymity in Bitcoins / Ethereum possible?
- True (correct, if done right)
- False
- P2P is less effort than centralized?
- P2P is less effort
- P2P is more effort (correct)
- How can you remain anonymous when dealing with cryptocurrencies? (answer: you could use Monero or Zcash)
- Transaction malleability: why do you want to chain transactions?
- To not always store TXs onchain (expensive) (correct)
- To allow micropayments (only store final balance) (correct)
- Because its called a blockchain
- How to attack Ethereum? (answer: one possibility - 51% attack)
- If an ICO allows direct payin to a contract (Ethereum) and an investor pays directly from an exchange, why will the investor loose everything? (answer: because the private key belongs to the exachange, thus also the resulting token)
- Ethereum contracts can receive Ethers. What is the drawback of funding/sending ethers directly to a smart contract? (answer: see above, repetition)
- How expensive is KYC in CH (Video Identifikation)? Upfront and per customer
- Upfront 2'000 CHF - 5'000 CHF and 2-3 CHF per customet
- Upfront 20'000 CHF - 50'000 CHF and 20-30 CHF per customer (correct)
- What consensus algorithm is used by the NEO blockchain?
- Practical Byzantine Fault Tolerance (PBFT)
- Proof of Work (PoW)
- Delegated Proof of Stake (DPOS)
- Proof of Stake (PoS)
- Delegated Byzantine Fault Tolerance (DBFT) (correct)
- The Bitcoin header nonce is a 32-bit integer. An Antminer S9 computes 14 TH/s. How long does it take until all possible combinations are computed?
- 0.0003 seconds (correct)
- 0.004 seconds
- 40 seconds
- 232 seconds
- 13 minutes
- In 2010, an explicit block size limit of 1 MB was introduced into Bitcoin by Satoshi Nakamoto. As transaction volume increased with widespread Bitcoin adoption, increasing the limit became subject to heavy debate in 2015. What are possible advantages as well as disadvantages of increasing the block size?
- More transactions per second, less scalability
- Less decentralization, increased scalability
- Increased decentralization, less scalbility
- More transactions per second, increased centralization (correct)
- Which hashes are required, besides hash HK, to calculate and prove that transaction HK is in the tree?
- HIJ, HKL, HMNOP, HABCDEFGH
- HL, HIJ, HMNOP, HABCDEFGH (correct)
- HK, HKL, HIJKL, HIJKLMNOP
- HL, HIJ, HIJKLMNOP, HABCDEFGH
- What is the latency on a ping (RTT) with a satellite connection?
- ~329 ms
- ~600 ms (correct)
- ~1930 ms
- What other UDP-based transport protocols do you know? (answer: QUIC, KCP, UDT)
- Does a public blockchain message need to be encrypted? Give a reason (answer: no, since everbody can read the transactions, however, e.g. Monera encrypts the messages in such way, that it can be verified but not read)
- Ethereum / Opinion: compression or protocol redesign? (opinion, there is no correct answer)
- I would add compression
- I would redesign the protocol
- What are the drawbacks of using 0RTT (Decryption without handshake could lead to DoS where a peer is spammed with requests that it attempts to decrypt)
- A signature over the same data with the same key always generates the same signature
- Yes, always the same signature
- No, it always different (correct)
- When should you use PoW or PoS consensus, and when should you use Paxos or Raft? (answer: blockchain PoW/PoS, cluster Paxos/Raft)
Challenge Task HS 2018
This semester's challenge task (CT) is the design and implementation of a fully-distributed, P2P messaging application with an integrated, blockchain-based notary service.
The system consists of two parts:
- The first part will be similar to a instant messaging application such as Bleep, Signal, or Telegram, where users are able to message other application's users. The application should have the notion of a contact list composed of friends. A friend is defined as being another application's user that accepted to appear within a respective user's contact list -- therefore the friendship is bi-directional, meaning that users should send requests to other users asking permission to be added. Once the permission is granted, the specific user becomes available in the contact list. Moreover, a user should be able to chat with one or more friends (supporting group chat) when the respective users are online. In order to achieve this, the user's contact lists as well as the user's status (online or offline) should be stored in a distributed manner. Optionally, the application should be able to support offline messages, meaning that offline users are able to receive either chat messages when they go online (at any time). Each student's group is free to decide about specifics of building the P2P messaging application and how to organize the information within the distributed network.
- The second part consists of a fully decentralized, persistent notary service (Eingeschriebener Brief). A user has the option to send a message and the recipient has to acknowledge its reception. The user on the receiving end should have the possibility to accept or reject such a message. The proof of reception needs to be globally and permanent available. Thus, even when sender and recipient are colluding are denying a message, it should still be provable by any other peer that the message was received.
Requirements
All requirements below must be met in order to pass the challenge task.
- Full decentralization and P2P mechanisms: The solution shall not contain any central elements (besides bootstrapping peers) and the solution shall be based on peer-to-peer mechanisms. Any peer can be used for bootstrapping. The solution can enable access from multiple peers and the solution shall be robust against peer or link failure.
- Send messages between peers. The application must support one-to-one and group communication.
- Quickly and easily verify messages. Each participating user of the network is connected to a wallet. Users can create verified messages from their connected wallet.
Further requirements are:
- The solution may use existing libraries and code, but those must be allowed to be published under an open software license.
- The final presentation shall outline the application and architecture.
Libraries and Tools
The items below represent supporting libraries, tools, or references that are recommended to be taken into consideration.
- We recommend to use Java as the programming language. You should use the latest version (Java10), as this has usually more useful features than older versions. The J2SE Software Development Kit (SDK) can be downloaded under http://java.sun.com/javase/downloads/. Features that are of particular interest is the new file notification API built into Java10.
- The use of TomP2P as a P2P overlay technology is recommended. TomP2P is an open-source implementation of the Kademlia DHT. More information can be found at http://tomp2p.net/ with a quick introduction to the TomP2P library.
- Note that you are allowed to use any language or framework. However, the supervisors are familiar with those: C#.NET, Swift, Java, and Golang. With respect to the P2P library, you have to research suitable libraries on your own if you are not using TomP2P.
- Ethereum is the most popular public blockchain for smart contracts. You can also use a Testnet such as Ropsten or Rinkeby.
- Use Remix as Web IDE to develop your smart contract with Solidity.
Organization
- The groups shall be equally balanced, each containing 3 team members. Please register your group in this form until September 23rd.
- During the challenge task, the group shall meet every week during exercise hours to work on the task and discuss the next steps.
- The groups shall utilize their homework times to work on the CT, besides the exercise time slots assigned on Tuesday or Wednesday.
- You do not have be physically present at the exercises. The supervisors will be available in the office 1.169 and can relocate to the exercise room if required on Tuesday, and on Wednesday only by request.
- The groups shall determine and set-up an internal project plan with the overall milestones timings provided here.
- Distribute the workload so that each group member gets a fair load of work (P2P load balancing, no free riding!) and make sure activities can run in parallel (non-blocking).
- Do not miss the opportunity of discussing details with your supervisor, he might give you good hints.
Milestones
There will be one milestone during the CT. The milestone shall include a fully distributed P2P system, preferably including basic messaging functionality.
Please send your source code to your supervisors until November 6th 23:59. Make sure that your submission includes setup instructions. If the supervisors are not able to run your application using the instructions given, you will be disqualified from winning an award. However, you will be given a second chance to submit your source code a week later in order to still pass the attestation. If you fail the second chance, you won't be able to attend the examination.
Presentation and Evaluation
Challenge task presentations and demonstrations will take place on December 11th. On these dates, the groups will present and demonstrate their results, which will be evaluated by a jury. Presentations and demos on dates will start at 08:10 in 3.114, and we will continue at 10:10 in room 1.263.
- Each group will have exactly 10 minutes for presenting their design and to demonstrate the working application (roughly 5 min presenting and 5 min demo). You will be interrupted by us if you exceed the 10 minutes presentation time. The presentation shall include slides. For the demonstration, you must run at least four instances (peers) on different machines. You can use your own laptops or machines from the HSR. Most of the demonstration, though, will be done using the machine connected to the projector(s), so more people can see what is going on. Ideally, it is the same machine that will run the slide presentation.
- Make sure that everything will work for your demo! Test everything beforehand with given conditions, especially the network. If a group fails to present within its time window, it will be disqualified.
- Remember that the audience will not only be interested in seeing whether or not your application works, but more specifically how the designed mechanisms for messages, contact list storage, and chat messages work behind the scenes. So it must be visible what these instances are doing; the UI must clearly show, for example, what messages peers exchange, which keys/values they store and query, how the application deals with users being online or offline, and how two users are connected to send messages. This can be achieved, for instance, by using a log file and tail -f.
- After the demonstration, each group will be evaluated by the jury. The jury is composed of lecturers and assistants, and each member will cast one vote per group. The following criteria will be taken into consideration: software design and implementation (fulfillment of requirements, overall design, trade-offs considered, scalability, usability, reliability of chat messages and payments), team work, presentation and demonstration of the solution. The results of the votes will be collected and disclosed after the last presentation.
- The winning group will have to present the application to their fellow students in the last lecture on December 18th. Furthermore, they will receive a prize (in Ether) and the "HSR P2P Challenge Champion 2018" award.
Note: The participation of the CT is mandatory for the permission to attend the exam. There will be no grade and you can only pass or fail the CT. However, keep in mind that participation will greatly reduce the effort you have to spend studying for the exam.