Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I have read the Bitcoin paper and there is one statement that I would like to know if it is really proven ir not:
The only way to confirm the absence of a transaction is to be aware of all transactions
The point is that if this statement is false, maybe there is a mechanism to solve the double-spending problem without using a blockchain (decentralized ledger).
Some potential transactions are forbidden, and so you can know for sure that they haven't taken place. For example, one cannot spend a coin that they don't have. But as long as a transaction is potentially allowed, there's no way to know that it has actually taken place without having access to its outcome. If you want to be sure which of the permitted transactions have actually taken place and which ones haven't, it means you want to be aware of all transactions that have actually taken place. This is merely a reformulation.
Note that “being aware of all transactions” doesn't necessarily mean that there is a practical way to list all transactions that have taken place. It can be sufficient to be able to get an answer to certain queries of the form “have transactions of a certain form have taken place?”.
This does not, however, imply that a blockchain is the only solution to double spending (which is when there are two transactions that are each permitted on their own, but the combination of the two transactions is not permitted). What it implies is that the only cryptographic solution to double spending is a single source of truth. If transactions A and B are each valid on their own, in order to determine whether A is valid, there has to be a way to know that B hasn't taken place. Cryptography deals with mathematical properties of information. If the validity of a transaction is purely cryptographic, then the only way to validate A is to have access to information that shows that B hasn't taken place. Thus, there has to be a way to obtain information based on all the transactions that have actually taken place, to show that B isn't one of them.
A central database of all transactions is a simple way to achieve this. A blockchain is a more complex way to achieve this, with the advantage that it's harder for a single entity to produce a fake database (you have to control a majority of the participants).
There are, of course, non-cryptographic solutions to double spending, that don't require a single source of truth. If a transaction is represented by physical objects that cannot be duplicated, then it's possible to avoid double spending without any knowledge of transactions other than your own. This is how cash works. If you receive a piece of information that lets you spend some money, you can use that piece of information as many times as you like, and the only way to avoid double spending is to keep track of when you've spent it. If you receive a physical token that lets you spend some money, double spending is avoided by making you give up the physical token when you spend it and making the physical token hard to duplicate.
Clearly if you are aware of all transactions then you can confirm the absence of a transaction.
Suppose you aren't aware of all transactions but you could confirm the absence of all transactions. Can you see the problem here? You cannot know a transaction is absent without knowing all transactions.
Arguably the mechanism of 'knowing' is important here. For instance, if you knew all transactions except a single one, you could easily deduce the missing transaction by finding the inconsistency. So you know the transaction.
