text:
What is the format of a Bitcoin block body?
To my understanding, the miners solve the nonce to get a valid block header based on the difficulty target. In the header, you have the Merkle root, which is generated from the transactions included in the block. Based on the documentation, the nodes validate the transactions. Does this mean the miner doesn't need to verify the transactions in the mempool?
I have been searching for examples of what a block submission looks like. I know blocks can be submitted via the RPC. Even though this won't be practical, however, say I was building a miner. Does anyone know what format is used to submit the block concretely? Are there any known practical implementations understandable by dummies? Looking for code or whatever.

Does this answer your question? What are the components of the raw block shown in this image?

These are two completely separate questions. Better edit it to be a single question and open a new question with the second paragraph.

does this mean the miner doesn't need to verify the transactions in the mempool ?

Miners must verify the transactions they include in a block, because if they don't, some invalid transaction may be included in the block. A block with an invalid transaction will not be accepted by the network, i.e. full nodes, which means that the miner wasted electricity and did not receive any reward.
Bitcoin block consists of:

block header

version
prev_block
merkle_root
timestamp
bits
nonce

transaction counter
transactions

Does this mean the miner doesn't need to verify the transactions in the mempool?

The actual entity doing the hashing doesn't have to verify anything as long as they have a block header to mine on. But first someone (generally the mining pool) would have to have built such block header, and for that they would have to have gathered transactions from the mempool and built the block and then took the merkle root of the transactions. In this process they would have validated the transactions included.

You are right, but I am also right since I mentioned a real possibility.


text:
Clarification on Ark pool transaction inputs
This is the definition of a pool transaction taken from https://arkpill.me/deep-dive:

Pool transactions are created by Ark service providers perpetually every 5 seconds, which are effectively blinded, footprint-minimal, rapid coinjoin rounds.
ASP funds the coinjoin with their own on-chain funds in exchange for vTXOs redemptions. Therefore, the coinjoin transaction that hits on-chain has only one or a few inputs provided by the ASP.
The pool transaction has three outputs: vTXOs output, connectors output, and ASP change. Service providers place vTXOs for the intended recipients to claim (under the vTXOs output) and connectors for senders to connect (under the connectors output) in their pools.

The doc says that all inputs of a pool tx are owned by the ASP. When Alice joins the ark by onboarding/lifting, how does this actually work if her on-chain funds are not used as inputs of the pool tx?
The most obvious explanation to me (I'm pretty sure it's not the right one though) is that Alice sent her funds to the ASP in a prior tx, but how could she be sure that the ASP will create the vtxos for her in the pool tx?

In Ark there is a process called lifting. When a user lift funds they take an onchain utxo (unspent transaction output) and getting an ark vtxo (virtual transaction output) in return.
To explain lifting it is crucial to understand what a vtxo is.
First of all, a vtxo is a specific type of bitcoin-transaction. We call it virtual because the transaction is supposed to never go on chain.
In Ark, a vtxo has a very specific design. The design allows the owner to spend the coins in the vtxo-unilaterally. However, there is some kind of an expiry date. After 4 weeks the vtxo expires and the Ark Service Provider is allowed to grab the funds.
Now we understand what a vtxo is. Creating a lifting protocol isn't that hard. Together, the user and ASP can create a virtual transaction that has a vtxo as an output. They also create a lifting transaction that can only be used to fund the virtual transaction.
At this point the transactions are created but aren't funded yet. The user has seen the transactions and knows that unilateral exit path exist. The user can safely sign and broadcast the transaction. The user has lifted their funds and has a vtxo that can be used.
However, it is not exactly like a vtxo yet. The ASP will only allow the user to spend the vtxo once the on-chain lifting transaction is confirmed. The ASP doesn't want to be the victim of a double-spend attack.
The double-spend attack is also exactly why the pool transaction must be fully funded by the ASP. If users would fund the pool transactions directly. An evil user could double-spend and prevent the pool-transaction from making it on chain.

so lifting transactions are the pool transactions ? and they need to be signed by the users joining the Ark?

No, they are two different kind of transactions.
Both go on chain though

To summarize, you can lift your own on-chain utxo directly into a vtxo and then you can use this vtxo just like any other vtxo that was the result of an Ark round: you can spend it in an Ark round in return for other vtxos

The ASP will only allow the user to spend the vtxo once the on-chain lifting transaction is confirmed.

How is this enforced?

Spending a vtxo is like an atomic swap between an old and a new vtxo.
The ASP can just decide to not provide the new vtxo

AFAIU, the lifting tx cannot be broadcasted before the pool tx where the vtxo is created because the pool tx's connector output is used as input of the lifting one.
Therefore, the pool tx must be broadcasted first in this scenario. And once a pool tx is broadcasted, vtxos are created and can be redeemed at any time, so how could the ASP enforce what you said? Did I misunderstand something?

The order you described isn't correct.
The pool tx and vtxo's are created first. Then, the pool transaction  is broadcasted.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
How to force node to use tor connections, onlynet=onion already
I've followed all these steps
How can I setup Bitcoin to be anonymous with Tor?
I've added onlynet line in my conf file, but all my peers come with ipv4 connection. When I run getnetworkinfo I get ipv4, ipv6 and onion all as reachable. Only unreachable is i2p. How do I force my node to use tor and not ipv4 and ipv6.
UPDATE
After deleting peers.dat file, ipv4 and ipv6 would become unreachable under getnetworkinfo. However after some time, not sure if caused by reboot or smth else, it would turn back to reachable and in peerinfo half of the peers would be through ipv4.
Conf file
datadir=/mnt/blockchain/.bitcoin/
txindex=1
server=1
daemon=1
rpcport=8332
rpcbind=0.0.0.0
rpcallowip=127.0.0.1
rpcallowip=10.0.0.0/8
rpcallowip=172.0.0.0/8
rpcallowip=192.0.0.0/8
zmqpubrawblock=tcp://0.0.0.0:28332
zmqpubrawtx=tcp://0.0.0.0:28333
zmqpubhashblock=tcp://0.0.0.0:28334
whitelist=127.0.0.1
rpcauth=bitcoin:#########hashed_out_for_security_reasons##########
proxy=127.0.0.1:9050
listen=1
bind=127.0.0.1
onlynet=onion

Can you paste your exact bitcoin.conf file into your question?

Hey Pieter, thanks for quick reply. I think I solved it tho. I've tried lots of things. Seems like deleting peers.dat file helped. Currently have 8 peers, all onion.https://media.tenor.com/d-51Xsn5N3AAAAAd/oignon-onion.gif

onlynet=... only controls outbound connections. Are you just seeing inbound connections through IPv4 and IPv6?

At the moment I have 9 onion connections, from which 8 are "outbound full relay" and 1 is "block relay only", and 1 ipv4 connection that is "block relay only". I'm not sure if that describes inbound and outbound connections. If not can you please point me to how to check that. Thanks

Can you paste the output of getpeerinfo in your answer?

Actually, "block relay only" implies it's outbound, so no need.

Try deleting anchors.dat ?

So full relay is both in and out, and block relay is outbound? Is there any benefit from security perspective to have all your connections through tor, or it is important to have just outbound through tor? Do not have {anchors.dat} in my .bitcoin.

All connections are bidirectional in terms of communication. "inbound" and "outbound" just refers to which node initiated the connection. From a security perspective, it's much better to have a mix of Tor and non-Tor connections, especially for outbound. Tor-only is mostly something you'd want for privacy reasons.

Thanks for explaining. So how would I make all the connections over Tor, if that is possible? I don't seem to have that anchors file.

Perhaps can you still provide the output of getpeerinfo?

https://pastebin.com/srmZ6M6w      Seems all of them are onion now. Haven't done anything.

https://pastebin.com/2a8p5gCx     This is getnetworkinfo         Seems ipv4 and ipv6 are unreachable again.

There have been recently some improvements to make sure onlynet is respected, most importantly https://github.com/bitcoin/bitcoin/pull/22834 which has been part of bitcoin core since v23.1.
It has been reported before that older versions of Bitcoin Core would in some situations not respect -onlynet=onion, see e.g. the discussion in https://github.com/bitcoin/bitcoin/issues/22647.
Another issue, that sometimes during initial peer bootstrap (empty peers.dat) DNS seeds would be queried violating the -onlynet option, was fixed in https://github.com/bitcoin/bitcoin/pull/25678 (which will be contained in v 24.x).

So it would help to know which version of Bitcoin core you are using?

So, after upgrading to 23, was using 22, all my connections are now onion. I've also noticed there is 14 connections now in comparison to 10 in previous versions and "cjdns" as new type. Gonna explore that more. Thanks to Pieter for explaining stuff and Lightlike for upgrade idea. I'm not sure how to close this request or if it needs closing. Seems I can't cast vote yet, however thanks for your time guys.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Bitcoin mining process-the leading zeros before the hash-how is the mining puzzle solved exactly?
Can someone please explain:
In Bitcoin proof of work, mining is done to create and validate new blocks. Who becomes the sole block producer is subject to winning a "mining puzzle".
As I understand, the difficulty is that the solution of this puzzle must have a specific number of leading zeros in the resulting hash.
My questions are:
1) must the hashing result have X number of leading zeros, or is the constraint more like "less or equal X number of leading zeros"?
2) If the mining puzzle's solution has a hash as a result, what is then the input parameters for doing the hashing? What are the miners exactly hashing, what are all the input factors?  As i understand, input factors are e.g. the Nonce, previous Block's hash, etc...
3) I understand a hash function is only one way function. You have an Input which produces a unique hash. This means that if multiple different parties are hashing the same input then their hash results must be identical, right?
Given this definition, I really do not understand how the situation of orphan blocks in Bitcoin can happen? Because orphans happen for example when 2 miners at the same time solve the mining puzzle. But both are solving the exact same mining puzzle right? This means, they both have dealt with the same difficulty level of the puzzle and arrived at the same number of leading zeros for their hash, right?
How is the blockchain then distinguishing between those 2 miners, who has "put more work into the mining" if they have solved the same thing? On which parameters is the network looking to determine which of the two miners should get the reward?
Thanks

I understand a hash function is only one way function. You have an Input which produces a unique hash. This means that if multiple different parties are hashing the same input then their hash results must be identical, right?

Multiple parties will never be hashing the same information. Either the parties are coordinating or they're not. If they're coordinating, they'll carefully avoid doing the same work because to do otherwise is foolish. If they're not coordinating, they can't possibly be doing the same work. I'm trying to find a hash that pays me money. If you're not coordinating with me, why would you also be doing that?

Given this definition, I really do not understand how the situation of orphan blocks in Bitcoin can happen? Because orphans happen for example when 2 miners at the same time solve the mining puzzle. But both are solving the exact same mining puzzle right? This means, they both have dealt with the same difficulty level of the puzzle and arrived at the same number of leading zeros for their hash, right?

Probably. But they will produce different blocks since they're either trying to mine to different destination addresses or carefully coordinating to avoid duplication fo work.

How is the blockchain then distinguishing between those 2 miners, who has "put more work into the mining" if they have solved the same thing? On which parameters is the network looking to determine which of the two miners should get the reward?

When the next block is found, whichever block the miner who found that block built on top of will be in a longer chain than the other, causing everyone to switch over to the longer chain. To get to keep your mining reward, the block you found must stay in the longest chain. To have the highest odds of this, you always try to mine to extend the chain that is already the longest. So any ties are quickly broken -- as soon as a block on top of one of the longest chains currently existing is found and no other block is found at around that same time, nearly everyone will be building on top of that block.


text:
Is Bitcoin PoW actually SHA256 + Merkle generation? Or have I misunderstood coinbase/append?
Miners can mutate nonce (32 bits) + time (mutates once a second). This allows for 232 (~4 billion) hashes per second. That's not enough anymore for our ASICs as they perform in the TH/s now rather than GH/s. So we allowed miners to mutate the coinbase transaction, but this requires us to generate a new Merkle tree. This means that a miner needs to generate a new Merkle tree every 232 hashes. at 1 TH/s The miner must generate a new Merkle tree 250 times per second.
TLDR: Is Bitcoin PoW actually SHA256 + Merkle tree generation? And not pure SHA256?
If I'm correct in asserting that Bitcoin PoW is SHA256 + Merkle tree, does this slow the commoditization of ASICs and therefore slow decentralization, as ASICs now must be more complex than if they did with just SHA256 + nonce mutations?

You are correct that effectively Bitcoin PoW involves computing the Merkle root every now and then in addition to the hash grinding.
However, this is negligable. Even ignoring nTime rolling, the Merkke root computation is just a dozen or so hashes every 232. It's so little because not the entire Merkle tree needs recomputation; just the coinbase transaction is modified, along with n Merkle nodes above it (assuming up to 2n transactions).
As far as I know, the burden of Merkle root computation is so low that it is generally done in the miner controller rather than in the ASIC itself.

Thank you for your answer Pieter,
I understand that it does not require much compute. But my criticism is towards the added complexity of doing two things to get a new hash, as opposed to one, just using the nonce (and extending it to 64bits).
It seems to me that there is accidental complexity we can shave off here. We can reduce the complexity of the miners, pool operators, RPC interface, stratum.
Why have we chosen to increase the complexity of the software, rather than increase the nonce to 64bits?
Thank you for your contributions to bitcoin, I'm a huge fan of yours.

@ascendzor Changing the header format like that requires a hard-fork.

Yes, things would have been slightly simpler if the nonce field was 64 bits in size. As @CodesInChaos points out, this would require a hard fork, and because of that it'll probably never happen. All infrastructure relies on 32-bit nonces, and already includes the complexity of grinding Merkle trees. Convincing the whole world to change that, and the risks for forks while doing so, just isn't worth the gain.


text:
Could Taproot create larger security risks or even hinder future protocol adjustments re Quantum threats?
I am quoting here a user named "blk014" who responded to Pieter's Taproot tweets from 24JAN. I find this user's comments very interesting and would like to ask a developer expert how much of a security issue this "Schnorr's linearity" can be in the future process of finding quantum resistant solutions? And how possibly mitigate or prevent this risks in advance?

While both, ECDSA as well as Schnorr signatures are unsafe vs quantum
  computers, Taproot exploits Schnorr's linearity for which no
  quantum-safe replacement is known today. While making Bitcoin
  quantum-safe is already hard, making Bitcoin-Taproot quantum-safe will
  be a nightmare.
Enabling taproot now should be supported by a rational risk
  assessment. The outcome depends on your choice of the following
  parameters: (1) time until QCs break ECC (2) time until QC-safe
  taproot replacement developed+vetted (3) time to upgrade network, ...
what to do with ignorant/dead user that wont upgrade (Satoshi, address
  re-users) whose UTXOs become vulnerable by (1)
Given these risks, an upgrade to tap root is not very risk averse,
  which is the appropriate approach in developing safety-critical
  systems, and which was followed so far.
It's not just a matter of priorities, because without taproot
  achieving QC-safety is hard, but a path is at least on the horizon
  (cf. current NIST standardization efforts). After taproot, the problem
  is completely open.
On a final note: I'm not personally against activating taproot (it's
  very elegant), but I would also like to have consensus on a rational
  assessment of the risks that are being accepted here [with Taproot].

The user goes on to describe 3 step approach to a solution, where without Taproot only 2 steps would be needed. But with Taproot a much more difficult 3rd step comes into play:

I think there are 3 major QC problems to solve: (1) find an
  appropriate post-quantum DSA (2) solve the transition problem before
  QCs become large, (3) find a linear PQ-DSA. Items (1)-(2) have to be
  solved in any case, as long as you believe QCs will become large
  eventually.
And Goolge's recent Quantum Supremacy experiment is significant
  evidence that we are on that track. With taproot activated, we also
  need to solve (3). If we solve (1) and (3) together, this may take too
  long to achieve (2). That's the risk we take by activating taproot
  now.
it might push the the time to make Bitcoin quantum-secure from 5-10 to
  10-20 years, as much more research is needed. Risk assessment should
  conclude whether we have the time and want to take the risk.

Thanks for your expert views on this issue.

I have a hard time answering this because it contains so many misconceptions. DSA is inherently vulnerable to quantum computers, linearity is not the problem, "linear DSA" makes no sense to me - DSA doesn't have the linearity property, and a solution for all these problems exists in the form of post-quantum zero-knowledge proofs ... they're just really big for now, so not really usable.

thx Pieter! this sounds very confident from you! but since I have literally no clue, the other user's arguments sounded equally confident. But nice to hear there  are solutions in your mind. i did not know that zk proofs can be used for QC resistancy. If this is the case, maybe another zk proof concept called "ZK-Starks" could also be of help. Or a concept called "trustless recursive zk-proofs" developed by the Zcash team, its called "HALO". They claim "small proof sizes". Maybe interesting when your main problem is "big for now".  Good luck tackling QC!!

There are dozens of zero-knowledge proof systems being developed (the field has really exploded the past few years), and some of them (including zkSTARKs) can be made PQC. However, all the ones that can have very large proof sizes. The compact ones (like Bulletproofs, Halo, ...) cannot be PQC.

And I'm not sure confidence is the right word. I don't think we have PQC solutions for Bitcoin with acceptable tradeoffs right now, but QC that can break cryptography are also not a real threat (it's unclear if the engineering challenges can be overcome at all, and if they do, we'll likely see them coming decades in advance).

Let me start by addressing the misconceptions in the posts you're quoting.
DSA (and Schnorr) are inherently based on the discrete logarithm problem, which is vulnerable to (sufficiently powerful) quantum computers. As a result, there is no such thing as a "post-quantum DSA". DSA also doesn't have Schnorr's linearity property - if "linear DSA" means anything it would just be a weird way to refer to Schnorr (DSA is a modification of Schnorr that was intended to circumvent his patent). There do exist digital signature schemes that are (plausibly) post-quantum secure, but they are not based on the discrete logarithm problem, and they're generally very large.
Another misconception is that Taproot relies on Schnorr's linearity. It does not - Taproot could be built using ECDSA as well; it would just be much less useful. The linearity property is needed for simple key aggregation, so that a single key can represent the consent of multiple parties.
So, does starting to rely on Schnorr's linearity make it harder to migrate to PQC signatures?
Linearity is just used as a tool to increase the privacy (and efficiency) of Bitcoin's scripting system without changing much. However, linear signatures aren't the only way those abstract goals can be reached. A PQC replacement wouldn't try to shoehorn the properties of Schnorr in another signature scheme - it'd just be built for private multisignatures (or more) in the first place. If such a scheme cannot be found, we'd just lose those privacy advantages (efficiency gains would generally not translate anyway), and not be worse off than if we never adopted Schnorr/Taproot in the first place.
There are obstacles though to doing so that are unrelated to Schnorr/Taproot. Probably the biggest one is how key derivation works today. PCQ signature schemes don't have anything similar to BIP32, and it's nontrivial to carry over much of the infrastructure that exists today around key generation (xpubs, derivation paths, PSBT, hardware wallets, ...). I suspect this will be a far harder problem to address than the constructions Taproot permits on a script-by-script basis.
Ideally, how would all these features carry over to PQC systems?
Before answering that, let me point out that in many ways, Schnorr/Taproot are just one step towards hiding a few things from scripts. It only brings advantages when outputs can be spent by a single party or cooperatively by many. In an ideal world, they'd be replaced with a zero-knowledge proof that whatever properties the receiver of a coin wanted to encumber their storage with, was satisfied when spending it, without revealing anything else.
Once you look at the problem this way, it becomes clear that what we need is in fact a zero-knowledge proof, not a signature. A signature is restricted to a single party proving something to a single verifier, who knows what they want. This isn't what we need: generally multiple parties are involved, and the verifiers (full nodes that enforce consensus rules) do not actually care about what policy was fulfilled - only that it matches the policy set by the coin's owner.
Zero-knowledge proof systems exist that could do this (to smaller or larger extent) today, though they come with performance/size tradeoffs or security assumptions that may be hard for the ecosystem to adopt right now. However, this domain of science has progressed enormously the past few years, and I expect it will keep doing so.
Back to PQC, some of these zero-knowledge proof schemes can be made PQC. Like PQC signature schemes, they're generally large (even more so than signatures), but improvements are being made. For QC, we're speaking about events that are likely decades away (or won't happen at all), and a lot can happen in such amounts of time.

This particular response is approximately tripe. Building on Pieter Wuille's comment.

find an appropriate post-quantum DSA

and

it might push the the time to make Bitcoin quantum-secure from 5-10 to 10-20 years, as much more research is needed.

We really know what to do to make Bitcoin Quantum safe, there's been methods for doing hash based cryptography in varying forms since 1979, which predates even Schnorr in 1991. Adding a new signature type to Bitcoin can be done with a soft fork, even though the specifics of how this would work (they would likely be a merkle tree of public keys).
I personally wrote a patch for adding OP_LAMPORTVERIFY as a project while bored on a plane in 2015, other than coming up with something sensible for the formats and desperately trying to convince people not to re-use addresses (for real this time!), it's engineering that can be done on a short international flight.

With taproot activated, we also need to solve (3). If we solve (1) and (3) together, this may take too long to achieve (2). That's the risk we take by activating taproot now.

The two are basically orthogonal, there's no difference between migrating between outputs stored with taproot and those using raw ECDSA. The existence of taproot doesn't make this any more or less difficult functionally.
If any quantum computing was a significant threat (ie, wasn't just theoretical or slower than classical computing), we would have a lot more to worry about than just Bitcoin regardless.


text:
51% attack - apparently very easy? refering to CZ's "rollback btc chain" - How to make sure such corruptible scenario can never happen so easily?
I was shocked to see binance CZ comment to literally "roll back" the bitcoin chain by just "calling" in some favors from "friendly" Asian miners .
This ONE person could effectively do it???  I mean are we all in a bubble, in some kind of utopia then, to think that the chain's decentralization makes it "bulletproof" and resistant to collusion by miners?
(1) This is fundamental question:  How are our highly regarded and brilliant Devs of bitcoin explaining such situation where only a handful of persons´ interests could essentially be enough to do a majority 51% attack?
(2) And secondly, are there active debates about how to mitigate such situation in the future, what technical aspects implemented in the btc chain (or to be implemented) could be helpful?
This huge mining farms are essentially very disturbing. it is like  in proof of stake , where the "richest" has most power. And in the PoW mining case , its similiar just that the "biggest hardware" has most power.
we have to try somehow to eliminate such easily corruptible scenarios, right?
in todays digital world, there are plenty of collusion examples of even more than 1000 different persons involved.
Handful of colluding majority miners would be a piece of cake, right?
Thank you for explaining to me this issue . I hope sincerely that this is taken up by our awesome dev community, or maybe I am just misunderstanding everything.

Since this is in Hot Network Questions, can someone link an article or something for background context on the comment that sparked this?  I know about bitcoin and how a blockchain works, but I don't use it or follow news about it.  edit: found https://ethereumworldnews.com/bitcoin-holds-strong-binance-hack-cz-ensures-blockchain-rollback-happen/ myself, looks like a decent summary.

Disclaimer: I believe this question may be primarily opinion-based and not very appropriate for this site, but there are a number of technical misunderstandings that can be clarified along with it, so I'll give it a shot.
There are many nuances involved here, and I fear that a large part of them didn't reach as much of an audience as the exchange announcing "we decided not to do it". I believe this was a poor choice of words, as the decision they made wasn't whether or not to roll back the chain; only whether or not to offer a bounty for doing so. I personally believe it would be very unlikely that the alternative would have actually resulted in a deep rollback.
Let's analyze the situation from a number of perspectives.
If we only consider miner's actions, is it theoretically possible for them to roll back the chain? Yes. If you're wondering if there is a small number of mining company CEOs in the world, which, if all together convinced, with complete disregard for their own financial interests, the health of the network, or legal repercussions, could decide to roll back the chain to a point before the theft, the answer is yes. This is the reason why people care about mining decentralization, and permissionlessness of entering the mining market. However, unless it's not just a majority of the hash rate that is on board with this, but actually close to all the network's hashrate (a substantially harder problem, as there are many small miners in addition to the few big ones), this would likely have take days or even weeks (if it's close to 50%), a time during which many things can happen - including a public outcry and a UASF-style fork to prevent the rollback from being accepted by the ecosystem. If considered over an even bigger timescale, events like this may even incentivize people and businesses to become miners, in order to reduce the influence of large pools.
Assuming miners maximize short-term profit, would it be financially interesting to rollback? No. Even if we assume that everyone in the network is acting selfishly to try to maximize their own (short-term) profit, and ignores the protocol rules and the possible repercussions from doing so, it is not. By the time the information about the theft became known, the transaction was already confirmed several hours before. During those hours, miners had created dozens of blocks, which together earned several hundred BTC in subsidy and fees. The exchange would need to offer at least that amount to the affected miners, to compensate them for the income they'd lose from rolling back those blocks, before it would even be worth discussing. Let's call this the rollback cost R. As the stolen amount was in the thousands (let's call this S), that seems like a reasonable option. However, nothing prevents the thief from using (part of) the stolen funds to do the same. Every BTC offered by the exchange above R can be countered by an equivalent amount offered by the thief. And then it becomes clear that the thief has the upper hand: the exchange can at most gain S-R by a rollback, but the thief stands to gain S by not having a rollback. A theoretical possibility is a bidding war between the exchange and the thief, where both increase the amount paid to make miners act in their favor. The end game of this is that the exchange offers S-R, the thief offers slightly more and keeps R, and miners are paid S-R by the thief, and no rollback happens.
What would happen in the real world? Theoretical models are interesting to study, but in reality many more practical considerations exist. I believe those too are generally in favor of no rollback:

Coordination between distrusting miners (especially close 100% hashrate) is hard, and would take time. The more time it takes, the less advantageous a rollback becomes (see the above point), and the more damage would be done to the ecosystem (see the next point).
An hours-long (in the very best case) or a weeks-long (in the worst case) rollback would monumentally hurt the ecosystem, and likely undermine the public's confidence in the system to the extent that it would severely reduce the profitability of many parties involved (including miners and the exchange itself!).
Even ignoring all the above, miners may not be willing to take a bribe to rollback because of legal reasons if they're publicly known (which they mostly currently are). They may equally not want to take stolen money as a bribe, so this cuts in both directions. This point becomes weaker if the mining ecosystem is more decentralized, but that would also make coordination harder.
As I pointed out above, in the extreme scenario where such a rollback is actually happening, the public has time to react. If a sufficiently large group of economically relevant parties in the network refuse to accept the rollback, miners have no choice but to go along with that. This is a last-resort option, and likely damaging to the ecosystem on its own, but it is an option.

So to summarize: in theory there are absolutely ways in which a rollback could happen, and it's good to be aware of those. In reality, the security of the system relies on economic incentives already which are nontrivial to analyze. It however seems very unlikely that in the case of a theft a deep rollback is a reasonable outcome.

You might want to elaborate on your short term profit formula to consider that R depends not just on the existing blocks but on the share of honest hashrate. E.g. In the simplified theoretical model R is infinite after confirmation with >50% hashrate honest. At just under 50% honest it's finite but much larger than the number of blocks that need to be replaced. Only at 0% honest does R equal just the cost of blocks that need to be replaced. Coordination challenges alone assure that some hashrate would behave honestly.

@pieter-wuille thanks great! but one question remains please: How do people intend to make the btc infrastructure MORE decentralized? And i dont agree with your opinion that "coordination" is "hard" to achieve. i think its easily achieved IF they have (for whatever reason) ONE and the same goal...

(adding some color) Some discussion I saw suggested that people promoting this believed they only needed to achieve >50% hashpower, which caused them to overestimate the feasibility. Reorging with only slightly over 50% would take weeks-- even months, creating massive disruption if successful, and virtually guaranteeing an effective public initiative to block it.  In such an event once the rollback began, users would advise each other to use the 'invalidateblock' debugging command to make their nodes ignore it. [I also had multiple users ask me to review patches ahead of the fork that would have blocked it, I told them I thought they were over-reacting and that this was a nothing burger. :)-- but a patch would only be needed before a fork existed, and clearly people were ready to start responding to this only on the basis of twitter chatter]

There a are a few things to take into account when we consider the probabilities of a rollback attack (a posteriori reorg destroying net value) to be successful:

If the reorg is shallower than 100 blocks (COINBASE_MATURITY), the attacker can minimize the amount of direct victims. But if we are talking about a deeper one, not only the payments he wants to revert may have been spent, mixed with additional inputs and all those coins owned by other innocent people, this would also apply to coinbases earned by honest miners. The longer it takes to perform the reorg, the higher the amount of victims and their value at stake.
The attack may take a long time. The fraction of miners participating (via direct control or bribes) and the amount of blocks to revert will determine how long.
For example, to revert 6 blocks (1 hour worth of confirmations) before coinbases start maturing, the attacker will need to get immediate control over 51.5% of the hashing power. If he falls short of that percentage or requires more time to convince some of the miners, it will take him over 33 hours and reverting more than 100 blocks in total, so rewards from the first blocks may have been mixed and spent already, tainting UTXOs worth much more.

If the attack uses existing mining capacity, during the time it takes to reorg the chain, the capacity of the longest chain will be reduced to less than half (slower block production). Every transaction valuable enough to be processed will need to adjust its fees, at least up to the marginal utility defined by the least valuable transactions included in the less frequent blocks. These transactions were paying a lower fee before, as it was enough to ensure confirmation. You can expect this to have a positive impact on total revenue for miners. Higher rewards on the honest chain will put additional pressure on miners carrying the attack.

A significant reorg does not only affect direct victims, every bitcoin holder would be affected due to a diminished confidence in the system, a reduction in Bitcoin utility and a drop in the price of the coins as a consequence.
PoW is a trust-minimized market signal enabling us to scale social consensus. But,  if somebody builds a heavier chain with a lower value, breaking PoW trust-minimization, users can choose not to follow it and make a UASF, invalidating the reorg:
$ bitcoin-cli invalidateblock "blockhash"
Coins in each chain are only as valuable as their chances to become part of the winning one. Miners coordination to carry the attack, higher fees in the longer/honest chain and UASF risk during the reorg are all factors against reorg-coins having as much value as those in the honest chain. This makes even more challenging to use them to bribe miners.

How can we make reorgs even more difficult? @LukeDashjr provided the first two of these ideas, that would help us achieve stronger immutability:

If users set individual checkpoints in their nodes, this would discourage reorg attempts and split the chain if one happens, leaving it for market to discover the value of each chain when PoW consensus assumptions break down.
Use pool swapping rule introduced by BFGMiner to prevent miners from wasting work on stale blocks. If one pool implements a reorg policy (even if it is trying to earn bribes), miners will refuse to ditch previously validated blocks and switch to a pool working on the newest block.
@TheBlueMatt's BetterHash mining protocol would have a similar effect, making practically impossible for mining pools to enforce an ordering of transactions, hence removing their ability to censor some of them.
The more independent miners, the more difficult it will be for anybody to coordinate them and try to 51% attack the network with existing mining capacity. Currently over 40% and growing.

But not every reorg is an attack destroying net value. We have examples when the blockchain was reorged, discarding some PoW as worthless, because it was economically rational to do so and avoid a greater damage:

On 15 Aug 2010, output-value-overflow bug created 184.5 billion BTC. Around 5 hours after the incident (30 blocks), a fix was released: client 0.3.10. It is believed that 51 blocks were reorged in total (>70% of the hashing power mined the alternative chain during ~12 hours). 2250 BTC in rewards were lost.
On 11 Mar 2013, migration from Berkeley DB to LevelDB caused a 6 hours chainsplit at block 225430. The 0.8.0 chain reached a maximum lead of 13 blocks over 0.7.2 at block 225451, but it was abandoned and reorged at block 225454. 600 BTC in rewards were lost.

I want to add a little bit to the coordination problem that @PiererWuille mentioned.
Not only does the probabilistic success of a rollback depend on the ability of miners and affected parties to coordinate, it also requires that individual miners must trust one another to participate in the rollback.
Consider this: If I had a significant portion of the hashpower, and I wanted my competitors to waste their resources mining a chain that will not end up being accepted, then why wouldn’t I just pretend that I was going to mine a rollback chain, but then actually keep working on the already-established chain? If the parties invested in a rollback were counting on my hashpower to succeed in their plan, then by not participating in the rollback I would guarantee its failure, and increase my profits at the same time (since less hashpower would be working on the already-accepted chain).
So coordination is tough beyond just actually contacting and coordinating with the other parties involved. The safest bet continues to be mining at the tip of the most-work chain.

I don't follow, how would you pretend to be working on the rollback chain? Are you imagining they trust your word? Or are you imagine some way of forging proof of work?

@DavidSchwartz hmm I suppose the colluding miners could share partial work with each other as proof, but I think the issue still remains in a weaker form. Over short time periods (and you want to act quickly, if attempting a rollback) it is hard to make someone prove they are mining with as much hashpower as they say they are. What if they just have bad luck? Or what if they don’t actually commit their hashpower? Or they commit less than they agreed to? Over longer periods, it becomes more obvious if someone is faking it.

It's really not hard at all. Literally, this is a completely solved problem. It's only difficult for very small amounts of hash power, which doesn't matter. With large amounts of hash power, you can get very, very highly accurate measurements of amount of hash power and what is being hashed in just a few seconds with absolutely no difficulty whatsoever.

@DavidSchwartz I think the problem still remains, consider the standoff that would occur: "who is going to be the first one to switch hashpower to the rollback chain?" Even you lie about your intention to mine it, your competitors won't realize that until some amount of time has passed, and by then they will have wasted resources mining, and setting up their backend to make the switch. I agree it is a small consideration though.

I also think the game theory for a standard mining pool is slightly different, because if another miner in your roll-back pool drops out, it might affect your profit in entirety, whereas in a standard pool it would not. So even an accurate ~real-time measurement of hashpower would not alleviate the risk of another miner switching off the roll-back chain at some point in the future. Doing so might mean the miner that switched also takes a loss, but only onchain-- its still possible that someone (eg the hacker) would make an off-chain payment (bribe) to stop the rollback.

The first one to switch hash power to the rollback chain will be one paid by whoever wants the rollback. Sure, a miner could switch off the roll-back chain at some point in the future, but presumably they're being paid enough (in some way) to make this a losing proposition for them unless they bring the rollback effort to below 50%. It's certainly high risk for everyone involved, but that includes the miners not participating in the rollback!

From a technical perspective, how would a bounty be "fairly" divided and paid out? For example, say there are 4 miners each with 15% of global hash power and they all wanted to do the rollback; and the exchange wants to pay a bounty of 3000 BTC as compensation for the rollback. If the exchange just published a transaction that pays 3000 BTC in fees using the same UTXOs as the "theft" tx, then the first miner to find a block that incorporates that tx would get the entire 3000 BTC, leaving nothing for the other 3.

@Elliot Lots of ways. For example, they could publish a transaction splitting the 3000 BTC into a number of outputs and then dribble out the keys to each of those outputs to the miners as needed.

--Re-reading the question, and realize I didn't answer the question :(. Instead, I have written below what Binance should have done!
Reorg sounded like as if BTC code would be permanently changed for future. I'm presenting below a suggestion in which Miners would still decide to work an alternate chain, not because of code change, but for a crumb of incentives available on that "possible" alternate chain.
Exchange whose coins were stolen will need to change its intent from recovering the BTCs for themselves to letting BTCs go to miners as 7,000 BTCs benefits the Bitcoin Ecosystem, then Exchange can take the following actions.
Step 1:
Exchange creates a number of serial transactions “double-spending” all the stolen 7000 Bitcoins. Using Binance example, Binance creates say 280 transactions of 25 BTCs each. They are serial in nature.
Txn1: From stolen address to address1 6975 BTCs, Fee 25 BTC
Txn2: From address1 to address2 6950 BTC, fee 25 BTC
....
....
Txn280: From address279 to address address280 0 BTC, fee 25 BTC
Step2:
Miners can potentially earn 25 BTCs each for next 280 Blocks if they decide to go back and re-mine from the block before the theft! If some pools start doing it, then others will start joining as they will start realizing that it is in their economic interest to join this!
In this scheme, Exchange has given up on the 7000 BTCs but instead of thief, BTCs will be given to the Bitcoin Ecosystem. It should be done in few hours of the theft, so as to make it look feasible to miners.
Can Exchange get greedy and not give the all lost BTCs to miner? While it is possible, but remember that thief may play a similar game by giving away larger part of BTCs to the miners! Actually, thief may still play games by giving higher (say, 50BTC) fee each on quite a few transactions to keep miners working on the chain with his transaction of his stolen BTCs! So, ability of Exchange to confidently tell miners that they will get all 7000 BTCs will be required.
While this may disrupt the Bitcoin chain for some time, but if this gets done one or two times, incentives for large scale theft will reduce.

Hi Satoshi, if your answer should not be an answer you should be able to delete by a link below your answer.

Even if the exchange gives all 7k bitcoin to the miners, the thief will still be able to outbid them, due to the cost of enacting a roll-back. See Pieter's answer for an explanation.

Understand and agree on being potentially outbid! My write-up was more in the direction that if victims of all large theft do this, they force thieves to give away lot of stolen Bitcoins to miners and essentially reduce the incentive for the thieves to do large scale thefts!

Reverting a few blocks of advance is an event that is in the realm of the regular workings of the network, it would also be too fast to trigger and deploy the social resilience (aforementioned potential UASF) of the community.  The exchange could create transaction(s) that forges an ad-hoc majority coalition of miner, who if only replace the hacker transaction, but otherwise do not alter previously created blocks' payload were unlikely target of any lawsuits. Miner who would accept a counter bribe of the hacker however would be certainly sued. Whether such an incentivized re-org is feasible depends mostly on the preparedness of the exchange and the miner of acting on an offer within a very short time frame. This was clearly not the case with Binance recently. An incentivized re-org can be done and could happen as sophistication of actors using the network improves, arguing strongly as if something technically feasible can not possibly happen creates a false sense of finality and security by only a single confirmation.

You can't just replace ONLY the hacking transaction. What if the hackers spent the bitcoins to buy goods and services from different vendors? What is those vendors spent those bitcoins to their suppliers? If you alter the original transaction, none of the other transactions remain valid. So you are basically sacrificing the people who play by the rules in favor of those that put their bitcoins in centralized systems?

Your what-if scenario just highlights that relying on too few confirmations can become expensive. Re-orgs that drop transactions happen regularly with depth 1 and could happen with more blocks in case of a temporary network split. It is arrogant to assume one would know and correctly evaluate all considerations miner make if offered an incentive to participate in re-org.

Binance did not know they were hacked until several hours later. When they considered they could roll back the chain it was almost multiple hours which means ~100 blocks were already mined on top of the block that contained the 'hacking' transaction. By the time they garner support of the miners, another 100 blocks might have been mined. So you are saying, people should wait for 200 block verification?

I wrote that a re-org was not feasible as Binance considered it, in my OP.

Also note that in my answer I specifically only talk about deep reorgs; the situation is indeed very different if the needed reorg is only a few blocks deep.

Tamas is probably with respect to relatively short intervals, however, the reason people shouldn't trust those is because the network will naturally and unavoidably have them esp during internet instability events.  In terms of rollbacks the short time that gets in the way of coordinating the defense also hurts coordinating the defense.  I have generally recommended parties accepting high value no-recourse payments should be waiting tens of confirmations at a minimum, higher if no active monitoring and response is possible.


text:
NBitcoin, how to implement wallet restoration? How does it work?
at first sorry for my ignorance, I have little experience at bitcoin programming.
Im trying to implement a very simple wallet using NBitcoin library. I have done some work, but now Im stucked with wallet restoration function.
Lets say I have mnemonic private key, then I calculate its public key.
With public key am I able to track all transactions associated with this key? Even if I used multiple adresses? How its done(NBitcoin)? Any advice? Do I have to iterate throught whole blockchain and chceck signatures?
Thank you.

Is it an HD wallet?

No I want to keep it as simplest as posible for start.

With public key am I able to track all transactions associated with this key?

A public key has two corresponding addresses: Uncompressed and compressed. I suggest only generating compressed public keys for simplicity. The relevant methods are Compress and Decompress here.
So, yes.

Even if I used multiple adresses?

Multiple addresses: Yes, you should track all of them.

Do I have to iterate throughout whole blockchain and check the signatures?

You should use SPV: Download a block, verify it, keep the headers, skip to the next block. Also you should keep the transactions that are incoming/outgoing. Writing the current block height to the wallet file is a good idea, as after you launch the wallet for the second time, you'll only need to download blocks and scan for relevant transactions after that block height.

Thank you for the answer. What API would you recomend for a beginer(query a blockchain)? I read a NBitcoin c# book and couple of articles + Mastering bitcoin, but Im still confused about the restoration thing.

Restoring the wallet balance:
To restore the wallet balance from just the mnemonic passphrase, and determine your spendable UTXO's, you need to perform a UTXO-scan with a trusted local node which has validated the Blockchain.
With Bitcoind server, consider querying scantxoutset, which allows you to determine (per public key/address) which unspent outputs are controlled by your wallets.
Restoring the wallet history:
Restoring the receiving/spending history of the wallet will require you to build an "address-index" over all transaction, indexing the tx's associated with addresses you control.
Libbitcoin-Server already indexes all transactions by standard addresses per default, so you can query a standard Libbitcoin server to get the full-history for each address in your wallet.
Note: You do not need to validate signatures during wallet restoration, because your local bitcoin server has validated these. You don't need to build an SPV client if you are running your own validating full-node.

Furthermore, one will need the derivation path(s) to scan.


text:
where can i do a testnet Lightning Network Reverse Submarine Swap?
i have Testnet LN Node,
i have created a wallet,
i have send on-chain funds to that wallet
i have connected to several peers
i have created several channels, all of these are outgoing one side funded channels,
i want to do a reverse submarine swap, i mean Pay in LN and receive in BTC
LN --> BTC
this site offers the other way https://submarineswaps.org/
the purpose of these is to reverse a channel, or the half capacity of channel to be ready to receive LN payments.
of course i could just spend money, but the idea is to reverse the channel without loosing money (loosing is simulated as its in testnet)
thanks

As of now this is possible with Lightning Labs' Loop.  It's a non-custodial reverse submarine swap implementation.

You need to build LND with some special flags to enable the feature.
Loop is installed and runs separately as a daemon.

Once you have both running, you can simply "loop out" to send balance in your channel and receive Bitcoin onchain.

could it be done with an Eclairs Android mobile wallet channel?

@emi only for a channel between Eclair mobile wallet and an LND node that's running loopd. Then you can provide loop the channel id.

you can try sideshift.ai or zigzag.io the first one supports testnet but is still invoite only. For zigzag.io I think this service is only offered on mainnet.

This is a trusted service for now but it utilizes the Lightning Loop to do a reverse submarine swap https://reckless.capital/swap
At the moment of writing this website is on the Lightning Testnet. Soon this service will be available for use on Mainnet.
Also full disclosure I am the owner of the website.


text:
How does block synchronization work in Bitcoin Core today?
When a Bitcoin (full) node connects to the network, it has to synchronize its blockchain with its peers, i.e. learn about the best chain the network knows.
There are many aspects to this (learning about the headers, downloading blocks, validating the blocks, and deciding which one to mark as active), using several protocol messages (inv, getdata, getblocks, getheaders, headers, block, as well as compact blocks). This mechanism has evolved significantly over time.
How does Bitcoin Core do that today (i.e., as of version 26.0)?

Since the introduction of headers-first synchronization in Bitcoin Core 0.10, the blockchain data structure can be seen as having three components:

The block header tree: a tree data structure, with the genesis block as root, containing all headers for known forks of the chain. This tree structure is always connected, i.e., it is not possible to add a header to the tree unless its parent is already in the tree as well.
The block data: for each entry in the block header tree, we may or may not have the corresponding block data. Blocks can be received (and asked for) out of order, as long as the corresponding header exists in the header tree. There can be gaps, so it is not the case that a block can only be stored if the parent block is also stored. Of course, a block can only become the active chain tip if it's fully validated, which requires having seen all blocks before it too. Since the introduction of block file pruning in Bitcoin Core 0.11, it is also possible to delete blocks again after being validated; in this case, the corresponding headers are still kept in the tree.
The active chaintip (a reference to an entry in our block header tree) with its corresponding UTXO set (or chainstate), representing the fully-validated block that we currently consider active (this was introduced in Bitcoin 0.8).

Now to explain how synchronization happens, there are three separate processes that govern these data structures respectively:

Header synchronization: the process of requesting, receiving, and storing, headers that a peer has but we do not.
Block synchronization: the process of requesting, receiving, and storing, the full block data for headers we already have, which peers have but we do not.
Block activation: the full validation of blocks we have, and resulting changing of the active chain tip.

They all happen in parallel in practice, but it's easier to think of them as a sequence.
1. Headers synchronization
Requesting headers. The first step of synchronization is learning about headers which our peers have. This is primarily done by sending getheaders to each peer when we connect or accept a connection (by sending a locator which indicates which headers we already have), to which they'll respond with a headers message containing up to 2000 new headers. If the full 2000 headers are received, we'll send another getheaders to ask for more. This process continues until we have all headers the peer has to offer. When we're far behind, we only ask one peer (the headers sync peer) to minimize duplicating bandwidth usage, but once we get close to the current timestamp, all peers are asked.
Non-connecting headers. If headers arrive that don't connect to our existing headers tree (i.e., the parent of a received block isn't in our tree yet), we also send a getheaders in response to first learn about all the headers in between. Under no circumstances are headers processed when we don't know their parents yet. This doesn't mean they are rejected (as in: they are not marked permanently invalid); they are just ignored (as if they were never received at all). If all goes well, we'll receive them again after their missing parent headers have arrived, at which point they'll be processed normally.
Direct headers announcement. Since the introduction of the direct headers announcement mechanism (negotiated using the BIP130 sendheaders message) added in Bitcoin Core 0.12.0, peers can send us headers messages directly to announce a new active chain tip (see below). In case this mechanism is not used (either because the peer believes we are far behind, or because the peer doesn't support BIP130), they can also send us an inv message with just a block hash. This too will trigger us to send a getheaders in response to learn about any headers we miss, up to and including the hash that was just inved to us.
Header validation. When headers arrive, they are validated to the extent possible. This includes syntactic correctness, proof-of-work, difficulty adjustments, rules about timestamps (larger than the median of the past 11 blocks, not more than 2 hours in the future), and rules about version numbers (BIP34, BIP66, and BIP65 put requirements on the version number). If a header fails any of these, or descends from a block/header which is known to be invalid, it is ignored.
Header spam protection. While block headers are tiny (81 bytes in a header message), we do need to protect against storing tons of low-difficulty ones that an attacker might create. Proof-of-work inherently makes it very expensive to produce good headers in mass, but an attacker can construct a headers chain that forks off somewhere early in history (e.g. just after the genesis block) when the difficulty was low, without ever amounting to a significant amount of work. This could ultimately lead to memory issues for nodes if they would accept these headers into their block header tree. Historically, checkpoints were (among other things) used to guard against this, but since Bitcoin Core 24.0 another, more comprehensive, mechanism is used: header pre-synchronization. In short, it involves downloading the headers twice:

a first time to verify the headers form a chain with a significant amount of work (which means at least as much as the minimum chain work, a hardcoded constant, and at least as much work as the active chain tip, minus at most 1 day worth of work), without adding them to the block header tree
a second time where they're redownloaded and if they match what was sent in the first phase, they are added to the block header tree.

You can read more about this mechanism in this answer.
2. Block synchronization
Acceptable blocks. Once we know about the headers, we can download blocks. In general, blocks are only requested (and accepted) if they are part of a headers chain whose tip has at least as much cumulative work as the current active chain tip. Blocks that are not on our headers tree are never accepted (these would be orphan blocks), nor are blocks on forks whose header chain doesn't have a competitive amount of cumulative work.
Request mechanism. Blocks are requested using getdata messages, to which the peer responds with block messages (getdatas are also used for transaction fetching, but I am ignoring that here). To decide which peers these requests are sent to, we keep track of the inv and headers announcements peers have sent us, so we have an idea of what the last block header we have in common with them is. Requests start as soon as the best header we know a peer has exceeds the minimum chain work. We generally assume that peers who announce a block to us can also actually provide the corresponding block data (at least when they set the NODE_NETWORK service flag, or NODE_NETWORK_LIMITED for sufficiently recent blocks).
Scheduling of requests. The actual getdata requests are sent for missing blocks anywhere along the path from the genesis block to the headers tree tip with the highest accumulated work (which can be distinct from the active chain tip) among all block header tree entries which are not marked as permanently invalid. The requests are spread over all peers for which we know they have the respective block, in a round-robin fashion, with a limit of 16 requested-but-not-yet-received blocks per peer. We do not request blocks which are more than 1024 blocks ahead of the current active chain tip, to limit how out-of-order blocks can be received (this matters for block file pruning). As long as a block request is outstanding, the same block is not requested again from another peer to avoid duplicating bandwidth usage. If a peer stalls too long in responding to a block request, it is disconnected, and the request will be sent elsewhere.
Unrequested blocks. It is possible that a block is received without it being requested. Bitcoin Core will not send unrequested blocks, but some other P2P clients might. If this happens, we will process the header inside the block as if it was received through a headers message, and then roughly if we would want to request it after seeing the header, we also process the block directly. Otherwise, it is ignored (i.e., we act as if only the header was received).
Compact block announcements. In Bitcoin Core 0.13.0, support for BIP152 compact blocks was added. In compact blocks, blocks are sent without their full transaction data, but with short (48-bit) salted hashes of the individual transactions instead. When receiving a compact block, the receiver tries to reconstruct the full block using transactions they have in memory, and then requests any missing ones. The details are out of scope here, but compact blocks includes a feature called high-bandwidth mode. When enabled, we permit a limited number of peers to announce blocks to us directly using a cmpctblock message, skipping a roundtrip using headers/inv and getdata which saves latency. In this case, we again process the header embedded in the compact block first, and then process the compact block if the block looks like it is very close to our active chain tip (max 2 blocks ahead).
Block validation. When a block is processed, all applicable consensus rules are performed, which includes syntactic validity, recomputing the transaction Merkle root, transaction finality, BIP34 ("height in coinbase"), segwit commitments, and the maximum block weight. If these checks fail, the block is ignored, or in some cases marked as permanently invalid, depending on the type of error:

When the invalidity is due to a commitment failure (e.g. the Merkle root of the provided transactions do not match the Merkle tree in the block header), the block is only ignored. It cannot be marked invalid, because we haven't seen the block's actual transactions in this case - and they could still be valid.
For other failures, the block header tree entry is marked as invalid.

Invalid blocks. When a block is permanently invalid, the existing block header tree entry is kept, but the block nor any of its descendants will ever be considered for downloading or activation anymore. If the checks succeed, the block data is stored on disk. Scripts, double-spending, and inflation cannot be verified yet.
getblocks based synchronization. Before the introduction of headers-first synchronization a different mechanism was used. Instead of getheaders to initiate synchronization, the similar getblocks message was sent, to which the peer would respond with an inv containing up to 500 block hashes, which would then trigger getdatas and further getblocks to continue. Bitcoin Core no longer uses this mechanism since version 0.10, but it is still supported for peers who want to synchronize this way (i.e., Bitcoin Core will respond to getblocks messages, but will not send them).
3. Block activation
Lastly, when we have the blocks, we can decide what our active chain tip should be, and fully validate the blocks involved.
The active chain tip The active chain tip is a reference to an entry in the block header tree. It starts off at the genesis block when a node first starts from scratch, and as blocks become available through the block synchronization process, it will move, to eventually match the best known block.
Active chain tip selection. The rule is that at every point in time, we aim to make the active chain tip be:

Among all blocks in the block header tree for which we have the full data and full data for all its ancestors, and which are not (yet) marked as permanently invalid...
considering only the ones with the highest cumulative work...
and among those, pick the one for which the full data was received first.

Moving towards the selection. If, at any point, the result of this selection is not the same as the current active chain tip, we start making progress towards the selection.

First the blocks that are part of the active chain but not in the selected chain are disconnected in reverse order. When the block is disconnected, the active chain tip moves to the block's parent.
Then the blocks in the selection not in the active chain are connected in forward order. When this happens, the active chain tip moves to the block's child.

If disconnections are involved in the activation process, it is called a reorganization.
Full block validation. Connecting involves performing full validation, of all consensus rules, including script validity, subsidy checks, and checking for double-spends, which need access to the UTXO set. We only maintain the UTXO set at the active chain tip, so connecting involves removing from the UTXO set any inputs in the block, and adding any outputs. Disconnecting does the reverse, removing any outputs the disconnected block added, and re-adding any inputs it spent. If validation fails here, the block is marked as permanently invalid, which will likely cause the selection logic above to change its idea about what the active chain tip should be.
Announcing new chain tips. Whenever the activation process stabilizes, peers are sent an announcement of our new active chain tip. If only a few blocks were connected, and the peer supports BIP130, a headers message is sent with the headers of all connected blocks. Otherwise we revert to sending an inv of just the new tip. In case the peer selected us as a high-bandwidth compact blocks peer, the announcement is sent before full validation completes in circumstances permitted by BIP152 (again as a means to reduce latency).

"81 bytes in a header message" -> why isn't it 80 bytes? Is there a size prefix to the serialization of a CBlockHeader? Or is it the serialization of a std::vector<CBlockHeader> of size 1 which would be 81 bytes because of the CompactSize?

Outstanding answer, thanks for this. One possible addition could be to note how the behaviour changes when Bitcoin Core is doing IBD vs just catching up. For instance the last section "Announcing new chain tips", it wouldn't announce in IBD.

@AntoinePoinsot Headers are 81 bytes because they are actually serialized as blocks with 0 transactions (and thus have a compactsize 0x00 for the vtx array). In the original codebase there was no separate CBlockHeader type.

Oh, interesting. For future reference: https://github.com/bitcoin/bitcoin/blob/9e1306fc886bcf8024ec37687bbfb8ae364286d6/src/net_processing.cpp#L4137-L4138.


text:
Is it possible to transmit a tx over the network that does not go into the blockchain?
Can I somehow create a transaction that is broadcasted over the bitcoin network but will not go into a block?
Might be handy for SatoshiDice like confirmations.
edit:
What I have in mind is transporting information over the bitcoin network without bloating the blockchain.

There's no way to do that, the protocol isn't built to do such a thing.

You are asking is there a transaction type that will be relayed by nodes but not included in a block. Does this help: http://bitcoin.stackexchange.com/a/6035/153

Fork of this question here: http://bitcoin.stackexchange.com/questions/8408/can-nlocktime-tx-be-used-to-flood-the-miners-mempools

@Lohoris: Answer accepted - for now :)

Actually it might be possible using nLocktime and sequence numbers... see fork link above. Might not be fully implemented as of now, though.

This has two problems:

The network still needs to remember those transactions, so this doesn't save storage space.
If someone does a double-spend attack, two nodes could believe two different things about the state of the network, depending on which transaction they heard about first. Over time, their views of the network would diverge more and more.

I would not mind about conflicting states. This is only about information transport.

It is perfectly possible to create a transaction that is valid but not broadcast to the Bitcoin network.
However the usefulness is a doubtful because what such a transaction will tell is basically "the person that created this transaction had control over this amount of money at this point of time", it has no use to actually transmit value as the blockchain does not timestamp the transaction by including it in a block and no one will acknowledge that the money has changed hands.
If you want to detail your use case you may get a better answer.

I meant it the other way round.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
How do the clients agree on the target to hash for?
Edit: They do not agree on a specific target hash. Any hash lower than or equal to the difficulty is sufficient. This means clients only have to agree on difficulty.

Are you asking how the difficulty is determined?

Hmm, I had not understood the process correctly. I had thought the network was looking for a specific target but it is looking for any hash lower or equal to the difficulty. So it is enough to agree on the difficulty. Thanks David!

By "difficulty" I mean the number that determines the minimum acceptable hash. Higher difficulties mean lower hash minimums and thus, on average, more hash attempts needed to produce a valid block. (Related terms are target and nBits).
Every 2,016 blocks there is a difficulty change block. Unless the block is a difficulty change block, the difficulty must be precisely the same as the previous block or the block is invalid.
On a difficulty change block, the difficulty must be precisely what the difficulty algorithm requires or the block is invalid. The algorithm takes into account the amount of time it took to generate the previous group of blocks and computes a new difficulty such that the block generation time will be, on average, once every ten minutes if the network hashing power stays the same.
If you want to see this in the source code, check out the GetNextWorkRequired function in the main.cpp file.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Create OP_RETURN tx with Bitcoinjs-lib
I know how to create a basic TX:
var bitcoin = require('bitcoinjs-lib')

var tx = new bitcoin.Transaction()

// Add the input (who is paying) of the form [previous transaction hash, index of the output to use]
tx.addInput("aa94ab02c182214f090e99a0d57021caffd0f195a81c24602b1028b130b63e31", 0)

// Add the output (who to pay to) of the form [payee's address, amount in satoshis]
tx.addOutput("THEADDRESS", 15000)

// Initialize a private key using WIF
key = bitcoin.ECKey.fromWIF("L1uyy5qTuGrVXrmrsvHWHgVzW9kKdrp27wBC7Vs6nZDTF2BRUVwy")

// Sign the first input with the new key
tx.sign(0, key)

// Print transaction serialized as hex
console.log(tx.toHex())
// => 0100000001313eb630b128102b60241ca895f1d0ffca2170d5a0990e094f2182c102ab94aa000000008a47304402200169f1f844936dc60df54e812345f5dd3e6681fea52e33c25154ad9cc23a330402204381ed8e73d74a95b15f312f33d5a0072c7a12dd6c3294df6e8efbe4aff27426014104e75628573696aed32d7656fb35e9c71ea08eb6492837e13d2662b9a36821d0fff992692fd14d74fdec20fae29128ba12653249cbeef521fc5eba84dde0689f27ffffffff01983a0000000000001976a914ad618cf4333b3b248f9744e8e81db2964d0ae39788ac00000000

// You could now push the transaction onto the Bitcoin network manually (see https://blockchain.info/pushtx)

But I didn't find out how I could create a OP_RETURN transaction with bitcoinjs-lib in Node.js. Does anyone know?

Relevant: http://bitcoin.stackexchange.com/questions/31989/insert-data-to-transaction-with-op-return

Here:
var bitcoin = require('bitcoinjs-lib')

data = new Buffer("Melons.")

var tx = new bitcoin.TransactionBuilder()
tx.addInput("aa94ab02c182214f090e99a0d57021caffd0f195a81c24602b1028b130b63e31", 0)
tx.addOutput("some address", 15000)
ret = bitcoin.script.compile(
  [
    bitcoin.opcodes.OP_RETURN,
    data
  ])
tx.addOutput(ret, 0)
key = bitcoin.ECPair.fromWIF("L1uyy5qTuGrVXrmrsvHWHgVzW9kKdrp27wBC7Vs6nZDTF2BRUVwy")
tx.sign(0, key)
console.log(tx.build().toHex())

That should do it.
Also, if you have more than 40 bytes of data, your transaction will be non-standard.

Seems things have changed. Now, instead of manually using a buffer and calling the compile function, I had to use bitcoin.script.nullDataOutput("Mellons."). I hope that helps someone.

nullDataoutput is deprecated

Here's how I was able to accomplish this with the latest bitcoinjs-lib version (5.2.0) using psbt.
const alice = bitcoin.ECPair.fromWIF(wif, bitcoin.networks.regtest);
const inputData1 = {
    hash: randomutxo.txid,
    index: randomutxo.vout,
    witnessUtxo: {script: Buffer.from(randomutxo.scriptPubKey, 'hex'), value: parseInt(randomutxo.amount*100000000)}
    };
const data = Buffer.from('YOUR OP_RETURN DATA HERE', 'utf8');
const embed = bitcoin.payments.embed({ data: [data] });
const psbt = new bitcoin.Psbt({ network: bitcoin.networks.regtest })
    .addInput(inputData1)
    .addOutput({
    script: embed.output,
    value: 0,
    })
    .addOutput({
    address: 'bcrt1q7xp6jcgmnuvvaqzr9sdg7yjdqfftswjdqz9897',
    value: 50000,
    })
    .addOutput({
    address: 'bcrt1q7xp6jcgmnuvvaqzr9sdg7yjdqfftswjdqz9897',
    value: parseInt(randomutxo.amount*100000000)-100000,
    })
    .signInput(0, alice);

psbt.finalizeAllInputs();
const txHex = psbt.extractTransaction().toHex();

For bitcoinjs-lib 3.2.0 (not latest):
bitcoinjs = require('bitcoinjs-lib');

const wif = 'private-key-of-sender-in-WIF';
const sender = 'miq6AWvTYZJ63hJfh1W7zozHAf1URDv5pS';
const unspent_txid = '8e320e71d43b130c0786cc9d50fae9ed79b953fba9bcf45070625e37120544c3';
const unspent_vout = 1;
const network = bitcoinjs.networks.testnet;
const keyPair = bitcoinjs.ECPair.fromWIF(wif,network);
const recipient = 'mwLfrTGnLNtyLWFzLfPVcmxEMcW4yaRUZA';

const txb = new bitcoinjs.TransactionBuilder(network);
const data = Buffer.from('YOUR OP_RETURN DATA HERE', 'utf8');
const dataScript = bitcoinjs.script.nullData.output.encode(data);
txb.addInput(unspent_txid, unspent_vout); // payer
txb.addOutput(recipient, Math.floor(1.88*1e8)); // payee
txb.addOutput(dataScript, 0); // OP_RETURN always with 0 value unless you want to burn coins

txb.sign(0, keyPair);

const txRaw = txb.build();
const txHex = txRaw.toHex();

// To broadcast, use local bitcoin core's `sendrawtransaction` or 3rd party service

UPDATE: with bitcoinjs-lib 5.0.2 (latest), same as above, only update the dataScript evaluation and the adding of the OP_RETURN output:
const dataScript = bitcoinjs.payments.embed({ data: [data] });
txb.addOutput(dataScript.output, 0); // OP_RETURN always with 0 value unless you want to burn coins


text:
Explanation of what an OP_RETURN transaction looks like
How is OP_RETURN used and why was it introduced in the first place?

Note: I went out and learned about how the OP_RETURN opcode works at the byte level in a bitcoin transaction. I’m writing it here so that others can learn quickly. First, a brief history of why we’re even talking about OP_RETURN.
Back in 2013 different players in the bitcoin ecosystem were trying to include bits of information into transactions so that they could take advantage of the irreversibility of the blockchain. Imagine for instance you wanted to write a contract and place it in an unchangeable location that at any future date one could go back to verify it existed. You can do this by using the blockchain. You add some bits to the transaction's scriptSig value that don't alter the end result of running that script, but allow you to store information like “I hereby declare to give asset A to address XYZ at time UNIX_TIMESTAMP”. There were even stranger ways people would add extra bits, like including it in the BTC value of an output. Some members of the community did not like this, as they saw these extra bits as polluting the blockchain. The extra bits were a network efficiency concern because more bits meant larger block chains and more of an onus on those who are running full nodes, and it was also a community consensus concern because they thought “we all implicitly agreed to store financial data in the blockchain, which is important to everyone, but we did not agree to store data like small text messages and invoice text”.
To reach a middle ground in these opposing views, the core-developers made the opcode OP_RETURN a valid opcode to be used in a bitcoin transaction, which allows 80 arbitrary bytes to be used in an unspendable transaction. A good explanation of this can be found here:
https://bitcoinfoundation.org/bitcoin/core-development-update-5/

Later in February 2014, the bytes count was reduced from 80 to 40 bytes. This change is documented in the link below. Note that in this pull discussion we learn that no more than one output with OP_RETURN can be included in a single transaction:
https://github.com/bitcoin/bitcoin/pull/3737

Now that we’ve got the reason behind OP_RETURN down, let’s look at an example of OP_RETURN. I used chain.com’s API to find a transaction which has an OP_RETURN in its scriptSig. That tx’s hash is
8bae12b5f4c088d940733dcd1455efc6a3a69cf9340e17a981286d3778615684

Make sure you are connected to a fully-loaded bitcoind node, and run this command:
$> bitcoind getrawtransaction 8bae12b5f4c088d940733dcd1455efc6a3a69cf9340e17a981286d3778615684 1

which will give you this output:
{
"hex" : "0100000001c858ba5f607d762fe5be1dfe97ddc121827895c2562c4348d69d02b91dbb408e010000008b4830450220446df4e6b875af246800c8c976de7cd6d7d95016c4a8f7bcdbba81679cbda242022100c1ccfacfeb5e83087894aa8d9e37b11f5c054a75d030d5bfd94d17c5bc953d4a0141045901f6367ea950a5665335065342b952c5d5d60607b3cdc6c69a03df1a6b915aa02eb5e07095a2548a98dcdd84d875c6a3e130bafadfd45e694a3474e71405a4ffffffff020000000000000000156a13636861726c6579206c6f766573206865696469400d0300000000001976a914b8268ce4d481413c4e848ff353cd16104291c45b88ac00000000",
"txid" : "8bae12b5f4c088d940733dcd1455efc6a3a69cf9340e17a981286d3778615684",
"version" : 1,
"locktime" : 0,
"vin" : [
    {
        "txid" : "8e40bb1db9029dd648432c56c295788221c1dd97fe1dbee52f767d605fba58c8",
        "vout" : 1,
        "scriptSig" : {
            "asm" : "30450220446df4e6b875af246800c8c976de7cd6d7d95016c4a8f7bcdbba81679cbda242022100c1ccfacfeb5e83087894aa8d9e37b11f5c054a75d030d5bfd94d17c5bc953d4a01 045901f6367ea950a5665335065342b952c5d5d60607b3cdc6c69a03df1a6b915aa02eb5e07095a2548a98dcdd84d875c6a3e130bafadfd45e694a3474e71405a4",
            "hex" : "4830450220446df4e6b875af246800c8c976de7cd6d7d95016c4a8f7bcdbba81679cbda242022100c1ccfacfeb5e83087894aa8d9e37b11f5c054a75d030d5bfd94d17c5bc953d4a0141045901f6367ea950a5665335065342b952c5d5d60607b3cdc6c69a03df1a6b915aa02eb5e07095a2548a98dcdd84d875c6a3e130bafadfd45e694a3474e71405a4"
        },
        "sequence" : 4294967295
    }
],
"vout" : [
    {
        "value" : 0.00000000,
        "n" : 0,
        "scriptPubKey" : {
            "asm" : "OP_RETURN 636861726c6579206c6f766573206865696469",
            "hex" : "6a13636861726c6579206c6f766573206865696469",
            "type" : "nulldata"
        }
    },
    {
        "value" : 0.00200000,
        "n" : 1,
        "scriptPubKey" : {
            "asm" : "OP_DUP OP_HASH160 b8268ce4d481413c4e848ff353cd16104291c45b OP_EQUALVERIFY OP_CHECKSIG",
            "hex" : "76a914b8268ce4d481413c4e848ff353cd16104291c45b88ac",
            "reqSigs" : 1,
            "type" : "pubkeyhash",
            "addresses" : [
                "1HnhWpkMHMjgt167kvgcPyurMmsCQ2WPgg"
            ]
        }
    }
],
"blockhash" : "000000000000000004c31376d7619bf0f0d65af6fb028d3b4a410ea39d22554c",
"confirmations" : 2655,
"time" : 1404107109,
"blocktime" : 1404107109
}

Now, look at this transaction’s list of outputs, in particular the 1st one. By referencing the Bitcoin Wiki’s page on Script, Bitcoin’s stack-based programming language, we can see here that the OP_RETURN opcode is represented by the hex value 0x6a. This first byte it followed by a byte which represents the length of the rest of the bytes in the scriptPubKey. In this case we see the hex value Ox13, which means there are 19 more bytes. These bytes comprise the arbitrary less-than-40 bytes you are allowed to send in a transaction marked by the OP_RETURN opcode. If you pop the message bytes into a UTF8 decoder, you’ll see that
636861726c6579206c6f766573206865696469

becomes “charley loves heidi”. Aw! It’s almost like a digital version of a couple’s romantic heart tree carving. Now you understand at a byte level how OP_RETURN is supposed to work. You can write software now that searches for the OP_RETURN opcode in an output’s scriptPubKey, and use it to verify a contract or some other digital asset.

An important aspect of OP_RETURN is that outputs which use it in the standard way are provable unspendable. This means that nodes can immediately remove such outputs from their unspent outputs cache and potentially forget about them altogether (though Bitcoin Core doesn't do this yet). This makes OP_RETURN transactions much less expensive for the network than other ways of stuffing data into the block chain.

FYI if anyone is looking to decode that message 636861726c6579206c6f766573206865696469 in php, it's the hex value so use hex2bin()

Why does this cost less to the network that just sending 1 satoshi to an arbitrary address that contains the 20 bytes of information itself ?

@NathanParker Because with OP_RETURN, the node knows that the transaction output index is unspendable and can just ignore it. Whereas when sending 1 satoshi, the node will need to keep that unspent output in memory or in a database, waiting until someone spends it someday.

@almel Nowadays the command to get the tx details is bitcoin-cli and not bitcoind.

In *NIX the xxd command can be used.  echo 636861726c6579206c6f766573206865696469 | xxd -p -r returns charley loves heidi

How is it possible that this famous transaction contains more than 80 bytes?

(it pushes 983 bytes)

You say that "no more than one output with OP_RETURN can be included in a single transaction" and provide a pull request as a source for this. Where in this pull request discussion is this mentioned?

For those wishing to decode the message using JavaScript, the one-liner in Node would be Buffer.from('636861726c6579206c6f766573206865696469', 'hex').toString('utf8');

According to the Script wiki: it is usually considered non-standard (though valid) for a transaction to have more than one OP_RETURN output or an OP_RETURN output with more than one pushdata op.

Why do the bytes I want to save in the blockchain have to come after the OP_RETURN and not before?

@theymos So this is just a convention/consensus that makes these transaction burn the coins, or there are other technical reasons?

@theymos https://twitter.com/lopp/status/947507679936774145?lang=en Here they say the coins are not burned.

Can I include an addresses entry in scriptPubKey to indicate the recipient of the message?

If you want to write OP_RETURNs to the blockchain without getting into the internals of how transactions are built, an easy way is to use our libraries for PHP and Python:
https://github.com/coinspark/php-OP_RETURN
https://github.com/coinspark/python-OP_RETURN
These support either sending individual transactions with one OP_RETURN attached, or else sending a batch of linked transactions to embed larger pieces of content. That content can then be retrieved from the blockchain using a single identifier.
Assuming you're using Bitcoin Core 0.11, you can change the value of OP_RETURN_MAX_BYTES to 80, rather than 40 as it currently stands in the code.

OP_RETURN is a way to get arbitrary data into the blockchain with less burden to the network
As a consequence, the data will also be present in less clients, as OP_RETURN data can be pruned out.
The goal of this answer is to explain what https://bitcoin.stackexchange.com/a/29555/21282 explained but with a bit more context for Bitcoin newbies.
How a standard transaction looks like
As seen in the JSON disassembly from https://bitcoin.stackexchange.com/a/29555/21282 each transaction has a list of outputs, and each output has a script.
The most common script by far is pay-to-pubkey-hash which basically says:

this output can be consumed by the person who controls the private key to this public key

or in simpler terms "pay X bitcoint to address Y".
That script has format:
OP_DUP OP_HASH160 <length-of-hash> <pubKeyHash> OP_EQUALVERIFY OP_CHECKSIG

where pubKeyHash is 20 bytes and all other 5 fields are 1 byte.
It is impossible to know if a standard transaction hash is an actual hash or arbitrary data
Because pubKeyHash is a hash, it is impossible to know if that is the actual hash of something, or arbitrary data someone wants to encode into the blockchain.
The catch is: if you add arbitrary data there, you won't have a corresponding private key to claim back those funds. So what people do is to make transactions with the smallest amount possible that miners are willing to take for the verification work.
Now, every transaction in the blockchain takes as input a previous unspent output.
Therefore, embedding this data costs you a little, because that output is unspendable: it can never be used as an input of another transaction.
In order to verify if a transaction is valid, Bitcoin implementations have to keep around a full list of every unspent output ever created, known as the UTXO set.
Spent outputs can be pruned to save space, but unspent ones can't.
Therefore, whenever you burn your fake pubkey hash output, you force every single implementation to keep that information around forever, since those funds can never be spent.
How OP_RETURN solves that problem
OP return is another type of script transaction different from the standard pay-to-pubkey-hash transaction.
As mentioned at: https://en.bitcoin.it/wiki/Script#Provably_Unspendable.2FPrunable_Outputs the transaction has simply the form:
OP_RETURN <data>

OP_RETURN simply stops the script execution with a failure, making it impossible for anyone to use that output as the input of another transaction.
Therefore, when a bitcoin implementation sees that transaction, it can immediately decide that it is unspendable, unlike the pay-to-pubkey-hash transaction above, where it is impossible to make that decision. That's why this transaction is called "provably unspendable".
So the miner can mine if for a mining fee, but then implementations immediately prune it from the UTXO set.
This allows the UTXO set to be smaller, thus making bitcoin more efficient to everyone.
But on the other hand, it also means that your embedded data will be present in less people's computers.

If I "add arbitrary data", won't it make the transaction invalid and not accepted in the blockchain? Or is it just the address of the recipient and instead of putting my own address I just put some arbitrary data?

@RonyTesler you just put arbitrary data instead of an actual address you control. But since addresses look completely random in nature (they are public keys) it is impossible for peers to distinguish, so it has to be added to the chain. And because you don't have the private key, it is impossible for you (or anyone else) to claim funds later on.

In case you are here trying to convert OP_RETURN to readable values:
Note: This is javascript / typescript
export default class OpReturnConverter {

    // Input -> <Buffer 35 33 36 39...>
    // Output -> 53696d706c6520616e737765722120f09f988a
    public static convertBufferToHex(buffer: Buffer) {
        const str = buffer.toString('hex')
        return Buffer.from(str, 'hex').toString()
    }

    // Input -> 53696d706c6520616e737765722120f09f988a
    // Output -> Simple answer!
    public static convertHexToString(hex: string) {
        return Buffer.from(hex, 'hex').toString()
    }

    // Input -> Simple answer!
    // Output -> <Buffer 35 33 36 39...>
    public static convertStringToBuffer(message: string) {
        const hexBuffer = Buffer.from(message).toString('hex')
        return Buffer.from(hexBuffer)
    }

}

Results
const string = 'Simple answer! '
console.log('Original ->', string)

const buf = OpReturnConverter.convertStringToBuffer(string)
console.log('Buffer ->', buf)

const hex = OpReturnConverter.convertBufferToHex(buf)
console.log('Hex ->', hex)

const unhex = OpReturnConverter.convertHexToString(hex)
console.log('Unhex ->', unhex)


text:
Is there a way to initiate a payment request in bitcoin?
I'm writing a recurring billing system and I want to be able to contact a customer and request a certain amount of money. Is this possible via bitcoin?
If not, could a URL be provided the customer so he can simply click it and it opens the bitcoin app and initiates a payment process?

There is talk of adding multi-signature transactions in the near future. Depending on how it is implemented it may become possible to allow a business the privilege of initiating the transaction by signing with their private key but not complete the transaction until the customer also signs. In future clients we may see a "needs approval" transaction queue for precisely such an occasion. I leave this as a comment instead of an answer because at present the below answers are entirely correct and there is no way to easily implement recurring billing within Bitcoin itself.

You can now use the Bitcoin payment protocol to do this, more info below.

You can now use the Bitcoin payment protocol to do this.
Here is an easy to use implementation from Bitpay.
There are already a few wallets that support this (including the reference client).  More will be released soon.
See:

BIP 70
BIP 71
BIP 72
BIP 73

There is no way to send messages within the Bitcoin system, and there is no URL link in the Bitcoin client yet. Generally, what you do is provide the customer a Bitcoin payment address and an amount either in the web page, by email, or by some other method.

I believe the Spesmilo alternate client does support URIs following the proposed standard scheme.

If you look at the Bitcoin Wallet app for Android, there is a URI schema used to request money from other users. Unfortunately this isn't part of the desktop version of the application.

You can't "contact" a bitcoin user via their address and likely never will because that could be used to compromise the anonymous nature of addresses.  Likewise there is no mechanism to request payments or send bills.  User can simply choose to pay you.
Thus you will need to contact the user, link unique payment addresses to a user account and track "time remaining" all "out of band".
Say you have a webhosting service which costs 1 BTC per 30 days, prepaid.  While there is no concept of periodic billing you could setup your website to create a unique payment address for for each user.  By recording user information and payment address in a database you know how a method to match incoming payments to users. When you receive payments by looking up the user account by the address you can "credit' the correct user account.  The advantage of doing it this way is the user doesn't need to wait for a bill, pay at any preset time, or wait for service to expire.  The concept of periodic payments will need to adapt to bitcoin unique features and limitations.
To improve payment rates at every login you could advise the user on the numbers of days remaining and remind them of payment.  User could at anytime send a payment to their unique payment address from any wallet and gain x more days of service based on payment size. You could also have the webservice send the user an email at 7 days remaining, 3 days remaining, and when service is expired.
Actually creating this infrastructure to make it turn key for other companies would be a good bitcoin service.

that could be used to compromise the anonymous nature of addresses Not necessarily. You could use something like bitmessage. Of course, that would have all the scaling problems that bitcoin itself has.

There's obviously a demand for a recurring payment system.  In my opinion, there are two ways to implement such a system.  One is a change to the bitcoin base client itself so that, with explicit authorization of the user, it will send x address x # of bitcoins each x number of days.  That kind of implementation would probably have a better chance of getting implemented than something that pulls money from the bitcoin wallet since that kind of action defies the anonymous (and fairly libertarian) nature of bitcoin.
While it's possible that it could be it could be implemented, in my opinion, a better way would actually be to create an API to do this.  DeathAndTaxes had a good outline of what such an API would need to do.
My idea of it is somewhat different, but builds on what DeathAndTaxes said.  The email reminder would be essential if it's going to be a "push" payment rather than an automatic "pull" payment.
I put this in a bitcointalk thread, but this is really a better place for it.
Here's my idea for an API:
1) Customer submits initial payment for x bitcoins.  Future payments are then pegged to the exchange rate for x bitcoins to x dollars (or whatever currency the merchant uses).
2) The service asks for authorization for "recurring billing"
3) If the user accepts, a recurring payment schedule is setup.  Email reminders are sent out for payment like DeathAndTaxes said.  At the 30 day mark, service is shut off if user has not paid.  This could be an automatic thing, or more likely, the API would contact whoever is implemented it that x user hasn't paid and thus needs to have x service disabled.
Actually, another way to implement recurring payments that would make a lot of sense would be with a deluxe wallet client like Armory and not touch the base bitcoin client.  In a way, this type of implementation would make much more sense than the API implementation because it can be totally recurring without the user having to do anything other than ensure that the proper amount of bitcoins is in his or her wallet and that it's not an offline wallet.  The problem with this type of implementation, of course, is that it would limit recurring payments to Armory (or whatever other wallet client implemented it).
Over time, I wouldn't be surprised if both types of implementations occur.  I don't see any reason why they can't both occur at the same time.

Who would host the API?

@NickODell, I'd say whoever created it would host it.  If it's going to be an offical API that everyone would be inclined to use, I'd say bitcoin.org would be the perfect place to host it.  But I doubt it would be quite THAT official, unless it gets implemented in one of the clients in which case it wouldn't really be an API.