Good morning, welcome to another session of Algorithm for Internet
Applications.
I would like to start with a remark that I should remind you to
register for the exams.
You can register until next Monday, 3rd of February.
And after that, you have to wait for the next period, end of the
summer term.
So if you would like to take the exam at the end of this term, you
have to register.
I guess that most of you have registered already.
If you have not, you should do that as soon as possible.
Important remark, so you should do that.
Then I would like to briefly look at the report on the evaluation of
this course.
So the feedback is important, an important instrument which we have
used for many, many years.
I have been one of the first faculties who actually did that.
And I am certainly glad to get this high learning quality index.
If I look at the particular things that you have given as feedback,
Well, this is Pflicht, Wahlpflichtveranstaltungen.
Okay, Persönliches Interesse, very few.
I hope that you are interested in what we are doing there.
Then, okay, this looks okay here.
Mitarbeit.
This is always a difficult question because the degree to which you
can actually participate in the lecture is definitely constrained
because it's a lecture.
And it's not an interactive event, and so that's different from a
seminar or a lab or things like that.
But you do see the relevance for your program of study.
It is beneficial for your analytical skills.
And certainly for self-determined work.
Definitely because you can decide on your own when you actually attend
or when you actually listen to this lecture.
This is all quite positive, what you say here on the quality of the
lecture.
Certainly I'm using extra media.
That's what you say is positive.
This is okay, so the workload is okay here, just a little bit to the
right.
And it seems to be acceptable, what we ask you to do.
And then we have here certain things about the contents, the speed is
okay.
That looks all fine.
This is what you usually get, like the degree to which you actually
look at the lecture content before you come to the lecture is
different.
I should make the remark, which I quite often repeat, that if you look
at other countries, for example in the American area or in Asia, there
you definitely look at the content that is to be presented before you
attend a lecture.
This is required.
It's just mandatory that you know what should be presented, that you
at least have looked at the slides if they have been available to you
before you attend the lecture, and definitely before you attend a
tutorial.
Both things seem to be not that common in our German situation, or at
least here at KIT, but I think it's the German situation, that you are
used to just attend a lecture and see what's coming to you, and then
maybe you look at the content.
It's a different attitude.
In other countries, it's definitely the attitude that you have to be
prepared.
But nevertheless, the result in the end is, I think it's okay.
And so, all these things here are positive on the quality of the room.
Then, thank you for positive feedback on my role here.
This is more or less okay.
Sometimes it seems to be necessary to explain a little bit better.
I'm here.
This is obvious.
You don't know where I am reachable.
It's the case that I'm away quite often, so there's always a tradeoff
between being active at many places and being present.
Those who are not very active in many projects are present all the
time, are reachable, but maybe they don't have to tell that much.
So there are differences.
So this is all okay, and then you are asked in the end to give some
textual feedback.
Here, you would have liked to have more tutorials.
Somebody misses how the actual shifting is done in the KMP algorithm.
I thought that I had presented how we actually shift.
I've given you examples.
You've seen that in tutorials.
Somebody would have liked Nukid lecture livestream.
Well, I'm not livestreaming the lecture.
It would be an interesting thing.
I did that once, sometime, or not just once, several times, when we
experimented with virtual university.
But we noticed that livestream is not really that successful.
So we are just recording the lecture, and you can look at it
afterwards.
But then, certainly, you don't have the Nukid tools for interacting.
So that doesn't fit together.
One could do it as a livestream, and then Nukid definitely makes
sense, because then somebody who is looking at it from a distant
location can interfere using Nukid.
So that's an interesting thing to do, but currently we don't broadcast
the lecture as a live event.
Then, those who give feedback in this evaluation gave the feedback
before the bonus exam, and so most of them have not attended the live
lecture.
So there are always these comments that they didn't have time to
attend the lecture, because the video is there.
And what they like is the availability of the recorded lectures.
That's always what they say.
And also some feedback on the contents that we have.
And then here, that's more or less the recorded lecture, what you see
here.
And then somebody doesn't like that the slides sometimes are a little
bit full of text.
Sometimes not up to date.
To some extent, I certainly know that there are some slides which
contain things which are a little bit older, but I always have
mentioned what is the current content and things there.
Could be updated.
I'm always updating a few things.
Then, well, my absence is negative, so it was not possible to do it
differently, this term, but I hope that that will change in next
years.
Okay, very old algorithms, but the quality of an algorithm is not
necessarily dependent on its age, or the relevance of an algorithm.
There are actually algorithms which are quite old, but still very
relevant, so it might be reasonable to present them.
So the pattern matching algorithms are still relevant, although they
are 40 years old.
But even in a new, or rather young discipline, it makes sense to
present old things if they are of relevance.
So, I should... Professor sollte auf wichtige Folien stärker eingehen.
Okay.
And, bonus clause, not that late.
Well, we had it usually on Saturday morning, and then there were
complaints, shouldn't be on the weekend.
And in the week, during the term, in the week, on weekdays, the only
free lecture halls are available in evening hours.
So, more or less, it's positive feedback, so I gave you the, or made
some remarks on that now.
I'm glad that you gave positive feedback, so this is good, and the
criticism is noticed, and I will try to follow that.
Okay, another reminder, you should register for the exam, and then we
can come to our lecture.
Last time, we started looking at electronic payment systems, and we
had looked there at, first of all, the different schemes for payment
systems.
We had looked at something like, or a system which would characterize
typical cash systems.
The problem there, if we transfer that in the electronic world, is how
can we actually prevent double spending of a digital coin, which
certainly can be easily copied, and so you could easily generate your
own money, but you must make sure that that is actually valid money,
and that's one of the major topics that have to be looked at.
We looked at the evaluation criteria, made some remarks on that.
I showed you something on typical procedures for doing online
payments.
We looked at some ways of, these were the criteria, then we looked at
credit card payment systems.
I briefly showed you some, or made some remarks on SSL or TLS,
transport layer security, very briefly, and then we looked at one of
the essential protocols, which is the secure electronic transaction
protocol, using an interesting concept, the double or dual signature,
as was shown on this slide, where you have two parts of this payment
or this ordering event.
You have information to the merchant for ordering something, and you
have information to the bank for paying something, and in order to
guarantee anonymity and confidentiality of information, the ordering
information is only available to the merchant, and the payment
information only available to the bank, and not to the merchant.
The merchant only gets an encrypted version, and you have a digital,
or a digest of the two parts, and can verify the dual signature by
just getting one part of the message, and two on both digests, and
then you can look, or then you can verify all the transactions.
We have looked at the transactions, looking all very complex, always
following the scheme that I presented to you at the end of the last
chapter on cryptographic algorithms.
So here the only difference is that you have two pairs of keys.
You have the certificate, or you have certificates for a signature
key, so you can sign messages, you can write a signature.
The other part is to exchange keys, that is the exchange of the
session key.
The session key has to be encrypted, and so you have an extra pair of
keys for encrypting the session key, and this was shown in all the
different events that we have here.
And another point was that you get this capture token issued by the
payment gateway, which checks that the balance is okay of the
customer, and so the merchant gets a capture token for getting the
money, and this is encrypted, which can only be decrypted by the bank,
or by the payment gateway, and so the merchant can later on submit
that when actually the capture token is sent to the payment gateway.
And I think that we have looked at all these different parts here, and
this is just a sequence of showing you the different scenarios, but it
doesn't make sense really to go into every slide in detail.
What can
be relevant for the exam?
For the exam it can be relevant that you know the essential
ingredients of SET, and the essential ingredients of SET are the dual
signature, and why it is used, the separate parts of the information
that you send as a customer to the bank and to the merchant, what the
dual signature is about, that you have two pairs of keys for
transmitting session keys, and for signing documents, or for digital
signatures, and that's the major point, and you could say what the
capture token, what that is about, why something is sent to the
merchant with respect to the payment event, which the merchant cannot
decrypt, for example, what the idea behind that is.
These are the essential things.
I will not ask you what is the exact scheme and the content of the
message in transaction number six.
I show it, I give it on the slides, so you can look it up and try to
understand what actually is happening there, but I have given you all
the information on how it in principle works, so what we see here in
the individual transactions is just a repetition of how do I actually
deal with completing or creating a signature, what do I do when I have
to verify a signature, verify a document, decrypt a document, how can
I do that, if I only get an encrypted key, what kind of information do
I need, where do I get the information from, it has been sent in the
message because there was the certificate of the public key for the
key exchange and for the signature, and so all the information is
there, it's just showing you what kind of information do you have to
send.
But in the exam, I can only ask questions on more principle things,
and I will not ask for what exactly is the fifth transaction in SET,
it doesn't make sense.
Yes,
they look difficult, complex, but it's just showing, if you look at it
more from a distance, you see it's always the same setup there, for
example, what we see up there, this is just verifying a signature.
Decrypting the key, and then decrypting the signature, and compare
whether the generated digest is the same as the received digest, and
this is just the standard procedure.
And if you just black or just take a more abstract view, you could
say, okay, abstract procedure A, abstract procedure B, and it looks
much more simple.
If you look at it like that, it looks more simple, and as I said, the
major points are, how do you actually utilize this secure
communication protocol, which we looked at at the end of the last
chapter, using session keys and encryption and signatures, how is that
utilized in such an application?
The additional things are the dual signature, which we didn't have
before, and then this capture token.
Okay, I think that clarifies that.
These were the major properties summarized here again, so this is the
central point that I could ask, and then certainly a little bit more
detail could be asked, but as I said, not particular steps of an
algorithm, I would not ask for that.
And then we come to the next real slide here, new one.
There are many different schemes for paying in online transactions,
and you know one, like there have been many more transaction schemes.
There is one scheme, like PayPal, what do you do there?
You open an account with PayPal, one way of paying, you open an
account there, and if you want to pay, you send account information to
the merchant, or you can, this information is, and you send that
usually by clicking on the PayPal, or giving the PayPal information,
and then this is sent, like this information is sent together with the
order information to PayPal, so this is the major difference from SET,
that here you don't have anonymity, you don't have confidentiality of
the ordering event, here the ordering information is also sent to
PayPal, there you can log in and confirm the payment directly, and
then PayPal will notify the merchant of the payment, so you have the
customer, you have the merchant, you have PayPal, and you send
information to the merchant, that is sending information to PayPal,
then you can, you have to interact with PayPal, PayPal is sending
information back to the merchant, and then you can complete this
ordering event.
And the communication is secured using TLS, or SSL, so using HTTPS,
and so the credentials for actually authorizing the payment event are
given by the customer directly to PayPal, the merchant doesn't get
those credentials, if the merchant only gets the information that is
necessary to actually create this communication between customer and
PayPal.
So this is, but it is not as anonymous as the SET scheme is, where the
payment gateway does not get information on what kind of things you
actually have purchased, this information is open in this scheme.
Another scheme is a payment by integrated online banking, I guess that
you have done that already, when you buy something in the internet,
you go to the merchant, the merchant website, you select the option to
pay directly using your online banking, then a window opens up, and
you can enter your information of the bank, like the bank information
of your account, and then you get your, like using some kind of
clearing point, you get communication with your customer bank, with
your online banking system, you identify yourself to the bank, and
then all the information with respect to the transaction is already
entered in the form that you have there, and then you authorize the
transfer, you have a transfer of funds between your bank and the
merchant bank, and if you have completed that, and authorized the
transaction, then the clearing point notifies the merchant, you see
that on the website that this is completed, and then since the fund
transfer has been initiated by the customer in the online banking
methods, then the merchant can, or the customer can get what he wanted
to order.
So this is just using other schemes, online banking mechanism, for
payment, which looks fine, although the merchant certainly gets some
information that you enter into the forms for actually calling your
online banking system.
But when you are doing this transaction, you are communicating with
the bank, with your own bank, and just doing something in
communication with your bank, which is what you do anyway in your
online bank transactions.
There are several different services available for this payment
scheme.
There was one, like one company here at Karlsruhe called Fun, that has
nothing to do with the English word fun, but is an abbreviation for a
company here at Karlsruhe.
So they are experts in payment software, and they have designed
something around these schemes.
But if you look at current websites of this company, you don't find
that much information on it, but there is some information still
available.
This is standard technology.
Now I would like to come to a, like this is not really that
interesting with respect to algorithms that we use.
Now I would like to present to you another concept, which is more
interesting with respect to algorithms, with respect to payment
systems, because here the idea is to create your own version of cash
in electronic ways.
And this is what I indicated initially in this chapter, that we should
actually look how we can actually create something equivalent to cash.
And it means that we have some kind of new currency.
A coin, cash coin, will be just a digital entity, so it is some file,
some object having some content.
It will be independent of other existing systems, but it should be
able to exchange e-cash for real cash, for real money.
Cash is anonymous, so this should also be anonymous.
This is something which is not liked by financial institutions,
because anonymity means that you can do money washing.
You can just exchange or get money from somebody or transfer money
between different entities, between different persons or institutions,
without control by the financial system.
And so this has some risk, and so it is something which is a
suspicious system for those who look at, or those financial
institutions are very afraid that these systems actually can create
some illegal fund transfer system.
So we have to look at how that can be prevented.
Then there is one point, which is an online solution.
Definitely it must be online, because we have digital coins that we
would like to spend.
But this online solution also refers to the fact that in order to
check the validity of a coin, we need a connection to some financial
institution which actually tells you that this coin is valid.
We will see how that works.
We will have some electronic coin in there, and it uses typical
encryption methods, could use RSA public key encryption, could use
other public key encryption methods, but essentially it is that it
uses public key encryption methods, and it uses a different type of
signature.
That's one of the major reasons why I present that to you, the idea of
a blind digital signature.
And what can blind signature be?
You may know that sometimes you get an envelope, and there is some
content in there, but you don't know what it is, but you are requested
to sign it.
On the envelope there is carbonated paper inside, and the recipient of
that document afterwards can take it out, and has a signature on a
piece of paper which you have not seen, as the person who is signing
it.
That's a blind signature.
You sign something without seeing the content, but you have agreed
before that you are willing to do so.
And then the recipient can, like if here is some document, can take
out that document, and on that document later on there is exactly that
signature.
Now this is the paper version of a blind signature, which you might
have seen.
Carbonated paper, you write on it, on the envelope, and inside you can
take out a piece of paper, and hence it carries your signature.
Simple scheme.
Now how can we do that in an electronic way?
So we will look at that.
First of all, it is encryption of e-cash.
It has three stakeholders, three actors, three parties.
You have the banks, which actually issue, or I should say they
validate the electronic coins.
They are actually created by the customers.
They are not created by the bank.
They change real money into e-cash, and they change e-cash into real
money.
And the customers, they have an account at some e-cash bank where they
can withdraw e-cash and they can deposit e-cash.
And the merchants accept e-cash.
Certainly they have to communicate with the bank to get the money.
When they get e-cash from a customer, they would like to get the money
and have to communicate with the bank.
Customer and bank have to communicate in order to exchange real money
into e-cash.
E-cash can be transferred to the merchant, and the merchant has to
validate, get the money, get the real money.
So this is a three-party system, and it is a closed-loop system
because you could provide this easily on to another merchant or to
some other party, but it's a question whether you actually present
them valid coins.
We will look at the problems that are there and how we deal with those
problems.
So how do I generate an electronic coin?
How can that work?
The coin is actually generated by the customer.
Perfect.
I can generate my own money.
But I can only generate a description of money, like some way I would
like to actually name or identify a coin, but it has to be validated
by a bank.
So first of all, I generate a random serial number, just a large
random number.
And this is the identifier of the coin.
Every customer can do that, and we just assume that the probability
that two customers generate the same serial numbers is very small, and
so we just take long enough numbers, and then they will all generate
different values.
So we have to make sure that the probability of not having unique
numbers is very, very small.
And then you fix the... so you have your number.
And this is supposed to be your coin.
And you say, okay, this coin should have a certain value.
For example, you say it should have a value of 5 Euro.
Now this is not sufficient to just write it's a 5 Euro coin.
Somebody has to validate that.
And then you send hidden serial numbers.
So you put this into an envelope.
Now inside that envelope you have this, but this is all hidden.
It is such an envelope with, what I said, carbonated paper.
And now you ask the issuing bank.
Certainly you send that in a secure way.
You send that, so for example, here you send that.
You send hidden serial numbers and coin values to the bank.
Encrypted with the customer's private key.
Or encrypted in some other way to make it confidential.
You could also use a symmetric method for encrypting that.
So the recipient can use the customer's public key to decrypt that.
And then you only have, so the bank can find out the hidden serial
number.
In some way you hide the number.
So you get that envelope.
That's the hidden serial number is the envelope.
On the envelope you write, I would like to get a 5 euro coin.
Please sign that.
And the bank validates the coins with a blind signature.
It is signing that.
Writes a signature, presents a certificate stating this is signed with
a key that corresponds to a 5 euro value.
And so I can see from the certificate, from the bank, that the bank
has signed that as a 5 euro coin.
But the bank does not see the serial number.
It only provides you with that signature.
And it deducts the corresponding amount from the customer's account.
Sends it back to the customer.
And then, so just using the customer's public key or some other method
for secure communication.
This is really not relevant.
Confidentiality can be achieved either by using asymmetric or
symmetric methods, as you know.
And then the customer software just makes the serial numbers visible
again.
Takes the coin out of that envelope.
Then you have that coin, you have again your serial number.
You have the 5 euro certificate of the bank.
And you have the signature of the bank on it.
The bank has signed it.
And then you can use that coin.
This now has a serial number, uniquely identifiable.
It has a certificate for a certain value issued by a bank.
You have the signature of...
So the signature tells you that it's exactly this serial number that
has been signed.
And so everything is fine.
You can use that.
And so the customer software makes the serial numbers visible.
Adds the validating digital signature from the bank.
You have the certificate.
So you can check whether that actually has been signed by the bank.
Yes?
The bank does not see the serial number.
Yes?
You will see how that works.
This is a valid question.
How do I check actually that I don't use double spending?
So if you send it again, if you would send the same serial number
again to the bank, what would happen?
The bank would again validate.
It doesn't see the serial number.
And it would deduct the corresponding amount from your account.
Now you are silly.
Because you'd ask the bank twice to validate a coin having the same
serial number.
Then the value is deducted twice.
The bank does not know that it is the same serial number.
You know it.
So you are really...
You will raise your money.
You shouldn't do that.
The other question, how do I actually check that this coin is not
double spent?
This is another point.
To
decrypt.
Yes, but this doesn't matter.
This is just showing that this is something that this customer has
actually sent.
So I would say, as I said when I presented that, this is just for some
kind of signature of the customer that he actually wants to get that
coin.
It's certainly not guaranteeing confidentiality because everybody can
open it.
If you have the public key, you can open it.
So this is not confidentiality.
If you would like to have confidentiality you can add this standard
method of using the symmetric method for encrypting and sending the
session key for that.
This is not the point here.
The point is that the customer identifies himself because he used the
secret or his private key.
This can be verified using the public key to decrypt that and you have
to decrypt it in order to get the hidden serial number and the coin
value and the request for please validate.
So this is just to make sure that the bank has a uniquely identified
customer.
Because for that the customer has to authorize that the corresponding
amount is deducted from his account.
So you need this identification.
That's the major purpose.
It's not the confidentiality but it is the authentication.
Yeah, good that you asked that question.
Okay, now how does this blind signature business work?
I just showed, okay, you can do that in some way.
How does that work?
So this is now an abstract setting.
You have Alice and Bob and they want to send something back and forth
or Alice would like that Bob signs a message without knowing the
message.
And so we look at this standard scheme.
How can we do that?
What do we do when we perform or when we sign something?
We sign usually we encrypt, digest with our private key.
Okay, so that's a signature in this sense.
Now, the idea is that you sign something and you don't know what you
actually signed.
So this hiding a serial number is done in the following way.
M in this case is the message.
The serial number that you generated for the coin.
And now you make it invisible by multiplying it by choosing a random
number and this random number has to be prime with respect to this
modulus N of our cryptographic algorithm and of this public key method
that you use where N is the modulus and then you make or you hide the
message M by multiplying M with R to the C modulo N.
So this is slightly different from the normal encrypting something so
without the M it would be encrypting R.
But here you have you take R to the C, multiply it with M and you have
a new value M'.
Now M' is the product of some R to the C and the original M M is your
serial number that you would like to hide and so from M' you cannot
know what the original M actually was without knowing this random
value R.
But this random value R is only known to Alice or to the customer in
the cyber money or e-cash setting.
And then Bob is asked to sign that.
Signing here just means use your private key to encrypt that message
so M' has to be used with his private key The private key, like R C
was the public key of Bob I don't know whether I said that when I
explained this So C is the public key, Bob's public key and D is
Bob's, here there I said it C and D, public and private keys So R to
the C, using the public key of Bob, then to sign it Bob has to use his
private key and to sign M' using his private key means compute M' to
the D modulo N M' is R to the C times M if you take that to the power
D it means that you have R to the C times D multiplied with M to the D
modulo N, but R to the C times D is congruent to R modulo N and so
this is actually U' this encrypted message U' is the encrypted version
of the message M' U' is R times M to the D D is Bob's private key so
what Bob has done implicitly is creating M to the D modulo N, but it
is hidden by that random value R and now this is sent back, this
message U' is sent back to Alice and Alice now just has to do the
following it has to cancel out the R so you multiply with the inverse
of R which exists because R is primed with respect to the modulus N
and then if you do that, multiply that with the inverse of R, you get
back M to the D mod N is the signature of the message M of that serial
number that you wanted to get signed, and since you have the public
key of Bob everybody can validate that this actually, like if you
provide the number N, you can validate that by decrypting this U you
can validate, ok, since it is the same value, Bob must have validated,
must have signed that number.
So what you see is you can, if you have if you know the public key of
Bob then you can just compute U to the C and you have the value M back
the value M is printed on your coin so you can check whether Bob
actually signed that.
So in this way, the bank signs the hidden serial number you get a
certificate back from the bank on the usage of a particular public
private key pair, so they signed it with their private key
corresponding to a specific amount and you can verify that that the
bank signed it just by using their public key which is given in the
certificate.
So everybody can verify this is a coin or this is a signature, in this
case here, that Bob has done on the value M and so we have this kind
of blind signature.
This is all which is behind this notion of a blind signature.
So only Bob could generate the signature U of M, because only Bob has
the private key.
He did not sign M but M' he signed actually the hidden value as I
said, you have this envelope where you sign without knowing the
content and this envelope corresponds to the multiplication of R to
the C Only Alice can retrieve the signed signature from the envelope.
Only Alice knows the value of R so only she can generate R to the
minus one and can retrieve that value so if this message this signed
coin is sent to somebody else this other person cannot do anything
with it because you first have to retrieve the value that you need for
the coin this M to the D so only Alice actually can unblind that
number and any other person after that can verify that Bob has signed
that and so that's what Alice wanted to have, she wanted to have some
kind of message that Bob has authorized, or has signed.
Okay, that's the blind signature.
Interesting concept.
And the first idea is, why should I do that?
What is the rationale behind that?
But I hope that you see that.
The bank is supposed to sign something and should not know the serial
number, but should make clear, I validated this entity by deducting
five euro from the account of the customer.
I'm sending it back to the customer, and now the customer has
something which has a value of five euro, because that amount has been
deducted from his account.
I don't know how it is specified, that's up to the customer to do
something with that value.
And sometimes later on, the bank might be asked to re-exchange that
value, that signed coin, into real number, or sorry, into real value.
So transfer back five euro to somebody who presents that coin.
And since any other person can verify that Bob has signed that, Bob
also could do that, or the bank certainly can verify that it has
signed that coin.
And so the bank knows, okay, this is the coin that this bank has
signed, so it is valid to transfer the money to the person who
presented that coin back.
But what happens then?
You present this coin to the bank at the moment where the bank has
actually exchanged that again into real value, certainly the bank has
to memorize that they do that.
They should have a list of all the coins that they have re-exchanged
into real value, into real money.
And so at the moment where a bank validates the coin, it knows that
serial number, it can check whether it has actually signed that.
So you could say, okay, I don't want to have that money transferred.
And then this could be used again.
But as soon as somebody has retrieved the money, then all other copies
certainly are invalid.
And so if somebody else presents the same coin, the bank should know,
okay, which one actually is the valid one.
This double spending problem is still a problem.
And so this is now just showing again what's happening here in this
scheme.
If we use the blind signature for the e-cash thing, here we have Alice
or the customers' wallet.
So you generate the coins, put them into an envelope by randomizing
that value, like multiplying with r to the c, as I said.
This is the first step that you blind the serial number and sign that
with your private key in order to authenticate that you are actually
requesting to have that coin signed.
The bank sends the coin to the bank encrypted with the bank's public
key.
If you do it like that, only the bank can open it.
Or you could send some other encryption method.
The third thing is that the bank verifies the customer's signature
signed.
So it verifies that the customer actually, or first of all, the bank
has to retrieve that or decrypt that envelope using its private key.
The bank verifies the customer's signature.
Decrypting that message, so authentication is checked.
Then the money is deducted from the customer's account and the bank
returns the validated blinded coins to the customer encrypted with his
public key, so only the recipient, only the customer can open it.
That's again confidentiality.
And then the customer uses his private key to decrypt the bank's
message.
Yeah, that's confidentiality.
Removes the blinding factor.
He certainly also gets the certificate from the bank relating to that
valid or to that amount that it was validated for.
And so the electronic coin that you actually use consists of the
serial number that you generated initially, the signature of the bank,
and the signing bank certificate.
In the certificate you have the specification for which value that has
been done.
So this is the coin.
And then the question is how that is actually used.
And so the customer goes to the merchant which accepts e-cash.
The merchant would like to get some money.
You send your coin and then the merchant would like to show or to see
whether that coin actually is valid.
Goes to the e-cash bank that has signed that coin and sends this file
with a coin to the bank.
Then the bank says okay that's the money, that's five euros, and
transfers five euros back to the merchants account.
And then the coin actually is invalid because the bank certainly
writes down this serial number and then has a record of having
transferred five euros to that merchant because of this coin.
The bank does not know who actually created the coin initially.
The bank only knows that somebody must have created that coin and that
this bank actually signed it.
But since the bank does not know which coins it actually signs, it
cannot check from the coin that it gets who actually was the original
generator of or creator of that coin.
Okay, so to get certainly a receipt from the merchant that he got the
money and then that's the payment event.
And the bank stores all the serial numbers of retrieved coins in a
database and if a serial number is already there, then the coin that
is presented must be a duplicate.
That's double spending.
But it requires that you have this central authority, the bank, which
is recording all the validations of coins where money has been
actually exchanged for a digital coin.
If you would say, okay, it should be possible or should be allowed
that the bank just looks whether a certain coin that you present to
the e-cash bank has already been spent, then you could also say, okay,
if it just gives the answer, this number is not in my list of coins
that I actually have used, then you could reuse that coin and transfer
it to somebody else.
But the customer certainly does not know what the merchant actually
does with it and so the customer can only use it once.
Only the merchant could reuse that coin if it doesn't request for
having it exchanged.
But if the customer now, that certainly is a risk because the customer
could easily take another copy or create another copy of that coin
because he had that coin and send that other copy of the coin to the
bank.
And if the bank would look, oh, has this already been used, then the
bank would say, no, it's not recorded.
So only being looked up by the merchant, so the customer could
actually get the money and then the merchant would not get the money.
So it doesn't make sense to say, I just look it up, get the
information.
It has not been exchanged into real value, but then somebody else
could try to get that money.
So it's a one-time use.
You use it once for paying something and then you get the money and
that's it.
So it's not really an equivalence to real cash because you cannot
prevent double spending in the system and you can only use it once and
the merchant, the recipient will directly go to the bank and have that
online transfer into real money.
Okay, so what are the characteristics of e-cash?
We have rather low transaction costs.
Depends on how much you have to pay for such a system.
Security is there by using all these encryption methods.
Traceability, what about that?
The customer is not visible to the or not known to the bank or it's
not known to the bank who actually created the coin, but certainly the
user or the creator of the coin knows a certain number and can check
who actually has, like the user could check with the bank who actually
got the money.
Yeah, so you can trace what actually happens to your coin, but it's
something it can be traced by the customer, not by the bank.
And then there's the undeniability of payment because you get a
receipt certainly and so the merchant cannot say he doesn't get, he
didn't get the money because he's stated that he got the money.
The problem is that you have a necessity for online checking, which
makes it a problem you cannot reuse, but in this way you prevent
double spending.
So all use points prevent misuse or prevent double spending.
Acceptability is a question whether you would like to have a cash
system where you can spend the money only once, you have to create
next money all the time.
Transferability depends on the trust you have.
You can only, like, if you transfer your file, like your electronic
coin to your friend, you say, okay, I will not use a copy of that.
Depends on how much trust you have in such a statement that you will
not use that again.
You have completely forgotten the number.
That's a problem.
Not bound to fixed hardware, but you do not know that a coin is still
valid.
So that's the problem.
And divisibility certainly depends on the coin values, what kind of
certificates you can get from the bank.
Usually the normal denominations of some value should be used.
The bank will not provide arbitrarily many signatures for a public
key.
Pairs for every value, but only for standard values.
An important point is that it is anonymous, that the anonymity of the
customer is something which is not present in the credit card payments
or online banking systems.
There you have traceability and everything is known to those who are
involved in the payment transactions.
And now I would like to come to another way of creating digital money,
which is quite popular at the moment, quite hot topic.
Bitcoins, like in December, there was a conference of the hacker
associations.
German hacker associations had a large conference where bitcoins were
a major topic.
If you look at the press, financial press, you will notice that
there's quite some discussion on the value of the way financial
institutions should deal with bitcoins.
And it is interesting to see how that actually operates.
And so here, what they certainly try to address is again, the problem
of how to prevent double spending.
And how can we do that without actually depending on the financial
institution?
Can we create our own currency for paying in online transactions?
And so you have, you know, the problem of e-cash, which I just
outlined.
And then there was an idea by a Japanese fellow, Satoshi Nakamoto.
And here the idea is to get rid of that central bank, which has to
validate the coins, and replace that with a pure peer-to-peer version.
That means the community is actually responsible for validating
financial transactions.
This is an interesting concept, a very complex concept.
And I will try to explain that to you in a rather abstract way.
Maybe you will have some questions and we can discuss that.
We can also discuss that in the tutorials.
So I tried to present to you a few essential points of that bitcoin
system.
You can look it up in the paper that Satoshi Nakamoto has written.
And there's on the web, there's quite some material available on
describing bitcoins, but it is directed to different target audiences.
So if you look at the different versions of describing bitcoins, you
can find something like certainly at the bitcoin.org site to get all
the information.
But then there's quite a bit of information just for the uninformed
user who just wants to know how to get bitcoins, how to pay with that,
but is not interested in the algorithmic background.
And we certainly would like to look more into the algorithmic
background.
And you will notice that if you look at the literature on bitcoins,
that there they make explicit use of elliptic curves, which I did not
present to you.
Elliptic curve cryptography, like public key methods, is a method
which I did not present.
It is used here as just some public key signature mechanism.
And in the documents that you find on bitcoins, you always find
elliptic curve digital signature systems, where you also need public
and private key pairs.
It's a simpler version than RSA.
In particular, the key length is much smaller.
But in principle, it is not important whether you use elliptic curve
cryptography or whether you use RSA or some other public key method.
The major point is that you use public key methods in this case, pairs
of public and private keys.
I will show you how that actually is working.
So there are many ingredients in that.
You will have to wait a little bit before we actually have all the
components of that available.
So the first thing is that you have bitcoin addresses, and you have
wallets.
So a bitcoin address is essentially an account.
But if you would like to get money, or to create money, how do you do
that?
To have some entity, we can say, oh, there's money.
Yeah, what you do is you create an account with a bank.
The bank says, okay, I will give you...
this is what you usually do.
You create an account at the bank, and you get some number in front of
that, some address, some account number.
This is exactly what is done in bitcoins.
First of all, what you create is an address for an account, where
somebody else can send you money, can make a transfer.
So how do you create an account?
Usually, you go to the bank, and the bank assigns to you a certain
account number, following certain rules, and then you can publicize
that account, and wait for somebody sending money to that account.
And then you have money, if that transaction is validated.
Usually, it's validated by the bank, because they have the rules how
money can be sent from somebody else into that account.
You have some record on that.
It's a valid transaction.
Later on, you can ask, oh, that transaction, was that actually valid?
And the bank presents to you some documents stating, okay, there has
been some transaction, which we checked, it's valid.
And so this is a real amount of money on your account.
And this validation now has to be done in some peer-to-peer setting.
Peer-to-peer, as you know, means many people who actually have to work
on validating that a certain transaction is valid.
How can that operate reasonably?
So it means many peers have to agree on actually doing some work
validating certain transactions.
So let's start with actually, how do you create an address for your
account?
What you do is, you have the public key you created.
So you create a private public key pair.
Certainly, in practice, what you do is you download the Bitcoin
software, you say create an account, and you get something looking
like this.
And this is generated from your public key.
How is it generated?
By using strange acronyms here.
What you know is SHA, Secure Hash Algorithm, 256.
So Secure Hash Algorithm of 256 bits is generated from your public
key.
And then another signature is used, RIPE MD.
So RIPE is another way of actually generating message digest.
So RIPE message digest 160 means you get a 160-bit result.
That is some transformed version of your public key.
Now this value is the fingerprint, as we normally call it, the
fingerprint of your public key.
You have taken, actually here, a sequence of two signature methods,
SHA and RIPE MD.
And this is the fingerprint.
And then you take that fingerprint again and perform twice SHA 256,
twice on that fingerprint.
And then you get the 256, like the result of that is a 256-bit
fingerprint, or digest of that fingerprint.
Double digest, or not double digest, it's just done twice.
And you take the first four bytes of that digest that you just
generated here.
And so you have the 20 bytes from the 160-bit message digest.
You have four bytes as this, what is called a checksum.
And here in front you have another byte, which is just some indicator.
It's not really that relevant for us in the moment.
What that actually means is just some agreed prefix that you have to
put there.
And then this is transformed from binary representation, so you have
these 25 bytes, into a base 58 representation.
Base 58 means you have small and capital letters, that's twice 26,
gives 52.
And then you have six digits that can be used.
So zero is taken out, some digits are taken out, so we have a 58
symbol or representation of that value that you have generated, of
these 25 bytes.
This is a sequence of symbols, base 58, and this is your account
number, your identifier of the account.
Okay, so this is how this is actually generated.
Looks a bit of a strange, I don't go into any arguments why it's
exactly taken or done like this, with double application of signatures
and so on, and here a combination of different signatures.
That's how it has been suggested, I just wanted to present you the
scheme.
I don't go into the details and into the arguments why it's just done
in this way and not in another way.
Just wanted to show you how it actually operates.
And then the question is, how do I get bitcoins?
Somebody has to transfer money to your account.
Okay, so an electronic coin in this case, or a bitcoin, or some value,
bitcoin value, is represented by a chain of transactions with a lot of
digital signatures.
The interesting thing is that bitcoins are actually representations of
everything that has been done with those bitcoins that have been
generated.
Yeah, so you can, if you get a bitcoin, you get a chain of
transactions.
You can see everything that has been done there, so there's no
anonymity, or there is pseudonymity, because you only see the, you see
account numbers, you don't see real names behind those account
numbers.
But as soon as you know something about who is associated to an
account, you can easily follow what kind of money or what kind of
transactions have been done on that person's account.
But that's only possible if you know the association between an
individual and an account number.
Now how does such an electronic coin, or such a transaction, actually
look like?
So what you assume, you have got a certain electronic coin, which is a
sequence of transactions.
So this is what you actually got, this sequence.
And now you have to continue that, you would like to transfer money to
somebody else.
So you write something in this transaction, you would like to make a
transaction to somebody else.
And now in this description, or in this electronic coin, you have
several ingredients.
You have there the owner, like this is owner two, who is, that was
owner one.
Now here you have owner two.
It's owner two's public key that's in there, that you have the public
key, or your own public key is given, or is in their transaction,
which you send to, like what you sent to the next one, is this.
So what you send to the, to the, to owner three is your own public
key.
Then you have here some more ingredients.
You have some hash, or you assign, or you have a signature of what has
been done before.
So this is a signature of a hash of what has been done before.
And this second owner's public key, that is hashed into a message
digest, and then signed by the previous owner.
This is a signature.
All this, all this information here, is now taken together with the
new recipients, owner three's public key, which you know, because you
have to know the next owner's public key in order to be able to send
him that, or some money.
You hash that and sign it with your own signature.
Now you have verified as owner two, that you want to make that
transaction.
You have verified that with your own signature.
So you can authenticate that this actually came from owner two.
You can verify it by looking at owner two's public key, which is also
sent to the, so a complete file is sent to owner three.
You have all these public keys.
It's a very large file, gigabytes of value, very large files.
And you get this signature.
And you get a description of the transaction.
You also have to put your own, or there's the owner's public key in
there.
And the hash is done from the previous transactions, like this old
electronic coin and the new recipient's public key.
This is signed by the owner two's private key.
So this is an authorization done by the owner two.
And it contains its signature of the statement that the owner three
actually is the recipient, the legal recipient of something which is
specified up there.
What is specified there is, for example, send 100 bitcoins to owner
three, to the account of owner three.
Now this is such a transaction where you have, where you provide all
the public keys that are necessary to verify signatures.
So the recipient can actually verify the complete chain.
But everything here is correct by using all this public key
information.
Can be a very long history of transactions that have been done.
Okay, but still you have to verify that this is something which is
legal.
Because you could send this to owner three, you could send the same to
owner four, to somebody else.
You could try to do double spending.
Yeah, and just say, okay, I send that much to a person, owner three,
that much to owner four, and so on.
And I just double spend those coins.
How can that be detected?
How's the verification actually done?
So for that, like the fraud that you have here, possible fraud is
double spending.
You have to prevent that.
You don't have that central institution.
And now we have to verify or to make sure to certify that we have
something valid by using that peer-to-peer network.
Now this is done by asking everybody to verify that their transactions
are actually valid.
So what you actually do is that if you would like to, or if you agree
to try to validate certain transactions, you get the so-called
blockchain.
Blocks are...
So you have a blockchain.
And in that blockchain, you always have, like, it's a chain of blocks
as indicated down here.
And if you look at two such blocks, what you have is the final block
here has a hash value of the previous block.
And it also contains a number of transactions.
Actions which you check for being acceptable.
And now, how do you actually do that?
So you can have... one point is that it may be that you have several
of those blockchains and you have to find out what is actually, like,
if at the moment where you have such a link, this one here is
accepted.
Now, if you have, if you look at such a situation, there might be two
different blocks.
And the question is which one actually will be accepted.
And so it depends on which transaction is actually accepted first.
And this one, so the longest chain is always taken as the valid one.
The others are discarded, and everybody agrees on that.
How would you discard something?
If you detect that somebody makes double spending, and you get all the
information, the previous transactions for everybody who's
trustworthy, since everybody who's working here, the peer knows all
the transaction history can check whether there is an indication of
double spending.
If there's no indication of double spending, you will accept it.
And you do that by adding another block.
Now, how, how can you actually add another block?
How do you do that?
So you need a proof of work.
First of all, you have to invest a certain amount of work.
And this work consists of the following.
You have this, you form this block.
You have the previous hash from the chain that you got.
You have a number of transactions that you would like to get verified.
And now you have, this is a number, like a number used only once.
That's the abbreviation nonce, is a number used only once.
And this number, now this is the work that you have to do.
The work consists of, I don't state it here, that's on the next
statement, on the next slide.
This number here actually has to be a number such that the hash of
that block, the hash value that you compute from that block, has a
certain number of leading zeros.
And so you request for a certain format of the hash of this block.
And you have to find a value in this field that, together with all the
other information in that block, so the hash of the previous block and
the transactions that you would like to include in that block, if you
hash that information, you get a digit or a digest having a few
leading zeros, which is determined, which is agreed upon in that
community, how many zeros you have to provide.
And this is the work you have to do.
So only those who are actually agreeing to do some work can generate
these blocks.
This is the proof of work.
You have to invest a certain amount of work, and only those who are
really honest will do that.
That's the assumption.
If you're investing, if you're willing to invest certain money, and
you assume that the majority of the participants in that network will
be honest and do that.
Okay, you also get some remuneration for the work.
That's on the next page.
So we assume that honest nodes make up the majority of the CPU power
that is used, actually.
And if you would like to, if you have some fraud, it would mean that
you have to modify everything that is on the history.
If you would like to modify some transactions there, you have to
modify some of the transactions that are recorded in order to prevent
that somebody else notices, oh, there is double spending.
This requires that the previous spending event is not visible.
So you have to change that.
If it's there already, and you would like to certify the next spending
of the money, you have to change something in the history.
And this is very, very much work, very expensive, so you wouldn't do
that.
This is the rationale behind that.
And then a payment is considered as accepted after a certain number of
blocks have been calculated.
So this is another reason there.
And now, what is actually, so what is the, whoops, yeah, this is
everything that is done there, sorry, here, that you have to find out
that value.
Now, how the network works is now that you have a new transaction that
you would like to make.
As I said, I extend this Bitcoin sequence, the sequence of
transactions with one new value.
This is broadcast in the network, the Bitcoin network.
And now every node collects new transactions into a block, not
necessarily all the transactions, but just some of them.
And then the node is working on finding a difficult proof of work for
its block.
It's difficult because it depends on the number of zeros that you have
to provide there.
And when a node finds a proof of work, that means find such a number,
which results in a hash having a certain number of leading zeros, then
this block is broadcasted to all the nodes.
And now the nodes accept the block that has been, that you did some
work on, if actually all transactions that are contained in it are
valid.
So everybody else is looking, or a node is looking, is that actually
valid, what this person did?
So is there a double spending in there?
If there's no double spending in there, then this, sorry, this block
is accepted.
And it's taken, it is extended by this node, by working on another
block.
And this other block is using a hash of the block that it just
received.
So as soon as you accept a block and work on a new block, you are
accepting the previous block, because you are working on the hash of
that block.
So this is what I said it there.
Now, this is the sequence of steps that is operating.
The question is, how do we actually get money?
So what is the incentive for maintaining the blockchain?
The first transaction in such a block, so I said there is this block,
and there are these transactions.
The first transaction actually provides you with money.
And it provides you with, at the moment, if you do that, you get 25
bitcoins per block.
I said at the moment, initially, you got 50 bitcoins for providing a
proof of work.
And the value of bitcoins that you get is halved, is divided by two,
every 210,000 blocks.
Sorry, I have to continue that.
We are done in a moment.
Every 210,000 blocks this value that you get for working on the block
is reduced by a factor of two.
And so the complete amount of money that you can actually generate, or
the number of bitcoins that you can generate, if you just sum up all
the bitcoins that you can generate initially for the first 210,000
blocks, you get 25 bitcoins for each block, and then 50, then 25, then
12.75 and so on.
So it's 12.5 and then and so on.
Different smaller values, it adds up to a limit of 21 million
bitcoins.
You cannot generate more.
And now this is a currency having a maximum of 21 million bitcoins.
Now you can do something with that.
And this is actually, it's evaluated on the stock market, or the
currency markets.
And currently 25 bitcoins are worth $25,000.
Yeah, so it's quite an amount.
And you can pay using bitcoins for online transactions, which like at
sites which accept bitcoins.
But everything depends on the ability of the availability of peers who
are willing to invest that work.
But the validation is done by the peer network.
There's nobody else controlling it.
It's based on the assumption there's a majority of honest notes.
Okay, that was bitcoins.
And then next week, we will finish that chapter on payment and start
with Internet of Energy.
Okay, yes, exactly.
I don't know.
Yeah, I don't know how they would certainly you could say, okay, then
I just provide you with the 0.5 Bitcoin, and then you could just
reduce the value.
So you can use a factor.
Yeah, but the real value that you get is reduced, the more people are
working on it.
Yeah, this is, I don't know whether that is actually is a sustainable
concept.
It doesn't look like it.
But it is an interesting concept.
At the moment, it is a hot discussion on whether that is actually
legal or something desirable, certainly not desirable by certain
financial institutions.
China is one of the biggest markets for that.
But the Chinese government has taken some measures to actually reduce
that.
Okay, thank you for your attention.