We want to encourage research in bounties related to RSA, as some Ethereum-related projects (VDF, DARK using RSA) make use of relatively recent assumptions that we believe are as difficult as the RSA problem and IFP, but of course this is unproven Assumptions to be checked RSA Adaptive root problem: Computing random prime roots of chosen elements in RSA groups with unknown factorization is hard [Necessary for Wesolowski]; implies Low order assumption RSA Low order problem: Finding an element with low order in an RSA group with unknown factorization is hard [Necessary for Pietrzak] Strong RSA assumption [RSA Accumulators] Suggested bounties It is very unlikely that the assumptions will be outright broken. Also, a lot of research has been done on IFP (Integer Factorization Problem), so even if any really cool ideas came about on say, the adaptive root problem, it might not initially compete with factorization on pure computational terms.
6/19/2023Reverse Bit Order Reverse bit order is the name for the order of a sequence of $n$ integers, that comes from reversing the bit sequence of each individual integer and then ordering by the resulting integer. It is an idempotent operation. For example, applying this to the integers $0,1,2,3,4,5,6,7$, results in the reverse bit order sequence $0,4,2,6,1,5,3,7$. Now say we have a root of unity $\omega^8=0$. Then the sequence $\omega^0,\omega^4,\omega^2,\omega^6,\omega^1,\omega^5,\omega^3,\omega^7$ is a permutation of the roots of unity of order 8 with the following nice properties: Partitioning it into the first four and the second four elements, we get a subgroup of order 4 ($\omega^0,\omega^4,\omega^2$) and a coset of order 4 ($\omega^6,\omega^1,\omega^5,\omega^3,\omega^7$) Partitioning it into four sets of size 2, we get cosets of the order 2 subgroup: ($\omega^0,\omega^4$) (which is also the subgroup), ($\omega^2,\omega^6$), ($\omega^1,\omega^5$) and ($\omega^3,\omega^7$) This property of the reverse bit order extends to higher powers: If you partition any list of length $n=2^k$ into powers of two, you always get cosets in each partition. This is useful for Fourier transforms.
2/23/2023Previous data shard construction: Add $n=64$ data shards to the beacon chain. Each slot, $n$ proposers independently propose their shard blobs, which are then confirmed by committees. Once a shard blob is confirmed (this can take several slots), it can be referenced by the execution chain. Here is an alternative proposal: Add a new type of transaction that can contain additional sharded data as calldata. The block is then constructed by a single block builder (which can be different from the proposer using proposer builder separation), and includes normal transactions as well as transactions with sharded calldata. This is efficient because it means that tight integrations between rollups and L1 become possible, and it is expected that this "super-block-builder" strategy will emerge in practice anyway in order to maximize MEV extraction. Advantages: Tighter coupling with the current Eth1 chain -- rollup data is immediately visible to manager contracts All data is confirmed together with the rollup calls Do not need to wait until shard blocks are confirmed
7/28/2022Assume $n \cdot n$ samples ($n$ per row and column), $v$ validators, and each validator being able to repopulate $s$ samples (because their rows and columns intersect at $s$ points). What we want: Very high probability that at least 50% of the samples on each row and column can be repopulated from orthogonal rows/columns. Probability computation For each given sample, the probability that one of the validators can make it available as one of their reconstructed samples is $$ p = 1 - (1 - q) ^ {s v} $$ where $q = \frac{1}{n^2}$.
5/19/2022