# Styling RSS w XLS notes
XML files can include both xml-stylesheets (XSLT) and normal stylesheets (CSS).
XSLT files are transformations, and allow you to process an XML doc into an HTML doc (among other things).
In this case, it doesn't matter if we import the CSS here or via /rss/rss.xsl -- it gets applied either way.
The XSLT will output HTML for us, but the HTML content from the RSS feed (i.e., the bodies of posts) must be unescaped.
There's a special attribute (`disable-output-escaping`) which will do that.
However, we need to run some JS, too, because not every browser supports decoding html like that.
* firefox does not seem to support `disable-output-escaping="yes"`, so it requires the JS in rss.js
* chrome does support `disable-output-escaping="yes"`, so don't remove those attrs
The JS works by testing `#cometestme`, and then (if needed) looping over elements matching `[name=decodable]` and basically `el.innerHTML = el.textContent`.
Note, `disable-output-escaping="yes"` is a legacy feature from XSLT v1.0; the new way to do it is with character maps.
When I tried those, they didn't seem to work in firefox (which is when I tried the original JS).
IDK if chrome support character maps, but if it does, then that is a good update to implement. TODO I guess.
Efficient Reorgs on Cryptonets<p>Every <a href="https://xk.io/glos/pow">PoW</a> driven cryptonet has a state. The state of Bitcoin (and forks) is the particular
set of Unspent Transaction Outputs (UTXOs) at the time - essentially the set of all Bitcoin
able to be spent.</p>
<p>When a new block arrives, the usual process to update the state is simple:</p>
<p>{% highlight text %}
Start with S[n,0] (state at block n)
Apply the first transaction from the new block (B[0]) to S</p>
<p>S[n,k] + B[k] -> S[n,k+1] for all k in B</p>
<p>S[n+1,0] = S[n,max(k)+1]
{% endhighlight %}</p>
<p>However, what happens when a new block arrives causing a <a href="https://xk.io/glos/reorg">reorganisation</a> of the main chain?</p>
<p>{% highlight text %}
. 3a← 4a <-- 3a and 4a are not in the main chain currently
↙
1 ← 2 ← 3 ← 4 <-- 3 and 4 are in the main chain</p>
<blockquote>
<p>5a arrives, causing the reorg:</p>
</blockquote>
<p>1 ← 2 ← 3a← 4a← 5a <-- New main chain
↖
3 ← 4 <-- Old main chain, 3 and 4 no longer in the main chain</p>
<p>In this case block #2 was the lowest common ancestor (a pivot point)
of the two competing chains 3a->5a and 3->4.
{% endhighlight %}</p>
<h2 id="the-problem-of-reorgs">The problem of reorgs</h2>
<p>Let's presume the distance from the <a href="https://xk.io/glos/lca">lowest common ancestor</a> (LCA) and the new head is <code>n</code>.</p>
<p>Bitcoin et al solve the issue by stepping backwards through time.</p>
<p>Since Bitcoin transactions spend outputs, and outputs may be spent only once, playing the
blockchain backwards is trivial:</p>
<p>{% highlight text %}
for each transaction:
remove it's outputs from the list of UTXOs.
add the outputs it spends to the list of UTXOs.
{% endhighlight %}</p>
<p>And bam! You can then play time forward from the LCA to calculate the new state. How nice.</p>
<p>What happens, though, when we move to a cryptonet that only operates on balances and doesn't
use the input/output system of Bitcoin?</p>
<p>Well, provided we're recording every transaction it's quite simple. A transaction moving
<code>X</code> coins from <code>A</code> to <code>B</code> results in <code>A-=X</code> and <code>B+=X</code>. That is trivial to reverse. However, the
caveat is that we must record every transaction. Once we start including complex mechanisms
within the protocol that produce transactions that are not recorded but simply implied, we
can no longer play time 'backwards' as <code>S[m]</code> depends on <code>S[m-1]</code> and without knowing <code>S[m-1]</code> to
calculate the implied transactions, we can't play time backwards. Of course, if we know <code>S[m-1]</code>
we don't need to do any of this anyway, so we're sort of stuck.
Examples of this sort of mechanism can be found in the way contracts create
transactions in Ethereum and the market evaluation in Marketcoin.</p>
<p>Remembering <code>S[m-1]</code> is easy but what if the reorg is of length 2, or 3, or 10? We can't just
remember <em>all</em> the states.</p>
<p>So, we can see that we have a problem.</p>
<h2 id="efficiently-remembering-states">Efficiently remembering states</h2>
<p>The intuitive solution (to me, at least) is to know <em>some</em> but not all states at strategic
intervals between the genesis block and the current head. When a reorg of length <code>n</code>
occurs, the network has already committed to evaluating <code>n</code> new states. I define 'efficient'
here to mean evaluating no more than <code>2n</code> new states (in the worst case). Unfortunately,
this means we'll need to remember about <code>2*log(2,h)</code> states, where <code>h</code> is the height of the
chain head. All the UTXOs in Bitcoin take up a few hundred meg of RAM, so for 500,000 blocks
we're looking at no more than 40 states, but that's still ~10 GB of space (by Bitcoin's
standards) which isn't ideal. It's unlikely that we'll see long reorganisations, but we'd still
be storing half of the figures mentioned above, which, while better, isn't perfect.</p>
<p>One solution may be to record the net implied change of state as the last transaction,
but that solution might be more painful than the cure, and requires introducing extra
complexity into the network architecture, which I'm against, so we won't consider
this option here.</p>
<p>In addition to the above constraint on 'efficient', we also require that for each block
building on the main chain we should only have to calculate one new state (the updated
current state). This implies that when we step through the blockchain, we only ever
forget cached states, with the exception of the new state produced by the next block.</p>
<p>Somewhat-formally:</p>
<p>{% highlight text %}
Current head is of height n.</p>
<p>A[n] = {cached states at height n}</p>
<p>Block n+1 arrives:</p>
<p>assert A[n] is a superset of {all a in A[n+1] s.t. a is not of height n+1}
{% endhighlight %}</p>
<p>Thus <code>A[n+1]</code> can be described as the set of some or all of the states in <code>A[n]</code> and
the state at <code>n+1</code>, and therefore our collection of states does
not requrie regeneration on each new block.</p>
<p>I propose a solution below that has a number of desired properties:</p>
<ul>
<li>A reorg of length <code>n</code> requires computing no more than <code>2n</code> states</li>
<li>Space efficient: <code>k</code> states saved where <code>ld(h) <= k <= 2*ld(h)</code></li>
<li>Incremental: only one new state has to be calculated for each new block</li>
</ul>
<p>{% highlight text %}
Initial conditions:
- Reorg length: n
- Current height: h >= 3
- i = 0; i < h</p>
<p>2<sup>k</sup> < h - i <= 2<sup>k+1</sup> is always the case for some k
if h-i == 2: set k to 1. (it would otherwise be 0)</p>
<p>After finding k, and while h-i > 1:
1. Cache states at height i + 2<sup>k</sup> and i + 2<sup>k-1</sup>.
2. i += 2<sup>k-1</sup>
{% endhighlight %}</p>
<p>and in python: (testing all combinations up to 2<sup>13)</sup></p>
<p>{% highlight python %}
import math</p>
<p>h = 3
states = set([1,2])</p>
<p>while h <= 2*<em>13:
newStates = set()
# find largest k s.t. 2<sup>k</sup> < h
i = 0
while h-i >= 2:
k = math.log(h-i)//math.log(2)
newStates.add(int(2</em><em>k)+i)
newStates.add(int(2</em><em>(k-1))+i)
i += int(2</em>*(k-1))
ts1 = set(states) # temp set for testing superset requirement
ts1.add(h) # add the current state (instead of removing it from newStates)
assert ts1 >= newStates # ts1 is a superset of newStates
l = list(newStates) # temp list just to print
l.sort()
print(h, math.log(h)//math.log(2)+1, len(l), l)
states = newStates
h += 1
{% endhighlight %}</p>
<p>Because of the ~log(n) space requirement a very fast block time is not a major concern.
A chain with a target time of 1 minute requires about 1.5x the storage capacity of an
equivelant chain with a target time of 10 minutes in the first year, and this ratio
rapidly approaches 1 in the following years.</p>
<p>That said, after the first year with a 1 minute block time, we'd be storing around 30 states.
If we ignored all states more than 2000 blocks deep (a day and a bit) we're still storing more
than 15, which isn't a particularly great optimisation. (When we have events like the
<a href="https://bitcoin.org/en/alert/2013-03-11-chain-fork">Fork of March 2013</a> we would like clients
to adjust quickly and efficiently).</p>
<p>I have some ideas about state-deltas to try and solve this issue (which is
ungood, but not doubleplusungood) but that can wait for a future post.</p>
https://xk.io/n/2006