Walking Onions: week 3 update
On our current grant from the zcash foundation, I'm working on a full specification for the Walking Onions design. I'm going to try to send out these updates once a week.
My previous updates are linked below:
Week 1: formats, preliminaries, git repositories, binary diffs, metaformat decisions, and Merkle Tree trickery.
https://lists.torproject.org/pipermail/tor-dev/2020-March/014178.html
Week 2: Specifying details of SNIP and ENDIVE formats, in CDDL.
https://lists.torproject.org/pipermail/tor-dev/2020-March/014181.html
You might like to check out those updates, and their references, if this update doesn't make sense to you.
===
As you might recall, the SNIPs need to be nice and small, but they need to be completely self-contained. The ENDIVE, on the other hand, needs to be diff-friendly, and compressible. Relays need to derive all the SNIPs from the ENDIVE. The ENDIVE and SNIP formats that I worked on during last week [SNIPFMT] was designed to meet these criteria.
This week, I wrote up the algorithms to extract signed SNIPs from an ENDIVE. This is in section 4 [RECONST] of the specs in my work-in-progress repository [GITREPO] This was mainly straightforward consequence from the work I did last week, but there were a few things that turned up.
One trickier aspect of this work is that we want to move most of the decision-making to the authorities, and have the relays simply do an expansion algorithm. Updating all the relays would be slow, so relays need to be able to handle new index types and data types without fully understanding them. That means that we need to specify an algorithm that can work flexibly with many future kinds of data.
Another tricky aspect is that the data which the relays need to put into SNIPs all needs to be signed, so all of that data needs to come out the same when relays calculate it as the when the authorities calculate it. Thus, all the algorithms for building Merkle trees and indices and SNIPRouterData bodies need to be deterministic.
I think that I got all of this relatively right in [RECONST], but there are probably some mistakes hiding in there.
I'm hoping that there is a cleaner alternative to the weighted-index reconstruction algorithm -- the one that's there right now puts a lot of requirements on the input data, in order to avoid floating-point operations.
===
After working on ENDIVE expansion, I moved on to the problem of authorities voting. There's a lot of uncertainty here and decisions I'll need to make.
The biggest decision is how the new voting process for ENDIVEs should relate to the current voting process for consensus documents. The choices seem to be:
* Have two processes with different kinds of votes. * Expand the information that goes into current votes, and generate ENDIVEs as a new kind of consensus from the current voting process. * Design the ENDIVE voting process so that it can also be used to generate current-style consensuses.
Using separate processes might be simplest, but it does carry risk for duplicated code, and for the two voting processes reaching divergent results. It would also be potentially bad if an authority could vote differently in each process.
The second approach -- where ENDIVEs are another kind of consensus generated from current-style voting documents -- has some charm to it, but it perpetuates our current consensus-voting system, and makes us specify a second encoding of CBOR objects as text, if we want to vote on them meaningfully. This is a bit nasty, since the standard-specified text encoding of cbor is not a bijection, and doesn't mesh too well with our old directory format.
Therefore the third approach seems a little better to me now. In it, we'd specify our votes as a CBOR-based format loosely based on the current vote format, and describe a way to extract from them the same data that is currently used for our voting algorithm. This would let us encode CBOR within the document naturally, while not having to throw away too much of our existing voting specification and voting code.
I've got a few more ideas here, though I don't have any specs yet. I've been collecting the ideas in a notes file [VNOTES] so I don't forget them.
===
While working on voting notes, I found some areas where the ENDIVE and SNIP formats might be better.
First, I hadn't thought about authority certificates. Those should go in, so that we can have the ENDIVE-signing keys be signed themselves with the authorities' long-lived identities.
Second, there seem to be some opportunities for transmitting indices in a simpler way. Instead of assigning a weight to each router separately, for example, we could derive one weighted index from another weighted index by re-weighting it, as we do with the "bandwidth-weights" values in the current consensus.
Teor also made some good suggestions for improving the diff format; I incorporated one and made a note to check the other.
===
I also spent a little while this week reading about BLS signatures, since they are the leading candidate for how we might do threshold signatures here.
===
Next week I'm going to try to get voting all specified. This will be a pretty deep dive, since I will need to maintain some backward compatibility with existing voting algorithms. There may be opportunities for simplification, however.
===
[GITREPO] https://github.com/nmathewson/walking-onions-wip
[RECONST] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/04-recons... d
[SNIPFMT] https://github.com/nmathewson/walking-onions-wip/blob/master/specs/02-endive...
[VNOTES] https://github.com/nmathewson/walking-onions-wip/blob/master/notes/voting.tx...
Hi Nick,
On 21 Mar 2020, at 05:38, Nick Mathewson nickm@torproject.org wrote:
Walking Onions: week 3 update
As you might recall, the SNIPs need to be nice and small, but they need to be completely self-contained. The ENDIVE, on the other hand, needs to be diff-friendly, and compressible. Relays need to derive all the SNIPs from the ENDIVE. The ENDIVE and SNIP formats that I worked on during last week [SNIPFMT] was designed to meet these criteria.
This week, I wrote up the algorithms to extract signed SNIPs from an ENDIVE. This is in section 4 [RECONST] of the specs in my work-in-progress repository [GITREPO] This was mainly straightforward consequence from the work I did last week, but there were a few things that turned up.
One trickier aspect of this work is that we want to move most of the decision-making to the authorities, and have the relays simply do an expansion algorithm. Updating all the relays would be slow, so relays need to be able to handle new index types and data types without fully understanding them. That means that we need to specify an algorithm that can work flexibly with many future kinds of data.
Another tricky aspect is that the data which the relays need to put into SNIPs all needs to be signed, so all of that data needs to come out the same when relays calculate it as the when the authorities calculate it. Thus, all the algorithms for building Merkle trees and indices and SNIPRouterData bodies need to be deterministic.
I think that I got all of this relatively right in [RECONST], but there are probably some mistakes hiding in there.
I'm hoping that there is a cleaner alternative to the weighted-index reconstruction algorithm -- the one that's there right now puts a lot of requirements on the input data, in order to avoid floating-point operations.
There's a shorter encoding for Raw:
for each [i, pos1, pos2] in index_ranges: w = pos2 - pos1 j = the index of pos1 among all sorted pos1s new_encoding = [i, j, w]
[i, j, w] is an efficient encoding if index_ranges is sparse compared with ENDIVERouterData, because: * j has the same cardinality as I * w is smaller than pos1 and pos2
If index_ranges is dense, there may be a more efficient encoding: add missing i with weight 0 drop j
With this encoding, you can drop a few of the constraints.
There's a faster calculation and more efficient encoding for Weighted, because there's a common factor in each POS() calculation: (1 << 32) / total_weight
If we remove that factor, we end up with a much simpler algorithm, that's also more flexible:
Algorithm: Expanding a "Weighted" indexspec.
Each weighted indexspec also has a multiplier, which may vary between indexspecs.
Let total_weight = SUM(indexspec.index_weights) Verify total_weight * multiplier <= UINT64_MAX.
Let total_so_far = 0. Let result_idx = {} (an empty mapping). Define POS(b) = b * multiplier
For 0 <= i < LEN(indexspec.indexweights): Let w = indexspec.indexweights[i]. Let lo = POS(total_so_far). Let total_so_far = total_so_far + w. Let hi = POS(total_so_far) - 1. Append (lo, hi) => i to result_idx.
Return result_idx.
If multiplier is large, then the weights can be quite small. (Small weights sacrifice some accuracy.) And if the multiplier is 1, you effectively have a "Raw" index.
If you make those changes, you should be able to use a similar process to expand all the different index types. (After multiplying, truncating, or hashing, you either end up with a delta, or an absolute position. You can turn deltas into absolute positions, and then feed them all into the same base algorithm.)
There are also a few things I think might be bugs:
Was there meant to be a constraint that the Weighted total is UINT64_MAX? Or close to UINT64_MAX? The fixed parameters don't make much sense otherwise.
I think v2 and v3 onion services assign descriptors to the next highest HSDir RSA id (or ed25519 hash). But INDEX_FROM_RING_KEYS() uses the relay input as the lowest value.
There is no next member for the last member in INDEX_FROM_RING_KEYS(), but the code asks for one. (Perhaps there are some typos here that make the code hard to understand.)
We'll need special treatment for ring wrapping. (That is, 0xFF… is not a real upper limit, it actually means, "use the lowest relay".)
It's weird to call a middle value a "suffix", but "infix" is also a bit of an unusual word.
There are also a bunch of typos, let me know when you're ready for copy-editing.
T
On Fri, Mar 20, 2020 at 5:09 PM teor teor@riseup.net wrote:
Hi Nick,
On 21 Mar 2020, at 05:38, Nick Mathewson nickm@torproject.org wrote:
Walking Onions: week 3 update
As you might recall, the SNIPs need to be nice and small, but they need to be completely self-contained. The ENDIVE, on the other hand, needs to be diff-friendly, and compressible. Relays need to derive all the SNIPs from the ENDIVE. The ENDIVE and SNIP formats that I worked on during last week [SNIPFMT] was designed to meet these criteria.
This week, I wrote up the algorithms to extract signed SNIPs from an ENDIVE. This is in section 4 [RECONST] of the specs in my work-in-progress repository [GITREPO] This was mainly straightforward consequence from the work I did last week, but there were a few things that turned up.
One trickier aspect of this work is that we want to move most of the decision-making to the authorities, and have the relays simply do an expansion algorithm. Updating all the relays would be slow, so relays need to be able to handle new index types and data types without fully understanding them. That means that we need to specify an algorithm that can work flexibly with many future kinds of data.
Another tricky aspect is that the data which the relays need to put into SNIPs all needs to be signed, so all of that data needs to come out the same when relays calculate it as the when the authorities calculate it. Thus, all the algorithms for building Merkle trees and indices and SNIPRouterData bodies need to be deterministic.
I think that I got all of this relatively right in [RECONST], but there are probably some mistakes hiding in there.
I'm hoping that there is a cleaner alternative to the weighted-index reconstruction algorithm -- the one that's there right now puts a lot of requirements on the input data, in order to avoid floating-point operations.
There's a shorter encoding for Raw:
for each [i, pos1, pos2] in index_ranges: w = pos2 - pos1 j = the index of pos1 among all sorted pos1s new_encoding = [i, j, w]
This will work when w is an integer that we can work on additively, but not so well when we're talking about something more like a hash ring. I think it makes sense to have two different possible encodings here, though. I'm calling this one "RawNumeric.
[i, j, w] is an efficient encoding if index_ranges is sparse compared with ENDIVERouterData, because:
- j has the same cardinality as I
- w is smaller than pos1 and pos2
If index_ranges is dense, there may be a more efficient encoding: add missing i with weight 0 drop j With this encoding, you can drop a few of the constraints.
There's a faster calculation and more efficient encoding for Weighted, because there's a common factor in each POS() calculation: (1 << 32) / total_weight
If we remove that factor, we end up with a much simpler algorithm, that's also more flexible:
Algorithm: Expanding a "Weighted" indexspec.
Each weighted indexspec also has a multiplier, which may vary
between indexspecs.
Let total_weight = SUM(indexspec.index_weights)
Verify total_weight * multiplier <= UINT64_MAX.
Let total_so_far = 0.
Let result_idx = {} (an empty mapping).
Define POS(b) = b * multiplier
For 0 <= i < LEN(indexspec.indexweights):
Let w = indexspec.indexweights[i].
Let lo = POS(total_so_far).
Let total_so_far = total_so_far + w.
Let hi = POS(total_so_far) - 1.
Append (lo, hi) => i to result_idx.
Return result_idx.
I'm not so sure about this one -- see the note below about the total value.
If multiplier is large, then the weights can be quite small.
(Small weights sacrifice some accuracy.) And if the multiplier
is 1, you effectively have a "Raw" index.
If you make those changes, you should be able to use a similar process to expand all the different index types. (After multiplying, truncating, or hashing, you either end up with a delta, or an absolute position. You can turn deltas into absolute positions, and then feed them all into the same base algorithm.)
There are also a few things I think might be bugs:
Was there meant to be a constraint that the Weighted total is UINT64_MAX? Or close to UINT64_MAX?
The actual intention is that it has to be " = UINT32_MAX", not" <= UINT32_MAX". Remember that the the client picks its next relay by specifying a random index value in range 0..UINT32_MAX, and it expects that the relay to that it is extending to _will_ have a snip that covers that range.
The fixed parameters don't make much sense otherwise.
I think v2 and v3 onion services assign descriptors to the next highest HSDir RSA id (or ed25519 hash). But INDEX_FROM_RING_KEYS() uses the relay input as the lowest value.
There is no next member for the last member in INDEX_FROM_RING_KEYS(), but the code asks for one. (Perhaps there are some typos here that make the code hard to understand.)
Okay, I'll have to look into this. I think you're probably right, and you _are_ right about the ring wrapping issues.
We'll need special treatment for ring wrapping. (That is, 0xFF… is not a real upper limit, it actually means, "use the lowest relay".)
It's weird to call a middle value a "suffix", but "infix" is also a bit of an unusual word.
There are also a bunch of typos, let me know when you're ready for copy-editing.
Once I'm through with sections 3 and 5, I'm going to do a big revision and consistency check of everything that's there before I move on to sections 6-8. Once that's done I hope that a copy edit would be more helpful.
Hi Nick,
This is from week 3:
On 30 Mar 2020, at 07:16, Nick Mathewson nickm@freehaven.net wrote:
There's a faster calculation and more efficient encoding for Weighted, because there's a common factor in each POS() calculation: (1 << 32) / total_weight
If we remove that factor, we end up with a much simpler algorithm, that's also more flexible:
Algorithm: Expanding a "Weighted" indexspec.
Each weighted indexspec also has a multiplier, which may vary
between indexspecs.
Let total_weight = SUM(indexspec.index_weights)
Verify total_weight * multiplier <= UINT64_MAX.
Let total_so_far = 0.
Let result_idx = {} (an empty mapping).
Define POS(b) = b * multiplier
For 0 <= i < LEN(indexspec.indexweights):
Let w = indexspec.indexweights[i].
Let lo = POS(total_so_far).
Let total_so_far = total_so_far + w.
Let hi = POS(total_so_far) - 1.
Append (lo, hi) => i to result_idx.
Return result_idx.
I'm not so sure about this one -- see the note below about the total value.
If multiplier is large, then the weights can be quite small.
(Small weights sacrifice some accuracy.) And if the multiplier
is 1, you effectively have a "Raw" index.
If you make those changes, you should be able to use a similar process to expand all the different index types. (After multiplying, truncating, or hashing, you either end up with a delta, or an absolute position. You can turn deltas into absolute positions, and then feed them all into the same base algorithm.)
There are also a few things I think might be bugs:
Was there meant to be a constraint that the Weighted total is UINT64_MAX? Or close to UINT64_MAX?
The actual intention is that it has to be " = UINT32_MAX", not" <= UINT32_MAX". Remember that the the client picks its next relay by specifying a random index value in range 0..UINT32_MAX, and it expects that the relay to that it is extending to _will_ have a snip that covers that range.
The fixed parameters don't make much sense otherwise.
Hmm, ok, then if we use multiplication, there are going to be some issues with the cumulative error from truncating the original division.
The error won't be too big, on average, it's N/2, worst case, it's N. (Where N is the number of indexes.) That's a tiny amount for large weights, but a huge amount for small weights. (Assuming that we continue to vote for relays with weights 1-100.)
But divisions also have some cumulative error.
Once you've revised these sections, let's review?
Only doing one division on the authorities is very appealing.
T
-
Nick Mathewson -
Nick Mathewson -
teor