I think there are plenty of good descriptions of the basics of short selling here, but I wanted to help explain the "who are you borrowing from" aspect.
When you trade, you must trade through a broker-dealer. A broker-dealer is authorized to trade on behalf of it's customers. A broker-dealer must uphold certain regulatory requirements put in place by the SEC, and policed by a variety of government and non-government entities, including organizations like FINRA.
Originally, shorting was managed by the broker-dealers. It was the responsibility of the broker-dealer to manage finding an entity to "borrow" the stock from (usually a large institutional client). These institutional clients own very large positions in the stock, and the broker-dealer normally provides a guarantee that it will be returned. If for some reason this process was mismanaged, when the trades cleared and settled, there would be a "fail to deliver" (meaning they weren't able to come up with the stock) This is a severe problem for the broker-dealer, and can result in them losing their license. Abusing this system became known as "naked shorting" where you never made an attempt to "locate" (borrow) the stock. Naked shorting was severely curtailed in 2005 under Regulation SHO.
You may also be curious how a customer knows what stocks its broker-dealer can borrow. Originally there was a black-list of sorts called the Hard-To-Borrow list. This list was stocks that were relatively illiquid and that couldnt be shorted freely. If you wanted to short these, you had to request a "locate" from your broker for a specified number of shares, and they would go looking for someone to provide it, and confirm how many shares they could find. Under Regulation SHO, this changed to a white-list "Easy-To-Borrow" model where you were only allowed to short stocks on the list freely and had to request locates for the remainder of the symbol universe.
Finally - another interesting note on shorting called the "uptick rule". The uptick rule was originally put into place in the 1980's under Rule 390. This rule was built to prevent a stock from being run into the ground by repeatedly shorting it while the price was already falling. It required that in order to short, the previous print (quote) must have been higher than the one before (the stock was heading up). This really didn't help the problem too much, and was repealed in 2007.
One other point to note here: when you open a margin account at a brokerage, you are asked to sign a number of agreements such as a credit agreement (officially recognizing that you will be borrowing money and specifying the interest rate), a hypothecation agreement (pledging the assets of the account as collateral for the margin loan and permitting the brokerage to subsequently re-pledge them as collateral to a bank from which it borrows the money that it loans you), and a loan consent agreement, which gives the brokerage the right to loan your shores to clients who wish to borrow stock for short selling. The broker will certainly require you to sign the first two, but according to the regs, they cannot require you to sign the loan consent agreement. However, I didn't see an easy way to opt out of it when I signed up for my account with a discount broker and it didn't seem worth the hassle to navigate their customer service to opt out even though lending provides them with a profitable business which I, as the ultimate lender, am not compensated for.
In case the borrower fails to deliver, the broker lose license, ok understood, but what about the stock itself? Does the transaction gets rolled back? Or will the total number of shares be permanently increased at the cost of the broker's license?
When you trade, you must trade through a broker-dealer. A broker-dealer is authorized to trade on behalf of it's customers. A broker-dealer must uphold certain regulatory requirements put in place by the SEC, and policed by a variety of government and non-government entities, including organizations like FINRA.
Originally, shorting was managed by the broker-dealers. It was the responsibility of the broker-dealer to manage finding an entity to "borrow" the stock from (usually a large institutional client). These institutional clients own very large positions in the stock, and the broker-dealer normally provides a guarantee that it will be returned. If for some reason this process was mismanaged, when the trades cleared and settled, there would be a "fail to deliver" (meaning they weren't able to come up with the stock) This is a severe problem for the broker-dealer, and can result in them losing their license. Abusing this system became known as "naked shorting" where you never made an attempt to "locate" (borrow) the stock. Naked shorting was severely curtailed in 2005 under Regulation SHO.
You may also be curious how a customer knows what stocks its broker-dealer can borrow. Originally there was a black-list of sorts called the Hard-To-Borrow list. This list was stocks that were relatively illiquid and that couldnt be shorted freely. If you wanted to short these, you had to request a "locate" from your broker for a specified number of shares, and they would go looking for someone to provide it, and confirm how many shares they could find. Under Regulation SHO, this changed to a white-list "Easy-To-Borrow" model where you were only allowed to short stocks on the list freely and had to request locates for the remainder of the symbol universe.
Finally - another interesting note on shorting called the "uptick rule". The uptick rule was originally put into place in the 1980's under Rule 390. This rule was built to prevent a stock from being run into the ground by repeatedly shorting it while the price was already falling. It required that in order to short, the previous print (quote) must have been higher than the one before (the stock was heading up). This really didn't help the problem too much, and was repealed in 2007.