Topic: Research topics in Bitcoin (Read 310 times)

@franky1 Thanks, among many papers in network topology topic, what papers would you recommend to start reading?

These r also interesting research areas/papers
*Consensus
https://youtu.be/WcwoA_s2Z_0
*Market Makers
https://youtu.be/UCBTh84aIwc
.
In general this TBPC site is like a bank of research papers
https://youtube.com/channel/UC_twxak5nXJrG-krI2c8YJA
& this one too
https://youtube.com/channel/UCLtXEnasHw3vJqKsupq80Ig

If we talk about MimbleWimble, then hiding amounts is not needed, we can leave that untouched, because if you have 100 inputs and 100 outputs (because anyone can join small transactions to form a bigger one), then you have no idea who owns what (and you have no idea how it was joined, because different miners can do that in different ways). I think adding range proofs or other ways of hiding amounts should be introduced separately.

Sure. As you already know, instead of using scrips, MW uses equations like a*G + H*k to represent a transaction for amount a and private key k (this implies that kH is a public key and we use the amount to make a second point. Then the points are added to get a transaction "ID", "hash", or whatever word is suitable to represent the uniqueness of the transaction).

Right now the main script types we are using are P2PKH, P2SH/P2WSH and P2WPKH. Somehow MW must make these kinds of scripts possible for compatibility reasons.

One way to do it would be, instead of multiplying a generator G by the amount a, to multiply the HAS160 of the script by G instead. (requires a soft fork to add a field to store this transaction "value"). This means the bitcoin script system will stay in place but what will actually be verified is this transaction "value" along with both generator points and whatever we end up using for a. This is quite cumbersome to handle though because now there's two steps of transaction signing/verification (bitcoin script and this MW point addition).

Another way of doing it would be to leave the current script types as they are, but make a new script type that stores the transaction "value/ID/hash" on the stack and using something like OP_EQ in the locking script. A soft fork would also be necessary here to add the new script type.

u may ask prof Eric Damiane about the accurate name of the data structure u r using, there r very fine details & I didn't complete reading ur MMR (I for example found Utreexo team using the term "cow forest" data structure in their discussion board that I couldn't find elsewhere and had to guess after a lot of Googling "cow" refers to recursion like the famous cheese cover exist everywhere inside)
.
My point was Utreexo too appends new UTXOs to the right as free leaves to accumulate each power of 2 with steps, it only differs in the way it deletes the UTXOs which involves "annoying" swaps as they described them. The new "evolving" Utreexo avoids the swaps in deletions completely, I just said that maybe their new swapless deletion scheme resembles deletions in MMR too.
.
Now that's the disputing part I disagree about, I think the Utreexo team probably hate me for being "persistent" in this
-Not all UTXOs have this nature, many do yes but not all, coinbase UTXOs have a min(not a peak) life of 101 and could reach O(10⁵), a fast sampling of less than 100 scattered block can gets u more than 20-40 of that order.
https://m.facebook.com/story.php?story_fbid=1432124977141946&id=100010333725264
-Add to this the burned UTXOs that will have infinity♾️ lifespan
https://user-images.githubusercontent.com/83260375/120076498-16874500-c0a6-11eb-9a48-84fb25599d54.jpg

.
-Even worse I found a Stanford report (Dec2015) that describes UTXOs as Chaotic with 2-3 different clusters u may say, with a follow-up AI (2017) that studied the median where u can also see 2 clusters one ascending and one approaching the X-axis.
.
-Now u get back to the Utreexo curve power-law or Pareto Distribution, and examine all the details...
-The curve says that about 10⁴ UTXOs lived for more than 1000 (10³) blocks, ...., and what r these thick areas& almost horizontal lines in the right?If it means consecutive adjacent values, then order analysis or drawing all in O(10⁵) as one point would have raised the point on the Y-axis at least by this length?
.
-In all, I believe either UTXOs should be categorized based on TX analysis & put in different trees according to their expected lifetime, or a different data structure could be used to accommodate all like Finger Tree or Van Emde Boas Tree or just layout,.....; Or both strategies.
.
(All the links r in my first comment to this post, instead of rewriting them again)
maybe just this
https://mobile.twitter.com/ArafatShymaa/status/1400197595029463040
.
Update remark:
Yes the performance is acceptable because in the forest structure, short living UTXOs will probably go away (become spent) while they r still in small trees of height 1-2, only other long living kinds I'm talking about will stay long enough to join the bigger trees(they will move gradually to the left). However, if the degradation in the insertion performance is slight and could pass, we r not sure that the enhancements in the deletion & the proof size in general ( by better tree height) doesn't worth the effort

Could you expand on what you mean by "common script types to its logarithmic-equation representation of transactions"?
Yeah, MW removes the Bitcoin script altogether. I don't see Bitcoin ever switching to MW design because it would drastically change the ability to audit the supply quite a bit. I also have no clue how this would be done on Bitcoin apart from doing it through an extension block.

MMR is a persistent data structure which enables things like FlyClient out of the box and it defaults to having new outputs on the far right of the tree(s). Looking at the Bitcoin blockchain, we can see that most of the outputs spent have been fairly recently created, which means that the MMR already has the optimized path sharing of these inclusion proofs.
It's a persistent data structure though so you can't know what has been deleted because an inclusion proof will always be valid, but you can complement the deletion by having another bitmap MMR and use one inclusion proof to know whether the output existed in the MMR and an inclusion proof for the bitmap MMR to know if it has been spent. Then you
might have everything you need (and perhaps more) without utreexo. In case you're interested, I tried to describe how to achieve fully validating node similar to utreexo node on a MW design with MMRs here https://gist.github.com/phyro/0ad4ccf71e936dd90545648110224e96, but it may be assuming some knowledge that is Grin specific

That's really amazing, I think this is almost the same idea as Utreexo, Utreexo uses a forest which is a number of trees with different powers of2 with insertions growing I'll say "almost" like MMR incase missed some details.
Only deletions r different in the original design, but in the improvement steps they removed the swaps switching to, again, resembling MMR
»However, they added the cache, the security analysis, & the UTXO lifespan analysis that I'm arguing against some it's details

This is the only paper that I read so far so I'll just comment on that. I'm kind of surprised that although the paper was written in 2016, no effort was made to post the common script types to its logarithmic-equation representation of transactions. It proposes removing Bitcoin Script, but since that is obviously impossible to do.

I also think it'll be difficult to try to put MimbleWimble properties into a new script type, you'd need another softfork like Segwit/Taproot that defines a new transaction version with extra fields, that a newer MimbleWimble script type can utilize.

Mimblewimble - https://github.com/mimblewimble/docs/wiki/MimbleWimble-Origin

Merkle Mountain Ranges - https://github.com/mimblewimble/grin/blob/master/doc/mmr.md, https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md

A2L: Anonymous Atomic Locks for Scalability in Payment Channel Hubs - https://eprint.iacr.org/2019/589.pdf

where I find Mimblewimble the most interesting one (by far). I think it's also simpler to achieve the benefits that come with Utreexo - without needing the utreexo accumulator.

Well, I just saw some people in the Ethereum community share the same worries, there r lots of supporting views/new ideas but since we r in Bitcointalk (not sure audience care about Ethereum) I just shared the common risks in scalability solutions
https://ethresear.ch/t/optimistic-rollup-is-not-secure-enough-than-you-think/9560
.
As for the Utreexo team, they didn't state their plans of how to approach full nodes. As I said in the previous comment, nothing about full nodes is written in the Utreexo gethub site yet. I quoted that from a post here about the HRF grant plans
https://bitcointalksearch.org/topic/--5266345
It is stated under "further development"
try to get Utreexo capabilities into Bitcoin Core node software

the reason to look into the network topology suggestion i made is just that

if idiots start running their branded full node in a less than full node option.
whether it be prunned or the gimmick 'stateless' or lite. then they are no longer blockchain seeders. but just leachers

what you then find is true full nodes dont want to be direct peers to leachers as its not helping themselves or others in the true decentraled network

if you want 8 connections to peers to have a safe varied/random observation of incoming blocks/transactions. you will not want to use up one of those limited resource peer connections on a leacher that doesnt relay.

thus why it says most cases of spv,lite.prunned."stateless" end up needing to self run a bridge node to be the seeder for the network and a translator. just to stay on the network.
or what actually happens is these less than full nodes end up using a commercial centralised service as their bridge.

..
there is alot of game theory and scenarios involved when you understand the network layout.
which does help to not only understand the network.. but also the users, the diversity, the power plays, and the challenges to offering different services and if differing services would ultimately help or mess with the network

in the case of utreexo full node users wont want to downgrade their node to a leacher wallet. otherwise there was no point in being a full node in the first place.
also full node users wont want to 'bridge' themselves to these downgraded leacher wallets

thus the NEED of utreexo to be added into a full node becomes less of a requirement. and more of a 'just make your own wallet software that API calls data from a proper node

.
in short utreexo wallets sit at the edges of the network. the bottom layer. sitting along side cell phone lite wallets

They call them stateless nodes as opposed to lite/full.
However, I read in a comment here (didn't contain the link to check) that their future work plans with the  research grants they took is to make it applicable to full nodes too.
It seems this is the trend everywhere due to scalability problems(check the burden blog article link from the comment above), Vitalik Buterin is talking about "sampling" which is in a simplified way validating/verifying only a random sample and give a time threshold for complains,
a week according to Justin Drake (a risk to the integrity I think, but maybe not too risky considering the Ethereum block rate of 10secs I guess)
https://www.joincolossus.com/episodes/14242194/drake-ethereum-into-the-ether?tab=blocks
I think min46 he starts talking about scalability
& That's from Vitalik (again more in the previous comment)
https://mobile.twitter.com/VitalikButerin/status/1371844878968176647
& from medium
https://medium.com/interdax/ethereum-l2-optimistic-and-zk-rollups-dffa58870c93
..
.
Anyways, like Utreexo these r just suggestions haven't took place yet

I find it awkward that u ask such question ignoring all cryptography, game Theory, Transaction Graph Analysis, AMM Automated Market Makers & their calculations to minimize the expected slippage (difference bet true & expected price) ,Merkle storing data structures,....
There's a lot of math & Theoretical CS here to learn & search in...
.
1-If u want something to approach new up-to-date protocols & still math, read about the Geometric Brownian Motion (Stochastic random walk) how it's used to represent the TX arrival (how to adapt the AMM EQs to the dynamic input of TXs, with TX arrival rate distribution expected mea, still keep u inside some price margin,...etc)
https://uniswap.org/blog/uniswap-v3/
https://github.com/Uniswap/uniswap-v3-core/
(The blog will lead u to the white paper where u can find the math stuff about BM and the rest of details)
.
2-The same random walk is used by this paper in EIP-1559 Simulations, where the BM is also used in simulating TXs arrival,
https://arxiv.org/abs/2102.10567
I forgot I had also this
https://mobile.twitter.com/barnabemonnot/status/1364096212517855236
Didn't re-read it after reading the paper, Oh yes there's an update of this she reached
https://notes.ethereum.org/@barnabe/rk5ue1WF_
(My not answered, I think math related, Qs
https://mobile.twitter.com/ArafatShymaa/status/1397430382878994432 )

3-Here's a punch of papers addressing the strength of a blockchain, not just1559,  against some attacks using Game Theory models
https://youtu.be/ndNyx-Oj9Wk
http://timroughgarden.org/papers/eip1559.pdf
Inside the report u'll find a lot of references, one of them
"Double-Spend Counterattacks: Threat of Retaliation in Proof-of-Work Systems", Daniel J.Moroz, Daniel J. Aronoff, Neha Narula, David C. Parkes, Feb2020
&Has just passed by this
https://ethresear.ch/t/bayesian-network-model-of-witness-creation-feedback-request/9115
.
4-The main public key cryptography used in most Blockchains is Elliptic Curve cryptography, that's gives a lot of room to math work in analysis, attacks,...etc
http://www.jbonneau.com/doc/B16a_BITCOIN_why_buy_when_you_can_rent.pdf
(I'm not sure, can't remember now, this paper addresses the hash from cryptographic or game thoeritic prospective)

5-you can read like forever the continuous changes/enhancements in the Ethereum Merkleization data structures ( they have 4 tries, they removed RLP recursive Length Prefix, they switched to binary Tries, they now suggesting 2-level tries Verkle from Vitalik-Merkle)
https://blog.ethereum.org/2020/11/30/the-1x-files-code-merkleization/
https://eips.ethereum.org/EIPS/eip-2926
https://eips.ethereum.org/EIPS/eip-2584

6-you can compare Merkles in each cryptocurrency (just said Eth uses Tries, Cardano uses AVL, Monero uses BST balanced periodically, Algorand don't use Merkle, in Bitcoin a lot of research Utreexo forest is the famous example)
https://www.programmersought.com/article/94887721041/
https://medium.com/coinmonks/merkle-trees-concepts-and-use-cases-5da873702318
I can find Cardano & Monero white papers online, tell me if u didn't the post became too crowded
...
There's a lot more, but reaching Utreexo,
7-u can help me in this dispute/contradiction/lack of mathematical understanding from my side, howcome what is described in this Stanford report as Chaotic (lifespan of UTXOs)
https://user-images.githubusercontent.com/83260375/119986617-5d047300-bfc4-11eb-942c-87c632113a04.jpg
https://user-images.githubusercontent.com/83260375/119986701-786f7e00-bfc4-11eb-87e8-82afea8106bf.jpg
https://user-images.githubusercontent.com/83260375/119986654-68579e80-bfc4-11eb-9725-fc2e1edc452c.jpg
https://user-images.githubusercontent.com/83260375/119986683-70afd980-bfc4-11eb-9876-d904cbcdd0e5.jpg
 is described by the Utreexo team (and another paper
https://eprint.iacr.org/2021/340; someone already provided u the link to Utreexo paper) as Pareto Distribution following the power law with alpha?
https://mobile.twitter.com/ArafatShymaa/status/1399963923412049921

8-Or in trying/ analyzing the performance at least of non famous although I believe could be more suitable data structures for the Merkle Tree problem; Buffer-Trees, cache oblivious Van Emde Boas layout(in Utreexo they do store it physically in memory as a sequential array, only with different ordering), priority queues, finger tree,...
(The objective is to minimize the proof size, ie siblings along the path from the requested leaf to the root, this is achieved by minimizing the tree height or/and by making the requested group of leaves adjacent to have a lot of siblings in common. That's why I find resemblance with cache oblivious, aside from that Utreexo project is doing real caching and I think researching now on predicting what to cache
https://mobile.twitter.com/ArafatShymaa/status/1402326526952095747
.....
There's a lot more, but that what I can remember at the moment.
.
9- Here's layer-2 u were asking about, I didn't get into it too much but maybe interests u the math in the sampling & the rest of stuff
https://web.stanford.edu/class/ee374/
https://ethereum.org/en/developers/docs/layer-2-scaling/
https://vitalik.ca/general/2021/01/05/rollup.html
https://m.youtube.com/watch?v=BhMoJM1kuO8&feature=youtu.be
.
10-Manipulation attacks  r really interesting with a lot of research, but not exactly mathematical
https://m.facebook.com/story.php?story_fbid=1386287771725667&id=100010333725264
...
& There is really much more areas here more than u could imagine

The idea of POB proof of Burn
https://youtu.be/Q5L8-GJVmZw
I used/needed to know about it in analyzing UTXOs, & Transactions in general, since the resulting UTXOs live for infinity; I think it also involves cryptography since 2 of the authors main research area is  security & cryptography
https://mobile.twitter.com/sol3gga
https://mobile.twitter.com/dionyziz
https://mobile.twitter.com/gtklocker

no it doesnt
the PDF clearly states that UTREEXO wallets wont even store the blockchain(thus not full node). but will need bridgenodes to pass it shrunken down data in the form of 'forrests' of merkle trees.. to then allow the UTREEXO wallets to have a fast and low system resource intensive experience..

utreexo wallets are not going to be full nodes. but would like legacy/native full nodes to have extra code to translate full data into forrest merkles. to then send/pass this lesser data to the utreexo (lite)wallets
..
anyway. research topics of bitcoin.
network topology
from asics(no blockdata just hash calculating)
stratums(pools collate tx in blocks, makes hash for asics. check asics solution, sends solved blocks to fullnodes)
fullnodes(receive, validate and then pass on full data)
litewallets(leachers that get data in differing volumes but dont all store/relay that data out)

learning these true network layers helps understand the whole dynamics of the decentralisation efforts. aswell as understanding the power play within the network of how each layer influencers each other in regards to consensus changes. [the equilibrium between stratum full nodes and merchant full nodes]

I personally like the progress that Utreexo (a method of using Merkle trees to represent the UTXO set) is making, because it will among other things lower the amount of RAM you need to run a full node, specifically during the initial block download. It generates slightly more network traffic though, but that shouldn't be a problem for connections that are already ingesting several hundred GB of data anyway. The whitepaper is at https://eprint.iacr.org/2019/611 along with a short progress tracker on Bitcoin Optech.

Hi all, I would like to hear about research topics in Bitcoin. For instance, https://ieeexplore.ieee.org/document/7163021 breaks down to 3 parts: Network, Transactions, Consensus. There are some literatures which carefully studies Nakamoto's consensus from a careful mathematical argument, for instance https://eprint.iacr.org/2019/943.pdf

Obviously, there are IOHK research, Ethereum research for their own consensus and scaling, but I would like to work on Bitcoin. Hence I would like to ask for your opinions for some topics which really solve challenges in Bitcoin. I am not an expert in Crypto at all, in fact, I am learning now as I am very fascinated by Bitcoin, but I thought it would be more effective to learn with some mete problems in my mind. (My back ground is math with PhD, and have been publishing papers in graph theory and topology. I am mainly interested in layer 1, but open to stuff like lightning project.) If you could let me know, that would be amazing. Please let me know!