roconnor-blockstream
commented
10 months ago This is pretty significant.
Profiling (see #214) shows that upwards of 60% of time is spent on computing various Merkle roots, in this kind of case. The use of Merkle trees for syntax is what enables pruning and helps with sharing, but we do have to run at least one SHA256 compression function per node when computing a Merkle Root. In this example there is slightly more that one node per serialized byte (i.e. per WU). For each node, not only do we need to perform a CMR computation but we need to do an IMR computation as well, which needs to hash not only the node, but the input and output Type Merkle roots. Additionally type Merkle roots themselves need to be computed, which again is potentially on the order of the size of the DAG, as it is in this test case.
The coverage analysis tool tells that we do can do up to 4 calls to the compression function per node (which is approximately per WU). If we estimate the cost of the compression function to be 225 ns, and if we want to maintain our goal of doing no more than 500 ns of work per WU, then we are in trouble because we can only do 2 calls to the compression function per node, and that leaves basically no time to do any other of the type inference work.
A couple of options on how to deal with this issue come to mind:
1. We can presume/require that nodes have SHA2 hardware acceleration
@apoelstra suggests hashing would be 100x faster with hardware acceleration. I think the improvements would be more modest than that, but it would certainly be faster. We could benchmark with this extended instruction set and see if that solves the problem.
2. We could eat into the budget
We currently use a budget mechanism to require a certain amount of witness weight to cover the cost of evaluation (which can be exponential in the size of the program). Stuffing the annex with empty data may be necessary to cover the cost of evaluation. (Technically tapscript does the same budgeting; its just that the annex trick isn't required for anything but the most obscene programs.)
We could extend this budget mechanism to count the number of nodes and cover the cost of all the hashing using the same budgeting system.
3. We could revamp the entire serialization format
This solution is my current favourite.
I devised the current bit-based serialization format to try to squeeze Simplicity programs to be as small as possible. But this issue suggests that the current serialization format is "too good".
We could revamp the format entirely to assign smaller codewords to jets. Jets have no parameterization whatsoever, and thus their CMRs and IMRs could be entirely precomputed, thus they wouldn't really incur compression costs. Then the Simplicity combinators can be assigned longer, multibyte codewords which would automatically consume sufficent WUs to cover all their hashing and other processing costs.
At the same time we can replace the current bit-based serialization format with a byte-based one. I'm sure this would make a lot of developers happy to be able to parse byte-streams instead of bit-streams.
I would probably also separate the witness data into a separate witness stack item while we are at it as there is no pressure on us to keep the number of bytes down to an absolute minimum in light of this issue.
sanket1729
apoelstra
uncomputable
I found a program that seems to exceed the expected runtime given its cost.
The program is constructed as follows:
Importantly, the type signature of
f(n)differs depending on how it is used. Sharing happens after the program is constructed.Let's build a C test vector that measures the runtime. The Elements test suite is inaccurate because it runs the same program multiple times.