Communications of the ACM
Last byte
Bounce Blockchain
At a time when the proof-of-work technique for the Bitcoin blockchain consumes as much electricity as the entire country of Denmark, and other techniques require a 2/3 majority of "stake," or fraction of ownership, yet can still be subverted, there is a simple energy-parsimonious solution to ensure the integrity of blockchains that, incidentally, also gives rise to some cool puzzles.
The idea is to implement a broadcast network through a satellite (or one or more cubesats), here we call the "Primary." Users sign their transactions and send them to satellites that bounce them to the Primary, which collects all the transactions received during some time period, say, one second, into a block, signs the block with its private key, and includes the hash of that block and the hash of the previous block. The Primary then sends the block, possibly partitioned into packets, to many sites on Earth.
There is a simple energy-parsimonious solution to ensure the integrity of blockchains that, incidentally, also gives rise to some cool puzzles.
Suppose the flood of data is too much for some sites, with each site able to take only one packet of the block. The sites then exchange information with other sites to reconstruct the whole block.
Warm-up. Suppose each of five sites receives one of the five packets of a block, as shown in this "map" of initial allocations: A: 1; B: 2; C: 3; D: 4; E: 5
How many time steps, each having duration of, say, 0.01 seconds, will it take for all sites to collect all five packets in the block? In one time step, one site s1 is able to send one packet to another site x and receive one packet from another site y. Note x and y may or may not be the same.
Solution. Exactly five time steps starting with this:
Initial allocation
A: 1; B: 2; C: 3; D: 4; E: 5
A—1 → B
B—2 → C
C—3 → D
D—4 → E
E—5 → A
A: 1,5; B: 2,1; C: 3,2; D: 4,3; E: 5,4;
A—5 → B
B—1 → C
C—2 → D
D—3 → E
E—4 → A
A: 1,5,4; B: 2,1,5; C: 3,2,1; D: 4,3,2; E: 5,4,3 and so on.
In the warm-up, we had a symmetric distribution among sites, but such a condition may not always be the case.
Challenge. Suppose the five packets were initially allocated according to the map in the figure here: A: 1; B: 2; C: 3; D: 4; E: 5, F: 1; G: 3
Figure. How can you ensure every site acquires all five packets in the block in five time units using only pairwise exchanges of single packets?
What is the smallest number of time steps needed to ensure all seven sites acquire all five packets? One solution could be
A—1 → B
B—2 → C
C—3 → D
D—4 → E
E—5 → F
F—1 → G
G—3 → A
A: 1,3; B: 2,1; C: 3,2; D: 4,3; E: 5,4; F: 1,5; G: 3,1
A—3 → B
B—1 → C
C—2 → D
D—4 → F
E—4 → G
F—5 → A
G—1 → E
A: 1,3,5; B: 2,1,3; C: 3,2,1; D: 4,3,2; E: 5,4,1; F: 1,5,4; G: 3,1,4
A—5 → B
B—2 → E
C—2 → F
D—4 → A
E—4 → C
F—5 → G
G—1 → D
A: 1,3,5,4; B: 2,1,3,5; C: 3,2,1,4; D: 4,3,2,1; E: 5,4,1,2; F: 1,5,4,2; G: 3,1,4,5
A—4 → B
B—5 → D
C—3 → E
D—2 → A
E—5 → C
F—2 → G
G—3 → F
Being able to solve this problem in five time steps was, in a sense, lucky. Suppose, for example, five kinds of packets were distributed over 20 sites, with 16 of them allocated packet 1. It would then take at least 19 steps just to send packet 2 (or 3, 4, and 5, respectively) to all sites. In fact, a lower bound if there are n sites is that if some packet is distributed to only j sites, then it would take at least ceiling((n–j)/j) time steps for all sites to acquire all packets.
Upstart 1. Suppose the block is divided into k packets that are sent, collectively, to n > k sites such that each packet goes to at least one site and all sites know the initial allocation map. What is the smallest number of time steps needed so each site acquires all packets, assuming that, in each time step, each site can send up to p packets to a single destination site and receive p packets from the same or another single site?
Upstart 2. How would you answer upstart 1 if you did not know the map, but each site could send its knowledge of the map whenever it sends its packets? That is, along with the p packets a given site s1 sends to another site s2, s1 can share any information it has received from other sites about which packets those other sites have received and when, as well as their initial allocation.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
©2018 ACM 0001-0782/18/9
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.
No entries found