tal-m
commented
4 years ago The new encoding scheme leads to much more efficient self-healing; this supersedes #10 for now.
Overview
We can think of each block as containing an encoding of votes for blocks in all previous layers. Each vote is a value in ${+1,0,-1}$ , corresponding to considering the block valid, being neutral, or considering the block invalid. The encoding scheme takes a vector of values and outputs a string that encodes it (the encoding can depend on all previous blocks that were received). The corresponding decoder takes the string and the previously-received blocks, and outputs the vector of votes.
In our current scheme, the encoding is very cheap (we just record the "view" of each block) but decoding is expensive ($\Omega(n^3)$ to completely decode a mesh with $n$ blocks).
We suggest moving to a new, more efficient encoding scheme, in which decoding is only $O(n^2)$, and (in the optimistic case) block sizes are also smaller.
Suggested Scheme: Simple
The encoded vector consists of a pointer to a "base" block, along with a list of "exceptions". An exception is a tuple $(X,v_X)$ such that the vote vector at position $X$ contains the vote $V_x$, but the base block's vote for $X$ is different. Note that if $B$ is in layer $i$, it votes neutral for all blocks in layers greater than $i$. Thus, since the base block is always in an earlier layer (though not necessarily the one immediately previous), the exception list will almost always contain votes for the most recent layers (the exception is when the Hare protocol has not terminated yet for those layers).
The decoder is recursive: to decode the votes of block $B$:
- Decode the votes of the base block $B'$. Let $V'$ be the output.
- Initialize the output vector $V\gets V'$.
- For every value (X,v_X) in the exception list, update $V[X]=v_x$.
Using dynamic programming, we can decode all the blocks in $O(n^2)$ memory and time: run the above algorithm for each block in sequence, but store the decoded vectors for all blocks once they are computed. Thus, step (1) takes constant time, so for every new block we use $O(n)$ time.
Potential optimization: sliding window
Just like the current Tortoise algorithm, we can keep only a sliding window of the votes for the last $k$ blocks rather than the full history. We set $k$ to be large enough that anything older will be in consensus and irreversible w.h.p.
We can also periodically rerun the algorithm with new data to ensure that we didn't miss anything due to the sliding window (see Verifying Tortoise below for efficient verification)
Suggested Scheme: DoS-prevention
The suggested scheme above encodes all votes perfectly (so our security proofs work without modification). However, the adversary can DoS the system by including arbitrarily-long exception lists. In order to prevent this, we'd like to limit the size of the exception list. If we do so, honest parties might not be able to encode their actual vote vectors (e.g., if every previous block in a party's view disagrees with that party on more than the exception-list limit).
We suggest the following workaround:
- Limit the size of the exception list (we need to figure out what this limit should be).
- If a party cannot encode its vote vector exactly (because it requires too many exceptions), it will do the following:
- Find a base block with the longest matching prefix
- Use its exception list to declare exceptions starting from the earliest one.
- Declare the first index at which the resulting vote vector has an "error" (i.e., the decoded vector does not match),
- Declare the requested size of the exception list that would allow exact encoding.
- When a block declares that its encoding has errors, the decoded vote vector will be considered neutral for all positions after the first error.
- A block will be allowed to created an extended exception list of length $L$, if it points to "enough" blocks (at least in the previous two clusters (i.e., previous 1600 blocks), such that the median of the requested exception list size is more than $L$ (a block that doesn't request a longer list is considered to request a list of the "regular" maximum length).
Analysis Ideas
If all honest blocks in a two-cluster sequence need a larger exception list (we use two clusters because we need to get closer to the 2/3 honest majority w.h.p), then the median will be larger, so the next set of blocks will be able to create larger lists. However, even if all malicious blocks request larger lists, the median won't change.
On the other hand, if there is an honest block that doesn't need a larger list, we're "ok" with other honest blocks using that as their base even with errors, since in our security analysis we don't care which honest block produced a block, just that it did.
This requires some more careful analysis
Suggested Implementation Guidelines
The scheme can be implemented in a very modular way: make sure the following are separate functions:
- Choosing the base block
- Computing the allowable exception list length
- Choosing which exceptions to include in the list.
This will allow us to initially implement a simplified version (e.g., one that doesn't limit the length of the list at all), and later update the algorithm to add DoS-prevention features.
Verifying Tortoise
The "Verifying Tortoise" is an optimized algorithm that, given a proposed vote vector, can verify whether this would be the output of the full Tortoise algorithm much more efficiently than actually running the full Tortoise.
The following $O(n)$ algorithm will work as long as all assumptions were satisfied since genesis (this is basically the same condition that we require for the current "optimized Tortoise):
- Mark the genesis block as "good"
- Go over all blocks, in order.
- For block $i$, mark it "good" if (1) its base block is marked good and (2) its exception list consists only of blocks that appear after the base block and are consistent with the input vote vector.
- Count the votes for the input vote vector by summing the weight of the good blocks (of course, each good block's weight only counts for the blocks preceding it).
- Declare the vote vector "verified" up to position $k$ if the total weight exceeds the confidence threshold in all positions up to $k$.
We need more research to see if we can extend this algorithm (or come up with another one) that will work even if assumptions were not satisfied for some periods in history.
avive
lrettig
In the new protocol, blocks should vote on a much larger set of blocks. We should: